Сафарі-парк
Ви коли-небудь відвідували сафарі-парк? Це місце, схоже на зоопарк, але тут тварини не утримуються в клітках. Відвідувачі можуть проїжджати або проходити через парк, спостерігаючи за тваринами в їхньому природному середовищі. Навіть такі небезпечні тварини, як леви та тигри, перебувають на волі. Я теж відкрив свій сафарі-парк, де тварини живуть в окремих регіонах. Для безпеки регіони не перетинаються, хоча можуть мати спільні межі. Тварини навчені не покидати свої території. Парк став настільки великим, що одна карта не може охопити всю територію. Тому я вирішив створити пристрій, який допоможе відвідувачам знаходити цікаві для них місця. Щоб знизити вартість, я придбав недорогі моделі з обмеженою пам'яттю. Для спрощення всі регіони зроблені трикутними. Регіони завантажуються залежно від місцезнаходження відвідувача, який може пересуватися парком на монорейці. Пристрій показує регіони, але не відображає мітки. Щоб дізнатися мітку регіону, потрібно ввести координати точки. Існують дві спеціальні мітки: 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 надрукуйте відповідь на запит. Не друкуйте порожній рядок між тестовими випадками. Дотримуйтесь прикладу вводу і виводу для деталей.