It's easy to see that $$$\left( \sum\limits_{i = 1}^n a_i \right) \bmod 4$$$ does not change after a single operation. Therefore, if $$$\left( \sum\limits_{i = 1}^n a_i \right) \bmod 4 \neq 0$$$, then the answer is "NO".

Otherwise, let's make $$$a_1 = 1, a_2 = -1, a_3 = 1, \dots, a_{n - 1} = (-1)^n$$$. We can always do that by performing operations with indices $$$1, 2, 3, \dots n - 1$$$ in this order, and after operation number $$$i$$$ we set the $$$i$$$-th element to the value we want. After that, $$$| \sum\limits_{i = 1}^n a_i | \leq 2$$$, so it is equal to zero because it's the only number divisible by $$$4$$$ in that range.

#include <iostream>

using namespace std;

void solve() {
    int n; cin >> n;
    int sm = 0;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        sm += x;
    }
    
    cout << (abs(sm) % 4 == 0 ? "YES\n" : "NO\n");
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

If $$$m \lt k$$$, then the answer is $$$-1$$$ because it is well known that in any array with $$$m$$$ elements there is a subarray with sum divisible by $$$m$$$. Here is a proof: Consider remainders of prefix sums by $$$m$$$. There are $$$m + 1$$$ prefix sums, and only $$$m$$$ possible remainders by modulo $$$m$$$, therefore two of the prefix sums have the same remainder and in the segment between these two prefix sums the sum is divisible by $$$m$$$.

Otherwise, the solution is to make $$$a_j = 1$$$ for all $$$j$$$ such that $$$j \mod k \neq 0$$$, and $$$a_j = m - k + 1$$$ for $$$j \mod k \equiv 0$$$. In this construction, every subarray of length $$$k$$$ has the sum of exactly $$$m$$$, and every subarray whose length is less than $$$k$$$ obviously has a sum that is greater than $$$0$$$ and less than $$$m$$$, therefore it can't be divisible by $$$m$$$.

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

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

    int t;
    cin >> t;
    while (t--) {
        int n, k, m;
        cin >> n >> k >> m;

        if (k > m) {
            cout << "NO\n";
            continue;
        }

        cout << "YES\n";
        for (int i = 0; i < n; i++) {
            cout << (i % k == 0 ? m - k + 1 : 1) << ' ';
        }
        cout << '\n';
    }
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

If $$$a = b$$$, the answer is $$$0$$$. If $$$a$$$ contains no $$$1$$$-s in it, the answer is $$$-1$$$ because we can't make any operation. Also, if $$$b$$$ doesn't have any $$$0$$$ values, then we can't get $$$b$$$ from any array in one operation, because all values on changed positions should be $$$0$$$ before the operation, but their sum would be even in this case.

If neither of these conditions holds, the answer is always $$$1$$$ or $$$2$$$. It's easy to check whether the answer is $$$1$$$: just consider the positions where $$$a_j \neq b_j$$$, and check if we can do an operation with exactly this set of indices. Otherwise, the answer is $$$2$$$.

Here is a proof: if in the set of indices where $$$a_j \neq b_j$$$ there are $$$\geq 2$$$ indices where $$$a_j = 1$$$, we can just split these wrong indices into two sets with odd sums of $$$a_j$$$. Otherwise, all values that should be changed in array $$$a$$$ are $$$0$$$. Also, there are indices $$$i$$$ and $$$k$$$ such that $$$a_i = b_i = 0$$$ and $$$a_k = b_k = 1$$$ just because the answer is not $$$-1$$$. So let's make the first operation with a subsequence which includes all wrong indices (where $$$a_j \neq b_j$$$) and indices $$$i$$$ and $$$k$$$. The operation is possible because the sum of all $$$a$$$ values is $$$1$$$. After this operation, we can make an operation with only two elements, $$$i$$$ and $$$k$$$. After these two operations, $$$a = b$$$.

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

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n), b(n);
        for (int &x : a) cin >> x;
        for (int &x : b) cin >> x;

        if (a == b) {
            cout << 0 << '\n';
            continue;
        }

        int sum = 0;

        for (int i = 0; i < n; ++i) {
            if (a[i] != b[i]) {
                sum += a[i];
            }
        }
        
        if (accumulate(a.begin(), a.end(), 0) == 0 || accumulate(b.begin(), b.end(), 0) == n) {
            cout << -1 << "\n";
            continue;
        }

        if (sum % 2 == 1) {
            cout << 1 << '\n';
        } else {
            cout << 2 << '\n';
        }
    }
    
    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

