题目描述

Alice 和 Bob 在玩游戏。

现在有多堆石子，其中第 $k$ 堆石子有 $p_k$ 个，先后手轮流操作。取石子时，可以选任意一堆进行操作。若记 $i$ 为在这次取之前这堆石子的个数，$j$ 为这次要取的石子数，$R$ 为给定的常数，则需满足以下条件：

$$1 \leq i + j \leq R,i \geq j \geq 1$$

使对方无法操作者即为胜者。游戏时，双方都采用最优策略。

有多次游戏，具体来说，共有 $T$ 个操作，分为两类：

1. “change x” 表示将 $R$ 更改为 $x$。

2. “query n” 表示进行一次游戏，接下来有 $n$ 行，这 $n$ 行中的第 $i$ 行有两个正整数 $l_i$ 和 $r_i$，表示这次游戏的石子的堆数和个数可以用这 $n$ 个区间来表示。第 $i$ 个区间表示这次游戏的石子的堆数新增了 $(r_i - l_i + 1)$ 堆，并且其中这个区间所表示的第 $j(1 \leq j \leq r_i - l_i + 1)$ 堆的石子个数为 $(l_i + j - 1)$。

   例如当这次游戏的 $n = 2$，并且两个区间分别为 $[1, 7]$ 和 $[2, 3]$ 的时候，这次游戏一共有 $[(7 - 1 + 1) + (3 - 2 + 1)] = 9$ 堆石子，这 $9$ 堆石子的个数分别为 $1, 2, 3, 4, 5, 6, 7, 2, 3$。

由于 Bob 和 Alice 都非常聪明，而 Bob 希望不赢太多次，在适当的时候让让 Alice。因而他希望你帮他编写一个程序，对于每次游戏，如果先手有必胜策略输出“1”，否则输出“0”，你能做到吗？

输入格式

第一行有一个正整数 $T$，表示操作的个数。

接下来有 $T$ 个操作，格式如题所述。

输出格式

输出共一行，为一个长度小于 $T$ 的由字符 0 和 1 组成的字符串，含义如题所述。

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

提示

样例 1 说明

共有 $T=5$ 个操作。

第 1 个操作将 $R$ 改成了 3。

第 2 个操作表示进行了一次游戏，这次游戏的 $n=1$，区间为 $[2, 2]$，表示这次游戏共有 $(2 - 2 + 1) = 1$ 堆石子，这 1 堆石子的个数为 $(2 + 1 - 1) = 2$。因为 $R=3$，因此先手最多只能够取 1 个。若取 2 个则不满足 题目描述 中的条件 $1 \leq i + j \leq R$，若取 3 个及以上则不满足 题目描述 中的条件 $1 \leq i + j \leq R,i \geq j \geq 1$，其中 $i$、$j$、$R$ 的含义如题所述。先手取完后唯一的一堆只剩下 1 颗石子，因为后手取了 1 颗石子后使先手无法操作，所以先手落败，又因为这是唯一的一种取法，所以先手必败，因此先手无必胜策略，输出“0”。

第 3 个操作将 $R$ 改成了 4。

第 4 个操作表示进行了一次游戏，这次游戏的 $n=1$，区间为 $[2, 2]$，表示这次游戏共有 $(2 - 2 + 1) = 1$ 堆石子，这 1 堆石子的个数为 $(2 + 1 - 1) = 2$。先手最多可以取 2 颗石子，因为当先手取 3 颗或以上时，不满足 题目描述 中的条件 $1 \leq i + j \leq R,i \geq j \geq 1$，其中 $i$、$j$、$R$ 的含义如题所述。因为当先手选择取 2 颗石子时，先手取完了所有石子，使后手无法操作，所以先手必胜，输出“1”。

第 5 个操作将 $R$ 改成了 2。

---

数据范围

对于 $100\%$ 的数据，满足 $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$，并且第一个操作一定是第 1 类操作。

对于测试点 1~2 ，满足 $T \leq 10, l_i \leq r_i \leq 3$，并且在一轮游戏中石子的堆数不会超过 4。

对于测试点 3~6 ，满足 $T \leq 100, R \leq 100, \sum{n} \leq 100$。

对于测试点 7~10 ，满足 $T \leq 10, R \leq 10^5, \sum{n} \leq 50$。

对于测试点 11~12 ，满足 $R \leq 5 \times 10^3, \sum{n} \leq 5 \times 10^5$，并且只有一次修改操作。

对于测试点 13~16 ，满足 $T \leq 10^5,R \leq 10^5,\sum{n} \leq 5 \times 10^5$。

共 20 个测试点，每个测试点 5 分。

题目来源

「JYLOI Round 1」 E

Idea / Solution / Data：abcdeffa