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

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% $ 的数据，$ 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 $。