Optimized Circuit Routing

Given an \(n \times m\) grid representing a circuit board, some cells are occupied by circuit components. Among these, some cells are interfaces that allow connections and may serve as endpoints for wiring, while other occupied cells act as obstacles. In addition, you are given \(k\) pairs of interface cells on the board. For each pair, you must connect the two cells with a continuous wire path that traverses adjacent cells (up, down, left, or right) without reusing any grid edge across all wires.

Each grid cell’s edge can be traversed by at most one wire. Although wires may share the same grid node (cell), they cannot share any edge. In other words, even though an unoccupied cell may allow several wires to cross through it, every edge of every cell is reserved for at most one wire. This naturally also limits an interface cell to at most 4 connections.

Alice wishes to achieve a wiring layout with the minimum total length, where the length is defined as the total number of grid edges used over all wires. Meanwhile, Bob is curious about how many distinct wiring solutions exist that achieve this minimal total length. Note that if it is impossible to connect all pairs under the given constraints, you should output \(-1\) for the total length and \(0\) for the number of solutions.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) (with \(1 \leq n, m \leq 4\) and \(1 \leq k \leq 2\)) – the number of rows, columns, and the number of interface pairs to connect, respectively.

The next \(n\) lines each contain a string of \(m\) characters representing the circuit board. Each character is one of the following:

• I: an interface cell (available for wiring and serves as an endpoint).
• .: a free cell (available for wiring).
• #: an obstacle cell (not available for wiring).

The next \(k\) lines each contain four integers \(r_1\), \(c_1\), \(r_2\), and \(c_2\) (1-indexed) indicating that there is a required connection between the interface cell at \((r_1, c_1)\) and the interface cell at \((r_2, c_2)\).

outputFormat

Output two integers separated by a space: the minimal total length (i.e. the total number of grid edges used) of all wires and the number of distinct wiring solutions that achieve this minimal total length. If no valid wiring exists, output "-1 0".

sample

3 3 1
I..
...
..I
1 1 3 3

4 6