AT_abc413_e [ABC413E] Reverse 2^i

$ (1,2,3,\ldots,2^{N}) $ の順列 $ P=(P_0,P_1,\ldots,P_{2^{N}-1}) $ が与えられます。 あなたは次の操作を何回でも( $ 0 $ 回でもよい)行うことができます。 - $ 0 \leq a \times 2^{b} < (a+1) \times 2^{b} \leq 2^{N} $ を満たす非負整数 $ a,b $ を選び、 $ P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} $ を反転する。ここで、 $ P_{a \times 2^{b}},P_{a \times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} $ を反転するとは、 $ P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} $ を $ P_{(a+1) \times 2^{b}-1}, P_{(a+1) \times 2^{b}-2},\ldots,P_{a \times 2^{b}} $ に同時に置き換えることを意味する。 操作を繰り返して得られる $ P $ のうち、辞書順最小のものを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \textrm{case}_1 $ $ \textrm{case}_2 $ $ \vdots $ $ \textrm{case}_T $ $ \textrm{case}_i $ は $ i $ 番目のテストケースを表し、以下の形式で与えられる。 > $ N $ $ P_0 $ $ P_1 $ $ \ldots $ $ P_{2^N-1} $

$ T $ 行出力せよ。 $ i $ 行目 $ (1 \leq i \leq T) $ には $ i $ 番目のテストケースに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースにおいて、 $ P $ に対して操作を一回も行わないとき、 $ P=(1,2) $ となります。これは辞書順で最小の順列です。よって答えは $ (1,2) $ です。 $ 2 $ 番目のテストケースにおいて、 $ a=1,b=1 $ を選んで操作を行うと $ P=(1,3,2,4) $ となります。 $ P $ に対して何回操作を行っても $ (1,3,2,4) $ より辞書順で小さい順列を得られません。よって答えは $ (1,3,2,4) $ です。 $ 3 $ 番目のテストケースにおいて、以下の順番で操作を行うことで、 $ P=(1,4,2,3) $ が得られます。 - $ a=0,b=1 $ を選んで操作を行う。 $ P=(3,2,4,1) $ となる。 - $ a=0,b=2 $ を選んで操作を行う。 $ P=(1,4,2,3) $ となる。 $ P $ に対して何回操作を行っても $ (1,4,2,3) $ より辞書順で小さい順列を得られません。よって答えは $ (1,4,2,3) $ です。 ### Constraints - $ 1 \leq T \leq 10^{5} $ - $ 1 \leq N \leq 18 $ - $ P $ は $ (1,2,3,\ldots,2^{N}) $ の順列 - 各入力ファイルについて、すべてのテストケースの $ 2^N $ の総和は $ 3 \times 10^{5} $ 以下 - 入力はすべて整数