Mr. Hacker's Department of Administrative Affairs (DAA) has an infinite amount of civil servants. Every integer is used as an ID (identification number) by exactly one civil servant. Mr. Hacker is keen on reducing overmanning in civil service, so he will only keep people with consecutive IDs in $$$[l, r]$$$, and dismiss all the others.

However, permanent secretary Sir Humphrey's ID is $$$x$$$, and he cannot be kicked out, so $$$l \leq x \leq r$$$ must hold. Mr. Hacker wants to be Prime Minister, so he demands that the sum of people's IDs $$$\sum_{i = l}^{r} i$$$ must be a prime number.

You, Bernard, need to make the reduction plan which meets the demands of both bosses. Otherwise, Mr. Hacker or Sir Humphrey will fire you.

Mr. Hacker would be happy to keep as few people as possible. Please calculate the minimum number of people left to meet their requirements.

A prime number $$$p$$$ is an integer greater than $$$1$$$ that has no positive integer divisors other than $$$1$$$ and $$$p$$$.

Two heroes are fighting, whose names are hero $$$0$$$ and hero $$$1$$$ respectively.

You are controlling the hero $$$0$$$, and your enemy is the hero $$$1$$$. Each hero has five integer attributes: ATTACK, DEFENSE, POWER, KNOWLEDGE, and HEALTH. When two heroes battle with each other, they will take turns to attack, and your hero moves first. One hero can make $$$\textbf{exactly one attack}$$$ in one turn, either a physical attack or a magical attack.

Assume their attributes are $$$A_i$$$, $$$D_i$$$, $$$P_i$$$, $$$K_i$$$, $$$H_i$$$ ($$$0 \leq i \leq 1)$$$. For hero $$$i$$$, its physical attack's damage is $$$C_p \cdot \max (1, A_i - D_{1-i})$$$, while its magical attack's damage is $$$C_m \cdot P_i$$$. Here, $$$C_p$$$ and $$$C_m$$$ are given constants.

After hero $$$i$$$'s attack, $$$H_{1-i}$$$ will decrease by the damage of its enemy. If $$$H_{1-i}$$$ is lower or equal to $$$0$$$, the hero $$$(1-i)$$$ loses, the hero $$$i$$$ wins, and the battle ends.

Hero $$$i$$$ can make magical attacks no more than $$$K_i$$$ times in the whole battle.

Now you know your enemy is a Yog who is utterly ignorant of magic, which means $$$P_1 = K_1 = 0$$$, and he will only make physical attacks. You can distribute $$$N$$$ attribute points into four attributes $$$A_0$$$, $$$D_0$$$, $$$P_0$$$, $$$K_0$$$ arbitrarily, which means these attributes can be any non-negative integers satisfying $$$0 \leq A_0 + D_0 + P_0 + K_0 \leq N$$$.

Given $$$C_p$$$, $$$C_m$$$, $$$H_0$$$, $$$A_1$$$, $$$D_1$$$, and $$$N$$$, please calculate the maximum $$$H_1$$$ such that you can build hero $$$0$$$ and fight so that it wins the game.

We have a tree $$$\langle V, E \rangle$$$ that consists of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$. Each vertex $$$i \in V$$$ has weight $$$a_i$$$. Each bidirectional edge $$$e = \langle u, v \rangle \in E$$$ has weight $$$b_e$$$. Here, $$$a_i$$$ are non-negative integers, and $$$b_e$$$ are integers.

You can perform at most $$$4 n$$$ operations. For each operation, select two vertices $$$X$$$ and $$$Y$$$, and a non-negative integer $$$W$$$. Consider the shortest path from $$$X$$$ to $$$Y$$$ (a path is shortest if the number of edges $$$k$$$ in it is minimum possible). Let this path consist of $$$k + 1$$$ vertices $$$(v_0, v_1, v_2, \ldots, v_k)$$$ where $$$v_0 = X$$$, $$$v_k = Y$$$, and for $$$0 \leq i \lt k$$$, the edges $$$e_i = \langle v_{i}, v_{i+1} \rangle \in E$$$. The operation changes the weights as follows:

$$$$$$a_X \leftarrow a_X \bigoplus W\text{;} \quad a_Y \leftarrow a_Y \bigoplus W\text{;} \quad b_{e_i}\leftarrow b_{e_i} + (-1)^i \cdot W \text{~for~} 0 \leq i \lt k\text{.}$$$$$$

Here, $$$\bigoplus$$$ denotes the bitwise XOR operation. We can notice that, if $$$X = Y$$$, nothing will change.

You need to decide whether it is possible to make all $$$a_i$$$ and all $$$b_e$$$ equal to $$$0$$$. If it is possible, find a way to do so.

You are given an undirected complete graph with $$$n$$$ vertices, where $$$n$$$ is odd. You need to partition its edge set into $$$k$$$ disjoint simple paths, satisfying that the $$$i$$$-th simple path has length $$$l_i$$$, and each undirected edge is used exactly once. The given lengths $$$l_i$$$ are integers from $$$1$$$ to $$$n - 3$$$.

A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A simple path is a path where vertices are pairwise distinct. The length of a path is the number of edges in it.

It can be shown that an answer always exists if $$$\displaystyle \sum\limits_{i=1}^k l_i = \frac{n(n-1)}{2}$$$ holds.

Mr. Docriz has $$$n$$$ different kinds of objects indexed by $$$1, 2, \ldots, n$$$. An object of the $$$i$$$-th kind weighs $$$i$$$ kilograms. For each $$$i$$$, Mr. Docriz has $$$b_i$$$ objects of the $$$i$$$-th kind. Among those objects, there are $$$a_i$$$ precious objects, and the remaining ones are common objects. Now, he wants to divide all his objects into some (one or more) disjoint sets. These sets have to satisfy the following conditions:

1. Each object should go to exactly one set.
2. Each set should contain exactly one precious object.
3. In each set, the weight of the precious object should be the median weight of this set.

Please tell him whether it is possible.

For a set of size $$$k$$$, if we sort its elements by non-descending weight as $$$c_1, c_2, \ldots, c_k$$$, the median weight of this set is defined as the weight of $$$c_{\lfloor (k + 1) / 2 \rfloor}$$$.

Nocriz is a student who, like many, has a dream for his life. Unfortunately, life isn't always easy, and there are times when the dream seems far away and the pursuit feels difficult.

Reality often drives people away from their pursuit of dreams to settle for what they have at hand. Lured to set aside the struggle, Nocriz said to Artemisia, "But I shouldn't give up the dream, right?". Artemisia replied: "Of course one should not give up the dream easily! Struggle, struggle until you are crushed by a rock!".

That night, Nocriz had a very bad dream. In his dream, there was a rock in the shape of an ellipse, and he was asked to calculate the sum of values $$$(x \oplus y)^{33} x^{-2} y^{-1}$$$, performing the calculations modulo $$$10^9 + 7$$$, for all integer points $$$(x, y)$$$ in the ellipse, where $$$\oplus$$$ is the bitwise XOR operation.

Formally, the ellipse is specified by six integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$, $$$e$$$, $$$f$$$. Consider the ellipse $$$E = \{(x, y) \mid x, y \in \mathbb{Z}, \, a (x - b)^2 + c (y - d)^2 + e (x - b) (y - d) \le f\}$$$. It is guaranteed that all points of the ellipse satisfy $$$0 \lt x, y \lt 4 \cdot 10^6$$$, and that the ellipse contains at least one integer point. Now, consider the coordinates as residues modulo $$$10^9 + 7$$$, and calculate $$$$$$\sum_{(x, y) \in E} (x \oplus y)^{33} x^{-2} y^{-1}\text{.}$$$$$$ In particular, considering numbers as residues means that $$$z^{-1}$$$ is the modular inverse of $$$z$$$, and the result of every addition and multiplication has to be taken modulo $$$10^9 + 7$$$.

Nocriz was not crushed by the rock that day. Can you solve this problem, like Nocriz did?

As a modern art lover, Nocriz loves going to the Power Station of Art.

Currently, art pieces of a modern genre of art called "red-black graphs" are exhibited in the Power Station of Art. Every red-black graph art piece is an undirected labeled graph with numbers and colors associated with each vertex. Each vertex is either red or black.

It is possible to modify a graph in the following way: choose an edge and swap the numbers written on the corresponding vertices. In addition, if the colors of the two vertices are the same, the colors of both vertices are changed (from red to black or from black to red). Otherwise, the colors of the two vertices remain unchanged.

Now, Nocriz is studying two art pieces. The graphs are the same but the numbers and colors may be different. Is it possible to make some (possibly zero) modifications to the art pieces to make them be the same?

Being a nostalgic boy, Nocriz loves watching HBK08 and Lantian28 playing the game Command and Conquer: Red Alert 2. However, he doesn't know how to play the game himself.

