1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

i64 pow(int a, int b, int p) {
    i64 ans = 1 % p;
    while (b) {
        if (b & 1) {
            ans = ans * a % p;
        }
        a = (i64)a * a % p;
        b >>= 1;
    }
    return ans;
}

void solve() {
    int a, b, p;
    cin >> a >> b >> p;
    cout << format("{}^{} mod {}={}\n", a, b, p, pow(a, b, p));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

i64 mul(i64 a, i64 b, i64 p) {
    i64 ans = 0;
    while (b) {
        if (b & 1) {
            ans = (ans + a) % p;
        }
        a = a * 2 % p;
        b >>= 1;
    }
    return ans;
}

void solve() {
    i64 a, b, p;
    cin >> a >> b >> p;
    cout << mul(a, b, p) << "\n"; 
}

 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

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> op(n);
    vector t(n, array<int, 31>{});
    for (int i = 0; i < n; i ++) {
        string top;
        int tt;
        cin >> top >> tt;
        if (top == "AND")
            op[i] = 0;
        else if (top == "OR")
            op[i] = 1;
        else
            op[i] = 2;
        int pos = 0;
        while (tt) {
            t[i][pos] = tt & 1;
            tt >>= 1;
            pos ++;
        }
    }

    auto calc = [&](int pos, int val) {
        for (int i = 0; i < n; i ++) {
            if (op[i] == 0)
                val &= t[i][pos];
            else if (op[i] == 1)
                val |= t[i][pos];
            else
                val ^= t[i][pos];
        }
        return val;
    };

    int val = 0, ans = 0;
    for (int i = 30; i >= 0; i --) {
        int r0 = calc(i, 0);
        int r1 = calc(i, 1);
        if (val + (1 << i) <= m and r0 < r1) {
            val += 1 << i, ans += r1 << i;
        } else {
            ans += r0 << i;
        }
    }
    cout << ans << "\n";
}

 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

