Description

$O2$ optimization is automatically enabled when submitting.

Little H wants you to maintain a sequence $a_1,a_2,\ldots,a_n$ of length $n$, and support:

• Update operation: change the value of all $a_i$ that satisfy $i\in[l,r]$ and $u\le a_i\le v$ to $w$.
• Query operation: compute $\sum_{i=l}^r a_i^t \bmod k$.

Input Format

There are $m+2$ lines in total.

The first line contains two positive integers $n,m$, representing the length of the sequence and the number of operations.

The second line contains $n$ positive integers $a_1,a_2\ldots,a_n$, representing the initial sequence.

The next $m$ lines each start with a number $o$, representing the operation type.

• If $o=0$, it means an update operation, followed by five positive integers $l,r,u,v,w$.
• If $o=1$, it means a query operation, followed by four positive integers $l,r,t,k$, with the meanings as described in the Description.

Numbers in each line are separated by a single space. The testdata is generated under Windows. There may be extra spaces at the end of lines.

Output Format

Output one integer per line, representing the XOR of the answers of all query operations (if there is no query operation, output $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

Hint

All numbers in the input are positive integers.
Assume there is a Constraints value $\mathrm{randmax}$ such that $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$.

It is guaranteed that, except for $n,m$ and the $t$ in test points $4,5$, the data is random. The meaning of each variable is as described in the Description.

Because the input size of this problem is large, and to avoid unnecessary judging time, please pay attention to input optimization. The following template is provided (c++ language):

/* ---- 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 ----- */

Calling the read() function reads an int integer from the input. Note that this template cannot handle negative numbers. When debugging, please use file input.

Translated by ChatGPT 5