#include<map>#include<cstdio>#include<string>#include<string.h>#include<iostream>#include<algorithm>using namespace std;int d[123456];char ty[123456][20];int n,m;//... int main(){    freopen("toy.in","r",stdin);    freopen("toy.out","w",stdout);    scanf("%d %d",&n,&m);    for(int i=0;i<n;i++)scanf("%d%s",d+i,ty[i]);    //for(int i=1;i<=n;i++)d[i]=d[i]?1:-1;    int now=0;    while(m--){        int op,s;        scanf("%d %d",&op,&s);        if(!d[now]){            if(op)now=(now+s)%n;            else now=((now-s)%n+n)%n;            }else{            if(op)now=((now-s)%n+n)%n;            else now=(now+s)%n;        }    }    cout<<ty[now];    return 0;}

#include<map>#include<cstdio>#include<string>#include<vector>#include<string.h>#include<iostream>#include<algorithm>using namespace std;struct edge{    int to,next;}e[601234];int cnt,last[301234],dep[301234],w[301234],ans[301234];int n,m;int s[301234],t[301234];void insert(int a,int b){    e[++cnt]=(edge){b,last[a]};last[a]=cnt;    e[++cnt]=(edge){a,last[b]};last[b]=cnt;}int fa[301234][20];void dfs(int v,int f){    //fa[v][0]=f;    //for(int i=1;i<=20;i++)fa[v][i]=fa[fa[v][i-1]][i-1];    for(int i=last[v];i;i=e[i].next){        int b=e[i].to;if(b!=f){            dep[b]=dep[v]+1;            dfs(b,v);        }    }}int an[301234];void dfs2(int v,int t,int f){    fa[v][0]=f;    //for(int i=1;i<=20;i++)fa[v][i]=fa[fa[v][i-1]][i-1];    for(int i=last[v];i;i=e[i].next){        int b=e[i].to;if(b!=f){            dfs2(b,t,v);            if(b==t){                an[v]=i;            }            if(an[b]){                an[v]=i;            }        }    }}void dfs3(int s,int t){    int v=s,ti=0;    ans[s]+=(ti==w[s]);    while(s!=t){        s=e[an[s]].to;        ++ti;        ans[s]+=(ti==w[s]);    }}int siz[301234];void dfs4(int v,int f){    //fa[v][0]=f;    //for(int i=1;i<=20;i++)fa[v][i]=fa[fa[v][i-1]][i-1];    for(int i=last[v];i;i=e[i].next){        int b=e[i].to;if(b!=f){            dep[b]=dep[v]+1;            dfs4(b,v);            siz[v]+=siz[b];            //fprintf(stderr,"Debug (%d)=%d\n",v,siz[v]);        }    }}vector<int>vec[301234];int main(){    freopen("running.in","r",stdin);    freopen("running.out","w",stdout);    scanf("%d %d",&n,&m);    for(int i=1,u,v;i<n;i++){        scanf("%d %d",&u,&v);        insert(u,v);    }    //dfs(1,0);    for(int i=1;i<=n;i++)scanf("%d",w+i);    for(int i=1;i<=m;i++)scanf("%d %d",s+i,t+i);    if(n<=1000){        for(int i=1;i<=m;i++){            memset(an,0,sizeof(an));            dfs2(s[i],t[i],0);            dfs3(s[i],t[i]);        }        for(int i=1;i<=n;i++)printf("%d ",ans[i]);    }else    if(n%10==4){        for(int i=1;i<=n;i++)if(t[i]>=s[i])vec[i].push_back(s[i]);        for(int i=1;i<=n;i++){            if(i-w[i]>=0){                int Ans=vec[i-w[i]].size(),cnt=0;                for(int x=0;x<Ans;x++){                    if(t[vec[i-w[i]][x]]<i)cnt++;                }                ans[i]+=(Ans-cnt);            }        }                //for(int i=1;i<=n;i++)printf("%d ",ans[i]);        for(int i=1;i<=n;i++)vec[i].clear();        for(int i=1;i<=n;i++)if(t[i]<s[i])vec[i].push_back(s[i]);        for(int i=1;i<=n;i++){            if(i+w[i]<=n){                int Ans=vec[i+w[i]].size(),cnt=0;                //fprintf(stderr,"at %d\n",Ans);                for(int x=0;x<Ans;x++){                    if(t[vec[i+w[i]][x]]>i){                        cnt++;                    }                }                ans[i]+=(Ans-cnt);            }        }        for(int i=1;i<=n;i++)printf("%d ",ans[i]);    }else {        for(int i=1;i<=n;i++)siz[t[i]]++;        dep[1]=0;         dfs4(1,0);        for(int i=1;i<=n;i++)printf("%d ",(w[i]==dep[i])*siz[i]);    }    return 0;//... //... //... }

