IME++ Starters Try-outs 2024
A. Array Issue
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Caio Harley is a dedicated competitive programmer and has been studying various algorithms related to arrays. One day he was analyzing various arrays and trying to find out the solution for the following problem: what is the subarray with the largest sum?

Now, instead of executing this algorithm for the entire array, he decides to do it for every prefix of the array. More formally, for an array of $$$n$$$ integers, he executes the algorithm for every $$$i$$$ from $$$1$$$ to $$$n$$$ on the prefix $$$1 ... i$$$. However, he was too tired of running several algorithms by himself, and so he calls upon you for help! Given an array $$$a$$$ of $$$n$$$ integers, help him find out the largest subarray sum for every prefix.

An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases that Caio gives to you.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$ — the length of the array of that test case.

The second line of each test case contains $$$n$$$ integers $$$(a_1, a_2, ..., a_n)$$$ $$$(-10^{11} \leq a_i \leq 10^{11})$$$ — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For the $$$i^{th}$$$ test case, output $$$n_i$$$ integers in a single line — the answer for each prefix.

Examples
Input
3
3
-1 -4 -5
4
-2 5 9 10
5
4 -4 4 -4 9
Output
0 0 0
0 5 14 24
4 4 4 4 9
Input
1
5
4 -3 0 6 1
Output
4 4 4 7 8

B. Breaking Up Words
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

GG is a new coach in town ready to present several seminars during the week. Wanting to be very exclusive, he only allows people to enter whose name is a palindrome. Recall that a palindrome is a word that is read the same backwards. As you can imagine, this really narrows down how many people are able to enter.

As such, on Wednesday afternoons, he changes the entry requirements in order to gift the unwashed masses with his outstanding knowledge. The requirement becomes the following: you're able to enter only if you're able to find an existing palindrome of length greater than or equal to $$$2$$$ within your name.

For each person that will try to attend the seminar this Wednesday afternoon, help GG determine whether or not access will be granted.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 3 \times 10^5)$$$ — the amount of people that will try to attend the seminar.

The next $$$n$$$ lines contain a single string $$$s$$$ $$$(1 \leq |s| \leq 20)$$$ — their names. The names consist only of lowercase letters of the English alphabet.

Output

For each person, print out yes if access is granted, no otherwise.

Example
Input
3
hannah
vieira
limevaz
Output
yes
yes
no
Note

Hannah is already a palindrome, so access is granted! Within Vieira, you have iei, which is indeed a palindrome!

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

At the Institute of Many Exams (commonly referred to as IME), Keller has been tasked with conducting several exams. He is given $$$t$$$ tests to grade, and in each one he sees that the student got $$$m$$$ questions right out of $$$n$$$. Knowing that the threshold for passing is at least 50$$$\%$$$, he needs to find out for each test, whether or not the student passed. Since the workload has been really high recently, he tasks you to help him out!

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases that Keller gives to you.

Each test case contains two integers, $$$n$$$, $$$m$$$ $$$(0 \leq m \leq n \leq 10^9)$$$ — the amount of questions in each test and the amount that Keller got correct. It is guaranteed that $$$n$$$ is at least $$$1$$$.

Output

For each test, print passed if the threshold is achieved, failed otherwise.

Example
Input
3
10 5
11 5
11 6
Output
passed
failed
passed

D. Don't Get Caught
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Today is a beautiful day in Rio de Janeiro and all of the students at IME (known as the Institute of Missions that are Enthralling) decide to go enjoy the beach that's right in front of the institute, all except for Kauã... Kauã needs to stay at IME to complete his mission of safeguarding the university. Although he's not allowed to leave, he decides he wants to sneak out to have fun with his friends, but obviously he doesn't want to get caught! You sympathize with this situation and decide to help him develop an escape plan.

