Description

给你一个在笛卡尔平面第一象限中的多边形。$^{\dagger}$

考虑多边形中 $\color{red}^{\dagger}$ 的所有网格点 $\color{blue}^{\dagger}$。将它们按斜率 $\color{green}^{\dagger}$ 从小到大排序 $\color{orange}^{\dagger}$。输出排序之后的第 $k$ 个网格点。

$^{\dagger}$ 这意味着多边形中任何顶点的坐标 $(x, y)$ 都满足 $x>0$ 和 $y>0$。

$\color{red}^{\dagger}$ 多边形边界上的一个点也被认为在多边形中。

$\color{blue}^{\dagger}$ 如果 $x,y\in \Z$，那么 $(x,y)$ 就是一个网格点。

$\color{green}^{\dagger}$ 点 $(x,y)$ 的斜率为 $\frac{y}{x}$。

$\color{orange}^{\dagger}$ 如果两个点具有相同的斜率，则先按 $x$ 从小到大排序，再按 $y$ 从小到大排序。换句话说，如果$(x_1<x_2)\vee(x_1=x_2\wedge y_1<y_2)$，则点 $(x_1,y_1)$ 在斜率上小于 $(x_2,y_2)$。

Input Format

第一行包含一个整数 $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)$。顶点按逆时针顺序给出。

保证多边形是简单的，即所有顶点互不相同，两条边只有在相邻时才会重叠，并且恰好重叠 $1$ 次。

保证 $k$ 不超过多边形中的网格点数。

保证 $\sum n \le 2000$。

Output Format

对于每组数据，输出一行两个整数 $x,y$，表示第 $k$ 个网格点的坐标。

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

3 2
500000000 500000000
7 8
730715389 644702744