問題文
在天下一王国,某种拼图游戏非常流行。 这个拼图游戏中, 1 × 1 将由 的正方形方块按边连接成的多边形称为拼块,并将给定的拼块 H × W 铺满矩形就完成了。
高桥君完成了这个拼图!
但是,他想试试看用食指能把完成的拼图破坏多少, 1 所以打算只按住从左数第 x 从上往下第几个。 y 块积木,并向下拖动。 当某个拼块包含会被向下拖动的积木时,这个拼块的所有积木都会被向下拖动。
此外,与被拖动积木的底边相连的积木也会被一起向下拖动。
他在进行这个拖动操作时, 1 × 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
- 1 行表示拼图纵向块的数量的整数 H (1 ≦ H ≦ 20000)、横向块的数量的整数 W (1 ≦ W ≦ 16) 以空格分隔给出
- 2 从行 H 行,给出拼图的信息。其中 i(1 ≦ i ≦ H) 行中, W 个字符的字符串被给予。在这些字符中 j(1 ≦ j ≦ W) 第一个字符 c_{i,j} 表示从上向下第 i 左起第 thj 个块的类型。当纵向或横向相邻的块是相同类型时,这些 2 个块表示同一件拼块。同时, c_{i,j} 必须是大写字母。
- H + 2 行表示高桥君将要拖动的候选位置的数量的整数 Q (1 ≦ Q ≦ 100000) 被给予
- H + 3 从行 Q 行,表示高桥君将要拖动的候选方块的位置信息 1 按行给出。 其中 i(1 ≦ i ≦ Q) 在线 i 表示第几候选块的位置 2 整数 x_i, y_i (1 ≦ x_i ≦ W, 1 ≦ y_i ≦ H) 用空格隔开给出
部分点
Q=1 中的所有测试用例都回答正确,您将获得部分分数。 30 点。 如果您正确回答了所有满足
出力
对于高桥君所拉的每个位置,可以拉多少块, 1 逐行 Q 行。在输出末尾添加换行符。
入力例1
5 3 AAB ABB CDE FFH GHH 2 1 1 2 3
出力例1
15 7
(x,y) 从左起 x 从上往下第几个。 y 这是第__块。
(1,1) 的块是 A。向下拖动 A,所有块都会被拖动。 (2,3) 是 D。向下拖动 D,D、F、G、H 会被拖动。
入力例2
2 2 AB BA 2 1 1 2 1
出力例2
2 2
请注意,即使使用相同的字母,也有可能是不同的块。
入力例3
5 5 AABAA ACDEA AFGHA AIJKA AAAAA 1 3 1
出力例3
25
B通过拖动__块,可以拖动所有块。