Определите две последние цифры шестнадцатеричной записи числа $0,AB_{16}^N$ при $N=20000000005_{10}$.

В ответе запишите подряд две шестнадцатеричные цифры в порядке их следования в числе.

Пример записи ответа:
1A

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно аналитически или использовали электронные таблицы и/или программирование на каком-то этапе решения задачи?

2. В аналитической части решения опишите, какие зависимости, закономерности и как Вы определили из условия, какие данные и формулы использовали для вычислений, и как это позволило получить ответ.

3. Если в какой-то части решения Вы использовали электронные таблицы, охарактеризуйте операции, которые Вы в них осуществили, назначение введенных в ячейки формул, и как это позволило получить ответ.

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

Рекомендуемое время пояснения решения 2-4 минуты.

На занятиях кружка по информатике Михаила Валерьевича, Петя и Вася получили задание написать генератор квадратных растровых изображений размером $N$ x $N$ пикселей, где $N$ всегда кратно четырем. Каждый пиксель может быть или черным, или белым. Петя решил сохранять в память изображение как последовательность кодов цветов пикселей, используя для записи кода цвета каждого пикселя минимально возможное, одинаковое для всех кодов цветов пикселей, количество бит. Вася заметил особенность генератора Пети – любое получившееся изображение можно разбить на непересекающиеся квадраты размером $4$ x $4$ пикселя, и в каждом таком квадрате всегда получается одинаковое количество белых и черных пикселей. Тогда Вася предложил присвоить уникальный числовой код каждому удовлетворяющему этому условию квадрату $4$ x $4$ и сохранять в память изображение как последовательность таких кодов, используя для записи кода каждого квадрата минимально возможное, одинаковое для всех кодов квадратов количество бит.

Вася обнаружил, что при его способе записи изображение занимает в памяти на $441$ байт меньше, чем при способе записи Пети. Определите $N$, при котором это возможно. В ответе укажите целое число.

Пример записи ответа:
171717

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно аналитически или использовали электронные таблицы и/или программирование на каком-то этапе решения задачи?

2. В аналитической части решения опишите, какие зависимости, закономерности и как Вы определили из условия, какие данные и формулы использовали для вычислений, и как это позволило получить ответ.

3. Если в какой-то части решения Вы использовали электронные таблицы, охарактеризуйте операции, которые Вы в них осуществили, назначение введенных в ячейки формул, и как это позволило получить ответ.

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

Рекомендуемое время пояснения решения 1-3 минуты.

Дана диаграмма Венна для четырех множеств: $a, b, c$ и $d$.

Определим логические выражения $A, B, C, D$ как утверждения, что точка принадлежит множеству $a, b, c$ или $d$, соответственно.

Найдите логическую функцию от четырех аргументов $F(A, B, C, D)$ такую, что она эквивалентна утверждению «Если точка принадлежит красной области, то она принадлежит синей области». В ответе укажите логическую формулу в максимально упрощенном виде, которая может содержать логические переменные $A, B, C, D$ и логические операции из набора {инверсия, конъюнкция, дизъюнкция}. Если таких функций нет, запишите в ответ $NULL$.

Комментарий по вводу ответа: операнды вводятся большими латинскими буквами; логические операции обозначаются, соответственно, как $not$, $and$ и $or$. Запись не должна содержать скобок.

Пример записи ответа:
A or not B

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно аналитически или использовали электронные таблицы и/или программирование на каком-то этапе решения задачи?

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

3. Если в какой-то части решения Вы использовали электронные таблицы, охарактеризуйте операции, которые Вы в них осуществили, назначение введенных в ячейки формул, и как это позволило получить ответ.

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

Рекомендуемое время пояснения решения 2-4 минуты.

Последовательности символов строятся по следующим правилам:

Исходная последовательность состоит из двух букв: “$AA$”. Далее на каждом шаге берется очередная буква английского алфавита, и пара таких букв добавляется в начало последовательности и после каждой буквы последовательности, полученной на предыдущем шаге. Например, последовательности, получаемые после первых $3$ шагов, будут выглядеть таким образом (третья последовательность разбита на две строки для лучшего восприятия):

1. $BBABBABB$
2. $CCBCCBCCACCBCCBCCACCBCCBCC$
3. $DDCDDCDDBDDCDDCDDBDDCDDCDDADDCDDCDDBDDCDDC$
   $DDBDDCDDCDDADDCDDCDDBDDCDDCDDBDDCDDCDD$

Построение завершается, когда в результате очередного шага в последовательности впервые появляются буквы $Z$. Эта последовательность является результирующей.

