В 2025 году в Берляндии впервые будет проводиться трёхдневный межпланетный съезд по вопросам проведения олимпиад по информатике. Доклады съезда разбиты на 12 секций, и теперь организаторам необходимо распределить секции по дням: в каждый день будут проводиться 4 секции.
Известно, что в съезде примут участие \(n\) человек. Каждый участник съезда выбрал 3 секции, которые он хочет посетить. Но поскольку в один день секции будут проводиться одновременно, каждый участник в один день может присутствовать не более чем на одной секции. Поэтому если в один день будут идти две или три секции, выбранные каким-то участником, то он всё равно сможет посетить только одну из них. Если же выбранные секции будут проходить в разные дни, участник сможет посетить их все.
Для того чтобы съезд принёс как можно больше пользы, необходимо составить расписание съезда таким образом, чтобы суммарное число секций, посещённых всеми участниками, было как можно больше. Помогите оргкомитету составить такое расписание.
Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(1 \leq n \leq 10\,000\)) — количество участников съезда.
В каждой из следующих \(n\) строк даны \(3\) попарно различных натуральных числа, не превосходящие \(12\), — номера секций, которые хочет посетить один из участников.
Формат выходных данных
Программа должна вывести \(3\) строки, в каждой из которых должны быть \(4\) числа через пробел — номера секций, проводимых в первый, второй и третий день съезда соответственно. Каждое из чисел от 1 до 12 должно встречаться в выводе ровно один раз. Если возможных оптимальных расписаний несколько, можно вывести любое из них.
Примечание
В примере из условия расписание составлено так, что второй и третий участник посетят все желаемые секции, а первый — две секции (\(5\) и одну из секций \(1\), \(6\)). Таким образом, суммарно будут посещены 8 секций. Можно показать, что этот результат улучшить нельзя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 6 1
6 7 9
1 9 7
|
1 11 6 12
10 5 7 8
9 2 3 4
|