영희의 심부름

스눕스 고등학교의 반장 영희는 선생님이 주신 심부름을 해야 한다. 심부름의 내용은 학교 어딘가에 있는 철수에게 가서 교무실로 가라고 전하는 것이다.

하지만 영희는 당장 다음 교시 숙제인 수학 익힘책 풀이를 해야 해서 심부름을 할 시간이 없다. 그래서 영희는 학교 곳곳에 숨겨 둔 사탕과 초콜릿의 위치가 표시된 비밀 지도를 케레에게 빌려주고, 대신 심부름을 해 줄 수 있는지 물어보았다.

비밀 지도는 다음과 같다.

• 지도는 $N \times N$ 격자이며, 각 칸은 학교의 한 구역을 나타낸다.
• 각 칸에서 상하좌우로 움직일 수 있으며, 상하좌우로 인접한 칸 사이의 거리는 모두 같다.
• 사탕이 있는 구역은 o, 초콜릿이 있는 구역은 x로 표시한다. 아무것도 없는 구역에는 별다른 표시가 없다.

케레의 심부름 과정은 다음과 같다. "무작위로 고른다"는 가능한 선택지 중 하나를 모두 같은 확률로 고른다는 뜻이다.

1. 왼쪽 위 칸에서 출발해 철수의 위치에 도달하는 최단 경로 중, 사탕이나 초콜릿이 있는 칸을 하나 이상 지나가는 경로들의 집합 $S$를 구한다.
2. $S$가 공집합이면 케레는 사탕과 초콜릿을 0개 얻는다. $S$가 공집합이 아니면 $S$의 경로 중 하나를 무작위로 고른다. 그 경로를 따라 이동하며 모든 사탕과 초콜릿을 얻는다.

케레는 이 지도로 심부름을 할 때 얻을 수 있는 사탕의 기댓값과 초콜릿의 기댓값을 알고 싶어 한다.

문제는 철수의 위치를 아직 모른다는 것이다. 그래서 철수가 지도의 어느 구역에든 있을 수 있다고 보고, 가능한 모든 위치에 대해 사탕 기댓값의 평균과 초콜릿 기댓값의 평균을 구하려 한다.

또한 일부 구역은 무언가 있는 것이 확실하지만, 사탕인지 초콜릿인지 잘못 표기되어 있을 수 있다. 칸 $(r, c)$의 정보가 잘못되었다는 제보가 들어올 때마다 지도를 수정하고, 수정된 지도에서의 기댓값의 평균을 알려 주어야 한다.

첫째 줄에 격자의 크기 $N$ ($1 \le N \le 1000$)이 주어진다.

다음 $N$개의 줄에 문자열 $s_i$가 주어진다. $s_i$의 $j$번째 문자는 지도의 $i$행 $j$열에 담긴 정보를 나타낸다.

• .: 아무것도 없는 구역
• o: 사탕이 있는 구역
• x: 초콜릿이 있는 구역

다음 줄에 제보의 수 $Q$ ($1 \le Q \le 100000$)가 주어진다. 다음 $Q$개의 줄에 두 정수 $r_i$, $c_i$ ($1 \le r_i, c_i \le N$)가 주어진다. 이는 $(r_i, c_i)$ 위치의 정보를 바꾸라는 뜻이다. 초콜릿이었다면 사탕으로, 사탕이었다면 초콜릿으로 바꾼다.

$(r_i, c_i)$는 최초 지도에서 .이 아닌 칸임이 보장된다.

기댓값의 평균은 다음과 같이 출력한다. $M = 998244353$이라 할 때, 기댓값의 평균이 기약 분수 $A / B$이면 $A \cdot B^{M-2}$를 $M$으로 나눈 나머지를 출력한다. 철수의 위치와 관계없이 1단계의 집합 $S$의 크기는 0이거나 $M$과 서로소임이 보장된다.

첫째 줄에 최초 지도에서 얻을 수 있는 사탕 기댓값의 평균과 초콜릿 기댓값의 평균을 공백으로 구분해 출력한다.

둘째 줄부터 $Q$개의 줄에 걸쳐, $i+1$번째 줄에는 1번째부터 $i$번째까지의 수정을 모두 적용한 지도에서의 사탕 기댓값의 평균과 초콜릿 기댓값의 평균을 공백으로 구분해 출력한다.

최초 지도에서 사탕 기댓값의 평균을 구하는 과정은 다음과 같다.

• 철수가 1행 1열에 있으면 사탕과 초콜릿을 지나는 최단 경로가 없으므로 영희는 사탕을 0개 얻는다.
• 철수가 1행 2열에 있는 경우도 마찬가지로 사탕을 0개 얻는다.
• 철수가 2행 1열에 있으면 사탕과 초콜릿을 지나는 최단 경로는 아래로 한 칸 내려가는 것뿐이다. 이 경로에서 사탕을 1개 얻는다.
• 철수가 2행 2열에 있으면 최단 경로는 'ㄱ'자 모양과 'ㄴ'자 모양 두 가지이다. 'ㄱ'자 경로에서는 사탕을 얻지 못하고, 'ㄴ'자 경로에서는 사탕을 1개 얻는다. 따라서 얻을 수 있는 사탕의 기댓값은 0.5개이다.

따라서 기댓값의 평균은 $(0 + 0 + 1 + 0.5) / 4 = 3/8$이므로, $3 \cdot 8^{M-2}$를 $M$으로 나눈 나머지인 623902721을 출력한다.

비슷한 방법으로 최초 지도에서 초콜릿 기댓값의 평균이 $(0 + 0 + 0 + 1) / 4 = 1/4$임을 알 수 있다. 따라서 $1 \cdot 4^{M-2}$를 $M$으로 나눈 나머지인 748683265를 출력한다.

첫 번째 제보 이후 지도에는 초콜릿이 없으므로 초콜릿 기댓값의 평균은 0이다.

두 번째 제보 이후 지도의 상태는 최초 지도와 같으므로, 첫 번째 줄과 세 번째 줄의 출력 값은 완전히 같다.