You have a toy consisting of $$$n$$$ sticks of varying lengths connected in order in a row by hinges. The sticks can be rotated arbitrarily around the hinges and are allowed to overlap.

You want to create an arch with these sticks. To do this, you will place the two endpoints of the structure anywhere on the surface of a table and position the rest of the sticks and hinges arbitrarily. You can ignore gravity and assume the sticks and hinges have zero width. Sticks are allowed to overlap and/or intersect with each other but may not intersect with the table. Note that the order of the sticks is fixed and cannot be changed. One possible arch is shown here:

You want to maximize the height of the arch, defined as the maximum distance from the surface of the table to a point on the arch (this is shown as the dotted red line above). What is the maximum height you can achieve?

You are given an integer $$$n$$$. In one operation, you can split the digits of $$$n$$$ into two nonempty parts and replace $$$n$$$ with their sum. For example, if $$$n=12526$$$, you could split it into $$$125$$$ and $$$26$$$ and set $$$n = 125 + 26 = 151$$$, or if $$$n=10001$$$, you could split it into $$$1$$$ and $$$0001$$$ and set $$$n=1 + 0001 =2$$$.

If you can perform this operation any number of times (including zero), what is the minimum $$$n$$$ you can achieve?

There is a hidden positive integer $$$k$$$ that has exactly $$$n$$$ divisors. These divisors were put into an array $$$a$$$ which was then shuffled into a hidden order.

You can ask the interactor questions of the form ? i j, and you will receive the position of $$$\gcd(a_i, a_j)$$$ in $$$a$$$. Note that since $$$a$$$ contains all divisors of $$$k$$$, this value is guaranteed to exist and be unique.

Using at most $$$3n$$$ queries, determine which indices of $$$a$$$ contain prime numbers.

After reading in $$$n$$$, you can make up to $$$3n$$$ queries.

For each query, print a line of the form ? i j ($$$1 \le i, j \le n$$$).

After printing the query, you can then read in an integer $$$x$$$, where $$$a_x = \gcd(a_i, a_j)$$$.