#include<map>#include<cstdio>#include<string>#include<vector>#include<string.h>#include<iostream>#include<algorithm>using namespace std;int n,m,v,e;int c[333],d[333];double k[333];/*int min(int a,int b){    return a<b?a:b;}*/struct zy{    int i,cost;}F[1234];bool cmp(zy a,zy b){    return a.cost>b.cost;}double brutef(){    double ans=1e23;    int _F=0;    for(int i=1;i<=n;i++){        int tmp=0;        if(tmp>1)tmp=tmp+g[c[i-1]][c[i]]-g[c[i-1]][d[i]];        if(tmp<n)tmp=tmp+g[c[i+1]][c[i]]-g[c[i+1]][d[i]];        F[++_F]=(zy){i,-tmp};    }    sort(F+1,F+_F+1,cmp);    int q[1234];    memset(q,0,sizeof(q));    for(int i=0;i<=m;i++){        q[F[i].i]=1;double tmp2=0;        for(int t=1;t<n;t++){            int a=c[t],b=c[t+1];            if(q[t])a=d[t];            if(q[t+1])b=d[t+1];            tmp2+=g[a][b];        }        //cout<<F[i].i<<","<<tmp2<<endl;        ans=min(ans,tmp2);    }    return ans;}int main() {    freopen("classroom.in","r",stdin);    freopen("classroom.out","w",stdout);    scanf("%d%d%d%d",&n,&m,&v,&e);    for(int i=1;i<=n;i++)scanf("%d",c+i);    for(int i=1;i<=n;i++)scanf("%d",d+i);    bool xz2=1;    for(int i=1;i<=n;i++)scanf("%lf",k+i),xz2=xz2&&(k[i]==1.0);        for(int i=1;i<=v;i++)for(int j=1;j<=v;j++)g[i][j]=(i!=j)*(1<<20);    for(int i=1;i<=e;i++){        int a,b,w;        scanf("%d %d %d",&a,&b,&w);        g[a][b]=min(g[a][b],w);        g[b][a]=min(g[b][a],w);    }        for(int p=1;p<=v;p++)for(int i=1;i<=v;i++)for(int j=1;j<=v;j++)g[i][j]=min(g[i][j],g[i][p]+g[p][j]);    if(m<2){        double ans=0,tmp=0;        for(int i=1;i<n;i++){            ans+=(g[c[i]][c[i+1]]);        }        tmp=ans;        if(m)        for(int x=1;x<=n;x++){            //cout<<x<<" :\n";            int res=0;            for(int i=1;i<n;i++){                int a=c[i],b=c[i+1];                if(i==x)a=d[x];                if(i+1==x)b=d[x];                res+=g[a][b];                            }            //cout<<res*k[x]+tmp*(1-k[x])<<endl;            ans=min(ans,res*k[x]+tmp*(1-k[x]));        }        printf("%.2lf",(double)ans);    }else if(n<=20&&m<=10){        double ans=1e23;        for(int i=0;i<(1<<n);i++){            int p[30],q[33],cnt=0;            for(int j=1;j<=n;j++)if(i&(1<<(j-1)))q[++cnt]=j;            if(cnt<=m){            //cerr<<"safe";            memset(p,0,sizeof(p));                double tmp=0;                for(int j=0;j<(1<<cnt);j++){                    double prob=1,tmp2=0;                    for(int t=1;t<=cnt;t++){                        if(j&(1<<(t-1))){                            prob=prob*k[q[t]];                            p[q[t]]=1;                        }else {                            prob=prob*(1-k[q[t]]);                            p[q[t]]=0;                        }                    }                    /*printf("(%d,%d)\n",i,j);                    for(int t=1;t<=cnt;t++)cout<<q[t]<<"!!";cout<<endl;*/                    for(int t=1;t<n;t++){                        int a=c[t],b=c[t+1];                        if(p[t])a=d[t];                        if(p[t+1])b=d[t+1];                        tmp2+=g[a][b];                    }                    //cout<<tmp2<<endl;;                    tmp+=tmp2*prob;                }                //cout<<"---"<<tmp<<endl;                ans=min(ans,tmp);                }            }//...                 printf("%.2lf",(double)ans);    }else{        printf("%.2lf",(double)brutef());    }    }

