Jack 和 Jill 拥有一张向右和向上无限延伸的棋盘。行和列均由从 1 开始的整数编号。他们在棋盘上进行如下游戏：初始时，棋盘上有 $k$ 枚棋子。在每一轮中，玩家选择一枚棋子，并将其向左、向下、对角线方向（向左和向下移动相同的格数）移动一格或多格，或者使用一种会减小行号和列号的马步（向下移动一格且向左移动两格，或向下移动两格且向左移动一格）。棋子不得移出棋盘，但可以跳过其他棋子或停留在与其他棋子相同的位置。无法进行移动的玩家输掉比赛。Jack 和 Jill 轮流移动，Jack 先手。

请帮助 Jack 找到一个获胜的移动，或者判断 Jill 是否拥有必胜策略。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 100$)。

每个测试用例包含多行。第一行包含一个整数 $k$，表示初始棋子的数量 ($1 \le k \le 10$)。接下来的 $k$ 行确定了棋子的初始位置，每行一个。每个位置由两个整数 $r$ 和 $c$ 给定，分别表示行号和列号 ($1 \le r, c \le 2000$)。

输出格式

对于每个测试用例，输出一行，包含三个空格分隔的整数：$i$、$r$ 和 $c$。这表示在双方均采取最优策略的情况下，Jack 的获胜移动是将第 $i$ 枚棋子移动到位置 $(r, c)$。棋子编号从 1 开始。

如果有多种可能的解，请输出字典序最小的一个：即棋子编号最小的解；若仍有歧义，则输出行号最小的解；若仍有歧义，则输出列号最小的解。

如果 Jack 没有获胜策略，请输出 “-1 -1 -1”（不含引号）。

样例

输入 1

3
5
2 3
3 2
3 3
3 3
3 3
1
2 4
2
1 1
3 2

输出 1

3 1 1
-1 -1 -1
2 1 1