H. One Step Closer To The AK
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The one step we've taken is for the next step. And that one step, too, is for the next one step. Our will shall be succeeded endlessly just like that.
— Yuria

Two thousand years ago, someone took the first step towards defeating the Dark Lord. Now, Yuria and friends are continuing that journey. However, before they can defeat the Dark Lord, they must first defeat their crippling boredom, since as it turns out, riding on a wagon for months on end is not the most fun experience. Thus, Yuria has devised a game that she and her party can play while on the road. Yuria creates an array of $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) $$$1$$$'s and $$$0$$$'s, represented by the array $$$a_1, a_2, \ldots, a_N$$$ ($$$0 \le a_i \le 1$$$). Then, she will perform $$$Q$$$ ($$$1 \le Q \le 2 \cdot 10^5$$$) queries on the array:

  • "1 l r" — Flip the values of all values in the subarray $$$a_l, a_{l + 1}, \ldots, a_r$$$. Formally, set $$$a_i = (a_i + 1)\%2$$$ for all $$$l \le i \le r$$$.
  • "2 l r" — Play a game using the values in the subarray $$$a_l, a_{l + 1}, \ldots, a_r$$$, where players take turns selecting a maximal subarray containing either all $$$1$$$'s or all $$$0$$$'s and remove it. The player who cannot make a move loses. Note that any subarray a player chooses must be maximal, meaning that it cannot be contained by a larger subarray containing all $$$1$$$'s or all $$$0$$$'s. Since Yuria is not very responsible at cleaning up after herself, after playing the game, all of the values in the subarray will be reset to $$$0$$$, ie. $$$a_i = 0$$$ for all $$$l \le i \le r$$$. Please tell Yuria if she will win as the player who makes the first move.
Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N, Q \le 2 \cdot 10^5$$$).

The second line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$0 \le a_i \le 1$$$).

The next $$$Q$$$ lines each contain three integers $$$t$$$, $$$l$$$, and $$$r$$$ ($$$1 \le t \le 2$$$, $$$1 \le l \le r \le N$$$).

Output

For each query of type $$$t = 2$$$, output "YES" if the player who makes the first move will win, "NO" if the player who makes the second move will win, and "DRAW" if the game will end in a tie.

Example
Input
9 7
100111010
2 7 9
2 6 7
2 3 9
1 6 7
2 4 8
1 4 4
2 6 7
Output
YES
NO
YES
YES
YES
Note

The first query uses the subarray $$$010$$$, and it can be shown that Yuria will win as the first player.

After the first query, the subarray is reset to $$$0$$$, so the array will become $$$100111000$$$.

After the third query, the array values are $$$100000000$$$.

The fourth query flips the interval $$$[6, 7]$$$, so the array will become $$$100001100$$$.