A permutation of n elements is an array of n different natural numbers, each of which is from 1 to n. For example, all permutations of 3 elements: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [ 3, 2, 1].
The elements of a permutation are numbered from 1 to n, for example, for a permutation a = [3, 1, 2] we have a[1] = 3, a[2] = 1, a[3] = 2. The element with number i is called a fixed point , if a[i] = i. Thus, in the permutation [3, 1, 2] there are no fixed points, and in the permutation [1, 3, 2] the element a[1] = 1 is a fixed point.
Let's order all permutations lexicographically — first on the first element, then on the second, and so on. At the beginning of the condition, all permutations of the three elements are listed in lexicographic order. We leave only those permutations that do not contain fixed points. For n = 3, the permutations [2, 3, 1] and [3, 1, 2] will remain.
Given n and t, print the first t in the
lexicographic order of permutations of n elements without fixed points. Permutations should be output in lexicographical order.
Input
The input is two integers n and t (2 ≤ n ≤ 1000, 1 ≤ t ≤ 10
4, nt ≤ 10
5 ). It is guaranteed that there are at least t permutations of n elements without fixed points.
Imprint
Print t lines, on the i-th of them print n numbers: the i-th lexicographical permutation of n elements without fixed points.
Examples
| # |
Input |
Output |
| 1 |
3 1 |
2 3 1 |