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, \dots, (R - 1)~ in order from north to south, and ~C~ vertical roads that run north-to-south, numbered ~0, \dots, (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.

You must handle these events by implementing the routines init(), changeH(), changeV() and escape(), as described below.

Examples

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.

Implementation

You should submit a file implementing the procedures init(), changeH() and changeV() and the function escape(), as follows:

Grader Procedure: init()

C/C++

void init(int R, int C, int H[5000][200], int V[5000][200]);

Pascal

type wombatsArrayType = array[0..4999, 0..199] of LongInt;
procedure init(R, C : LongInt; var H, V : wombatsArrayType);

Description

This procedure gives you the initial layout of the map, and allows you to initialise any global variables and data structures. It will be called only once, before any calls to changeH(), changeV() or escape().

Parameters

• R: The number of horizontal roads.
• C: The number of vertical roads.
• H: A two-dimensional array of size ~R \times (C - 1)~, where ~H[P][Q]~ gives the number of wombats on the segment of horizontal road between intersections ~(P, Q)~ and ~(P, Q + 1)~.
• V: A two-dimensional array of size ~(R - 1) \times C~, where ~V[P][Q]~ gives the number of wombats on the segment of vertical road between intersections ~(P, Q)~ and ~(P + 1, Q)~.

Grader Procedure: changeH()

C/C++

void changeH(int P, int Q, int W);

Pascal

procedure changeH(P, Q, W: LongInt);

Description

This procedure will be called when the number of wombats changes on the horizontal road segment between intersections ~(P, Q)~ and ~(P, Q + 1)~.

Parameters

• P: Indicates which horizontal road is affected ~(0 \le P \le R - 1)~.
• Q: Indicates between which two vertical roads the segment lies ~(0 \le Q \le C - 2)~.
• W: The new number of wombats on this road segment ~(0 \le W \le 1\,000)~.

Grader Procedure: changeV()

C/C++

void changeV(int P, int Q, int W);

Pascal

procedure changeV(P, Q, W: LongInt);

Description

This procedure will be called when the number of wombats changes on the vertical road segment between intersections ~(P, Q)~ and ~(P + 1, Q)~.

Parameters

• P: Indicates between which two horizontal roads the segment lies ~(0 \le P \le R - 2)~.
• Q: Indicates which vertical road is affected ~(0 \le Q \le C - 1)~.
• W: The new number of wombats on this road segment ~(0 \le W \le 1\,000)~.

Grader Function: escape()

C/C++

int escape(int V1, int V2);

Pascal

function escape(V1, V2 : LongInt) : LongInt;

Description

This function should calculate the fewest possible wombats a person must pass when travelling from intersection ~(0, V1)~ to ~(R - 1, V2)~.

Parameters

• V1: Indicates where the person begins on horizontal row ~0~ ~(0 \le V1 \le C - 1)~.
• V2: Indicates where the person ends on horizontal row ~R - 1~ ~(0 \le V2 \le C - 1)~.
• Returns: The smallest number of wombats the person must pass.

Sample Session

The following session describes the sample above:

Constraints

• ~2 \le R \le 5\,000~
• ~1 \le C \le 200~
• At most ~500~ changes (calls to either changeH() or changeV)
• At most ~200\,000~ calls to escape()
• At most ~1\,000~ wombats on any segment at any time

Subtasks

Subtask	Points	Additional Input Constraints
1	9	~C = 1~
2	12	~R,C \le 20~, and there will be no calls to changeH() or changeV()
3	16	~R, C \le 100~, and there will be at most ~100~ calls to escape()
4	18	~C = 2~
5	21	~C \le 100~
6	24	(None)