Маленький Вася очень любит играть со множествами из натуральных чисел. Для того, чтобы играть было еще интереснее, Вася выбрал n таких непустых множеств, что никакие два из них не имеют общих элементов.
Однажды он захотел показать своим друзьям, что играть с числами очень интересно. Для этого он выписал на n·(n - 1) / 2 листочках бумаги всевозможные объединения двух различных множеств и перемешал сами листочки. Числа в объединениях он выписывал в произвольном порядке.
Например, если n = 4, а сами множества имеют вид {1, 3}, {5}, {2, 4}, {7}, то количество пар множеств окажется равным шести. На шести листочках могут быть указаны следующие числа:
- 2, 7, 4.
- 1, 7, 3;
- 5, 4, 2;
- 1, 3, 5;
- 3, 1, 2, 4;
- 5, 7.
Затем Вася показал эти листочки друзьям, но n множеств сохранил от них в секрете. Друзья смогли быстро вычислить, какие множества загадал Вася. А сможете ли вы восстановить множества по заданным листочкам?
Выходные данные
Выведите в n строках описание множеств Васи. Первое число в строке — это количество чисел в текущем множестве, а далее должны быть записано множество перечислением своих элементов. Числа разделяйте пробелами. Каждое число и каждое множество нужно выводить ровно один раз. Множества и числа в них выводите в любом порядке. Если ответов несколько, выведите любой.
Гарантируется, что решение существует.