MITIT Spring 2026 Invitationals Qualification Round 2
A. Circular Board Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Wandering past the fresh produce, Busy Beaver's attention is captured by the local dairy vendor with a peculiar board game at his stall.

There is a circular board with $$$N$$$ squares numbered from $$$0$$$ to $$$N-1$$$. Busy Beaver plays a game on this board with an $$$N$$$ sided die labelled from $$$0$$$ to $$$N-1$$$. If he is on square $$$s$$$ and moves by $$$t$$$ steps, he will land directly on the square $$$s+t \pmod N$$$.

There is also one magical portal on the board, such that if the player lands exactly on square $$$X$$$, they are instantly teleported to square $$$Y$$$.

Busy Beaver rolls the die $$$K$$$ times and obtains the sequence $$$a_1, a_2, \dots, a_K$$$. From his initial square, Busy Beaver will move by $$$a_1$$$ steps, then by $$$a_2$$$ steps, and so on until he has completed all $$$K$$$ moves, where he moves by $$$a_i$$$ on the $$$i$$$-th move.

For each possible initial square from $$$0$$$ to $$$N-1$$$ (inclusive, except square $$$X$$$), determine the square that Busy Beaver lands on after all $$$K$$$ moves are completed (including any teleports).

Input

The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 2 \cdot 10^3$$$).

The first line of each test case contains four integers $$$N$$$, $$$K$$$, $$$X$$$, and $$$Y$$$ ($$$2 \le N \le 5 \cdot 10^5$$$, $$$1 \le K \le 5 \cdot 10^5$$$, $$$0 \le X, Y \lt N$$$, $$$X \ne Y$$$).

The second line of each test case contains $$$K$$$ integers $$$a_1, a_2, \dots, a_K$$$ ($$$0 \le a_i \lt N$$$).

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

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

Output

For each test case, output $$$N-1$$$ integers representing the square that Busy Beaver would land on if he started on square $$$i$$$, for all $$$0 \le i \lt N$$$ except for $$$i = X$$$.

Scoring

There are two subtasks for this problem.

  • ($$$20$$$ points): The sum of $$$N$$$ across all test cases does not exceed $$$5 \cdot 10^3$$$, and the sum of $$$K$$$ across all test cases does not exceed $$$5 \cdot 10^3$$$.
  • ($$$80$$$ points): No additional constraints.
Example
Input
3
5 1 0 1
1
5 3 0 1
1 2 3
20 10 3 1
4 15 9 2 6 5 3 5 8 9
Output
2 3 4 1 
2 4 4 1 
6 7 6 6 11 10 11 14 15 16 17 18 17 18 17 2 1 4 1
Note

In the first sample test case, there are $$$5$$$ squares on the board and one die roll that rolls $$$1$$$. The portal teleports the player from square $$$0$$$ to square $$$1$$$. For each of the starting squares, here is the sequence of events:

  • $$$0$$$: The portal teleports from this square; we do not need to output anything.
  • $$$1$$$: starts on square $$$1$$$, moves by $$$1$$$ to square $$$2$$$
  • $$$2$$$: starts on square $$$2$$$, moves by $$$1$$$ to square $$$3$$$
  • $$$3$$$: starts on square $$$3$$$, moves by $$$1$$$ to square $$$4$$$
  • $$$4$$$: starts on square $$$4$$$, moves by $$$1$$$ to square $$$0$$$ and teleports to square $$$1$$$

In the second sample test case, there are $$$5$$$ squares on the board and three die rolls that roll $$$1,2,3$$$ respectively. The portal teleports the player from square $$$0$$$ to square $$$1$$$. For each of the starting squares, here is the sequence of events:

  • $$$0$$$: The portal teleports from this square; we do not need to output anything.
  • $$$1$$$: starts on square $$$1$$$, moves by $$$1$$$ to square $$$2$$$, moves by $$$2$$$ to square $$$4$$$, moves by $$$3$$$ to square $$$2$$$
  • $$$2$$$: starts on square $$$2$$$, moves by $$$1$$$ to square $$$3$$$, moves by $$$2$$$ to square $$$0$$$ and teleports to square $$$1$$$, moves by $$$3$$$ to square $$$4$$$
  • $$$3$$$: starts on square $$$3$$$, moves by $$$1$$$ to square $$$4$$$, moves by $$$2$$$ to square $$$1$$$, moves by $$$3$$$ to square $$$4$$$
  • $$$4$$$: starts on square $$$4$$$, moves by $$$1$$$ to square $$$0$$$ and teleports to square $$$1$$$, moves by $$$2$$$ to square $$$3$$$, moves by $$$3$$$ to square $$$1$$$

