问题描述

给定n个互不相同的正整数，这些数已经按照升序排列形成一个序列。现要将这n个数的所有可能的全排列输出，且每个数只能使用一次。注意：优先输出较小的数字。

输入

两行， 第一行一个正整数n（1≤n≤9）， 第二行n个整数。

输出

输出若千行，每行包括n个空格分隔的数字，表示一组序列。

Samples

3
7 9 12

7 9 12
7 12 9
9 7 12
9 12 7
12 7 9
12 9 7

Limitation

1s, 1024KiB for each test case.