Let \(W\) be the maximum number of wins achieved by a player before the last \(N\) matches. The champion will have \(W\) or \((W+1)\) wins, so a player with \((W-2)\) wins before the last \(N\) matches will never become the champion. Thus, it is safe to set their win counts to \(0\).

By this modification, the last \(N\) matches are classified into the following:

• a match between players with \(W\) wins
• a match between a player with \(W\) wins and another with \((W-1)\) wins
• a match between a player with \(W\) wins and another with \(0\) wins
• a match between players with \((W-1)\) wins
• a match between a player with \((W-1)\) wins and another with \(0\) wins
• a match between players with \(0\) wins

Let \(m _ 0,m _ 1,m _ 2,m _ 3,m _ 4,m _ 5\) be the numbers of such matches, respectively. Also, let us refer to these categories as group \(m _ 0\), group \(m _ 1\), and so on.

If a player has the most wins after all the matches complete, call them a champion candidate. We will find the probability for each pair of the number of champion candidates and the champion’s winning count, and take their sum to find the answer.

When the champion’s winning count \(W\) is fixed, each match satisfies exactly one of the following two:

1. the match yields one champion candidate with probability \(\dfrac12\), and zero candidates with probability \(\dfrac12\).
2. There exist a real number \(p\) between \(0\) and \(1\) (inclusive) and a positive integer \(k\), such that the match yields \(k\) candidates with probability \(p\), and causes a contradiction with probability \((1-p)\).

Call them type \(1\) and type \(2\).

Let \(P\) be the product of \(p\), and \(K\) be the sum of \(k\), over all type-\(2\) matches. Then there will be between \(K\) and \((K+x)\) champion candidates.

For a player competing in a type-\(1\) match who may win a total of \(W\) times, the probability that there are a total of \(w\) candidates \((K+1\le w\le K+x)\), including that player, is expressed as \(P\times\dfrac{{} _ {x-1}\mathrm C_{w-K-1}}{2 ^ x}\), by considering the results of all type-\(1\) matches except for the one the player is participating in.

For a player competing in a type-\(2\) match who may win a total of \(W\) times, the probability that there are a total of \(w\) candidates \((K\le w\le K+x)\), including that player, is expressed likewise as \(qP\times\dfrac{{} _ {x}\mathrm C_{w-K}}{2 ^ x}\), where \(q\) is the probability that the player wins a total of \(W\) times, given that no contradiction occurs.

1. If the champion wins a total of \(W+1\) times

In this case, groups \(m _ 1\) and \(m _ 2\) constitute type-\(1\) matches. The others are type \(2\), with \(p=1,k=1\) for group \(m _ 0\) and \(p=1,k=0\) for groups \(m _ 3,m _ 4,m _ 5\).

Therefore, for a player in group \(m _ 1,m _ 2\) with \(W\) wins, the probability that there are a total of \(w\) candidates \((m _ 0+1\le w\le m _ 0+m _ 1+m _ 2)\), including that player, is \(\dfrac{{} _ {m _ 1+m _ 2-1}\mathrm C _ {w - m _ 0-1}}{2 ^ {m _ 1+m _ 2}}\); for a player in group \(m _ 0\)\(m _ 0\)\(m _ 0\)\(m _ 0\), the probability that there are a total of \(w\) candidates \((m _ 0+1\le w\le m _ 0+m _ 1+m _ 2)\), including that player, is \(\dfrac{{} _ {m _ 1+m _ 2}\mathrm C _ {w - m _ 0}}{2 ^ {m _ 1+m _ 2+1}}\).

2. If the champion wins a total of \((W+1)\) times

In this case, group \(m _ 4\) constitute type-\(1\) matches. The others are type \(2\), with:

• Group \(m _ 0\): \(p=0\)
• Group \(m _ 1\): \(p=\dfrac12,k=2\)
• Group \(m _ 2\): \(p=\dfrac12,k=1\)
• Group \(m _ 3\): \(p=1,k=1\)
• Group \(m _ 5\): \(p=1,k=0\)

Based on these parameters, the probability can be computed in the same way as the former case.

---

Precalculate the factorials to enable constant-time computation of a binomial coefficient in a certain range. By also precomputing \(\dfrac P{2 ^ x}\) for the cases with \(W\) and \((W+1)\) wins, the aforementioned probabilities can be obtained in constant time each. With the precomputed factorials in hand, the inverse of the number of champion candidates can also be obtained in constant time.