Определите, какие буквы стоят в результирующей последовательности на позициях $116$ $031$ $285$ и $2$ $269$ $896$ $645$ $051$, считая от начала строки с $1$. В ответе укажите их подряд в указанном порядке.

Примечание. Порядок следования символов в английском алфавите: $ABCDEFGHIJKLMNOPQRSTUVWXYZ$.

Пример записи ответа:
AB

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно программированием или использовали электронные таблицы и/или аналитические методы на каком-то этапе решения задачи?

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

3. Если в какой-то части решения Вы использовали аналитические методы решения, опишите, какие зависимости, закономерности и как Вы определили из условия или результатов работы программы, какие данные и формулы использовали для вычислений, и как это позволило получить ответ.

4. Если в какой-то части решения Вы использовали электронные таблицы, охарактеризуйте операции, которые Вы в них осуществили, назначение введенных в ячейки формул, и как это позволило получить ответ.

Рекомендуемое время пояснения решения 1-3 минуты.

Дана блок-схема алгоритма.

На вход алгоритму подается целое положительное число $N$ и массив из трех элементов $[3, 2, 1]$.

Известно, что исполнение алгоритма успешно завершилось и было выведено число $1$. Определите значение $N$, которое подали на вход алгоритма.

В ответе укажите целое число. Если такого числа не существует, запишите в ответ $NULL$. Если таких чисел несколько, запишите минимальное из них.

Примечания:

1. Индексация элементов массива начинается с $0$.
2. Функция $sum(mas)$ вычисляет сумму элементов массива.
3. Операция сравнения $!=$ обозначает «не равно».
4. Операция $A//B$ означает вычисление частного при целочисленном делении $A$ на $B$, а операция $A \%B$ означает вычисление остатка при целочисленном делении $A$ на $B$.

Пример записи ответа:
171717

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно программированием или использовали электронные таблицы и/или аналитические методы на каком-то этапе решения задачи?

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

3. Если в какой-то части решения Вы использовали аналитические методы решения, опишите, какие зависимости, закономерности и как Вы определили из условия или результатов работы программы, какие данные и формулы использовали для вычислений, и как это позволило получить ответ.

4. Если в какой-то части решения Вы использовали электронные таблицы, охарактеризуйте операции, которые Вы в них осуществили, назначение введенных в ячейки формул, и как это позволило получить ответ.

Рекомендуемое время пояснения решения 1-3 минуты.

Маршрутизаторы (аппаратные или программные) выполняют задачу выбора оптимального маршрута следования IP пакета и его отправки по этому маршруту. Для принятия решения анализируется адрес получателя и устанавливается маршрут следования на основе таблиц маршрутизации.

В таблице маршрутизации присутствуют как минимум следующие поля:

1. адрес назначения (адрес IP-сети или IP адрес хоста) и маска назначения (она может задаваться или в десятичном формате, или в виде количества бит $=1$, то есть бит под адрес сети),
2. идентификатор порта, через который пакет идет до сети назначения (порт обозначается IP-адресом или внутренним номером),
3. шлюз (IP адрес, принадлежащий к одной из локальных сетей, непосредственно подключенных к маршрутизатору, на который необходимо отправить пакет, после того как пакет покинет порт, чаще всего – это адрес принадлежит следующему по маршруту маршрутизатору),
4. метрика (показатель качества маршрута).

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

Маршрутные записи на сеть в качестве адреса (поля $1$) содержат IP адрес сети и маску сети.

Маршрутные записи на хост (например, на один компьютер с известным IP адресом) в качестве адреса в первом и втором поле содержат IP адрес целевого хоста и маску, равную $255.255.255.255$ ( $/32$).

Запись по умолчанию отличается тем, что в первом поле адрес назначения и маска назначения имеют значения $= 0.0.0.0$ ($0.0.0.0/0$).

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

Когда маршрутизатору необходимо определить маршрут для продвижения IP пакета, то сначала по заголовку IP пакета определяется адрес назначения, а потом ищется подходящая запись в таблице маршрутизации. Несколько упрощая, можно считать, что маршрут ищется по принципу от частного к общему, т.е. сначала ищется маршрут на хост, потом маршрут на IP сеть, к которой принадлежит целевой адрес с маской $/30$ ($255.255.255.252$), потом c маской $/29$ ($255.255.255.248$) и т.д. Последним используется маршрут по умолчанию.

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

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

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

R1

R2

R3

R4

R5

Выполняется обращение с хоста $5.80.90.33$ на хост $5.80.90.185$ и ответ в обратную сторону. Определите маршрут прохождения сетевого пакета туда и обратно. В ответе укажите номера (цифры) всех использованных маршрутизаторов для передачи пакета через запятую.

