题目描述

在农夫约翰的厨房里吃了太多水果后，奶牛贝西做了一些非常奇怪的梦！在她最近的一个梦中，她被困在一个$\red{N×}$$\red{M}$的瓷砖网格形状的迷宫中$\red{（1≤}$$\red{N}$、 $\red{M≤}$$\red{1,000). }$她从左上角开始，想进入右下角。当她站在瓷砖上时，她可能会在四个基本方向中的任何一个方向移动到相邻的瓷砖。

但是等等。每个瓷砖都有一种颜色，每种颜色都有不同的属性！一想到这件事，贝西的头就疼：

如果瓷砖是红色的，则无法通行。

如果瓷砖是粉红色的，那么它可以正常行走。

如果瓷砖是橙色的，那么它可以正常行走，但会让贝西闻起来像桔子。

如果一块瓷砖是蓝色的，那么它包含食人鱼，只有当贝闻起来像桔子时，食人鱼才会让她通过。

如果一个瓷砖是紫色的，那么贝西将沿着该方向滑动到下一个瓷砖（除非她无法穿过它）。如果该瓷砖也是紫色瓷砖，则贝西将继续滑动，直到她落在非紫色瓷砖上或碰到无法通行的瓷砖。滑动瓷砖视为移动。紫色 瓷砖也可以去除贝茜的气味。 （如果您对紫色瓷砖感到困惑，本示例将说明它们的用法。）

请帮助贝西以旧能少的动作从左上角到右下角。

输入格式

第一行有两个整数$\red{N}$和$\red{M，}$表示迷宫的行数和列数。

接下来的$\red{N}$行各有$\red{M}$个整数，表示迷宫：

整数"$\red{0}$"是一个红色平铺

整数"$\red{1}$"是粉红色的平铺

整数"$\red{2}$"是橙色平铺

整数"$\red{3}$"是蓝色平铺

整数"$\red{4}$"是紫色平铺

左上角和右下角的整数始终为"$\red{1}$"。

输出格式

一个整数，表示 $\red{Bessie }$穿过迷宫必须使用的最小移动数，如果不可能，则为 $\red{-1}$。

样例

输入样例

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

输出样例

10

提示

在此示例中，$\red{Bessie }$向下走一格，向右走两格（然后再向右滑动一格）。她向上走一格，向左走一格，向下走一格（再向下滑动两格），最后向右走一格。这总共是 $\red{10 }$步 $\red{(DRRRULDDDR)}$ 。