AT_tenka1_2014_qualA_e パズルの移動

在天下一王国，一款拼图游戏大受欢迎。在这个游戏中，将若干 $1 \times 1$ 的小方块通过边缘相连构成的多边形称作拼图块。当你将给定的拼图块完美拼接成一个 $H \times W$ 的矩形时，拼图便完成了。 高桥君已经成功完成了这款拼图。但他产生了一个有趣的念头：想测试一下用一根食指最多能破坏多少个拼图块。具体来说，他会按住某个拼图块，并将其拖动到最下面。若某个拼图块包含了被按住的方块，这个拼图块的所有部分都会一起被拖动。而且，与被拖动的拼图块底部相连的拼图块也会因此一起被拖动。 高桥君想在进行这个拽动操作之前，预先知道会有多少个 $1 \times 1$ 的方块被卷入其中。 现在给出 $Q$ 个位置作为高桥君可能按住并拖动的选择。你需要对于每一个位置，输出最终被拖动的拼图块的数目。

从标准输入读取数据，格式如下： > $ H $ $ W $ $ c_{1,1} $ $ c_{1,2} $ ... $ c_{1,W} $ $ c_{2,1} $ $ c_{2,2} $ ... $ c_{2,W} $ : $ c_{H,1} $ $ c_{H,2} $ ... $ c_{H,W} $ $ Q $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ : $ x_Q $ $ y_Q $ - 第一行包含两个整数 $H\ (1 \leq H \leq 20000)$ 和 $W\ (1 \leq W \leq 16)$，分别表示拼图的行数和列数。 - 接下来的 $H$ 行中，每行提供一个长度为 $W$ 的字符串，描述拼图的具体信息。字符串中的第 $j$ 个字符 $c_{i,j}$ 表示第 $i$ 行、第 $j$ 列位置的拼图块类型。若相邻（横向或纵向）的拼图块类型相同，则说明它们属于同一个拼图块。注意，$c_{i,j}$ 均为大写字母。 - 第 $H + 2$ 行包含整数 $Q\ (1 \leq Q \leq 100000)$，表示高桥君可能按压的拼图块位置的数量。 - 随后的 $Q$ 行中，每行包含两个整数 $x_i,\ y_i\ (1 \leq x_i \leq W,\ 1 \leq y_i \leq H)$，表示第 $i$ 个候选的按压位置。

输出共 $Q$ 行，其中每行对应一个位置，表示从该位置开始拽动所能影响到的方块总数。每行输出结尾需换行。

###部分分数 若在所有 $Q=1$ 的测试用例中答案正确，可以获得 $30$ 分的部分分。 ### 样例解释 1. 对于位置 $(1, 1)$，该方块是 A。拖动 A 后，所有方块都会被拖动。 2. 对于位置 $(2, 3)$，该方块是 D。拖动 D 后，会有 D, F, G, H 被拖动。 注意，即便使用相同字母，不同拼图块也可能为独立的拼图块，这可能影响结果。对于某些拼图，某一类的方块确保所有的拼图块都被拖动。 **本翻译由 AI 自动生成**