В комнате у Аркадия Семеновича Тапкина стоят электронные часы. Цифры на этих часах показываются в специальной псевдографике. А именно, каждое поле, на котором изображается цифра, состоит из w ячеек в ширину и h ячеек в высоту (при этом ячейки на поле имеют форму квадратов).

Но недавно у Аркадия Семеновича появилась проблема. Последнее время он стал плохо видеть. В связи с этим он хочет увеличить изображение этих цифр. Он уже приладил старый 19'' монитор к часам, и теперь дело осталось за малым. Осталось написать программу, которая будет рисовать цифры на дисплее. Аркадий Семенович хочет увеличить изображение в k раз и сделать толщину линий равной d. Помогите ему в этом.

Опишем более формально понятие «увеличить в k раз». Занумеруем ячейки поля w×h сверху вниз и слева направо. Таким образом, верхняя левая ячейка имеет координаты (0, 0), правая нижняя – (w - 1, h - 1), правая верхняя – (w - 1, 0), левая нижняя – (0, h - 1). Кроме этого, введем декартову прямоугольную систему координат так, что начало координат находится в центре верхней левой ячейки, ось Ox направлена вправо, ось Oy – вниз, длину единичного отрезка примем равной длине стороны ячейки. Таким образом, координаты центра ячейки совпадают с ее координатами во введенной нумерации.

Каждая десятичная цифра задается набором составляющих ее изображение отрезков. Для простоты каждый из отрезков либо параллелен одной из координатных осей, либо идет под углом в 45 градусов к ней.

Увеличенная в k раз цифра рисуется на поле размером (w - 1) ^. (k - 1) + w ячеек по горизонтали на (h - 1) ^. (k - 1) + h ячеек по вертикали.

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

После этого, для того, чтобы получить толщину линий равную d, дополнительно закрашиваются те ячейки, центры которых располагаются на расстоянии, не превышающем (d - 1) от центров основных ячеек. Расстоянием между точками A(x_A, y_A) и B(x_B, y_B) будем называть число (A, B) = | x_A - x_B| + | y_A - y_B|.

По описанию цифры и параметрам k и d выведите изображение цифры, увеличенное в k раз, с толщиной линий d.

Вася пишет новую версию своего офисного пакета "Closed Office". Недавно он начал работу над редактором "Dword", входящим в состав пакета.

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

Документ в формате редактора "Dword" представляет собой последовательность абзацев. Каждый абзац представляет собой последовательность элементов – слов и рисунков. Элементы одного абзаца разделены пробелами и/или переводом строки. Абзацы разделены пустой строкой. Строка, состоящая только из пробелов, считается пустой.

Слово --- это последовательность символов, состоящая из букв латинского алфавита, цифр, и знаков препинания: ".", ",", ":", ";", "!", "?", "-", "'".

Рисунок описывается следующим образом: "(image image parameters)". Каждый параметр рисунка имеет вид "имя=значение". Параметры рисунка разделены пробелами и/или переводом строки. У каждого рисунка обязательно есть следующие параметры:

Документ размещается на бесконечной вверх и вниз странице шириной \(w\) пикселей (разбиение на конечные по высоте страницы планируется в следующей версии редактора). Одна из точек на левой границе страницы условно считается точкой с ординатой равной нулю. Ордината увеличивается вниз.

Размещение документа происходит следующим образом. Абзацы размещаются по очереди. Первый абзац размещается так, что его верхняя граница имеет ординату 0.

 

Абзац размещается следующим образом. Элементы располагаются по строкам. Каждая строка исходно имеет высоту \(h\) пикселей. В процессе размещения рисунков высота строк может увеличиваться, и строки могут разбиваться рисунками на фрагменты.

Слова размещаются следующим образом. Считается, что каждый символ имеет ширину \(c\) пикселей. Перед каждым словом, кроме первого во фрагменте, ставится пробел шириной также в \(c\) пикселей. Если слово помещается в текущем фрагменте, то оно размещается на нем. Если слово не помещается в текущем фрагменте, то оно размещается в первом фрагменте текущей строки, расположенном правее текущего, в котором оно помещается. Если такого фрагмента нет, то начинается новая строка, и поиск подходящего фрагмента продолжается в ней. Слово всегда "прижимается" к верхней границе строки.

Размещение рисунка зависит от его расположения относительно текста.

