时间限制： 6.0 秒

空间限制： 1024 MB

题目描述

类似二进制下的异或操作，小 C 定义了一种 $k$ 进制下的异或运算 $\oplus_k$。

对于任意非负整数 $a,b$ 定义 $a$ 和 $b$ 进行 $k$ 进制下的不进位加法的结果为 $a\oplus_k b$。

形式化地，如果 $a=\sum\limits_{i=0}^n(a_i\cdot k^i),b=\sum\limits_{i=0}^n(b_i\cdot k^i)$，其中 $a_i,b_i$ 是小于 $k$ 的非负整数，则 $a\oplus_k b=\sum\limits_{i=0}^n(((a_i+b_i)\bmod k)\cdot k^i)$。

如计算 $11\oplus_3 7$ 的过程如下：$11$ 可表示为 $2\times 3^0+0\times 3^1+1\times 3^2$，$7$ 可表示为 $1\times 3^0+2\times 3^1+0\times 3^2$，则 $11\oplus_3 7=((2+1)\bmod 3)\times 3^0+((2+0)\bmod 3)\times 3^1+((0+1)\bmod 3)\times 3^2=0\times 3^0+2\times 3^1+1\times 3^2=15$。

之后小 C 在此运算基础上对任意非负整数 $n$ 定义了一个函数 $f$，具体如下：

$$ f(n)= \begin{cases} 0 & (n=0)\\ n\oplus_k f(n-1) & (n> 0) \end{cases} $$

现在小 C 有一个非负整数序列 $a_1,a_2,\cdots,a_n$ 和全局给定的奇数 $k$。小 C 希望对这个序列进行 $m$ 次操作：

• 操作一给出三个参数 $l,r,v$，表示将下标在区间 $[l,r]$ 内的 $a_i$ 修改为 $a_i \oplus_k v$。
• 操作二给出两个参数 $l,r$，表示查询 $f(a_l)\oplus_k f(a_{l+1})\oplus_k \cdots \oplus_k f(a_r)$。

输入格式

从标准输入读入数据。

第一行给出三个正整数 $n,m,k$。

接下来一行给出 $n$ 个非负整数，表示序列 $a$。

接下来 $m$ 行每行给出三个或者四个非负整数，表示 $m$ 次操作。

每行第一个数字为操作的类型 $t$。

• 如果 $t$ 为 $1$，则该操作为操作一，接下来给出三个非负整数 $l,r,v$ 作为该操作的参数。
• 如果 $t$ 为 $2$，则该操作为操作二，接下来给出两个正整数 $l,r$ 作为该操作的参数。

输出格式

输出到标准输出。

对于每个操作二，输出单独的一行，包含一个非负整数，为该操作的答案。

5 4 11
13 17 14 19 15
1 1 3 9
2 1 2
1 3 5 6
2 4 5

76
50

样例 1 解释

• 第一个操作结束之后，序列 $a$ 为：$[{\color{red}11},{\color{red}15},{\color{red}12},19,15]$。
• 第二个操作的答案为 $f(a_1)\oplus_{11}f(a_2)=11\oplus_{11} 65=76$。
• 第三个操作结束之后，序列 $a$ 为：$[11,15,{\color{red}18},{\color{red}14},{\color{red}21}]$。
• 第四个操作的答案为 $f(a_4)\oplus_{11}f(a_5)=50\oplus_{11} 0=50$。

样例 2

见题目文件区的 2.in 和 2.ans。

样例 2 解释

该样例满足子任务 1 的限制。

样例 3

见题目文件区的 3.in 和 3.ans。

样例 3 解释

该样例满足子任务 2 的限制。

样例 4

见题目文件区的 4.in 和 4.ans。

样例 4 解释

该样例满足子任务 3 的限制。

样例 5

见题目文件区的 5.in 和 5.ans。

样例 5 解释

该样例满足子任务 4 的限制。

子任务

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

对于所有数据满足：$1\le n\le 5 \times 10^{5},\ 1\le m \le 10^{4},\ 11\le k \le 10^{9}$ 且 $k$ 为奇数。对于每个操作保证 $t\in\{1,2\},1\le l\le r\le n$。对于任意时刻，保证 $a_i$ 非负。对于所有操作一，保证参数 $v$ 非负。记所有时刻序列中的元素 $a_i$​ 和所有操作一中的参数 $v$ 的最大值为 $R$，则保证 $R\le10^{12}$。

子任务编号	分值	$n\le$	$m\le$	特殊性质
1	20	$10^3$		$R\le 10^6$
2	30			无
3	20	$5\times 10^5$	$10^4$	$a_i$ 和操作一的参数 $v$ 均是 $k$ 的倍数
4	30			无

提示

子任务 3 可能有助于你更好地探索函数 $f$ 的相关性质。