평형 상태

물체 P에 작용하는 힘의 합이 0이면 P는 움직이지 않는다. 이때 P가 평형 상태에 있다고 한다.

그림 1. 물체 P에 작용하는 힘

그림 2와 같은 상황을 보자. x축 위에 고정점 F1과 F2가 있고, 물체 P가 스프링 S1과 S2로 연결되어 있다. S1은 F1과 P를 잇고, S2는 F2와 P를 잇는다. 두 스프링의 탄성계수를 각각 $w_1$, $w_2$라 하고, F1과 F2의 x좌표를 각각 $x(F_1)$, $x(F_2)$라 하자. 후크 법칙에 따라 S1이 P에 가하는 힘은 $w_1 \times (x(P) - x(F_1))$이고, S2가 P에 가하는 힘은 $w_2 \times (x(P) - x(F_2))$이다. 여기서 $x(P)$는 P의 x좌표다.

그림 2. 평형 상태의 예

예를 들어 그림 2에서 $x(F_1) = 0$, $x(F_2) = 7$, $w_1 = 3$, $w_2 = 4$이고 P가 평형 상태이면 P의 위치는 $x(P) = 4$로 정해진다.

이제 그림 3처럼 평면 위에서 여러 물체가 여러 스프링으로 연결된 상황을 생각하자. 고정점은 $F_1, \ldots, F_k$의 $k$개, 물체는 $P_1, \ldots, P_n$의 $n$개, 스프링은 $S_1, \ldots, S_m$의 $m$개이고 스프링 $S_i$의 탄성계수는 $w_i$다. 스프링 하나는 고정점과 물체를 잇거나 물체 두 개를 잇는다. 평면에서도 후크 법칙은 그대로 성립해서, 두 점 A와 B를 잇는 탄성계수 $w$인 스프링이 A에 가하는 힘은 벡터 $w \times (A - B)$이고 x성분과 y성분에 같은 식이 각각 적용된다. 모든 물체가 스프링 두 개 이상에 연결되어 있으면 물체는 결국 모두 평형 상태가 되며, 그때 각 물체의 위치가 하나로 정해진다.

$k$개 고정점의 좌표, $m$개 스프링의 탄성계수, 물체와 고정점의 연결 관계가 주어질 때 평형 상태에서 $n$개 물체의 좌표를 구하는 프로그램을 작성하시오.

그림 3. 평면에서의 평형 상태 예

다음을 가정해도 된다.

1. 모든 물체는 스프링 두 개 이상에 연결되어 있고, 물체와 고정점을 통틀어 어떤 두 점을 잡아도 스프링을 하나 이상 거쳐 이어져 있다.
2. (물체, 물체) 한 쌍이나 (물체, 고정점) 한 쌍을 잇는 스프링은 많아야 하나다.
3. 한 직선 위에 있지 않은 고정점이 세 개 이상 있다.
4. 모든 물체가 평형 상태일 때 두 스프링이 서로 교차하지 않고, 두 물체가 같은 위치에 놓이지 않는다.
5. 좌표가 같은 고정점은 없다.

입력은 표준 입력으로 받는다. 첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $k$ ($3 \le k \le 100$), $m$ ($3 \le m \le 3000$), $n$ ($1 \le n \le 1000$)이 공백으로 구분되어 주어진다. $k$는 고정점의 개수, $m$은 스프링의 개수, $n$은 물체의 개수다.

이어지는 $k$개 줄 중 $i$번째 줄에는 고정점 $F_i$의 정수 좌표 $x_i$, $y_i$ ($-10000 \le x_i, y_i \le 10000$)가 주어진다.

이어지는 $m$개 줄 중 $i$번째 줄에는 세 정수 $w_i$, $u_i$, $v_i$가 주어진다. $w_i$ ($1 \le w_i \le 100$)는 스프링 $S_i$의 탄성계수이고, $u_i$와 $v_i$는 $S_i$가 연결하는 두 끝점의 번호다. $u_i$가 음수이면 고정점 $F_{-u_i}$ ($1 \le -u_i \le k$)를 뜻하고, 양수이면 물체 $P_{u_i}$ ($1 \le u_i \le n$)를 뜻한다. $v_i$도 같은 방식으로 읽는다.

결과는 표준 출력으로 내보낸다. 테스트 케이스마다 먼저 Test case number : 뒤에 테스트 케이스 번호를 붙여 한 줄에 출력한다. 번호는 1부터 시작한다. 그다음 $n$개 줄 중 $i$번째 줄에 번호 $i$와 물체 $P_i$의 좌표 $x_i$, $y_i$를 공백 하나로 구분해 출력한다.

좌표는 소수점 셋째 자리에서 반올림해 소수점 아래 두 자리까지 출력한다. 반올림은 0에서 먼 쪽으로 하고, 반올림한 값이 0이면 부호를 붙이지 않고 0.00으로 출력한다. 정답 좌표의 정확한 값은 반올림 경계에서 $10^{-6}$ 이상 떨어져 있으므로 출력할 문자열은 하나로 정해진다.