#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, m; cin >> n >> m;
	vector<int> v(m + 1);
	vector<int> ans1(m + 1);
	vector<int> ans2(m + 1);
	for (int i = 1; i <= m; ++i) {
		cin >> v[i];

		ans1[i] = ans2[i] = v[i];
	}

	bool ok = false; int i = m;
	while (!ok)	{
		if (v[i] > 1) {
			ans1[i] = v[i] - 1;
			ok = true;
		}
		else {
			--i;
		}
	}

	ok = false; i = m;
	while (!ok)	{
		if (v[i] < n) {
			ans2[i] = v[i] + 1;
			ok = true;
		}
		else {
			--i;
		}
	}

	for (int i = 1; i <= m; ++i) {
		cout << ans1[i] << " ";
	}
	cout << "\n";
	for (int i = 1; i <= m; ++i) {
		cout << ans2[i] << " ";
	}
}