Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Leaving Auction

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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} ≤ 10^{9}, *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.

Examples

Input

6

1 10

2 100

3 1000

1 10000

2 100000

3 1000000

3

1 3

2 2 3

2 1 2

Output

2 100000

1 10

3 1000

Input

3

1 10

2 100

1 1000

2

2 1 2

2 2 3

Output

0 0

1 10

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

- In the second question participants 2 and 3 are absent, so the sequence of bids looks:
- 1 10
- 1 10 000

- In the third question participants 1 and 2 are absent and the sequence is:
- 3 1 000
- 3 1 000 000

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 18:38:29 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|