#arc106c. [arc106_c]Solutions

[arc106_c]Solutions

问题陈述

当满足 L1R2L_1 \leq R_2 并且 L2R1L_2 \leq R_1 时,两个区间 \[L_1:R_1\]\[L_2:R_2\] 被称为 相交

考虑以下问题 PP

输入:NN 个区间 \[L_1: R_1\], \cdots, \[L_N:R_N\] L1,L2,,LN,R1,R2,,RNL_1, L_2, \cdots, L_N, R_1, R_2, \cdots, R_N 两两不同。 输出:最多可以选择的区间数量,使得它们之间没有相交。

高桥实现了一个程序,其工作原理如下:

按照 RiR_i 的递增顺序对给定的区间进行排序,结果为 $\[L_{p_1}:R_{p_1}\], \[L_{p_2}:R_{p_2}\], \cdots , \[L_{p_N}:R_{p_N}\]$。 对于每个 i=1,2,,Ni = 1, 2, \cdots , N,执行以下操作: 如果 \[L_{p_i}:R_{p_i}\] 没有与迄今选择的任何区间相交,则选择它。 打印选择的区间数量。

另一方面,青木实现了一个程序,其工作原理如下:

按照 LiL_i 的递增顺序对给定的区间进行排序,结果为 $\[L_{p_1}:R_{p_1}\], \[L_{p_2}:R_{p_2}\], \cdots , \[L_{p_N}:R_{p_N}\]$。 对于每个 i=1,2,,Ni = 1, 2, \cdots , N,执行以下操作: 如果 \[L_{p_i}:R_{p_i}\] 没有与迄今选择的任何区间相交,则选择它。 打印选择的区间数量。

给定整数 NNMM。构造一个问题 PP 的输入,包含 NN 个区间,满足以下条件:

(高桥程序输出的值)(青木程序输出的值)=M(高桥程序输出的值)-(青木程序输出的值)= M

约束条件

  • 输入中的所有值都是整数。
  • 1N2×1051 \leq N \leq 2 \times 10^5
  • \-NMN\-N \leq M \leq N

输入

输入数据以以下格式从标准输入给出:

NN MM

输出

如果没有满足条件的 NN 个区间集合,则打印 -1

否则,按照以下方式打印 NN 行:

L1L_1 R1R_1 L2L_2 R2R_2 \vdots LNL_N RNR_N

这里,\[L_1:R_1\], \cdots, \[L_N:R_N\] 必须满足以下条件:

  • 1Li<Ri1091 \leq L_i < R_i \leq 10^9
  • LiLjL_i \neq L_j (iji \neq j)
  • RiRjR_i \neq R_j (iji \neq j)
  • LiRjL_i \neq R_j
  • L1,,LN,R1,,RNL_1, \cdots , L_N , R_1, \cdots , R_N 都是整数

如果有多个答案,任何一个都可接受。

请确保在输出末尾打印一个换行符。


示例输入 1

5 1

示例输出 1

1 10
8 12
13 20
11 14
2 4

我们将这五个区间分别称为 Segment 11, Segment 22, cdots\\cdots, Segment 55

高桥的程序的工作过程如下:

按照 Segment 55, Segment 11, Segment 22, Segment 44, Segment 33 的顺序重新排列区间。 选择 Segment 55。 跳过 Segment 11(因为它与 Segment 55 相交)。 选择 Segment 22。 跳过 Segment 44(因为它与 Segment 22 相交)。 选择 Segment 33

因此,高桥的程序将打印 33

青木的程序的工作过程如下:

按照 Segment 11, Segment 55, Segment 22, Segment 44, Segment 33 的顺序重新排列区间。 选择 Segment 11。 跳过 Segment 55(因为它与 Segment 11 相交)。 跳过 Segment 22(因为它与 Segment 11 相交)。 选择 Segment 44。 跳过 Segment 33(因为它与 Segment 44 相交)。

因此,青木的程序将打印 22

在这里,我们有 32=13 - 2 = 1(与 MM 相等),因此这五个区间满足条件。


示例输入 2

10 -10

示例输出 2

-1