You are given a set of n distinct integers. Produce every subset of the set, including the empty subset and the full set.

To make the answer unique, print the subsets in a fixed canonical order:

1. Within each subset, the elements are listed in ascending order.
2. Subsets are ordered first by their size (fewest elements first), and subsets of the same size are ordered lexicographically by their ascending element lists.

Input format

Line 1: an integer n. Line 2: n space-separated distinct integers (this line is empty when n = 0).

Output format

Line 1: an integer M, the number of subsets (which equals 2^n). The next M lines: one subset per line, its elements space-separated in ascending order. The empty subset is printed as an empty line.

Constraints

• 0 ≤ n ≤ 15
• -1000000 ≤ each value ≤ 1000000
• all n values are distinct

3
3 1 2

8

1
2
3
1 2
1 3
2 3
1 2 3

1
5

2

5