可重排列

题目描述

请按字典序从小到大的顺序输出所有序列，满足序列中有 $p_1$ 个 $1$, $p_2$ 个 $2$, $\dots$, $p_n$ 个 $n$。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $p_1, p_2, \dots, p_n$。

输出格式

按字典序从小到大的顺序一行一行输出所有满足条件的序列，每行一个序列，相邻两个数字需要用空格隔开。

样例输入

3
1 2 2

样例输出

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

数据范围

对于 $100\%$ 的数据，保证 $1\leq n\leq 9, 1\leq p_i\leq 9$，保证满足条件的序列个数不超过 $10^5$ 个。