SP10579 DESRUG - Desrugenstein

德斯鲁根斯坦市的城市规划乱成一团。地图上看似井然有序，因为城市是按照方形网格建造的，但实际上却没有统一的道路行驶方向。每个路口都标示了可以通行的方向（北、南、西、东）。市长丹尼尔·斯内克固执又懒惰，拒绝对现状做任何改变。因此，德斯鲁根斯坦的精神顾问大师乔达诺·马芬请求你，作为德斯鲁根斯坦的高级程序员和第十七级精神顾问，编写一个程序，以计算从一个路口 $(x, y)$ 到另一个路口 $(z, w)$ 的最小移动成本，考虑到这些混乱的街道。

输入文件包含多个测试用例。每个测试用例的第一行是一个整数 $N$，表示城市网格的边长（即 $N \times N$ 的方形网格）。当输入文件中的 $N = 0$ 时，表示结束，不再处理。接下来的 $N$ 行各自表示一条城市街道，从最北端（$N-1$ 行）到最南端。每行包含 $4 \times N$ 个整数，每个路口有四个值：$A$（北）、$B$（南）、$C$（西）、$D$（东）。如果可以朝某个方向行走，则相应值为 1，否则为 0。 城市地图之后，你的程序需要读取一个整数 $P$，表示问题的数量。接下来的 $P$ 行每行有四个整数 $x_0\ y_0\ x_1\ y_1$，询问：“从路口 $(x_0, y_0)$ 到路口 $(x_1, y_1)$ 的最小移动成本是多少？”从一个路口到相邻路口的移动成本为 1。

对于每个查询，如果两个路口之间没有按规则通行的有效路径，则输出「Impossible」；如果存在路径，则输出最小成本。每个测试用例的结果后都应输出一个空行。

$$1 \leq N \leq 100, 1 \leq P \leq 100$$ **本翻译由 AI 自动生成**