MITIT Spring 2026 Invitationals Finals
A. Edit Distance Parity
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver has a sequence of $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ and a sequence of $$$M$$$ integers $$$b_1, b_2, \dots, b_M$$$.

For every $$$1\le i\le N$$$ and $$$1\le j\le M$$$, he computes the edit distance between the sequences $$$a_1, a_2, \dots, a_i$$$ and $$$b_1, b_2, \dots, b_j$$$. The edit distance between two sequences is defined as the minimum number of operations needed to go from the first sequence to the second sequence if the following three operations are allowed:

  • Insertions: Any integer can be inserted in any position in the sequence. The rest of the sequence remains the same. For example, in one operation, the sequence $$$1, 2, 3, 4$$$ can become $$$1, 2, 5, 3, 4$$$.
  • Deletions: Any integer present in the sequence can be deleted. The rest of the sequence remains the same. For example, in one operation, the sequence $$$1, 2, 3, 4$$$ can become $$$1, 2, 4$$$.
  • Replacements: Any integer present in the sequence can be replaced by another integer. The rest of the sequence remains the same. For example, in one operation, the sequence $$$1, 2, 3, 4$$$ can become $$$1, 2, 5, 4$$$.

As storing each of these values takes too much space, Busy Beaver only stores the least significant bit of each edit distance as $$$d_{i,j}$$$ ($$$0$$$ if it is even and $$$1$$$ if it is odd).

Unfortunately, Busy Beaver has lost the original sequences and only has the values $$$d_{i,j}$$$ for each $$$i$$$ and $$$j$$$. Help him find any pair of sequences $$$a_1, a_2, \dots, a_N$$$ and $$$b_1, b_2, \dots, b_M$$$ that will give the same values for $$$d_{i,j}$$$. It is possible that no original sequences can produce $$$d_{i,j}$$$, in which case you should report this.

Input

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

The first line of each test case contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 2\cdot 10^3$$$).

The $$$i$$$-th of the next $$$N$$$ lines of each test case contains $$$M$$$ integers $$$d_{i,1}, d_{i,2}, \dots, d_{i,M}$$$ ($$$0\le d_{i,j}\le 1$$$).

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

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

Output

For each test case, print a sequence of $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$0\le a_i\le 10^9$$$) on the first line, and a sequence of $$$M$$$ integers $$$b_1, b_2, \dots, b_M$$$ ($$$0\le b_i\le 10^9$$$) on the second line, such that all $$$d_{i,j}$$$ have the same parity as the edit distance between $$$a_1, a_2, \dots, a_i$$$ and $$$b_1, b_2, \dots, b_j$$$.

If there are no such sequences, print $$$-1$$$ on a single line.

It can be shown that if there are any sequences $$$a_1, a_2, \dots, a_N$$$ and $$$b_1, b_2, \dots, b_M$$$ that work, then there are sequences that satisfy $$$0\le a_i\le 10^9$$$ and $$$0\le b_i\le 10^9$$$.

Example
Input
2
5 3
1 0 1
0 0 0
1 1 1
1 1 0
0 1 0
4 6
1 1 0 1 0 1
1 1 1 0 1 0
0 1 1 1 0 1
1 0 0 0 0 0
Output
0 1 2 3 3 
3 3 1 
-1
Note

In the first test case, it can be checked that $$$[0,1,2,3,3]$$$ and $$$[3,3,1]$$$ work. For example, the edit distance for $$$[0, 1, 2, 3]$$$ and $$$[3, 3]$$$ is $$$3$$$ because the following operations work:

  1. Delete the first element of $$$[0,1,2,3]$$$ to get $$$[1,2,3]$$$
  2. Delete the first element of $$$[1,2,3]$$$ to get $$$[2,3]$$$
  3. Replace the first element of $$$[2,3]$$$ to get $$$[3,3]$$$
The least significant bit of $$$3$$$ is $$$1$$$, which matches the input.

In the second test case, it can be shown that there do not exist any valid sequences.

B. Fruit Blast
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Busy Beaver downloaded a new game on his phone and needs your help to play it!

In this game, a level consists of $$$N^2$$$ starting fruits in a line, each of a type numbered $$$1$$$ through $$$N$$$, with $$$N$$$ fruits of each type. A move consists of the following:

  • Choose a subset of $$$N$$$ fruits in the line, not necessarily consecutive, such that the chosen fruit types are $$$k, k+1, \dots, N, 1, \dots, k-1$$$ in order for some $$$1 \le k \le N$$$, and such that the starting fruit type $$$k$$$ is different from that of every previous move.
  • Remove the chosen fruits from the line.
Busy Beaver wins the level if he performs $$$N$$$ moves that remove every fruit from the line. (Formally: a level is winnable if it can be partitioned into $$$N$$$ subsequences, each a distinct cyclic shift of $$$1, 2, \dots, N$$$.)

