Problem Statement

You are given an integer sequence $A=(A_1,A_2,\ldots,A_N)$ of length $N$.

Process $Q$ operations in order. There are three types of operations:

• A type-1 operation is represented by a triple of integers $(l,r,x)$, which corresponds to replacing $A_i$ with $\max\lbrace A_i,x\rbrace$ for each $i=l,l+1,\ldots,r$.
• A type-2 operation is represented by an integer $i$, which corresponds to canceling the $i$-th operation (it is guaranteed that the $i$-th operation is of type 1 and has not already been canceled). The new sequence $A$ can be obtained by performing all type-1 operations that have not been canceled, starting from the initial state.
• A type-3 operation is represented by an integer $i$, which corresponds to printing the current value of $A_i$.

Constraints

• $1\leq N\leq2\times10^5$
• $1\leq A_i\leq10^9\ (1\leq i\leq N)$
• $1\leq Q\leq2\times10^5$
• In a type-1 operation, $1\leq l\leq r\leq N$ and $1\leq x\leq10^9$.
• In a type-2 operation, $i$ is not greater than the number of operations given before, and $1\leq i$.
• In a type-2 operation, the $i$-th operation is of type 1.
• In type-2 operations, the same $i$ does not appear multiple times.
• In a type-3 operation, $1\leq i\leq N$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N
Q
\operatorname{query}_1
\operatorname{query}_2
\vdots
\operatorname{query}_Q

Here, $\operatorname{query}_k\ (1\leq k\leq Q)$ represents the $k$-th operation, and depending on the type of the $k$-th operation, one of the following is given.

For a type-1 operation, the following is given, meaning that the $k$-th operation is a type-1 operation represented by $(l,r,x)$:

1 l r x

For a type-2 operation, the following is given, meaning that the $k$-th operation is a type-2 operation represented by $i$:

2 i

For a type-3 operation, the following is given, meaning that the $k$-th operation is a type-3 operation represented by $i$:

3 i

Output

Let $q$ be the number of type-3 operations. Print $q$ lines. The $i$-th line $(1\leq i\leq q)$ should contain the value that should be printed for the $i$-th given type-3 operation.