Alice and Bob need to implement a circuit on a circuit board based on a given circuit diagram and a specified board size.

The circuit board can be viewed as an $n \times m$ grid.

The circuit provided by the user consists of several components, each of which may occupy one or more cells. We classify the cells occupied by components into two types. The first type simply occupies the cell; this cell will not be used again, and no circuit wires can be connected from it. We treat such cells as obstacles on the circuit board. The second type of cell is called a component interface; although occupied by a component, it is still possible to connect circuit wires from it to other components to form the circuit.

For some circuit wires in the circuit diagram that connect two components, we can specify $K$ pairs of cells on the circuit board, requiring a circuit wire to be connected between each pair.

A single cell may belong to multiple pairs (e.g., in some parallel circuits).

No two circuit wires can intersect (though they can connect to the same cell containing a component), and each edge of every cell on the circuit board can be traversed by at most one circuit wire. (Therefore, each component interface can have at most 4 different circuit wires connected to it.) However, a cell not occupied by a component can have multiple circuit wires passing through it.

Specifically: To ensure that circuit wires do not intersect, one circuit wire can enter the current cell from the top boundary and leave from the left boundary, while another circuit wire can enter from the bottom boundary and leave from the right boundary. (Note: Circuit wires themselves have no concept of direction; the edge relationship described by the cell pairs is undirected. Thus, this scheme can also be described as entering from the left boundary and leaving from the top, or entering from the right boundary and leaving from the bottom.)

There are several similar schemes.

Now, Alice wants to find a feasible scheme such that the total length of the paths is minimized. Bob wants to know how many such schemes satisfy the minimum total length.

Input

The first line contains three integers $n, m, k$, representing the size of the circuit board and the number of cell pairs that need to be connected.

The next $m$ lines each contain $n$ integers, which are either $0$ or $1$. $0$ indicates that the current cell is available, while $1$ indicates an obstacle that cannot be used.

The next $k$ lines each contain $4$ integers $x_1, y_1, x_2, y_2$, giving a pair of cells and indicating that the corresponding circuit should connect these two cells. The rows and columns of the cells are 0-indexed, so $0 \le x_1, x_2 < n$ and $0 \le y_1, y_2 < m$.

There are multiple test cases (up to 30), and the input ends with $0\ 0\ 0$.

Output

For each test case, output two integers: the minimum wire length and the number of ways to achieve this minimum length.

The number of ways should be output modulo $25619849$.

If there is no solution, output $-1\ 0$.

Examples

Input 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

Output 1

16 96
12 1

Note 1

For the first test case: There are 4 paths between $(1,2)$ and $(2,1)$. It is immediately apparent that the minimum total path length is 16. For each feasible scheme, any path between $(1,2)$ and $(2,1)$ can correspond to any of the 4 required paths. In terms of configuration, there are 4 distinct schemes. Considering the number of permutations $4! = 24$, the total number of schemes is $96$.

For the second test case: Because there are 3 obstacle points, there is only one feasible path.

Constraints

For 20% of the data: $n, m \le 4$. For 40% of the data: $n, m \le 8$. For 100% of the data: $n, m \le 9, k \le 10$.

Additionally: 10% of the data has $k=1$. 30% of the data has $k \le 3$.