В городе \(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, если же клетка оставлена белой, то на игровом поле она должна быть пустой.

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

Недавно Петя начал играть в шахматы.

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

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

Фигуры ходят следующим образом:

король - на любую соседнюю по вертикали, горизотнали или диагонали клетку;

ферзь - на любое расстояние по вертикали, горизонтали или диагонали;

ладья - на любое расстояние по вертикали или горизонтали;

слон - на любое расстояние по диагонали;

конь - в форме буквы "Г": на 1 клетку по горизонтали и на 2 по вертикали, или наоборот, на 1 клетку по вертикали и 2 по горизонтали.

Вам даны позиции одной белой и одной черной фигуры.

Определите, бьют ли фигуры друг друга, и, если бьют, выведите какая из них бьет какую.