题目描述

JOHNKRAM 和 C-SUNSHINE 在玩一个游戏。游戏规则如下：有若干堆石子，游戏前选定一个正整数 $p$，JOHNKRAM 先手，两个人轮流操作。定义一次操作是选择某一堆石子，然后拿出其中的 $p ^ k (k \in \mathbb{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 \leq 10$；
• 对于 $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$。