Sometimes it happens

Input

The first line contains three integers $n$, $k$, $q$ (1 \le n, k, q \le 10^6) — the length of the array $a$, the number $k$, and the number of queries.

The second line contains $n$ integers a_1, a_2, \dots, a_n (0 \le a_i \le 1) — Sergey’s array.

Each of the next $q$ lines contains two integers $l$ and $r$ (1 \le l; l+2 \cdot k-1 \le r \le n) — Sergey’s queries.

Output

You need to answer each query. If the array is not good, output «NO», otherwise output «YES».

Examples

Note

Query $[1,10]$: Subarray [1,0,1,0,0,1,0,0,0,1]. First move on $[1,6]$: subarray [1,0,1,0,0,1] has $3$ zeros and $3$ ones, repaint \to [1,1,1,1,1,1,0,0,0,1]. Second move on $[5,10]$. Answer: YES.

Query $[11,17]$: Subarray [0,1,1,1,1,0,0] — it is impossible to cover all zeros with permissible operations. Answer: NO.

Query $[8,14]$: Subarray [0,0,1,0,1,1,1]. Move on $[8,13]$: [0,0,1,0,1,1] — $3$ zeros, $3$ ones, one move completes. Answer: YES.

Query $[7,13]$: Subarray [0,0,0,1,0,1,1] — $4$ zeros, $3$ ones. This is impossible to accomplish. Answer: NO.

Query $[1,6]$: Subarray [1,0,1,0,0,1] — exactly $3$ zeros and $3$ ones, one move for the entire segment. Answer: YES.

Scoring

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

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

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

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

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

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

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

8. ($48$ points): If the answer is «YES», then it can be done in just one operation.

9. ($128$ points): Without additional constraints.