Description

Using a GPS system, they obtained a rough map of the rainforest. The map is an $n$-by-$m$ character grid: '.' denotes empty ground, '*' denotes impassable terrain, '#' denotes an area that needs to be cleared, and 'H' marks Xiao H's position, which is also empty ground.

There are $t$ types of movements, denoted by $a[i]$, $b[i]$ ($1 \leq i \leq t$). If they are currently at row $x$, column $y$, then their next position can be row $x + a[i]$, column $y + b[i]$, or the opposite direction, row $x - a[i]$, column $y - b[i]$. Each day, they may choose exactly one movement type and move a positive number of steps continuously in the forward or backward direction, then stop; they are not allowed to stay put.

During that day’s movement, they may not enter any impassable cells ('*'). If they reach a cell marked '#', they stop moving immediately. For the rest of the day, they clear that cell; afterwards, it permanently becomes empty ground ('.').

They send you $q$ queries over the network, asking for the number of cells they can reach on day $d[i]$ ($1 \leq i \leq q$). It is guaranteed that there is no situation where they cannot move at all. Can you help them?

Input Format

• The first line contains three positive integers $n$, $m$, and $t$.
• Lines $2$ to $n+1$: each line contains $m$ characters (each is one of '.', '*', '#', 'H'; there is exactly one 'H').
• Lines $n+2$ to $n+t+1$: each line contains two integers $a[i]$ and $b[i]$ (not both $0$).
• Line $n+t+2$: a single integer $q$.
• Lines $n+t+3$ to $n+t+q+2$: each of the next $q$ lines contains one integer $d[i]$, the queried day.

Output Format

Output $q$ lines. For each query, output the number of cells that can be reached on day $d[i]$.

3 3 2
H#.
*..
…
1 0
0 1
2
1
2 

1
4

Hint

Constraints:

• For 20% of the testdata, $n, m \leq 4$, $q \leq 100$.
• For 70% of the testdata, $n, m \leq 300$.
• For 100% of the testdata, $n, m \leq 1000$, $t \leq 5$, $q \leq 1000$, $0 \leq d[i] \leq 10^9$.

HEOI 2012 Day 2 Task 3.

Translated by ChatGPT 5