#include <bits/stdc++.h>
#ifndef SKY
#include "doll.h"
#endif // SKY
using namespace std;
#define N 1000010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back
int n,q,dem=0,root[N];
vector<int>lis[N];
vector<ii>flow_out[N];
vector<int>a,C,X,Y;
#ifdef SKY
void answer(vector<int>C,vector<int>X,vector<int>Y)
{
for(auto u:C)cout<<u<<" ";cout<<endl;
for(int i=0;i<X.size();i++)cout<<X[i]<<" "<<Y[i]<<endl;
}
#endif // SKY
struct haha
{
int child[2]={},tt=0;
}node[N];
void build(int u,int h)
{
if(h==0)
return;
node[u].child[0]=++dem;
node[u].child[1]=++dem;
build(node[u].child[0],h-1);
build(node[u].child[1],h-1);
}
ii DFS(int u)
{
if(node[u].child[0]==0)
{
ii res={u,node[u].tt};
node[u].tt^=1;
return res;
}
node[u].tt^=1;
return DFS(node[u].child[(node[u].tt^1)]);
}
void solve(int u)
{
int k=ceil(log2(lis[u].size()));
dem++;
C[u]=-dem;
int moc=dem;
root[u]=moc;
build(moc,k-1);
while(1)
{
ii cc=DFS(moc);
if(!flow_out[u].empty()&&cc==flow_out[u][0])
break;
//cout<<"cc\n";
flow_out[u].pb(cc);
}
for(auto cc:flow_out[u])
node[cc.fs].child[cc.sc]=moc;
int pos=dem;
while(!lis[u].empty())
{
ii cc=flow_out[u].back();
flow_out[u].pop_back();
int i=lis[u].back();
lis[u].pop_back();
if(i==q-1)
{
node[cc.fs].child[cc.sc]=0;
}else
{
node[cc.fs].child[cc.sc]=-a[i+1];
}
}
}
void create_circuit(int cc, vector<int> vec)
{
a=vec;
n=cc;
q=a.size();
// cout<<m<<" "<<n<<endl;
for(int i=0;i<q;i++)
lis[a[i]].pb(i);
// for(int i=1;i<=n;i++)cout<<lis[i].size()<<endl;
C.resize(n+1,0);
C[0]=a[0];
for(int i=1;i<=n;i++)
if(!lis[i].empty())
{
if(lis[i].size()==1)
{
if(lis[i].back()!=q-1)
C[i]=a[lis[i].back()+1];
continue;
}
solve(i);
}
for(int i=1;i<=dem;i++)
X.pb(-node[i].child[0]),Y.pb(-node[i].child[1]);
answer(C,X,Y);
}
#ifdef SKY
int main()
{
freopen("A.inp","r",stdin);
freopen("A.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int m,n;
cin>>m>>n;
vector<int>a;
for(int i=1;i<=n;i++)
{
int u;
cin>>u;
a.pb(u);
}
create_circuit(m,a);
return 0;
}
#endif
