What happens if you fix the very first element $$$p_1$$$?

What happens if you look at the last $$$k$$$ bits such that $$$2^k$$$ divides $$$n$$$?

Fixing $$$p_1$$$ uniquely determines the sequence as $$$p_i = p_1 \oplus \text{pref}_i$$$.

Let $$$k$$$ be the highest power of $$$2$$$ that divides $$$n$$$. The set $$${0, 1, \dots, n-1}$$$ has a special property: XORing every element by any value $$$y \lt 2^k$$$ simply permutes the set. This means if there is one valid starting value $$$p_1$$$, there are exactly $$$2^k$$$ valid choices varying only in their lowest $$$k$$$ bits.

For any bit position $$$b \ge k$$$, the number of elements with the $$$b$$$-th bit set in $$${0, 1, \dots, n-1}$$$ (let's call it $$$C_b$$$) is strictly never $$$n/2$$$. By comparing $$$C_b$$$ with the count of set bits in our pref array at position $$$b$$$ (let's call it $$$D_b$$$), we can uniquely deduce the upper bits of $$$p_1$$$:

• If $$$D_b = C_b$$$, the $$$b$$$-th bit of $$$p_1$$$ must be $$$0$$$.
• If $$$n - D_b = C_b$$$, the $$$b$$$-th bit of $$$p_1$$$ must be $$$1$$$.
• Otherwise, $$$0$$$ valid permutations exist.

After determining the unique prefix (the bits $$$\ge k$$$), we set its lower $$$k$$$ bits to $$$0$$$ to form our base. If base produces a valid permutation, our valid $$$p_1$$$ candidates are exactly $$$\text{base} + y$$$ for $$$0 \le y \lt 2^k$$$. Because a smaller $$$p_1$$$ yields a lexicographically smaller sequence, the $$$K$$$-th valid starting element is simply $$$\text{base} + K - 1$$$.

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

