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

#define ll              long long 
#define pb              push_back
#define all(v)          v.begin(),v.end()
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define popcount(x)     __builtin_popcountll(x)
#define pll             pair<ll,ll> 
#define pii             pair<int,int>
#define ld              long double

const int M = 1000000007;
const int MM = 998244353;
const long double PI = acos(-1);

template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
template<typename T, typename U> ostream& operator<<(ostream &os, const pair<T, U> &p)
{ 
    return os<<'('<<p.F<< ","<<p.S<<')'; 
}

template<typename flow_t =long long int, typename cost_t =long long int>
struct mcSFlow{
    struct Edge{
        cost_t c;
        flow_t f;
        int to, rev;
        Edge(int _to, cost_t _c, flow_t _f, int _rev):c(_c), f(_f), to(_to), rev(_rev){}
    };
    const cost_t INFCOST = numeric_limits<cost_t>::max()/4;
    const cost_t INFFLOW = numeric_limits<flow_t>::max()/4;
    cost_t epsilon;
    int N, S, T;
    vector<vector<Edge> > G;
    vector<unsigned int> isEnqueued, state;
    mcSFlow(int _N, int _S, int _T):epsilon(0), N(_N), S(_S), T(_T), G(_N){}
    void add_edge(int a, int b, flow_t cap, cost_t cost){
        if(a==b){assert(cost>=0); return;}
        cost*=N;// to preserve integer-values
        epsilon = max(epsilon, abs(cost));
        assert(a>=0&&a<N&&b>=0&&b<N);
        G[a].emplace_back(b, cost, cap, G[b].size());
        G[b].emplace_back(a, -cost, 0, G[a].size()-1);
    }
    flow_t calc_max_flow(){ // Dinic max-flow
        vector<flow_t> dist(N), state(N);
        vector<Edge*> path(N);
        auto cmp = [](Edge*a, Edge*b){return a->f < b->f;};
        flow_t addFlow, retflow=0;;
        do{
            fill(dist.begin(), dist.end(), -1);
            dist[S]=0;
            auto head = state.begin(), tail = state.begin();
            for(*tail++ = S;head!=tail;++head){
                for(Edge const&e:G[*head]){
                    if(e.f && dist[e.to]==-1){
                        dist[e.to] = dist[*head]+1;
                        *tail++=e.to;
                    }
                }
            }
            addFlow = 0;
            fill(state.begin(), state.end(), 0);
            auto top = path.begin();
            Edge dummy(S, 0, INFFLOW, -1);
            *top++ = &dummy;
            while(top != path.begin()){
                int n = (*prev(top))->to;
                if(n==T){
                    auto next_top = min_element(path.begin(), top, cmp);
                    flow_t flow = (*next_top)->f;
                    while(--top!=path.begin()){
                        Edge &e=**top, &f=G[e.to][e.rev];
                        e.f-=flow;
                        f.f+=flow;
                    }
                    addFlow=1;
                    retflow+=flow;
                    top = next_top;
                    continue;
                }
                for(flow_t &i=state[n], i_max = G[n].size(), need = dist[n]+1;;++i){
                    if(i==i_max){
                        dist[n]=-1;
                        --top;
                        break;
                    }
                    if(dist[G[n][i].to] == need && G[n][i].f){
                        *top++ = &G[n][i];
                        break;
                    }
                }
            }
        }while(addFlow);
        return retflow;
    }
    vector<flow_t> excess;
    vector<cost_t> h;
    void push(Edge &e, flow_t amt){
        if(e.f < amt) amt=e.f;
        e.f-=amt;
        excess[e.to]+=amt;
        G[e.to][e.rev].f+=amt;
        excess[G[e.to][e.rev].to]-=amt;
    }
    void relabel(int vertex){
        cost_t newHeight = -INFCOST;
        for(unsigned int i=0;i<G[vertex].size();++i){
            Edge const&e = G[vertex][i];
            if(e.f && newHeight < h[e.to]-e.c){
                newHeight = h[e.to] - e.c;
                state[vertex] = i;
            }
        }
        h[vertex] = newHeight - epsilon;
    }
    const int scale=2;
    pair<flow_t, cost_t> minCostFlow(){
        cost_t retCost = 0;
        for(int i=0;i<N;++i){
            for(Edge &e:G[i]){
                retCost += e.c*(e.f);
            }
        }
        //find feasible flow
        flow_t retFlow = calc_max_flow();
        excess.resize(N);h.resize(N);
        queue<int> q;
        isEnqueued.assign(N, 0); state.assign(N,0);
        // cost scaling
        for(;epsilon;epsilon>>=scale){
            fill(state.begin(), state.end(), 0);
            for(int i=0;i<N;++i)
                for(auto &e:G[i])
                    if(h[i] + e.c - h[e.to] < 0 && e.f) push(e, e.f);
            for(int i=0;i<N;++i){
                if(excess[i]>0){
                    q.push(i);
                    isEnqueued[i]=1;
                }
            }
            while(!q.empty()){
                int cur=q.front();q.pop();
                isEnqueued[cur]=0;
                // discharge
                while(excess[cur]>0){
                    if(state[cur] == G[cur].size()){
                        relabel(cur);
                    }
                    for(unsigned int &i=state[cur], max_i = G[cur].size();i<max_i;++i){
                        Edge &e=G[cur][i];
                        if(h[cur] + e.c - h[e.to] < 0){
                            push(e, excess[cur]);
                            if(excess[e.to]>0 && isEnqueued[e.to]==0){
                                q.push(e.to);
                                isEnqueued[e.to]=1;
                            }
                            if(excess[cur]==0) break;
                        }
                    }
                }
            }
            if(epsilon>1 && epsilon>>scale==0){
                epsilon = 1<<scale;
            }
        }
        for(int i=0;i<N;++i){
            for(Edge &e:G[i]){
                retCost -= e.c*(e.f);
            }
        }
        //cerr << " -> " << retFlow << " / " << retCost << " bzw. " << retCost/2/N << "\n";
        return make_pair(retFlow, retCost/2/N);
    }
    flow_t getFlow(Edge const &e){
        return G[e.to][e.rev].f;
    }
};
// pass edges in the form ... from to capacity cost

