#include using namespace std; // ============================================================= // Tunable parameters // PRESET = 0: FAST (時間優先、そこそこスコア) // PRESET = 1: BALANCED (推奨：5sに収めつつスコアも狙う) // PRESET = 2: AGGRESSIVE (手数優先：重いので環境によってはTLEしやすい) // ============================================================= // #ifndef PRESET #define PRESET 1 // #endif struct Params { // wall-clock guard (ms). 5s制限なので少し余裕を取る static constexpr int SOFT_TIME_LIMIT_MS = 4900; // ---- Core inference (IPF) ---- #if PRESET == 0 static constexpr int IPF_ITERS = 5; static constexpr int IPF_RECENT_RECORDS = 22; // 直近だけ使う(速い) #elif PRESET == 1 static constexpr int IPF_ITERS = 7; static constexpr int IPF_RECENT_RECORDS = 36; #else static constexpr int IPF_ITERS = 10; static constexpr int IPF_RECENT_RECORDS = 60; // ほぼ全履歴 #endif // 当たりに行く閾値（IPFの重み w は「その候補が秘密集合に含まれる確率」近似） #if PRESET == 0 static constexpr double HIT_THRESHOLD = 0.78; #elif PRESET == 1 static constexpr double HIT_THRESHOLD = 0.72; #else static constexpr double HIT_THRESHOLD = 0.68; #endif // ---- Information query search (expensive, but reduces misses early) ---- #if PRESET == 0 static constexpr bool ENABLE_INFO_QUERY = true; static constexpr int INFO_POOL_TOP = 60; static constexpr int INFO_POOL_RAND = 140; static constexpr int INFO_SAMPLE_CAND = 1600; #elif PRESET == 1 static constexpr bool ENABLE_INFO_QUERY = true; static constexpr int INFO_POOL_TOP = 90; static constexpr int INFO_POOL_RAND = 220; static constexpr int INFO_SAMPLE_CAND = 2600; #else static constexpr bool ENABLE_INFO_QUERY = true; static constexpr int INFO_POOL_TOP = 140; static constexpr int INFO_POOL_RAND = 420; static constexpr int INFO_SAMPLE_CAND = 4200; #endif // 情報質問の評価関数の係数 static constexpr double SCORE_COEF_ENT = 1.00; // エントロピー（情報量） static constexpr double SCORE_COEF_ELIM = 0.08; // 0バケット発生による候補削減期待 static constexpr double SCORE_COEF_HIT = 0.65; // 当たり確率 // ---- Endgame exact-ish solver (can be heavy) ---- #if PRESET == 2 static constexpr bool ENABLE_ENDGAME_SOLVER = true; static constexpr int ENDGAME_M_MAX = 7; static constexpr int ENDGAME_CAND_MAX = 1400; #else static constexpr bool ENABLE_ENDGAME_SOLVER = false; static constexpr int ENDGAME_M_MAX = 0; static constexpr int ENDGAME_CAND_MAX = 0; #endif // ---- Optional fixed probes (early constraints) ---- // 0なら無効。固定で数手使う代わりに序盤の絞り込みを強める。 #if PRESET == 2 static constexpr int PROBE_STEPS = 2; // 01234, 56789 を先に打つ #else static constexpr int PROBE_STEPS = 0; #endif // ---- Auto throttle by elapsed time ---- static constexpr bool AUTO_THROTTLE = true; }; // ============================================================= // Problem constants // ============================================================= static constexpr int L = 5; static constexpr int DIG = 10; static constexpr int T = 21; // (H,B) with H+B<=5 static constexpr int M_TOTAL = 30; static int IDX[L+1][L+1]; struct Stopwatch { chrono::steady_clock::time_point st = chrono::steady_clock::now(); inline int ms() const { return (int)chrono::duration_cast(chrono::steady_clock::now() - st).count(); } }; struct Code { array d{}; uint16_t mask = 0; string s; }; static vector

 generate_all_codes() {
    vector all;
    all.reserve(30240);
    array cur{};
    string buf(L, '0');

    function dfs = [&](int pos, uint16_t mask) {
        if (pos == L) {
            Code c;
            c.d = cur;
            c.mask = mask;
            c.s = buf;
            all.push_back(std::move(c));
            return;
        }
        for (int dig = 0; dig < DIG; dig++) {
            if (mask & (1u << dig)) continue;
            cur[pos] = (uint8_t)dig;
            buf[pos] = char('0' + dig);
            dfs(pos + 1, (uint16_t)(mask | (1u << dig)));
        }
    };
    dfs(0, 0);
    return all;
}

