#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) {
		//kisebb
		for (int sz : szamok) {
			cout << sz-1 << " ";
		}
		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) {
			kindex=m-i;
			kicsi=szamok[m-i]-1;
		}
	}
	if (kicsi==-1) {
		for (int sz : szamok) {
			cout << sz-1 << " ";
		}
	}
	else {
		for (int i=0; i<kindex; i++) {
			cout << szamok[i] << " ";
		}
		for (int i=kindex; i<m; i++) {
			cout << kicsi+i-kindex << " ";
		}
	}

	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 << " ";
	}


}