题目描述

$2$ つの区間 $[L_1:R_1],\ [L_2:R_2]$ について, $L_1\ \leq\ R_2$ かつ $L_2\ \leq\ R_1$ であるとき, この $2$ つの区間が交わると定義します。

以下の問題 $P$ を考えます。

入力: $N$ 個の区間 $[L_1:\ R_1],\ \cdots,\ [L_N:R_N]$ $ L_1,\ L_2,\ \cdots,\ L_N,\ R_1,\ R_2,\ \cdots,\ R_N $は全て異なる。 出力: どの $2$ つの区間も交わらないように選べる区間の最大数

高橋君は、以下のように動作するプログラムを実装しました。

$R_i$ の値が昇順となるように, 入力された区間を $ [L_{p_1}:R_{p_1}],\ [L_{p_2}:R_{p_2}],\ \cdots\ ,\ [L_{p_N}:R_{p_N}] $ と並び替える。 $i\ =\ 1,\ 2,\ \cdots\ ,\ N$ について、以下を行う。 これまでに選んだどの区間とも交わらないならば、 $[L_{p_i}:R_{p_i}]$ を選ぶ。 選んだ区間の数を出力する。

一方、青木君は、以下のように動作するプログラムを実装しました。

$L_i$ の値が昇順となるように, 入力された区間を $ [L_{p_1}:R_{p_1}],\ [L_{p_2}:R_{p_2}],\ \cdots\ ,\ [L_{p_N}:R_{p_N}] $ と並び替える。 $i\ =\ 1,\ 2,\ \cdots\ ,\ N$ について、以下を行う。 これまでに選んだどの区間とも交わらないならば、 $[L_{p_i}:R_{p_i}]$ を選ぶ。 選んだ区間の数を出力する。

整数 $N,\ M$が与えられます。 $N$ 個の区間から成る問題 $P$ の入力であって、

$$ (高橋君のプログラムが出力する値)\ -\ (青木君のプログラムが出力する値)\ =\ M $$

となるものを構築してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$

输出格式

条件を満たす $N$ 個の区間が存在しない場合は -1 と出力せよ。

存在する場合は、 以下のように $N$ 行出力せよ。

$L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$

ただし, $[L_1:R_1],\ \cdots,\ [L_N:R_N]$は以下の条件を満たさなければならない。

• $1\ \leq\ L_i\ <\ R_i\ \leq\ 10^9$
• $L_i\ \neq\ L_j$ ($i\ \neq\ j$)
• $R_i\ \neq\ R_j$ ($i\ \neq\ j$)
• $L_i\ \neq\ R_j$
• $L_1,\ \cdots\ ,\ L_N\ ,\ R_1,\ \cdots\ ,\ R_N$ は整数 (21:46 追記)

答えが複数存在する場合は、どれを出力しても構わない。

出力の最後には必ず改行を行うこと。

题目大意

对于两个区间 $[L_1:R_1]$，$[L_2:R_2]$，如果 $L_1 \leq R_2$ 且 $L_2 \leq R_1$，则定义这两个区间相交。

考虑以下问题 $P$。

有 $N$ 个区间 $[L_1: R_1]$，⋯， $[L_N:R_N]$，这 $2N$ 个整数互不相同，选择最多的区间，使它们互不相交。

$A$ 的算法：对所有区间按 $R_i$ 升序排列后，依次考虑 $i=1,2,…,N$，如果排名为 $i$ 的区间和目前已经选择的区间都不相交，则选择第 $i$ 个区间。

$B$ 的算法：对所有区间按 $L_i$ 升序排列后，依次考虑 $i=1,2,⋯,N$，如果排名为 $i$ 的区间和目前已经选择的区间都不相交，则选择第 $i$ 个区间。

给定整数 $N$ 和 $M$。请你构造出 $N$ 个区间，使得 $A$ 的答案 $-$ $B$ 的答案 $=M$。

无解输出 $-1$。

5 1

1 10
8 12
13 20
11 14
2 4

10 -10

-1

提示

制約

• 入力は全て整数
• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $-N\ \leq\ M\ \leq\ N$

Sample Explanation 1

$5$ つの区間を順に区間 $1$ 、区間 $2$ 、$\cdots$ 、区間 $5$ と名付けます。 高橋君のプログラムは以下のように動作します。 > 区間を区間 $5$ 、区間 $1$ 、区間 $2$ 、区間 $4$ 、区間 $3$ と並び替えます。 区間 $5$ を選びます。 区間 $1$ は選びません。(区間 $5$ と交わっている為) 区間 $2$ を選びます。 区間 $4$ は選びません。 (区間 $2$ と交わっている為) 区間 $3$ を選びます。 以上より、高橋君のプログラムが出力する値は $3$ となります。 青木君のプログラムは以下のように動作します。 > 区間を区間 $1$ 、区間 $5$ 、区間 $2$ 、区間 $4$ 、区間 $3$ と並び替えます。 区間 $1$ を選びます。 区間 $5$ は選びません。(区間 $1$ と交わっている為) 区間 $2$ は選びません。 (区間 $1$ と交わっている為) 区間 $4$ を選びます。 区間 $3$ は選びません。 (区間 $4$ と交わっている為) 以上より、青木君のプログラムが出力する値は $2$ となります。 このとき、 $3\ -\ 2\ =\ 1\ \left(=\ M\ \right)$ であり、この $5$ つの区間は条件を満たします。