HPI 2026 Novice
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. Yash is Cross-Eyed
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a string $$$s$$$, output "YES" if it is possible to make adjacent swaps to make $$$s$$$ of the form $$$t + t$$$ for some string $$$t$$$, and "NO" if it is not possible.

Input

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

Each test case contains a single line with a string $$$s$$$ ($$$|s|\geq 1$$$, and the sum of $$$|s|$$$ over all testcases is at most $$$2\times10^5$$$). Each string consists of lowercase Latin letters.

Output

For each test case, output "YES" if it is possible to perform adjacent swaps and "NO" if otherwise.

"YES" and "NO" are case sensitive, so "yes", "nO", etc are not permitted.

Examples
Input
1
abba
Output
YES
Input
2
a
abcdeadbceff
Output
NO
YES

C. Repetition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Print a string $$$s$$$ such that there exactly $$$n$$$ palindromic substrings in $$$s$$$.

A palindromic substring $$$p$$$ is a substring in $$$s$$$ such that it is a palindrome. For example, $$$aba$$$ has exactly 4 palindromic substrings: $$$a$$$, $$$b$$$, $$$a$$$, $$$aba$$$.

Input

The input consists of one integer $$$n$$$ $$$(1 \le n \le 1000)$$$.

Output

Output a valid string $$$s$$$ $$$(1 \le |s| \le n)$$$.

Example
Input
4
Output
aba

D. Skills
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Gladwell said it takes $$$10,000$$$ hours to master a skill. Bob disagrees and says he only needs $$$N$$$ hours. Bob wants to know how many days it will take him to master $$$M$$$ skills, assuming that he can practice $$$\textbf{each}$$$ skill for at most $$$\textbf{2 hours a day}$$$ and he needs to sleep $$$\textbf{8 hours a day}$$$.

Input

The first line contains two integers, $$$N$$$ $$$(1 \leq N \lt 10^4)$$$ and $$$M$$$ $$$(1 \leq M \leq 10^6)$$$.

Output

Print the number of days it takes Bob to master all M skills.

Examples
Input
10 2
Output
5
Input
5 4
Output
3

E. 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$$$.

F. 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

G. 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

H. 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".

I. 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$$$.

J. 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.