Wombats

The city of Brisbane has been overrun by mutant wombats (an Australian animal that looks a bit like a raccoon) grown to an enormous size. Your job is to guide people safely to the south.

Brisbane's roads form a large grid. There are $R$ horizontal roads running east to west, numbered $0, 1, \dots, R-1$ from north to south, and $C$ vertical roads running north to south, numbered $0, 1, \dots, C-1$ from west to east. The figure below shows an example of roads numbered this way.

The wombats advance from the north and people flee to the south. A person may move freely east or west along horizontal roads, but along vertical roads they may only move south, the safe direction.

The intersection of horizontal road $P$ and vertical road $Q$ is written $(P, Q)$. Each road segment between two neighboring intersections may contain some wombats, and that count can change over time. You must guide a person who arrives at some intersection on the northern edge (horizontal road $0$) to a specified intersection on the southern edge (horizontal road $R-1$) so that the total number of wombats encountered along the way is as small as possible.

First you are given the size of the grid and the number of wombats on each road segment. Then $E$ events occur in order, each of one of two kinds.

• change: the number of wombats on some road segment changes.
• escape: a person arrives at some intersection on horizontal road $0$, and you must find the minimum number of wombats they encounter on the way to a specified intersection on horizontal road $R-1$.

The figure above shows the initial state of a map with $R = 3$ horizontal roads and $C = 4$ vertical roads, with the wombat count on each segment shown. Suppose the following events occur in order.

• A person arrives at intersection $A = (0, 2)$ and wants to flee to intersection $B = (2, 1)$. The minimum number of wombats encountered is $2$, which the dashed path in the figure confirms.
• Another person arrives at intersection $X = (0, 3)$ and wants to flee to intersection $Y = (2, 3)$. The minimum here is $7$.
• Two change events occur. The wombat count on the topmost segment of vertical road $0$ becomes $5$, and the wombat count on the middle segment of horizontal road $1$ becomes $6$. Check the circled numbers in the figure below.

A third person again arrives at intersection $A = (0, 2)$ and wants to flee to intersection $B = (2, 1)$. This time the minimum number of wombats encountered is $5$.

Given the layout of the roads, the number of wombats on each segment, and the events in the order they occur, write a program that processes them.

The first line contains the number of horizontal roads $R$ and the number of vertical roads $C$, separated by a space. ($2 \le R \le 5000$, $1 \le C \le 200$)

The next $R$ lines describe the horizontal segments. Line $i$ ($0 \le i \le R-1$) contains $C-1$ integers H[i][0] through H[i][C-2], where H[i][j] is the number of wombats on the horizontal segment between intersections $(i, j)$ and $(i, j+1)$.

The next $R-1$ lines describe the vertical segments. Line $i$ ($0 \le i \le R-2$) contains $C$ integers V[i][0] through V[i][C-1], where V[i][j] is the number of wombats on the vertical segment between intersections $(i, j)$ and $(i+1, j)$.

The next line contains the number of events $E$.

The following $E$ lines each contain one event, in the order they occur. Each event has one of the three forms below.

• 1 P Q W: set the number of wombats on the horizontal segment between $(P, Q)$ and $(P, Q+1)$ to $W$. ($0 \le P \le R-1$, $0 \le Q \le C-2$, $0 \le W \le 1000$)
• 2 P Q W: set the number of wombats on the vertical segment between $(P, Q)$ and $(P+1, Q)$ to $W$. ($0 \le P \le R-2$, $0 \le Q \le C-1$, $0 \le W \le 1000$)
• 3 V1 V2: ask for the minimum number of wombats encountered when moving from $(0, V1)$ to $(R-1, V2)$. ($0 \le V1 \le C-1$, $0 \le V2 \le C-1$)

Events of type 1 and 2 occur at most $500$ times combined, and events of type 3 occur at most $200000$ times. At every moment the number of wombats on any single segment is at most $1000$.

For each event of type 3, print the minimum number of wombats encountered when moving from $(0, V1)$ to $(R-1, V2)$, one per line in the order the events occur.