Например, если передача между двумя компьютерами, от IP1 к IP2, осуществлялась через маршрутизаторы $R10$, $R11$ туда и $R11, R13, R10$ обратно, то в ответе будет $10,11,11,13,10$. Обратите внимание, что когда пакет идёт туда, адрес назначения в его заголовке – IP2, а когда ответ идёт обратно, адрес назначения будет IP1.

При решении задачи следует считать, что имеется вся другая необходимая конфигурационная информация (шлюзы по умолчанию на компьютерах, маршруты к непосредственно подключенным сетям и т.п.).

Пример записи ответа:
1,2,3,4,5

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно аналитически или использовали электронные таблицы и/или программирование на каком-то этапе решения задачи?

2. В аналитической части решения опишите, какие зависимости, закономерности и как Вы определили из условия, какие данные и формулы использовали для вычислений, и как это позволило получить ответ.

3. Если в какой-то части решения Вы использовали электронные таблицы, охарактеризуйте операции, которые Вы в них осуществили, назначение введенных в ячейки формул, и как это позволило получить ответ.

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

Рекомендуемое время пояснения решения 2-4 минуты.

Петя изучает различные виды диаграмм в электронных таблицах. Для того, чтобы потренироваться в построении точечной диаграммы с маркерами, Петя решил изобразить логотип IT-компании VK, заполнив целыми неотрицательными числами диапазон $A2:B21$:

Известно, что числа в столбце $B$ отсортированы по невозрастанию. Какая минимальная сумма может быть у чисел в красных ячейках. В ответе укажите целое число.

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

Пример записи ответа:
171717

Рекомендации к пояснению решения задачи.

В пояснении к решению задачи раскройте следующие вопросы:

1. Решали ли Вы задачу исключительно в электронных таблицах или использовали программирование и/или аналитические методы на каком-то этапе решения задачи?

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

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

4. Если в какой-то части решения Вы использовали аналитические методы решения, опишите, какие зависимости, закономерности и как Вы определили из условия или результатов вычислений в электронных таблицах, какие данные и формулы использовали для вычислений, и как это позволило получить ответ. Рекомендуемое время пояснения решения 1-3 минуты.

IT-компания «VK» имеет огромную инфраструктуру проектов, и чтобы разработчики могли гармонично работать вместе и структурировать вносимые в код изменения, им необходима система контроля версий (VCS).

Полноценные системы контроля версий устроены достаточно сложно, и некоторые компании даже разрабатывают свои собственные VCS, заточенные под конкретные нужды или особенности рабочего процесса. Разумеется, разработчики из «VK» могут справиться с задачей реализовать свою VCS, но сегодня эта задача предлагается вам.

Ваша примитивная система контроля версий должна иметь вид дерева изменений состояния проекта.

• «Корень» дерева — стартовая вершина, соответствующая изначальному состоянию проекта. Это единственная вершина, в которую не входят ребра.
• Каждая вершина, кроме корня, соответствует определенному коммиту. Коммит — блок из одного или более изменений.
• Версия проекта, задаваемая вершиной — набор всех изменений на путях между стартовой вершиной и данной.
• Есть несколько выделенных веток, каждая имеет уникальное имя и задается указателем на определенную вершину дерева. С веткой ассоциируется версия проекта, соответствующая вершине, на которую она указывает.
• Из всех веток выделяется текущая ветка — версия проекта, с которой сейчас работает пользователь. Вершину, на которую указывает текущая ветка, будем обозначать как $\text{HEAD}$.

Пример дерева можно видеть ниже. Рядом с каждым коммитом указаны соответствующие ему изменения. Вершины номер $8$ и $9$ появляются после команды $\text{rebase}$ между ветками «$\text{main}$ и «$\text{new}$_$\text{config}$» (описание команд см. ниже). Набор команд, позволяющий получить приведенную структуру графа версий, приведен в первом тесте. Пошаговые иллюстрации изменения графа версий можно видеть в архиве.

Изначально дерево состоит из единственной вершины с номером $1$, на которую указывает текущая ветка «$\text{main}$». Требуется поддерживать следующие команды:

1. «$\text{add}$ <файл> <хеш изменений>» — запомнить изменения, внесенные в данный файл. Хеш однозначно описывает набор изменений в файле. Иными словами, хеши двух независимых изменений совпадают тогда и только тогда, когда в файл были внесены одинаковые изменения.
   Иными словами, если в пустой файл добавляется строчка «$\text{print(something)}$», и в непустой файл добавляется та же строчка, хеши этих двух изменений будут различными.

