311369: CF1975F. Set

F. Settime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Define the binary encoding of a finite set of natural numbers $T \subseteq \{0,1,2,\ldots\}$ as $f(T) = \sum\limits_{i \in T} 2^i$. For example, $f(\{0,2\}) = 2^0 + 2^2 = 5$ and $f(\{\}) = 0$. Notice that $f$ is a bijection from all such sets to all non-negative integers. As such, $f^{-1}$ is also defined.

You are given an integer $n$ along with $2^n-1$ sets $V_1,V_2,\ldots,V_{2^n-1}$.

Find all sets $S$ that satisfy the following constraint:

• $S \subseteq \{0,1,\ldots,n-1\}$. Note that $S$ can be empty.
• For all non-empty subsets $T \subseteq \{0,1,\ldots,n-1\}$, $|S \cap T| \in V_{f(T)}$.

Due to the large input and output, both input and output will be given in terms of binary encodings of the sets.

Input

The first line of input contains a single integer $n$ ($1 \leq n \leq 20$).

The second line of input contains $2^n-1$ integers $v_1,v_2,\ldots,v_{2^n-1}$ ($0 \leq v_i < 2^{n+1}$) — the sets $V_i$ given in their binary encoding where $V_i = f^{-1}(v_i)$.

Output

The first line of output should contain an integer $k$ indicating the number of possible $S$.

In the following $k$ lines, you should output $f(S)$ for all possible $S$ in increasing order.

ExamplesInput

3
15 15 15 15 15 15 12

Output

4
3
5
6
7

Input

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

Output

1
19

Note

In the first test case, one possible $S$ is $f^{-1}(3) = \{0,1\}$. All the non-empty subsets $T \subseteq \{0,1,2\}$ and the corresponding $|S \cap T|$, $f(T)$ and $V_f(T)$ are as follows:

$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\}$

题目大意：
定义自然数有限集合T的二进制编码为 f(T) = Σ2^i (i属于T)。例如，f({0,2}) = 2^0 + 2^2 = 5，f({}) = 0。注意f是从所有这样的集合到所有非负整数的双射。因此，f^(-1)也是定义良好的。

给定一个整数n以及2^n-1个集合V_1, V_2, ..., V_(2^n-1)。

找到所有满足以下条件的集合S：
1. S是{0,1,...,n-1}的子集。注意S可以是空集。
2. 对于所有非空子集T属于{0,1,...,n-1}，|S交T|属于V_(f(T))。

由于输入和输出很大，输入和输出都将用集合的二进制编码表示。

输入数据格式：
第一行输入包含一个整数n (1 ≤ n ≤ 20)。
第二行输入包含2^n-1个整数v_1, v_2, ..., v_(2^n-1) (0 ≤ v_i < 2^(n+1)) —— 集合V_i以其二进制编码给出，其中V_i = f^(-1)(v_i)。

输出数据格式：
第一行输出应该包含一个整数k，表示可能的S的数量。
在接下来的k行中，你应该按递增顺序输出所有可能的S的f(S)。题目大意： 定义自然数有限集合T的二进制编码为 f(T) = Σ2^i (i属于T)。例如，f({0,2}) = 2^0 + 2^2 = 5，f({}) = 0。注意f是从所有这样的集合到所有非负整数的双射。因此，f^(-1)也是定义良好的。 给定一个整数n以及2^n-1个集合V_1, V_2, ..., V_(2^n-1)。 找到所有满足以下条件的集合S： 1. S是{0,1,...,n-1}的子集。注意S可以是空集。 2. 对于所有非空子集T属于{0,1,...,n-1}，|S交T|属于V_(f(T))。 由于输入和输出很大，输入和输出都将用集合的二进制编码表示。 输入数据格式： 第一行输入包含一个整数n (1 ≤ n ≤ 20)。 第二行输入包含2^n-1个整数v_1, v_2, ..., v_(2^n-1) (0 ≤ v_i < 2^(n+1)) —— 集合V_i以其二进制编码给出，其中V_i = f^(-1)(v_i)。 输出数据格式： 第一行输出应该包含一个整数k，表示可能的S的数量。 在接下来的k行中，你应该按递增顺序输出所有可能的S的f(S)。