In this game, optimal play is strictly dictated by the frequency $$$f_x$$$ of each distinct value $$$x$$$. We categorize these frequencies into two states:

• Traps ($$$f_x \ge 2$$$): To score $$$x$$$ points, a player must remove the final copy (reducing $$$f_x$$$ from 1 to 0). This requires someone else to make the sacrificial move of reducing it from 2 to 1. If a player makes this sacrifice, the opponent will immediately claim the remaining copy and the points. Therefore, neither player will ever touch an element with $$$f_x \ge 2$$$ unless absolutely forced.
• Safe Moves (Odd Frequencies): A safe move is any reduction that does not leave exactly one copy of a number. Every element with an odd frequency provides exactly 1 safe move (reducing it to an even frequency). Elements with an even frequency provide 0 safe moves. Game Flow and Parity Because both players strictly avoid traps, the game is purely a race to exhaust the safe moves. Let $$$k$$$ be the total number of distinct values in the array that have an odd frequency.

Since Alice and Bob alternate turns, the parity of $$$k$$$ perfectly determines who runs out of safe moves first: * If $$$k$$$ is Odd: Alice takes the final safe move. Bob is cornered and forced to open the first trap. This triggers a cascading chain reaction where Alice will inevitably secure the points for every single value that has $$$f_x \ge 2$$$. * If $$$k$$$ is Even: Bob takes the final safe move. Alice is cornered. Bob secures the points for every single value that has $$$f_x \ge 2$$$.

The Greedy Phase While exhausting the safe moves, players still want to maximize their immediate score. * A safe move on $$$f_x \ge 3$$$ yields 0 immediate points. * A safe move on $$$f_x = 1$$$ immediately awards $$$x$$$ points.

Thus, both players will greedily prioritize the elements where $$$f_x = 1$$$. They will draft from the pool of $$$f_x = 1$$$ elements in strictly descending order. Because Alice always takes the first turn of the game, she takes the largest, Bob takes the second largest, Alice takes the third, and so on.

The "Hakurei Reduction Ritual" precisely simulates the subtractive Euclidean algorithm. To determine how many valid pairs can be purified in exactly $$$k$$$ steps, it is mathematically more intuitive to analyze the process in reverse.

Starting from the purified root state $$$(1, 1)$$$ at step $$$0$$$, any ordered pair $$$(a, b)$$$ can "generate" two distinct parent pairs that would have reduced to it in the previous step: $$$(a+b, b)$$$ and $$$(a, a+b)$$$.

At step $$$k=0$$$, we have exactly $$$1$$$ valid pair: $$$(1, 1)$$$. For any subsequent step, because the elements of any newly generated pair are strictly distinct (one value is always greater than the other), applying the reverse operation will always branch out into exactly two completely new, unique ordered pairs. Therefore, the number of new ordered pairs added at exactly $$$k$$$ steps grows geometrically: it is exactly $$$2^k$$$ for any $$$k \ge 1$$$.

To find $$$f(k)$$$, which represents the total number of ordered pairs requiring $$$\le k$$$ steps, we sum the new pairs generated at each level. This forms a standard geometric progression:

The problem asks for the smallest $$$k$$$ such that $$$f(k) \ge s$$$. By substituting our derived formula, we establish the inequality:

Taking the base-2 logarithm of both sides, this mathematical requirement cleanly translates to:

Mathematical Formulation & Core Observations: Let $$$S_{L,R} = {P_L, P_{L+1}, \dots, P_R}$$$ be the set of energy signatures in the segment $$$[L, R]$$$. The segment is defined as stable if and only if:

To build the optimal sequence of extensions, we rely on two mathematical properties of permutations:

1. Forced Expansion (Uniqueness of Validity): Suppose the current segment $$$[L, R]$$$ is stable. If we extend the segment by exactly one adjacent index (yielding size $$$R - L + 2$$$), the segment remains stable if and only if the new $$$\max - \min$$$ difference increases by exactly $$$1$$$. Consequently, the new element $$$P_{new}$$$ (where $$$new \in {L-1, R+1}$$$) must strictly satisfy:

Any other value breaks the equality. Therefore, extensions are strictly forced; we never branch arbitrarily.

