Given a tree$$$^{[6]}$$$ of $$$n$$$ vertices, find the lexicographically$$$^{[2]}$$$ smallest string $$$s$$$ that satisfies the following:

• String $$$s$$$ only consists of letters 'a', 'b', and 'c'.
• For every edge $$$(u,v)$$$ of the tree, $$$s_u \neq s_v$$$.

The judges of DCPC are offering free problems to the contestants; you just have to take them!

They will ask you if you want a free problem.

If you want one, you should output "Yee", and the judges will give you a free problem. Anything else, even "Yes" or "Sure", and they won't give you one.

So, do you want a free problem?

Given a tree$$$^{[6]}$$$ with $$$n$$$ vertices, where the $$$i$$$-th vertex is labeled with a positive integer $$$a_i$$$. A tree is eggy when the greatest common divisor of all its vertex-values is equal to $$$1$$$.

You have to process $$$q$$$ queries as follows:

• $$$i\; x$$$: update the value of $$$i_{th}$$$ vertex by assigning $$$a_i = x$$$.
• After each update, check if there's any edge in the tree that, when removed, splits the tree into two trees, where at least one of those trees is eggy.

You are given two integers $$$n$$$ and $$$m$$$. Find the number of ways to fill an $$$n\times m$$$ grid with the numbers $$$1, 2, \ldots, n \times m$$$, using each number exactly once, such that the following conditions are satisfied:

• Every row forms a strictly monotonic$$$^{[5]}$$$ sequence.
• Every column forms a strictly monotonic sequence.

Count the number of valid fillings, modulo $$$998\,244\,353$$$.

Given a permutation$$$^{[3]}$$$ $$$p$$$ of length $$$n$$$. Obada and the Harraaak are playing a game with this permutation with an initial score of $$$0$$$.

The players must follow a set of rules described as follows:

• On each turn, a player must choose an integer $$$x$$$ from the permutation that has not been selected before. The player either adds or subtracts $$$x$$$ from the score.
• During the first turn, a player can select any integer.
• For all turns except the first, if $$$m$$$ is the integer selected in the previous turn and $$$p_m$$$ is not chosen yet, then the player must select $$$p_m$$$ in this turn. Otherwise, they can pick any integer that has not been selected yet.
• The game terminates when all integers in the permutation have been selected.

The players alternate turns, with Obada starting first. Obada aims to maximize the score of the game, while the Harraaak aims to minimize it.

Your task is to find the final score of the game when both players play optimally.

This is an interactive problem. Your program will interact with the judge using standard input and output.

You are given an array $$$a$$$ of $$$n$$$ positive integers and an integer $$$k$$$, where $$$2k \leq n$$$. You have an initial score equal to $$$0$$$.

You will be asked $$$k$$$ queries. For each query, you will be given an integer $$$x \in \{1, 2\}$$$. You must choose an index $$$i$$$ ($$$1 \leq i \leq n$$$) such that$$$^\dagger$$$:

• $$$i$$$ is divisible by $$$x$$$;
• The index $$$i$$$ has not been chosen in any previous query;

Whenever you choose some index $$$i$$$ in some query, the value of $$$a_i$$$ is added to the score.

Your task is to maximize the score after completing all $$$k$$$ queries.

The interaction proceeds as follows for $$$k$$$ times:

• The judge will output a single integer $$$x \in \{1, 2\}$$$.
• You must respond with a single integer $$$i$$$ ($$$1 \leq i \leq n$$$) that satisfies the conditions above$$$^\dagger$$$.
• The judge will output "1" if $$$i$$$ is divisible by $$$x$$$ and it has not been chosen before in any previous query, and "0" otherwise.

If your program makes an invalid response, then the judge's response will be "0". After receiving such a response, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.

After responding to a query, do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• sys.stdout.flush() in Python;
• std::io::stdout().flush() in Rust;
• see the documentation for other languages.

Вам дана колода из $$$n$$$ карт, на каждой из которых записано число $$$a_i$$$. Игра начинается с пустой руки и начального общего счета, равного нулю.

На $$$i$$$-м ходу вы должны взять $$$i$$$-ю карту со значением $$$a_i$$$, затем по желанию сбросить некоторые карты из вашей руки, обеспечив, чтобы после этого шага побитовое исключающее ИЛИ любых двух оставшихся карт в руке было простым числом. Счёт за этот ход — это сумма значений всех карт в вашей руке, которая затем добавляется к общему счету.

Определите максимальный возможный общий счет после завершения всех $$$n$$$ ходов.

You are given an array $$$a$$$ of length $$$n$$$. Count the number of non-empty subarrays$$$^{[1]}$$$ ($$$a[l, l + 1, \ldots, r]$$$) such that its sum is equal to its MEX$$$^{[10]}$$$.

