Aboard the spaceship Skeld are you — the ship's commander — along with $$$N$$$ crewmates. The voyage from Earth to Polus was meant to be peaceful... until it wasn't. A series of strange incidents occurs: oxygen runs low, the reactor nearly melts down, the lights flicker, and the doors jam shut. Suspicion spreads — there might be impostors among us.

Moments of crisis were handled with the crewmates' unity, but the tension lingered. Each crewmate now secretly suspects exactly one crewmate of being the impostor. Remarkably, no crewmate is suspected by more than one person. Formally, there exists a permutation $$$P$$$ of length $$$N$$$, where $$$P[i]$$$ is the crewmate whom the $$$i$$$-th crewmate suspects.

Overseeing this chaos from the commander's room, you, however, are not actually concerned with finding the impostors. Rather, your only goal is to determine the hidden permutation $$$P$$$.

Naturally, to achieve this, you may call emergency meetings. In each meeting, you can choose the order in which the crewmates speak.

Given a crewmate speaking, they will accuse the crewmate they suspect. If the speaker has not yet been marked as sus, their accusation is valid, and the accused crewmate becomes sus. However, if the speaker is already sus, their accusation is ignored.

Unfortunately, as the commander, you cannot attend the meetings yourself. Instead, after each meeting, the ship's log reports the sus status of all crewmates as a binary array, where 1 indicates sus and 0 indicates not sus.

Since time is limited, you may hold at most $$$400$$$ emergency meetings. Your task is to determine the hidden permutation $$$P$$$ within this limit.

Your program first reads a single integer $$$N$$$ ($$$2 \le N \le 100$$$) — the number of crewmates.

Then, you may repeatedly perform queries (call emergency meetings). To make a query, print a line in the following format:

• ? $$$q_1$$$ $$$q_2$$$ $$$\dots$$$ $$$q_N$$$

Here, $$$(q_1, q_2, \dots, q_N)$$$ is the order in which the crewmates will speak during the meeting. The sequence must be a permutation of length $$$N$$$.

After printing a query, flush the output and read a line containing $$$N$$$ integers:

• $$$s_1$$$ $$$s_2$$$ $$$\dots$$$ $$$s_N$$$

Here, $$$s_i$$$ indicates the status of the $$$i$$$-th crewmate after the meeting ends:

• $$$s_i = 0$$$ — the $$$i$$$-th crewmate is not sus.
• $$$s_i = 1$$$ — the $$$i$$$-th crewmate is sus.

Each emergency meeting is independent; all crewmates start as not sus.

When you have determined the hidden permutation $$$P$$$, print it in the following format:

• ! $$$p_1$$$ $$$p_2$$$ $$$\dots$$$ $$$p_N$$$

Printing the answer does not count as a query. After printing the final answer, your program should immediately terminate. Failure to do so may result in an undefined verdict.

You may perform at most 400 queries. If your program performs more than $$$400$$$ queries or outputs an invalid format, you may receive a Wrong Answer verdict.

The interactor is not adaptive, which means that the hidden permutation does not depend on the queries you make.

After printing a query or an answer, do not forget to output the end of line and flush the output. Otherwise, you may get an Idleness Limit Exceeded verdict. To do this, use:

• fflush(stdout) or cout.flush() in C/C++;
• System.out.flush() in Java and Kotlin;
• sys.stdout.flush() in Python;

Jack is playing a game with his cat, Salmon. On a shelf, Jack has comic books labeled from volume $$$1$$$ to volume $$$N$$$, arranged in some order from left to right. All books are identical in size.

Jack and Salmon will repeat the following sequence of moves exactly $$$M$$$ times (where $$$M$$$ may be zero):

1. Jack chooses one comic book that is not the rightmost book and knocks it to the ground.
2. He then closes the gap by shifting all books to the right of that position leftward to fill the space, leaving the empty spot at the rightmost end of the shelf.
3. Finally, Salmon picks up the fallen book and places it into the gap at the rightmost position.

Your task is to determine the lexicographically largest initial arrangement of the books such that, after performing exactly $$$M$$$ sets of moves as described, there exists a sequence of choices for Jack that results in the books being sorted in ascending order from volume $$$1$$$ to volume $$$N$$$ from left to right.

Two different arrangements $$$A$$$ and $$$B$$$ of $$$N$$$ books are compared lexicographically as follows: $$$A$$$ is said to be lexicographically larger than $$$B$$$ if, at the first position $$$i$$$ from left side where they differ, $$$A_i \gt B_i$$$.

