Lexicographic Subset Generator

You are given an array of n integers. Your task is to generate all possible subsets of the array in lexicographic order. The array should be sorted in ascending order before generating the subsets. Each subset must be printed on a new line with its elements separated by a single space. The empty subset should be represented as an empty line.

For clarity, the lexicographic order is defined as follows: for any two subsets \(A=[a_1,a_2,\dots,a_k]\) and \(B=[b_1,b_2,\dots,b_m]\), we say \(A < B\) if there exists an index \(i\) such that \(a_j = b_j\) for all \(1 \leq j < i\) and \(a_i < b_i\), or if \(A\) is empty while \(B\) is non-empty.

inputFormat

The first line of input contains a single integer \(n\) (the number of elements). The second line contains \(n\) integers separated by spaces.

outputFormat

Output all subsets in lexicographic order, each on a separate line. Each subset's elements should be separated by a single space. The empty subset must be printed as an empty line.

3
1 2 3

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