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

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

Побудуйте дороги на найменій кількості прохідних клітинок так, щоб можна було пройти з будь-якої клітинки однієї держави до будь-якої клітинки другогї держави. По клітинкам будь-якої держави можна безперешкодно переміщатися. Переміщатися по карті можна тільки по горизонталі та вертикалі.

Вхідні дані

Перший рядок містить розмір карти n і m (1 ≤ n, m ≤ 1000). Наступні n рядків містить по m символів:

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

Вихідні дані

Виведіть найменшу кількість клітинок, в яких варто побудувати дороги так, щоб були з'єднані всі клітинки всіх держав. Якщо цього зробити не можна, то виведіть -1.