#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int N=100050;
const int M=2000050;
int a[M],n,m;
vector<pair<int,ll>> seq;
void push(int x, ll sz)
{
if(seq.size() && seq.back().first==x) seq[seq.size()-1].second+=sz;
else seq.pb({x,sz});
}
void Decrypt()
{
int key=0;
for(int i=1;i<=m;i++)
{
if(a[i]==key)
{
if(a[i+1]==key)
{
push(a[i+1],a[i+2]+1);
}
else
{
if(a[i+2]==0) key=a[i+1];
else push(a[i+1],a[i+2]+3);
}
i+=2;
}
else push(a[i],1);
}
}
vector<pair<int,set<int>>> groups;
void Check()
{
for(int i=0;i<groups.size();i++)
{
if(groups[i].second.empty())
{
swap(groups[i],groups[groups.size()-1]);
groups.pop_back();
return;
}
}
}
unordered_map<int,int> change[N];
vector<int> ans;
int Calc1(ll sz)
{
int cnt=0;
while(sz>0)
{
cnt+=3;
sz-=n;
}
return cnt;
}
int Calc2(ll sz)
{
int cnt=0;
while(sz>0)
{
if(sz<=3) cnt+=sz;
else cnt+=3;
sz-=n+2;
}
return cnt;
}
void Solve()
{
groups.pb({0,{0}});
set<int> tmp;
for(int i=1;i<n;i++) tmp.insert(i),change[i][-1]=0;
groups.pb({3,tmp});
for(int tm=0;tm<seq.size();tm++)
{
int x=seq[tm].first;
ll sz=seq[tm].second;
//printf("(%i %i) ",x,sz);
int dp;
for(int i=0;i<groups.size();i++)
{
if(groups[i].second.count(x))
{
dp=groups[i].first;
groups[i].second.erase(x);
if(groups[i].second.empty()){
for(int j=i+1;j<groups.size();j++)groups[j-1]=groups[j];
groups.pop_back();
}
}
}
Check();
int c1=Calc1(sz);
int c2=Calc2(sz);
int mn=0;
for(int i=0;i<groups.size();i++)
{
groups[i].first+=c2;
if(i==0 || groups[mn].first>groups[i].first) mn=i;
}
if(groups[mn].first+3<dp+c1)
{
change[x][tm]=*groups[mn].second.begin();
dp=groups[mn].first+3;
}
else dp+=c1;
bool ok=0;
for(int i=0;i<groups.size();i++) if(groups[i].first==dp)
{
groups[i].second.insert(x);
ok=1;
break;
}
if(!ok) groups.pb({dp,{x}});
}
}
void Add(int key, int x, ll sz)
{
while(sz>0)
{
if(key==x)
{
int l=min(sz,(ll)n);
ans.pb(l-1);
ans.pb(x);
ans.pb(key);
sz-=l;
}
else
{
if(sz<=3)
{
while(sz--) ans.pb(x);
}
else
{
int l=min(sz,(ll)n+2);
ans.pb(l-3);
ans.pb(x);
ans.pb(key);
sz-=l;
}
}
}
}
void ChangeKey(int x, int y)
{
ans.pb(0);
ans.pb(y);
ans.pb(x);
}
void Encrypt()
{
int mn=0;
for(int i=0;i<groups.size();i++) if(i==0 || groups[mn].first>groups[i].first) mn=i;
int key=*groups[mn].second.begin();
for(int i=seq.size()-1;i>=0;i--)
{
//printf("\ni:%i key:%i",i,key);
if(change[key].count(i))
{
int nKey=change[key][i];
ChangeKey(nKey,key);
key=nKey;
}
Add(key,seq[i].first,seq[i].second);
}
if(key!=0) ChangeKey(0,key);
reverse(ans.begin(),ans.end());
}
int main()
{
scanf("%i %i",&n,&m);
for(int i=1;i<=m;i++) scanf("%i",&a[i]);
Decrypt();
Solve();
Encrypt();
printf("%i\n",ans.size());
for(int i:ans) printf("%i ",i);
printf("\n");
return 0;
}