2. Greedy Monotonic Traversal: Let $$$D(u, v) = |u - v| + |P_u - P_v| - 1$$$ be the cost function. Because $$$D(u, v)$$$ is based on the $$$L_1$$$ (Manhattan) metric, moving along a strictly increasing or decreasing contiguous subsegment of $$$P$$$ satisfies the triangle equality: $$$D(u, v) + D(v, w) = D(u, w)$$$. Thus, whenever an expansion enters a monotonic subsegment ($$$|P_k - P_{k \pm 1}| = 1$$$), it is strictly optimal to traverse the entire maximal monotonic chain in a single $$$\mathcal{O}(1)$$$ step.

Dynamic Programming & The Objective Function: Let $$$\text{dist}(u, v) = |u - v| + |P_u - P_v|$$$ (the cost without the $$$-1$$$ deduction). For a maximal stable segment of final size $$$S$$$, exactly $$$S-1$$$ jumps are made. The true total cost is:

Because the final segment boundaries $$$[L_{fin}, R_{fin}]$$$ satisfy $$$R_{fin} - L_{fin} = S - 1$$$, we can entirely omit the $$$-1$$$ from the DP transitions and simply return $$$-(R_{fin} - L_{fin})$$$ as the base case. This massive negative weight algebraically offsets the jumps and naturally forces the $$$\min()$$$ transitions to prioritize paths that maximize the size of the final interval.

State Transitions: Let $$$dp(L, R) = (C_L, C_R)$$$, where $$$C_L$$$ is the minimal future cost to exhaust the permutation ending the current sweep at $$$L$$$, and $$$C_R$$$ is the cost ending at $$$R$$$. When expanding from $$$[L, R]$$$ to a new maximal monotonic boundary $$$[L', R']$$$, the recurrence to finish at $$$L'$$$ (from a starting position $$$u \in {L, R}$$$) is:

