Print all permutations of $k$ elements from the positive integers $1,2,3,\ldots,n$.

A permutation is a way of selecting items from a larger group, where the order matters.

Input

• One line containing two integers $n$ and $k$.

Output

• Each line contains $k$ integers representing a permutation. The output should follow dictionary order.

Constraints

• $1 \le k < n \le 7$.

Example

Input:

3 2

Output:

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