Enumeration of Subsets II

$0$から$n-1$までの$n$個の整数を要素とする集合$U$の部分集合$T$が与えられます。$U$の部分集合であって、$T$を部分集合に持つような全ての集合を列挙してください。ただし、$0$から$n-1$をそれぞれ2進数の00...0001、00...0010、00...0100、...、10...0000とし、存在する要素のビットごとの論理和を取ったものをその部分集合の整数値とします。

Input

入力は以下の形式で与えられます。

$n$
$k \; b_0 \; b_1 \; ... \; b_{k-1}$

$k$は$T$ の要素数で、$b_i$ は$T$に含まれる要素を示します。

Output

部分集合をそれらの整数値の昇順で出力してください。１つの部分集合は以下の形式で出力してください。

$d$: $e_0$ $e_1$ ...

整数値$d$の後にコロン:、続けて部分集合に含まれる要素$e_i$を昇順で空白付きで出力してください。

Constraints

• $1 \leq n \leq 18$
• $0 \leq k \leq n$
• $0 \leq b_i < n$

Sample Input 1

4
2 0 2

Sample Output 1

5: 0 2
7: 0 1 2
13: 0 2 3
15: 0 1 2 3

---