Bəzən elə olur

Giriş

Birinci sətir $n$, $k$, $q$ (1 \le n, k, q \le 10^6) tam ədədlərini – $a$ massivinin uzunluğunu, $k$ ədədini və sorğuların sayını ehtiva edir.

İkinci sətir a_1, a_2, \dots, a_n (0 \le a_i \le 1) – Sergiyin massivini ehtiva edir.

Növbəti $q$ sətirin hər biri iki tam ədəd $l$ və $r$ (1 \le l; l+2 \cdot k-1 \le r \le n) ehtiva edir – Sergiyin sorğuları.

Çıxış

Hər sorğuya cavab verməlisiniz. Əgər massiv yaxşı deyilsə «NO», əks halda «YES» çıxarın.

Nümunələr

Qeyd

Sorğu $[1,10]$: Altseqment [1,0,1,0,0,1,0,0,0,1]. Birinci əməliyyat $[1,6]$-da: altseqment [1,0,1,0,0,1] var $3$ sıfır və $3$ birlərdən ibarətdir, çevrilir \to [1,1,1,1,1,1,0,0,0,1]. İkinci əməliyyat $[5,10]$-da. Cavab: YES.

Sorğu $[11,17]$: Altseqment [0,1,1,1,1,0,0] – icazə verilmiş əməliyyatlarla bütün sıfırları əhatə edə bilmək mümkün deyil. Cavab: NO.

Sorğu $[8,14]$: Altseqment [0,0,1,0,1,1,1]. Əməliyyat $[8,13]$-da: [0,0,1,0,1,1] – $3$ sıfır və $3$ birlərdən ibarətdir, bir əməliyyat tamamlayır. Cavab: YES.

Sorğu $[7,13]$: Altseqment [0,0,0,1,0,1,1] – $4$ sıfır, $3$ birlər. Bunu etmək mümkün deyil. Cavab: NO.

Sorğu $[1,6]$: Altseqment [1,0,1,0,0,1] – $3$ sıfır və $3$ birlərdən ibarət, bütün seqment üçün bir əməliyyat. Cavab: YES.

Bal hesablama

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

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

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

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

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

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

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

8. ($48$ bal): Əgər cavab «YES» olsa, bunu yalnız bir əməliyyatla etmək olar.

9. ($128$ bal): Əlavə məhdudiyyətlər olmadan.