P9672 [ICPC 2022 Jinan R] Grid Points

给你一个在笛卡尔平面第一象限中的多边形。这意味着多边形中任何顶点的坐标 $(x, y)$ 都满足 $x>0$ 和 $y>0$。 考虑多边形中的所有网格点。将它们按**斜率**从小到大排序。输出排序之后的第 $k$ 个网格点。 如果 $x,y\in \Z$，那么 $(x,y)$ 就是一个网格点。多边形边界上的一个点也被认为在多边形中。点 $(x,y)$ 的斜率为 $y/x$。如果两个点具有相同的斜率，则先按 $x$ 从小到大排序，再按 $y$ 从小到大排序。换句话说，如果$(x_1

第一行包含一个整数 $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$。

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