#6138. 「2017 山东三轮集训 Day4」Right

内存限制:512 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

JOHNKRAM和 C-SUNSHINE 在玩一个游戏。游戏规则如下:有若干堆石子,游戏前选定一个正整数 p ,JOHNKRAM 先手,两个人轮流操作。定义一次操作是选择某一堆石子,然后拿出其中的 p ^ k (k \in N) 个石子扔掉,不能操作者输。

C_SUNSHINE 表示判定谁能赢太简单了,于是他放了 n 堆石子,编号为 1 \sim n 。他每次把编号在某个区间内的石子堆加上若干个石子,或者询问以编号在某个区间内的石子堆进行游戏,是谁胜利。JOHNKRAM 表示他不会做,于是他来向你求助。

输入格式

第一行三个数 n, q, p n 表示序列的长度, q 表示接下来操作的次数, p 的意义如题目描述中所说。
接下来一行 n 个数,第 i 个数表示初始时第 i 堆石子的石子数量。
接下来 q 行每行第一个数 t 表示操作类型, t = 0 表示修改, t = 1 表示询问。
对于一个修改操作,该行还会有三个数 l, r, x ,表示把 [l \ldots r] 的所有石子堆加上 x 个石子。
对于一个询问操作,该行还会有两个数 l, r ,表示询问以 [l \ldots r] 的所有石子堆进行游戏是谁胜。

输出格式

对于每一个询问操作,如果 JOHNKRAM 胜利则输出 1 ,否则输出 0

样例

样例输入

10 9 3
2 6 2 5 8 7 4 3 4 1
1 1 10
0 5 7 15
1 1 3
0 3 9 11
1 3 7
0 4 5 53
0 1 2 26
1 6 10
1 4 9

样例输出

0
0
0
1
0

数据范围与提示

对于 10\% 的数据, n,q \leq10
对于 20\% 的数据, n,q \leq 1 \times 10 ^ 2
对于 30\% 的数据, n,q \leq 5 \times 10 ^ 3
对于 40\% 的数据, n,q \leq 5 \times 10 ^ 4
对于 50\% 的数据, n,q \leq 7 \times 10 ^ 4
对于 60\% 的数据, n,q \leq 8 \times 10 ^ 4
对于另外 10\% 的数据,所有修改的 l r 相同;
对于另外 10\% 的数据,所有询问的 l r 相同;
对于另外 10\% 的数据, p \leq 10 ^ 2
对于 100\% 的数据, 1 \leq n,q,p \leq 10 ^ 5 ,每一堆石子的初始数量 \leq 10 ^ 5