A mathematician from ancient times left behind a riddle for future generations. Carved into stone lies a challenge about numbers and operations : Any number can be represented using a sequence of $$$+$$$ and $$$-$$$ signs applied to the numbers 1, 2, 3, ...

You, a bright and curious mind from the future, decide to take up this challenge and makes it even more challenging.

Given an integer $$$X$$$, your task is to express it in the form $$$1 \pm 2 \pm 3 \pm 4 \pm \ldots \pm N$$$ so that the result equals $$$X$$$ and $$$N$$$ is the smallest number.

Audrey and Bastian are about to start on an epic dungeon crawl where they'll face $$$R$$$ monsters ($$$1 \le R \le 10^9$$$). Each monster has a health point (HP) value between $$$0$$$ and $$$N$$$ ($$$1 \le N \le 5 \times 10^5$$$).

Game Rules

The battle proceeds in turns, with Audrey going first:

• On each turn, the current player selects a monster with HP $$$ \gt 0$$$
• If the chosen monster has HP $$$= x$$$, the player can choose to deal damage $$$d$$$ where $$$1 \le d \le p[x]$$$. It's guaranteed that $$$1 \le p[x] \le x$$$ for all $$$x$$$.
• The monster's HP becomes $$$x - d$$$
• The player who defeats the last monster (reduces the last non-zero HP to $$$0$$$) wins

Both players play optimally.

The Setup Phase

Audrey's Preparation: Audrey, being a cunning adventurer, prepares the dungeon in advance. She sets the initial HP of all $$$R$$$ monsters to values $$$a_1, a_2, \ldots, a_R$$$ where $$$0 \le a_i \le N$$$. Audrey configures the monsters such that she is guaranteed to win if the game proceeds with these HP values.

Bastian's Sabotage: Bastian discovers Audrey's scheme and decides to sabotage exactly one monster before the battle begins. He chooses one monster with HP $$$= a_i$$$ where $$$a_i \ge K$$$ and decreases its HP by $$$K$$$, making its new HP equal to $$$a_i - K$$$.

