8522: Pandaemonium Asphodelos: The First Circle (Savage)

Oops, there is something wrong with the Pandaemonium. The friend of Azem, Themis, is just waiting for you to have a look together.

Oh no, rattled Erichthonios, who is the guard of Pandaemonium, misunderstanding you as enemies, starts attacking you. Can you protect yourself and Themis until he calms down?

To simplify the problem, Themis' defending system have $n$ blocks in a line. All the blocks have a initial weight 0 and the same attribute. Erichthonios will perform following 4 kinds of attack $q$times:

• $1$ $x$ $c$: Erichthonios uses his chain to connect the $x$-th block and all $\mathbf{closest}$ $2c$ blocks, giving them a new attribute (overlapping the origin atrributes of the blocks).
• $2$ $x$ $y$: Erichthonios copies the attribute of $x$-th block to $y$-th and all $y$-th block's $\mathbf{nearby}$, $\mathbf{continuous}$, $\mathbf{same}\mathbf{attribute}$, $\mathbf{longest}$ blocks. (A segment of same attribute blocks containing $y$-th, and the left adjacent block of the segment has a different attribute or is out of boundary, so as right.)
• $3$ $x$ $v$: Erichthonios makes the weight of all the blocks with the same attribute as $x$-th block increase by $v$.
• $4$ $x$: Erichthonios attacks the defending system. Only if you output the weight of the $x$-th block, can you defend it.

Attention: Since you don't know what Erichthonios will do next, there is encoding with the queries. (See the $\mathbf{input}$)

If you couldn't solve this problem, you will be laughed at by Hythlodaeus later. You don't want to be like that, right?

Each test contains multiple test cases. The first line contains the number of test cases$(1\le T\le 20)$. Description of the test cases follows.

The first line contains two integers $n$ and $q$ (3≤n≤108, 1≤q≤105) -- The number of Themis defending system blocks, and the number of attacks that Erichthonios will perform.

The following $q$ lines contains Erichthonios' attacks, (initially, $last=0$):

• 1 x'′ c'′: contains 3 integers, 1≤x′≤n, floor1≤c′≤⌊2n−1⌋, actually, x=((x′−1)⊕last)modn + 1, c=((c′−1)⊕last)mod⌊2n−1⌋ + 1.
• 2 x'′ y'′: contains 3 integers, ≤x′≤n, 1≤y′≤n, actually, x=((x′−1)⊕last)modn + 1,y=((y′−1)⊕last)modn + 1.
• 3 x′ v: contains 3 integers, 1≤x′≤n, 1≤v≤109, actually, x=((x′−1)⊕last)modn + 1, and there is no encode with v 1≤v≤109.
• 4 x'′: contains 2 integers, 1≤x′≤n, actually, x=((x′−1)⊕last)modn + 1, after you get the $Answer$, don't forget to update, $last=Answer\text{and}1073741823$.

Where $\oplus$ means bitwise XOR operation, $\text{and}$ means bitwise AND operation.

It is guaranteed that the sum of n does not exceed 2⋅109 and the sum of q does not exceed 106

For each test case:

For each 4-th attack, print one integer in a line --- the weight of the block.

1
16 12
3 10 16
4 2
1 1 6
1 5 6
1 9 7
1 15 7
2 2 10
2 2 13
3 1 16
4 16
4 9
4 4

16
32
32
16

The decoded attacks in example:

3, x = 10 , v = 16

4, x = 2

1, x = 1 , c = 1

1, x = 5 , c = 1

1, x = 9 , c = 2

1, x = 15 , c = 2

2, x = 2 , y = 10

2, x = 2 , y = 13

3, x = 1 , v = 16

4, x = 16

4, x = 9

4, x = 4