#1159330 (C++17) No.3501 Digit Products 2

• 問題: No.3501 Digit Products 2
• ユーザー: おおえはるき
• 提出日時: 2026-04-18 09:39:16
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 29,684 bytes
• コンパイル時間: 2,389 ms
• コンパイル使用メモリ: 261,216 KB
• 実行使用メモリ: 30,332 KB
• 平均クエリ数: 11.44
• 最終ジャッジ日時: 2026-04-18 09:39:42
• 合計ジャッジ時間: 18,711 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	WA * 1
other	WA * 72

ソースコード

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

using ll = long long;
using str = string;

static int intMin = numeric_limits<int>::min();
static int intMax = numeric_limits<int>::max();
static long long longMin = numeric_limits<long long>::min();
static long long longMax = numeric_limits<long long>::max();
const ll INF = 1e9 + 7;
static ll mod = 998244353;
static long long di[] = { -1, 0, 1, 0, -1, -1, 1, 1};
static long long dj[] = { 0, 1, 0, -1, -1, 1, -1, 1};

class ReadArray { public:
    vector<int> in() { string s; getline(cin >> ws, s); istringstream is(s); return vector<int>(istream_iterator<int>(is), {}); }
    vector<long long> ll() { string s; getline(cin >> ws, s); istringstream is(s); return vector<long long>(istream_iterator<long long>(is), {}); }
    vector<float> fl() { string s; getline(cin >> ws, s); istringstream is(s); return vector<float>(istream_iterator<float>(is), {}); }
    vector<double> dbl() { string s; getline(cin >> ws, s); istringstream is(s); return vector<double>(istream_iterator<double>(is), {}); }
    vector<string> str() { string s; getline(cin >> ws, s); istringstream is(s); return vector<string>(istream_iterator<string>(is), {}); }
    vector<char> ch() { string s; getline(cin >> ws, s); istringstream is(s); vector<char> v; for (char c; is >> c;) v.push_back(c); return v; }
}; ReadArray readArray;
class ReadMap { public:
    vector<vector<int>> in(int h, int w) { vector<vector<int>> r(h,vector<int>(w)); for(int i=0;i<h;i++){auto s = readArray.in(); for(int j=0;j<w;j++) r.at(i).at(j)=s.at(j);} return r; }
    vector<vector<long long>> ll(int h, int w) { vector<vector<long long>> r(h,vector<long long>(w)); for(int i=0;i<h;i++){auto s = readArray.ll(); for(int j=0;j<w;j++) r.at(i).at(j)=s.at(j);} return r; }
    vector<vector<char>> ch(int h, int w) { vector<vector<char>> r(h,vector<char>(w)); for(int i=0;i<h;i++){string s; cin >> s; for(int j=0;j<w;j++) r.at(i).at(j)=s.at(j);} return r; }
    vector<vector<bool>> bo(int h, int w, char c = '.') { vector<vector<bool>> r(h,vector<bool>(w)); for(int i=0;i<h;i++){string s; cin >> s; for(int j=0;j<w;j++) r.at(i).at(j)=(s.at(j)==c);} return r;}
};
class ReadFunctions { public:
    int in() { int x; scanf("%d", &x); return x; }
    auto in2() { int x, y; scanf("%d %d", &x, &y); return make_tuple(x, y); }
    auto in3() { int x, y, z; scanf("%d %d %d", &x, &y, &z); return make_tuple(x, y, z); }
    auto in4() { int x, y, z, w; scanf("%d %d %d %d", &x, &y, &z, &w); return make_tuple(x, y, z, w); }
    auto in5() { int x, y, z, w, u; scanf("%d %d %d %d %d", &x, &y, &z, &w, &u); return make_tuple(x, y, z, w, u); }
    auto in6() { int x, y, z, w, u, v; scanf("%d %d %d %d %d %d", &x, &y, &z, &w, &u, &v); return make_tuple(x, y, z, w, u, v); }
    long long ll() { long long x; scanf("%lld", &x); return x; }
    auto ll2() { long long x, y; scanf("%lld %lld", &x, &y); return make_tuple(x, y); }
    auto ll3() { long long x, y, z; scanf("%lld %lld %lld", &x, &y, &z); return make_tuple(x, y, z); }
    auto ll4() { long long x, y, z, w; scanf("%lld %lld %lld %lld", &x, &y, &z, &w); return make_tuple(x, y, z, w); }
    auto ll5() { long long x, y, z, w, u; scanf("%lld %lld %lld %lld %lld", &x, &y, &z, &w, &u); return make_tuple(x, y, z, w, u); }
    auto ll6() { long long x, y, z, w, u, v; scanf("%lld %lld %lld %lld %lld %lld", &x, &y, &z, &w, &u, &v); return make_tuple(x, y, z, w, u, v); }
    float fl() { float x; scanf("%f", &x); return x; }
    double dbl() { double x; scanf("%lf", &x); return x; }
    string str() { string x; cin >> x; return x; }
    char cha() { char x; scanf(" %c", &x); return x; }
    
