Lexicographically Extreme Maze Exploration

Alice has a maze represented by a full binary tree with 2ⁿ leaves (node indices 2ⁿ to 2ⁿ⁺¹-1) and a total of 2ⁿ⁺¹-1 nodes. The internal nodes (numbered 1 to 2ⁿ-1) each host a statue guard who is initially sleeping. To wake the guard at an internal node u (forcing a fixed traversal order) Alice must spend w_u units of magical power. Each leaf v (nodes 2ⁿ to 2ⁿ⁺¹-1) contains a rune q_v. It is guaranteed that the runes on the leaves form a permutation of {1, 2, …, 2ⁿ}.

An explorer starts at node 1 with an empty sequence Q and travels as follows:

• If the explorer reaches a leaf v, the rune q_v is appended to Q and the explorer returns to the parent.
• If the explorer reaches an internal node u:
• If the guard is awake (forced), the explorer must visit the left child first, then the right child, and finally return to the parent.
• If the guard is sleeping, the explorer can choose either of the two orders: left child then right child, or right child then left child, with the corresponding visit and backtracking.

After returning to node 1, the exploration ends. Since each leaf is visited exactly once, the sequence Q has exactly 2ⁿ integers. Bob, who will be exploring the maze, wants the final sequence Q to be lexicographically as small as possible. In contrast, Alice wants Q to be as lexicographically large as possible. To influence the outcome, before Bob starts his journey, Alice may choose some internal nodes to wake up at a total cost not exceeding K. Bob is informed which statues are awake. Once in the maze, at every internal node whose guard remains sleeping, Bob will choose the order that minimizes the lexicographical order of the eventual Q (that is, he picks between the two possible orders the one yielding the lexicographically smaller sequence).

For two sequences Q₁ and Q₂ (each of length 2ⁿ), we say that Q₁ is lexicographically smaller than Q₂ if there exists some index i (1 ≤ i ≤ 2ⁿ) such that:

• Q_{1, j} = Q_{2, j} for all 1 ≤ j < i, and
• Q_{1, i} < Q_{2, i}.

If both Alice and Bob play optimally, what will the final sequence Q be?

Note on traversal orders:

• If an internal node's guard is awake, the order is left then right.
• If the guard is sleeping, Bob chooses between the two orders and will pick the one that gives the lexicographically smallest sequence for Q.

Input Format: The input begins with two integers n and K. The next line contains 2ⁿ-1 integers representing w₁, w₂, …, w_2ⁿ-1</em> (the cost to wake each internal node). The third line contains 2ⁿ integers which form a permutation of {1,2,…,2ⁿ} representing q_2ⁿ, q_2ⁿ+1, …, q_2ⁿ⁺¹-1 (the runes in the leaves).

Output Format: Output the final sequence Q as 2ⁿ space‐separated integers.

inputFormat

Input begins with two integers n and K.

The second line contains 2ⁿ-1 integers: w₁, w₂, ..., w_2ⁿ-1.

The third line contains 2ⁿ integers forming a permutation of {1, 2, ..., 2ⁿ}, representing the runes stored in the leaf nodes with indices from 2ⁿ to 2ⁿ⁺¹-1.

outputFormat

Output one line with 2ⁿ space‐separated integers: the final sequence Q.

sample

1 0
100
2 1

1 2

</p>