All integers from $$$l$$$ to $$$r$$$ inclusive are written on the board, each exactly once.

We call a number on the board beautiful if it is equal to the sum of all numbers on the board, including this number itself. For example, if the numbers $$$-4$$$, $$$-1$$$, $$$2$$$, $$$3$$$, $$$5$$$ are written on the board, then the number $$$5$$$ is beautiful.

You may erase any numbers from the board, but at least one number must remain. Find the minimum number of numbers that need to be erased so that after that there is at least one beautiful number on the board. It is not necessary to erase any numbers if there is already a beautiful number on the board.

We call a binary string $$$s$$$ of length $$$m$$$ periodic if there exists an integer $$$k$$$ ($$$1 \le k \lt m$$$) such that $$$s_i = s_{i+k}$$$ for every $$$i$$$ from $$$1$$$ to $$$m-k$$$ inclusive. The characters of the string are numbered starting from $$$1$$$. The smallest such $$$k$$$ is called the period of the string.

We call a string $$$s$$$ rhythmic if it is periodic and among the first $$$p$$$ characters of the string (where $$$p$$$ is the period of the string), there is exactly one 1.

For example, the string 0010010 is periodic with period $$$p=3$$$ and rhythmic: among the first three characters there is exactly one 1. The string 0110110 is also periodic with period $$$p=3$$$, but it is not rhythmic: among the first three characters there are two 1s.

You are given an array $$$a$$$ of $$$n$$$ integers and a string $$$s$$$, initially consisting of $$$10^{18}$$$ zeros. For each element $$$a_i$$$, all characters of the string whose indices are divisible by $$$a_i$$$ are replaced by ones. In other words, the characters at positions $$$a_i,2a_i,3a_i,\ldots$$$, not exceeding the length of the string, become ones. Replacing a character with one again does nothing.

For example, if $$$a=[3,7,5,3]$$$, then the string $$$s$$$ will begin with 001011101101011...

Before performing these changes, you may remove any elements from array $$$a$$$. Find the minimum number of elements that need to be removed so that the resulting string $$$s$$$ is rhythmic.

You are given an integer $$$n$$$. Consider the array $$$a = [1, 2, \ldots, n]$$$. You may choose any elements of the array and multiply each chosen element by $$$2$$$. Each element can be doubled at most once. You may choose any subset of elements, including all of them or none of them. Denote the resulting array by $$$b$$$.

Let $$$k$$$ be the bitwise OR of all elements of the original array $$$a$$$, and let $$$m$$$ be the bitwise XOR of all elements of the resulting array $$$b$$$:

$$$$$$ k = a_1 \mathbin{|} a_2 \mathbin{|} \cdots \mathbin{|} a_n, \qquad m = b_1 \oplus b_2 \oplus \cdots \oplus b_n. $$$$$$

Choose which elements to double so that $$$m \ge 2k$$$. It can be shown that this is possible for every valid value of $$$n$$$. You do not need to minimize the number of doubled elements.

You are given a tree with $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. Initially, all vertices are white.

You must choose a single integer $$$k$$$ from $$$1$$$ to $$$2n$$$, inclusive. Then, for each $$$i$$$ from $$$1$$$ to $$$n$$$ in increasing order, if the tree contains a vertex numbered $$$k-i$$$ and $$$k-i \ne i$$$, the following operation is performed:

1. vertices $$$i$$$ and $$$k-i$$$ are recolored black, regardless of their current colors;
2. all white vertices on the simple path between $$$i$$$ and $$$k-i$$$ are recolored gray. The colors of the other vertices on this path do not change.

You must choose $$$k$$$ to maximize the number of black vertices (higher priority) and the number of gray vertices (lower priority). In other words, choose $$$k$$$ so that the number of black vertices in the tree is as large as possible, and among the values of $$$k$$$ that give the maximum number of black vertices, choose one that gives as many gray vertices as possible.

Find any optimal value of $$$k$$$. If there are multiple suitable values of $$$k$$$, print any of them.

You are given a binary string $$$s$$$ of length $$$n$$$. The characters of the string are numbered from $$$1$$$ to $$$n$$$.

You have to partition all integers from $$$1$$$ to $$$n$$$ into nonempty sets so that each integer belongs to exactly one set. For each pair of distinct integers $$$x$$$ and $$$y$$$ in the same set, at least one of the following conditions must hold:

• $$$s_x = s_y$$$;
• $$$|x-y| = 1$$$.

For a set $$$M$$$, let $$$f(M)$$$ be the number of distinct characters among $$$s_x$$$ over all $$$x \in M$$$. The cost of the set $$$M$$$ is $$$|M| \cdot f(M)$$$, where $$$|M|$$$ is the number of elements in $$$M$$$. The cost of a partition is the sum of the costs of all its sets.

For example, if the string $$$s$$$ is 10001000, the partition into the sets $$$\{1, 2\}, \{3, 8\}, \{4, 5, 6\}, \{7\}$$$ is valid, and its cost is $$$2 \cdot 2 + 2 \cdot 1 + 3 \cdot 2 + 1 \cdot 1 = 13$$$.

Find the maximum possible cost of a partition and the number of partitions with this cost. Partitions that differ only in the order of the sets or the order of elements within the sets are considered the same. Output the number of partitions modulo $$$998\,244\,353$$$.

You are given a directed graph with $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. The graph is constructed as follows: for each vertex $$$i$$$ from $$$2$$$ to $$$n$$$, you are given two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \lt i$$$). For each integer $$$j \in [l_i, r_i]$$$, the graph contains a directed edge from $$$j$$$ to $$$i$$$. There are no other edges in the graph.

Consider a second directed graph on the same $$$n$$$ vertices. For any two distinct vertices $$$x$$$ and $$$y$$$, a path from $$$x$$$ to $$$y$$$ must exist in the second graph if and only if it exists in the first graph.

Find the minimum possible number of edges in the second graph.

You are given a directed graph with $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. Each vertex has at least one incoming edge. The graph may contain self-loops, but it has no multiple edges. For each vertex $$$v$$$, an integer $$$k_v$$$ is given, ranging from $$$1$$$ to the number of incoming edges of that vertex.

Each vertex has a number written on it. Every second, all the numbers are updated as follows. For a vertex $$$v$$$, take the numbers at the vertices $$$u$$$ for which there is an edge $$$u\to v$$$, sort them in non-decreasing order, and update vertex $$$v$$$ with the number at the position $$$k_v$$$. Positions in the sorted list are numbered starting from $$$1$$$. In other words, the new number at vertex $$$v$$$ is the $$$k_v$$$-th order statistic of the array consisting of the numbers at the vertices $$$u$$$ for which there is an edge $$$u \to v$$$.

All vertices are updated simultaneously: only the numbers from before the current update are used to compute the new numbers. If a vertex has a self-loop, its own number also affects the update.

You have to process $$$q$$$ queries of the following form:

• $$$t$$$ $$$a_1$$$ $$$a_2$$$ ... $$$a_n$$$ — determine the numbers that will be written on the vertices of the graph after $$$t$$$ seconds if their initial numbers are $$$a_1, a_2, \dots, a_n$$$.