2015 AlBaath Collegiate Programming Contest
A. Traffic Lights
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Tamer is traveling with his brother on a long highway. He sees a traffic light at a distance. He calculated that it will take him x seconds until he arrives at the traffic light, he also knows that the green light lasts for g seconds, the yellow light lasts for y seconds and the red light lasts for r seconds. Now he is wondering in what color will the light be when he arrives there?

You know he is now busy driving, so he asks you to tell him the answer! you know that the light has just turned green at the moment of his question, and that the sequence of the lights is: GREEN, YELLOW, RED and then GREEN and so on.

Input

The first line of input contains one integer T - the number of test cases.

Each test case contains four integers x, g, y, r as described in the statement.

1 ≤ x, g, y, r ≤ 109

Output

For each test case output a single word, "RED" or "YELLOW" or "GREEN" without the quotes.

Examples
Input
3
5 5 2 8
7 5 2 8
16 5 2 8
Output
YELLOW
RED
GREEN
Note

In the samples the light changes as follows:

Light: g, g, g, g, g, y, y, r, r, r, r, r , r , r , r , g , g , g , g ...

Time : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18...

B. 8 Queens, Again!!
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Yaaaay, Haven't you heard the news? Bakaloria results are out! And Reem had very good grades. Finally she can go to IT college and pursue her childhood dream of becoming a great programmer.

