题目背景

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

10 9
4 3 2 1 9 6 8 8 1 3 
0 4 8 3 10 9
1 1 3 2 973874498
0 10 10 5 9 6
1 7 9 3 738164087
1 1 10 1 694888198
0 2 2 4 7 7
0 1 6 1 3 3
1 1 10 3 868703567
1 4 9 3 545789338

525

提示

输入的所有数字均为正整数。
设存在数据范围 $\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++语言）：

/* ---- 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 (c<48||c>57) c=gc();
	while (c>47&&c<58) {r=(r<<3)+(r<<1)+(c^48); c=gc();} return r;
}
#undef gc
/* ---- read() & rlong() -- end ----- */

调用read()函数会从输入中读入一个int型整数，注意该模板不能处理负数，调试时请使用文件输入。