Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






F. Вне зоны доступа

Задачу добавил: alef

Успешно сдано решений: 5

ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

Программист периодически посещает семинары, на которых рассказывают об обновлениях программного обеспечения, с которым он работает.

Во время очередного семинара, как обычно, очередной выступающий в очередной раз попросил всех выключить сотовые телефоны. Как обычно, никто телефон не выключил. Программисту вскоре стало немного скучно: поняв, что кардинальных обновлений в новой версии ПО не произошло, он стал наблюдать за соседями по своему ряду.

Его наблюдения оказались весьма небезынтересными. Как только кому-то из слушателей звонят на сотовый, этот кто-то сбрасывает звонок и выключает телефон.

Для того, чтобы вытащить телефон и сбросить звонок, слушателю требуется 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

Сдать задачу

Задать вопрос жюри по этой задаче