It is inefficient to perform swaps whose index XOR is not a power of two.

Suppose we want to swap $$$a_i$$$ and $$$a_j$$$ $$$(i \lt j)$$$, and $$$i \oplus j$$$ is not a power of two. Let $$$b$$$ be the highest differing bit in numbers $$$i$$$ and $$$j$$$. Then perform the following swaps in order: $$$(i, i + 2^b), (i + 2^b, j), (i, i + 2^b)$$$. It's easy to see that $$$i \oplus (i + 2^b) = 2^b$$$, however, $$$(i + 2^b) \oplus j$$$ might not be a power of two. In this case, we want to replace this swap recursively with the same procedure with a sequence of swaps, such that each of which has an XOR equal to a power of $$$2$$$. It's easy to see that after performing these swaps, the only change in the array is that elements on positions $$$i$$$ and $$$j$$$ are swapped.

Now we want to solve the problem. How do we check whether we can sort the array using only operations with XOR at most $$$2^j$$$? Let's split the array into contiguous blocks of elements with size $$$2^{j + 1}$$$ (the size of the last block may be less than $$$2^{j+1}$$$). It's easy to see that each element will remain in its original block after any number of swaps with XOR $$$\leq 2^j$$$. And within a single block, we can obtain any permutation of its elements just because we can always do any swap inside the block with some sequence of swaps $$$\leq 2^j$$$. Therefore, we only need to check whether sorting every contiguous block of $$$2^{j + 1}$$$ elements, the array becomes sorted.

We can simplify that by only considering two values, $$$min_j$$$ and $$$max_j$$$, which correspond to the maximum and minimum elements in block $$$j$$$. Then we want to check that $$$ \forall j \; | \; max_j \leq min_{j + 1}$$$ holds.

For the simple version of this task, we can check it naively in $$$O(n \log n)$$$ because there are $$$O(log n)$$$ different possible answers, and each one of them can be checked in $$$O(n)$$$.

