Поиск драгоценных камней — это хобби, заключающееся в поиске ценных горных пород и драгоценных камней в естественной среде. Будучи профессионалом в этом деле, вы полны решимости найти самый ценный камень!

Вы нашли участок земли, поперечное сечение которого можно представить как 2D евклидову плоскость, где поверхность земли находится на линии $y = 0$. Всё, что ниже этой линии — твердая порода, а всё, что выше — воздух. Внутри породы скрыто $N$ редких драгоценных камней, каждый из которых находится в (возможно, не уникальной) точке $(x, y)$ с $y < 0$.

Некоторые из этих камней уже были обнаружены другими искателями, которые заявили о своих находках, опубликовав их местоположение (оставив сами камни на месте). Это всё ещё оставляет несколько камней, которые вам предстоит найти!

Чтобы действительно найти драгоценные камни, вы планируете использовать осциллограф для обнаружения волн, излучаемых каждым камнем. Каждый камень имеет уникальную частоту, которую можно измерить на расстоянии; однако у этого конкретного осциллографа есть особенность: каждый раз при использовании он записывает только частоту, излучаемую ближайшим камнем, используя евклидово расстояние. В случае равенства расстояний он произвольно выбирает частоту, излучаемую одним из ближайших камней.

Рисунок G.1: Иллюстрация примера 1. Значки камней под землей представляют ранее обнаруженные драгоценные камни, а точки на поверхности указывают на показания вашего осциллографа.

Вы только что использовали осциллограф $N$ раз в различных уникальных точках $(x_j, 0)$ на поверхности Земли. Вы записали эти местоположения вместе с частотой $f_j$, обнаруженной осциллографом в этой точке. Интересно, что вы заметили, что частота каждого драгоценного камня встречается в ваших записях ровно один раз.

Из камней, которые еще не были обнаружены другими искателями, вы хотели бы найти самый ценный. И, конечно, чем глубже камень, тем он ценнее!

Правдоподобная конфигурация драгоценных камней — это такое размещение каждого необнаруженного камня на 2D евклидовой плоскости, которое удовлетворяет следующим условиям: каждый драгоценный камень находится под землей ($y < 0$); для каждого показания осциллографа с частотой $f_j$ в точке $(x_j, 0)$ ни один драгоценный камень не находится ближе к $(x_j, 0)$ по евклидову расстоянию, чем камень с частотой $f_j$.

Вы хотите вычислить для каждого еще не обнаруженного драгоценного камня максимально возможную глубину (наиболее отрицательную $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$ уникальны, что они перечислены в порядке возрастания и что каждый драгоценный камень (обнаруженный и необнаруженный) имеет ровно одно показание осциллографа. Также гарантируется, что существует по крайней мере одна правдоподобная конфигурация драгоценных камней.

Выходные данные

Для каждого из $N - K$ необнаруженных драгоценных камней выведите строку с целым числом и отрицательным вещественным числом: частоту $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

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