今天有 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。