Othman is a lazy student who relies entirely on leaked exam statistics to pass his high school national exams with a high score.

This morning, Othman is taking his final Biology exam, which consists of $$$100$$$ multiple-choice questions. Each question has four possible choices: a, b, c, and d.

By pure luck (or so he claims), Othman found out that among the $$$100$$$ questions, exactly $$$A$$$ questions have the correct answer a, $$$B$$$ questions have the correct answer b, $$$C$$$ questions have the correct answer c, and $$$D$$$ questions have the correct answer d. However, he has no idea which specific answer belongs to which question.

To make use of this information, Othman decides to mark exactly $$$A$$$ questions as a, $$$B$$$ questions as b, $$$C$$$ questions as c, and $$$D$$$ questions as d on his answer sheet.

Help Othman determine the maximum number of questions he is guaranteed to answer correctly, regardless of how the actual correct answers are arranged.

Omar left his home for 14 years because of the war in Syria.

He has a favorite array $$$a$$$ of size $$$n$$$.

Before he left, he used to do the following process:

• Consider all possible triples of indices $$$(i, j, k)$$$ with $$$1 \le i \lt j \lt k \le n$$$.
• For each triple, he takes the three values $$$a_i$$$, $$$a_j$$$, $$$a_k$$$, sorts them, and writes down the median (the middle element) on a piece of paper.
• He does this for every triple, in some random order.

After returning home, he found that his array was lost due to the destruction. However, he managed to find the paper where he had written all the medians.

But the paper is damaged — some numbers may be incorrect. Omar is not sure if the information on the paper is valid or not.

Given the size $$$n$$$ and a multiset of $$$\binom{n}{3}$$$ numbers (the numbers written on the paper), your task is to determine whether there exists any array $$$a$$$ of size $$$n$$$ such that the multiset of medians of all triples of indices matches exactly the given multiset.

Here $$$\binom{n}{3}$$$ denotes the binomial coefficient, which is the number of triples of distinct indices from $$$n$$$ indices:

$$$$$$ \binom{n}{3} = \frac{n(n-1)(n-2)}{6} $$$$$$

For example, $$$\binom{4}{3} = 4$$$, $$$\binom{5}{3} = 10$$$, and $$$\binom{6}{3} = 20$$$.

Tomeh always boasts "Strings are my playground"

yet he never manages to solve the problems without resorting to overkill.

To prove that simplicity is the true mark of mastery: Given a string $$$s$$$, write a program that outputs the frequency count of the most frequent substring$$$^\dagger$$$ within $$$s$$$, without using tomeh's overkill power.

This is an interactive problem.

After the war in T-Land ended, the people were divided into three groups:

• The fighters who liberated the country, called Thowwar, denoted by the letter T.
• The supporters of the previous regime despite all of its crimes, called Floul, denoted by the letter F.
• People with no opinion or clear identity, called Mkaw3, denoted by the letter M.

There are $$$n$$$ people in the waiting room. Your task is to determine the type of every person.

Fortunately, you can ask Abu Dujana for help. He is able to identify people's apparent identities by simply looking at them.

You may perform the following operation any number of times:

• Choose exactly $$$k$$$ ($$$2 \le k \le n$$$) people and send them into Abu Dujana's inspection room.
• Their behavior is as follows:
  • Every Thowwar remains a Thowwar.
  • Every Floul remains a Floul.
  • If a Mkaw3 does not find any Thowwar inside the room, they feel safe and return to their original nature as a Floul.
  • Otherwise, if there is at least one Thowwar in the room, every Mkaw3 immediately starts singing "Labat Labat" and successfully fools Abu Dujana into thinking they are a Thowwar.

Formally, let the chosen group contain $$$T$$$ Thowwar, $$$F$$$ Floul, and $$$M$$$ Mkaw3. Abu Dujana returns a single integer:

• If $$$T = 0$$$, Abu Dujana returns $$$0$$$.
• Otherwise, Abu Dujana returns $$$T + M$$$.

