Alice owns a maze, which can be abstracted as a full binary tree with $2^n$ leaf nodes. The total number of nodes is $(2^{n+1} - 1)$, numbered $1 \sim (2^{n+1} - 1)$. Nodes $2^n \sim (2^{n+1} - 1)$ are leaf nodes, and nodes $1 \sim (2^n - 1)$ are non-leaf nodes. For any non-leaf node $1 \le u \le (2^n - 1)$, its left child is $2u$ and its right child is $(2u + 1)$.

Each non-leaf node has a stone guardian. Initially, all stone guardians are asleep. Waking up the stone guardian at node $u$ requires $w_u$ magic points.

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

An explorer starts with an empty sequence $Q$ and begins at node $1$, moving according to the following rules: When reaching a leaf node $v$, add the rune $q_v$ to the end of sequence $Q$, then return to the parent node. When reaching a non-leaf node $u$: If the stone guardian at this node has been awakened, the explorer must first visit the left child, then (after returning from the left child) visit the right child, and finally return to the parent node. If the stone guardian at this node is asleep, the explorer can choose one of the following: Visit the left child first, then the right child, and finally return to the parent node. Visit the right child first, then the left child, and finally return to the parent node.

The exploration ends upon returning to node $1$. It can be proven that the explorer visits each leaf node exactly once, so the length of $Q$ at this time is $2^n$.

Bob, the explorer, is preparing to enter the maze. He wants the lexicographical order of $Q$ at the end of the exploration to be as small as possible. Conversely, Alice wants the lexicographical order of $Q$ to be as large as possible.

Before Bob starts, Alice can choose some stone guardians to awaken, such that the sum of their magic costs does not exceed $K$. When Bob starts, he knows which guardians Alice has awakened. Assuming both parties play optimally, find the final sequence $Q$.

For two sequences $Q_1, Q_2$ of length $2^n$, $Q_1$ is lexicographically smaller than $Q_2$ if and only if: $\exists 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

The input contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. For each test case: The first line contains two integers $n$ and $K$, representing the maze scale and the maximum magic points Alice can spend to awaken stone guardians. The second line contains $(2^n - 1)$ integers $w_1, w_2, \dots, w_{2^n-1}$, representing the magic cost to awaken each stone guardian. * The third line contains $2^n$ integers $q_{2^n}, q_{2^n+1}, \dots, q_{2^{n+1}-1}$, representing the runes at each leaf node.

Output

For each test case, output a single line containing $2^n$ integers $Q_1, Q_2, \dots, Q_{2^n}$, representing the final sequence $Q$ when both parties play optimally.

Examples

Input 1

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

Output 1

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

Note 1

• In the first test case, Alice cannot awaken any stone guardians. Bob can choose to visit leaf node 3 first, then leaf node 2, resulting in $Q = \{1, 2\}$.
• In the second test case, Alice can awaken the stone guardian at node 1. Bob is forced to visit leaf node 2 first, then leaf node 3, resulting in $Q = \{2, 1\}$.
• In the third test case, Alice's optimal strategy is to awaken the stone guardians at nodes 5 and 6.

Subtasks

Let $\sum 2^n$ denote the sum of $2^n$ over all test cases in a single test file. 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}, \dots, 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$.