HPI 2026 Advanced
A. Harker!!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given $$$n$$$ strings $$$s_1, \dots, s_n$$$, output whether or not each string contains a substring "harker".

Input

The first line contains the value of $$$n$$$. The next $$$n$$$ lines contain the strings $$$s_1, \dots, s_n$$$.

It is guaranteed that $$$n\geq 1$$$, each string has a length of at least one, and the sum of the lengths of the strings is at most $$$10^5$$$.

Each string only consists of lowercase letters from the Latin alphabet.

Output

Output $$$n$$$ lines. The $$$i$$$-th line contains 1 if the string contains "harker" as a substring; else, output 0.

Example
Input
4
abcd
harkerharker
aharker
datar
Output
0
1
1
0

B. String Runs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The OF!Z language has $$$n$$$ words. However some words are too big for the database to store completely, so some are stored as the concatenation of other words in the database. Look at the input format for how a word is defined.

The desirability of a string $$$s$$$ is defined as $$$|f(s)|$$$ where $$$f(s)$$$ is the compression of all equal, adjacent characters into one character with same value as the compressed ones. For example, if $$$s = aabbbbaaaaccccaaaabaa$$$, then $$$f(s) = abacaba$$$ and the desirability of $$$s$$$ is $$$7$$$.

Everyone wants to know the desirability of the words, so for each word $$$w_i$$$, print its desirability modulo $$$10^9 + 7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 10^4)$$$. The description of each test case follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$ — the number of words in the language.

The next $$$n$$$ lines come in the following form:

$$$\cdot$$$ $$$1$$$ $$$s$$$ — this means that $$$w_i = s$$$. It is guaranteed that the first word is of this type.

$$$\cdot$$$ $$$2$$$ $$$k$$$ $$$x_1$$$ $$$x_2$$$ $$$\dots$$$ $$$x_k$$$ — this means that $$$w_i$$$ is the concatenation of strings with indices $$$x_1$$$ $$$x_2$$$ $$$\dots$$$ $$$x_k$$$ in that order. It is guaranteed that $$$1 \leq x_j \lt i$$$. It is not guaranteed that each $$$x_j$$$ is distinct.

It is guaranteed that all strings contain lowercase latin letters.

It is guaranteed that $$$\sum{|s|} \leq 2 \cdot 10^5$$$ across all queries of type $$$1$$$.

It is guaranteed that $$$\sum{k} \leq 2 \cdot 10^5$$$ across all queries of type $$$2$$$

Output

Print the desirability of each $$$w_i$$$ $$$(1 \leq i \leq n)$$$ modulo $$$10^9 + 7$$$, each separated by a space.

Example
Input
1
6
1 daniel
1 andrew
1 regina
1 yash
2 2 3 2
2 5 1 2 3 4 5
Output
6 6 6 4 11 33
Note

$$$s_4 = reginaandrew$$$ so its desirability is $$$11$$$.

$$$|f(s_5)| = 6 + 6 + 6 + 4 + 11 = 33$$$ so the desirability of $$$s_5$$$ is $$$33$$$.

C. The Penguin-Gopher Shuffle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Desperation is magical!
— the Penguin
A penguin and a gopher were given strings $$$a$$$ and $$$b$$$, each with length $$$1\leq n \leq 1000$$$. They were tasked with transforming $$$a$$$ into $$$b$$$.

They can perform the following operation at most $$$2000$$$ times:

In a step, choose an integer $$$i$$$ satisfying $$$1\leq i\leq n$$$. Then, reverse the suffix of $$$a$$$ that starts at position $$$i$$$.

If the penguin and gopher cannot achieve their goal, output $$$-1$$$. Otherwise, output the sequence of choices of $$$i$$$ that transform $$$a$$$ into $$$b$$$.

Input

The input consists of three lines. The first line contains $$$n$$$ $$$(1\leq n\leq 1000)$$$. The second and third lines contain $$$a$$$ and $$$b$$$, respectively. $$$a$$$ and $$$b$$$ are both of length $$$n$$$, and both strings only contain lowercase Latin letters.

Output

