2026 ICPC Gran Premio de Mexico 2da Fecha
A. A simple problem
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Find the number of different strings of length $$$k$$$ that you can get by concatenating prefixes of a given string $$$S$$$.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 2000$$$)  — the number of test cases. The description of test cases follows.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq k \leq 2000$$$)  — the length of $$$S$$$ and the size of the desired strings.

The second line contains a string $$$S$$$ consisting of $$$n$$$ lowercase letters. It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$2000$$$.

Output

For each test case, print a line with one integer  — the answer to the problem. Since the answer may be huge, print it modulo $$$998244353$$$.

Example
Input
4
5 7
aaaaa
4 4
abcd
3 3
aba
7 15
abacaba
Output
1
8
3
2809

B. Baus Stream
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Baus, the top laner of Los Ratones, is legendary for his Sion strategy: equipping Ghost and Teleport, ignoring every enemy on the map, and running in a straight line toward the enemy Nexus. The champion dies on impact, but the passive keeps him rolling, dealing massive damage to structures even in death. It is chaotic, it is reckless, and it works.

When Baus announced a dedicated Sion stream, the Los Ratones community went wild. Thousands of viewers flooded the channel, filling the chat with messages. Bastian and Franchesco, the team's two most dedicated fans and self-appointed chat moderators, recorded the username of every viewer who sent at least one message during the stream. All usernames in the registry are distinct.

After the stream, they realized the list had grown too large to manage. They agreed it needed to be trimmed by exactly $$$k$$$ usernames enough to keep it under control, but no more, since every extra deletion risks removing a genuine fan. The only moderation tool at their disposal works as follows: given a search string $$$t$$$, the system displays all usernames that begin with $$$t$$$, and a single confirmation removes every username shown in those results.

Bastian and Franchesco need to choose which $$$k$$$ usernames to remove and execute the deletions using as few searches as possible. Can you help them?

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^4$$$, $$$1 \le k \lt n$$$), the number of usernames in the registry and the number of usernames to remove.

The next $$$n$$$ lines each contain one username consisting of lowercase English letters. All usernames are distinct. The sum of the lengths of all usernames does not exceed $$$10^5$$$.

Output

Print a single integer. The minimum number of search operations needed to remove exactly $$$k$$$ usernames from the registry.

Examples
Input
5 2
sion
sionfan
sionbot
run
runner
Output
1
Input
5 4
sion
sionfan
sionbot
run
runner
Output
2

C. Counting heroes
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The evil math magician Matematicus is about to destroy the world! and he has given Ana, Beto and Carlos a last chance to defeat him. He will give them a number $$$N$$$ and each one of them will guess a random number between $$$1$$$ and $$$N$$$, and if the number guessed by Ana and by Beto added equals the number guessed by Carlos, they'll pass the test. If they manage to do this $$$k$$$ times, the world will be saved.

To make it more interesting Matematicus used his magic to ensure that the number that Ana guesses is smaller than the number guessed by Beto, and that the number guessed by Beto is smaller than the number guessed by Carlos. Our heros have asked you, what's the probability the world will be saved by them?

Input

On the first line a number $$$k$$$, ($$$1\leq k\leq 10^6$$$) the number of times they'll have to do the test. On the next $$$k$$$ lines, a number $$$N_i$$$($$$3\leq N\leq 10^6$$$) the $$$i$$$-th number given by Matematicus.

Output

$$$k$$$ lines, in the $$$i$$$-th line a number representing the probability that they passed the first $$$i$$$ tests. It can be proven that the answer can be represented as a rational number $$$\frac{p}{q}$$$ with coprime $$$p$$$ and $$$q$$$. You need to output $$$p \cdot q^{-1}$$$ mod $$$10^{9}+7$$$.

Examples
Input
1
3
Output
1
Input
3
3
5
10
Output
1
800000006
466666670

D. Dragon King's Palace
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Dragon King's palace is unlike any structure in the mortal realm. Rather than walls and corridors, its grounds consist of two great circular gardens, each centered around an enchanted fountain. The gardens may overlap, lie apart, or one may even contain the other — the Dragon King enjoys architectural ambiguity.

