Problem Description

Alice owns a maze. The maze can be modeled as a perfect binary tree with $2^n$ leaf nodes, and the total number of nodes is $(2^{n+1} - 1)$. The nodes are numbered in order from $1$ to $(2^{n+1} - 1)$. Nodes numbered $2^n \sim (2^{n+1} - 1)$ are leaf nodes, and nodes numbered $1 \sim (2^n - 1)$ are non-leaf nodes. For each non-leaf node $1 \le u \le (2^n - 1)$, its left child is numbered $2u$, and its right child is numbered $(2u + 1)$.

Each non-leaf node has a stone statue guard. Initially, all stone statue guards are asleep. Waking up the stone statue guard at node $u$ costs $w_u$ mana.

Each leaf node has a rune. The rune at leaf node $v$ is denoted by $q_v$. It is guaranteed that $q_{2^n}, q_{2^n+1},\cdots, q_{2^{n+1}-1}$ form a permutation of $1 \sim 2^n$.

An explorer initially holds an empty sequence $Q$ and starts from node $1$, acting according to the following rules:

• When arriving at a leaf node $v$, append the rune $q_v$ to the end of sequence $Q$, then return to its parent node.
• When arriving at a non-leaf node $u$:
  • If the stone statue guard at this node has been awakened, the explorer must go to the left child first, then (after returning from the left child) go to the right child, then (after returning from the right child) finally return to the parent node.
  • If the stone statue guard at this node is asleep, the explorer may choose either of the following:
    • Go to the left child first, then the right child, and finally return to the parent node.
    • Go to the right child first, then the left child, and finally return to the parent node.

When the explorer returns to node $1$, the exploration ends. It can be proven that the explorer will visit each leaf node exactly once, so at this time the length of $Q$ is $2^n$.

Explorer Bob is about to enter the maze. He wants the final sequence $Q$ to be as lexicographically small as possible. In contrast, Alice wants $Q$ to be as lexicographically large as possible.

Before Bob sets off, Alice may choose some stone statue guards whose total mana cost does not exceed $K$ and wake them up. When Bob sets off, he knows exactly which statues Alice has awakened. If both sides play optimally, find the final value of sequence $Q$.

For two sequences $Q_1, Q_2$ of length $2^n$, we say $Q_1$ is lexicographically smaller than $Q_2$ if and only if the following holds:

• $\exist i \in [1, 2^n]$ such that:
  • $\forall 1 \le j < i，Q_{1,j} = Q_{2,j}$；
  • $Q_{1,i} < Q_{2,i}$。

Input Format

This problem has multiple test cases. The first line contains a positive integer $T$, indicating the number of test cases.

Then follow $T$ test cases. For each test case:

• The first line contains two integers $n, K$, representing the maze size and the upper limit of mana Alice can use to wake stone statue guards.
• The second line contains $(2^n - 1)$ integers $w_1, w_2, \cdots, w_{2^n-1}$, representing the mana cost to wake each stone statue guard.
• The third line contains $2^n$ integers $q_{2^n}, q_{2^n+1},\cdots, q_{2^{n+1}-1}$, representing the runes on each leaf node.

Output Format

For each test case, output one line containing $2^n$ integers $Q_1, Q_2, \cdots, Q_{2^n}$, representing the final value of sequence $Q$ when both sides play optimally.

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

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

Hint

[Sample 1 Explanation]

• In the first test case, Alice cannot wake any stone statue guard. Bob can choose to visit leaf node $3$ first and then leaf node $2$, obtaining $Q = \{1, 2\}$.
• In the second test case, Alice can wake the stone statue guard at node $1$. Bob can only visit leaf node $2$ first and then leaf node $3$, obtaining $Q = \{2, 1\}$.
• In the third test case, Alice’s optimal strategy is to wake the stone statue guards at nodes $5, 6$.

[Sample 2]

See the attached maze2.in/ans.

This test case satisfies special property A.

[Sample 3]

See the attached maze3.in/ans.

This test case satisfies special property B.

[Sample 4]

See the attached maze4.in/ans.

[Sample 5]

See the attached maze5.in/ans.

[Subtasks]

Let $\sum 2^n$ denote the sum of $2^n$ over all test cases within a single test point. For all test cases, it is guaranteed that:

• $1\le T \le 100$；
• $1\le n \le 16$，$1 \le \sum 2^n \le 10^5$；
• $0\le K \le 10^{12}$。
• $\forall 1 \le u \le (2^n-1)$，$0 \le w_u \le 10^{12}$；
• $q_{2^n},q_{2^n+1},\cdots,q_{2^{n+1}-1}$ form a permutation of $1\sim 2^n$.

Special property A: $\forall 2^n \le v \le (2^{n+1}-1)$，$q_v = (2^{n+1}-v)$。

Special property B: $\forall 1 \le u \le (2^n-1)$，$w_u = 1$。

Translated by ChatGPT 5