2017 ACM Arabella Collegiate Programming Contest
A. Sherlock Bones
time limit per test
1.5 s
memory limit per test
256 megabytes
input
standard input
output
standard output

The great dog detective Sherlock Bones is on the verge of a new discovery. But for this problem, he needs the help of his most trusted advisor -you- to help him fetch the answer to this case.

He is given a string of zeros and ones and length N.

Let F(x, y) equal to the number of ones in the string between indices x and y inclusively.

Your task is to help Sherlock Bones find the number of ways to choose indices (i, j, k) such that i < j < k, sj is equal to 1, and F(i, j) is equal to F(j, k).

Input

The first line of input is T – the number of test cases.

The first line of each test case is an integer N (3 ≤ N ≤ 2 × 105).

The second line is a string of zeros and ones of length N.

Output

For each test case, output a line containing a single integer- the number of ways to choose indices (i, j, k).

Example
Input
3
5
01010
6
101001
7
1101011
Output
2
3
7

B. Unusual Team
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A lion, a mouse, and a beaver are one of the best teams at Animal University, and they have qualified to the ACM Arabella 2017 contest!

They want to choose their team name, and after many suggestions, they have reduced their options to two names: "FunkyMonkeys" and "WeWillEatYou".

They then created a poll on Facebook to help them with their final decision.

The results of the poll are now with Dr. Samer, and he will use the name with the highest votes to register the team. Can you help Dr. Samer to know which team name they will register with?

Input

The first line of input is T – the number of test cases.

The first line of each test case contains two integers a, b (1 ≤ a, b ≤ 100) - the number of votes for "FunkyMonkeys" and "WeWillEatYou" respectively.

Output

For each test case, output a single line containing "FunkyMonkeys" (without quotes), if that name received more points or tied with “WeWillEatYou”, otherwise output “WeWillEatYou”.

Example
Input
2
15 20
70 70
Output
WeWillEatYou
FunkyMonkeys

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

There are N kangaroos going out to eat at an Indian restaurant. The ith kangaroo wants to eat exactly xi food. The kangaroos all want to order the same size of plates, but each one can order more than one plate for themselves if they need to. If the kangaroo orders more than he needs, he can simply hide the leftovers in his pouch.

At this Indian restaurant, the cost of the plate is the same as its size. Since Karl the Kangaroo is paying and is low on money, he wants to know what is the minimum cost to feed all N kangaroos and what is the largest possible size of the plates that satisfies this minimum cost?

Input

The first line of input is T – the number of test cases.

The first line of each test case is an integer N (1 ≤ N ≤ 105).

The second line contains N space-separated integers xi (1 ≤ xi ≤ 109).

Output

For each test case, output a line containing two space-separated integers – the minimum cost and the maximum plate size that corresponds to when the total cost is minimized.

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

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

In a magical forest, there exists N bamboos that don't quite get cut down the way you would expect.

Originally, the height of the ith bamboo is equal to hi. In one move, you can push down a bamboo and decrease its height by one, but this move magically causes all the other bamboos to increase in height by one.

If you can do as many moves as you like, is it possible to make all the bamboos have the same height?

Input

The first line of input is T – the number of test cases.

The first line of each test case contains an integer N (1 ≤ N ≤ 105) - the number of bamboos.

The second line contains N space-separated integers hi (1 ≤ hi ≤ 105) - the original heights of the bamboos.

Output

For each test case, output on a single line "yes” (without quotes), if you can make all the bamboos have the same height, and "no" otherwise.

Example
Input
2
3
2 4 2
2
1 2
Output
yes
no

E. Competitive Seagulls
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are two seagulls playing a very peculiar game. First they line up N unit squares in a line, all originally colored white.

Let L be the length of the longest continuous sub-segment of white unit squares. Let P be any prime that satisfies the condition that . The player can choose any P if it satisfies the conditions but if there is no value of P that does, then P is set to 1.

The current player then proceeds to choose any continuous sub-segment of white unit squares of length P and paint them black. The player who can’t make a move loses.

If both players play optimally and the first player starts, which player is going to win the game?

Input

The first line of input is T – the number of test cases.

Each test case contains a line with a single integer N (1 ≤ N ≤ 107).

Output

For each test case, output on a single line "first" (without quotes) if the first player would win the game, or "second" if the second would win.

Example
Input
2
2
5
Output
second
first

F. Monkeying Around
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

