Задача 1F. Новая система

Автор:А. Кленин, И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Утенок Даки на киникулах придумал новую систему для измерения времени и решил внедрить ее в своем университете. С помощью нее Даки предложил определять момент окончания лекций.

Его система использует два таймера В первых таймер установлен на a минут, второй — на b минут. В начале лекции профессор запускает первые, вторые или сразу и те и другие часы. Как только какой-нибудь таймер срабатывает (выходит установленное время), профессор может перезапустить первый, второй или сразу оба таймера. При запуске время на таймерах устанавливается в соответсвие с начальным.

К концу лекции оба таймера должны закончить свою работу. Лекция длится T минут.

По заданным a, b и T определите искомую последовательность перезапусков.

Считается, что профессор перезапускает часы мгновенно.

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

Формат входного файла

Первая строка входного файла содержит количество тестов n. Далее следует n строк с целыми числами T, a, b.

Формат выходного файла

Выходной файл должен содержать n блоков с ответами на тесты.

Первая строка каждого блока должна содержать количество действий, k. Далее должно следовать k строк с парами целых чисел ti mi в каждой, где ti — время выполнения действия, mi — одно из чисел 1, 2 или 3, обозначающее, что необходимо перезапустить первый, второй или оба таймера соответственно. Для первого действия должно быть ti = 0, для остальных ti должно быть таким, что в этот момент песок хотя бы в одних часах только что полностью пересыпался вниз. Все ti должны быть различны и расположены по возрастанию.

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

Примечание: Поскольку блоки в выходном файле находятся один за другим, то, если указать неверное k в начале блока, все последующие блоки будут восприняты как ошибочные. Поэтому в случае частичного решения задачи рекомендуется указывать k = 0 для тех тестов, ответ к которым вам найти не удалось.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
11 4 7
7 4 7

2
0 1
4 2
1
0 3

0.212s 0.024s 17