Given a plane with $n$ horizontal lines and $m$ vertical lines, they intersect to form a grid of $n$ rows and $m$ columns. The intersection point of the $r$-th horizontal line from the top and the $c$-th vertical line from the left is called a grid point $(r, c)$. The line segment between any two horizontally or vertically adjacent grid points in the grid is called an edge, and each edge has a non-negative integer weight.

There are $T$ queries. Each query is in the following form: Given $k$ (the value of $k$ may differ for each of the $T$ queries) additional points, each located on a ray extending outward from the edge of the grid. All rays extending outward from the grid edges are numbered from $1$ to $2n + 2m$ in the order of top-left to top-right, top-right to bottom-right, bottom-right to bottom-left, and bottom-left to top-left, as shown in the figure below:

Figure 2: Numbering of the rays

For each query, the rays on which the different additional points are located are distinct. The line segment between each additional point and the nearest grid point is also called an edge and has a non-negative integer weight (note that a grid point at a corner may be connected to two additional points simultaneously).

Given the color of each additional point (black or white), please color each grid point within the grid either black or white such that the sum of the weights of all edges whose endpoints have different colors is minimized. Output this minimum sum of edge weights.

Input

The input is read from the file traffic.in.

The first line contains three positive integers $n, m, T$, representing the number of horizontal lines, vertical lines, and the number of queries, respectively.

The next $n - 1$ lines each contain $m$ non-negative integers. The $j$-th non-negative integer in the $i$-th line, $x1_{i,j}$, represents the weight of the edge between $(i, j)$ and $(i + 1, j)$.

The next $n$ lines each contain $m - 1$ non-negative integers. The $j$-th non-negative integer in the $i$-th line, $x2_{i,j}$, represents the weight of the edge between $(i, j)$ and $(i, j + 1)$.

Then, $T$ queries are input sequentially. The $i$-th query starts with a line containing a single positive integer $k_i$, representing the total number of additional points for this query. The next $k_i$ lines each contain three non-negative integers. The $j$-th line contains $x3_{i,j}, p_{i,j}, t_{i,j}$, representing the weight of the edge between the $j$-th additional point and the adjacent grid point, the ray number it is located on, and the color of the additional point ($0$ for white, $1$ for black), respectively. It is guaranteed that $p_{i,j}$ are distinct within the same query.

Multiple integers in each line are separated by spaces.

Output

The output is written to the file traffic.out.

Output $T$ lines, where the $i$-th line contains a single non-negative integer representing the minimum sum of weights of edges with different colored endpoints after coloring for the $i$-th query.

Examples

Input 1

2 3 1
9 4 7
3 3 8
10 5
2
19 3 1
17 9 0

Output 1

12

Note 1

Optimal strategy: $(1, 3), (1, 2), (2, 3)$ are black; $(1, 1), (2, 1), (2, 2)$ are white.

Examples 2-5

See files traffic/traffic2.in through traffic/traffic5.in and their corresponding .ans files in the contestant directory.

Constraints

For all data, $2 \le n, m \le 500$, $1 \le T \le 50$, $1 \le k_i \le \min\{2(n + m), 50\}$, $1 \le \sum_{i=1}^T k_i \le 50$, $0 \le x \le 10^6$, $1 \le p \le 2(n + m)$, $t \in \{0, 1\}$. It is guaranteed that for each $i \in [1, T]$, $p_{i,j}$ are distinct.