As per tradition, we are collecting your favorite phrases!

However, this time, there are some rules. Christian particularly likes phrases that have exactly $$$n$$$ space-free substrings — substrings that don't contain the space character. For example, the phrase "$$$\mathrm{Hey \; yo}$$$" has $$$9$$$ space-free substrings: $$$\mathrm{Hey}$$$, $$$\mathrm{He}$$$, $$$\mathrm{ey}$$$, $$$\mathrm{H}$$$, $$$\mathrm{e}$$$, $$$\mathrm{y}$$$, as well as $$$\mathrm{yo}$$$, $$$\mathrm{y}$$$, and $$$\mathrm{o}$$$.

If one space-free substring appears multiple times, it is counted that many times. In other words, we count the total number of space-free substrings, not the number of unique space-free subtrings.

Given a positive integer $$$n$$$, output a phrase with exactly $$$n$$$ space-free substrings.

For an array $$$a$$$ of length $$$n$$$, we define the aura of the array to be the number of indices $$$i$$$ ($$$1 \leq i \leq n-1$$$) such that at least one of the following conditions holds:

• $$$a_i = 6$$$ and $$$a_{i+1} = 7$$$
• $$$a_i = 7$$$ and $$$a_{i+1} = 6$$$

You are given an array $$$a$$$ of length $$$n$$$. You may perform the following operation any number of times:

• Choose an index $$$i$$$ ($$$1 \leq i \leq n-1$$$) and swap the elements $$$a_i$$$ and $$$a_{i+1}$$$ in the array $$$a$$$.

After performing the operation some number of times (possibly zero), you would like to know the maximum possible aura of the resulting array $$$a$$$.

You are given an array of $$$n$$$ positive integers and $$$q$$$ queries.

On each query, you are given a positive integer $$$x$$$. You need to output $$$\max\limits_{i=1}^n \left[\mathrm{lcm}{(x, a_i)} \right]$$$.

In other words, what is the maximum least common multiple of $$$x$$$ with any number from $$$a$$$?

You originally joined Columbia Space Initiative to build and program rockets, but ever since Columbia Housing colonized a distant planet and finished a set of new constructions, your duties have been reassigned. You are about to board the spaceship to the new planet, Carlton Legs, when you remember you'll need to buy metal house numbers to affix to the front of your new house (so it can be identified for maintenance). Unfortunately, the 250 light-year journey back is reserved for Columbia Housing staff, so you'll need to buy your house numbers before you leave.

You know that there are only $$$n$$$ houses on the planet, numbered from $$$1$$$ to $$$n$$$, but you aren't sure which one you've been assigned. University Hardware sells individual metal digits $$$0$$$–$$$9$$$ for $$$1$$$ dollar apiece, with an infinite supply of each digit, and you can buy as many digits as necessary to label your house. What is the minimal amount you must spend to ensure that, regardless of which house number you are assigned, you'll be able to label your house using the digits you bought?

The next season of Squid Game is about to begin! The Frontman put you in charge of the third game of the season, Mingle.

Mingle is defined by an initial number of players $$$p$$$, the number of safe rooms $$$m$$$, and a sequence of $$$k$$$ positive integers $$$b_1, \ldots, b_k$$$.

The game consists of $$$k$$$ rounds. In the $$$i$$$-th round, the remaining players need to form teams of size exactly $$$b_i$$$, and each team must hide in one of the $$$m$$$ safe rooms. Each safe room admits at most one team. If a player doesn't join a team of size $$$b_i$$$, or their team doesn't hide in a safe room, they are eliminated.

All players who survive the $$$i$$$-th round advance to the next, $$$i+1$$$-th round. Teams may change arbitrarily between rounds. Players who have made it past round $$$k$$$ are declared the winners of Mingle.

The Frontman is interested in computing the maximum possible number of winners in the game. However, since neither the initial number of players nor the sequence itself has been determined yet, you need to answer multiple queries about the game.

At the start, you are given a sequence $$$a$$$ of size $$$n$$$ and the number of safe rooms $$$m$$$, fixed for all queries. Then, $$$q$$$ queries follow. Each query is one of two types:

• $$$1 \; i \; x$$$ ($$$1 \leq i \leq n$$$, $$$1 \leq x \leq 10^9$$$) — update $$$a_i := x$$$.
• $$$2 \; l \; r \; p$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq p \leq 10^9$$$) — what is the maximum number of winners in Mingle played on the sequence $$$a_l, a_{l+1}, \ldots, a_r$$$ with $$$m$$$ safe rooms and $$$p$$$ initial players?

For each query of type $$$2$$$, output the maximum possible number of winners. Note that queries of type $$$2$$$ are independent from each other.

