Một trong những yếu tố quan trọng giúp VNG vươn lên trong top 5 doanh nghiệp có môi trường làm việc tốt nhất Việt Nam năm 2023 chính là tinh thần đoàn kết mạnh mẽ giữa các nhân viên. Chính nhờ tinh thần này mà mọi công việc nhóm trong công ty đều được hoàn thành không chỉ nhanh chóng mà còn đạt chất lượng vượt trội. Đặc biệt, đối với các nhân viên mới, nhất là các lập trình viên trẻ, VNG không ngừng tổ chức những khóa huấn luyện về tinh thần đồng đội và kỹ năng làm việc nhóm. Hãy cùng khám phá một trò chơi rèn luyện đầy thú vị mà VNG đã tổ chức dưới đây.

Ban đầu, tất cả mọi nhân viên tham gia trò chơi đều được chia vào các nhóm. Có ~2^k~ nhóm, nhóm thứ ~i~ có ~a_i~ nhân viên. Trò chơi cũng có một quản trò sẽ ra các hiệu lệnh. Sau mỗi hiệu lệnh, số lượng nhóm và số lượng thành viên trong các nhóm sẽ thay đổi. Trò chơi sẽ kết thúc khi người quản trò đọc xong tất cả các câu lệnh.

Giả sử ở thời điểm hiện tại đang có ~2^x~ nhóm, nhóm thứ ~i~ đang có ~a'_i~ nhân viên. Hiệu lệnh mà người quản trò sẽ ra thuộc một trong hai loại sau:

• Hiệu lệnh 0: Đây là hiệu lệnh gộp nhóm, sẽ có 2 nhóm được gộp lại thành một nhóm lớn hơn. Quá trình gộp nhóm diễn ra như sau:

  • Nhóm ~2^{x-1}~ sẽ gộp vào nhóm ~1~, tạo ra nhóm có ~a_1 + a_{2^{x-1}}~ nhân viên;

  • Nhóm ~2^{x-1} + 1~ sẽ gộp vào nhóm ~2~, tạo ra nhóm có ~a_2 + a_{2^{x-1} + 1}~ nhân viên;

  • ...

  • Nhóm ~2^x~ sẽ gộp vào nhóm ~2^{x-1} - 1~, tạo ra nhóm có ~a_{2^{x-1} - 1} + a_{2^x}~ nhân viên.

  • Số lượng nhóm giảm xuống còn ~2^{x-1}~, và các nhóm được đánh số từ ~1~ đến ~2^{x-1}~ theo thứ tự vừa mô tả.

  • Người quản trò đảm bảo rằng tại thời điểm này đang có ít nhất 2 đội.

• Hiệu lệnh 1: Đây là hiệu lệnh tách nhóm, mỗi nhóm sẽ được tách thành 2 nhóm nhỏ. Số lượng nhóm sẽ tăng lên thành ~2^{x+1}~, các nhóm sẽ được đánh số từ ~1~ đến ~2^{x+1}~. Trong quá trình này, mỗi nhân viên ở nhóm ~i~ có thể chọn ở lại nhóm thứ ~i~, hoặc di chuyển đến nhóm thứ ~i + 2^x~. Sau thao tác này, một số nhóm có thể không chứa thành viên nào cả.

Giả sử khi trò chơi kết thúc, số nhóm mà mọi người được chia vào sẽ là ~2^h~, nhóm thứ ~i~ sẽ có ~b_i~ nhân viên. Nhiệm vụ của tất cả mọi người tham gia trò chơi là khi trò chơi kết thúc, dãy ~b~ được tạo thành cần phải là dãy có thứ tự từ điển nhỏ nhất có thể tạo được trong tất cả các dãy có thể được tạo ra.

Đây là một trò chơi mang tính đồng đội rất cao, do đó mọi nhân viên đều có thể thảo luận chiến thuật trước khi chơi. Là một người cũng tham gia trò chơi này, hãy giúp tất cả mọi người đưa ra một chiến thuật chơi tối ưu và tìm ra dãy ~b~ có thứ tự từ điển nhỏ nhất có thể.

Một dãy ~a~ được gọi là có thứ tự từ điển nhỏ hơn dãy ~b~ khi và chỉ khi một trong hai điều sau đúng:

• ~a~ là tiền tố của ~b~, nhưng ~a \ne b~;

• Tại vị trí đầu tiên mà ~a~ và ~b~ khác nhau, phần tử của dãy ~a~ nhỏ hơn phần tử của dãy ~b~.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \leq t \leq 50~). Mô tả của mỗi test case như sau.

Dòng đầu chứa một số nguyên ~k~ (~0 \le k \le 16~). Ban đầu sẽ có ~2^k~ nhóm.

Dòng thứ hai chứa ~2^k~ số nguyên không âm ~a_1, a_2, \ldots, a_{2^k}~ ~(0 \le a_i \le 10^5)~ – số lượng nhân viên của mỗi nhóm.

Dòng cuối cùng nhập một dãy nhị phân ~s~ – danh sách hiệu lệnh của người quản trò. Kí tự ~s_i~ sẽ thể hiện hiệu lệnh thứ ~i~.

Dữ liệu đảm bảo rằng:

• tổng ~|s|~ trong tất cả các testcase không quá ~10^5~, và

• tổng số lượng vị trí sau cùng (độ dài dãy ~b~), trong tất cả các test không quá ~2^{16}~.

Output

Với mỗi testcase, in ra một dãy gồm ~2^h~ phần tử ~b_1, b_2, \ldots, b_{2^h}~ là dánh sách số lượng nhân viên của từng nhóm có thứ tự từ điểm nhỏ nhất khi trò chơi kết thúc.

Scoring

Sample Input 1

2
1
4 2
10
1
4 2
01

Sample Output 1

4 2 
0 6

Notes

Trong testcase đầu tiên, ban đầu có ~2^k = 2^1 = 2~ nhóm, với số lượng thí sinh thể hiện bởi dãy ~a = [4, 2]~. Dãy hiệu lệnh của người quản trò thể hiện bởi xâu ~s = \texttt{10}~.

1. Hiệu lệnh đầu tiên là hiệu lệnh ~1~, tức hiệu lệnh tách nhóm. Từ dãy ~a = [{\color{red}4}, {\color{blue}2}]~, người chơi có thể tạo thành các nhóm với dãy ~a = [{\color{red}1}, {\color{blue}1}, {\color{red}3}, {\color{blue}1}]~.

2. Hiệu lệnh thứ hai là hiệu lệnh ~0~, tưc hiệu lệnh gộp nhóm. Từ dãy ~a = [{\color{red}1}, {\color{blue}1}, {\color{red}3}, {\color{blue}1}]~, người chơi có thể tạo thành các nhóm với dãy ~a = [{\color{red}4}, {\color{blue}2}]~.