(A symmetric recurrence applies for $$$C_{R'}$$$).

Why does the DP not visit $$$\mathcal{O}(N^2)$$$ states?

In a naive Interval DP, evaluating every valid contiguous subsegment of a permutation can visit up to $$$\mathcal{O}(N^2)$$$ states. For example, in the identity permutation $$$P = [1, 2, 3, \dots, N]$$$, every single contiguous block is a valid stable segment, leading exactly to $$$\frac{N(N+1)}{2}$$$ states. This would instantly cause a Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) verdict.

However, our solution is strictly bounded to $$$\mathcal{O}(N)$$$ states. To prove this, we rely on a concept from algebraic combinatorics known as the Substitution Decomposition of Permutations (or Modular Decomposition).

1. The Substitution Decomposition Tree The family of all valid stable segments (intervals) of any permutation can be perfectly represented by a unique hierarchical tree. In this tree: * The leaves are the individual elements of the permutation (exactly $$$N$$$ leaves). * The internal nodes represent valid intervals formed by merging their children.

Graph theory dictates that for any tree with $$$N$$$ leaves where every internal node has at least two children, the maximum number of internal nodes is exactly $$$N - 1$$$.

There are exactly two types of internal nodes in a permutation's decomposition tree: * Linear Nodes (Monotonic): The children of this node strictly increase or decrease (e.g., $$$P = [4, 5, 6, 7]$$$). Any contiguous combination of these elements forms a valid interval. This specific node is the only reason permutations can have $$$\mathcal{O}(N^2)$$$ valid intervals. * Prime Nodes (Simple): The children form a complex, non-monotonic pattern (of length $$$K \ge 4$$$) that cannot be broken down into smaller valid intervals (e.g., $$$P = [3, 1, 4, 2]$$$). A Prime node of size $$$K$$$ only generates $$$\mathcal{O}(K)$$$ valid sub-intervals.

2. The Effect of the Greedy Fast-Forward Recall our DP transitions: when the DP detects that an adjacent element perfectly extends the segment (e.g., $$$P_{L-1} = \min - 1$$$), it does not just take one step. It uses the precomputed arrays $$$f$$$ and $$$g$$$ to instantly fast-forward to the end of the monotonic chain: $$$nl = f[L-1]$$$.

When the DP encounters a Linear Node, it detects the monotonic pattern. By fast-forwarding, the DP completely skips all intermediate $$$\mathcal{O}(K^2)$$$ subset combinations. Instead of visiting $$$[5, 6]$$$, then $$$[4, 6]$$$, then $$$[4, 7]$$$, the DP instantly jumps from the single element to the absolute maximal boundaries of the Linear Node.

Mathematically, this optimization perfectly collapses the $$$\mathcal{O}(K^2)$$$ states of every Linear Node into exactly $$$1$$$ state (the root of the node itself).

3. The Final $$$\mathcal{O}(N)$$$ Bound Let's calculate the total number of unique valid intervals $$$[L, R]$$$ our DP will ever push to the memoization hash map across all possible starting points: * For Prime Nodes, it evaluates the boundaries of the node. * For Linear Nodes, because of the $$$f$$$ and $$$g$$$ arrays, it evaluates only the single maximal boundary of the node.

Therefore, the only states $$$(L, R)$$$ ever visited and stored by our DP correspond exactly to the roots of the subtrees in the Substitution Decomposition Tree, plus the single leaves.

Because $$$2N - 1$$$ is strictly linear, the number of unique states $$$[L, R]$$$ queried or stored in the hash map is mathematically guaranteed to be $$$\mathcal{O}(N)$$$. This ensures the sparse Interval DP safely operates well within the $$$\mathcal{O}(\sum N)$$$ time and space limits without ever experiencing a combinatorial explosion.

Time Complexity: $$$\mathcal{O}(N)$$$ or expected $$$\mathcal{O}(N \log N)$$$ per test case depending on the hash table implementation. The aggregate time complexity is $$$\mathcal{O}(\sum N)$$$, comfortably passing the time limit.

1. The Bijection: Erasing the Tree The most striking feature of this problem is that the structure of the tree is completely irrelevant. We can prove this using a standard property of XOR on trees.

Let's pick an arbitrary root, say Node 1. Instead of assigning weights to edges, let's assign a "potential" $$$X_i$$$ to each node $$$i$$$, defined as the XOR sum of all edge weights on the simple path from Node 1 to Node $$$i$$$. By definition, the root has a potential of $$$X_1 = 0$$$.

Because $$$A \oplus A = 0$$$, any shared edges on the paths to $$$u$$$ and $$$v$$$ will cancel out. Therefore, the path XOR between any two nodes $$$u$$$ and $$$v$$$ is elegantly given by:

Furthermore, there is a perfect one-to-one bijection between any assignment of $$$N-1$$$ edge weights and any assignment of $$$N-1$$$ node potentials $$$(X_2, X_3, \dots, X_N)$$$. The problem is mathematically reduced from a graph problem to a pure algebraic one:

Find the number of arrays $$$X$$$ (with $$$X_1 = 0$$$) such that:

2. Bitwise Independence Since XOR operates independently on each bit, we can calculate the total sum by looking at the matrix of bits vertically rather than horizontally.

Consider the $$$b$$$-th bit across all $$$N$$$ node potentials. Suppose exactly $$$k$$$ nodes have this bit set to $$$1$$$, and the remaining $$$N-k$$$ nodes have it set to $$$0$$$. A pair of nodes $$$(u, v)$$$ will only contribute to the total sum at the $$$b$$$-th bit if their bits differ (one is $$$1$$$, the other is $$$0$$$). The number of such pairs is exactly $$$k(N-k)$$$.

Thus, choosing $$$k$$$ nodes to have the $$$b$$$-th bit set contributes exactly $$$k(N-k) \cdot 2^b$$$ to the total sum. Since $$$X_1$$$ is locked to $$$0$$$, we are choosing $$$k$$$ nodes from the remaining $$$N-1$$$ nodes, which can be done in $$$\binom{N-1}{k}$$$ ways.

3. The DP Formulation We have distilled the entire problem into finding the number of sequences $$$k_0, k_1, \dots, k_{60}$$$ (where $$$0 \le k_b \le N-1$$$) such that:

Because the coefficient $$$k(N-k)$$$ can be much larger than 1 (up to $$$\approx \frac{N^2}{4}$$$), the bits will "carry over" to higher positions, just like standard addition. We can solve this using Digit DP.

Let's process the target sum $$$S$$$ from the most significant bit down to the least significant bit. We maintain a DP state representing the "required carry"—the exact numerical value that the remaining lower bits must sum up to, scaled to the current bit's perspective.

At the $$$b$$$-th bit, let our currently required carry be $$$j$$$: 1. Target Bit: If the $$$b$$$-th bit of $$$S$$$ is $$$1$$$, the total sum required at this level increases by $$$1$$$. So, our required carry $$$j$$$ becomes $$$j + 1$$$. 2. Our Choice: We select a number of $$$1$$$s, $$$k \in [0, N-1]$$$. This generates a sum of $$$k(N-k)$$$ at the current bit level. 3. The Transition: After generating $$$k(N-k)$$$, the remaining deficit that must be fulfilled by the lower bits is $$$j - k(N-k)$$$. 4. The Shift: Because we are moving down to the $$$(b-1)$$$-th bit, which has exactly half the place value, the deficit from the perspective of the new bit is doubled. Our new required carry state becomes $$$nx = 2 \times (j - k(N-k))$$$.

By multiplying the number of ways to transition by $$$\binom{N-1}{k}$$$ and bubbling it down to bit 0, the final answer will be the number of ways to perfectly achieve a required carry of exactly $$$0$$$.

Complexity: * Time Complexity: $$$\mathcal{O}(\log S \cdot N^3)$$$. The maximum carry $$$j$$$ never exceeds the maximum possible generation at a single bit, $$$\frac{N^2}{4}$$$. Transitioning takes $$$\mathcal{O}(N)$$$, giving $$$\mathcal{O}(\log S \cdot N^3)$$$ which easily passes for $$$N = 300$$$. * Space Complexity: $$$\mathcal{O}(N^2)$$$ for the combinations matrix and the DP row.

The Lower Bound To achieve a MEX of at least $$$1$$$ for any row or column, the value $$$0$$$ must be present in every single row and column. This strictly requires at least $$$n$$$ zeros in the matrix. If $$$k \lt n$$$, constructing such a matrix is impossible, so the answer is -1. Since the problem explicitly excludes $$$k = n$$$, we only need to formulate a valid construction for $$$k \ge n + 1$$$.

The Construction Strategy For edge case n =2 we can hardcode it. Now, We set the target permutation to the identity sequence $$$p = (1, 2, \ldots, n)$$$ and construct the matrix systematically:

1. Initialize the Base Grid: Start by filling the $$$n \times n$$$ matrix as a cyclic Latin square using the formula $$$A[r][c] = (c - r + n) \bmod n$$$. This guarantees every row and column initially contains every value from $$$0$$$ to $$$n-1$$$ exactly once.
2. Lock the Column MEX: Overwrite the last row with the sequence $$$(n-1, 1, 2, \dots, n-2, 0)$$$. This selectively removes the value $$$i$$$ from column $$$i$$$ while preserving all smaller integers, successfully forcing the MEX of column $$$i$$$ to be exactly $$$i$$$.
3. Lock the Row MEX: For each row $$$i$$$ (from $$$2$$$ to $$$n$$$), find the column $$$j$$$ containing the value $$$i$$$. Swap $$$A[i][j]$$$ with $$$A[1][j]$$$. Swapping vertically preserves the exact multiset of every column but cleanly evicts the value $$$i$$$ from row $$$i$$$, forcing its MEX to exactly $$$i$$$.
4. Finalize the Matrix: The previous step dumps discarded values into row $$$1$$$. To guarantee row $$$1$$$ has a MEX of $$$1$$$, we forcefully overwrite $$$A[1][2] = 0$$$. This places the $$$(n+1)$$$-th zero into the grid, fully satisfying the frequency constraint $$$k \ge n+1$$$.

Complexity This direct construction generates the required grid in optimal $$$\mathcal{O}(n^2)$$$ time and space.

The optimal strategy can be divided into two distinct phases: identifying the exact multiset of letters in the secret word, and then determining their correct arrangement.

Phase 1: Identifying the Multiset We can query strings made of $$$m$$$ distinct letters from the alphabet. Each query tells us exactly how many of those specific letters are in the secret. To cover an alphabet of size $$$n$$$, we partition the alphabet into blocks of size $$$m$$$, which generally requires $$$c = \lceil n/m \rceil$$$ queries.

However, we can save exactly one query in a few edge cases: * If $$$n \equiv 1 \pmod m$$$, the final unqueried block contains exactly $$$1$$$ letter. Since we know the secret word has a fixed length $$$m$$$, any missing character count must belong to this single remaining letter, so we don't need to explicitly query it. * Similarly, if $$$n = m$$$ or $$$m = 1$$$, we can deduce the letters while merging this step with Phase 2, reducing the dedicated identification queries by $$$1$$$.

In these cases, we set $$$c = \lceil n/m \rceil - 1$$$.

Phase 2: Determining the Order The absolute worst-case scenario occurs when the secret word consists of $$$m$$$ distinct letters. This maximizes the number of valid permutations to $$$m!$$$. Since we have already identified the letters, we just need to guess the arrangements.

The minimum worst-case guesses required to finish the game is simply the sum of the identification queries and the permutation queries: $$$m! + c$$$. We compute this result modulo $$$10^9+7$$$.

Time Complexity: $$$\mathcal{O}(m)$$$ to precompute factorials up to $$$10^6$$$, and $$$\mathcal{O}(1)$$$ per test case to compute $$$\lceil n/m \rceil$$$ and retrieve the factorial.

If Bob knows the parity of Alice's location, he can complete the problem in $$$n$$$ or $$$n-1$$$ guesses: He starts guessing from $$$n$$$ or $$$n-1$$$, whichever is at the same parity as Alice. At each turn, he reduces his guess by $$$1$$$. Since both always have the same parity, they must meet somewhere in the middle, as Alice cannot ``cross" Bob.

With this idea, Bob makes the following sequence of guesses: $$$n-1, n-2, \cdots , 3, 2$$$

Now Bob has either won, or he knows Alice's parity.

If he hasn't won yet, then initially, Alice and Bob had different parities (i.e. Alice and $$$n$$$ had the same parity). After these $$$n-2$$$ moves, Alice's parity is the same as $$$n + (n-2) = 2n-2$$$, which is even. Also, the maximum number Alice could have reached is $$$2n-2$$$.

Bob makes the following sequence of guesses: $$$2n-2, 2n-3, \cdots, 4,3$$$ ($$$2n-4$$$ guesses — an even number of moves) If Bob still hasn't won, Alice must be at an even number, so Bob finally guesses $$$2$$$ and wins in $$$(n-2) + (2n-4) + (1) = 3n-5$$$ guesses.

Check the string $$$s$$$ of length $$$n$$$ against three simple conditions:

1. All characters are identical: No non-palindromic substring exists. Output $$$0$$$.
2. $$$s$$$ is not a palindrome: The longest valid substring is the entire string itself. Output $$$n$$$.
3. $$$s$$$ is a palindrome (but characters differ): Removing the last character breaks the palindrome. (If a palindrome of length $$$n$$$ had a palindromic prefix of length $$$n-1$$$, all characters would be forced to be identical, which we already ruled out). Output $$$n-1$$$.

Time Complexity: $$$\mathcal{O}(n)$$$ to check the characters and reverse the string.

Hint 1

For any two sequences, $$$d(i,j) = \text{popcount}(a_i \oplus a_j)$$$. Since $$$a_i \lt 2^{30}$$$, the difference can only take 31 possible values (from $$$0$$$ to $$$30$$$).

Hint 2

By the Pigeonhole Principle, if we look at just the first 64 elements, we can form 32 disjoint pairs (e.g., $$$(1,2), (3,4) \dots$$$). Since there are only 31 possible difference values, at least two disjoint pairs must share the same difference. Thus, we never need to examine more than $$$m = \min(n, 64)$$$ elements.

Hint 3

We only need to store up to 3 pairs per popcount bucket. Treat each pair of indices as an edge between two nodes. If a set of edges contains no two disjoint pairs, they must form either a star (all sharing a single center node) or a triangle (three nodes forming three edges: $$$(a,b), (b,c), (a,c)$$$). If our 3 stored pairs form a triangle, any new pair involving a 4th node can intersect at most 2 nodes of the triangle. It must be disjoint from the 3rd stored pair! If our 3 stored pairs form a star, any new pair that doesn't share the center node can intersect at most 2 of the star's "leaves". Again, it must be disjoint from the 3rd stored pair!

Thus, storing 3 pairs is sufficient.

Solution

We can drastically reduce the search space. Read the array but discard everything after the first 64 elements. Enumerate all pairs $$$(i, j)$$$ in this reduced array.

For each pair, calculate $$$pc = \text{popcount}(a_i \oplus a_j)$$$ and check if any previously stored pair in groups[pc] is disjoint from $$$(i,j)$$$. * If a disjoint pair is found, output the four indices and stop. * If not, store $$$(i, j)$$$ in groups[pc] (up to a maximum of 3 pairs).

Complexity: The number of examined pairs is at most $$$\binom{64}{2} \le 2016$$$. Checking stored pairs takes $$$O(1)$$$. Thus, time and memory complexity per test case is $$$O(1)$$$.

Every vertex in a functional graph has exactly one outgoing edge. This strict property guarantees that the graph is composed of one or more directed cycles, with directed trees feeding into those cycles.

Let's define the distance $$$d[u]$$$ for each vertex $$$u$$$: * If $$$u$$$ is part of a cycle, $$$d[u] = 0$$$. * If $$$u$$$ is in a tree, $$$d[u]$$$ is the number of edges it takes to reach the nearerst cycle.

A valid move from any vertex $$$u$$$ at distance $$$d$$$ will always move tokens to a vertex at distance $$$d-1$$$. The only exception is making a move from the cycle ($$$d = 0$$$): the Ghost Rule states that these tokens disappear.

Raw Intuition: The Mirroring Strategy Imagine you move $$$k$$$ tokens from a vertex at $$$d=1$$$ to $$$d=0$$$. Because the tokens are now on the cycle ($$$d=0$$$), your opponent's very next move can be to push those exact same $$$k$$$ tokens along the cycle, causing them to disappear completely. Your move achieved absolutely nothing toward winning the game; the opponent just canceled it out.

This logic cascades. If you move tokens from an odd distance to an even distance, the opponent can immediately push them to the next odd distance, restoring the balance. Because of this mirroring strategy, tokens on odd distances are completely useless to the current player.

Grundy Numbers & Proof of Correctness: Let's formalize this intuition using Grundy numbers (Nim-values). We treat every vertex as an independent game pile. * Claim: The Grundy value of a vertex $$$u$$$ with an odd distance $$$d[u]$$$ is strictly $$$0$$$ (it is a "dummy" pile). The Grundy value of a vertex with an even distance $$$d[u]$$$ is exactly its token count, $$$a_u$$$ (it acts as a real Nim pile).

Proof: By the Sprague-Grundy Theorem, the game's total state $$$X$$$ is the XOR sum of all independent games. Based on our claim:

If $$$X = 0$$$ (Losing State for Current Player): Any move the current player makes will leave a non-zero XOR sum for the opponent. * If they move $$$k$$$ tokens from an even distance to an odd distance, an active pile $$$a_u$$$ decreases, breaking the XOR balance. * If they move $$$k$$$ tokens from an odd distance to an even distance, the opponent uses the Mirroring Strategy: they immediately push those same $$$k$$$ tokens from the even distance to the next odd distance (or into the void). This entirely undoes the first player's move, perfectly restoring the even-distance XOR sum back to $$$0$$$.

If $$$X \neq 0$$$ (Winning State for Current Player): The current player can always force a win. By the standard rules of Nim, there will always be at least one valid move from an even distance to an odd distance (or the void) that perfectly balances the XOR sum $$$X$$$ back to $$$0$$$, forcing the opponent into the losing trap described above.

Implementation Details:

1. Use Topological Sorting to strip away the incoming trees. Any vertex left with an in-degree $$$ \gt 0$$$ after the queue is empty is part of a cycle.

2. Traverse backward from the cycle vertices to calculate $$$d[u]$$$ for all tree vertices. Compute the XOR sum of $$$a_u$$$ for all vertices where $$$d[u] \pmod 2=0$$$. If the sum $$$ \gt 0$$$, Alice wins. Otherwise, Bob wins.

• Time Complexity: $$$\mathcal{O}(N)$$$. Topo Sort and the distance calculation both require traversing the $$$N$$$ edges at most once.

The naive approach requires iterating over all $$$K^N$$$ possible transmissions, calculating $$$f(A)$$$, squaring it, and summing the results. This is computationally impossible.

Instead of evaluating each transmission individually, we can reframe the problem using double counting (often seen alongside linearity of expectation). The value $$$(f(A))^2$$$ represents the number of pairs of valid subsequences $$$(P, Q)$$$ in the transmission $$$A$$$ that both form the target pattern $$$B$$$. Therefore, summing $$$(f(A))^2$$$ over all transmissions is equivalent to asking:

"For every possible pair of subsequences $$$(P, Q)$$$ that form $$$B$$$, in how many valid transmissions $$$A$$$ can they coexist?"

The Intersection Property

Let the two subsequences be $$$P$$$ and $$$Q$$$. Both must form the sequence $$$1, 2, \dots, M$$$. If $$$P$$$ and $$$Q$$$ share an index in the transmission $$$A$$$, the value at that index must simultaneously satisfy the requirement for $$$P$$$ and the requirement for $$$Q$$$. * If $$$P$$$ needs the value $$$x$$$ at this index and $$$Q$$$ needs the value $$$y$$$, they can only share the index if $$$x = y$$$. * Because $$$B$$$ is strictly increasing ($$$1, 2, \dots, M$$$), all its elements are distinct. Therefore, $$$P$$$ and $$$Q$$$ can only intersect at the exact same relative position in $$$B$$$.

Let $$$c$$$ be the number of shared indices between $$$P$$$ and $$$Q$$$ ($$$0 \le c \le M$$$). If they share exactly $$$c$$$ indices, the total number of unique indices required in the transmission $$$A$$$ to form both $$$P$$$ and $$$Q$$$ is:

Constructing the Answer

For a fixed number of shared elements $$$c$$$, let's build the valid transmissions:

1. Choose the indices in $$$A$$$: We need $$$j$$$ unique positions in $$$A$$$ to place our interleaved sequences. We can choose these in $$$\binom{N}{j}$$$ ways.

2. Fill the remaining positions: There are $$$N - j$$$ unused indices in the transmission. These can be filled with any of the $$$K$$$ possible frequencies. This gives $$$K^{N - j}$$$ combinations.

3. Interleave the sequences ($$$W[c]$$$): We need to know how many valid ways there are to interleave the unshared elements of $$$P$$$ and $$$Q$$$ such that their relative orders are maintained, and they intersect exactly $$$c$$$ times. Let's call this weight $$$W[c]$$$.

The total sum of squared resonances is simply the sum over all possible overlap counts $$$c$$$:

Calculating the Interleaving Weight $$$W[c]$$$

The number of valid interleavings $$$W[c]$$$ depends on the parity of $$$c$$$ and can be derived from path-counting on a grid (similar to Catalan numbers).

Using $$$k = \lfloor \frac{c}{2} \rfloor$$$, the formulas simplify to the ones used in the optimized solution:

If $$$c$$$ is even:

If $$$c$$$ is odd:

By precomputing factorials and modular inverses up to $$$2M$$$, we can calculate $$$W[c]$$$ in $$$\mathcal{O}(1)$$$ time inside the loop.

Complexity Analysis: * Time Complexity: $$$\mathcal{O}(M)$$$ per testcase. Precomputing the factorials takes $$$\mathcal{O}(\max(M))$$$ globally. Inside each test case, the loop runs exactly $$$M+1$$$ times, doing constant-time modular arithmetic. * Space Complexity: $$$\mathcal{O}(M)$$$.

Solution Idea: Let $$$f(x)$$$ be the sum of passenger loads $$$A_i$$$ in the subtree of $$$x$$$. If we split the tree and connect a vertex $$$u$$$ to some vertex $$$v$$$, then $$$u$$$ should be connected directly to $$$1$$$ to minimize distances. Instead of guessing the cut, let us fix $$$u$$$ as the newly connected vertex and find the optimal ancestor edge to remove. To minimize distances for nodes on the newly formed cycle, the cut should be exactly halfway between $$$1$$$ and $$$u$$$.

Implementation: We can solve this using two depth-first searches. The first search computes $$$dist(1, x)$$$, parent nodes, subtree sums $$$f(x)$$$, and the initial total delay. The second search computes $$$ans[u]$$$, the minimum delay if we connect $$$u$$$ directly to $$$1$$$.

To find the optimal break node efficiently, we can maintain a list of active ancestors during our DFS. The optimal break node for $$$u$$$ is either its parent's break node or one step further down the path. Because the break node strictly shifts downwards as we go deeper, we can find the new break node in O(1) amortized time simply by checking the next node in our ancestor list.

When moving the connection from $$$p$$$ (parent of $$$u$$$) to $$$u$$$, the network delay changes in two specific ways: 1. Nodes inside the subtree of $$$u$$$ get 1 step closer to the Central Terminal, decreasing the total delay by $$$f(u)$$$. 2. Nodes in the detached component outside of $$$u$$$ (which corresponds exactly to the subtree of the break node minus the subtree of $$$u$$$) must now travel upwards through $$$u$$$ instead of $$$p$$$, meaning they take 1 step further. This increases the delay by $$$f(break) - f(u)$$$.

This gives us the following O(1) transition:

The minimum $$$ans[u]$$$ across all nodes is the final answer.

We want to construct the lexicographically smallest sequence where every contiguous subsegment has a strictly unique maximum element (a single peak).

To make the sequence lexicographically smallest, we must place the smallest possible number, $$$1$$$, as early and as often as possible. However, we cannot place two 1s adjacent to each other (the subsegment [1, 1] would have no unique peak). To pack the maximum number of 1s safely, we must place them at every alternating position starting from the first index: 1, _, 1, _, 1, _, 1...

Now, consider the empty spots. If we temporarily ignore all the $$$1$$$s, the remaining sequence of empty spots must also satisfy the exact same unique-peak property for all of its subsegments! To keep the sequence lexicographically smallest, this remaining sequence should be built using the exact same greedy alternating strategy, but using the number $$$2$$$. Filling half of the remaining empty spots gives: 1, 2, 1, _, 1, 2, 1, _, 1, 2, 1...

If we repeat this logic recursively for $$$3, 4, \dots$$$, we generate a famous fractal sequence often referred to as the Ruler Function.

More formally, we can define the sequence blocks recursively:

• $$$S_1 = [1]$$$
• $$$S_k = S_{k-1} + [k] + S_{k-1}$$$

Because of this recursive structure, any segment containing a number $$$x$$$ will encapsulate at least one instance of $$$x+1$$$, and hence no subsegment can have duplicate maximums with value $$$x$$$.

The answer for a given $$$n$$$ is simply the initial $$$n$$$ terms in the least $$$k$$$ such that $$$|S_k| \ge n$$$, which can be computed in $$$O(n)$$$ using the observation that $$$a_i$$$ is $$$1$$$ more than the highest power of $$$2$$$ dividing $$$i$$$ ($$$1$$$-indexed).

The problem requires us to assign unique labels from $$$0$$$ to $$$n-1$$$ to the vertices of a tree such that for every integer $$$k$$$, there exists a connected component with a minimum excluded value (mex) of exactly $$$k$$$.

For a connected component to have a mex of $$$k$$$, it must contain all labels strictly less than $$$k$$$, and it must not contain $$$k$$$ itself. Because this condition must hold sequentially for all possible values of $$$k$$$, the set of vertices labeled $$$0$$$ through $$$k-1$$$ must always form a valid, connected subgraph.

Assuming we fix the position of the label $$$0$$$ at a specific vertex $$$r$$$, we can treat this problem as a DP formulation. Let $$$f(u)$$$ be the number of ways to validly label the subtree rooted at $$$u$$$ using a set of relative labels $$${0,1,…,size(u)−1}$$$, where $$$u$$$ must receive the smallest label $$$0$$$ to maintain connectivity with its parent, and the remaining $$$size(u)−1$$$ labels must be distributed among the subtrees of its children. Suppose vertex $$$u$$$ has children $$$v_1, v_2, ..., v_m$$$. The number of ways to partition these labels into sets of sizes $$$size(v_1),...,size(v_m)$$$ is given by the multinomial coefficient

Further, for each child $$$v_i$$$, there are $$$f(v_i)$$$ ways to internally label its subtree. Combining these, the recurrence relation is

Expanding this recursively, we get

Since the label $$$0$$$ could theoretically be assigned to any vertex, we must calculate this value for all possible root positions and sum the results. We can apply a Rerooting DP technique for this, by calculating the answer for an initial, arbitrary root and then conceptually shift the root to an adjacent vertex.

When the root moves across a single edge from a node $$$u$$$ to its adjacent node $$$v$$$, only two subtree sizes are modified: $$$u$$$ and $$$v$$$. This allows us to instantly update the number of valid labelings quickly:

This shifting allows us to accumulate the total number of valid label configurations in $$$\mathcal{O}(n)$$$ or $$$\mathcal{O}(n \cdot log(MOD))$$$ time.