Problem Background

To entertain and exercise his cows, Farmer John has built a beautiful pond. This rectangular pond is divided into $M$ rows and $N$ columns of squares ($1 \leq M, N \leq 30$). Some squares are surprisingly sturdy lotuses, some are rocks, and the rest are beautiful, pure, azure waters that may hide treasures.

Bessie is practicing ballet and stands on a lotus, wanting to jump to another lotus. She can only jump from one lotus to another, neither into the water nor onto rocks.

Bessie's dance steps resemble the knight's moves in chess: each move involves either moving one square horizontally and two squares vertically, or two squares vertically and one square horizontally. At most, Bessie has eight possible directions to move.

John has been watching Bessie's ballet practice and noticed that sometimes she cannot reach the end because of missing lotuses in between. So he wants to add some lotuses to help Bessie complete her task, of course, not on rocks.

Problem Description

However! John discovered an interesting thing while planting lotuses: some squares cannot be directly planted with lotuses because... to be honest, the soil in those squares is mostly genuine platinum, which hinders the normal growth of lotuses! Fortunately, John has just learned the method of mining platinum and has the relevant tools. He also found that squares mined for platinum can be planted with lotuses normally without worrying about soil deficiency. (Since Bessie is eager to practice, John will not mine platinum in squares where he does not plan to plant lotuses.)

Mining platinum is tiring, just like planting lotuses; both consume 1 point of John's energy (meaning turning a platinum square into a lotus square requires 2 points of energy). John initially has $P$ points of energy to plant lotuses or mine platinum.

Help John calculate the minimum amount of energy, denoted as $S$, needed to help Bessie complete her task, and the number of ways, denoted as $W_S$, to consume this energy to help Bessie complete her task. Also, calculate the maximum amount of platinum, denoted as $G$, that can be mined while consuming $S$ points of energy to help Bessie complete her task, and the number of ways, denoted as $W_G$, to mine $G$ pieces of platinum while consuming $S$ points of energy to help Bessie complete her task.

If it is not possible to help Bessie within $P$ points of energy, output -1.

If it is not possible to mine platinum within $S$ points of energy, the second line should output -1.

Input Format

The first line contains three space-separated integers: $P$, $M$, and $N$.

The next $M$ lines, each containing $N$ space-separated integers, describe the state of the pond:

• $0$ represents water,
• $1$ represents a lotus,
• $2$ represents a rock,
• $3$ represents Bessie's starting point,
• $4$ represents Bessie's destination,
• $5$ represents a platinum deposit.

Output Format

The first line contains two space-separated integers: $S$ and $W_S$ (the minimum energy required and the number of ways to achieve it; if it is not possible to help, output -1).

The second line contains two space-separated integers: $G$ and $W_G$ (the maximum amount of platinum mined and the number of ways to achieve it; if it is not possible to mine platinum within $S$ points of energy, output -1).

If the first line is -1, do not output the second line.

Ensure that the output numbers do not exceed long long.

Sample Input and Output

Input Sample #1

4 5 6
0 0 0 1 0 0
2 0 0 2 0 0
0 0 5 0 0 0
3 0 0 0 4 0
0 0 2 0 0 0

Output Sample #1

2 2
1 1

Input Sample #2

3 3 2
3 5
4 2
0 1

Output Sample #2

-1

Notes

John can make a small profit from the mined platinum, but if he uses extra energy to mine platinum without planting lotuses, Bessie will be very angry!

见题面 Input 部分

见题面 Output 部分