Kauã reaches the main entrance hall and is greeted with this large hallway containing a number of guards watching the place. Since it's quite the boring night and they think that the institute is safe, the guards remain static throughout the entire night, looking solely in one direction. After carefully analyzing their positions, Kauã hands to you a map of the main entrance hall. It consists of a grid with dimensions $$$n \times m$$$, in which Kauã starts at position $$$(1, 1)$$$ and has to get to the main entrance itself, at $$$(n, m)$$$. The guards will be situated in other positions of the grid, however, due to some restrictions, there's never someone at $$$(1, 1)$$$ nor at $$$(n, m)$$$.

Kauã asks you to help him determine whether or not he's able to traverse the main entrance hall. If he's able to, he asks you to show in the map what's the smallest path he's able to take.

The picture depicts where Kauã needs to traverse.
Input

The first line of the input consists of two integers $$$n$$$, $$$m$$$ $$$(1 \leq n, m \leq 2 \times 10^3)$$$ — the dimensions of the main entrance hall.

The next $$$n$$$ lines will contain a string of $$$m$$$ characters $$$(a_{i, 1}, a_{i, 2}, ..., a_{i, m})$$$, indicating the layout of the $$$i^{th}$$$ line.

$$$a_{i, j}$$$ can be either ., >, v, <, ^ — indicating what's present on that position.

  • If $$$a_{i, j} =$$$ ., then the position is empty.
  • If $$$a_{i, j} =$$$ >, v, <, ^, then the position contains a guard that is facing east, south, west, and north respectively. The guard's line of sight is one square wide and extends straight in the direction the person is facing, blocked only by another person.
Output

If it is impossible to reach the main entrance itself, then print out $$$-1$$$. Otherwise, print out the grid once more, substituting the positions Kauã is supposed to pass through with an X. This should be the shortest path, and if there are multiple shortest paths, you can print out any of them.

Examples
Input
5 5
.....
.>.v.
.....
.^.<.
.....
Output
X....
X>.v.
X....
X^.<.
XXXXX
Input
3 6
.v....
.^.v..
...^..
Output
XvXXX.
X^XvX.
XXX^XX
Input
4 4
....
..^.
.<..
....
Output
-1

E. Earthquake
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

An earthquake has once again struck IME (commonly referred to as the Institute of Manifold Earthquakes), and every time this happens, some hallways end up simply being destroyed. Since another earthquake will probably happen shortly after, the commander is only open to building what is necessary in order for IME to be connected once again.

The layout of the institute can be thought of as a series of rooms and pathways, where pathways strictly connect two different rooms, and that there are no redundant pathways. Since the commander is indeed, the commander, he orders you to help him find out what's the smallest amount of hallways that need to be built given the map of the current situation.

Input

