Cumulonimbus Clouds

Every April, the city is always shrouded under cumulonimbus clouds. The city consists of \(n\) buildings and \(m\) two-way streets. It is guaranteed that any two buildings can reach each other directly or indirectly, no street connects a building to itself, and there is at most one street between any pair of buildings.

The city has a unique layout: if we view it as an undirected graph \(G\), then for any non-empty subgraph of \(G\), there is at least one building within that subgraph whose degree (i.e. the number of incident streets in that subgraph) is no more than \(10\). This means the graph is 10-degenerate and is relatively sparse.

Initially, there are \(a_i\) cumulonimbus clouds above the \(i\)-th building. Then, over \(q\) days, one of the following two events occurs each day:

• 1 x v: \(v\) cumulonimbus clouds are added to building \(x\).
• 2 x: Report the total number of cumulonimbus clouds over all buildings directly connected to building \(x\).

Your task is to process these events. For each query of the second type, output the corresponding result on a new line.

inputFormat

The input begins with three integers: \(n\), \(m\), and \(q\) — the number of buildings, the number of streets, and the number of events.

The next line contains \(n\) integers: \(a_1, a_2, \dots, a_n\), where \(a_i\) is the initial number of cumulonimbus clouds above building \(i\).

Each of the following \(m\) lines contains two integers \(u\) and \(v\), indicating a two-way street between buildings \(u\) and \(v\).

Then \(q\) lines follow, each representing an event in one of the following formats:

• 1 x v: Add \(v\) clouds to building \(x\).
• 2 x: Query the sum of clouds on all buildings directly connected to building \(x\).

outputFormat

For each query of the form 2 x, output a single integer representing the sum of cumulonimbus clouds above all buildings adjacent to building \(x\).

sample

3 2 3
5 0 10
1 2
2 3
2 2
1 1 2
2 2

15
17