Xiao Q is a designer who is in charge of the design of a park. She has already determined the location and content of each attraction, as well as the paths between them. However, she is struggling with how to set the environment (theme) around the attractions. For some paths, if the themes of the attractions at both ends are inconsistent, the transition might seem too abrupt; for other paths, if the themes are the same, it might seem too monotonous. Furthermore, depending on the content of the attraction, different themes may be more suitable for different attractions. She wants to use a program to decide which attractions should have a Western theme and which should have a Sci-Fi theme. However, Xiao Q's programming ability is limited, so she wants you to help her solve this problem.

The park has $n$ attractions and $m$ undirected paths connecting two attractions. The $i$-th path connects the $x_i$-th and $y_i$-th attractions. If the themes of the attractions at both ends of the $i$-th path are the same, an aesthetic value of $c_i$ is obtained; if the themes are different, an aesthetic value of $d_i$ is obtained. If the $i$-th attraction uses the Western theme, an aesthetic value of $w_i$ is obtained; if it uses the Sci-Fi theme, an aesthetic value of $s_i$ is obtained.

The park's layout is carefully designed by Xiao Q. Xiao Q guarantees that in the park she designed, one can reach all attractions starting from any attraction; she guarantees that each path connects two different attractions; she guarantees that no two different paths connect the same pair of attractions; and for any four attractions $A, B, C, D$, there are no two paths that share any points other than their common endpoints, and these six paths connect every pair of the four attractions—$AB, AC, AD, BC, BD, CD$.

Below are some examples of park layouts that are definitely not designed by Xiao Q:

Cannot reach attraction 3 from node 1

For attractions 1, 4, 5, 6, there exist six paths that share no edges: 1→4, 4→5, 5→6, 6→1, 4→3→6, 1→2→5 connecting every pair of these four attractions

You need to set the theme for each attraction to either the Sci-Fi theme or the Western theme such that the sum of the aesthetic values of all attractions and paths is maximized.

Xiao Q may modify the values of $w_i$ and $s_i$ for an attraction or the values of $c_i$ and $d_i$ for a path by recalculating them. She will make $Q$ modifications, and you need to output the maximum total aesthetic value before any modifications and after each modification. Note that the modifications are not independent of each other.

Input

The first line contains two positive integers $n, m$.

The next $n$ lines each contain two non-negative integers, where the $i$-th line represents $w_i, s_i$.

The next $m$ lines each contain four positive integers, where the $i$-th line represents $x_i, y_i, c_i, d_i$.

The $(n+m+2)$-th line contains a non-negative integer $Q$.

The next $Q$ lines each contain three positive integers $x, a, b$. If $x \le n$, it means Xiao Q changes $w_x$ to $a$ and $s_x$ to $b$; if $n < x \le n+m$, it means Xiao Q changes $c_{x-n}$ to $a$ and $d_{x-n}$ to $b$.

Output

Output $Q+1$ lines, each containing a single positive integer. The first line represents the answer before any modifications, and the $(i+1)$-th line ($1 \le i \le Q$) represents the answer after the $i$-th modification.

Examples

Input 1

2 1
2 3
4 7
1 2 5 7
1
1 2 6

Output 1

16
18

Note

The park layout is shown in the figure below.

Before the modification, the optimal solution is to use the Western theme for attraction 1 and the Sci-Fi theme for attraction 2, with a total aesthetic value of 2+7+7=16. After the modification, the optimal solution is to use the Sci-Fi theme for attraction 1 and the Sci-Fi theme for attraction 2, with a total aesthetic value of 6+7+5=18.

Input 2

5 6
4 8
5 2
3 7
5 3
4 9
1 2 3 8
1 3 7 4
2 3 9 2
2 4 7 9
1 5 4 9
3 5 6 4
4
4 2 6
9 6 3
7 4 2
2 8 5

Output 2

72
71
70
68
71

Subtasks

It is guaranteed that $2\le n \le 100000, Q \le 100000$; $x_i, y_i \le n$, $x \le n+m$, $s_i, w_i, c_i, d_i, a, b \le 10^6$. It is guaranteed that the layout is designed by Xiao Q.

In general, parks have entrances and exits. However, in this problem, you can consider the entrances and exits of the park as attractions themselves.

A cycle is defined as a set of paths where the start and end points are the same, and no intermediate attractions are repeated.

• Subtask 1 (2 points): $Q=0$, $m=n-1$;
• Subtask 2 (3 points): $n \le 17$, $Q\le 17$;
• Subtask 3 (7 points): $Q=0$, each path belongs to at most one cycle;
• Subtask 4 (5 points): $Q=0$;
• Subtask 5 (13 points): $n, Q \le 1000$;
• Subtask 6 (19 points): $s_i=w_i=0$, $x > n$, each path belongs to at most one cycle;
• Subtask 7 (17 points): $s_i=w_i=0$, $x > n$;
• Subtask 8 (23 points): $m=n-1$;
• Subtask 9 (11 points): No special restrictions.