#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m;
	cin>>n>>m;
	vector<int> v; 
	for (int i=0; i<m;i++){
		int x;
		 cin>>x;
		 v.push_back(x);
	}	
	vector<int> z=v;
	bool van=false; 
	for (int i=m-1;i>0;i--){
		if (v[i]-1!=v[i-1]){
			z[i]=z[i]-1;
			int cnt=n;
			for (int j=m-1; j>i;j--){
				z[j]=cnt;
				cnt--;
			}
			for (int h:z) cout<<h<<" "; 
			van=true;
			break;
		}
	}
	if (!van){
		z[0]=z[0]-1;
		for (int h:z) cout<<h<<" "; 

	}
	cout<<endl;
	bool van2=false;
	if (v[m-1]!=n){
		v[m-1]++;
		for (int h:v) cout<<h<<" "; ; 
	} 
	else {
		for (int i=m-2; i>=0;i--){
		if (v[i]+1!=v[i+1]){
			v[i]++;
			for (int h:v) cout<<h<<" "; 
			van2=true; 
			break; 
		}
	}
	
}
}