Permutations of n by k

For a given natural number $n$, derive all permutations of integers from $1$ to $n$ to $k$ numbers in lexicographic order.

Input

Two natural numbers $n$ and $k$ $(1\le k\le n\le 8$).

Output

Derive all permutations of integers from $1$ to $n$ to $k$ numbers in lexicographic order. Each permutation should be displayed on a separate line.

Examples