The MITIT Winter 2025-26 contest takes place on December 6-7, 2025.

This is an interactive problem.

Busy Beaver has a secret array $$$a_1, \dots, a_N$$$, where $$$1 \leq a_i \leq 10^9$$$ for all $$$i$$$ and every two elements are coprime. (Two integers are coprime if the only positive integer dividing both is $$$1$$$.)

You may ask up to $$$100$$$ queries of the following form:

• Pick two distinct indices $$$i$$$ and $$$j$$$. In response, you will receive the product $$$a_i \times a_j$$$.

Let $$$Q$$$ be the maximum number of queries you use to determine Busy Beaver's array. For full points, you must have $$$Q \leq \mathbf{67}$$$.

For each test case, begin by reading $$$N$$$.

To make a query, output "$$$\texttt{?}\;i\;j$$$" ($$$1 \leq i, j \leq n$$$; $$$i \neq j$$$) without quotes. Afterwards, you should read in a single integer — the product $$$a_i \times a_j$$$. You can make at most $$$100$$$ such queries in a single test case.

If you receive the integer $$$-1$$$ instead of an answer, it means your program has made an invalid query, has exceeded the limit of $$$100$$$ queries, or has given an incorrect answer on some previous test case. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

When you are ready to give the final answer, output "$$$\texttt{!}\;a_1\;\dots\;a_N$$$" ($$$1 \leq a_i \leq 10^9$$$) without quotes — Busy Beaver's array. Giving this answer does not count towards the limit of $$$100$$$ queries. Afterwards, your program must continue to solve the remaining test cases, or exit if all test cases have been solved.

After printing a query do not forget to output end of line and flush the output. To do this, use:

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

• For full points, you must have $$$Q \leq \mathbf{67}$$$.
• For partial points, using $$$67 \lt Q \leq 100$$$ queries will award $$$\lfloor 1.067^{125-Q} \rfloor$$$ points.

Busy Beaver has $$$X$$$ cards with the letter $$$\texttt{M}$$$, $$$Y$$$ cards with the letter $$$\texttt{I}$$$, and $$$Z$$$ cards with the letter $$$\texttt{T}$$$.

He wants to arrange these $$$X+Y+Z$$$ cards into a row following some constraints:

• Busy Beaver likes variety, so no two adjacent cards can be equal;
• Busy Beaver wants to avoid getting sued, so no three consecutive cards in a row can read $$$\texttt{MIT}$$$ or $$$\texttt{TIM}$$$.

Determine if he can do this. If it is possible, output an example.

Deep in Busy Beaver's robotics lab sits an experimental Busy Beaver machine. Given a positive integer $$$X$$$ written in base $$$B$$$, it attempts to produce two positive integers $$$Y$$$ and $$$Z$$$ such that $$$X + Y = Z$$$, and the base-$$$B$$$ representations of $$$Y$$$ and $$$Z$$$ contain exactly the same multiset of digits.

The machine never produces leading zeroes and never outputs numbers with $$$2 \cdot 10^5$$$ or more digits. It has recently stopped functioning, so your task is to determine whether such $$$Y$$$ and $$$Z$$$ exist, and to output them if they do. You are given the digits of $$$X$$$ in base $$$B$$$ without leading zeroes.

Busy Beaver is hosting an upcoming exam for his students in the MITIT exam room. Due to last-minute preparation and bad testing, the students will need to come up to him to complain about things like bad difficulty distributions, server issues, misleading statements, and awful flavortexts without disturbing other students, so he needs to ensure that the seats are well separated.

The room has $$$N$$$ seats at points $$$P_i = (x_i,y_i)$$$, with Busy Beaver's desk located at $$$O = (0,0)$$$. He wants to choose a nonempty subset of the seats satisfying the following condition:

• Each seat in the subset is strictly closer to Busy Beaver's desk than any other seat in the subset. Formally, for all pairs $$$P_i,P_j$$$ ($$$i \neq j$$$) in the subset, $$$\text{dist}(P_i,P_j) \gt \text{dist}(O,P_i)$$$, where $$$\text{dist}$$$ denotes Euclidean distance.

How many nonempty subsets satisfy this criterion? Since the answer may be enormous, output it modulo $$$998\,244\,353$$$.

