Codeforces Round 388 (Div. 2) |
---|
Закончено |
Сегодня проходит аукцион, в котором принимают участие 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.
Для каждого запроса выведите два числа в одной строке через пробел — номер победителя и величину его ставки. Если победитель отсутствует (то есть не было сделано ни одной ставки), выведите два нуля.
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
3
1 10
2 100
1 1000
2
2 1 2
2 2 3
0 0
1 10
Пояснение к первому примеру:
Название |
---|