B. Food Fight
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is causing chaos at the farmers' market again! This time, he is starting a food fight among the stalls.

The stalls are numbered from $$$1$$$ to $$$N$$$ and are connected by $$$N-1$$$ roads, forming a tree. In other words, it is possible to travel from any stall to any other stall by following the roads, and there is exactly one simple path between any two stalls.

Busy Beaver assigns each stall to either Team Potato or Team Tomato as follows:

  • He starts at stall $$$1$$$, travels along the roads, visits every stall, and finally returns to stall $$$1$$$. Among all such routes, he chooses one with the minimum possible total number of roads traversed.
  • Stall $$$1$$$ is assigned to Team Potato.
  • Whenever Busy Beaver visits a stall for the first time (other than stall $$$1$$$), he immediately assigns it to one of the two teams. To keep the fight fair, he alternates the team assignment each time he assigns a new stall. That is, if the most recently assigned stall was assigned to Team Potato, then the next newly visited stall must be assigned to Team Tomato, and vice versa.

Your task is to count the number of possible team assignments. Note that different minimum-length routes may produce the same final assignment; such assignments should be counted only once. Since the answer may be enormous, output it modulo $$$10^9+7$$$.

Input

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

The first line of each test case contains a single integer $$$N$$$ ($$$2 \le N \le 10^5$$$).

Each of the next $$$N-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$, $$$u \neq v$$$), indicating that there is a road between stalls $$$u$$$ and $$$v$$$.

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 number of possible final team assignments modulo $$$10^9+7$$$.

Scoring

There are two subtasks for this problem.

  • ($$$10$$$ points): The stalls form a star graph rooted at stall $$$1$$$. More specifically, stall $$$1$$$ has $$$N-1$$$ roads connected to it.
  • ($$$20$$$ points): The stalls form a binary tree rooted at stall $$$1$$$. More specifically, stall $$$1$$$ has at most $$$2$$$ roads connected to it, and every other stall has at most $$$3$$$ roads connected to it.
  • ($$$70$$$ points): No additional constraints.
Example
Input
4
4
1 2
2 3
2 4
7
1 2
1 3
1 4
1 5
1 6
1 7
7
1 2
1 3
2 4
2 5
3 6
3 7
7
1 2
1 3
1 4
2 5
2 6
2 7
Output
2
20
8
12
Note

The sample contains $$$4$$$ test cases:

  • Test case $$$1$$$ satisfies the second subtask (binary tree).
  • Test case $$$2$$$ satisfies the first subtask (star graph).
  • Test case $$$3$$$ satisfies the second subtask (binary tree).
  • Test case $$$4$$$ satisfies the third subtask (no additional constraints).

In the first test case, one possible team assignment is shown below.

One minimum-length route is: $$$$$$ 1 \to 2 \to 3 \to 2 \to 4 \to 2 \to 1. $$$$$$

Its total length is $$$6$$$, which is the smallest possible for a route that starts at stall $$$1$$$, visits every stall, and returns to stall $$$1$$$.

The stalls are then assigned in the order in which they are first visited:

  • Stall $$$1$$$ is assigned to Team Potato.
  • Stall $$$2$$$ is assigned to Team Tomato.
  • Stall $$$3$$$ is assigned to Team Potato.
  • Stall $$$4$$$ is assigned to Team Tomato.

The other possible team assignment is obtained by visiting stall $$$4$$$ before stall $$$3$$$, which swaps their teams. Therefore, the total number of possible team assignments is $$$2$$$.

C. Banana Lounge
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Busy Beaver loves spending his afternoons at MIT's Banana Lounge. He decides to help out by stacking banana boxes! He needs to collect the inventory across $$$N$$$ consecutive rooms, arranged in a single row and numbered $$$1$$$ to $$$N$$$ from left to right. Due to the quirky architecture of MIT's buildings, each room $$$i$$$ has a specific ceiling clearance height, $$$h_i$$$.

Busy Beaver needs to select one room $$$k$$$ ($$$1 \le k \le N$$$) to serve as the Main Hub. Then, $$$N$$$ of his friends, one from each room, each carry a vertical stack of banana boxes from their starting room $$$i$$$ directly to the hub room $$$k$$$. Since they must walk in a straight line, the maximum number of boxes they can carry is limited by the minimum clearance on their path.

