Rockhounding là sở thích tìm kiếm các loại đá và đá quý có giá trị trong môi trường tự nhiên. Là một người chơi rockhounding cấp quốc gia, bạn quyết tâm tìm ra viên đá quý giá trị nhất có thể!

Bạn đã tìm thấy một khu vực đất mà mặt cắt ngang của nó có thể được mô hình hóa bằng mặt phẳng Euclid 2D với mặt đất nằm trên đường thẳng $y = 0$. Mọi thứ bên dưới đường thẳng này là đá cứng, và mọi thứ bên trên là không khí. Được chôn vùi trong đá là $N$ viên đá quý hiếm, mỗi viên nằm tại một vị trí $(x, y)$ (có thể không duy nhất) với $y < 0$.

Một số viên đá quý này đã được các người chơi rockhounding khác tìm thấy và họ đã công bố vị trí của chúng (trong khi vẫn để nguyên các viên đá tại chỗ). Điều đó vẫn còn lại một số viên đá quý để bạn tìm kiếm!

Để thực sự tìm thấy các viên đá quý, bạn dự định sử dụng một máy hiện sóng (oscilloscope) để phát hiện các dạng sóng phát ra từ mỗi viên đá. Mỗi viên đá có một tần số duy nhất có thể đo được từ xa; tuy nhiên, chiếc máy hiện sóng cụ thể này có một đặc điểm là mỗi khi sử dụng, nó chỉ ghi lại tần số phát ra từ viên đá gần nhất, sử dụng khoảng cách Euclid. Trong trường hợp có sự ngang bằng, nó sẽ chọn ngẫu nhiên một tần số phát ra từ một trong những viên đá gần nhất.

Hình G.1: Minh họa cho Ví dụ 1. Các biểu tượng đá quý dưới lòng đất đại diện cho những viên đá đã được phát hiện trước đó, và các điểm trên bề mặt biểu thị các kết quả đọc từ máy hiện sóng của bạn.

Bạn vừa sử dụng máy hiện sóng $N$ lần tại các vị trí duy nhất khác nhau $(x_j, 0)$ trên bề mặt Trái Đất. Bạn đã ghi lại các vị trí này cùng với tần số $f_j$ được máy hiện sóng phát hiện tại vị trí đó. Thú vị thay, bạn nhận thấy rằng tần số của mọi viên đá quý đều xuất hiện chính xác một lần trong các bản ghi của bạn.

Trong số những viên đá chưa được những người chơi khác phát hiện, bạn muốn tìm viên có giá trị nhất. Và tất nhiên, viên đá càng sâu thì càng có giá trị!

Một cấu hình hợp lý của các viên đá quý là cách đặt mỗi viên đá chưa được phát hiện lên mặt phẳng Euclid 2D thỏa mãn các điều kiện sau: mọi viên đá quý đều nằm dưới lòng đất ($y < 0$); đối với mỗi kết quả đọc tần số $f_j$ tại vị trí $(x_j, 0)$, không có viên đá nào gần $(x_j, 0)$ hơn theo khoảng cách Euclid so với viên đá có tần số $f_j$.

Bạn muốn tính toán, cho mỗi viên đá chưa được phát hiện, tọa độ $y$ sâu nhất có thể (âm nhất) của viên đá đó trong tất cả các cấu hình hợp lý của các viên đá quý.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách $N$ ($2 \le N \le 10^5$) và $K$ ($1 \le K \le N - 1$): số lượng đá quý được chôn (và các kết quả đọc từ máy hiện sóng) và số lượng đá quý đã được những người chơi khác phát hiện.

Mỗi dòng trong $K$ dòng tiếp theo chứa ba số nguyên cách nhau bởi dấu cách $x_i$ ($|x_i| \le 10^6$), $y_i$ ($-10^6 \le y_i < 0$), và $f_i$ ($1 \le f_i \le N$), mô tả vị trí và tần số của một viên đá quý đã được phát hiện. Có khả năng hai hoặc nhiều viên đá quý nằm cùng một vị trí. Đảm bảo rằng các giá trị $f_i$ là duy nhất.

Cuối cùng, mỗi dòng trong $N$ dòng cuối cùng chứa hai số nguyên cách nhau bởi dấu cách $x_j$ ($|x_j| \le 10^6$) và $f_j$ ($1 \le f_j \le N$), mô tả một kết quả đọc từ máy hiện sóng. Đảm bảo rằng các giá trị $x_j$ là duy nhất, chúng được liệt kê theo thứ tự tăng dần, và mọi viên đá quý (đã phát hiện và chưa phát hiện) đều có chính xác một kết quả đọc từ máy hiện sóng. Cũng đảm bảo rằng có ít nhất một cấu hình hợp lý của các viên đá quý.

Dữ liệu ra

Đối với mỗi viên đá trong số $N - K$ viên đá chưa được phát hiện, hãy in ra một dòng gồm một số nguyên và một số thực âm: tần số $f_\ell$ của viên đá và tọa độ $y$ sâu nhất (âm nhất) có thể $y_\ell$ của viên đá đó trong tất cả các cấu hình hợp lý của các viên đá quý. Có thể chứng minh rằng tọa độ $y$ sâu nhất có thể này tồn tại cho mọi viên đá chưa được phát hiện và là một số âm hữu hạn.

Bạn có thể in các dòng này theo bất kỳ thứ tự nào. Câu trả lời của bạn sẽ được chấp nhận nếu mỗi giá trị độ sâu mà bạn gán cho một viên đá chưa được phát hiện sai lệch so với đáp án của giám khảo theo sai số tương đối hoặc tuyệt đối tối đa là $10^{-5}$.

Ví dụ

Ví dụ 1

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

Ví dụ 1

2 -7.615773
3 -3.162278
5 -5.830952

Ví dụ 2

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

Ví dụ 2

3 -3.605551