2. «$\text{commit}$» — подвесить к $\text{HEAD}$ новую вершину, состоящую из всех изменений ($\text{add}$), сделанных с момента предыдущего успешного коммита. Новой вершине присваивается первый неиспользованный натуральный номер, после чего $\text{HEAD}$ перемещается на нее.
   Операция возможна только тогда, когда множество сделанных изменений непустое. В противном случае требуется выдать ошибку «$\text{FAILURE: no changes}$», при этом новая вершина не создается.

3. «$\text{reset}$ <номер>» — переместить $\text{HEAD}$ на вершину с данным номером.
   Гарантируется, что вершина с данным номером существует. Если присутствуют несохраненные ($\text{commit}$) изменения ($\text{add}$), операция отклоняется с ошибкой «$\text{FAILURE: uncommitted changes}$».

4. «$\text{checkout}$ <имя ветки>» — поменять текущую ветку на ветку с указанным именем (и, соответственно, переместить $\text{HEAD}$ на версию, соответствующую выбранной ветке). Если ветки с таким именем не существует, создать новую ветку с таким именем, которая будет указывать на $\text{HEAD}$, после чего сделать ее текущей.
   Если присутствуют несохраненные изменения, операция отклоняется с ошибкой «$\text{FAILURE: uncommitted changes}$», аналогично операции $\text{reset}$.

5. «$\text{rebase}$ <имя ветки>» — перенести изменения из ветки с указанным именем в текущую ветку. При этом находится ближайший общий предок двух веток и все коммиты в указанной ветке после общего предка (то есть все вершины, которых нет в текущей ветке) копируются и вставляются в текущую ветку после $\text{HEAD}$ в исходном порядке. $\text{HEAD}$ при этом перемещается на последнюю из скопированных вершин, а указатель второй ветки не двигается. Гарантируется, что имя второй ветки не совпадает с текущей.
   Если есть незакоммиченные изменения, операция отклоняется с ошибкой «$\text{FAILURE: uncommitted changes}$».
   Если несохраненных изменений нет, проверяется отсутствие конфликтов при объединении. Конфликтом считается ситуация, когда в состояниях проекта, соответствующим данным веткам, с одним и тем же файлом сделаны различные изменения. Иными словами, если обозначить множество изменений определенного файла в текущей ветке как $D_1$, а во второй — как $D_2$, то конфликт возникает, когда оба множества $D_1 \setminus D_2$ и $D_2 \setminus D_1$ непустые. В таком случае операция отклоняется с ошибкой «$\text{FAILURE: conflicts detected}$». \

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

   Если какое-то изменение содержится в версиях разное ненулевое количество раз (например, изменение может присутствовать дважды после $\text{rebase}$ двух веток, в которые оно входило), конфликт не возникает. Конфликт возникает только если в каждой версии есть изменение одного и того же файла, которого нет в другой версии.

   Ниже можно найти иллюстрации к успешным и конфликтным вызовам операции $\text{rebase}$.

Вам дается последовательность команд, которые требуется обработать. Для каждой команды выведите через пробел слово «$\text{SUCCESS}$» и номер вершины, на которую указывает $\text{HEAD}$, если команда выполнена успешно, или же соответствующую ошибку, если команда отклонена.

Формат входных данных

В первой строке дано единственное целое число $T$ — количество наборов входных данных, которые вам предстоит обработать ($1 \le T \le 20$). Далее следуют описания наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное целое число $n$ — количество команд в наборе ($0 \le n \le 400$). В $i$-й из следующих $n$ строк задается $i$-я команда.

Гарантируется, что имена веток состоят только из маленьких латинских букв ('$\text{a}$' — '$\text{z}$') и нижних подчеркиваний ('_'), а хеши изменений — уникальные шестнадцатеричные строки длины ровно $6$ (состоят из цифр и маленьких латинских букв от '$\text{a}$' до '$\text{f}$'). Имена файлов в команде $\text{add}$ состоят из маленьких латинских букв, точек и слешей ('/').

Также гарантируется, что команде $\text{reset}$ всегда передается существующая вершина, а команде $\text{merge}$ — существующая ветка, не совпадающая с текущей.

Формат выходных данных

Для каждого набора входных данных в порядке их следования во вводе сначала выведите строку «$\text{Test case}$ <номер>» (наборы нумеруются от $1$ до $T$), а затем $n$ результатов выполнения команд, каждый в своей строке.

Результат выполнения каждой команды должен соответствовать либо формату «$\text{SUCCESS}$ <$\text{HEAD}$>», либо формату «$\text{FAILURE:}$ <сообщение об ошибке>».

Пример

