【题目描述】

落尘现在正在探究一个数字迷宫。

首先，这个数字迷宫有一个参数 𝑝，保证这是一个质数。

数字迷宫可以抽象为一个 𝑛 行 𝑚 列的矩阵，第 𝑖 行第 𝑗 列的格子上写有一个数字$a_{𝑖,𝑗}<𝑝$。

接下来，落尘会进行 𝑇 次探究任务。每次任务形如询问落尘从 $(𝑠_𝑥,𝑠_𝑦)$ 以初始价值 ≤𝑝 开始游走，使得到达 $(𝑡_𝑥,𝑡_𝑦)$这个格子时所得价值为 𝑞 的最少游走步数。游走规则为落尘从当前格子选择一个四联通的格子走过去（不能越过地图边界），记原先价值为 𝑏， 则这步走完得到的价值为$(𝑏+𝑎_{𝑖,𝑗})^2mod 𝑝$。

同时落尘不希望走太远的路，如果一次任务不能找到不超过16步的方案则判断无解，输出-1。

【输入格式】

从文件 maze.in 中读入数据。

第一行一个整数表示 𝑇。

接下来 𝑇 次读入，每次先是三个整数表示 𝑛,𝑚,𝑝。

接下来 𝑛 行每行共 𝑚 个整数表示 $𝑎_{𝑖,𝑗}$。

然后一行六个整数表示这次任务的$𝑠_𝑥,𝑠_𝑦,𝑡_𝑥,𝑡_𝑦,𝑤,𝑞$。

【输出格式】

输出到文件 maze.out 中。

共 𝑇 行表示答案。

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

2

【样例1解释】

第1步：从 (1,1) 走到 (1,2)：

• 当前位置：(1,1)，当前价值：𝑏=1

• 走到 (1,2)，格子值：$𝑎_{1,2} =2$

• 新价值：$(𝑏+𝑎_{𝑖,𝑗})^2mod𝑝 = (1+2)^2mod7 = 9mod7 =2$

第2步：从 (1,2) 走到 (1,3)：

• 当前位置：(1,2)，当前价值：𝑏=2

• 走到 (1,3)，格子值：$𝑎_{1,3} =3$

• 新价值：$(𝑏+𝑎_{𝑖,𝑗})^2mod𝑝 = (2+3)^2mod7 = 25mod7 =4$

数据规模与约定

对于所有数据，$𝑇 ≤5，𝑛,𝑚≤100，𝑝≤10^7$，𝑝 为质数，地图在满足数据范围情况下随机生成。