You are given an array of $$$N^2$$$ integers $$$a_1, \dots, a_{N^2}$$$, each in the range $$$[0, N]$$$. Count the number of ways to replace each $$$0$$$ in the array with an integer in $$$[1, N]$$$, so that the resulting sequence is a winnable level. Output the answer modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$N$$$ ($$$2 \le N \le 11$$$).

The second line contains $$$N^2$$$ space-separated integers $$$a_1, \dots, a_{N^2}$$$ ($$$0 \le a_i \le N$$$).

It is guaranteed that each value in $$$[1, N]$$$ appears at most $$$N$$$ times in the array $$$a$$$.

Output

Output a single nonnegative integer: the number of possible winnable levels modulo $$$10^9 + 7$$$.

Scoring

There are three subtasks for this problem.

  • ($$$20$$$ points): $$$N = 4$$$.
  • ($$$20$$$ points): $$$a_i \neq 0$$$ for all $$$1 \le i \le N^2$$$.
  • ($$$60$$$ points): No additional constraints.
Examples
Input
2
0 0 1 0
Output
2
Input
4
1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 3
Output
30608
Note

In the first sample, we count two winnable levels:

  • The level $$$[1, 2, 1, 2]$$$, since we can remove the first and last fruits on move $$$1$$$ and remove the remaining fruits on move $$$2$$$.
  • The level $$$[2, 1, 1, 2]$$$, since we can remove the first two fruits on move $$$1$$$ and the remaining fruits on move $$$2$$$.
On the other hand, a level like $$$[2, 2, 1, 1]$$$ is not winnable, since it is not possible to choose a different starting fruit type on the second move compared to the first.

C. Tree Partition
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Busy Beaver has a very large tree with $$$N$$$ vertices, where $$$N = 2^k - 1$$$ for some integer $$$k \ge 1$$$. He wants to cut some of its edges such that the resulting forest has exactly $$$k$$$ connected components with $$$1, 2, 4, 8, \dots, 2^{k-1}$$$ vertices, respectively, and each component forms a simple path. Help Busy Beaver count the number of ways to cut edges to satisfy this condition, modulo $$$10^9 + 7$$$.

To reduce the size of the input, the tree is given in a compressed format. There are $$$M$$$ key vertices labelled $$$1,\dots,M$$$, connected by $$$M-1$$$ paths. The $$$i$$$-th path connects key vertices $$$u_i$$$ and $$$v_i$$$ and consists of $$$\ell_i$$$ edges, where $$$1+\sum_{i=1}^{M-1} \ell_i = N$$$.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 2^{60}-1$$$, $$$1 \le M \le \min(N,10^5)$$$, $$$N = 2^k - 1$$$ for some integer $$$k \ge 1$$$).

Each of the next $$$M-1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$\ell_i$$$ ($$$1 \le u_i,v_i \le M$$$, $$$u_i \ne v_i$$$, $$$1 \le \ell_i \le N-1$$$), specifying a path between $$$u_i$$$ and $$$v_i$$$ of length $$$\ell_i$$$.

The total number of vertices in the tree is equal to $$$N$$$ (formally, $$$1+\sum_{i=1}^{M-1} \ell_i = N$$$).

Output

Output a single integer: the number of such partitions modulo $$$10^9 + 7$$$.

Scoring

There are three subtasks for this problem.

  • ($$$10$$$ points): $$$N \le 2^9-1$$$.
  • ($$$30$$$ points): $$$N \le 2^{17}-1$$$.
  • ($$$60$$$ points): No additional constraints.
Examples
Input
7 4
1 2 1
1 3 2
1 4 3
Output
5
Input
1 1
Output
1
Note

In the first sample test case, the $$$5$$$ ways to partition the tree are as follows:

D. Sell in Pairs
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Busy Beaver sells mushrooms at his market. Each mushroom has a flavor index, an integer between $$$1$$$ and $$$N$$$ (inclusive). For each $$$i$$$, there are $$$a_i$$$ mushrooms of flavor index $$$i$$$.

Busy Beaver sells mushrooms only in pairs. Each mushroom can be used in at most one pair. A pair can be sold in one of the following ways:

  • Type 1: two mushrooms with the same flavor index for price $$$x$$$.
  • Type 2: two mushrooms whose flavor indices differ by exactly $$$1$$$ (e.g. $$$(3,4)$$$) for price $$$y$$$.

You are given $$$Q$$$ scenarios. In the $$$j$$$-th scenario, the prices are $$$(x_j, y_j)$$$. For each scenario, compute the maximum total profit Busy Beaver can obtain.

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 integers $$$N$$$ and $$$Q$$$ ($$$2 \le N \le 3 \cdot 10^5$$$, $$$1 \le Q \le 3 \cdot 10^5$$$).

The second line of each test case contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$0 \le a_i \le 10^6$$$).

Each of the next $$$Q$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i \le 10^6$$$, $$$0 \le y_i \le 10^6$$$), describing each scenario.

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

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

Output

Print $$$Q$$$ lines.

