Interior Points of a Convex Lattice Polygon

A lattice point is a point whose x-coordinate and y-coordinate are both integers. A lattice polygon is a polygon whose every vertex is a lattice point.

A lattice point on the boundary of a polygon is called a boundary point. A lattice point inside the polygon but not on its boundary is called an interior point.

A convex polygon is a polygon in which the segment between any two points of the polygon always lies inside the polygon or on its boundary. In this problem, each input polygon is a convex lattice polygon, and its vertices are given in the specified order.

For each integer y-coordinate, if there are interior points with that y-coordinate, then the x-coordinate of the leftmost interior point and the x-coordinate of the rightmost interior point are determined. If there is only one such interior point, the two values are equal.

For each given convex lattice polygon, find every horizontal line (integer y-coordinate) that contains at least one interior point. Print those y-coordinates from top to bottom, along with the x-coordinates of the leftmost and rightmost interior points on each line.

The vertices are given in the following order.

1. The first point has the largest y-coordinate. If several points have that y-coordinate, the one with the smaller x-coordinate comes first.
2. The vertices are given in clockwise order.

The first line contains the number of test cases P (1 ≤ P ≤ 1000).

For each test case, the first line contains the number of polygon vertices N (3 ≤ N ≤ 50). Each of the next N lines contains two integers, the x-coordinate and y-coordinate of a vertex, in the order described above. Every coordinate is an integer between -30 and 30, inclusive.

For each test case, first print the number of integer y-coordinates that contain at least one interior point. If there is at least one such y-coordinate, print them in decreasing order, one per line. Each line must contain the y-coordinate, the x-coordinate of the leftmost interior point on that y-coordinate, and the x-coordinate of the rightmost interior point on that y-coordinate, separated by spaces.