题目链接：
题意：n个二元组（x，y）。一个集合S，初始时S中只有一个元素K。对于二元组中的元素若满足x=sigama(ki*Si)(1<=i<=M，M为S中的元素个数，Si为S中的元素，Ki为非负整数），则将这个二元组放入集合Q中。三种操作：（1）将S中增加一个元素a；（2）将原来n个二元组中的第t个二元组的y值减小det；（3）查询Q集合中y值最大的二元组，输出其y值并将其删除。
思路：对于在Q集合中的元素，我们只需要维护查找和删除，线段树可以维护。然后最重要的是找出n个二元组哪些在Q集合中。由于S中只有K比较小，而a的值较大，我们将所有的二元组按照其x%K分成K组[0,K-1]。对于S中的所有元素，计算出一个d数组。d[i]（0<=i<=K-1）表示对于所有模K为i的数字x，最小可以表示的是d[i]*K+i。显然对于比d[i]*K+i大而且模K等于i的我们加若干个K即可。计算这个d数组使用SPFA。首先将1进队，然后每次出队元素为u，枚举S中的每一个元素（K除外）Si，设x=(u+Si)/K,y=(u+Si)%K，则d[y]=min(d[y],d[u]+x)。
struct node{ int L,R,mid,Max;};node a[N<<2];int b[N],c[N];vector<int> V[N];int n,m,K;i64 h,pos[N],p[N],cnt,d[N];void Add(i64 t){ p[cnt++]=t; clr(d,-1); int h[N]={0},i,j,u,v; i64 x,y; queue<int> Q; Q.push(1); d[1]=0; while(!Q.empty()) { u=Q.front(); Q.pop(); h[u]=0; FOR0(i,cnt) { x=(u+p[i])/K; y=(u+p[i])%K; if(d[y]==-1||d[y]>d[u]+x) { d[y]=d[u]+x; if(!h[y]) Q.push(y); } } } clr(b,0); FOR0(i,K) if(d[i]!=-1) FOR0(j,SZ(V[i])) { u=V[i][j]; if(pos[u]>=d[i]*K+i) b[u]=1; }}void pushUp(int t){ a[t].Max=max(a[t*2].Max,a[t*2+1].Max);}void build(int t,int L,int R){ a[t].L=L; a[t].R=R; a[t].mid=(L+R)>>1; if(L==R) { if(!b[L]) a[t].Max=-1; else a[t].Max=c[L]; return; } build(t*2,L,a[t].mid); build(t*2+1,a[t].mid+1,R); pushUp(t);}void update(int t,int x,int y){ if(a[t].L==a[t].R) { a[t].Max-=y; c[x]-=y; return; } if(x<=a[t].mid) update(t*2,x,y); else update(t*2+1,x,y); pushUp(t);}void modify(int t,int x){ if(a[t].L==a[t].R) { a[t].Max=0; c[a[t].L]=0; return; } if(a[t*2].Max==x) modify(t*2,x); else modify(t*2+1,x); pushUp(t);}int main(){ RD(h); RD(n,m,K); int i; FOR1(i,n) { RD(pos[i]),RD(c[i]); V[pos[i]%K].pb(i); if(pos[i]%K==1) b[i]=1; } build(1,1,n); int op,x,y; i64 A; while(m--) { RD(op); if(op==1) { RD(A); Add(A); build(1,1,n); } else if(op==2) { RD(x,y); update(1,x,y); } else { if(a[1].Max<=0) puts("0"); else PR(a[1].Max),modify(1,a[1].Max); } }}