#include <bits/stdc++.h>
#include <cassert>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for (auto &u : a) cin >> u;
    if (is_sorted(all(a))) {
        cout << "0\n";
        return;
    }
    for (int x = 0;; x++) {
        int mx = -1;
        bool good = 1;
        for (int j = 0; j * (1 << (x+1)) < n; j++) {
            int cmx = -1;
            for (int i = 0; j * (1<<(x+1)) + i < n && i < (1<<(x+1)); i++) {
                int cur = a[j *(1<<(x+1)) + i];
                good &= (mx <= cur);
                cmx = max(cmx, cur);
            }
            mx = max(mx, cmx);
        }
        if (good) {
            cout << (1<<x) << '\n';
            return;
        }
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    int tt = 1;
    cin >> tt;

    while (tt--) {
        solve();
    }

    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

First, read the solution for the problem D1.

In the hard version, we need to also handle queries. Let us append several $$$\infty$$$ values to the end of the array so that its length becomes a power of two. Then let's build a segment tree over this array. Now each node of the segment tree corresponds to a block. In each vertex of segment tree we want to maintain the following three values: -maximum value on the segment -minimum value on the segment -minimum $$$k$$$ needed to sort the segment

It is easy to compute the values of a node from the values of its children: maximum and minimum are trivial, and for $$$k$$$ we need to take maximum among our two children, and if $$$max_L \gt min_R$$$ we need to increase $$$k$$$ to length of the segment divided by two. ($$$max_L$$$ is the maximum in the left son, and $$$min_R$$$ is the minimum in the right son).

This solution works in $$$O(n + q \log n)$$$ time.

#include <bits/stdc++.h>
#include <cassert>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for (auto &u : a) cin >> u;
    int N = 1;
    while (N < n) N *= 2;
    while (n < N) {
        a.pb(1e9);
        n++;
    }
    vector<array<int, 3>> t(2 * n);
    vector<int> L(2 * n, 1);
    for (int j = 0; j < n; j++) t[n + j] = {a[j], a[j], 0};
    auto pull= [&](int j, int len) {
        t[j][0] = min(t[j << 1][0], t[j << 1 | 1][0]);
        t[j][1] = max(t[j << 1][1], t[j << 1 | 1][1]);
        t[j][2] = max(t[j<<1][2], t[j<<1|1][2]);
        if (t[j<<1][1] > t[j<<1|1][0]) t[j][2] = max(t[j][2], len / 2);
    };
    for (int j = n - 1; j >= 1; j--) {
        L[j] = 2 * L[j << 1];
        pull(j, L[j]);
    }
    cout << t[1][2] << '\n';
    while (q--) {
        int p, x; cin >> p >> x;
        p += n;
        t[p] = {x, x, 0};
        p >>= 1;
        int len = 2;
        while (p) {
            pull(p, len);
            p >>= 1;
            len *= 2;
        }
        cout << t[1][2] << '\n';
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    int tt = 1;
    cin >> tt;

    while (tt--) {
        solve();
    }

    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

Thanks to Um_nik for sharing this solution! My initial approach was more complicated.

Consider the centroid of the answer and set it as the root of the tree. Then the sum of distances $$$\leq 2 \cdot$$$ (sum of heights of all vertices). It is easy to see that, to maximize the sum of distances, we need to make two roughly equal subtrees with sizes close to $$$\lfloor \frac{n}{2} \rfloor$$$, so we now have an upper bound for our answer. The lower bound is obviously $$$2 \cdot (n - 1)$$$ because we need to traverse each edge at least twice, because we start at vertex 1 and finish there. From this observation, we can also notice that the answer is always even because, for each edge, we must cross from one side of the edge to the other an even number of times to always come back.

Now our goal is to build the tree such that after rooting it with its centroid, $$$2 \cdot$$$ (sum of heights of vertices) equals the required $$$x$$$. Let's start from a tree where the centroid has $$$n - 1$$$ direct children. Then we reroot the children one by one until the sum of heights reaches the desired $$$\frac{x}{2}$$$. We will also maintain the condition that each subtree's size doesn not exceed the $$$\lfloor \frac{n}{2} \rfloor$$$ bound. It is always possible to build such a tree because we know that our answer lies in the range of all possible answers, and we can reroot each vertex not only to the highest vertex from a big subtree, but also to all of its parents, so we can make an increase in the sum of heights by 1, 2, and all numbers up to the current maximum height.

When we have built our tree, we need to label its vertices to solve the problem. Basically, we need to label vertices in such a way that $$$\operatorname{dist}(i, (i \bmod n) + 1) = h_i + h_{(i \bmod n) + 1}$$$, where $$$h$$$ corresponds to the array of all vertices' heights. For this to hold, we need to distribute labels so that vertices $$$i$$$ and $$$(i \bmod n) + 1$$$ end up in different subtrees of the centroid (we will label the centroid as vertex 1 and forget about it because for the centroid the condition holds automatically).

Now it's a standard problem to put each label into some subtree so that two consecutive labels end up in different subtrees. The approach is to assign labels one by one, and we always try to put the label into the subtree with the maximum number of remaining free spots, also considering the last label's subtree. It's easy to prove by induction that, with the constraint on the size of each subtree, this approach works.

This can be implemented in $$$O(n \log n)$$$ time; however, there are many different possible solutions working in linear time. Also, this problem can be solved under the condition that the tree must be a chain, but I prefer the centroid-based solution.

#include <bits/stdc++.h>
#include <cassert>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back

void solve() {
    ll n, k; cin >> n >> k;
    ll top = 0;
    for (int x = 1; x <= n / 2; x++) {
        top += x;
        if (2 * x <= n - 1) top += x;
    }
    top *= 2;
    if (k % 2 == 1 || k < 2 * (n - 1) || k > top) {
        cout << "-1\n";
        return;
    } 
    if (n == 2) {
        cout << "1 2\n";
        return;
    }
    vector<int> cnt(2, (n - 1) / 2);
    if (n % 2 == 0) cnt[1]++;
    ll cur = top;
    cur /= 2;
    k /= 2;
    for (int i = 0; ; i++) {
        int id = i % 2;
        if (cnt[id] > 1 && cur - (cnt[id] - 1) >= k) {
            cur -= (cnt[id] - 1);
            cnt.pb(1);
            cnt[id]--;
        } else if (cnt[id] > 1 || cur == k) {
            vector<pair<int, int>> edges;
            int cr = 2;
            vector<int> startv(sz(cnt));
            for (int j = 0; j < sz(cnt); j++) {
                startv[j] = cr;
                if (j != id) {
                    int prv = 1;
                    for (int x = 0; x < cnt[j]; x++) {
                        edges.pb({prv, cr++});
                        prv = cr - 1;
                    }
                } else {
                    int prv = 1, start = cr;
                    for (int x = 0; x < cnt[j] - 1; x++) {
                        edges.pb({prv, cr++});
                        prv = cr - 1;
                    }
                    int was = cnt[j];
                    int neww = was - (cur - k);
                    if (neww == 1) edges.pb({1, cr++});
                    else edges.pb({start + (neww - 2), cr++});
                }
            }
            set<pair<int, int>> st;
            for (int j = 0; j < sz(cnt); j++) st.insert({cnt[j], j});
            vector<int> per(n + 1);
            per[1] = 1;
            int lst = -1;
            for (int x = 2; x <= n; x++) {
                auto it = --st.end();
                while ((*it).second == lst) it--;
                auto [c,id] = *it;
                st.erase(it);
                per[startv[id]] = x;
                startv[id]++;
                lst = id;
                assert(cnt[id] > 0);
                cnt[id]--;
                st.insert({cnt[id], id});
            }
            for (auto &[u, v] : edges) {
                u = per[u]; v = per[v];
                cout << u << ' ' << v << '\n';
            }
            break;
        }
    }
}

signed main() {
    int t = 1;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve

First, let us observe that if there is at least one cell in a $$$\textit{good}$$$ set of cells through which no path from cell $$$(1, 1)$$$ to cell $$$(n, m)$$$ passes, then the same is true for all other cells in the set as well. Otherwise, there would exist at least one path contradicting the definition of a $$$\textit{good}$$$ set. Therefore, we can immediately add $$$2^{\text{free}} - 1$$$ to the answer, where $$$free$$$ is the number of free cells through which none of the required paths pass.

From now on, we consider only those free cells through which at least one required path passes. Suppose our set contains some free cell $$$(i, j)$$$ and another cell $$$(i_1, j_1)$$$. Notice that one of the following two conditions must hold: $$$(i_1 \leq i, j_1 \leq j)$$$ or $$$(i_1 \geq i, j_1 \geq j)$$$. This is because at least one required path passes through each of these cells, and if neither condition holds, then such paths cannot coincide, since a path may only move either one cell down or one cell to the right;

In the first case, $$$(i_1 \leq i, j_1 \leq j)$$$, we need the following condition: every path from $$$(1, 1)$$$ to $$$(i, j)$$$ must pass through cell $$$(i_1, j_1)$$$; otherwise, the set is not $$$\textit{good}$$$. Similarly, if the second condition $$$(i_1 \geq i, j_1 \geq j)$$$ holds, then every path from cell $$$(i, j)$$$ to $$$(n, m)$$$ must pass through cell $$$(i_1, j_1)$$$.

Therefore, we construct directed edges from cell $$$(i, j)$$$ to all cells $$$(i_1, j_1)$$$ such that $$$(i_1 \leq i, j_1 \leq j)$$$ and every path from $$$(1, 1)$$$ to $$$(i, j)$$$ passes through $$$(i_1, j_1)$$$, and also to all cells satisfying $$$(i_1 \geq i, j_1 \geq j)$$$ such that every path from $$$(i, j)$$$ to $$$(n, m)$$$ passes through $$$(i_1, j_1)$$$. Then we find the strongly connected components of this graph. A set of cells is good if and only if all of its cells belong to the same SCC.

Essentially, such edges mean that every path from $$$(1, 1)$$$ to $$$(n, m)$$$ passing through $$$(i, j)$$$ also passes through $$$(i_1, j_1)$$$. This makes it clear that if all cells of the set belong to one SCC, then the set is good; otherwise, it is not.

Now let us understand how to efficiently find SCCs in this graph. Consider only the edges from cells $$$(i, j)$$$ to cells $$$(i_1, j_1)$$$ satisfying $$$(i_1 \leq i, j_1 \leq j)$$$. Notice that if there exists an edge $$$(i, j) \rightarrow (i_1, j_1)$$$ and an edge $$$(i_1, j_1) \rightarrow (i_2, j_2)$$$, then there also exists an edge $$$(i, j) \rightarrow (i_2, j_2)$$$, because the edge $$$(i, j) \rightarrow (i_1, j_1)$$$ means that all paths from $$$(1, 1)$$$ to cell $$$(i, j)$$$ pass through cell $$$(i_1, j_1)$$$.

We can also observe that all cells reachable by such edges from $$$(i, j)$$$ form a path in the directed graph. Therefore, for each cell $$$(i, j)$$$ it is sufficient to find the edge to the cell $$$(i_1, j_1)$$$ with the maximum value of $$$i_1 + j_1$$$.

We process cells in increasing order of $$$i + j$$$. If cell $$$(i - 1, j)$$$ is reachable from $$$(1, 1)$$$ and cell $$$(i, j - 1)$$$ is not reachable from $$$(1, 1)$$$, then the required edge goes to cell $$$(i - 1, j)$$$. Similarly, if cell $$$(i - 1, j)$$$ is not reachable from $$$(1, 1)$$$ and cell $$$(i, j - 1)$$$ is reachable from $$$(1, 1)$$$, then the required edge goes to cell $$$(i, j - 1)$$$.

Otherwise, the required edge goes to the LCA of cells $$$(i - 1, j)$$$ and $$$(i, j - 1)$$$ in the tree formed by the previously constructed SCC edges.

Analogously, we can construct edges $$$(i, j) \rightarrow (i_1, j_1)$$$ to cells satisfying $$$i_1 \geq i$$$ and $$$j_1 \geq j$$$.

Thus, our graph contains only $$$O(nm)$$$ edges, and we can easily find its SCCs.

To answer LCA queries in the tree, we use binary lifting. Therefore, the overall complexity of the solution is $$$O(nm \log nm)$$$ time and $$$O(nm \log nm)$$$ memory.

In fact, building SCCs is not even necessary. We can merge two cells $$$A$$$ and $$$B$$$ in dsu if $$$A$$$ is the direct parent of $$$B$$$ in a tree built from the cell $$$(1, 1)$$$ and if $$$B$$$ is the direct parent of $$$A$$$ in a tree built from the cell $$$(n, m)$$$.

#include <bits/stdc++.h>
#include <cassert>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back

const int maxl = 20, maxn = 1e6 + 10;
int up[maxl][maxn];

constexpr ll mod = 998244353;
ll sum(ll x, ll y) {
    return (x + y >= mod ? x + y - mod : x + y);
}
ll mul(ll x, ll y) {
    return (x * y) % mod;
}
ll diff(ll x, ll y) {
    return (x >= y ? x - y : x + mod - y);
}

void solve() {
    int n, m; cin >> n >> m;
    vector<string> s(n);
    for (auto &u : s) cin >> u;

    vector<vector<int>> is_path(n, vector<int>(m));
    vector<int> h(n * m);
    vector<vector<int>> g_scc(n * m);
    for (int j = 0; j < maxl; j++) up[j][0] = 0;
    auto newv = [&](int v, int p) {
        g_scc[v].pb(p);
        h[v] = h[p] + 1;
        up[0][v] = p;
        for (int j = 1; j < maxl; j++) up[j][v] = up[j - 1][up[j - 1][v]];  
    };
    auto jump = [&](int v, int where) {
        for (int j = maxl - 1; j >= 0; j--) {
            if (((h[v] - where) >> j) & 1) v = up[j][v];
        }    
        return v;
    };
    auto lca = [&](int u, int v){
        if (h[u] > h[v]) swap(u, v);
        v = jump(v, h[u]);
        if (u == v) return u;
        for (int j = maxl - 1; j >= 0; j--) {
            if (up[j][v] != up[j][u]) {
                v = up[j][v]; u = up[j][u];
            }
        }
        return up[0][v];
    };  

    is_path[0][0] = (s[0][0] == '1');
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 && j == 0) continue;
            if (s[i][j] == '0') continue;
            is_path[i][j] = (i > 0 && is_path[i - 1][j]) || (j > 0 && is_path[i][j - 1]);
            if (is_path[i][j]) {
                int par;
                if (i == 0 || !is_path[i - 1][j]) par = i * m + j - 1;
                else if (j == 0 || !is_path[i][j - 1]) par = (i - 1) * m + j;
                else par = lca((i - 1) * m + j, i * m + j - 1);
                newv(i * m + j, par);
            }
        }
    }

    h.assign(n * m, 0);
    for (int j =0; j < maxl; j++) up[j][n * m - 1] = n * m - 1;
    vector<vector<int>> is_path2(n, vector<int>(m));
    is_path2[n - 1][m - 1] = (s[n - 1][m - 1] == '1');
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (i == n - 1 && j == m - 1) continue;
            if (s[i][j] == '0') continue;
            is_path2[i][j] = (i + 1 < n && is_path2[i + 1][j]) || (j + 1 < m && is_path2[i][j + 1]);
            if (is_path2[i][j]) {
                int par;
                if (i + 1 == n || !is_path2[i + 1][j]) par = i * m + j + 1;
                else if (j + 1 == m || !is_path2[i][j + 1]) par = (i + 1) * m + j;
                else par = lca((i + 1) * m + j, i * m + j + 1);
                newv(i * m + j, par);
            }
        }
    }
    int cntbad = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cntbad += (!is_path[i][j] || !is_path2[i][j]);
    }
    ll ans = 1;
    for (int j = 0; j < cntbad; j++) ans = mul(ans, 2);
    ans = diff(ans, 1);
    // cout << cntbad << endl;

    vector<int> used(n * m), ord;
    auto dfs = [&](int v, auto&&self) -> void {
        used[v] = 1;
        for (int u : g_scc[v]) if (!used[u]) self(u, self);
        ord.pb(v);
    };  
    for (int j =0; j < n * m; j++) {
        if (!used[j] && is_path[j/m][j % m] && is_path2[j/m][j % m]) dfs(j, dfs);
    }
    reverse(all(ord));
    vector<bool> is_good(n * m);
    for (int el : ord) is_good[el] = 1;
    
    vector<vector<int>> grev(n * m);
    for (int i = 0; i < n * m; i++) for (int u : g_scc[i]) grev[u].pb(i);
    vector<int> cnt;
    used.assign(n * m, 0);
    auto dfs2 = [&](int v, auto&&self) -> void {
        cnt.back()++;
        used[v] = 1;
        for (int u : grev[v]) {
            if (!used[u] && is_good[u]) self(u, self);
        }
    };      
    for (int u : ord) {
        if (!used[u]) {
            cnt.pb(0);
            dfs2(u, dfs2);
        }
    }
    for (int c : cnt) {
        ll cur = 1;
        for (int j = 0; j < c; j++) cur = mul(cur, 2);
        ans = sum(ans, diff(cur, 1));
    }
    cout << ans << '\n';
}

signed main() {
    int t = 1;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

• Good Problem
• Okay Problem
• Bad Problem
• Didn't Solve