표지판 따라가기

Farmer John의 큰 정사각형 밭은 $(N+1)\times (N+1)$ ($1\le N\le 1500$) 격자로 나뉘어 있습니다. 셀 $(i, j)$는 위에서 $i$번째 행, 왼쪽에서 $j$번째 열의 셀을 뜻합니다. $1 \le i, j \le N$인 모든 셀 $(i, j)$에는 소 한 마리가 살고 있고, 오른쪽 또는 아래를 가리키는 표지판이 있습니다. $(N+1, N+1)$을 제외하고 $i=N+1$ 또는 $j=N+1$인 모든 셀에는 사료 통이 있습니다. $(i, j)$의 사료 통은 소 한 마리에게 먹이는 데 $c_{i,j}$ ($1 \le c_{i,j} \le 500$)가 듭니다.

매일 저녁 식사 시간에 Farmer John이 종을 울리면, 각 소는 표지판을 따라 사료 통에 도착할 때까지 이동하고 그 통에서 먹이를 받습니다. 그다음 소들은 다음 날을 위해 원래 자리로 돌아갑니다.

Farmer John은 매일 모든 소에게 먹이를 주는 데 드는 총비용을 알고 싶어 합니다. 매일 저녁 식사 전에, 셀 $(i, j)$의 소가 자기 표지판의 방향을 뒤집습니다(오른쪽에서 아래로, 또는 아래에서 오른쪽으로). 표지판은 다시 뒤집히기 전까지 이후 날에도 새 방향을 유지합니다.

매일 뒤집히는 표지판의 셀이 주어지면, 그날의 비용을 출력하세요. 총 $Q$일입니다.

첫 줄에 $N$ ($1 \le N \le 1500$)이 주어집니다. 다음 $N+1$개 줄은 위에서 아래 순서로 격자를 나타냅니다. 처음 $N$개 줄은 길이 $N$의 방향 문자열(오른쪽이면 R, 아래면 D)과 그 뒤에 붙는 비용 $c_{i,N+1}$로 이루어집니다. 마지막 줄에는 $N$개의 비용 $c_{N+1,j}$가 주어집니다. 다음 줄에 $Q$ ($1 \le Q \le 1500$)가 주어집니다. 이어서 $Q$개의 줄에 각각 두 정수 $i$, $j$ ($1 \le i, j \le N$)가 주어지며, 그날 방향이 뒤집히는 표지판의 좌표입니다.

$Q+1$개의 줄을 출력합니다. 첫 줄은 처음의 총비용이고, 이어지는 $Q$개의 줄은 각 뒤집기 후의 총비용입니다.

처음 뒤집기 전에는 $(1, 1)$과 $(1, 2)$의 소가 각각 1, $(2, 1)$의 소가 100, $(2, 2)$의 소가 500의 비용이 들어 총 602입니다. 첫 번째 뒤집기 후에는 $(1,1)$의 표지판이 R에서 D로 바뀌어 $(1, 1)$의 소가 100의 비용이 들고, 나머지는 그대로이므로 총 701이 됩니다. 두 번째와 세 번째 뒤집기는 같은 표지판을 다시 뒤집어 값이 오갑니다. 네 번째 뒤집기 후에는 $(1, 1)$과 $(2, 1)$의 소가 모두 500의 비용이 들어 총 1501이 됩니다.