F. Множество
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим бинарное кодирование конечного множества целых неотрицательных чисел $$$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)}$$$.

Для экономии входные и выходные данные будут заданы в терминах двоичных кодировок множеств.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 20$$$).

Вторая строка содержит $$$2^n-1$$$ целое число $$$v_1,v_2,\ldots,v_{2^n-1}$$$ ($$$0 \leq v_i < 2^{n+1}$$$) — множества $$$V_i$$$, заданные их двоичными кодированиями, где $$$V_i = f^{-1}(v_i)$$$.

Выходные данные

Первая строка вывода должна содержать целое число $$$k$$$, обозначающее количество подходящих $$$S$$$.

В следующих $$$k$$$ строках вы должны вывести $$$f(S)$$$ для всех подходящих $$$S$$$ в порядке возрастания.

Примеры
Входные данные
3
15 15 15 15 15 15 12
Выходные данные
4
3
5
6
7
Входные данные
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
Примечание

В первом примере одним из возможных $$$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\}$$$