Formally, the number of banana boxes delivered by the friend starting at room $$$i$$$ to the hub room $$$k$$$ is:

  • $$$\min(h_i, h_{i+1}, \dots, h_k)$$$ if $$$i \le k$$$.
  • $$$\min(h_k, h_{k+1}, \dots, h_i)$$$ if $$$i \gt k$$$.
The total number of banana boxes gathered at the hub is the sum of the boxes delivered by all $$$N$$$ friends, which is: $$$$$$ \sum_{i = 1}^{k - 1}\min(h_i,\dots,h_k) + h_k + \sum_{i = k + 1}^N \min(h_k,\dots,h_i) $$$$$$ Fortunately, Busy Beaver has a friend in MIT Facilities. Before the friends start carrying the boxes, he can request to renovate at most one room (which cannot be the chosen hub room $$$k$$$) to change its clearance height $$$h_i$$$ to any value.

What is the maximum total number of banana boxes Busy Beaver can gather at the Main Hub after choosing the optimal hub location $$$k$$$ and performing at most one ceiling renovation?

Input

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

The first line of each test case contains a single integer $$$N$$$ ($$$2 \leq N \leq 10^6$$$).

The next line of each test case contains $$$N$$$ space-separated integers $$$h_1,h_2,\dots,h_N$$$ ($$$1 \leq h_i \leq 10^9$$$).

The sum of $$$N$$$ across all test cases does not exceed $$$10^6$$$.

Output

For each test case, output one line containing one integer: the answer for the test case.

Scoring

There are two subtasks for this problem.

  • ($$$30$$$ points): The sum of $$$N$$$ across all test cases does not exceed $$$3\cdot 10^3$$$.
  • ($$$70$$$ points): No additional constraints.
Example
Input
2
5
1 10 1 10 1
5
10 10 10 10 10
Output
32
50
Note

In the first sample case, the best option is to choose hub $$$k = 2$$$ and renovate $$$h_3$$$ to at least $$$10$$$, allowing the middle three friends to all carry $$$10$$$, for a total of $$$32$$$.

In the second sample case, no renovation can increase the number of banana boxes, so the answer is $$$50$$$.

D. Infinite Market
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is at the farmers' market! There are $$$N$$$ stalls, numbered from $$$1$$$ to $$$N$$$. There are also $$$M$$$ directed paths between stalls. The $$$i$$$-th path goes from stall $$$a_i$$$ to stall $$$b_i$$$, where $$$a_i\ne b_i$$$. It is guaranteed that no paths leave stall $$$N$$$, at least one path leaves every stall other than stall $$$N$$$, no two paths have the same starting and ending stalls, and for every path going from stall $$$r_1\ne N$$$ to $$$r_2\ne N$$$, there is another path going from $$$r_2$$$ to $$$r_1$$$. Each path $$$i$$$ that does not end at stall $$$N$$$ has a unique successor path $$$s_i$$$. It is guaranteed that path $$$s_i$$$ can be used after path $$$i$$$. In other words, $$$a_{s_i} = b_i$$$. Each stall also has an integer counter $$$x_i$$$.

Busy Beaver chooses a stall to start his shopping. First, Busy Beaver travels along any path leaving his starting stall. Then, every minute, supposing Busy Beaver has just traveled along path $$$p$$$ from $$$a_p$$$ to $$$b_p$$$, he performs the following two actions:

  1. He reaches $$$b_p$$$ and increments $$$x_{b_p}$$$ by $$$1$$$.
  2. If $$$x_{b_p}$$$ is a multiple of some positive integer $$$K$$$, Busy Beaver will go along path $$$s_p$$$ next. Otherwise, Busy Beaver travels along any path leaving $$$b_p$$$.
If Busy Beaver ever reaches stall $$$N$$$, he will leave the farmers' market. Given the map of the farmers' market, does there exist a positive integer $$$K$$$, initial integer values for all $$$x_i$$$, and a starting stall for Busy Beaver, so that he can stay in the market forever?
Input

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

The first line of each test case contains two space-separated integers $$$N$$$ and $$$M$$$ ($$$2 \le N \le 2\cdot 10^5$$$, $$$1 \le M \le 4\cdot 10^5$$$) — the total number of stalls and the number of directed paths in the farmers' market.

