2015-16 Woburn Challenge Finals - Senior Division

At last, the final battle for Scarberia is upon us! The cows and monkeys have agreed that the fighting will take place on a circle of ~N~ ~(3 \le N \le 300\,000)~ pastures, connected to one another in a cycle by ~N~ two-way bridges. The ~i~-th bridge can support a weight of at most ~S_i~ ~(1 \le S_i \le 10^6)~ pounds, and connects pastures ~i~ and ~i + 1~ ~(1 \le i < N)~, or pastures ~N~ and ~1~ ~(i = N)~.

The monkeys' base of operations is located in pasture ~1~, and they have troops stationed in all of the other pastures. The monkeys, being masterful makers of war, are keenly aware that the most effective soldiers are well-fed soldiers. As such, they have a convoy of ~M~ ~(1 \le M \le 300\,000)~ trucks which will deliver bananas from their base daily. The ~i~-th truck has a weight of ~W_i~ ~(1 \le W_i \le 10^6)~ pounds, and every day, it will depart from pasture ~1~, driving around amongst the pastures and delivering ~B_i~ ~(1 \le B_i \le 10^6)~ bananas to each other pasture that it can reach. Each truck can only cross bridges which can at least support its weight, and it can drive back and forth as much as necessary (even revisiting pastures multiple times), but it will only deliver a load of bananas to each pasture at most once. Therefore, each day, the ~i~-th truck will deliver between ~0~ and ~B_i \times (N-1)~ bananas in total.

The battle is scheduled to last for ~D~ ~(1 \le D \le 300\,000)~ days, and in order to manage their banana hoard successfully, the monkeys would like to determine how many bananas their trucks will deliver on each day. However, this aspect of the war promises to be particularly dynamic, as those dastardly cows are also well aware of the military importance of the supply chain and will attempt to sabotage it, while the monkeys will hopefully enact the necessary countermeasures. One event will occur at the start of each day (before the trucks roll out to make their deliveries, with the type of the event on the ~i~-th day indicated by ~T_i~ ~(1 \le T_i \le 2)~):

• If ~T_i = 1~, the cows will undermine the structural integrity of the ~X_i~-th ~(1 \le X_i \le N)~ bridge, permanently reducing its maximum supported weight by ~Y_i~ ~(1 \le Y_i < 10^6)~ pounds. It's guaranteed that it will still be able to support a weight of at least ~1~ pound.
• If ~T_i = 2~, the monkeys will remodel their ~X_i~-th ~(1 \le X_i \le M)~ truck such that it henceforth weighs ~Y_i~ ~(1 \le Y_i \le 10^6)~ pounds. Note that this could cause its weight to increase (thanks to cows cleverly disguised as monkey mechanics).

The outcome of the entire war, and the monkeys' opportunity to reclaim Scarberia once and for all, depends on this supply chain! Can you help the monkeys determine how many bananas their trucks will deliver in total on each of the ~D~ days of the battle?

In test cases worth ~6/33~ of the points, ~N \le 200~, ~M \le 200~, and ~D \le 200~.
In test cases worth another ~8/33~ of the points, ~N \le 2000~, ~M \le 2000~, and ~D \le 2000~.
In test cases worth another ~8/33~ of the points, ~T_i = 1~.
In test cases worth another ~8/33~ of the points, ~T_i = 2~.

Input Specification

The first line of input consists of three space-separated integers, ~N~, ~M~, and ~D~.
~N~ lines follow. The ~i~-th of these lines consists of a single integer, ~S_i~ (for ~i = 1 \dots N~).
~M~ lines follow. The ~i~-th of these lines consists of two space-separated integers, ~W_i~ and ~B_i~ (for ~i = 1 \dots M~).
~D~ lines follow. The ~i~-th of these lines consists of three space-separated integers, ~T_i~, ~X_i~, and ~Y_i~ (for ~i = 1 \dots D~).

Output Specification

Output ~D~ lines. The ~i~-th line of output should consist of a single integer representing the total number of bananas delivered on the ~i~-th day (for ~i = 1 \dots D~).
Note that each of these values may not fit within a 32-bit integer.

Sample Input

4 5 4
5
4
2
8
3 5
1 100
2 1
5 20
6 4
2 2 100
1 4 3
1 4 4
2 2 1

Sample Output

62
58
33
333

Explanation

On the first day, the first truck will deliver ~5~ bananas each to pastures ~2~, ~3~, and ~4~. The second truck, now weighing ~100~ pounds, won't deliver any bananas. The third truck will deliver ~1~ banana to each of those ~3~ pastures, the fourth will deliver ~20~ bananas to pastures ~2~ and ~4~, and the fifth will deliver ~4~ bananas to just pasture ~4~. The total number of bananas delivered on this day will then be ~5 \times 3 + 1 \times 3 + 20 \times 2 + 4 \times 1 = 62~.