Once a century, the Dragon King holds his Grand Procession: an honor guard must march in a perfectly straight line, never stepping outside the palace grounds (the union of the two gardens). To impress visiting dignitaries, the procession route must span at least $$$K$$$ units in length.

You are given two circles $$$C_1$$$ and $$$C_2$$$ in the plane, with centers $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$ and radii $$$r_1$$$, $$$r_2$$$ respectively. Determine whether there exists a line segment of Euclidean length at least $$$K$$$ such that every point on the segment belongs to $$$C_1 \cup C_2$$$ — that is, lies within or on the boundary of at least one of the two gardens.

Input

The first line contains a single integer $$$T$$$ $$$(1 \le T \le 10^3)$$$, the number of procession scenarios the Dragon King wishes to evaluate.

Each test case consists of three lines.

The first line contains three integers $$$x_1$$$, $$$y_1$$$, and $$$r_1$$$ $$$(-10^9 \le x_1,\, y_1 \le 10^9,\ 1 \le r_1 \le 10^6)$$$, the center and radius of the first garden $$$C_1$$$.

The second line contains three integers $$$x_2$$$, $$$y_2$$$, and $$$r_2$$$ $$$(-10^9 \le x_2,\, y_2 \le 10^9,\ 1 \le r_2 \le 10^6)$$$, the center and radius of the second garden $$$C_2$$$.

The third line contains a single integer $$$K$$$ $$$(1 \le K \le 4 \times 10^6)$$$, the minimum required length of the procession route. All values are integers.

Output

For each test case, print YES if a valid procession route exists, NO otherwise.

Examples
Input
1
0 0 5
0 0 3
10
Output
YES
Input
1
0 0 3
10 0 3
7
Output
NO
Input
1
0 0 5
4 0 5
12
Output
YES

E. Evil "Taquero"
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have been hired by a Taqueria who's facing a serious problem, its clients keep calling the "taquero" by "mesero", and he refuses to answer to it. So now, you have to create a censorship program that replaces every instance of the word "mesero" with "taquero".

Input

A string $$$S$$$ ($$$1\leq |S| \leq 10^6$$$) made up of lowercase letters with no spaces, the string you'll have to process.

Output

A string $$$R$$$, the string $$$S$$$ after replacing all instances of "mesero" with "taquero".

Examples
Input
mesero
Output
taquero
Input
icpc
Output
icpc

F. Forever in love
time limit per test
2 s
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given $$$n$$$ trapezoids, all of height $$$1$$$.

Trapezoid $$$i$$$ is described by four positive integers $$$l_{i,0}$$$, $$$r_{i,0}$$$, $$$l_{i,1}$$$, $$$r_{i,1}$$$. At height $$$y = 0$$$, it occupies the interval $$$[-l_{i,0}, r_{i,0}]$$$. At height $$$y = 1$$$, it occupies the interval $$$[-l_{i,1}, r_{i,1}]$$$.

Equivalently, its vertices are $$$(-l_{i,0}, 0)$$$, $$$(r_{i,0}, 0)$$$, $$$(r_{i,1}, 1)$$$, $$$(-l_{i,1}, 1)$$$.

Before placing a trapezoid, you may reflect it with respect to the horizontal axis, the vertical axis, both, or neither.

The following picture shows the four possible orientations of the same trapezoid.

You have to place all trapezoids inside the strip $$$0 \le y \le 1$$$. You may translate each trapezoid only along the $$$x$$$ axis, and you may choose any left-to-right order.

The interiors of different trapezoids must not intersect, but they are allowed to touch at the boundary.

The width of a placement is $$$\max_x - \min_x$$$, where $$$\max_x$$$ is the largest $$$x$$$-coordinate covered by at least one trapezoid, and $$$\min_x$$$ is the smallest one.

Find the minimum possible width.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 20$$$).

Each of the next $$$n$$$ lines contains four integers $$$l_{i,0}$$$, $$$r_{i,0}$$$, $$$l_{i,1}$$$, $$$r_{i,1}$$$ ($$$1 \le l_{i,0}, r_{i,0}, l_{i,1}, r_{i,1} \le 10^9$$$).

For the given input format, it can be proved that the answer is always an integer.

Output

Print one integer: the minimum possible width.

