III USP Freshmen Contest
A. MaratonIME stacks popcorn buckets
time limit per test
2 с
memory limit per test
64 megabytes
input
standard input
output
standard output

On a Friday afternoon, some members of MaratonIME decided to watch a movie at CinIME.

There were n members who received popcorn buckets numbered from 1 to n.

At a certain moment, bucket 1 had one popcorn, bucket 2 had two popcorns and so on until bucket n, which had n popcorns. As good competitive programmers, they always prefer to simplify things, and decided to gather all the popcorn in just one bucket.

They proceeded on the following way: In bucket 2, they gather the popcorn from buckets 1 and 2. Then, in bucket 3, those of bucket 2 and 3 and so on until the last bucket. Formally, they perform n - 1 movements, on the i-th movement they join the popcorn from buckets i and i + 1 on bucket i + 1. However, they are known to be clumsy and at each moment they join two buckets, they let a single popcorn fall to the ground, which they promptly throw in the trash.

Jiang, the Sharp, realized that maybe the last bucket would be too small to hold all of the popcorn. Therefore, he asked for your help to determine how much popcorn should remain in the last bucket.

Given n, the number of members who decided to watch the movie, print the amount of popcorn that would remain in bucket n. Keep in mind that exactly one popcorn is lost at each step.

Input

The first line contains the integer n (2 ≤ n ≤ 3 * 109) – the number of members from MaratonIME who decided to watch the movie.

Output

An integer: The amount of popcorn the last bucket should have.

Examples
Input
2
Output
2
Input
3
Output
4
Input
1000000
Output
499999500001

B. MaratonIME challenges USPGameDev
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Year after year, MaratonIME (group that authored this contest) and USPGameDev (game developing group at USP) fight epic clashes that last for centuries over which group will get each freshman to join them. This year, Russo (from MaratonIME) challenged Wil (from USPGameDev) to a dangerous match of darts.

Each one of them has already thrown their darts at the bullseye, but they can't decide which one of them got closest to hitting the center of it. Each one of them claims to have won the match. You, as a fair freshman, decided to judge the clash yourself.

Two points on the 2d plane are given, r, the point where Russo's dart hit, and w, the point where Wil's dart hit. If r is closest to the origin (0, 0) than w, Russo won and you should print out "Russo" (no quotes) and join MaratonIME. If w and r are equally close to the origin, there's a draw, you should print "Empate" (no quotes), which stands for "Draw" in portuguese, and join MaratonIME, because that was the agreed draw outcome. If w is closest to the origin than r, you should print "Wil" (no quotes) and join MaratonIME anyway, because it is the coolest group.

Input

On the first line of the input, a pair of integers xr and yr is given, the coordinates hit by Russo. On the second line another pair of integers xw and yw is given, the coordinates hit by Wil. Every coordinate is guaranteed not to exceed 10000 on absolute value, formally,  - 10000 ≤ xr, yr, xw, yw ≤ 10000.

Output

A single line containing "Russo", "Wil" or "Empate", acording to statement's instructions.

Examples
Input
2 1
3 0
Output
Russo
Input
10000 0
10000 1
Output
Russo

C. MaratonIME eats japanese food
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After a long time eating japanese food, the members of MaratonIME are getting really good at it. Nowadays, a massive amount of japanese food is eaten by the group and it's often difficult to find space for all the plates in the table, since two plates can touch but never overlap. The fact that there is so much food in each plate makes this even worse, because they can't move the plates on the table until there is no more food in them.

For that reason, everytime a plate arrives, they need to try lots of different positions for that plate on the table. You need to help them by creating a program that will aid on that rampant gluttony. Your program starts off with an empty table and has to respond to various queries, each of one of two types:

  1. A x y r - Place a circular plate centered at (x, y) with radius r.
  2. R x y r - Remove the circular plate centered at (x, y) with radius r.

