n = int(input())
if n % 9 == 0:
	print(n)
else:
	print(-1)

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

void solve(){
    int n,ans=0;
    cin >> n;
    int arr[n];
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    vector <int> eq;
    for(int i=0;i<n;i++){
        if(arr[i]==arr[(i+1)%n]){
            eq.push_back(i);
            ans++;
        }
    }
    for(int i=0;i<eq.size();i++){
        if(arr[(eq[i]+1)%n]==arr[eq[(i+1)%eq.size()]]&&(eq[i]+1)%n!=eq[(i+1)%eq.size()]){
            ans++;
        }
    }
    if(ans==0){
        ans=1;
    }
    cout << ans << endl;
}

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

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

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

    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<int> head(n + 1, -1);
    vector<int> to(max(0, 2 * (n - 1)));
    vector<int> nxt(max(0, 2 * (n - 1)));
    int ec = 0;

    auto add_edge = [&](int u, int v) {
        to[ec] = v;
        nxt[ec] = head[u];
        head[u] = ec++;
    };

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    // root the tree at 1
    vector<int> parent(n + 1, 0);
    vector<int> order;
    order.reserve(n);

    order.push_back(1);
    parent[1] = -1;

    for (size_t idx = 0; idx < order.size(); ++idx) {
        int u = order[idx];
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (v == parent[u]) continue;
            parent[v] = u;
            order.push_back(v);
        }
    }

    long long ans = 0;

    for (int u = 1; u <= n; ++u) {
        int parity = (a[u] == 0); // need[u] = 1 xor a[u]

        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (parent[v] == u) {
                parity ^= (a[v] == 0);
            }
        }

        ans += parity;
    }

    cout << ans << '\n';
    return 0;
}

The maximum of lines always make a convex function. This means that if $$$M = 0$$$, $$$f(x)$$$ is guaranteed to be convex.

Observe that $$$f(x)$$$ taking the minimum at any point creates a "spike" or "dip" in the function, causing it to no longer be convex. This means that in order for $$$f(x)$$$ to be convex, the minimum of all $$$N$$$ lines must be equal to the maximum of all $$$N$$$ lines at every $$$x \in S$$$. In other words, all $$$N$$$ lines must intersect at every $$$x \in S$$$.

Case $$$M = 0$$$: As the hint states, $$$f(x)$$$ is guaranteed to be convex.

Case $$$M = 1$$$: Check if all $$$N$$$ lines intersect at $$$S_0$$$ by plugging in $$$S_0$$$ into every line. $$$f(x)$$$ is convex if and only if all lines have the same value at $$$S_0$$$.

Case $$$M \gt = 2$$$ (assume $$$S$$$ has at least 2 distinct values): Since different lines cannot intersect at more than one point, if more than one distinct line is given, $$$f(x)$$$ cannot be convex. Otherwise, if all $$$N$$$ lines given are the same (in which case they intersect at every point), $$$f(x)$$$ is convex.

The final time complexity is $$$O(N+M).$$$

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