The $$$i$$$-th of the next $$$M$$$ lines of each test case contains three space-separated integers $$$a_i$$$, $$$b_i$$$, and $$$s_i$$$ ($$$1 \le a_i, b_i \le N$$$, $$$a_i \neq b_i$$$, $$$1 \le s_i \le M$$$) — indicating that the $$$i$$$-th path goes from stall $$$a_i$$$ to stall $$$b_i$$$, and its unique successor path is $$$s_i$$$. If $$$b_i=N$$$, then $$$s_i=-1$$$, indicating the path has no successor.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2\cdot 10^5$$$ and the sum of $$$M$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.

Output

For each test case, if there exists a value for $$$K$$$, initial values for all $$$x_i$$$, and a starting stall such that Busy Beaver can stay in the market forever without ever reaching stall $$$N$$$, print "YES". Otherwise, print "NO".

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.

Example
Input
2
5 9
1 2 3
2 1 7
2 3 5
3 2 2
3 1 9
1 3 4
1 4 8
4 1 1
1 5 -1
4 9
1 2 8
2 1 7
2 3 9
3 2 8
3 1 7
1 3 9
1 4 -1
2 4 -1
3 4 -1
Output
YES
NO
Note

The market for test case $$$1$$$ is shown below. The stalls are circled and the paths are in blue. It is possible for Busy Beaver to stay in the market forever. A solution is to set $$$K=2$$$, $$$x=[0,0,0,0,0]$$$, and initially put Busy Beaver at stall $$$1$$$. Busy Beaver will then travel along the closed path through the stalls $$$1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 4\rightarrow 1$$$, repeating forever. When Busy Beaver reaches stall $$$1$$$ with path $$$5$$$, $$$x_1$$$ becomes odd, and when Busy Beaver reaches stall $$$1$$$ with path $$$8$$$, $$$x_1$$$ becomes even. This ensures that Busy Beaver is never forced to take path $$$9$$$ (which leads to stall $$$N$$$).

The market for test case $$$2$$$ is shown below. It can be shown that it is impossible for Busy Beaver to stay in the market forever.

E. Street Magician
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

While visiting the farmers' market, Busy Beaver stops to watch a street magician. The magician presents a row of $$$N$$$ boxes, holding $$$M$$$-bit nonnegative integers $$$a_1, a_2, \dots, a_N$$$, where $$$0 \le a_i \lt 2^M$$$ for all $$$1 \le i \le N$$$.

The magician magically sorts the boxes into non-decreasing order by a series of magic swaps. In a single magic swap, the magician chooses an index $$$i$$$ ($$$1 \le i \lt N$$$) such that the binary representations of $$$a_i$$$ and $$$a_{i+1}$$$ differ by exactly one bit, and swaps $$$a_i$$$ and $$$a_{i+1}$$$.

Watching the performance, Busy Beaver wonders about the limits of this trick. Out of all $$$2^{MN}$$$ possible initial values of $$$a_1, a_2, \dots, a_N$$$ in the boxes, how many of them can be sorted into non-decreasing order using magic swaps? Since this number may be large, Busy Beaver is content with finding it modulo $$$10^9+7$$$.

Input

The first and only line of input contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N,M \le 50$$$).

Output

Output a single integer: the number of sequences that can be sorted using magic swaps, modulo $$$10^9+7$$$.

Scoring

There are five subtasks for this problem.

  • ($$$10$$$ points): $$$1 \le N,M \le 5$$$.
  • ($$$20$$$ points): $$$1 \le M \le 4$$$.
  • ($$$10$$$ points): $$$1 \le M \le 10$$$.
  • ($$$10$$$ points): $$$1 \le M \le 15$$$.
  • ($$$50$$$ points): No additional constraints.
Examples
Input
3 2
Output
44
Input
50 1
Output
898961331
Input
10 10
Output
649370314
Note

In the first sample, one sequence that can be sorted using magic swaps is $$$[a_1,a_2,a_3] = [3,1,2]$$$, as follows:

  1. Choose $$$i = 1$$$. Note that $$$a_1 = 3$$$ and $$$a_2 = 1$$$ differ by exactly one bit, so this is a magic swap. The sequence becomes $$$[1,3,2]$$$.
  2. Choose $$$i = 2$$$. Note that $$$a_2 = 3$$$ and $$$a_3 = 2$$$ differ by exactly one bit, so this is a magic swap. The sequence becomes $$$[1,2,3]$$$, which is in non-decreasing order.
Out of the $$$2^{3 \cdot 2} = 64$$$ initial sequences, $$$44$$$ of them can be sorted using magic swaps.