Wombats

Brisbane has been overrun by wombats, giant mutant versions of the raccoon-like animals native to Australia. Your job is to rescue the people.

Brisbane's roads form a large grid. There are $R$ east-west horizontal roads, numbered 0, ..., $R-1$ from north to south. There are $C$ north-south vertical roads, numbered 0, ..., $C-1$ from west to east. The following figure shows roads numbered this way.

The wombats are coming from the north, and the people flee south. People can move sideways in either direction, but they can only move vertically toward the south, which is the safe direction.

The intersection of horizontal road $P$ and vertical road $Q$ is written $(P, Q)$. Wombats may be on the road segment between two intersections, and the number of wombats on a segment can change over time. Your task is to tell a person who arrives at a given intersection on horizontal road 0 (the north edge) how to reach a given intersection on horizontal road $R-1$ (the south edge). The route must meet as few wombats as possible.

First, the grid size and the number of wombats on each road segment are given. Then $E$ events follow in order. Each event is one of the following two types.

• change: The number of wombats on a road segment changes.
• escape: A person arrives at a given intersection on horizontal road 0. Find a route that sends this person to a given intersection on horizontal road $R-1$ while meeting the fewest wombats.

These events must be handled with the functions init(), changeH(), changeV(), and escape(), defined as follows.

• $2 \le R \le 5000$
• $1 \le C \le 200$
• change is called at most 500 times (changeH() or changeV() calls).
• escape() is called at most 200,000 times.
• The number of wombats on any segment is always at most 1,000.