격자점 C 찾기

평면 위 서로 다른 두 격자점 $A$와 $B$에 친구 두 명이 서 있다. 두 사람을 한 장에 담기 위해 다음 조건을 모두 만족하는 격자점 $C$를 고른다.

1. $C$는 $A$와 다르고 $B$와도 다르다.
2. 선분 $AC$ 위에는 두 끝점 말고 다른 격자점이 없다.
3. 선분 $BC$ 위에는 두 끝점 말고 다른 격자점이 없다.
4. 삼각형 $ABC$의 넓이가 $0$보다 크다. 즉 $C$는 $A$와 $B$를 지나는 직선 위에 있지 않다.
5. 삼각형 $ABC$의 내부에는 격자점이 없다.

$x$좌표와 $y$좌표가 모두 정수인 점을 격자점이라고 한다.

사진은 한 장만 찍지 않으므로, 주어진 $A$와 $B$마다 조건을 만족하는 $C$를 $K$개 구한다. 조건을 만족하는 $C$는 무수히 많아서 답이 하나로 정해지지 않으므로, 그중 어느 $K$개를 출력할지는 출력에서 정한 규칙을 따른다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 1000$)

다음 $T$개의 줄에 정수 다섯 개 $A_x$, $A_y$, $B_x$, $B_y$, $K$가 주어진다. $A = (A_x, A_y)$, $B = (B_x, B_y)$이고 두 점은 서로 다르다. ($-10^9 \le A_x, A_y, B_x, B_y \le 10^9$, $0 \le K$, 모든 $K$의 합은 $20000$ 이하)

각 테스트 케이스마다 점 $C$의 좌표를 "$C_x$ $C_y$" 형식으로 한 줄에 하나씩 $K$줄 출력한다. $K = 0$인 케이스에서는 아무것도 출력하지 않는다.

출력할 $K$개의 점은 다음 규칙으로 정한다. 위 조건을 모두 만족하는 격자점 $C$ 가운데

$s(C) = (B_x - A_x)(C_y - A_y) - (B_y - A_y)(C_x - A_x) > 0$

이면서

$f(C) = (C_x - A_x)(B_x - A_x) + (C_y - A_y)(B_y - A_y) \ge 0$

인 점만 남긴다. 남은 점을 $f(C)$가 작은 것부터 차례로 $K$개 출력한다.

남은 점은 무수히 많으므로 언제나 $K$개를 고를 수 있고, 남은 점의 $f(C)$ 값은 서로 다르므로 출력은 하나로 정해진다. 이 규칙으로 고른 점의 좌표는 절댓값이 $10^{14}$ 이하이다.