2969-й год. Прошло 1000 лет с момента посадки на луну. Человечество колонизировало Гиперпространство и жило в гармонии.
Жило, пока мы не поняли, что мы не одни.
Не очень далеко от Земли многочисленный космический флот инопланетян готовит атаку на Землю. Впервые за долгое время человечеству угрожает реальная опасность. Повсюду паника и кризис. Ученые со всей солнечной системы встретились и обсуждают возможный выход из ситуации. Но пока все усилия тщетны.
Последняя надежда Земли — ВЫ!
К счастью, Земля имеет мощную систему защиты, созданную специалистами из MDCS. Флот инопланетян содержит \(N\) кораблей на одной линии. Система защиты состоит из трех типов вооружения:
- SQL-ракеты: каждая SQL-ракета может уничтожить не более одного корабля инопланетян из заданного для каждой ракеты набора.
- лучи Познания: каждому лучу Познания сопоставлен отрезок \([l,r]\), он может уничтожить не более одного корабля инопланетян из этого отрезка.
- OMG-базука: каждая OMG-базука имеет ровно три цели и может уничтожить либо ровно ноль, либо ровно два корабля. Кроме того, система прицеливания является «умной», поэтому множества трех целей для любых двух OMG-базук не пересекаются (таким образом, каждый корабль находится под прицелом не более чем одной OMG-базуки).
Ваша задача — найти такой план атаки на корабли инопланетян, чтобы уничтожить максимально возможное количество кораблей. Каждый уничтоженный корабль должен быть уничтожен ровно одним оружием.
Выходные данные
Первая строка должна содержать максимальное количество уничтоженных кораблей \(X\).
Каждая из следующих \(X\) строк должна содержать два целых числа \(A\) и \(B\), где \(A\) — номер оружия, а \(B\) — номер корабля, уничтоженного оружием \(A\).
Примечание
SQL-ракета может уничтожить только четвертый корабль. OMG-базука может уничтожить два из 1-го, 4-го или 5-го кораблей, а луч Познания может уничтожить любой корабль из отрезка \([1,4]\). Максимальное количество уничтоженных кораблей равно 4, один из возможных планов — SQL-ракета уничтожает 4-й корабль, OMG-базука уничтожает 1-й и 5-й корабли, а луч Познания уничтожает 2-й корабль.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
0 1 4
2 5 4 1
1 1 4
|
4
2 1
3 2
1 4
2 5
|