题目描述

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.

输入格式

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 $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.