사파리 공원

사파리 공원에서는 동물을 우리에 가두지 않는다. 방문객은 차를 타거나 걸어서 공원을 돌아다니며 자유롭게 지내는 동물을 볼 수 있다. 사자나 호랑이처럼 위험한 동물도 마찬가지다. 나도 사파리 공원을 하나 열었고, 같은 방식으로 운영한다.

공원은 동물마다 구역 하나로 나뉜다. 안전을 위해 서로 다른 동물의 구역은 내부를 조금도 공유하지 않는다. 두 구역이 경계를 그대로 공유할 수는 있다. 동물은 자기 구역을 벗어나지 않도록 훈련받았다.

공원이 너무 넓어서 지도 한 장에 전체를 담을 수 없다. 그래서 방문객이 원하는 곳을 찾도록 도와주는 안내 장치를 준비했다. 값을 아끼려고 성능이 낮은 기종을 골랐고, 메모리도 넉넉하지 않다. 처리를 간단하게 하려고 구역은 모두 삼각형으로 만들었다. 구역 정보도 처음에 한꺼번에 올리지 않고, 방문객이 모노레일로 이동한 위치에 따라 그때그때 불러온다. 그래서 삼각형은 뒤섞인 순서로 장치에 도착한다.

장치는 구역을 화면에 그려 주지만 이름은 보여 주지 않는다. 좌표를 입력하면 그 점이 들어 있는 구역의 번호를 알려 준다. 번호 두 개는 특별하다. 0은 그 점이 어느 구역에도 들어 있지 않다는 뜻이고, -1은 어떤 구역의 경계나 꼭짓점 위에 있다는 뜻이다.

삼각형 구역이 하나씩 추가되고, 그 사이사이에 점의 위치를 묻는 질의가 들어온다. 두 삼각형의 관계는 다음 네 가지로 정리된다.

질의로 주어진 점이 어떤 구역의 내부에 있으면 그 구역의 번호를 출력한다. 모든 구역의 바깥에 있으면 0을, 어떤 구역의 경계나 꼭짓점 위에 있으면 -1을 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($T \le 2$)

각 테스트 케이스의 첫째 줄에 명령의 개수 $N$이 주어진다. ($N \le 300000$) 이어지는 $N$개의 줄에 명령이 한 줄에 하나씩 주어진다. 명령은 문자 R 또는 문자 Q로 시작한다.

R 명령에는 정수 여섯 개 $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$이 뒤따르고, 삼각형 구역 하나를 새로 추가한다. 한 테스트 케이스의 R 명령은 최대 50000개다. $k$번째 R 명령으로 추가된 구역의 번호는 $k$다.

Q 명령에는 정수 두 개 $x_q$, $y_q$가 뒤따르고, 그 점이 어느 구역에 들어 있는지 묻는다. 질의는 그 명령보다 앞에 나온 구역만 고려한다. 앞에 R 명령이 $n$개 있었다면 답은 $-1$부터 $n$까지의 값 중 하나다.

명령에 적힌 정수는 실제 좌표가 아니다. 직전 질의의 답을 $d$라고 하면(첫 질의 전에는 $d = 0$), 적힌 값 $x$, $y$의 실제 좌표는 $x + x_1[d]$, $y + y_1[d]$다. 여기서 $x_1[d]$, $y_1[d]$는 $d$번 구역의 첫 번째 꼭짓점의 실제 좌표다. $d$가 $0$이거나 $-1$이면 $x_1[d] = y_1[d] = 0$으로 본다. 한 명령에 적힌 좌표 전부에 같은 값을 더한다.

구역의 세 꼭짓점은 항상 시계 방향으로 주어진다. 구역이 도착하는 순서는 무작위다. 실제 좌표는 모두 0 이상 100000 이하다.

각 테스트 케이스마다 먼저 테스트 케이스 번호를 Case k: 형식으로 출력한다. $k$는 1부터 세는 테스트 케이스 번호다. 그다음 각 Q 명령의 답을 명령이 나온 순서대로 한 줄에 하나씩 출력한다. 테스트 케이스 사이에 빈 줄을 출력하지 않는다.