Три государства расположены на прямоугольной карте размером n * m. Из любой клетки любого государства можно добраться до любой клетки этого же государства, перемещаясь только по его клеткам по горизонтали или вертикали. Клетки каждого государства обозначены одной из цифр (1, 2 или 3).

На карте присутствуют проходимые (".") и непроходимые ("#") клетки.

Постройте дороги на наименьшем количестве проходимых клеток так, чтобы можно было пройти из любой клетки одного государства до любой клетки другого государства. По клеткам любого государства можно беспрепятственно передвигаться. Передвигаться по карте можно только по горизонтали или вертикали.

Входные данные

Первая строка содержит размер карты n и m (1 ≤ n, m ≤ 1000). Следующие n строк содержат по m символов:

• 1, 2, 3 - клетки принадлежащие государствам;
• "." - проходимая клетка, на ней можно строить дорогу;
• "#" - непроходимая клетка, на ней нельзя строить дорогу;

Выходные данные

Выведите наименьшее количество клеток, в которых следует построить дороги так, чтобы были соединены все клетки всех государств. Если этого сделать невозможно, то выведите -1.