Kod źródłowy zgłoszenia nr 928023

#include <bits/stdc++.h>
using namespace std;using ull=unsigned long long;using u32=uint32_t;using u64=uint64_t;using u16=uint16_t;static ull ac[1025][6];static vector<int>dz[11];static int dk[1024];inline ull ba(int n,int k){if(k<0||k>n)return 0;return ac[n][k];}inline uint64_t de(const vector<int>&em){uint64_t cr=0;uint64_t cz=1;for(int x:em){cr += cz*(uint64_t)x;cz *= 11;}return cr;}vector<pair<int,int>>cj(const vector<int>&ek){vector<pair<int,int>>g;for(int x:ek){if(g.empty()||g.back().first!=x)g.push_back({x,1});else g.back().second++;}return g;}ull bn(const vector<pair<int,int>>&cf){ull aj=1;for(auto [w,bc]:cf)aj *= ba((int)dz[w].size(),bc);return aj;}vector<int>ei(int N,int K,ull r){vector<int>ck;ck.reserve(K);int eb=0;for(int dj=0;dj<K;dj++){for(int i=eb;i<=N-(K-dj);i++){ull bc=ba(N-i-1,K-dj-1);if(r<bc){ck.push_back(i);eb=i + 1;break;}r -= bc;}}return ck;}ull dp(int N,int K,const vector<int>&ck){ull r=0;int eb=0;for(int dj=0;dj<K;dj++){for(int i=eb;i<ck[dj];i++)r += ba(N-i-1,K-dj-1);eb=ck[dj] + 1;}return r;}vector<int>ej(const vector<pair<int,int>>&cf,ull r){vector<int>dy;for(auto [w,bc]:cf){int N=(int)dz[w].size();ull el=ba(N,bc);ull ed=r % el;r /= el;vector<int>ck=ei(N,bc,ed);for(int id:ck)dy.push_back(dz[w][id]);}return dy;}ull dq(const vector<pair<int,int>>&cf,const vector<int>&dy){vector<vector<int>>ax(11);for(int v:dy)ax[__builtin_popcount((unsigned)v)].push_back(v);for(int w=0;w<=10;w++)sort(ax[w].begin(),ax[w].end());ull cz=1;ull aj=0;for(auto [w,bc]:cf){vector<int>ck;ck.reserve(bc);for(int v:ax[w])ck.push_back(dk[v]);ull ed=dp((int)dz[w].size(),bc,ck);aj += cz*ed;cz *= ba((int)dz[w].size(),bc);}return aj;}void bs(const vector<int>&ca,int ee,int ec,vector<int>&bl,const function<void(const vector<int>&)>&cb){if(ee==0){cb(bl);return;}for(int w=ec;w<=10;w++){bool ak=false;for(int x:ca)if(x==w){ ak=true;break;}if(ak)continue;bl.push_back(w);bs(ca,ee-1,w,bl,cb);bl.pop_back();}}static const int ad=11*11*11*11;static vector<vector<u16>>cg[11];static vector<array<int,5>>aa;static int bf[120][32];struct Family5{array<int,5>W{};vector<int>dg;vector<u32>du;};inline int cs(int a,int b,int c,int d){return ((a*11 + b)*11 + c)*11 + d;}void av(){for(int k=0;k<=10;k++)cg[k].assign(ad,{});for(int k=0;k<=10;k++){if(k==0){cg[0][0].push_back(0);continue;}u32 bi=(1u<<k)-1u;const u32 cu=1u<<16;while (bi<cu){u16 m=(u16)bi;int s[4]={0,0,0,0};u32 x=m;while (x){int b=__builtin_ctz(x);x &= x-1;for(int i=0;i<4;i++)s[i] += (b>>i)&1;}cg[k][cs(s[0],s[1],s[2],s[3])].push_back(m);u32 x2=bi&-bi;u32 y=bi + x2;bi=(((bi&~y)/x2)>>1)|y;}}}inline u32 eg(int di,u32 cw){u32 t=0;while (cw){int b=__builtin_ctz(cw);cw &= cw-1;t |= 1u<<bf[di][b];}return t;}vector<Family5>cc(){av();map<array<int,5>,int>bx;vector<Family5>by;for(int b=0;b<=10;b++){int a=10-b;if(a<0||a>16||b>16)continue;for(int k1=0;k1<ad;k1++)if(!cg[a][k1].empty()){int s0=k1/(11*11*11);int dr=k1 % (11*11*11);int s1=dr/(11*11);dr %= 11*11;int s2=dr/11;int s3=dr % 11;for(int k2=0;k2<ad;k2++)if(!cg[b][k2].empty()){int t0=k2/(11*11*11);int ds=k2 % (11*11*11);int t1=ds/(11*11);ds %= 11*11;int t2=ds/11;int t3=ds % 11;array<int,5>W={s0 + t0,s1 + t1,s2 + t2,s3 + t3,b};if(!(W[0]<=W[1]&&W[1]<=W[2]&&W[2]<=W[3]&&W[3]<=W[4]))continue;if(!bx.count(W)){Family5 bt;bt.W=W;for(int di=0;di<120;di++){const auto &df=aa[di];bool ok=true;for(int i=0;i<5;i++)if(W[i]!=W[df[i]]){ ok=false;break;}if(ok)bt.dg.push_back(di);}bx[W]=(int)by.size();by.push_back(std::move(bt));}}}}for(auto &bt:by){int b=bt.W[4],a=10-b;for(int s0=0;s0<=a;s0++)for(int s1=0;s1<=a;s1++)for(int s2=0;s2<=a;s2++)for(int s3=0;s3<=a;s3++){int t0=bt.W[0]-s0;int t1=bt.W[1]-s1;int t2=bt.W[2]-s2;int t3=bt.W[3]-s3;if(t0<0||t1<0||t2<0||t3<0)continue;if(t0>b||t1>b||t2>b||t3>b)continue;const auto &A=cg[a][cs(s0,s1,s2,s3)];const auto &B=cg[b][cs(t0,t1,t2,t3)];if(A.empty()||B.empty())continue;for(u16 lo:A){for(u16 hi:B){u32 cw=(u32)lo|((u32)hi<<16);u32 ao=cw;for(int di:bt.dg){u32 t=eg(di,cw);if(t<ao)ao=t;}if(ao!=cw)continue;int ea=0;for(int di:bt.dg)if(eg(di,cw)==cw)ea++;if(ea==1)bt.du.push_back(cw);}}}}vector<Family5>dd;dd.reserve(by.size());for(auto &bt:by)if(!bt.du.empty()){sort(bt.du.begin(),bt.du.end());dd.push_back(std::move(bt));}return dd;}vector<int>cx(u32 cw){vector<int>v;v.reserve(10);for(int c=0;c<32;c++)if((cw>>c)&1u)v.push_back(c);return v;}static const int ae=11*11*11*11*11;static vector<vector<u32>>ci[8];static vector<array<int,6>>ab;struct Family6{array<int,6>W{};vector<array<int,6>>dh;vector<array<int,64>>be;array<vector<array<u64,256>>,8>bb;vector<u64>du;};inline int ct(int a,int b,int c,int d,int e){return (((a*11 + b)*11 + c)*11 + d)*11 + e;}void aw(){for(int k=0;k<=7;k++)ci[k].assign(ae,{});ci[0][0].push_back(0);for(int k=1;k<=7;k++){u64 bi=(1ULL<<k)-1ULL;const u64 cu=1ULL<<32;while (bi<cu){u32 m=(u32)bi;int s[5]={0,0,0,0,0};u32 x=m;while (x){int b=__builtin_ctz(x);x &= x-1;for(int i=0;i<5;i++)s[i] += (b>>i)&1;}ci[k][ct(s[0],s[1],s[2],s[3],s[4])].push_back(m);u64 x2=bi&-bi;u64 y=bi + x2;bi=(((bi&~y)/x2)>>1)|y;}}}Family6 cv(const array<int,6>&W){Family6 bt;bt.W=W;for(const auto &p:ab){bool ok=true;for(int i=0;i<6;i++)if(W[i]!=W[p[i]]){ ok=false;break;}if(ok)bt.dh.push_back(p);}int P=(int)bt.dh.size();bt.be.assign(P,{});for(int di=0;di<P;di++){const auto &q=bt.dh[di];for(int c=0;c<64;c++){int nc=0;for(int j=0;j<6;j++)if((c>>j)&1)nc |= 1<<q[j];bt.be[di][c]=nc;}}for(int b=0;b<8;b++){bt.bb[b].assign(P,{});for(int di=0;di<P;di++){for(int m=0;m<256;m++){u64 dv=0;int al=8*b;int x=m;while (x){int j=__builtin_ctz((unsigned)x);x &= x-1;dv |= (1ULL<<bt.be[di][al + j]);}bt.bb[b][di][m]=dv;}}}return bt;}inline u64 eh(const Family6 &bt,int di,u64 cw){return bt.bb[0][di][cw&255ULL]| bt.bb[1][di][(cw>>8)&255ULL]| bt.bb[2][di][(cw>>16)&255ULL]| bt.bb[3][di][(cw>>24)&255ULL]| bt.bb[4][di][(cw>>32)&255ULL]| bt.bb[5][di][(cw>>40)&255ULL]| bt.bb[6][di][(cw>>48)&255ULL]| bt.bb[7][di][(cw>>56)&255ULL];}Family6 cd(const array<int,6>&W){Family6 bt=cv(W);int a=10-W[5];int b=W[5];for(int s0=0;s0<=a;s0++)for(int s1=0;s1<=a;s1++)for(int s2=0;s2<=a;s2++)for(int s3=0;s3<=a;s3++)for(int s4=0;s4<=a;s4++){int t0=W[0]-s0;int t1=W[1]-s1;int t2=W[2]-s2;int t3=W[3]-s3;int t4=W[4]-s4;if(t0<0||t1<0||t2<0||t3<0||t4<0)continue;if(t0>b||t1>b||t2>b||t3>b||t4>b)continue;const auto &A=ci[a][ct(s0,s1,s2,s3,s4)];const auto &B=ci[b][ct(t0,t1,t2,t3,t4)];if(A.empty()||B.empty())continue;for(u32 lo:A){for(u32 hi:B){u64 cw=(u64)lo|((u64)hi<<32);u64 ao=cw;for(int di=0;di<(int)bt.dh.size();di++){u64 t=eh(bt,di,cw);if(t<ao)ao=t;}if(ao!=cw)continue;int ea=0;for(int di=0;di<(int)bt.dh.size();di++)if(eh(bt,di,cw)==cw)ea++;if(ea==1)bt.du.push_back(cw);}}}sort(bt.du.begin(),bt.du.end());return bt;}vector<int>cy(u64 cw){vector<int>v;v.reserve(10);for(int c=0;c<64;c++)if((cw>>c)&1ULL)v.push_back(c);return v;}struct Bucket{uint64_t cr=0;bool co=false;int bw=-1;vector<pair<int,int>>cf;ull bm=0;ull az=0;int dn=0;};static vector<Family5>bu;static vector<Family6>bv;static vector<Bucket>au;static vector<ull>dl;static unordered_map<uint64_t,int>at;void bj(unordered_map<uint64_t,Bucket>&ao,Bucket &&ay,ull &ef){auto it=ao.find(ay.cr);if(it==ao.end()){ef += ay.az;ao.emplace(ay.cr,std::move(ay));return;}const Bucket &db=it->second;if(ay.az>db.az||(ay.az==db.az&&ay.dn<db.dn)){ef += ay.az-db.az;it->second=std::move(ay);}}void ag(unordered_map<uint64_t,Bucket>&ao,int bw,int dn,ull &ef){const auto &bt=bu[bw];vector<int>bz(bt.W.begin(),bt.W.end());vector<int>bl;bs(bz,5,0,bl,[&](const vector<int>&D){vector<int>ai;ai.reserve(10);for(int x:bt.W)ai.push_back(x);for(int x:D)ai.push_back(x);sort(ai.begin(),ai.end());auto cf=cj(D);ull bm=bn(cf);if(bm==0)return;ull az=(ull)bt.du.size()*bm;Bucket b;b.cr=de(ai);b.co=false;b.bw=bw;b.cf=cf;b.bm=bm;b.az=az;b.dn=dn;bj(ao,std::move(b),ef);});}void ah(unordered_map<uint64_t,Bucket>&ao,int bw,int dn,ull &ef){const auto &bt=bv[bw];vector<int>bz(bt.W.begin(),bt.W.end());vector<int>bl;bs(bz,4,0,bl,[&](const vector<int>&D){vector<int>ai;ai.reserve(10);for(int x:bt.W)ai.push_back(x);for(int x:D)ai.push_back(x);sort(ai.begin(),ai.end());auto cf=cj(D);ull bm=bn(cf);if(bm==0)return;ull az=(ull)bt.du.size()*bm;Bucket b;b.cr=de(ai);b.co=true;b.bw=bw;b.cf=cf;b.bm=bm;b.az=az;b.dn=dn;bj(ao,std::move(b),ef);});}void cm(){for(int n=0;n<=1024;n++)ac[n][0]=1;for(int n=1;n<=1024;n++)for(int k=1;k<=5;k++)ac[n][k]=ac[n-1][k] + ac[n-1][k-1];for(int v=0;v<1024;v++)dz[__builtin_popcount((unsigned)v)].push_back(v);for(int w=0;w<=10;w++){sort(dz[w].begin(),dz[w].end());for(int i=0;i<(int)dz[w].size();i++)dk[dz[w][i]]=i;}array<int,5>p5={0,1,2,3,4};do aa.push_back(p5);while (next_permutation(p5.begin(),p5.end()));for(int di=0;di<120;di++){const auto &df=aa[di];for(int c=0;c<32;c++){int nc=0;for(int i=0;i<5;i++)if((c>>i)&1)nc |= 1<<df[i];bf[di][c]=nc;}}array<int,6>p6={0,1,2,3,4,5};do ab.push_back(p6);while (next_permutation(p6.begin(),p6.end()));}void dm(ull da){bu=cc();unordered_map<uint64_t,Bucket>ao;ao.reserve(120000);ull ef=0;int dn=0;for(int i=0;i<(int)bu.size();i++)ag(ao,i,dn++,ef);if(ef<da){aw();static const array<array<int,6>,7>af={{{{5,5,5,6,6,7}},{{4,4,5,5,6,6}},{{4,4,5,5,5,7}},{{5,5,6,6,7,7}},{{4,4,5,5,7,7}},{{3,3,5,5,6,6}},{{3,3,4,4,5,5}}}};bv.clear();bv.reserve(7);for(const auto &W:af){bv.push_back(cd(W));ah(ao,(int)bv.size()-1,dn++,ef);if(ef>=da)break;}for(int k=0;k<=7;k++){vector<vector<u32>>().swap(ci[k]);}}au.clear();au.reserve(ao.size());for(auto &kv:ao)au.push_back(std::move(kv.second));sort(au.begin(),au.end(),[](const Bucket &a,const Bucket &b){ return a.cr<b.cr;});dl.assign(au.size()+ 1,0);at.clear();at.reserve(au.size()*2 + 1);for(int i=0;i<(int)au.size();i++){dl[i + 1]=dl[i] + au[i].az;at[au[i].cr]=i;}}vector<string>br(ull x){ull r=x-1;int ar=int(upper_bound(dl.begin(),dl.end(),r)-dl.begin())-1;ull cn=r-dl[ar];const Bucket &as=au[ar];ull dt=cn/as.bm;ull bo=cn % as.bm;vector<string>M(10,string(10,'0'));vector<int>bp=ej(as.cf,bo);if(!as.co){const Family5 &bt=bu[as.bw];u32 cw=bt.du[(size_t)dt];vector<int>bg=cx(cw);for(int i=0;i<5;i++){for(int j=0;j<10;j++)if((bg[j]>>i)&1)M[i][j]='1';}for(int i=0;i<5;i++){int v=bp[i];for(int j=0;j<10;j++)if((v>>j)&1)M[5 + i][j]='1';}} else{const Family6 &bt=bv[as.bw];u64 cw=bt.du[(size_t)dt];vector<int>bg=cy(cw);for(int i=0;i<6;i++){for(int j=0;j<10;j++)if((bg[j]>>i)&1)M[i][j]='1';}for(int i=0;i<4;i++){int v=bp[i];for(int j=0;j<10;j++)if((v>>j)&1)M[6 + i][j]='1';}}return M;}ull bq(const vector<string>&M){vector<int>dx(10);vector<int>ai;ai.reserve(10);for(int i=0;i<10;i++){int s=0;for(char ch:M[i])s += ch-'0';dx[i]=s;ai.push_back(s);}sort(ai.begin(),ai.end());uint64_t cr=de(ai);auto cq=at.find(cr);if(cq==at.end())return 1;const Bucket &as=au[cq->second];ull dt=0;vector<int>bp;if(!as.co){const Family5 &bt=bu[as.bw];bool cl[11]={false};for(int x:bt.W)cl[x]=true;vector<int>bk,ws;for(int r=0;r<10;r++)if(cl[dx[r]]){ bk.push_back(r);ws.push_back(dx[r]);}if((int)bk.size()!=5)return 1;sort(ws.begin(),ws.end());for(int i=0;i<5;i++)if(ws[i]!=bt.W[i])return 1;sort(bk.begin(),bk.end(),[&](int a,int b){if(dx[a]!=dx[b])return dx[a]<dx[b];return a<b;});int am[10];u32 an=0;for(int bh=0;bh<10;bh++){int bd=0;for(int i=0;i<5;i++)if(M[bk[i]][bh]=='1')bd |= 1<<i;am[bh]=bd;an |= 1u<<bd;}u32 ap=UINT32_MAX;int aq=-1;for(int di:bt.dg){u32 t=eg(di,an);if(t<ap){ap=t;aq=di;}}auto it=lower_bound(bt.du.begin(),bt.du.end(),ap);if(it==bt.du.end()||*it!=ap)return 1;dt=(ull)(it-bt.du.begin());vector<pair<int,int>>dc;dc.reserve(10);for(int bh=0;bh<10;bh++)dc.push_back({bf[aq][am[bh]],bh});sort(dc.begin(),dc.end());bool cp[10]={false};for(int r:bk)cp[r]=true;for(int r=0;r<10;r++)if(!cp[r]){int v=0;for(int j=0;j<10;j++)if(M[r][dc[j].second]=='1')v |= 1<<j;bp.push_back(v);}} else{const Family6 &bt=bv[as.bw];bool cl[11]={false};for(int x:bt.W)cl[x]=true;vector<int>bk,ws;for(int r=0;r<10;r++)if(cl[dx[r]]){ bk.push_back(r);ws.push_back(dx[r]);}if((int)bk.size()!=6)return 1;sort(ws.begin(),ws.end());for(int i=0;i<6;i++)if(ws[i]!=bt.W[i])return 1;sort(bk.begin(),bk.end(),[&](int a,int b){if(dx[a]!=dx[b])return dx[a]<dx[b];return a<b;});int am[10];u64 an=0;for(int bh=0;bh<10;bh++){int bd=0;for(int i=0;i<6;i++)if(M[bk[i]][bh]=='1')bd |= 1<<i;am[bh]=bd;an |= 1ULL<<bd;}u64 ap=~0ULL;int aq=-1;for(int di=0;di<(int)bt.dh.size();di++){u64 t=eh(bt,di,an);if(t<ap){ap=t;aq=di;}}auto it=lower_bound(bt.du.begin(),bt.du.end(),ap);if(it==bt.du.end()||*it!=ap)return 1;dt=(ull)(it-bt.du.begin());vector<pair<int,int>>dc;dc.reserve(10);for(int bh=0;bh<10;bh++)dc.push_back({bt.be[aq][am[bh]],bh});sort(dc.begin(),dc.end());bool cp[10]={false};for(int r:bk)cp[r]=true;for(int r=0;r<10;r++)if(!cp[r]){int v=0;for(int j=0;j<10;j++)if(M[r][dc[j].second]=='1')v |= 1<<j;bp.push_back(v);}}vector<int>dw;dw.reserve(bp.size());for(int v:bp)dw.push_back(__builtin_popcount((unsigned)v));sort(dw.begin(),dw.end());auto ce=cj(dw);if(ce!=as.cf)return 1;ull bo=dq(as.cf,bp);return dl[cq->second] + dt*as.bm + bo + 1;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cm();string en;ull n;int t;cin>>en>>n>>t;dm(n);if(dl.empty()||dl.back()<n)return 0;if(en=="Algosia"){for(int tc=0;tc<t;tc++){ull x;cin>>x;vector<string>M=br(x);for(int i=0;i<10;i++)cout<<M[i]<<'\n';cout.flush();}} else{for(int tc=0;tc<t;tc++){vector<string>M(10);for(int i=0;i<10;i++)cin>>M[i];cout<<bq(M)<<'\n';cout.flush();}}return 0;}

