MITIT Winter 2025 Beginner Round
A. MIT Time
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver arrived to his MIT class late! However, thanks to "MIT time", all classes actually start $$$5$$$ minutes later than the posted time.

Busy Beaver wants to make a generalization of this system. Namely, if someone arrives $$$N$$$ minutes late to an event, then:

  • if $$$N \le 5$$$, they arrived on "MIT time";
  • if $$$5 \lt N \le 25$$$, they arrived on "MIT$$$^2$$$ time";
  • if $$$25 \lt N \le 125$$$, they arrived on "MIT$$$^3$$$ time";
  • and so on. Formally, if $$$k \ge 2$$$, then "MIT$$$^k$$$ time" is when $$$5^{k-1} \lt N \le 5^k$$$.
Given $$$N$$$, determine on which of "MIT time", "MIT$$$^2$$$ time", etc. this person arrived at.
Input

The first line contains a single integer $$$T$$$ $$$(1 \leq T \leq 10^5)$$$ — the number of test cases.

The only line of each test case contains a single integer $$$N$$$ ($$$1 \le N \le 10^9$$$) — the number of minutes late to an event the person is.

Output

For each test case, output a single line that consists of either "MIT time" or "MIT^$$$k$$$ time" for some integer $$$k \geq 2$$$, corresponding to the time this person arrives at.

Example
Input
5
4
5
13
126
1
Output
MIT time
MIT time
MIT^2 time
MIT^4 time
MIT time
Note

In the first test case, $$$N = 4$$$, which is at most $$$5$$$, so this is MIT time.

In the second test case, $$$N = 5$$$, which is equal to $$$5$$$, so this is also MIT time.

In the third test case, $$$N = 13$$$, which is not more than $$$25$$$ but more than $$$5$$$, so this is MIT$$$^2$$$ time.

The fourth test case, $$$N = 126$$$, which is not more than $$$5^4=625$$$ but more than $$$5^3 = 125$$$, so this is MIT$$$^4$$$ time.

B. M(IT)+
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is bored in class one day and decides to write several strings. He calls a string repetitive if it is the character $$$\texttt{M}$$$ suffixed with one or more repetitions of $$$\texttt{IT}$$$. For example, the shortest repetitive strings are $$$\texttt{MIT}$$$, $$$\texttt{MITIT}$$$, $$$\texttt{MITITIT}$$$, ....

You are given a string $$$S$$$. Determine whether it can be expressed as the concatenation of one or more repetitive strings.

Input

The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 1000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$|S|$$$ ($$$3 \leq |S| \leq 2 \cdot 10^5$$$) — the length of $$$S$$$.

The second line of each test case contains the string $$$S$$$ consisting of uppercase Latin characters.

The sum of $$$|S|$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single string "YES" or "NO" (without the quotes) denoting if the string $$$S$$$ is a concatenation of repetitive strings.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Example
Input
6
5
MITIT
4
MITI
15
MITITMITMITITIT
6
MITITM
9
MITBEAVER
5
MIIIT
Output
YES
NO
YES
NO
NO
NO
Note

In the first test case, the entire string $$$\tt{MITIT}$$$ is repetitive.

In the second test case, it can be shown that the string is not a concatenation of repetitive strings.

In the third test case, the string is the following concatenation of repetitive strings: $$$\texttt{MITIT} + \texttt{MIT} + \texttt{MITITIT}$$$.

C. Traveling Salesman Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$N$$$ cities numbered from $$$1$$$ to $$$N$$$, the $$$i$$$-th of which is at coordinates $$$(x_i, y_i)$$$.

Busy Beaver wants to start at city $$$1$$$, visit every city exactly once, and return to city $$$1$$$.

To go from city $$$i$$$ to city $$$j$$$, it takes $$$|x_i - x_j + y_i - y_j|$$$ seconds. Find the minimum number of seconds for Busy Beaver to complete his trip.

Input

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 a single integer $$$N$$$ ($$$2 \leq N \leq 2 \cdot 10^5$$$) — the number of cities.

