1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
#include <algorithm>
#include <numeric>
using namespace std;

long long memo[11][1026][512];
vector<int> masks[512];

int get_next_p(int m, int p) {
    for (int j = 0; j < 9; ++j)
        if (((m >> (9 - j)) & 1) && !((m >> (8 - j)) & 1)) p |= (1 << j);
    return p;
}

long long dp(int r, int ost_m, int p) {
    if (r == 10) return (p == 511 ? 1 : 0);
    if (memo[r][ost_m][p] != -1) return memo[r][ost_m][p];
    long long maxx = 0;
    for (int m : masks[p])
        if (m < ost_m) maxx += dp(r + 1, m, get_next_p(m, p));
    return memo[r][ost_m][p] = maxx;
}

bool is_valid(int m, int p) {
    for (int j = 0; j < 9; ++j)
        if (!((p >> j) & 1))
            if (!((m >> (9 - j)) & 1) && ((m >> (8 - j)) & 1)) return false;
    return true;
}

void init() {
    memset(memo, -1, sizeof(memo));
    for (int s = 0; s < 512; ++s) {
        for (int m = 0; m < 1024; ++m)
            if (is_valid(m, s)) masks[s].push_back(m);
        sort(masks[s].rbegin(), masks[s].rend());
    }
    dp(0, 1025, 0);
}

void alg(long long n, int t) {
    for (int i = 0; i < t; ++i) {
        long long hid;
        cin >> hid;
        int ost_m = 1025, p = 0;
        vector<int> rows;
        for (int r = 0; r < 10; ++r) {
            for (int m : masks[p]) {
                if (m < ost_m) {
                    long long ways = dp(r + 1, m, get_next_p(m, p));
                    if (hid <= ways) {
                        rows.push_back(m);
                        ost_m = m;
                        p = get_next_p(m, p);
                        break;
                    }
                    hid -= ways;
                }
            }
        }
        for (int r = 0; r < 10; ++r) {
            for (int b = 9; b >= 0; --b) cout << ((rows[r] >> b) & 1);
            cout << "\n";
        }
        cout.flush();
    }
}
void baj(long long n, int t) {
    for (int i = 0; i < t; ++i) {
        vector<int> c_m(10, 0);
        for (int j = 0; j < 10; ++j) {
            string s; cin >> s;
            for (int c = 0; c < 10; ++c)
                if (s[c] == '1') c_m[j] |= (1 << (9 - c));
        }
        long long b_res = -1;
        vector<int> cols(10);
        iota(cols.begin(), cols.end(), 0);

        int cur[10];
        do {
            for(int r = 0; r < 10; ++r) {
                cur[r] = 0;
                for(int c = 0; c < 10; ++c) {
                    if ((c_m[r] >> (9 - cols[c])) & 1) cur[r] |= (1 << (9 - c));
                }
            }

            sort(cur, cur + 10, greater<int>());

            bool ok = true;
            int ost = 1025, p = 0;
            for(int r = 0; r < 10; ++r) {
                if (cur[r] >= ost || !is_valid(cur[r], p)) {
                    ok = false;
                    break;
                }
                ost = cur[r];
                p = get_next_p(cur[r], p);
            }

            if (ok && p == 511) {
                long long res = 1;
                int ost_m = 1025, cur_p = 0;
                for (int r = 0; r < 10; ++r) {
                    int tgt = cur[r];
                    for (int m : masks[cur_p]) {
                        if (m < ost_m) {
                            if (m == tgt) {
                                ost_m = m;
                                cur_p = get_next_p(m, cur_p);
                                break;
                            }
                            res += dp(r + 1, m, get_next_p(m, cur_p));
                        }
                    }
                }
                b_res = res;
                break;
            }
        } while(next_permutation(cols.begin(), cols.end()));

        cout << b_res << "\n" << flush;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string osoba;
    cin >> osoba;
    long long n;
    int t;
    cin >> n >> t;
    init();
    if (osoba == "Algosia") alg(n, t);
    else baj(n, t);
    return 0;
}