During Collea's war with The Alliance, Collea faced massive bombardments all across the country, destroying or damaging most of the roads and infrastructure within the country. There are currently cities in the country of Collea, where of them are considered crucial to the country. Currently, there are roads in Collea that are reparable within the month, the th of which connecting cities and while costing Freitz. Note that each road only connects two cities in Collea and that if all the roads were repaired, it would be possible to travel from any city to all other cities in Collea while only using these roads. During the course of the war, reports of two different types are received. Reports of type give a city number , and details that if is currently an unimportant city, it would be deemed crucial, and if it was already a crucial city, it would be deemed as unimportant. Reports of type details that the cost of repairing the th road is changed to Freitz. Burdened by war reparations, the Collean government needs to find the minimal cost of connecting all of their crucial cities within the month. Help them find this minimum cost initially, and after each report.

#### Constraints

##### Subtask 1 [10%]

##### Subtask 2 [25%]

All reports are of type .

##### Subtask 3 [65%]

No additional constraints.

#### Input Specification

The first line will contain three positive integers, , , and .

The next line contains positive integers, the original crucial cities of Collea.

lines will follow, the th of which containing the integers , , and .

more lines will follow, each one in the form of either `1 c`

or `2 r u`

, describing the type and parameters of the report.

#### Output Specification

On the first line, print the initial minimal cost of connecting all of the crucial cities of Collea.

Output more lines, the th of which containing one integer, the minimal cost of connecting all of the crucial cities of Collea after the th report.

#### Sample Input

```
5 2 2
2 5
2 4 3
1 2 1
3 2 2
5 1 4
1 3
2 2 5
```

#### Sample Output

```
5
7
11
```

## Comments

I think data for this problem are weak. Master Acutie (AQT) today informed me that my LCA implementation for HLD is incorrect but it still passed for this problem.

(Presumably) incorrect submission

IMQT orz