Dynamic Connectivity and Weight Operations

You are given N nodes numbered from \(1\) to \(N\). Initially, all nodes are disconnected and the i-th node has an initial weight \(a_i\). You need to perform a sequence of operations on these nodes. The operations can be one of the following types:

• 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 weight of all nodes in the connected component containing node \(x\) by \(v\).
• A3 v: Increase the weight of all nodes 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.

Input Format:

The first line contains two integers \(N\) and \(Q\) indicating the number of nodes and the number of operations, respectively.

The second line contains \(N\) integers \(a_1, a_2, \ldots, a_N\) representing the initial weights of the nodes.

Each of the following \(Q\) lines represents an operation as described above.

Note: The connectivity is defined by the added edges. When an edge is added between two nodes they become part of the same connected component. The operations should be processed in the given order.

inputFormat

The first line contains two space-separated integers \(N\) and \(Q\).

The second line contains \(N\) space-separated integers \(a_1, a_2, \ldots, a_N\), denoting the initial weight of each node.

Each of the next \(Q\) lines contains one operation in one of the following formats:

• U x y
• A1 x v
• A2 x v
• A3 v
• F1 x
• F2 x
• F3

outputFormat

For each query operation (F1, F2, F3), output the answer on a new line in the order the queries appear.

sample

5 7
1 2 3 4 5
F3
A1 1 10
F1 1
U 1 2
A2 2 5
F2 1
F3

5
11
16
16