Задача №111994. Поле боя
Сегодня в длительной и непримиримой войне между Аарляндией и Берляндией происходит ключевая битва. Командование армии Берляндии собралось в штабе перед специальным радаром, чтобы следить за сражением. Радар показывает неуничтоженные боевые единицы (и их координаты), которые в данный момент находятся на поле боя.
К сожалению, радар этот не очень хорош. Боевые единицы на нем могут исчезать и появляться вновь на том же месте. К тому же, радар не показывает принадлежность боевых единиц армиям (то есть непонятно, свой ли это солдат или чужой). Командование знает порядок событий вида:
- боевая единица возникла на радаре в точке (x, y);
- боевая единица исчезла с радара из точки (x, y).
В общей неразберихе боя командование армии Берляндии с помощью радара иногда пытается понять, где в данный момент находится линия фронта (это нужно для планирования дальнейших боевых действий). Исходя из соображения о том, что силы примерно равны, командование полагает, что линия фронта — это вертикальная прямая вида 
(a — неотрицательное целое число), такая, что количество боевых единиц слева от этой прямой строго равно количеству боевых единиц справа от этой прямой, и a максимально (то есть, если возможных линий фронта существует несколько, руководство хочет знать самую правую из них).
Помогите командованию армии не проиграть эту битву. Напишите программу, которая будет сообщать линию фронта для текущей ситуации на поле боя, когда этого требует руководство армии Берляндии.
В первой строке вводится одно целое число n — количество событий (1 ≤ n ≤ 106).
В следующих n строках вводятся описания событий трех видов.
- «A x y» — боевая единица возникла на радаре в точке с целочисленными координатами x, y (1 ≤ x, y ≤ 109).
- «D x y» — боевая единица исчезла с радара из точки с целочисленными координатами x, y (1 ≤ x, y ≤ 109). Гарантируется, что до этого запроса в этой точке на радаре была боевая единица.
- «Q» — командование Берляндии захотело узнать текущую линию фронта.
Для каждого события вида «Q» выведите в отдельной строке максимальное неотрицательное целое a такое, что прямая — это линия фронта. В случае, если линии фронта не существует, или существует бесконечно много вариантов провести линию фронта, выведите «-1».
12
A 1 1
A 2 1
Q
A 2 2
A 3 1
Q
A 4 1
A 5 1
Q
D 1 1
D 5 1
Q
1
-1
2
2
- Решения, корректно работающие при x, y ≤ 10, будут оцениваться не менее чем 32 баллами.
- Решения, корректно работающие при x, y ≤ 100, будут оцениваться не менее чем 44 баллами.
- Решения, корректно работающие при x, y ≤ 1 000 000, будут оцениваться не менее чем 80 баллами.