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

using namespace std;

struct Node {
    int X, Y, size;
    Node *Left, *Right;

    Node(int x, int y, int s = 1) {
        X = x;
        Y = y;
        size = s;
        Left = nullptr;
        Right = 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;
}

void split(Node *treap, int pivotKey, Node *&lRes, Node *&rRes) {
    if (treap == nullptr) {
        lRes = rRes = nullptr;
    } else if (pivotKey < treap->X) {
        split(treap->Left, pivotKey, lRes, treap->Left);
        rRes = treap;
        updSize(rRes);
    } else {
        split(treap->Right, pivotKey, treap->Right, rRes);
        lRes = treap;
        updSize(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;
    }
    updSize(treap);
}

void insert(Node *&treap, Node *toIns) {
    Node *t1, *t2;
    split(treap, toIns->X, t1, t2);
    merge(treap, t1, toIns);
    merge(treap, treap, t2);
    updSize(treap);
}

void del(Node *&treap, int key) {
    Node *t1, *t2, *t3;
    split(treap, key - 1, t1, t2);
    split(t2, key, t2, t3);
    merge(treap, t1, t3);
    updSize(treap);
}
void printTreap(Node *&treap) {
    if (treap == nullptr) return;
    printTreap(treap->Left);
    cout << treap->X << " ";
    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));
        updSize(treap);
    }

    printTreap(treap);
    cout << endl;

    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        insert(treap, x, new Node(rand(), i));
    }

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