The Adventures of Leopold the Cat
- Come out, you coward!
- Guys, let's live in harmony...
In this problem, Leopold has devised a game to teach the mice a lesson. The game involves a sequence of non-negative numbers with K elements. During each move, you can decrease any element of the sequence, except the first one, ensuring it remains non-negative, while simultaneously increasing the preceding element by the same amount. The player who cannot make a move loses. To simplify the process, they use a shared array of N natural numbers to derive the game sequence. The mice lazily write down numbers from position l to position r in a row, and then the clever Leopold selects an additional number from the remaining ones to append to the end of the sequence. This sequence becomes the starting point for the game. The mice always make the first move.
Your task is to determine if Leopold can choose a number to append to the sequence such that he can guarantee a win.
Input
The first line contains the number N (1 ≤ N ≤ 10^6)—the length of the array used by Leopold and the mice to select the game sequence. The following line contains N numbers, representing the array. Then, there are M (1 ≤ M ≤ 10^5) queries. Each of the next M lines contains three natural numbers, each not exceeding 10^9—x, l, r. If x is one, the numbers l and r define the subsequence chosen by the mice, and you must output "Yes" if Leopold can select the last number to ensure a win, and "No" otherwise. It is guaranteed that at least one number remains unchosen by the mice. If x is two, it indicates that the element at position l has been changed to r.
Output
For each query where x equals one, output "Yes" or "No".