1
2

#include <bits/stdc++.h>
using namespace std;using ull=unsigned long long;using u32=uint32_t;using u64=uint64_t;using u16=uint16_t;static ull ac[1025][6];static vector<int>dz[11];static int dk[1024];inline ull ba(int n,int k){if(k<0||k>n)return 0;return ac[n][k];}inline uint64_t de(const vector<int>&em){uint64_t cr=0;uint64_t cz=1;for(int x:em){cr += cz*(uint64_t)x;cz *= 11;}return cr;}vector<pair<int,int>>cj(const vector<int>&ek){vector<pair<int,int>>g;for(int x:ek){if(g.empty()||g.back().first!=x)g.push_back({x,1});else g.back().second++;}return g;}ull bn(const vector<pair<int,int>>&cf){ull aj=1;for(auto [w,bc]:cf)aj *= ba((int)dz[w].size(),bc);return aj;}vector<int>ei(int N,int K,ull r){vector<int>ck;ck.reserve(K);int eb=0;for(int dj=0;dj<K;dj++){for(int i=eb;i<=N-(K-dj);i++){ull bc=ba(N-i-1,K-dj-1);if(r<bc){ck.push_back(i);eb=i + 1;break;}r -= bc;}}return ck;}ull dp(int N,int K,const vector<int>&ck){ull r=0;int eb=0;for(int dj=0;dj<K;dj++){for(int i=eb;i<ck[dj];i++)r += ba(N-i-1,K-dj-1);eb=ck[dj] + 1;}return r;}vector<int>ej(const vector<pair<int,int>>&cf,ull r){vector<int>dy;for(auto [w,bc]:cf){int N=(int)dz[w].size();ull el=ba(N,bc);ull ed=r % el;r /= el;vector<int>ck=ei(N,bc,ed);for(int id:ck)dy.push_back(dz[w][id]);}return dy;}ull dq(const vector<pair<int,int>>&cf,const vector<int>&dy){vector<vector<int>>ax(11);for(int v:dy)ax[__builtin_popcount((unsigned)v)].push_back(v);for(int w=0;w<=10;w++)sort(ax[w].begin(),ax[w].end());ull cz=1;ull aj=0;for(auto [w,bc]:cf){vector<int>ck;ck.reserve(bc);for(int v:ax[w])ck.push_back(dk[v]);ull ed=dp((int)dz[w].size(),bc,ck);aj += cz*ed;cz *= ba((int)dz[w].size(),bc);}return aj;}void bs(const vector<int>&ca,int ee,int ec,vector<int>&bl,const function<void(const vector<int>&)>&cb){if(ee==0){cb(bl);return;}for(int w=ec;w<=10;w++){bool ak=false;for(int x:ca)if(x==w){ ak=true;break;}if(ak)continue;bl.push_back(w);bs(ca,ee-1,w,bl,cb);bl.pop_back();}}static const int ad=11*11*11*11;static vector<vector<u16>>cg[11];static vector<array<int,5>>aa;static int bf[120][32];struct Family5{array<int,5>W{};vector<int>dg;vector<u32>du;};inline int cs(int a,int b,int c,int d){return ((a*11 + b)*11 + c)*11 + d;}void av(){for(int k=0;k<=10;k++)cg[k].assign(ad,{});for(int k=0;k<=10;k++){if(k==0){cg[0][0].push_back(0);continue;}u32 bi=(1u<<k)-1u;const u32 cu=1u<<16;while (bi<cu){u16 m=(u16)bi;int s[4]={0,0,0,0};u32 x=m;while (x){int b=__builtin_ctz(x);x &= x-1;for(int i=0;i<4;i++)s[i] += (b>>i)&1;}cg[k][cs(s[0],s[1],s[2],s[3])].push_back(m);u32 x2=bi&-bi;u32 y=bi + x2;bi=(((bi&~y)/x2)>>1)|y;}}}inline u32 eg(int di,u32 cw){u32 t=0;while (cw){int b=__builtin_ctz(cw);cw &= cw-1;t |= 1u<<bf[di][b];}return t;}vector<Family5>cc(){av();map<array<int,5>,int>bx;vector<Family5>by;for(int b=0;b<=10;b++){int a=10-b;if(a<0||a>16||b>16)continue;for(int k1=0;k1<ad;k1++)if(!cg[a][k1].empty()){int s0=k1/(11*11*11);int dr=k1 % (11*11*11);int s1=dr/(11*11);dr %= 11*11;int s2=dr/11;int s3=dr % 11;for(int k2=0;k2<ad;k2++)if(!cg[b][k2].empty()){int t0=k2/(11*11*11);int ds=k2 % (11*11*11);int t1=ds/(11*11);ds %= 11*11;int t2=ds/11;int t3=ds % 11;array<int,5>W={s0 + t0,s1 + t1,s2 + t2,s3 + t3,b};if(!(W[0]<=W[1]&&W[1]<=W[2]&&W[2]<=W[3]&&W[3]<=W[4]))continue;if(!bx.count(W)){Family5 bt;bt.W=W;for(int di=0;di<120;di++){const auto &df=aa[di];bool ok=true;for(int i=0;i<5;i++)if(W[i]!=W[df[i]]){ ok=false;break;}if(ok)bt.dg.push_back(di);}bx[W]=(int)by.size();by.push_back(std::move(bt));}}}}for(auto &bt:by){int b=bt.W[4],a=10-b;for(int s0=0;s0<=a;s0++)for(int s1=0;s1<=a;s1++)for(int s2=0;s2<=a;s2++)for(int s3=0;s3<=a;s3++){int t0=bt.W[0]-s0;int t1=bt.W[1]-s1;int t2=bt.W[2]-s2;int t3=bt.W[3]-s3;if(t0<0||t1<0||t2<0||t3<0)continue;if(t0>b||t1>b||t2>b||t3>b)continue;const auto &A=cg[a][cs(s0,s1,s2,s3)];const auto &B=cg[b][cs(t0,t1,t2,t3)];if(A.empty()||B.empty())continue;for(u16 lo:A){for(u16 hi:B){u32 cw=(u32)lo|((u32)hi<<16);u32 ao=cw;for(int di:bt.dg){u32 t=eg(di,cw);if(t<ao)ao=t;}if(ao!=cw)continue;int ea=0;for(int di:bt.dg)if(eg(di,cw)==cw)ea++;if(ea==1)bt.du.push_back(cw);}}}}vector<Family5>dd;dd.reserve(by.size());for(auto &bt:by)if(!bt.du.empty()){sort(bt.du.begin(),bt.du.end());dd.push_back(std::move(bt));}return dd;}vector<int>cx(u32 cw){vector<int>v;v.reserve(10);for(int c=0;c<32;c++)if((cw>>c)&1u)v.push_back(c);return v;}static const int ae=11*11*11*11*11;static vector<vector<u32>>ci[8];static vector<array<int,6>>ab;struct Family6{array<int,6>W{};vector<array<int,6>>dh;vector<array<int,64>>be;array<vector<array<u64,256>>,8>bb;vector<u64>du;};inline int ct(int a,int b,int c,int d,int e){return (((a*11 + b)*11 + c)*11 + d)*11 + e;}void aw(){for(int k=0;k<=7;k++)ci[k].assign(ae,{});ci[0][0].push_back(0);for(int k=1;k<=7;k++){u64 bi=(1ULL<<k)-1ULL;const u64 cu=1ULL<<32;while (bi<cu){u32 m=(u32)bi;int s[5]={0,0,0,0,0};u32 x=m;while (x){int b=__builtin_ctz(x);x &= x-1;for(int i=0;i<5;i++)s[i] += (b>>i)&1;}ci[k][ct(s[0],s[1],s[2],s[3],s[4])].push_back(m);u64 x2=bi&-bi;u64 y=bi + x2;bi=(((bi&~y)/x2)>>1)|y;}}}Family6 cv(const array<int,6>&W){Family6 bt;bt.W=W;for(const auto &p:ab){bool ok=true;for(int i=0;i<6;i++)if(W[i]!=W[p[i]]){ ok=false;break;}if(ok)bt.dh.push_back(p);}int P=(int)bt.dh.size();bt.be.assign(P,{});for(int di=0;di<P;di++){const auto &q=bt.dh[di];for(int c=0;c<64;c++){int nc=0;for(int j=0;j<6;j++)if((c>>j)&1)nc |= 1<<q[j];bt.be[di][c]=nc;}}for(int b=0;b<8;b++){bt.bb[b].assign(P,{});for(int di=0;di<P;di++){for(int m=0;m<256;m++){u64 dv=0;int al=8*b;int x=m;while (x){int j=__builtin_ctz((unsigned)x);x &= x-1;dv |= (1ULL<<bt.be[di][al + j]);}bt.bb[b][di][m]=dv;}}}return bt;}inline u64 eh(const Family6 &bt,int di,u64 cw){return bt.bb[0][di][cw&255ULL]| bt.bb[1][di][(cw>>8)&255ULL]| bt.bb[2][di][(cw>>16)&255ULL]| bt.bb[3][di][(cw>>24)&255ULL]| bt.bb[4][di][(cw>>32)&255ULL]| bt.bb[5][di][(cw>>40)&255ULL]| bt.bb[6][di][(cw>>48)&255ULL]| bt.bb[7][di][(cw>>56)&255ULL];}Family6 cd(const array<int,6>&W){Family6 bt=cv(W);int a=10-W[5];int b=W[5];for(int s0=0;s0<=a;s0++)for(int s1=0;s1<=a;s1++)for(int s2=0;s2<=a;s2++)for(int s3=0;s3<=a;s3++)for(int s4=0;s4<=a;s4++){int t0=W[0]-s0;int t1=W[1]-s1;int t2=W[2]-s2;int t3=W[3]-s3;int t4=W[4]-s4;if(t0<0||t1<0||t2<0||t3<0||t4<0)continue;if(t0>b||t1>b||t2>b||t3>b||t4>b)continue;const auto &A=ci[a][ct(s0,s1,s2,s3,s4)];const auto &B=ci[b][ct(t0,t1,t2,t3,t4)];if(A.empty()||B.empty())continue;for(u32 lo:A){for(u32 hi:B){u64 cw=(u64)lo|((u64)hi<<32);u64 ao=cw;for(int di=0;di<(int)bt.dh.size();di++){u64 t=eh(bt,di,cw);if(t<ao)ao=t;}if(ao!=cw)continue;int ea=0;for(int di=0;di<(int)bt.dh.size();di++)if(eh(bt,di,cw)==cw)ea++;if(ea==1)bt.du.push_back(cw);}}}sort(bt.du.begin(),bt.du.end());return bt;}vector<int>cy(u64 cw){vector<int>v;v.reserve(10);for(int c=0;c<64;c++)if((cw>>c)&1ULL)v.push_back(c);return v;}struct Bucket{uint64_t cr=0;bool co=false;int bw=-1;vector<pair<int,int>>cf;ull bm=0;ull az=0;int dn=0;};static vector<Family5>bu;static vector<Family6>bv;static vector<Bucket>au;static vector<ull>dl;static unordered_map<uint64_t,int>at;void bj(unordered_map<uint64_t,Bucket>&ao,Bucket &&ay,ull &ef){auto it=ao.find(ay.cr);if(it==ao.end()){ef += ay.az;ao.emplace(ay.cr,std::move(ay));return;}const Bucket &db=it->second;if(ay.az>db.az||(ay.az==db.az&&ay.dn<db.dn)){ef += ay.az-db.az;it->second=std::move(ay);}}void ag(unordered_map<uint64_t,Bucket>&ao,int bw,int dn,ull &ef){const auto &bt=bu[bw];vector<int>bz(bt.W.begin(),bt.W.end());vector<int>bl;bs(bz,5,0,bl,[&](const vector<int>&D){vector<int>ai;ai.reserve(10);for(int x:bt.W)ai.push_back(x);for(int x:D)ai.push_back(x);sort(ai.begin(),ai.end());auto cf=cj(D);ull bm=bn(cf);if(bm==0)return;ull az=(ull)bt.du.size()*bm;Bucket b;b.cr=de(ai);b.co=false;b.bw=bw;b.cf=cf;b.bm=bm;b.az=az;b.dn=dn;bj(ao,std::move(b),ef);});}void ah(unordered_map<uint64_t,Bucket>&ao,int bw,int dn,ull &ef){const auto &bt=bv[bw];vector<int>bz(bt.W.begin(),bt.W.end());vector<int>bl;bs(bz,4,0,bl,[&](const vector<int>&D){vector<int>ai;ai.reserve(10);for(int x:bt.W)ai.push_back(x);for(int x:D)ai.push_back(x);sort(ai.begin(),ai.end());auto cf=cj(D);ull bm=bn(cf);if(bm==0)return;ull az=(ull)bt.du.size()*bm;Bucket b;b.cr=de(ai);b.co=true;b.bw=bw;b.cf=cf;b.bm=bm;b.az=az;b.dn=dn;bj(ao,std::move(b),ef);});}void cm(){for(int n=0;n<=1024;n++)ac[n][0]=1;for(int n=1;n<=1024;n++)for(int k=1;k<=5;k++)ac[n][k]=ac[n-1][k] + ac[n-1][k-1];for(int v=0;v<1024;v++)dz[__builtin_popcount((unsigned)v)].push_back(v);for(int w=0;w<=10;w++){sort(dz[w].begin(),dz[w].end());for(int i=0;i<(int)dz[w].size();i++)dk[dz[w][i]]=i;}array<int,5>p5={0,1,2,3,4};do aa.push_back(p5);while (next_permutation(p5.begin(),p5.end()));for(int di=0;di<120;di++){const auto &df=aa[di];for(int c=0;c<32;c++){int nc=0;for(int i=0;i<5;i++)if((c>>i)&1)nc |= 1<<df[i];bf[di][c]=nc;}}array<int,6>p6={0,1,2,3,4,5};do ab.push_back(p6);while (next_permutation(p6.begin(),p6.end()));}void dm(ull da){bu=cc();unordered_map<uint64_t,Bucket>ao;ao.reserve(120000);ull ef=0;int dn=0;for(int i=0;i<(int)bu.size();i++)ag(ao,i,dn++,ef);if(ef<da){aw();static const array<array<int,6>,7>af={{{{5,5,5,6,6,7}},{{4,4,5,5,6,6}},{{4,4,5,5,5,7}},{{5,5,6,6,7,7}},{{4,4,5,5,7,7}},{{3,3,5,5,6,6}},{{3,3,4,4,5,5}}}};bv.clear();bv.reserve(7);for(const auto &W:af){bv.push_back(cd(W));ah(ao,(int)bv.size()-1,dn++,ef);if(ef>=da)break;}for(int k=0;k<=7;k++){vector<vector<u32>>().swap(ci[k]);}}au.clear();au.reserve(ao.size());for(auto &kv:ao)au.push_back(std::move(kv.second));sort(au.begin(),au.end(),[](const Bucket &a,const Bucket &b){ return a.cr<b.cr;});dl.assign(au.size()+ 1,0);at.clear();at.reserve(au.size()*2 + 1);for(int i=0;i<(int)au.size();i++){dl[i + 1]=dl[i] + au[i].az;at[au[i].cr]=i;}}vector<string>br(ull x){ull r=x-1;int ar=int(upper_bound(dl.begin(),dl.end(),r)-dl.begin())-1;ull cn=r-dl[ar];const Bucket &as=au[ar];ull dt=cn/as.bm;ull bo=cn % as.bm;vector<string>M(10,string(10,'0'));vector<int>bp=ej(as.cf,bo);if(!as.co){const Family5 &bt=bu[as.bw];u32 cw=bt.du[(size_t)dt];vector<int>bg=cx(cw);for(int i=0;i<5;i++){for(int j=0;j<10;j++)if((bg[j]>>i)&1)M[i][j]='1';}for(int i=0;i<5;i++){int v=bp[i];for(int j=0;j<10;j++)if((v>>j)&1)M[5 + i][j]='1';}} else{const Family6 &bt=bv[as.bw];u64 cw=bt.du[(size_t)dt];vector<int>bg=cy(cw);for(int i=0;i<6;i++){for(int j=0;j<10;j++)if((bg[j]>>i)&1)M[i][j]='1';}for(int i=0;i<4;i++){int v=bp[i];for(int j=0;j<10;j++)if((v>>j)&1)M[6 + i][j]='1';}}return M;}ull bq(const vector<string>&M){vector<int>dx(10);vector<int>ai;ai.reserve(10);for(int i=0;i<10;i++){int s=0;for(char ch:M[i])s += ch-'0';dx[i]=s;ai.push_back(s);}sort(ai.begin(),ai.end());uint64_t cr=de(ai);auto cq=at.find(cr);if(cq==at.end())return 1;const Bucket &as=au[cq->second];ull dt=0;vector<int>bp;if(!as.co){const Family5 &bt=bu[as.bw];bool cl[11]={false};for(int x:bt.W)cl[x]=true;vector<int>bk,ws;for(int r=0;r<10;r++)if(cl[dx[r]]){ bk.push_back(r);ws.push_back(dx[r]);}if((int)bk.size()!=5)return 1;sort(ws.begin(),ws.end());for(int i=0;i<5;i++)if(ws[i]!=bt.W[i])return 1;sort(bk.begin(),bk.end(),[&](int a,int b){if(dx[a]!=dx[b])return dx[a]<dx[b];return a<b;});int am[10];u32 an=0;for(int bh=0;bh<10;bh++){int bd=0;for(int i=0;i<5;i++)if(M[bk[i]][bh]=='1')bd |= 1<<i;am[bh]=bd;an |= 1u<<bd;}u32 ap=UINT32_MAX;int aq=-1;for(int di:bt.dg){u32 t=eg(di,an);if(t<ap){ap=t;aq=di;}}auto it=lower_bound(bt.du.begin(),bt.du.end(),ap);if(it==bt.du.end()||*it!=ap)return 1;dt=(ull)(it-bt.du.begin());vector<pair<int,int>>dc;dc.reserve(10);for(int bh=0;bh<10;bh++)dc.push_back({bf[aq][am[bh]],bh});sort(dc.begin(),dc.end());bool cp[10]={false};for(int r:bk)cp[r]=true;for(int r=0;r<10;r++)if(!cp[r]){int v=0;for(int j=0;j<10;j++)if(M[r][dc[j].second]=='1')v |= 1<<j;bp.push_back(v);}} else{const Family6 &bt=bv[as.bw];bool cl[11]={false};for(int x:bt.W)cl[x]=true;vector<int>bk,ws;for(int r=0;r<10;r++)if(cl[dx[r]]){ bk.push_back(r);ws.push_back(dx[r]);}if((int)bk.size()!=6)return 1;sort(ws.begin(),ws.end());for(int i=0;i<6;i++)if(ws[i]!=bt.W[i])return 1;sort(bk.begin(),bk.end(),[&](int a,int b){if(dx[a]!=dx[b])return dx[a]<dx[b];return a<b;});int am[10];u64 an=0;for(int bh=0;bh<10;bh++){int bd=0;for(int i=0;i<6;i++)if(M[bk[i]][bh]=='1')bd |= 1<<i;am[bh]=bd;an |= 1ULL<<bd;}u64 ap=~0ULL;int aq=-1;for(int di=0;di<(int)bt.dh.size();di++){u64 t=eh(bt,di,an);if(t<ap){ap=t;aq=di;}}auto it=lower_bound(bt.du.begin(),bt.du.end(),ap);if(it==bt.du.end()||*it!=ap)return 1;dt=(ull)(it-bt.du.begin());vector<pair<int,int>>dc;dc.reserve(10);for(int bh=0;bh<10;bh++)dc.push_back({bt.be[aq][am[bh]],bh});sort(dc.begin(),dc.end());bool cp[10]={false};for(int r:bk)cp[r]=true;for(int r=0;r<10;r++)if(!cp[r]){int v=0;for(int j=0;j<10;j++)if(M[r][dc[j].second]=='1')v |= 1<<j;bp.push_back(v);}}vector<int>dw;dw.reserve(bp.size());for(int v:bp)dw.push_back(__builtin_popcount((unsigned)v));sort(dw.begin(),dw.end());auto ce=cj(dw);if(ce!=as.cf)return 1;ull bo=dq(as.cf,bp);return dl[cq->second] + dt*as.bm + bo + 1;}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cm();string en;ull n;int t;cin>>en>>n>>t;dm(n);if(dl.empty()||dl.back()<n)return 0;if(en=="Algosia"){for(int tc=0;tc<t;tc++){ull x;cin>>x;vector<string>M=br(x);for(int i=0;i<10;i++)cout<<M[i]<<'\n';cout.flush();}} else{for(int tc=0;tc<t;tc++){vector<string>M(10);for(int i=0;i<10;i++)cin>>M[i];cout<<bq(M)<<'\n';cout.flush();}}return 0;}