Examples
Input
3
1 8 8 1
4 4 4 4
8 1 1 8
Output
33
Input
5
2 9 9 2
8 3 1 10
3 8 10 1
5 5 5 5
1 7 6 2
Output
58
Note

In the first sample, one optimal placement uses the order $$$1, 3, 2$$$. In the picture below, the left panel shows the order $$$1, 2, 3$$$, while the right panel shows the order $$$1, 3, 2$$$.

The right panel has width $$$33$$$, so the answer is $$$33$$$.

G. Group forming
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It's school time, and Professor Carlos's next assignment is going to be done on pairs. And he wants to avoid as much problems as possible, so he has decided that the pairs shouldn't be friends. He has made a list of who is friend with who, and knows that the friendship in the school follows 3 rules:

  • if $$$A$$$ is friend with $$$B$$$ and $$$B$$$ is friend with $$$C$$$ then $$$A$$$ is friend with $$$C$$$.
  • if $$$A$$$ is friend with $$$B$$$ then $$$B$$$ is friend with $$$A$$$.
  • Everyone is friend with themselves.

So given the list of $$$M$$$ friendships he has observed and the number of students $$$N$$$, help him make as many pair of non friends as possible.

Input

The first line of input contains two integers $$$N$$$ and $$$M$$$ ($$$1\leq N\leq 10^5$$$, $$$0\leq M \leq 10^6$$$) — The number of students and the number of friendships Carlos has registered.

The next $$$M$$$ lines contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$0\leq a_i, b_i\leq N-1$$$) — The pair $$$(a_{i}, b_{i})$$$ means that $$$a_i$$$ is friend with $$$b_i$$$.

Output

In the first line a number $$$k$$$ indicating the maximum number of pairs Carlos can make. In the next $$$k$$$ lines, 2 numbers $$$c_i$$$ and $$$d_i$$$ representing the $$$i$$$-th pair you would make.

Example
Input
5 3
0 1
1 2
3 4
Output
2
2 4
1 3

H. Huron Airlines
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Legendary Huron airlines is going through a tough time: tariffs are increasing and their customer satisfaction is plummeting. A particular customer complaint that they receive often is that the time that it takes to board one of their planes is too long. To try and tackle this problem their optimization department is developing an algorithm and your job is to test it.

For a set of $$$N$$$ passengers the algorithm outputs a fixed order $$$A$$$ in which the passengers are supposed to board the plane. Given this order your job is to compute how much time will it take to onboard the $$$N$$$ passengers. For the $$$i$$$-th passenger you know in what row ($$$r_i$$$) their seat is and how many seconds ($$$k_i$$$) it takes them to store their luggage in the overhead compartment. It takes $$$1$$$ second to move from the $$$\rho$$$-th row to the $$$(\rho+1)$$$-th one, thus the total time it takes the $$$i$$$-th passenger to take a seat is $$$r_i + k_i$$$ (since the door can be seen as row $$$0$$$ of the plane). It's impossible for two or more passengers to be on the same row at the same exact time. Hence, no two passengers can onboard at the same time.

A new rule was added since no one wants to wait on the aisle. This rule states that a passenger is only allowed to start onboarding if all of the previous passengers that are seating in a closer row (to the door) than them have already seated. More formally, this rule states that the $$$i$$$-th passenger can only begin to onboard the plane at time $$$\tau$$$ if there's no $$$j \lt i$$$ such that $$$r_j \leq r_i$$$ and $$$t_j + r_j + k_j \gt \tau$$$, where $$$t_j$$$ is the time at which the $$$j$$$-th passenger started onboarding the plane.

Help the Legendary Huron airlines improve their customer satisfaction!

Input

In the first line you will get one integer $$$N$$$ $$$(1 \leq N \leq 4 \cdot 10^5)$$$ — the number of passengers that will onboard the plane.

In the next line you will get $$$N$$$ integers $$$r_i$$$ $$$(1 \leq r_i \leq 10^5)$$$ — the row for the $$$i$$$-th passenger. It's confirmed that any row doesn't repeat more than $$$4$$$ times in the input.

In the last line you will get $$$N$$$ integers $$$k_i$$$ $$$(1 \leq k_i \leq 10^9)$$$ — the time it takes the $$$i$$$-th passenger to store their luggage in the overhead compartment.

Output

Print a single integer — the time, in seconds, that it takes to onboard the $$$N$$$ passengers onto the plane.

Examples
Input
2
10 5
1 2
Output
11
Input
2
10 5
1 6
Output
12
Input
3
4 5 2
5 3 1
Output
17

I. I don't have the name I was supposed to have
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Problem B — Bad Latex from 2026 ICPC Gran Premio de Mexico - Primera Fecha had some trouble with its testcases. Apparently, the input format didn't specify correctly the format restrictions on the testdata and contestants ended up very confused about it.

This time, you will help Racsó by coding a validator for the currently generated test cases. The restrictions Racsó set up so that the problem becomes easy to solve are the following:

  • The test data will only consist of letters (could be in lowercase or uppercase), digits, spaces and the special symbols !?.,;$#^{}_=+*.
  • There won't be any leading or trailing space in the lines of the test data.
  • All subscripts and superscripts will appear with integers with the exact format X_{Y} or X^{Y} (where $$$X$$$ is either an integer or an alphanumeric string and $$$Y$$$ is an integer) and they will not be nested. These should be the only possible structures in which characters _^{} appear.
  • In addition, every digit is surrounded by other digits, letters or spaces, with the subscripts/superscripts being the only exception to this.
  • Numbers won't have leading zeros.
  • There are no consecutive spaces.
  • If a line ends with an integer and the next one starts with an integer, these two are not part of the same value.

Can you handle these test cases?

Input

The first line of input contains an integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — The number of lines of the test case.

The following $$$n$$$ lines contain a string $$$s_{i}$$$ ($$$1 \leq |s_{i}| \leq 1000$$$) — The $$$i$$$-th line contains the contents of the $$$i$$$-th line of the test case.

It is guaranteed that all $$$s_{i}$$$ consists of printable ASCII characters (codes in range $$$[32, 126]$$$).

Output

Print a single line — "Ok" if the test case is valid or "Validation failed" otherwise.

Examples
Input
4
This example shows a value
Of 1000000000 without being compressed to 10^{9}
Which is annoying when read. $ S_{10} = 2^{100000} + 780000 $
My ID is RA180000 but that was back in the year 20000
Output
Ok
Input
3
This example should show
An incorrect test case since 100.10^{1000}
Should not be correct.
Output
Validation failed
Input
2
Another simple example with multiple incorrect braces
$$ 10^{100} = 10 {14} $$
Output
Validation failed
Input
1
$ 100^{2x + 1} $ should not be possible
Output
Validation failed
Input
1
  Leading and Trailing
Output
Validation failed
Input
2
Hey, this one looks like it is not valid.
However, it is even if it contains a single 0
Output
Ok
Input
1
Hello,  this has two  consecutive spaces.
Output
Validation failed
Input
1
Wait, is 000 valid?
Output
Validation failed
Input
1
No nested $ X_{10_{11}} $ allowed!
Output
Validation failed
Input
1
My email is [email protected]
Output
Validation failed

J. Jorge likes "sum over all subarrays" problems
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jorge, as a dedicated ICPC participant, was upsolving the problems from the 2026 ICPC Gran Premio de Mexico 1ra Fecha contest. The last problem he upsolved was $$$F(x,l,r)$$$, a problem that asks contestants to find the sum of a function over all subarrays of a given array. Immediately after he finished upsolving, he started thinking about more problems that ask for the sum of a function over all subarrays, and he came up with the following problem:

For a given array $$$A=[a_1,a_2,\dots,a_n]$$$, Jorge defines $$$F(l,r)$$$ as:

$$$$$$ F(l,r)=\prod_{i=l}^r a_i $$$$$$

Jorge defines the value of the array $$$A$$$ as the sum of $$$F(l,r)$$$ over all its subarrays:

$$$$$$ \sum_{l=1}^n \sum_{r=l}^n F(l,r) $$$$$$

Jorge immediately found the answer to this problem, so he thought that it was too easy. Then he thought, "What if we now find the sum of the values of all permutations of length $$$n$$$?" This problem is not as trivial as Jorge thought, so he asks you to solve it.