When the monkey professor leaves his class for a short time, all the monkeys go bananas. N monkeys are lined up sitting side by side on their chairs. They each have the same joke book. Before the professor returns, M jokes were heard.

Each of the M jokes are said in the order given and have the following properties:

xi - position of the monkey who said it.

li – index of the joke in the book.

ki – volume the monkey says that joke.

When the monkey at position xi says the joke li, all monkeys at a distance less than or equal to ki from that monkey (including the monkey who said the joke) will fall off their chairs in laughter if they have never heard the joke li before.

If the joke li has been heard anytime during the past before, and the monkey hears it again, then he will sit back up in his chair.

A monkey can fall off his chair more than once (every time he hears a new joke), and if he is already on the ground and hears a new joke, he will stay on the ground.

Can you figure out how many monkeys will be in their seats by the time the professor comes back?

Input

The first line of input is T – the number of test cases.

The first line of each test case is N, M (1 ≤ N ≤ 105) (1 ≤ M ≤ 105) – the number of monkeys in the class, and the number of jokes said before the professor returns.

The next M lines contain the description of each joke: xi, li, ki (1 ≤ xi ≤ N) (1 ≤ li ≤ 105) (0 ≤ ki ≤ N).

Output

For each test case, output on a line a single integer - the number of monkeys in their seats after all jokes have been said.

Example
Input
1
10 7
3 11 0
3 11 2
5 12 1
8 13 2
7 11 2
10 12 1
9 12 0
Output
3

G. Snake Rana
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Old Macdonald wants to build a new hen house for his hens. He buys a new rectangular area of size N by M. The night before he builds the hen house, snake Rana devises an evil plan to plant bombs in K distinct cells in the area to kill the hens and eat them for dinner later.

The morning of, Old Macdonald notices that each of the K cells, where snake Rana planted a bomb, have a marking on them. That won’t stop him though, all he must do is build the hen house in an area with no bombs.

Assume that rows are numbered from top to bottom, and columns are numbered from left to right. Old Macdonald now wants to know the number of ways he can choose sub-rectangles of top left coordinates (x1, y1) and bottom right coordinates (x2, y2) (x1 ≤ x2) (y1 ≤ y2) such that there are no bombs in the sub rectangle.

Input

The first line of input is T – the number of test cases.

The first line of each test case is three integers N, M, and K (1 ≤ N, M ≤ 104) (1 ≤ K ≤ 20).

The next K lines each contains distinct pair of integers x, y (1 ≤ x ≤ N) (1 ≤ y ≤ M) - where (x, y) is the coordinate of the bomb.

Output

For each test case, output a line containing a single integer - the number of sub-rectangles that don’t contain any bombs.

Example
Input
3
2 2 1
2 2
6 6 2
5 2
2 5
10000 10000 1
1 1
Output
5
257
2500499925000000

H. Mirrored String I
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The gorillas have recently discovered that the image on the surface of the water is actually a reflection of themselves. So, the next thing for them to discover is mirrored strings.

A mirrored string is a palindrome string that will not change if you view it on a mirror.

Examples of mirrored strings are "MOM", "IOI" or "HUH". Therefore, mirrored strings must contain only mirrored letters {A, H, I, M, O, T, U, V, W, X, Y} and be a palindrome.

e.g. IWWI, MHHM are mirrored strings, while IWIW, TFC are not.

A palindrome is a string that is read the same forwards and backwards.

Can you tell if string S is a mirrored string?

Input

The first line of input is T – the number of test cases.

Each test case contains a non-empty string S of maximum length 1000. The string contains only uppercase English letters.

Output

For each test case, output "yes" (without quotes) if the string S is a mirrored string, otherwise output "no".

Example
Input
3
IOI
ARABELLA
RACECAR
Output
yes
no
no

I. Mirrored String II
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Note: this is a harder version of Mirrored string I.

The gorillas have recently discovered that the image on the surface of the water is actually a reflection of themselves. So, the next thing for them to discover is mirrored strings.

A mirrored string is a palindrome string that will not change if you view it on a mirror.

Examples of mirrored strings are "MOM", "IOI" or "HUH". Therefore, mirrored strings must contain only mirrored letters {A, H, I, M, O, T, U, V, W, X, Y} and be a palindrome.

e.g. IWWI, MHHM are mirrored strings, while IWIW, TFC are not.

A palindrome is a string that is read the same forwards and backwards.

Given a string S of length N, help the gorillas by printing the length of the longest mirrored substring that can be made from string S.

