题目描述

桌上从左到右摆着 $n$ 张双面卡片。第 $i$ 张卡片正面写着整数 $a_i$，反面写着整数 $b_i$。

你需要让每张卡片选择一面朝上，得到序列 $x_1,x_2,\ldots,x_n$，其中 $x_i\in\{a_i,b_i\}$。

要求相邻两项满足

如果存在合法方案，请输出所有合法序列中字典序最小的一个；如果不存在，输出 -1。

两个等长整数序列的字典序比较方式与字符串类似：在第一个不同的位置，数值较小的序列字典序更小。

输入格式

第一行两个整数 $n,D$。

接下来 $n$ 行，第 $i$ 行两个整数 $a_i,b_i$。

输出格式

若无解，输出一行 -1。

否则输出一行 $n$ 个整数，表示字典序最小的合法序列。

样例

4 3
1 4
5 2
3 8
6 5

1 2 3 5

数据范围

• $1\le n\le 2\times 10^5$；
• $0\le D\le 2\times10^9$；
• $-10^9\le a_i,b_i\le 10^9$。