F. Вне зоны доступа
Задачу добавил: alef
Успешно сдано решений: 5
Программист периодически посещает семинары, на которых рассказывают об обновлениях программного обеспечения, с которым он работает.
Во время очередного семинара, как обычно, очередной выступающий в очередной раз попросил всех выключить сотовые телефоны. Как обычно, никто телефон не выключил. Программисту вскоре стало немного скучно: поняв, что кардинальных обновлений в новой версии ПО не произошло, он стал наблюдать за соседями по своему ряду.
Его наблюдения оказались весьма небезынтересными. Как только кому-то из слушателей звонят на сотовый, этот кто-то сбрасывает звонок и выключает телефон.
Для того, чтобы вытащить телефон и сбросить звонок, слушателю требуется 1 единица времени, а отключает телефон слушатель мгновенно.
Если кто-то оказывается между двумя слушателями, отключившими свои сотовые телефоны, он тоже отключает телефон — спустя ровно 1 единицу времени после того, как его отключил второй из его соседей (пока телефон выключен только у одного из непосредственных соседей, это не вызывает беспокойства).
Занумеруем всех, сидящих в ряду, числами от 1 до N. Известно, что в течение семинара поступило M звонков на сотовые телефоны этих участников семинара. Для каждого звонка известно, кому он был адресован и в какой момент времени поступил.
На вход будет подано Q запросов. Запросы бывают двух видов: первый — по заданному моменту времени определить, сколько телефонов в этот момент включены; второй — по заданному номеру слушателя и моменту времени нужно определить, включен ли телефон у этого слушателя в этот момент.
В первой строке содержатся целые числа N, M и Q (1 ≤ N, M, Q ≤ 105) (через пробел — количество слушателей, количество поступивших звонков и количество запросов.
В каждой из следующих M строк содержится по два целых числа через пробел: номер слушателя и момент времени, в который на его сотовый телефон поступает звонок. Момент времени — количество единиц времени, прошедших с начала семинара.
В каждой из следующих Q строк содержится целое число 1 или 2, определяющее вид запроса, а затем собственно запрос.
Для запросов вида 1 указывается момент времени, для которого нужно определить количество включенных телефонов; для запросов вида 2 — момент времени и через пробел номер слушателя, состояние телефона которого представляет интерес.
Все моменты времени положительны и не превосходят 105.
Выведите Q строк — в каждой строке должен содержаться результат выполнения соответствующего запроса.
На запрос вида 1 выведите соответствующее число — количество включенных телефонов в этот момент времени.
На запрос вида 2 выведите число - 2, если телефон абонента выключен, и - 1 — если включен.
6 4 12
5 1
1 9
2 6
4 5
1 1
1 2
1 5
2 8 3
2 7 3
1 6
1 7
1 8
2 5 4
2 6 4
2 9 1
2 10 1
6
5
5
-2
-1
4
3
2
-1
-2
-1
-2