#include<bits/stdc++.h>
#include "avian.h"
using namespace std;
using ll = int;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define M(i) (1LL<<(i))
#define MP make_pair
#define ms(a) memset(a,0,sizeof (a))
namespace {
    struct way{
        ll c,k,times;
        vector <vector <ll> > a;
    };
    way all[4];
    ll cv(string s){
        ll res = 0;
        for (auto x:s)res ^= MASK(x-'0');
        return res;
    }
    bool check_basis(vector <ll> a){
        ll n = sz(a);
        vector <ll> basis(n);
        for (auto x:a){
            for (ll i = n-1;i>=0;i--){
                if (BIT(x,i)){
                    if (basis[i])x^=basis[i];
                    else {basis[i]=x;break;}
                }
            }
        }
        bool res = 1;
        for (ll i = 0;i < n; i++)res&=basis[i]!=0;
        return res;
    }
    bool check_way(ll i){
        vector <ll> a(all[i].c);
        bool ok = 1;
        function <void(ll,ll)> brute = [&](ll j1,ll j2){
            if (!ok)return;
            if (j1 == all[i].c){
                vector <ll> res;
                for (auto x:a)res.insert(res.end(),all[i].a[x].begin(),all[i].a[x].end());
                if (!check_basis(res))ok=0;
                return;
            }
            if (j2 == all[i].k)return;
            for (ll k2 = j2;k2 < all[i].k;k2 ++){
                a[j1] = k2;
                brute(j1+1,k2+1);
            }
        };
        brute(0,0);
        return ok;
    }
    void complete_way(ll i){
        if (all[i].a[all[i].k-1].back()!=-1)assert(check_way(i));
        else{
            ll maxbit = all[i].c*all[i].times;
            bool ok = 0;
            function <void(ll)> brute = [&](ll j){
                if (j==all[i].times){
                    if (check_way(i))ok=1;
                    return;
                }
                for (ll k = 0;!ok && k < MASK(maxbit);k ++){
                    all[i].a[all[i].k-1][j] = k;
                    brute(j+1);
                }
            };
            brute(0);
            assert(check_way(i));
        }
    }
    void init(){
        all[0].c=2,all[0].k=4,all[0].times=2;
        all[0].a.resize(all[0].k);
        all[0].a[0] = {cv("0"),cv("1")};all[0].a[1]={cv("2"),cv("3")};all[0].a[2] = {cv("02"),cv("13")};all[0].a[3] = {cv("012"),cv("123")};

        all[1].c=2,all[1].k=4,all[1].times=3;
        all[1].a.resize(all[1].k);
        all[1].a[0] = {cv("0"),cv("1"),cv("2")};all[1].a[1] = {cv("3"),cv("4"),cv("5")};all[1].a[2] = {cv("03"),cv("14"),cv("25")};all[1].a[3] = {cv("023"),cv("134"),cv("245")};

        all[2].c=3,all[2].k=5,all[2].times=2;
        all[2].a.resize(all[2].k);
        all[2].a[0] = {cv("0"),cv("1")};all[2].a[1]={cv("2"),cv("3")};all[2].a[2]={cv("4"),cv("5")};all[2].a[3] = {cv("024"),cv("135")};all[2].a[4] = {cv("0134"),cv("0235")};

        all[3].c=3,all[3].k=5,all[3].times=3;
        all[3].a.resize(all[3].k);
        all[3].a[0] = {cv("0"),cv("1"),cv("2")};all[3].a[1] = {cv("3"),cv("4"),cv("5")};all[3].a[2] = {cv("6"),cv("7"),cv("8")};all[3].a[3] = {cv("036"),cv("147"),cv("258")};all[3].a[4] = {cv("0146"),cv("1257"),cv("012348")};
        for (ll j = 0;j < 4;j ++)complete_way(j);
    }
    vector <string> cv1(ll type,string X){
        vector <string> res(all[type].k);
        for (ll i = 0;i < all[type].k;i ++){
            string s;s.resize(all[type].times);
            for (ll j = 0;j < all[type].times;j ++){
                ll xr = 0;
                for (ll k = 0;k < 10;k ++){
                    if (BIT(all[type].a[i][j],k)){
                        xr ^= X[k]-'0';
                    }
                }
                s[j] = xr+'0';
            }
            res[i] = s;
        }
        return res;
    }
    string cv2(ll type,vector <string> res,vector <ll> id){
        string X;X.resize(all[type].c*all[type].times);
//        cout<<"TYPE "<<type<<endl;
//        for (ll i = 0;i < sz(id);i ++){
//            cout<<id[i]<<' '<<res[i]<<endl;
//        }
        vector <pll> basis(sz(X));
        vector <pll> a;
        for (ll i1 = 0;i1 < sz(id);i1 ++){
            ll i = id[i1];
            for (ll j = 0;j < all[type].times;j ++){
                a.push_back({all[type].a[i][j],res[i1][j]-'0'});
            }
        }
//        for (auto x:a){
//            cout<<x.fi<<' '<<x.se<<endl;
//        }
        for (auto x:a){
            for (ll i = sz(X)-1;i>=0;i--){
                if (BIT(x.fi,i)){
                    if (basis[i].fi){
                        x.fi^=basis[i].fi;
                        x.se^=basis[i].se;
                    }
                    else{
                        basis[i] = x;
                        break;
                    }
                }
            }
        }
        for (ll i = 0;i < sz(X);i ++){
            ll mask = MASK(i);
            ll ans = 0;
            for (ll j = sz(X)-1;j>=0;j--){
                if (BIT(mask,j)){
                    mask^=basis[j].fi;
                    ans^=basis[j].se;
                }
            }
            X[i] = ans+'0';
        }
        return X;
    }
    vector<string> penis(ll c, ll k, ll n, string X) {
        init();
        vector <string> res(k);
        if (n%2==0){
            for (ll i = 0;i < n;i += 2){
                string tmp(X,i*c,2*c);
                vector <string> sus = cv1(0+(c==3)*2,tmp);
                for (ll j = 0;j < k;j ++){
                    res[j].insert(res[j].end(),sus[j].begin(),sus[j].end());
                }
            }
        }
        else{
            for (ll i = 0;i < n-3;i += 2){
                string tmp(X,i*c,2*c);
                vector <string> sus = cv1(0+(c==3)*2,tmp);
                for (ll j = 0;j < k;j ++){
                    res[j].insert(res[j].end(),sus[j].begin(),sus[j].end());
                }
            }
            string tmp(X,(n-3)*c,3*c);
            vector <string> sus = cv1(1+(c==3)*2,tmp);
            for (ll j = 0;j < k;j ++){
                res[j].insert(res[j].end(),sus[j].begin(),sus[j].end());
            }
        }
        return res;
    }
    string pussy(ll c,ll k,ll n,vector <string> Y,vector <ll> I){
        init();
        string ans;
        if (n % 2 == 0){
            for (ll i = 0;i < n;i += 2){
                vector <string> res(c);
                vector <ll> id(c);
                for (ll j = 0;j < c;j ++){
                    res[j] = Y[j].substr(i,2);
                    id[j] = I[j];
                }
                ans += cv2(0+(c==3)*2,res,id);
            }
        }
        else{
            for (ll i = 0;i < n-3;i += 2){
                vector <string> res(c);
                vector <ll> id(c);
                for (ll j = 0;j < c;j ++){
                    res[j] = Y[j].substr(i,2);
                    id[j] = I[j];
                }
                ans += cv2(0+(c==3)*2,res,id);
            }
            vector <string> res(c);
            vector <ll> id(c);
            for (ll j = 0;j < c;j ++){
                res[j] = Y[j].substr(n-3,3);
                id[j] = I[j];
            }
            ans += cv2(1+(c==3)*2,res,id);
        }
        return ans;
    }
}
vector<string> encode(int C, int K, int N, string X) {
	return penis(C,K,N,X);
}