If the task is impossible, output $$$-1$$$. Otherwise, output one line containing $$$k$$$ $$$(0\leq k\leq 2000)$$$. Then, in the next $$$k$$$ lines, output the choices of $$$i$$$ that turn $$$a$$$ into $$$b$$$.

Examples
Input
1
m
m
Output
0
Input
3
deb
fyf
Output
-1
Input
4
emog
egom
Output
1
2

D. Regina's Task
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Andrew does not want Regina to drive on the tennis courts because of memories of his failing career as a tennis player.
— Regina, GPL 2025

Regina was driving Andrew to his dreaded tennis practice when he proposed to her a very interesting question. Andrew gave Regina a simple graph of $$$N$$$ ($$$1 \leq N \leq 2\cdot 10^5$$$) nodes and $$$M$$$ ($$$0 \leq M \leq 3\cdot 10^5$$$) edges, and he requested Regina to find $$$4$$$ distinct nodes $$$a$$$, $$$b$$$, $$$c$$$, and $$$d$$$ such that $$$(a, b)$$$, $$$(b, c)$$$, and $$$(c, d)$$$ are all edges in the graph. Help her find nodes that satisfy these conditions, or output -$$$1$$$ if no such nodes exist.

Input

The first line contains two integers: $$$N$$$ and $$$M$$$.

The following $$$M$$$ lines contain two integers: $$$u$$$ and $$$v$$$, denoting an edge between $$$u$$$ and $$$v$$$.

It is guaranteed that $$$1\leq N\leq2 \cdot 10^5$$$ and $$$0\leq M \leq 3 \cdot 10^5$$$.

There are no self-loops or duplicate edges in the graph.

Output

If it is impossible to find four nodes that satisfy the conditions, output $$$-1$$$.

Otherwise, on $$$4$$$ separate lines, output the four nodes $$$a$$$, $$$b$$$, $$$c$$$, and $$$d$$$ with $$$ab$$$, $$$bc$$$, and $$$cd$$$ adjacent.

Examples
Input
4 1
3 4
Output
-1
Input
6 7
1 3
1 5
2 3
2 5
2 6
4 5
4 6
Output
5
1
3
2

E. Tung Tung String
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
What if instead of Triple T it was Double T, and instead of Sahur it was a String?
— Mark Twain

Oh no! Tung Tung Sahur is now Tung Tung String and his letters are all messed up! He needs your help ASAP.

Given a string $$$s$$$, output the minimum number of adjacent swaps required to make $$$s$$$ of the form $$$t + t$$$ for some string $$$t$$$. This will bring back Tung Tung String back to his original form!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). The description of each test case follows.

Each test case contains a single line with a string $$$s$$$ ($$$1 \leq |s| \leq 2 \cdot 10^5$$$). Each string consists of lowercase Latin letters.

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

Output

For each test case, output one integer — the minimum number of adjacent swaps required. The input guarantees that the goal can be achieved within a finite number of swaps.

Example
Input
3
aabb
abab
aaaabbbb
Output
1
0
4
Note

In the first test case, we can swap the second and third characters to form "abab".

In the second test case, no swaps are required.

In the third test case, we can use four swaps to form "aabbaabb".

F. Pace Pushers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

On a straight training track, coaches drop effort beacons. Each beacon projects an intensity zone. Whenever zones overlap and one is weaker, the weaker beacon levels up by one. All beacons update together each round until the effort levels stop changing.

You are given an integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^{5}$$$). There are $$$N$$$ beacons on a straight line. For each $$$i$$$, you are given a position $$$x_i$$$ ($$$0 \le x_i \le 10^{9}$$$) and a power $$$p_i$$$ ($$$1 \le p_i \le 10^{9}$$$).

Each beacon $$$i$$$ powers the closed interval $$$[\,x_i - p_i,\; x_i + p_i\,]$$$.

If two powered intervals overlap and their powers are not equal, the weaker beacon's power increases by $$$1$$$. All such increases happen synchronously in rounds: in each round, every beacon decides using the powers at the start of that round, and all chosen increases occur together. Repeat rounds until a full round makes no changes (it can be shown that this process terminates). In the final state, output the total length covered by the union of all powered intervals.

The length of the interval $$$[l, r]$$$ is calculated as $$$r - l + 1$$$.

Input