Bastian's goal is to turn the tables and guarantee his own victory. If there's no way for Bastian to choose a monster that guarantees his win, Bastian abandons the dungeon (the game doesn't happen).

You have to determine how many distinct configurations $$$(a_1, a_2, \ldots, a_R)$$$ are possible on the final day (after Bastian's sabotage, if the game proceeds).

Important: Count configurations based on the HP values after Bastian's modification, not the initial values Audrey set.

Two configurations are considered different if they contain different HP values or the same HP values in different orders (e.g., $$$(1, 3, 2) \neq (1, 2, 3)$$$)

Elena the Ashen Witch has decided to spend some time in a magical country and is now searching for a place to stay. The country consists of $$$N$$$ cities, numbered from $$$1$$$ to $$$N$$$, connected by $$$M$$$ one-way streets. Since flying magic has been banned for intercity travel, Elena must rely on these streets to move from one city to another.

Each street is described by four integers $$$u$$$, $$$v$$$, $$$p$$$, and $$$h$$$ — meaning there is a road leading from city $$$u$$$ to city $$$v$$$ that requires a pass level of $$$p$$$ and takes $$$h$$$ hours to traverse. To use a street, Elena needs a travel pass. If she holds a pass of level $$$p$$$, she can use any streets that require a pass level less than or equal to $$$p$$$. There may be multiple streets from city $$$u$$$ to city $$$v$$$.

Elena has prepared $$$Q$$$ questions for her journey, each falling into one of the following two types:

• Type 1: Elena is considering staying in city $$$u$$$ and wants to know the minimum pass level required so that, with that pass, the travel time from city $$$u$$$ to any city does not exceed $$$h$$$ hours.

• Type 2: Elena is choosing where to stay and wants to find a city such that, from that city, she can reach any city within $$$h$$$ hours while requiring the lowest possible pass level. If multiple cities achieve the same minimum requirement, she will choose the one with the smallest city number, since the average cost of living there is lower.

With the quarantine measures lifted, Jack's hometown decides to hold a festival. Jack is still cautious about meeting too many people, so he wants to plan his route through the festival to maximize his happiness using a simple strategy.

The festival has $$$N$$$ stalls, numbered from $$$1$$$ to $$$N$$$. If Jack enters the $$$i$$$-th stall, he meets $$$p_i$$$ people and gains happiness $$$h_i$$$. He walks from stall $$$1$$$ to stall $$$N$$$ in order and does not revisit any stall. At each stall, he can either enter it or walk past it.

It is guaranteed that $$$p_i \ge p_{i+1}$$$ for all $$$i \lt N$$$, since earlier stalls tend to draw larger crowds.

Jack wants to meet at most $$$P$$$ people in total. He also considers only stalls whose happiness exceeds a certain threshold value $$$threshold$$$. The $$$threshold$$$ should be a non-negative integer.

Formally, let $$$ht$$$ be Jack's total happiness and $$$m$$$ be the number of people he has met. Jack will follow the following strategy.

Jack's strategy (pseudo-code):

ht = 0 // initially, the total happiness is zero
m = 0 // initially, he meets zero person
for i = 1 to N:
    if h[i] > threshold and m + p[i] <= P:
        enter stall i
        ht = ht + h[i]
        m = m + p[i]
    else:
        skip stall i

Jack wants to choose the value of $$$threshold$$$ that maximizes his total happiness $$$ht$$$. If multiple thresholds achieve the same maximum happiness, he wants the minimum such threshold.

In a galaxy far, far away, there are $$$N$$$ planets. The $$$i$$$-th planet is located at coordinates $$$(x_i,y_i,z_i)$$$. The planets are connected by a galactic railway system consisting of $$$N-1$$$ bi-directional railways, forming a tree structure.

As an agent of the Galactic Adventure Agency, you are planning a promotional campaign. For this campaign, you must choose two planets to highlight. Wanderers can journey between these two planets in two different ways:

• By galactic train: Traveling along the unique simple path that connects the two planets in the railway system. Each railway has an associated satisfaction score (it can be negative), and the total satisfaction is the sum of the scores along the path.
• By private rocket: Traveling directly between the two planets along the $$$x$$$, $$$y$$$, and $$$z$$$ axes. The satisfaction score for this option is equal to the Manhattan distance between the two planets, i.e. $$$|x_i - x_j| + |y_i - y_j| + |z_i - z_j|$$$.

To please both types of tourists, you want to select a pair of planets $$$(u, v)$$$ that maximizes the combined satisfaction value, defined as the sum of the train satisfaction and the rocket satisfaction between them.

Your task is to find this maximum combined satisfaction value.

Life feels dull when you cannot go outside or meet your favorite people. Fortunately, your favorite bands keep releasing new hits this year, such as Ussewa, Wan Koei Tuen, and Thought Crime. Therefore, you decide to work out at home with your playlist!

You have a playlist of $$$N$$$ songs, numbered from $$$1$$$ to $$$N$$$, representing the order in which they are played. Each song $$$i$$$ has a hypeness value $$$A_i$$$.

While exercising, you only want to listen to songs that match a certain pattern of rising excitement. You may choose to skip some songs, keeping the remaining ones in their original order.

Formally, let $$$S = [S_1, S_2, \dots, S_k]$$$ be a subsequence of $$$[1, 2, \dots, N]$$$ representing the indices of unskipped songs. Your task is to find the longest possible subsequence $$$S$$$ such that:

• The hypeness strictly increases: $$$A_{S_i} \gt A_{S_{i-1}}$$$ for all $$$i \ge 2$$$.
• The increase in hypeness also strictly increases: $$$A_{S_i} - A_{S_{i-1}} \gt A_{S_{i-1}} - A_{S_{i-2}}$$$ for all $$$i \ge 3$$$.

In other words, both the hypeness values and the gaps between them must form strictly increasing sequences. Find the maximum possible length of such a subsequence $$$S$$$.

Myth generation has begun !

Ina is given a string $$$S$$$ of length $$$N$$$, consisting only of the characters 'I', 'C', and 'P'.

Her task is to repeatedly extract the substring "ICPC" from $$$S$$$ as many times as possible. Each time she extracts "ICPC", she must choose four characters from $$$S$$$ in order (not necessarily contiguous, but respecting the original order) that form "ICPC". After each extraction, the chosen characters are removed from the string. The remaining characters close the gap and form the new string for the next extraction.

You must help her determine the maximum number of times she can extract "ICPC" and the indices (1-indexed) of the characters removed from the original string $$$S$$$ for each extraction.

At a grand and dazzling dance party, there are $$$N$$$ guests, each with their own dance skill power $$$a_i$$$.

When two guests pair up on the dance floor, their performance score is equal to the square root of the sum of their skill powers. For example, if one guest has a skill power of $$$4$$$ and another has $$$5$$$, their duet would have a performance score of $$$\sqrt{4 + 5} = 3$$$.

As the host of this vivid celebration, you wish to measure the collective joy — the total performance score of every possible pair of guests dancing together exactly once.

Your task is to determine this total score.

Welcome to the Kickshot Tournament, part of the prestigious International Cue & Pocket Championship (ICPC) ! This year is a special year because they decide to host the tournament in the virtual world instead of real life !

You are playing on a rectangular pool table of size $$$(R - 1) \times (C - 1)$$$. On every lattice point of the table lies a virtual coin, forming a total of $$$R \times C$$$ coins. The coordinate system is $$$1$$$-indexed, with the coin at row $$$1$$$, column $$$1$$$ positioned at the bottom-left corner. Rows increase upward, and columns increase to the right.

A ball is placed on the coin located at row $$$M$$$, column $$$N$$$, and is shot at a perfect $$$45^\circ$$$ angle in the up-right direction. Initially, for each millisecond, the ball moves one unit upward (toward larger row numbers) and one unit rightward (toward larger column numbers). When the ball hits the top or bottom wall, it flips its vertical direction; when it hits the left or right wall, it flips its horizontal direction. There is no energy loss — the ball continues bouncing perfectly until it lands in one of the four corner pockets.

Each time the ball passes through a coin, that coin immediately disappears from the table. Collecting a coin does not affect the trajectory of the ball. The coin at row $$$M$$$ column $$$N$$$ is immediately collected when shot. The process continues until the ball reaches a corner, where it finally stops.

Your task is to determine how many coins the ball collects in total, including both the starting coin and the final coin at the pocket.

A mega-scale project to convert laser light into usable energy for general purposes has begun in the almost infinite experiment area with laser-amplifying glass panes.

The experiment was conducted by placing a laser emitter in one room. After that, the $$$N$$$ laser receivers were placed in room coordinates $$$(x_i,y_i)$$$; each room has a glass pane on the vertical and horizontal side which is shared between adjacent rooms.

• When the laser passes through each vertical glass pane, the laser intensity is increased by $$$A$$$ units.
• When the laser passes through each horizontal glass pane, the laser intensity is increased by $$$B$$$ units.

The room coordinate in the experiment area with a glass pane on each side

Furthermore, the administrator of the project has provided 1 L-shaped reflector to change the trajectory of the laser from horizontal to vertical or vice versa. You want to run $$$Q$$$ simulation tests to provide the information on the minimum possible laser intensity given the starting point for the laser at coordinates $$$(s_i,t_i)$$$; your task is to come up with the resulting laser intensity.

The Marvelous Maximillian is a stage magician famous for his grand finale, The Perfect Permutation. He claims he can arrange $$$N$$$ cards, numbered $$$1$$$ to $$$N$$$, into any permutation $$$P$$$ requested by the audience.

As his apprentice, you know his secret: it's a precise $$$N$$$-step procedure. The trick starts with an empty pile. For each card $$$i$$$ from $$$1$$$ to $$$N$$$, in order:

1. Maximillian places card $$$i$$$ on top of the pile.
2. He immediately asks you for a secret number, $$$x_i$$$ (where $$$1 \le x_i \le i$$$). He takes the top $$$x_i$$$ cards from the pile and moves them, in order, to the bottom. For example, if the pile is [3, 1, 2] (top to bottom) and $$$x = 2$$$, the pile becomes [2, 3, 1].

Tonight, an audience member has demanded the final pile be in the specific order $$$P$$$, where $$$P_1$$$ is the top card and $$$P_N$$$ is the bottom.

Maximillian is on stage and looking at you. You must provide the correct sequence of cut numbers, $$$x_1, x_2, \ldots, x_N$$$, to produce the permutation $$$P$$$ and save the show.

Alice and Bob are standing somewhere in a vaccination queue of $$$N$$$ people (including themselves). With everyone wearing facemasks and keeping their distance, it's almost impossible to recognize anyone else.

Alice counts $$$A$$$ people standing in front of her, while Bob counts $$$B$$$ people standing behind him.

Even if they can't see each other, they still want to know how far apart they are. Can you help them find out how many people are standing between Alice and Bob (excluding both of them)?