You are given two integers $$$n$$$ and $$$m$$$. For a sequence of $$$n$$$ integers $$$A=(a_1, a_2, \ldots, a_n)$$$, the parallel sums of $$$A$$$ are the $$$n-m+1$$$ integers $$$s_1, s_2, \ldots, s_{n-m+1}$$$ defined by $$$s_i = a_i + a_{i+1} + \ldots + a_{i+m-1}$$$ for each $$$i$$$ ($$$1 \leq i \leq n-m+1$$$).

You are given the values of $$$s_1, s_2, \ldots, s_{n-m+1}$$$. Your task is to answer $$$q$$$ queries, described as follows. In the $$$j$$$-th query, you are given two integers $$$l_j$$$ and $$$r_j$$$, and you are asked to find the smallest possible value of $$$\max(a_{l_j}, a_{l_j+1}, \ldots, a_{r_j})$$$ among all sequences $$$A=(a_1, a_2, \ldots, a_n)$$$ of $$$n$$$ integers (possibly negative) such that $$$s_1, s_2, \ldots, s_{n-m+1}$$$ are the parallel sums of $$$A$$$. Or determine if this value can be arbitrarily small.

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq m \leq n \leq 200\,000$$$).

The second line contains $$$n-m+1$$$ integers $$$s_1, s_2, \ldots, s_{n-m+1}$$$ ($$$-10^9 \leq s_i \leq 10^9$$$).

The third line contains a single integer $$$q$$$ ($$$1 \leq q \leq 100\,000$$$).

The $$$j$$$-th of the next $$$q$$$ lines contains two integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \leq l_j \leq r_j \leq n$$$).

Output

Output $$$q$$$ lines. The $$$j$$$-th line should contain the smallest possible value of $$$\max(a_{l_j}, a_{l_j+1}, \ldots, a_{r_j})$$$. If that value can be arbitrarily small, output unbounded instead.

Note

Explanation for the sample input/output #1

For the first query, take $$$A = (9, -4, -3, 2, 1, 2, 1, 1)$$$. The parallel sums of $$$A$$$ are $$$(4, -4, 2, 6, 5)$$$ as required. Then $$$\max(a_3, \ldots, a_7) = \max(-3, 2, 1, 2, 1) = 2$$$. It can be shown that $$$2$$$ is the smallest possible value.

For the second query, you can make the value arbitrarily small.

For the third query, take $$$A = (4, -3, 0, 3, -4, 3, 4, 2)$$$. Then $$$\max(4, -3, 0, 3, -4, 3, 4, 2) = 4$$$, which is the smallest possible value.

Parallel Sums

Examples