Cerința

O tablă este formată din \(10^6\) rânduri și \(10^6\) coloane, numerotate de la \(1\) la \(10^6\). Pe tablă se află \(n\) ture. Tura \(i\) se află inițial în celula \((x_i,y_i)\).

Într-o mutare, o tură se poate deplasa în orice altă celulă de pe același rând sau aceeași coloană cu celula de pornire. Nu pot fi deplasate mai multe ture în aceeași mutare și în orice moment, mai multe ture se pot afla într-o singură celulă.

Turele vor să se întâlnească într-o celulă \((X,Y)\). Tu trebuie să alegi celula \((X,Y)\) în mod optim, astfel încât numărul total de mutări pe care trebuie să le facă turele pentru a se întâlni să fie minim.

Date de intrare

Pe prima linie se va afla valoarea \(n\) (numărul de ture de pe tablă). A \(i\)-a linie dintre următoarele \(n\) va conține valorile \(x_i\) și \(y_i\) (linia și rândul celulei în care se află inițial tura \(i\)).

Date de ieșire

Pe prima linie se vor afișa valorile \(X\), \(Y\), \(m\) (linia și coloana celulei optime de întâlnire și numărul total de mutări). Dacă există mai multe celule optime, oricare dintre ele se va considera corectă. Dacă numărul minim de mutări este corect, dar celula de întâlnire nu conduce la acest număr minim de mutări, se va obține 50% din punctaj.

Restricții și precizări

• Pentru toate testele, se respectă \(1 \le n \le 10^5\) și \(1 \le x_i,y_i \le 10^6\) pentru orice \(1 \le i \le n\)
• Subtask 1, 10p: \(1 \le n \le 100\) și \(1 \le x_i,y_i \le 100\) pentru orice \(1 \le i \le n\)
• Subtask 2, 40p: \(x_i=1\) pentru orice \(1 \le i \le n\)
• Subtask 3, 50p: restricțiile inițiale

Exemplu 1:

Intrare

4
1 1
1 3
3 3
4 4

Ieșire

1 3 4

Explicație

Alegem \((1,3)\) ca celulă de întâlnire. Prima tură va face o mutare \((1,1) \xrightarrow{} (1,3)\). A doua tură nu se va muta. A treia tură va face o mutare \((3,3) \xrightarrow{} (1,3)\). A patra tură va face două mutări \((4,4) \xrightarrow{} (1,4) \xrightarrow{} (1,3)\). În total se fac \(4\) mutări, iar acesta este numărul minim de mutări.

Exemplu 2:

Intrare

3
1 1
1 1
1 1

Ieșire

1 1 0

Explicație

Dacă alegem celula \((1,1)\) ca celulă de întâlnire, nu va trebui să facem nicio mutare.

Exemplu 3:

Intrare

4
1 1
1 3
3 3
4 4

Ieșire

1 3 4

Explicație

Numărul minim de mutări este \(2\). Celula de întâlnire poate fi \((1,1)\), \((1,2)\), \((2,1)\) sau \((2,2)\).