Задача C. Профессор и песок ≡

Условие

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

К концу лекции весь песок в часах вновь должен оказаться внизу. Лекция длится T минут.

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

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

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

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

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

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

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

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

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

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

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

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

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

2
11 4 7
7 4 7

2
0 1
4 2
1
0 3