Alice and Bob Stone Game

Alice and Bob are playing a game with several piles of stones. Initially, each pile k has p_k stones. The players take turns; on a turn, a player may choose any pile and remove a number of stones subject to the following rule:

If the chosen pile currently has i stones and the player removes j stones, then letting R be a given constant, the move is legal if and only if

$$1 \le i + j \le R, \quad i \ge j \ge 1.$$

In other words, in a move on a pile with i stones, the player may remove any number j satisfying

$$1 \le j \le \min(i, R-i).$$

The pile then becomes i - j (possibly 0). A player who is unable to make a move loses the game. Both players play optimally.

There are T operations. Each operation is one of the following two types:

1. change x: Update the constant R to x.
2. query n: This represents playing a game. The next n lines each contain two positive integers l_i and r_i. These n intervals describe the piles used in this game. For each interval [l, r], exactly (r - l + 1) new piles are added; the j-th pile in this interval has (l + j - 1) stones. For example, if n = 2 and the two intervals are [1, 7] and [2, 3], then the game has 7 + 2 = 9 piles with stone counts: 1, 2, 3, 4, 5, 6, 7, 2, 3.

For each game (i.e. each query operation), if the first player (the one who moves first) has a winning strategy then output 1, otherwise output 0. Note that both players play optimally.

Hint: The game for each pile is impartial. Denote by g(p) the Grundy value of a pile with p stones. For a pile with p stones (with p < R), the allowed moves are to remove any j stones, where 1 ≤ j ≤ \min(p, R-p), leaving a pile of p - j stones. For any pile with p ≥ R, no move is possible so g(p) = 0. The overall position is the nim-sum of the Grundy values of all piles.

inputFormat

The first line contains a positive integer T, the number of operations. Each of the following operations is in one of the following two formats:

• change x: Update the constant R to x.
• query n: Indicates a game query. It is followed by n lines, each containing two positive integers l_i and r_i, representing an interval as described above.

It is guaranteed that the test cases contain more than 2 cases and all fields are non-empty.

outputFormat

For each query operation, output a single line containing 1 if the first player can force a win under optimal play, or 0 otherwise.

sample

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

0
1
1

</p>