The first line of the input consists of two integers, $$$n$$$, $$$m$$$ $$$(1 \leq n \leq 10^5)$$$ $$$(0 \leq m \leq \min(10^6, \frac{n \times (n - 1)}{2})$$$ — the amount of rooms in IME and the amount of pathways that still remain after the earthquake.

The next $$$m$$$ lines consist of two integers, $$$a$$$, $$$b$$$ $$$(1 \leq a, b \leq n)$$$, $$$(a \neq b)$$$ — indicating that rooms $$$a$$$ and $$$b$$$ are still connected after the earthquake.

Output

Output a single integer — the smallest amount of hallways that need to be built in order for IME to be connected.

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

F. Foreign Language
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Pedro Vieira finally got accepted to his internship at AMAN (commonly referred to as the Academy of Many Amazing Netizens), and unfortunately for him, they speak a really strange language there. However, he only discovered this fact after etching a commemorative phrase onto a plaque, and now he wants to modify it into the strange language spoken at AMAN.

Vieira thinks that it'll be too much of a hassle to make a new plaque from scratch, so he asks for help from a friend who's able to perform certain modifications to the plaque. This friend is able to (don't ask how, though) insert letters anywhere in the phrase, remove them or simply modify them, each having their own respective cost.

Knowing that spaces are a non-issue, given the original phrase and the one in the strange language, Pedro Vieira wants to find out what's the minimum cost in order for this change to be done.

Input

The first line of the input contains 5 integers $$$n, m, a, b, c$$$ $$$(1 \leq n, m \leq 2 \times 10^3)$$$, $$$(1 \leq a, b, c \leq 10^9)$$$ — the length of the phrase on the plaque, the length of the phrase in the strange language, the cost of inserting letters, the cost of removing them and the cost of modifying them, respectively.

The next line contains string $$$s$$$ $$$(|s| = n)$$$ — the phrase on the plaque.

The next line contains string $$$t$$$ $$$(|t| = m)$$$ — the phrase in the strange language.

Both strings contain letters of the English alphabet and note that capital and lowercase letters are considered different.

Output

Output a single integer — the minimum cost of correcting the plaque.

Examples
Input
9 11 827 3281 921
ILoveAMAN
beepbopobep
Output
9943
Input
3 4 19 28 3
Abc
abcd
Output
22

G. Greatest Math Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Vaz Lime is one of the most renowned calculus teachers in the world and really enjoys teaching class. So much so, that even though his class is the one right before lunch, he won't allow the hungry students to go (not even 1 minute before the bell!).

Fortunately, Romariz is one of the best math students of the class, and one day confidently challenges the teacher to a math duel. Vaz Lime determines that he will give Romariz a series of questions that, if answered correctly in less than two seconds, will allow the students that day to go to lunch earlier.

Romariz is given several test cases containing an array of length $$$n$$$ and an integer $$$k$$$ related to that array. For each test case, he needs to find the largest value of a positive integer $$$x$$$, such that $$$\sqrt{\lfloor \frac{a_1}{x} \rfloor + \lfloor \frac{a_2}{x} \rfloor + ... + \lfloor \frac{a_n}{x} \rfloor} \geq k$$$

Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the amount of test cases that Vaz Lime gives to Romariz.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ $$$(1 \leq n \leq 10^6)$$$, $$$(1 \leq k \leq 10^9)$$$ — the amount of elements in the array and the associated integer.

The second line of each test case contains $$$n$$$ integers $$$(a_1, a_2, ..., a_n)$$$ $$$(1 \leq a_i \leq 10^{9})$$$ — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, output the maximum value of a positive integer $$$x$$$ that satisfies the equation. If no such number exists, print out -1.

Examples
Input
1
4 5
123 94 21 2
Output
9
Input
3
5 10
39 281 2 3 2
4 7
2 8 34 1223
7 5
9 4 28 9 3 12 95
Output
3
25
5

H. Hierarchy Mess
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The Institute of Multiple Echelons, commonly referred to as IME, has plenty of staff and students, all of whom are forced to follow a strict hierarchical order. The leader of the institute, known as the commander, has no idea how the system works below him, as he's on top of the food chain and so it's nothing for him to worry about. One fine day, when he finally dared to look down, the commander uncovered the complete hierarchical map of his institute. It is a giant web of people with numerous ways for information to reach him.

He became interested in this map, and came up with the following inquiry: how many different ways exist for information to reach him, starting from any person within IME. Information is able to reach him the following way: the person who needs to pass something to the commander passes it to his/her superior, who then passes it on to his/her superior, and so on until it reaches the commander. If a person tries to send some information to the commander, it is impossible for that information to return to the sender somehow.

Of course, since he's the commander, he delegates this task to you. He presents to you the map, consisting of $$$n$$$ people and $$$m$$$ hierarchical relationships. Each relationship describes two people, $$$a$$$ and $$$b$$$, in which $$$b$$$ is a subordinate of $$$a$$$. It is guaranteed that the commander's ID is 1, that he isn't anyone's subordinate and that anyone is able to reach him.

Input

The first line of the input consists of two integers, $$$n$$$, $$$m$$$ $$$(1 \leq n \leq 10^5)$$$ $$$(n - 1 \leq m \leq \min (10^6, \frac{n \times (n - 1)}{2})$$$ — the amount of people in the institute and the amount of relationships described in the map.

The next $$$m$$$ lines describe the relationships, each line consists of two integers, $$$a$$$, $$$b$$$ $$$(1 \leq a, b \leq n)$$$ — indicating that the person with ID $$$b$$$ is a subordinate of the person with ID $$$a$$$. It is guaranteed that $$$b$$$ isn't $$$1$$$ and that for every relationship $$$(a, b)$$$, it is impossible for information starting at $$$a$$$ to end up with the person $$$b$$$.

Output

Print a single integer — the number of ways information is able to reach the commander starting from any person. Since this number can be very large, print it out modulo $$$998244353$$$.

Example
Input
5 7
1 2
2 3
2 5
5 3
3 4
1 5
5 4
Output
11
Note

For the sample input it is easy to see that the following paths are possible for info to travel through:

4 - 5 - 1

4 - 5 - 2 - 1

4 - 3 - 2 - 1

2 - 1

5 - 2 - 1

4 - 3 - 5 - 1

3 - 2 - 1

4 - 3 - 5 - 2 - 1

3 - 5 - 1

3 - 5 - 2 - 1

5 - 1

I. Inversion Test
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Schubert has recently been studying properties of arrays, and something that caught his attention is called inversions. From what he recalls from class, the number of inversions of an array $$$a$$$ of size $$$n$$$ is defined by the number of pairs $$$(i, j)$$$ such that $$$(1 \leq i \lt j \leq n)$$$, in which $$$(a_i \gt a_j)$$$. Schubert realized that given an array, there are plenty of subarrays whose number of inversions is the same as the original array. As such, he gave this simple task: given an array, find the size of the smallest subarray in which the number of inversions is the same as in the original array.

An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases that Schubert gives to you.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$ — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$(a_1, a_2, ..., a_n)$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$ — the elements of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, output a single integer in a separate line — the size of the smallest subarray in which the number of inversions is the same as the original one.

Examples
Input
2
4
49 0 2 -1
6
5 6 59 23 71 100
Output
4
2
Input
1
5
1 2 3 4 5
Output
0

J. Joust
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Saboya and Alfredo are two very dedicated students who have a special competition between them during contests. They really don't care about being the person who solves the most amount of questions; rather, they prefer to be the one that solves the most amount of problems first. That being said, if during a contest, one of them solves 6 problems and the other solves 8, the former may still be declared the victor if he has more first solves than the other. Note that, if they end up solving the same question at the same time, then neither of them can claim the title of first solve for that one.

They end up participating in $$$t$$$ contests, and since it can be a large amount, they ask for your assistance in discovering who came out victorious in each contest.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of contests in which Saboya and Alfredo participate.

The first line of each contest contains an integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$ — the amount of questions in that specific contest.

The second line of each contest contains $$$n$$$ integers $$$(a_1, a_2, ..., a_n)$$$ $$$(-1 \leq a_i \leq 10^9)$$$ — the time that had elapsed during the contest when Saboya got the question correct. If the value is -1, then he was unable to solve it during the contest.

The third line of each contest contains $$$n$$$ integers $$$(b_1, b_2, ..., b_n)$$$ $$$(-1 \leq b_i \leq 10^9)$$$ — the time that had elapsed during the contest when Alfredo got the question correct. If the value is -1, then he was unable to solve it during the contest.

It is guaranteed that the sum of $$$n$$$ over all contests doesn't exceed $$$10^6$$$.

Output

For each contest, output Saboya if he'd win the competition, Alfredo if he'd win it, otherwise output Tie if there's a tie happening.

Examples
Input
1
3
4 5 2
-1 2 1
Output
Alfredo
Input
2
4
-1 -1 -1 -1
-1 -1 -1 -1
5
4 9 2 0 1
5 7 2 3 2
Output
Tie
Saboya