本文共 5514 字，大约阅读时间需要 18 分钟。

Serge came to the school dining room and discovered that there is a big queue here. There are mm pupils in the queue. He’s not sure now if he wants to wait until the queue will clear, so he wants to know which dish he will receive if he does. As Serge is very tired, he asks you to compute it instead of him.

Initially there are nn dishes with costs a1,a2,…,ana1,a2,…,an. As you already know, there are the queue of mm pupils who have b1,…,bmb1,…,bm togrogs respectively (pupils are enumerated by queue order, i.e the first pupil in the queue has b1b1 togrogs and the last one has bmbm togrogs)

Pupils think that the most expensive dish is the most delicious one, so every pupil just buys the most expensive dish for which he has money (every dish has a single copy, so when a pupil has bought it nobody can buy it later), and if a pupil doesn’t have money for any dish, he just leaves the queue (so brutal capitalism…)

But money isn’t a problem at all for Serge, so Serge is buying the most expensive dish if there is at least one remaining.

Moreover, Serge’s school has a very unstable economic situation and the costs of some dishes or number of togrogs of some pupils can change. More formally, you must process qq queries:

change aiai to xx. It means that the price of the ii-th dish becomes xx togrogs.

change bibi to xx. It means that the ii-th pupil in the queue has xx togrogs now. Nobody leaves the queue during those queries because a saleswoman is late.

After every query, you must tell Serge price of the dish which he will buy if he has waited until the queue is clear, or −1−1 if there are no dishes at this point, according to rules described above.

Input

The first line contains integers nn and mm (1≤n,m≤300 0001≤n,m≤300 000) — number of dishes and pupils respectively. The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1061≤ai≤106) — elements of array aa. The third line contains mm integers b1,b2,…,bmb1,b2,…,bm (1≤bi≤1061≤bi≤106) — elements of array bb. The fourth line conatins integer qq (1≤q≤300 0001≤q≤300 000) — number of queries.

Each of the following qq lines contains as follows:

if a query changes price of some dish, it contains 11, and two integers ii and xx (1≤i≤n1≤i≤n, 1≤x≤1061≤x≤106), what means aiai becomes xx.

if a query changes number of togrogs of some pupil, it contains 22, and two integers ii and xx (1≤i≤m1≤i≤m, 1≤x≤1061≤x≤106), what means bibi becomes xx. Output For each of qq queries prints the answer as the statement describes, the answer of the ii-th query in the ii-th line (the price of the dish which Serge will buy or −1−1 if nothing remains)

Examples

Input 1 1 1 1 1 1 1 100 Output 100 Input 1 1 1 1 1 2 1 100 Output -1 Input 4 6 1 8 2 4 3 3 6 1 5 2 3 1 1 1 2 5 10 1 1 6 Output 8 -1 4 Note In the first sample after the first query, there is one dish with price 100100 togrogs and one pupil with one togrog, so Serge will buy the dish with price 100100 togrogs.

In the second sample after the first query, there is one dish with price one togrog and one pupil with 100100 togrogs, so Serge will get nothing.

In the third sample after the first query, nobody can buy the dish with price 88, so Serge will take it. After the second query, all dishes will be bought, after the third one the third and fifth pupils will by the first and the second dishes respectively and nobody will by the fourth one.

挺奇特的一道题。 题意：n个人买m种菜，每种菜的价格是a[i]，每个人手中有b[i]钱。每个人必须买他能买的起的最贵的菜，问m个人买完了之后还剩下菜的最大价格是多少。还有两种操作，1操作就改变菜的价格，2操作时改变人手中拿的钱的数量。 思路：要是按着题意模拟的话，必tle无疑。对于这种中途改变的操作，线段树就可以做。怎么用线段树维护呢。首先排队的顺序和最后的结果是没有关系的。如果说最后的价格是x的话，那么拥有超过x钱的人数绝对小于菜的价格是x的人数。这样的话，我们按着价值建一棵权值线段树。对于菜的钱数a[i]，我们把1~a[i]位置全都+1，对于每个人拥有的钱数b[i],我们就在1 ~b[i]上都-1.这样相当于维护了一个前缀和。对于线段树上价值大于0的节点，就代表着当前那些人买不了这些价值的菜。当然有的菜的价格是不存在的。那么哪一个节点的价格是存在的呢，就最右边价值大于0的节点。因为一开始更新的时候，就是在1 ~a[i]上+1的。a[i]是右端点。所以在线段树上维护最大值，在找的时候，二分去找，优先找右边的。 代码如下：

#include
   
    #define ll long longusing namespace std;const int maxx=1e6+100;const int maxn=3e5+100;struct node{
   	int l;	int r;	int lazy;	int sum;}p[maxx<<2];int a[maxx],b[maxx];int n,m,q;inline void pushup(int cur){
   	p[cur].sum=max(p[cur<<1].sum,p[cur<<1|1].sum);}inline void pushdown(int cur)//区间更新，延迟标记{
   	if(p[cur].lazy)	{
   		p[cur<<1].sum+=p[cur].lazy;		p[cur<<1|1].sum+=p[cur].lazy;		p[cur<<1].lazy+=p[cur].lazy;		p[cur<<1|1].lazy+=p[cur].lazy;		p[cur].lazy=0;	}}inline void build(int l,int r,int cur){
   	p[cur].l=l;	p[cur].r=r;	p[cur].sum=0;	p[cur].lazy=0;	if(l==r) return ;	int mid=l+r>>1;	build(l,mid,cur<<1);	build(mid+1,r,cur<<1|1);}inline void update(int l,int r,int v,int cur){
   	int L=p[cur].l;	int R=p[cur].r;	if(l<=L&&R<=r)	{
   		p[cur].sum+=v;		p[cur].lazy+=v;		return ;	}	pushdown(cur);	int mid=L+R>>1;	if(r<=mid) update(l,r,v,cur<<1);	else if(l>mid) update(l,r,v,cur<<1|1);	else	{
   		update(l,mid,v,cur<<1);		update(mid+1,r,v,cur<<1|1);	}	pushup(cur);}inline int query(int cur){
   	int L=p[cur].l;	int R=p[cur].r;	if(L==R) return L;	pushdown(cur);	if(p[cur<<1|1].sum>0) return query(cur<<1|1);	else if(p[cur<<1].sum>0) return query(cur<<1);}int main(){
   	int op,x,y;	while(~scanf("%d%d",&n,&m))	{
   		build(1,maxx,1);		for(int i=1;i<=n;i++) scanf("%d",&a[i]),update(1,a[i],1,1);		for(int i=1;i<=m;i++) scanf("%d",&b[i]),update(1,b[i],-1,1);		scanf("%d",&q);		while(q--)		{
   			scanf("%d%d%d",&op,&x,&y);			if(op==1) update(1,a[x],-1,1),update(1,a[x]=y,1,1);//先将之前的更新抹掉，在将新的标记			else if(op==2) update(1,b[x],1,1),update(1,b[x]=y,-1,1);			if(p[1].sum<=0) printf("-1\n");			else printf("%d\n",query(1));		}	}	return 0;}
   

努力加油a啊，(^o)/~

转载地址：http://cktvi.baihongyu.com/