SUN Cactus Molecule

Tamlef, a graduate student in chemistry, wants to build a molecule made of S, U, and N atoms. Lef has already decided the molecular structure. If atoms are vertices and bonds are edges, Lef's structure forms a special cactus graph. A special cactus graph is a graph in which every vertex belongs to at most one simple cycle.

Lef has not yet decided which atom goes in which position. Lef does not know how to bond two atoms of the same kind, so two bonded atoms must be different kinds. Given the energy needed to place an S, U, or N atom at each position, Lef wants the most stable molecule. The most stable molecule is the one whose total energy over all positions is the lowest.

Through experiments, Lef keeps revising the energy needed to place an atom at each position. After each revision, tell Lef the total energy of the most stable molecule that can be built.

The first line contains N, M, and Q, the number of atoms, the number of bonds, and the number of experiments, separated by spaces.

The next N lines each contain Si, Ui, and Ni, the energies needed to place an S, U, or N atom at position i, separated by spaces. ($1 \le i \le N$)

The next M lines each contain the two positions connected by the i-th bond, separated by spaces.

The next Q lines each contain Ai, Bi, and Ci, separated by spaces. This means the energy needed to place a Bi atom at position Ai is changed to Ci. Bi is 1 for S, 2 for U, and 3 for N.

Print Q lines. For each experiment, print the total energy of the most stable molecule that can be built after the revision, one per line.

• 1 ≤ N ≤ 100,000
• M ≥ N - 1
• 1 ≤ Q ≤ 100,000
• 1 ≤ Si, Ui, Ni ≤ $10^4$ (1 ≤ i ≤ N)
• The graph formed by the molecule is a simple graph.
• The graph formed by the molecule is connected.
• In the graph formed by the molecule, every vertex belongs to at most one simple cycle.
• 1 ≤ Ai ≤ N, 1 ≤ Bi ≤ 3, 1 ≤ Ci ≤ $10^4$ (1 ≤ i ≤ Q)