8990번 - Pocket Ball 다국어채점 준비 중

There is a billiard table with a square shape, where each side has a unit length, and there are pockets at the four corners. A billiard ball hit at some corner of the table moves along some direction. Whenever the ball hits the side of the table not at a corner, it is reflected in the mirror direction, and it continues to travel on the table until the ball reaches a corner and drops into a pocket.

We label the four sides of the billiard table with N(orth), S(outh), E(ast), and W(est) and label the four corners with 1, 2, 3, and 4 as in the following figure. Suppose the billiard table is located in a plane so that corner 1 matches the origin of the coordinate system, and sides S and W of the table are parallel with the x- and the y-axes, respectively. Given the slope of the line along which the ball starts at the origin, compute the sequence of sides of the billiard table which the ball bounces off and the corner in which the ball drops into a pocket.

For example, if the slope of the line along which the ball starts is 3/5, then the trajectory of the ball until it drops into a pocket is shown in the figure below on the right. The ball leaves corner 1 and bounces off sides E, N, W, E, S, and W sequentially and finally drops into a pocket in corner 3.

The input file consists of T test cases. The number of test cases (T ) is given on the first line of the input file. The first line of each test case contains two integers p, q 1( ≤ p,q ≤ 100), where the quotient p / q is the slope of the line along which the ball leaves corner 1. 

For each test case, your program reports the sequence of sides of the billiard table which the ball bounces off and the corner in which the ball drops into a pocket. In the first line, your program reports the number of sides of the table the ball bounces off. In the second line, your program sequentially reports the sequence of sides of the table which the ball bounces off and the final corner in which the ball drops into a pocket. If the ball cannot drop into a pocket in some corner, your program is to report an integer –1 on the first line. The following shows sample input and output for three test cases.