The $$$i$$$-th of the next $$$N$$$ lines of each test case contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) — the coordinates of the $$$i$$$-th city.

The sum of $$$N$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the minimum number of seconds needed for Busy Beaver to complete his trip.

Example
Input
3
5
0 0
-2 0
1 2
-1 3
0 1
3
0 0
1 4
3 4
2
-1 9
8 -4
Output
10
14
8
Note

In the first test case, we can take the path $$$1 \xrightarrow{3\,\text{seconds}} 3 \xrightarrow{1\,\text{second}} 4 \xrightarrow{1\,\text{second}} 5 \xrightarrow{3\,\text{seconds}} 2 \xrightarrow{2\,\text{seconds}} 1$$$ which takes $$$3+1+1+3+2=10$$$ seconds.

D. Scoreboard Screenshots
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The MITIT 2025 Winter Contest has successfully ended with the participation of $$$K$$$ teams, and Busy Beaver has to write a report for the contest.

For the report, Busy Beaver took $$$N$$$ screenshots of the scoreboard during the contest. Each screenshot contains the scores of all $$$K$$$ teams when the screenshot was taken.

Unfortunately, Busy Beaver forgot in which order he took the screenshots! He assumes that if there were no regrades during the contest, each team's score will be nondecreasing over time. Under this assumption, Busy Beaver wants to recover the order of the screenshots.

Determine if there is a valid ordering such that no team's score ever decreases over time, and if it exists, print any such order.

Input

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$2 \leq N \leq 400$$$; $$$1 \leq K \leq 400$$$) — the number of screenshots and teams.

The $$$i$$$-th of the next $$$N$$$ lines contains $$$K$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,k}$$$ ($$$0 \leq a_{i,j} \leq 900$$$), where $$$a_{i, j}$$$ is the score of the $$$j$$$-th team in the $$$i$$$-th screenshot.

Output

If a valid ordering exists, print "YES" (without quotes) on the first line. On the second line, print $$$N$$$ integers $$$b_1, \dots, b_N$$$, where $$$b_i$$$ is the index of the $$$i$$$-th screenshot in the valid ordering. If there are multiple solutions, you can print any of them.

If there is no valid ordering, print "NO" (without quotes).

Scoring

There are two subtasks for this problem.

  • ($$$20$$$ points) $$$K = 1$$$.
  • ($$$80$$$ points) No additional constraints.
Examples
Input
3 2
1 1
0 0
0 1
Output
YES
2 3 1
Input
3 3
0 0 1
1 0 0
0 1 0
Output
NO
Note

In the first test case, a valid ordering of the screenshots is:

  • Second screenshot: Team $$$1$$$ has score $$$0$$$, and Team $$$2$$$ has score $$$0$$$.
  • Third screenshot: Team $$$1$$$ has score $$$0$$$, and Team $$$2$$$ has score $$$1$$$.
  • First screenshot: Team $$$1$$$ has score $$$1$$$, and Team $$$2$$$ has score $$$1$$$.

In the second test case, no valid ordering exists because it is impossible to arrange the screenshots so that all scores for each team are nondecreasing over time.

E. Missing Number Queries
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver has an array of positive integers $$$a_1, \dots, a_N$$$, consisting of positive integers at most $$$N$$$. He needs to perform $$$Q$$$ operations on the array of two types:

  • $$$\texttt{1}\,~x\,~y$$$: Set $$$a_x \leftarrow y$$$.
  • $$$\texttt{2}\,~l\,~r$$$: Output any integer in the range $$$[1, N]$$$ that is not found in $$$a_l, a_{l+1}, \dots, a_r$$$.

Help answer all of Busy Beaver's queries! The input will be generated in such a way that an answer exists for all type $$$\texttt{2}$$$ queries.

Input

The first line contains two positive integers $$$N$$$ and $$$Q$$$ ($$$2 \le N \le 2 \cdot 10^5$$$; $$$1 \le Q \le 2 \cdot 10^5$$$).

