Sau khi giúp cơ quan đầu não của ta giải quyết vấn đề về truyền tin, Phong được điều động lên tiền tuyến để hỗ trợ các đơn vị tại đây.

Trong một ngôi nhà nhỏ giữa lòng thủ đô, bầu không khí như bị dồn nén, căng thẳng mà cũng chan chứa niềm hy vọng. Sau bao tháng năm chịu cảnh lầm than, đói khát và áp bức, giờ đây thời cơ đã đến gần. Tại đây, trong gian phòng tối chỉ le lói ánh đèn dầu, các đồng chí lãnh đạo địa phương đang bận rộn. Trên bàn, tấm bản đồ thành phố trải rộng, những dấu bút đỏ đánh dấu trụ sở các cơ quan cai trị của địch, những điểm tập trung đông quần chúng, những tuyến đường di chuyển. Giấy tờ, tài liệu ngổn ngang, nhưng từng nét chữ, từng ký hiệu đều toát lên sự cẩn trọng và quyết đoán.

Phong lặng lẽ đứng bên, quan sát. Anh cảm nhận được sự gấp gáp trong từng hơi thở. Người thì khẩn trương chép lại hiệu lệnh, người khác chỉnh sửa khẩu hiệu, còn ngoài sân, các tổ tự vệ thay nhau luyện tập động tác, chuẩn bị cờ, băng rôn và loa tay. Không khí rộn ràng ấy khiến anh tưởng như nghe được cả nhịp tim chung của dân tộc, đang dồn dập, rạo rực, chờ giây phút bùng nổ.

Một đồng chí phụ trách tuyên truyền mang vào chồng truyền đơn vừa in xong. Tờ giấy còn thơm mùi mực, chữ in rõ ràng: "Việt Nam hoàn toàn độc lập! Toàn dân vùng lên giành chính quyền!". Những khẩu hiệu ấy sẽ được bí mật phát đi khắp nơi, để vài hôm nữa đồng loạt xuất hiện trong tay hàng vạn người dân. Phong cầm một tờ truyền đơn, ngón tay run run. Anh thấy rõ trong từng câu chữ là sức mạnh của niềm tin, của khát vọng cháy bỏng không gì ngăn nổi.

Ở góc phòng, một thanh niên trẻ đang tỉ mỉ khâu lại lá cờ đỏ sao vàng. Mỗi mũi kim, mỗi đường chỉ được thực hiện chậm rãi, trang nghiêm, như gửi gắm cả tấm lòng vào biểu tượng thiêng liêng của Tổ quốc. Ánh đèn dầu hắt lên khuôn mặt anh ta, sáng lên sự quyết liệt và xúc động. Phong nhìn lá cờ ấy, trong lòng chợt dâng trào hình ảnh hàng vạn lá cờ tung bay, như biển đỏ phủ trùm khắp phố phường.

Đêm hôm ấy, vầng trăng sáng rực bên ngoài khung cửa số, tiếng cho sủa vang vọng, khuấy động không gian im ắng của thành phố. Trong nhà, tiếng thì thầm bàn bạc của các lãnh đạo, tiếng sửa soạn của các đồng chí không ngớt, làm Phong cảm thấy vừa hồi hộp, vừa thiêng liêng, như thể mình đang sống lại từng khoảnh khắc trước một cột mốc lịch sử vĩ đại.

Nhiệm vụ của Phong và nhóm của mình là giải mã những mệnh lệnh mới được chuyển đến. Mệnh lệnh được mã hóa bằng một khóa có độ dài ~n = 2^k~ (với ~k~ là số nguyên), được đánh số từ ~0~, gồm các số nguyên không âm. Khóa này cũng đã được mã hóa. để giải mã, nhóm của Phong có thế thực hiện thao tác sau không giới hạn số lần (có thể không thực hiện):

• Chọn hai số nguyên ~p, d~ sao cho ~0\le d\le k~ và ~0\le p\times2^d\le (p + 1)\times 2^d\le 2^k~.

• Đảo ngược thứ tự của các phần tử của khóa trong đoạn ~[p\times 2^d; (p + 1) \times 2^d)~.

Khóa để giải mã mệnh lệnh là khóa có thứ tự từ điển~^\dagger~ bé nhất có thể thu được sau khi thực hiện các thao tác trên một cách tối ưu.

Do Phong đã giải mã được một số khóa nên đã bắt tay vào giải mã mệnh lệnh. Vì thế, bạn hãy giúp Phong giải mã những khóa còn lại để nhanh chóng biết được mệnh lệnh của cơ quan đầu não là gì nhé.

~\dagger~ Dãy ~x_1, x_2, \dots, x_m~ được coi là nhỏ hơn theo thứ tự từ điển so với dãy ~y_1, y_2, \dots, y_m~ nếu:

• Tồn tại một số ~r < m~ sao cho ~x_1 = y_1, x_2 = y_2, \dots , x_r = y_r~ và ~x_{r + 1} < y_{r + 1}~.

Input

Dòng đầu tiên chứa số nguyên ~\mathcal{T}~ cho biết số lượng testcase cần xử lý.

Mỗi testcase gồm ~2~ dòng có định dạng:

• Dòng đầu tiên của mỗi testcase chứa một số nguyên ~k~ cho biết độ dài của một khóa được mã hoá là ~2^k~.
• Dòng thứ hai chứa ~2^k~ số nguyên ~a_0, a_1, a_2, \dots, a_{2^k - 1}~ mô tả khóa được mã hoá.

Output

Với mỗi testcase, in ra một dãy số ~b~ gồm ~2^k~ phần tử trên một dòng riêng biệt, mô tả khóa để giải mã mệnh lệnh.

Scoring

Sample Input 1

4
1
0 1
2
2 1 3 2
2
0 3 3 3
1
1 0

Sample Output 1

0 1 
1 2 2 3 
0 3 3 3 
0 1

Notes

Ở testcase thứ hai của test ví dụ, ta thực hiện hai thao tác sau để biến đổi dãy ~[2, 1, 3, 2]~ thành ~[1, 2, 2, 3]~:

• Chọn ~p = 0~ và ~d = 1~, khi đó đoạn được đảo ngược là ~[0; 2)~, dãy ~a~ được biến đổi thành ~[1, 2, 3, 2]~.

• Chọn ~p = 1~ và ~d = 1~, khi đó đoạn được đảo ngược là ~[2; 4)~, dãy ~a~ được biến đổi thành ~[1, 2, 2, 3]~.

Không khó để chứng minh đây là dãy có thứ tự từ điển bé nhất có thể có được từ quá trình biến đổi trên.