Kingdom

Time limit1sMemory limit128 MB

Summary

Roads merge cities into connected states over time, and each query asks how many states a horizontal line meets and how many cities those states contain.

Level: Hard8 of 10
Topics: Union-find, Segment tree, Geometry, Intervals
Solved: No attempts yet

Problem

In an ancient kingdom there were $n$ cities. At first every city was isolated. As time went on the kings ordered roads to be built between cities, and each road is a straight line segment between the two cities it connects.

The cities are partitioned into disjoint groups by road connectivity. A connected group of cities is called a state: a state is made up of some cities together with the roads that link them.

A historical record lists the road constructions in chronological order. A road between two cities $A$ and $B$ never crosses another road except possibly at a shared endpoint city. Before a road is built, $A$ and $B$ may already belong to the same state or to two different states; after it is built they belong to the same state, so two states merge into one whenever necessary.

Professor Kim, a historian, wants to answer this question about a past moment: how many states does a horizontal line (the latitude of a particular place) pass through? The figure below shows one possible layout of roads. A circle is a city and a segment is a road. Here there are $3$ states: the line $y = 4.5$ passes through two states containing $8$ cities in total, and the line $y = 6.5$ passes through one state containing $5$ cities.

Write a program that processes the following two kinds of commands:

road A B: a road is built between cities $A$ and $B$ . It does not cross any other road except at shared endpoint cities. This command only updates the state of the kingdom; your program prints nothing for it.
line C: a query. Print how many states the line $y = C$ passes through and the total number of cities in those states.

Input

The input is read from standard input. The first line contains the number of test cases $T$ . Each test case has the following form.

The first line contains an integer $n$ , the number of cities, with $1 \le n \le 100{,}000$ . Each of the next $n$ lines contains two integers $x$ and $y$ with $0 \le x, y \le 1{,}000{,}000$ , the coordinates of a city, separated by a single space. The cities are numbered from $0$ to $n-1$ in the order they are given.

The next line contains an integer $m$ , the number of commands, with $1 \le m \le 200{,}000$ . Each of the next $m$ lines is either road A B or line C, where $0 \le A \ne B < n$ and $C$ (with $0 < C < 1{,}000{,}000$ ) is a real number whose fractional part is always $0.5$ . At most one road is ever built between a given pair of cities, and every test case contains at least one query.

Output

Write to standard output. For every query, across all test cases, print exactly one line containing two integers: the number of states the line passes through and the total number of cities in those states.

Examples3

Example 1

Input

3
10
1 7
5 7
8 6
3 5
5 5
2 3
10 3
7 2
4 1
11 1
11
road 0 1
road 3 5
line 6.5
road 4 2
road 3 8
road 4 7
road 6 9
road 4 1
road 2 7
line 4.5
line 6.5
1
100 100
1
line 100.5
2
10 10
20 20
2
road 0 1
line 15.5

Expected output

Example 2

Input

1
2
0 3
5 7
5
line 5.5
road 0 1
line 5.5
line 2.5
line 7.5

Expected output

Example 3

Input

1
7
0 0
0 10
5 2
5 8
9 4
9 4
20 5
6
road 0 1
road 2 3
road 4 5
line 5.5
line 1.5
line 9.5

Expected output

2 4
1 2
1 2