Problems
The city of Brisbane has been taken over by large mutated wombats, and you must lead the people to safety.
The roads in Brisbane are laid out in a large grid. There are R horizontal roads that run east to west, numbered 0, …, (R 1) in order from north to south, and C vertical roads that run north to south, numbered 0, …, (C 1) in order from west to east, as shown in the picture below.
The wombats have invaded from the north, and the people are escaping to the south. People can run along horizontal roads in either direction, but on vertical roads they will only run towards the south, towards safety.
The intersection of horizontal road P with vertical road Q is denoted (P, Q). Each segment of road between two intersections contains some number of wombats, and these numbers may change over time. Your task is to guide each person from some given intersection in the north (on horizontal road 0) to some given intersection in the south (on horizontal road R-1), taking them on a route that passes as few wombats as possible.
To begin, you will be given the size of the grid and the number of wombats on each road segment. Following this you will be given a series of E events, each of which is either:
a change: which alters the number of wombats on some road segment; or
an escape: where some person arrives at a given intersection on horizontal road 0, and you must find a route to a given intersection on horizontal road R-1 that passes the fewest possible wombats.
The picture above shows an initial map with R = 3 horizontal roads and C = 4 vertical roads, with the number of wombats marked on each segment. Consider the following series of events:
A person arrives at intersection A = (0, 2) and wishes to escape to intersection B = (2, 1). The smallest number of wombats she can pass is 2, as indicated by a dashed line.
Another person arrives at intersection X = (0, 3) and wishes to escape to intersection Y = (2, 3). The smallest number of wombats he can pass is 7, again indicated by a dashed line.
Two change events occur: the number of wombats on the top segment of vertical road 0 changes to 5, and the number of wombats on the middle segment of horizontal road 1 changes to 6. See the circled numbers in the picture below.
A third person arrives at intersection A = (0, 2) and wishes to escape to intersection B = (2, 1). Now the smallest number of wombats she can pass is 5, as indicated by the new dashed line.
Input
The first line contains the number of horizontal roads R (2≤R≤5,000) and the number of vertical roads C (1≤C≤200), separated by spaces.
The next R lines contain the number of wombats W (0≤W≤1,000) for each C-1 horizontal roads. If C = 1, the empty lines containing the number of wombats on horizontal roads (lines 2 through R+1) are not necessary.
Then, the R-1 line contains the number of wombats W (0≤W≤1,000) for each C vertical roads.
Next, the number of events occurring, E (1≤E), is only contained in a line.
From the next line onwards, event information is contained on each line. The format is as follows:
1 p q w : change event, the number of wombats between intersections (p, q) and (p, q+1) changes to w.
2 p q w: change event, the number of wombats between intersections (p, q) and (p+1, q) changes to w.
3 v1 v2: escape event, find a way to get from intersection (0, v1) to intersection (p-1, v2).
<Constraints>
2 ≤ R ≤ 5,000, 1 ≤ C ≤ 200
Change events can be occured up to 500 times, escape events up to 200,000 times
The number of wombats on each road after the first and change events is always less than 1,000.
Output
For each escape event, print the minimum number of wombats encountered along the given path, separated by rows.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 9 | C = 1 |
| #2 | 12 | R, C ≤ 20, and there will be no change event. |
| #3 | 16 | R, C ≤ 100, and there will be at most 100 escape events. |
| #4 | 18 | C = 2 |
| #5 | 21 | C ≤ 100 |
| #6 | 24 | (None) |
Example
3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1
2
7
5
You must sign in to write code.