왕국

옛날 어느 왕국에 $n$개의 도시가 있었다. 처음에는 모든 도시가 서로 떨어져 있었다. 시간이 지나면서 왕들은 도시를 잇는 길을 건설하도록 명령했고, 각 길은 두 도시를 잇는 직선 선분이다.

도시들은 길로 연결되어 있는지에 따라 서로소인 그룹으로 나뉜다. 길로 연결된 하나의 도시 그룹을 주(state)라고 부른다. 하나의 주는 몇 개의 도시와 그 도시들을 잇는 길들로 이루어진다.

역사 기록에는 길을 건설한 순서가 시간순으로 적혀 있다. 두 도시 $A$와 $B$를 잇는 길은 공유하는 끝점 도시를 제외하고는 다른 길과 절대 만나지 않는다. 길을 놓기 전에 $A$와 $B$는 같은 주에 속할 수도 있고 서로 다른 주에 속할 수도 있다. 길을 놓은 뒤에는 둘이 같은 주에 속하게 되므로, 필요하면 두 주가 하나로 합쳐진다.

역사학자 김 교수는 과거 어느 시점에 대해 다음 질문의 답을 알고 싶어 한다. 수평선(어떤 장소의 위도에 해당하는 가로선) 하나가 몇 개의 주를 지나는가? 아래 그림은 길이 놓인 한 가지 상태를 보여준다. 원은 도시이고 선분은 길이다. 여기에는 $3$개의 주가 있으며, 직선 $y = 4.5$는 도시가 모두 $8$개인 두 주를 지나고, 직선 $y = 6.5$는 도시가 $5$개인 한 주를 지난다.

다음 두 종류의 명령을 처리하는 프로그램을 작성하라.

• road A B: 도시 $A$와 $B$ 사이에 길을 건설한다. 이 길은 공유하는 끝점 도시를 제외하고 다른 길과 만나지 않는다. 이 명령은 왕국의 상태만 갱신하며, 프로그램은 아무것도 출력하지 않는다.
• line C: 질의이다. 직선 $y = C$가 지나는 주의 개수와 그 주들에 속한 도시의 총 개수를 출력한다.

입력은 표준 입력으로 주어진다. 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

첫 줄에는 도시의 수 $n$이 주어지며 $1 \le n \le 100{,}000$이다. 이어지는 $n$개의 줄에는 각각 두 정수 $x$와 $y$가 공백 하나로 구분되어 주어지고, 이는 한 도시의 좌표를 나타내며 $0 \le x, y \le 1{,}000{,}000$이다. 도시는 주어진 순서대로 $0$번부터 $n-1$번까지 번호가 매겨진다.

그다음 줄에는 명령의 수 $m$이 주어지며 $1 \le m \le 200{,}000$이다. 이어지는 $m$개의 줄에는 각각 road A B 또는 line C 형태의 명령이 주어진다. 여기서 $0 \le A \ne B < n$이고, $C$는 $0 < C < 1{,}000{,}000$이며 소수 부분이 항상 $0.5$인 실수이다. 같은 도시 쌍 사이에는 길이 최대 한 번만 건설되고, 각 테스트 케이스에는 질의가 적어도 하나 있다.

출력은 표준 출력으로 한다. 모든 테스트 케이스를 통틀어 각 질의마다 정확히 한 줄을 출력한다. 그 줄에는 두 정수, 즉 직선이 지나는 주의 개수와 그 주들에 속한 도시의 총 개수를 출력한다.