AT_k4pc_f タイトル未定(Untitled)

[problemUrl]: https://atcoder.jp/contests/k4pc/tasks/k4pc_f カガミズさんは息子のキュウリ君にあげるクリスマスプレゼントを考えています． カガミズさんにはある懸念があります．キュウリ君は競技プログラミングが大好きなので，コンテストでよくある変な問題文に触発されて，プレゼントに配列が欲しいとかグラフが欲しいとか言われてしまうおそれがあるのです． 急に言われて慌てるよりは，早い内に聞いておくほうがよいと考えたカガミズさんは，クリスマスプレゼントにほしいものをキュウリ君に尋ねました．すると，キュウリ君は次のように答えました． 「今から言う問題に対する自然な問題設定がほしい！」

> $ N $ $ X_1 $ $ K_1 $ $ D_1 $ : $ X_N $ $ K_N $ $ D_N $

どのように点を加えても問題の条件を満たせない場合は `impossible` と出力せよ． 条件を満たすように点を加えることは可能だが，加える点の個数がどのようにしても $ 10^5 $ を超えてしまう場合は `too many` と出力せよ． $ 10^5 $ 個以下の点を加えることで条件を満たすことができる場合は，その具体例を以下のフォーマットで出力せよ． > $ M $ $ A_1 $ … $ A_M $ ただし，$ M $ は加える点の個数で $ A_j $ は加える点の座標である．ここで，$ M $ の値は $ 10^5 $ 以下であり，各 $ A_j $ の値は $ 32 $ ビット符号付き整数の表現できる範囲内に収まっていなければならない． **また, 出力に際して余計な空行や空白があってはならない. (16 : 36 追記)**

### 課題 $ 1 $ 次元空間上に $ N $ 個の点があり，$ i $ 番目の点 $ P_i $ の座標は $ X_i $ である． いま，新たにいくつかの点を加えることで $ N $ 個の点がある条件を満たすようにしたい．その条件は $ N $ 要素の整数列 $ K $, $ D $ によって次のように表される． - 条件: $ i\ =\ 1,\ ...,\ N $ に対し，点 $ P_i $ から $ K_i $ 番目に近い点までの距離が $ D_i $ である．ただし，$ 2 $ 点間の距離はその座標の差の絶対値とする． 距離を考える点の対象は新たに加えた点だけではなく，元からある $ N $ 個の点も考慮する．つまり，ある点から $ 1 $ 番近い点は自分自身と考えられる． いくつかの点を加えることで上の条件を満たすことができるかどうかを判定せよ．もし可能な場合は，加える点の個数を $ 10^5 $ 個以下にできるかどうかも判定し，それも可能な場合は加える点の座標の具体例を $ 1 $ つ求めよ． ただし，$ X_i $, $ D_i $ および加える点の座標はすべて整数であるとする．また，加える点の座標は $ 32 $ ビット符号付き整数の表現できる範囲内に収まっていなければならない． 元からある $ N $ 個の点や加える点については，同じ座標に複数の点があってもよいことに注意せよ． ### 制約 すべての入力データは以下の制約を満たす． - $ 1\ ≦\ N\ ≦\ 10^3 $． - $ -10^9\ ≦\ X_i\ ≦\ 10^9 $． - $ 1\ ≦\ K_i\ ≦\ 10^9 $． - $ 0\ ≦\ D_i\ ≦\ 10^9 $． また，この問題には部分点が設定されており，$ 2 $ 点分の入力データは追加で以下の制約を満たす． - $ N\ ≦\ 10 $． - $ K_i\ =\ 2 $． ### Sample Explanation 1 加える点の個数は $ 10^5 $ 以下でありさえすれば最小である必要はないので，以下のような出力もこの問題では許可される． ``` 2 -1 1 ``` ### Sample Explanation 3 ある点に最も近い点は自分自身であり，その距離は $ 0 $ であることに注意せよ． ### Sample Explanation 4 たとえば座標 $ 2 $ に $ 114,513 $ 個の点を置けば条件を満たすことはできる．ただし，$ 10^5 $ 個以内では条件を満たすことができないため `too many` を出力する． ### Sample Explanation 5 \*\*このケースに余計な空行を追加しないよう注意せよ. (16:36 追記)\*\*