Poszukiwanie minerałów to hobby polegające na poszukiwaniu cennych skał i kamieni szlachetnych w środowisku naturalnym. Jako poszukiwacz na poziomie krajowym, jesteś zdeterminowany, aby znaleźć jak najcenniejszy kamień!

Znalazłeś obszar terenu, którego przekrój można modelować za pomocą dwuwymiarowej płaszczyzny euklidesowej, gdzie grunt znajduje się na linii $y = 0$. Wszystko poniżej tej linii to lita skała, a wszystko powyżej to powietrze. W skale ukrytych jest $N$ rzadkich kamieni szlachetnych, każdy w (potencjalnie nieunikalnej) lokalizacji $(x, y)$ przy $y < 0$.

Niektóre z tych kamieni zostały już namierzone przez innych poszukiwaczy, którzy zgłosili swoje odkrycia, publikując ich lokalizacje (pozostawiając same kamienie na miejscu). To wciąż pozostawia kilka kamieni do znalezienia dla Ciebie!

Aby faktycznie znaleźć kamienie, planujesz użyć oscyloskopu do wykrywania fal emitowanych przez każdy z nich. Każdy kamień ma unikalną częstotliwość, którą można zmierzyć z odległości; jednak ten konkretny oscyloskop ma taką osobliwość, że za każdym razem, gdy jest używany, rejestruje tylko częstotliwość emitowaną przez najbliższy kamień, używając odległości euklidesowej. W przypadku remisu, oscyloskop arbitralnie wybiera częstotliwość emitowaną przez jeden z najbliższych kamieni.

Rysunek G.1: Ilustracja przykładowego wejścia 1. Ikony kamieni pod ziemią reprezentują wcześniej odkryte kamienie, a punkty na powierzchni wskazują odczyty z oscyloskopu.

Właśnie użyłeś oscyloskopu $N$ razy w różnych unikalnych lokalizacjach $(x_j, 0)$ na powierzchni Ziemi. Zarejestrowałeś te lokalizacje wraz z częstotliwością $f_j$ wykrytą przez oscyloskop w danej lokalizacji. Co ciekawe, zauważyłeś, że częstotliwość każdego kamienia pojawia się w Twoich zapisach dokładnie raz.

Spośród kamieni, które nie zostały jeszcze odkryte przez innych poszukiwaczy, chciałbyś znaleźć ten najcenniejszy. A oczywiście, im głębiej znajduje się kamień, tym jest cenniejszy!

Plausybilna konfiguracja kamieni to takie rozmieszczenie każdego nieodkrytego kamienia na płaszczyźnie euklidesowej 2D, które spełnia następujące warunki: każdy kamień znajduje się pod ziemią ($y < 0$); dla każdego odczytu oscyloskopu o częstotliwości $f_j$ w lokalizacji $(x_j, 0)$, żaden kamień nie znajduje się bliżej punktu $(x_j, 0)$ w sensie odległości euklidesowej niż kamień o częstotliwości $f_j$.

Chcesz obliczyć, dla każdego jeszcze nieodkrytego kamienia, najgłębszą możliwą (najbardziej ujemną) współrzędną $y$ tego kamienia spośród wszystkich plausybilnych konfiguracji kamieni.

Wejście

Pierwsza linia zawiera dwie liczby całkowite oddzielone spacją $N$ ($2 \le N \le 10^5$) oraz $K$ ($1 \le K \le N - 1$): odpowiednio liczbę ukrytych kamieni (oraz odczytów oscyloskopu) i liczbę tych kamieni, które zostały już odkryte przez innych poszukiwaczy.

Każda z kolejnych $K$ linii zawiera trzy liczby całkowite oddzielone spacją $x_i$ ($|x_i| \le 10^6$), $y_i$ ($-10^6 \le y_i < 0$) oraz $f_i$ ($1 \le f_i \le N$), opisujące lokalizację i częstotliwość kamienia, który został już odkryty. Możliwe jest, że dwa lub więcej kamieni zajmuje tę samą lokalizację. Gwarantuje się, że wartości $f_i$ są unikalne.

Na koniec, każda z ostatnich $N$ linii zawiera dwie liczby całkowite oddzielone spacją $x_j$ ($|x_j| \le 10^6$) oraz $f_j$ ($1 \le f_j \le N$), opisujące odczyt oscyloskopu. Gwarantuje się, że wartości $x_j$ są unikalne, że są podane w kolejności rosnącej oraz że każdy kamień (odkryty i nieodkryty) ma dokładnie jeden odczyt oscyloskopu. Gwarantuje się również, że istnieje co najmniej jedna plausybilna konfiguracja kamieni.

Wyjście

Dla każdego z $N - K$ nieodkrytych kamieni wypisz linię zawierającą liczbę całkowitą i ujemną liczbę rzeczywistą: częstotliwość $f_\ell$ kamienia oraz najgłębszą (najbardziej ujemną) możliwą współrzędną $y_\ell$ tego kamienia spośród wszystkich plausybilnych konfiguracji kamieni. Można udowodnić, że ta najgłębsza możliwa współrzędna $y$ istnieje dla każdego nieodkrytego kamienia i jest ujemna oraz skończona.

Możesz wypisać te linie w dowolnej kolejności. Twoja odpowiedź zostanie zaakceptowana, jeśli każda wartość głębokości przypisana do nieodkrytego kamienia różni się od rozwiązania sędziego o błąd względny lub bezwzględny co najwyżej $10^{-5}$.

Przykład 1

Wejście 1

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

Wyjście 1

2 -7.615773
3 -3.162278
5 -5.830952

Przykład 2

Wejście 2

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

Wyjście 2

3 -3.605551