#include<cstdio>#include<algorithm>#include<iostream>using namespace std;int t,k,n,m,c[2333][2333],s[2333][2333];int main(){    freopen("problem.in","r",stdin);    freopen("problem.out","w",stdout);    scanf("%d%d",&t,&k);    for(int i=0;i<=2000;i++)c[i][1]=i%k;    for(int i=1;i<=2000;i++)        for(int j=2;j<=i;j++)            c[i][j]=(c[i-1][j]+c[i-1][j-1])%k;    for(int i=1;i<=2000;i++)        for(int j=1;j<=2000;j++){            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(j<=i)*(!c[i][j]);        }    while(t--){        scanf("%d %d",&n,&m);        /*for(int i=1;i<=n;i++,puts(""))            for(int j=1;j<=i;j++)printf("%d ",s[i][j]);        */printf("%d\n",s[n][m]);    }    return 0;}

#include<queue>#include<cstdio>#include<iostream>#include<algorithm>using namespace std;int n,m,q,u,v,t;double p;int a[123456];int PQ[123456],_PQ,od[7123456];namespace solution{    int x[7123456][2],y[7123456][2],z[7123456][2];    int hx,hy,hz,tx,ty,tz;        void init(){hx=hy=hz=1;tx=n;ty=tz=0;}    void debug(int tim){        for(int i=hx;i<=n;i++)printf("%d ",x[i][0]+q*(tim-x[i][1]));        printf("!");for(int i=hy;i<=ty;i++)printf("%d ",y[i][0]+q*(tim-y[i][1]));        printf("!");for(int i=hz;i<=tz;i++)printf("%d ",z[i][0]+q*(tim-z[i][1]));        printf("!");        puts("");    }    //wo hui zuo d2t2 ei    void getres(){//debug(m);        for(int i=1;i<=n+m;i++){            int c=-12345;int *I;                if(hx<=n)if(x[hx][0]+q*(m-x[hx][1])>c)c=x[hx][0]+q*(m-x[hx][1]),I=&hx;            if(hy<=ty)if(y[hy][0]+q*(m-y[hy][1])>c)c=y[hy][0]+q*(m-y[hy][1]),I=&hy;            if(hz<=tz)if(z[hz][0]+q*(m-z[hz][1])>c)c=z[hz][0]+q*(m-z[hz][1]),I=&hz;            ++*I;            if(!(i%t))printf("%d ",c);        }    }    int main(){        sort(a+1,a+n+1,greater<int>());//nlogn        for(int i=1;i<=n;i++)x[i][0]=a[i];        p=u;p/=v;        init();        for(int i=1;i<=m;i++){            int c=-12345;            int *I;            if(hx<=n)if(x[hx][0]+q*(i-1-x[hx][1])>c)c=x[hx][0]+q*(i-1-x[hx][1]),I=&hx;            if(hy<=ty)if(y[hy][0]+q*(i-1-y[hy][1])>c)c=y[hy][0]+q*(i-1-y[hy][1]),I=&hy;            if(hz<=tz)if(z[hz][0]+q*(i-1-z[hz][1])>c)c=z[hz][0]+q*(i-1-z[hz][1]),I=&hz;            int A,B;            A=p*c;            B=c-A;            //printf("cut %d into(%d,%d)\n",c,A,B);            y[++ty][0]=A;            z[++tz][0]=B;            z[tz][1]=y[ty][1]=i;            ++*I;            od[i]=c;            //cerr<<"h..="<<hx<<endl;             //debug(i);        }        for(int i=t;i<=m;i+=t)printf("%d ",od[i]);puts("");                getres();        return 0;    }}int main(){    freopen("earthworm.in","r",stdin);    freopen("earthworm.out","w",stdout);    //cerr<<sizeof(solution::x)*3;    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);    for(int i=1;i<=n;i++)scanf("%d",a+i);    if(n<=1000&&m<=1000){        for(int i=1;i<=n;i++)PQ[i]=a[i];_PQ=n;        for(int _t=1;_t<=m;_t++){            int mx=1;            for(int i=2;i<=_PQ;i++)if(PQ[i]>PQ[mx])mx=i;            int x=PQ[mx];            PQ[mx]=(int)u*1.0/v*x;            PQ[++_PQ]=x-PQ[mx];            //printf("cut %d into(%d,%d)\n",x,PQ[mx],PQ[_PQ]);            for(int i=1;i<_PQ;i++)if(i!=mx)PQ[i]+=q;            od[_t]=x;        }        for(int i=t;i<=m;i+=t)printf("%d ",od[i]);        sort(PQ+1,PQ+n+m+1,greater<int>());        puts("");        for(int i=t;i<=n+m;i+=t)printf("%d ",PQ[i]);    }else         solution::main();    return 0;}