27248번 - Без неподвижных точек 다국어

Перестановкой $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$ элементов без неподвижных точек.