The NYPD is making a plan for patrolling a neighborhood of Manhattan.

The neighborhood can be represented by a $$$n \times m$$$ grid of square blocks with coordinates from $$$(1, 1)$$$ to $$$(n, m)$$$. Each block is patrolled by one particular officer. For training purposes, every once in a while the NYPD wants to change assignments of officers to blocks. However, to maintain the existing cooperations, they want to preserve the Manhattan distance between each pair of officers.

More formally, let $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ be the initial coordinates of two officers, and $$$(x_1', y_1')$$$ and $$$(x_2', y_2')$$$ be their final coordinates after reassignment. Then, the following must hold: $$$|x_1-x_2|+|y_1-y_2| = |x_1'-x_2'| + |y_1'-y_2'|$$$.

How many possible assignments of officers to blocks are there which preserve the pairwise Manhattan distances?

Two assignments are considered different if some officer is moved to a different block. The officers are allowed to stay in original positions. Since the answer might be large, output its remainder modulo $$$998244353$$$.

The students at Rubgers University are organizing a programming contest. Since a lot of strong teams will participate, they expect some of them to solve all problems. To distinguish between them, a special prize will be awarded to the team with a special solve order.

The contest consists of $$$N \leq 26$$$ problems labelled $$$\mathrm{A}$$$, $$$\mathrm{B}$$$, etc: the first $$$N$$$ letters of the English alphabet.

A solve order for a team is a sequence of letters denoting the order in which it solved all the problems: e.g., for $$$N=3$$$, a possible solve order is $$$\mathrm{BAC}$$$ — $$$\mathrm{B}$$$ solved first, then $$$\mathrm{A}$$$, then $$$\mathrm{C}$$$. We only consider teams which solve every problem exactly once, so, e.g., $$$\mathrm{AC}$$$ or $$$\mathrm{ABAC}$$$ are not valid solve orders.

Solve order $$$a$$$ is lexicographically smaller than solve order $$$b$$$ if, at the first position where they differ, the character in $$$a$$$ comes in the alphabet before the character in $$$b$$$. E.g., $$$\mathrm{ACB}$$$ is lexicographically smaller than $$$\mathrm{BAC}$$$, which is lexicographically smaller than $$$\mathrm{BCA}$$$.

Consider all possible solve orders of the $$$N$$$ problems. Let their number be $$$M$$$. Sort the $$$M$$$ solve orders from lexicographically smallest to largest. In this list, the median solve order is located at position $$$\lceil \frac{M}{2} \rceil$$$ ($$$\frac{M}{2}$$$ rounded up).

Any team with the median solve order will get a special prize. Help Rubgers students decide what the order is!

You are given an undirected graph. You must color each vertex of the graph in such a way that the following two conditions are met:

• There is no monochromatic cycle$$$^*$$$ in the graph, i.e., there is no cycle whose vertices are all of the same color.
• For each pair of distinct colors $$$c_1$$$, $$$c_2$$$ that appear in the graph, there exists a bichromatic cycle with colors $$$c_1$$$ and $$$c_2$$$, i.e., there is a cycle that contains at least one vertex of color $$$c_1$$$, at least one vertex of color $$$c_2$$$, and no vertices of any other color.

Report whether or not it is possible to do so, and, if it is, provide a valid coloring.

$$$^*$$$ A cycle in a graph is a list of distinct vertices $$$(v_1, \ldots, v_c)$$$, where $$$c \geq 3$$$, such that for all $$$1 \leq i \lt c$$$ there is an edge between vertices $$$v_i$$$ and $$$v_{i+1}$$$, and there is also an edge between $$$v_c$$$ and $$$v_1$$$.

This is an interactive problem.

The Entomology department at Columbia wants to expand its colony of ants.

The colony currently consists of $$$n$$$ male and $$$n$$$ female ants, each numbered $$$1$$$ through $$$n$$$. The scientists want to find a female ant to mate with each male ant. Since ants are polyandrous, one female can mate with multiple males at once.

Two ants can mate only if they are attracted to each other. One male ant may be attracted to multiple female ants, and vice versa.

To find which pairs of ants are attracted to each other, the scientists can run experiments with the aid of an AI (Ant Inspection) tool by Ant-ropic. In one experiment, they take $$$x$$$ male ants and $$$y$$$ female ants, and place them in a cell. The AI observes their behaviour and reports one pair of ants which are attracted to each other, or that none exist. The cost of this experiment is $$$x + y$$$ dollars.

More formally, you can make the following queries to the interactor:

