Hay momentos así

Entrada

La primera línea contiene tres números enteros $n$, $k$, $q$ (1 \le n, k, q \le 10^6) — la longitud del arreglo $a$, el número $k$, y la cantidad de consultas.

La segunda línea contiene $n$ números enteros a_1, a_2, \dots, a_n (0 \le a_i \le 1) — el arreglo de Serguéi.

Cada una de las siguientes $q$ líneas contiene dos números enteros $l$ y $r$ (1 \le l; l+2 \cdot k-1 \le r \le n) — las consultas de Serguéi.

Salida

Debes responder a cada consulta. Si el arreglo no es bonito, debes imprimir «NO», de lo contrario imprimir «YES».

Ejemplos

Nota

Consulta $[1,10]$: Subarreglo [1,0,1,0,0,1,0,0,0,1]. Primer paso en $[1,6]$: el subarreglo [1,0,1,0,0,1] tiene $3$ ceros y $3$ unos, lo cambiamos \to [1,1,1,1,1,1,0,0,0,1]. Segundo paso en $[5,10]$. Respuesta: YES.

Consulta $[11,17]$: Subarreglo [0,1,1,1,1,0,0] — imposible cubrir todos los ceros con las operaciones permitidas. Respuesta: NO.

Consulta $[8,14]$: Subarreglo [0,0,1,0,1,1,1]. Paso en $[8,13]$: [0,0,1,0,1,1] — $3$ ceros, $3$ unos, un paso lo concluye. Respuesta: YES.

Consulta $[7,13]$: Subarreglo [0,0,0,1,0,1,1] — $4$ ceros, $3$ unos. Esto es imposible hacerlo. Respuesta: NO.

Consulta $[1,6]$: Subarreglo [1,0,1,0,0,1] — exactamente $3$ ceros y $3$ unos, un paso para todo el segmento. Respuesta: YES.

Puntuación

1. ($12$ puntos): q = 1; l_1 = 1; r_1 = n;

2. ($20$ puntos): n \le 10;

3. ($40$ puntos): n,q \le 5\,000;

4. ($68$ puntos): l_i = 1;

5. ($8$ puntos): k = 1;

6. ($44$ puntos): k \le 50;

7. ($32$ puntos): r_i - l_i + 1 = 4 \cdot k;

8. ($48$ puntos): Si la respuesta es «YES», esto se puede lograr solo en una operación.

9. ($128$ puntos): Sin restricciones adicionales.