You are given an binary matrix A of n rows and m columns. In a move, from one cell, you can go to any of 4 adjacent cells (i.e. share the same edge). You cannot move to cell with number 1.
Find the shortest distance from (1,1) to (n,m).
### Input
- The first line contains 2 integers n,m.
- The next n lines, each line contains a binary string of length m, matrix A.
### Output
- Print the distance from (1,1) to (n,m), or print -1 if no path exists.
### Constraints
- 1≤n,m≤103.
### Example
Input:
4501000010100001011010
Output:
11
