Сафари-парк
Вы когда-нибудь бывали в сафари-парке? Это место, напоминающее зоопарк, но здесь животные не содержатся в клетках. Посетители могут проезжать или проходить через парк, наблюдая за животными в естественной среде. Даже такие опасные животные, как львы и тигры, находятся на свободе. Я тоже открыл свой сафари-парк, где животные живут в отдельных регионах. Для безопасности регионы не пересекаются, хотя могут иметь общие границы. Животные обучены не покидать свои территории. Парк стал настолько большим, что одна карта не может охватить всю территорию. Поэтому я решил создать устройство, которое поможет посетителям находить интересующие их места. Чтобы снизить стоимость, я приобрел недорогие модели с ограниченной памятью. Для упрощения все регионы сделаны треугольными. Регионы загружаются в зависимости от местоположения посетителя, который может перемещаться по парку на монорельсе. Устройство показывает регионы, но не отображает метки. Чтобы узнать метку региона, нужно ввести координаты точки. Существуют две специальные метки: 0 — точка вне региона, -1 — точка на границе или углу.
Например, предположим, что известно о двух регионах: Жираф: (0, 0), (0, 5), (5, 0) и Дельфин: (10, 10), (10, 5), (5, 10). Если запросить координаты (1, 1), будет показан Жираф. Если запросить (9, 9), ответ будет Дельфин. Однако, если запросить (5, 5), будет показано 0. Теперь предположим, что на карте появляется новый регион: Лев: (4, 6), (6, 4), (4, 4). Если снова запросить (5, 5), ответ будет -1.
Итак, вам будут даны некоторые треугольники. Треугольники могут иметь общие стороны и углы, но ни один треугольник не будет иметь свой угол на стороне другого треугольника. Стороны разных треугольников могут совпадать, но не частично перекрываться. Вы можете обратиться к следующей диаграмме для ясности:
Ни у каких двух треугольников не будет общей области. Если точка запроса строго внутри региона, вы должны напечатать его метку. Если точка строго вне всех регионов, напечатайте 0. Если точка на границе или углу, напечатайте -1. Подробности ввода и вывода приведены в соответствующем разделе.
Входные данные
Первая строка тестового файла содержит положительное целое число T (T ≤ 2), обозначающее количество тестовых случаев. Первая строка каждого случая содержит N (N ≤ 300000), обозначающее количество команд. Каждая команда начинается с Q или R. Q обозначает запрос, а R обозначает регион. Q сопровождается 2 целыми числами: x_q и y_q. R сопровождается 6 целыми числами: x_1 y_1 x_2 y_2 x_3 y_3. Эти числа не являются реальными координатами. Вы должны декодировать их, используя ответ на последний запрос. Предположим, d — это ответ на последний запрос Q (изначально d = 0), тогда реальные координаты x, y будут: x + x_1[d], y + y_1[d]. Здесь x_1[d], y_1[d] — это первая координата (декодированная) d-го региона. d-й регион — это регион, предоставленный d-й командой R.
Если d = 0 или -1 (в случае нахождения вне региона или на границе/углу), считайте x_1[d] = y_1[d] = 0. Запрос должен быть отвечен с учетом только регионов, предоставленных до соответствующей команды Q. Если перед командой Q есть n R команд, то ответ на этот запрос будет варьироваться от -1 до n, -1 если на границе/углу, 0 если вне какого-либо региона и другое число в зависимости от региона, в котором находится точка. Координаты регионов всегда будут в порядке по часовой стрелке. Регионы могут появляться в случайном порядке, даже если сами регионы не случайны. Значение декодированных координат x y неотрицательно и ограничено 100000.
Выходные данные
Для каждого тестового случая сначала напечатайте номер случая. Затем для каждой команды Q напечатайте ответ на запрос. Не печатайте пустую строку между тестовыми случаями. Следуйте примеру ввода и вывода для подробностей.