English · Original
Chinese · Translation
Formal · Original
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_ < _b__i_ + 1 for all _i_ < _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_ < _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
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 _a__i_ and _b__i_ (1 ≤ _a__i_ ≤ _n_, 1 ≤ _b__i_ ≤ 109, _b__i_ < _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_ ≤ 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 _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 200 000.
## Output
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.
[samples]
## Note
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 10 000
4. 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. 1 10
2. 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:
1. 3 1 000
2. 3 1 000 000
The winner is participant 3 with the bid 1 000.
今天有 #cf_span[n] 个人参加拍卖。拍卖规则是经典的。共产生了 #cf_span[n] 个出价，但不能保证它们来自不同的人。有些人可能根本没有出价。
每个出价由两个整数 #cf_span[(ai, bi)] 定义，其中 #cf_span[ai] 是出价人的编号，#cf_span[bi] 是出价金额。出价按时间顺序给出，即对所有 #cf_span[i < n] 有 #cf_span[bi < bi + 1]。此外，参与者不会连续两次出价（没有人更新自己的出价），即对所有 #cf_span[i < n] 有 #cf_span[ai ≠ ai + 1]。
现在你好奇如下问题：如果某些参与者缺席，谁（以及哪个出价）会赢得拍卖？假设如果某人缺席，他的所有出价都会被移除，且不会新增任何出价。
注意，如果在想象中排除某些参与者后，剩余参与者连续两次（或更多次）出价，则仅保留其中第一个出价。为更好理解，请参考样例。
你心中有多个问题，请为每个问题计算答案。
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200 000]) —— 参与者和出价的数量。
接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai ≤ n, 1 ≤ bi ≤ 109, bi < bi + 1]) —— 第 #cf_span[i] 个出价的参与者编号及其出价金额。
下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 200 000]) —— 你心中的问题数量。
接下来的 #cf_span[q] 行，每行包含一个整数 #cf_span[k] (#cf_span[1 ≤ k ≤ n])，后跟 #cf_span[k] 个整数 #cf_span[lj] (#cf_span[1 ≤ lj ≤ n]) —— 本次问题中缺席的人数及其编号。保证单个问题中的 #cf_span[lj] 值互不相同。
保证所有问题中 #cf_span[k] 的总和不超过 #cf_span[200 000]。
对于每个问题，请输出两个整数 —— 获胜者的编号和获胜出价的金额。如果没有获胜者（没有剩余出价），请输出两个零。
考虑第一个样例：
## Input
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200 000]) —— 参与者和出价的数量。接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai ≤ n, 1 ≤ bi ≤ 109, bi < bi + 1]) —— 第 #cf_span[i] 个出价的参与者编号及其出价金额。下一行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 200 000]) —— 你心中的问题数量。接下来的 #cf_span[q] 行，每行包含一个整数 #cf_span[k] (#cf_span[1 ≤ k ≤ n])，后跟 #cf_span[k] 个整数 #cf_span[lj] (#cf_span[1 ≤ lj ≤ n]) —— 本次问题中缺席的人数及其编号。保证单个问题中的 #cf_span[lj] 值互不相同。保证所有问题中 #cf_span[k] 的总和不超过 #cf_span[200 000]。
## Output
对于每个问题，请输出两个整数 —— 获胜者的编号和获胜出价的金额。如果没有获胜者（没有剩余出价），请输出两个零。
[samples]
## Note
考虑第一个样例：
在第一个问题中，参与者 #cf_span[3] 缺席，因此出价序列为：
#cf_span[1] #cf_span[10]
#cf_span[2] #cf_span[100]
#cf_span[1] #cf_span[10 000]
#cf_span[2] #cf_span[100 000]
参与者 #cf_span[2] 以出价 #cf_span[100 000] 获胜。
在第二个问题中，参与者 #cf_span[2] 和 #cf_span[3] 缺席，因此出价序列为：
#cf_span[1] #cf_span[10]
#cf_span[1] #cf_span[10 000]
获胜者当然是参与者 #cf_span[1]，但获胜出价是 #cf_span[10] 而非 #cf_span[10 000]，因为在本题中没有人会连续更新自己的出价。
在第三个问题中，参与者 #cf_span[1] 和 #cf_span[2] 缺席，序列为：
#cf_span[3] #cf_span[1 000]
#cf_span[3] #cf_span[1 000 000]
获胜者是参与者 #cf_span[3]，出价为 #cf_span[1 000]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of participants and bids.
Let $ B = \{(a_i, b_i)\}_{i=1}^n $ be the sequence of bids, where $ a_i \in \{1, \dots, n\} $ is the participant index and $ b_i \in \mathbb{Z}^+ $ is the bid amount, satisfying:
- $ b_i < b_{i+1} $ for all $ i \in \{1, \dots, n-1\} $,
- $ a_i \ne a_{i+1} $ for all $ i \in \{1, \dots, n-1\} $.
Let $ q \in \mathbb{Z}^+ $ be the number of queries.
For each query $ j \in \{1, \dots, q\} $, let $ S_j \subseteq \{1, \dots, n\} $ be the set of absent participants, with $ |S_j| = k_j $.
**Constraints**
1. $ 1 \le n \le 200{,}000 $
2. $ 1 \le q \le 200{,}000 $
3. For each query $ j $: $ 1 \le k_j \le n $, and $ S_j $ consists of distinct integers in $ \{1, \dots, n\} $
4. $ \sum_{j=1}^q k_j \le 200{,}000 $
**Objective**
For each query $ j $:
- Remove all bids $ (a_i, b_i) $ such that $ a_i \in S_j $.
- From the remaining bid sequence, eliminate consecutive bids by the same participant, keeping only the first of each run.
- Among the resulting sequence of bids, identify the bid with the maximum amount.
- Output the participant index and bid amount of this winning bid.
- If no bids remain, output $ (0, 0) $.
API Response (JSON)
{
"problem": {
"name": "D. Leaving Auction",
"description": {
"content": "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 p",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF749D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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 p...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "今天有 #cf_span[n] 个人参加拍卖。拍卖规则是经典的。共产生了 #cf_span[n] 个出价，但不能保证它们来自不同的人。有些人可能根本没有出价。\n\n每个出价由两个整数 #cf_span[(ai, bi)] 定义，其中 #cf_span[ai] 是出价人的编号，#cf_span[bi] 是出价金额。出价按时间顺序给出，即对所有 #cf_span[i < n] 有 #cf_span[bi...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of participants and bids. \nLet $ B = \\{(a_i, b_i)\\}_{i=1}^n $ be the sequence of bids, where $ a_i \\in \\{1, \\dots, n\\} $ is the participant ...",
"is_translate": false,
"language": "Formal"
}
]
}