#include<ios>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cstring>

#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>

using namespace std;

/** Ilość pomiarów temperatury */
int n;
/** Ilość uczniów */
int m;

/**
 * Klasa przechowująca ciąg danych (kopia)
 */
class Data {
public:
    /** Nr ucznia */
    int u;
    /** Dane danego ucznia */
    int* data;

    Data(int u) {
       this->u=u;
       data=new int[n];
    }

    Data(const Data* src, int u, int p, int x) {
        this->u=u;
        data=new int[n];
        memcpy(data, src->data, sizeof(int)*n);
        data[p]=x;
    }
};

struct DataCompare {
    bool operator() (const Data* a, const Data* b) const {
        for(int i=0;i<n;++i) {
            int d=a->data[i] - b->data[i];

            if(d<0) return true;
            if(d>0) return false;
        }
        return a->u < b->u;
    }

};

/** Implementacja prosta, działająca w oparciu o porównanie wszystkich elementów - dla małych danych */
void simpleCalc() {
    set<Data*, DataCompare> all;

    Data *d=new Data(1);
    for(int i=0;i<n;++i) cin>>d->data[i];
    all.insert(d);

    for(int i=1;i<m;++i) {
        int p,x;
        cin>>p>>x;
        d=new Data(d, i+1, p-1,x);
        all.insert(d);
    }

    for(set<Data*, DataCompare>::iterator it=all.begin();it!=all.end();++it) {
        cout<< (*it)->u<<" ";
    }
}

const int MAX_STUDENTS=500000;
const int MAX_DATA=5000000;
const int STUDENTS_FIX=-1000000;

struct Node {
    /** Liść lewy */
    Node* left;
    /** Liść prawy */
    Node* right;
    /** Wartość elementu */
    int value;
};

class NodeCompare {
public:
    int compareRec(const Node* a, const Node* b) {
        if(a==b) return 0;  // taki sam
        if(a->left==NULL) return a->value - b->value;   // porównanie liści
        // jeżeli nie są takie same to wejście w głąb
        int r=compareRec(a->left, b->left);
        if(r==0) r=compareRec(a->right, b->right);
        return r;
    }
    bool operator() (const Node* a, const Node* b) {
        int r=compareRec(a->left, b->left);
        if(r==0) r=compareRec(a->right, b->right);  // dalej kolejne elementy
        if(r==0) return a<b;
        if(r<0) return true;
        else return false;
    }
};

class Algorithm {
public:
    /** Bufor dla kompletu danych, tj.
     */
    Node node[MAX_STUDENTS+MAX_DATA*2+MAX_STUDENTS*22+500];
    /** Wysokość drzewa */
    int treeHeight;
    /** Limitowy element drzewa (poziom wyżej) */
    int treePos;

    // wskaźnik to pierwszego wolnego węzła
    Node *freeNode;

    Node* students;

    /** Wyświetlenie drzewa, czyli ciągu danych */
    void displayTreeRec(Node* node) {
        if(node->left==NULL) { // liść nie ma dzieci...
            cout<<node->value<<" ";
        } else {
            displayTreeRec(node->left);
            displayTreeRec(node->right);
        }
    }

    void displayTree(Node *node) {
        cout<<"Student: "<<((node-students))<<"="; // id ucznia jest ujemne i pomniejszone o 1 mln
        displayTreeRec(node);
        cout<<endl;
    }

    int buildTreeRec(int* data, Node* node, int level, int pos) {
        // obsługa ostatniego elementu w drzewie - liścia
        if(pos<treePos) {
            if(level==treeHeight) {
                node->left=NULL;
                node->right=NULL;
                node->value=data[pos++];
                return pos;
            }
        } else if(level==treeHeight-1) {
            node->value=data[pos++];
            node->left=NULL;
            node->right=NULL;
            return pos;
        }
        // jeżeli element nie jest liściem, to budujemy w głąb
        node->left=freeNode++;
        pos=buildTreeRec(data, node->left, level+1, pos);
        node->right=freeNode++;
        node->value=pos;    // połowa danych
        pos=buildTreeRec(data, node->right, level+1, pos);
        return pos;
    }

    /** Etap 1 - wczytanie pierwszego ciągu i zainicjowanie danych */
    void init() {
        students=node;
        freeNode=&node[MAX_STUDENTS+5]; // pierwsze zostawiamy na wierzchołki
        int* data=new int[n];
        // obliczanie wysokości drzewa, a więc log(n)
        {
            int v=n;
            treeHeight=0;
            while(v>1) { ++treeHeight; v=v>>1; }
            if(n>(1<<treeHeight)) {
                treePos=(n-(1<<treeHeight))*2;
                ++treeHeight;
            } else {
                treePos=n;  // wszystkie elementy na jednym poziomie
            }
        }

        /** Odczytujemy ciąg startowy */
        for(int i=0;i<n;++i) cin>>data[i];

        buildTreeRec(data, &students[0], 0, 0);

        delete[] data;
//        displayTreeRec(&students[0]);
    }

    /**
     * Metoda budująca nowe drzewo, na bazie poprzedniego (old)
     */
    void rebuildTreeRec(Node* old, Node* node, int pos, int newValue) {
        if(old->left==NULL) {   // liść, czyli już podmiana
            node->left=NULL;
            node->right=NULL;
            node->value=newValue;
        } else { // jeżeli wierzchołek wewnętrzny, to kopujemy ścieżke
            node->value=old->value;
            if(pos<node->value) {   // idzemy na lewo
                node->left = freeNode++;
                node->right = old->right;
                rebuildTreeRec(old->left, node->left, pos, newValue);
            } else {
                node->left=old->left;
                node->right=freeNode++;
                rebuildTreeRec(old->right, node->right, pos, newValue);
            }
        }
    }

    void process() {
        set<Node*, NodeCompare> all;

        all.insert(&students[0]);

        // odczytujemy podmiany kolejnych uczniów
        for(int i=1;i<m;++i) {
            int p,x;
            cin>>p>>x;
            rebuildTreeRec(&students[i-1], &students[i], p-1, x);
            all.insert(&students[i]);
//            displayTree(&students[i]);
        }

        for(set<Node*, NodeCompare>::iterator it=all.begin();it!=all.end();++it) {
            Node* n=*it;
            cout<<((n-students)+1)<<" ";
        }

    }

};

int main(int argc, char** argv) {
    // przyspiszenie cin/cout
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>m;

    if(n<20) {    // jeżeli jest mało danych, to prosty algorytm, bo w komplenym nie ma obsługi dla n=1
        simpleCalc();
    }else
    {
        Algorithm* a=new Algorithm();
        a->init();
        a->process();
    }

    return 0;
}