给你两个整数 $n$ 和 $m$。对于一个长度为 $n$ 的整数序列 $A = (a_1, a_2, \dots, a_n)$，$A$ 的并行和（parallel sums）是指 $n - m + 1$ 个整数 $s_1, s_2, \dots, s_{n-m+1}$，其定义为：对于每个 $i$（$1 \le i \le n - m + 1$），$s_i = a_i + a_{i+1} + \dots + a_{i+m-1}$。

现在给定 $s_1, s_2, \dots, s_{n-m+1}$ 的值。你的任务是回答 $q$ 个询问。在第 $j$ 个询问中，给定两个整数 $l_j$ 和 $r_j$，你需要求出在所有满足 $s_1, s_2, \dots, s_{n-m+1}$ 是其并行和的长度为 $n$ 的整数（可能为负数）序列 $A = (a_1, a_2, \dots, a_n)$ 中，$\max(a_{l_j}, a_{l_j+1}, \dots, a_{r_j})$ 的最小可能值。或者判断该值是否可以任意小。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 200\,000$）。

第二行包含 $n - m + 1$ 个整数 $s_1, s_2, \dots, s_{n-m+1}$（$-10^9 \le s_i \le 10^9$）。

第三行包含一个整数 $q$（$1 \le q \le 100\,000$）。

接下来的 $q$ 行中，第 $j$ 行包含两个整数 $l_j$ 和 $r_j$（$1 \le l_j \le r_j \le n$）。

输出格式

输出 $q$ 行。第 $j$ 行应包含 $\max(a_{l_j}, a_{l_j+1}, \dots, a_{r_j})$ 的最小可能值。如果该值可以任意小，则输出 unbounded。

样例

输入样例 1

8 4
4 -4 2 6 5
4
3 7
4 6
1 8
2 5

输出样例 1

2
unbounded
4
-1

说明

对于第一个询问，可以取 $A = (9, -4, -3, 2, 1, 2, 1, 1)$。此时 $A$ 的并行和为 $(4, -4, 2, 6, 5)$，符合要求。此时 $\max(a_3, \dots, a_7) = \max(-3, 2, 1, 2, 1) = 2$。可以证明 $2$ 是最小可能值。

对于第二个询问，可以使该值任意小。

对于第三个询问，可以取 $A = (4, -3, 0, 3, -4, 3, 4, 2)$。此时 $\max(a_1, \dots, a_8) = \max(4, -3, 0, 3, -4, 3, 4, 2) = 4$，这是最小可能值。