bool solve() {
    int n,m; cin >> n >> m;
    vector<pair<int,int>> a(n); vector<int> s(m);
    for(int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
    for(int i = 0; i < m; i++) cin >> s[i];

    if(m==0) return true;

    else if(m==1) {
        int y = a[0].first*s[0]+a[0].second;

        for(int i = 1; i < n; i++) if(a[i].first*s[0]+a[i].second != y) return false;
        return true;
    }

    else {
        for(int i = 1; i < n; i++) if(a[i] != a[0]) return false;
        return true;
    }
}

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

    int t; cin >> t;
    while(t--) {
        if(solve()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

If a red node is connected to a green node, then every red node is connected to a green node.

Following Hint 1, note that if a blue node is distance 2 from a green node, that means that every blue node is distance 2 from a green node. This is because if the path is blue node 1 -> red node 2 -> green node 3, that means that every red node is connected to a green node and also every blue node is connected to a red node, so it must be distance 2 from a green node.

Following this logic, lets set our origin node to be $$$x$$$ and let's find the distance from $$$x$$$ to any red node. It's clear by an extension of the above reasoning that if $$$x$$$ is distance $$$k$$$ from a red node, that means that every node of the same color as $$$x$$$ is distance $$$k$$$ from a red node. This means that the nodes themselves don't matter, but only the colors! And this makes the problem easier because there are only $$$L\le 500$$$ colors.

It follows that we can just find the color of the node that we are in, and find the distance to each of the exit colors, and take the minimum distance. To do this fast, we can precompute the distances using multiple BFS's or Floyd-Warshall. The solution runs in $$$O(N + L^2 + Q\cdot\sum l)$$$ time.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, e, L;
    cin >> n >> e >> L;

    vector<pair<int,int>> raw_edges(e);
    for (auto& [u, v] : raw_edges) cin >> u >> v;

    vector<int> label(n + 1);
    for (int i = 1; i <= n; i++) cin >> label[i];

    // Build label graph
    vector<set<int>> label_adj_set(L + 1);
    for (auto [u, v] : raw_edges) {
        int a = label[u], b = label[v];
        if (a != b) {
            label_adj_set[a].insert(b);
            label_adj_set[b].insert(a);
        }
    }
    vector<vector<int>> label_adj(L + 1);
    for (int a = 1; a <= L; a++)
        label_adj[a].assign(label_adj_set[a].begin(), label_adj_set[a].end());

    // BFS from each label
    const int INF = 1e9;
    vector<vector<int>> dist(L + 1, vector<int>(L + 1, INF));
    for (int src = 1; src <= L; src++) {
        dist[src][src] = 0;
        queue<int> bfs;
        bfs.push(src);
        while (!bfs.empty()) {
            int a = bfs.front(); bfs.pop();
            for (int b : label_adj[a]) {
                if (dist[src][b] == INF) {
                    dist[src][b] = dist[src][a] + 1;
                    bfs.push(b);
                }
            }
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int v, l;
        cin >> v >> l;
        vector<int> labs(l);
        for (int& a : labs) cin >> a;

        int ans = INF;
        for (int a : labs)
            ans = min(ans, dist[label[v]][a]);
        cout << (ans == INF ? -1 : ans) << "\n";
    }

    return 0;
}

If the turtles' paths do not intersect, they form the shape of a spiral!

Let $$$A$$$ and $$$B$$$ contain the individual line segments of the red and blue turtles' paths. In which case $$$A_i$$$ and $$$B_i$$$ are the line segments created by the red and blue turtle during the $$$i-th$$$ step, respectively.

Following hint 1, observe that the spiral shape implies that for any $$$i$$$, if $$$A_i$$$ does intersect with any line segments from $$$B$$$, it will at least intersect $$$B_{i+3}$$$. Similarly, if $$$B_i$$$ does intersect with any line segments from $$$A$$$, it will at least intersect $$$A_{i+3}$$$.

The above observation proves that it is sufficient to check for each $$$i$$$ if $$$A_i$$$ intersects with $$$B_{i+3}$$$ and if $$$B_i$$$ intersects with $$$A_{i+3}$$$.

The final time complexity is $$$O(N+M).$$$

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

vector<pair<int,int>> dirs = {{0,-1},{-1,0},{0,1},{1,0}};

vector<vector<int>> buildPaths(const vector<int>& moves, int currDir) {
    vector<vector<int>> paths; // Each vector in the form of (x1,y1,x2,y2)
    pair<int,int> pos = {0,0};

    bool firstMove = true; // Flag to skip the initial (0,0)

    for(int d : moves) {
        pair<int,int> newPos = {pos.first+d*dirs[currDir].first, pos.second+d*dirs[currDir].second};

        if(firstMove) {
            pos.first+=1*dirs[currDir].first;
            pos.second+=1*dirs[currDir].second;
        }
        firstMove = false;

        currDir = (currDir+1)%(dirs.size());

        paths.push_back({pos.first,pos.second,newPos.first,newPos.second});
        pos = newPos;
    }
    return paths;
}

bool intersect(vector<int> A, vector<int> B) {
    if(A[0] != A[2] || B[1] != B[3]) swap(A,B); // For convenience, make A the horizontal one and B the vertical one

    if(A[1] > A[3]) swap(A[1],A[3]); if(B[0] > B[2]) swap(B[0],B[2]);

    // Check if B falls between A
    if(!(B[1] >= A[1] && B[1] <= A[3])) return false;

    // Check if A falls between B
    if(!(A[0] >= B[0] && A[0] <= B[2])) return false;

    return true;
}

bool solve() {
    int n,m; cin >> n >> m;
    vector<int> a(n), b(m);
    for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 0; i < m; i++) cin >> b[i];

    vector<vector<int>> pathsA = buildPaths(a,0), pathsB = buildPaths(b,2);

    // Only check between A[i] and B[i+3] and vice versa
    for(int i = 0; i < n && i+3 < m; i++) if(intersect(pathsA[i],pathsB[i+3])) return true;
    for(int i = 0; i < m && i+3 < n; i++) if(intersect(pathsA[i+3],pathsB[i])) return true;

    return false;
}

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

    int t; cin >> t;
    while(t--) {
        if(solve()) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
    return 0;
}

Consider the graph formed by treating constraints as edges.

We need a tree. What happens when we take a spanning tree of each connected component?

Read the hints.

Let $$$\operatorname{path}(u, v)$$$ be the path XOR between nodes $$$u$$$ and $$$v$$$ on the final tree. First, we observe that the path XOR between two nodes is equal to the XOR of the path XORs between the two nodes and an intermediate node, that is,

\begin{equation*}\operatorname{path}(u, w) = \operatorname{path}(u, v) \oplus \operatorname{path}(v, w)\end{equation*} for three nodes $$$u$$$, $$$v$$$, and $$$w$$$.

Proof. We root the tree at $$$v$$$. Then, edges from $$$\operatorname{lca}(u, w)$$$ to $$$v$$$ appear in both paths, so they don't contribute to the overall path XOR. The remaining edges precisely form the path from $$$u$$$ to $$$w$$$.

This relationship extends to any number of intermediate nodes, i.e.,

\begin{equation*} \operatorname{path}(u, w) = \operatorname{path}(u, v_1) \oplus \operatorname{path}(v_1, v_2) \oplus \cdots \oplus \operatorname{path}(v_k, w)\end{equation*}

for $$$k$$$ intermediate nodes $$$v_1, v_2, \dots, v_k$$$.

As a consequence, when we treat the constraints $$$\operatorname{path}(u, v) = w$$$ as edges, the path XOR between any two nodes in each connected component will be the same for all valid trees if any tree exists. Therefore, it suffices to take a spanning tree of each connected component and check that each constraint is satisfied. Note that since this graph may be disconnected, we will need to add edges of arbitrary weight between two nodes.

Creating the spanning tree can be done in multiple ways. The model solution uses a DSU to only add an edge if it unites two connected components.

To verify that the constraints are satisfied, we need to be able to find the path XOR between two nodes. This can be done efficiently using

\begin{equation*}\operatorname{path}(u, v) = \operatorname{path}(u, 1) \oplus \operatorname{path}(1, v)\end{equation*}

from above, so we need to only need to compute path XORs starting from $$$1$$$ or any other arbitrary node.

Time complexity: $$$\mathcal{O}(n\alpha(n))$$$ (with DSU) or $$$\mathcal{O}(n)$$$ (without DSU)

/**
 * @author n685
 * @date Saturday, April 11, 2026 2:14:29 PM
 */
#include <bits/stdc++.h>

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;

struct DSU {
  std::vector<int> val;
  int cnt{};
  DSU() = default;
  explicit DSU(int n) : val(n, -1), cnt(n) {}
  int find(int i) { return val[i] < 0 ? i : (val[i] = find(val[i])); }
  bool unite(int u, int v) {
    u = find(u), v = find(v);
    if (u == v)
      return false;
    if (val[u] > val[v])
      std::swap(u, v);
    val[u] += val[v];
    val[v] = u;
    --cnt;
    return true;
  }
  bool connected(int u, int v) { return find(u) == find(v); }
  int size(int u) { return -val[find(u)]; }
  int count() const { return cnt; }
};

void tc() {
  int n, m;
  std::cin >> n >> m;

  DSU dsu(n);
  std::vector<std::tuple<int, int, int>> ans, constr(m);
  std::vector<std::vector<std::pair<int, int>>> adj(n);
  for (auto& [u, v, w] : constr) {
    std::cin >> u >> v >> w;
    --u;
    --v;
    if (dsu.unite(u, v)) {
      ans.emplace_back(u, v, w);
      adj[u].emplace_back(w, v);
      adj[v].emplace_back(w, u);
    }
  }

  int pre = -1;
  for (int i = 0; i < n; ++i) {
    if (dsu.val[i] < 0) {
      if (pre != -1) {
        ans.emplace_back(pre, i, 0);
        adj[pre].emplace_back(0, i);
        adj[i].emplace_back(0, pre);
      }
      pre = i;
    }
  }

  std::vector<int> path(n);
  auto dfs = [&](auto&& self, int node, int par) -> void {
    for (auto [w, i] : adj[node]) {
      if (i == par)
        continue;
      path[i] = path[node] ^ w;
      self(self, i, node);
    }
  };
  dfs(dfs, 0, -1);

  for (auto [u, v, w] : constr) {
    if ((path[u] ^ path[v]) != w) {
      std::cout << "NO\n";
      return;
    }
  }

  std::cout << "YES\n";
  for (auto [u, v, w] : ans)
    std::cout << u + 1 << ' ' << v + 1 << ' ' << w << '\n';
}

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int t;
  std::cin >> t;
  for (int i = 1; i <= t; ++i)
    tc();
}

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

static const int MAXA = 1'000'000;

struct Occ {
	int p;
	int e;
};

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

	int n, k;
	cin >> n >> k;

	vector<int> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];

	// smallest prime factor sieve
	vector<int> spf(MAXA + 1, 0), primes;
	spf[1] = 1;
	for (int i = 2; i <= MAXA; ++i) {
		if (!spf[i]) {
			spf[i] = i;
			primes.push_back(i);
		}
		for (int p : primes) {
			long long v = 1LL * i * p;
			if (v > MAXA || p > spf[i]) break;
			spf[(int)v] = p;
		}
	}

	// collect one entry per distinct prime factor per number
	vector<Occ> occs;
	occs.reserve(7 * n);

	for (int x : a) {
		while (x > 1) {
			int p = spf[x];
			int e = 0;
			while (x % p == 0) {
				x /= p;
				++e;
			}
			occs.push_back({p, e});
		}
	}

	sort(occs.begin(), occs.end(), [](const Occ& lhs, const Occ& rhs) {
		return lhs.p < rhs.p;
	});

	vector<int> gcdPrimes;
	vector<int> gcdExps;
	vector<vector<int>> gcdCosts;

	for (size_t l = 0; l < occs.size(); ) {
		size_t r = l;
		int p = occs[l].p;

		array<int, 21> hist{};
		hist.fill(0);

		long long totalExp = 0;
		int occCount = 0;

		while (r < occs.size() && occs[r].p == p) {
			hist[occs[r].e]++;
			totalExp += occs[r].e;
			++occCount;
			++r;
		}

		hist[0] = n - occCount;

		int emax = (int)(totalExp / n);
		if (emax > 0) {
			vector<int> cost(emax + 1, 0);

			long long cntLess = hist[0];
			long long sumLess = 0;
			for (int e = 1; e <= emax; ++e) {
				cost[e] = (int)(1LL * e * cntLess - sumLess);
				if (e < (int)hist.size()) {
					cntLess += hist[e];
					sumLess += 1LL * e * hist[e];
				}
			}

			gcdPrimes.push_back(p);
			gcdExps.push_back(emax);
			gcdCosts.push_back(move(cost));
		}

		l = r;
	}

	int m = (int)gcdPrimes.size();
	vector<int> best(k + 1, 0);

	function<void(int, int, int)> dfs = [&](int idx, int value, int used) {
		if (used > k) return;
		if (idx == m) {
			best[used] = max(best[used], value);
			return;
		}

		int cur = 1;
		for (int e = 0; e <= gcdExps[idx]; ++e) {
			int nxtUsed = used + gcdCosts[idx][e];
			if (nxtUsed <= k) {
				dfs(idx + 1, value * cur, nxtUsed);
			}
			cur *= gcdPrimes[idx];
		}
	};

	dfs(0, 1, 0);

	for (int i = 1; i <= k; ++i) {
		best[i] = max(best[i], best[i - 1]);
	}

	for (int i = 1; i <= k; ++i) {
		cout << best[i] << (i == k ? '\n' : ' ');
	}

	return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define int long long
