Рабочее место участника

Фирма хранит упорядоченную таблицу серийных номеров в виде списка диапазонов серийных номеров, в которой записаны также две соответствующих части информации – так называемый статусный код и трансферный код. Этот список диапазонов, в свою очередь, представляет собой таблицу из 4-х колонок: начальный серийный номер, конечный серийный номер, статусный код и трансферный код. Серийные номера, как и трансферные коды, представляют собой числа от 1 до `2^31\ -\ 1` включительно, а статусный код всегда является одной заглавной латинской буквой. Таблица диапазонов хранится строго в порядке возрастания серийных номеров, диапазоны номеров никогда не перекрываются, и, для каждого серийного номера, таблица должна всегда предоставлять самую последнюю информацию (статусный код и трансферный код) для этого серийного номера.

Рассмотрим пример. Пусть были созданы 100 000 серийных номеров со статусом "A" и трансферным кодом 1. Запись в таблице диапазонов в таком случае будет выглядеть так:

Понятно, что такая запись гораздо более эффективна, чем хранение 100 000 отдельных строк в таблице. Единственная проблема – произведение изменений в таблице более сложно, чем если бы мы хранили отдельные строки. К примеру, если серийный номер 12345 должен поменять статус на "B", то вместо одной записи у нас будет уже три:

Теперь, изменим трансферный код для всех серийных номеров в диапазоне от 12000 до 12999 на 2. Получим такую таблицу:

Теперь, сменим для всех серийные номеров от 10000 до 100000 статус на "C" и трансферный код на 2:

Однажды созданный серийный номер никогда не должен удаляться, но допустимо иметь диапазоны неопределенных серийных номеров, между диапазонами определенных. К примеру, давайте изменим все серийные номера с 1000000 до 1999999 на статус "Z" и трансферный код 99:

И наконец, таблица всегда должна содержать минимальное количество строк. Например, рассмотрим следующую таблицу:

Первые две строки можно объединить, поэтому эта таблица может быть заменена на следующую:

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

И наконец, следующая таблица также не может быть сокращена, потому что между первой и второй строкой есть неопределенный элемент:

Ваша задача – по заданному списку запросов вывести результирующую минимальную таблицу серийных номеров. Запросы применяются к таблице последовательно. Изначально все серийные номера в таблице не определены.

В первой строке входного файла содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 100\ 000`) – количество запросов на изменение таблицы серийных номеров. В следующих `N` строках содержатся запросы на изменение, по одному на строку, в формате, описанном выше.

Необходимо вывести несколько строк – результирующую минимальную таблицу серийных номеров в формате, описанном выше.

2
1 100000 A 1
12345 12345 B 1

1 12344 A 1
12345 12345 B 1
12346 100000 A 1

4
1 100000 A 1
12345 12345 B 1
12000 12999 A 2
12345 12345 B 2

1 11999 A 1
12000 12344 A 2
12345 12345 B 2
12346 12999 A 2
13000 100000 A 1

5
1 100000 A 1
12345 12345 B 1
12000 12999 A 2
12345 12345 B 2
10000 100000 C 2

1 9999 A 1
10000 100000 C 2

6
1 100000 A 1
12345 12345 B 1
12000 12999 A 2
12345 12345 B 2
10000 100000 C 2
1000000 1999999 Z 99

1 9999 A 1
10000 100000 C 2
1000000 1999999 Z 99