Электронная таблица представляет собой прямоугольную таблицу, левая и верхняя граница которой зафиксированы, а правая и нижняя отсутствуют, таким образом, таблица бесконечна вправо и вниз. В каждой ячейке таблицы может быть записано какое-либо значение. Значение ячейки – это произвольная последовательность символов с кодами от 32 до 126.

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

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

Если в значении ячейки встречается один из символов ",", ";", ".'"или "\", то в файл записывается два символа – сначала "\", а затем данный символ. Соответственно, запятая, точка с запятой и точка, которые идут непосредственно после "\", не являются разделителями значений ячеек. В частности, после них не может следовать перевода строки.

Каждая ячейка относится к одному из трех типов: числовая, строковая, пустая. Пустая ячейка – это ячейка, значение которой является пустой строкой. Числовая ячейка содержит целое число из диапазона от -32768 до 32767 включительно. Число должно быть записано без ведущих нулей и лишних знаков "+" или "-" (знак "-'" должен быть только у отрицательных чисел, причем ровно один). Любая другая ячейка относится к строковому типу. Так, например, к строковому типу относятся ячейки, содержащие следующие значения: 01 (включает ведущий нуль), 55000 (не входит в указанный диапазон), а также ячейка, содержащая один символ "пробел".

Столбец таблицы называется пустым, если все ячейки, которые он содержит – пустые. Столбец таблицы называется числовым, если он содержит только числовые и пустые ячейки. В противном случае столбец называется строковым. Требуется для каждого столбца таблицы, начиная с первого, и до последнего непустого, определить, к какому типу он относится.

Специальный терминал, разработанный в лаборатории, где работает Дима, представляет собой горизонтальный прямоугольник, состоящий из m×n ячеек, каждая из которых может содержать произвольное целое число. Ячейки занумерованы парами чисел, левая верхняя ячейка имеет номер (1, 1), правая нижняя – (\(m\), \(n\)).

Специальное устройство ввода, сконструированное специально для этого терминала, позволяет отправлять терминалу две команды: \(A\)(\(r\), \(c\), \(d\), \(v\)) и \(B\)(\(r_1\), \(c_1\), \(r_2\), \(c_2\), \(d\), \(v\)).

Рассмотрим сначала команду \(A\). Параметры \(r\) и \(c\) изменяются в пределах от 1 до \(m\) и от 1 до \(n\) соответственно и указывают, к какой ячейке применяется команда. Параметр \(d\) может принимать значение из множества {\(L\), \(R\), \(U\), \(D\)} и задает направление, в котором применяется команда: влево, вправо, вверх или вниз соответственно. Параметр \(v\) представляет собой целое неотрицательное число. В результате выполнения команды значения во всех ячейках, находящихся в направлении \(d\) от ячейки (\(r\), \(c\)), включая эту ячейку, увеличиваются на \(v\).

Например, если терминал имеет размер 5×4, то после выполнения команды \(A\)(3, 2, \(R\), 3) значения в ячейках (3, 2), (3, 3) и (3, 4) увеличатся на 3, а после команды \(A\)(2, 1, \(U\), 2) значения в ячейках (2, 1) и (1, 1) увеличатся на 2.

Рассмотрим теперь команду \(B\). Первые четыре ее параметра являются целыми числами и удовлетворяют условиям 1\( \le\) \(r_1\) \(\le\) \(r_2\) \(\le\) \(m\) и 1\( \le\) \(c_1\) \(\le\) \(c_2\) \(\le\) \(n\). Параметры \(d\) и \(v\) могут принимать те же значения, что и соответствующие параметры команды \(A\). Команда \(B\) выполняется следующим образом: для всех пар (\(r\), \(c\)), таких, что \(r_1\) \(\le\) \(r\) \(\le\) \(r_2\) и \(c_1\) \(\le\) \(c\) \(\le\) \(c_2\) выполняется команда \(A\)(\(r\), \(c\), \(d\), \(v\)).

Исходно все ячейки терминала содержат нули. Выведите содержимое терминала после выполнения заданной последовательности команд.

Между \(N\) населенными пунктами совершаются пассажирские рейсы на машинах времени.

В момент времени 0 вы находитесь в пункте \(A\). Вам дано расписание рейсов. Требуется оказаться в пункте B как можно раньше (то есть в наименьший возможный момент времени).

При этом разрешается делать пересадки с одного рейса на другой. Если вы прибываете в некоторый пункт в момент времени \(T\), то вы можете уехать из него любым рейсом, который отправляется из этого пункта в момент времени \(T\) или позднее (но не раньше).

Яша плавал в бассейне размером \(N\) x \(M\) метров и устал. В этот момент он обнаружил, что находится на расстоянии \(x\) метров от одного из длинных бортиков (не обязательно от ближайшего) и \(y\) метров от одного из коротких бортиков. Какое минимальное расстояние должен проплыть Яша, чтобы выбраться из бассейна на бортик?

Пастбище представляет собой прямоугольник, разбитый на \(N\) x \(N\) клеток. В каждой клетке растет трава, имеющая свою калорийность (во всех клетках калорийность травы разная). В левой нижней клетке стоит корова Мурка. Съев всю траву в своей клетке, она перемещается на одну клетку вправо или на одну клетку вверх, всегда выбирая ту из клеток, калорийность травы в которой больше (за пределами поля трава не растет). В конце концов корова приходит в правую верхнюю клетку. Требуется определить, сколько всего калорий получит корова (считая калории травы в первой и в последней клетках).