Once you have determined which indices contain prime numbers, print a single line ! m p_1 p_2 ... p_m ($$$0 \le m \le n$$$, $$$1 \le p_i \le n$$$, where $$$m$$$ is the number of prime factors and $$$p_1$$$ through $$$p_m$$$ are their positions in $$$a$$$. This is not counted towards your total of $$$3n$$$ queries.

After printing a query do not forget to output the end of 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;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

The interactor is non-adaptive. This means that the array $$$a$$$ is fixed at the start of the interaction, and does not change after the queries.

You have a set $$$S$$$ containing the first $$$n$$$ powers of $$$2$$$. However, Thomas tampered with your set and negated some of its values. For example, for $$$n=4$$$, $$$S = \{1, 2, 4, 8\}$$$, and Thomas could negate the $$$2$$$ and $$$4$$$ to turn $$$S$$$ into $$$\{1, -2, -4, 8\}$$$.

You are given a positive integer $$$k$$$. Express $$$k$$$ as the sum of some subset of $$$S$$$, or state that this is impossible.

There is an infinite grid of squares. The squares at positions $$$(0, 0)$$$ through $$$(n-1, 0)$$$ are then colored red, blue, or green. You want to color additional squares such that for each of the three colors, the subset of squares of that color is connected, where two squares are considered connected if they share an edge.

In other words, for every pair of squares of the same color $$$c$$$, it should be possible to travel from one to the other, moving only through squares of color $$$c$$$ that share an edge.

Find a solution that colors at most $$$10^6$$$ additional squares (not including the squares that are currently present), or determine that there is no solution. It can be shown that under the given constraints, if there is a solution, there is one using at most $$$10^6$$$ additional squares.

You do not need to minimize the number of additional squares.

There is a permutation$$$^\dagger$$$ $$$p$$$ of size $$$n$$$ that you are trying to sort. To do so, you may perform up to $$$20$$$ operations of the following form:

• Select a subset of distinct indices $$$i_1, i_2, \cdots i_k$$$ such that the value of $$$p_{i_1} \oplus p_{i_2} \oplus \cdots \oplus p_{i_k}$$$, where $$$\oplus$$$ represents the bitwise XOR operation, is zero.
• Sort the values of $$$p$$$ on indices $$$i_1, i_2, \cdots i_k$$$.

For example, for $$$p = [7, 3, 4, 1, 2, 6, 5]$$$, you could choose the indices $$$[2, 4, 5]$$$, since $$$p_2 \oplus p_4 \oplus p_5 = 1 \oplus 2 \oplus 3 = 0$$$. After this operation, $$$p$$$ would be equal to $$$[7, 1, 4, 2, 3, 6, 5]$$$.

It can be shown that if it is possible to sort the permutation in any number of operations, then it is possible in at most $$$20$$$.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2, 3, 1, 5, 4]$$$ is a permutation, but $$$[1, 2, 2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1, 3, 4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

You are a member of the Rutgers Programming Contest problemsetting team, and you have just come up with a new problem for the Spring 2025 contest. However, you realized you're not yet sure how to write the judge program for this problem. Your task now is to implement that judge.

Define a number $$$b$$$ to be a subsequence of a number $$$a$$$ if, when you write out $$$a$$$ in decimal notation, you can erase some (but not all) of its digits so that the remaining digits, in order, form $$$b$$$. For example, $$$356$$$ is a subsequence of $$$1234567$$$, because you can erase the $$$1$$$, $$$2$$$, $$$4$$$, and $$$7$$$ to form $$$356$$$. However, $$$0$$$ is not a subsequence of $$$23527$$$, because the digit $$$0$$$ is not present in $$$23527$$$.

The problem you have just come up with requires the user to construct an integer $$$n$$$ such that the $$$\operatorname{MEX}$$$ of its subsequences is the input number $$$x$$$. Therefore, the judge program should read an integer $$$n$$$ from the user and compute the $$$\operatorname{MEX}$$$ of its subsequences, so that value can then be compared against the original input $$$x$$$.

The $$$\operatorname{MEX}$$$ of a set of integers is defined as the smallest non-negative integer which does not occur in the set. For example, the $$$\operatorname{MEX}$$$ of $$$\{0, 1, 2, 4\}$$$ is $$$3$$$, and the $$$\operatorname{MEX}$$$ of $$$\{1, 4, 6, 8\}$$$ is $$$0$$$.

You are given a directed graph. For each vertex $$$v$$$, you can remove up to half of the edges directed away from $$$v$$$. Formally, if there are $$$x$$$ edges directed away from $$$v$$$, you can remove up to $$$\lfloor \frac{x}{2} \rfloor$$$ of them. Remove edges in such a way that vertex $$$n$$$ is not reachable from vertex $$$1$$$ or state that this is impossible.

For example, in the below graph, one solution is to remove the three red edges. Note that no vertex has more than half of the edges directed away from it colored red.

There is an $$$n$$$ by $$$n$$$ grid of white squares, each containing a bidirectional horizontal or vertical arrow. In one operation, you can choose any square, and based on the arrow in that square, color all squares in the corresponding row or column black. For example, here is one possible sequence of two operations on a grid with $$$n=4$$$:

What is the minimum number of operations needed to color all squares black, and which squares should you choose in the operations?

A lattice triangle is a triangle in the plane whose vertices have integer coordinates. You are given a lattice triangle $$$S$$$. How many lattice triangles $$$T$$$ contain a vertex of $$$S$$$ on each of their sides, without sharing any vertices with $$$S$$$?

A suspicious string is a string of the form s$$$^n$$$u$$$^n$$$s$$$^n$$$ for $$$n \gt 0$$$. In other words, a suspicious string is made up of $$$n$$$ copies of the letter s, followed by $$$n$$$ copies of the letter u, and then another $$$n$$$ copies of the letter s. So sus and sssuuusss are examples of suspicious strings, but suuus and sssuus are not.

A chain of suspicion is a concatenation of zero or more suspicious strings. For example, the empty string, sus, and susssuusssus are chains of suspicion, and susus and sssusss are not.

Given a string $$$t$$$ consisting of the letters s and u, print the length of the longest (possibly empty) substring that is a chain of suspicion.

The Rutgers scientific committee members don't like magic, and by extension, they don't like magic squares either. Thus, they like to construct grids of numbers that completely go against the principles of magic squares. Here is how they do it.

They start with an $$$n \times n$$$ grid of cells, and in each cell they put an integer from the range $$$[1, 4]$$$. The numbers are chosen such that the set formed by taking the $$$2n$$$ row and column sums consists of $$$2n$$$ distinct values (diagonal sums are not considered).

Given an integer $$$n$$$, your task is to construct an $$$n \times n$$$ grid according to the above rules. It can be proven that such a grid always exists.

Suppose we have a graph $$$G$$$ with vertex set $$$V$$$. A straight-line embedding of $$$G$$$ is a rendition of $$$G$$$ in 3D space such that the edges are straight line segments which do not intersect except possibly at their endpoints.

Formally, a function $$$f: V \to \mathbb{R}^3$$$ is called a straight-line embedding of $$$G$$$ if it satisfies the following conditions:

• $$$f$$$ is injective; that is, $$$f(u) \neq f(v)$$$ when $$$u \neq v$$$.
• For any pair of edges $$$(a, b)$$$ and $$$(c, d)$$$ in $$$G$$$, the line segment from $$$f(a)$$$ to $$$f(b)$$$ and the line segment from $$$f(c)$$$ to $$$f(d)$$$ do not intersect, except possibly by endpoints coinciding. In other words, no point of one segment may be in the interior of another segment.

Next, for $$$n \gt 0$$$, consider the cube of all points in $$$\mathbb{R}^3$$$ whose coordinates are in $$$[0, n+1]$$$. Denote this cube by $$$C_n$$$.

You are given a simple undirected graph $$$G$$$ (not necessarily connected) with vertices numbered $$$1$$$ through $$$n$$$ and the guarantee that for all vertices $$$v$$$, $$$v$$$ has degree at most $$$3$$$. Your task is to construct a straight-line embedding $$$f$$$ of $$$G$$$ such that for each $$$v$$$, the coordinates of $$$f(v)$$$ are all integers, and $$$f(v)$$$ lies on one of the 12 line segments comprising the edges of $$$C_n$$$.

It can be shown that, given the degree restriction on the vertices of $$$G$$$, such an embedding always exists.

You are given a zero-indexed array $$$a$$$ of size $$$2^k$$$. For each $$$x$$$ from $$$0$$$ through $$$2^k-1$$$, consider the array $$$b_x$$$ where $$$(b_x)_i = a_{i \oplus x}$$$, where $$$\oplus$$$ denotes the bitwise XOR operator. Note that because $$$a$$$ is of size $$$2^k$$$ and is zero-indexed, this array is well-defined.

Given an array $$$c$$$ of size $$$n$$$, let $$$\texttt{inv}(c)$$$ denote the number of inversions in $$$c$$$, in other words, the number of pairs $$$(i, j)$$$ where $$$0 \le i \lt j \lt n$$$ and $$$c_i \gt c_j$$$.

Your task is to compute $$$\sum_{x=0}^{2^k-1} \texttt{inv}(b_x)$$$.

You are given an integer $$$n$$$. Construct any string $$$s$$$ that has exactly $$$n$$$ distinct nonempty substrings. It can be shown that such a string always exists.

A string $$$t$$$ is a substring of a string $$$s$$$ if $$$t$$$ can be obtained from $$$s$$$ by the deletion of several (possibly zero) characters from the beginning and several (possibly zero) characters from the end.

For example, the string $$$aba$$$ has $$$5$$$ distinct nonempty substrings — $$$a$$$, $$$b$$$, $$$ab$$$, $$$ba$$$, and $$$aba$$$.