Background

This is a template problem.

Problem Description

You need to implement a data structure to maintain a sequence, supporting the following operations (for every past historical version):

1. Insert a number $x$ after the $p$-th number.
2. Delete the $p$-th number.
3. Reverse the interval $[l,r]$. For example, if the original sequence is $\{5,4,3,2,1\}$, after reversing $[2,4]$, it becomes $\{5,2,3,4,1\}$.
4. Query the sum of all numbers in the interval $[l,r]$.

Different from an ordinary balanced tree, every operation is performed based on some historical version, and generates a new version (operation $4$ keeps the original version unchanged). The new version is numbered as the index of this operation.

This problem is strictly online.

Input Format

The first line contains an integer $n$, the total number of operations.

The next $n$ lines each start with two integers $v_i, \mathrm{opt}_i$. Here, $v_i$ is the index of the past version it is based on ($0 \le v_i < i$), and $\mathrm{opt}_i$ is the operation type ($1 \le \mathrm{opt}_i \le 4$).

If $\mathrm{opt}_i=1$, then two more integers $p_i, x_i$ follow, meaning: insert number $x$ after the $p_i$-th number.
If $\mathrm{opt}_i=2$, then one more integer $p_i$ follows, meaning: delete the $p_i$-th number.
If $\mathrm{opt}_i=3$, then two more integers $l_i, r_i$ follow, meaning: reverse the interval $[l_i, r_i]$.
If $\mathrm{opt}_i=4$, then two more integers $l_i, r_i$ follow, meaning: query the sum of the interval $[l_i, r_i]$.

Strict online rule:
Let the answer of the last operation of type $4$ before the current operation be $lastans$ (if there is no previous type $4$ operation, then $lastans=0$).
Then $p_i,x_i$ or $l_i,r_i$ of this operation are each XORed bitwise with $lastans$ to obtain the real $p_i,x_i$ or $l_i,r_i$.

Output Format

For each query operation with type $4$, output one line with one number: the sum of the interval.

10
0 1 0 1
1 1 1 2
2 4 1 2
3 1 2 0
4 4 2 1
5 3 5 7
6 4 5 6
4 1 7 1
8 3 4 6
9 4 4 1

3
4
5
10

Hint

:::info[Sample Explanation] The sample input:

10
0 1 0 1
1 1 1 2
2 4 1 2
3 1 1 3
4 4 1 2
5 3 1 3
6 4 1 2
4 1 2 4
8 3 1 3
9 4 1 4

After all operations, a total of $11$ versions are generated:

Version $0$ (initial version): $\varnothing$

Version $1$: $\{1\}$

Version $2$: $\{1,2\}$

Version $3$: $\{1,2\}$ (this operation queries the sum on $\left[1,2\right]$ and outputs $3$.)

Version $4$: $\{1,3,2\}$

Version $5$: $\{1,3,2\}$ (this operation queries the sum on $\left[1,2\right]$ and outputs $4$.)

Version $6$: $\{2,3,1\}$

Version $7$: $\{2,3,1\}$ (this operation queries the sum on $\left[1,2\right]$ and outputs $5$.)

Version $8$: $\{1,3,4,2\}$

Version $9$: $\{4,3,1,2\}$

Version $10$: $\{4,3,1,2\}$ (this operation queries the sum on $\left[1,4\right]$ and outputs $10$.) ::::

Strict online: the following constraints on $p_i, x_i, l_i, r_i$ are after XORing with $lastans$.

• For $6$ test points, $n \le 5000$.
• For another $6$ test points, $v_i = i - 1$.
• Users are welcome to strengthen the testdata. You may contact the administrator or the problem setter.

For $100\%$ of the data, $1 \le n \le 2 \times {10}^5$, $|x_i| < {10}^6$.

Assume the sequence length of the referenced historical version is $len \ge 1$, then:
If $\mathrm{opt}_i=1$, then $0 \le p_i \le len$.
If $\mathrm{opt}_i=2$, then $1 \le p_i \le len$.
If $\mathrm{opt}_i=3$, then $1 \le l_i \le r_i \le len$.
If $\mathrm{opt}_i=4$, then $1 \le l_i \le r_i \le len$.

Assume the sequence length of the referenced historical version is $0$, then:
$\mathrm{opt}_i=1$, $p_i=0$.

Translated by ChatGPT 5