给你两个整数 $$$n$$$ 和 $$$m$$$。对于 $$$n$$$ 整数序列 $$$A=(a_1, a_2, \ldots, a_n)$$$, 并行求和 是 $$$n-m+1$$$ 整数 $$$s_1, s_2, \ldots, s_{n-m+1}$$$ 定义为 $$$s_i = a_i + a_{i+1} + \ldots + a_{i+m-1}$$$ 对于每个 $$$i$$$ ($$$1 \leq i \leq n-m+1$$$)。
给定的值为 $$$s_1, s_2, \ldots, s_{n-m+1}$$$。您的任务是回答 $$$q$$$ 查询,如下所述。在第 $$$j$$$ 查询中,给定两个整数 $$$l_j$$$ 和 $$$r_j$$$,并要求你在所有序列 $$$A=(a_1, a_2, \ldots, a_n)$$$ 的 $$$n$$$ 整数(可能为负),使得 $$$s_1, s_2, \ldots, s_{n-m+1}$$$ 是 $$$A$$$ 的并行和。或者判断这个值是否可以任意小。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq m \leq n \leq 200\,000$$$)。
第二行包含 $$$n-m+1$$$ 整数 $$$s_1, s_2, \ldots, s_{n-m+1}$$$ ($$$-10^9 \leq s_i \leq 10^9$$$)。
第三行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 100\,000$$$)。
接下来的 $$$q$$$ 行的第 $$$j$$$ 行包含两个整数 $$$l_j$$$ 和 $$$r_j$$$ ($$$1 \leq l_j \leq r_j \leq n$$$)。
输出
输出 $$$q$$$ 行。第 $$$j$$$ 行应包含 $$$\max(a_{l_j}, a_{l_j+1}, \ldots, a_{r_j})$$$ 的最小可能值。如果该值可以任意小,则输出 无界 相反, 。
示例
输入复制
8 4 4 -4 2 6 5 4 3 7 4 6 1 8 2 5
输出复制
2 unbounded 4 -1
注意
示例输入/输出 #1 的说明
对于第一个查询,取 $$$A = (9, -4, -3, 2, 1, 2, 1, 1)$$$。根据要求,$$$A$$$ 的并行和为 $$$(4, -4, 2, 6, 5)$$$。那么 $$$\max(a_3, \ldots, a_7) = \max(-3, 2, 1, 2, 1) = 2$$$。可以证明 $$$2$$$ 是最小的可能值。
对于第二个查询,您可以将该值设置为任意小。
对于第三个查询,取 $$$A = (4, -3, 0, 3, -4, 3, 4, 2)$$$。那么 $$$\max(4, -3, 0, 3, -4, 3, 4, 2) = 4$$$,这是最小的可能值。