Problem Description

Alice and Bob are playing a game.

There are multiple piles of stones. The $k$-th pile has $p_k$ stones. The two players take turns making moves. On each move, you may choose any pile to operate on. Let $i$ be the number of stones in the chosen pile before this move, let $j$ be the number of stones to take in this move, and let $R$ be a given constant. The following conditions must be satisfied:

The player who makes the opponent unable to move wins. During the game, both players use optimal strategies.

There are multiple games. Specifically, there are $T$ operations in total, divided into two types:

1. "change x" means changing $R$ to $x$.

2. "query n" means starting one game. Then there are $n$ lines. The $i$-th line contains two positive integers $l_i$ and $r_i$, meaning that the number of piles and their sizes in this game can be described by these $n$ intervals. The $i$-th interval adds $(r_i - l_i + 1)$ new piles to this game, and for the $j$-th pile in this interval $(1 \leq j \leq r_i - l_i + 1)$, the number of stones is $(l_i + j - 1)$.

For example, when $n = 2$ and the two intervals are $[1, 7]$ and $[2, 3]$, then this game has $[(7 - 1 + 1) + (3 - 2 + 1)] = 9$ piles, and the pile sizes are $1, 2, 3, 4, 5, 6, 7, 2, 3$.

Since both Bob and Alice are very smart, and Bob does not want to win too many times, he wants to "yield" to Alice at appropriate moments. Therefore, he wants you to write a program. For each game, output "1" if the first player has a winning strategy, otherwise output "0". Can you do it?

Input Format

The first line contains a positive integer $T$, meaning the number of operations.

Then there are $T$ operations, in the format described above.

Output Format

Output a single line: a string consisting of characters 0 and 1, with length less than $T$, whose meaning is as described above.

5
change 3
query 1
2 2
change 4
query 1
2 2
change 2

01

5
change 11
change 68
query 15
15 16
54 64
49 55
33 38
27 52
20 30
45 46
29 60
58 64
11 55
17 40
15 58
41 63
7 30
15 37
query 14
15 57
13 34
4 13
35 43
12 20
16 62
63 65
17 29
19 67
48 63
25 49
1 8
1 37
44 49
query 14
15 24
6 50
49 60
30 53
33 52
4 44
1 5
44 59
4 40
45 48
1 20
12 27
44 63
21 39

001

Hint

Sample 1 Explanation

There are $T=5$ operations in total.

The 1st operation changes $R$ to 3.

The 2nd operation starts a game. In this game, $n=1$ and the interval is $[2, 2]$, which means this game has $(2 - 2 + 1) = 1$ pile, and this pile has $(2 + 1 - 1) = 2$ stones. Since $R=3$, the first player can take at most 1 stone. If they take 2 stones, it does not satisfy the condition $1 \leq i + j \leq R$ in the Description. If they take 3 stones or more, it does not satisfy the condition $1 \leq i + j \leq R,i \geq j \geq 1$ in the Description. The meanings of $i$, $j$, and $R$ are as described above. After the first player takes stones, the only pile has 1 stone left. Then the second player takes 1 stone and makes the first player unable to move, so the first player loses. Since this is the only possible move, the first player is guaranteed to lose, so the first player has no winning strategy, and the output is "0".

The 3rd operation changes $R$ to 4.

The 4th operation starts a game. In this game, $n=1$ and the interval is $[2, 2]$, which means this game has $(2 - 2 + 1) = 1$ pile, and this pile has $(2 + 1 - 1) = 2$ stones. The first player can take at most 2 stones, because if the first player takes 3 stones or more, it does not satisfy the condition $1 \leq i + j \leq R,i \geq j \geq 1$ in the Description. The meanings of $i$, $j$, and $R$ are as described above. Since when the first player chooses to take 2 stones, they take all stones and make the second player unable to move, the first player must win, and the output is "1".

The 5th operation changes $R$ to 2.

Constraints

For $100\%$ of the data, it holds that $1 \leq T \leq 10^5, 2 \leq R \leq 10^{15}, 0 \leq l_i \leq r_i < R, 1 \leq \sum{n} \leq 5 \times 10^5$, and the first operation is guaranteed to be a type 1 operation.

For testdata 1~2, it holds that $T \leq 10, l_i \leq r_i \leq 3$, and in a single game the number of piles will not exceed 4.

For testdata 3~6, it holds that $T \leq 100, R \leq 100, \sum{n} \leq 100$.

For testdata 7~10, it holds that $T \leq 10, R \leq 10^5, \sum{n} \leq 50$.

For testdata 11~12, it holds that $R \leq 5 \times 10^3, \sum{n} \leq 5 \times 10^5$, and there is only one modification operation.

For testdata 13~16, it holds that $T \leq 10^5,R \leq 10^5,\sum{n} \leq 5 \times 10^5$.

There are 20 testdata points in total, 5 points each.

Source

"JYLOI Round 1" E

Idea / Solution / Data: abcdeffa

Translated by ChatGPT 5