描述

一家公司（名字保密）在隆德市中心有一栋办公楼。该建筑的屋顶是一个完美的正方形，上面有一些天窗。由于最近发生了一系列盗窃案，罪犯通过这些天窗进入建筑，因此公司决定用一只看门狗来守护天窗。他们选择了一种特别凶猛但相当愚蠢的狗，不幸的是，这只狗在第三次值班时从屋顶掉了下去。

公司又采购了一只新狗，并决定在其项圈上系上一根皮带，另一端固定在屋顶的某个点。然而，如果皮带太短，狗就无法到达所有天窗；但如果皮带太长，狗又会再次从建筑上掉下去。皮带两端都有钩子，因此没有任何部分用于打结。公司希望狗能够到达每个天窗的中心（狗能够到达的距离正好等于皮带平铺在屋顶上时能够到达的距离），但又不希望皮带延伸到屋顶的边缘之外（延伸到边缘是可以接受的）。他们希望通过仔细选择皮带的长度和固定点，让狗能够到达所有天窗，同时避免从建筑上掉下去的风险。皮带只能固定在整数坐标的点上（如果建筑是 10 米 × 10 米，那么建筑的西南角坐标为 (0, 0)，东北角坐标为 (10, 10)）。皮带不能固定在有天窗的点上。

如果找不到一个可以固定皮带的地方，既能到达所有天窗，又不会延伸到屋顶边缘之外，那么就无法使用这种狗，公司将会改用贵宾犬（这是一种比较不凶猛的狗，但也不容易从建筑上掉下去）。

输入

输入的第一行是一个正整数 $N$，表示接下来的测试用例数量。每个测试用例以一行包含两个整数 $S$ 和 $H$ 开始，其中 $S$ 是偶数，$2 \leq S \leq 40$，$1 \leq H \leq 50$。$S$ 表示正方形屋顶的边长（单位：米），$H$ 表示天窗的数量。

接下来的 $H$ 行每行包含两个整数 $X$ 和 $Y$，这些是天窗的坐标。天窗永远不会位于屋顶之外或屋顶的边缘上，且没有两个天窗占据同一个位置。

输出

对于每个测试用例，输出一行，包含固定皮带的坐标 $X$ $Y$（如果有多个可能的点，输出 $X$ 最小的那个点；如果仍然有多个可能的点，则在 $X$ 最小的点中选择 $Y$ 最小的那个点），使得合适长度的皮带能够让狗到达所有天窗且不会延伸到屋顶边缘之外。如果没有这样的点，输出 “poodle” 作为该测试用例的结果。

输入数据 1

3  
10 2  
6 6  
5 4  
20 2  
1 1  
19 19  
10 3  
1 1  
1 2  
1 3

输出数据 1

3 6  
poodle  
2 2

来源

2004年西北欧