Comparing Plants

문제

Hazel the botanist visited a special exhibition in the Singapore Botanical Gardens. In this exhibition, $nn$ plants of distinct heights are placed in a circle. These plants are labelled from $00$ to $n-1n-1$ in clockwise order, with plant $n-1n-1$ beside plant $00$.

For each plant $ii$ ($0\le i\le n-10\; \backslash leq\; i\; \backslash leq\; n-1$), Hazel compared plant $ii$ to each of the next $k-1k-1$ plants in clockwise order, and wrote down the number $r[i]r[i]$ denoting how many of these $k-1k-1$ plants are taller than plant $ii$. Thus, each value $r[i]r[i]$ depends on the relative heights of some $kk$ consecutive plants.

For example, suppose $n=5n=5$, $k=3k=3$ and $i=3i=3$. The next $k-1=2k-1\; =\; 2$ plants in clockwise order from plant $i=3i\; =\; 3$ would be plant $44$ and plant $00$. If plant $44$ was taller than plant $33$ and plant $00$ was shorter than plant $33$, Hazel would write down $r[3]=1r[3]\; =\; 1$.

You may assume that Hazel recorded the values $r[i]r[i]$ correctly. Thus, there is at least one configuration of distinct heights of plants consistent with these values.

You were asked to compare the heights of $qq$ pairs of plants. Sadly, you do not have access to the exhibition. Your only source of information is Hazel's notebook with the value $kk$ and the sequence of values $r[0],\dots ,r[n-1]r[0],\; \backslash ldots,\; r[n-1]$.

For each pair of different plants $xx$ and $yy$ that need to be compared, determine which of the three following situations occurs:

• Plant $xx$ is definitely taller than plant $yy$: in any configuration of distinct heights $h[0],\dots ,h[n-1]h[0],\; \backslash ldots,\; h[n\; -\; 1]$ consistent with the array $rr$ we have $h[x]>h[y]h[x]\; >\; h[y]$.
• Plant $xx$ is definitely shorter than plant $yy$: in any configuration of distinct heights $h[0],\dots ,h[n-1]h[0],\; \backslash ldots,\; h[n\; -\; 1]$ consistent with the array $rr$ we have .
• The comparison is inconclusive: neither of the previous two cases applies.