## VZLA2019F - Friendship

I live for a world full of chaos, mayhem is my dream. Sadly, friendship bonds keep the world together. \textbf{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_{1}, s_{2},... 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 7Output:14

14

8

11

12

### Constraints

• 1 ≤ N, M, Q ≤ 10^{5}

• 1 ≤ s_{i} , x^{i} ≤ 10^{5}

• 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.

Added by: | Samuel Nacache |

Date: | 2019-10-27 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |

Resource: | Augusto Hidalgo - Used for Venezuelan 2019 ICPC Local Contest |