CF2206E.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 \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.

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

$$s_i = a_i + a_{i+1} + \ldots + a_{i+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)$（元素可为负数）中，$\max(a_{l_j}, a_{l_j+1}, \ldots, a_{r_j})$ 的最小可能值；这里的“满足条件”指 $s_1, s_2, \ldots, s_{n-m+1}$ 恰好是 $A$ 的并行和。若该最小值可以任意小（即无下界），则需判定这一点。

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

输入的第一行包含两个整数 $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$）。

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.

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

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.

样例输入/输出 #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$，这是可能的最小值。