Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
正の整数 N 及び K が与えられます。
以下の条件をみたすように、3N 個の整数 K,K+1,...,K+3N-1 を 3 整数からなる N 個の組 (a_1,b_1,c_1),...,(a_N,b_N,c_N) に分割することが可能かを判定して下さい。K,K+1,...,K+3N-1 のうちどの整数も、N 個の組のうちちょうど 1 個に現れなければなりません。
- 1 以上 N 以下のすべての整数 i に対して a_i + b_i \leqq c_i が成り立つ。
また、可能な場合はそのような分割を 1 つ構成してください。
制約
- 1 ≦ N ≦ 10^5
- 1 ≦ K ≦ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
条件をみたすように N 個の三つ組に分割することができない場合 -1
を出力せよ。可能な場合は N 個の三つ組を以下の形式で出力せよ。
a_1 b_1 c_1 : a_N b_N c_N
入力例 1
1 1
出力例 1
1 2 3
入力例 2
3 3
出力例 2
-1
Score : 700 points
Problem Statement
Given are positive integers N and K.
Determine if the 3N integers K, K+1, ..., K+3N-1 can be partitioned into N triples (a_1,b_1,c_1), ..., (a_N,b_N,c_N) so that the condition below is satisfied. Any of the integers K, K+1, ..., K+3N-1 must appear in exactly one of those triples.
- For every integer i from 1 to N, a_i + b_i \leq c_i holds.
If the answer is yes, construct one such partition.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq K \leq 10^9
Input
Input is given from Standard Input in the following format:
N K
Output
If it is impossible to partition the integers satisfying the condition, print -1
. If it is possible, print N triples in the following format:
a_1 b_1 c_1 : a_N b_N c_N
Sample Input 1
1 1
Sample Output 1
1 2 3
Sample Input 2
3 3
Sample Output 2
-1