Нехай ~p(n,k)~ позначає ~k~-ту перестановку (у лексикографічному порядку) ~1 \dots n~.

Наприклад, ~p(4,1)=[1,2,3,4]~ і ~p(4,2)=[1,2,4,3]~.

Ваше завдання опрацювати два типи тестів:

• Дано ~n~ і ~k~, знайдіть ~p(n,k)~
• Дано ~n~ і ~p(n,k)~, знайдіть ~k~

Обмеження

• ~1 \le t \le 1000~
• ~1 \le n \le 20~
• ~1 \le k \le n!~

Формат вхідних даних

У першому рядку є ціле число ~t~: кількість тестів.

Кожен тест є або «~1 n k~», або «~2 n p(n,k)~».

Формат вихідних даних

До кожного тесту роздрукуйте відповідь згідно прикладу.

Приклад вхідних даних

6
1 4 1
1 4 2
2 4 1 2 3 4
2 4 1 2 4 3
1 5 42
2 5 2 4 5 3 1

Приклад вихідних даних

1 2 3 4
1 2 4 3
1
2
2 4 5 3 1
42