将有限自然数集 $$$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$$$ 行中,您应该按升序输出所有可能的 $$$S$$$ $$$f(S)$$$。
示例
输入 #1
3 15 15 15 15 15 15 12
输出 #1
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
输出 #2
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\}$$$