Fişierul intrare/ieşire:	stars.in, stars.out	Sursă	AGM 2019, runda finala
Autor	Tamio-Vesa Nakajima	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.5 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Stars

You are the flower who I have chosen,
and with care I have chosen you,
If it were for me to choose again,
Again I would choose you.
The sky, it does have many stars,
But I want only one of them,
There are flowers in the whole world,
But I want only my flower.
(Nicolae Guta)

Nicolae vede N stele in fata sa. Acestea se pot modela ca niste puncte 2-dimensionale, fiecare avand coordonate intregi intre -10⁸ si 10⁸. Acum trebuie sa decida pozitia si marimea florii gravitationale centrale ale universului. Aceasta se poate modela ca un cerc 2-dimensional, cu centrul intr-un punct intreg. Vrea sa faca acest lucru astfel incat exact jumatate din stele sunt in interiorul florii gravitationale centrale ale universului, si exact jumatate din stele sunt in exteriorul acestuia.
Mai formal, se dau N puncte (x_i, y_i). Sa se gaseasca trei numere intregi x, y, r astfel incat -10⁸ ≤ x, y ≤ 10⁸, 0 ≤ r ≤ 10¹⁸ si pentru exact N / 2 puncte (x', y') dintre cele N satisfac (x - x')² + (y - y')² ≤ r, si exact N / 2 puncte (x', y') dintre cele N satisfac (x - x')² + (y - y')² > r. Observati ca r nu este raza cercului, ci patratul razei.

Date de intrare

Fişierul de intrare stars.in va contine, pe primul rand, numarul T de teste.
Fiecare test incepe cu un numar natural N, cu semnificatia din enunt. Urmeaza N linii, iar cea e a i-a linie contine valorile x_i, y_i.

Date de ieşire

În fişierul de ieşire stars.out sa se afiseze, pe cate T randuri, raspunsurile pentru fiecare test. Pentru fiecare test sa se afiseze trei valori x, y, r care satisfac conditiile din enunt.

Restricţii

• 1 ≤ T ≤ 100.000
• 1 ≤ N ≤ 100.000
• Suma valorilor lui N nu depasesc 100.000 intr-un fisier.
• N e par.
• -10⁸ ≤ x_i, y_i ≤ 10⁸.

Exemplu

Cum se trimit solutii?