C - Solutions Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

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 の入力であって、

\begin{equation} (高橋君のプログラムが出力する値) - (青木君のプログラムが出力する値) = M \end{equation}

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

制約

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

入力

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

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 追記)

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

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


入力例 1

5 1

出力例 1

1 10
8 12
13 20
11 14
2 4

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 つの区間は条件を満たします。


入力例 2

10 -10

出力例 2

-1

Score : 500 points

Problem Statement

Two segments [L_1:R_1] and [L_2:R_2] are said to intersect when L_1 \leq R_2 and L_2 \leq R_1 holds.

Consider the following problem P:

Input: N segments [L_1: R_1], \cdots, [L_N:R_N]
       L_1, L_2, \cdots, L_N, R_1, R_2, \cdots, R_N are pairwise distinct.
Output: the maximum number of segments that can be chosen so that no two of them intersect.

Takahashi has implemented a program that works as follows:

Sort the given segments in the increasing order of R_i and let the result be [L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots , [L_{p_N}:R_{p_N}].
For each i = 1, 2, \cdots , N, do the following:
  Choose [L_{p_i}:R_{p_i}] if it intersects with none of the segments chosen so far.
Print the number of chosen segments.

Aoki, on the other hand, has implemented a program that works as follows:

Sort the given segments in the increasing order of L_i and let the result be [L_{p_1}:R_{p_1}], [L_{p_2}:R_{p_2}], \cdots , [L_{p_N}:R_{p_N}].
For each i = 1, 2, \cdots , N, do the following:
  Choose [L_{p_i}:R_{p_i}] if it intersects with none of the segments chosen so far.
Print the number of chosen segments.

Given are integers N and M. Construct an input for the problem P, consisting of N segments, such that the following holds:

\begin{equation} (\text{The value printed by Takahashi's program}) - (\text{The value printed by Aoki's program}) = M \end{equation}

Constraints

  • All values in input are integers.
  • 1 \leq N \leq 2 \times 10^5
  • -N \leq M \leq N

Input

Input is given from Standard Input in the following format:

N M

Output

If there is no set of N segments that satisfies the condition, print -1.

Otherwise, print N lines as follows:

L_1 R_1
L_2 R_2
  \vdots
L_N R_N

Here, [L_1:R_1], \cdots, [L_N:R_N] must satisfy the following:

  • 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 are integers (21:46 added)

If there are multiple answers, any of them will be accepted.

Be sure to print a newline at the end of the output.


Sample Input 1

5 1

Sample Output 1

1 10
8 12
13 20
11 14
2 4

Let us call the five segments Segment 1, Segment 2, \cdots, Segment 5.

Takahashi's program will work as follows:

Rearrange the segments into the order Segment 5, Segment 1, Segment 2, Segment 4, Segment 3.
Choose Segment 5.
Skip Segment 1 (because it intersects with Segment 5).
Choose Segment 2.
Skip Segment 4 (because it intersects with Segment 2).
Choose Segment 3.

Thus, Takahashi's program will print 3.

Aoki's program will work as follows:

Rearrange the segments into the order Segment 1, Segment 5, Segment 2, Segment 4, Segment 3.
Choose Segment 1.
Skip Segment 5 (because it intersects with Segment 1).
Skip Segment 2 (because it intersects with Segment 1).
Choose Segment 4.
Skip Segment 3 (because it intersects with Segment 4).

Thus, Aoki's program will print 2.

Here, we have 3 - 2 = 1 \left(= M \right), and thus these five segments satisfy the condition.


Sample Input 2

10 -10

Sample Output 2

-1