The United Galactic Federation has constructed the Quantum Corridor, a massive linear particle accelerator consisting of $$$n$$$ discrete energy chambers indexed from $$$1$$$ to $$$n$$$.

You are the lead physicist overseeing an experiment with a single Chronon particle currently stabilized in chamber $$$i$$$. Due to the corridor's unique resonance, the Chronon travels exclusively by tunneling, instantly teleporting from its current position to a new one. The tunneling drive operates in two modes:

• Alpha Shift: Teleport exactly $$$a$$$ chambers to the left or right.
• Beta Shift: Teleport exactly $$$b$$$ chambers to the left or right.

The containment field is strictly bounded by the corridor's physical dimensions. A tunnel is only successful if the destination chamber $$$x$$$ satisfies $$$1 \le x \le n$$$. If a jump attempts to land the particle outside this range, the field suppresses the move, and the Chronon remains in its current chamber.

The Chronon possesses infinite energy and can perform any sequence of valid jumps. However, the specific geometry of the corridor and the jump lengths may render certain sections of the accelerator permanently inaccessible.

Your task is to calculate the number of Dark Chambers, defined as the number of indices in the range $$$[1, n]$$$ that the Chronon can never reach, regardless of the sequence of moves attempted.

Bob has a secret prime number $$$p$$$ ($$$10 \le p \le 10^8$$$). While he appreciates the properties of prime numbers, he would prefer it if his number were composite.

To achieve this, Bob can modify $$$p$$$ by prepending one or more decimal digits to the front of its decimal representation. He wants to prepend the minimum number of digits necessary to transform $$$p$$$ into a composite number.

For example, if $$$p = 11$$$:

• Prepending $$$5$$$ gives $$$511$$$, which is a composite number ($$$7 \times 73$$$).
• Prepending $$$12$$$ gives $$$1211$$$, which is also a composite number ($$$7 \times 173$$$).

Bob asks for your help.

This is an interactive problem. Your program should perform the following steps for each test case:

1. First, output an integer $$$x$$$ ($$$1 \le x \le 10^6$$$) that you wish to test as a prefix.
2. Remember to flush your standard output after printing $$$x$$$.
3. The judge will respond with YES if the number formed by prepending $$$x$$$ to $$$p$$$ is composite, or NO if it is prime.
4. Finally, output an integer $$$y$$$ ($$$1 \le y \le 10^6$$$) such that prepending $$$y$$$ to $$$p$$$ results in a composite number using the minimum number of digits possible. If multiple such values of $$$y$$$ exist, you may output any of them.
5. Flush your output again after printing $$$y$$$.

There are $$$n$$$ nests in a forest. These nests are connected by $$$n-1$$$ branches, forming a tree structure. From any nest, a crow can reach any other nest by flying along the branches, and there are no cycles.

A wise old crow wants to travel through all nests exactly once. It can fly in a straight path from one nest to the next if there exists a branch between those nests. The crow already decided the exact order in which it wants to visit the nests.

However, the current branch structure may not form a single straight path. To help the crow, you are allowed to carefully rearrange branches.

Your task is to transform the initial tree structure of nests into the desired chain structure using at most $$$n^2$$$ rearrangement operations.

In one rearrangement operation, you can choose three distinct nests $$$a,b,c$$$ such that the branches $$$(a,b)$$$ and $$$(b,c)$$$ exist in the current tree. Then perform the following change:

• remove the branch $$$(a,b)$$$;
• add the branch $$$(a,c)$$$.

In the far-away galaxy of Phitron, a rare cosmic phenomenon known as a Dual Star System can be observed.

The system consists of two identical spherical planets, each with same radius, rotating on a circular orbit. The center of their rotation is the midpoint of the two planet centers. Throughout the motion, the two planets always remain on opposite sides of the orbit.

An astronaut living on a space station at the origin $$$(0,0,0)$$$ is fascinated by this phenomenon. He is feeling lazy today and he decided only to start his daily routine if he can draw a single straight line from his position that intersects or touches both planets at the same time.

Figure: Dual Star System in three-dimensional space.

You are given the current coordinates of the centers of the two planets, $$$C_1$$$ and $$$C_2$$$, along with their common radius $$$r$$$ and angular speed $$$\omega$$$. The planets rotate with this speed, but the direction of rotation is unknown: it may be clockwise or counter-clockwise.

It is guaranteed that the space station lies on the same plane as the orbit of the planets. It is also guaranteed that the distance from the origin to the center of rotation is strictly greater than the radius of the circular orbit and planets are non-overlapping.

Since the direction of rotation is unknown, the astronaut wants to know the earliest possible time at which the alignment can occur, assuming the planets rotate in the more favorable direction.

Determine whether the alignment is possible. Print $$$-1$$$ if it is impossible, otherwise the minimum time at which it occurs.

You are given an array $$$A$$$ of length $$$n$$$ consisting only of numbers $$$0$$$ and $$$1$$$. You may obtain another array $$$A'$$$ by performing a cyclic rotation of $$$A$$$ by any number of positions (possibly zero).

A cyclic rotation shifts elements of an array circularly. For example, rotating $$$[1, 0, 1, 1, 0]$$$ gives: $$$$$$ [1, 0, 1, 1, 0], \; [0, 1, 1, 0, 1], \; [1, 1, 0, 1, 0], \; [1, 0, 1, 0, 1], \; [0, 1, 0, 1, 1] $$$$$$

Define an array $$$B$$$ as follows: $$$$$$B[i] = A[i] \oplus A'[i] \quad \text{for all } 0 \le i \lt n$$$$$$ where $$$\oplus$$$ denotes the bitwise XOR operation.

An array $$$X$$$ is said to be lexicographically larger than an array $$$Y$$$ if:

• at the first position where they differ, $$$X$$$ has a $$$1$$$ and $$$Y$$$ has a $$$0$$$.

Your task is to determine the lexicographically maximum binary array $$$B$$$ that can be obtained among all possible cyclic rotations of $$$A$$$.

You are given two integers $$$N$$$ and $$$S$$$. Consider all possible arrays $$$[a_1, a_2, \dots, a_n]$$$ of $$$N$$$ non-negative integers such that $$$a_1 + a_2 + \dots + a_n = S$$$.

For each such array, compute the bitwise XOR of all its elements, i.e., $$$a_1 \oplus a_2 \oplus \dots \oplus a_n$$$. Find the sum of these values over all possible arrays.

Since the answer can be very large, output it modulo $$$998244353$$$.

You are a close friend of Dr. G, a bioinformatics scientist working at Phitron. Dr. G is studying the evolution of a synthetic genome in a controlled laboratory environment. Each genome is represented by a non-negative integer, where each bit in its binary representation corresponds to the presence or absence of a specific genetic marker.

The genome evolves over discrete time steps according to the following rules:

• At time step $$$1$$$, the genome has value $$$a$$$.
• At time step $$$2$$$, the genome has value $$$b$$$.
• For every time step $$$t \ge 3$$$, the genome is formed by examining the genomes at time steps $$$t-1$$$ and $$$t-2$$$, and constructing a new genome that contains only those genetic markers that appear in both of them.

Dr. G has been manually checking whether the genome sequences evolve correctly, but this task has become extremely tedious and time-consuming. To help your friend, you decide to write a program that determines the genome value at a given time step $$$t$$$.

You are given a directed graph with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$. Each node $$$i$$$ has an integer value $$$a_i$$$ associated with it. For any two distinct node $$$u$$$ and $$$v$$$, there is a directed edge from $$$u$$$ to $$$v$$$ if and only if:

$$$$$$(a_u \oplus a_v \gt a_u) \quad and \quad (a_u \oplus a_v \lt a_v)$$$$$$

where $$$\oplus$$$ denotes the bitwise XOR operation.

You may start from any node and traverse the graph by following directed edges. What is the maximum number of distinct nodes that can be visited in a single path?

Bob visited the country of Bakdum not so long ago. The country has $$$n$$$ cities and they are all connected by two-way roads. Also, from one city, there is exactly one way to reach any other city.

Among the cities, there are several with high security because they have magical ley-lines running through them. Any city has at most 1 ley-line running through it. Bob went to a total of $$$m$$$ tours to see the ley-lines. During each tour, he was able to ride on a tracker bus, which could detect the presence of ley-lines. The $$$i$$$th tour can be represented as Bob going from city $$$u_i$$$ to city $$$v_i$$$, and during the whole tour the tracker was always on. But due to magical interference, Bob was only able to determine whether there was an even or odd number of ley-lines on that path, given as $$$p_i \in \{0, 1\}$$$.

Now after Bob returned, he was confused about the data he had collected. He has a suspicion that one of his tour results got flipped by a high energy cosmic ray bit flip incident. Now, for each tour report, assuming it was flipped individually, calculate the revised total number of ley-lines in Bakdum. If it is impossible to determine it uniquely or the data is inconsistent report them too.

You are given an array $$$A$$$ of length $$$n$$$, where the array uses one-based indexing (i.e., the elements are $$$A[1], A[2], \dots, A[n]$$$).

Define the following function:

Function F(i, n, A):
    Reverse(A[1..i]) // Reverse the prefix of length i
    ret ← 0
    For j ← 1 to n:
        ret ← ret + (j × A[j]) // weighted sum
    Return ret

That is, the function reverses the prefix of the array from index $$$1$$$ to $$$i$$$ and then computes the weighted sum.

