1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
// PA2017, Iloczyn
// Andrzej Pezarski

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

unsigned long long P1 = 22227661796573LL;
unsigned long long P2 = 13LL;

int N, M, L, I, nodesCnt;

struct Node{
    int next[2];
    unsigned long long val;
};

Node *nodes;
int *roots;

void wczytajT() {
    for (int i=0; i<N; i++) {
        int t;
        scanf("%d", &t);
        nodes[L+i].val=t;
    }
    for (int i=N; i<L; i++) {
        nodes[L+i].val=0;
    }
    for (int v=L-1; v>0; v--) {
        nodes[v].val = ((nodes[2*v].val*P1)^nodes[2*v+1].val)*P2;
        nodes[v].next[0]=2*v;
        nodes[v].next[1]=2*v+1;
    }
    roots[0]=1;
}

int addPath(int v, int p, int x, int l) {
    l/=2;
    int newV=nodesCnt++;
    if (l==0) {
        nodes[newV].val=x;
    } else {
        nodes[newV].next[p<l]=nodes[v].next[p<l];
        nodes[newV].next[p>=l]=addPath(nodes[v].next[p>=l], (p<l)?p:(p-l), x, l);
        nodes[newV].val = ((nodes[nodes[newV].next[0]].val*P1)^nodes[nodes[newV].next[1]].val)*P2;
    }
    return newV;
}

void wczytajM() {
    for (int m=1; m<M; m++) {
        int p, x;
        scanf("%d%d", &p, &x);
        p--;
        roots[m]=addPath(roots[m-1], p, x, L);
    }
}

bool myCmp(int m1, int m2) {
    int v1=roots[m1];
    int v2=roots[m2];
    if (nodes[v1].val==nodes[v2].val) return m1<m2;
    for (int i=1; i<I; i++) {
        if (nodes[nodes[v1].next[0]].val==nodes[nodes[v2].next[0]].val) {
            v1=nodes[v1].next[1];
            v2=nodes[v2].next[1];
        } else {
            v1=nodes[v1].next[0];
            v2=nodes[v2].next[0];
        }
    }
    return nodes[v1].val < nodes[v2].val;
}

int main() {
    scanf("%d%d", &N, &M);
    for (L=1, I=1; L<N; L*=2, I++);
    nodes = new Node[2*L+M*I+10];
    roots = new int[M];
    nodesCnt=2*L;
    
    wczytajT();
    wczytajM();
    
    vector<int> res(M);
    for (int m=0; m<M; m++) {
        res[m]=m;
    }
    
//    for (int i=0; i<nodesCnt; i++) {
//        printf("%d %d %d %lld\n", i, nodes[i].next[0], nodes[i].next[1], nodes[i].val);
        
//    }
    
    sort(res.begin(), res.end(), myCmp);

    for (auto x:res) printf("%d ", x+1);
    printf("\n");
    
    delete[] roots;
    delete[] nodes;
    return 0;
}