Представляем вам новый язык программирования URCAPL — Universal Reusable Cool and Amazing Programming Language.

Внимание: если вы что-нибудь знаете о языке программирования Befunge и описанный ниже синтаксис покажется вам знакомым, тем не менее внимательно прочтите описание языка URCAPL. Он был специально придуман для данного соревнования и имеет мало общего с Befunge.

Язык URCAPL работает только с целыми числами, не превосходящими 10⁵ по модулю. Для хранения чисел используются 27 регистров: один текущий и 26 регистров памяти, которые кодируются заглавными латинскими буквами от A до Z. Изначально во всех регистрах записано число ноль.

Программа представляет собой двумерное поле размером H × W, в каждой клетке которого записан некоторый оператор. Исполнение программы происходит с помощью «каретки», которая стоит в некоторой клетке поля и имеет одно из четырёх возможных направлений движения: вверх, вправо, вниз, влево. В момент начала исполнения программы каретка находится в верхнем левом углу поля, направление её движения — вправо. В процессе исполнения программы направление движения каретки может меняться в зависимости от оператора в клетке, в которой она находится. Работа программы разбита на такты. На каждом такте сначала выполняется оператор в клетке каретки, затем каретка сдвигается на одну клетку в текущем направлении.

Список операторов:

• "^", ">", "v", "<" — поменять направление движения каретки соответственно вверх, вправо, вниз, влево;
• "." — ничего не делать;
• "A"…"Z" — поменять местами числа в текущем регистре и регистре, обозначенном буквой;
• "?" — считать число из входного потока и записать его в текущий регистр (при этом старое число удаляется из текущего регистра);
• "!" — вывести в выходной поток число, записанное в текущем регистре (при этом в текущий регистр записывается число 0);
• "+" — увеличить число в текущем регистре на единицу;
• "-" — уменьшить число в текущем регистре на единицу;
• "@" — (условный оператор) если число в текущем регистре равно 0, изменить направление движения против часовой стрелки, иначе — по часовой стрелке;
• "#" — немедленно завершить выполнение программы.

Если в процессе исполнения значение в текущем регистре превысит 10⁵ по модулю, программа завершится с ошибкой OVERFLOW ERROR. Если каретка выйдет за границы поля, программа завершится с ошибкой RUNTIME ERROR. Если в течение 10⁶ тактов не будет выполнен оператор завершения программы и не произойдёт ни одна из двух описанных выше ошибок, то программа завершится с ошибкой TIME LIMIT EXCEEDED.

Ваша задача — написать интерпретатор языка, то есть по заданной программе на языке URCAPL и входным данным сказать, что выдаст программа во время её исполнения.

В первой строке записаны целые числа H и W (1 ≤ H, W ≤ 100) — размеры поля. Далее дана таблица из H строк и W столбцов, представляющая собой синтаксически верную (то есть содержащую только описанные выше операторы) программу на языке URCAPL.

В следующей строке записано целое число n (1 ≤ n ≤ 10⁵) — количество чисел во входных данных для программы. В следующих n строках по одному в строке записаны числа, по модулю не превосходящие 10⁵, — входные данные для программы. Если программа в ходе работы уже считала n чисел из входных данных, все последующие запросы на чтение будут возвращать последнее число из этого списка. Если программа в процессе выполнения считывает не все числа, это не является ошибкой.

На каждую команду вывода в программе на URCAPL необходимо вывести число в отдельной строке. Если в какой-то момент времени произойдёт ошибка OVERFLOW ERROR, RUNTIME ERROR или TIME LIMIT EXCEEDED, необходимо вывести соответствующее сообщение в отдельной строке.

Обратите внимание, что программа на URCAPL сразу же завершается после первой ошибки. Например, если во время одного такта произошли одновременно ошибки OVERFLOW ERROR и RUNTIME ERROR, должно быть выведено только сообщение «OVERFLOW ERROR» (без кавычек), так как сначала выполняется оператор в клетке, где находится каретка, и лишь потом происходит движение каретки.