В кассовом зале вокзала внедрили систему «электронная очередь». Теперь пассажир, который хочет купить билеты, при входе в зал получает талончик, после чего ожидает, когда подойдет очередь, и его пригласят к освободившейся кассе.

Система «электронная очередь» работает следующим образом. В зале имеются N касс, которые работают все время, за исключением времени перерывов (время перерывов в каждой кассе свое). Пассажиры приглашаются к кассам строго в порядке получения ими талончиков. Каждый пассажир проводит у кассы 5 минут (которые уходят на выбор поезда и оплату заказа), плюс оформление каждого билета дополнительно занимает еще одну минуту (таким образом, если пассажир, например, хочет оформить 3 билета, то он проведет у кассы 8 минут). Если пассажир был приглашен к кассе в момент времени A, а оформление его займет K минут, то и он, и эта касса освободятся к моменту времени A+K+1.

В освободившуюся кассу направляется очередной покупатель, если только в этой кассе не должно быть перерыва в ближайшие 5 минут. Но если касса начала оформление заказа какого-то пассажира, то она завершает оформление этого заказа, даже если в ней в процессе оформления должен начаться перерыв. При этом перерыв не сдвигается (то есть начинается на некоторое время позднее, но заканчивается ровно во столько, во сколько и должен). Считается, что если перерыв в кассе с момента A до момента B, то касса, освобождаясь в момент (A–5) начинает обслуживание очередного покупателя, а освобождаясь в моменты (A–4), (A–3), и так далее, — не начинает, а первого покупателя после перерыва касса начнет обслуживать в момент (B+1).

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

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

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

В городе \(n\) автобусных остановок, через которые проходят \(k\) кольцевых автобусных маршрутов. Каждый маршрут задается списком номеров остановок, через которые он проходит, \(i\)-ый маршрут проходит по остановкам \(a_{i, 1}\), \(a_{i, 2}\), …, \(a_{i, l_i}\) (в этом порядке). По маршруту ходит ровно один автобус. В момент времени 0 этот автобус находится на остановке \(a_{i,1}\). На то, чтобы доехать до следующей на своем маршруте остановки, автобус тратит ровно одну минуту. Временем стоянки автобуса на остановке можно пренебречь. Все маршруты кольцевые, то есть через минуту после остановки \(a_{i, l_i}\) автобус оказывается на остановке \(a_{i, 1}\) и едет по маршруту еще раз.

Несколько человек в этом городе решили покататься на автобусах. При этом каждый из них составил план своего катания. План \(j\)-го человека состоит из остановки \(b_j\), на которой человек начнет свое катание и последовательности чисел \(c_{j, 1}\), \(c_{j, 2}\), …, \(c_{j, m_j}\). Эти числа означают следующее: в момент времени 0 человек придет на остановку \(b_j\) и дождется ближайшего автобуса (если в этот момент какой-то автобус находится на остановке \(b_j\), человек сядет в него). На этом автобусе он проедет \(c_{j, 1}\) остановок, после чего выйдет и дождется следующего автобуса на той остановке, где он окажется. На нем он проедет \(c_{j, 2}\) остановок, снова выйдет и снова дождется следующего автобуса. И так далее. Если в какой-то момент к остановке подъедет сразу несколько автобусов, то человек сядет в автобус с минимальным номером маршрута. Когда человек выходит из автобуса на какой-то остановке, он может уехать с этой остановки не раньше, чем через минуту.

Для каждого человека определите, через сколько минут после начального момента и на какой остановке закончится его катание.

Мальчику Васе очень нравится известная игра «Сапер». В нее играет один человек. Игра идет на клетчатом поле размером \(m\)×\(n\) (\(m\) строк, \(n\) столбцов). В некоторых клетках поля стоят мины. В каждой из остальных клеток записано либо число от 1 до 8 – количество мин в соседних с ней клетках, либо ничего не написано – это означает, что в соседних клетках мин нет. Клетки являются соседними, если они имеют хотя бы одну общую вершину. В одной клетке не может стоять более одной мины. Будем называть поле с расположенными на нем минами и числами картой.

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

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

У Васи есть рисунки, нарисованные на клетчатой бумаге следующим образом: некоторые клетки закрашены в черный цвет, а некоторые оставлены белыми. Вася хочет по каждому такому рисунку сделать соответствующее ему поле для игры в «Сапера» по следующему правилу: если на рисунке клетка покрашена в черный цвет, то на этом месте должна быть либо мина, либо число от 1 до 8, если же клетка оставлена белой, то на игровом поле она должна быть пустой.

Напишите программу, которая сделает это за Васю.

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

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

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