Angry high math-Snowball

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

在下雪的时候小红和m个好朋友准备去打雪仗,地方是一个n*n的操场,每个人都会有一个位置坐标(x,y),( 1 < = x,y < = n ),想要攻击道某一个人所花费的力气为(x1-x2)^2+(y1-y2)^2。小红想知道她站在什么地方才能花费最小力气攻击到所有人,因为小红不想和其他人在一起,所以小红一定单独占一个坐标。如果有多个位置输出x坐标最小,x相同输出y最小。

Input

 多组输入,先输入两个整数n,m ( 1 < = m < = min(n^2-1,100) , 2 < = n < = 1000 ),接下来m行,每行有两个整数x,y,代表每个人的位置坐标。

Output

 输出小红的位置坐标以及花费的力气。

Sample Input

2 1
1 1

Sample Output

1 2 1

Hint

 

Source

LB