ロックハンディング（岩石採集）は、自然環境の中で価値のある岩石や宝石を探す趣味です。あなた自身も全国レベルのロックハンダーとして、可能な限り価値のある宝石を見つけようと決意しています！

あなたは、断面が2次元ユークリッド平面でモデル化できる土地を見つけました。地面は直線 $y = 0$ であり、この線より下は固い岩石、上は空気です。岩石の中には $N$ 個の希少な宝石が埋まっており、それぞれが（重複する可能性がある）$y < 0$ の位置 $(x, y)$ に存在しています。

これらの宝石の一部はすでに他のロックハンダーによって追跡されており、彼らはその位置を公表することで発見を主張しています（石自体はその場に残されています）。しかし、まだあなたが見つけるべき宝石が残っています！

実際に宝石を見つけるために、あなたはオシロスコープを使って各宝石から放出される波形を検出する計画を立てました。各宝石には遠くから測定できる固有の周波数がありますが、この特定のオシロスコープには癖があり、使用するたびにユークリッド距離で最も近い宝石から放出される周波数のみを記録します。同距離の場合は、最も近い宝石のいずれかから放出される周波数を任意に選択します。

図 G.1: サンプル入力 1 の図。地下の宝石アイコンはすでに発見された宝石を表し、地表の点はオシロスコープの測定値を示しています。

あなたは地球の表面上の様々なユニークな位置 $(x_j, 0)$ でオシロスコープを $N$ 回使用しました。あなたはこれらの位置と、その場所でオシロスコープによって検出された周波数 $f_j$ を記録しました。興味深いことに、すべての宝石の周波数があなたの記録にちょうど一度ずつ現れていることに気づきました。

他のロックハンダーによってまだ発見されていない宝石のうち、最も価値のあるものを見つけたいと考えています。もちろん、宝石は深いほど価値があります！

宝石の「妥当な配置（plausible configuration）」とは、各未発見の宝石を2次元ユークリッド平面上の以下の条件を満たす位置に配置することです。

• すべての宝石が地下にあること（$y < 0$）。
• 周波数 $f_j$ のすべてのオシロスコープの測定値（位置 $(x_j, 0)$）に対して、周波数 $f_j$ を持つ宝石よりも、位置 $(x_j, 0)$ にユークリッド距離で近い宝石は存在しないこと。

あなたは、すべての宝石の妥当な配置の中で、各未発見の宝石について、その宝石の最も深い（最も負の値に近い）$y$ 座標を計算したいと考えています。

入力

最初の行には、2つのスペース区切りの整数 $N$ ($2 \le N \le 10^5$) と $K$ ($1 \le K \le N - 1$) が含まれます。これらはそれぞれ、埋まっている宝石の総数（およびオシロスコープの測定回数）と、すでに他のロックハンダーによって発見された宝石の数です。

続く $K$ 行の各行には、3つのスペース区切りの整数 $x_i$ ($|x_i| \le 10^6$)、$y_i$ ($-10^6 \le y_i < 0$)、$f_i$ ($1 \le f_i \le N$) が含まれており、すでに発見された宝石の位置と周波数を表しています。2つ以上の宝石が同じ位置にある可能性があります。$f_i$ の値は一意であることが保証されています。

最後に、続く $N$ 行の各行には、2つのスペース区切りの整数 $x_j$ ($|x_j| \le 10^6$) と $f_j$ ($1 \le f_j \le N$) が含まれており、オシロスコープの測定値を表しています。$x_j$ の値は一意であり、昇順に並んでいること、およびすべての宝石（発見済みおよび未発見）がそれぞれ1つのオシロスコープ測定値に対応していることが保証されています。また、少なくとも1つの妥当な宝石の配置が存在することが保証されています。

出力

$N - K$ 個の未発見の宝石それぞれについて、宝石の周波数 $f_\ell$ と、宝石のすべての妥当な配置における最も深い（最も負の値に近い）$y$ 座標 $y_\ell$ を、整数と負の実数として1行に出力してください。この最も深い $y$ 座標はすべての未発見の宝石に対して存在し、負かつ有限であることが証明できます。

これらの行はどのような順序で出力しても構いません。未発見の宝石に割り当てた深さの値が、ジャッジの解と相対誤差または絶対誤差で $10^{-5}$ 以内であれば正解となります。

入出力例

入出力例 1

5 2
7 -3 4
2 -3 1
1 1
3 3
9 4
12 5
14 2

2 -7.615773
3 -3.162278
5 -5.830952

入出力例 2

3 2
3 -3 1
3 -3 2
0 1
2 2
5 3

3 -3.605551