static inline uint8_t type_idx(const Code &a, const Code &q) {
    int hit = 0;
    for (int i = 0; i < L; i++) hit += (a.d[i] == q.d[i]);
    int common = __builtin_popcount((unsigned)(a.mask & q.mask));
    int blow = common - hit;
    return (uint8_t)IDX[hit][blow];
}

struct Solver {
    const vector &codes;
    const int N;
    Stopwatch sw;

    vector possible; // まだ秘密であり得る
    vector asked;    // 質問済み
    vector found;    // 発見済み(=秘密だと確定して当てた)
    int foundCount = 0;

    struct Record {
        int qid;
        array need;     // 残り秘密のヒストグラム（(5,0)除外済み）
        array aliveCnt; // possible のうち、この型に入る候補数
    };

    vector recs;
    vector> typeCache; // typeCache[r][cid] = type(code[cid], query[r])

    vector planned; // endgameで一意解が出たときの回収リスト

    // probe queries (by string)
    vector probeQids;

    explicit Solver(const vector& codes_)
        : codes(codes_), N((int)codes_.size()),
          possible(N, 1), asked(N, 0), found(N, 0) {

        // Prepare probe IDs if enabled
        if (Params::PROBE_STEPS > 0) {
            unordered_map mp;
            mp.reserve(N*2);
            for (int i=0;i probes = {"01234", "56789", "02468", "13579"};
            for (auto &s: probes) if (mp.count(s)) probeQids.push_back(mp[s]);
        }
    }

    inline bool time_low() const {
        return sw.ms() >= Params::SOFT_TIME_LIMIT_MS;
    }

    inline double time_scale() const {
        if (!Params::AUTO_THROTTLE) return 1.0;
        double t = (double)sw.ms() / (double)Params::SOFT_TIME_LIMIT_MS;
        // 早い段階は1.0、終盤は0.35くらいまで落とす
        double s = 1.0 - 0.65 * max(0.0, min(1.0, t));
        return max(0.35, s);
    }

    void kill_candidate(int cid) {
        if (!possible[cid]) return;
        possible[cid] = 0;
        for (int r = 0; r < (int)recs.size(); r++) {
            int t = typeCache[r][cid];
            recs[r].aliveCnt[t]--;
        }
    }

    void recompute_aliveCnt(int r) {
        recs[r].aliveCnt.fill(0);
        for (int cid = 0; cid < N; cid++) {
            if (!possible[cid]) continue;
            if (asked[cid]) continue;
            recs[r].aliveCnt[typeCache[r][cid]]++;
        }
    }

    void eliminate_bucket(int r, int t) {
        // need[t]==0 -> bucket 全消し
        auto &row = typeCache[r];
        for (int cid = 0; cid < N; cid++) {
            if (!possible[cid] || asked[cid]) continue;
            if (row[cid] == t) kill_candidate(cid);
        }
    }

    void apply_found_secret_to_past(int sid) {
        // 新しく見つかった秘密 sid は、過去の記録では(5,0)になっていた分だけ
        // 本来の型を1つ消す必要がある
        for (int r = 0; r < (int)recs.size(); r++) {
            int t = typeCache[r][sid];
            if (recs[r].need[t] > 0) {
                recs[r].need[t]--;
                if (recs[r].need[t] == 0) eliminate_bucket(r, t);
            }
        }
    }

    void add_record(int qid, const array &hist) {
        Record rec;
        rec.qid = qid;
        rec.need = hist;
        rec.aliveCnt.fill(0);

        vector row(N);
        for (int cid = 0; cid < N; cid++) row[cid] = type_idx(codes[cid], codes[qid]);

        typeCache.push_back(std::move(row));
        recs.push_back(std::move(rec));

        int r = (int)recs.size() - 1;
        recompute_aliveCnt(r);

        // 0 bucket elimination (exact)
        for (int t = 0; t < T; t++) {
            if (recs[r].need[t] == 0) eliminate_bucket(r, t);
        }
    }

    void observe(int qid, const vector> &hb) {
        // (-1,-1) が来たら即終了
        if (hb[0].first == -1 && hb[0].second == -1) exit(0);

        int cnt50 = 0;
        array hist{};
        hist.fill(0);
        for (auto &p: hb) {
            if (p.first == 5 && p.second == 0) cnt50++;
            else hist[IDX[p.first][p.second]]++;
        }

        asked[qid] = 1;
        // qid 自体は秘密でも秘密でなくても「未発見候補」ではない
        kill_candidate(qid);

        if (cnt50 == foundCount + 1) {
            foundCount++;
            found[qid] = 1;
            apply_found_secret_to_past(qid);
        }

        // この hist は「現在の未発見集合」に対する分布（合計は 30-cnt50）
        add_record(qid, hist);
    }

    int find_forced_hit() {
        // need[t] == aliveCnt[t] > 0 なら、そのバケットの候補は全て秘密
        for (int r = 0; r < (int)recs.size(); r++) {
            for (int t = 0; t < T; t++) {
                int need = recs[r].need[t];
                int alive = recs[r].aliveCnt[t];
                if (need > 0 && alive == need) {
                    auto &row = typeCache[r];
                    for (int cid = 0; cid < N; cid++) {
                        if (!possible[cid] || asked[cid]) continue;
                        if (row[cid] == t) return cid; // guaranteed hit
                    }
                }
            }
        }
        return -1;
    }

    // (optional) endgame: try to find unique remaining set (very limited)
    bool try_endgame_unique() {
        if (!Params::ENABLE_ENDGAME_SOLVER) return false;
        int M = M_TOTAL - foundCount;
        if (M > Params::ENDGAME_M_MAX) return false;

        vector cand;
        cand.reserve(N);
        for (int cid = 0; cid < N; cid++) if (possible[cid] && !asked[cid]) cand.push_back(cid);
        if ((int)cand.size() > Params::ENDGAME_CAND_MAX) return false;
        if (recs.empty()) return false;

        int R = (int)recs.size();

        // choose record with minimal branching (rough)
        int bestR = 0;
        double best = 1e300;
        for (int r = 0; r < R; r++) {
            array sz{};
            sz.fill(0);
            for (int cid: cand) sz[typeCache[r][cid]]++;
            double sc = 1.0;
            for (int t=0;t best) break;
            }
            if (sc < best) { best=sc; bestR=r; }
        }

        vector> bucket(T);
        bucket.assign(T, {});
        for (int i=0;i<(int)cand.size();i++){
            bucket[typeCache[bestR][cand[i]]].push_back(i);
        }

        vector> need(R);
        for (int r=0;r used(cand.size(), 0);
        vector cur;
        vector> sols;

        vector types;
        for (int t=0;t0) types.push_back(t);

        // recursion with time guard
        function dfs = [&](int ti, int pickLeft, int start) {
            if ((int)sols.size() >= 2) return;
            if (time_low()) return;

            if (ti == (int)types.size()) {
                if ((int)cur.size() != M) return;
                for (int r=0;r= 2) return;
                if (time_low()) return;
            }
        };

        dfs(0, -1, 0);

        if ((int)sols.size() == 1) {
            planned = std::move(sols[0]);
            return true;
        }
        planned.clear();
        return false;
    }

    // IPF on candidates (recent records only)
    void ipf_weights(const vector& cand, vector& w, vector& wById) {
        int M = M_TOTAL - foundCount;
        int K = (int)cand.size();
        w.assign(K, (double)M / (double)K);
        wById.assign(N, 0.0);

        int R = (int)recs.size();
        int useR = min(R, Params::IPF_RECENT_RECORDS);
        int rs = R - useR;

        int iters = Params::IPF_ITERS;
        double sc = time_scale();
        iters = max(2, (int)floor(iters * sc));

        array sum;
        array fac;

        for (int it = 0; it < iters; it++) {
            for (int r = rs; r < R; r++) {
                sum.fill(0.0);

                auto &row = typeCache[r];
                for (int i = 0; i < K; i++) {
                    sum[row[cand[i]]] += w[i];
                }
                for (int t = 0; t < T; t++) {
                    if (recs[r].need[t] == 0 || sum[t] <= 0.0) fac[t] = 0.0;
                    else fac[t] = (double)recs[r].need[t] / sum[t];
                }
                for (int i = 0; i < K; i++) {
                    w[i] *= fac[typeCache[r][cand[i]]];
                }
            }
            // normalize sum(w)=M
            double tot = 0.0;
            for (double x : w) tot += x;
            if (tot <= 0.0) break;
            double mul = (double)M / tot;
            for (double &x : w) x *= mul;
            if (time_low()) break;
        }

        for (int i = 0; i < K; i++) wById[cand[i]] = w[i];
    }

    int choose_info_query(const vector& cand, const vector& w, const vector& wById) {
        // Build query pool: top weighted candidates + random codes
        int K = (int)cand.size();
        double sc = time_scale();

        int poolTop  = (int)floor(Params::INFO_POOL_TOP  * sc);
        int poolRand = (int)floor(Params::INFO_POOL_RAND * sc);
        poolTop  = max(20, poolTop);
        poolRand = max(40, poolRand);

        int sampleN = (int)floor(Params::INFO_SAMPLE_CAND * sc);
        sampleN = max(500, sampleN);
        sampleN = min(sampleN, K);

        // top indices for poolTop / sampleN
        vector idx(K);
        iota(idx.begin(), idx.end(), 0);

        int wantTop = min(poolTop, K);
        nth_element(idx.begin(), idx.begin() + wantTop, idx.end(),
            [&](int a, int b){ return w[a] > w[b]; });
        idx.resize(wantTop);
        sort(idx.begin(), idx.end(), [&](int a, int b){ return w[a] > w[b]; });

        vector inPool(N, 0);
        vector pool;
        pool.reserve(wantTop + poolRand);

        for (int j : idx) {
            int qid = cand[j];
            if (asked[qid]) continue;
            if (!inPool[qid]) { inPool[qid] = 1; pool.push_back(qid); }
        }

        static mt19937 rng(1234567);
        uniform_int_distribution uni(0, N-1);
        while ((int)pool.size() < wantTop + poolRand && !time_low()) {
            int qid = uni(rng);
            if (asked[qid]) continue;
            if (!inPool[qid]) { inPool[qid] = 1; pool.push_back(qid); }
        }
        if (pool.empty()) return cand[idx[0]];

        // sample candidates (mostly top, plus random tail)
        vector sidx;
        sidx.reserve(sampleN);

        int topPart = min(sampleN, (int)floor(sampleN * 0.70));
        // reuse idx for bigger topPart if needed
        if (topPart > wantTop) {
            vector idx2(K);
            iota(idx2.begin(), idx2.end(), 0);
            nth_element(idx2.begin(), idx2.begin() + topPart, idx2.end(),
                [&](int a, int b){ return w[a] > w[b]; });
            idx2.resize(topPart);
            sort(idx2.begin(), idx2.end(), [&](int a, int b){ return w[a] > w[b]; });
            for (int j : idx2) sidx.push_back(j);
        } else {
            for (int i = 0; i < topPart; i++) sidx.push_back(idx[i]);
        }
        uniform_int_distribution uniK(0, K-1);
        while ((int)sidx.size() < sampleN && !time_low()) {
            sidx.push_back(uniK(rng));
        }

        // scoring
        int M = M_TOTAL - foundCount;
        vector mass(T);
        vector cnt(T);

        int bestQ = pool[0];
        double bestScore = -1e300;

        for (int qid : pool) {
            fill(mass.begin(), mass.end(), 0.0);
            fill(cnt.begin(), cnt.end(), 0);

            double massTot = 0.0;
            for (int j : sidx) {
                int sid = cand[j];
                double ww = w[j];
                uint8_t t = type_idx(codes[sid], codes[qid]);
                mass[t] += ww;
                cnt[t]  += 1;
                massTot += ww;
            }
            if (massTot <= 0.0) continue;

            // entropy
            double ent = 0.0;
            for (int t = 0; t < T; t++) {
                if (mass[t] <= 0.0) continue;
                double p = mass[t] / massTot;
                ent -= p * log(p);
            }

            // expected elimination (rough)
            double expElim = 0.0;
            for (int t = 0; t < T; t++) {
                if (mass[t] <= 0.0) continue;
                double p = mass[t] / massTot;
                double q = max(1e-12, 1.0 - p);
                double probZero = exp((double)M * log(q)); // approx (1-p)^M
                double estBucket = (double)cnt[t] * ((double)K / (double)sampleN);
                expElim += estBucket * probZero;
            }

            double hitP = wById[qid]; // 0 if not candidate
            double score = Params::SCORE_COEF_ENT * ent
                         + Params::SCORE_COEF_ELIM * (expElim / (double)max(1, K))
                         + Params::SCORE_COEF_HIT * hitP;

            if (score > bestScore) {
                bestScore = score;
                bestQ = qid;
            }
            if (time_low()) break;
        }

        return bestQ;
    }

    int choose_next() {
        if (foundCount >= M_TOTAL) return -1;

        // planned（終盤一意解）
        if (!planned.empty()) {
            int q = planned.back();
            planned.pop_back();
            return q;
        }

        // probes
        if (Params::PROBE_STEPS > 0 && (int)recs.size() < Params::PROBE_STEPS) {
            int pi = (int)recs.size();
            if (pi < (int)probeQids.size() && !asked[probeQids[pi]]) return probeQids[pi];
        }

        // forced hit
        int forced = find_forced_hit();
        if (forced != -1) return forced;

        // endgame attempt
        if (Params::ENABLE_ENDGAME_SOLVER) {
            int M = M_TOTAL - foundCount;
            if (M <= Params::ENDGAME_M_MAX && try_endgame_unique() && !planned.empty()) {
                int q = planned.back();
                planned.pop_back();
                return q;
            }
        }

        // first query (lex smallest) is "01234"
        if (recs.empty()) return 0;

        // candidates
        vector cand;
        cand.reserve(N);
        for (int cid = 0; cid < N; cid++) if (possible[cid] && !asked[cid]) cand.push_back(cid);
        if (cand.empty()) {
            for (int cid = 0; cid < N; cid++) if (!asked[cid]) return cid;
            return 0;
        }

        // IPF weights
        vector w, wById;
        ipf_weights(cand, w, wById);

        // best hit candidate
        int bestI = 0;
        for (int i = 1; i < (int)cand.size(); i++) if (w[i] > w[bestI]) bestI = i;
        int bestCid = cand[bestI];
        double bestW = w[bestI];

        // If confident enough, just hit
        if (bestW >= Params::HIT_THRESHOLD || !Params::ENABLE_INFO_QUERY || time_low()) {
            return bestCid;
        }

        // Otherwise do info-query search (bounded by parameters)
        return choose_info_query(cand, w, wById);
    }
};

int main() {
    // build IDX (H,B) -> 0..20
    int id = 0;
    for (int h = 0; h <= L; h++) {
        for (int b = 0; b <= L - h; b++) IDX[h][b] = id++;
    }

    vector codes = generate_all_codes();
    Solver solver(codes);

    while (true) {
        int qid = solver.choose_next();
        if (qid < 0) return 0;

        // output & flush (必須)  :contentReference[oaicite:5]{index=5}
        cout << codes[qid].s << '\n' << flush;

        // read 30 pairs (必ず最後まで読む) :contentReference[oaicite:6]{index=6}
        vector> hb(M_TOTAL);
        for (int i = 0; i < M_TOTAL; i++) {
            if (!(cin >> hb[i].first >> hb[i].second)) return 0;
        }

        // termination: since answers are lex-sorted, (H0,B0)=(5,0) iff all are (5,0)
        // so all secrets are found -> exit  :contentReference[oaicite:7]{index=7}
        if (hb[0].first == 5 && hb[0].second == 0) return 0;

        // invalid interaction -> exit  :contentReference[oaicite:8]{index=8}
        if (hb[0].first == -1 && hb[0].second == -1) return 0;

        solver.observe(qid, hb);
    }
}