Safari Park

A safari park keeps its animals out of cages. Visitors may drive or walk through the park and watch the animals roam free, dangerous ones like lions and tigers included. I have opened a safari park of my own and I run it the same way.

The park is divided into one region per animal. For safety, regions of different animals share no interior area at all. Two regions may share a boundary. The animals are trained so that they never leave their own territory.

The park is so large that a single map cannot show all of it, so I prepared a handheld device that helps visitors find the place they are looking for. To keep the price down I bought a low end model, and its memory is small. To make the processing simple, every region is a triangle. The regions are not all loaded at the start either. They are loaded as the visitor moves around the park by mono-rail, so the triangles reach the device in a shuffled order.

The device draws the regions on its screen but shows no names. You type in the coordinates of a point and the device tells you the number of the region that contains it. Two numbers are special. 0 means the point is in no region at all, and -1 means the point lies on the boundary or on a corner of some region.

Triangular regions are added one at a time, and queries about the position of a point arrive in between. The relation between two triangles falls into these four cases.

If a query point is strictly inside some region, print the number of that region. If it is outside every region, print 0. If it lies on the boundary or on a corner of some region, print -1.

The first line contains the number of test cases $T$. ($T \le 2$)

The first line of each test case contains the number of commands $N$. ($N \le 300000$) Each of the next $N$ lines contains one command. A command starts with the letter R or the letter Q.

An R command is followed by six integers $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$ and adds one new triangular region. A test case contains at most 50000 R commands. The region added by the $k$-th R command has number $k$.

A Q command is followed by two integers $x_q$, $y_q$ and asks which region contains that point. A query considers only the regions that appear before it. If $n$ R commands appear before a Q command, its answer is one of the values from $-1$ to $n$.

The integers written in a command are not the real coordinates. Let $d$ be the answer to the previous query, with $d = 0$ before the first query. The real coordinates of a written pair $x$, $y$ are then $x + x_1[d]$, $y + y_1[d]$, where $x_1[d]$, $y_1[d]$ are the real coordinates of the first corner of region $d$. If $d$ is $0$ or $-1$, take $x_1[d] = y_1[d] = 0$. The same shift is added to every coordinate written in that one command.

The three corners of a region are always given in clockwise order. The regions arrive in random order. Every real coordinate is between 0 and 100000, inclusive.

For each test case, first print the test case number in the form Case k:, where $k$ counts from 1. Then print the answer to each Q command on its own line, in the order the commands appear. Do not print a blank line between test cases.