#include <iostream>
#include <algorithm>
#include <string>
#include <ctime>
#include <vector>

using namespace std;

struct Node {
    int Y, size, data, empty;
    Node *Left, *Right, *Parent;

    Node(int y, int d, int emp = 0) {
        empty = emp;
        Y = y;
        data = d;
        size = 1;
        Left = Right = Parent = nullptr;
    }
};

int getSize(Node *treap) {
    return treap ? treap->size : 0;
}

void updSize(Node *treap) {
    if (treap != nullptr) treap->size = getSize(treap->Left) + getSize(treap->Right) + 1;
}

int getEmptyCnt(Node *treap) {
    return treap ? treap->empty : 0;
}

void updEmptyCnt(Node *treap) {
    if (treap != nullptr)
        treap->empty = getEmptyCnt(treap->Left) + getEmptyCnt(treap->Right) + (treap->data == 0 ? 1 : 0);
}

void bigUpd(Node *treap) {
    updSize(treap);
    updEmptyCnt(treap);
}

void split(Node *treap, int pivotKey, Node *&lRes, Node *&rRes) {
    if (treap == nullptr) {
        lRes = rRes = nullptr;
        return;
    }
    int XX = getSize(treap->Left);
    if (pivotKey < XX) {
        split(treap->Left, pivotKey, lRes, treap->Left);
        rRes = treap;
        bigUpd(rRes);
    } else {
        split(treap->Right, pivotKey, treap->Right, rRes);
        lRes = treap;
        bigUpd(lRes);
    }
}

void merge(Node *&treap, Node *l, Node *r) {
    if (!l || !r) {
        treap = l ? l : r;
    } else if (l->Y > r->Y) {
        merge(l->Right, l->Right, r);
        treap = l;
    } else {
        merge(r->Left, l, r->Left);
        treap = r;
    }
    bigUpd(treap);
}

void delNextZero(Node *&treap) {
    if (treap == nullptr) return;
    if (getEmptyCnt(treap->Left) != 0){
        return delNextZero(treap->Left);
    }
    if (treap->data == 0) {
        Node *t1, *t2, *t3;
        split(treap, treap->size - 2, t1, t2);
        split(t2, treap->size, t2, t3);
        merge(treap, t1, t3);
        bigUpd(treap);
    }
    if (getEmptyCnt(treap->Right) != 0){
        return delNextZero(treap->Right);
    }
}

void insertWithDelNextZero(Node *&treap, int pos, Node *toIns) {
    Node *t1, *t2;
    // Troubles::??
    split(treap, pos, t1, t2);
    delNextZero(t2);
    merge(treap, t1, toIns);
    merge(treap, treap, t2);
    bigUpd(treap);
}

void printTreap(Node *&treap) {
    if (treap == nullptr) return;
    printTreap(treap->Left);
    cout << treap->data << " ";
    printTreap(treap->Right);
}

int main() {
    srand(time(nullptr));
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    Node *treap = nullptr;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        merge(treap, treap, new Node(rand(), 0, 1));
        bigUpd(treap);
    }

    // заполнить курево
//    treap = new Node(rand(), 0, 1);
//    Node *last = treap;
//    for (int i = 1; i < m; ++i) {
//        int YY = rand();
//        Node *toAdd = new Node(YY, 0, 1);
//        if (last->Y < YY) {
//            last->Right = toAdd;
//            last->Right->Parent = last;
//        } else {
//            Node *cur = last->Parent;
//            while (cur && cur->Y > YY) {
//                cur = cur->Parent;
//            }
//            if (cur == nullptr) {
//                // вылетели из корня*
//                toAdd->Left = treap;
//                toAdd->Left->Parent = toAdd;
//                treap = toAdd;
//            } else {
//                Node *oldRight = cur->Right;
//                cur->Right = toAdd;
//                cur->Right->Parent = cur;
//                cur->Right->Left = oldRight;
//                cur->Right->Left->Parent = toAdd;
//            }
//        }
//        last = toAdd;
//        bigUpd(last);
//    }
    // закончили заполнять

    printTreap(treap);
    cout << endl;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        insertWithDelNextZero(treap, x, new Node(rand(), i, 0));
    }

    printTreap(treap);
    cout << endl;
    return 0;
}