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

int n, m;

vector<int> sorrend;

bool noveld(int i) {
  if (sorrend[i] < n) {
    sorrend[i]++;
    return true;
  }
  
  if (i <= 0) {
    return false;
  }
  
  bool siker = noveld(i-1);
  
  if (!siker) {
    return false;
  }
  
  sorrend[i] = sorrend[i-1]+1;
  
  return true;
}

bool csokk(int i) {
  if (i <= 0) {
    if (sorrend[i]-1 > 0) {
      sorrend[i]--;
      return true;
    } else {
      return false;
    }
  }
  
  if (sorrend[i]-1 > sorrend[i-1]) {
    sorrend[i]--;
    return true;
  }
  
  bool siker = csokk(i-1);
  
  if (!siker) {
    return false;
  }
  
  sorrend[i] = sorrend[i-1]+1;
  
  return true;
}

int main() {
  cin >> n >> m;
  
  vector<int> realSorrend;
  
  for (int i = 0; m > i; i++) {
    int temp;
    cin >> temp;
    
    realSorrend.push_back(temp);
  }
  
  sorrend = realSorrend;
  
  bool lehet = csokk(m-1);
  
  if (lehet) {
    for (int i = 0; m > i; i++) {
      cout << sorrend[i] << " ";
    }
    
    cout << endl;
  } else {
    for (int i = n-m+1; n+1 > i; i++) {
      cout << i << " ";      
    }
    
    cout << endl;
  }
  
  sorrend = realSorrend;
  
  lehet = noveld(m-1);
  
  if (lehet) {
    for (int i = 0; m > i; i++) {
      cout << sorrend[i] << " ";
    }
    
    cout << endl;
  } else {
    for (int i = 1; m >= i; i++) {
      cout << i << " ";      
    }
    
    cout << endl;
  }
  
	return 0;
}