The second line contains $$$N$$$ integers $$$a_1, \dots, a_N$$$ ($$$1 \le a_i \le N$$$).

Each of the next $$$Q$$$ lines contains three positive integers: either $$$\texttt{1}\,~x\,~y$$$ or $$$\texttt{2}\,~l\,~r$$$ ($$$1 \le x, y \le N$$$; $$$1 \le l \le r \le N$$$).

Additional constraint on the input: there is at least one type $$$\texttt{2}$$$ query, and every type $$$\texttt{2}$$$ query has an answer.

Output

For each type $$$\tt{2}$$$ query, output a single line containing the answer. If there are multiple possible answers for a query, you may output any of them.

Scoring

There are three subtasks for this problem.

  • ($$$20$$$ points) $$$N, Q \le 2000$$$.
  • ($$$30$$$ points) All queries are of type $$$\texttt{2}$$$.
  • ($$$50$$$ points) No additional constraints.
Example
Input
5 4
3 5 2 1 5
2 1 5
1 4 4
1 3 1
2 3 5
Output
4
2
Note

In the first query, the only integer from $$$1$$$ to $$$5$$$ missing from $$$[3, 5, 2, 1, 5]$$$ is $$$4$$$, so $$$4$$$ is the only possible answer.

After the second query, the array becomes $$$[3, 5, 2, 4, 5]$$$.

After the third query, the array becomes $$$[3, 5, 1, 4, 5]$$$.

The last query asks for an integer from $$$1$$$ to $$$5$$$ missing from $$$[1, 4, 5]$$$. Either $$$2$$$ or $$$3$$$ would be acceptable answers to this query.

F. AAB ↔ BAA
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is preparing for the MIT Mystery Hunt! He is playing a game on two strings $$$S_1$$$ and $$$S_2$$$, each consisting only of the letters $$$\texttt{A}$$$ and $$$\texttt{B}$$$. He can perform the following operation any number of times (possibly zero) on $$$S_1$$$:

  • Replace any contiguous substring $$$\texttt{AAB}$$$ with a contiguous substring $$$\texttt{BAA}$$$, or vice versa.
  • Replace any contiguous substring $$$\texttt{BBA}$$$ with a contiguous substring $$$\texttt{ABB}$$$, or vice versa.

Find the minimum number of operations needed to transform $$$S_1$$$ into $$$S_2$$$, or report that this is impossible.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^3$$$) — the number of test cases.

The only line of each test case contains two space-separated strings $$$S_1$$$ and $$$S_2$$$ ($$$1\le |S_1| = |S_2|\le 10^5$$$) consisting of characters $$$\texttt{A}$$$ and $$$\texttt{B}$$$.

The total length of all strings across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print the minimum number of operations you need to transform $$$S_1$$$ into $$$S_2$$$. If this is impossible, output $$$-1$$$.

Scoring

There are three subtasks for this problem.

  • ($$$10$$$ points) There exists exactly one $$$\texttt{B}$$$ in both $$$S_1$$$ and $$$S_2$$$.
  • ($$$20$$$ points) $$$S_1$$$ consists only of $$$\texttt{A}$$$s followed by $$$\texttt{B}$$$s, and $$$S_2$$$ consists only of $$$\texttt{B}$$$s followed by $$$\texttt{A}$$$s.
  • ($$$70$$$ points) No additional constraints.
Examples
Input
1
AABBB BABBA
Output
2
Input
1
AAAAAABBB BBBAAAAAA
Output
9
Note

In the first test case, we can perform two operations: $$$\color{red}{\texttt{AAB}}\texttt{BB} \to \color{blue}{\texttt{BAA}}\texttt{BB}$$$ and then $$$\texttt{BA}\color{red}{\texttt{ABB}} \to \texttt{BA}\color{blue}{\texttt{BBA}}$$$.

G. Grid and Numbers Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver and Calico Bear are playing a game with an $$$N$$$ by $$$M$$$ grid of nonnegative integers $$$a_{i,j}$$$, where initially no two edge-adjacent numbers are equal.

