Гном в замке

В прямоугольной матрице размером N×M клеток закодирован план староинного замка. Каждая клетка плана описана одним целым числом A (0≤A≤ 31), образованным суммой чисел по такому правилу:

• 1 – если есть стена на западе;
• 2 – если есть стена на севере;
• 4 – если есть стена на востокеі;
• 8 – если есть стена на юге;
• 16 - если в клетке есть мешок золота.

Считается, что внутренняя стена принадлежит двум клеткам. Например, южная стена клетки (1, 2) есть также северной стеной клктки (2, 2) (см. рисуннок и пример входного файла).

Внешняя клетка, не имеющая соответствующей внешней стены называется клеткой-выход. На рисунке изображено две такие клетки (2, 1) и (1, 5). Всего таких клеток не более 10.

В клетке с известными координатами (i, j) находится гном. Он может двигаться по соседних клетках, сделав шаг через общую сторону, если ему не мешают стены замка. За какое минимальное количество шагов K гном сможет попасть в любую клетку–выход, прихватив ровно один мешок золота (больше он не донесёт)?

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

В первой строке четыре числа: N, M – размер матрицы (1 ≤ N,M≤ 50) и i, j – координаты гнома (1 ≤i ≤N, 1 ≤j ≤M). Последующие N строк по M чисел в кождой описывают план замка за указанными выше правилам.

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

Одно число – минимальное количество шаговK к выходу или -1, если гном не сможет выполнить задание.