题目描述

植物学家 Hazel 参观过新加坡植物园的一个特别展览。在这次展览中，有 $n$ 棵高度互不相同的植物，它们排成了一个圆。这些植物按顺时针方向从 $0$ 到 $n-1$ 编号，植物 $n-1$ 与植物 $0$ 是相邻的。

对于每棵植物 $i$ $(0 \le i \le n-1)$，Hazel 将它与顺时针方向的后 $k-1$ 棵植物进行比较，记录下数值 $r_i$ 以表示这 $k-1$ 棵植物中有多少棵的高度大于植物 $i$。因此，每个 $r_i$ 的数值是由某段连续 $k$ 棵植物的相对高度决定的。

例如，假设 $n=5$，$k=3$，$i=3$。植物 $3$ 顺时针方向的后 $k-1=2$ 棵植物是植物 $4$ 和植物 $0$。如果植物 $4$ 比植物 $3$ 高，且植物 $0$ 比植物 $3$ 矮，那么 Hazel 将会记录 $r_3 = 1$。

你可以假设 Hazel 记录的数值 $r_i$ 都是正确的。也就是说，这些植物至少存在一组互不相同的高度符合 Hazel 所记录的数值。

本题要求你比较 $q$ 对植物的高度。由于你没有机会参观这次展览，你仅有的信息来源是 Hazel 的笔记本，其中记录了 $k$ 和序列 $r_0, \ldots, r_{n-1}$ 的值。
对于每对需要比较的植物 $x$ 和 $y$（$x$ 和 $y$ 不同），判定它们符合以下哪种情况：

1. 植物 $x$ 一定比植物 $y$ 高：对于任意一组符合数组 $r$ 且互不相同的高度 $h_0, \ldots, h_{n-1}$，都有 $h_x > h_y$。
2. 植物 $x$ 一定比植物 $y$ 矮：对于任意一组符合数组 $r$ 且互不相同的高度 $h_0, \ldots, h_{n-1}$，都有 $h_x < h_y$。
3. 该比较没有定论：以上两种情况都不成立。

实现细节

要求你实现以下函数：

• void init(int k, int[] r)

  • $k$：决定每个 $r_i$ 数值的连续植物的棵数。
  • $r$：一个大小为 $n$ 的数组，其中 $r_i$ 是植物 $i$ 顺时针方向的后 $k-1$ 棵植物中比它高的棵数。
  • 该函数恰好被调用一次，且在对 compare_plants 的任何调用之前。

• int compare_plants(int x, int y)

  • $x, y$：待比较的植物的编号。
  • 该函数应该返回：
    • $1$：如果植物 $x$ 一定比植物 $y$ 高，
    • $-1$：如果植物 $x$ 一定比植物 $y$ 矮，
    • $0$：如果该比较没有定论。
  • 该函数恰好被调用 $q$ 次。

评测程序示例

评测程序示例以如下格式读取输入数据：

• 第 $1$ 行：$n\ k\ q$
• 第 $2$ 行：$r_0\ r_1\ \ldots\ r_{n-1}$
• 第 $3+i$ $(0 \le i \le q-1)$ 行：$x\ y$，表示第 $i$ 次调用 compare_plants 时的参数

评测程序示例以如下格式打印你的答案：

• 第 $1+i$ $(0 \le i \le q-1)$ 行: 第 $i$ 次调用 compare_plants 的返回值

---

样例 1

输入

4 3 2
0 1 1 2
0 2
1 2

输出

1
-1

解释
考虑以下调用：

• init(3, [0, 1, 1, 2])
• 假设评测程序调用了 compare_plants(0, 2)。由 $r_0=0$ 可以推断植物 $2$ 不比植物 $0$ 高，因此该调用应该返回 $1$。
• 假设评测程序接下来调用了 compare_plants(1, 2)。由于对每组符合以上条件的植物高度，都有植物 $1$ 比植物 $2$ 矮，因此该调用应该返回 $-1$。

---

样例 2

输入

4 2 2
0 1 0 1
0 3
1 3

输出

1
0

解释
考虑以下调用：

• init(2, [0, 1, 0, 1])
• 假设评测程序调用了 compare_plants(0, 3)。由 $r_3=1$ 可以推断植物 $0$ 比植物 $3$ 高，因此该调用应该返回 $1$。
• 假设评测程序接下来调用了 `compare_plants(1, 3)$。两组高度$[3,1,4,2]$和$[3,2,4,1]$ 都符合 Hazel 的观测记录，由于在第一种情况中植物 $1$ 比植物 $3$ 矮，而在第二种情况中它比植物 $3$ 高，因此该调用应该返回 $0$。

---

数据范围与提示

对于 $100\%$ 的数据，满足：

• $2 \le k \le n \le 200\,000$
• $1 \le q \le 200\,000$
• $0 \le r_i \le k-1$（对所有 $0 \le i \le n-1$）
• $0 \le x < y \le n-1$
• 存在一组或多组互不相同的高度符合数组 $r$ 记录的情况

子任务

子任务	附加限制	分值
1	$k=2$	5
2	$n \le 5000$，$2 \cdot k > n$	14
3	$2 \cdot k > n$	13
4	每次 compare_plants 调用的正确答案是 $1$ 或 $-1$	17
5	$n \le 300$，$q \le \frac{n \cdot (n-1)}{2}$	11
6	每次调用 compare_plants 时有 $x=0$	15
7	没有附加约束条件	25