#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
const int M=2000050;
int a[M],n,m;
vector<pair<int,ll>> seq;
void push(int x, int 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);
}
}
int change[M];
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;
}
int dp[N],lzy;
set<pair<int,int>> all;
void Solve()
{
for(int i=1;i<n;i++) dp[i]=3;
for(int i=0;i<n;i++) all.insert({dp[i],i});
lzy=0;
for(int tm=0;tm<seq.size();tm++)
{
change[tm]=-1;
int x=seq[tm].first;
ll sz=seq[tm].second;
int k=-1;
for(int j=0;j<n;j++) if(j!=x && (k==-1 || dp[k]>dp[j])) k=j;
int c1=Calc1(sz);
int c2=Calc2(sz);
dp[x]+=c1;
for(int j=0;j<n;j++) if(j!=x) dp[j]+=c2;
if(dp[k]+3<dp[x]) dp[x]=dp[k]+3,change[tm]=k;
/*all.erase({dp[x],x});
int tmp=dp[x]+lzy;
int c1=Calc1(sz);
int c2=Calc2(sz);
int mn,p;
tie(mn,p)=*all.begin();
mn+=lzy;
if(mn+lzy+c2+3<tmp+c1)
{
change[tm]=p;
tmp=mn+lzy+c2+3;
}
else tmp+=c1;
lzy+=c2;
dp[x]=tmp-lzy;
all.insert({dp[x],x});*/
}
}
void Add(int key, int x, ll sz)
{
while(sz>0)
{
if(key==x)
{
int l=min(sz,(ll)n);
ans.pb(key);
ans.pb(x);
ans.pb(l-1);
sz-=l;
}
else
{
if(sz<=3)
{
while(sz--) ans.pb(x);
}
else
{
int l=min(sz,(ll)n+2);
ans.pb(key);
ans.pb(x);
ans.pb(l-3);
sz-=l;
}
}
}
}
void ChangeKey(int x, int y)
{
ans.pb(x);
ans.pb(y);
ans.pb(0);
}
void Encrypt()
{
//int key=all.begin()->second;
int key=0;
for(int i=0;i<n;i++) if(dp[i]<dp[key]) key=i;
vector<pair<int,pair<int,ll>>> op;
for(int i=seq.size()-1;i>=0;i--)
{
if(seq[i].first==key && change[i]!=-1)
{
int nKey=change[i];
//ChangeKey(nKey,key);
op.pb({nKey,{key,-1}});
key=nKey;
}
//Add(key,seq[i].first,seq[i].second);
op.pb({key,{seq[i].first,seq[i].second}});
}
if(key!=0) op.pb({0,{key,-1}});//ChangeKey(0,key);
reverse(op.begin(),op.end());
for(auto o:op)
{
if(o.second.second==-1) ChangeKey(o.first,o.second.first);
else Add(o.first,o.second.first,o.second.second);
}
}
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;
}