Determine the type of every person while using at most 812 operations (in honor of 8/12, T-Land Liberation Day).

It is guaranteed that among the $$$n$$$ people there is at least one Thowwar, at least one Floul and at least one Mkaw3.

The first line of the input contains a single integer $$$n$$$ ($$$3 \le n \le 400$$$) — the number of people.

To ask a query, print a line in the following format:

? k i1 i2 ... ik

where $$$2 \le k \le n$$$, all indices are distinct, and $$$1 \le i_j \le n$$$.

After printing a query, flush the output and read a single integer $$$x$$$.

Suppose the chosen group contains:

• $$$T$$$ Thowwar,
• $$$F$$$ Floul,
• $$$M$$$ Mkaw3een.

The interactor responds as follows:

• If $$$T = 0$$$, it returns $$$0$$$.
• Otherwise, it returns $$$T + M$$$.

You may ask at most 812 queries.

When you have determined the type of every person, print

! s

where $$$s$$$ is a string of length $$$n$$$, and the $$$i$$$-th character is:

• T if the $$$i$$$-th person is a Thowwar;
• F if the $$$i$$$-th person is a Floul;
• M if the $$$i$$$-th person is a Mkaw3.

After printing the answer, terminate your program immediately.

Your program will receive the verdict Wrong Answer if it asks more than $$$812$$$ queries or prints an invalid query.

Remember to flush the output after every query. For example, use:

• fflush(stdout) in C/C++;
• System.out.flush() in Java;
• stdout.flush() in Python;
• flush(output) in Pascal.

Khaled and Saleem spent months building a complex logistics network, but everything crashed right on launch day. Watching the servers collapse on the screen, Saleem slammed his hand on the desk and shouted: "Mesh mante2 ya zalame!"

To salvage what they could, Khaled realized they had to track and identify the good vertices in their directed network to correct the system's routing and avoid bankruptcy.

Their network is represented as a directed graph containing $$$N$$$ vertices and $$$M$$$ edges and dosen't have self loops or multiple edges, and they have a constant factor $$$K$$$ that controls the routing cycles.

Due to continuous failures, the system faces $$$Q$$$ queries to test the network. In each query, you are given a subset $$$S$$$ of vertices of size $$$c$$$, along with two integers $$$a$$$ and $$$b$$$.

For each query and for each vertex $$$v$$$ in the graph, we define two values:

• $$$cnt_1$$$: is the number of vertices $$$u$$$ in $$$S$$$ such that there is at least one directed walk$$$^\dagger$$$ from $$$u$$$ to $$$v$$$ of length $$$L_1$$$ satisfying $$$L_1 \equiv a \pmod K$$$.
• $$$cnt_2$$$: is the number of vertices $$$u$$$ in $$$S$$$ such that there is at least one directed walk from $$$u$$$ to $$$v$$$ of length $$$L_2$$$ satisfying $$$L_2 \equiv b \pmod K$$$.

For each query, help Khaled and Saleem find the number of good vertices to bring the system back online and prove that things can return to making logical sense.

You are given an array $$$A$$$ of size $$$N$$$.

You have to answer $$$Q$$$ queries. Each query consists of two integers $$$l$$$ and $$$r$$$.

For each query, count the number of contiguous subarrays that satisfy both of the following conditions:

• The length of the subarray is exactly $$$r-l+1$$$.
• Every integer in the range $$$[l, r]$$$ appears exactly once in the subarray.

In other words, the elements of the subarray form a permutation of the integers $$$l, l+1, \ldots, r$$$.

While most of the world spends their time in disputes about ($$$7as$$$ or $$$3rr$$$), (i64 or ll), (VS Code or Geany), a baby lives a peaceful life, saying only one word: "AGUAGU".

Now, the troublemakers want to discover the baby's bias.

They ask him a single question: is he $$$7as$$$ or $$$3rr$$$? The baby responds with the only word he knows: "AGUAGU".

