There are $N$ nodes, labeled from $1$ to $N$, which are initially disconnected. The initial weight of the $i$-th node is $a_i$. There are several types of operations:

• U x y: Add an edge connecting node $x$ and node $y$.
• A1 x v: Increase the weight of node $x$ by $v$.
• A2 x v: Increase the weights of all nodes in the connected component containing node $x$ by $v$.
• A3 v: Increase the weights of all nodes in the graph by $v$.
• F1 x: Output the current weight of node $x$.
• F2 x: Output the maximum weight among all nodes in the connected component containing node $x$.
• F3: Output the maximum weight among all nodes in the graph.

Input

The first line contains an integer $N$, representing the number of nodes.

The next line contains $N$ integers $a_1, a_2, \ldots, a_N$, representing the initial weights of the $N$ nodes.

The next line contains an integer $Q$, representing the number of operations.

The last $Q$ lines each contain an operation in the format described above.

Output

For each F1, F2, and F3 operation, output the corresponding result on a new line.

Examples

Input 1

3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3

Output 1

-10
10
10

Subtasks

For $30\%$ of the data, $N \le 100$ and $Q \le 10^4$.

For $80\%$ of the data, $N \le 10^5$ and $Q \le 10^5$.

For $100\%$ of the data, $N \le 3 \times 10^5$ and $Q \le 3 \times 10^5$.

For all data, it is guaranteed that the input is valid and $-10^3 \le v, a_1, a_2, \ldots, a_N \le 10^3$.