A substring is a (possibly empty) string of characters that is contained in another string S. e.g. "Hell" is a substring of "Hello".

Input

The first line of input is T – the number of test cases.

Each test case contains a non-empty string S of maximum length 1000. The string contains only uppercase English letters.

Output

For each test case, output on a line a single integer - the length of the longest mirrored substring that can be made from string S.

Example
Input
3
IOIKIOOI
ROQ
WOWMAN
Output
4
1
3

J. Lazy Physics Cat
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Physics cat likes to draw shapes and figure out their area. He starts by drawing a circle. Then inside the circle, he draws the triangle X, Y, Z - where Y is the center point of the circle, and X and Z touch the circumference of the circle. Please note that points X and Y always have the same x-coordinate.

Given L (the distance between Points X and Y) and A (the angle XYZ in degrees); help physics cat find the shaded area between the right side of the triangle and the circumference of the circle. And when we say help, we mean do all the work for him.

Input

The first line of input is T – the number of test cases.

The first line of each test case is integers L and A (1 ≤ L ≤ 1000) (1 ≤ A ≤ 180).

Output

For each test case, output on a line the area of the shaded region rounded to 6 decimal places.

Example
Input
3
1 90
2 180
10 30
Output
0.285398
6.283185
1.179939

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

The owls have the following equation:

Y = a × x2 + b × x

With a, b, and N given, they decide to put into a set the integer values of Y that are less than or equal to N and that are outputted from the equation from any positive integer x.

With that set of numbers, they come up with the problem of finding the winning digit among them.

The winning digit is a digit from 0 to 9 that will get the maximum number of points. How are points for a digit calculated you may ask? Well, be a bit more patient, I’m going to tell you now.

For each number in the set, if the digit was the most repeated digit or tied with other digits as the most repeated digit in the ith number of set S, then it would get one point from that ith number.

Can you tell the owls what the winning digit is?

Input

The first line of input is T – the number of test cases.

The first line of each test case is a, b, and N (1 ≤ a, b, N ≤ 105).

Output

For each test case, print on a line the winning digit with the maximum number of points. If there is a tie, print the minimum digit among them. If the set is empty, print  - 1.

Example
Input
2
1 2 50
20 3 10
Output
3
-1

L. All’s Wall That Ends Wall
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the magical forest, you come upon N walls that you think is a great place to store water for your animal friends. The ith wall consists of ai blocks stacked on top of each other.

Your job is to answer queries of two types:

- For queries of the first type, print the amount of water that could be stored between all the walls.

- For queries of the second type, increase the number of blocks on the xth wall by v.

Input

The first line of input is T – the number of test cases.

The first line of each test case is integers N and Q (1 ≤ N, Q ≤ 105).

The second line contains N space-separated integers ai (1 ≤ ai ≤ 105).

The next Q lines contain either ‘P’ – denoting a query of the first type, or ‘U’ followed by x and v – denoting a query of the second type (1 ≤ x ≤ N) (1 ≤ v ≤ 104).

Output

For each test case and query of the first type, output on a line the amount of water that could be stored between the walls.

Example
Input
1
6 3
2 1 4 2 1 3
P
U 1 2
P
Output
4
6

M. Make Cents?
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Every year, an elephant qualifies to the Arab Collegiate Programming Competition. He graduated this year, but that’s irrelephant. What’s important is that the location of the competition might not have been the same every year. Therefore, after every trip, he always has leftover money in the currency of the country he visited.

Now he wants to see how much Jordanian Dinars he has after all those competitions. Can you help him convert the leftover money from all competitions to Jordanian Dinar, if that makes any cents?

Input

The first line of input is T – the number of test cases.

The first line of each test case contains C and N (1 ≤ C, N ≤ 100000), the number of currency types and the number of competitions, respectively.

The next C lines each contain the name of the currency Ci of maximum length 10 in lowercase and/or uppercase letters, and the value Vi of that currency in Jordanian Dinar (0 < Vi ≤ 1000). The names are case-sensitive.

The next N lines each contains an amount left over from each competition (0 ≤ Ni ≤ 1000), and the name of the currency of that amount (it is guaranteed that the name was either given in the input or is “JD”).

Output

For each test case, print on a single line the total amount of money he has in Jordanian Dinar(JD) rounded to 6 decimal digits.

Example
Input
1
3 5
dollar 0.71
euro 0.76
turkish 0.17
5.1 dollar
6 dollar
7 turkish
3 euro
1.1 JD
Output
12.451000