#define all(x) begin(x), end(x)
using i4 = array<int, 4>;
using i2 = array<int, 2>;

int getd() {
    char c;
    cin >> c;
    if (c == 'R') return 0;
    if (c == 'L') return 1;
    if (c == 'U') return 2;
    return 3;
}

void solve() {
    int n;
    cin >> n;
    vector xy(2, vector<int>(n));
    vector<int> t(n), d(n, -1);
    map<int, vector<i2>> m[2];
    for (int i = 0; i < n; i++) {
        cin >> t[i] >> xy[0][i] >> xy[1][i];
        if (t[i] == 3) d[i] = getd();
        for (int c = 0; c < 2; c++) m[c][xy[c^1][i]].push_back({xy[c][i], i});
    }

    // make graph
    // seg: c, y, x1, x2
    vector<vector<int>> adj(n);
    vector<i4> eseg[n], oseg[n];
    for (int c = 0; c < 2; c++) {
        for (auto& [y, s] : m[c]) {
            sort(all(s));
            int sz = size(s);
            for (int c2 = 0; c2 < 2; c2++) {
                int cd = 2*c + c2;
                for (int ix = 0; ix < sz-1; ix++) {
                    int i = s[ix][1], j = s[ix+1][1];
                    if (t[i] == 2) continue;
                    if (t[i] == 3 && d[i] != cd) continue;
                    auto [x1, x2] = minmax(xy[c][i], xy[c][j]);
                    i4 seg = {c, y, x1, x2};
                    if (t[j] == 2) {
                        oseg[i].push_back(seg);
                        continue;
                    }
                    adj[i].push_back(j);
                    eseg[i].push_back(seg);
                }

                // arev
                reverse(all(s));
            }
        }
    }

    // find cc
    vector<vector<int>> radj(n);
    for (int i = 0; i < n; i++) for (int j : adj[i]) radj[j].push_back(i);

    auto dfs = [&]() {
        vector<bool> v(n);
        v[0] = 1;
        queue<int> q{{0}};
        while (size(q)) {
            int i = q.front();
            q.pop();
            for (auto j : adj[i]) {
                if (v[j]) continue;
                v[j] = 1;
                q.push(j);
            }
        }
        return v;
    };
    auto v = dfs();
    swap(adj, radj);
    auto v2 = dfs();
    swap(adj, radj);
    for (int i = 0; i < n; i++) v[i] = v[i] & v2[i];

    // segments
    map<int, set<i2>> segs[2];
    auto ins = [&](i4 &seg) {
        auto [c, y, x1, x2] = seg;
        segs[c][y].insert({x1, x2});
    };
    for (int i = 0; i < n; i++) {
        if (!v[i]) continue;
        for (auto &s : oseg[i]) ins(s);
        for (int k = 0; k < size(adj[i]); k++) {
            int j = adj[i][k];
            if (v[j]) ins(eseg[i][k]);
        }
    }

    int ans = 0;
    for (int c = 0; c < 2; c++) {
        for (auto& [y, s] : segs[c]) {
            for (auto it = next(begin(s)); it != end(s); it++) {
                auto [cl, cr] = *it;
                auto [pl, pr] = *prev(it);
                if (cl <= pr) {
                    s.erase(prev(it));
                    s.erase(it);
                    it = s.insert({pl, max(pr, cr)}).first;
                }
            }
            for (auto [x1, x2] : s) ans += x2 - x1 + 1;
        }
    }

    // segment intersection
    vector<i4> ev;
    for (auto& [y, s] : segs[0]) {
        for (auto [x1, x2] : s) {
            ev.push_back({x1, 0, y, 0});
            ev.push_back({x2, 2, y, 0});
        }
    }
    for (auto& [x, s] : segs[1]) {
        for (auto [y1, y2] : s) {
            ev.push_back({x, 1, y1, y2});
        }
    }
    sort(all(ev));
    oset<int> os;
    for (auto& [x, t, y1, y2] : ev) {
        if (t == 0) os.insert(y1);
        else if (t == 2) os.erase(y1);
        else {
            int c1 = os.order_of_key(y1), c2 = os.order_of_key(y2 + 1);
            ans -= c2 - c1;
        }
    }

    // ans
    cout << ans << '\n';
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
}

