尋寶（Rockhounding）是一種在自然環境中搜尋珍貴岩石與寶石的愛好。身為國家級的尋寶專家，你決心要找到最珍貴的寶石！

你發現了一塊土地，其橫截面可以建模為一個二維歐幾里得平面，地面位於直線 $y = 0$。這條線下方的一切皆為堅硬的岩石，上方則為空氣。在岩石中埋藏著 $N$ 顆稀有寶石，每一顆都位於一個（可能不唯一）座標 $(x, y)$，其中 $y < 0$。

有些寶石已經被其他尋寶者追蹤到，他們透過公佈寶石位置來宣稱發現（同時將寶石留在原處）。這仍然留下了一些寶石等待你去發現！

為了實際找到寶石，你計畫使用示波器來偵測每顆寶石發出的波形。每顆寶石都有一個獨特的頻率，可以從遠處測量；然而，這款特定的示波器有一個特性，即每次使用時，它只會記錄距離最近的寶石所發出的頻率（使用歐幾里得距離）。若距離相同，它會隨機挑選其中一顆最近寶石的頻率。

圖 G.1：範例輸入 1 的示意圖。地下的寶石圖示代表已發現的寶石，地表的點代表你的示波器讀數。

你剛在地球表面的不同唯一位置 $(x_j, 0)$ 使用了示波器 $N$ 次。你記錄了這些位置以及示波器在該位置偵測到的頻率 $f_j$。有趣的是，你注意到每顆寶石的頻率在你的記錄中都恰好出現了一次。

在尚未被其他尋寶者發現的寶石中，你想要找到最珍貴的那一顆。當然，寶石埋得越深，就越珍貴！

寶石的「合理配置」（plausible configuration）是指將每顆未發現的寶石放置在二維歐幾里得平面上，並滿足以下條件： 每顆寶石都在地下（$y < 0$）； 對於每個位於 $(x_j, 0)$ 的頻率 $f_j$ 示波器讀數，沒有任何寶石在歐幾里得距離上比頻率為 $f_j$ 的寶石更靠近 $(x_j, 0)$。

你希望針對每一顆尚未發現的寶石，計算在所有可能的寶石合理配置中，該寶石可能的最深（最負的）$y$ 座標。

輸入格式

第一行包含兩個以空格分隔的整數 $N$ ($2 \le N \le 10^5$) 和 $K$ ($1 \le K \le N - 1$)：分別為埋藏的寶石總數（以及示波器讀數總數）和已被其他尋寶者發現的寶石數量。

接下來的 $K$ 行，每行包含三個以空格分隔的整數 $x_i$ ($|x_i| \le 10^6$)、$y_i$ ($-10^6 \le y_i < 0$) 和 $f_i$ ($1 \le f_i \le N$)，描述一顆已發現寶石的位置與頻率。可能會有兩顆或多顆寶石位於相同位置。保證 $f_i$ 的值皆為唯一。

最後的 $N$ 行，每行包含兩個以空格分隔的整數 $x_j$ ($|x_j| \le 10^6$) 和 $f_j$ ($1 \le f_j \le N$)，描述一個示波器讀數。保證 $x_j$ 的值皆為唯一，且按遞增順序排列，並且每顆寶石（已發現與未發現）都恰好對應一個示波器讀數。同時保證至少存在一種合理的寶石配置。

輸出格式

對於每一顆未發現的寶石，輸出一行，包含一個整數與一個負實數：該寶石的頻率 $f_\ell$ 以及在所有合理配置中，該寶石可能的最深（最負的）$y$ 座標 $y_\ell$。可以證明，對於每一顆未發現的寶石，這個最深 $y$ 座標皆存在且為負的有限值。

你可以按任意順序輸出這些行。如果你的答案中為未發現寶石所設定的深度值與裁判解答的相對誤差或絕對誤差不超過 $10^{-5}$，則你的答案將被接受。

範例

範例輸入 1

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

範例輸出 1

2 -7.615773
3 -3.162278
5 -5.830952

範例輸入 2

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

範例輸出 2

3 -3.605551