Plant Height Comparisons

Botanist Hazel visited a special exhibition at the Singapore Botanic Gardens. In the exhibition there were \(n\) plants with distinct heights arranged in a circle. The plants are labeled \(0,1,\ldots,n-1\) in clockwise order (with plant \(n-1\) adjacent to plant \(0\)).

For each plant \(i\) \((0\le i\le n-1)\) Hazel compared it with the next \(k-1\) plants in clockwise order and recorded a value \(r[i]\) defined as the number of these \(k-1\) plants that have height greater than plant \(i\). In other words, for each contiguous block of \(k\) plants (starting at \(i\) and including its successive \(k-1\) plants modulo \(n\)), if we sort the heights in descending order then the rank of plant \(i\) is \(r[i]+1\). Note that if \(r[i]=0\) then plant \(i\) is the highest among these \(k\) plants, and if \(r[i]=k-1\) then it is the lowest.

You are given the integer \(k\) and the array \(r[0],r[1],\ldots,r[n-1]\) (which is guaranteed to be correct, i.e. there exists at least one assignment of distinct heights satisfying these numbers). Your task is to answer \(q\) queries. In each query you are given two (distinct) plant indices \(x\) and \(y\), and you need to decide which one of the following is true:

• Plant \(x\) must be taller than plant \(y\): for any valid assignment of heights \(h[0],\ldots, h[n-1]\) satisfying the data, \(h[x] > h[y]\).
• Plant \(x\) must be shorter than plant \(y\): for any valid assignment, \(h[x] < h[y]\).
• The relative order between \(x\) and \(y\) cannot be determined.

The following functions must be implemented:

void init(int k, std::vector<int> r)

where

• k is the length of the contiguous block used to compute \(r[i]\).
• r is an array of size \(n\) with \(r[i]\) defined as above.

and

int compare_plants(int x, int y)

where \(x\) and \(y\) are indices of two plants. This function should return:

• 1 if plant \(x\) must be taller than plant \(y\),
• -1 if plant \(x\) must be shorter than plant \(y\),
• 0 if the comparison is indeterminate.

Implementation detail: The function init is called exactly once before any calls to compare_plants, and compare_plants is called exactly \(q\) times. It is guaranteed that the given \(r\) array is consistent (i.e. there is at least one valid assignment of distinct heights satisfying all the recorded values).

---

Observation and Strategy:

Each recorded value \(r[i]\) comes from the contiguous block of \(k\) plants \(i, i+1, \ldots, i+k-1 \) (indices taken modulo \(n\)). Notice that if \(r[i] = 0\), then plant \(i\) is the highest in that block and thus \(h[i] > h[j]\) for every other plant \(j\) in that block. Similarly, if \(r[i] = k-1\), then plant \(i\) is the lowest in its block and we have \(h[i] < h[j]\) for every other plant \(j\) in that block.

One method to decide a query is to build a directed graph with vertices representing the plants. For each \(i\), for every \(j\) in the block \(i+1, i+2, \ldots, i+k-1\) (modulo \(n\)):

• If \(r[i] = 0\), add an edge from \(i\) to \(j\) (indicating \(h[i] > h[j]\)).
• If \(r[i] = k-1\), add an edge from \(j\) to \(i\) (indicating \(h[j] > h[i]\)).

After adding these edges, compute the transitive closure (i.e. if there is a path from \(x\) to \(y\) then \(h[x] > h[y]\) in every valid height assignment). Then, for each query:

• If there is a path from \(x\) to \(y\), answer 1.
• If there is a path from \(y\) to \(x\), answer -1.
• Otherwise, answer 0.
</p>

This strategy will be sufficient to decide the comparisons that are forced by the records.

inputFormat

The input is given via standard input and has the following format:

 n k
 r[0] r[1] ... r[n-1]
 q
 x1 y1
 x2 y2
 ...
 xq yq

Here, \(n\) is the number of plants (\(n = r.size()\)).

outputFormat

For each of the \(q\) queries, output one line containing 1 if plant \(x\) must be taller than plant \(y\), -1 if it must be shorter, and 0 if the relative order cannot be determined.

sample

5 3
0 2 0 2 1
4
0 1
2 4
1 3
0 4

1
1
-1
1

</p>