조개 줍기

바닷가에 있는 정올시는 정사각형 격자 모양의 지역으로 나뉘어 있다. 각 지역에는 한 가구가 살고, 가장 왼쪽 위 지역에는 수산시장이 있다. 수산시장이 있는 지역에도 한 가구가 산다.

각 지역에서 수산시장으로 갈 때는 다음 두 가지 이동만 쓴다.

1. 바로 위에 붙어 있는 지역으로 이동
2. 바로 왼쪽에 붙어 있는 지역으로 이동

각 가구는 매일 수산시장으로 출근하면서 지나가는 지역에서 조개를 주워 수산시장에 판다. 출발하는 지역과 수산시장이 있는 지역에서도 조개를 주울 수 있다.

지역마다 자연보호를 위해 그 지역을 지나가는 한 가구가 주울 수 있는 조개 개수의 최댓값이 정해져 있다. 여러 가구가 지나가도 가구마다 그 최댓값만큼 주울 수 있을 만큼 조개는 충분하다.

예를 들어 격자의 크기가 3행 3열이고, 한 가구가 주울 수 있는 조개 개수의 최댓값이 아래 왼쪽 표와 같다고 하자.

각 지역의 가구가 하루에 수산시장에 팔 수 있는 조개 개수의 최댓값은 오른쪽 표와 같다. 맨 오른쪽 아래 지역에서 출발하는 가구는 위로 두 번, 왼쪽으로 두 번 움직이는 경로에서 $8+6+7+2+3=26$개를 주울 수 있고, 이것이 그 지역의 최댓값이다. 아홉 지역의 최댓값을 모두 더하면 $3+5+12+7+9+18+12+15+26=107$이다.

정올시의 성실한 공무원들은 주기적으로 각 지역의 조개 수를 조사해 한 가구가 주울 수 있는 조개 개수의 최댓값을 고친다. 급격한 변화는 위험하므로 한 번의 조정은 최댓값을 $+1$ 또는 $-1$만큼만 바꾼다. 조정하지 않은 지역의 최댓값은 그대로 유지된다. 예를 들어 위 왼쪽 표에서 1행 2열의 $2$가 $3$으로 바뀌면 두 표는 다음과 같이 바뀐다.

각 칸의 최댓값의 초기 상태와 변화 명령이 주어진다. 초기 상태와 각 변화 직후에 대해, 모든 지역이 하루에 수산시장에 팔 수 있는 조개 개수 최댓값의 합을 구하는 프로그램을 작성하라.

첫째 줄에 격자의 행과 열의 개수를 나타내는 정수 $N$이 주어진다 ($2 \le N \le 1500$).

다음 $N$개의 줄에는 각 칸에서 주울 수 있는 조개 개수의 최댓값이 맨 윗 행부터 한 줄에 한 행씩 주어진다. 한 행의 값은 가장 왼쪽 열부터 차례로 나열되며, 모두 $0$ 이상 $1000$ 이하이다.

다음 $N$개의 줄에는 변화 명령이 한 줄에 하나씩 주어진다. 각 명령은 문자 U 또는 D로 시작하고, 빈칸 하나를 사이에 두고 행 번호와 열 번호가 차례로 주어진다. U는 그 칸에서 주울 수 있는 조개 개수의 최댓값을 $1$ 늘리고, D는 $1$ 줄인다. 줄인 결과가 음수가 되는 경우는 없다. 각 명령은 앞의 명령이 모두 적용된 상태에 적용된다.

첫째 줄에 초기 상태에서 모든 지역이 하루에 팔 수 있는 조개 개수 최댓값의 합을 출력한다. 이어서 변화 명령을 순서대로 하나씩 적용할 때마다, 적용한 뒤의 합을 한 줄에 하나씩 출력한다. 전체 출력은 $N+1$줄이다.