Younghee's Errand

Younghee, the class president at Snoops High School, has an errand from her teacher. She must find Chulsoo somewhere on campus and tell him to go to the faculty office.

She has no time for it, though, because she has to solve the math workbook problems due in the next period. So she lends Kere a secret map that marks where she hid her candies and chocolates, and asks whether Kere can run the errand instead.

The map has these properties:

• The map is an $N \times N$ grid, and each cell is one area of the school.
• From each cell, you can move up, down, left, or right. The distance between adjacent cells is the same in every direction.
• A cell with candy is marked o, and a cell with chocolate is marked x. A cell with nothing has no mark.

Kere runs the errand in these steps. "Choose uniformly at random" means picking one of the available options, with each option having the same probability.

1. Find the set $S$ of shortest paths from the top-left cell to Chulsoo's cell that pass through at least one candy or chocolate cell.
2. If $S$ is empty, Kere gets 0 candies and 0 chocolates. Otherwise, choose one path in $S$ uniformly at random. Walk along it and collect every candy and chocolate on the way.

Kere wants to know the expected number of candies and the expected number of chocolates collected with this map.

The problem is that Younghee does not know where Chulsoo is. So assume Chulsoo can be in any cell, and find the average of the expected candy count and the average of the expected chocolate count over all possible positions.

Some cells are known to hold an item, but the map may have labeled them as the wrong kind. Each time a report says the information for cell $(r, c)$ is wrong, flip that cell's label and report the average expected values on the updated map.

The first line contains the grid size $N$ ($1 \le N \le 1000$).

The next $N$ lines each contain a string $s_i$. The $j$-th character of $s_i$ describes row $i$, column $j$ of the map.

• .: nothing in this cell
• o: candy in this cell
• x: chocolate in this cell

The next line contains the number of reports $Q$ ($1 \le Q \le 100000$). The next $Q$ lines each contain two integers $r_i$ and $c_i$ ($1 \le r_i, c_i \le N$). The cell at $(r_i, c_i)$ changes from chocolate to candy, or from candy to chocolate.

It is guaranteed that cell $(r_i, c_i)$ is not . in the original map.

Print the answers as follows. Let $M = 998244353$. If the average expected value is the irreducible fraction $A / B$, print $A \cdot B^{M-2}$ modulo $M$. For every Chulsoo position, the size of $S$ is either 0 or coprime to $M$, and this is guaranteed.

On the first line, print the average expected candy count and the average expected chocolate count for the original map, separated by a space.

From line 2 through line $Q+1$, line $i+1$ prints the same two averages for the map after applying the first $i$ reports, separated by a space.

For the original map, the candy average is computed as follows.

• If Chulsoo is at row 1, column 1, no path contains a candy or chocolate, so Younghee gets 0 candies.
• If Chulsoo is at row 1, column 2, the result is also 0 candies.
• If Chulsoo is at row 2, column 1, the only shortest path with a candy or chocolate goes down one cell. It collects 1 candy.
• If Chulsoo is at row 2, column 2, there are two shortest paths: an L-shaped path and the other L-shaped path. The first collects no candy, and the second collects 1 candy. The expected candy count is 0.5.

So the average is $(0 + 0 + 1 + 0.5) / 4 = 3/8$, and the output is $3 \cdot 8^{M-2}$ modulo $M$, which is 623902721.

The chocolate average works out similarly to $(0 + 0 + 0 + 1) / 4 = 1/4$, so the output is $1 \cdot 4^{M-2}$ modulo $M$, which is 748683265.

After the first report, the map has no chocolate, so the chocolate average is 0.

After the second report, the map is the same as the original, so the first and third output lines are identical.