Олимпиадный тренинг

Задача . D. Побег с аукциона


Задача

Темы: Бинарный поиск Структуры данных *2000

Сегодня проходит аукцион, в котором принимают участие n человек. Аукцион проходит по классическим правилам. Известно, что было сделано n ставок, при этом не гарантируется, что каждая ставка была сделана уникальным участником, то есть какие-то участники могли и вовсе не делать ставок.

Каждая ставка определяется парой целых чисел (ai, bi), где ai — номер участника, сделавшего ставку, а bi — величина ставки. Все ставки даны в хронологическом порядке, то есть bi < bi + 1 для всех i < n. Кроме того, ни один из участников не делал две ставки подряд (не перебивал свою ставку), то есть ai ≠ ai + 1 для всех i < n.

Из праздного любопытства вы заинтересовались следующим вопросом: кто и с какой ставкой выиграет в аукционе, если бы некоторые из участников на самом деле отсутствовали? При этом считается, что этих участников и их ставок просто не было, а среди оставшихся участников новых ставок не появится.

Обратите внимание, что если после мысленного вычёркивания каких-либо участников получится ситуация, когда кто-то перебивает свою ставку, то необходимо считать, что этого не происходит и из серии последовательных ставок одного и того же человека останется только первая. Для лучшего понимания, посмотрите примеры.

У вас есть несколько подобных предположений, вычислите ответ для каждого из них.

Входные данные

В первой строке дано число n (1 ≤ n ≤ 200 000) — количество участников аукциона и сделанных ставок.

В следующих n строках расположены по два числа ai и bi (1 ≤ ai ≤ n, 1 ≤ bi ≤ 109, bi < bi + 1) — номер участника, сделавшего i-ю ставку, и размер этой ставки.

В следующей строке дано число q (1 ≤ q ≤ 200 000) — количество запросов.

В каждой из следующих q строк дано число k (1 ≤ k ≤ n), а затем k чисел lj (1 ≤ lj ≤ n) — количество отсутствующих участников, и их номера. Все номера в пределах одного запроса различны.

Гарантируется, что сумма всех k во всех запросах не превосходит 200 000.

Выходные данные

Для каждого запроса выведите два числа в одной строке через пробел — номер победителя и величину его ставки. Если победитель отсутствует (то есть не было сделано ни одной ставки), выведите два нуля.

Примечание

Пояснение к первому примеру:

  • В первом запросе отсутствует только участник с номером 3, тогда последовательность ставок будет выглядеть следующим образом:
    1. 1 10
    2. 2 100
    3. 1 10 000
    4. 2 100 000
    В такой ситуации побеждает участник с номером 2, при этом его ставка составляет 100 000.
  • Во втором запросе отсутствуют участники 2 и 3, тогда последовательность ставок будет выглядеть следующим образом:
    1. 1 10
    2. 1 10 000
    Здесь победил участник с номером 1, но поскольку участнику не выгодно перебивать свою ставку, то выигрышной ставкой является 10, а не 10 000.
  • В третьем запросе отсутствуют участники 1 и 2, тогда последовательность ставок будет выглядеть следующим образом:
    1. 3 1 000
    2. 3 1 000 000
    Побеждает участник 3 со ставкой 1 000.

Примеры
№Входные данныеВыходные данные
1 6
1 10
2 100
3 1000
1 10000
2 100000
3 1000000
3
1 3
2 2 3
2 1 2 
2 100000
1 10
3 1000
2 3
1 10
2 100
1 1000
2
2 1 2
2 2 3 
0 0
1 10

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет