Note that if $$$min(n, x+1) < k$$$, then the answer is $$$-1$$$.

Otherwise, there are two cases:

• If $$$k=x$$$, then the suitable array looks like $$$[0, 1, 2, \dots, k-1, \dots, k-1]$$$.

• If $$$k \ne x$$$, then the suitable array looks like $$$[0, 1, 2, \dots, k-1, x, \dots, x]$$$.

In both cases, we can construct the array and calculate its sum in linear time. The overall complexity is $$$O(n \cdot t)$$$.

Note that after performing the operation on $$$b_j$$$, which has some bit set to 1, this bit will become 1 for all numbers in $$$a$$$ (and will remain so, as a bit cannot change from 1 to 0 in the result of an OR operation). If $$$n$$$ is even, then in the final XOR, this bit will become 0, as it will be equal to the XOR of an even number of ones. If $$$n$$$ is odd, then this bit will be 1 in the final XOR.

Therefore, if $$$n$$$ is even, by performing the operation on $$$b_j$$$, we set all the bits that are 1 in $$$b_j$$$ to 0 in the final XOR. If $$$n$$$ is odd, we do the opposite and set these bits to 1. So, if $$$n$$$ is even, the XOR does not increase when applying the operation, which means that to obtain the minimum possible XOR, we need to apply the operation to all the numbers in $$$b$$$, and the maximum XOR will be the original XOR. For odd $$$n$$$, it is the opposite: the minimum is the original XOR, and the maximum is obtained after applying the operation to all elements in $$$b$$$.

To apply the operation to all elements in $$$b$$$, it is sufficient to calculate their bitwise OR and apply the operation to the array $$$a$$$ with it.

Let's fix the color $$$x$$$ for which we will calculate the answer. If there is no $$$a_i = x$$$, then there will be no cells of color $$$x$$$, and the answer is $$$0$$$. Otherwise, there is at least one cell of color $$$x$$$.

To find the minimum rectangle containing all cells of this color, we need to find the topmost, bottommost, leftmost, and rightmost cells of this color in the array $$$b$$$. Let's find the prefix in $$$a$$$ of the maximum length, where all numbers are strictly less than $$$x$$$. Let the length of this prefix be $$$L$$$. Then in the first $$$L$$$ rows and columns of the array $$$b$$$, there will be no cells of color $$$x$$$, because for all these cells, the formula $$$b_{i, j} = min(a_i, a_j)$$$ will have a number from the prefix, and all numbers on it are less than $$$x$$$. In the $$$L+1$$$-th row and $$$L+1$$$-th column, there will be cells of color $$$x$$$, because $$$a_{L+1} \geq x$$$. Thus, we have found the topmost and leftmost cells of color $$$x$$$. To find the bottom and right cells, we need to find the longest suffix where all numbers are less than $$$x$$$.

Now we need to learn how to quickly find prefixes and suffixes for all colors. Notice that the prefix for color $$$x$$$ is not shorter than the prefix for color $$$x + 1$$$, so all prefixes can be calculated in just one pass through the array, similarly for suffixes.

Note that if there is a prefix for which there is a longer prefix that costs less, then it is useless to buy the shorter prefix. All its purchases can be replaced with purchases of the longer prefix, and the answer will only improve. Therefore, we can replace each $$$c_i$$$ with the minimum $$$c_j$$$ among $$$i \leq j \leq n$$$ (the minimum price of a prefix of length at least $$$i$$$). After this, we will have $$$c_i \leq c_{i+1}$$$.

Now let's solve the problem greedily. We want to maximize the first element of the resulting array. It will be equal to $$$k / c_1$$$, since we cannot buy more prefixes of length $$$1$$$ ($$$c_1$$$ is the smallest price). After buying $$$k / c_1$$$ prefixes of length $$$1$$$, we will have some coins left. Now we can replace some purchases of $$$c_1$$$ with purchases of longer prefixes to improve the answer.

How much will it cost to replace $$$c_1$$$ with $$$c_i$$$? It will cost $$$c_i - c_1$$$ coins. Moreover, note that to replace $$$c_1$$$ with $$$c_i$$$, we can sequentially replace $$$c_1$$$ with $$$c_2$$$, $$$c_2$$$ with $$$c_3$$$, $$$\ldots$$$, $$$c_{i-1}$$$ with $$$c_i$$$ (since $$$c_1 \leq c_2 \leq \ldots \leq c_i$$$). This means that we can make only replacements of purchases of $$$c_{i-1}$$$ with purchases of $$$c_i$$$.

Let's say we have maximized the first $$$i-1$$$ elements of the answer, and we have $$$x$$$ coins left. Now we want to replace some purchases of $$$c_{i-1}$$$ with $$$c_i$$$. How many replacements can we make? We can afford to make no more than $$$\frac{x}{c_i - c_{i-1}}$$$ replacements (if $$$c_{i-1} = c_i$$$, then we can replace all $$$c_{i-1}$$$), and we cannot replace more purchases than we have made, so no more than $$$a_{i-1}$$$ replacements (this is the number of purchases of $$$c_{i-1}$$$). Therefore, $$$a_i = \min(a_{i-1}, \frac{x}{c_i - c_{i-1}})$$$, as we want to maximize $$$a_i$$$. Finally, subtract the cost of replacements from the number of coins and move on to $$$c_{i+1}$$$.

