Description

There are $N$ nodes labeled from $1$ to $N$, initially all disconnected. The initial weight of the $i$-th node is $a_i$. Then the following operations occur:

• 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 by $v$.
• F1 x: output the current weight of node $x$.
• F2 x: output the maximum weight within the connected component containing node $x$.
• F3: output the maximum weight among all nodes.

Input Format

The first line contains an integer $N$, the number of nodes. The second line contains $N$ integers $a_1,a_2,\dots,a_N$, the initial weights of the $N$ nodes.

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

Each of the following $Q$ lines is in one of the formats described above.

Output Format

For operations F1 x, F2 x, and F3, output the corresponding result, one per line.

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

-10
10
10

Hint

Constraints:

• For $30\%$ of the testdata, $N \le 100$, $Q \le 10000$.
• For $80\%$ of the testdata, $N \le 100000$, $Q \le 100000$.
• For $100\%$ of the testdata, $N \le 300000$, $Q \le 300000$.
• For all testdata, the input is guaranteed to be valid, and $-1000 \le v, a_1, a_2, \dots, a_N \le 1000$.

Translated by ChatGPT 5