P7134 小 H 的序列

小 H 有一个序列。

**提交时自动开启 O2 优化。** 小 H 想让你维护一个长为 $n$ 序列 $a_1,a_2,\ldots,a_n$，要求支持 - 修改操作：将所有满足$i\in[l,r]$且$u\le a_i\le v$的$a_i$的值修改为$w$； - 查询操作：求出$\sum_{i=l}^ra_i^t\bmod k$。

总共包括 $m+2$ 行。 第一行包含两个正整数 $n,m$，分别表示序列长度和操作次数。 第二行包含 $n$ 个正整数 $a_1,a_2\ldots,a_n$，表示最初的序列。 接下来的 $m$ 行，每行由一个数 $o$ 开头，表示操作类型。 - 如果 $o=0$，表示修改操作，紧接着给出五个正整数 $l,r,u,v,w$； - 如果 $o=1$，表示查询操作，紧接着给出四个正整数 $l,r,t,k$，意义如【题目描述】中所述。 每行的两个数字间由单个空格隔开，数据在 Windows 下生成。**行末不保证没有多余空格**。

一行一个整数，表示所有查询操作的答案的异或和（如果没有查询操作输出一个数 $0$）。

输入的所有数字均为正整数。 设存在数据范围 $\mathrm{randmax}$，满足 $n,m,a_i,w\le\mathrm{randmax},1\le l\le r\le n,1\le u\le v\le \mathrm{randmax},1\le t,k\le10^9$。  保证数据除 $n,m$ 以及测试点 $4,5$ 的 $t$ 外随机，各变量意义如【题目描述】中所述。 由于本题输入量较大及为了省下不必要的评测耗时，请注意输入优化。在此给出以下模板（`c++`语言）： ```cpp /* ---- read() & rlong() - begin ---- */ #define gc() (p0==p1&&(p1=(p0=buf)+fread(buf,1,1048576,stdin),p0==p1)?EOF:*p0++) char buf[1048576],*p0,*p1; inline int read() { int r=0; char c=gc(); while (c57) c=gc(); while (c>47&&c