// constructor in the form indexOfLastVertex+1,source,sink

int _runtimeTerror_()
{
    int d,n;
    cin>>d>>n;
    int u = (1<<d) - 1;
    mcSFlow<> flow(2*u+3,0,2*u+1);
    vector<int> a(n);
    for(int i=0;i<n;++i)
    {
        string s;
        cin>>s;
        int x = 0;
        for(int j=0;j<d;++j)
            if(s[j] == '1')
                x += (1<<j);
        a[i] = x;
        flow.add_edge(0,a[i],1,-popcount(a[i]));
        flow.add_edge(u+a[i],2*u+1,1,0);
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            if(i == j)
                continue;
            if((a[i]&a[j]) == a[i])
            {
                flow.add_edge(a[i],u+a[j],1,0);
            }
        }
    }
    flow.minCostFlow();
    vector<int> p(u+1,-1),vis(u+1,0);
    for(int i=0;i<n;++i)
        p[a[i]] = 0;
    for(auto &j:flow.G[0])
    {
        if(flow.getFlow(j) == 1)
        {
            vis[j.to] = 1;
        }
    }
    for(int i=0;i<n;++i)
    {
        for(auto &j:flow.G[a[i]])
        {
            if(flow.getFlow(j) == 1 && j.to > u)
            {
                p[j.to-u] = a[i];
            }
        }
    }
    vector<vector<int>> chains;
    int ans = 0;
    for(int i=1;i<=u;++i)
    {
        if(vis[i] || p[i] == -1)
            continue;
        vector<int> a;
        int cur = i;
        while(cur)
        {
            a.push_back(cur);
            vis[cur] = 1;
            cur = p[cur];
        }
        a.push_back(0);
        reverse(all(a));
        vector<int> b;
        for(int i=1;i<sz(a);++i)
        {
            for(int j=0;j<d;++j)
                if((a[i]&(1<<j)) && ((a[i-1]&(1<<j)) == 0))
                    b.push_back(j);
        }
        chains.push_back(b);
        ans += sz(b);
    }
    ans += sz(chains) - 1;
    cout<<ans<<"\n";
    for(int i=0;i<sz(chains);++i)
    {
        for(auto &k:chains[i])
            cout<<k<<" ";
        if(i < sz(chains) - 1)
            cout<<"R ";
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef runSieve
        sieve();
    #endif
    #ifdef NCR
        initialize();
    #endif
    int TESTS=1;
    //cin>>TESTS;
    while(TESTS--)
        _runtimeTerror_();
    return 0;
}
### Prompt

Please create a solution in cpp to the following problem:

You are standing in front of the room with great treasures. The only thing stopping you is the door with a push-button combination lock. This lock has d buttons with digits from 0 to d - 1. Whenever you press a button, it stays pushed down. You can not pop back up just one button, but there is a "RESET" button — pressing it pops up all other buttons. Initially, no buttons are pushed down.

The door instantly opens when some specific set of digits is pushed down. Sadly, you don't know the password for it. Having read the documentation for this specific lock, you found out that there are n possible passwords for this particular lock. 

Find the shortest sequence of button presses, such that all possible passwords appear at least once during its execution. Any shortest correct sequence of button presses will be accepted.

Input

