题目描述

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 $。

样例

input

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

output

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 $。