J. Sally's Stroll (Hard Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The difference between the versions is that in this version $$$0 \leq q \leq n \cdot m$$$.

Sally the Snake has found herself in a field of grass and rocks. The field can be represented as a grid with $$$n$$$ rows and $$$m$$$ columns. Every cell in the grid is either '*' (grass) or '@' (rock).

Sally is a fast snake. Interestingly, she moves at a speed $$$k_v$$$ when moving up or down, while she moves at a speed of $$$k_h$$$ when moving left or right.

Sally is a peculiar snake, and every movement she takes must consist of the following steps:

  • Sally will choose an orthogonal direction (up, down, left, or right). If she decides to move up or down, she will move $$$k_v$$$ cells in that direction. Otherwise she will move $$$k_h$$$ cells in her desired direction. She can only do this if all the k cells in the path contain grass.
  • She will then choose a new direction (her direction can stay the same), and repeat the process from the previous step. Again, the k cells in her path must contain grass. Note that there are exactly two steps in each movement.

Sally is a curious snake. She wants to know how many pairs of grass cells $$$a$$$ and $$$b$$$ there are such that $$$a \neq b$$$ and she can reach cell $$$b$$$ after some number of complete movements from cell $$$a$$$. She calls this quantity the openness of the field.

Sally is a stupid snake. She needs you to find this value for her!

Lastly, Sally is in danger for the next $$$q$$$ minutes. Each minute from $$$1$$$ to $$$q$$$, a rock will fall from the sky and land in some cell of the grid (that contained grass). The cell that the rock falls on will no longer have grass and should be considered a rock cell.

Please help Sally by finding the openness of the field before any rocks fall, as well as after each rock falls onto the grid.

Input

The first line of input will contain four integers $$$n$$$, $$$m$$$, $$$k_v$$$, and $$$k_h$$$ ($$$2 \leq n, m \leq 10^5$$$, $$$n \cdot m \leq 2 \cdot 10^5$$$, $$$1 \leq k_v \lt n$$$, $$$1 \leq k_h \lt m$$$) — denoting the number of rows in the grid, number of columns in the grid, Sally's vertical speed, and Sally's horizontal speed, respectively.

The $$$i$$$th of the next $$$n$$$ lines contains a string of length $$$m$$$, consisting only of characters '*' and '@' — describing the $$$i$$$th row of the grid, where '*' denotes a grass cell and '@' denotes a rock cell.

The next line contains a single integer $$$q$$$ ($$$0 \leq q \leq n \cdot m$$$) — denoting the number of minutes for which rocks will fall from the sky.

The $$$j$$$th of the next $$$q$$$ lines contains two integers $$$r_j$$$ and $$$c_j$$$ ($$$1 \leq r_j \leq n$$$, $$$1 \leq c_j \leq m$$$) — denoting the row and column of which the $$$j$$$th rock will fall. It is guaranteed that the cell at row $$$r_j$$$ and column $$$c_j$$$ will be grass before the $$$j$$$th rock falls.

Output

Output $$$q + 1$$$ space separated integers, where the $$$j$$$th integer denotes the openness of the field after the first $$$j - 1$$$ rocks have fallen onto the field.

Examples
Input
2 2 1 1
**
@*
1
1 2
Output
2 0
Input
3 7 1 2
@@@@***
@******
***@@@@
3
2 6
1 5
1 7
Output
26 20 6 6