웜뱃

브리즈번 시는 돌연변이로 거대해진 웜뱃(호주에 사는 너구리와 비슷한 동물)에게 점령당했다. 당신의 임무는 사람들을 구조하는 것이다.

브리즈번 시의 도로는 큰 격자 모양이다. 동서 방향의 수평 도로가 $R$개 있고, 북쪽에서 남쪽으로 0번부터 $R-1$번까지 번호가 매겨져 있다. 남북 방향의 수직 도로는 $C$개 있고, 서쪽에서 동쪽으로 0번부터 $C-1$번까지 번호가 매겨져 있다. 다음 그림은 이렇게 번호가 매겨진 도로의 예이다.

웜뱃은 북쪽에서 쳐들어오고, 사람들은 남쪽으로 도망친다. 사람들은 가로 방향으로는 어느 쪽으로든 움직일 수 있지만, 세로 방향으로는 안전한 남쪽으로만 움직일 수 있다.

수평 도로 $P$와 수직 도로 $Q$의 교차로는 $(P, Q)$로 나타낸다. 두 교차로 사이의 도로 구간에는 웜뱃이 있을 수 있으며, 구간마다 웜뱃의 수는 시간에 따라 변할 수 있다. 당신의 임무는 북쪽 수평 도로 0번의 주어진 교차로에 도착한 사람을, 남쪽 수평 도로 $R-1$번의 주어진 교차로까지 보내는 경로를 알려주는 것이다. 이 경로는 가능한 한 적은 수의 웜뱃을 만나야 한다.

먼저 격자의 크기와 각 도로 구간에 있는 웜뱃의 수가 주어진다. 이후 $E$개의 이벤트가 차례로 주어지며, 각 이벤트는 다음 두 가지 중 하나이다.

• change: 어떤 도로 구간에 있는 웜뱃의 수가 바뀐다.
• escape: 사람 한 명이 북쪽 수평 도로 0번의 주어진 교차로에 도착한다. 이 사람을 가장 적은 수의 웜뱃을 만나며 남쪽 수평 도로 $R-1$번의 주어진 교차로까지 보내는 경로를 구해야 한다.

이벤트는 다음과 같이 정의된 함수 init(), changeH(), changeV(), escape()로 처리해야 한다.

• $2 \le R \le 5000$
• $1 \le C \le 200$
• change는 최대 500번 (changeH() 또는 changeV() 호출)이다.
• escape()는 최대 200,000번 호출된다.
• 한 구간에 있는 웜뱃의 수는 항상 1,000 이하이다.