Trong cờ vua, quân Hậu có thể đi, bắt quân theo hàng ngang, hàng dọc và đường chéo với số ô tuỳ ý.

Một cách đặt quân Hậu trên bàn cờ được biểu diễn bởi một bộ \(n\) số từ \(1\) tới \(n\), số thứ \(i\) là vị trí (cột) của quân Hậu ở hàng \(i\).

Ví dụ với \(n = 8\), bộ \((3, 5, 2, 8, 1, 7, 4, 6)\), tương ứng với cách xếp như sau:

Lưu ý rằng cột \(a\:b\:c\:d\:e\:f\:g\:h\) lần lượt tương ứng với cột \(1\:2\:3\:4\:5\:6\:7\:8\).

Với \(n = 8\) có \(92\) cách đặt quân Hậu (tính cả các đối xứng*) mà không có cặp Hậu nào tấn công nhau, \(3\) cách xếp đầu tiên theo thứ tự từ điển thỏa mãn điều kiện này lần lượt là:

\((1, 5, 8, 6, 3, 7, 2, 4)\)

\((1, 6, 8, 3, 7, 4, 2, 5)\)

\((1, 7, 4, 6, 8, 2, 5, 3)\)

Cho trước \(n\) và \(k\), bạn hãy tìm cách xếp thứ \(k\) (theo thứ tự từ điển) của các cách xếp \(n\) quân Hậu trong bàn cờ \(n\)x\(n\) mà không có cặp Hậu nào tấn công nhau.

Ghi chú: "Tính cả các đối xứng" nghĩa là hai cách xếp trở nên giống nhau bằng cách xoay, lấy đối xứng bàn cờ vẫn được tính là hai cách xếp phân biệt.

Đầu vào

Dòng đầu tiên chứa hai số tự nhiên \(n\) và \(q\) \((3 \le n \le 16, 1 \le q \le 100)\) lần lượt là cỡ của bàn cờ - số quân hậu cần đặt vào bàn cờ và số lần truy vấn.

\(q\) dòng tiếp theo mỗi dòng chứa một số nguyên dương, thứ tự của cách xếp.

Đầu ra

\(q\) dòng, mỗi dòng chứa một dãy số \(n\) phần tử là trả lời của một truy vấn.

Ghi chú: Mỗi truy vấn luôn đảm bảo có một cách xếp thỏa mãn.

Subtask

\(20\%\) số test có \(n \le 14\).

\(20\%\) số test có \(n = 15\).

\(20\%\) số test có \(n = 16, t = 10\).

\(40\%\) số test còn lại có \(n = 16, t = 100\).

Ví dụ

Đầu vào:

8 4
1 
69
42 
92

Đầu ra:

1 5 8 6 3 7 2 4
6 3 1 8 4 2 7 5
4 7 5 2 6 1 3 8
8 4 1 3 6 2 7 5