There are four subtasks for this problem.

• ($$$10$$$ points): $$$N$$$ does not exceed $$$15$$$.
• ($$$10$$$ points): $$$N$$$ does not exceed $$$24$$$.
• ($$$10$$$ points): $$$N$$$ does not exceed $$$80$$$.
• ($$$70$$$ points): No additional constraints.

Busy Beaver has finally rage-quit Minesweeper and picked up Mahjong Connect instead. He has $$$N$$$ mahjong tiles at distinct locations on the Cartesian plane. Each tile $$$i$$$ has integer coordinates $$$(x_i, y_i)$$$ and a type $$$t_i$$$ with $$$1 \le t_i \le M$$$.

Two distinct tiles $$$i$$$ and $$$j$$$ match if and only if all of the following hold:

• They share the same type, i.e. $$$t_i=t_j$$$;
• They are on the same row or column, i.e. $$$x_i=x_j$$$ or $$$y_i=y_j$$$;
• They are not blocked by other types, i.e. every tile strictly between them in that row or column (if any) has the same type. Formally:
  • If $$$y_i=y_j$$$, then for every tile $$$k$$$ with $$$y_k=y_i$$$ and $$$\min\{x_i,x_j\} \lt x_k \lt \max\{x_i,x_j\}$$$, we must have $$$t_k=t_i$$$;
  • If $$$x_i=x_j$$$, then for every tile $$$k$$$ with $$$x_k=x_i$$$ and $$$\min\{y_i,y_j\} \lt y_k \lt \max\{y_i,y_j\}$$$, we must have $$$t_k=t_i$$$.

A perfect matching is a partition of the $$$N$$$ tiles into $$$N/2$$$ disjoint pairs such that every pair is a valid match under the rules above. Determine whether a perfect matching exists. If it does, output any one perfect matching; otherwise, report that no perfect matching exists.

Busy Beaver recently learned about the Collatz Conjecture! He has written down a sequence of $$$N$$$ positive integers $$$a_1, a_2, \ldots , a_N$$$ on a blackboard to experiment with and further his understanding of the conjecture. He also notices a counter left on a table and comes up with the following game to play.

The counter initially starts at the number $$$1$$$. A move consists of picking a number on the blackboard and replacing it:

• If the counter shows an odd number, Busy Beaver must pick some odd number $$$x$$$ on the board and replace it with $$$3x+1$$$.
• If the counter shows an even number, he must pick some even number $$$y$$$ on the board and replace it with $$$\frac{y}{2}$$$.

Busy Beaver wants to play this game for as long as possible. Help him determine the maximum number of moves he can perform before he runs out of moves!

Busy Beaver has arranged $$$N$$$ logs in a line to form the base of his dam. Each log has an integer quality value between $$$-2$$$ and $$$2$$$. From time to time, some logs are replaced. He occasionally wants to know if there is a contiguous segment of logs whose total quality equals a given nonzero number $$$X$$$, and may also want to know the segment. Help Busy Beaver process all updates and queries efficiently.

There are four subtasks in this problem. You can receive $$$50\%$$$ of the points for each subtask if the YES/NO answers are correct, but the indices are incorrect. To obtain these partial points, you must still output integers $$$l$$$ and $$$r$$$ between $$$1$$$ and $$$N$$$ after all YES answers.

• ($$$10$$$ points): The sum of $$$N$$$ over all test cases is at most $$$10^3$$$, and the sum of $$$Q$$$ over all test cases is at most $$$10^3$$$.
• ($$$20$$$ points): $$$-1\le a_i\le 1$$$ for all $$$i$$$, and for any query of the first type, $$$-1\le x\le 1$$$.
• ($$$30$$$ points): $$$0\le a_i\le 2$$$ for all $$$i$$$, and for any query of the first type, $$$0\le x\le 2$$$.
• ($$$40$$$ points): No additional constraints.

Busy Beaver has $$$N$$$ favorite snack spots along the Charles River, labeled $$$1, 2, \dots, N$$$. Each day, he wishes to enjoy a snack at spot $$$i$$$ during time $$$i$$$. What a perfectly optimized routine!

