Escape from the Mutated Wombats

In Brisbane, mutated wombats have taken over the city. You must guide people from danger in the north to safety in the south. The city is laid out as a grid with (R) horizontal roads (numbered from (0) to (R-1)) and (C) vertical roads (numbered from (0) to (C-1)). Each intersection is given by ((P, Q)). Between adjacent intersections are road segments that initially have a given number of wombats, and their numbers may change over time. People may move in both directions along a horizontal road, but on a vertical road they can only move southward (i.e. toward increasing row numbers).

Initially, you will be given the grid size and the number of wombats on each road segment. Then (E) events occur. Each event is one of two types:

1. Query event: A person appears at a specified intersection on the northmost road (row (0)) and needs to reach a specified intersection on the southmost road (row (R-1)). You must determine the minimum total number of wombats encountered along any valid route.

2. Update event: The number of wombats on one or more road segments changes. An update event specifies how many segments will be changed and for each one, whether it is a horizontal segment (denoted by H) or a vertical segment (denoted by V), its grid location, and its new value.

A valid move consists of one of the following:

• Moving horizontally on the same row. If moving from ((i,j)) to ((i,j+1)), the cost is the number on the horizontal segment on row (i) between columns (j) and (j+1); similarly, moving left uses the segment between ((i,j-1)) and ((i,j)).
• Moving vertically downward. From ((i,j)) to ((i+1,j)), the cost is the number on the vertical segment from row (i) to row (i+1) in column (j).

For example, consider a grid with (R = 3) and (C = 4). The initial weights on the road segments are provided as follows:

• Horizontal segments (three rows, each with three numbers): Row 0: 1, 1, 1 Row 1: 2, 1, 2 Row 2: 1, 1, 1

• Vertical segments (two rows, each with four numbers): Between row 0 and 1: 2, 3, 0, 3 Between row 1 and 2: 1, 1, 1, 4

Then, the following events occur:

1. A query event: A person at ((0,2)) wants to reach ((2,1)). The minimum total cost is 2 (for instance, via the route: ((0,2) \to (1,2)) using a vertical segment with cost 0, then ((1,2) \to (1,1)) using a horizontal segment with cost 1, then ((1,1) \to (2,1)) using a vertical segment with cost 1).

2. A query event: A person at ((0,3)) wants to reach ((2,3)). The best route is to move straight down column 3, with total cost (3+4=7).

3. An update event is issued with 2 changes:

   • The vertical segment on road (V) at top of column 0 (i.e. from ((0,0)) to ((1,0))) is updated from 2 to 5.
   • The horizontal segment on row 1, in the middle (i.e. between ((1,1)) and ((1,2))) is updated from 1 to 6.

4. Another query event: A person at ((0,2)) now wants to reach ((2,1)) again. After the updates, the previously best route now costs 7, but an alternate route (e.g. moving horizontally at the top row: ((0,2) \to (0,1)) with cost 1, then downward from ((0,1)) to ((1,1)) with cost 3, and finally downward from ((1,1)) to ((2,1)) with cost 1) now gives the minimum cost of 5.

Your task is to process the events and output the minimum cost for each query event.

inputFormat

The first line contains three integers: (R), (C), and (E), representing the number of horizontal roads, vertical roads, and events, respectively.

Then follow (R) lines, each containing (C-1) integers. The (i)-th line represents the horizontal road segments in row (i) (0-indexed), where the (j)-th integer is the cost on the segment connecting ((i, j)) and ((i, j+1)).

Next, there are (R-1) lines, each containing (C) integers. The (i)-th line represents the vertical road segments between row (i) and row (i+1), where the (j)-th integer is the cost on the segment from ((i,j)) to ((i+1,j)).

Finally, there are (E) events. Each event is either:

• A query event: A line beginning with Q followed by two integers (s) and (t), meaning a person appears at ((0, s)) who wants to reach ((R-1, t)).

• An update event: A line beginning with U followed by an integer (k), indicating that there are (k) update operations. This is followed by (k) lines, each with the format T i j v where T is either H (for a horizontal segment) or V (for a vertical segment). For a horizontal segment, i is the row and j is the index of the segment (between ((i, j)) and ((i, j+1))); for a vertical segment, i is the row index of the upper intersection and j is the column. v is the new cost for that segment.

outputFormat

For each query event, output a single line with the minimum total number of wombats (i.e. the minimum path cost) encountered along a valid route from the starting intersection to the destination.

sample

3 4 4
1 1 1
2 1 2
1 1 1
2 3 0 3
1 1 1 4
Q 2 1
Q 3 3
U 2
V 0 0 5
H 1 1 6
Q 2 1

2
7
5

</p>