L 有一棵二叉树，每个叶子节点 $u$ 都有一个标签 $a_u$。

如果我们按顺序（先左子节点，后右子节点）遍历整棵树，可以将所有的叶子节点排列成一个序列。

现在，L 将执行以下操作恰好 $m$ 次： 1. 选择一个非叶子节点 $a$。 2. 交换节点 $a$ 的左子节点和右子节点。

在这些操作之后，L 希望你确定他能得到的字典序最小的序列。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($0 \le m \le \frac{n-1}{2}, n \le 1000, 2 \nmid n$)。

接下来 $n$ 行，第 $i$ 行以一个整数 $type \in \{1, 2\}$ 开头。

• 如果 $type = 1$，则接下来有两个整数 $l_i, r_i$ ($i < l_i, r_i$)，分别表示 $i$ 的左子节点和右子节点。
• 如果 $type = 2$，则接下来有一个整数 $a_i$ ($1 \le a_i \le 10^9$)，表示该叶子节点的标签。

输出格式

输出一行，包含 $\frac{n+1}{2}$ 个整数，表示最优序列。

样例

输入 1

3 0
1 2 3
2 1
2 2

输出 1

1 2

输入 2

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

输出 2

2 4 3 1

输入 3

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

输出 3

1 3 4 2