#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,a[N],ans[N];
int T[N];

void del(int x) { 
    while (x<=n) T[x]--,x+=x&-x;
}
int query(int x,int ans=0) {
    while (x) ans+=T[x],x-=x&-x;
    return ans;
}
int main()
{
    scanf("%d",&n);
    for (int i=2;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) T[i]=i&-i;

    for (int i=n;i;i--)
    {
        int l=1,r=n;
        while (l<r)
        {
            int mid=(l+r)>>1;
            if (query(mid)>a[i]) r=mid;
            else l=mid+1;
        }
        ans[i]=l,del(l);
    }
    for (int i=1;i<=n;i++) printf("%d\n",ans[i]);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,a[N],ans[N];
int T[N];

void del(int x) { 
    while (x<=n) T[x]--,x+=x&-x;
}
int query(int x,int ans=0) {
    while (x) ans+=T[x],x-=x&-x;
    return ans;
}
int main()
{
    scanf("%d",&n);
    for (int i=2;i<=n;i++) scanf("%d",&a[i]);
    for (int i=1;i<=n;i++) T[i]=i&-i;

    for (int i=n;i;i--)
    {
        int l=1,r=n;
        while (l<r)
        {
            int mid=(l+r)>>1;
            if (query(mid)>a[i]) r=mid;
            else l=mid+1;
        }ans[i]=l,del(l);
    }
    for (int i=1;i<=n;i++) printf("%d\n",a[i]);
    return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+1;
int n,m,a[N];

struct BIT {
    int T[N]; void add(int x,int y) { while (x<=n) T[x]+=y,x+=x&-x; }
    int query(int x,int ans=0) { while (x) ans+=T[x],x-=x&-x; return ans; }
}A,B;

int query(int x) {
    return A.query(x)*(x+1)-B.query(x);
}
signed main()
{
    scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) 
    scanf("%lld",&a[i]); for (int i=n;i;i--) a[i]-=a[i-1];
    for (int i=1;i<=n;i++) A.add(i,a[i]),B.add(i,i*a[i]);

    while (m--)
    {
        char op; int x,y,z; scanf(" %c%d%d",&op,&x,&y);
        if (op=='Q') printf("%lld\n",query(y)-query(x-1) );
        else { scanf("%lld",&z); A.add(x,z),A.add(y+1,-z); 
        B.add(x,x*z),B.add(y+1,(y+1)*-z); }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=4e4;
int n,m,fa[N];

int get(int x,int y) {
    return x*n+y;
}
int find(int x) {
    return fa[x]^x?fa[x]=find(fa[x]):x;
}
int main()
{
    for (int i=0;i<N;i++) fa[i]=i;
    scanf("%d%d",&n,&m); for (int i=1;i<=m;i++)
    {
        int x,y,a,b; char op;
        scanf("%d%d %c",&x,&y,&op);
        a=get(x-1,y-1); b=op=='D'?get(x,y-1):get(x-1,y);
        x=find(a),y=find(b); if (x^y) fa[x]=y;
        else return printf("%d",i),0;
    }
    puts("draw");
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
map<int,int> a;
int T,n,fa[N];
int rp,cnt;

int get(int x) {
    if (a[x]) return a[x];
    a[x]=++rp; fa[rp]=rp; return rp;
}
struct Query {
    int x,y;
}Q[N];

int find(int x) {
    return fa[x]^x?fa[x]=find(fa[x]):x;
}
bool check()
{
    for (int i=0;i<cnt;i++)
        if (find(Q[i].x)==find(Q[i].y) )
            return false;
    return true;
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        a.clear(); rp=cnt=0;
        for (int i=0,x,y,op;i<n;i++)
        {
            scanf("%d%d%d",&x,&y,&op);
            x=get(x),y=get(y); 
            if (op) fa[find(x)]=find(y);
            else Q[cnt++]={x,y};
        }
        puts(check()?"YES":"NO");
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+1;
int fa[N],dis[N];
map<int,int> a;
int n,rp;

int get(int x) {
    if (a[x]) return a[x];
    a[x]=++rp,fa[rp]=rp; return rp;
}
int find(int x)
{
    if (fa[x]^x)
    {
        int f=find(fa[x]);
        dis[x]^=dis[fa[x] ];
        fa[x]=f;
    }
    return fa[x];
}
int main()
{
    cin.tie(0),cout.tie(0);
    cin>>n>>n; int ans=n;
    for (int i=0;i<n;i++)
    {
        string s; int x,y,w; cin>>x>>y>>s;
        x=get(x-1),y=get(y),w=s=="odd";
        int fx=find(x),fy=find(y);
        if (fx==fy&&dis[x]^dis[y]^w) {ans=i; break;}
        else if (fx^fy) fa[fy]=fx,dis[fy]=dis[x]^dis[y]^w;
    }printf("%d",ans); return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+1;
int fa[N],d[N],s[N];

int find(int x)
{
    if (fa[x]^x)
    {
        int f=find(fa[x]);
        d[x]+=d[fa[x] ];
        fa[x]=f;
    }
    return fa[x];
}
int main()
{
    for (int i=1;i<N;i++) fa[i]=i,s[i]=1;
    int T; scanf("%d",&T); while (T--)
    {
        char ch; int x,y,fx,fy;
        scanf(" %c%d%d",&ch,&x,&y); fx=find(x),fy=find(y);
        if (ch=='M'&&fx^fy) fa[fx]=fy,d[fx]=s[fy],s[fy]+=s[fx];
        else if (ch=='C') printf("%d\n",fx^fy?-1:max(0,abs(d[x]-d[y])-1) );
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int v[N],w[N],f[N];
int n,m,k,fa[N];

int find(int x) {
    return fa[x]^x?fa[x]=find(fa[x]):x;
}
int main()
{
    scanf("%d%d%d",&n,&k,&m);
    for (int i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]),fa[i]=i;
    while (k--) { int x,y; scanf("%d%d",&x,&y); fa[find(x)]=find(y); }
    for (int i=1;i<=n;i++) if (fa[i]^i) { v[find(i)]+=v[i],w[find(i)]+=w[i],v[i]=w[i]=0; }
    for (int i=1;i<=n;i++) for (int j=m;j>=w[i];j--) f[j]=max(f[j],f[j-w[i] ]+v[i]);
    printf("%d",f[m]); return 0;
}