The first line contains two integers d and n (1 ≤ d ≤ 10; 1 ≤ n ≤ 2^d - 1). Next n lines describe possible passwords. Each line contains a string s_i of d zeros and ones: for all j from 1 to d the j-th character is 1 iff the button with the digit j - 1 must be pushed down.

All strings s_i are different, and each string contains at least one 1.

Output

On the first line, print the number k — the minimum number of button presses. On the second line, print k tokens, describing the sequence. Whenever you press a button with a digit, print that digit. Whenever you press "RESET", print "R".

Examples

Input


2 2
10
11


Output


2
0 1 


Input


3 4
001
111
101
011


Output


6
2 0 R 1 2 0 

Note

In the second example, the sequence 1 2 R 2 0 1 is also possible.

### Response

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

#define ll              long long 
#define pb              push_back
#define all(v)          v.begin(),v.end()
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define popcount(x)     __builtin_popcountll(x)
#define pll             pair<ll,ll> 
#define pii             pair<int,int>
#define ld              long double

const int M = 1000000007;
const int MM = 998244353;
const long double PI = acos(-1);

template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
template<typename T, typename U> ostream& operator<<(ostream &os, const pair<T, U> &p)
{ 
    return os<<'('<<p.F<< ","<<p.S<<')'; 
}

template<typename flow_t =long long int, typename cost_t =long long int>
struct mcSFlow{
    struct Edge{
        cost_t c;
        flow_t f;
        int to, rev;
        Edge(int _to, cost_t _c, flow_t _f, int _rev):c(_c), f(_f), to(_to), rev(_rev){}
    };
    const cost_t INFCOST = numeric_limits<cost_t>::max()/4;
    const cost_t INFFLOW = numeric_limits<flow_t>::max()/4;
    cost_t epsilon;
    int N, S, T;
    vector<vector<Edge> > G;
    vector<unsigned int> isEnqueued, state;
    mcSFlow(int _N, int _S, int _T):epsilon(0), N(_N), S(_S), T(_T), G(_N){}
    void add_edge(int a, int b, flow_t cap, cost_t cost){
        if(a==b){assert(cost>=0); return;}
        cost*=N;// to preserve integer-values
        epsilon = max(epsilon, abs(cost));
        assert(a>=0&&a<N&&b>=0&&b<N);
        G[a].emplace_back(b, cost, cap, G[b].size());
        G[b].emplace_back(a, -cost, 0, G[a].size()-1);
    }
    flow_t calc_max_flow(){ // Dinic max-flow
        vector<flow_t> dist(N), state(N);
        vector<Edge*> path(N);
        auto cmp = [](Edge*a, Edge*b){return a->f < b->f;};
        flow_t addFlow, retflow=0;;
        do{
            fill(dist.begin(), dist.end(), -1);
            dist[S]=0;
            auto head = state.begin(), tail = state.begin();
            for(*tail++ = S;head!=tail;++head){
                for(Edge const&e:G[*head]){
                    if(e.f && dist[e.to]==-1){
                        dist[e.to] = dist[*head]+1;
                        *tail++=e.to;
                    }
                }
            }
            addFlow = 0;
            fill(state.begin(), state.end(), 0);
            auto top = path.begin();
            Edge dummy(S, 0, INFFLOW, -1);
            *top++ = &dummy;
            while(top != path.begin()){
                int n = (*prev(top))->to;
                if(n==T){
                    auto next_top = min_element(path.begin(), top, cmp);
                    flow_t flow = (*next_top)->f;
                    while(--top!=path.begin()){
                        Edge &e=**top, &f=G[e.to][e.rev];
                        e.f-=flow;
                        f.f+=flow;
                    }
                    addFlow=1;
                    retflow+=flow;
                    top = next_top;
                    continue;
                }
                for(flow_t &i=state[n], i_max = G[n].size(), need = dist[n]+1;;++i){
                    if(i==i_max){
                        dist[n]=-1;
                        --top;
                        break;
                    }
                    if(dist[G[n][i].to] == need && G[n][i].f){
                        *top++ = &G[n][i];
                        break;
                    }
                }
            }
        }while(addFlow);
        return retflow;
    }
    vector<flow_t> excess;
    vector<cost_t> h;
    void push(Edge &e, flow_t amt){
        if(e.f < amt) amt=e.f;
        e.f-=amt;
        excess[e.to]+=amt;
        G[e.to][e.rev].f+=amt;
        excess[G[e.to][e.rev].to]-=amt;
    }
    void relabel(int vertex){
        cost_t newHeight = -INFCOST;
        for(unsigned int i=0;i<G[vertex].size();++i){
            Edge const&e = G[vertex][i];
            if(e.f && newHeight < h[e.to]-e.c){
                newHeight = h[e.to] - e.c;
                state[vertex] = i;
            }
        }
        h[vertex] = newHeight - epsilon;
    }
    const int scale=2;
    pair<flow_t, cost_t> minCostFlow(){
        cost_t retCost = 0;
        for(int i=0;i<N;++i){
            for(Edge &e:G[i]){
                retCost += e.c*(e.f);
            }
        }
        //find feasible flow
        flow_t retFlow = calc_max_flow();
        excess.resize(N);h.resize(N);
        queue<int> q;
        isEnqueued.assign(N, 0); state.assign(N,0);
        // cost scaling
        for(;epsilon;epsilon>>=scale){
            fill(state.begin(), state.end(), 0);
            for(int i=0;i<N;++i)
                for(auto &e:G[i])
                    if(h[i] + e.c - h[e.to] < 0 && e.f) push(e, e.f);
            for(int i=0;i<N;++i){
                if(excess[i]>0){
                    q.push(i);
                    isEnqueued[i]=1;
                }
            }
            while(!q.empty()){
                int cur=q.front();q.pop();
                isEnqueued[cur]=0;
                // discharge
                while(excess[cur]>0){
                    if(state[cur] == G[cur].size()){
                        relabel(cur);
                    }
                    for(unsigned int &i=state[cur], max_i = G[cur].size();i<max_i;++i){
                        Edge &e=G[cur][i];
                        if(h[cur] + e.c - h[e.to] < 0){
                            push(e, excess[cur]);
                            if(excess[e.to]>0 && isEnqueued[e.to]==0){
                                q.push(e.to);
                                isEnqueued[e.to]=1;
                            }
                            if(excess[cur]==0) break;
                        }
                    }
                }
            }
            if(epsilon>1 && epsilon>>scale==0){
                epsilon = 1<<scale;
            }
        }
        for(int i=0;i<N;++i){
            for(Edge &e:G[i]){
                retCost -= e.c*(e.f);
            }
        }
        //cerr << " -> " << retFlow << " / " << retCost << " bzw. " << retCost/2/N << "\n";
        return make_pair(retFlow, retCost/2/N);
    }
    flow_t getFlow(Edge const &e){
        return G[e.to][e.rev].f;
    }
};
// pass edges in the form ... from to capacity cost