void solve() {
    int n;
    cin >> n;
    vector<int> ans;
    function<void(int)> dfs = [&](int x) {
        if (x == n + 1) {
            vector<bool> ref(n);
            for (auto v : ans)
                ref[v - 1] = true;
            for (int v : ref)
                if (v)
                    cout << "Y";
                else
                    cout << "N";
            cout << "\n";
            return;
        }
        dfs(x + 1);

        ans.push_back(x);
        dfs(x + 1);
        ans.pop_back();
    };
    dfs(1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> ans;
    function<void(int)> dfs = [&](int x) {
        if (ans.size() > m or ans.size() + (n - x + 1) < m)
            return;

        if (x == n + 1) {
            for (auto x : ans)
                cout << x << " ";
            cout << "\n";
            return;
        }

        ans.push_back(x);
        dfs(x + 1);
        ans.pop_back();
        
        dfs(x + 1);
    };
    dfs(1);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> ans(n + 1), vis(n + 1);
    function<void(int)> dfs = [&](int x) {
        if (x == k + 1) {
            for (int i = 1; i <= k; i ++)
                cout << ans[i] << " ";
            cout << "\n";
            return;
        }
        for (int i = 1; i <= n; i ++) {
            if (vis[i])
                continue;
            ans[x] = i;
            vis[i] = true;
            dfs(x + 1);
            vis[i] = false;
            ans[x] = 0;
        }
    };
    dfs(1);
}

 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

using grid = array<array<bool, 5>, 5>;

grid calc(grid a, int x, int y) {
    a[x][y] = not a[x][y];
    if (x < 4) {
        a[x + 1][y] = not a[x + 1][y];
    }
    if (x > 0) {
        a[x - 1][y] = not a[x - 1][y];
    }
    if (y < 4) {
        a[x][y + 1] = not a[x][y + 1];
    }
    if (y > 0) {
        a[x][y - 1] = not a[x][y - 1];
    }
    return a;
}

struct grid_hash {
    size_t operator()(const grid& g) const {
        u64 res = 0;
        for (int i = 0; i < 5; i ++) {
            for (int j = 0; j < 5; j ++) {
                res += g[i][j];
                res <<= 1;
            }
        }
        return res;
    }
};

unordered_map<grid, int, grid_hash> path;
auto init() {
    grid a;
    for (int i = 0; i < 5; i ++) {
        for (int j = 0; j < 5; j ++) {
            a[i][j] = true;
        }
    }
    queue<grid> q;
    q.push(a);
    while (not q.empty()) {
        grid x = q.front(); q.pop();
        if (path[x] >= 6)
            break;
        for (int i = 0; i < 5; i ++) {
            for (int j = 0; j < 5; j ++) {
                grid y = calc(x, i, j);
                if (not path[y] and y != a) {
                    path[y] = path[x] + 1;
                    q.push(y);
                }
            }
        }
    }
    return a;
}

grid b;

void solve() {
    array<array<bool, 5>, 5> a = {};
    for (int i = 0; i < 5; i ++) {
        for (int j = 0; j < 5; j ++) {
            char x;
            cin >> x;
            a[i][j] = x != '0';
        }
    } 
    if (path[a] == 0) {
        cout << (a == b ? 0 : -1) << "\n";
    } else {
        cout << path[a] << "\n";
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    b = init();
    cin >> t;
    while (t --) {
        solve();
    }
    return 0;
}

 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

using i64 = long long;
using u64 = unsigned long long;

i64 power(i64 a, i64 b, int p = INT_MAX) {
    i64 res = 1;
    a %= p;
    while (b) {
        if (b & 1) {
            (res *= a) %= p;
        }
        (a *= a) %= p;
        b >>= 1;
    }
    return res;
}

const i64 mod = 9901;

i64 sum(i64 p, i64 c) {
    if (p == 0)
        return 0;
    if (c == 0)
        return 1;
    i64 ans = 0;
    if (c % 2 == 0) {
        return ((1 + power(p, c / 2, mod)) * sum(p, c / 2 - 1) % mod + power(p, c, mod)) % mod;
    }
    return (1 + power(p, (c + 1) / 2, mod)) * sum(p, c / 2) % mod;
}

void solve() {
    i64 a, b;
    cin >> a >> b;
    vector<pair<i64, i64>> fact;
    for (i64 i = 2; i * i <= a; i ++) {
        if (a % i)
            continue;
        i64 c = 0;
        while (a % i == 0) {
            c ++;
            a /= i;
        }
        fact.push_back({i, c});
    }
    if (a != 1)
        fact.push_back({a, 1});

    i64 ans = 1;
    for (auto [p, c] : fact) {
        (ans *= sum(p, b * c)) %= mod;
    }
    cout << ans << "\n";
}

 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

const int maxn = 5e3 + 10;

array<array<int, maxn + 10>, maxn + 10> s = {}; 

void solve() {
    int m, n;
    cin >> n >> m;
    for (int i = 0; i < n; i ++) {
        int x, y, z;
        x = y = z = 0;
        cin >> x >> y >> z;
        s[x + 1][y + 1] += z;
    }
    for (int i = 1; i <= maxn; i ++) {
        for (int j = 1; j <= maxn; j ++) {
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }

    int ans = 0;
    for (int i = m; i <= maxn; i ++) {
        for (int j = m; j <= maxn; j ++) {
            int cur = s[i][j] - s[i - m][j] - s[i][j - m] + s[i - m][j - m];;
            ans = max(ans, cur);
        }
    }
    cout << ans << "\n";
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;

    vector<int> b(n);
    b[0] = a[0];
    for (int i = 1; i < n; i ++) {
        b[i] = a[i] - a[i - 1];
    }
    int p = 0, q = 0;
    for (int i = 1; i < n; i ++) {
        if (b[i] > 0)
            p += b[i];
        else if (b[i] < 0)
            q -= b[i];
    }
    cout << max(p, q) << "\n";
    cout << abs(p - q) + 1 << "\n";
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void solve() {
    int n, ith, h, r;
    cin >> n >> ith >> h >> r;
    vector<int> d(n + 2);
    vector<int> c(n + 2);
    set<pair<int, int>> vis;
    for (auto _ : views::iota(0, r)) {
        int a, b;
        cin >> a >> b;
        if (a > b)
            swap(a, b);
        if (vis.count({a, b}))
            continue;
        vis.insert({a, b});
        d[a + 1] --, d[b] ++;
    }
    for (int i = 1; i <= n; i ++) {
        c[i] = c[i - 1] + d[i];
        cout << h + c[i] << "\n";
    }
}

 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

void solve() {
    int n, l;
    cin >> n >> l;
    vector<double> a(n + 1);
    for (auto& x : a | views::drop(1))
        cin >> x;
        
    const double eps = 1e-5; 
    auto check = [&](double t) {
        auto b = a;
        for (auto& x : b | views::drop(1))
            x -= t;
        for (int i = 1; i <= n; i ++) {
            b[i] += b[i - 1];
        }
        double ans = -1e10;
        double min_val = 0;
        for (int i = l; i <= n; i ++) {
            min_val = min(min_val, b[i - l]);
            ans = max(ans, b[i] - min_val);
        }
        return ans >= 0;
    };
    double lo = -1e6, hi = 1e6;
    while (hi - lo > eps) {
        double x = (lo + hi) / 2;
        if (check(x))
            lo = x;
        else
            hi = x;
    }
    cout << int(hi * 1000) << "\n";
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    iota(a.begin(), a.end(), 1);
    ranges::stable_sort(a, [](int l, int r) {
        return compare(l, r);
    });
    cout << "! ";
    for (auto x : a)
        cout << x << " ";
    cout << "\n";
}

 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

void solve() {
    int n;
    cin >> n;
    unordered_map<int, int> lan;
    for (int i = 0; i < n; i ++) {
        int x;
        cin >> x;
        lan[x] ++;
    }
    int m;
    cin >> m;
    vector<tuple<int, int, int>> film(m);
    for (int i = 0; i < m; i ++) {
        get<0>(film[i]) = i;
        cin >> get<1>(film[i]);
    }
    for (int i = 0; i < m; i ++) {
        cin >> get<2>(film[i]);
    }
    ranges::sort(film, [&](auto l, auto r) {
        auto [la, lb, lc] = l;
        auto [ra, rb, rc] = r;
        lb = lan[lb], lc = lan[lc];
        rb = lan[rb], rc = lan[rc];
        if (lb == rb) {
            if (lc == rc)
                return la < ra;
            return lc > rc;
        }
        return lb > rb;
    });
    cout << get<0>(film.front()) + 1 << "\n";
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    ranges::sort(a);
    int mid = a[(n + 1) / 2];
    int ans = 0;
    for (auto x : a)
        ans += abs(x - mid);
    cout << ans << "\n";
}

 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

void solve() {
    int n, m, t;
    i64 sumr = 0, sumc = 0;
    std::cin >> n >> m >> t;
    std::vector<int> row(n);
    std::vector<int> col(m);
    
    for (auto i : rep(t)) {
        int x, y;
        std::cin >> x >> y;
        x --, y --;
        row[x] ++, col[y] ++;
        sumr ++, sumc ++;
    }
    bool modr = sumr % n, modc = sumc % m;
    sumr /= n, sumc /= m;
    
    if (modr and modc) {
        std::cout << "impossible" << endl;
        return;
    }
    
    std::vector<i64> prer(n + 1), prec(m + 1);
    for (auto i : rep(n)) {
        prer[i + 1] = prer[i] + row[i] - sumr;
    }
    for (auto i : rep(m)) {
        prec[i + 1] = prec[i] + col[i] - sumc;
    }
    
    prer.erase(prer.begin());
    rgs::sort(prer);
    auto midr = prer[n / 2];
    i64 ansr = 0;
    for (auto x : prer)
        ansr += std::abs(x - midr);
        
    prec.erase(prec.begin());
    rgs::sort(prec);
    auto mic = prec[m / 2];
    i64 ansc = 0;
    for (auto x : prec)
        ansc += std::abs(x - mic);
        
    if (modc)
        std::cout << "row " << ansr << endl;
    else if (modr)
        std::cout << "column " << ansc << endl;
    else
        std::cout << "both " << ansr + ansc << endl;
}

 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

void solve() {
    std::priority_queue<int, std::vector<int>, 
                             std::less<int>> big;
    std::priority_queue<int, std::vector<int>, 
                             std::greater<int>> small;
    int n, x, mid = 0;
    std::cin >> n;
    std::cin >> x;
    big.emplace(x);
    std::cout << big.top() << endl;
    for (auto i : rep(n) | vws::drop(1)) {
        std::cin >> x;
        if (x > big.top())
            small.emplace(x);
        else
            big.emplace(x);
        while (std::abs<i64>(big.size() - small.size()) > 1) {
            if (big.size() > small.size()) {
                small.emplace(big.top());
                big.pop();
            } else {
                big.emplace(small.top());
                small.pop();
            }
        }
        if (i % 2 == 0) {
            std::cout << (big.size() > small.size() ? 
		                  big.top() : small.top()) << endl;
        }
    }
}

 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

auto solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n), b(n);
    for (auto& x : a)
        std::cin >> x;
        
    i64 ans = 0;
    std::function<void(int,int)> merge = [&](auto l, auto r) -> void {
        if (r - l == 1)
            return;
        auto mid = (l + r) / 2;
        auto i = l, j = mid, k = l;
        merge(l, mid), merge(mid, r);
        while (i < mid and j < r) {
            if (a[i] <= a[j]) {
                b[k++] = a[i++];
            } else {
                b[k++] = a[j++]; 
                ans += mid - i;
            }
        }
        while (i < mid)
            b[k++] = a[i++];
        while (j < r)
            b[k++] = a[j++];
        for (auto t = l; t < r; t ++)
            a[t] = b[t];
    };
    
    merge(0, n);
    
    std::cout << ans << endl;
}

 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

auto solve(int n) {
    std::vector<int> a(n * n), b(n * n);
    for (auto& x : a)
        std::cin >> x;
    for (auto& x : b)
        std::cin >> x;
        
    a.erase(rgs::find(a, 0));
    b.erase(rgs::find(b, 0));
    
    std::function<void(int,int,std::vector<int>&,std::vector<int>&,i64&)> merge = [&merge](int l, int r, std::vector<int>& a, std::vector<int>& b, i64& ans) -> void {
        if (r - l <= 1)
            return;
        auto mid = (l + r) / 2;
        auto i = l, j = mid, k = l;
        merge(l, mid, a, b, ans), merge(mid, r, a, b, ans);
        while (i < mid and j < r) {
            if (a[i] <= a[j]) {
                b[k++] = a[i++];
            } else {
                b[k++] = a[j++]; 
                ans += mid - i;
            }
        }
        while (i < mid)
            b[k++] = a[i++];
        while (j < r)
            b[k++] = a[j++];
        for (auto t = l; t < r; t ++)
            a[t] = b[t];
    };
    
    auto cnta = 0ll, cntb = 0ll;
    auto tmpa = std::vector<int>(a.size());
    auto tmpb = std::vector<int>(b.size());
    
    merge(0, a.size(), a, tmpa, cnta);
    merge(0, b.size(), b, tmpa, cntb);
    
    if (cnta % 2 == cntb % 2)
        std::cout << "TAK" << endl;
    else
        std::cout << "NIE" << endl;
}

 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

void solve() {
    i64 n, m, k;
    std::cin >> n >> m >> k;
    std::vector<i64> p(n), m1(2 * n), m2(2 * n);
    for (i64& x : p)
        std::cin >> x;
        
    auto check = [&k, &m, &p, &m1, &m2](i64 l, i64 mid, i64 r) -> bool {
        for (i64 i = mid; i < r; i++)
            m1[i] = p[i];
            
        std::sort(m1.begin() + mid, m1.begin() + r);
        i64 lp = l, rp = mid, idx = 0, res = 0;
        while (lp < mid and rp < r) {
            if (m1[lp] <= m1[rp])
                m2[idx++] = m1[lp++];
            else
                m2[idx++] = m1[rp++];
        }
        while (lp < mid)
            m2[idx++] = m1[lp++];
        while (rp < r)
            m2[idx++] = m1[rp++];
            
        for (i64 i = 0; i < m and i < idx; i++, idx--) {
            res += (m2[i] - m2[idx - 1]) * (m2[i] - m2[idx - 1]);
        }
        return res <= k;
    };
    
    i64 l = 0, r = 0, ans = 0;
    while (r < n) {
        i64 d = 1;
        while (d > 0) {
            if (r + d <= n and check(l, r, r + d)) {
                r += d, d <<= 1;
                if (r >= n)
                    break;
                for (i64 i = l; i < r + d; i++)
                    m1[i] = m2[i - l];
            } else {
                d >>= 1;
            }
        }
        ans++, l = r;
    }
    std::cout << ans << endl;
}

 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

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::pair<int, int>> cow(n);
    for (auto& [l, r] : cow)
        std::cin >> l >> r;
        
    rgs::sort(cow, [](auto l, auto r) {
        return l.first > r.first;
    });
    
    std::multiset<int> lot;
    for (auto i : rep(m)) {
        int l, r;
        std::cin >> l >> r;
        for (auto j : rep(r))
            lot.insert(l);
    }
    
    int ans = 0;
    for (auto [l, r] : cow) {
        auto itl = lot.lower_bound(l);
        auto itr = lot.upper_bound(r);
        if (std::distance(itl, itr) < 1)
            continue;
        lot.erase(std::max_element(itl, itr));
        ans++;
    }
    std::cout << ans << endl;
}

 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

void solve() {
    int n;
    std::cin >> n;
    std::vector<std::tuple<int, int, int>> vec(n);
    auto cnt = 0;
    for (auto& [l, r, idx] : vec) {
        std::cin >> l >> r;
        idx = cnt++;
    }
    rgs::sort(vec);
    
    std::vector<int> ans(n);
    std::vector<int> s;
    for (auto i : rep(n)) {
        ans[get<2>(vec[i])] = -1;
        for (auto j : rep(s.size())) {
            if (get<1>(vec[s[j]]) < get<0>(vec[i])) {
                ans[get<2>(vec[i])] = j;
                break;
            }
        }
        if (ans[get<2>(vec[i])] == -1)
            ans[get<2>(vec[i])] = s.size(), s.emplace_back(i);
        else
            s[ans[get<2>(vec[i])]] = i;
    }
    std::cout << s.size() << endl;
    for (auto x : ans)
        std::cout << x + 1 << endl;
}

 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

template <size_t N>
struct BigInt {
    int a[N];
    BigInt(int x = 0) : a {} {
        for (int i = 0; x; i ++) {
            a[i] = x % 10;
            x /= 10;
        }
    }
    auto &operator*=(int x) {
        for (int i = 0; i < N; i ++) {
            a[i] *= x;
        }
        for (int i = 0; i < N - 1; i ++) {
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        return *this;
    }

    auto &operator/=(int x) {
        for (int i = N - 1; i >= 0; i --) {
            if (i) {
                a[i - 1] += a[i] % x * 10;
            }
            a[i] /= x;
        }
        return *this;
    }

    auto &operator+=(const BigInt &x) {
        for (int i = 0; i < N; i ++) {
            a[i] += x.a[i];
            if (a[i] >= 10) {
                a[i + 1] += 1;
                a[i] -= 10;
            }
        }
        return *this;
    }

    auto operator<(const BigInt &x) {
        int l = N - 1;
        while (a[l] == 0)
            l --;
        int r = N - 1;
        while (x.a[r] == 0)
            r --;
        if (l > r)
            return false;
        if (l < r)
            return true;
        for (int i = l; i >= 0; i --) {
            if (a[i] > x.a[i])
                return false;
            if (a[i] < x.a[i])
                return true;
        }
        return false;
    }
};

template<size_t N>
auto &operator<<(ostream &o, const BigInt<N> &a) {
    int t = N - 1;
    while (a.a[t] == 0)
        t --;
    if (t < 0) {
        o << 0;
        return o;
    }
    for (int i = t; i >= 0; i --)
        o << a.a[i];
    return o;
}

void solve() {
    int n;
    cin >> n;
    int a, b;
    cin >> a >> b;
    vector<pair<int, int>> vec(n);
    for (auto &[l, r] : vec)
        cin >> l >> r;
    ranges::sort(vec, [](auto l, auto r) {
        return l.first * l.second < r.first * r.second;
    });
    BigInt<10000> mul = 1, tmp, ans;
    mul *= a;
    for (int i = 0; i < n; i ++) {
        tmp = mul;
        tmp /= vec[i].second;
        if (ans < tmp)
            ans = tmp;
        mul *= vec[i].first;
    }
    cout << ans << endl;
}