The first line contains $$$N$$$. Each of the next $$$N$$$ lines contains two integers, $$$x_i$$$ and $$$p_i$$$.

Output

Print a single integer — the length of the union of the intervals in the final (stable) state.

Example
Input
7
0 1
3 1
5 2
9 1
12 3
20 1
21 1
Output
23
Note

Intervals are inclusive, and updates are synchronous. For the input above the initial intervals are $$$[-1,1],[2,4],[3,7],[8,10],[9,15],[19,21],[20,22]$$$ and $$$p=(1,1,2,1,3,1,1)$$$.

Overlaps force weaker beacons to level up: first $$$2$$$ and $$$4$$$, then the increase cascades through beacons $$$1$$$ to $$$5$$$ . After $$$5$$$ rounds, beacons $$$1$$$ to $$$5$$$ equalize at power $$$3$$$ while $$$6$$$ and $$$7$$$ stay at $$$1$$$, so the final components are $$$[-3,15]$$$ and $$$[19,22]$$$. The total inclusive length is $$$(15-(-3)+1)+(22-19+1)=19+4=23$$$.

G. Skating With Alysa Liu
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alysa Liu is sad and looking for someone to skate with her. However she gives a problem to you before you can skate with her. Solve it fast so you can have more time on the ice with Alysa Liu!

The input has an integer and $$$n$$$ ($$$1\le n\le 5\cdot10^{5}$$$). There are $$$n$$$ integers in an array. For each $$$i$$$, there is $$$a_{i}$$$ ($$$1\le a_{i}\le 10^{9}$$$). You also have another integer $$$m$$$ ($$$1\le m\le 10^{9}$$$).

Furthermore, you have an ice skate of size $$$k$$$ ($$$1\le k\le n$$$) that allows you to increment any range $$$[l, r]$$$ of length $$$k$$$ ($$$1\le l\le r\le n,$$$ $$$r - l + 1 = k$$$) in the array by a positive integer $$$x$$$ ($$$1 \le x$$$).

After an arbitrary amount of operations, you want to maximize $$$\sum_{i=1}^{n}{(a_{i} \bmod m)}$$$. Print the maximum value. If you solve this problem you will become partners with Alysa Liu and she won't be sad anymore!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^{4}$$$). The description of each test case follows.

The first line will contain $$$n$$$, $$$m$$$, and $$$k$$$.

The second line will contain $$$n$$$ integers, the $$$i$$$th describing $$$a_i$$$.

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

Output

Print the answer to maximize $$$\sum_{i=1}^{n}{(a_{i} \bmod m)}$$$ after an arbitrary amount of operations.

Example
Input
4
3 10 3
5 8 2
4 3 2
1 1 1 1
5 13 2
1 1 1 1 1
10 1 3
6 7 6 7 6 7 6 7 6 7
Output
18
8
58
0
Note

In the first testcase, it is optimal to perform one operation and by making $$$x = 1$$$ so that the resulting array becomes $$$[6, 9, 3]$$$ which has a resulting sum of $$$18$$$ when each element is taken under $$$\bmod 10$$$.

In the second testcase, an optimal array after all operations is $$$[2, 2, 2, 2]$$$ which gives the resulting sum of $$$8$$$.

In the third testcase, an optimal array after all operations in $$$[12, 23, 12, 12, 12]$$$ which gives the resulting sum of $$$58$$$ after each element is taken under $$$\bmod 13$$$.

In the fourth testcase, any array after any operations is optimal.

H. Looksmaxxing with Clavicular
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ fraternity houses at ASU, and the $$$i$$$-th frat house has an average frame value of $$$a_i$$$. Clavicular has decided to stream $$$n - k + 1$$$ times, with the $$$i$$$th stream starting from frat house $$$i$$$ and ending at frat house $$$i + k - 1$$$. Clavicular starts every stream with a frame value of $$$0$$$, but each time he visits a new frat house, his frame value will increase by $$$1$$$. Now, if Clavicular visits frat house $$$i$$$ while he has a frame value of $$$f$$$, he will get frame-mogged if $$$a_i \geq f$$$. Furthermore, if he gets frame-mogged at all $$$k$$$ houses in a given stream, he gets stream-mogged.