The problem can be obtained by summing them up.

The following is sample code.

#include <iostream>
#include <vector>
#include <numeric>
#include <ranges>
#include <array>
#include <atcoder/modint>

int main() {
    using namespace std;
    using modint = atcoder::static_modint<998244353>;
    unsigned N;
    cin >> N;

    // Precalculating factorials
    vector<modint> fact(2 * N + 1), ifact(2 * N + 1);
    iota(begin(fact), end(fact), modint{});
    fact.front() = 1;
    inclusive_scan(begin(fact), end(fact), begin(fact), multiplies{});
    iota(begin(ifact), end(ifact), modint{1});
    ifact.back() = 1 / fact.back();
    inclusive_scan(rbegin(ifact), rend(ifact), rbegin(ifact), multiplies{});
    const auto binom{[&fact, &ifact](const unsigned n, const unsigned r) {
        return fact[n] * ifact[r] * ifact[n - r];
    }};
    const auto inv{[&fact, &ifact](const unsigned n) {
        return ifact[n] * fact[n - 1];
    }};

    vector<pair<unsigned, unsigned>> match(N);
    unsigned max_win{};
    for (auto&& [L, R] : match) {
        cin >> L >> R;
        max_win = max({max_win, L, R});
    }

    // Classify matches
    const auto match_type{[max_win](unsigned L, unsigned R){
        if (L > R)
            swap(L, R);
        if (R == max_win) {
            if (L == max_win) return 0;
            if (L + 1 == max_win) return 1;
            return 2;
        }
        if (R + 1 == max_win) {
            if (L + 1 == max_win) return 3;
            return 4;
        }
        return 5;
    }};

    // Count how many matches are there in each group
    array<unsigned, 6> match_count{};
    for (const auto& [L, R] : match)
        ++match_count[match_type(L, R)];

    // For each group, find the winning probability of the player with (more wins, less wins)
    array<pair<modint, modint>, 6> prob{};

    // If the champion candidates win (max_win + 1) times
    {
        const auto winner_min{match_count[0]}, winner_max{match_count[0] + match_count[1] + match_count[2]};
        const auto coef{modint::raw(2).pow(match_count[1] + match_count[2]).inv()};
        if (winner_min) {
            for (const auto w : views::iota(winner_min, winner_max + 1)) {
                const auto p{binom(winner_max - winner_min, w - winner_min) * coef * inv(w)};
                prob[0].first += p * ((998244353 + 1) / 2);
                prob[0].second += p * ((998244353 + 1) / 2);
            }
        }
        for (const auto w : views::iota(winner_min + 1, winner_max + 1)) {
            const auto p{binom(winner_max - winner_min - 1, w - winner_min - 1) * coef * inv(w)};
            prob[1].first += p;
            prob[2].first += p;
        }
    }

    // If the champion candidates win max_win times
    if (match_count[0] == 0) {
        const auto winner_min{2 * match_count[1] + match_count[2] + match_count[3]}, winner_max{2 * match_count[1] + match_count[2] + match_count[3] + match_count[4]};
        const auto coef{modint::raw(2).pow(match_count[1] + match_count[2] + match_count[4]).inv()};
        if (winner_min) {
            for (const auto w : views::iota(winner_min, winner_max + 1)) {
                const auto p{binom(winner_max - winner_min, w - winner_min) * coef * inv(w)};
                prob[1].first += p;
                prob[1].second += p;
                prob[2].first += p;
                prob[3].first += p * ((998244353 + 1) / 2);
                prob[3].second += p * ((998244353 + 1) / 2);
            }
        }
        for (const auto w : views::iota(winner_min + 1, winner_max + 1)) {
            const auto p{binom(winner_max - winner_min - 1, w - winner_min - 1) * coef * inv(w)};
            prob[4].first += p;
        }
    }

    for (const auto& [L, R] : match) {
        const auto& [a_large, a_small]{prob[match_type(L, R)]};
        if (L < R)
            cout << a_small.val() << " " << a_large.val() << " ";
        else
            cout << a_large.val() << " " << a_small.val() << " ";
    }
    cout << endl;
    return 0;
}