Leaving Auction
Contest: Codeforces Round 388 (Div. 2)
Difficulty rating: 2000
Tags: binary search, data structures

There are n people taking part in auction today. The rules of auction are classical. There were n bids made, though it's not guaranteed they were from different people. It might happen that some people made no bids at all.

Each bid is define by two integers (ai, bi), where ai is the index of the person, who made this bid and bi is its size. Bids are given in chronological order, meaning bi < bi + 1 for all i < n. Moreover, participant never makes two bids in a row (no one updates his own bid), i.e. ai ≠ ai + 1 for all i < n.

Now you are curious with the following question: who (and which bid) will win the auction if some participants were absent? Consider that if someone was absent, all his bids are just removed and no new bids are added.

Note, that if during this imaginary exclusion of some participants it happens that some of the remaining participants makes a bid twice (or more times) in a row, only first of these bids is counted. For better understanding take a look at the samples.

You have several questions in your mind, compute the answer for each of them.

Input format:
The first line of the input contains an integer n (1 ≤ n ≤ 200 000) — the number of participants and bids.

Each of the following n lines contains two integers ai and bi (1 ≤ ai ≤ n, 1 ≤ bi ≤ 109, bi < bi + 1) — the number of participant who made the i-th bid and the size of this bid.

Next line contains an integer q (1 ≤ q ≤ 200 000) — the number of question you have in mind.

Each of next q lines contains an integer k (1 ≤ k ≤ n), followed by k integers lj (1 ≤ lj ≤ n) — the number of people who are not coming in this question and their indices. It is guarenteed that lj values are different for a single question.

It's guaranteed that the sum of k over all question won't exceed 200 000.

Output format:
For each question print two integer — the index of the winner and the size of the winning bid. If there is no winner (there are no remaining bids at all), print two zeroes.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Consider the first sample:

- In the first question participant number 3 is absent so the sequence of bids looks as follows:   1 10  2 100  1 10 000  2 100 000  Participant number 2 wins with the bid 100 000.
- In the second question participants 2 and 3 are absent, so the sequence of bids looks:   1 10  1 10 000  The winner is, of course, participant number 1 but the winning bid is 10 instead of 10 000 as no one will ever increase his own bid (in this problem).
- In the third question participants 1 and 2 are absent and the sequence is:   3 1 000  3 1 000 000  The winner is participant 3 with the bid 1 000.

Example input:
6
1 10
2 100
3 1000
1 10000
2 100000
3 1000000
3
1 3
2 2 3
2 1 2

Example output:
2 100000
1 10
3 1000

Example input:
3
1 10
2 100
1 1000
2
2 1 2
2 2 3

Example output:
0 0
1 10

Editorial:
For every man at the auction we will save two values: his maximum bid and the list of all his bids. Then save all men in the set sorted by the maximal bid.
Now, when the query comes, we will remove from the set all men who left the auction, then answer the query, and then add the men back. The total number of deletions and insertions will not exceed 200000.
How to answer the query. Now our set contains only men who has not left.
• If the set is empty, the answer is 0 0. Otherwise, the maximal man in the set is the winner. Now we have to determine the winning bid. Let’s look at the second maximal man in the set.
• If it doesn’t exist, the winner takes part solo and wins with his minimal bid.
• Otherwise he should bid the minimal value that is greater than the maximal bid of the second man in the set. This is where we need a list of bids of the first maximal man. We can apply binary search and find the maximal bid of the second man there.