#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<int> chairS(M);
for (auto &e : chairS) {
cin >> e;
}
int index;
if (chairS[M - 1] == M) {
index = -1;
}
else {
// előző: csökkentjük a legutolsót, amit nem előz meg nála eggyel kisebb szám; a továbbiak a lehetséges értékek legvége lesznek
index = M - 1;
while (index > 0 && chairS[index] == chairS[index - 1] + 1) {
--index;
}
for (int i = 0; i < index; i++) {
cout << chairS[i] << " ";
}
cout << chairS[index] - 1 << " ";
}
for (int i = index + 1; i < M; i++) {
cout << N - (M - 1 - i) << " ";
}
cout << '\n';
if (chairS[0] == N - (M - 1)) {
index = 0;
chairS[0] = 1;
cout << 1 << " ";
}
else {
// következő: növeljük a legutolsót, amit még növelhetünk; a továbbiak közvetlenül utána következnek
index = M - 1;
while (index > 0 && chairS[index] == N - (M - 1) + index) {
--index;
}
for (int i = 0; i < index; i++) {
cout << chairS[i] << " ";
}
cout << ++chairS[index] << " ";
}
for (int i = index + 1; i < M; i++) {
chairS[i] = chairS[i - 1] + 1;
cout << chairS[i] << " ";
}
cout << '\n';
}