For a cow travelling either North or South, what's the bound on the number of seconds they can survive? What about a cow travelling East or West?

You should have found that the bounds are $$$n$$$ and $$$m$$$ respectively. What is $$$\min(n, m)$$$ bounded by?

Try reducing the grid to a state where only cows travelling on the same axis (e.g. North/South or East/West) are present.

Make sure to read the hints, as they are important to the solution.

As mentioned in Hint 3, we want to reach a state where all cows are either going North/South or East/West, as simulating the state for these cows can be done efficiently. Thus, we first want to process all cow collisions between cows travelling along different axis.

The times at which such collisions can occur is bounded by $$$\min(n, m)$$$. It turns out that $$$\min(n, m) \leq \sqrt{nm}$$$, since $$$\min(n, m) \cdot \min(n, m) \leq nm$$$. This allows us to simulate $$$\sqrt{nm}$$$ seconds of the process, resulting in a grid where all cows travel alongst the same axis.

Now, the only question is efficiently calculating the answer for our reduced grid. For the sake of simplicity, we can consider solving this problem for a line of cows traveling East or West, as this is equivalent to solving the reduced grid.

We sweep from left to right on this line, and apply the following algorithm:

• If this cow goes towards the West, we find the nearest cow whose position has the same parity that is travelling East. We can calculate their collision time by dividing their distance by 2. If such a cow does not exist, we know the current cow simply goes off the grid.
• If this cow goes towards the East, we put it into a stack of cows, making sure to differentiate cows by their parity.

Distinguishing cows by their parity is necessary, as two cows that are adjacent and travelling towards each other do not intersect.

With that, we solve the problem in $$$\mathcal{O}(nm\sqrt{nm})$$$, which runs comfortably in time.

#include <bits/stdc++.h>

using ll = long long;

char dirs[]{'N', 'E', 'S', 'W'};
int dr[]{-1, 0, 1, 0};
int dc[]{0, 1, 0, -1};

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::array<int, 3>> cows(k);
    std::vector cur_cow(n, std::vector<int>(m, -1));
    for (int i = 0; i < k; i++) {
        auto &[r, c, d] = cows[i];
        char dir;
        std::cin >> r >> c >> dir;
        --r, --c;
        for (int t = 0; t < 4; t++) {
            if (dirs[t] == dir) {
                d = t;
            }
        }

        cur_cow[r][c] = i;
    }

    std::vector<int> times(k);

    const int sims = 1 + std::min(n, m);
    for (int t = 0; t < sims; t++) {
        std::vector<std::array<int, 2>> del;
        std::vector nxt(n, std::vector<int>(m, -1));

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (cur_cow[i][j] == -1) continue;
                int ind = cur_cow[i][j];
                ++times[ind];

                int dir = cows[ind][2];
                int nr = i + dr[dir];
                int nc = j + dc[dir];
                if (0 <= nr && nr < n && 0 <= nc && nc < m) {
                    if (nxt[nr][nc] != -1) del.push_back({nr, nc});
                    nxt[nr][nc] = ind;
                }
            }
        }

        for (const auto &[i, j] : del) {
            nxt[i][j] = -1;
        }

        cur_cow = std::move(nxt);
    }

    auto sim = [&](std::vector<int> lane, bool is_vert) -> void {
        std::array<std::vector<int>, 2> go_r{};
        for (int i = 0; i < lane.size(); i++) {
            if (lane[i] == -1) continue;
            int d = cows[lane[i]][2];
            bool is_l = is_vert ? dr[d] == -1 : dc[d] == -1;
            if (is_l) {
                if (!go_r[i % 2].empty()) {
                    int j = go_r[i % 2].back();
                    go_r[i % 2].pop_back();

                    times[lane[i]] += (i - j) / 2;
                    times[lane[j]] += (i - j) / 2;
                } else {
                    times[lane[i]] += i + 1;
                }
            } else {
                go_r[i % 2].push_back(i);
            }
        }

        for (int t = 0; t < 2; t++) {
            for (int i : go_r[t]) {
                times[lane[i]] += lane.size() - i;
            }
        }
    };

    if (n < m) {
        for (int i = 0; i < n; i++) {
            sim(cur_cow[i], false);
        }
    } else {
        for (int j = 0; j < m; j++) {
            std::vector<int> arr;
            for (int i = 0; i < n; i++) {
                arr.push_back(cur_cow[i][j]);
            }

            sim(arr, true);
        }
    }

    for (int i = 0; i < k; i++) {
        std::cout << times[i] << " \n"[i == k - 1];
    }
}

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

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
}

import sys

data = sys.stdin.read().split()
it = iter(data)

dirs = {'N': 0, 'E': 1, 'S': 2, 'W': 3}
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

out = []

def solve():
    n, m, k = int(next(it)), int(next(it)), int(next(it))

    cows = [[0, 0, 0] for _ in range(k)]
    cur_cow = [[-1] * m for _ in range(n)]

    for i in range(k):
        r, c = int(next(it)) - 1, int(next(it)) - 1
        d = dirs[next(it)]
        cows[i] = [r, c, d]
        cur_cow[r][c] = i

    times = [0] * k

    sims = 1 + min(n, m)
    for _ in range(sims):
        del_list = []
        nxt = [[-1] * m for _ in range(n)]

        for i in range(n):
            for j in range(m):
                ind = cur_cow[i][j]
                if ind == -1:
                    continue
                times[ind] += 1

                d = cows[ind][2]
                nr = i + dr[d]
                nc = j + dc[d]
                if 0 <= nr < n and 0 <= nc < m:
                    if nxt[nr][nc] != -1:
                        del_list.append((nr, nc))
                    nxt[nr][nc] = ind

        for i, j in del_list:
            nxt[i][j] = -1

        cur_cow = nxt

    def sim(lane, is_vert):
        go_r = [[], []]
        for i, cow_idx in enumerate(lane):
            if cow_idx == -1:
                continue
            d = cows[cow_idx][2]
            is_l = (dr[d] == -1) if is_vert else (dc[d] == -1)
            if is_l:
                if go_r[i % 2]:
                    j = go_r[i % 2].pop()
                    times[lane[i]] += (i - j) // 2
                    times[lane[j]] += (i - j) // 2
                else:
                    times[lane[i]] += i + 1
            else:
                go_r[i % 2].append(i)

        lane_len = len(lane)
        for t in range(2):
            for i in go_r[t]:
                times[lane[i]] += lane_len - i

    if n < m:
        for i in range(n):
            sim(cur_cow[i], False)
    else:
        for j in range(m):
            sim([cur_cow[i][j] for i in range(n)], True)

    out.append(' '.join(map(str, times)))

