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

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cpx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}
template <typename T, typename U>
ostream& operator<<(ostream &os, pair<T, U> p){return os << "(" << p.fs << ", " << p.sn << ")";}

int mat22[4][4] = {
    {0, 1, 2, 3},
    {2, 3, 0, 1},
    {3, 2, 1, 0},
    {1, 0, 3, 2}
};

int mat23[8][8] = {
    {0, 1, 2, 3, 4, 5, 6, 7},
    {2, 3, 0, 1, 6, 7, 4, 5},
    {4, 5, 6, 7, 0, 1, 2, 3},
    {6, 7, 4, 5, 2, 3, 0, 1},
    {3, 2, 1, 0, 7, 6, 5, 4},
    {1, 0, 3, 2, 5, 4, 7, 6},
    {7, 6, 5, 4, 3, 2, 1, 0},
    {5, 4, 7, 6, 1, 0, 3, 2}
};

int mat32[4][4][4] = {
    {
        {0, 1, 2, 3},
        {2, 3, 0, 1},
        {3, 2, 1, 0},
        {1, 0, 3, 2}
    },
    {
        {3, 2, 1, 0},
        {1, 0, 3, 2},
        {0, 1, 2, 3},
        {2, 3, 0, 1}
    },
    {
        {1, 0, 3, 2},
        {3, 2, 1, 0},
        {2, 3, 0, 1},
        {0, 1, 2, 3}
    },
    {
        {2, 3, 0, 1},
        {0, 1, 2, 3},
        {1, 0, 3, 2},
        {3, 2, 1, 0}
    }
};

int mat33[8][8][8] = {
    {
        {0, 1, 2, 3, 4, 5, 6, 7},
        {2, 3, 0, 1, 6, 7, 4, 5},
        {4, 5, 6, 7, 0, 1, 2, 3},
        {6, 7, 4, 5, 2, 3, 0, 1},
        {3, 2, 1, 0, 7, 6, 5, 4},
        {1, 0, 3, 2, 5, 4, 7, 6},
        {7, 6, 5, 4, 3, 2, 1, 0},
        {5, 4, 7, 6, 1, 0, 3, 2}
    },
    {
        {3, 2, 1, 0, 7, 6, 5, 4},
        {1, 0, 3, 2, 5, 4, 7, 6},
        {7, 6, 5, 4, 3, 2, 1, 0},
        {5, 4, 7, 6, 1, 0, 3, 2},
        {0, 1, 2, 3, 4, 5, 6, 7},
        {2, 3, 0, 1, 6, 7, 4, 5},
        {4, 5, 6, 7, 0, 1, 2, 3},
        {6, 7, 4, 5, 2, 3, 0, 1}
    },
    {
        {6, 7, 4, 5, 2, 3, 0, 1},
        {4, 5, 6, 7, 0, 1, 2, 3},
        {2, 3, 0, 1, 6, 7, 4, 5},
        {0, 1, 2, 3, 4, 5, 6, 7},
        {5, 4, 7, 6, 1, 0, 3, 2},
        {7, 6, 5, 4, 3, 2, 1, 0},
        {1, 0, 3, 2, 5, 4, 7, 6},
        {3, 2, 1, 0, 7, 6, 5, 4}
    },
    {
        {5, 4, 7, 6, 1, 0, 3, 2},
        {7, 6, 5, 4, 3, 2, 1, 0},
        {1, 0, 3, 2, 5, 4, 7, 6},
        {3, 2, 1, 0, 7, 6, 5, 4},
        {6, 7, 4, 5, 2, 3, 0, 1},
        {4, 5, 6, 7, 0, 1, 2, 3},
        {2, 3, 0, 1, 6, 7, 4, 5},
        {0, 1, 2, 3, 4, 5, 6, 7}
    },
    {
        {7, 6, 5, 4, 3, 2, 1, 0},
        {5, 4, 7, 6, 1, 0, 3, 2},
        {3, 2, 1, 0, 7, 6, 5, 4},
        {1, 0, 3, 2, 5, 4, 7, 6},
        {4, 5, 6, 7, 0, 1, 2, 3},
        {6, 7, 4, 5, 2, 3, 0, 1},
        {0, 1, 2, 3, 4, 5, 6, 7},
        {2, 3, 0, 1, 6, 7, 4, 5}
    },
    {
        {4, 5, 6, 7, 0, 1, 2, 3},
        {6, 7, 4, 5, 2, 3, 0, 1},
        {0, 1, 2, 3, 4, 5, 6, 7},
        {2, 3, 0, 1, 6, 7, 4, 5},
        {7, 6, 5, 4, 3, 2, 1, 0},
        {5, 4, 7, 6, 1, 0, 3, 2},
        {3, 2, 1, 0, 7, 6, 5, 4},
        {1, 0, 3, 2, 5, 4, 7, 6}
    },
    {
        {1, 0, 3, 2, 5, 4, 7, 6},
        {3, 2, 1, 0, 7, 6, 5, 4},
        {5, 4, 7, 6, 1, 0, 3, 2},
        {7, 6, 5, 4, 3, 2, 1, 0},
        {2, 3, 0, 1, 6, 7, 4, 5},
        {0, 1, 2, 3, 4, 5, 6, 7},
        {6, 7, 4, 5, 2, 3, 0, 1},
        {4, 5, 6, 7, 0, 1, 2, 3}
    },
    {
        {2, 3, 0, 1, 6, 7, 4, 5},
        {0, 1, 2, 3, 4, 5, 6, 7},
        {6, 7, 4, 5, 2, 3, 0, 1},
        {4, 5, 6, 7, 0, 1, 2, 3},
        {1, 0, 3, 2, 5, 4, 7, 6},
        {3, 2, 1, 0, 7, 6, 5, 4},
        {5, 4, 7, 6, 1, 0, 3, 2},
        {7, 6, 5, 4, 3, 2, 1, 0}
    }
};