You are given an integer $$$n$$$. Help Jorge find the sum of the values of all permutations of the integers $$$1,2,\dots,n$$$. Since the answer might be huge, find it modulo $$$998244353$$$.

Input

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

Each test case consists of a single line with an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)  — the length of the permutation.

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

Output

For each test case, print a line with an integer  — the answer to the problem modulo $$$998244353$$$.

Example
Input
5
1
2
3
5
100
Output
1
10
116
41532
586129619
Note

Remember to upsolve all the problems!

K. K Vertices
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two simple undirected graphs $$$G_1$$$ and $$$G_2$$$ on the same set of labeled vertices $$$1, 2, \dots, n$$$.

In one operation, you choose exactly $$$k$$$ vertices. Then, for every pair of chosen vertices:

  • if the corresponding edge is present in the current graph, you delete it;
  • otherwise, you add it.

In other words, you toggle every edge inside the chosen set of $$$k$$$ vertices.

Determine whether it is possible to transform $$$G_1$$$ into $$$G_2$$$ after some number of operations.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 200000$$$).

The second line contains one integer $$$m_1$$$ ($$$0 \le m_1 \le \min(300000, \frac{n(n-1)}{2})$$$), the number of edges of $$$G_1$$$.

Each of the next $$$m_1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), describing one edge of $$$G_1$$$.

The next line contains one integer $$$m_2$$$ ($$$0 \le m_2 \le \min(300000, \frac{n(n-1)}{2})$$$), the number of edges of $$$G_2$$$.

Each of the next $$$m_2$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), describing one edge of $$$G_2$$$.

It is guaranteed that both graphs are simple.

Output

Print YES if it is possible to transform $$$G_1$$$ into $$$G_2$$$, and NO otherwise.

Examples
Input
5 4
0
4
1 2
2 3
3 4
4 5
Output
NO
Input
6 5
0
8
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
Output
YES

L. Landau's Fourth Problem
time limit per test
11 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

It is the year 1912 and you are in the United Kingdom, attending the Fifth International Congress of Mathematicians (ICM). The internet, League of Legends, and Geosé don't exist yet... what a wonderful world!

Sir Abraham Marckess and Sir Feet Tester (Yes, that name is actually pretty common in Zacateland, the city he is from) are two assistants to the brilliant mathematician Edmund Landau.

Landau is about to present four fundamental problems related to prime numbers at this congress. What they don't yet know is that the year 2026 will arrive and these problems will still remain unsolved. Mr. Landau already has the first three prepared, but for the last one, he still has some things to verify. The problem is:

Do there exist infinitely many prime numbers $$$p$$$ such that $$$p-1$$$ is a perfect square?

Or said more simply:

Let $$$f(n) = n^2 + 1$$$ with $$$n \ge 1$$$. Do there exist infinitely many primes generated this way?

Since computers as we know them today didn't exist back then, and Landau didn't want to look incompetent at the congress, he needed to verify empirically that his proposal was correct at least up to a very large number.

Thus, Landau tasked Sir Marckess and Sir Tester with the enormous task of calculating how many $$$f(n)$$$ are truly primes up to a given $$$N$$$. However, not trusting their abilities completely, Landau decided to test them by posing this question through many queries.

Your mission is to help Sir Marckess and Sir Feet Tester answer them all correctly before the conference begins.

Input

The first line contains a single integer $$$Q$$$ ($$$1 \le Q \le 4 \times 10^6$$$), the number of queries.

The next $$$Q$$$ lines each contain an integer $$$N$$$ ($$$1 \le N \le 7 \times 10^7$$$).

Output

For each query, print a single integer: the count of values $$$n$$$ in the range $$$1 \le n \le N$$$ for which $$$f(n) = n^2 + 1$$$ is prime.

Example
Input
3
10
100
1000
Output
5
19
112
Note

For the first query ($$$N = 10$$$): $$$f(n) = n^2 + 1$$$ for $$$n \in \{1, 2, \ldots, 10\}$$$ yields the values $$$\{2, 5, 10, 17, 26, 37, 50, 65, 82, 101\}$$$. Among these, the primes are $$$\{2, 5, 17, 37, 101\}$$$, for a total of 5.