← Home
write a go solution for Description:
Define the binary encoding of a finite set of natural numbers Tsubseteq0,1,2,ldots as f(T)=sumlimits_iinT2^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:

- Ssubseteq0,1,ldots,n-1. Note that S can be empty.
- For all non-empty subsets Tsubseteq0,1,ldots,n-1, |ScapT|inV_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 Format:
The first line of input contains a single integer n (1<=qn<=q20).

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

Output Format:
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.

Note:
In the first test case, one possible S is f^-1(3)=0,1. All the non-empty subsets Tsubseteq0,1,2 and the corresponding |ScapT|, f(T) and V_f(T) are as follows:

T|ScapT|f(T)V_f(T)0110,1,2,31120,1,2,32040,1,2,30,1230,1,2,30,2150,1,2,31,2160,1,2,30,1,2272,3. Output only the code with no comments, explanation, or additional text.