Busy Beaver is throwing an MITIT party!
Busy Beaver is planning to print a large banner. His printer is old-school: it draws on an $$$N \times N$$$ pixel board, where $$$N$$$ is odd, using $$$\texttt{#}$$$ for ink and $$$\texttt{.}$$$ for blank space. For the first letter of the banner, he needs the letter M, printed as shown below.
Your job is to tell the printer exactly which pixels to ink.
Formally, the M is defined as follows. The left and right edges of the banner are the M's vertical legs, running all the way from top to bottom. From the top corners, two strokes with slope $$$1$$$ and $$$-1$$$ descend inward, one from each side, meeting exactly in the middle row. Because $$$n$$$ is odd, there is a single center column and a single middle row where the slanted strokes touch. Below that meeting point, only the two outer legs continue to the bottom.
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 50$$$) — the number of test cases.
The only line of each test case contains a single odd integer $$$N$$$ ($$$5 \leq N \lt 50$$$, $$$N$$$ is odd) — the side length of Busy Beaver's board.
For each test case, output $$$N$$$ lines, each containing $$$N$$$ characters $$$\texttt{#}$$$ and $$$\texttt{.}$$$ without spaces — the letter M, as described in the statement.
Do not output empty lines between test cases.
3579
#...###.###.#.##...##...##.....###...###.#.#.##..#..##.....##.....##.....##.......###.....###.#...#.##..#.#..##...#...##.......##.......##.......##.......#
Busy Beaver has a string $$$A$$$ made up of characters $$$\texttt{P}$$$ and $$$\texttt{N}$$$. He can perform two types of operations on $$$A$$$:
- Pick a substring$$$^{\text{∗}}$$$ $$$\texttt{P}$$$ and replace it with $$$\texttt{NP}$$$.
- Pick a substring $$$\texttt{NP}$$$ and replace it with $$$\texttt{P}$$$.
Busy Beaver has a target string $$$B$$$. Determine if he can turn $$$A$$$ into $$$B$$$ after some number of operations.
$$$^{\text{∗}}$$$A substring of length $$$k$$$ is a contiguous sequence of $$$k$$$ adjacent characters of a string.
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$) — the number of test cases.
The only line of each test case contains the strings $$$A$$$ and $$$B$$$ ($$$1 \leq |A|, |B| \leq 10^5$$$), consisting of characters $$$\texttt{P}$$$ and $$$\texttt{N}$$$.
The sum of $$$|A|+|B|$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output YES if Busy Beaver can turn $$$A$$$ into $$$B$$$ using the operations above, and NO otherwise.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
7P NPPNPN NPPNPP NPNPN PPNPPNPP PPNNNNNNNNNNNNNNNNNNPPPNNPPNNPP NNPPNNPPNNNPNNNNNPN PPPN
YESYESNONOYESNONO
In the first test case, we can perform one operation to turn $$$\texttt{P}$$$ into $$$\texttt{NP}$$$.
In the second test case, we can do two operations: $$$\texttt{P}\color{red}{\texttt{NP}}\texttt{N} \to \texttt{P}\color{red}{\texttt{P}}\texttt{N}$$$ and then $$$\color{red}{\texttt{P}}\texttt{PN} \to \color{red}{\texttt{NP}}\texttt{PN}$$$.
In the third test case, we can show that it is not possible to turn $$$\texttt{PP}$$$ into $$$\texttt{NP}$$$ using any number of operations.
Busy Beaver lines up $$$N$$$ marbles numbered $$$1$$$ through $$$N$$$, where the $$$i$$$-th marble shows a number $$$p_i \neq i$$$, and every number from $$$1$$$ to $$$N$$$ appears exactly once among $$$p_1, \dots, p_N$$$ (more formally, $$$p$$$ is a permutation over $$$1, \dots, N$$$ such that $$$p_i \neq i$$$).
He wants to paint the marbles so that each marble $$$i$$$ has a different color from marble $$$p_i$$$. However, he only has three colors: red, green, and blue. Help him find any valid painting.
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$) — the number of test cases.
The first line of each test case contains one integer $$$N$$$ ($$$2 \le N \le 10^5$$$) — the number of marbles.
The second line of each test case contains $$$N$$$ integers $$$p_1, p_2, \dots, p_N$$$ ($$$1 \le p_i \le N$$$; $$$p_i \ne i$$$) — the numbers on the marbles. These numbers form a rearrangement of the numbers $$$1, \dots, N$$$ in some order.
The sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, output a string of length $$$N$$$ containing the characters $$$\texttt{R}$$$, $$$\texttt{G}$$$, and $$$\texttt{B}$$$, where the $$$i$$$-th character denotes the color (red, green, or blue, respectively) of the $$$i$$$-th marble, satisfying the constraints.
If there are multiple possible answers, you can output any of them. We have a proof that under these constraints, an answer always exists.
552 1 5 3 462 1 4 3 6 552 3 4 5 133 1 244 3 2 1
GBBGR BGGRRB RBRBG RGB BRGG
In the first test case, the coloring $$$\texttt{GBBGR}$$$ works as follows:
- Marble $$$1$$$ is colored green and has the number $$$2$$$ written on it; marble $$$2$$$ is colored blue, and since green is not blue, the constraint is satisfied.
- Marble $$$2$$$ is colored blue and has the number $$$1$$$ written on it; marble $$$1$$$ is colored green, and since blue is not green, the constraint is satisfied.
- Marble $$$3$$$ is colored blue and has the number $$$5$$$ written on it; marble $$$5$$$ is colored red, and since blue is not red, the constraint is satisfied.
- Marble $$$4$$$ is colored green and has the number $$$3$$$ written on it; marble $$$3$$$ is colored blue, and since green is not blue, the constraint is satisfied.
- Marble $$$5$$$ is colored red and has the number $$$4$$$ written on it; marble $$$4$$$ is colored green, and since red is not green, the constraint is satisfied.
Busy Beaver has just learned about divisors and multiples in elementary school. Now, Busy Beaver challenges you with the following problem.
You are given a sequence $$$a$$$ of length $$$N$$$. Find any positive integer $$$X$$$ such that:
- For every $$$i$$$, $$$X$$$ is either a multiple or a divisor of $$$a_i$$$;
- there exists at least one index $$$i$$$ such that $$$X$$$ is a multiple of $$$a_i$$$;
- there exists at least one index $$$i$$$ such that $$$X$$$ is a divisor of $$$a_i$$$;
or determine that no such integer exists.
The first line contains a single integer $$$T$$$ ($$$1\leq T\leq 10^4$$$) — the number of test cases.
The first line of each test case contains an integer $$$N$$$ ($$$2\le N\le 3 \cdot 10^5$$$) — the length of the sequence $$$a$$$.
The second line of each test case contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$1 \le a_i \le 10^9$$$).
The sum of $$$N$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.
For each test case, output a single integer — the value of $$$X$$$, or $$$-1$$$ if no such $$$X$$$ exists.
If there are multiple valid values for $$$X$$$, you may output any of them.
There are two subtasks for this problem.
- ($$$40$$$ points): The sum of $$$N$$$ across all test cases does not exceed $$$2000$$$.
- ($$$60$$$ points): No additional constraints.
6336 2 12610 20 30 40 50 6078 7 6 5 4 3 2610 6 1 90 2 15310 2 521 1
6 10 -1 30 10 1
In the first test case, $$$6$$$ is a divisor of $$$36$$$ and $$$12$$$, and is a multiple of $$$2$$$.
In the second test case, $$$10$$$ is a divisor of all elements, and also a multiple of $$$10$$$.
In the third test case, there is no integer that satisfies the constraints.
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}$$$.
Each test contains multiple test cases. The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 1000$$$) — the number of test cases.
The first line of each test case contains an integer $$$N$$$ ($$$5 \leq N \leq 100$$$). After reading this line, you should begin the interaction.
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.
2 5 77 30 85 5 69
? 1 2 ? 3 4 ? 4 5 ! 7 11 6 5 17 ? 1 5 ! 1 40 61 41 69
During an actual run the solution does not know the hidden array; it is shown here only to justify the sample.
In the first test case, the judge prints 5, so $$$N=5$$$. Its hidden array is $$$[7,11,6,5,17]$$$.
- The program asks ? 1 2 and receives 77 from $$$7\times 11$$$.
- It asks ? 3 4 and receives 30 from $$$6\times 5$$$.
- It asks ? 4 5 and receives 85 from $$$5\times 17$$$.
In the second test case, the judge prints 5. Its hidden array is $$$[1,40,61,41,69]$$$.
The program asks ? 1 5 and receives 69 from $$$1\times 69$$$. It then outputs ! 1 40 61 41 69, which matches the judge's array.
This illustrates one valid interaction sequence; any correct determination of the array using allowed queries is acceptable.
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.
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 50$$$) — the number of test cases.
The only line of each test case contains three integers $$$X$$$, $$$Y$$$, and $$$Z$$$ ($$$0 \leq X, Y, Z \leq 10^5$$$). There is at least one card in each test case ($$$X+Y+Z \gt 0$$$).
The combined sum of $$$X+Y+Z$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.
For each test case, if Busy Beaver cannot arrange all $$$X+Y+Z$$$ cards, output NO.
Otherwise, output YES. Then, output one line — a string of length $$$X+Y+Z$$$ consisting of characters $$$\texttt{M}$$$, $$$\texttt{I}$$$, and $$$\texttt{T}$$$, satisfying the constraints in the statement.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses. You can also output the string in any case.
21 1 13 0 0
YESITMNO
In the first test case, there are $$$4$$$ possible combinations that will work: $$$\texttt{ITM}$$$, $$$\texttt{IMT}$$$, $$$\texttt{MTI}$$$, $$$\texttt{TMI}$$$. $$$\texttt{ITM}$$$ is one of them. It does not have equal adjacent cards, and there is no $$$\texttt{MIT}$$$ or $$$\texttt{TIM}$$$.
In the second test case, there is only one possible construction: $$$\texttt{MMM}$$$, but it is not valid, as there are adjacent $$$\texttt{M}$$$s.
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.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 100$$$), the number of test cases.
Each test case consists of two lines. The first line of each test case contains two integers $$$N$$$ and $$$B$$$ ($$$1 \le N \le 10^5$$$; $$$2 \le B \le 10^5$$$).
The second line of each test case contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$0 \le a_i \le B-1$$$; $$$a_1 \ne 0$$$), representing the digits of $$$X$$$ in base $$$B$$$: $$$$$$ X = a_1 B^{N-1} + a_2 B^{N-2} + \cdots + a_N. $$$$$$
The sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, if no valid solution exists, output a single line containing NO.
Otherwise, output YES on the first line. On the second line output an integer $$$M$$$ ($$$1 \le M \le 2 \cdot 10^5$$$), the number of digits in both $$$Y$$$ and $$$Z$$$.
On the next line output $$$M$$$ digits $$$p_1, p_2, \ldots, p_M$$$ ($$$0 \le p_i \le B-1$$$; $$$p_1 \ne 0$$$), representing $$$$$$ Y = p_1 B^{M-1} + p_2 B^{M-2} + \cdots + p_M. $$$$$$ On the following line output $$$M$$$ digits $$$q_1, q_2, \ldots, q_M$$$ ($$$0 \le q_i \le B-1$$$; $$$q_1 \ne 0$$$), representing $$$$$$ Z = q_1 B^{M-1} + q_2 B^{M-2} + \cdots + q_M. $$$$$$ The digit sequences $$$(p_1, \ldots, p_M)$$$ and $$$(q_1, \ldots, q_M)$$$ must use exactly the same multiset of digits, and the integers they represent must satisfy $$$X + Y = Z$$$. You may print YES and NO in any mixture of uppercase and lowercase letters.
32 103 64 51 4 3 45 124 8 8 3 1
YES 2 1 5 5 1 YES 4 1 4 3 2 3 4 2 1 NO
In the first test case, with $$$B = 10$$$ and $$$X = 36$$$, a valid solution is $$$Y = 15$$$ and $$$Z = 51$$$, since $$$51 = 36 + 15$$$ and both numbers use the digits $$$\{1,5\}$$$.
In the second test case, with $$$B = 5$$$ and $$$X$$$ given by digits $$$(1, 4, 3, 4)_5$$$, $$$$$$ X = 1 \cdot 5^3 + 4 \cdot 5^2 + 3 \cdot 5^1 + 4 = 244. $$$$$$ One valid pair is $$$$$$ Y = (1, 4, 3, 2)_5 = 242, \qquad Z = (3, 4, 2, 1)_5 = 486, $$$$$$ which share the digit multiset $$$\{1,2,3,4\}$$$ and satisfy $$$X + Y = Z$$$.
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$$$.
The first line contains a single integer $$$N$$$ ($$$1 \le N \le 500$$$).
The $$$i$$$-th of the next $$$N$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i,y_i \le 10^9$$$).
All $$$N$$$ points in the input are distinct and not equal to $$$(0,0)$$$.
Output a single integer — the number of valid nonempty subsets 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.
21 22 1
2
31 22 11 -3
5
In the first sample, the two desks are $$$\sqrt{2}$$$ apart and $$$\sqrt{5}$$$ away from the origin, so either one or the other can be used.
In the second sample, the third desk is $$$\sqrt{10}$$$ away from the origin and $$$\sqrt{17}$$$ away from the closest other desk, so the third desk can always be used. The valid subsets are: $$$$$$ \{\text{desk }1\}, \{\text{desk }2\}, \{\text{desk }3\}, \{\text{desk }1, \text{desk }3\}, \{\text{desk }2, \text{desk }3\}. $$$$$$
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.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2\le N\le 3\cdot 10^5$$$, $$$1\le M\le 3\cdot 10^5$$$, $$$N$$$ is even).
The next $$$N$$$ lines describe the tiles. The $$$i$$$-th of these lines contains three integers $$$x_i$$$, $$$y_i$$$ and $$$t_i$$$ ($$$|x_i|,|y_i|\le 10^9$$$, $$$1\le t_i\le M$$$).
It is guaranteed that the pairs $$$(x_i,y_i)$$$ are distinct.
If no perfect matching exists, print a single line containing NO.
Otherwise, print a single line containing YES. Then print $$$N/2$$$ lines, each containing two integers $$$i$$$ and $$$j$$$ ($$$1\le i,j\le N$$$, $$$i\neq j$$$), indicating that tiles $$$i$$$ and $$$j$$$ form a matched pair.
Each index from $$$1$$$ to $$$N$$$ must appear in exactly one pair. The pairs may be printed in any order, and within each pair, the order of $$$i$$$ and $$$j$$$ does not matter.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
4 2-1 0 11 0 10 -1 20 1 2
YES 1 2 3 4
4 2-1 0 11 0 10 0 20 1 2
NO
22 31 1 21 2 21 3 21 4 12 3 23 2 13 1 24 3 25 4 15 3 15 2 15 1 17 1 37 2 37 3 37 4 39 4 310 4 311 4 310 3 110 2 110 1 3
YES 1 7 2 3 4 9 5 8 6 11 10 12 13 22 14 15 16 17 18 19 20 21
In the first test case, we can pair up the tiles at $$$(-1,0),(1,0)$$$ and $$$(0,-1),(0,1)$$$, respectively.
In the second test case, we cannot do the same thing because the tile at $$$(0,0)$$$ blocks the connection between $$$(-1,0)$$$ and $$$(1,0)$$$.
The visualization of the third test case is as follows (different colors represent different types of tiles):
Note again that, if the answer is YES, any valid pairing with any order will be accepted. For instance, for the first sample, the following output is also acceptable:
YES
4 3
1 2