#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    #define ll long long
    //fread->read
    bool IOerror=0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if (p1==pend){
            p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if (pend==p1){IOerror=1;return -1;}
            //{printf("IO error!\n");system("pause");for (;;);exit(0);}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(ll &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (sign)x=-x;
    }
    inline void read(double &x){
        bool sign=0; char ch=nc(); x=0;
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        if (ch=='-')sign=1,ch=nc();
        for (;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';
        if (ch=='.'){
            double tmp=1; ch=nc();
            for (;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');
        }
        if (sign)x=-x;
    }
    inline void read(char *s){
        char ch=nc();
        for (;blank(ch);ch=nc());
        if (IOerror)return;
        for (;!blank(ch)&&!IOerror;ch=nc())*s++=ch;
        *s=0;
    }
    inline void read(char &c){
        for (c=nc();blank(c);c=nc());
        if (IOerror){c=-1;return;}
    }
    //getchar->read
    inline void read1(int &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (bo)x=-x;
    }
    inline void read1(ll &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (bo)x=-x;
    }
    inline void read1(double &x){
        char ch;int bo=0;x=0;
        for (ch=getchar();ch<'0'||ch>'9';ch=getchar())if (ch=='-')bo=1;
        for (;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
        if (ch=='.'){
            double tmp=1;
            for (ch=getchar();ch>='0'&&ch<='9';tmp/=10.0,x+=tmp*(ch-'0'),ch=getchar());
        }
        if (bo)x=-x;
    }
    inline void read1(char *s){
        char ch=getchar();
        for (;blank(ch);ch=getchar());
        for (;!blank(ch);ch=getchar())*s++=ch;
        *s=0;
    }
    inline void read1(char &c){for (c=getchar();blank(c);c=getchar());}
    //scanf->read
    inline void read2(int &x){scanf("%d",&x);}
    inline void read2(ll &x){
        #ifdef _WIN32
            scanf("%I64d",&x);
        #else
        #ifdef __linux
            scanf("%lld",&x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void read2(double &x){scanf("%lf",&x);}
    inline void read2(char *s){scanf("%s",s);}
    inline void read2(char &c){scanf(" %c",&c);}
    inline void readln2(char *s){gets(s);}
    //fwrite->write
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        void out(char ch){
            if (p1==pend){
                fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
            }
            *p1++=ch;
        }
        void print(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(int x){
            static char s[15],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1);
        }
        void println(ll x){
            static char s[25],*s1;s1=s;
            if (!x)*s1++='0';if (x<0)out('-'),x=-x;
            while(x)*s1++=x%10+'0',x/=10;
            while(s1--!=s)out(*s1); out('\n');
        }
        void print(double x,int y){
            static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,
                1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,
                100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if (x<-1e-12)out('-'),x=-x;x*=mul[y];
            ll x1=(ll)floor(x); if (x-floor(x)>=0.5)++x1;
            ll x2=x1/mul[y],x3=x1-x2*mul[y]; print(x2);
            if (y>0){out('.'); for (size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i); print(x3);}
        }
        void println(double x,int y){print(x,y);out('\n');}
        void print(char *s){while (*s)out(*s++);}
        void println(char *s){while (*s)out(*s++);out('\n');}
        void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    //puts->write
    char Out[OUT_SIZE],*o=Out;
    inline void print1(int x){
        static char buf[15];
        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
        while(x)*p1++=x%10+'0',x/=10;
        while(p1--!=buf)*o++=*p1;
    }
    inline void println1(int x){print1(x);*o++='\n';}
    inline void print1(ll x){
        static char buf[25];
        char *p1=buf;if (!x)*p1++='0';if (x<0)*o++='-',x=-x;
        while(x)*p1++=x%10+'0',x/=10;
        while(p1--!=buf)*o++=*p1;
    }
    inline void println1(ll x){print1(x);*o++='\n';}
    inline void print1(char c){*o++=c;}
    inline void println1(char c){*o++=c;*o++='\n';}
    inline void print1(char *s){while (*s)*o++=*s++;}
    inline void println1(char *s){print1(s);*o++='\n';}
    inline void println1(){*o++='\n';}
    inline void flush1(){if (o!=Out){if (*(o-1)=='\n')*--o=0;puts(Out);}}
    struct puts_write{
        ~puts_write(){flush1();}
    }_puts;
    inline void print2(int x){printf("%d",x);}
    inline void println2(int x){printf("%d\n",x);}
    inline void print2(char x){printf("%c",x);}
    inline void println2(char x){printf("%c\n",x);}
    inline void print2(ll x){
        #ifdef _WIN32
            printf("%I64d",x);
        #else
        #ifdef __linux
            printf("%lld",x);
        #else
            puts("error:can't recognize the system!");
        #endif
        #endif
    }
    inline void println2(ll x){print2(x);printf("\n");}
    inline void println2(){printf("\n");}
    #undef ll
    #undef OUT_SIZE
    #undef BUF_SIZE
};
using namespace fastIO;
const int N=500000;
struct query{
    int where,w;
}q[N+10];
struct tree{
    int l,r,w;
}t[N*25];
struct atom2{
    int l,r;
};
int C[N*25],tot,linkL[N*25],linkR[N*25],num[N*25];
int len,root[N+10],n,m,w[N+10];
int buildtree(int k1,int k2){
    int now=++len;
    if (k1==k2){
        t[now].w=w[k1]; return now;
    }
    int mid=k1+k2>>1;
    t[now].l=buildtree(k1,mid);
    t[now].r=buildtree(mid+1,k2);
    return now;
}
int insert(int k1,int k2,int k3,int k4,int k5){
    int now=++len; t[now]=t[k1];
    if (k2==k3) {
        t[now].w=k5; return now;
    }
    int mid=k2+k3>>1;
    if (mid>=k4){
        t[now].l=insert(t[k1].l,k2,mid,k4,k5);
    } else {
        t[now].r=insert(t[k1].r,mid+1,k3,k4,k5);
    }
    return now;
}
vector<int>A[N+10];
int a[N+10],c[N+10],x[N+10],y[N+10],sa[N+10];
int pd[N*25],where[N+10],sign,loc[N*25];
int compare(int k1,int k2){
    return num[linkL[k1]]<num[linkL[k2]]||(num[linkL[k1]]==num[linkL[k2]]&&k1<k2);
}
int compare2(int k1,int k2){
    return t[C[k1]].w<t[C[k2]].w;
}
void getnum(atom2 mem){
    int n=mem.r-mem.l+1;
    for (int i=1;i<=n;i++) c[i]=0;
    for (int i=1;i<=n;i++) x[i]=num[linkR[i+mem.l-1]];
    for (int i=1;i<=n;i++) c[x[i]]++;
    for (int i=1;i<=n;i++) c[i]+=c[i-1];
    for (int i=1;i<=n;i++){
        y[c[x[i]]]=i; c[x[i]]--;
    }
    for (int i=1;i<=n;i++) c[i]=0;
    for (int i=1;i<=n;i++) x[i]=num[linkL[i+mem.l-1]];
    for (int i=1;i<=n;i++) c[x[y[i]]]++;
    for (int i=1;i<=n;i++) c[i]+=c[i-1];
    for (int i=n;i;i--){
        sa[c[x[y[i]]]]=y[i]+mem.l-1; c[x[y[i]]]--;
    }
    int cur=1; num[sa[1]]=1;
    for (int i=2;i<=n;i++){
        if (num[linkL[sa[i]]]!=num[linkL[sa[i-1]]]||num[linkR[sa[i]]]!=num[linkR[sa[i-1]]]) cur++;
        num[sa[i]]=cur;
    }
}
void clearhashtable(){
    sign++; len=0;
}
int insert(int k1){
    if (pd[k1]==sign) return loc[k1];
    len++; pd[k1]=sign; loc[k1]=len+tot; where[len]=k1; return loc[k1];
}
void solve(int l,int r,atom2 mem){
    if (l==r){
        int len=mem.r-mem.l+1;
        for (int i=1;i<=len;i++) a[i]=mem.l+i-1;
        sort(a+1,a+len+1,compare2); int cur=1; num[a[1]]=1;
        for (int i=2;i<=len;i++){
            if (t[C[a[i]]].w!=t[C[a[i-1]]].w) cur++;
            num[a[i]]=cur;
        }
        return;
    }
    clearhashtable();
    for (int i=mem.l;i<=mem.r;i++)
        linkL[i]=insert(t[C[i]].l);
    atom2 L=(atom2){tot+1,tot+len};
    for (int i=1;i<=len;i++) C[i+tot]=where[i];
    tot+=len;
    clearhashtable();
    for (int i=mem.l;i<=mem.r;i++)
        linkR[i]=insert(t[C[i]].r);
    atom2 R=(atom2){tot+1,tot+len};
    for (int i=1;i<=len;i++) C[i+tot]=where[i];
    tot+=len; //cout<<tot<<endl;
    int mid=l+r>>1;
    solve(l,mid,L); solve(mid+1,r,R);
//  cout<<"in"<<endl;
    getnum(mem);
//  cout<<"out"<<endl;
//  cout<<"merge "<<l<<" "<<r<<endl;
//  for (int i=mem.l;i<=mem.r;i++) cout<<linkL[i]-L.l+1<<" "<<linkR[i]-R.l+1<<endl;
//  for (int i=L.l;i<=L.r;i++) cout<<num[i]<<" "; cout<<endl;
//  for (int i=R.l;i<=R.r;i++) cout<<num[i]<<" "; cout<<endl;
//  for (int i=mem.l;i<=mem.r;i++) cout<<num[i]<<" "; cout<<endl;
}
int get(int where,int num){
    return lower_bound(A[where].begin(),A[where].end(),num)-A[where].begin()+1;
}
int getrand(){
    return rand();
}
const int inf=1e9;
int getw(){
    return rand()%(inf*2+1)-inf;
}
void readdata(){
    read(n); read(m);
    for (int i=1;i<=n;i++) read(w[i]);
    for (int i=2;i<=m;i++){
        read(q[i].where); read(q[i].w);
    }
}
void gendata(){
    n=500000; m=500000;
    for (int i=1;i<=n;i++) w[i]=getw();
    for (int i=2;i<=m;i++){
        q[i].where=getrand()%n+1; q[i].w=getw();
    }
}
int main(){
    //gendata(); 
    readdata();
    for (int i=1;i<=n;i++) A[i].push_back(w[i]); 
    for (int i=2;i<=m;i++){
        A[q[i].where].push_back(q[i].w);
    }
    for (int i=1;i<=n;i++){
        sort(A[i].begin(),A[i].end());
        A[i].resize(unique(A[i].begin(),A[i].end())-A[i].begin());
    }
    for (int i=1;i<=n;i++) w[i]=get(i,w[i]);
    for (int i=2;i<=m;i++) q[i].w=get(q[i].where,q[i].w);
    root[1]=buildtree(1,n);
    for (int i=2;i<=m;i++) root[i]=insert(root[i-1],1,n,q[i].where,q[i].w);
    tot=m; clearhashtable();
    for (int i=1;i<=m;i++) linkL[i]=insert(root[i]);
    atom2 cur=(atom2){tot+1,tot+len};
    for (int i=1;i<=len;i++) C[tot+i]=where[i];
    tot+=len;
    solve(1,n,cur); 
    for (int i=1;i<=m;i++) a[i]=i;
    sort(a+1,a+m+1,compare);
    for (int i=1;i<=m;i++) printf("%d ",a[i]," \n"[i==m]);
    printf("\n"); return 0;
}