You are given an m * n matrix containing 0, 1 or 2 , where 0 represents an empty cell, 1 represents a fresh orange, 2 represents rotten orange. Every hour, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Print the minimum number of hours that must elapse until no cell has a fresh orange. In case if all the oranges can't become rotten print -1
Input Format
First line contains two integers m and n. Each of next m line contains n integers 0,1 or 2.
Output Format
Print minimum hours.
Constraints
1 <= m,n <= 1000
Example
Input
3 3 2 1 1 1 1 0 0 1 1
Output
4