Yeah, we failed to make up a New Year legend for this problem.

A permutation of length $n$ is an array of $n$ integers such that every integer from $1$ to $n$ appears in it exactly once. 

An element $y$ of permutation $p$ is reachable from element $x$ if $x = y$, or $p_x = y$, or $p_{p_x} = y$, and so on. 

The decomposition of a permutation $p$ is defined as follows: firstly, we have a permutation $p$, all elements of which are not marked, and an empty list $l$. Then we do the following: while there is at least one not marked element in $p$, we find the leftmost such element, list all elements that are reachable from it in the order they appear in $p$, mark all of these elements, then cyclically shift the list of those elements so that the maximum appears at the first position, and add this list as an element of $l$. After all elements are marked, $l$ is the result of this decomposition.

For example, if we want to build a decomposition of $p = [5, 4, 2, 3, 1, 7, 8, 6]$, we do the following:  initially $p = [5, 4, 2, 3, 1, 7, 8, 6]$ (bold elements are marked), $l = []$;  the leftmost unmarked element is $5$; $5$ and $1$ are reachable from it, so the list we want to shift is $[5, 1]$; there is no need to shift it, since maximum is already the first element;  $p = [\textbf{5}, 4, 2, 3, \textbf{1}, 7, 8, 6]$, $l = [[5, 1]]$;  the leftmost unmarked element is $4$, the list of reachable elements is $[4, 2, 3]$; the maximum is already the first element, so there's no need to shift it;  $p = [\textbf{5}, \textbf{4}, \textbf{2}, \textbf{3}, \textbf{1}, 7, 8, 6]$, $l = [[5, 1], [4, 2, 3]]$;  the leftmost unmarked element is $7$, the list of reachable elements is $[7, 8, 6]$; we have to shift it, so it becomes $[8, 6, 7]$;  $p = [\textbf{5}, \textbf{4}, \textbf{2}, \textbf{3}, \textbf{1}, \textbf{7}, \textbf{8}, \textbf{6}]$, $l = [[5, 1], [4, 2, 3], [8, 6, 7]]$;  all elements are marked, so $[[5, 1], [4, 2, 3], [8, 6, 7]]$ is the result. 

