Street Trees

Yonsei University is planting street trees across the whole campus. The school wants to work out how much budget the job needs before it starts.

The campus has $N$ buildings, and exactly one tree goes in front of each building, so $N$ trees in total. Every tree is one of two kinds. One is a ginkgo, which attracts no pests but smells bad in autumn. The other is a plane tree, which gives shade in summer but can cause respiratory allergies in some people in spring.

The school has already surveyed, for every building, the cost of planting a ginkgo and the cost of planting a plane tree. The terrain and the surroundings differ from building to building, so the same kind of tree can cost different amounts in front of different buildings.

The school wrote a plan that plants a tree in front of every building at the lowest total cost. A designer who joined the project late said the plan looks bad and needs a lot of revision. Each designer request is one of two kinds.

1. Building $i$ and building $j$ must get the same kind of tree.
2. Building $i$ and building $j$ must get different kinds of trees.

Worse, revising the plan took so long that the surveyed costs started to change too. Each cost change is one of two kinds.

1. The cost of planting a ginkgo in front of building $i$ changes.
2. The cost of planting a plane tree in front of building $i$ changes.

The school decided that revising the plan by hand is no longer workable, and asked the computer science department for a program that applies the incoming requests and price changes at once and reports the optimal plan. Write that program.

The first line has the number of buildings $N$ and the number of plan requests the designer has made so far, $D$. ($1 \le N \le 200{,}000$, $0 \le D \le 200{,}000$)

Buildings are numbered from 1.

Each of the next $N$ lines has the cost $G_i$ of planting a ginkgo and the cost $P_i$ of planting a plane tree in front of one building, given in order from building 1. ($1 \le G_i, P_i \le 10^9$)

Each of the next $D$ lines has one designer request in the form C i j. ($C$ is 0 or 1, $1 \le i \le N$, $1 \le j \le N$, $i \ne j$)

$C = 0$ means building $i$ and building $j$ must get the same kind of tree, and $C = 1$ means building $i$ and building $j$ must get different kinds of trees.

The next line has $Q$, the number of later designer requests and cost changes combined. ($1 \le Q \le 200{,}000$)

Each of the next $Q$ lines has one request or change in the form C A B, classified as follows.

1. $C = 0$ with $1 \le A, B \le N$ and $A \ne B$ is a request that building $A$ and building $B$ get the same kind of tree.
2. $C = 1$ with $1 \le A, B \le N$ and $A \ne B$ is a request that building $A$ and building $B$ get different kinds of trees.
3. $C = 2$ with $1 \le A \le N$ and $1 \le B \le 10^9$ means the cost of planting a ginkgo in front of building $A$ has changed to $B$.
4. $C = 3$ with $1 \le A \le N$ and $1 \le B \le 10^9$ means the cost of planting a plane tree in front of building $A$ has changed to $B$.

For any two different designer requests $i$ and $j$, $(A_i, B_i)$ never equals $(A_j, B_j)$ and never equals $(B_j, A_j)$.

Every request and every change accumulates.

Print $Q + 1$ lines.

On the first line print the minimum cost of planting one tree in front of every building when only the $D$ requests given above are applied, before any later request or cost change.

On each of the next $Q$ lines print the minimum cost of planting one tree in front of every building right after that request or change is applied.

While the $D$ requests and all the later requests are processed, planting one tree in front of every building never becomes impossible.

In the example the campus has 4 buildings, and the designer first asks for the same tree in front of buildings 1 and 3. The best plan is a ginkgo, a plane tree, a ginkgo, and a ginkgo in order from building 1, at a cost of 17.

The three later changes work out as follows. After the request for the same tree in front of buildings 1 and 2, planting a ginkgo in front of every building becomes optimal, at a cost of 18. After the request for different trees in front of buildings 1 and 4, the best plan is a plane tree, a plane tree, a plane tree, and a ginkgo, at a cost of 30. Finally the cost of planting a plane tree in front of building 4 drops from 100 to 1, so the best plan becomes a ginkgo, a ginkgo, a ginkgo, and a plane tree, at a cost of 18.