// constructor in the form indexOfLastVertex+1,source,sink

int _runtimeTerror_()
{
    int d,n;
    cin>>d>>n;
    int u = (1<<d) - 1;
    mcSFlow<> flow(2*u+3,0,2*u+1);
    vector<int> a(n);
    for(int i=0;i<n;++i)
    {
        string s;
        cin>>s;
        int x = 0;
        for(int j=0;j<d;++j)
            if(s[j] == '1')
                x += (1<<j);
        a[i] = x;
        flow.add_edge(0,a[i],1,-popcount(a[i]));
        flow.add_edge(u+a[i],2*u+1,1,0);
    }
    for(int i=0;i<n;++i)
    {
        for(int j=0;j<n;++j)
        {
            if(i == j)
                continue;
            if((a[i]&a[j]) == a[i])
            {
                flow.add_edge(a[i],u+a[j],1,0);
            }
        }
    }
    flow.minCostFlow();
    vector<int> p(u+1,-1),vis(u+1,0);
    for(int i=0;i<n;++i)
        p[a[i]] = 0;
    for(auto &j:flow.G[0])
    {
        if(flow.getFlow(j) == 1)
        {
            vis[j.to] = 1;
        }
    }
    for(int i=0;i<n;++i)
    {
        for(auto &j:flow.G[a[i]])
        {
            if(flow.getFlow(j) == 1 && j.to > u)
            {
                p[j.to-u] = a[i];
            }
        }
    }
    vector<vector<int>> chains;
    int ans = 0;
    for(int i=1;i<=u;++i)
    {
        if(vis[i] || p[i] == -1)
            continue;
        vector<int> a;
        int cur = i;
        while(cur)
        {
            a.push_back(cur);
            vis[cur] = 1;
            cur = p[cur];
        }
        a.push_back(0);
        reverse(all(a));
        vector<int> b;
        for(int i=1;i<sz(a);++i)
        {
            for(int j=0;j<d;++j)
                if((a[i]&(1<<j)) && ((a[i-1]&(1<<j)) == 0))
                    b.push_back(j);
        }
        chains.push_back(b);
        ans += sz(b);
    }
    ans += sz(chains) - 1;
    cout<<ans<<"\n";
    for(int i=0;i<sz(chains);++i)
    {
        for(auto &k:chains[i])
            cout<<k<<" ";
        if(i < sz(chains) - 1)
            cout<<"R ";
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef runSieve
        sieve();
    #endif
    #ifdef NCR
        initialize();
    #endif
    int TESTS=1;
    //cin>>TESTS;
    while(TESTS--)
        _runtimeTerror_();
    return 0;
}
```