t = int(next(it))
for _ in range(t):
    solve()

sys.stdout.write('\n'.join(out) + '\n')

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

static const int MOD = 1'000'000'007;

static int mod_pow(long long a, long long e) {
    long long r = 1;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return (int)r;
}

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

    int n, k;
    cin >> n >> k;

    vector<int> head(n + 1, -1);
    vector<int> to(max(0, 2 * (n - 1)));
    vector<int> nxt(max(0, 2 * (n - 1)));
    int ec = 0;

    auto add_edge = [&](int u, int v) {
        to[ec] = v;
        nxt[ec] = head[u];
        head[u] = ec++;
    };

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    // factorials for nCk modulo MOD
    vector<int> fact(n + 1), ifact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = 1LL * fact[i - 1] * i % MOD;
    ifact[n] = mod_pow(fact[n], MOD - 2);
    for (int i = n; i >= 1; --i) ifact[i - 1] = 1LL * ifact[i] * i % MOD;

    auto C = [&](int s) -> int {
        if (s < k) return 0;
        return 1LL * fact[s] * ifact[k] % MOD * ifact[s - k] % MOD;
    };

    // root the tree at 1
    vector<int> parent(n + 1, 0), order;
    order.reserve(n);
    parent[1] = -1;

    vector<int> st;
    st.reserve(n);
    st.push_back(1);

    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        order.push_back(u);

        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (v == parent[u] || parent[v] != 0) continue;
            parent[v] = u;
            st.push_back(v);
        }
    }

    vector<int> sz(n + 1, 1);
    for (int i = n - 1; i > 0; --i) {
        int u = order[i];
        sz[parent[u]] += sz[u];
    }

    vector<int> delta(n + 1, 0), ans(n + 1, 0);
    long long base = 0;

    for (int v = 2; v <= n; ++v) {
        int s = sz[v];
        int left = C(s);
        int right = C(n - s);
        base += left;
        if (base >= MOD) base -= MOD;

        delta[v] = right - left;
        if (delta[v] < 0) delta[v] += MOD;
    }

    ans[1] = (int)base;

    for (int i = 1; i < n; ++i) {
        int v = order[i];
        int p = parent[v];
        int x = ans[p] + delta[v];
        if (x >= MOD) x -= MOD;
        ans[v] = x;
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << (i == n ? '\n' : ' ');
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int mod=1000000007;
constexpr int i2=500000004;

static inline int c0(int p){
    return (p*p+3*p+2)%mod;
}

static inline int c1(int p){
    return (2*p+3)%mod;
}

struct Point {
    int pos,val;
    bool operator<(const Point& o) const{
        return pos<o.pos;
    }
};

struct Query {
    int pos;
    bool is_left;
    int id;
    bool operator<(const Query& o) const{
        return pos<o.pos;
    }
};

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<Point> points;
    points.reserve(4*n);
    while(n--){
        int op,l,r;
        cin >> op >> l >> r;
        int len=r-l+1;
        if(op==1){
            points.push_back({l,1});
            points.push_back({l+1,mod-1});
            points.push_back({r+1,mod-1});
            points.push_back({r+2,1});
        }
        else{
            points.push_back({l,1});
            points.push_back({r+1,mod-len-1});
            points.push_back({r+2,len});
        }
    }
    sort(points.begin(),points.end());
    points.push_back({mod, 0});
    int q;
    cin >> q;
    int ans[q];
    for(int i=0;i<q;i++) ans[i]=0;
    vector<Query> query;
    query.reserve(2*q);
    for(int i=0;i<q;i++){
        int l,r;
        cin >> l >> r;
        query.push_back({l-1,1,i});
        query.push_back({r,0,i});
    }
    sort(query.begin(),query.end());
    int s0=0,s1=0,s2=0,ptr=0;
    for(int i=0;i<2*q;i++){
        while(points[ptr].pos<=query[i].pos){
            int k=points[ptr].pos,d=points[ptr].val;
            s0=(s0+d)%mod; s1=(s1+k*d)%mod; s2=(s2+(k*k%mod)*d)%mod;
            ptr++;
        }
        int p=query[i].pos;
        int ret=((c0(p)*s0-c1(p)*s1+s2)%mod+mod)%mod*i2%mod;
        if(query[i].is_left) {
            if(ret>0) ret=mod-ret;
        }
        ans[query[i].id]+=ret;
        if(ans[query[i].id]>=mod) ans[query[i].id]-=mod;
    }
    for(int i=0;i<q;i++){
        cout << ans[i] << '\n';
    }
    return 0;
}

A node can be removed if it has no neighboring nodes of type 1 that are directly connected to a node of type 2. Note that since we are only removing nodes, a node can never become unsafe to remove if it was previously safe. Furthermore, if a valid removal order exists, it is impossible for us to reach a state where we cannot continue a valid removable order (and unremovable nodes still remain), so we do not need to worry about backtracking when constructing a removal order; if we find a node that we can remove, we should remove it immediately.

So, we can easily precompute the number of adjacent nodes of type 2 for each node in the graph. Then, repeatedly loop through all unremoved nodes in the graph. For each node, check all of its unremoved type 1 neighbors; if none of them have an adjacent node of type 2, we can safely add it to our removal order. If the node we just removed is a type 2, we can subtract 1 from the precomputed type 2 adjacency count for all of its neighbors. Continue until all nodes are marked as removed or we fail to find any valid removable node in a single pass. If all nodes have been removed, output the removal order we have found; otherwise, a valid removal order cannot exist.

Since in the worst case, only one node is removed per pass across $$$n$$$ passes, this algorithm runs in O($$$n^2$$$), which is more than sufficient to pass $$$N, M \lt = 200$$$.

Note that when we remove a node, only a specific subset of its neighbors become potentially available for removal — namely,

The final time complexity is O($$$n+m$$$), since each edge is traversed a constant number of times.

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

