P6639 「JYLOI Round 1」让

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 组成的字符串，含义如题所述。

### 样例 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