    ReadArray array;
    ReadMap map;
}; ReadFunctions re;

void write(string s) { printf("%s\n", s.c_str()); }
void write(char c) { printf("%c\n", c); }
void write(int n) { printf("%i\n", n); }
void write(long long n) { printf("%lld\n", n); }
void write(double n) { printf("%.10f\n", n); }
void write(bool a) { printf("%s\n", a ? "Yes" : "No"); }
void writeMinus1() {printf("%i\n", -1);}

/* keysにそってvalueをソート */
template <typename T> void Sort(std::vector<T>& keys, std::vector<T>& values) {
    std::vector<std::pair<T, T>> paired;
    for (size_t i = 0; i < keys.size(); ++i) {
        paired.emplace_back(keys[i], values[i]);
    }
    std::sort(paired.begin(), paired.end());
    for (size_t i = 0; i < keys.size(); ++i) {
        keys[i] = paired[i].first;
        values[i] = paired[i].second;
    }
}
template <typename T> void Sort(vector<T> &array) {sort(array.begin(), array.end());}
template <typename T> void Reverse(vector<T> &array) {reverse(array.begin(), array.end());}

struct pair_hash {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ (h2 << 1); // XORとビットシフトを利用してハッシュを合成
    }
};
struct tuple_hash {
    template <typename... T>
    size_t operator()(const tuple<T...>& t) const {
        size_t seed = 0;
        apply([&seed](const auto&... args) {
            ((seed ^= 
                hash<decay_t<decltype(args)>>{}(args)
                + 0x9e3779b97f4a7c15ULL
                + (seed << 6)
                + (seed >> 2)
            ), ...);
        }, t);
        return seed;
    }
};

long long average(long long a, long long b) {return a + (b - a) / 2; }
long long kaijou(long long v) { long long r = 1; for (long long i = v; i > 0; i--) r *= i; return r; }
long long yojou(int v, int v2) { long long r = v % v2; return r < 0 ? r + v2 : r; }
long long yojou(ll v, ll v2) { long long r = v % v2; return r < 0 ? r + v2 : r; }
int digit_count(long long n) {if(n==0)return 1;n=llabs(n);int cnt=0;while(n>0){cnt++;n/=10;}return cnt;}
bool rangeCheck(int i, int j, int h, int w) { return (0 <= i && i < h && 0 <= j && j < w);}
long long power(long long base, long long exp) { long long result = 1; for (int i = 0; i < exp; ++i) result *= base; return result; }
long long modPow(long long r, long long n) {long long res = 1; r %= mod; while (n > 0) { if (n & 1) res *= r; res %= mod; r *= r; r %= mod; n >>= 1;} return res % mod;}
long long modinv(long long a) { ll b = mod, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v);	} u %= mod; if (u < 0) u += mod; return u; }
int popcount(ll num) {int count = 0;while(num){count+=num&1;num>>=1;}return count;}
long long GCD(long long a, long long b) {if(b==0)return a;return GCD(b,a%b);}

