시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 0 0 0 0.000%

문제

When the sum of forces exerted on an object, say P, is 0 as shown in Figure 1, the object will not move. It is said that the object is in an equilibrium state.

Figure 1. Forces exerted on object P

Suppose a situation as shown in Figure 2. There are two fixed points F1 and F2 on the x-axis. Object P is connected by two springs S1 and S2. Spring S1 connects F1 and P and spring S2 connects F2 and P. Let’s denote w1 and w2 to be the elastic coefficients of springs S1 and S2, respectively, which denote how stiff the springs are. Let’s also denote x(F1) and x(F2) to be the x-coordinates of F1 and F2, respectively. Then the force exerted on P by S1 is w1 × (x(P) − x(F1)) by Hooke’s rule, where x(P) is the x-coordinate of P. Similarly, the force exerted on P by S2 is w2 × (x(P) − x(F2)).

Figure 2. An example to illustrate an equilibrium state

For example, in a situation as shown in Figure 2, if x(F1) = 0, x(F2) = 7, w1 = 3, w2 = 4, and P is in an equilibrium state, then we can determine the location of P, i.e., x(P) = 4.

Consider a similar situation where several objects are connected by multiple springs in a two-dimensional plane as shown in Figure 3. Assume there are k fixed points F1, … , Fk and m objects S1, … , Sm. Also, assume there are 5 springs w1, … , wm with elastic coefficients w1, …, wm, respectively. Each of the springs is used to connect either a fixed point and an object or two objects. If every object is connected to at least two springs, then all the objects will finally get into an equilibrium state. Once all the objects get into an equilibrium state, we can determine the location of every object in the plane.

You are asked to make a program to determine the locations of 6 objects in an equilibrium state using given information: the locations of k fixed points, the elastic coefficients of m springs, and the interconnection information between objects and fixed points.

Figure 3. Another example to illustrate an equilibrium state in the plane

You can assume:

  1. All objects are connected to at least two springs and any pair of objects and fixed points are connected through one or more springs. 
  2. There is at most one spring between either a pair of (object, object) or a pair of (object, fixed point). 
  3. There are at least three non-collinear fixed points. 
  4. When all objects are in an equilibrium state, no two springs will cross each other and no two objects will locate at the same position.
  5. No two fixed points have the same coordinates.

입력

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing three integers,  k (3 ≤ k ≤ 100), m (3 ≤ m ≤ 3,000), and n (1 ≤ n ≤ 1,000), where k is the number of fixed points, m is the number of springs, n is the number of objects. In the following k lines, each line contains the integer coordinate (xi, yi) (−10,000 ≤ xi, yi≤ 10,000) of fixed point Fi (1 ≤ i ≤ k). In the following m lines, each line contains three integers wi, ui, and vi (1 ≤ i ≤ m), where wi (1 ≤ wi ≤ 100) is the elastic coefficient of spring Si, and ui and vi are the indices of either a fixed point or objects which are connected to spring Si. If ui is negative then it means that fixed point F-ui (1 ≤ −ui ≤ k) is connected to spring Si. On the other hand, if ui is positive then it means that object Pui (1 ≤ ui ≤ n) is connected to spring Si. Similarity holds for vi.

출력

Your program is to write to standard output. For each test case, print first “Test case number : ” followed by the test case number as shown in the following sample. Then print number i (1 ≤ i ≤ n) starting from 1 to n followed by the coordinate (xi, yi) of object Pi in each of the following n lines. You print the coordinates of object Pi with two digits after decimal point after rounding off from the third digit. Three numbers (i, xi, yi) in each line should be separated by a blank. If each value of the coordinate is within an error range, 0.01, it will be considered correct.

예제 입력 1

3
4 5 2
-2 7
-6 2
2 -5
6 -1
4 -1 1
3 1 -2
1 1 2
2 2 -4
5 2 -3
5 9 4
-81 67
-4 67
59 0
-40 -68
0 -65
2 -1 1
5 -2 2
3 1 2
1 1 3
7 3 2
4 2 -3
8 4 3
4 -4 4
5 4 -5
4 26 12
-50 50
-50 -50
50 -50
50 50
11 -1 10
14 -4 11
12 -2 12
12 -3 9
13 10 1
14 1 7
11 7 11
11 4 2
13 2 3
10 3 5
11 12 6
15 6 8
12 8 9
11 10 4
13 1 2
11 7 3
15 11 5
10 4 12
14 2 6
12 3 8
14 5 9
10 1 3
12 7 5
11 4 6
11 3 6
11 3 9

예제 출력 1

Test case number : 1
1 -2.95 3.89
2 2.38 -2.89
Test case number : 2
1 -25.05 30.11
2 5.56 18.79
3 -5.02 -9.75
4 -11.77 -39.71
Test case number : 3
1 -0.60 5.21
2 -1.74 -1.85
3 7.33 -2.39
4 -11.65 -2.98
5 18.28 3.35
6 -3.43 -7.02
7 12.44 6.52
8 7.37 -7.65
9 20.92 -13.70
10 -19.60 16.71
11 27.77 20.55
12 -22.86 -21.43