On the $$$i$$$-th line, output the maximum profit Busy Beaver can obtain in the $$$i$$$-th scenario.

Scoring

There are five subtasks for this problem.

  • ($$$15$$$ points): $$$Q = 1$$$, $$$1 \le x_1 \lt y_1$$$
  • ($$$30$$$ points): For each $$$i \in \{1, 2, \dots, Q\}$$$, $$$1 \le x_i \lt y_i$$$
  • ($$$15$$$ points): $$$Q = 1$$$, $$$1 \le y_1 \lt x_1$$$
  • ($$$30$$$ points): For each $$$i \in \{1, 2, \dots, Q\}$$$, $$$1 \le y_i \lt x_i$$$
  • ($$$10$$$ points): No additional constraints.
Example
Input
2
4 5
2 3 2 1
7 2
2 9
0 2
4 4
5 3
7 3
5 4 3 6 3 3 4
10 19
5 7
6 3
Output
21
36
8
16
16
247
92
75
Note

Below is the explanation for the first test case.

In the first scenario, it is optimal to sell three type 1 pairs as follows: $$$$$$ (1, 1), (2, 2), (3, 3) $$$$$$ which yields a profit of $$$21$$$.

In the second scenario, it is optimal to sell four type 2 pairs as follows: $$$$$$ (1, 2), (1, 2), (2, 3), (3, 4) $$$$$$ which yields a profit of $$$36$$$.

In the fifth scenario, it is optimal to sell two type 1 pairs and two type 2 pairs as follows: $$$$$$ (1, 1), (2, 2), (2, 3), (3, 4) $$$$$$ which yields a profit of $$$16$$$.

E. Planar Exact Cover
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The farmers' market has $$$N$$$ stalls and $$$M$$$ storage barns on a two-dimensional plane. There are $$$6M$$$ roads, each connecting a stall to a storage barn, such that no two roads intersect except at endpoints. In other words, the stalls and barns form a planar bipartite graph. Furthermore, every storage barn is connected to exactly $$$6$$$ distinct stalls.

Busy Beaver wants to select a subset of storage barns such that every stall is connected to exactly one selected barn by a road. How many ways are there to choose such a subset? As the answer may be large, 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 two integers $$$N$$$ and $$$M$$$ ($$$6 \le N \le 3 \cdot 10^5$$$, $$$N/6 \le M \le 10^5$$$, $$$N \equiv 0 \pmod 6$$$), the number of stalls and the number of barns, respectively.

The $$$i$$$-th of the next $$$M$$$ lines starts with the integer $$$6$$$, followed by $$$6$$$ distinct integers $$$a_{i1},\dots,a_{i6}$$$ ($$$1 \le a_{ij} \le N$$$ for all $$$1 \le j \le 6$$$), describing the stalls connected to the $$$i$$$-th barn in clockwise order.

The $$$i$$$-th of the next $$$N$$$ lines starts with an integer $$$d_i$$$ ($$$1 \le d_i \le M$$$), followed by $$$d_i$$$ distinct integers $$$b_{i1},\dots,b_{id_i}$$$ ($$$1 \le b_{ij} \le M$$$ for all $$$1 \le j \le d_i$$$), describing the barns connected to the $$$i$$$-th stall in clockwise order.

It is guaranteed that the input describes a valid planar combinatorial embedding.

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

The sum of $$$M$$$ across all test cases does not exceed $$$10^5$$$.

Output

Output a single integer for each test case: the number of ways, modulo $$$10^9+7$$$.

Scoring

There are two subtasks for this problem.

  • ($$$50$$$ points): The sum of $$$N$$$ across all test cases does not exceed $$$3 \cdot 10^3$$$, and the sum of $$$M$$$ across all test cases does not exceed $$$10^3$$$.
  • ($$$50$$$ points): No additional constraints.
Example
Input
2
12 4
6 1 2 3 4 5 6
6 7 8 9 10 11 12
6 4 3 2 1 12 11
6 10 9 8 7 6 5
2 1 3
2 1 3
2 1 3
2 1 3
2 1 4
2 1 4
2 2 4
2 2 4
2 2 4
2 2 4
2 2 3
2 2 3
12 4
6 1 2 3 4 5 6
6 6 7 8 9 10 11
6 1 12 6 11 10 9
6 8 7 6 5 4 3
2 1 3
1 1
2 1 4
2 1 4
2 1 4
4 1 4 2 3
2 2 4
2 2 4
2 2 3
2 2 3
2 2 3
1 3
Output
2
0
Note

In the first test case, the barns and stalls are as follows:

There are $$$2$$$ ways to select the subset: either choosing barns $$$1$$$ and $$$2$$$, or choosing barns $$$3$$$ and $$$4$$$.

In the second test case, the barns and stalls are as follows:

Note that the barns connected to stall $$$6$$$ are listed in clockwise order: $$$1, 4, 2, 3$$$. There are no ways to select a subset of barns such that every stall is connected to exactly one selected barn.