Let's solve the problem using dynamic programming, let's store $$$dp[i][j]$$$ such that $$$dp[i][j]=1$$$ if it is possible to obtain an $$$XOR$$$ of $$$MEX$$$ values from the prefix up to $$$i$$$ (excluding $$$i$$$) equal to $$$j$$$, and $$$0$$$ otherwise. Notice that the answer cannot be greater than $$$n$$$. Therefore, the size of this two-dimensional array is $$$O(n^2)$$$.

Let's learn how to solve this in $$$O(n^3)$$$:

We iterate over $$$l$$$ from $$$1$$$ to $$$n$$$, and inside that, we iterate over $$$r$$$ from $$$l$$$ to $$$n$$$, maintaining the value $$$x=MEX([a_l, a_{l+1}, \dots, a_r])$$$. Then, for all $$$j$$$ from $$$0$$$ to $$$n$$$, we update $$$dp[r+1][j \oplus x]=1$$$ if $$$dp[l][j]=1$$$. This way, we update based on the case when the resulting set includes the set $$$[a_l, a_{l+1}, \dots, a_r]$$$.

We also need to update if $$$dp[l][x]=1$$$, we assign $$$dp[l+1][x]=1$$$. This accounts for the case when we do not include $$$a_l$$$ in the answer.

Let's define $$$MEX(l, r) = MEX([a_l, a_{l+1}, \dots, a_r])$$$, this will make the following text clearer.

Let's consider the segment $$$l, r$$$. Notice that if there exist $$$l_2$$$ and $$$r_2$$$ ($$$l \leq l_2 \leq r_2 \leq r$$$) such that $$$l_2 \ne l$$$ or $$$r_2 \ne r$$$ and $$$MEX(l, r)=MEX(l_2, r_2)$$$, then we can take the segment $$$l_2, r_2$$$ instead of the segment $$$l, r$$$ in the set of $$$MEX$$$ values, and the answer will remain the same. If, however, there is no such segment $$$l_2, r_2$$$ for the segment $$$l, r$$$, then we call this segment $$$l, r$$$ irreplaceable.

Now let's prove that there are no more than $$$n \cdot 2$$$ irreplaceable segments. For each irreplaceable segment, let's look at the larger element of the pair $$$a_l, a_r$$$, let's assume $$$a_l$$$ is larger (the other case is symmetric). Now, let's prove that there is at most one segment where $$$a_l$$$ is the left element and $$$a_l \geq a_r$$$, by contradiction:

Suppose there are at least 2 such segments, let's call their right boundaries $$$r_1, r_2$$$ ($$$r_1 < r_2$$$). Notice that $$$MEX(l, r_1) > a_l$$$, otherwise the segment $$$l, r_1$$$ would not be irreplaceable (we could remove $$$a_l$$$). Since $$$a_l \geq a_{r_2}$$$, then $$$MEX(l, r_1) > a_{r_2}$$$. It is obvious that $$$a_{r_2}$$$ appears among the elements $$$[a_l, \dots, a_{r_1}]$$$, and therefore $$$MEX(l, r_2-1) = MEX(l, r_2)$$$, which means that the segment $$$l, r_2$$$ is not irreplaceable, contradiction.

For each $$$a_i$$$, there is at most one irreplaceable segment where it is the smaller of the two extremes, and at most one where it is the larger. Therefore, the total number of irreplaceable segments is no more than $$$2 \cdot n$$$.

Let's update the DP only through the irreplaceable segments, then the solution works in $$$O(n^2+n \cdot C)$$$ time, where $$$C$$$ is the number of irreplaceable segments. However, we have already proven that $$$C\leq 2n$$$, so the overall time complexity is $$$O(n^2)$$$.

Let's store all the number entries in a trie. Consider two traversals of this trie — depth-first search (DFS) and breadth-first search (BFS). In both traversals, we go to the children of a node in ascending order of the number on the edge (in the trie). Let the index of the node representing the number $$$x$$$ in the DFS traversal be $$$dfs(x)$$$, and in the BFS traversal be $$$bfs(x)$$$. Then notice that $$$x = bfs(x)$$$, as in BFS on the trie, we simply look at all the number entries with a certain length in order (lengths are concidered in increasing order). On the other hand, $$$dfs(x)$$$ is the index of the number entry $$$x$$$ in the sorted array. Therefore, we want to calculate the number of $$$x$$$ for which $$$dfs(x) = bfs(x)$$$.

Let's fix a layer in the trie, meaning we only consider numbers with a fixed, equal length of representation. Then let's look at $$$dfs(x) - bfs(x)$$$ for the numbers in this layer. Notice that for two numbers $$$y$$$ and $$$y + 1$$$ in this layer, it holds that $$$bfs(y + 1) - bfs(y) = 1$$$, and $$$dfs(y + 1) - dfs(y) \geq 1$$$. This means that for a fixed layer, the function $$$dfs(x) - bfs(x)$$$ is non-decreasing. Therefore, we can find the $$$0$$$ of this function using binary search on each layer.

Now let's learn how to calculate $$$dfs(x) - bfs(x)$$$. $$$bfs(x) = x$$$, which we can calculate. To find $$$dfs(x)$$$, we can traverse up from the trie node corresponding to $$$x$$$, and at each step, add the sizes of the subtrees that we have traversed in DFS before the subtree with the node $$$x$$$.

The trie has a depth of $$$O(\log(n))$$$, binary search takes the same time, so the overall asymptotic complexity of the solution is $$$O(\log^3(n))$$$.

I apologize for the issues some participants faced with the time limit, if they implemented the author's idea suboptimally.

Let's start by introducing a more convenient way to store numbers — an array $$$cnt$$$, where $$$cnt[x]$$$ represents the number of occurrences of $$$x$$$ in the prefix for which we are finding the answer. All $$$x$$$ such that $$$x > n$$$ will be added to $$$cnt[0]$$$ because applying the operation to $$${x}$$$ in such cases is optimal.

Let's introduce a few array operations that will be sufficient to solve the problem.

• Create the number $$$x$$$. Apply the operation to the set of numbers $$${0, 1, 2, \dots, x-1}$$$. In terms of the array $$$cnt$$$, this is equivalent to subtracting $$$1$$$ from the range $$$0$$$ to $$$x-1$$$ and adding $$$1$$$ to $$$cnt[x]$$$.

• Turn the number $$$x$$$ into $$$0$$$. To do this, apply the operation to $$${x}$$$. In terms of the array $$$cnt$$$, this is equivalent to subtracting $$$1$$$ from $$$cnt[x]$$$ and adding $$$1$$$ to $$$cnt[0]$$$.

• Create the number $$$x$$$ and clear the multiset. This is the same as creating the number $$$x$$$, but we apply the operation to all other numbers, leaving only the single number $$$x$$$ (or a larger number) in the set.

It can be proven that by using only operations of this kind, we can always obtain the optimal answer.

Now we can forget about the original condition and solve the problem for the array.

Let's learn how to check if it is possible to create the number $$$k$$$ and clear the multiset:

First, let's try to create the number $$$k$$$. If it is possible, the answer is yes. Otherwise, we look at the rightmost number that is missing (or in other words, the rightmost $$$0$$$). We try to create it, and now we need to find the rightmost element $$$\leq 1$$$ to the left of it, and so on. To implement this, we need to maintain a number $$$p$$$ such that we subtract $$$p$$$ from all elements in the prefix (initially $$$p=1$$$), iterate through the array from right to left, and if $$$cnt[i]<p$$$, assign $$$p \mathrel{{+}{=}} (p-cnt[i])$$$. When we reach zero, $$$p$$$ may be greater than $$$cnt[0]$$$, in which case we need to use the operation to turn any number into $$$0$$$. To do this, simply check that the remaining number of elements in the array is greater than or equal to $$$p$$$.

This currently works in $$$O(k)$$$ time, which is not very efficient.

Optimization techniques:

First, let's maintain the sum of elements $$$sm$$$ and as soon as it becomes negative, terminate the process. To achieve this, when subtracting $$$p-cnt[i]$$$ from $$$p$$$, let's subtract $$$(p-cnt[i])\cdot(i-1)$$$ from $$$sm$$$. Now let's use a bottom-up segment tree to find the nearest number smaller than $$$p$$$ to the left in $$$O(\log(i))$$$ time.

Now let's notice that when we update through $$$cnt[i]$$$, we subtract at least $$$i-1$$$ from $$$sm$$$, so there can't be more than $$$O(\sqrt{n})$$$ different values of $$$i$$$ through which we will update.

Now we can answer for a specific $$$k$$$ in $$$O(\sqrt{n} \cdot \log(n))$$$ time, but in reality, the complexity is $$$O(\sqrt{n})$$$ (due to the peculiarities of the bottom-up segment tree), and the authors have a proof for this, but they are afraid that you will find an error in it, so they decided not to provide it(we will add proof later).

Now let's see how to solve the full problem:

Initially, the answer is $$$0$$$, and we notice that it does not decrease. So after each addition, we will check if it is possible to increase the answer and increase it as long as possible. The answer cannot exceed $$$n$$$, so we will perform no more than $$$2 \cdot n$$$ checks.

Overall, the solution works in $$$O(n \cdot \sqrt{n})$$$ time. That's how it is.

Let's consider that in our query, the segment tree processed $$$k$$$ nodes $$$[x_1, x_2, \dots, x_k]$$$ from the bottom.

Then, the number of operations is the sum of $$$dist(x_i, x_{i+1})$$$ for $$$i$$$ from 1 to $$$k-1$$$, and $$$dist(0, x_1)$$$, where $$$dist$$$ represents the length of the path between nodes in the segment tree. Now, let's notice that for the query $$$dist(a, b)$$$, we enter the segment tree node responsible for a block of length $$$2^t$$$ only if $$$a$$$ and $$$b$$$ are in different blocks of length $$$2^{t-1}$$$, which is logical. Also, let's notice that this doesn't happen very often, specifically, the numbers $$$[x_1, x_2, \dots, x_k]$$$ can be part of a maximum of $$$\sqrt{\frac{n}{2^t}}$$$ blocks of length $$$2^t$$$ (asymptotically). Therefore, the sum of all queries is asymptotically equal to the sum of $$$\sqrt{\frac{n}{2^t}}$$$ for $$$t$$$ from 0 to 20, which is a geometric progression with a ratio of $$$\frac{1}{\sqrt{2}}$$$. Hence, the sum is asymptotically equal to $$$\sqrt{n}$$$. Proof completed.

Let's unfold all the edges, now we need to ensure that all regular vertices are reachable from the selected vertices.

First, you should familiarize yourself with the algorithm for finding the ordered minimum spanning tree, also known as the Edmonds' algorithm (I will refer to his work here and without knowledge of it, the solution cannot be understood). Next, it is worth noting that the compressions in the process of this algorithm (almost) do not depend on the root, and all compressions can be performed as if there is no root (previously creating dummy edges from $$$i$$$ to $$$i+1$$$ for $$$i$$$ from $$$1$$$ to $$$n-1$$$ and from vertex $$$n$$$ to vertex $$$1$$$ with a cost of $$$n * max(a_i)+1$$$). Then, after all the compressions, only one vertex will remain. Note that the difference from Edmonds' algorithm is that if at any step of the algorithm the minimum edge from a vertex leads to the root, compression is not necessary.

So, let's maintain a tree in which each vertex corresponds to its corresponding compressed vertex or to the original vertex, and the children of vertex $$$v$$$ are all the vertices that we compressed to obtain vertex $$$v$$$. It is implied that with each compression, we create a new vertex.

