Comparing Plants

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

For each plant $i$ ($0 \leq i \leq n-1$), Hazel compared plant $i$ with each of the next $k-1$ plants in clockwise order and wrote down $r[i]$, the number of these $k-1$ plants that are taller than plant $i$. Each $r[i]$ therefore depends on the relative heights of $k$ consecutive plants.

For example, let $n=5$, $k=3$, and $i=3$. The next $k-1=2$ plants clockwise from plant $3$ are plants $4$ and $0$. If plant $4$ is taller than plant $3$ and plant $0$ is shorter than plant $3$, Hazel writes $r[3]=1$.

You may assume Hazel recorded every $r[i]$ correctly. At least one arrangement of distinct heights matches these values.

You need to compare the heights of $q$ pairs of plants. You cannot enter the exhibition. Your only information is the value $k$ and the sequence $r[0], \ldots, r[n-1]$ in Hazel's notebook.

For each pair of different plants $x$ and $y$, decide which of the following holds:

• Plant $x$ is definitely taller than plant $y$: in every arrangement of distinct heights $h[0], \ldots, h[n-1]$ consistent with $r$, $h[x] > h[y]$.
• Plant $x$ is definitely shorter than plant $y$: in every consistent arrangement, $h[x] < h[y]$.
• The comparison is inconclusive: neither of the above holds.

$2 \leq k \leq n \leq 200000$

$1 \leq q \leq 200000$

$0 \leq r[i] \leq k-1$ (for all $0 \leq i \leq n-1$)

$0 \leq x < y \leq n-1$

At least one arrangement of distinct heights is consistent with $r$.