走一个大整数迷宫

题号：NC274864
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给一个 $n\times m$ 矩阵迷宫，第 $i$ 行第 $j$ 列的值为 $c_{i,j}$ ， $LH$ 在迷宫中迷路了，他需要你的帮助。

$LH$ 当前在 $(1,1)$ 的位置，出口在 $(n,m)$ ，这个迷宫有一个计数器，只有当计数器的值模 $(p-1)$ 的余数为 $0$ 时迷宫出口才会开门（出口没有开门意味着即使在 $(n,m)$ 的位置也不能逃出去）。

$LH$ 每一秒会向迷宫的上下左右四个方向走一步（不可以不走），并且不能走出迷宫的边界，假设 $LH$ 从 $(i,j)$ 走到了 $(i',j')$ ，然后计数器将会加上 $c_{i',j'}$ 。

特别的，计数器初始是 $c_{1,1}$ 。

$c_{i,j}=a_{i,j}\times p^{2^{b_{i,j}}}$ 。

现在 $LH$ 问你，他最快需要多久才可以走出迷宫。

输入描述:

第一行输出三个整数 。

接下来输入一个  行  列的矩阵 。

接下来输入一个  行  列的矩阵 。

。

输出描述:

输出一个整数，表示满足条件的最短路径长度。

假如不存在一条路径满足条件，输出 。

示例1

输入

复制

输出

复制

备注:

。

第一秒，从  走到 ，计数器的值为 。

第二秒，从  走到 ，计数器的值为 。

第三秒，从  走到 ，计数器的值为 。

第四秒，从  走到 ，计数器的值为 。

第五秒，从  走到 ，计数器的值为 。

第六秒，从  走到 ，计数器的值为 ，是  的倍数，逃出迷宫。