题目描述

平方取模迷宫

在一个 m 行 n 列的迷宫中，每个格子都有一个整数。你从起点(qx,qy) 出发，初始能量值为起点的格子值。每次你可以向上、下、左、右四个方向移动一格，但不能走出迷宫，也不能重复经过同一个格子。

每当你移动到一个新格子时，你的能量值会按照以下规则更新：

新能量值 = ( 当前能量值 + 新格子的值 )^2 mod q

你的目标是到达终点 (zx,zy)，并且到达时能量值恰好等于 w。求最少需要移动多少步。

如果无法在 16 步以内（包含 16 步） 到达终点并满足条件，则输出 -1。

输入格式

第二行两个整数 m 和 n，表示迷宫有 m 行 n 列。

接下来 m 行，每行 n 个整数，第 i 行第 j 个数表示格子 (i, j) 的数值。

整个程序只读入一次迷宫。

接下来 T 行，每行六个整数 qx, qy, zx, zy, q, w，分别表示：

起点的行、列 qx, qy

终点的行、列 zx, zy

取模参数 q

目标和 w

（行列均从 1 开始编号）

输出格式

对于每组测试数据，输出一个整数，表示最少步数。如果无法在 16 步内到达终点并满足条件，输出 -1。

每组输出占一行。

3
3 3
1 2 3
4 5 6
7 8 9
1 1 1 1
10 5
1 1 1 2
100 4
1 1 3 3
1000 81

-1
3
4

1
3 3
1 2 3
4 5 6
7 8 9
1 1 3 3
1000 604

6

数据范围与约定

数据范围 1≤T≤10 1≤n≤m≤900 1≤qx,zx≤m， 1≤qy,zy≤n 1≤q≤10 0≤w<q 起点不参与能量计算，初始能量直接为起点的格子值。

每次移动后，能量值更新为 (当前能量 + 新格子值)^2 % q。

不能重复经过同一个格子。

如果 16 步内无法到达终点或到达时能量值不等于 w，输出 -1。