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

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

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

You may assume that Hazel recorded the values $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 $q$ pairs of plants. Sadly, you do not have access to the exhibition. Your only source of information is Hazel's notebook with the value $k$ and the sequence of values $r[0],\dots ,r[n-1]$.

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

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

Implementation details

You should implement the following procedure:

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

• $k$: the number of consecutive plants whose heights determine each individual value $r[i]$.
• $r$ : an array of size $n$, where $r[i]$ is the number of plants taller than plant $i$ among the next $k-1$ plants in clockwise order.
• This procedure is called exactly once, before any calls to compare_plants.

int compare_plants(int x, int y)

• $x,y$ : labels of the plants to be compared.
• This procedure should return:
  • $1$ if plant $x$ is definitely taller than plant $y$,
  • $-1$ if plant $x$ is definitely shorter than plant $y$,
  • $0$ if the comparison is inconclusive.
• This procedure is called exactly $q$ times.

Examples

Example 1

Consider the following call:

init(3, {0, 1, 1, 2})

Let's say the grader calls compare_plants(0, 2). Since $r[0]=0$ we can immediately infer that plant $2$ is not taller than plant $0$. Therefore, the call should return $1$.

Let's say the grader calls compare_plants(1, 2) next. For all possible configurations of heights that fit the constraints above, plant $1$ is shorter than plant $2$. Therefore, the call should return $-1$.

Example 2

Consider the following call:

init(2, {0, 1, 0, 1})

Let's say the grader calls compare_plants(0, 3). Since $r[3]=1$, we know that plant $0$ is taller than plant $3$. Therefore, the call should return $1$.

Let's say the grader calls compare_plants(1, 3) next. Two configurations of heights $[3,1,4,2]$ and $[3,2,4,1]$ are both consistent with Hazel's measurements. Since plant $1$ is shorter than plant $3$ in one configuration and taller than plant $3$ in the other, this call should return $0$.

Constraints

• $2\le k\le n\le 200000$
• $1\le q\le 200000$
• $0\le r[i]\le k-1$ $($for all $0\le i\le n-1)$
• $0\le x<y\le n-1$
• There exists one or more configurations of distinct heights of plants consistent with the array $r$.

Subtasks

1. ($5$ points) $k=2$
2. ($14$ points) $n\le 5000,2\cdot k>n$
3. ($13$ points) $2\cdot k>n$
4. ($17$ points) The correct answer to each call of compare_plants is $1$ or $-1$.
5. ($11$ points) $n\le 300,q\le \frac{n\cdot (n-1)}{2}$
6. ($15$ points) $x=0$ for each call of compare_plants.
7. ($25$ points) No additional constraints.

Sample grader

The sample grader reads the input in the following format:

• line $1$: $nkq$
• line $2$: $r[0]r[1]\dots r[n-1]$
• line $3+i$ $(0\le i\le q-1)$: $xy$ for the $i$-th call to compare_plants

The sample grader prints your answer in the following format:

• line $1+i$ $(0\le i\le q-1)$: return value of the $i$-th call to compare_plants.