Если расположение рисунка относительно текста установлено в "\(embedded\)", то он располагается так же, как слово, за тем исключением, что его ширина равна ширине, указанной в параметрах рисунка. Кроме того, если высота рисунка больше текущей высоты строки, то она увеличивается до высоты рисунка (при этом верхняя граница строки не перемещается, а смещается вниз нижняя граница). Если рисунок типа "\(embedded\)" не первый элемент во фрагменте, то перед ним ставится пробел шириной \(c\) пикселей. Рисунки типа "\(embedded\)" также прижимаются к верхней границе строки.

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

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

Если расположение рисунка относительно текста установлено в "\(floating\)", то рисунок размещается поверх текста и других рисунков и никак с ними не взаимодействует. В этом случае у рисунка есть два дополнительных параметра: "\(dx\)" и "\(dy\)" --- целые числа, задающие смещение в пикселях верхнего левого угла рисунка вправо и вниз, соответственно, относительно позиции, где находится верхний правый угол предыдущего слова или рисунка (или самой левой верхней точки первой строки абзаца, если рисунок --- первый элемент абзаца).

Если при размещении рисунка таким образом он выходит за левую границу страницы, то он смещается вправо, так, чтобы его левый край совпадал с левой границей страницы. Аналогично, если рисунок выходит за правую границу страницы, то он смещается влево, чтобы его правый край совпадал с правой границей страницы.

Верхняя граница следующего абзаца совпадает с более низкой точкой из нижней границы последней строки и самой нижней границы рисунков типа "\(surrounded\)" предыдущего абзаца.

По заданным \(w\), \(h\), \(c\) и документу найдите координаты верхних левых углов всех рисунков в документе.

Когда пользователь работает в операционной системе Windows, у него часто запущено несколько приложений. Каждое из приложений работает в отдельном окне. Для переключения между окнами используется комбинация клавиш «Alt+Tab». Эта комбинация делает активным окно, в котором пользователь работал перед тем, как перейти в текущее активное окно.

Чтобы переключиться в другое окно, можно нажать клавишу «Alt» и затем, не отпуская ее, несколько раз нажать клавишу «Tab». Чтобы понять, какое окно станет активным после этого, воспользуемся следующей моделью. Пусть запущено n приложений. Приложения в операционной системе организованы в виде списка и упорядочены по убыванию времени последней активности. То есть приложение, окно которого является активным в настоящий момент – первое в списке, приложение, окно которого было активно перед этим – второе, и т. д.

Если нажать клавишу «Alt» и затем, не отпуская ее, нажать клавишу «Tab» k раз, то активным станет окно приложения, которое находится на (k mod n) + 1-м месте в списке. Здесь a mod b означает остаток от деления a на b. Иными словами, операционная система рассматривает список как циклический, переходя после последнего элемента списка к первому.

При запуске нового приложения оно добавляется в начало списка.

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

Максимальное время работы на одном тесте: 2 секунды

При разработке программ для просмотра веб-страниц одной из наиболее сложных задач является корректное отображение таблиц. Компания «Kozilla», в которой вы работаете, планирует разработать новую версию браузера «Waterrat» для работы в терминальном режиме и просит вас написать фрагмент ядра отображения веб-страниц, ответственный за формирование структуры таблиц.

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

Таблица состоит из строк, каждая строка состоит из одной или нескольких ячеек, j-я ячейка i-й строки имеет ширину a_{i, j}.

По заданным параметрам таблицы постройте символическое изображение ее структуры.

Сережа очень любит старые игры. Недавно он нашел у себя на компьютере одну старую приключенческую игру. Управляя героем, надо перемещаться по карте и собирать различные предметы.

На определенном этапе игры Сережа столкнулся с неожиданной проблемой. Для продолжения приключений герою надо перебраться через пропасть. Для этого можно использовать последовательно расположенные лифты, которые имеют вид горизонтальных платформ. Каждый лифт вертикально перемещается туда-сюда между некоторыми уровнями. Герой может переходить между соседними платформами, однако это можно сделать только в тот момент, когда они находятся на одном уровне. Аналогично, с края пропасти на лифт и обратно можно перейти лишь в тот момент, когда лифт окажется на уровне края.

Каждый лифт имеет ширину, равную четырем метрам. В начале герой находится на расстоянии два метра от края пропасти. Он должен закончить свое путешествие в двух метрах от противоположного края пропасти. Герой перемещается со скоростью два метра в секунду. Таким образом, если герой находится в начальном положении или в центре лифта и хочет перейти на соседний лифт (или сойти с последнего лифта на противоположный край пропасти), он должен начать движение ровно за одну секунду до того момента, когда они окажутся на одном уровне. Через две секунды герой оказывается в центре соседнего лифта (или в конечном положении).

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