Reem is very excited about her college, she already started learning programming. Today she was learning about a very well known problem, the 8-Queens problem (you never saw that coming, didn't you?) she has wrote a program to generate all the possible situations of the queens, but as a novice programmer she found it hard to check whether if these situations are valid. As usual you come to her rescue and offer to help with this hard task!

Now you are stuck with this task: Given the positions of 8 queens on a regular chess board, determine if this situation is valid.

A valid situation is a configuration of the 8 queens where no queen can strike any other queen.

On a standard 8 × 8 chess board, a queen can strike any other queen on it's row, column, or two diagonals.

Input

The first line of input has one integer T the number of test cases your program must process.

Each of the next T lines contains the positions of 8 queens. A position of a queen is described as one character [A - H] (the column of the queen), followed by one number [1 - 8] (the row of the queen)

For example: "A4" represents a queen at the first column and the fourth row.

(see sample input for more details)

Output

For each test case print one line containing the word Valid if the configuration is valid, or Invalid otherwise.

Examples
Input
2
A1 B5 C8 D6 E3 F7 G2 H4
C3 E4 C4 E1 C4 F4 A8 G6
Output
Valid
Invalid
C. Rotate It !!
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Dzy and Fox have a sequence A consisting of N numbers [A1...AN]. Dzy starts by taking the first number, then Fox takes the second number, then Dzy takes the third number and so on, they continue taking turns until all of the N numbers are taken. The player with the highest sum of numbers wins.

Since Dzy is your dear friend, you decided to rotate the sequence (you may rotate it as many times as you like) in order to maximize Dzy's sum of numbers.

Rotation is defined as removing the first element from the beginning of the sequence and adding it to the end of the sequence.

So given the sequence A , you have to help Dzy and let him achieve the maximum possible sum.

Input

The first line containts a single integer T, the number of test cases.

Then T testcases are given as follows :

The first line of each testcase contains a single integer N (1 ≤ n ≤ 104).

The second line of each testcase contains N space-separated integers [A1...AN],the elements of the sequence A (1 ≤ i ≤ n) ( - 109 ≤ Ai ≤ 109).

Output

Output T lines , The answer for each testcase which is the maximum achievable sum by Dzy if you help him.

Examples
Input
1
5
1 5 3 2 4
Output
12
Note

Consider all 5 rotations of the sequence:

1 5 3 2 4 (Dzy score = 1 + 3 + 4 = 8)

5 3 2 4 1 (Dzy score = 8)

3 2 4 1 5 (Dzy score = 12)

2 4 1 5 3 (Dzy score = 6)

4 1 5 3 2 (Dzy score = 11)

D. The Three Kings of Asgard
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

The Three Kingdoms of Asgard are ruled by three very powerful and wealthy kings: Adam, Bob and Carl. Many people think they are very, very evil kings. Every year they exchange some artillery forces to keep the kingdom at peace.

Traditionally king Adam has to give to king Bob as much force as king Bob has. then King Bob gives King Carl as much force as King Carl has. In the end King Carl gives King Adam as much force as King Adam has left.

This year the three kings were surprised to find that all three of them have the same amount of force, but they couldn't recall how this happened so it's your job to find out how much force each one had last year!

Input

The first line contains T the number of test cases your program has to solve.

Each test case contains one number N(1 ≤ N ≤ 109) the amount of force each king has this year.

Output

For each testcase output three integers: A, B, C. The amount of power Adam, Bob and Carl had last year, respectively. Or say that it is "Impossible".

Examples
Input
2
24
10
Output
33 21 18
Impossible
Note

In the first testcase:

last year: Adam has 33, Bob has 21 and Carl has 18.

Adam gives Bob as much as Bob has, so Adam in now 12 and Bob is now 42, Carl still have 18.

After that: Bob gives Carl 18, so Adam(12), Bob(24), Carl(36)

Now Carl gives Adam 12: Adam(24), Bob(24), Carl(24). So In the end Each king has 24 force, as the input indicates.

E. Qwerty78 Trip
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Qwerty78 is a well known programmer (He is a member of the ICPC WF winning team in 2015, a topcoder target and one of codeforces top 10).

He wants to go to Dreamoon's house to apologize to him, after he ruined his plans in winning a Div2 contest (He participated using the handle "sorry_Dreamoon") so he came first and Dreamoon came second.

Their houses are presented on a grid of N rows and M columns. Qwerty78 house is at the cell (1, 1) and Dreamoon's house is at the cell (N, M).

If Qwerty78 is standing on a cell (r, c) he can go to the cell (r + 1, c) or to the cell (r, c + 1). Unfortunately Dreamoon expected Qwerty78 visit , so he put exactly 1 obstacle in this grid (neither in his house nor in Qwerty78's house) to challenge Qwerty78. Qwerty78 can't enter a cell which contains an obstacle.

Dreamoon sent Qwerty78 a message "In how many ways can you reach my house?". Your task is to help Qwerty78 and count the number of ways he can reach Dreamoon's house. Since the answer is too large , you are asked to calculate it modulo 109 + 7 .

Input

The first line containts a single integer T , the number of testcases.

Then T testcases are given as follows :

The first line of each testcase contains two space-separated N , M ( 2 ≤ N, M ≤ 105)

The second line of each testcase contains 2 space-separated integers OR, OC - the coordinates of the blocked cell (1 ≤ OR ≤ N) (1 ≤ OC ≤ M).

Output

Output T lines , The answer for each testcase which is the number of ways Qwerty78 can reach Dreamoon's house modulo 109 + 7.

Examples
Input
1
2 3
1 2
Output
1
Note

Sample testcase Explanation :

The grid has the following form:

Q*.

..D

Only one valid path:

(1,1) to (2,1) to (2,2) to (2,3).

F. black-white
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Steven met his old friend Mikael yesterday and he told him about a very interesting game. The game board is made of N cells aligned in a row , and two colored stones in two different fixed positions of this row. The first stone is white, and the second is black. Steven plays with the white stone, and Mikael plays with the black one.

The two players play alternately, Each player in his turn can move his stone one cell to the right or to the left, but he cannot move it outside the board or onto a cell occupied by the other player. Steven goes first. The player who cannot make any move loses.

Steven and Mikael have become very good at playing this game, so they can know the winner of the game just by looking at the starting state of the board. Can you do the same?

You are given the initial game board and you should know who is the winner of this match, considering both players playing optimally (if both players play optimally the game will end).

Input

The first line of input is an integer T which represents the number of test cases. Each of the next T lines consists three integers N , W , B , the length of the game board , the position of the white stone , the position of the black stone (2  ≤  N  ≤  100000) (1  ≤  B , W  ≤  N)

Output

For each test case, output a single line representing its answer; if Steven is the winner output "Steven" (without quotes) otherwise "Mikael" (without quotes).

Examples
Input
1
11 4 8
Output
Steven
G. Square Spiral Search
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

A new computer scientist is trying to develop a new memory management system called "spiral memory management".

The basic idea of this system is that it represents the memory as a 2D grid with a predefined origin point, and the address of each memory location is represented as its (x,y) coordinates, and it tries to store frequently used data as close to the origin point as possible.

This system needs a search algorithm. Our computer scientist is currently developing an algorithm called "square spiral search".

The algorithm searches the memory locations in the following order (also shown in the figure):

(0,0), (1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (2,-1), (2,0), (2,1), (2,2), (1,2), (0,2), (-1,2), (-2,2), (-2,1), (-2,0), (-2,-1), (-2,-2,) ,(-1,-2) ... and so on.

Now he is wondering: how many steps would it take to reach a memory location with the address (x, y) using the square spiral search. Can you help him find the answer?

Input

The input starts with T the number of test cases, T test cases follows.

Each test case consists of two numbers: X, Y the address of the memory location.

 - 1, 000, 000, 000 ≤ X ≤ 1, 000, 000, 000

 - 1, 000, 000, 000 ≤ Y ≤ 1, 000, 000, 000

Output

For each test case print the number of steps it would take to reach the memory location ( x, y ) .

Examples
Input
3
1 0
1 1
-2 1
Output
1
2
17
Note

The number of steps to reach a memory location is defined as the number of memory locations searched before searching the requested location.

H. Phobia
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Sally has a phobia of cockroaches. Every night she is having the same horrible nightmare! Where she is standing alone in a big maze surrounded by millions and millions of cockroaches. She wakes up horrified and screaming when she sees a huge cockroach standing on her foot. After many sleepless nights like that one, she finally decided to ask you for help.

Since you have some experience with psychology (after all you are a programmer, right?) you tell her that the best way to cure her phobia is to fight it. She must be strong and fight these stinky little insects. After many argument she agrees with you and decides that she must overcome her fears. To do so she must reach for her sandals (you know, she needs a weapon for this great battle). Sally marked her sandals with a big red X sign to make sure they are clearly noticeable.

Here comes your job! You thought that you should write a program to help her train for this battle. Given the maze information, your program should tell her whether if she could reach her sandals without being touched by any cockroach.

The maze is an N × M rectangular grid, each cell of this grid is either empty or a wall or a hole. Cockroaches emerge from these holes and spread in all directions. Sally and Cockroaches cannot pass through walls, in other words Sally can only move to an empty cell, and cockroaches can only occupy an empty cell.

Formally, at time t if cell (i, j) is occupied by cockroaches then in time t + 1 cells (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1) as well as cell (i, j) will be occupied by cockroaches if the respective cells are empty and are inside the borders of the maze.

In one second, Sally can move to an adjacent empty cell. Formally if at time t Sally is at cell (i, j), then in time t + 1 she can move to one of these cells: (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1) if the respective cells are empty and are inside the borders of the maze.

One empty cell contains Sally starting position, and One other empty cell Contains her Sandals. Sally's goal is to reach her sandals without touching any cockroach. Sally touches a cockroach when Sally's current position is occupied by cockroaches.

Input

The first line will be the number of test cases T.

Each test case contains two integers N and M (1 ≤ N, M ≤ 100) followed by N × M grid that represents the maze where:

'S' : sally's starting position.

'X' : Sally's sandals position.

'#' : a Wall.

'*' : a hole.

'.' : an empty cell.

Output

For each test case print "yes" if Sally can exit from the maze without touching any cockroach or "no" otherwise.

Examples
Input
2
5 5
S..#*
...#.
...##
.....
....X
5 5
S..#*
...#.
...#.
.....
....X
Output
yes
no
I. What a Mess
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Alex is a very clever boy, after all he is the son of the greatest watchmaker in Odin.

One day, Alex was playing with some old watches and he found n gears, each gear has ai teeth in it. Alex likes to make beautiful pairs of gears, he thinks a pair of gears is beautiful if we attach the two gears together and spin the first gear exactly one rotation, then the other gear spins an integer number of rotations. For example a pair of 8 and 4 is beautiful, whereas a pair of 8 and 5 isn't, neither is pair of 4 and 8.

Now Alex is curious, he wants to know how many beautiful pairs are there. Counting is not Alex's thing, so he asked you to help him.

Input

The first line of input contains one integer T: The number of test cases you need to process.

Each test case consists of two lines. The first line is a single integer n: the number of gears Alex has. The second line contains n space separated integers ai: the number if teeth in the ith gear.

1 ≤ n ≤ 104

2 ≤ ai ≤ 106

Output

For each testcase print a single integer: the number of distinct pairs that satisfy the problem statement.

Examples
Input
2
5
4 6 7 8 12
6
2 2 2 3 3 4
Output
3
7
Note

note that we consider two pair distinct when they differ by at least one gear.

In the first sample the pairs are: (4,8) , (4,12) , (6,12)

J. Killing everything
time limit per test
4 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

There are many enemies in the world such as red coders and hackers. You are trying eliminate everybody. Everybody is standing on a road, which is separated into 109 sections. The sections are numbered 1, 2, 3, 4, …109 from west to east. You want to kill N enemies. The ith enemy will be standing on the section Ai. In order to kill the enemies, you prepared P small bombs and Q large bombs. You can choose a positive integer w as a parameter for energy consumption. Then, a small bomb can kill all enemies in at most w consecutive sections, and a large bomb can kill all enemies of at most 2w consecutive sections.

Enemies can be killed by more than one bomb. You want to kill all enemies. Since it is expected that many civilians will walk down that road, for the sake of safety, you have to fix the positions of the bombs and minimize the value of w.

So you decided to Write a program that, given information of the enemies and the number of bombs, determine the minimum value of w so all enemies can be killed.

Input

The input consists of several test cases, the first line contains the number of test cases T. For each test case: The first line of input contains three space separated integers N, P, Q (1 ≤ N ≤ 2000, 0 ≤ P ≤ 105, 0 ≤ Q ≤ 105), where N is the number of the enemies, P is the number of small bombs, and Q is the number of large bombs.

The ith line (1 ≤ i ≤ N) of the following N lines contains an integer Ai, the section where the ith enemy will be standing.

Output

Output: For each test cases print the solution of the problem on a new line.

Examples
Input
1
3 1 1
2
11
17
Output
4
Note

In the sample test case you have 3 enemies at positions: 2, 11, 17.

For w = 4, one possible solution is to throw one small bomb on segment 1 - 4, and one large bomb on segment 11 - 18. This configuration will kill all three enemies.

There is no configuration with w < 4 that can kill them all.

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

In computing, JPEG is a commonly used method of lossy compression for digital images, particularly for those images produced by digital photography . The degree of compression can be adjusted, allowing a selectable tradeoff between storage size and image quality,and JPEG typically achieves 10:1 compression with little perceptible loss in image quality. Entropy coding is a special form of lossless data compression. It involves arranging the image components in a "zigzag" order employing run-length encoding (RLE) algorithm that groups similar frequencies together, inserting length coding zeros, and then using Huffman coding on what is left.

Now i am so busy ,so i will give you a square matrix that represents pixel intensities of the image.

Your task is simple: reconstruct the image so that the value in the ith row and jth column of the resulting image is the value of the (i * N + j)th pixel visited in the zigzag sequence .

Input

Your program will be tested on one or more test cases. The first line of the input contains a single integer T (1  ≤  T  ≤  100) the number of test cases. Followed by T test cases.

Each test case consists of N+1 lines. The first line contains an integer N (2  ≤  N  ≤  100). The next lines consists of an squared pixel matrix.

Output

For each test case print the required transformed matrix.

Examples
Input
1
5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
Output
1 2 6 11 7 
3 4 8 12 16 
21 17 13 9 5 
10 14 18 22 23 
19 15 20 24 25