409342: GYM103486 I Nim Game

Memory Limit:256 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Nim Gametime limit per test1.0 smemory limit per test256 megabytesinputstandard inputoutputstandard output

Diana is now playing a game with Ava called "Nim Game". They take turns removing stones from several piles. On each turn, a player must remove one or more stones from exactly one pile. The one who can't take any stone loses the game.

They play several rounds of the games on $$$N$$$ piles. The $$$i$$$-th pile contains $$$A_{i}$$$ stones. Each round, they play Nim game by selecting several piles (non-zero) from an interval $$$A_{l}, A_{l + 1}, \ldots, A_{r}$$$. Sometimes, they add $$$x$$$ stones to each pile in interval $$$A_{l}, A_{l + 1}, \ldots, A_{r}$$$. After that, the piles in the interval turns to $$$A_{l} + x, A_{l + 1} + x, \ldots, A_{r} + x$$$.

Ava plays first-hand in the game, and Diana chooses the piles to play the game. Please you help Diana to determine if there is a way to choose of piles to guarantee her sure win.

Input

The first line contains two positive integers $$$N (1 \le N \le 10^{5})$$$ and $$$M (1 \le M \le 10^{5})$$$, indicating the number of piles and the number of operations. The next line contains $$$N$$$ integers $$$A_{1}, A_{2}, \ldots, A_{n} (1 \le A_{i} \le 10^{9})$$$, indicating the number of stones in each pile.

The following $$$M$$$ lines describe all the operations. Each line describes one operation, and it is formatted in one of the two following formats, depends on the kind it is:

  • "$$$1\ l\ r\ x$$$" — Add $$$x$$$ stones to each pile in the interval $$$A_{l}, A_{l + 1}, \ldots, A_{r}$$$.
  • "$$$2\ l\ r$$$" — Query if there is a way to choose of piles to guarantee Diana's win if they play game on interval $$$A_{l}, A_{l + 1}, \ldots, A_{r}$$$.
It's guaranteed that $$$1 \le l \le r \le N, 1 \le x \le 10^{4}$$$.Output

For each query, if there is a way to choose of piles to guarantee Diana's win, output "Yes"; otherwise, output "No" (no quotes).

ExamplesInput
5 2
1 2 3 4 5
2 2 5
2 2 4
Output
Yes
No
Input
5 4
1 2 4 8 16
2 1 5
1 1 1 1
1 2 3 2
2 1 5
Output
No
Yes

加入题单

上一题 下一题 算法标签: