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

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

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

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

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

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

Издательская система LATEX предназначена для верстки сложных научно-технических текстов с большим количеством формул. Исходный файл для системы LATEX пишется на языке TEX и представляет собой текст документа, в который включены специальные символы и команды. Специальные символы и команды описывают размещение текста, в частности в математических формулах. Команда представляет собой последовательность латинских букв (регистр важен), перед которой стоит символ &lquot;\&rquot;. Так, команда \frac предназначена для описания дроби, в которой числитель расположен над знаменателем. Рассмотрим простейшую структуру команды \frac.

Команда \frac имеет два параметра — числитель и знаменатель. Перед самой командой не обязательно ставить пробел. Следом за ключевым словом frac записываются числитель и знаменатель. Если числитель и знаменатель имеют длину более одного символа, они заключаются в фигурные скобки. Если числитель или знаменатель записываются одной буквой или цифрой, их можно не брать в фигурные скобки. Если числитель записывается одним символом, то он отделяется от \frac хотя бы одним пробелом. Если знаменатель записывается одним символом, то он не отделяется пробелом от числителя. Произвольное ненулевое количество пробелов считается синтаксически эквивалентным одному пробелу. Нельзя разделять пробелами на части ключевое слово \frac.

Дадим также формальное определение выражения для нашей задачи:

<выражение> ::= <элемент> | <элемент><выражение>
<элемент> ::= <дробь> | "{" <выражение> "}" | <другой математический элемент>
<дробь> ::= "\frac" <тело дроби>
<тело дроби> ::= <числитель><знаменатель>
<числитель> ::= <пробелы><непробельный символ> | [<пробелы>] "{" <выражение> "}"
<знаменатель> ::= <непробельный символ> | [<пробелы>] "{" <выражение> "}"
<другой математический элемент> ::= произвольная последовательность печатных символов, не содержащая фигурных скобок и подстроки "\frac"
<пробелы> ::= " " | " " <пробелы>
<непробельный символ> ::= произвольный печатный символ, за исключением " ", "", "{" и "}"

Здесь вертикальная черта | означает "или", заключенная в квадратные скобки часть может отсутствовать, а символы, записанные в кавычках обозначают самих себя. Печатный символ - любой символ с ASCII кодом от 32 (пробел) до 127. Например, выражение

записывается на языке TEX как

\frac{a+b}{d+1}+\frac ax -\frac 2 {2+\frac{3}{y}}

Чтобы в печатаемом документе вывести формулу, необходимо вычислить ее высоту для используемого при печати шрифта. Шрифт определяет размеры \(S\) - высоту отдельного символа и \(D\) - высоту горизонтальной дробной черты. Значения \(S\) и \(D\) задаются целыми числами. Ваша задача - для заданного выражения на языке TEX вычислить высоту формулы.

Отметим, что если две дроби принадлежат одному выражению, то их дробные черты записываются на одном уровне, а если нет (например, относятся к числителям или знаменателям различных дробей), это свойство может и не выполняться. Чтобы проиллюстрировать применение этого правила, приведем два примера:

\frac{a+b}{\frac cd}+\frac{\frac ef}{g+h}

\frac{a+b+c}{\frac{\frac de}{g+h}}+\frac{i+j+k}{\frac{l+m}{\frac no}}

Компания MacroHard разработала новый язык программирования PASCAL++. В этом языке имеется оператор вывода PrintLn, с помощью которого можно выводить строки любой длины. По стандарту языка, разработанному специалистами компании, некоторые комбинации символов в строке должны при выводе играть особую роль:

Комбинация	Значение
\n	Переход на новую строку
\t	Вывод K пробелов (\(1\leq K \leq 7\))), после чего курсор оказывается на позиции, имеющей номер вида \(7N+1\) (первая позиция каждой строки имеет номер 1).
\\	Вывод символа "\".
\XY где X и Y – шестнадцатеричные цифры (0..9, A..F или a..f), причем XY20	Вывод символа, имеющего ASCII код XY

Например, строка "New line\ntab\tslash\\\nA char \41, rus Б \81" должна была быть напечатана в следующем виде :

Напечатано	Здесь пробелы для наглядности обозначены символами 
New line tab slash\ A char A, rus Б Б	Newline tabslash\ AcharA,rusББ

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

Ученику второго класса рассказали правила, как нужно выполнять арифметические действия, чтобы вычислить значение арифметического выражения, состоящего из чисел, скобок и знаков арифметических операций + (сложение) и * (умножение). После этого ему дали упражнения — несколько задач, в которых требуется расставить порядок выполнения действий. Помогите ему.

Правила вычисления выражения, рассказанные ученику, звучат так. Если в выражении вообще нет скобок, то сначала выполняются все операции умножения слева направо, а затем — операции сложения также слева направо. Если же в выражении есть скобки, то находится самая левая пара скобок (открывающая и закрывающая), содержащая внутри себя бесскобочное выражение, которое может быть вычислено по вышеописанным правилам. Дальше это выражение (вместе со скобками) мысленно удаляется из выражения и заменяется числом – результатом. Если в выражении остались скобки, то процедура повторяется.

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