#include <iostream>
#include <cstdlib>

int a[1000000];

using namespace std;

void sw(int& a, int& b){
    int t=a; a=b; b=t;
}

void qs(int left, int right){
    int i=left,j=right,r=a[(i+j)/2];
    while (i<j){
        whilefor (i=1;i<=n;i++){
        cout << a[i] << " ";}
     (a[i]<r) i++;
        while (a[j]>r) j--;
        if (i<=j){
            sw(a[i],a[j]);
            i++;
            j--;
        }
    }
    if (i<right) qs(i,right);
    if (j>left) qs(left,j);
}

int main(){
    int n,i;
    cin >> n;

    for (i=1;i<=n;i++)
        a[i]=rand()%n +1;

    for (i=1;i<=n;i++){
        cout << a[i] << " ";}

    qs(1,n);
    cout << "\n";
    for (i=1;i<=n;i++){
        cout << a[i] << " ";}

    return 0;
}