在农夫约翰的厨房里吃了太多水果后，母牛贝西做了一些非常奇怪的梦！在她最近的梦中，她被困在一个由 N×M 格子（1≤N，M≤1,000）组成的迷宫中。她从左上角的图块开始，想要到达右下角的图块。当她站在棋子上时，她可能会在四个基本方向中的任何一个上移动到相邻的棋子。

可是等等！每个瓷砖都有一种颜色，每种颜色都有不同的属性！贝西想想就头疼：

• 如果一个瓷砖是 红色的，那么它是无法通行的。
• 如果瓷砖是 粉红色的，那么它可以正常行走。
• 如果瓷砖是 橙色的，那么它可以正常行走，但会使 Bessie 闻起来像橘子。
• 如果一块瓷砖是 蓝色的，那么它包含食人鱼，只有当贝西闻起来像橘子时才会让她通过。
• 如果一个瓷砖是 紫色的，那么 Bessie 会沿着那个方向滑到下一个瓷砖（除非她无法穿过它）。如果这块瓷砖也是紫色瓷砖，那么 Bessie 将继续滑动，直到她落在非紫色瓷砖上或撞到无法通过的瓷砖上。滑过瓷砖算作移动。紫色瓷砖也会去除贝西的气味。

（如果您对紫色瓷砖感到困惑，该示例将说明它们的用途。）

请帮助 Bessie 尽可能少地从左上角到右下角。

输入格式（文件dream.in）：

第一行有两个整数 N 和 M，表示迷宫的行数和列数。接下来的 N 行每行有 M 个整数，表示迷宫：

• 整数 '0' 是红色方块
• 整数 '1' 是粉红色的瓷砖
• 整数“2”是橙色瓷砖
• 整数 '3' 是蓝色方块
• 整数 '4' 是紫色方块

左上角和右下角的整数将始终为“1”。

输出格式（文件dream.out）：

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

SAMPLE INPUT:

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

SAMPLE OUTPUT:

10

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