CF1975F Set

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.

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) $ .

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.

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