地图探险

• 时间限制：$1.0$ 秒
• 空间限制：$512\text{ MB}$

题目描述

小 W 在一个 $n \times n$ 大小的地图上探险，地图上有空位和障碍，空位为 .，障碍为 #，小 W 需要从起点到达终点，在这个过程中，他一碰到障碍或者走出边界就会失败。

小 W 有一个 $(x_1,y_1)$ 到终点的长度为 $m$ 的移动序列，记小 W 目前所在的位置为 $(x,y)$，则小 W 下一步可以走到 $(x + u,y + v)$ 或不移动。在这里如果不移动也算一步。$u,v$ 为在 $[-1,1]$ 中的任意一个整数，由于一些原因，小 W 分别在每一步中不能使用一些 $u,v$，在第 $i$ 步，一种 $u,v$ 是否能被使用会用一个长度为 $8$ 的 01 字符串 $s_i$ 来表示，这八个约束的 $u,v$ 分别为：$(-1,-1)$，$(-1,0)$，$(-1,1)$，$(0,-1)$，$(0,1)$，$(1,-1)$，$(1,0)$，$(1,1)$。

现在有 $q$ 组询问，每组询问表示小 W 在 $m$ 步内是否能在中途不碰到障碍的情况下从 $(x_1,y_1)$ 走到 $(x_2,y_2)$，能则输出到达 $(x_2,y_2)$ 所需要的最小步数（不移动算入移动步数内），不能则输出 $-1$。

输入格式

本题多测，第一行输入两个正整数 $c,t$ 分别表示 Subtask 编号和测试数据组数，特别的，样例 $c = 0$。

对于每组测试数据：

• 第一行输入五个正整数 $n,m,q,x_1,y_1$。
• 之后输入 $n$ 行每行长度为 $n$ 的字符串表示初始地图的每个坐标的类型。
• 之后输入 $m$ 行第 $i$ 行长度为 $8$ 的字符串 $s_i$ 表示对于第 $i$ 步的约束。
• 之后输入 $q$ 行每行两个正整数 $x_2,y_2$。

输出格式

对于每组测试数据：

• 输出 $q$ 行，每行一个整数表示你的答案。

样例 1 输入

0 1
3 4 5 2 2
...
...
...
00001000
00000010
00001000
01000000
2 3
1 3
1 2
3 2
1 1

样例 1 输出

1
4
4
2
-1

样例 1 解释

对于第一组测试数据，第一步从 $(2,2)$ 移动至 $(2,3)$ 即可满足要求，可以证明这是需要的最少步数。

对于第二组测试数据，第一步从 $(2,2)$ 移动至 $(2,3)$，第二、三步不移动，第四步从 $(2,3)$ 移动至 $(1,3)$ 即可满足要求，可以证明这是需要的最少步数。

数据规模与约定

对于所有数据，保证：

• $1 \le t \le 10^5$；
• $1 \le n \le 3000$；
• $1 \le m,q \le 10^5$；
• $\sum n^2 \le 3000^2$；
• $\sum m,\sum q \le 10^6$。

本题采用捆绑测试，各子任务特殊性质如下：