Let's call the cost of vertex $$$v$$$ the minimum cost of an edge leaving vertex $$$v$$$ in the process of Edmonds' algorithm (taking into account changes in edge costs during compression in Edmonds' algorithm).

Then we need to maintain the sum of the costs of the vertices in the tree, in the subtrees of which there are no selected vertices (where the selected vertices can only be leaves). This can be easily done using a segment tree.

You can choose one best problem, or not choose if you think there is no such task.

Try to look at the parity of $$$n, m$$$.

The player who wins does not depend on player's strategy.

The only thing that the winning player depends on is the parity of $$$n, m$$$.

Note that the game will end only when the chip is in the upper right corner (otherwise you can move it $$$1$$$ square to the right or up). For all moves, the chip will move $$$n - 1$$$ to the right and $$$m - 1$$$ up, which means that the total length of all moves is $$$n + m - 2$$$ (the length of the move is how much the chip moved per turn). Since the length of any move is odd, then after any move of Burenka, the sum of the lengths will be odd, and after any move of Tonya is even. So we can find out who made the last move in the game by looking at $$$(n + m - 2) \operatorname{mod} 2 = (n + m) \operatorname{mod} 2$$$. With $$$(n + m) \operatorname{mod} 2 = 0$$$, Tonya wins, otherwise Burenka.

The complexity of the solution is $$$O(1)$$$.

Instead of $$$k$$$, we can consider the remainder of dividing $$$k$$$ by 4.

There is no answer for the remainder 0.

For all other remainders, there is an answer.

Note that from the number $$$k$$$ we only need the remainder modulo $$$4$$$, so we take $$$k$$$ modulo and assume that $$$0 \leq k \leq 3$$$.

If $$$k = 0$$$, then there is no answer, because the product of the numbers in each pair must be divisible by $$$4 = 2^2$$$, that is, the product of all numbers from $$$1$$$ to $$$n$$$ must be divisible by $$$2^{\frac{n}{2} \cdot 2} = 2^n$$$, but the degree of occurrence of $$$2$$$ in this sum is $$$\lfloor\frac{n}{2}\rfloor +\lfloor\frac{n}{4}\rfloor$$$, which is less than $$$n$$$.

If $$$k = 1$$$ or $$$k = 3$$$, then we will make all pairs of the form $$$(i, i + 1)$$$, where $$$i$$$ is odd. Then $$$a + k$$$ will be even in each pair, since $$$a$$$ and $$$k$$$ are odd, and since $$$b$$$ is also even, the product will be divisible by $$$4$$$. Если $$$k = 2$$$, then we will do the same splitting into pairs, but in all pairs where $$$i + 1$$$ is not divisible by $$$4$$$, we will swap the numbers (that is, we will make $$$a = i + 1$$$ and $$$b = i$$$). Then in pairs where $$$i + 1 \operatorname{mod} 4 = 0$$$, $$$b$$$ is divisible by $$$4$$$ (therefore the product too), and in the rest $$$a + k$$$ is divisible by $$$4$$$ (since $$$a$$$ and $$$k$$$ have a remainder $$$2$$$ modulo $$$4$$$).

The complexity of the solution is $$$O(n)$$$.

Who would win duels if the strongest athlete was the first in queue?

After what number of rounds is the strongest athlete guaranteed to be at the front of the queue?

Simulate the first $$$n$$$ rounds and write down their winners so that for each person you can quickly find out the number of wins in rounds with numbers no more than a given number.

Note that after the strongest athlete is at the beginning of the queue, only he will win. The strongest athlete will be at the beginning of the queue no more than after the $$$n$$$-th round. Let's simulate the first $$$n$$$ rounds, if the $$$j$$$-th athlete won in the $$$i$$$-th round, then we will write down the $$$i$$$ number for him. Now, to answer the query $$$(i, k)$$$, it is enough to find the number of wins of the $$$i$$$ athlete in rounds with numbers $$$j \leq k$$$, and if $$$k > n$$$, and the strength of the $$$i$$$ athlete is equal to $$$n$$$, then add to the answer another $$$k - n$$$.

The complexity of the solution is $$$O(n + q \operatorname{log}(n))$$$.

Segments of length greater than 2 are not needed.

For A1 you can use dynamic programming

Dynamic programming where dp[i][v] means the minimum time to make $$$a_j = 0$$$ for $$$j < i$$$ and $$$a_i = v$$$. (Notice that v can be any number from 0 to 8191)

There is an answer in which segments of length $$$2$$$ does not intersect with segments of length $$$1$$$.

If $$$a_l\oplus a_{l + 1} \oplus \ldots \oplus a_{r} = 0$$$ is executed for $$$l, r$$$, then we can fill this segment with zeros in $$$r-l$$$ seconds using only segments of length 2.

There is an answer where the time spent is minimal and the lengths of all the segments taken are 1 and 2. because of the segment $$$l, r, x$$$ can be replaced to $$$\lceil\frac{r-l+1}{2}\rceil$$$ of segments of length 2 and 1, or rather $$$[l, l + 1, x], [l+ 2, l + 3, x], \ldots, [r, r, x]$$$(or $$$[r-1, r, x]$$$ if $$$(l - r + 1)$$$ even).

Note that if $$$a_l\oplus a_{l + 1} \oplus \ldots \oplus a_{r} = 0$$$ is executed for $$$l, r$$$, then we can fill the $$$l, r$$$ subsections with zeros for $$$r-l$$$ seconds with queries $$$[l, l+1, a_l], [l+1, l+2, a_l \oplus a_{l+1}], ... [r-1, r, a_l\oplus a_{l+1} \oplus \ldots \oplus a_r]$$$.

Note that if a segment of length 2 intersects with a segment of length 1, they can be changed to 2 segments of length 1.

It follows from all this that the answer consists of segments of length 1 and cover with segments of length 2. Then it is easy to see that the answer is ($$$n$$$ minus (the maximum number of disjoint sub-segments with a xor of 0)), because in every sub-segments with a xor of 0 we can spend 1 second less as I waited before. this amount can be calculated by dynamic programming or greedily. Our solution goes greedy with a set and if it finds two equal prefix xors($$$prefix_l = prefix_r$$$ means that $$$a_{l + 1} \oplus a_{l+2} \oplus \ldots \oplus a_{r} = 0$$$), it clears the set. 168724728

The complexity of the solution is $$$O(n \operatorname{log}(n))$$$.

Try to express $$$n$$$(the sum of all $$$c_i$$$) as $$$F_1 + F_2 + \ldots + F_m = n$$$.

At the beginning, let's check that the number $$$n$$$ (the sum of all $$$c_i$$$) is representable as the sum of some prefix of Fibonacci numbers, otherwise we will output the answer NO.

Let's try to type the answer greedily, going from large Fibonacci numbers to smaller ones. For the next Fibonacci number, let's take the letter with the largest number of occurrences in the string from among those that are not equal to the previous letter taken (to avoid the appearance of two adjacent blocks from the same letter, which cannot be). If there are fewer occurrences of this letter than this number, then the answer is NO. Otherwise, we will put the letter on this Fibonacci number and subtract it from the number of occurrences of this letter.If we were able to dial all the Fibonacci numbers, then the answer is YES.

Why does the greedy solution work? Suppose at this step you need to take $$$F_i$$$ (I will say take a number from $$$c_t$$$, this will mean taking $$$F_i$$$ letters $$$t$$$ from string), let's look at the maximum $$$c_x$$$ now, if it cannot be represented as the sum of Fibonacci numbers up to $$$F_i$$$ among which there are no neighbors, then the answer is no. It can be proved that if $$$c_x > F_{i+1}$$$, then it is impossible to represent $$$c_x$$$.

If there is exactly one number greater than or equal to $$$F_i$$$ at the step, then there is only one option to take a number, so the greedy solution works.

If there are two such numbers and they are equal, then the option to take a number is exactly one, up to the permutation of letters. the greedy solution works again.

If there are $$$c_j \geq F_i, c_x \geq F_i, j \ne x$$$, then we note that the larger of the numbers $$$c_j, c_x$$$ will be greater than $$$F_i$$$, if we don't take it, then at the next step this number will be greater than $$$F_{i+1}$$$ ($$$i$$$ will be 1 less), according to the above proven answer will not be, so, taking the larger of the numbers is always optimal.

The complexity of the solution is $$$O(k \operatorname{log}(n)\operatorname{log}(k))$$$.

The answer for $$$k=x$$$ and $$$k=\gcd(x,n)$$$ is the same.

In this problem, a general statement is useful: for any array $$$c$$$ of length $$$m$$$, $$$m\cdot\operatorname{max}(c_1, c_2, \ldots, c_m) \geq c_1 +c_2 +\ldots+c_m$$$ is true.

Try applying the second hint for $$$k_1$$$ and $$$k_2$$$ divisible by $$$k_1$$$, where $$$k_1, k_2$$$ are divisors of $$$n$$$.

We can consider only $$$k$$$ which equals to $$$\frac{n}{p}$$$, where $$$p$$$ is a simple divisor of $$$n$$$.

Let's note that the answer for $$$k=x$$$ and $$$k=\gcd(x,n)$$$ is the same.

Indeed, for the number $$$k$$$, we will visit numbers with indices $$$s + ik \mod n$$$ for $$$i$$$ from $$$0$$$ to $$$n-1$$$ inclusive, from this we can see that the index of the $$$i$$$-th number coincides with the index of $$$i + \frac{n}{\gcd(k,n)}$$$, and if we look at two indexes, the difference between which is $$$l$$$ and $$$l<\frac{n}{\gcd(k,n)}$$$, then they are different, since $$$k\cdot l \mod n \neq 0$$$, therefore, the answer is (the sum of numbers with indices $$$s + ik \mod n$$$ for $$$i$$$ from $$$0$$$ to $$$\frac{n}{\gcd(k,n)}-1$$$) $$$\cdot\gcd(k,n)$$$.

Now let's prove that the first $$$\gcd(k,n)$$$ numbers are the same for $$$(s,x)$$$ and $$$(s,\gcd(x,n))$$$, note that only those indices that have the same remainder as $$$s$$$ when divided by $$$\gcd(x,n)$$$ are suitable, but there are only $$$\frac{n}{\gcd(k,n)}$$$ of such indices, and we proved that we should have $$$\frac{n}{\gcd(k,n)}$$$ of different indices, so they are all represented once, therefore the answer for $$$k=x$$$ and $$$k=\gcd(x, n)$$$ is the same, because the sum consists of the same numbers.

So, we need to consider only $$$k$$$ being divisors of $$$n$$$, this is already passes tests if we write, for example, a segment tree, but we don't want to write a segment tree, so we go further, prove that for $$$k_1 = x$$$, the answer is less or equal than for $$$k_2 = x \cdot y$$$ if $$$k_1$$$ and $$$k_2$$$ are divisors of $$$n$$$, why is this so?

Note that for the number $$$k$$$, the answer beats for $$$\gcd(k,n)$$$ groups of numbers, so that in each group there is exactly $$$\frac{n}{\gcd(k,n)}$$$ and each number is in exactly one group, and for different $$$s$$$ the answer will be (the sum in the group that $$$s$$$ belongs to) $$$\cdot\gcd(k,n)$$$.

Let's look at the answer for the optimal $$$s$$$ for $$$k_1$$$, let's call the set at which it is reached $$$t$$$, note that in $$$k_2$$$ for different $$$s$$$ there are $$$m$$$ independent sets that are subsets of $$$t$$$. Let $$$m_i$$$ be the sum in the $$$i$$$-th set. Now note that we need to prove $$$max(m_1, m_2, \ldots, m_y) * y\geq m_1 +m_2 +\ldots m_y$$$ this is true for any $$$m_i$$$, easy to see.

So you need to iterate the divisors which equals to $$$\frac{n}{p}$$$ where $$$p$$$ is prime, now it can be passed with a set. Hurray!

For the divisor $$$d$$$, it is proposed to store answers for all pairs $$$(s, d)$$$, where $$$s\le\frac{n}{d}$$$ and the maximum among them, they can be counted initially for $$$O(n log n)$$$ for one $$$d$$$, each request is changing one of the values, this can be done for $$$O(log n)$$$.

The complexity of the author's solution is $$$O(6\cdot n\operatorname{log}(n))$$$, where 6 is the maximum number of different prime divisors of the number $$$n$$$.

Try to reduce the task to a single array and tree.

Try to reduce the tree to a match of bipartite graph.

The first part: For each $$$a_i=0$$$, a segment of suitable values.

The second part: The set $$$S$$$ and the number $$$d$$$.

There exist $$$L$$$ and $$$R$$$ such that the answer to the query is ''YES'' if and only if $$$L \le d \le R$$$.

Let's build a tree recursively starting from the segment $$$[1, n]$$$, at each step we will choose the root of the subtree $$$v = \operatorname{argmax}([p_l, p_{l+1}\ldots, p_r]) +l - 1$$$, then recursively construct trees for subtrees $$$[l, v-1], [v+1, r]$$$ if they are not empty, then create edges from the root to the roots of these subtrees. What we got is called a Cartesian tree by array. This Cartesian tree will be mentioned further in the analysis.

It is easy to see that Cartesian trees by arrays coincide if and only if these arrays are similar. Then the necessary and sufficient condition for the array $$$a$$$ to be similar to $$$p$$$ is that for any pair $$$u, v$$$ such that $$$u$$$ is in the subtree $$$v$$$, $$$a_v > a_u$$$ is satisfied, in other words $$$a_v$$$ is the maximum among the numbers in the subtree of the vertex $$$v$$$.

Let's call the position $$$i$$$ initially empty if initially $$$a_i = 0$$$.

Let's call an array $$$a$$$ almost similar to $$$p$$$ if for any pair $$$u, v$$$ such that $$$u$$$ is in the subtree $$$v$$$, $$$a_v > a_u$$$ is executed, or both positions $$$u$$$, $$$v$$$ are initially empty.

Let's prove that if there is a way to fill in the gaps in $$$a$$$ to get an array almost similar to $$$p$$$, then there is also a way to fill in the gaps to get a similar to $$$p$$$ array $$$a$$$.

Indeed, let's look at the $$$a$$$ array almost similar to $$$p$$$. let's walk through the tree recursively starting from the root. At the step with the vertex $$$v$$$, we first start recursively from all the children of $$$v$$$, now it is true for them that the maxima of their subtrees are in them, let's look at the maximum child $$$v$$$, let it be $$$u$$$, then if $$$a_v > a_u$$$, then everything is fine, otherwise $$$a_v < a_u$$$ note that $$$v$$$ is initially an empty position, because for all initially non-empty positions it is true that they are maximums in their subtrees (this is easy to see in the definition), but $$$v$$$ is not. Note that $$$u$$$ is initially an empty position. Otherwise, we have never changed $$$a_v$$$ and $$$a_u$$$, therefore, in the original array $$$a$$$ almost similar to $$$p$$$, $$$a_v > a_u$$$ contradiction was executed, it is contradiction. so $$$v, u$$$ are initially empty, we can perform $$$swap(a_v, a_u)$$$ and everything will be executed.

After executing this algorithm, we changed only the initially empty elements and got $$$a$$$ similar to $$$p$$$. Q.E.D.

How to check the existence of an array almost similar to $$$p$$$? Let's call the number $$$r_i$$$ the minimum among all the numbers $$$a_v$$$ such that $$$i$$$ is in the subtree of $$$v$$$. Let's call the number $$$l_i$$$ the maximum among all the numbers $$$a_v$$$ such that $$$v$$$ is in the subtree of $$$i$$$. it is easy to see that $$$a$$$ is almost similar to $$$p$$$ if and only if for all $$$i$$$, $$$l_i < a_i < r_i$$$ is satisfied.

That sounds incredibly good. So, all we need is to find a matching of the set $$$S$$$ and number $$$d$$$ and segments $$$[l_i, r_i]$$$ for $$$i$$$ that are initially empty. Now it is easy to prove that the suitable $$$d$$$ is a continuous segment (let's say the answer is yes for $$$d_1$$$, we don't know the answer for $$$d_2$$$, try looking at the alternating path from $$$d_1$$$ to $$$d_2$$$ in good matching for $$$d_1$$$, it's easy to see that if there is such a path, then for $$$d_2$$$ the answer is yes, otherwise, no. If you look at the structure of the matching of points with segments, you can see that an alternating path exists for a continuous segment of values $$$d_2$$$). the boundaries can be found by binary search or by typing greedily twice.

Final complexity is $$$O(n \operatorname{log} n)$$$ or $$$O(n \operatorname{log}^2 n)$$$

you can notice that a pair of operations $$$1\, i\, j$$$, $$$2\, k\, t$$$ and $$$2\, k\, t$$$, $$$1\, i\, j$$$ lead to the same result, what does this mean?

This means that operations can be represented as two permutations describing which swaps will occur with rows and which swaps will occur with columns.

Try to reduce this problem to a graph isomorphism problem.

Let's have two permutations: $$$p$$$ of length $$$n$$$ and $$$q$$$ of length $$$m$$$. Initially, both permutations are identical. For operation $$$1\, i\, j$$$, we will execute $$$\operatorname{swap}(p_i, p_j)$$$, for operation $$$2\, i\, j$$$ we will execute $$$\operatorname{swap}(q_i, q_j)$$$. It is easy to see that after performing all operations in the position $$$i, j$$$ will be $$$a_{p_i,q_j}$$$.

Now we need to find permutations of $$$p, q$$$ so that $$$a_{p_i,q_j} = b_{i, j}$$$.

Let's look at a bipartite graph where the first part is rows and the second is columns. Let if $$$a_{i,j}\ne 0$$$, then from $$$i$$$ there is an undirected edge in $$$j$$$ of the color $$$a_{i, j}$$$. if we construct the same graph for $$$b$$$, then we need to check for isomorphism two bipartite graphs, each edge of which has a color, and as we remember, by the condition of the vertex, 2 edges of the same color cannot be Incidence. Let's call them graph $$$a$$$ and graph $$$b$$$.

This problem is largely for implementation, therefore, starting from this moment, the actions that you can observe in the author's solution are described 168728958.

Let $$$n < m$$$ otherwise let's swap $$$n$$$ and $$$m$$$ in places. Let's try to match the elements of the array $$$a$$$ to the elements of the array $$$b$$$. Let's go through the indices from $$$1$$$ to $$$n$$$. Let's now choose which pair of $$$b$$$ to choose for the $$$i$$$-th vertex of the first fraction of the graph $$$a$$$. If we have already found a pair earlier, skip the step, otherwise let's sort out the appropriate option for the pair among all the vertices of the first component $$$b$$$ that do not yet have a pair, there are no more than $$$n$$$, after the vertices are matched, the edges are also uniquely matched (because there are no 2 edges of different colors), let's then run the substitution recursively for edges (if we have mapped the vertex $$$v$$$ to the vertex $$$u$$$ and from $$$v$$$ there is an edge of color $$$x$$$ in $$$i$$$, and from $$$u$$$ there is an edge $$$x$$$ in $$$j$$$, then it is easy to prove that in the answer $$$i$$$ will be mapped to $$$j$$$), which means we will restore the entire component. Let the sum of the number of vertices and the number of edges in the component be $$$k$$$, then we will perform no more than $$$n \cdot k$$$ actions to restore the component.

by permutations, getting a sequence of swaps is a matter of technique, I will not explain it, but this is a separate function in the author's solution you will understand.

in total, our solution works for $$$O(n(n\cdot m + n + m))$$$ or $$$O(min(n, m)(n\cdot m + n + m))$$$, where $$$n\cdot m + n +m$$$ is the total number of vertices and edges in all components.

feel free to ask any questions

The only one hint to this problem is don't try to solve, it's not worth it.

In order to find the number of numbers from $$$1$$$ to $$$C$$$ that are mutually prime with $$$x$$$, we write out its prime divisors (various). Let these be prime numbers $$$a_{1}, a_{2}, \ldots, a_{k}$$$. Then you can find the answer for $$$2^{k}$$$ using the inclusion-exclusion formula.

Because $$$\left\lfloor\frac{a}{b\cdot c}\right\rfloor = \left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor$$$, a similar statement is made for $$$k$$$ numbers (you can divide completely in any order).

Let's split the primes up to $$$2\times 10^4$$$ into 2 classes — small ($$$\leq 42$$$) and large (the rest). There are 13 small numbers, and 2249 large ones. Separately, we will write down pairs of large numbers that in the product give a number not exceeding $$$10 ^ 5$$$. There will be 4904 such pairs.

Let's match each set of small primes with a mask. Let's write $$$dp[mask]$$$ — alternating sum over the $$$mask$$$ submasks of numbers $$$\left\lfloor\frac{C}{a_{1}\cdot a_{2}\cdot\ldots \cdot a_{k}} \right\rfloor$$$, where $$$a_{1}, \ldots, a_{k}$$$ — prime numbers from the submask. Similarly, we define $$$dp[mask][big]$$$ (in addition to the mask, there is a large prime $$$big$$$) and $$$dp[mask][case]$$$ (in addition to the mask, there are a pair of primes from a pair of large primes $$$case$$$). Each $$$dp$$$ can be counted for $$$states\times bits$$$, where $$$states$$$ — is the number of states in $$$dp$$$, and $$$bits$$$ — is the mask size (number of bits).

If we write out all the large primes on the segment for which $$$mask$$$ — mask of small primes, the answer for this segment will be the sum of $$$dp[mask] + \sum dp[mask][big_{i}] + \sum dp[mask][case_{i}]$$$ (for $$$big$$$ and $$$case$$$ lying on the segment). Thus, the request can be answered in 7000 calls to $$$dp$$$.

In order to find a set of prime numbers on a segment, you can use the MO algorithm.

Final complexity is $$$O(n\sqrt{n} + q\times(\pi(m)+casesCount(C)))$$$

It is worth noting that (with a very strong desire) it is possible to further optimize the solution using avx, to speed up the calculation of the amount by submasks in dynamics by 16 times, to speed up the calculation of the amount of $$$dp[mask][big]$$$ by 8 times, which will allow you to answer the request in ~5000 (instead of 7000) calls to $$$dp$$$, and the pre-calculation for $$$4\cdot 10^7$$$ instead of $$$7\cdot 10^8$$$ (in fact, the pre-calculation works much faster due to compiler optimizations).

You can choose one best problem, or not choose if you think there is no such task.