• "? $$$x \; i_1 \; i_2 \ldots i_x \; y \; j_1 \; j_2 \; \ldots j_y$$$" — run the experiment on male ants $$$i_1, i_2, \ldots, i_x$$$ and female ants $$$j_1, j_2, \ldots, j_y$$$. The interactor replies with some pair of attracted ants "$$$i_k \; j_\ell$$$", meaning that $$$i_k$$$-th male ant can mate with $$$j_\ell$$$-th female ant, or "$$$-1 \; -1$$$" if no such pair exists. The same pair may be reported in multiple experiments. The cost of this query is $$$x + y$$$ dollars.

After running some experiments, the scientists need to report, for each male ant, which female ant it can mate with, or $$$-1$$$ if no such ant exists. Since the scientists are on a budget, the total cost of all experiments may not exceed $$$35 \, 000$$$ dollars.

To make a query, output a line (without quotes) in the following format:

• "? $$$x \; i_1 \; i_2 \ldots i_x \; y \; j_1 \; j_2 \; \ldots j_y$$$" ($$$1 \leq x, y \leq n$$$, $$$1 \leq i_1, i_2, \ldots i_x \leq n$$$, $$$1 \leq j_1, j_2, \ldots j_y \leq n$$$).

After each query, read two space-separated integers — the answer to the query. If an attracted pair exists, the answer will be "$$$i_k \; j_\ell$$$" for some $$$k$$$ and $$$\ell$$$ ($$$1 \leq k \leq x$$$, $$$1 \leq \ell \leq y$$$), indicating the attracted pair. Otherwise, the answer will be "$$$-1 \; -1$$$".

The cost of this query is $$$x + y$$$.

The total cost of all queries must not exceed $$$35 \, 000$$$.

An answer to the problem is a sequence $$$p_1, p_2, \ldots, p_n$$$, where $$$p_i$$$ is the index of a female ant with which the $$$i$$$-th male ant can mate, or $$$-1$$$ if no such ant exists.

Once you have determined an answer to the problem, print the line (without quotes) in the following format:

• "! $$$p_1 \; p_2 \ldots p_n$$$" ($$$p_i = -1$$$ or $$$1 \leq p_i \leq n$$$)

If there are multiple correct answers, output any.

After this, terminate the program.

The interactor in this task is not adaptive. In other words, the pairs of attracted ants do not change throughout the interaction.

If you make queries of total cost more than $$$35 \, 000$$$, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing each line, do not forget to output the end of line and flush the output buffer. Otherwise, you will receive the Idleness Limit Exceeded verdict. To flush, use:

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

It is a sunny day on Columbia campus, and Alice and Bob decide to go to Butler Lawns to play their favorite game: Permutation Game. Since the weather is so nice, Alice wants to stay on the lawns as long as possible, while Bob has a midterm the next day and wants to get home to study.

Permutation Game is played as follows:

1. Alice receives a permutation $$$a$$$ and Bob receives a permutation $$$b$$$, both of size $$$n$$$$$$^{\text{∗}}$$$.
2. Alice chooses an index $$$i$$$ ($$$1 \leq i \leq n$$$) and places a token on position $$$i$$$ of her permutation $$$a$$$.
3. Bob, after seeing where Alice has placed her token, chooses an index $$$j$$$ ($$$1 \leq j \leq n$$$) and places his own token on position $$$j$$$ of his permutation $$$b$$$.
4. Alice and Bob each follow their permutation one step at a time:
   • Alice moves her token to index $$$a_i$$$, then $$$a_{a_i}$$$, and so on.
   • Bob moves his token to index $$$b_j$$$, then $$$b_{b_j}$$$, and so on.
   This process continues until both tokens return to their respective starting indices after a step is performed.

For an array of integers $$$a$$$, a triplet of elements is defined by 3 distinct indices $$$(a_i, a_j, a_k)$$$, and their order does not matter.

Consider the triplets from $$$a$$$ that sum to zero.

For example, the array $$$a = [1, 1, 1, 2, -2, 0]$$$ has $$$4$$$ triplets that sum to zero: $$$(a_1, a_2, a_5)$$$, $$$(a_1, a_3, a_5)$$$, $$$(a_2, a_3, a_5)$$$, and $$$(a_4, a_5, a_6)$$$.

Given an integer $$$k$$$, construct an array of integers $$$a$$$ such that exactly $$$k$$$ triplets of elements from $$$a$$$ sum to zero.

Your array must have size at most $$$5000$$$.

You are given $$$n$$$ points on a plane. Find the largest area triangle or quadrilateral with vertices at some of these points.

One week before the contest, CULC organizers learned that a certain highly rated coder will participate. In shock, they quickly opened TaskGPT, and, with trembling fingers, typed: