Background

You are playing Sabbat of the Witch and suddenly start thinking about a philosophical question: does the restart route in this game count as NTR?

After thinking for a long time, you suddenly realize this is a philosophical problem involving timelines and personal identity.

Then you suddenly discover that galgames and data structures have some deeply mysterious connections. To think about this problem better, you decide to write a data structure problem.

Problem Description

Maintain a sequence and support the following three operations.

1. Range assignment.
2. Range sum query.
3. Undo a previous range assignment operation.

Online only.

Note: this undo operation does not affect any operations before it, and also does not affect any operations after it. In other words, after undoing an operation, the sequence becomes the state as if the undone operation had never existed in history.

For example, suppose we apply operations $1,2,3,4,5$ in order.

• When we undo operation $4$, the whole sequence should be the same as the sequence after applying operations $1,2,3,5$ in order.
• When we then undo operation $2$, the whole sequence should be the same as the sequence after applying operations $1,3,5$ in order.

Input Format

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

The second line contains $n$ integers $a_{1}...a_{n}$, where $a_{i}$ is the $i$-th element of the sequence.

Next $m$ lines:

• If a line is $1,l,r,v$, it means assigning the interval $(l,r)$ to value $v$. If this operation is the $k$-th assignment operation, then its ID is $k$.
• If a line is $2,l,r$, it means querying the sum of numbers in the interval $(l,r)$.
• If a line is $3,x$, it means undoing the operation whose ID is $x$.

It is guaranteed that the undone operation always exists, and each operation will be undone at most once.

To enforce the online requirement, let lastans be the answer of the most recent query at the time the current operation is read (lastans is initially $0$).

• For operation 1, the real interval you need to modify is $(l \oplus lastans,r \oplus lastans)$.
• For operation 2, the real interval you need to query is $(l \oplus lastans,r \oplus lastans)$.
• For operation 3, the real operation ID you need to undo is $x \oplus lastans$.

Here $\oplus$ denotes the XOR operation.

Output Format

For each operation 2, output one integer per line, representing the sum of elements in the queried interval.

To help you understand the statement and debug, we prepared two samples: one is online-only and the other is not online-only (although this problem has no partial score for the non-online-only part).

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

52
54
7
30
2
22

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

52
54
7
30
2
22

Hint

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

For the remaining test points, $n,m \leq 10^5$, and the number of operation 1 does not exceed $65000$.

All input numbers are guaranteed to be less than $10^9$.

Translated by ChatGPT 5