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

int N, M;
vector<int>a;

int main()
{
	cin >> N >> M;
    int i;
	a.resize(M+2);
	for(i = 1; i <= M; ++i)cin >> a[i];
	a[0] = 0;
	a[M + 1] = N + 1;
	i = M;

	while (i > 0 && a[i] == a[i - 1] + 1)--i;
	for(int j = 1; j <= i - 1; ++j)cout << a[j] << ' ';
	if (i != 0)cout << a[i] - 1 << ' ';
	for(int j = i + 1; j <= M; ++j)cout << N - M + j << ' ';
	cout << '\n';

	i = M;
	while(i > 0 && a[i] == a[i + 1] - 1)--i;

	for(int j = 1; j <= i - 1; ++j)cout << a[j] << ' ';

	int k = a[i] + 1;
	if (i == 0) ++i;

	for(int j = i; j <= M; ++j)
	{
		cout << k << ' ';
		++k;
	}
	cout << '\n';
	return 0;
}