Windmill Animation#5130
A windmill animation works as follows:
A two-dimensional set of points, no three of which lie on a line is chosen. Then one of the points is chosen (as the first pivot) and a line is drawn through the chosen point at some initial angle. The animation proceeds by rotating the line counter-clockwise about the pivot at a constant rate. When the line hits another of the points, that point becomes the new pivot point. In the two examples below, the points are , , , and .
Example 1
In Example 1, the start point is point and the line starts rotated degrees from horizontal. When the line rotates to degrees, point is hit and becomes the new pivot. Then point becomes the new pivot, then point , then point .
Example 2
In Example 2 the initial point is point and the line starts horizontal. At degrees, point becomes the pivot, then at about degrees, point becomes the pivot. At about degrees, point becomes the pivot again, then point , point and back to as at the start.
Write a program, which takes as input the points of the set, the initial point and the initial line angle and outputs the sequence of pivot points.
The first line of input contains a single integer , (1 \le P \le 1000), which is the number of data sets that follow. Each data set should be processed identically and independently.
Each data set consists of multiple lines of input. The first line of each data set consists of four space-separated decimal integers followed by a single floating-point value. The first integer is the data set number. The second integer is the number of points to follow (3 \le M \le 20). The third integer gives the number, , of the pivot points to output (3 \le S \le 20) and the fourth integer gives the index, , of the initial point (1 \le I \le M). The floating-point value is the angle, , in degrees, that the initial line is rotated counter-clockwise from horizontal (0 \le A \le 180).
The remaining lines in the data set contain the coordinates of the set points. Each line consist of an integer, the point's index, , and two floating-point values, the and coordinates of the point respectively.
For each data set there is a single line of output. It contains the data set number, followed by space separated point indices (excluding the initial point index).
Example 1