题目描述

对于用户给出的电路图和指定大小的电路板，$\text{Alice}$ 和 $\text{Bob}$ 需要将电路在电路板上实现出来。

所谓电路板，可以看作是一个 $n \times m$ 的格子图。

用户给定的电路由若干电路原件组成，每一个电路原件可能会占用一个或多个格子。这里，我们将被电路原件占据的格子分为两类。

第一类只是纯粹占据了这个格子，之后这个格子不会再被使用，也不会从被占据的位置连出去任何的电路线。这样的格子被我们视作是电路板上的障碍物。

还有一类格子，我们称为是电路原件的接口，上面虽然被电路原件占用，但是仍有可能从其中连出去一些电路线到其它的电路原件上，从而形成电路。

对于电路图中一些链接某两个原件的电路线，我们可以指定为电路板上的 $k$ 个格子对，要求每对格子对之间连一条电路线。

同一个格子可能属于多个格子对（比如一些并联电路）。

任意两条电路线不能相交（但可以连接到同一个有着电路原件的格子中），且电路板上的每一个格子的每一条边都只能经过一条电路线。（所以每一个电路原件的接口上只能接出去最多 $4$ 条不同的电路线）。然而，每一个不被电路原件占用的格子内却可以经过多条电路线。

具体来说：为了保证电路线不相交，可以一条电路线从上边界进入当前格子，从左边界离开这个格子，另外一条电路线可以从下边界进入格子，从右边界出去。（需要注意的是：电路线本身是没有方向感念的，即格子对描述的边关系是无向边。所以这样的方案也可以描述为从左边界进入后从上边界出去，从右边界进入后从下边界出去）相似的方案还有好几种。

现在，$\text{Alice}$ 希望找到一个可行方案，使得路径的总长度最短。而 $\text{Bob}$ 则希望知道满足最短长度的方案有多少种。

输入格式

第一行三个整数 $n,m,k$，表示电路板的大小，以及需要连接电路线的格子对个数。

接下来 $m$ 行，每行 $n$ 个整数，为 $0$ 或 $1$。$0$ 代表当前格子可以用，否则表示有障碍，不能使用。

接下来 $k$ 行，每行 $4$ 个整数 $x1,y1,x2,y2$，给出一组格子对，表示对应的电路要连接的两个格子。格子的行列都从 $0$ 开始编号，所以 $0 \le x1,x2 < n$，$0 \le y1,y2 < m$。

本题有多组数据（最多 $30$ 组），输入文件最后以 0 0 0 结束。

输出格式

对于每组数据，输出两个整数，最短电线长度和最短电线长度的方案数。

方案数只需要输出对 $25619849$ 取余数后的结果。

如果无解，输出 -1 0。

4 4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 2 2 1
2 1 1 2
1 2 2 1
2 1 1 2
4 4 2
0 0 1 1
0 0 0 0
1 0 0 0
0 0 0 0
1 0 2 2
0 0 3 0
0 0 0

16 96
12 1

提示

样例解释：

第一组数据：$(1,2)$ 与 $(2,1)$ 之间有 $4$ 条路径，立刻可以发现，最短路径长度和为 $16$。对于每一种可行方案，任意一条 $(1,2)$ 与 $(2,1)$ 之间的路径都可以对应要求的 $4$ 条路径中的任何一条。而若就形态来说，完全不同的方案有 $4$ 种，考虑到排列数 $4! = 24$，所以总的方案为 $96$ 种。

第二组数据：因为有 $3$ 个障碍点，所以可行路径只有一条。

数据规模：

对于 $20\%$ 的数据：$n, m \le 4$。

对于 $40\%$ 的数据：$n, m \le 8$。

对于 $100\%$ 的数据，$n, m \le 9$，$k \le 10$。

此外：

存在 $10\%$ 的数据：$k=1$。

存在 $30\%$ 的数据：$k \le 3$。