题目描述

$\red{Farmer John }$建造了一个美丽的池塘，用于让他的牛们审美和锻炼。这个长方形的池子被分割成了 $\red{M }$行和 $\red{N }$列$\red{( 1 ≤}$ $\red{M ≤}$ $\red{30 }$; $\red{1 ≤}$ $\red{N ≤}$ $\red{30 ) }$正方形格子的 。

某些格子上有惊人的坚固的莲花，还有一些岩石，其余的只是美丽，纯净，湛蓝的水。 贝茜正在练习芭蕾舞，她从一个莲花跳跃到另一个莲花，当前位于一个莲花。

她希望在莲花上一个一个的跳，目标是另一个给定莲花。她能跳既不入水，也不到一个岩石上。 令门外汉惊讶的是，贝茜的每次的跳跃像中国象棋的马一样：横向移动$\red{1，}$纵向移动$\red{2，}$或纵向移动$\red{1，}$横向移动$\red{2}$。贝茜有时可能会有多达$\red{8}$个选择的跳跃。

$\red{Farmer John }$在观察贝茜的芭蕾舞联系，他意识到有时候贝茜有可能跳不到她想去的目的地，因为路上有些地方没有莲花。于是他想要添加几个莲花使贝茜能够完成任务。一贯节俭的$\red{Farmer John}$想添加最少数量的莲花。当然，莲花不能放在石头上。

请帮助$\red{Farmer John}$确定必须要添加的莲花的最少数量。在添加的莲花最少基础上，算出贝茜从起始点跳到目标点需要的最少的步数。最后，还要算出满足添加的莲花的 最少数量时，跳跃最少步数的跳跃路径的条数。

输入格式

第 $\red{1 }$行: 两个整数 $\red{M , N}$

第 $\red{2..M + 1 }$行:

第 $\red{i + 1 }$行，第 $\red{i + 1 }$行 有 $\red{N }$个整数，表示该位置的状态: $\red{0 }$为水; $\red{1 }$为莲花;

$\red{2 }$为岩石; $\red{3 }$为贝茜开始的位置; $\red{4 }$为贝茜要去的目标位置.

输出格式

第 $\red{1 }$行: 一个整数: 需要添加的最少的莲花数. 如果无论如何贝茜也无法跳到，输出 $\red{-1.}$

第 $\red{2 }$行: 一个整数: 在添加的莲花最少基础上，贝茜从起始点跳到目标点需要的最少的步数。如果第$\red{1}$行输出$\red{-1，}$这行不输出。

第 $\red{3 }$行: 一个整数: 添加的莲花的最少数量时，跳跃步数为第$\red{2}$行输出的值的跳跃路径的条数 如果第$\red{1}$行输出$\red{-1，}$这行不输出。

样例

输入样例

4 8
0 0 0 1 0 0 0 0
0 0 0 0 0 2 0 1
0 0 0 0 0 4 0 0
3 0 0 0 0 0 1 0

输出样例

2
6
2

提示

输出说明

至少要添加2朵莲花，放在了'x'的位置。

0 0 0 1 0 0 0 0     0 0 0 1 0 0 0 0
  0 x 0 0 0 2 0 1     0 0 0 0 0 2 0 1
  0 0 0 0 x 4 0 0     0 0 x 0 x 4 0 0
  3 0 0 0 0 0 1 0     3 0 0 0 0 0 1 0

贝茜至少要条6步，有以下两种方案

0 0 0 C 0 0 0 0     0 0 0 C 0 0 0 0
0 B 0 0 0 2 0 F     0 0 0 0 0 2 0 F
0 0 0 0 D G 0 0     0 0 B 0 D G 0 0
A 0 0 0 0 0 E 0     A 0 0 0 0 0 E 0