Определим бинарное кодирование конечного множества целых неотрицательных чисел \(T \subseteq \{0,1,2,\ldots\}\) как \(f(T) = \sum\limits_{i \in T} 2^i\). Например, \(f(\{0,2\}) = 2^0 + 2^2 = 5\) и \(f(\{\}) = 0\). Обратите внимание, что \(f\) — это биекция от всех таких множеств ко всем неотрицательным целым числам. Таким образом, \(f^{-1}\) также определено.
Дано целое число \(n\) и \(2^n-1\) множество \(V_1,V_2,\ldots,V_{2^n-1}\).
Найдите все множества \(S\), которые удовлетворяют следующим ограничениям:
- \(S \subseteq \{0,1,\ldots,n-1\}\). Заметим, что \(S\) может быть пустым.
- Для всех непустых \(T \subseteq \{0,1,\ldots,n-1\}\) выполнено \(|S \cap T| \in V_{f(T)}\).
Для экономии входные и выходные данные будут заданы в терминах двоичных кодировок множеств.
Выходные данные
Первая строка вывода должна содержать целое число \(k\), обозначающее количество подходящих \(S\).
В следующих \(k\) строках вы должны вывести \(f(S)\) для всех подходящих \(S\) в порядке возрастания.
Примечание
В первом примере одним из возможных \(S\) является \(f^{-1}(3) = \{0,1\}\). Все непустые подмножества \(T \subseteq \{0,1,2\}\) и соответствующие им \(|S \cap T|\), \(f(T)\) и \(V_f(T)\) имеют следующий вид:
| \(T\) | \(|S\cap T|\) | \(f(T)\) | \(V_{f(T)}\) |
| \(\{0\}\) | \(1\) | \(1\) | \(\{0,1,2,3\}\) |
| \(\{1\}\) | \(1\) | \(2\) | \(\{0,1,2,3\}\) |
| \(\{2\}\) | \(0\) | \(4\) | \(\{0,1,2,3\}\) |
| \(\{0,1\}\) | \(2\) | \(3\) | \(\{0,1,2,3\}\) |
| \(\{0,2\}\) | \(1\) | \(5\) | \(\{0,1,2,3\}\) |
| \(\{1,2\}\) | \(1\) | \(6\) | \(\{0,1,2,3\}\) |
| \(\{0,1,2\}\) | \(2\) | \(7\) | \(\{2,3\}\) |
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
15 15 15 15 15 15 12
|
4
3
5
6
7
|
|
2
|
5
63 63 63 63 6 63 63 63 63 63 63 5 63 63 63 63 63 63 8 63 63 63 63 2 63 63 63 63 63 63 63
|
1
19
|