Multiset Permutations

Problem Description

Output all sequences in lexicographically increasing order such that the sequence contains $p_1$ copies of $1$, $p_2$ copies of $2$, $\dots$, $p_n$ copies of $n$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$.

Output Format

Output all valid sequences in lexicographically increasing order, one sequence per line. Numbers in a sequence are separated by spaces.

Sample Input

3
1 2 2

Sample Output

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

Constraints

For $100\%$ of the data, $1 \le n \le 9$, $1 \le p_i \le 9$, and the total number of valid sequences does not exceed $10^5$.