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

Подвал в доме профессора представляет собой прямоугольник n × m, разбитый на квадратные клетки 1 × 1. Некоторые клетки — стены, которые непроходимы, остальные клетки проходимы. Из любой проходимой клетки можно попасть в любую другую проходимую клетку, двигаясь через смежные по ребрам проходимые клетки. Одна из проходимых клеток является выходом из подвала. Робот находится ровно в одной из проходимых клеток, в том числе, он может находиться в клетке выхода.

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

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

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