#2747. [HEOI2012]野外探险

题目描述

小H是一位探险家。在险峻的珠穆朗玛峰，原始辽阔的非洲大草原，美丽冻人的南极大陆等 地方都留下过这位探险家的足迹。这次，他来到了位于南美洲充斥着大量毒虫猛兽的以及各 式各样传说的亚马逊热带雨林进行探险。为此，他花了许多时间来准备这次激动人心的探险。 在准备就绪后，小H和他的助手在当地导游的带领下踏入了这片雨林。 通过GPS定位系统，他们获得了雨林大致的地图。这个地图是一个n行m列的字符网格 图，'.'表示的是空地，'*'表示的是不可通行的区域，'#'表示的是需要清理的区 域，'H'表示小H所在的位置，该区域是空地。他们的移动方式有t种，用 a[i],bi表示，假设他们所在的位置为第x行第y列，那么他们下一步的位置将 是第x+a[i]行第y+b[i]列，也可以是反方向，即第x-a[i]行第y-b[i]列。小H一行人每天 可在选择一种移动方式，朝着正方向或者反方向连续走若干步之后停下，不可以不走。在当 天的行走过程中，他们不可以到达不可通行的区域，如果他们到达了一个需要清理的区域， 他们会停止移动。为了以后探险的方便，他们会用该天剩下的时间来清理该区域，之后该区 域将永久变成空地。 现在，为了使探险活动顺利的进行，他们将q个询问通过网络发送给了你，询问他们在 第di天能到达的区域个数，题目保证不会有无路可走的情况。你能帮助他解决 这个问题吗？

输入格式

输入的第1行包含三个正整数，分别表示n、m、t。
在第2行至第n+1行中，每行都有m个字符（只可能是'.'，'*'，'#'，'H'，其中'H' 有且只有一个）。
在第n+2行至第n+t+1行中，每行有两个整数，分别表示a[i]，b[i]（a[i]，b[i]不可能 同时为0）。
在第n+t+2行包含一个正整数，表示q。
在第n+t+3行至第n+t+q+2行共有q个整数，表示他们所询问的时间点（即d[i]）。

输出格式

输出共q行，对于每一个询问，输出他们所能走到的地点的个数。

样例

样例输入

3  3 2  

H#. *..   

…   

1  0  

0  1  

2   

 1 2   

样例输出

1   

4   

数据范围与提示

【数据范围】

对于20%的数据，满足n，m<=4, q <= 100；

对于70%的数据，满足n，m<=300；

对于100%的数据，满足n，m<=1000, t<=5, q<=1000, 0<=d[i]<=10^9；