某城市正在进行应急通道规划。城市中心被划分为一个由若干方格组成的矩形区域，共有 N \times M 个方格（1 \le N, M \le 1000）。每个方格根据道路与设施状况，具有不同的通行规则。

一支应急巡查小组需要从左上角方格 (1,1) 出发，前往右下角方格 (N,M)。巡查人员每次可以向上、下、左、右四个方向移动到相邻方格之一，且只能在 N \times M 的矩阵内进行移动。

然而，不同类型的方格具有不同的通行特性：

• 类型 0（封闭区）：无法进入。
• 类型 1（普通道路）：可以正常通行。
• 类型 2（补给点）：可以通行，并为该小组颁发电子“通行许可”（如果小组已经获得“通行许可”，则进入该区域不会重复颁发）。
• 类型 3（管控区）：只有在小组获得电子“通行许可”时才能进入，进入管控区不会取消小组获得的电子“通行许可”。

• 类型 4（快速通道）：

  • 进入该方格后，将沿当前移动方向自动前进。
  • 若下一个方格仍为快速通道，则继续前进。
  • 直到遇到非快速通道方格，或无法继续通行为止。自动前进在无法继续时，停留在最后一个成功进入的方格。
  • 每前进一个方格，计为一次移动。
  • 一旦进入任意一个快速通道方格，若此前持有电子通行许可，则在自动前进开始之前，该许可立即失效。

请你计算巡查小组从起点到终点所需的最少移动次数。 如果无法到达终点，输出 -1。

第一行包含两个整数 N, M，表示方格的行数和列数。

接下来 N 行，每行包含 M 个整数，表示方格类型：

• 0：表示封闭区。
• 1：表示普通道路。
• 2：表示补给点。
• 3：表示管控区。
• 4：表示快速通道。

数据保证起点 (1,1) 和终点 (N,M) 均为 1。

输出一个整数，表示从起点到终点的最少移动次数；若无法到达，请输出 -1。

样例 1 说明

巡查小组的一种最优移动方案如下：

• 向下移动 1 次，到达 (2, 1)。
• 向右移动 1 次，到达 (2, 2)；再向右移动一次，到达 (2, 3)，该位置为快速通道，因此自动前进 1 次，到达 (2, 4)。
• 向上移动 1 次，到达 (1, 4)，向左移动 1 次，到达 (1, 3)，在该位置获得电子通行许可。
• 向下移动 1 次，到达 (2, 3)，再次进入快速通道，电子通行许可失效，并自动前进 2 次，到达 (4, 3)。
• 向右移动 1 次，最终抵达右下角方格 (4, 4)。

整个过程中共计 10 次移动，不存在更短方案。

数据范围

对于 30\% 的数据，满足 2 \le N, M \le 50。

对于 10\% 的数据，满足读入的方格类型只有 0 和 1 两种。

对于 10\% 的数据，满足读入的方格类型没有 2 或者 没有 4。

对于 30\% 的数据，满足读入的方格类型没有 3。

对于 100\% 的数据，满足 1 \le N, M \le 1000，每个方格类型为 0 \sim 4 的整数，起点与终点保证可通行，即：为数字 1。

月赛26年2月广搜