3271 -- Lilypad Pond

Language:

Lilypad Pond

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 1888		Accepted: 482

Description

FJ has installed a beautiful pond for his cows' aesthetic enjoyment and exercise.

The rectangular pond has been partitioned into square cells of M rows and N columns (1 ≤ M ≤ 30; 1 ≤ N ≤ 30). Some of the cells have astonishingly sturdy lilypads; others have rocks; the remainder are just beautiful, cool, blue water.

Bessie is practicing her ballet moves by jumping from one lilypad to another and is currently located at one of the lilypads. She wants to travel to another lilypad in the pond by jumping from one lilypad to another.

Surprising only to the uninitiated, Bessie's jumps between lilypads always appear as a chess-knight's move: one move in one direction and then two more in the orthogonal direction (or perhaps two in one direction and then one in the orthogonal direction).

Farmer John is observing Bessie's ballet drill and realizes that sometimes she might not be able to jump to her destination lilypad because intermediary lilypads are missing.

Ever thrifty, he wants to place additional lilypads so she can complete her quest (perhaps quickly, perhaps by using a large number of intermediate lilypads). Of course, lilypads cannot be placed where rocks already intrude on a cell.

Help Farmer John determine the minimum number of additional lilypads he has to place, and in how many ways he can place that minimum number.

Input

Line 1: Two space-separated integers: M and N
Lines 2..M+1: Line i+1 describes row i of the pond using N space-separated integers with these values: 0 indicates empty water; 1 indicates a lilypad in place; 2 indicates rock in place; 3 indicates the lilypad Bessie starts on; 4 indicates the lilypad Bessie wants to travel to.

Output

Line 1: One integer: the minimum number of additional lilypads required. If it is not possible to help Bessie jump to her destination, print -1.
Line 2: One integer: the total number of possible ways the additional lilypads can be positioned. This number is guaranteed to fit into a single 64-bit signed integer. Do not output this line if line 1 contains -1.

Sample Input

Sample Output

2
3

Hint

Two lilypads are required. There are three ways to place them: row 4 column 2 and row 2 column 3; row 1 column 3 and row 3 column 2; or row 1 column 3 and row 2 column 5:

R1C2,R2C3       R1C3,R3C2       R1C3,R2C5
1 0 0 0 0       1 0 X 0 0       1 0 X 0 0
3 0 X 0 0       3 0 0 0 0       3 0 0 0 X
0 0 2 0 0       0 X 2 0 0       0 0 2 0 0
0 X 0 4 0       0 0 0 4 0       0 0 0 4 0

Source

USACO 2007 February Gold