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

브리즈번 시의 도로는 커다란 격자 모양으로 되어 있다. 동서 방향으로 놓인 수평 도로는 R 개가 있고, 북쪽에서 남쪽 방향으로 차례로 번호가 0, …, (R - 1) 로 매겨져 있다. 또한, 남북 방향으로 놓인 수직 도로는 C 개가 있고, 서쪽에서 동쪽 방향 으로 차례로 번호가 0, …, (C - 1) 로 매겨져 있다.

다음 그림은 이렇게 번호가 매겨진 도로의 예이다.

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

수평 도로 P 와 수직 도로 Q 의 교차로는 (P, Q) 로 표현한다. 두 교차로 사이 세그먼트에는 웜뱃들이 있을 수 있고, 몇 마리의 웜뱃이 있는지는 시간이 흐르면서 변할 수 있다. 여러분의 임무는 북쪽(수평 도로 0 번)의 주어진 교차로에 도착한 사람을 남쪽(수평 도로 R - 1 번)의 주어진 교차로로 가는 길을 알려주는 것인데, 이 경로를 지날 때 가능한 한 적은 수의 웜뱃을 만나야 한다.

먼저, 격자의 크기와 각 도로 세그먼트에 웜뱃이 몇 마리가 있는지가 주어진다. 다음에는 E 개의 이벤트가 차례로 주어지는데, 각 이벤트는 아래 두 가지 중 하나의 형태이다

예시

위 그림은 수평 도로가 R = 3 개, 수직 도로가 C = 4 개, 그리고 각 도로 세그먼트에 웜뱃이 몇 마리가 있는지 주어진 지도의 처음 상황이다.

다음 순서대로 이벤트가 발생한다고 하자.

• 한 사람이 교차로 A = (0, 2) 에 도착해서 교차로 B = (2, 1) 로 도망치고 싶어 한다. 이 때 만나는 웜뱃 마릿수의 최소값은 2 인데, 점선을 따라가면 이를 확인할 수 있다.
• 또 한 사람이 교차로 X = (0, 3) 에 도착해서 교차로 Y = (2, 3) 로 도망치고 싶어한다. 이 때 만나는 웜뱃 마릿수의 최소값은 7 인데, 또 점선을 따라가면 이를 확인할 수 있다.
• change 이벤트가 두 번 발생한다. 수직 도로 0 의 가장 위 세그먼트에 있는 웜뱃의 수가 5 마리로 바뀌고, 수평 도로 1 의 가운데 세그먼트에 있는 웜뱃의 수가 6 마리로 바뀐다. 아래 그림의 동그라미를 친 숫자를 확인해보자.

  

• 세 번째 사람이 교차로 A = (0, 2) 에 도착해서 교차로 B = (2, 1) 로 도망치고 싶어한다. 이번에는 만나게 되는 웜뱃의 최소 숫자가 5 마리이고, 다시 점선을 따라가면 이를 확인할 수 있다.

입력

• 첫 줄에는 수평도로의 개수 R 과 수직 도로의 개수 C 가 주어진다. 2 ≤ R ≤ 5 000 , 1 ≤ C ≤ 200
• 다음 여러 줄에는 도로에 있는 웜뱃의 최초 마리 수
• 다음 한 수는 질의 수와 change 정보가 주어진다. 3 2 1 이란 (0,3) 에서 (2,1) 3 3 3 ... (0,3) ????

출력

입출력 예

입력

3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1

출력

2
7
5

출처:ioi 2013