#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e9;
const int md1 = 1e9+7;
const int md2 = 998244353;
#define sz(v) ((int)v.size())
#define pb push_back
#define pry cout << "YES\n"
#define prn cout << "NO\n"
#define endl '\n'
#define fst first
#define scn second
/* #define ONPC */
const int M = 1e5;
vector<int> v[M+5], x, y, c;
const int S = 4e5;
const int P = 2e7;
vector<int> reala;
map<int,int> compress;
int p = 0;
void answer(vector<int> C, vector<int> X, vector<int> Y);
int
news()
{
x.pb(0);
y.pb(0);
return sz(x);
}
void
dfs2(int l, int r, int s, int k)
{
if (l == r) {
reala[l] = s;
return;
}
int mid = (l+r)>>1;
dfs2(l,mid,s,k+1);
dfs2(mid+1,r,s+(1<<k),k+1);
}
int
dfs(int l, int r, int ind, vector<int>& a,int k)
{
if (l == r) {
if ((1<<x[ind-1])-1-l >= sz(a))
return -ind;
else
return a[compress[reala[l]]];
/* if (l >= sz(a)-1) { */
/* if (l == (1<<x[ind-1])-1) */
/* return a[sz(a)-1]; */
/* else */
/* return -ind; */
/* } */
}
int mid = (l+r)>>1;
int _x = dfs(l,mid,ind,a,k+1);
int _y = dfs(mid+1,r,ind,a,k+1);
if (_x == _y)
return _x;
int index = news();
p += (1<<(x[ind-1]-k));
x[index-1] = _x;
y[index-1] = _y;
return -index;
}
int
donode(vector<int> &a)
{
if (sz(a) == 1) return 0;
int l = 31 - __builtin_clz(sz(a));
if (sz(a) ^ (1<<l))
++l;
int ind = news();
x[ind-1] = l;
p += (1<<(l));
reala.resize(1<<l);
dfs2(0,(1<<l)-1,0,0);
vector<int> normalization;
for (int i = 0; i < sz(a); ++i) {
normalization.pb(reala[(1<<l)-1-i]);
}
sort(normalization.begin(), normalization.end());
for (int i = 0; i < sz(a); ++i) {
compress[normalization[i]] = i;
}
int mid = ((1<<l)-1)>>1;
int _x = dfs(0,mid,ind,a,1);
int _y = dfs(mid+1,(1<<l)-1,ind,a,1);
x[ind-1] = _x;
y[ind-1] = _y;
return -ind;
}
void
create_circuit(int m, vector<int> a)
{
int n = sz(a);
vector<int> a2;
for (int j = 1; j < n; ++j) {
a2.pb(a[j]);
}
a2.pb(0);
int indx = donode(a2);
c.assign(m+1,indx);
c[0] = a[0];
/* assert(sz(x)<=n*2); */
/* cout << sz(x) << ' ' << n << ' ' << n + 31 - __builtin_clz(n) << endl; */
/* return; */
/* assert(sz(x)<=S); */
assert(sz(x)<=n+log2(n));
/* return; */
assert(p<=P);
answer(c,x,y);
return;
}
#ifdef ONPC
void
answer(vector<int> C, vector<int> X, vector<int> Y)
{
int s = sz(X);
int m = sz(C)-1;
for (int i = 0; i < sz(C); ++i) {
assert(C[i] <= m);
assert(C[i] >= -s);
}
for (int i = 0; i < sz(X); ++i) {
assert(X[i] <= m);
assert(X[i] >= -s);
assert(Y[i] <= m);
assert(Y[i] >= -s);
}
vector<int> ans;
vector<bool> state(sz(X),0);
/* for (int i = 0; i < sz(X); ++i) { */
/* cout << "-" << i+1 << ": " << X[i] << ' ' << Y[i]<< endl; */
/* } */
int tg = C[0];
while (tg) {
if (tg >= 0) {
ans.pb(tg);
tg = C[tg];
} else {
int index = -tg-1;
if (state[index]==0) tg = X[index];
else tg = Y[index];
state[index] = !state[index];
}
}
for (int i = 0; i < sz(X); ++i) {
if (state[i]) {
cout << i << endl;
cout << "Error\n";
return;
}
}
cout << sz(ans) << endl;
for (int i = 0; i < sz(ans); ++i) {
cout << ans[i] << ' ';
}
cout << endl;
return;
}
void
solve()
{
int n, m;
cin >> m;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
cout << m << ' ';
create_circuit(m, a);
}
int32_t
main(int argc, char **argv)
{
if (argc >= 2) {
freopen(argv[1], "r", stdin);
} else
ios_base::sync_with_stdio(0);cin.tie(0);
int t = 1;
/* cin >> t; */
while(t--)
solve();
}
#endif
