You are given a string $$$S$$$ of length $$$2n$$$, consisting of the characters A, B and C. Determine if $$$S$$$ can be split into $$$n$$$ non-intersecting subsequences, each of which forms one of the strings "AB", "AC", "BC". If it is possible, find such a splitting.

Let's call an array $$$[a_1, a_2, \ldots, a_k]$$$ of positive integers phenomenal, if the product of its elements is equal to the sum of its elements (i.e. if $$$a_1 a_2 \ldots a_k = a_1 + a_2 + \ldots + a_k$$$) .

For example, the array $$$[2, 2]$$$ is phenomenal, because $$$2\cdot 2 = 2+2 = 4$$$, and $$$[3, 1, 2]$$$ is phenomenal, because $$$3\cdot 1 \cdot 2 = 3 + 1 + 2 = 6$$$, but the array $$$[2, 3]$$$ is not phenomenal, as $$$2\cdot 3 \neq 2+3$$$.

Let $$$f(i)$$$ denote the number of phenomenal arrays of size $$$i$$$. It can be shown that for any fixed $$$i \ge 2$$$ there is only a finite number of phenomenal arrays of size $$$i$$$.

You are given an integer $$$n$$$. Find $$$f(2), f(3), \ldots, f(n)$$$. As these numbers can be very big, output them modulo $$$P$$$, where $$$P$$$ is a given prime number.

You are given integers $$$N, M$$$ with and a prime modulo $$$P$$$.

Consider all permutations of length $$$N \cdot M$$$ such that the length of their longest increasing subsequence equals $$$N$$$ and the length of their longest decreasing subsequence equals $$$M$$$.

Define $$$f(pos, val)$$$ for each $$$1 \le pos, val \le N \cdot M$$$ as the number of such permutations in which the $$$pos$$$-th element of the permutation equals to $$$val$$$.

Find $$$f(pos, val)$$$ for all $$$1 \le pos, val \le NM$$$, modulo $$$P$$$.

Given are two black and white $$$N \times M$$$ images $$$A$$$ and $$$B$$$.

The "flood fill" tool works as follows: you choose any cell $$$(x, y)$$$, locate its connected component and flip the colors of all the cells in the component (if the cell was black, it becomes white, and if it was white, it becomes black). The connected component of the cell is the set of cells you can reach by going up/down/left/right without changing color.

You can apply the "flood fill" tool to image $$$A$$$ any number of times. What is the minimum number of cells in which $$$A$$$ can be different from $$$B$$$ after some sequence of operations?

You are playing a game, and you are going to fight the secret boss. In this game, the boss doesn't attack you, but they can cast regeneration spells.

The fight consists of exactly $$$N$$$ rounds, in each round the following actions can happen, in this order:

1. The boss can choose to cast the "Regeneration" spell.
2. You can choose to cast the "Poison" spell if you have any mana left.
3. You attack with a sword, dealing $$$X$$$ damage.
4. All the passive effects are applied.

There are two types of passive effects: regeneration and poison. The effects stack, which means that the current state of the boss can be described with three integers: current health points ($$$hp$$$), current poison stacks ($$$p$$$) and current regeneration stacks ($$$r$$$). At the beginning of the fight, there are no poison stacks and no regeneration stacks ($$$p=r=0$$$). Each poison stack deals $$$P$$$ damage, each regeneration stack heals $$$R$$$ health points.

Spells have the following effects:

"Regeneration": increase the number of regenerations stacks $$$r$$$ by $$$1$$$.

"Poison": increase the number of poison stacks $$$p$$$ by $$$1$$$. If the number of regeneration stacks is strictly positive ($$$r \gt 0$$$), then decrease it by $$$1$$$.

After the round the $$$hp$$$ will decrease by $$$X + P \cdot p - R \cdot r$$$ (this value can be negative if the boss heals faster than you deal damage).