The function operates on a temporary copy of the array $$$A$$$. That is,

• The reversal of the prefix $$$A[1..i]$$$ is performed only for the purpose of computing $$$F(i, n, A)$$$.
• The original array $$$A$$$ remains unchanged after the function call.
• For each value of $$$i$$$, the function is evaluated independently on the original array.

For the given array $$$A$$$, consider all values $$$F(i, n, A)$$$ for $$$1 \le i \le n$$$. Your task is to output an ordering of indices $$$[p_1, p_2, \dots, p_n]$$$ which is a permutation of $$$\{1, 2, \dots, n\}$$$, such that:

• If $$$F(i, n, A) \le F(j, n, A)$$$, then index $$$i$$$ appears before index $$$j$$$ in the ordering.
• If multiple valid orderings satisfy the above condition, output the lexicographically smallest one.

There is a lottery that is going to happen and $$$n$$$ ($$$1 \le n \le 10^6$$$) people have already bought one or more lottery tickets: the $$$i$$$th person has bought $$$t_i$$$ ($$$1 \le t_i \le 5$$$) lottery tickets. There will be $$$m$$$ ($$$1 \le m \le \min{\left( 100, n \right)}$$$) draws. In the $$$j$$$-th ($$$1 \le j \le m$$$) draw:

• a ticket $$$T$$$ is selected uniformly randomly among all the remaining tickets;
• the person $$$P$$$ who has bought the ticket $$$T$$$ will be declared as the winner of the $$$m-j+1$$$-th prize;
• and all of person $$$P$$$'s tickets are removed from the lottery.

Alice is the last (that is, the $$$n+1$$$-th) ticket buyer, and she wants to win the $$$k$$$-th prize ($$$1 \le k \le m$$$). Alice can buy between $$$1$$$ to $$$l$$$ ($$$1 \le l \le 2000$$$) lottery tickets (inclusive range). She wants to know, for each $$$x \in \{ 1, \dots, l \}$$$, what the probability for winning the $$$k$$$-th prize is if she buys exactly $$$x$$$ tickets.

Alice has figured out that the probability $$$f(x)$$$ of winning the first prize is given by $$$$$$ f(x) = \sum_{\substack{A \subseteq \{ 1, \dots, n\} \\ |A| \le m - 1}} \left( -1 \right)^{m - 1 - |A|} {{n - |A|}\choose{m - 1 - |A|}} \left( \frac{x}{x + \sum_{j \not\in A} t_j} \right) $$$$$$

Alice has asked you to figure out the rest.

You are simulating a classic Snake game on an $$$n \times n$$$ grid.

Grid

Cells are addressed by coordinates $$$(x, y)$$$, where:

• $$$1 \le x \le n$$$ is the row number,
• $$$1 \le y \le n$$$ is the column number.

The snake initially consists of a single cell:

• Head position: $$$(1, 1)$$$,
• Initial length: $$$1$$$.

Moves

You are given a string $$$s$$$ of length $$$k$$$. Each character represents a move:

• L: $$$(x, y) \rightarrow (x, y - 1)$$$
• R: $$$(x, y) \rightarrow (x, y + 1)$$$
• U: $$$(x, y) \rightarrow (x - 1, y)$$$
• D: $$$(x, y) \rightarrow (x + 1, y)$$$

Wrapping

The grid is toroidal. If the head moves outside the grid, it reappears on the opposite side:

• If $$$y = 0$$$, then $$$y = n$$$,
• If $$$y = n + 1$$$, then $$$y = 1$$$,
• If $$$x = 0$$$, then $$$x = n$$$,
• If $$$x = n + 1$$$, then $$$x = 1$$$.

Food

There are $$$m$$$ foods given in a fixed order at positions $$$(x_i, y_i)$$$.

• Initially, only food $$$1$$$ is present on the grid.
• When the snake eats food $$$i$$$:
  • the snake's length increases by $$$1$$$,
  • food $$$i+1$$$ immediately appears (if $$$i \lt m$$$).
• At any moment, at most one food exists on the grid.
• A food is eaten if after a move the snake's head lands exactly on the current food cell.

Snake Movement

Each move is processed as follows:

1. The head moves by one cell (with wrapping).
2. If the head lands on the current food cell:
   • the snake grows (the tail does not move in this step).
3. Otherwise:
   • the snake keeps the same length (the tail moves forward by one cell).

Death Rule

The snake dies if after moving, its head occupies a cell that is currently part of its body. If the snake does not eat during this move, moving into the current tail cell is allowed, because the tail leaves at the same time.

Task

Simulate the game for at most $$$k$$$ moves.

• If the snake dies before completing all moves, output DEAD.
• Otherwise, output ALIVE L, where $$$L$$$ is the final length of the snake.