Gọi \(p(n,k)\) là hoán vị thứ \(k\) (theo thứ tự từ điển) của \(1 \dots n\). Ví dụ, \(p(4,1)=[1,2,3,4]\) và \(p(4,2)=[1,2,4,3]\).

Nhiệm vụ của bạn là xử lý hai loại truy vấn:

• Cho \(n\) và \(k\), hãy tìm \(p(n,k)\)

• Cho \(n\) và \(p(n,k)\), hãy tìm \(k\)

Input

Dòng đầu tiên chứa một số nguyên \(t\): số lượng truy vấn.

Mỗi truy vấn có dạng "1 \(n\) \(k\)" hoặc "2 \(n\) \(p(n,k)\)".

Output

Với mỗi truy vấn, in ra đáp án theo ví dụ.

Constraints

• \(1 \le t \le 1000\)

• \(1 \le n \le 20\)

• \(1 \le k \le n!\)

Example

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