In a move, a player chooses a positive integer in the grid and decreases it by $$$1$$$, subject to the constraint that after the move, it still holds that no two edge-adjacent numbers are equal and that all numbers are non-negative. If a player has no legal moves on their turn, they lose, and the other player wins.

Busy Beaver moves first, and then the players alternate. Assuming both players play optimally, determine whether or not Busy Beaver has a winning strategy.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$) — the number of test cases. The description of each test case follows.

The first line of each test case contains two positive integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M, N \cdot M \leq 2.5 \cdot 10^5$$$) — the dimensions of the grid.

The $$$i$$$-th of the next $$$N$$$ lines contains $$$M$$$ space-separated nonnegative integers $$$a_{i,1}, \dots, a_{i,M}$$$ ($$$0 \leq a_{i,j} \leq 10^9$$$), where $$$a_{i,j}$$$ represents the integer in the grid in row $$$i$$$ and column $$$j$$$.

The sum of $$$N \cdot M$$$ over all test cases does not exceed $$$2.5 \cdot 10^5$$$.

Output

For each test case, output "YES" (without quotes) if Busy Beaver wins, and "NO" (without quotes) if Calico Bear wins.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Scoring

There are two subtasks for this problem.

  • ($$$20$$$ points) $$$0 \leq a_{i,j} \leq 100$$$.
  • ($$$80$$$ points) No additional constraints.
Example
Input
5
1 1
1
1 5
0 1 2 3 4
3 3
0 1 0
10 3 10
0 1 0
2 4
0 2 4 6
1 3 5 7
4 5
6 7 6 7 6
7 6 7 6 7
6 7 6 7 6
7 6 7 6 7
Output
Yes
No
Yes
No
No
Note

In the first test case, Busy Beaver can decrease the $$$1$$$ to a $$$0$$$. Then, Calico Bear has no moves, so Busy Beaver has a winning strategy.

In the second test case, Busy Beaver has no legal moves. Therefore, Calico Bear has a winning strategy.

In the third test case, Busy Beaver first decreases the central $$$3$$$ to a $$$2$$$. Then, regardless of which $$$10$$$ Calico Bear decreases, Busy Beaver can decrease the other one. Therefore, Calico Bear runs out of moves before Busy Beaver does, giving Busy Beaver a winning strategy.

H. Toy Marbles
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver has discovered that someone has mixed up his toy marbles!

There are $$$N$$$ containers, numbered from $$$1$$$ to $$$N$$$. The $$$i$$$-th container currently contains a single marble of color $$$c_i$$$.

Busy Beaver wants to tidy up his marbles so that the $$$i$$$-th container only contains marbles of color $$$i$$$. To achieve this, he can perform either of the following actions any number of times (possibly zero):

  • Swap the marbles in two containers $$$x$$$ and $$$y$$$. After this action, all marbles from container $$$x$$$ move to container $$$y$$$, and vice versa.
  • Move all the marbles from one container $$$y$$$ to another container $$$x$$$. After this action, container $$$y$$$ becomes empty, and all its marbles are moved to container $$$x$$$.

Find a way to organize the marbles using the minimum number of actions.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$) — the number of containers.

The second line contains $$$N$$$ integers $$$c_1, c_2, \dots, c_N$$$ ($$$1 \leq c_i \leq N$$$) — the marble initially in each container.

Output

On the first line, print a single integer $$$K$$$ — the minimum number of actions required.

On the next $$$K$$$ lines, describe the actions in order, one per line. Each action should be in one of the following formats:

  • $$$\texttt{1}~\,x~\,y$$$: Swap the marbles in containers $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq N$$$; $$$x \neq y$$$).
  • $$$\texttt{2}~\,x~\,y$$$: Move all marbles from container $$$y$$$ to container $$$x$$$ ($$$1 \leq x, y \leq N$$$; $$$x \neq y$$$).

