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
#include<bits/stdc++.h>

using namespace std;

#define mod 10000000009;

int baza;
long long pot[1<<20];

struct Node {
    long long war;
    int id;
    Node *left, *right;

    Node() : war(0), left(nullptr), right(nullptr) {}

    void add( int where, int ile, int pocz=0, int kon=baza ) {
        if( pocz == kon-1 ) {
            war = ile;
            return;
        }
        int sr = (pocz+kon)/2;
        if( where < sr ) {
            Node * pom = new Node;
            if( left != nullptr ) {
                *pom = *left;
            }
            left = pom;
            left->add( where, ile, pocz, sr );
        } else {
            Node * pom = new Node;
            if( right != nullptr ) {
                *pom = *right;
            }
            right = pom;
            right->add( where, ile, sr, kon );
        }
        war = left->war*pot[sr-pocz]%mod;
        if( right != nullptr ) {
            war = (war+right->war)%mod;
        }
    }

    bool operator < ( Node other ) const {
        const Node *a = this, *b = &other;
        int x = baza;
        while( x>1 ) {
            x/=2;
            if( a->left->war == b->left->war ) {
                a = a->right;
                b = b->right;
            } else {
                a = a->left;
                b = b->left;
            }
        }
        return a->war < b->war;
    }
};

int32_t main() {
    ios_base::sync_with_stdio( 0 );
    cin.tie( 0 );

    int n, m;
    cin >> n >> m;
    baza = 1;
    while( baza <= n ) baza*=2;
    pot[0] = 1;
    for( int i=1; i<=baza; i++ ) {
        pot[i] = pot[i-1]*1000000007%mod;
    }
    vector<Node> v;
    v.push_back( {} );
    for( int a, i=0; i<n; i++ ) {
        cin >> a;
        v.back().add( i, a );
    }
    v.back().add( n, 1 );
    v.back().id = 1;
    for( int a, b, i=2; i<=m; i++ ) {
        cin >> a >> b;
        v.push_back( v.back() );
        v.back().add( n, i );
        v.back().add( a-1, b );
        v.back().id = i;
    }
    sort( v.begin(), v.end() );
    for( auto & i : v ) {
        cout << i.id << " ";
    }
    return 0;
}