You are given a connected, undirected, weighted graph with $$$n$$$ vertices and $$$m$$$ edges labeled from $$$1$$$ through $$$m$$$. Define:

• $$$G[l, r]$$$: the graph on all $$$n$$$ vertices containing only the edges numbered from $$$l$$$ to $$$r$$$.
• $$$\text{W}(H)$$$: the total weight of a minimum spanning tree$$$^{[7]}$$$ of graph $$$H$$$, or $$$\infty$$$ in case $$$H$$$ is disconnected.

You have to process $$$q$$$ queries. For each query specified by a range $$$[l, r]$$$, count the number of pairs $$$(x, y)$$$ that satisfy the following:

• $$$l \leq x \leq y \leq r$$$;
• $$$\text{W}(G[x, y]) = \text{W}(G[1, m])$$$.

Given two integers $$$n$$$ and $$$k$$$. An array $$$a$$$ is considered good if the following conditions hold:

• The length of $$$a$$$ is equal to $$$n$$$.
• $$$a$$$ contains positive integers.
• The sum of elements of $$$a$$$ is equal to $$$k$$$ (i.e. $$$\sum a_i = k$$$).

The cost of the array $$$a$$$ is equal to the sum of $$$a_i$$$ $$$\&$$$ $$$a_{i - 1}$$$ for all $$$i$$$ such that $$$1 \lt i \le n$$$, where $$$\&$$$ is the bitwise AND$$$^{[9]}$$$ operator.

Your task is to find the minimum cost of a good array.

Given two integers $$$n$$$ and $$$k$$$, your task is to find the $$$k$$$-th smallest derangement$$$^{[4]}$$$ of length $$$n$$$ when all derangements of length $$$n$$$ are listed in lexicographical order$$$^{[2]}$$$.

Given a permutation$$$^{[3]}$$$ $$$p$$$ of length $$$n$$$ and two integers $$$k_1$$$ and $$$k_2$$$, both not exceeding $$$n$$$. There is also an integer array $$$a$$$, initially empty. Obada and Osama are playing a game. Obada starts first, and the players alternate turns. On their turn, the player must do one of the following:

• Remove the leftmost element from $$$p$$$ and append it to the end of the array $$$a$$$.
• Append $$$0$$$ to the end of the array $$$a$$$.

There is one restriction, the player can't make a move that makes the array $$$a$$$ invalid.

The array $$$a$$$ is invalid when at least one of the following two conditions hold:

• The array $$$a$$$ contains a subarray of length more than $$$k_1$$$ that contains no $$$0s$$$.
• The array $$$a$$$ contains a subarray of length more than $$$k_2$$$ which elements are all $$$0s$$$.

The game ends when $$$p$$$ is empty, and the score of the game is equal to the largest number removed from the permutation by Obada in his turn.

Obada wants to maximize the score of the game, while Osama wants to minimize it. You are asked to find the score of the game if both players play optimally.

Given an array $$$a$$$ of length $$$n$$$. A partition of the array $$$a$$$ is dividing it into subarrays$$$^{[1]}$$$ such that each element of $$$a$$$ belongs to exactly one subarray. Two partitions are considered different if there is a subarray that is present in one of the partitions but not in both of them.

We define the cost of a partition of $$$a$$$ as the following:

1. Let's initialize cost to be equal to $$$0$$$.
2. For each subarray of $$$a$$$ (i.e. $$$a[l, l + 1, \ldots, r]$$$) that is present in the partition, let $$$s$$$ be equal to the sum of integers in this subarray (i.e. $$$\displaystyle\sum_{i=l}^r a_i$$$).
3. Update cost to be equal to cost $$$\oplus$$$ $$$s$$$, where $$$\oplus$$$ is the bitwise XOR$$$^{[8]}$$$ operator.

Find the bitwise XOR of the costs of all possible partitions of $$$a$$$.

Given an array $$$a$$$ consisting of $$$n$$$ positive integers. For each $$$i$$$ such that $$$1 \le i \le n$$$, there are $$$a_i$$$ sticks of length $$$i$$$, and let $$$m$$$ be equal to the total number of sticks (i.e. $$$m = \displaystyle\sum_{i=1}^{n} a_i$$$).

You have $$$m$$$ colors, and for each stick, you must choose an integer $$$k$$$ such that $$$1 \le k \le m$$$, and color the $$$i$$$-th stick with the $$$k$$$-th color.

Your goal is to color these sticks in such a way that it would be impossible to form a square by choosing four sticks of the same color.

What is the minimum number of different colors you need to use?