For each round you know if the boss will cast "Regeneration". You have enough mana to cast "Poison" $$$K$$$ times (you don't have to use all of your mana). What's the largest total damage you can deal to the boss, in other words, what is the maximum value of $$$hp_{start} - hp_{end}$$$? Assume that $$$hp_{start} = 10^{1000}$$$, so you can't actually kill the boss in $$$N$$$ rounds. Boss $$$hp$$$ can go higher than the initial value (see the third sample case).

Consider an array $$$A$$$ and a set $$$B$$$ of integers such that all numbers in $$$A$$$ and $$$B$$$ are distinct. Your task is to turn $$$A$$$ into a sorted array. To do this you can take any number from $$$B$$$ and replace any element of $$$A$$$ with it. You can perform this operation any number of times, but each element of $$$B$$$ can be used at most once.

Determine the minimum number of operations needed to turn $$$A$$$ into a sorted array, or determine that it is impossible.

You are given a colored tree on $$$n$$$ nodes, node $$$i$$$ has color $$$c_i$$$. As a reminder, a tree on $$$n$$$ nodes is a connected graph with $$$n-1$$$ edges.

Compute the number of connected subgraphs of this tree, for which there exists some color (majority color), such that strictly more than half of the nodes of this subgraph have this color.

Since the answer can be quite large, compute it modulo $$$998\,244\,353$$$.

You are given a permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$. Each position from $$$1$$$ to $$$n$$$ is colored in one of $$$k$$$ colors. We want to sort the permutation, and for that, we can apply any number of operations of the following types:

• Swap any two elements. This operation costs $$$S$$$ coins;
• Choose any color $$$i$$$, and permute the elements on positions of color $$$i$$$ as you wish. This operation costs $$$C_i$$$ coins.

Note that the positions are colored, not the elements, so when you swap two elements, the positions won't change their colors.

Find the minimum number of coins you need to spend to sort the permutation.

You are given a string $$$S$$$ of length $$$3n$$$, consisting of the characters A, B and C. You are allowed to perform the following operation:

• Select some subsegment of this string and a character $$$c$$$ (one of A, B and C). Then, replace all the characters on the subsegment with $$$c$$$.

Find the smallest number of times that you would have to apply the operation above to get a string which contains each of characters A, B and C exactly $$$n$$$ times. It can be shown that it is always possible to get such a string.

In addition, find a sequence of operations of the smallest possible length. If there are many such sequences, you can output any of them.

Consider an undirected tree. The following algorithm constructs a post-order traversal of the tree:

fun dfs(v):
    mark v as used
    for u in neighbours(v):
        if u is not used:
            dfs(u)
    append v to order

The post-order traversal will be in the list order.

You are allowed to choose the order of neighbors for each vertex as well as the starting vertex. What is the lexicographically minimal order you can get?

Define $$$\mathbb{P}_{LR} = \mathbb{P} \cap [L;R]$$$, where $$$\mathbb{P}$$$ is the set of prime numbers. In other words, $$$\mathbb{P}_{LR}$$$ is the set of all primes between $$$L$$$ and $$$R$$$ inclusive.

Given $$$L$$$ and $$$R$$$, find the number of integers that can be represented as XOR of some (possibly empty) subset of $$$\mathbb{P}_{LR}$$$.

Given $$$K$$$, construct two non-empty binary strings $$$S$$$ and $$$T$$$ of length at most 8848 such that they have exactly $$$K$$$ different longest common subsequences. More formally, if $$$L$$$ is the length of the longest common subsequence of $$$S$$$ and $$$T$$$, there should exist exactly $$$K$$$ distinct binary strings of length $$$L$$$ which are subsequences of both $$$S$$$ and $$$T$$$.

It is guaranteed that under the constraints of this problem such strings always exist.

You are given $$$2n$$$ pairs $$$(a_i, b_i)$$$ of integers. Consider a complete graph on $$$2n$$$ vertices and define the weight of the edge $$$(ij)$$$ to be $$$w_{ij} = max(|a_i-a_j|, |a_i-b_j|, |b_i-a_j|, |b_i-b_j|)$$$.

Determine the maximum weight of the matching in this graph.

In other words, consider all ways to select $$$n$$$ edges of this graph such that no two chosen edges have a common endpoint. What is the maximum possible total weight of these edges?