void solve(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> adj(n+1);
    vector<bool> a(n+1),active(n+1);
    vector<int> stable(n+1),safe(n+1);
    for(int i=1;i<=n;i++){
        int x;
        cin >> x;
        a[i]=x-1;
        stable[i]=0;
        safe[i]=0;
        active[i]=1;
    }
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++) for(int u:adj[i]) if(a[u]) stable[i]++;
    for(int i=1;i<=n;i++) for(int u:adj[i]) if((!a[u])&&(stable[u]>a[i])) safe[i]++;
    queue<int> q;
    for(int i=1;i<=n;i++) if(!safe[i]) q.push(i);
    vector<int> ans;
    while(q.size()>0){
        int f=q.front();
        q.pop();
        if(!active[f]) continue;
        active[f]=0;
        if(a[f]){
            for(int u:adj[f]){
                if(active[u]&&!a[u]){
                    stable[u]--;
                    for(int v:adj[u]){
                        if(active[v]&&stable[u]==a[v]){
                            safe[v]--;
                            if(!safe[v]) q.push(v);
                        }
                    }
                }
            }
        }
        else{
            for(int v:adj[f]){
                if(active[v]&&stable[f]>a[v]){
                    safe[v]--;
                    if(!safe[v]) q.push(v);
                }
            }
        }
        ans.push_back(f);
    }
    if(ans.size()!=n){
        cout << -1 << '\n';
        return;
    }
    for(int u:ans) cout << u << ' ';
    cout << '\n';
}

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

Observe that, for a valid construction, all paths from node $$$1$$$ to any other node must have the same length. This is the shortest path.

Try writing out each edge as a constraint on the distance values from node $$$1$$$. Do these inequalities look familiar?

As mentioned in the hints, the distance from node $$$1$$$ to any other node must be the same across all paths. Let this distance be $$$\text{dist}[u]$$$, denoting the distance from node $$$1$$$ to node $$$u$$$.

A directed edge $$$u \rightarrow v$$$ with weight constraint $$$[l, r]$$$ then implies that:

Doing a bit of rearranging, we get:

These inequalities actually enforce the same thing as an edge in a shortest path algorithm! An edge $$$(u, v, w)$$$ in a shortest paths problem forces $$$\text{dist}[v]$$$ to be at most $$$\text{dist}[u] + w$$$, which is essentially what these inequalities are doing.

So, we can construct a graph with these edges. How can we construct our answer, or determine it's impossible to do so?

Since each path from $$$1$$$ to $$$u$$$ has the same distance, we know that the weight of an edge from $$$u$$$ to $$$v$$$ must have weight $$$\text{dist}[v] - \text{dist}[u]$$$, otherwise it would violate the condition. So, if we were unable to calculate the true shortest paths from node $$$1$$$, it would be impossible to construct an answer.

A construction does not exist when the graph has a negative cycle, since a negative cycle would make the distances infinitely negative. The easiest way to check for a negative cycle while calculating distances is using the Bellman-Ford algorithm, but there are other ways of calculating it.

We'll omit the proof for why a negative cycle implies a construction is impossible, but it essentially boils down to chaining together inequalities and making sure that the final result is mathematically valid.

Since we run Bellman-Ford on our graph, the time complexity of the solution is $$$\mathcal{O}(nm)$$$.

#include <bits/stdc++.h>

using ll = long long;

constexpr ll inf = 1e18;

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::array<int, 4>> edges(m);
    for (auto &[u, v, l, r] : edges) {
        std::cin >> u >> v >> l >> r;
        u--, v--;
    }

    std::vector<ll> dist(n, inf);
    dist[0] = 0;

    for (int i = 1; i <= n; i++) {
        auto cpy = dist;
        for (const auto &[u, v, l, r] : edges) {
            dist[v] = std::min(dist[v], dist[u] + r);
            dist[u] = std::min(dist[u], dist[v] - l);
        }

        if (i == n && cpy != dist) {
            std::cout << "-1\n";
            return;
        }
    }

    for (int i = 0; i < m; i++) {
        const auto &[u, v, l, r] = edges[i];
        std::cout << dist[v] - dist[u] << " \n"[i == m - 1];
    }
}

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

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
}

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    edges = []
    for _ in range(m):
        u, v, l, r = map(int, input().split())
        edges.append((u - 1, v - 1, l, r))

    INF = float('inf')
    dist = [INF] * n
    dist[0] = 0

    for i in range(1, n + 1):
        cpy = dist[:]
        for u, v, l, r in edges:
            if dist[u] < INF:
                dist[v] = min(dist[v], dist[u] + r)
            if dist[v] < INF:
                dist[u] = min(dist[u], dist[v] - l)
        if i == n and cpy != dist:
            print(-1)
            return

    results = []
    for u, v, l, r in edges:
        results.append(str(dist[v] - dist[u]))
    print(' '.join(results))

t = int(input())
for _ in range(t):
    solve()

How could divide and conquer be applied to this problem?

In order to solve this problem, we need to use a quadtree (consider it as similar to a 2D segment tree). More specifically, every time we have a grid, we divide it into $$$4$$$ roughly equal size quadrants and in this problem, we try to maintain the connectivity problem between the quadrants of the different levels.

Initially, we should first build the quadtree when given the initial state of the grid. Consider the following when building a specific quadrant:

For the base case of a grid smaller than or equal to $$$3*3$$$, assumed as the overall grid is size of $$$n*n$$$, what we could do is simply enumerate all of the internal connections of the grid and maintain it with a dsu.

For larger grids, what we should do is inherit the information from the lower layers of the sub-quadrants edges, as the inner connectivity cannot be changed with the outside information and only consider the additional information given by the connectivity of the edges from the sub-quadrants that would "intersect" with others affecting the dsu states and process of connecting the dsu only need to be one directional, i.e. only consider the two edges are correspond one to one the grids updating their dsu status.

After recursing by first building the base cases and building the higher levels based on the lower levels, we have the initial state of the quadtree.

To update a specific grid, we would first update the smallest quadrant on a level that contains the grid and gradually work the way up updating every single quadrant in the different levels that contains the flipped grid.

As the initialization of the quadtree is $$$O(n^2)$$$ and each update is $$$O(n)$$$, thus the overall complexity is $$$O(n(n+q))$$$.