After finally replacing his old MacBook with a gaming laptop, Tomeh has become addicted to video games, just as everyone expected.

He is currently playing The Great Hall. The game is represented by a string $$$t$$$ and consists of $$$k$$$ consecutive stages.

At the end of the $$$i$$$-th stage ($$$1 \le i \le k$$$), Tomeh encounters the boss of that stage. To let him pass, the boss gives him exactly one of the following choices:

• Pay exactly $$$i$$$ gold coins.
• Present any palindromic substring of string $$$t$$$ whose length is exactly $$$i$$$.

As a true "Shami", Tomeh will not spend a single coin unless he is absolutely forced to.

You are given a string $$$s$$$, an integer $$$k$$$, and $$$q$$$ queries.

Each query consists of two integers $$$l$$$ and $$$r$$$. Let $$$t = s[l \dots r]$$$ denote the corresponding substring of $$$s$$$.

For each query, determine the minimum total number of gold coins Tomeh must pay to clear all $$$k$$$ stages of the game played on the string $$$t$$$.

Khaled and his brother are having an intense Mortal Kombat match. Determined to secure a "Flawless Victory" and leave his brother no room to breathe, Khaled decides to unleash a relentless chain of special moves.

In this game, the combo system is represented as a rooted tree consisting of $$$n$$$ nodes, where node $$$1$$$ is the root. Each node $$$i$$$ has a specific button assigned to it, represented by a lowercase English letter $$$c_i$$$.

To execute the special move associated with node $$$x$$$, a player must input the exact sequence of buttons along the simple path from the root to node $$$x$$$. Let this string of button presses be $$$S_x$$$.

For his ultimate attack, Khaled wants to execute two special moves, $$$u$$$ and $$$v$$$, in a single rapid string of inputs. A sequence of button presses is considered valid if both $$$S_u$$$ and $$$S_v$$$ are contiguous substrings$$$^\dagger$$$ of this sequence(they can overlap).

Since Khaled wants to execute the attack as quickly as possible, he needs your help to determine the minimum number of button presses required to perform both moves. You are given $$$q$$$ queries, each consisting of two nodes $$$u$$$ and $$$v$$$.For each query, output the minimum length of a valid button sequence.

————————————————————————

$$$^\dagger$$$A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

One day, Hosen found a massive, incredibly heavy tree with $$$n$$$ nodes. The tree was special: each node had a value $$$a_i$$$ written on it, forming a permutation of integers from $$$0$$$ to $$$n-1$$$.

Without warning, Hosen threw the giant tree right into Rasoulo's arms!

"Hold the tree! Don't let it fall!" Hosen shouted as he started running away. "I am going to get us some shawarma. I will calculate its paths when I get back!"

Now, Rasoulo is stuck holding the tree. His arms are shaking, his back hurts, and he is sweating. The tree is so heavy! He desperately wants to put it down. To finish the task before his arms completely give out, Rasoulo decides to calculate the answer himself.

For any simple path between node $$$u$$$ and node $$$v$$$ ($$$u \lt v$$$), we define:

• The length of the path as the number of edges between $$$u$$$ and $$$v$$$.
• The MEX of the path as the smallest non-negative integer that does not appear on any node along the path.

Rasoulo wants to calculate the total sum of $$$F(u, v)$$$ for all valid pairs of nodes $$$(u, v)$$$ such that $$$u \lt v$$$, where: $$$$$$F(u, v) = \text{length}(u, v) \times \text{MEX}(u, v)$$$$$$

Since the answer can be very large, print it modulo $$$10^9 + 7$$$. Can you help Rasoulo calculate the answer so he can finally drop the tree?

Homsi had a strange dream involving two positive integers $$$k$$$ and $$$b$$$.

In his dream, he saw a strictly increasing infinite array $$$a$$$ such that for every non-negative integer $$$x$$$, there exist exactly one ordered tuple of indices $$$i_1, i_2, \ldots, i_k$$$ (where the indices are not necessarily distinct and are not required to be in non-decreasing order) satisfying