Unfortunately, the geese have other plans. For each index $$$i$$$, a goose occupies spot $$$a_i$$$ at time $$$i$$$. Busy Beaver absolutely refuses to visit the same spot as a goose, so his final schedule $$$p_1,p_2,\dots,p_N$$$ must be a permutation of $$$1,2,\dots,N$$$ that satisfies $$$p_i \neq a_i$$$ for every $$$1 \le i \le N$$$.

Busy Beaver also wants to keep his life predictable. Among all valid schedules $$$p$$$, determine the minimum possible number of inversions$$$^{\text{∗}}$$$ $$$p$$$ can have. If no valid schedule exists, output $$$-1$$$.

This is an interactive problem.

Busy Beaver has a secret array $$$a_1,a_2,\dots,a_N$$$ of distinct positive integers between $$$1$$$ and $$$10^9$$$. For $$$1 \le l \le r \le N$$$, Busy Beaver defines $$$f(l,r)$$$ to be equal to $$$\min(a_l,a_{l+1},\dots,a_r)$$$.

Busy Beaver allows you to ask some queries to uncover information about the array. In a query, you can specify $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le N$$$), and Busy Beaver will tell you the value of $$$f(l,r)$$$ for a cost of $$$\frac{1}{r-l+1}$$$. You must ensure that the total cost of all queries is at most $$$1$$$.

After making all your queries, you report to Busy Beaver a list of pairs $$$(l,r)$$$ for which you determined the value of $$$f(l,r)$$$. If any of your answers are wrong, Busy Beaver will be displeased and award you $$$0$$$ points. Otherwise, your score will depend on the fraction of the $$$\frac{N(N+1)}{2}$$$ pairs $$$(l,r)$$$ with $$$1 \le l \le r \le N$$$ where you determined a value for $$$f(l,r)$$$ (see the Scoring section for more details).

To reduce the size of the output, you report your knowledge using $$$k$$$ tuples of the form $$$(l_{min},l_{max},r_{min},r_{max},v)$$$, where $$$1 \le l_{min} \le l_{max} \le r_{min} \le r_{max} \le N$$$ and $$$1 \le v \le 10^9$$$. Each tuple declares that $$$f(l,r) = v$$$ for all $$$l_{min} \le l \le l_{max}$$$ and $$$r_{min} \le r \le r_{max}$$$. Any pairs $$$(l,r)$$$ that do not correspond to any tuple are treated as unspecified. It is allowed to have multiple tuples that describe the same pair $$$(l,r)$$$, but you will receive $$$0$$$ points if these tuples indicate inconsistent values.

The first line of input contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$), the length of Busy Beaver's secret array.

You may repeatedly ask queries by outputting a line of the form "? l r", where $$$1 \le l \le r \le N$$$. Then, the judge will respond with a single integer, denoting the value of $$$f(l,r)$$$. If you exceed a total cost of $$$1$$$, the judge will instead respond with $$$-1$$$, and you should terminate your program immediately to receive a Wrong Answer verdict.

After you are finished with your queries, first output a line of the form "! k" ($$$0 \le k \le 2N$$$), representing that you will describe your knowledge of $$$f$$$ using $$$k$$$ tuples $$$(l_{min},l_{max},r_{min},r_{max},v)$$$.

Then, the next $$$k$$$ lines should each contain $$$5$$$ space-separated integers $$$l_{min}$$$, $$$l_{max}$$$, $$$r_{min}$$$, $$$r_{max}$$$, and $$$v$$$, specifying a tuple.

The interactor is not adaptive, meaning that Busy Beaver will not change the entries of his secret array $$$a$$$ in response to your queries.

For all test cases used for scoring, $$$N = 10^5$$$.

If you exceed a cost of $$$1$$$ or any of the values you claim for $$$f(l,r)$$$ are incorrect, you will receive $$$0$$$ points and a Wrong Answer verdict.

Otherwise, let $$$x$$$ be the fraction of the $$$\frac{N(N+1)}{2}$$$ values of $$$f(l,r)$$$ that you specified a value for. Your score for the test case will be equal to $$$$$$ \left\lfloor \min\left(100,100 \cdot \frac{x}{0.8}\right) \right\rfloor. $$$$$$ In particular, if $$$x \ge 0.8$$$, then you will receive full points for the test case.

Your final score will be the minimum score over all test cases.