Maintain the Table

This problem requires you to implement a data structure that maintains a table. The table is initially populated with a single element \(1\). You need to support the following operations, where \(x\) and \(y\) are positive integers in the range \([1, 10^6]\), and it is guaranteed that all numbers in the table are distinct at any point in time. The total number of operations does not exceed \(10^5\).

• 1 x y: Insert element \(y\) immediately after element \(x\).
• 2 x: Query the element immediately after \(x\). If \(x\) is the last element, output \(0\).
• 3 x: Delete the element immediately after \(x\) (do nothing if there is no such element), while preserving the order of the remaining elements.

Input Format: The first line contains an integer \(Q\), the number of operations. Each of the following \(Q\) lines contains an operation in one of the three formats described above.

Output Format: For each query operation (type 2), output the answer on a new line.

Note: In all formulas, expressions formatted in LaTeX are enclosed within \( ... \) or \[ ... \].

inputFormat

The first line contains a single integer \(Q\) (\(1 \le Q \le 10^5\)), representing the number of operations. Each of the next \(Q\) lines contains one of the following operations:

• 1 x y — Insert element \(y\) immediately after element \(x\).
• 2 x — Query the element immediately after \(x\). If \(x\) is the last element, output \(0\).
• 3 x — Delete the element immediately after \(x\).

It is guaranteed that \(x\) and \(y\) are positive integers in the range \([1, 10^6]\) and all elements in the table are distinct at any time.

outputFormat

For each query operation of type 2, output a single integer that is the element immediately following \(x\) (or \(0\) if \(x\) is the last element) on a separate line.

sample

5
1 1 2
2 1
1 2 3
3 1
2 1

2
3