int toInt(const string &str, int n){
    int x = 0;
    FR(i, n) x |= (str[i]-'0') << i;
    return x;
}

string toStr(int x, int n){
    string str;
    FR(i, n) str.pb('0' + ((x >> i) & 1));
    return str;
}

vi genInts(int c, int k, int n, vi vec){
    //dbgArr(vec, SZ(vec));
    int x = 0;
    for(int v : vec) x ^= v;
    int r;
    if(c == 2 && n == 2) r = mat22[vec[0]][vec[1]];
    if(c == 2 && n == 3) r = mat23[vec[0]][vec[1]];
    if(c == 3 && n == 2) r = mat32[vec[0]][vec[1]][vec[2]];
    if(c == 3 && n == 3) r = mat33[vec[0]][vec[1]][vec[2]];
    vec.pb(x);
    vec.pb(r);
    return vec;
}

vector<string> encode(int c, int k, int n, const vector<string> &strs){
    if(c == 3 && k == 4){
        string x(n, '0');
        FR(i, n) x[i] = strs[0][i] ^ strs[1][i] ^ strs[2][i];
        //dbg(x);
        return {strs[0], strs[1], strs[2], x};
    }
    if(n > 3){
        vector<string> res = encode(c, k, n-2, strs);
        vector<string> strEnds(c);
        FR(i, c) strEnds[i] = strs[i].substr(n-2, 2);
        vector<string> resEnds = encode(c, k, 2, strEnds);
        FR(i, k) for(char ch : resEnds[i]) res[i].pb(ch);
        return res;
    }

    vi vec;
    for(string str : strs) vec.pb(toInt(str, n));
    vi resInts = genInts(c, k, n, vec);
    vector<string> res;
    for(int a : resInts) res.pb(toStr(a, n));
    return res;
}

vector<string> encode(int c, int k, int n, string str){
    vector<string> strs(c);
    FR(i, c) strs[i] = str.substr(i*n, n);
    return encode(c, k, n, strs);
}

vector<string> decodeVec(int c, int k, int n, const vector<string> &strs, const vi &inds){
    k = *max_element(ALL(inds))+1;
    if(k == c){
        vector<string> res(c);
        FR(i, c) res[inds[i]] = strs[i];
        return res;
    }
    if(k == c+1){
        string xStr(n, 0);
        FR(i, c) FR(j, n) xStr[j] ^= strs[i][j];
        FR(i, n) xStr[i] |= '0';
        vector<string> res(c);
        FR(i, c) if(inds[i] < c) res[inds[i]] = strs[i];
        FR(i, c) if(res[i].empty()) res[i] = xStr;
        return res;
    }

    vector<string> res(c);
    if(n > 3){
        res = decodeVec(c, k, n-2, strs, inds);
        vector<string> strEnds(k);
        FR(i, c) strEnds[i] = strs[i].substr(n-2, 2);
        vector<string> resEnds = decodeVec(c, k, 2, strEnds, inds);
        FR(i, c) for(char ch : resEnds[i]) res[i].pb(ch);
        return res;
    }

    vi vec(k, -1);
    FR(i, c) vec[inds[i]] = toInt(strs[i], n);

    if(c == 2){
        FR(a, 1<<n) FR(b, 1<<n){
            vi testVec = genInts(c, k, n, {a, b});
            FR(i, k) if(vec[i] != -1 && testVec[i] != vec[i]) goto loopEnd1;
            return {toStr(a, n), toStr(b, n)};
            loopEnd1:;
        }
    }
    if(c == 3){
        FR(x, 1<<n) FR(y, 1<<n) FR(z, 1<<n){
            vi testVec = genInts(c, k, n, {x, y, z});
            FR(i, k) if(vec[i] != -1 && testVec[i] != vec[i]) goto loopEnd2;
            return {toStr(x, n), toStr(y, n), toStr(z, n)};
            loopEnd2:;
        }
    }

    assert(false);
    return {};
}

string decode(int c, int k, int n, vector<string> strs, vi inds){
    vector<string> vecRes = decodeVec(c, k, n, strs, inds);
    string res;
    for(string str : vecRes) for(char ch : str) res.pb(ch);
    return res;
}