For each plate, its center position (x, y) and its radius are given in centimeters (the plate's located x centimeters away from the left border and y centimeters away form the upper border). The table always has 10 meters both in width and height and a plate is allowed to hang off the table, as long as it's center is on the table (or on its border).

For each query of type A, you must determine if it was possible to place the given plate on the given position (if that plate does not overlap any other, note that it is allowed for it to touch other plates) and place it if possible. For each query of type R, you must determine if it was possible to remove that plate on the given position from the table (if there is a plate with those coordinates and radius on that position) and remove it if possible.

Input

On the first line of the input an integer Q ≤ 5000 is given, the amount of queries that need to be answered.

On each one of the Q following lines the queries are described. Each of them is given by a character , the type of the query, and three integers x, y and r, the coordinates and radius of the plate, 0 ≤ x, y ≤ 1000 and 1 ≤ r ≤ 1000.

Output

For each query, print a line with "Ok" (without quotes) if it is possible to perform such query (add the plate on type A and remove the plate on type R) and "No" otherwise.

Example
Input
8
A 20 25 15
A 25 25 5
A 20 55 15
A 35 40 7
A 35 40 6
R 20 25 15
A 20 25 10
R 20 25 15
Output
Ok
No
Ok
No
Ok
Ok
Ok
No

D. MaratonIME in the golden moment
time limit per test
0.5 с
memory limit per test
256 megabytes
input
standard input
output
standard output

It is a common knowledge the importance in practicing a physical activity, mainly when you take part in ICPC competitions. Keeping this in mind, Giovana Delfino invited her friends from MaratonIME to go rowing.

The initial total ability of the boat is 0. Despite the equal enthusiasm of all members, each friend i has a physical ability h(i). Dear teacher Gabi knows that whenever two friends x and y are together in the boat, the boat's total ability is increased by h(x)·h(y).

Giovana invited n friends, but rowing is not always possible when you have programming assignments and exams of the great professor Arnaldo Mandel ahead, so sometimes not everyone shows up. However, the teacher Gabi is very optimistic and hopes that, for the final semester competition, all n friends will attend in order to increase MaratonIME odds. Help Gabi find the total ability of the boat in this possible golden moment, assuming all friends show up.

Input

The first line contains one integer n (1 ≤ n ≤ 105) - the number of friends invited to row.

The second line contains n integers h1, h2, ..., hn (1 ≤ hi ≤ 3·104) - the abilities of each member.

Output

Print one integer - the boat's total ability in the golden moment.

Examples
Input
2
5 10
Output
50
Input
4
1 3 7 11
Output
152
Note

In the first example, in the golden moment there will be two members on the boat, then the ability there will be 5 × 10 = 50.

E. MaratonIME does (not do) PAs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Another semester has ended and Arthur finally achieved his dream of attending Data Structures I with all professors in the Mathematics Department. Now, he can finally pass this subject, but, like everyone expected, he didn't do any PAs (programming assignments), and all deadlines have passed.

Fortunately, all PAs can still be submitted for grading, but with a penalty given by: (late submission time) - (expected deadline time) for each PA.

Arthur, having taken Data Structures I so many times, knows exactly how much time he needs to complete each assignment. Now, he wants to write a program that determines the minimum sum of penalties that can be achieved, given he can do the PAs in any order.

It's worth noting that Arthur can't do more than one assignment at a time, since that skill is only learned in Data Structures II. Therefore, if Arthur starts working on an assignment, he needs to finish it before starting any other.

There is only one problem left: Arthur believes this problem to be unsettlingly similar to a PA, and, therefore, refuses to do it.

Help Arthur complete this task and, finally, take Data Structures II.

Input

The first line of input contains two integers 1 ≤ n ≤ 105 and 1 ≤ s ≤ 109, the amount of PAs Arthur needs to do and the time when he started to do them, respectively.

n lines follow, the i-th line contains two integers 1 ≤ ti ≤ 109 and 0 ≤ ei ≤ 109, the time Arthur takes to complete the i-th assignment and the expected deadline time for that assignment.

It is guaranteed s > ei for all i.

Output

Print the sum of all penalties if Arthur completes the PAs in the optimal order.

Example
Input
2 1
2 0
1 0
Output
6
Note

In the first example, if Arthur does the second PA first, he finishes it at time 2, and finishes the first one at time 4, making his total penalty equals to (2-0)+(4-0) = 6.

F. MaratonIME educates
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

USP has many lunch options between all the uni cafeterias and the restaurants inside the campus. An option that is usually chosen by MaratonIME seniors is the restaurant in the School of Education, for its good prices and free jelly.

The seniors have years of experience weighting on their shoulders, and therefore have tired legs. So they choose to go to the restaurant by car. Trying to save gas, the seniors always minimize the number of cars necessary to take everyone to the restaurant.

The seniors asked you to help them solve their problems. This morning, n cars with seniors arrived in the university, and all of them want to go to the restaurant. Each car holds up to 5 people. What is the minimum number of cars necessary to take everyone to the restaurant to "educate"?

Input

On the first line, an integer n, the number of cars. On the second line, n integers a1, ..., an, how many people arrived in each car.

Limits

  • 1 ≤ n ≤ 105.
  • 1 ≤ ai ≤ 5, for all i.
Output

Print a single integer, the minimum number of cars needed to take everyone to the restaurant.

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

G. MaratonIME does a competition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It's January and MaratonIME is attending to an ACM-ICPC Summer School in Campinas. Renzo, THE POWERFUL, went to visit his students and, as usual, brought chocolates from Peru. However, after a couple of parties, MaratonIME is growing a lot and Renzo doesn't have enough chocolates for everyone.

There is enough chocolate for of the students. So, Renzo will reward the best contestants. As a great coach, Renzo wants MaratonIME to work as a team, so he divided the students in 4 teams, , , and . The team which solves more problems wins. If two teams manage to solve the same amount of problems, Renzo rewards the team with smaller lexicographical name (if and draw, gets the chocolates).

In order to assign participants to teams, Renzo found out the amount n of contestants and gave each one of them a different integer from 1 to n. Having numbered the students, Renzo decided that the one with number 1 would go to team , the one with number 2 would go to team and so on. Formally:

  • The contestant with number 1 is on team
  • If 1 < i + 1 ≤ n and contestant i is on , then contestant i + 1 is on team
  • If 1 < i + 1 ≤ n and contestant i is on , then contestant i + 1 is on team
  • If 1 < i + 1 ≤ n and contestant i is on , then contestant i + 1 is on team
  • If 1 < i + 1 ≤ n and contestant i is on , then contestant i + 1 is on team

    There are many students and Renzo is busy thinking about the next contest he's creating, so you were chosen to determine which team wins the big prize! You are given a vector a of size n where, for each index 1 ≤ i ≤ n, ai is the amount of problems solved by contestant i during the contest. The amount of problems solved by a team is the sum of the problems solved by it's contestants.

Input

The first line of input has an integer 4 ≤ n ≤ 105. The second line, n integers 0 ≤ ai ≤ 104.

Output

You should print one line with name of the team that gets the chocolates: , , or .

Example
Input
4
1 2 3 4
Output
D

H. MaratonIME gets candies
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Obs: this is an interactive problem. More information is under the "Interaction" section.

MaratonIME is gathering to start another group practice. This time, Renzo decided to reward the students with candies as they solve problems. Curious as they are, the members of MaratonIME started to guess how many candies did Renzo bring. For each question, Renzo answered if the amount of candies was higher, lower or equal to the number asked.

Breno, noticing that the amount of candies could be very high, decided to limit the number of queries to 50. This way, the practice would start as soon as possible.

Renzo bought at least 1 and no more than 109 candies. Find how many candies were bought by Renzo with no more than 50 questions.

Input

For every question asked, read a character. It will be " > " if the amount of Renzo's candies is higher than your guess, " < " if the amount of Renzo's candies is lower than your guess or " = " if your guess is equal to the amount of Renzo's candies.

Output

You must print every query in the format "Q y", where y is the number guessed, and 1 ≤ y ≤ 109. After printing a question, you need to flush the output. Check the "Interaction" section for examples of how to flush the output.

Interaction

To ask Renzo a question, print the query in the format above. After printing a question, you need to flush the output. See examples below for each language:

C: fflush(stdout)

C++: cout.flush()

Java: System.out.flush()

Python: sys.stdout.flush()

Pascal: flush(output)

After each query, read a character as described above.

As soon as Renzo answers your question with "=" the program has to terminate. Your answer will be considered correct if you asked no more than 50 questions.

Example
Input
>
<
=
Output
Q 1
Q 3
Q 2
Note

In the example, the number of candies is 2. The answer is considered to be correct because only 3 out of the 50 possible questions were asked to obtain the character " = ".

Make sure to flush the output after printing each question!

I. MaratonIME divides fairly
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In a country trip, the contestants decided to play a soccer match. Yan, who was a professional player once, decided not to play to keep the teams balanced. He wanted to participate in another way, so he decided to choose the two teams.

Unfortunately, unlike soccer, Yan is very bad at math and doesn't know if he divided the teams fairly. Yan considers a division fair if the absolute difference between the number of players in each team is minimum. Can you help him?

Input

The first line has a single integer T, the number of test cases. The next T lines have two integers a and b, the number of players in each team.

  • 1 ≤ T ≤ 1000.
  • 0 ≤ a, b ≤ 109.
Output

Print T lines, one for each test case.

If Yan was fair, output the word "Ok".

If Yan wasn't fair, output two integers x and y, x ≤ y, the sizes of the teams in a fair division.

Example
Input
2
2 2
0 2
Output
Ok
1 1

J. MaratonIME goes to Mito
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

On MaratonIME's first trip to Mito, a restaurant, our dearest friend Estrela displayed some trouble to walk streets with trees. Every time he walked close enough to one, something really bad happened to him.

To avoid further harm, he decided to split the sidewalk into three separate lanes called S, M and H, each one approximately one meter wide, being S the one close to the street, M the one in the middle and H the one next to the houses. You can think of the region where Estrela walks as a grid with 3 lines (the lanes S, M and H) and n columns. Estrela is placed at the beginning (meter 1) of the sidewalk and wants to walk to meter n, where Mito is located. He knows the location of all the trees on his path and wants you to tell him if he can make it there unharmed. In order to guarantee that Estrela will arrive at Mito safely, he must not walk over any of the eight cells adjacent to the trees neither on the cells where trees are located.

The positions of the trees are given ordered, in other words, if i < j, the i-th tree wont be further away from the column 1 than the j-th tree.

Estrela can start and finish his walk at any lane.

The figure exemplifies the second test case. The dashed path is the path chosen by Estrela.

Input

In the first line there are two integers n e m the distance that Estrela wants to walk and the number of trees.

Then m lines follow, in the i-th line there is an integer ai and a character ci, meaning the i-th tree is in the lane ci and in the column ai. It is guaranteed that, if 1 ≤ i < j ≤ m, then ai ≤ aj, and no two trees in the input have the same lane and column.

Limits

  • 3 ≤ n ≤ 105.
  • 1 ≤ m ≤ 104.
  • 1 ≤ ai ≤ n e c1 = S or M or H for all i.
Output

Print "Yes" (without quotes) if Estrela can get to Mito safe and sound or "No" if not.

Examples
Input
4 2
1 S
4 S
Output
Yes
Input
5 2
1 H
5 S
Output
Yes

K. MaratonIME bot
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

As you probably already know, all members of MaratonIME use Telegram to communicate, for its amazing web and desktop apps, its bots and, of course, its stickers.

As time goes by, members eventually graduate and leave the group, a sad event for all. Victor "Sena" Sena, a member of MaratonIME, is tired of countless goodbyes, and has decided to do something about the void that fills his noble soul.

Sena realized that people in Brazil are becoming more and more alike, expressing themselves in the same way, with expressions like "kk eae men", "ata" and "zapzap". The members of MaratonIME are very similar as well, but they use different expressions.

Peculiarly, whenever someone asks a question, everyone answers "7". This is a tradition, from unknown origins, passed on by Germano "Germs" UnionFind. Besides, whenever someone says a sentence (that is not a question) and he mentions the dear member Gabriel "Sussu" Fernandes, all members yell in unison "AI SUSSU!". For any other sentence that doesn't fit any of these rules, the answer is "O cara é bom!" (this guy is good).

Figuring out these patterns, and using his incredible knowledge of software engineering, Sena decided to create a Telegram bot that simulates retired members of MaratonIME. He developed the whole platform, he just need the part that prints the answer for a given sentence, can you help him?

It has been agreed that a sentence is a question if it's last character is ?. Also, it is only said that there was a mention to Sussu's great name if one of the words in the sentence is exactly Sussu.

Input

The input consists of a single sentence, that is, a non-empty line, with space-separated words (strings with lower or upper case letters). The last character is always one among ., ! and ?. The line has at most 200 characters.

Output

Print what a MaratonIME member would answer to that sentence.

Examples
Input
Na viagem o Sussu comeu gelo achando que era gelatina.
Output
AI SUSSU!
Input
O Carlinhos zuou o Sussu!
Output
AI SUSSU!
Input
Bojack Horseman eh a melhor serie do Netflix.
Output
O cara é bom!
Input
Voce acredita na conjectura de Goldbach?
Output
7
Input
Eu estava andando e de repente sussu Susu SUSSU Sussussu Sussuzodia foi muito interessante.
Output
O cara é bom!

L. MaratonIME doesn't like odd numbers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Estrela is known for defending tolerance time in delay tolerance. When he was attending to his MAC101 classes, there was a 15 minutes tolerance for delays and once he got 19 minutes late to the class. Estrela lost 7 points in his grade because of this even after he tried to explain how big the line for the Hot-Dog truck was. Later that day, he was talking about this situation during a training day for MaratonIME when Yan noticed a something odd: there was a 15 minutes delay tolerance, Estrela was 19 minutes late and lost 7 points. He said: "Estrela, can't you see? These are all odd numbers!".

The observation startled them and they realized that many of MaratonIME's catchphrases had a odd number of alphanumeric characters: "Oh, Fox!", "7", "Wubalubbadubdub", among others. That could not be a coincidence! They also realized that in their own names: Estrela and Yan.

Sena, whose name doesn't fit the observations, wants people to stop worrying about this kind of nonsense and focus on their training but he's busy trying to contain the great ruckus caused by the "7 Theory".

You agree with Sena and believe that if you create a super catchphrase with even length, people won't believe this crazy theory anymore. A super catchphrase is the concatenation of some (possibly none) catchphrases, as an example, "Da Matta is big." (12 alphanumeric characters) and "What a man!" (8 alphanumeric characters) can be used to make the super catchphrase "Da Matta is big. What a man!" (22 alphanumeric characters).

Since MaratonIME has a gigantic amount of catchphrases, you have to make a program that will determine the size of the greatest even length possible for a super catchphrase that is the concatenation of some (possibly none) of MaratonIME catchphrases. Note that if no super catchphrase with even length can be created the answer is 0.

Input

On the first line there will be an integer n, the amount of catchphrases and, on the second line, n integers, the i-th integer, ai, is the amount of alphanumerics on the i-th catchphrase.

Limits

  • 1 ≤ n ≤ 105.
  • 1 ≤ ai ≤ 104.
Output

Print the largest even size of a super catchphrase.

Examples
Input
3
1 2 4
Output
6
Input
6
4 8 15 16 23 42
Output
108