If there are multiple ways to achieve the goal in the minimum number of actions, you may print any valid solution.

Scoring

There are two subtasks for this problem.

  • ($$$20$$$ points) All $$$c_i$$$ are distinct.
  • ($$$80$$$ points) No additional constraints.
Examples
Input
4
2 4 3 1
Output
2
1 2 4
1 1 2
Input
8
3 6 7 6 3 6 8 3
Output
6
2 6 4
2 6 2
1 8 7
1 7 3
2 3 1
2 3 5
Note

In the first test case, it is able to achieve the goal in two actions:

  • Swap the marbles in containers $$$2$$$ and $$$4$$$.
  • Swap the marbles in containers $$$1$$$ and $$$2$$$.

It is impossible to achieve the goal in less than two actions.

I. Snakes on a Grid
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

On a rectangular grid, a snake of size $$$k$$$ is defined to be a subset of cells that is formed by taking the first $$$k$$$ numbered cells in the following figure, where cells are numbered along a path with alternating right and down steps:

Additionally, subsets that are rotations, translations, or reflections of these shapes are also considered snakes. A grid is considered good if every connected component consisting of equal values in the grid is a snake.

Busy Beaver has an $$$N \times M$$$ grid with rows numbered $$$0, \dots, N-1$$$ and columns numbered $$$0, \dots, M-1$$$, where each cell $$$(i, j)$$$ in row $$$i$$$, column $$$j$$$ has a value $$$a_{ij}$$$. Since he's afraid of snakes, he wants you to answer $$$Q$$$ of the following queries: given a contiguous subrectangle of the grid, determine whether or not the subgrid is good.

Input

The first line contains 2 integers, $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 1000$$$) — the dimensions of the grid.

Each of the next $$$N$$$ rows contains $$$M$$$ integers, with the $$$j$$$-th element of the $$$i$$$-th row being $$$a_{i,j}$$$ ($$$1 \leq a_{i, j} \leq 10^6$$$) — the number written in the $$$j$$$-th cell of the $$$i$$$-th row.

The next line contains a single integer, $$$Q$$$ ($$$1 \leq Q \leq 5 \cdot 10^5$$$) — the number of queries.

The next $$$Q$$$ lines describe the queries, Each line contains 4 integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ $$$(0 \leq x_1 \leq x_2 \lt N,$$$ $$$ 0 \leq y_1 \leq y_2 \lt M)$$$, representing a query asking whether the rectangular subgrid with top left corner at $$$(x_1, y_1)$$$ and bottom right corner at $$$(x_2, y_2)$$$ is good.

Output

For each query, output "YES" (without quotes) if the corresponding subgrid consists only of snakes, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Scoring

There are four subtasks for this problem.

  • ($$$15$$$ Points): The sum of the areas of all the queries does not exceed $$$10^6$$$.
  • ($$$15$$$ Points): Every connected component of equal values in the grid has size at most $$$4$$$.
  • ($$$30$$$ Points): Every connected component of equal values in the grid has size at most $$$5$$$.
  • ($$$40$$$ Points): No additional constraints.
Example
Input
10 9
1 1 2 2 3 3 2 2 1
4 1 1 3 3 2 2 4 4
4 4 1 1 2 2 3 4 4
4 2 2 1 1 3 3 4 4
2 2 3 4 4 2 2 3 3
1 1 3 3 4 4 2 2 3
2 1 1 3 3 4 4 2 4
2 2 1 2 4 4 3 3 4
1 3 3 4 4 2 2 3 4
3 3 1 1 1 1 4 4 4
5
0 1 6 5
5 4 7 8
0 6 2 8
6 0 9 3
8 5 9 8
Output
YES
NO
NO
YES
NO
Note

If we color the sample grid with respect to the value in each cell, we get

In the first query, all components are snakes.
In the second query, the component that is not a snake is colored in black.
In the third query, the component that is not a snake is colored in black.
In the fourth query, all components are snakes.
In the fifth query, the component that is not a snake is colored in black.