Minimum Edge Weight Cut in a Colored Grid

You are given n horizontal lines and m vertical lines on a plane, which form an n×m grid. The intersection between the r-th horizontal line (from top) and the c-th vertical line (from left) is denoted by the grid point \((r,c)\).

Any line segment between two grid points that are adjacent horizontally or vertically is called an edge and is assigned a nonnegative integer weight. In addition, there are additional edges defined as follows. Consider all rays that start from the boundary of the grid and go outward. These rays are numbered from \(1\) to \(2n+2m\) in the order: top side (from left to right), right side (from top to bottom), bottom side (from right to left), and left side (from bottom to top). Each ray originates from a grid boundary point. (Note that a corner grid point may be attached to two different additional edges.) For an additional edge, you are given its weight (a nonnegative integer) and a color assigned to its additional point (either black or white). This additional edge connects the additional point and its nearest grid point.

You are then given \(T\) queries. In each query, you are given \(k\) additional points. The rays on which these additional points are located are all distinct in the same query. For each additional point, its color is specified, and the corresponding additional edge has the given weight.

Your task is to color every grid point in black or white so that the sum of the weights of all edges whose two endpoints are colored differently is minimized. Here, the set of edges includes both the internal grid edges and the additional edges connecting an additional point (with fixed color) and its nearest grid point.

For example, if an additional point is black and its edge weight is \(w\), then if its nearest grid point is colored white the edge contributes \(w\) to the total cost; otherwise it contributes 0. Similarly, for a grid edge with weight \(w\) connecting two adjacent grid points, if the two grid points are assigned different colors, it contributes \(w\) to the cost.

Output the minimum possible total cost for each query.

Input Format

• Line 1: Three integers \(n\), \(m\), and \(T\) separated by spaces.
• Next \(n\) lines: Each line contains \(m-1\) integers. The \(j\)-th integer on the \(i\)-th line denotes the weight of the horizontal edge between grid points \((i,j)\) and \((i,j+1)\). (\(1 \le i \le n, 1 \le j \le m-1\))
• Next \(n-1\) lines: Each line contains \(m\) integers. The \(j\)-th integer on the \(i\)-th line denotes the weight of the vertical edge between grid points \((i,j)\) and \((i+1,j)\). (\(1 \le i \le n-1, 1 \le j \le m\))
• Then, for each of the \(T\) queries:
  • The first line contains an integer \(k\) (the number of additional points in this query).
  • Each of the next \(k\) lines contains an integer \(p\), an integer \(w\), and a character \(c\) separated by spaces. Here, \(p\) (\(1 \le p \le 2n+2m\)) is the ray number, \(w\) is the weight of the additional edge, and \(c\) is either B (for black) or W (for white).

Mapping for Additional Points

An additional point on ray number \(p\) is connected to a grid point determined as follows:

• If \(1 \le p \le m\): grid point \((1, p)\) (top side).
• If \(m+1 \le p \le m+n\): grid point \((p-m, m)\) (right side).
• If \(m+n+1 \le p \le 2m+n\): let \(\text{idx} = p - (m+n)\); grid point \((n, m - \text{idx} + 1)\) (bottom side, from right to left).
• If \(2m+n+1 \le p \le 2m+2n\): let \(\text{idx} = p - (2m+n)\); grid point \((n - \text{idx} + 1, 1)\) (left side, from bottom to top).

Output Format

• For each query, output a single integer — the minimum possible total cost.

Note: There is at least one test case and your submitted code should correctly solve all of them.

inputFormat

The first line contains three integers \(n\), \(m\), and \(T\) (n rows, m columns, and number of queries). The following \(n\) lines each contain \(m-1\) integers denoting the weights of horizontal edges. The next \(n-1\) lines each contain \(m\) integers denoting the weights of vertical edges. Then \(T\) queries follow. Each query starts with an integer \(k\), followed by \(k\) lines, each containing an integer \(p\) (the ray number), an integer \(w\) (the edge weight), and a character \(c\) (B for black, W for white) separated by spaces.

Example:

2 2 3
1
2
3 4
1
1 5 B
2
2 2 W
7 1 B
2
8 3 W
4 4 B

outputFormat

For each query, output one line containing a single integer – the minimum total cost of edges whose endpoints are colored differently.

Example:

0
1
3

sample

2 2 3
1
2
3 4
1
1 5 B
2
2 2 W
7 1 B
2
8 3 W
4 4 B

0
1
3

</p>