Admiral Yi Sun-sin

There are n regions numbered from 1 to n, and the workshop for building the turtle ship is in region 1. Each region i has a difficulty value hard_i.

There are two kinds of roads: national roads and expressways. The initial m roads are all national roads. Regions in the same national-road connected component can travel between each other using only national roads.

A region in the current national-road connected component containing region 1 is no longer difficult: its hard_i becomes its comfort value. If region 1 can reach a region using only expressways, that region's comfort value is 2 * hard_i. A region outside the national-road connected component containing region 1 contributes 0 to comfort sums.

The expressway graph must always remain acyclic. Also, two regions can be directly connected by an expressway only when there is already a path between them using only current national roads.

Process q operations in order. The operations add national roads, add or remove expressways, and ask queries about the current state.

The first line contains two integers n and m, the number of regions and the number of initial national roads. (1 <= n, m <= 121600)

The second line contains hard_1, hard_2, ..., hard_n. (1 <= hard_i <= 1216)

Each of the next m lines contains two integers a and b describing one national road. (1 <= a, b <= n, a != b)

The next line contains q, the number of operations. (1 <= q <= 121600)

Each of the next q lines contains three integers p, a, b describing one operation. (1 <= p <= 6, 1 <= a, b <= n, a != b)

The operations mean the following.

• p = 1: Add a national road between regions a and b.
• p = 2: Add an expressway between regions a and b. If there is no national-road path between them, or if adding this expressway would create an expressway cycle, print -1 and do not add it.
• p = 3: Remove the direct expressway between regions a and b. If no such expressway exists, print -1.
• p = 4: Print the sum of hard values over all regions that are still difficult. In this operation, a and b are present only to keep the input format uniform.
• p = 5: Print the sum of the comfort values of regions a and b.
• p = 6: Print the sum of the comfort values of all regions on the expressway-only path from a to b. If no such expressway path exists, print -1.

All operations are processed one at a time in the order given.

For each operation that requires output, print the answer on its own line.