감시견

한 회사의 사옥은 완전한 정사각형 모양의 평평한 지붕을 가지고 있으며, 지붕에는 여러 개의 채광창(해치)이 있다. 도둑들이 이 해치를 통해 침입하는 사건이 이어지자, 회사는 해치를 감시견에게 지키게 하기로 했다.

개가 지붕에서 떨어지지 않도록, 목줄의 한쪽 끝은 개의 목걸이에, 다른 쪽 끝은 지붕 위의 한 지점에 고정한다. 목줄이 너무 짧으면 개가 모든 해치에 닿지 못하고, 너무 길면 개가 건물 밖으로 떨어질 수 있다. 목줄의 양쪽 끝에는 고리가 달려 있어 매듭에 쓰이는 길이는 없다(목줄의 길이가 곧 개가 닿을 수 있는 거리이다).

회사는 다음 두 조건을 모두 만족시키고자 한다.

• 개가 모든 해치의 중심에 닿을 수 있어야 한다(개가 닿을 수 있는 최대 거리는 목줄을 지붕 위에 평평하게 펼쳤을 때의 길이와 같다).
• 목줄이 지붕의 가장자리를 넘어가지 않아야 한다(가장자리에 정확히 닿는 것은 허용된다).

목줄은 정수 좌표를 가진 지점에만 고정할 수 있다. 지붕이 $10 \times 10$ 미터라면 남서쪽 모서리는 $(0, 0)$, 북동쪽 모서리는 $(10, 10)$이다. 해치가 있는 지점에는 목줄을 고정할 수 없다.

이 조건을 모두 만족하도록 목줄을 고정할 수 있는 지점이 하나도 없다면, 이 견종은 사용할 수 없다.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 $S$와 $H$가 주어진다. $S$는 정사각형 지붕의 한 변의 길이(미터)이며 짝수이고 $2 \le S \le 40$이다. $H$는 해치의 개수로 $1 \le H \le 50$이다.

이어지는 $H$개의 줄에는 각 해치의 좌표 $X$ $Y$가 주어진다. 해치는 절대 지붕 밖이나 지붕의 경계선 위에 있지 않으며, 서로 다른 두 해치가 같은 위치에 있지 않다.

각 테스트 케이스마다, 개가 모든 해치에 닿으면서 목줄이 지붕의 가장자리를 넘지 않도록 목줄을 고정할 수 있는 지점의 좌표 $X$ $Y$를 한 줄에 출력한다.

가능한 지점이 여러 개라면 $X$가 가장 작은 것을 출력하고, 그런 지점이 여러 개라면 그중 $Y$가 가장 작은 것을 출력한다.

그러한 지점이 존재하지 않으면 그 테스트 케이스에 대해 poodle을 출력한다.