题目描述

長さ $N$ の整数列 $A\ =\ (A_1,\ A_2,\ \ldots,\ A_N)$ と正整数 $K$ が与えられます。

各 $i\ =\ 1,\ 2,\ \ldots,\ Q$ について、$A$ の連続部分列 $(A_{l_i},\ A_{l_i+1},\ \ldots,\ A_{r_i})$ が良い数列かどうかを判定してください。

ここで、長さ $n$ の数列 $X\ =\ (X_1,\ X_2,\ \ldots,\ X_n)$ は、下記の操作を好きな回数（ $0$ 回でも良い）だけ行うことによって、$X$ のすべての要素を $0$ にすることができるとき、かつ、そのときに限り良い数列です。

$1\ \leq\ i\ \leq\ n-K+1$ を満たす整数 $i$ および、整数 $c$ （負の数でも良い）を選び、$K$ 個の要素 $X_{i},\ X_{i+1},\ \ldots,\ X_{i+K-1}$ のそれぞれに $c$ を加算する。

なお、すべての $i\ =\ 1,\ 2,\ \ldots,\ Q$ について、$r_i\ -\ l_i\ +\ 1\ \geq\ K$ が保証されます。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$ $Q$ $l_1$ $r_1$ $l_2$ $r_2$ $\vdots$ $l_Q$ $r_Q$

输出格式

$Q$ 行出力せよ。 $i\ =\ 1,\ 2,\ \ldots,\ Q$ について、$i$ 行目には数列 $(A_{l_i},\ A_{l_i+1},\ \ldots,\ A_{r_i})$ が良い数列である場合は Yes を、 そうでない場合は No を出力せよ。

题目大意

给定一个长为 $N$ 的序列，常数 $k$， $M$ 次询问，判断 $[l, r]$ 内的子序列是否为 $good$ 序列
一个序列被认为为 $good$ 序列，当且仅当用以下操作可以使 该序列的所有元素值都变为 $0$

选定两个整数 $c$ , $i$ ，使区间 $[i, i + k - 1]$ 内的元素同时减去 $c$

对于每次询问，输出 ${Yes}$ 或者 ${No}$

7 3
3 -1 1 -2 2 0 5
2
1 6
2 7

Yes
No

20 4
-19 -66 -99 16 18 33 32 28 26 11 12 0 -16 4 21 21 37 17 55 -19
5
13 16
4 11
3 12
13 18
4 10

No
Yes
No
Yes
No

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ K\ \leq\ \min\lbrace\ 10,\ N\ \rbrace$
• $-10^9\ \leq\ A_i\ \leq\ 10^9$
• $1\ \leq\ Q\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ l_i,\ r_i\ \leq\ N$
• $r_i-l_i+1\ \geq\ K$
• 入力はすべて整数

Sample Explanation 1

数列 $ X\ \coloneqq\ (A_1,\ A_2,\ A_3,\ A_4,\ A_5,\ A_6)\ =\ (3,\ -1,\ 1,\ -2,\ 2,\ 0) $ は良い数列です。 実際、下記の手順で操作を行うことで、すべての要素を $0$ にすることができます。 - まず、$i\ =\ 2,\ c\ =\ 4$ として操作を行う。その結果、$X\ =\ (3,\ 3,\ 5,\ 2,\ 2,\ 0)$ となる。 - 次に、$i\ =\ 3,\ c\ =\ -2$ として操作を行う。その結果、$X\ =\ (3,\ 3,\ 3,\ 0,\ 0,\ 0)$ となる。 - 最後に、$i\ =\ 1,\ c\ =\ -3$ として操作を行う。その結果、$X\ =\ (0,\ 0,\ 0,\ 0,\ 0,\ 0)$ となる。 よって、$1$ 行目には Yes を出力します。 一方、数列 $ (A_2,\ A_3,\ A_4,\ A_5,\ A_6,\ A_7)\ =\ (-1,\ 1,\ -2,\ 2,\ 0,\ 5) $ は、 どのような手順で操作を行ってもすべての要素を $0$ にすることはできないため、良い数列ではありません。 よって、$2$ 行目には No を出力します。