#include<bits/stdc++.h>
#define pb push_back
using ll = long long;
using lb = long double;
const lb eps = 1e-9;
const ll mod = 1e9 + 7, ll_max = 1e18;
const int MX = 2009, int_max = 0x3f3f3f3f;
struct {
  template<class T>
  operator T() {
    T x; std::cin >> x; return x;
  }
} in;
using namespace std;
int grid[MX][MX];
int cc[11][MX][MX];
int dsu[MX*MX];
int c_vis[MX*MX];
int n, q;
inline int find(int u){
    return dsu[u]<0?u:dsu[u]=find(dsu[u]);
}
inline void Union(int a, int b){
    a = find(a); b = find(b);
    if(a == b)
        return;
    if(dsu[a] > dsu[b])
        swap(a, b);
    dsu[a] += dsu[b];
    dsu[b] = a;
}
vector<int> vis;
inline int comp(int x,int y){
    return x*n+y;
}
inline void merge(int x1, int x2, int y1, int y2, int op){
    if(x2 - x1 <= 3 || y2 - y1 <= 3){
        for(int i = x1; i<x2; i++)
            for(int j = y1; j<y2; j++)
                if(grid[i][j]){
                    if(i+1 < x2 && grid[i+1][j]) Union(comp(i, j), comp(i+1, j));
                    if(j+1 < y2 && grid[i][j+1]) Union(comp(i, j), comp(i, j+1));
                }
        for(int i = x1; i<x2; i++)
            for(int j = y1; j<y2; j++)
                cc[op][i][j] = find(comp(i, j));
        for(int i = x1; i<x2; i++)
            for(int j = y1; j<y2; j++)
                dsu[comp(i, j)] = -1;
    }else{
        int mx = (x1+x2)/2;
        int my = (y1+y2)/2;
        for(int i : {x1, mx-1, mx, x2-1})
            for(int j = y1; j<y2; j++){
                cc[op][i][j] = cc[op+1][i][j];
                if(!c_vis[cc[op][i][j]]) vis.pb(cc[op][i][j]);
                c_vis[cc[op][i][j]] = 1;
            }
        for(int j : {y1, my-1, my, y2-1})
            for(int i = x1; i<x2; i++){
                cc[op][i][j] = cc[op+1][i][j];
                if(!c_vis[cc[op][i][j]]) vis.pb(cc[op][i][j]);
                c_vis[cc[op][i][j]] = 1;
            }
        for(int i : {x1, mx-1, mx, x2-1})
            for(int j = y1; j<y2; j++)
                if(grid[i][j]){
                    if(i == mx-1 && grid[i+1][j]) Union(cc[op][i][j], cc[op][i+1][j]);
                    if(j+1 < y2 && grid[i][j+1]) Union(cc[op][i][j], cc[op][i][j+1]);
                }
        for(int j : {y1, my-1, my, y2-1})
            for(int i = x1; i<x2; i++)
                if(grid[i][j]){
                    if(i+1 < x2 && grid[i+1][j]) Union(cc[op][i][j], cc[op][i+1][j]);
                    if(j == my-1 && grid[i][j+1]) Union(cc[op][i][j], cc[op][i][j+1]);
                }
        for(int i : {x1, mx-1, mx, x2-1})
            for(int j = y1; j<y2; j++)
                cc[op][i][j] = find(cc[op][i][j]);
        for(int j : {y1, my-1, my, y2-1})
            for(int i = x1; i<x2; i++)
                cc[op][i][j] = find(cc[op][i][j]);
        for(int x : vis){
            c_vis[x] = 0;
            dsu[x] = -1;
        }
        vis.clear();
    }
}
inline void go(int x, int y, int x1, int x2, int y1, int y2, int op){
    if(x2 - x1 > 3 && y2 - y1 > 3){
        int mx = (x1 + x2)/2;
        int my = (y1 + y2)/2;
        if(x < mx && y < my)
            go(x, y, x1, mx, y1, my, op+1);
        else if(x < mx && y >= my)
            go(x, y, x1, mx, my, y2, op+1);
        else if(x >= mx && y < my)
            go(x, y, mx, x2, y1, my, op+1);
        else
            go(x, y, mx, x2, my, y2, op+1);
    }
    merge(x1, x2, y1, y2, op);
}
inline void build(int x1, int x2, int y1, int y2, int op){
    if(x2 - x1 > 3 && y2 - y1 > 3){
        int mx = (x1 + x2)/2;
        int my = (y1 + y2)/2;
        build(x1, mx, y1, my, op+1);
        build(x1, mx, my, y2, op+1);
        build(mx, x2, y1, my, op+1);
        build(mx, x2, my, y2, op+1);
    }
    merge(x1, x2, y1, y2, op);
}
int pre=0;
string answer(){
    pre*=2;
    if(grid[0][0] == 0 || grid[n-1][n-1] == 0)
        return "NO";
    if(cc[0][0][0] == cc[0][n-1][n-1]){
        pre++;
        return "YES";
    }
    else
        return "NO";
}
int num;
int xx[40009];
int yy[40009];
void solve(){
    memset(dsu, -1, sizeof(dsu));
    n = in;
    for(int i = 0; i<n; i++){
        string s = in;
        for(int j = 0; j<n; j++){
            grid[i][j] = s[j]-'0';
        }
    }
    build(0, n, 0, n, 0);
    q=in;
    num=in;
    num=(1<<num);
    for(int i=0;i<num;i++)
        xx[i]=in,yy[i]=in;
    for(int i= 1; i<=q; i++){
        int x = in, y = in;
        x+=xx[pre],y+=yy[pre];
        if(x>n)
            x-=n;
        if(y>n)
            y-=n;
        x--, y--;
        grid[x][y] ^= 1;
        go(x, y, 0, n, 0, n, 0);
        cout << answer() << "\n";
        pre%=num;
    }
}
signed main(){
    solve();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const long long int MOD=1000000007;
const long long int nul=(1LL<<62);

struct Range{
    ll L,R;
};

struct Config{
    Range r;
    ll empty_pos;
};

struct Node{
    Config cfg;
    ll ws;
    int prev,next;
};

bool intersect(Range a,Range b){
    if(a.R<b.L||b.R<a.L) return 0;
    return 1;
}

ll flodiv(ll a,ll b){
    if(a>=0||a%b==0) return a/b;
    else return a/b-1;
}

ll modd(ll a,ll b){
    return (a%b+b)%b;
}

Config newran(ll newws,ll newt){
    if(newt%2){
        ll fd=flodiv(newws,newt),m=modd(newws,newt);
        if(m==0) return {{fd-newt/2,fd+newt/2},nul};
        else return {{fd-newt/2,fd+newt/2+1},fd+newt/2+1-m};
    }
    else{
        ll fd=flodiv(newws,newt),m=modd(newws,newt);
        if(m<=newt/2) return {{fd-newt/2,fd+newt/2},fd-m};
        else if(m==newt/2) return {{fd-newt/2+1,fd+newt/2},nul};
        else return {{fd-newt/2+1,fd+newt/2+1},fd+newt+1-m};
    }
}

ll sos(ll c){
    c=modd(c,MOD);
    return (((((c*(c+1))%MOD)*(2*c+1))%MOD)*((MOD+1)/6))%MOD;
}

ll contrib(Config p){
    if(p.empty_pos==nul) return modd(sos(p.r.R)-sos(p.r.L-1),MOD);
    p.empty_pos=modd(p.empty_pos,MOD);
    return modd(sos(p.r.R)-sos(p.r.L-1)-((p.empty_pos*p.empty_pos)%MOD),MOD);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    ll initsum=0;
    Node link[n+2];
    link[0]={{{-nul,-nul},nul},nul,-1,1};
    link[n+1]={{{nul,nul},nul},nul,n,n+2};
    for(int i=1;i<=n;i++){
        long long int pos, siz;
        cin >> pos >> siz;
        link[i]={{{pos-siz/2,pos+siz/2},((siz%2)?(nul):(pos))},pos*siz,i-1,i+1};
        initsum+=(((pos*pos)%MOD)*siz)%MOD;
        initsum%=MOD;
    }
    int ptr=1;
    while(ptr<=n){
        int nex=link[ptr].next;
        if(intersect(link[ptr].cfg.r,link[nex].cfg.r)){
            ll newws=link[ptr].ws+link[nex].ws;
            ll newt=link[ptr].cfg.r.R-link[ptr].cfg.r.L
                +link[nex].cfg.r.R-link[nex].cfg.r.L
                +(link[ptr].cfg.empty_pos==nul)+(link[nex].cfg.empty_pos==nul);
            link[ptr].cfg=newran(newws,newt);
            link[ptr].ws=newws;
            int newn=link[nex].next;
            link[ptr].next=newn;
            link[newn].prev=ptr;
            ptr=link[ptr].prev;
        }
        else{
            ptr=link[ptr].next;
        }
    }
    ptr=1;
    ll finalsum=0;
    while(ptr<=n){
        finalsum+=contrib(link[ptr].cfg);
        finalsum%=MOD;
        ptr=link[ptr].next;
    }
    long long int ans=(modd(finalsum-initsum,MOD)*((MOD+1)/2))%MOD;
    cout << ans << '\n';
    return 0;
}

Is there a greedy that determines the optimal independent set?

How can we make the $$$K$$$ grids "independent"?

Think game theory. What does the graph also represent?

We can first notice that choosing the independent set can be done greedily from maximum to minimum $$$S$$$ due to $$$NM^{K \cdot S} \gt NM^{K \cdot (S-1)} (NM^K - 1)$$$. The issue now is the large value of $$$K$$$, which calls for finding a way to think of each of the $$$K$$$ boards independently. To do this, consider the following two player-game:

Initially, each grid, numbered $$$1$$$ to $$$K$$$, has one token on one of the cells. Alice and Bob take turns alternately. On each player's turn, the current player chooses some grid $$$G$$$ $$$(1 \leq G \leq K)$$$ and moves the token on cell $$$(i, j)$$$ and moves it to either $$$(k, j)$$$ $$$(0 \leq k \lt i)$$$ or $$$(i, k)$$$ $$$(0 \leq k \lt j)$$$ on grid $$$G$$$. Note that this is equivalent to traversing the graph with each move moving closer to $$$((0, 0), \dots, (0, 0))$$$. The current player loses when they cannot move.

The key realization here is that the game states in which the current player is losing is exactly our desired independent set in the graph. Because there are $$$K$$$ disjoint boards in the setting of a game, we can now think of each token position as some Grundy number. Let $$$\text{SG}(i, j)$$$ be the Grundy number if the token is at $$$(i, j)$$$. From this transformation, we see that a node $$$(P_1, P_2, \dots, P_K)$$$ is in our desired independent set if and only if $$$\text{SG}(P_1) \oplus \text{SG}(P_2), \cdots, \text{SG}(P_{K-1})\oplus \text{SG}(P_K) = 0$$$, where $$$\oplus$$$ is the bitwise XOR operator.

We can then let

Now, denoting the $$$\oplus$$$ convolution operator as $$$*$$$, the answer is $$$(\underbrace{C * ... * C}_{\text{K times}})_0$$$. Naive binary exponentiation can compute this in $$$\mathcal{O}((N + M)^2 \log K)$$$ given that $$$\max(SG(i, j))$$$ scales on the order of $$$\mathcal{O}(N + M)$$$.

These are already some very tough observations, but this still only gets $$$60/100$$$ points. There are still two more key parts to achieve a full solution.

The first part is to optimize calculating Grundy numbers of each cell, in which a naive solution takes $$$\mathcal{O}(NM (N + M))$$$. If we write a brute force and look for patterns, what we find is that $$$\text{SG}(i, j) = i \oplus j$$$. This can be proven by induction by showing that if this property holds for all cells in the square $$$((0, 0), (2^k-1, 2^k-1))$$$, then it also holds for all values in the square $$$((0, 0), (2^{k+1}-1, 2^{k+1}-1))$$$. The full proof is left as an exercise for the reader.

The second part is to optimize the $$$\oplus$$$ convolution. To do this, we must use $$$\oplus$$$ $$$\text{FWHT}$$$ (Fast WalshΓÇôHadamard transform). Denoting $$$\text{FWHT}$$$ as $$$F$$$ for short, we note that $$$C * C = F^{-1}(F(C) \cdot F(C))$$$. Applying $$$\text{FWHT}$$$ naively with binary exponentiation obtains an $$$\mathcal{O}((N + M) \log (N + M)\log K)$$$ solution.

However, we can make this faster by more closely analyzing the convolution.

Canceling the $$$F$$$ and $$$F^{-1}$$$, we get

From this, by induction, we can notice that $$$\underbrace{C * ... * C}_{\text{K times}} = F^{-1}\left(F(C)^K\right)$$$. This allows us to use binary exponentiation on each index of $$$C$$$ and only $$$2$$$ calls of $$$\text{FWHT}$$$, solving the problem in $$$\mathcal{O}((N + M) \cdot (\log (N + M) + \log K))$$$.

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

constexpr int mod = 998244353, inv2 = (mod + 1) / 2;
typedef long long ll;

int add(int x, int y) {
    if (x + y >= mod) return x + y - mod;
    if (x + y < 0) return x + y + mod;
    else return x + y;
}

int mul(int x, int y) {
    return (ll)x * y % mod;
}

int power(int x, int p) {
    int res = 1;
    while (p) {
        if (p & 1) res = mul(res, x);
        x = mul(x, x);
        p >>= 1;
    }

    return res;
}

void FWHT(vector<int> &a, bool inv = false) {
    int sz = a.size();
    for (int len = 1; 2 * len <= sz; len <<= 1) {
        for (int i = 0; i < sz; i += 2 * len) {
            for (int j = i; j < i + len; j++) {
                int x = a[j], y = a[j + len];
                if (!inv) a[j] = add(x, y), a[j + len] = add(x, -y);
                else a[j] = mul(add(x, y), inv2), a[j + len] = mul(add(x, -y), inv2);
            }
        }
    }
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int x = n * m, y = 1;
    while (y < x) y <<= 1;
    int v = power(x, k);
    vector<vector<int>> a(n, vector<int>(m));
    vector<int> f(y);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            f[i ^ j] = add(f[i ^ j], power(v, a[i][j]));
        }
    }

    FWHT(f);
    for (int i = 0; i < y; i++) {
        f[i] = power(f[i], k);
    }

    FWHT(f, 1);
    cout << f[0] << "\n";
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}