Вам дана бинарная матрица \(b\) (все элементы матрицы равны \(0\) или \(1\)) из \(n\) строк и \(n\) столбцов.
Вам нужно построить \(n\) множеств \(A_1, A_2, \ldots, A_n\), для которых выполняются следующие условия:
- Каждое множество непустое и состоит из различных целых чисел от \(1\) до \(n\) включительно.
- Все множества попарно различны.
- Для всех пар \((i,j)\), удовлетворяющих условиям \(1\leq i, j\leq n\), \(b_{i,j}=1\) тогда и только тогда, когда \(A_i\subsetneq A_j\). Другими словами, \(b_{i, j}\) равно \(1\), если \(A_i\) является собственным подмножеством \(A_j\) и \(0\) в противном случае.
Множество \(X\) является собственным подмножеством множества \(Y\), если \(X\) является непустым подмножеством \(Y\), и \(X \neq Y\).
Гарантируется, что для всех наборов входных данных в этой задаче, такие \(n\) множеств существуют. Заметим, что это не означает, что такие \(n\) множеств существуют для всех возможных наборов входных данных.
Если существует несколько решений, то можно вывести любое из них.
Выходные данные
Для каждого набора входных данных выведите \(n\) строк.
В \(i\)-й строке сначала выведите \(s_i\) \((1 \le s_i \le n)\) — размер множества \(A_i\). Затем выведите \(s_i\) попарно различных целых чисел от \(1\) до \(n\) — элементы множества \(A_i\).
Если существует несколько решений, то можно вывести любое из них.
Гарантируется, что для всех наборов входных данных в данной задаче такие \(n\) множеств существуют.
Примечание
В первом наборе входных данных имеем \(A_1 = \{1, 2, 3\}, A_2 = \{1, 3\}, A_3 = \{2, 4\}, A_4 = \{1, 2, 3, 4\}\). Множества \(A_1, A_2, A_3\) являются собственными подмножествами \(A_4\), а также множество \(A_2\) является собственным подмножеством \(A_1\). Никакое другое множество не является собственным подмножеством никакого другого множества.
Во втором наборе входных данных имеем \(A_1 = \{1\}, A_2 = \{1, 2\}, A_3 = \{1, 2, 3\}\). \(A_1\) является собственным подмножеством \(A_2\) и \(A_3\), а \(A_2\) является собственным подмножеством \(A_3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
0001
1001
0001
0000
3
011
001
000
|
3 1 2 3
2 1 3
2 2 4
4 1 2 3 4
1 1
2 1 2
3 1 2 3
|