The New Year transformation of a permutation is defined as follows: we build the decomposition of this permutation; then we sort all lists in decomposition in ascending order of the first elements (we don't swap the elements in these lists, only the lists themselves); then we concatenate the lists into one list which becomes a new permutation. For example, the New Year transformation of $p = [5, 4, 2, 3, 1, 7, 8, 6]$ is built as follows:  the decomposition is $[[5, 1], [4, 2, 3], [8, 6, 7]]$;  after sorting the decomposition, it becomes $[[4, 2, 3], [5, 1], [8, 6, 7]]$;  $[4, 2, 3, 5, 1, 8, 6, 7]$ is the result of the transformation. 

We call a permutation good if the result of its transformation is the same as the permutation itself. For example, $[4, 3, 1, 2, 8, 5, 6, 7]$ is a good permutation; and $[5, 4, 2, 3, 1, 7, 8, 6]$ is bad, since the result of transformation is $[4, 2, 3, 5, 1, 8, 6, 7]$.

Your task is the following: given $n$ and $k$, find the $k$-th (lexicographically) good permutation of length $n$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Then the test cases follow. Each test case is represented by one line containing two integers $n$ and $k$ ($1 \le n \le 50$, $1 \le k \le 10^{18}$).


-----Output-----

For each test case, print the answer to it as follows: if the number of good permutations of length $n$ is less than $k$, print one integer $-1$; otherwise, print the $k$-th good permutation on $n$ elements (in lexicographical order).


-----Example-----
Input
5
3 3
5 15
4 13
6 8
4 2

Output
2 1 3 
3 1 2 5 4 
-1
1 2 6 3 4 5 
1 2 4 3

Source: codeforces | Difficulty: VERY_HARD
Tags: Dynamic programming

Combinatorics


Solutions:
import math
maxn = 55
g = [1]
for i in range(maxn):
	g.append(math.factorial(i))
f = [0] * maxn
f[0] = 1
for i in range(1, maxn):
	for j in range(i):
		f[i] += f[j] * g[i - j - 1]

def kth(n, k):
	if n == 1:
		return [1]
	ret = [-1] * n
	ret[0] = n - 1
	p1 = [i for i in range(n)]
	p2 = [i for i in range(n)]
	vis = [False] * n
	p1[0] = n - 1
	p2[n - 1] = 0
	vis[n - 1] = True
	for i in range(1, n - 1):
		j = 0
		now = math.factorial(n - i - 2)
		while True:
			while vis[j] or (i < n - 1 and j == p2[i]):
				j += 1
			if k > now:
				k -= now
				j += 1
			else:
				p1[p2[i]] = p1[j]
				p2[p1[j]] = p2[i]
				ret[i] = j
				vis[j] = True
				break
	ret[-1] = p2[-1]
	return [x + 1 for x in ret]

def solve(n, k):
	if n == 0:
		return []
	i = 1
	while g[i - 1] * f[n - i] < k:
		k -= g[i - 1] * f[n - i]
		i += 1
	rem = solve(n - i, (k - 1) % f[n - i] + 1)
	rem = [x + i for x in rem]
	k = (k - 1) // f[n - i] + 1
	return kth(i, k) + rem

def SOLVE():
	(n, k) = map(int, input().split())
	if k > f[n]:
		print(-1)
		return
	ans = solve(n, k)
	for x in ans:
		print(x, end=' ')
	print()
T = int(input())
while T > 0:
	T -= 1
	SOLVE()


from sys import stdin, stdout
from math import factorial
N = 55
cyc = [1] * N
for i in range(1, N):
	cyc[i] = factorial(i - 1)
dp = [0] * N
dp[0] = 1
for i in range(1, N):
	for j in range(i):
		dp[i] += dp[j] * cyc[i - j - 1]

def kth_cycle(n, k):
	if n == 1:
		return [1]
	res = [-1] * n
	res[0] = n - 1
	used = [False] * n
	used[n - 1] = True
	fr = [i for i in range(n)]
	fr[n - 1] = 0
	to = [i for i in range(n)]
	to[0] = n - 1
	for i in range(1, n - 1):
		cur = factorial(n - i - 2)
		for j in range(n):
			if used[j] or j == fr[i]:
				j += 1
			elif k > cur:
				k -= cur
				j += 1
			else:
				to[fr[i]] = to[j]
				fr[to[j]] = fr[i]
				res[i] = j
				used[j] = True
				break
	res[n - 1] = fr[n - 1]
	return [x + 1 for x in res]

def solve(n, k):
	if n == 0:
		assert k == 1
		return []
	cnt = 1
	while cyc[cnt - 1] * dp[n - cnt] < k:
		k -= cyc[cnt - 1] * dp[n - cnt]
		cnt += 1
	nxt = (k - 1) % dp[n - cnt] + 1
	kth = (k - 1) // dp[n - cnt] + 1
	other = solve(n - cnt, nxt)
	other = [x + cnt for x in other]
	return kth_cycle(cnt, kth) + other

def solve_testcase():
	(n, k) = [int(x) for x in stdin.readline().split()]
	if dp[n] < k:
		stdout.write('-1\n')
		return
	ans = solve(n, k)
	for i in ans:
		stdout.write(str(i) + ' ')
	stdout.write('\n')

def main():
	t = int(stdin.readline())
	for i in range(t):
		solve_testcase()
main()


import math
from decimal import *
getcontext().prec = 50

class DSU:

	def __init__(self, n):
		self.hash = {}
		for i in range(1, n + 1):
			self.hash[i] = [i]

	def union(self, i, j):
		lst1 = self.hash[i]
		lst2 = self.hash[j]
		lst1.extend(lst2)
		for element in lst2:
			self.hash[element] = lst1

	def same_set(self, i, j):
		return j in self.hash[i]

def getKthPerm(lst, k, offset):
	if len(lst) - 1 == offset:
		return True
	elif len(lst) <= offset:
		return False
	else:
		n = len(lst) - offset
		index = math.ceil(k / math.factorial(n - 1)) - 1 + offset
		if index >= len(lst):
			return False
		if index > offset:
			temp = lst[index]
			lst.pop(index)
			lst.insert(offset, temp)
		while k - math.factorial(n - 1) > 0:
			k -= math.factorial(n - 1)
		return getKthPerm(lst, k, offset + 1)

def getKthCycle(n, k, fact):
	lst = [i - 1 for i in range(n + 1)]
	num_open = n
	dsu = DSU(n)
	dsu.union(1, n)
	lst[1] = n
	num_open -= 1
	pos = 2
	while pos < n:
		i = pos
		while i <= n:
			if dsu.same_set(pos, lst[i]):
				pass
			elif k <= fact[num_open - 2]:
				break
			else:
				k -= fact[num_open - 2]
			i += 1
		if i == n + 1:
			return None
		else:
			num_open -= 1
			dsu.union(pos, lst[i])
			temp = lst[i]
			j = i
			while j > pos:
				lst[j] = lst[j - 1]
				j -= 1
			lst[pos] = temp
		pos += 1
	return lst[1:]

def cycles(n, fact):
	if n <= 1:
		return 1
	elif n - 2 in fact:
		return fact[n - 2]
	else:
		return math.factorial(n - 2)

def dp(i, n, table, fact):
	if i > n:
		return 0
	elif i == n:
		return 1
	elif i in table:
		return table[i]
	else:
		val = 0
		for j in range(i, n + 1):
			val += dp(j + 1, n, table, fact) * cycles(j - i + 1, fact)
		table[i] = val
		return val

def Max(i, table, fact):
	if i in table:
		return table[i]
	elif i <= 1:
		table[i] = 1
		return 1
	else:
		val = 0
		for j in range(1, i + 1):
			val += Max(i - j, table, fact) * cycles(j, fact)
		table[i] = val
		return val

def getKthGoodPermutation(n, k, Max, fact):
	if Max[n] < k:
		return None
	if n == 1:
		if k == 1:
			return [1]
		else:
			return None
	block_len = 1
	while k - cycles(block_len, fact) * Max[n - block_len] > 0:
		k -= cycles(block_len, fact) * Max[n - block_len]
		block_len += 1
	k_block = math.ceil(Decimal(k) / Decimal(Max[n - block_len]))
	k_rem = k - (k_block - 1) * Max[n - block_len]
	new_lst = getKthCycle(block_len, k_block, fact)
	if n - block_len > 0:
		rem_lst = getKthGoodPermutation(n - block_len, k_rem, Max, fact)
		for i in range(len(rem_lst)):
			rem_lst[i] += block_len
		new_lst.extend(rem_lst)
	return new_lst

def compute_fact(n, table):
	table[0] = 1
	table[1] = 1
	x = 2
	while x <= n:
		table[x] = x * table[x - 1]
		x += 1
	return
T = int(input())
(N, K) = ([], [])
for _ in range(T):
	inp = input().rstrip().split(' ')
	(n, k) = (int(inp[0]), int(inp[1]))
	N.append(n)
	K.append(k)
max_n = max(N) + 5
fact = {}
compute_fact(max_n, fact)
dp_table = {}
a = 1
while a <= max_n:
	Max(a, dp_table, fact)
	a += 1
j = 0
while j < len(N):
	lst = getKthGoodPermutation(N[j], K[j], dp_table, fact)
	if lst != None:
		for i in range(len(lst)):
			lst[i] = str(lst[i])
		print(' '.join(lst))
	else:
		print('-1')
	j += 1


MAXN = 55
f = [0] * MAXN
fac = [0] * MAXN
fac[0] = 1
for i in range(1, 51):
	fac[i] = fac[i - 1] * i
f[0] = 1
for i in range(1, 51):
	f[i] += f[i - 1]
	for j in range(2, i + 1):
		f[i] += fac[j - 2] * f[i - j]

def my_fac(n):
	if n <= 0:
		return 1
	return fac[n]

def solve_first(n, k):
	ret = [0] * (n + 1)
	ret[1] = n
	for p in range(2, n + 1):
		for i in range(1, n + 1):
			if i in ret or i == p:
				continue
			ret[p] = i
			cur = p
			good = True
			for fuck in range(0, n - 1):
				cur = ret[cur]
				if cur == 0:
					good = True
					break
				if cur == p:
					good = False
					break
			if not good:
				ret[p] = 0
				continue
			k1 = my_fac(n - p - 1)
			if k > k1:
				k -= k1
			else:
				break
			ret[p] = 0
	ret.pop(0)
	assert len(ret) == n
	return ret

def solve(n, k):
	if k == 1:
		ret = []
		for i in range(1, n + 1):
			ret.append(i)
		return ret
	tot = 0
	first = -1
	for i in range(1, n + 1):
		if tot + my_fac(i - 2) * f[n - i] >= k:
			first = i
			break
		tot += my_fac(i - 2) * f[n - i]
	k -= tot
	cnt1 = my_fac(first - 1)
	cnt2 = f[n - first]
	x = k // cnt2 + 1
	y = k % cnt2
	if y == 0:
		y = cnt2
		x -= 1
	ret = solve_first(first, x)
	for v in solve(n - first, y):
		ret.append(v + first)
	return ret
T = int(input())
for t in range(0, T):
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	if k > f[n]:
		print('-1')
	else:
		ans = solve(n, k)
		for x in ans:
			print(x, end=' ')
		print('')


3
from math import factorial as fact
N = 55
c = [1]
for i in range(N):
	c.append(fact(i))
dp = [0] * N
dp[0] = 1
for i in range(1, N):
	for j in range(i):
		dp[i] += dp[j] * c[i - j - 1]

def get_kth_cycle(n, k):
	if n == 1:
		return [1]
	ans = [-1] * n
	ans[0] = n - 1
	fin = [i for i in range(n)]
	fin[0] = n - 1
	init = [i for i in range(n)]
	init[n - 1] = 0
	used = [False] * n
	used[n - 1] = True
	for i in range(1, n - 1):
		j = 0
		cur = fact(n - i - 2)
		while True:
			while used[j] or (i < n - 1 and j == init[i]):
				j += 1
			if k > cur:
				k -= cur
				j += 1
			else:
				fin[init[i]] = fin[j]
				init[fin[j]] = init[i]
				ans[i] = j
				used[j] = True
				break
	ans[-1] = init[-1]
	return [x + 1 for x in ans]

def f(n, k):
	if n == 0:
		assert k == 1
		return []
	cl = 1
	while c[cl - 1] * dp[n - cl] < k:
		k -= c[cl - 1] * dp[n - cl]
		cl += 1
	rest = f(n - cl, (k - 1) % dp[n - cl] + 1)
	rest = [x + cl for x in rest]
	k = (k - 1) // dp[n - cl] + 1
	return get_kth_cycle(cl, k) + rest

def solve():
	(n, k) = map(int, input().split())
	if k > dp[n]:
		print(-1)
		return
	print(*f(n, k))

def main():
	t = int(input())
	while t > 0:
		t -= 1
		solve()
main()


from itertools import accumulate
from math import *
import os, sys
import threading
from io import BytesIO
from bisect import bisect_left
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
from math import factorial as fact
N = 55
c = [1]
for i in range(N):
	c.append(fact(i))
dp = [0] * N
dp[0] = 1
for i in range(1, N):
	for j in range(i):
		dp[i] += dp[j] * c[i - j - 1]

def get_kth_cycle(n, k):
	if n == 1:
		return [1]
	ans = [-1] * n
	ans[0] = n - 1
	fin = [i for i in range(n)]
	fin[0] = n - 1
	init = [i for i in range(n)]
	init[n - 1] = 0
	used = [False] * n
	used[n - 1] = True
	for i in range(1, n - 1):
		j = 0
		cur = fact(n - i - 2)
		while True:
			while used[j] or (i < n - 1 and j == init[i]):
				j += 1
			if k > cur:
				k -= cur
				j += 1
			else:
				fin[init[i]] = fin[j]
				init[fin[j]] = init[i]
				ans[i] = j
				used[j] = True
				break
	ans[-1] = init[-1]
	return [x + 1 for x in ans]

def f(n, k):
	if n == 0:
		assert k == 1
		return []
	cl = 1
	while c[cl - 1] * dp[n - cl] < k:
		k -= c[cl - 1] * dp[n - cl]
		cl += 1
	rest = f(n - cl, (k - 1) % dp[n - cl] + 1)
	rest = [x + cl for x in rest]
	k = (k - 1) // dp[n - cl] + 1
	return get_kth_cycle(cl, k) + rest

def solve():
	(n, k) = map(int, input().split())
	if k > dp[n]:
		print(-1)
		return
	print(*f(n, k))
t = int(input())
while t > 0:
	t -= 1
	solve()