#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> szamok(m);
for (int i=0; i<m; i++) {
cin >> szamok[i];
}
//nagyobb
bool legnagyobb=true; //legnagyobb e?
bool legkisebb=true;
for (int i=0; i<m; i++) {
if (szamok[m-i-1]!=n-i) {
//cout << "nemnagy\n";
legnagyobb=false;
}
if (szamok[i]!=i+1) {
//cout << "Nemkicsi\n";
legkisebb=false;
}
}
if (legnagyobb==true) {
//legnagyobb
cout << szamok[0]-1 << " ";
for (int i=1; i<m; i++) {
cout << szamok[i] << " ";
}
cout << "\n";
for (int i=0; i<m; i++) {
cout << i+1 << " ";
}
return 0;
}
if (legkisebb==true) {
for (int i=n-m+1; i<n+1; i++) {
cout << i << " ";
}
cout << "\n";
for (int i=0; i<m-1; i++) {
cout << i+1 << " ";
}
cout << m+1 << " \n";
return 0;
}
//kisebb
int kindex=0;
int kicsi=-1;
for (int i=1; i<m; i++) {
if (szamok[m-i]-szamok[m-i-1]!=1) {
//cout << i << "\n";
kindex=m-i;
kicsi=szamok[m-i]-1;
break;
}
}
if (kicsi==-1) {
cout << szamok[0]-1 << " ";
for (int i=1; i<m; i++) {
cout << i+n-m+1 << " ";
}
}
else {
for (int i=0; i<kindex; i++) {
cout << szamok[i] << " ";
}
cout << kicsi << " ";
for (int i=n-(m-kindex-1)+1; i<=n; i++) {
cout << i << " ";
}
}
cout << "\n";
//nagyobb
int hanyadik=-1;
int melyik=-1;
for (int i=0; i<m; i++) {
if (szamok[m-i-1]!=n-i) {
//cout << m-i << "\n\n";
hanyadik=m-i-1;
melyik=szamok[m-i-1]+1;
break;
}
}
for (int i=0; i<hanyadik; i++) {
cout << szamok[i] << " ";
}
for (int i=0; i<m-hanyadik; i++) {
cout << melyik+i << " ";
}
}