← 返回题目列表

Codeforces · 749/D

D. 离开拍卖

中文机器翻译题面 查看原题

今天有 n 人参加拍卖。拍卖规则是经典的。有 n 个出价,但不能保证它们来自不同的人。可能会发生有些人根本没有出价的情况。

每个出价由两个整数 (ai, bi) 定义,其中 ai 是发出此出价的人的索引,bi 是其大小。出价按时间顺序给出,即对于所有 i < n,bi < bi + 1。此外,参与者永远不会连续两次出价(没有人更新自己的出价),即,对于所有 i < n,ai ≠ ai + 1。

现在您对以下问题感到好奇:如果某些参与者缺席,谁(以及哪个出价)将赢得拍卖?考虑一下,如果有人缺席,则他的所有出价都会被删除,并且不会添加新的出价。

请注意,如果在排除某些参与者的过程中,某些剩余参与者连续两次(或多次)出价,则仅计算这些出价中的第一个。为了更好地理解,请查看示例。

你脑子里有几个问题,计算每个问题的答案。

输入

输入的第一行包含一个整数 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) - 未参与此问题的人数及其索引。保证单个问题的 lj 值是不同的。

保证所有问题的 k 总和不超过 200 000。

输出

对于每个问题,打印两个整数 - 获胜者的索引和获胜出价的大小。如果没有获胜者(根本没有剩余的出价),则打印两个零。

示例

输入 #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

注意

考虑第一个样本:

- 在第一个问题中,3 号参与者缺席,因此出价顺序如下: 1 10 2 100 1 10 000 2 100 000 2 号参与者以出价 100 000 获胜。
- 在第二个问题中,参与者 2 和 3 缺席,因此出价顺序如下: 1 10 1 10 000 当然,获胜者是 1 号参与者,但中标出价是 10,而不是 10 000,因为没有人会提高自己的出价(在本问题中)。
- 在第三个问题中,参与者 1 和 2 缺席,顺序为: 3 1 000 3 1 000 000 获胜者是出价为 1 000 的参与者 3。