Alice 拥有一座迷宫，这座迷宫可以抽象成一棵拥有 2^n 个叶节点的满二叉树，总节点数目为 (2^{n+1} - 1)，依次编号为 1 \sim (2^{n+1} - 1)。其中编号为 2^n \sim (2^{n+1} - 1) 的是叶节点，编号为 1 \sim (2^n - 1) 的是非叶节点，且非叶节点 1 \le u \le (2^n - 1) 的左儿子编号为 2u，右儿子编号为 (2u + 1)。

每个非叶节点都有一个石像守卫，初始时，所有石像守卫均在沉睡。唤醒 u 点的石像守卫需要 w_u 的魔力值。

每个叶节点都有一个符文，v 点的符文记作 $qv。**保证 q{2^n}, q{2^n+1},\cdots, q{2^{n+1}-1} 构成 1 \sim 2^n$ 的排列**。

探险者初始时持有空序列 Q，从节点 1 出发，按照如下规则行动：

• 到达叶节点 v 时，将 v 点的符文 q_v 添加到序列 Q 的末尾，然后返回父节点。
• 到达非叶节点 u 时：
  • 若该点的石像守卫已被唤醒，则只能先前往左儿子，（从左儿子返回后）再前往右儿子，（从右儿子返回后）最后返回父节点。
  • 若该点的石像守卫在沉睡，可以在以下二者中任选其一：
    • 先前往左儿子，再前往右儿子，最后返回父节点。
    • 先前往右儿子，再前往左儿子，最后返回父节点。

返回节点 1 时，探险结束。可以证明，探险者一定访问每个叶节点各一次，故此时 Q 的长度为 2^n。

探险者 Bob 准备进入迷宫，他希望探险结束时的 Q 的字典序越小越好，与之相对，Alice 希望 Q 的字典序越大越好。

在 Bob 出发之前，Alice 可以选择一些魔力值花费之和不超过 K 的石像守卫，并唤醒它们。Bob 出发时，他能够知道 Alice 唤醒了哪些神像。若双方都采取最优策略，求序列 Q 的最终取值。

对于两个长度为 2^n 的序列 Q_1,Q_2，称 Q_1 字典序小于 Q_2 当且仅当以下条件成立：

• \exist i \in [1, 2^n] 满足以下两个条件：
  • $\forall 1 \le j < i，Q{1,j} = Q{2,j}$；
  • $Q{1,i} < Q{2,i}$。

本题有多组测试数据。输入的第一行包含一个正整数 T，表示测试数据组数。

接下来依次 T 组测试数据。对于每组测试数据：

• 第一行两个整数 n,K 表示迷宫规模和 Alice 可用于唤醒石像守卫的魔力值上限。
• 第二行 (2^n - 1) 个整数 $w_1,w2,\cdots,w{2^n-1}$ 表示唤醒各个石像守卫耗费的魔力值。
• 第三行 2^n 个整数 $q{2^n}, q{2^n+1},\cdots, q_{2^{n+1}-1}$ 表示各个叶节点上的符文。

对于每组数据，输出一行 2^n 个整数 $Q_1,Q2,\cdots,Q{2^n}，表示双方都采取最优策略的情况下，序列 Q$ 的最终取值。

【样例 1 解释】

• 第一组数据中，Alice 无法唤醒石像守卫，Bob 可以选择先访问叶节点 3，再访问叶节点 2，得 Q = {1, 2}。
• 第二组数据中，Alice 可以唤醒节点 1 的石像守卫，Bob 只能先访问叶节点 2，再访问叶节点 3，得 Q = {2, 1}。
• 第三组数据中，Alice 的最优策略是唤醒节点 5, 6 的石像守卫。

设 \sum 2^n 表示单个测试点钟所有测试数据的 2^n 的和。对于所有测试数据，保证

• 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} 构成 1\sim 2^n$ 的排列。

特殊性质 A：\forall 2^n \le v \le (2^{n+1}-1)，q_v = (2^{n+1}-v)。

特殊性质 B：\forall 1 \le u \le (2^n-1)，w_u = 1。

联合省选