Бригада из четырех роботов будет доставить детали в производственный цех. Цех организован в виде прямоугольной сетки, в которой каждый робот занимает одну квадратную ячейку. Каждый робот представлен целым числом от 1 до 4 и может двигаться в четырех ортогональных направлениях (влево, вправо, вверх, вниз). Однако, однажды приведенный в движение, робот остановится только тогда, когда он обнаружит соседнее препятствие (например, стены, края фабрики или других неподвижных роботов). Роботы не движутся одновременно, то есть в каждый момент времени движется только один робот.

Цель состоит в том, чтобы вычислить эффективную последовательность движений, чтобы робот 1 достиг заданной цели; для этого возможно потребуется убрать с пути других роботов или использовать их в качестве препятствий для "рикошетных" движений.

Рассмотрим приведенный выше пример, где серые ячейки представляют стены, X - это целевое местоположение, а 1 и 2 обозначают начальные позиции двух роботов. Одно оптимальное решение состоит из шести ходов, описанных ниже.

Обратите внимание, что последовательность движений должна оставлять робота 1 в заданном месте, а не просто проходить через него (цель не заставляет роботов останавливаться - только стены, края и другие роботы).

Имея описание производственного плана, начальную позицию робота и целевую позицию, вычислите минимальное общее количество ходов, необходимое чтобы робот 1 достиг цели.

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

Первая строка содержит количество роботов n (1 ≤ n ≤ 4), ширину w и высоту h (w, h ≥ 1, max(w, h) ≤ 10) производственного этажа в ячейках, и верхний предел l (1 ≤ l ≤ 10) на количество ходов для поиска решений. Остальные h строк текста представляют собой строки производственного цеха с w символами, каждый из которых представляет позицию ячейки:

• W ячейка занятая стеной;
• X (одна) целевая ячейка;
• 1, 2, 3, 4 начальные позиции роботов;
• ’.’ пустая ячейка.

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

Выведите минимальное количество ходов для робота 1, за которое можно достичь целевого местоположения, или NO SOLUTION если не существует решения с меньшим или равным заданному верхнему пределу количеством ходов.