Problem Background

You are playing "Sabbat of the Witch" when a philosophical question suddenly strikes you: Does the restart line in this game count as ntr (netorare)?

After pondering for a long time, you suddenly realize that this is a philosophical issue involving time lines and personal identity.

At this moment, you notice a profound connection between galgames and data structures. To better contemplate this question, you decide to write a data structure problem.

Problem Description

Maintain a sequence that supports the following three operations:

1. Interval assignment
2. Interval sum query
3. Undo a previous interval assignment operation

Mandatory online

Note: The undo operation does not affect previous or subsequent operations. In other words, after undoing an operation, the sequence will revert to the state it was in before the operation was ever performed.

For example, suppose we perform operations 1, 2, 3, 4, 5 on the sequence in order.

When we undo operation 4, the sequence should be the same as if operations 1, 2, 3, 5 were performed in order.

When we then undo operation 2, the sequence should be the same as if operations 1, 3, 5 were performed in order.

Input Format

The first line contains two integers \( n, m \) representing the length of the sequence and the number of operations, respectively.

The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \) where \( a_i \) represents the \( i \)-th element of the sequence.

The next \( m \) lines describe the operations:

• If the line is \( 1, l, r, v \), it means to assign the interval \( (l, r) \) the value \( v \). If this is the \( k \)-th assignment operation, its identifier is \( k \).
• If the line is \( 2, l, r \), it means to query the sum of the numbers in the interval \( (l, r) \).
• If the line is \( 3, x \), it means to undo the operation with identifier \( x \).

Data guarantees that the operation to be undone exists and each operation is undone only once.

To reflect the online nature of the problem, let \( lastans \) be the answer to the last query before the current operation (initialized to 0).

For operation 1, the actual interval to operate on is \( (l \oplus lastans, r \oplus lastans) \).

For operation 2, the actual interval to query is \( (l \oplus lastans, r \oplus lastans) \).

For operation 3, the identifier of the operation to undo is \( x \oplus lastans \).

Here, \( \oplus \) denotes the XOR operation.

Output Format

For each operation 2, output a single integer on a new line, representing the sum of the elements in the queried interval.

To help you understand the problem and debug, we have prepared two sample inputs, one with mandatory online and the other without (although there is no partial credit for the non-mandatory online part).

Sample Input and Output

Sample Input #1

20 20
8 6 4 9 9 8 5 5 7 9 8 8 5 8 2 2 2 1 9 4 
1 17 19 4
1 3 8 5
3 2
2 4 10
1 14 19 8
2 10 16
2 9 9
1 1 18 1
1 1 7 10
2 4 6
2 9 10
1 5 17 2
1 10 19 6
1 2 5 2
1 6 8 2
1 14 19 1
1 4 7 6
1 17 19 10
2 8 12
1 10 10 2

Sample Output #1

52
54
7
30
2
22

Sample Input #2

20 20
8 6 4 9 9 8 5 5 7 9 8 8 5 8 2 2 2 1 9 4 
1 17 19 4
1 3 8 5
3 2
2 4 10
1 58 39 8
2 62 36
2 63 63
1 6 21 1
1 6 0 10
2 3 1
2 23 20
1 7 19 2
1 8 17 6
1 0 7 2
1 4 10 2
1 12 17 1
1 6 5 6
1 19 17 10
2 10 14
1 28 28 2

Sample Output #2

52
54
7
30
2
22

Notes

For test points 9 and 10, \( n, m \leq 10^4 \), and each of these test points is worth 1 point.

For the remaining test points, \( n, m \leq 10^5 \) and the number of operation 1s does not exceed 65,000.

All input numbers are guaranteed to be less than \( 10^9 \).

见题面 Input 部分

见题面 Output 部分