웜뱃

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

브리즈번 시의 도로는 커다란 격자 모양으로 되어 있다. 동서 방향으로 놓인 수평 도로는 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 ≤ R ≤ 5,000
• 1 ≤ C ≤ 200
• change는 최대 500번 (changeH() 또는 changeV() 호출)
• escape()는 최대 200,000번 호출
• 한 세그먼트에 있는 웜뱃의 마릿수는 항상 1,000 이하