$$$$$$x = a_{i_1} + b \cdot a_{i_2} + b^2 \cdot a_{i_3} + \cdots + b^{k-1} \cdot a_{i_k}$$$$$$

In other words, every non-negative integer has a unique representation of the above form.

After waking up, Homsi told his friends about the dream. Hussain doubted that such an array could even exist, so he challenged Homsi with the following task.

For each test case, given the integers $$$b$$$, $$$k$$$, $$$l$$$, and $$$r$$$, determine the value of $$$a_l + a_{l+1} + \cdots + a_r$$$ modulo $$$10^9+7$$$.

If no array satisfying the required property exists, output -1.

Due to severe destruction in Syria, many residents have fled and left their homes empty. The thief Hamoosh takes advantage of this to steal iron from the abandoned buildings, but the policeman Homsi spots him and initiates a pursuit.

There are $$$N$$$ buildings arranged in a circle, numbered $$$1$$$ to $$$N$$$ in clockwise order. For $$$1\le i \lt N$$$, the building following building $$$i$$$ is $$$i+1$$$, and the building following building $$$N$$$ is $$$1$$$. The $$$i$$$-th building contains $$$W_i$$$ units of iron.

You must choose the initial starting building for Hamoosh and the initial starting building for Homsi. At time $$$0$$$, both are placed on their respective starting buildings. In each turn, they move simultaneously in the clockwise direction: Hamoosh jumps forward by exactly $$$A$$$ buildings, and Homsi jumps forward by exactly $$$B$$$ buildings.

Hamoosh steals all $$$W_i$$$ units of iron from any building $$$i$$$ he lands on for the first time. If Hamoosh and Homsi land on the same building at the exact same moment, Hamoosh is immediately caught and the game ends. When caught, Hamoosh is arrested before he can steal the iron from that specific building.

You must assign the starting positions such that Homsi is guaranteed to eventually catch Hamoosh. Under this restriction, what is the maximum amount of iron Hamoosh can collect before being caught?

You are given a permutation $$$P = (P_1, P_2, \dots, P_N)$$$ of the integers from $$$1$$$ to $$$N$$$.

For a subarray $$$P[l \dots r] = (P_l, P_{l+1}, \dots, P_r)$$$ (where $$$1 \le l \le r \le N$$$), let us define its Value as follows: $$$$$$\text{Value}(l, r) = \text{Sum}(l, r) - \text{MEX}(l, r)$$$$$$

Where:

• $$$\text{Sum}(l, r) = \sum_{k=l}^{r} P_k$$$
• $$$\text{MEX}(l, r)$$$ is the smallest positive integer ($$$1, 2, 3, \dots$$$) that does not appear in the subarray $$$P[l \dots r]$$$.

We call a range 3afwey if its value is as large as possible. El 3afweya is calling ..., and you have to respond. Determine the value of the 3afwey range.

Khaled is the CEO of a rapidly growing industrial empire. His company recently acquired $$$N$$$ new factories, and he has hired $$$N$$$ workers to operate them. Both the workers' homes and the factories are located along a long, straight highway, which can be represented as the $$$X$$$-axis.

The $$$i$$$-th worker lives at coordinate $$$x_i$$$, and the $$$j$$$-th factory is located at coordinate $$$y_j$$$. Khaled needs to assign exactly one worker to each factory so that no two workers are assigned to the same factory.

Khaled requires a "stable" assignment. An assignment is invalid if swapping two workers' factories strictly increases the sum of their squared travel distances. Formally, for any worker $$$i$$$ assigned to factory $$$a$$$ and worker $$$j$$$ assigned to factory $$$b$$$, the following condition must NOT hold:

$$$$$$(x_i - y_a)^2 + (x_j - y_b)^2 \lt (x_i - y_b)^2 + (x_j - y_a)^2$$$$$$

Given the locations, help Khaled find any valid assignment satisfying his strict stability condition.