Без неподвижных точек

Перестановкой $n$ элементов называется массив из различных натуральных $n$ чисел, каждое из которых от $1$ до $n$. Например, все перестановки $3$ элементов: $\[1, 2, 3]$, $\[1, 3, 2]$, $\[2, 1, 3]$, $\[2, 3, 1]$, $\[3, 1, 2]$, $\[3, 2, 1]$.

Элементы перестановки пронумерованы от одного до $n$, например для перестановки $a = \[3, 1, 2]$ выполнено $a\[1] = 3$, $a\[2] = 1$, $a\[3] = 2$. Элемент с номером $i$ называется неподвижной точкой, если $a\[i] = i$. Так, в перестановке $\[3, 1, 2]$ нет неподвижный точек, а в перестановке $\[1, 3, 2]$ элемент $a\[1] = 1$ является неподвижной точкой.

Упорядочим все перестановки лексикографически --- сначала по первому элементу, потом по второму, и так далее. В начале условия все перестановки трех элементов приведены в лексикографическом порядке. Оставим только те перестановки, которые не содержат неподвижных точек. Для $n = 3$ останутся перестановки $\[2, 3, 1]$ и $\[3, 1, 2]$.

По заданным $n$ и $t$ требуется вывести первые $t$ в лексикографическом порядке перестановок $n$ элементов без неподвижных точек. Перестановки следует выводить в лексикографическом порядке.

На ввод подаются два целых числа $n$ и $t$ ($2 \le n \le 1000$, $1 \le t \le 10^4$, $nt \le 10^5$). Гарантируется, что существует хотя бы $t$ перестановок $n$ элементов без неподвижных точек.

Выведите $t$ строк, на $i$-й из них выведите $n$ чисел: $i$-ю в лексикографическом порядке перестановку $n$ элементов без неподвижных точек.