string decode(int C, int K, int N, vector<string> Y, vector<int> I) {
	return pussy(C,K,N,Y,I);
}
/*#include<bits/stdc++.h>
#include "avian.h"
using namespace std;
using ll = int;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define M(i) (1LL<<(i))
#define MP make_pair
#define ms(a) memset(a,0,sizeof (a))
namespace {
    struct way{
        ll c,k,times;
        vector <vector <ll> > a;
    };
    way all[4];
    ll cv(string s){
        ll res = 0;
        for (auto x:s)res ^= MASK(x-'0');
        return res;
    }
    bool check_basis(vector <ll> a){
        ll n = sz(a);
        vector <ll> basis(n);
        for (auto x:a){
            for (ll i = n-1;i>=0;i--){
                if (BIT(x,i)){
                    if (basis[i])x^=basis[i];
                    else {basis[i]=x;break;}
                }
            }
        }
        bool res = 1;
        for (ll i = 0;i < n; i++)res&=basis[i]!=0;
        return res;
    }
    bool check_way(ll i){
        vector <ll> a(all[i].c);
        bool ok = 1;
        function <void(ll,ll)> brute = [&](ll j1,ll j2){
            if (!ok)return;
            if (j1 == all[i].c){
                vector <ll> res;
                for (auto x:a)res.insert(res.end(),all[i].a[x].begin(),all[i].a[x].end());
                if (!check_basis(res))ok=0;
                return;
            }
            if (j2 == all[i].k)return;
            for (ll k2 = j2;k2 < all[i].k;k2 ++){
                a[j1] = k2;
                brute(j1+1,k2+1);
            }
        };
        brute(0,0);
        return ok;
    }
    void complete_way(ll i){
        if (all[i].a[all[i].k-1].back()!=-1)assert(check_way(i));
        else{
            ll maxbit = all[i].c*all[i].times;
            bool ok = 0;
            function <void(ll)> brute = [&](ll j){
                if (j==all[i].times){
                    if (check_way(i))ok=1;
                    return;
                }
                for (ll k = 0;!ok && k < MASK(maxbit);k ++){
                    all[i].a[all[i].k-1][j] = k;
                    brute(j+1);
                }
            };
            brute(0);
            assert(check_way(i));
        }
    }
    void init(){
        all[0].c=2,all[0].k=4,all[0].times=2;
        all[0].a.resize(all[0].k);
        all[0].a[0] = {cv("0"),cv("1")};all[0].a[1]={cv("2"),cv("3")};all[0].a[2] = {cv("02"),cv("13")};all[0].a[3] = {cv("012"),cv("123")};

        all[1].c=2,all[1].k=4,all[1].times=3;
        all[1].a.resize(all[1].k);
        all[1].a[0] = {cv("0"),cv("1"),cv("2")};all[1].a[1] = {cv("3"),cv("4"),cv("5")};all[1].a[2] = {cv("03"),cv("14"),cv("25")};all[1].a[3] = {cv("023"),cv("134"),cv("245")};

        all[2].c=3,all[2].k=5,all[2].times=2;
        all[2].a.resize(all[2].k);
        all[2].a[0] = {cv("0"),cv("1")};all[2].a[1]={cv("2"),cv("3")};all[2].a[2]={cv("4"),cv("5")};all[2].a[3] = {cv("024"),cv("135")};all[2].a[4] = {cv("0134"),cv("0235")};

        all[3].c=3,all[3].k=5,all[3].times=3;
        all[3].a.resize(all[3].k);
        all[3].a[0] = {cv("0"),cv("1"),cv("2")};all[3].a[1] = {cv("3"),cv("4"),cv("5")};all[3].a[2] = {cv("6"),cv("7"),cv("8")};all[3].a[3] = {cv("036"),cv("147"),cv("258")};all[3].a[4] = {cv("0146"),cv("1257"),cv("012348")};
        for (ll j = 0;j < 4;j ++)complete_way(j);
    }
    vector <string> cv1(ll type,string X){
        vector <string> res(all[type].k);
        for (ll i = 0;i < all[type].k;i ++){
            string s;s.resize(all[type].times);
            for (ll j = 0;j < all[type].times;j ++){
                ll xr = 0;
                for (ll k = 0;k < 10;k ++){
                    if (BIT(all[type].a[i][j],k)){
                        xr ^= X[k]-'0';
                    }
                }
                s[j] = xr+'0';
            }
            res[i] = s;
        }
        return res;
    }
    string cv2(ll type,vector <string> res,vector <ll> id){
        string X;X.resize(all[type].c*all[type].times);
//        cout<<"TYPE "<<type<<endl;
//        for (ll i = 0;i < sz(id);i ++){
//            cout<<id[i]<<' '<<res[i]<<endl;
//        }
        vector <pll> basis(sz(X));
        vector <pll> a;
        for (ll i1 = 0;i1 < sz(id);i1 ++){
            ll i = id[i1];
            for (ll j = 0;j < all[type].times;j ++){
                a.push_back({all[type].a[i][j],res[i1][j]-'0'});
            }
        }
//        for (auto x:a){
//            cout<<x.fi<<' '<<x.se<<endl;
//        }
        for (auto x:a){
            for (ll i = sz(X)-1;i>=0;i--){
                if (BIT(x.fi,i)){
                    if (basis[i].fi){
                        x.fi^=basis[i].fi;
                        x.se^=basis[i].se;
                    }
                    else{
                        basis[i] = x;
                        break;
                    }
                }
            }
        }
        for (ll i = 0;i < sz(X);i ++){
            ll mask = MASK(i);
            ll ans = 0;
            for (ll j = sz(X)-1;j>=0;j--){
                if (BIT(mask,j)){
                    mask^=basis[j].fi;
                    ans^=basis[j].se;
                }
            }
            X[i] = ans+'0';
        }
        return X;
    }
    vector<string> penis(ll c, ll k, ll n, string X) {
        init();
        vector <string> res(k);
        if (n%2==0){
            for (ll i = 0;i < n;i += 2){
                string tmp(X,i*c,2*c);
                vector <string> sus = cv1(0+(c==3)*2,tmp);
                for (ll j = 0;j < k;j ++){
                    res[j].insert(res[j].end(),sus[j].begin(),sus[j].end());
                }
            }
        }
        else{
            for (ll i = 0;i < n-3;i += 2){
                string tmp(X,i*c,2*c);
                vector <string> sus = cv1(0+(c==3)*2,tmp);
                for (ll j = 0;j < k;j ++){
                    res[j].insert(res[j].end(),sus[j].begin(),sus[j].end());
                }
            }
            string tmp(X,(n-3)*c,3*c);
            vector <string> sus = cv1(1+(c==3)*2,tmp);
            for (ll j = 0;j < k;j ++){
                res[j].insert(res[j].end(),sus[j].begin(),sus[j].end());
            }
        }
        return res;
    }
    string pussy(ll c,ll k,ll n,vector <string> Y,vector <ll> I){
        init();
        string ans;
        if (n % 2 == 0){
            for (ll i = 0;i < n;i += 2){
                vector <string> res(c);
                vector <ll> id(c);
                for (ll j = 0;j < c;j ++){
                    res[j] = Y[j].substr(i,2);
                    id[j] = I[j];
                }
                ans += cv2(0+(c==3)*2,res,id);
            }
        }
        else{
	return pussy(C,K,N,Y,I);
}
*/