Formally, stream $$$i$$$ stream-mogs Clavicular if $$$a_{i + j - 1} \geq j$$$ for all $$$1 \leq j \leq k$$$.

As Clavicular's PR specialist, you do not want him to get stream-mogged too many times. However, you also don't want him to not get stream-mogged at all, as that would be a little too uninteresting. Hence, you've decided that he should be stream-mogged exactly $$$x$$$ times.

To achieve this goal, you can rearrange the frat houses however you want. Your job is to either output a suitable permutation of $$$a$$$ or report that the task is impossible.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). The description of each test case follows.

Each test case begins with three integers $$$n$$$, $$$k$$$ and $$$x$$$ ($$$1 \leq k \leq n \leq 5 \cdot 10^5$$$, $$$0 \leq x \leq n$$$).

The next line contains $$$n$$$ integers, $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq k$$$).

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

Output

For each test case, if the task is impossible, output the single integer $$$0$$$.

Otherwise, output any permutation of $$$a$$$ that stream-mogs Clavicular exactly $$$x$$$ times.

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

For the first test case, none of the streams will stream-mog Clavicular. For instance, stream $$$1$$$ visits frat houses $$$1$$$, $$$2$$$, and $$$3$$$. This does not stream-mog Clavicular because although $$$a_1 = 3 \geq 1$$$ and $$$a_2 = 3 \geq 2$$$, $$$a_3 = 1 \lt 3$$$. Note that in this case, the original order of $$$a$$$ is also valid.

In the second case, it can be shown that all possible permutations will stream-mog Clavicular at least once. For instance, the given permutation stream-mogs Clavicular $$$1$$$ time during stream $$$4$$$, which visits frat houses $$$4$$$, $$$5$$$, and $$$6$$$.

I. Daniel Saves Yash
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Due to an unfortunate incident in math class, Yash developed a severe fear of palindromes. However, evil Andrew decided to send him a string $$$S$$$ possibly containing palindromes as a gift! To protect his friend, Daniel intercepts the delivery and ensures that there is no presence of palindromes by removing all of them.

In an operation, Daniel can remove a substring of $$$S$$$ that is a palindrome with length greater than one. Note that removing a substring may result in more palindromic substrings, which may be removed later.

Given the gift, a string $$$S$$$ of length $$$N$$$, let $$$C$$$ be the maximum number of characters that can be removed by Daniel. Let $$$R$$$ be the minimum number of operations needed to achieve $$$C$$$ characters removed. Find $$$C$$$ and $$$R$$$.

Input

The first line contains $$$N$$$, the length of the string.

The second line contains $$$S$$$, the string.

It is guaranteed that $$$|S|=N$$$, and $$$1\leq N\leq 500$$$.

The string only contains lowercase Latin letters.

Output

Output two lines:

The first line contains $$$C$$$, the maximum number of characters removed by Daniel.

The second line contains $$$R$$$, the minimum number of removals needed to achieve $$$C$$$ characters removed.

Examples
Input
1
a
Output
0
0
Input
10
wqzzldajsw
Output
2
1
Input
6
abbcax
Output
5
2
Note

In the first example, no characters can be removed.

In the second example, only the substring zz can be removed.

In the third example, we can remove the substring bb. Then, the string becomes acax, and we can remove the substring aca. In total, we have removed $$$C=5$$$ characters in $$$R=2$$$ operations.

J. Tree Queries
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Too tired to write flavor-text...
— Daniel

Given a tree on $$$n$$$ nodes, answer $$$q$$$ queries of the following form: what's the size of the smallest subset of edges that connects all pairs of nodes $$$(u, v)$$$ for $$$u, v \in [l, r]$$$?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). The description of each test case follows.

The first line will contain $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) and $$$q$$$ ($$$1 \leq q \leq 3 \cdot 10^5$$$).

The next $$$n - 1$$$ lines describe the edges of the tree, and the next $$$q$$$ lines describe $$$l$$$ and $$$r$$$ for each query.

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

Output

Output $$$q$$$ integers representing the answer to each query.

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

For the third query, we must keep at least 4 edges: $$$2-4, 1-2, 1-5$$$, and $$$5-6$$$.