볼록 격자 다각형의 내부점

격자점은 x좌표와 y좌표가 모두 정수인 점이다. 격자 다각형은 모든 꼭짓점이 격자점인 다각형이다.

다각형의 경계 위에 있는 격자점을 경계점, 경계 위에 있지 않고 다각형 안에 있는 격자점을 내부점이라고 한다.

볼록 다각형은 다각형 안의 임의의 두 점을 이은 선분이 항상 다각형의 내부 또는 경계에 놓이는 다각형이다. 이 문제의 입력은 볼록 격자 다각형이며, 꼭짓점은 지정된 순서로 주어진다.

각 정수 y 좌표에 대해, 그 y 좌표를 갖는 내부점들이 존재하면 가장 왼쪽 내부점의 x 좌표와 가장 오른쪽 내부점의 x 좌표가 정해진다. 내부점이 하나뿐이면 두 값은 같다.

주어진 각 볼록 격자 다각형에 대해 내부점이 존재하는 모든 수평선(정수 y 좌표)을 찾아, 위에서 아래 순서로 해당 y 좌표와 가장 왼쪽/오른쪽 내부점의 x 좌표를 출력하라.

입력되는 꼭짓점 순서는 다음과 같다.

1. 첫 번째 점은 y 좌표가 가장 큰 점이다. 그러한 점이 여러 개이면 x 좌표가 작은 점이 먼저 온다.
2. 꼭짓점은 시계 방향으로 주어진다.

첫 줄에 테스트 케이스의 개수 P (1 ≤ P ≤ 1000)가 주어진다.

각 테스트 케이스의 첫 줄에는 다각형 꼭짓점의 개수 N (3 ≤ N ≤ 50)이 주어진다. 이어지는 N개의 줄에는 꼭짓점의 x 좌표와 y 좌표가 위에서 설명한 순서대로 주어진다. 모든 좌표는 -30 이상 30 이하의 정수이다.

각 테스트 케이스마다 먼저 내부점이 존재하는 정수 y 좌표의 개수를 출력한다. 하나 이상이면 각 y 좌표를 내림차순으로 한 줄에 하나씩 출력한다. 각 줄에는 y 좌표, 그 y에서의 가장 왼쪽 내부점의 x 좌표, 가장 오른쪽 내부점의 x 좌표를 공백으로 구분해 출력한다.