You are given a list of n unique elements. Your task is to generate all possible permutations of the elements in the list and output them in lexicographical order.

Input

The first line contains a single integer n (1 β€ n β€ 6), representing the length of the list.
The second line contains n space-separated distinct integers (1 β€ β€ 100), denoting the elements of the list.

Output

Output all possible permutations of the given list, with each permutation printed on a separate line. Each permutation should be represented as a space-separated sequence of elements.