Места в новом трамвае в Загребе организованы в виде сетки, состоящей из \(N\) рядов, пронумерованных от \(1\) до \(N\), и двух столбцов, пронумерованных от \(1\) до \(2\). Расстояние между между сиденьями \((R_a, C_a)\) и \((R_b, C_b)\) равно евклидому расстоянию между центрами соответствующих клеток, а именно \(\sqrt{(R_a - R_b)^2 + (C_a - C_b)^2}\).

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

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

События пронумерованы от \(1\) до \(M\) в том порядке, в котором они произошли. Существует два вида событий: событие типа «Е» соответствует пассажиру, входящему в трамвай, а событие типа «L» соответствует пассажиру, покидающему трамвай. Для события типа «L» также дается целое число \(P\) - оно указывает, что уходящий пассажир - это тот, который зашел в трамвай во время события \(P\).

Гарантируется, что в трамвае всегда будет хотя бы одно свободное место, когда пассажир пытается войти.

Байтазар, король Байтотии организовал масштабную реформу имён своих подданных. Имена жителей Байтотии исторически часто содержат повторяющиеся фразы и Байтазар хочет с одной стороны упростить имена, а с другой, сохранить традиции повторения, а именно Байтазар хочет заменить каждое из имён в Байтотии на имя такой же длины, чтобы при этом множества периодов для старого и нового имён совпали, но имя при этом состояло только из символов «0» и «1». Из всех кандидатов в новое имя Байтазар хочет выбрать лексикографически минимальное.

Натуральное число \(k\) (\(1 \le k \lt n\)) называется периодом строки \(s\) длины \(n\) тогда и только тогда, когда для любого натурального \(i\), такого что \(1 \le i \le n - k\), верно что \(s_i = s_{i + k}\).

Множество периодов для данной строки \(s\) – множество таких чисел \(i\), что \(i\) является периодом \(s\). Обозначим его за Per(\(s\)). К примеру, Per(«ABIABUABIAB») = {6, 9}, Per(«0000») = {1, 2, 3}.

Помогите Байтазару перевести имена его подданных, и, возможно, он разрешит вам сохранить ваше собственное имя!