In the game, you own a sniper initially located at $$$(-10^{100}, -10^{100}, -10^{100})$$$ in a 3D world. There are $$$n$$$ enemy soldiers, where the $$$i$$$-th soldier is located at $$$(x_i, y_i, z_i)$$$. We say the range of the sniper to be $$$k$$$ if the sniper can kill all enemies such that $$$\max(|x_s - x_e|, |y_s - y_e|, |z_s - z_e|) \le k$$$, where $$$(x_s, y_s, z_s)$$$ is the location of the sniper and $$$(x_e, y_e, z_e)$$$ is the location of the enemy.

In one step, the sniper can move from $$$(x, y, z)$$$ to $$$(x + 1, y, z)$$$, $$$(x, y + 1, z)$$$, or $$$(x, y, z + 1)$$$. The enemies don't move. The sniper is allowed to make an unlimited number of steps, and is allowed to kill all enemies in range whenever all his coordinates are integers. What is the minimum range $$$k$$$ such that the sniper can eventually kill all enemies?

Teacher Docriz is planning to select some students in his class for a typing contest.

There are $$$n$$$ students in the class. The $$$i$$$-th classmate's initial typing speed is $$$s_i$$$ and the typing noise is $$$f_i$$$. However, when several students are selected to compete, their total typing speed is not the sum of everyone's initial typing speed, because the noise each person makes affects others.

Specifically, if students $$$1, 2, 3, \ldots, k$$$ form a team, the actual typing speed of student $$$1$$$ is $$$s_1 \cdot (1 - f_1 f_2 - f_1 f_3 - \ldots - f_1 f_k)$$$, the actual typing speed of student $$$2$$$ is $$$s_2 \cdot (1 - f_2 f_1 - f_2 f_3 - \ldots - f_2 f_k)$$$, and so on.

Teacher Docriz wants to form a team so that the total typing speed is as large as possible. Please help him calculate the maximum typing speed he could possibly achieve.

Koishi is playing a game with Satori.

There is an array of length $$$10^{18}$$$. In the game, Koishi and Satori take turns operating on this array, and Koishi goes first. At the start of a player's turn, if there is only one element left in the array, she loses the game immediately. Otherwise, she needs to delete either the leftmost number or the rightmost number of the remaining array.

The game is too boring for Koishi, so she came up with the following modified rules.

There are $$$n$$$ sub-segments of this array that are special. Specifically, the $$$i$$$-th sub-segment is described by three integers $$$(l_i, r_i, z_i)$$$. They mean that, at the start of a player's turn, if the remaining array is the sub-segment $$$[l_i, r_i]$$$, she will win immediately if $$$z_i = 1$$$ or lose immediately if $$$z_i = 0$$$.

If there is a special sub-segment $$$(x, x, 1)$$$ given for some $$$x$$$, a player will immediately win when the remaining array is $$$[x, x]$$$ at the start of their turn. Importantly, if there is no special sub-segment $$$(x, x, 1)$$$ given for some $$$x$$$, it is assumed that $$$[x, x]$$$ is an immediate loss, as in the original rules.

There will be $$$q$$$ games. At the beginning of the $$$i$$$-th game, Utuoho will give two players the sub-segment $$$[a_i, b_i]$$$ and take away all other parts of the array. That means Koishi and Satori only play on sub-segment $$$[a_i, b_i]$$$, not on the whole array. All the $$$q$$$ games are independent.

Two players always use the optimal strategy. Please tell them who will win in each game.

Koishi gives you an integer array $$$B$$$ of length $$$n$$$ satisfying $$$1 \leq B_1 \leq B_2 \leq \ldots \leq B_n \leq n + 1$$$.

Let $$$S(T)$$$ denote the set of numbers that appear in array $$$T$$$. Koishi asks you whether an array $$$A$$$ of length $$$n$$$ exists such that, for any $$$l$$$ and $$$r$$$ such that $$$1 \leq l \leq r \leq n$$$, the equality $$$S(A[l,r]) = S(A[1,n])$$$ holds if and only if $$$r \ge B_l$$$. If so, please construct an array $$$A$$$ that satisfies the condition above.

Here, $$$A[l,r]$$$ represents the sub-array of $$$A$$$ formed by $$$A_l, A_{l+1}, \ldots, A_{r}$$$.

You can only use integers from $$$0$$$ to $$$10^9$$$ in the array. It can be shown that, if a solution exists, then there also exists a solution satisfying this condition.

Notice: If there exists such an index $$$i$$$ ($$$1 \leq i \leq n$$$) that $$$B_i \lt i$$$ holds, the required $$$A$$$ must not exist.