Alice and Bob are twins. In their birthday, they have a really large cake of dimensions 104 × 104. The cake has a number of flowers on it. As usual, Alice and Bob starts playing with it. First, Alice cuts the cake in two pieces, and then Bob takes the part with the maximum flowers on it. Since, Alice likes the flowers too, she will try to get maximum number of flowers. The flowers, which are incident by the cut are ruined, and thus non of them get those. The badness of a cut is the difference of the number of flowers between the two sets. The task presented to you is not to maximize the number of flowers, Alice gets. Instead, you are given the co-ordinates of the flowers, and a cut, made by Alice. You need to find out the number of flowers, that are partitioned into two parts, and the number of flowers, being ruined by the cut. Alice always cuts in a straight line. Input First line contains T, the number of test cases. Each test case starts with an integer N, the number of flowers. Following N lines each contains two integers, xi and yi, the co-ordinate of the i-th flower. No three flowers will be collinear. After that, a line with values, M, X1, Y1, X2, Y2, dX1, dY1, dX2, dY2 follows. Here, M is the number of queries. Each of these queries will be a line between two given points. The end points are generated by the function given below. Each call to the function generate will produce the end points of the query line. X1, Y1, X2, Y2, dX1, dY1, dX2, dY2 are used to generate the lines. X1, Y1, X2, Y2, dX1, dY1, dX2, dY2 function generate X1= Y1= X2= Y2 = Output (X1 + dX1) mod 104 (Y1 + dY1) mod 104 (X2 + dX2) mod 104 (Y2+dY2)mod104 ifX1 ==X2 andY1 ==Y2 thenY2 =(Y1+1)mod104 Each case starts with the line ‘Case #n:’ where n is the number of the test case. For each line, output three integers, p, q and r; where r is the number of flowers on the line and p and q are the number of flowers on the sides of the line. Constraints •t≤3 • N ≤ 1500 • M ≤ 700000 • For all location of flower (xi, yi), 0 ≤ xi, yi ≤ 10000. No three points will be collinear. •p≤q • All input values will fit into a 32bit signed integer
2/2 Sample Input 1 4 55 5 10 10 5 10 10 2 -7 -7 7 7 1 1 1 1 Sample Output Case #1: 112 112