Профессор опять потерял своего домашнего робота. После некоторых раздумий профессор понял, что робота он оставил в подвале.
Подвал в доме профессора представляет собой прямоугольник n × m, разбитый на квадратные клетки 1 × 1. Некоторые клетки — стены, которые непроходимы, остальные клетки проходимы. Из любой проходимой клетки можно попасть в любую другую проходимую клетку, двигаясь через смежные по ребрам проходимые клетки. Одна из проходимых клеток является выходом из подвала. Робот находится ровно в одной из проходимых клеток, в том числе, он может находиться в клетке выхода.
Профессору страшно идти ночью в темный подвал искать робота. Но у него есть план подвала, а также пульт дистанционного управления роботом. Профессор с помощью пульта может посылать сигналы роботу, чтобы он сдвигался на одну клетку влево, вправо, вверх или вниз. Получив сигнал, робот сдвигается в нужном направлении, если соседняя с ним клетка в данном направлении проходима. Иначе робот стоит на месте.
Профессор выписал на листочек последовательность из k команд, которая, по его мнению, приведет робота к выходу из подвала, где бы он ни находился изначально. Он запрограммировал другого робота, чтобы тот нажимал на пульте нужные кнопки в соответствии с записью на листочке. Профессор уже было хотел запустить программу на выполнение и пойти спать, но тут его осенило.
На выполнение каждой команды тратится электроэнергия, а профессор не хочет получить в конце месяца большой счет за электричество. Поэтому он хочет найти наименьший префикс в выписанной им последовательности, который гарантированно приведет робота к выходу после его выполнения. Именно с этой просьбой профессор тревожит вас в столь поздний час.
Выходные данные
В выходной файл выведите длину наименьшего префикса, который гарантированно приводит робота к клетке выхода. Другими словами, робот должен оказаться в клетке выхода после выполнения всех команд из префикса (в процессе выполнения команд робот мог приходить в клетку выхода, а затем уходить из нее, но нас интересует положение робота только в самом конце), где бы он ни находился в подвале изначально. Если профессор ошибся и никакой префикс (включая всю последовательность) не приводит робота к выходу, выведите «-1» (без кавычек). Если единственная проходимая клетка поля — выход, то выведите «0» (без кавычек).