Persistent Sequence Operations

You are required to implement a persistent data structure that maintains a sequence. Initially, version 0 is an empty sequence. Each operation is applied on a historical version and creates a new version (the new version number is the 1-indexed order of the operation). Operation 4 (query) does not modify the sequence, but it still creates a new version which is identical to the base version.

The supported operations are defined as follows (all indices are 1-indexed unless otherwise specified):

• Operation 1: Given a version v, and two integers p and x, insert the integer \( x \) after the \( p \)-th element of the sequence. Note that if \( p = 0 \), insert at the beginning.
• Operation 2: Given a version v and an integer p, delete the \( p \)-th element from the sequence.
• Operation 3: Given a version v and two integers l and r, reverse the subarray from index \( l \) to \( r \) (inclusive). For example, if the sequence is \( \{5,4,3,2,1\} \) and you reverse the subarray \( [2,4] \), the resulting sequence will be \( \{5,2,3,4,1\} \).
• Operation 4: Given a version v and two integers l and r, query the sum of the subarray from index \( l \) to \( r \) (inclusive) and print the result. This operation does not change the sequence.

Each operation is given with a base version number on which it is applied. The input is handled online and the new version number equals the current operation's index (starting from 1).

inputFormat

The first line contains an integer \( Q \) representing the number of operations. Each of the following \( Q \) lines describes an operation in one of the following formats:

• For Operation 1: 1 v p x — Based on version v, insert integer x after the \( p \)-th element (if \( p = 0 \), insert at the beginning).
• For Operation 2: 2 v p — Based on version v, delete the \( p \)-th element.
• For Operation 3: 3 v l r — Based on version v, reverse the subarray from index \( l \) to \( r \) (inclusive).
• For Operation 4: 4 v l r — Based on version v, query the sum of the subarray from index \( l \) to \( r \) and print the result.

Note: The new version created after an operation is numbered with the order of the operation (starting from 1). For Operation 4, although the sequence remains unchanged, a new version is still created which is identical to version v.

outputFormat

For each Operation 4, output a single line containing the sum of the elements in the specified subarray.

sample

5
1 0 0 10
1 1 1 20
3 2 1 2
4 3 1 2
2 3 1

30