cf 749D Leaving Auction

Leaving Auction

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 ≤ 10⁹, 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

Output

2 100000
1 10
3 1000

Input

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. 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.
题意：拍卖一件物品，有n个竞标，一个人可以有多个竞标。给出n个竞标，a[i],b[i].a[i]表示人的序号，b[i]表示竞标价格。接下来有q个询问，每次一个k，之后k个数表示该序号的人缺席。问谁最终以多少钱得标。如果没有输出0 0，否则输出序号和价钱。
我们要按竞标价格排个序然后删除那些缺席人找到竞标价格第一大和第二大的用二分找到第一大的人中投标的价格大于第二大投标的最大价格
注意的是那个删除来找第一第二大的地方用vector超时了换成set过了

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #include<string.h>

 #include<set>

 #include<vector>

 #include<queue>

 #include<stack>

 #include<map>

 #include<cmath>

 typedef long long ll;

 typedef unsigned long long LL;

 using namespace std;

 const double PI=acos(-1.0);

 const double eps=0.0000000001;

 const int N=+;

 const ll mod=1e9+;

 const int INF=0x3f3f3f3f;

 struct node{

     int maxx=;

     int pos;

 }a[N];

 int b[N];

 vector<int>ans[N];

 set<pair<int,int> >aa,bb;

 int maxx[N];

 int vis[N];

 int check(int x,int y){

     int i=ans[y].size()-;

     int tt=ans[y][i];

     int low=;

     int high=ans[x].size()-;

     int anss=ans[x][];

     while(low<=high){

         int mid=(low+high)>>;

         if(ans[x][mid]>=tt){

             high=mid-;

             anss=ans[x][mid];

         }

         else{

             low=mid+;

         }

     }

     return anss;

 }

 int main(){

     int n;

     int x,y;

     int t=;

     cin>>n;

     memset(vis,,sizeof(vis));

    // for(int i=0;i<=n;i++)ans[i].clear();

     for(int i=;i<=n;i++){

         scanf("%d%d",&x,&y);

         a[i].maxx=y;

         a[i].pos=x;

         ans[x].push_back(y);

     }

     memset(b,,sizeof(b));

     for(int i=n;i>=;i--){

         if(vis[a[i].pos]==){

             aa.insert(make_pair(-i,a[i].pos));

             vis[a[i].pos]=i;continue;

         }

     }

     set<pair<int,int> >::iterator it;

     int q;

     scanf("%d",&q);

     //vector<int>::iterator it;

     while(q--){

         int m;

         scanf("%d",&m);

         for(int i=;i<=m;i++){

             scanf("%d",&x);

             b[i]=x;

             if(vis[x]==)continue;

             //cout<<a[vis[x]].pos<<" "<<-vis[x]<<endl;

             aa.erase(make_pair(-vis[x],a[vis[x]].pos));

         }

         if(aa.size()==){

             cout<<<<" "<<<<endl;

         }

         else if(aa.size()==){

             int t=aa.begin()->second;

             int t1=ans[t][];

             cout<<t<<" "<<t1<<endl;

         }

         else{

             int t=aa.begin()->second;

             int t1=(++aa.begin())->second;

             cout<<t<<" "<<check(t,t1)<<endl;

         }

         for(int i=;i<=m;i++){

             x=b[i];

             if(vis[x]){

                 aa.insert(make_pair(-vis[x],a[vis[x]].pos));

             }

         }

     }

 }

秒客网

cf 749D Leaving Auction

相关文章