#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, m; cin >> n >> m;
	vector<int> v(m + 1);
	vector<int> el(m + 1);
	vector<int> ut(m + 1);

	for (int i = 1; i <= m; ++i) {
		cin >> v[i];

		el[i] = v[i];
		ut[i] = v[i];
	}

	bool t = false;
	for (int i = m; i > 0 && !t; --i) {
		if (el[i] > 1 && (i == 1 || el[i] - 1 > el[i - 1])) {
			--el[i];

			for (int j = i + 1; j <= m; ++j) {
				el[j] = n - (m - j);
			}
			t = true;
		}
	}
	if (!t) {
		for (int i = 1; i <= m; ++i) { 
			el[i] = n - m + i;
		}
	}

	t = false;
	for (int i = m; i > 0 && !t; --i) {
		if (ut[i] < n -(m-i)) {
			++ut[i];

			for (int j = i + 1; j <= m; ++j) {
				ut[j] = ut[j - 1] + 1;
			}
			t = true;
		}
	}
	if (!t) {
		for (int i = 1; i <= m; ++i) {
			ut[i] = i;
		}
	}

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