Box Delivery

Time limit1sMemory limit256 MB

Summary

A 1x1x3 box rolls 90 degrees across a grid, and we want the fewest rolls until it touches the destination cell; the box has two stable resting shapes.

Level: Medium7 of 10
Topics: BFS, Graph, Implementation, Simulation
Solved: No attempts yet

Problem

A courier has to move one box to a customer's house. He cannot lift the box, so he rolls it instead.

The box is $1 \times 1 \times 3$ , and at the start it stands upright with a $1 \times 1$ face on the ground.

The map is an $n \times m$ grid, and every cell is either ground or a sinkhole. One roll turns the box 90 degrees around an edge that touches the floor, and the box has to hold its new position.

When a $1 \times 1$ face is on the ground, that cell must be ground.
When a $1 \times 3$ face is on the ground, the three covered cells must have ground at both ends, or ground in the middle.

If neither condition holds, the box falls into a hole and cannot be moved any further. Every cell the box touches must stay inside the map.

Given the starting position and the destination, find the smallest number of rolls that brings the box to the destination. The box does not have to stand upright at the destination. It is enough that one of the cells the box touches is the destination.

Input

The first line has the height $n$ and the width $m$ of the map ( $1 \le n \le 500$ , $1 \le m \le 500$ ).

Each of the next $n$ lines has $m$ digits with no spaces between them. 0 is a sinkhole, 1 is ground, 2 is the starting cell of the box, and 3 is the destination. Exactly one 2 and exactly one 3 appear, and both of those cells are ground.

Output

Print the smallest number of rolls that brings the box to the destination. If the box cannot reach it, print -2.

Examples7

Example 1

Input

Expected output

Example 2
Input
```
1 4
2113
```
Expected output
```
1
```
Example 3
Input
```
1 2
23
```
Expected output
```
-2
```
Example 4
Input
```
5 1
2
0
1
0
3
```
Expected output
```
2
```
Example 5
Input
```
1 5
21013
```
Expected output
```
2
```
Example 6
Input
```
1 4
2130
```
Expected output
```
1
```
Example 7
Input
```
2 5
21110
01113
```
Expected output
```
3
```