mt19937 rng(123456);  // 固定seed（好きな数字でOK）
// [l, r] の整数乱数
int rand_int(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}
// [0, 1) の実数乱数
double rand_double() {
    uniform_real_distribution<double> dist(0.0, 1.0);
    return dist(rng);
}
class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank;

public:
    // コンストラクタ: 要素数nの集合を作成
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 1); // 初期ランクは1
        for (int i = 0; i < n; ++i) {
            parent[i] = i; // 各要素は自分自身が親
        }
    }

    // Find: xが属する集合の代表を返す（経路圧縮付き）
    int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            // 経路圧縮：再帰的に親を探して更新
            return parent[x] = find(parent[x]);
        }
    }

    // Union: xとyの集合を統合する（ランク付き）
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // ランクの高い方に統合
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                // ランクが同じ場合、どちらかに統合しランクを上げる
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    // 同じ集合に属しているかを判定する
    bool isSameSet(int x, int y) {
        return find(x) == find(y);
    }
};

template <typename T> int FindEqual(vector<T> &vec, T target) {
    int l = 0; int r = vec.size()-1;
    int ret = -1;
    while(l <= r) {
        int mid = (l + r)/2;
        if(vec.at(mid) > target) {
            r = mid - 1;
        }
        else if(vec.at(mid) == target)
        {
            ret = mid;
            break;
        }
        else l = mid + 1;
    }
    return ret;
}
template <typename T> int FindFirstGreater(vector<T> &vec, T target) {
    int l = 0; int r = vec.size()-1;
    int ret = -1;
    while(l <= r) {
        int mid = (l + r)/2;
        if(vec.at(mid) >= target) {
            ret = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return ret;
}
template <typename T> int FindFirstLess(vector<T> &vec, T target) {
    int l = 0; int r = vec.size()-1;
    int ret = -1;
    while(l <= r) {
        int mid = (l + r)/2;
        if(vec.at(mid) <= target) {
            ret = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return ret;
}

class SegmentTreeSum {
private:
    std::vector<long long> tree; // セグメントツリー
    int size; // 配列のサイズ

    // セグメントツリーの構築
    void build(const std::vector<int>& arr, int node, int start, int end) {
        if (start == end) {
            // 葉ノードの場合
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            // 左右の子ノードを再帰的に構築
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            // 子ノードをマージ
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

    // 範囲クエリ
    long long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            // 範囲外の場合
            return 0;
        }
        if (l <= start && end <= r) {
            // 完全に範囲内の場合
            return tree[node];
        }
        // 範囲が部分的に重なる場合
        int mid = (start + end) / 2;
        long long leftSum = query(2 * node + 1, start, mid, l, r);
        long long rightSum = query(2 * node + 2, mid + 1, end, l, r);
        return leftSum + rightSum;
    }

    // 値の更新
    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            // 葉ノードを更新
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (start <= idx && idx <= mid) {
                // 左部分木を更新
                update(2 * node + 1, start, mid, idx, val);
            } else {
                // 右部分木を更新
                update(2 * node + 2, mid + 1, end, idx, val);
            }
            // 子ノードの値を基に現在のノードを更新
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }
    }

public:
    // コンストラクタ: 配列を受け取り、セグメントツリーを構築
    SegmentTreeSum(const std::vector<int>& arr) {
        size = arr.size();
        tree.resize(4 * size);
        build(arr, 0, 0, size - 1);
    }

    // 範囲クエリの公開メソッド
    long long query(int l, int r) {
        return query(0, 0, size - 1, l, r);
    }

    // 値の更新の公開メソッド
    void update(int idx, int val) {
        update(0, 0, size - 1, idx, val);
    }
};
class SegmentTreeMax {
private:
    std::vector<long long> tree; // セグメントツリー（区間の最大値）
    int size; // 配列のサイズ

    // セグメントツリーの構築
    void build(const std::vector<long long>& arr, int node, int start, int end) {
        if (start == end) {
            // 葉ノードの場合
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            // 左右の子ノードを再帰的に構築
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            // 子ノードをマージ（最大値を保持）
            tree[node] = std::max(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    // 範囲クエリ（最大値を取得）
    long long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            // 範囲外の場合（最小値を返す）
            return LLONG_MIN;
        }
        if (l <= start && end <= r) {
            // 完全に範囲内の場合
            return tree[node];
        }
        // 範囲が部分的に重なる場合
        int mid = (start + end) / 2;
        long long leftMax = query(2 * node + 1, start, mid, l, r);
        long long rightMax = query(2 * node + 2, mid + 1, end, l, r);
        return std::max(leftMax, rightMax); // 最大値を取得
    }

    // 値の更新
    void update(int node, int start, int end, int idx, long long val) {
        if (start == end) {
            // 葉ノードを更新
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                // 左部分木を更新
                update(2 * node + 1, start, mid, idx, val);
            } else {
                // 右部分木を更新
                update(2 * node + 2, mid + 1, end, idx, val);
            }
            // 親ノードの値を更新（最大値を保持）
            tree[node] = std::max(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

public:
    // コンストラクタ: 配列を受け取り、セグメントツリーを構築
    SegmentTreeMax(const std::vector<long long>& arr) {
        size = arr.size();
        tree.resize(4 * size);
        build(arr, 0, 0, size - 1);
    }

    // 範囲クエリ（最大値）の公開メソッド
    long long query(int l, int r) {
        return query(0, 0, size - 1, l, r);
    }

    // 値の更新の公開メソッド
    void update(int idx, long long val) {
        update(0, 0, size - 1, idx, val);
    }
};
class SegmentTreeMin {
private:
    std::vector<long long> tree; // セグメントツリー（区間の最小値）
    int size; // 配列のサイズ

    // セグメントツリーの構築
    void build(const std::vector<long long>& arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node + 1, start, mid);
            build(arr, 2 * node + 2, mid + 1, end);
            tree[node] = std::min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    // 範囲クエリ（最小値を取得）
    long long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return LLONG_MAX; // 範囲外なら最大値を返す（最小値を取るため）
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        long long leftMin = query(2 * node + 1, start, mid, l, r);
        long long rightMin = query(2 * node + 2, mid + 1, end, l, r);
        return std::min(leftMin, rightMin); // 最小値を取得
    }

    // 値の更新
    void update(int node, int start, int end, int idx, long long val) {
        if (start == end) {
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                update(2 * node + 1, start, mid, idx, val);
            } else {
                update(2 * node + 2, mid + 1, end, idx, val);
            }
            tree[node] = std::min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

public:
    SegmentTreeMin(const std::vector<long long>& arr) {
        size = arr.size();
        tree.resize(4 * size);
        build(arr, 0, 0, size - 1);
    }

    long long query(int l, int r) {
        return query(0, 0, size - 1, l, r);
    }

    void update(int idx, long long val) {
        update(0, 0, size - 1, idx, val);
    }
};

class LazySegmentTreeSum {
private:
    int n;                           // 配列のサイズ
    vector<long long> tree;          // セグメントツリーのデータ
    vector<long long> lazy;          // 遅延評価用のデータ

    // 区間の合計を計算する (加算クエリに対応)
    void apply(int node, int start, int end, long long value) {
        tree[node] += value * (end - start + 1); // ノードの値を更新
        if (start != end) { // 子ノードが存在する場合
            lazy[node * 2] += value;     // 左の子ノードに遅延を追加
            lazy[node * 2 + 1] += value; // 右の子ノードに遅延を追加
        }
    }

    // 遅延を伝播する
    void propagate(int node, int start, int end) {
        if (lazy[node] != 0) { // 遅延が存在する場合
            apply(node, start, end, lazy[node]);
            lazy[node] = 0; // 遅延をクリア
        }
    }

    // 区間更新 (内部)
    void updateRange(int node, int start, int end, int l, int r, long long value) {
        propagate(node, start, end); // 遅延を反映

        if (start > r || end < l) return; // 完全に範囲外
        if (start >= l && end <= r) {     // 完全に範囲内
            apply(node, start, end, value);
            return;
        }

        // 部分的に範囲内
        int mid = (start + end) / 2;
        updateRange(node * 2, start, mid, l, r, value);
        updateRange(node * 2 + 1, mid + 1, end, l, r, value);
        tree[node] = tree[node * 2] + tree[node * 2 + 1]; // 子ノードの結果を合成
    }

    // 区間クエリ (内部)
    long long queryRange(int node, int start, int end, int l, int r) {
        propagate(node, start, end); // 遅延を反映

        if (start > r || end < l) return 0; // 完全に範囲外
        if (start >= l && end <= r) return tree[node]; // 完全に範囲内

        // 部分的に範囲内
        int mid = (start + end) / 2;
        long long left = queryRange(node * 2, start, mid, l, r);
        long long right = queryRange(node * 2 + 1, mid + 1, end, l, r);
        return left + right; // 子ノードの結果を合成
    }

public:
    LazySegmentTreeSum(int size) {
        n = size;
        tree.resize(4 * n, 0); // セグメントツリーのサイズ
        lazy.resize(4 * n, 0); // 遅延配列のサイズ
    }

    // 区間更新
    void update(int l, int r, long long value) {
        updateRange(1, 0, n - 1, l, r, value);
    }

    // 区間クエリ
    long long query(int l, int r) {
        return queryRange(1, 0, n - 1, l, r);
    }
};
class LazySegmentTreeMax {
private:
    int n;                            // 配列サイズ
    vector<long long> tree;           // 区間最大値
    vector<long long> lazy;           // 遅延加算

    // 遅延値をノードに適用
    void apply(int node, int start, int end, long long value) {
        tree[node] += value;          // 最大値に加算
        if (start != end) {           // 葉でなければ子へ遅延伝播
            lazy[node * 2] += value;
            lazy[node * 2 + 1] += value;
        }
    }

    // 遅延伝播
    void propagate(int node, int start, int end) {
        if (lazy[node] != 0) {
            apply(node, start, end, lazy[node]);
            lazy[node] = 0;
        }
    }

    // 区間更新
    void updateRange(int node, int start, int end,
                     int l, int r, long long value) {
        propagate(node, start, end);

        if (start > r || end < l) return; // 範囲外

        if (start >= l && end <= r) {     // 完全包含
            apply(node, start, end, value);
            return;
        }

        int mid = (start + end) / 2;
        updateRange(node * 2, start, mid, l, r, value);
        updateRange(node * 2 + 1, mid + 1, end, l, r, value);

        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }

    // 区間クエリ
    long long queryRange(int node, int start, int end,
                         int l, int r) {
        propagate(node, start, end);

        if (start > r || end < l) return LLONG_MIN; // 単位元
        if (start >= l && end <= r) return tree[node];

        int mid = (start + end) / 2;
        long long left = queryRange(node * 2, start, mid, l, r);
        long long right = queryRange(node * 2 + 1, mid + 1, end, l, r);

        return max(left, right);
    }

public:
    LazySegmentTreeMax(int size) {
        n = size;
        tree.resize(4 * n, 0);
        lazy.resize(4 * n, 0);
    }

    // 区間加算
    void update(int l, int r, long long value) {
        updateRange(1, 0, n - 1, l, r, value);
    }

    // 区間最大値取得
    long long query(int l, int r) {
        return queryRange(1, 0, n - 1, l, r);
    }
};
class LazySegmentTreeMin {
private:
    int n;                            // 配列のサイズ
    vector<long long> tree;           // 区間最小値を保持
    vector<long long> lazy;           // 遅延加算を保持

    // 遅延を適用
    void apply(int node, int start, int end, long long value) {
        tree[node] += value; // 区間の最小値を一括加算
        if (start != end) { // 葉でなければ子に遅延を伝える
            lazy[node * 2] += value;
            lazy[node * 2 + 1] += value;
        }
    }

    // 遅延を伝播
    void propagate(int node, int start, int end) {
        if (lazy[node] != 0) {
            apply(node, start, end, lazy[node]);
            lazy[node] = 0;
        }
    }

    // 区間更新 (内部)
    void updateRange(int node, int start, int end, int l, int r, long long value) {
        propagate(node, start, end);

        if (start > r || end < l) return; // 範囲外
        if (start >= l && end <= r) {     // 完全に範囲内
            apply(node, start, end, value);
            return;
        }

        int mid = (start + end) / 2;
        updateRange(node * 2, start, mid, l, r, value);
        updateRange(node * 2 + 1, mid + 1, end, l, r, value);
        tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
    }

    // 区間クエリ (内部)
    long long queryRange(int node, int start, int end, int l, int r) {
        propagate(node, start, end);

        if (start > r || end < l) return LLONG_MAX; // 範囲外は無限大
        if (start >= l && end <= r) return tree[node];

        int mid = (start + end) / 2;
        long long left = queryRange(node * 2, start, mid, l, r);
        long long right = queryRange(node * 2 + 1, mid + 1, end, l, r);
        return min(left, right);
    }

public:
    LazySegmentTreeMin(int size) {
        n = size;
        tree.resize(4 * n, 0);  // 区間最小値 (初期値は0で構築)
        lazy.resize(4 * n, 0);  // 遅延配列
    }

    // 区間更新
    void update(int l, int r, long long value) {
        updateRange(1, 0, n - 1, l, r, value);
    }

    // 区間クエリ
    long long query(int l, int r) {
        return queryRange(1, 0, n - 1, l, r);
    }
};

vector<long long> fact, fact_inv, inv;
/*  init_nCk :二項係数のための前処理
    計算量:O(n)
*/
void init_nCk(int SIZE) {
    fact.resize(SIZE + 5);
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}
/*  nCk :modでの二項係数を求める(前処理 int_nCk が必要)
    計算量:O(1)
*/
long long nCk(int n, int k) {
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod;
}

static vector<ll> memo = {-1};
/*
void dfs(int v, vector<vector<ll>> &con, vector<ll> &ans, vector<bool> &seen, vector<bool> &finished, ll &cnt)
{
    for(int u : con.at(v))
    {
        if(finished.at(u)) continue;
        
        if(seen.at(u))
        {
            if(cnt > 0)
            {
                cout << "! -1" << endl;
                cnt = 100;
                return;
            }
            
            cnt++;
            memo = ans;
        }

        ans.push_back(u);
        seen.at(u) = true;
        
        dfs(u, con, ans, seen, finished, cnt);
        if(cnt > 1) return;

        seen.at(u) = false;
        ans.pop_back();
    }
    finished.at(v) = true;

    return;
}
*/
// 辺を表す構造体
template<class T> struct Edge {
    int from, to;
    T val;
    Edge(int f = -1, int t = -1, T v = -1) : from(f), to(t), val(v) {}
};

// グラフを表す型
template<class T> using Graph = vector<vector<Edge<T>>>;

// サイクル検出ソルバー
template<class T> struct CycleDetection {
    // 入力されたグラフ
    Graph<T> G;
    
    // 探索の様子
    vector<bool> seen, finished;
    vector<Edge<T>> history;
    
    // コンストラクタ
    CycleDetection() { }
    CycleDetection(const Graph<T> &graph) { init(graph); }
    void init(const Graph<T> &graph) {
        G = graph;
        seen.assign(G.size(), false);
        finished.assign(G.size(), false);
    }
    
    // サイクル検出
    // return the vertex where cycle is detected
    int dfs(int v, const Edge<T> &e, bool is_prohibit_reverse = true) {
        seen[v] = true;    // 行きがけ時に true になる
        history.push_back(e);    // 履歴を残す
        for (const Edge<T> &e2 : G[v]) {
            // 逆流を禁止する場合は逆流を禁止する
            if (is_prohibit_reverse && e2.to == e.from) continue;
            
            // 頂点 v2 がすでに探索済みの場合はスキップ
            if (finished[e2.to]) continue;

            // サイクルが検出された
            if (seen[e2.to] && !finished[e2.to]) {
                history.push_back(e2);
                return e2.to;
            }

            // 頂点 v2 を再帰的に探索する
            int pos = dfs(e2.to, e2, is_prohibit_reverse);
            if (pos != -1) return pos;
        }
        finished[v] = true;    // 帰りがけ時に true になる
        history.pop_back();    // 探索が完全に終了した頂点 (赤色) は履歴から除去する
        return -1;
    }
    
    // 履歴からサイクルのみを抽出する関数 (pos：サイクルを検出した頂点)
    vector<Edge<T>> reconstruct(int pos) {
        vector<Edge<T>> cycle;
        
        // 履歴を遡ってサイクルを形作る
        while (!history.empty()) {
            const Edge<T> &e = history.back();
            cycle.push_back(e);
            history.pop_back();
            if (e.from == pos) break;
        }
        
        // サイクルの向きを正順にする
        reverse(cycle.begin(), cycle.end());
        return cycle;
    }
    
    // サイクルを返す関数 (is_prohibit_reverse は逆流を許さないかどうか)
    vector<Edge<T>> detect(bool is_prohibit_reverse = true) {
        int pos = -1;
        for (int v = 0; v < (int)G.size() && pos == -1; ++v) {
            if (seen[v]) continue;
            history.clear();
            pos = dfs(v, Edge<T>(), is_prohibit_reverse);
            if (pos != -1) return reconstruct(pos);
        }
        return vector<Edge<T>>();
    }
};

int main() 
{    
    int n = re.in();
    vector<vector<ll>> con(n*10);
    Graph<int> G(n*10);

    for(int i = 0; i < n; i++)
    {
        cout << "? " << i << " " << ((i+1)%n) << endl;
        ll p = re.ll();

        int k = 0;
        for(int a = 0; a <= 9; a++)
        {
            for(int b = 0; b <= 9; b++)
            {
                if(a*b == p)
                {
                    //con.at(i*10 + a).push_back(((i+1)%n)*10 + b);
                    //cout << i*10 + a << " " << ((i+1)%n)*10 + b << endl;
                    G[i*10+a].push_back(Edge(i*10+a, ((i+1)%n)*10 + b, k));
                    k++;
                }
            }
        }
    }

    vector<int> state(n*10,0);
int cycle_count = 0;

function<void(int)> dfs = [&](int v) {
    state[v] = 1;

    for (auto &e : G[v]) {
        int u = e.to;

        if (state[u] == 0) {
            dfs(u);
        }
        else if (state[u] == 1) {
            cycle_count++;
        }
    }

    state[v] = 2;
};

    for (int i = 0; i < n*10; i++) 
    {
        if (state[i] == 0) dfs(i);
    }

    if(cycle_count  != 1) {
        cout << "! -1" << endl;
        return 0;
    }

    // cycle detection
    CycleDetection<int> cd(G);
    const vector<Edge<int>> &res = cd.detect(false);
    
    // 出力
    if (res.empty()) cout << -1 << endl;
    else {
        auto res1 = res;
        Reverse(res1);
        for (const Edge<int> &e : res1) {
            cout << e.from%10;
        }
        cout << endl;
    }

    /*
    ll cnt = 0;
    for(int i = 0; i < 10; i++)
    {
        vector<ll> ans;
        ans.push_back(i);
        vector<bool> seen(n*10,false);
        seen.at(i) = true;
        vector<bool> finished(n*10,false);
        dfs(i, con, ans, seen, finished, cnt);
    }

    if(cnt > 1) return 0;

    Sort(memo);

    Reverse(memo);

    cout << "! ";
    for(ll i : memo)
    {
        cout << i%10;
    }
    cout << endl;
    */
}