2
12
add a.cpp 1f1f1f
reset 1
commit
checkout dev
reset 1
add a.cpp d2d2d2
commit
rebase main
reset 1
add b.cpp abc123
commit
rebase main
23
add main.cpp 1a44bf
add conf.json 3bb3c1
commit
add conf.json 11fdd5
checkout new_config
commit
checkout new_config
checkout main
reset 2
checkout experimental
add driver.cpp b19de7
commit
checkout main
add main.cpp aa46ac
add core/db.cpp f78c43
commit
add core/socket.cpp 554d3b
commit
checkout new_config
add conf.json bbf451
commit
checkout main
rebase new_config

Test case 1
SUCCESS 1
FAILURE: uncommitted changes
SUCCESS 2
SUCCESS 2
SUCCESS 1
SUCCESS 1
SUCCESS 3
FAILURE: conflicts detected
SUCCESS 1
SUCCESS 1
SUCCESS 4
SUCCESS 5
Test case 2
SUCCESS 1
SUCCESS 1
SUCCESS 2
SUCCESS 2
FAILURE: uncommitted changes
SUCCESS 3
SUCCESS 3
SUCCESS 3
SUCCESS 2
SUCCESS 2
SUCCESS 2
SUCCESS 4
SUCCESS 2
SUCCESS 2
SUCCESS 2
SUCCESS 5
SUCCESS 5
SUCCESS 6
SUCCESS 3
SUCCESS 3
SUCCESS 7
SUCCESS 6
SUCCESS 9

Примечание

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

Комментарий

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

Рекомендации к пояснению решения задачи

В пояснении к решению задачи раскройте следующие вопросы:

1. Кратко опишите алгоритм решения задачи.

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

3. По желанию, можно привести оценку сложности предложенного алгоритма.

Рекомендуемое время пояснения решения 2-4 минуты.

Специально для $n$ сотрудников ИТМО, пользующихся личными автомобилями, планируется открыть парковку. На парковке должно быть ровно $n$ парковочных мест, каждому сотруднику должно достаться свое место.

Для экономии мест парковка будет разбита на несколько «рядов». Места в каждом ряду нумеруются от $1$ (самое дальнее от въезда) до длины ряда (самое ближнее ко въезду), и дальние места недоступны, пока не освободятся все более ближние.

Для каждого сотрудника известно, в какое время он приезжает, и в какое время заканчивает работу. Так как сотрудники ИТМО — очень трудолюбивые люди, каждый из них приезжает на работу в один день, а уезжает уже в следующий. Для каждого известно время, в которое он приезжает на работу $t^\mathrm{in}_i$, и время, в которое он уезжает на следующий день $t^\mathrm{out}_i$. Требуется назначить места сотрудникам так, чтобы никому из них не понадобилось ждать

• появления доступного парковочного места, когда он приезжает;
• возможности выехать, когда он заканчивает работу.

Более формально, если сотрудникам $i$ и $j$ назначены места $p_i$ и $p_j$ в одном ряду, и $p_i < p_j$, должно выполняться $t^\mathrm{in}_i \le t^\mathrm{in}_j$ и $t^\mathrm{out}_i \ge t^\mathrm{out}_j$.

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

Формат входных данных

В первой строке ввода дано единственное целое число $T$ — количество наборов входных данных ($1 \le T \le 100$). Далее следуют описания наборов входных данных.

В первой строке описания набора входных данных дано единственное целое число $n$ — количество сотрудников, которых необходимо разместить на парковке.

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $10^5$.

В следующих $n$ строках перечислены времена въезда и выезда для каждого сотрудника, в $i$-й строке через пробел $t^\mathrm{in}_i$ и $t^\mathrm{out}_i$ ($1 \le t^\mathrm{in}_i, t^\mathrm{out}_i \le 10^9$).

Формат выходных данных

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

В первой строке выведите число $k$ — минимальное необходимое количество рядов.

В $i$-й из следующих $n$ строк выведите через пробел сначала номер ряда, а затем номер места в этом ряду, которое надо отдать $i$-му сотруднику. Ряды и места нумеруются с единицы.

Если существует несколько различных ответов, минимизирующих $k$, выведите любой из них.

Пример

4
2
1 3
2 4
3
5 4
7 3
6 1
4
1 8
2 7
3 5
4 6
2
3 2
1 5

2
1 1
2 1
2
1 1
2 1
1 2
2
1 1
1 2
1 3
2 1
1
1 2
1 1

Комментарий

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

Рекомендации к пояснению решения задачи

В пояснении к решению задачи раскройте следующие вопросы:

1. Кратко опишите алгоритм решения задачи.

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

3. По желанию, можно привести оценку сложности предложенного алгоритма.

Рекомендуемое время пояснения решения 2-4 минуты.