I live for a world full of chaos, mayhem is my dream. Sadly, friendship bonds keep the world together. This has to end.

Initially, there are N people living in the world, and I know the strength of each one and the friendship bonds between them. A group of connected people will sum up their strengths if attacked (the power of friendship... disgusting, right?), so I'm interested in the strength of full groups of connected people, specially in the maximum strength of a group.

I have already set a plan of action, the order in which I will destroy friendships! But, turns out, that when one destroys friendships, people may react and increase or decrease their strength. I need your help to find out how successful my plan is.

I'll give you the initial information (strengths and bonds) and a list of Q events, each event will be either a destruction event, or a strength change event.

I need to know the maximum strength of a group after each event.

Input

The first line of input consists of two integers N and M, the number of people and the initial number of bonds respectively.

Next line will contain N integers s₁, s₂ ... s_N separated with exactly one white space, being s_i the initial strength of the i-th person.

Next M lines will contain two integers a_i and b_i, representing a friendship bond between those two people.

The next line will contain a single integer Q, the number of events.

The following Q lines will be either:

• 1 k: Indicating the destruction of bond number k (in the input order)
• 2 p x: Indicates that the person p changed her strength to x

Output

Print Q lines, the maximum strength of a group after each event.

Example

Input:
5 6
3 3 3 3 3
1 2
1 3
2 3
2 5
3 4
4 5
5
2 1 2
1 5
1 4
2 4 8
2 3 7

Output:
14
14
8
11
12

Constraints

• 1 ≤ N, M, Q ≤ 10⁵
• 1 ≤ s_i, x^_i ≤ 10⁵
• 1 ≤ a_i, b_i ≤ N
• 1 ≤ k_i ≤ M
• 1 ≤ p_i ≤ N
• every bond will be deleted at most once.
• between two people there is at most one bond.