给定一个笛卡尔坐标系第一象限内的简单多边形。这意味着多边形内任意一点的坐标 $(x, y)$ 均满足 $x > 0$ 且 $y > 0$。

考虑多边形内的所有网格点。按斜率递增的顺序对它们进行排序。输出该顺序下的第 $k$ 个网格点。

网格点是指坐标 $x$ 和 $y$ 均为整数的点。多边形边界上的点被视为在多边形内。点 $(x, y)$ 的斜率为 $y/x$。如果两个点的斜率相同，则按字典序排序，先比较 $x$，再比较 $y$。换句话说，如果 $(x_1 < x_2) \lor (x_1 = x_2 \land y_1 < y_2)$，则点 $(x_1, y_1)$ 在字典序上小于 $(x_2, y_2)$。

输入格式

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

对于每个测试用例，第一行包含两个整数 $n, k$ ($n \ge 3, 1 \le k$)。接下来的 $n$ 行描述多边形的顶点。每个顶点由两个整数 $x, y$ ($1 \le x, y \le 10^9$) 表示，代表其坐标 $(x, y)$。顶点按逆时针顺序给出。

保证多边形是简单的，即顶点互不相同，两条边仅在边界上连续时才可能重叠，且重叠部分恰好为一个点。保证 $k$ 不超过多边形内网格点的总数。

保证所有测试用例的 $n$ 之和不超过 $2000$。

输出格式

对于每个测试用例，输出一行两个整数 $x, y$，表示第 $k$ 个网格点的坐标 $(x, y)$。

样例

输入 1

4
3 3
1 1
3 1
3 3
4 500000000000000000
1 1
1000000000 1
1000000000 1000000000
1 1000000000
9 22
9 6
6 7
9 7
10 10
6 9
3 9
1 6
1 5
7 3
5 22447972861454999
270353376 593874603
230208698 598303091
237630296 255016434
782669452 568066304
654623868 958264153

输出 1

3 2
500000000 500000000
7 8
730715389 644702744