void solve() {
    int n;
    long long k_idx;
    cin >> n >> k_idx;
    
    vector<int> pref(n, 0);
    for (int i = 1, x; i < n; ++i) {
        cin >> x;
        pref[i] = pref[i - 1] ^ x;
    }
    
    vector<int> s = pref;
    sort(s.begin(), s.end());
    if (unique(s.begin(), s.end()) != s.end()) {
        cout << 0 << "\n-1\n";
        return;
    }
    
    int k = __builtin_ctz(n), base = 0;
    for (int b = k; b < 30; ++b) {
        int cb = 0, db = 0;
        for (int i = 0; i < n; ++i) {
            cb += (i >> b) & 1;
            db += (pref[i] >> b) & 1;
        }
        if (db == cb) continue;
        if (n - db == cb) base |= (1 << b);
        else {
            cout << 0 << "\n-1\n";
            return;
        }
    }
    
    for (int x : pref) {
        if ((base ^ x) >= n) {
            cout << 0 << "\n-1\n";
            return;
        }
    }
    
    long long tot = 1LL << k;
    cout << tot << "\n";
    if (k_idx > tot) {
        cout << "-1\n";
    } else {
        int p1 = base + (k_idx - 1);
        for (int i = 0; i < n; ++i) {
            cout << (p1 ^ pref[i]) << " \n"[i == n - 1];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Which sequences consisting of only $$${0,1,2}$$$, cannot always be constructed?

Consider the integers greater than 2, in $$$A$$$. Let there be $$$g$$$ of them. We can fix $$$0 \leq r \leq g$$$ of them, which are to remain greater than 2 after all operations, and the rest $$$\leq 2$$$. Since the highest result of the mex of two numbers is $$$2$$$, no change was made to the $$$r$$$ elements we fixed, in any operation.

Now we find $$$V(r)$$$, the number of valid assignments to the remaining $$$n-r$$$ of them.

First consider the case $$$r \gt 0$$$. We claim that all assignments of only $$$0,1,2$$$ to them is attainable, except the assignment of $$$2$$$ to everything. The assignment of $$$2$$$ to everything is only attainable when the original array was already so. To see this, observe that a new 2 can only be obtained by the mex of 0 and 1. Now, to show that all other assignments can be achieved, note that any element can be made $$$0$$$ by mexing with some fixed element with value greater than $$$2$$$. From this, we can immediately form $$$1$$$ too, by the mex of this $$$0$$$ and an element greater than 2. To get $$$2$$$, first have $$$0$$$ at a position where in the end we want either $$$0$$$ or $$$1$$$ (and such an element is present since it isn't all $$$2$$$s). Then, at the position where we want a $$$2$$$, form a $$$1$$$, then mex with the $$$0$$$ we formed. Now the $$$0$$$ we had temporarily, can be upgraded to $$$1$$$ if required, as described before. Thus we have $$$3^{n-r} - 1$$$ possibilities if not all elements less than or equal to $$$2$$$, are $$$2$$$, and $$$3^{n-r}$$$ possibilities otherwise.

Now the case $$$r = 0$$$. We can construct any sequence that is not uniformly 0,1 or 2, using a similar argument as the previous case. And we can see that these uniform sequences cannot be formed from any other sequence, because a new element requires the mex of two elements not equal to it (Hence the last operation cannot leave everything equal). Thus, we have $$$3^n-3$$$ possibilities when not all of them are equal to one of $$$0,1,2$$$, and $$$3^n-2$$$ possibilities otherwise.

We iterate for all $$$0 \leq r \leq g$$$, adding $$${g \choose r} \cdot V(r)$$$ to the answer. This may be written as a single expression modulo the corrections, using the binomial theorem.

#include <bits/stdc++.h>

using namespace std;

#define int long long 

int mod = 998'244'353;

int fact[1'000'001];
int invfact[1'000'001];

int modpow(int b, int e) {
	int a = 1;
	while (e) {
		if (e&1) a = a * b % mod;
		b = b * b % mod;
		e >>= 1;
	}
	return a;
}

int ncr(int n, int r) {
	return fact[n] * invfact[r] % mod * invfact[n-r] % mod;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
	fact[0] = 1;
	for (int i = 1; i < 1'000'001; i++) fact[i] = fact[i-1] * i % mod;
	invfact[1'000'000] = modpow(fact[1'000'000], mod-2);

	for (int i = 1'000'000; i > 0; i--) {
		invfact[i-1] = i * invfact[i] % mod;
	}

	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		int g2 = 0;
		vector<int> a(n); for (auto& u : a) {
			cin >> u;
			if (u > 2) g2++;
		}

		if (g2 == 0) {
			int aeq = true;
			for (int i = 1; i < n; i++) {
				if (a[i] != a[i-1]) {
					aeq = false;
					break;
				}
			}
			// 3^n - 3 + aeq
			int _ = modpow(3, n);
			_ += aeq + mod - 3;
			_ %= mod;
			cout << _ << '\n';
		} else {
			int ans = 0;
			for (int i = 1; i <= g2; i++) {
				int r = ncr(g2, i);
				r = r * ((modpow(3, n-i) - 1 + mod)%mod) % mod;
				ans = (ans + r) % mod;
			}
			int mn = 1000;
			for (int i = 0; i < n; i++) mn = min(mn, a[i]);
			if (mn >= 2) {
				ans = (ans + 1) % mod;
			}
			ans = (ans + modpow(3, n) - 3) % mod;
			cout << ans << '\n';
		}

	}

	return 0;
}

Since $$$b = 2^k$$$ is even, adding or subtracting 1 modulo $$$b$$$ always flips the parity of a digit. How does this affect the total sum of the digits?

Because exactly one digit changes parity each turn, the parity of the total sum of digits strictly alternates every move. The target state $$$0$$$ has an even sum ($$$0$$$). Therefore, Ananth can force a win if and only if the initial sum of digits is odd.

The parity of the sum of base-$$$2^k$$$ digits of $$$n$$$ is simply the XOR sum of the lowest bit of each digit. These correspond to bits $$$0, k, 2k, 3k, \dots$$$ in the binary representation of $$$n$$$.

Notice that adjacent integers $$$(2m, 2m+1)$$$ differ only at bit $$$0$$$. Because bit $$$0$$$ is always included in our check, exactly one number in every such pair will have an odd digit sum. Thus, the number of valid integers in the prefix $$$[0, x]$$$ is exactly $$$(x+1)/2$$$ if $$$x$$$ is odd. If $$$x$$$ is even, it is $$$x/2$$$ plus whether $$$x$$$ itself is valid. We can query $$$[l, r]$$$ as calc(r) - calc(l-1) in $$$O(60/k)$$$ time per testcase.

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

long long calc(long long x, int k) {
    if (x < 0) return 0;
    if (x % 2 != 0) return (x + 1) / 2;
    int p = 0;
    for (int i = 0; i <= 60; i += k) p ^= (x >> i) & 1;
    return x / 2 + p;
}

void solve() {
    long long l, r;
    int k;
    cin >> l >> r >> k;
    cout << calc(r, k) - calc(l - 1, k) << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Can you make use of the operations that replace $$$x,y$$$ with $$$x$$$?

The maximum possible final value is $$$t+1$$$, where $$$n=t(k-1)+p,\quad 1\le p\le k-1$$$, Moreover, every value from (1) to (t+1) is attainable.

Can you prove the construction by induction on $$$t$$$?

Let $$$n=(k-1)t+p$$$ where $$$1\le p\le k-1.$$$ We will prove that the possible final values are exactly $$$\boxed{1,2,\ldots,t+1}.$$$ We first prove the upper bound, and then prove constructively that every value in this range is achievable.

Upper bound

We claim that throughout the process, there is always at least one number on the board which is at most $$$(t+1)$$$. Initially, $$$1$$$ is on the board, so the claim is true. Now suppose that before some operation there is a number $$$x\le t+1$$$ on the board. Consider the two numbers $$$a,b$$$ chosen for the operation. If both $$$a,b \gt t+1$$$, then $$$x$$$ is not erased, so the claim remains true. If both $$$a,b\le t+1$$$, then

because $$$k\ge3$$$. Finally, suppose $$$a\le t+1$$$ and $$$b \gt t+1$$$. Since every number on the board is at most $$$n$$$, $$$a+b\le (t+1)+n.$$$ Using $$$n=(k-1)t+p,\quad p\le k-1$$$, we get $$$a+b \le (t+1)+(k-1)t+(k-1) = k(t+1)$$$. Hence $$$\left\lceil\frac{a+b}{k}\right\rceil\le t+1$$$. Thus, after every operation, there is still some number at most $$$t+1$$$. When only one number remains, it follows that the final answer must be at most $$$t+1$$$. Therefore, $$$\boxed{x \gt t+1\text{ is impossible}.}$$$

When can one number eat another?

We say that $$$x$$$ eats $$$y$$$ if $$$\left\lceil\frac{x+y}{k}\right\rceil=x.$$$ This happens exactly when $$$x-1 \lt \frac{x+y}{k}\le x,$$$ which is equivalent to $$$\boxed{(x-1)(k-1)\le y\le x(k-1)}.$$$ We will use this observation in the construction.

Construction by induction on $$$t$$$

We prove the following statement by induction on $$$t$$$: For every $$$n=(k-1)t+p$$$, $$$1\le p\le k-1$$$, we can construct every value $$$1,2,\ldots,t+1.$$$

Base case: $$$t=0$$$

Since $$$n=(k-1)\cdot0+p=p,$$$ we have $$$1\le n\le k-1.$$$ The only value we need to construct is $$$t+1=1$$$. We can repeatedly combine numbers while keeping the value $$$1$$$. Indeed, $$$1$$$ can eat any $$$y$$$ satisfying $$$0\le y\le k-1.$$$ Since every number on the board is between $$$1$$$ and $$$k-1$$$ the initial $$$1$$$ can eat all other numbers one by one. Therefore we can finish with $$$\boxed{1}.$$$ So the statement holds for $$$t=0$$$.

Induction step

Now assume the statement is true for $$$t-1$$$, and consider $$$n=(k-1)t+p, \quad 1\le p\le k-1$$$. We show how to construct every value from $$$1$$$ to $$$t+1$$$.

Constructing a value $$$z\le t$$$

Consider the number $$$t+1$$$. By our eating condition, $$$t+1$$$ can eat every number in $$$[t(k-1),(t+1)(k-1)]$$$. In particular, it can eat all the numbers $$$(k-1)t+1, (k-1)t+2, \ldots, (k-1)t+p$$$. After performing these operations, the remaining numbers are exactly $$$1,2,\ldots,(k-1)t$$$. Now observe that $$$(k-1)t=(k-1)(t-1)+(k-1)$$$. Thus this is precisely an instance of the same problem with parameter $$$t-1$$$ and $$$p'=k-1$$$, so by the induction hypothesis, we can construct any value $$$1\le z\le t$$$ from these remaining numbers. Therefore every value $$$z\le t$$$ is achievable.

Constructing $$$t+1$$$

It remains to construct $$$t+1$$$. Again, let the initial $$$t+1$$$ eat the numbers $$$(k-1)t+2, (k-1)t+3, \ldots, (k-1)t+p.$$$ This is valid because all these numbers lie in the interval $$$[t(k-1),(t+1)(k-1)].$$$ Notice that we deliberately leave $$$(k-1)t+1$$$ untouched. After these operations, the board contains $$$1,2,\ldots,(k-1)t+1$$$. Now consider the first $$$(k-1)t$$$ numbers. By the induction hypothesis, since $$$(k-1)t=(k-1)(t-1)+(k-1),$$$ we can construct the value $$$t$$$ from $$$1,2,\ldots,(k-1)t$$$. Therefore, after these operations, the only two numbers remaining are $$$t$$$ and $$$(k-1)t+1$$$. Perform one final operation. Its value is

Hence $$$t+1$$$ is also achievable. This completes the induction. Therefore, for $$$n=(k-1)t+p,\quad 1\le p\le k-1,$$$ the set of possible final values is exactly $$$\boxed{1\le x\le t+1}.$$$ The recursive construction performs only $$$O(1)$$$ operations for each number, so the complete construction can be generated in $$$\boxed{O(n)}$$$ time.

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n, k, x;
        cin >> n >> k >> x;
        
        int km1 = k - 1;
        int t = (n - 1) / km1;          // n = (k-1)*t + p
        if (x > t + 1) {
            cout << "NO\n";
            continue;
        }
        
        cout << "YES\n";
        vector<pair<int, int>> ops;
        vector<tuple<int, int, int>> stk;
        stk.emplace_back(n, x, 0);
        
        while (!stk.empty()) {
            auto [cur_n, cur_x, state] = stk.back();
            stk.pop_back();
            
            // Base case: all numbers ≤ k-1, the only achievable target is 1
            if (cur_n <= km1) {
                for (int i = 2; i <= cur_n; ++i) {
                    ops.emplace_back(1, i);
                }
                continue;
            }
            
            int cur_t = (cur_n - 1) / km1;
            int start = km1 * cur_t;          // (k-1)*cur_t
            int cur_p = cur_n - start;        // p for the current subproblem
            
            if (state == 0) {
                if (cur_x == cur_t + 1) {
                    // Build t+1: eat numbers start+2 .. start+cur_p, leave start+1
                    for (int y = start + 2; y <= start + cur_p; ++y) {
                        ops.emplace_back(cur_t + 1, y);
                    }
                    stk.emplace_back(cur_n, cur_x, 1);   // combine later
                    stk.emplace_back(start, cur_t, 0);   // build t from first part
                } else {
                    // Build z ≤ t: eat all top numbers start+1 .. start+cur_p
                    for (int y = start + 1; y <= start + cur_p; ++y) {
                        ops.emplace_back(cur_t + 1, y);
                    }
                    stk.emplace_back(start, cur_x, 0);   // recurse on first part
                }
            } else {  // state == 1
                // Final combination: result 't' with (k-1)t+1
                ops.emplace_back(cur_t, start + 1);
            }
        }
        
        for (auto [a, b] : ops) {
            cout << a << ' ' << b << '\n';
        }
    }
    return 0;
}

When you evaluate $$$P(B)$$$ and convert it to base $$$B$$$, the resulting digits perfectly match the original coefficients $$$c_i$$$ if and only if $$$c_i \lt B$$$ for all $$$i$$$.

Since the base $$$B$$$ digits of $$$P(B)$$$ match the coefficients $$$c_i$$$ if and only if $$$c_i \lt B$$$ for all $$$i$$$, finding the number of valid polynomials for a fixed base $$$B$$$ is equivalent to finding the number of solutions to $$$\sum_{i=1}^N c_i = S$$$ subject to $$$0 \le c_i \le B-1$$$.

Using the Principle of Inclusion-Exclusion, the number of valid sequences is:

Using the identity $$$\binom{A+B}{B} = \binom{A+B}{A}$$$, we can rewrite the second combination as $$$\binom{S - jB + N - 1}{S - jB}$$$. Since $$$S \le 2 \cdot 10^5$$$, we can precompute $$$G[j] = \binom{N}{j}$$$ and $$$F[X] = \binom{X + N - 1}{X}$$$ for all $$$j, X \le S$$$ in $$$O(S)$$$ time. Then, we compute the sum of $$$W(B)$$$ over all bases $$$B \in [2, S]$$$ in $$$O(S \log S)$$$ time using the harmonic series property. Finally, the probability is the sum of valid configurations divided by the total possible combinations $$$(S-1)\binom{S+N-1}{S}$$$.

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

const int MOD = 998244353;

long long power(long long b, long long e) {
    long long r = 1;
    b %= MOD;
    while (e) {
        if (e % 2) r = (r * b) % MOD;
        b = (b * b) % MOD;
        e /= 2;
    }
    return r;
}

void solve() {
    long long n, s;
    cin >> n >> s;
    
    vector<long long> inv(s + 1, 1), f(s + 1, 1), g(s + 1, 1);
    for (int i = 2; i <= s; i++) {
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
    }
    for (int i = 1; i <= s; i++) {
        if (n >= i) g[i] = g[i - 1] * ((n - i + 1) % MOD) % MOD * inv[i] % MOD;
        else g[i] = 0;
        f[i] = f[i - 1] * ((i + n - 1) % MOD) % MOD * inv[i] % MOD;
    }
    
    long long num = 0;
    for (int b = 2; b <= s; b++) {
        for (int j = 0; j * b <= s; j++) {
            long long term = g[j] * f[s - j * b] % MOD;
            if (j % 2 == 1) num = (num - term + MOD) % MOD;
            else num = (num + term) % MOD;
        }
    }
    
    long long den = (s - 1) % MOD * f[s] % MOD;
    cout << num * power(den, MOD - 2) % MOD << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

Can you look at the sequence backwards?

In the minimal sequence of a fraction with a maximal number of / presses, what happens if you replace two consecutive + presses by a single +?

Minimal sequences

We want to maximize the number of / presses in the minimal sequence of a reachable fraction $$$\frac{p}{q},\quad 1\le p,q\le N$$$. Look at the sequence backwards. Suppose the current fraction is $$$\frac{p}{q}$$$. If $$$p \lt q$$$, then the last operation must have been /. If $$$p \gt q$$$, the last operation must be +. Indeed, / would give $$$q/p \lt 1$$$, and the operation immediately before that would also have to be /, which is never useful in a minimal sequence since two consecutive / presses cancel each other. Thus, the minimal sequence is essentially determined by repeatedly doing the following: if $$$p \lt q$$$, swap $$$p,q$$$; if $$$p \gt q$$$, replace $$$p$$$ by $$$p-q$$$. Every fraction is reachable, and the minimal sequence is unique.

Removing consecutive + presses

Now consider a fraction whose minimal sequence contains the maximum possible number of / presses. Suppose its sequence contains two consecutive + presses. Replacing these two presses by a single + produces another reachable fraction where the resulting numerator and denominator are both no larger than those of the original fraction. Therefore, if we are looking for a fraction under the bounds $$$p,q\le N$$$ with the maximum number of / presses, we do not need to consider a sequence containing two consecutive + presses. Hence the sequence alternating between + and /, starting with+, is maximal. We can see that the numerators and denominators are consecutive Fibonacci numbers. Thus, one of the best fractions is of the form $$$\frac{F_i}{F_{i+1}}$$$ where both Fibonacci numbers are at most $$$N$$$. So we simply find the largest consecutive Fibonacci numbers not exceeding $$$N$$$, and output their ratio (with the numerator $$$\leq$$$ the denominator). Since Fibonacci numbers grow exponentially, there are only $$$O(\log N)$$$ of them. Therefore the total complexity is $$$\boxed{O(\log N)}.$$$

#include <iostream>
#include <vector>

using namespace std;

// Store precomputed Fibonacci numbers
vector<long long> F;

void precompute_fibs() {
    F.push_back(0); // F[0] = 0 (1-based indexing for ease)
    F.push_back(1); // F[1] = 1
    F.push_back(1); // F[2] = 1
    
    // Precompute up to just safely over 10^18
    while (true) {
        long long next_F = F[F.size() - 1] + F[F.size() - 2];
        F.push_back(next_F);
        if (next_F > 2000000000000000000LL) {
            break;
        }
    }
}

void solve() {
    long long n;
    cin >> n;

    // Edge case for N = 1
    if (n == 1) {
        cout << 0 << " " << 1 << " " << 1 << "\n";
        return;
    }

    // Find the largest Fibonacci number F[m] such that F[m] <= n
    int m = 1;
    while (m + 1 < F.size() && F[m + 1] <= n) {
        m++;
    }

    // The maximum division presses is exactly m - 2.
    // A fraction achieving this optimally is F[m-1] / F[m].
    long long k = m - 2;
    long long p = F[m - 1];
    long long q = F[m];

    cout << k << " " << p << " " << q << "\n";
}

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

    precompute_fibs();

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

    return 0;
}

If a string $$$s \in S$$$ can be formed by concatenating two or more other strings from $$$S$$$, do we ever need to include $$$s$$$ in our basis $$$B$$$?

The required subset $$$B$$$ is exactly the set of "non-composite" strings in $$$S$$$. If a string is composite (can be formed by $$$\ge 2$$$ strings in $$$S$$$), it can be built from smaller strings, which by induction can be built from non-composite strings. If it is non-composite, it cannot be built from anything else and must be in $$$B$$$. Thus, this $$$B$$$ is the unique minimal solution.

We can check if a string $$$s$$$ is composite using a standard reachability DP over its length: $$$\text{dp}[i]$$$ is true if the prefix of length $$$i$$$ can be formed. To ensure $$$s$$$ is made of $$$\ge 2$$$ pieces, we simply forbid the single split that uses the entire length $$$|s|$$$.

Naively, this DP takes $$$O(|s|^2)$$$ per string. However, since all strings are distinct, the number of distinct lengths $$$D$$$ among all strings is bounded by $$$O(\sqrt{\sum |s|})$$$. Instead of trying all possible split points, we only transition using piece-lengths that actually exist in $$$S$$$. Using polynomial hashing for $$$O(1)$$$ substring checks, the total time complexity drops to $$$O(\sum |s| \cdot \sqrt{\sum |s|})$$$.

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

void solve() {
    int n;
    if (!(cin >> n)) return;
    
    vector<string> s(n);
    vector<int> lens;
    unordered_set<uint64_t> dict;
    const uint64_t P = 13331;
    
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
        lens.push_back(s[i].length());
        uint64_t h = 0;
        for (char c : s[i]) h = h * P + c;
        dict.insert(h);
    }
    
    sort(lens.begin(), lens.end());
    lens.erase(unique(lens.begin(), lens.end()), lens.end());
    
    vector<string> ans;
    for (int i = 0; i < n; ++i) {
        int m = s[i].length();
        vector<uint64_t> h(m + 1, 0), p(m + 1, 1);
        for (int j = 0; j < m; ++j) {
            h[j + 1] = h[j] * P + s[i][j];
            p[j + 1] = p[j] * P;
        }
        
        vector<int> dp(m + 1, 0);
        dp[0] = 1;
        for (int j = 1; j <= m; ++j) {
            for (int l : lens) {
                if (l > j) break;
                if (l == m) continue;
                if (dp[j - l]) {
                    uint64_t sub = h[j] - h[j - l] * p[l];
                    if (dict.count(sub)) {
                        dp[j] = 1;
                        break;
                    }
                }
            }
        }
        if (!dp[m]) ans.push_back(s[i]);
    }
    
    cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); ++i) {
        cout << ans[i] << " \n"[i == ans.size() - 1];
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    if (cin >> t) {
        while (t--) solve();
    }
    return 0;
}

Consider the remaining distance $$$x$$$ in the horizontal direction, and $$$y$$$ in the vertical direction. Is there an invariant you can force on the next player, if it isn't satisfied in your turn?

The first player wins exactly when $$$m \neq n$$$. The winning strategy is to just move to make the remaining board a square, so that after the next player moves (if he can), the remaining board becomes a non-square again, after which we are again guaranteed a move, and so on.

Alternatively, this can be solved by viewing this as a nim game with two piles.

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

int main() {
    int t; cin >> t;
    while(t--) {
        int n, m; cin >> n >> m;
        if (n == m) cout << "Dip\n";
        else cout << "Shankha\n";
    }
    return 0;
}