测试数据来自 system/1869

描述

对于用户给出的电路图和指定大小的电路板，Alice和Bob需要将电路在电路板上实现出来。
所谓电路板，可以看作是一个n*m的格子图。
用户给定的电路由若干电路原件组成，每一个电路原件可能会占用一个或多个格子。这里，我们将被电路原件占据的格子分为两类。第一类只是纯粹占据了这个格子，之后这个格子不会再被使用，也不会从被占据的位置连出去任何的电路线。这样的格子被我们视作是电路板上的障碍物。还有一类格子，我们称为是电路原件的接口，上面虽然被电路原件占用，但是仍有可能从其中连出去一些电路线到其它的电路原件上，从而形成电路。
对于电路图中一些链接某两个原件的电路线，我们可以指定为电路板上的K个格子对，要求每对格子对之间连一条电路线。
同一个格子可能属于多个格子对（比如一些并联电路）。
任意两条电路线不能相交（但可以连接到同一个有着电路原件的格子中），且电路板上的每一个格子的每一条边都只能经过一条电路线。（所以每一个电路原件的接口上只能接出去最多4条不同的电路线）。然而，每一个不被电路原件占用的格子内却可以经过多条电路线。
具体来说：为了保证电路线不相交，可以一条电路线从上边界进入当前格子，从左边界离开这个格子，另外一条电路线可以从下边界进入格子，从右边界出去。（需要注意的是：电路线本身是没有方向感念的，即格子对描述的边关系是无向边。所以这样的方案也可以描述为从左边界进入后从上边界出去，从右边界进入后从下边界出去）
相似的方案还有好几种。
现在，Alice希望找到一个可行方案，使得路径的总长度最短。而Bob则希望知道满足最短长度的方案有多少种。

格式

输入格式

第一行三个整数，n，m，k，表示电路板的大小，以及需要连接电路线的格子对个数。
接下来m行，每行n个整数，为0或1，0代表当前格子可以用，否则表示有障碍，不能使用。
接下来k行，每行4个整数x1，y1，x2，y2，给出一组格子对，表示对应的电路要连接的两个格子。格子的行列都从0开始编号，所以0 <= x1 , x2 < m，0 <= y1 , y2 < n。
本题有多组数据（最多30组），输入文件最后以0 0 0结束。

输出格式

对于每组数据，输出两个整数，最短电线长度和最短电线长度的方案数。
方案数只需要输出对25619849取余数后的结果。
如果无解，输出 -1 0。
注意，自环是不被允许的，所以若有(x1,y1)=(x2,y2)的边存在，最后一定是无解的。

样例1

样例输入1

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

样例输出1

16 96
12 1

限制

对于20％的数据，n,m<=4。
对于40％的数据，n,m<=8。
对于100％的数据，n,m<=9, k<=10。
此外存在10％的数据：k=1。
此外还存在30％的数据：k<=3。

各个测试点3s

提示

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

来源

SDOI 2014