Roger has finally finished running the DMPG and returns to one of his hobbies, playing chess.
Victor has given Roger the following chess-themed math problem: Given an chessboard with good squares, neutral squares, and evil squares, as well as a source and a destination, compute the minimum number of neutral squares that need to be converted to good squares such that there is a path for a knight to take from the source to the destination using only good squares. Along with that, compute how many subsets of that many neutral squares can be converted such that such a path can be constructed.
The first line will contain two integers, and .
Each of the next lines contains space-separated integers. These integers will be between and , as follows:
- 0 represents a neutral square
- 1 represents a good square
- 2 represents an evil square
- 3 represents a good square and the source for the knight
- 4 represents a good square and the destination for the knight
Output either one or two lines. If it is impossible to construct a path for the knight,
output one line containing exactly
Otherwise, output two lines. The first line should be a single integer, the minimum number of squares to convert. The second line should be a single integer, the number of ways to convert that many squares to yield a valid path.
4 5 1 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 4 0