Description

Given a circuit diagram and a circuit board of specified size, $\text{Alice}$ and $\text{Bob}$ need to realize the circuit on the board.

You can regard the circuit board as an $n \times m$ grid.

The user’s circuit consists of several components, each of which may occupy one or more cells. We classify the cells occupied by components into two types:

• One type merely occupies the cell; afterward the cell will no longer be used, and no wire will run from that occupied position. Such cells are considered obstacles on the circuit board.
• The other type are interfaces of components. Although occupied by a component, wires may still be connected from these cells to other components to form the circuit.

For some wires in the circuit that connect two components, we specify them as $k$ pairs of cells on the board. Each pair must be connected by exactly one wire.

The same cell may belong to multiple pairs (for example, in some parallel circuits).

Any two wires must not intersect (but they may connect to the same cell that contains a component), and each edge of every cell on the board can be used by at most one wire. Therefore, each component interface can have at most $4$ wires attached. However, a cell not occupied by a component may be traversed by multiple wires.

Specifically, to ensure that wires do not intersect: one wire can enter a cell from the top edge and leave from the left edge, while another wire can enter from the bottom edge and leave from the right edge. Note that wires themselves are undirected; that is, the relation described by a pair of cells is an undirected edge. So the same configuration can also be described as entering from the left edge and leaving from the top edge, and entering from the right edge and leaving from the bottom edge. There are several similar valid pairings.

Now, $\text{Alice}$ wants to find a feasible scheme that minimizes the total length of all wires. $\text{Bob}$ wants to know how many schemes achieve this minimal total length.

Input Format

The first line contains three integers $n, m, k$, denoting the size of the circuit board and the number of pairs of cells that must be connected by wires.

Then follow $n$ lines, each containing $m$ integers, each being $0$ or $1$. A $0$ means the cell is usable; a $1$ means it is an obstacle and cannot be used.

Then follow $k$ lines, each containing $4$ integers $x1,y1,x2,y2$, giving one pair of cells to be connected by a wire. The row and column indices of cells are $0$-based, so $0 \le x1,x2 < n$ and $0 \le y1,y2 < m$.

This problem has multiple testcases (at most $30$). The input ends with a line 0 0 0.

Output Format

For each testcase, output two integers: the minimal total wire length, and the number of schemes that achieve this minimal length.

Output the number of schemes modulo $25619849$.

If there is no solution, output -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

Hint

Sample explanation:

• For the first testcase: there are $4$ paths between $(1,2)$ and $(2,1)$, and it is easy to see that the minimal total path length is $16$. In any feasible scheme, any path between $(1,2)$ and $(2,1)$ can correspond to any of the required $4$ paths. If we consider distinct shapes, there are $4$ different schemes. Taking into account permutations, $4! = 24$, the total number of schemes is $96$.
• For the second testcase: due to $3$ obstacle cells, there is only one feasible path.

Constraints:

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

In addition:

• There exists $10\%$ of the testdata with $k=1$.
• There exists $30\%$ of the testdata with $k \le 3$.

Translated by ChatGPT 5