Parallel Sums

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 \le i \le 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 \le m \le n \le 200\,000\)).

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

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

The \(j\)-th of the next \(q\) lines contains two integers \(l_j\) and \(r_j\) (\(1 \le l_j \le r_j \le 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.

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

2
unbounded
4
-1

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.