Leaving Auction

题意翻译

一场拍卖会，共n个买家。这些买家共出价n次，有的买家可能一次都没有出价。 每次出价用（ai,bi）表示，ai为此次出价人的编号，bi为价格。 出价严格递增（bi<bi+1）并且没有玩家在一轮竞拍中在没有其他竞争对手的情况下自动增加自己的出价（ai!=ai+1）。 现在给定q次查询，每次去掉一些出价者及其所有出价，问最后谁是赢家并且他以什么价格赢得拍卖品。

题目描述

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 $ (a_{i},b_{i}) $ , where $ a_{i} $ is the index of the person, who made this bid and $ b_{i} $ is its size. Bids are given in chronological order, meaning $ b_{i}&lt;b_{i+1} $ for all $ i&lt;n $ . Moreover, participant never makes two bids in a row (no one updates his own bid), i.e. $ a_{i}≠a_{i+1} $ for all $ i&lt;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.

输入输出格式

输入格式

The first line of the input contains an integer $ n $ ( $ 1<=n<=200000 $ ) — the number of participants and bids. Each of the following $ n $ lines contains two integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i}<=n,1<=b_{i}<=10^{9},b_{i}&lt;b_{i+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<=200000 $ ) — the number of question you have in mind. Each of next $ q $ lines contains an integer $ k $ ( $ 1<=k<=n $ ), followed by $ k $ integers $ l_{j} $ ( $ 1<=l_{j}<=n $ ) — the number of people who are not coming in this question and their indices. It is guarenteed that $ l_{j} $ values are different for a single question. It's guaranteed that the sum of $ k $ over all question won't exceed $ 200000 $ .

输出格式

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.

输入输出样例

输入样例 #1

6
1 10
2 100
3 1000
1 10000
2 100000
3 1000000
3
1 3
2 2 3
2 1 2

输出样例 #1

2 100000
1 10
3 1000

输入样例 #2

3
1 10
2 100
1 1000
2
2 1 2
2 2 3

输出样例 #2

0 0
1 10

说明

Consider the first sample: - In the first question participant number $ 3 $ is absent so the sequence of bids looks as follows: 1. $ 1 $ $ 10 $ 2. $ 2 $ $ 100 $ 3. $ 1 $ $ 10000 $ 4. $ 2 $ $ 100000 $ Participant number $ 2 $ wins with the bid $ 100000 $ . - In the second question participants $ 2 $ and $ 3 $ are absent, so the sequence of bids looks: 1. $ 1 $ $ 10 $ 2. $ 1 $ $ 10000 $ The winner is, of course, participant number $ 1 $ but the winning bid is $ 10 $ instead of $ 10000 $ 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: 1. $ 3 $ $ 1000 $ 2. $ 3 $ $ 1000000 $ The winner is participant $ 3 $ with the bid $ 1000 $ .

题意翻译

一场拍卖会，共n个买家。这些买家共出价n次，有的买家可能一次都没有出价。 每次出价用（ai,bi）表示，ai为此次出价人的编号，bi为价格。 出价严格递增（bi<bi+1）并且没有玩家在一轮竞拍中在没有其他竞争对手的情况下自动增加自己的出价（ai!=ai+1）。 现在给定q次查询，每次去掉一些出价者及其所有出价，问最后谁是赢家并且他以什么价格赢得拍卖品。