Часом буває так

Вхідні дані

Перший рядок містить три цілі числа $n$ , $k$ , $q$ $(1 \leq n, k, q \leq 1 0^{6})$ (1 \le n, k, q \le 10^6) — довжина масиву $a$ , число $k$ , та кількість запитів.

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n $(0 \leq a_{i} \leq 1)$ (0 \le a_i \le 1) — масив Сергія.

Кожен з наступних $q$ рядків містить по два цілі числа $l$ та $r$ $(1 \leq l; l + 2 \cdot k - 1 \leq r \leq n)$ (1 \le l; l+2 \cdot k-1 \le r \le n) — запити Сергія.

Вихідні дані

Потрібно відповісти на кожен запит. Якщо масив не гарний, то потрібно вивести «NO», інакше вивести «YES».

Приклади

Приклад 1

Loading

Примітка

Запит $[1, 10]$ : Підмасив $[1, 0, 1, 0, 0, 1, 0, 0, 0, 1]$ [1,0,1,0,0,1,0,0,0,1]. Перший хід на $[1, 6]$ : підмасив $[1, 0, 1, 0, 0, 1]$ [1,0,1,0,0,1] має $3$ нулі та $3$ одиниці, перефарбовуємо $\to [1, 1, 1, 1, 1, 1, 0, 0, 0, 1]$ \to [1,1,1,1,1,1,0,0,0,1]. Другий хід на $[5, 10]$ . Відповідь: YES.

Запит $[11, 17]$ : Підмасив $[0, 1, 1, 1, 1, 0, 0]$ [0,1,1,1,1,0,0] — неможливо покрити всі нулі допустимими операціями. Відповідь: NO.

Запит $[8, 14]$ : Підмасив $[0, 0, 1, 0, 1, 1, 1]$ [0,0,1,0,1,1,1]. Хід на $[8, 13]$ : $[0, 0, 1, 0, 1, 1]$ [0,0,1,0,1,1] — $3$ нулі, $3$ одиниці, один хід завершує. Відповідь: YES.

Запит $[7, 13]$ : Підмасив $[0, 0, 0, 1, 0, 1, 1]$ [0,0,0,1,0,1,1] — $4$ нулі, $3$ одиниці. Це зробити неможливо. Відповідь: NO.

Запит $[1, 6]$ : Підмасив $[1, 0, 1, 0, 0, 1]$ [1,0,1,0,0,1] — рівно $3$ нулі та $3$ одиниці, один хід на весь відрізок. Відповідь: YES.

Оцінювання

( $12$ балів): $q = 1$ q = 1; $l_{1} = 1$ l_1 = 1; $r_{1} = n$ r_1 = n;
( $20$ балів): $n \leq 10$ n \le 10;
( $40$ балів): $n, q \leq 5000$ n,q \le 5\,000;
( $68$ балів): $l_{i} = 1$ l_i = 1;
( $8$ балів): $k = 1$ k = 1;
( $44$ бали): $k \leq 50$ k \le 50;
( $32$ бали): $r_{i} - l_{i} + 1 = 4 \cdot k$ r_i - l_i + 1 = 4 \cdot k;
( $48$ балів): Якщо відповідь «YES», то це можна зробити лише за одну операцію.
( $128$ балів): Без додаткових обмежень.