寻宝是自然环境中搜寻珍贵岩石和宝石的爱好。作为一名国家级的寻宝者，你决心找到尽可能珍贵的宝石！

你发现了一片土地，其横截面可以建模为二维欧几里得平面，地面位于直线 $y = 0$ 处。该直线下方的一切都是坚硬的岩石，上方的一切都是空气。岩石中埋藏着 $N$ 颗稀有宝石，每颗宝石位于一个（可能不唯一）坐标 $(x, y)$ 处，且满足 $y < 0$。

其中一些宝石已经被其他寻宝者追踪到，他们通过公布宝石的位置（同时将宝石留在原处）来宣称自己的发现。但这仍然留下了一些等待你去发现的宝石！

为了真正找到宝石，你计划使用示波器来检测每颗宝石发出的波形。每颗宝石都有一个可以从远处测量的唯一频率；然而，这种特定的示波器有一个特性：每次使用时，它只会记录距离最近的宝石所发出的频率（使用欧几里得距离）。如果距离相等，它会随机选择其中一颗最近宝石发出的频率。

图 G.1：样例输入 1 的示意图。地下的宝石图标代表已发现的宝石，地表的点表示你的示波器读数。

你刚刚在地球表面的不同唯一位置 $(x_j, 0)$ 使用了 $N$ 次示波器。你记录了这些位置以及示波器在这些位置检测到的频率 $f_j$。有趣的是，你注意到每颗宝石的频率在你的记录中都恰好出现了一次。

对于那些尚未被其他寻宝者发现的宝石，你希望找到最珍贵的那一颗。当然，宝石埋藏得越深，就越珍贵！

宝石的一种“合理配置”是指在二维欧几里得平面上放置每颗未发现的宝石，且满足以下条件：

• 每颗宝石都在地下 ($y < 0$)；
• 对于每一个位于 $(x_j, 0)$ 且频率为 $f_j$ 的示波器读数，没有任何宝石在欧几里得距离上比频率为 $f_j$ 的那颗宝石更靠近 $(x_j, 0)$。

你希望计算出，在所有可能的宝石合理配置中，每颗尚未发现的宝石可能达到的最深（即 $y$ 坐标最小）的 $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$ 坐标 $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