#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,x; ifstream f("szamok.txt");
    cin>>n>>m; vector<bool>a(n);
    for(int i=0; i<n; i++){a[i]=0;}
    for(int i=0; i<m; i++){
        cin>>x; a[x-1]=1;}
    int egykis=-1,k=0;
    for(int i=n-1; i>0; i--){
        k+=a[i];
        if(a[i]==1 && a[i-1]==0){egykis=i-1; break;}}
    vector<bool>kis=a;
    if(egykis!=-1){
        swap(kis[egykis],kis[egykis+1]);
        for(int i=1; i<k; i++){kis[n-i]=1;}
        for(int i=k; i<n-egykis; i++){kis[n-i]=0;}}
    else{for(int i=0; i<n-m; i++){kis[i]=0;}
        for(int i=n-m; i<n; i++){kis[i]=1;}}
    for(int i=0; i<n; i++){if(kis[i])cout<<i+1<<" ";}
    cout<<endl;
    vector<bool>nagy=a;
    int egynagy=-1; k=0;
    for(int i=n-1; i>0; i--){
        k+=a[i];
        if(a[i]==0 && a[i-1]==1){egynagy=i-1; break;}}
    if(egynagy!=-1){
        swap(nagy[egynagy], nagy[egynagy+1]);
        for(int i=1; i<k; i++){nagy[egynagy+1+i]=1;}
        for(int i=egynagy+k+2; i<n; i++){nagy[i]=0;}}
    else{for(int i=0; i<m; i++){nagy[i]=1;}
        for(int i=m; i<n; i++){nagy[i]=0;}}
    for(int i=0; i<n; i++){if(nagy[i])cout<<i+1<<" ";}
    return 0;
}