Higher Institute for Applied Sciences and Technology Collegiate Programming Contest 2016
A. Cards
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Omar has a deck of cards. Every card has a unique integer number written on it. He says that his cards are numbered starting from 1, and if a card with number N exists, then a card with number N + 1 exists. Yes he may have an infinite sequence !

Yesterday when he went to school, his little brother Samir played with his cards by sorting them into two boxes according to the numbers written on them by repeating the following two steps:

  1. Take the card with the smallest number, let it be X.
  2. Put the card with number X in the first box and put the card with number 2 * X in the second box.
So the first few numbers in the boxes will be:

First box : 1, 3, 4, 5, 7, ...

Second box : 2, 6, 8, 10, 14, ...

Omar came back home and he asked Samir for the card with number Q written on it. Help Samir to find out in which box he can find the required card.

Input

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases .

T lines follow, each describing a test case consisting of a single integer Q (1 ≤ Q ≤ 1018)

Output

For every test case print "First Box" if the card is in the first box or "Second Box" otherwise.

Example
Input
3
1
6
1024
Output
First Box
Second Box
First Box

B. RGB plants
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Farmer John has recently bought three flowers in order to plant them around his house. The flowers were of three different colors red, green and blue.

As we all know, the garden that surrounds farmer John's house is a magical garden. That means that if you plant a number of flowers in it on some day, then the number of flowers will increase in the next day.

The garden increases the number of flowers depending on the color of the flowers, that is, if you plant a red flower in a day, then it will turn into 6 flowers in the next day (1 red flower, 2 green flowers, and 3 blue flowers). If you plant a green flower in a day, then it will turn into 15 flowers in the next day (4 red flowers, 5 green flowers, and 6 blue flowers). If you plant a blue flower in a day, then it will turn into 24 flowers in the next day (7 red flowers, 8 green flowers, and 9 blue flowers).

As we have mentioned above, farmer John has three flowers (1 red flower, 1 green flower, and 1 blue flower), and he will plant them in his magical garden around his house, so the number of the flowers will increase over time. Farmer John knows that if he plants his three flowers in his magical garden, then the number of flowers will increase from day to day, so he wants to know the total number of flowers in his magical garden in the nth day.

Input

The first line of the input is the number of test cases T (1 ≤ T ≤ 103). Each test case consists of a single line containing a single integer n (1 ≤ n ≤ 109).

Output

For each test case, print a single line containing the total number of flowers in the magical garden in the nth day modulo 1000000007.

Example
Input
4
1
2
20
1000000
Output
3
45
238775645
464884429

C. Ramzi
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ramzi -Aufa's best friend- lives in the city of Rainland, Rainland is a very ordinary city except for one thing. It has a very Bad Weather!

The city is described as a set of intersections and a set of connections. Each pair of intersections is either connected with a cars-road, or with a pedestrian-road. Some pairs has a cars-road and a pedestrian-road connecting them and some pairs doesn't has any roads between them at all. You can assume that no pair has more than one pedestrian-road or more than one cars-road.

Ramzi can get a taxi to go from intersection A to intersection B if A and B has a cars-road connecting them, but he has to walk if it's a pedestrian road. Mostly he will be walking in the rain!

Ramzi is in intersection x and he want to meet Aufa in intersection y. Your job is to help him find the Optimal path form x to y.

The Optimal path is described as the path with the minimum walking time. If there is more than one path with the same minimum walking time, the Optimal path is the one with the minimum total time. The walking time for any path is the sum of the pedestrian-roads' time that occur in the path.

The total time for any path is the sum of its roads's time "pedestrian-roads and cars-roads" .

You can assume that Ramzi doesn't get wet when he is waiting for the taxi in some intersection, so we aren't interested in the waiting time for the taxi. Also he cant't walk throw any cars-road. So if he want to use a cars-road, he must take a taxi.

Input

The first line of the input will contain T the number of test cases.

Each test case starts with two integers on a single line (0 < N ≤ 100), the number of the intersections, (0 < M ≤ N * (N - 1)), the number of the connections.

Then M lines follow, each describes a connection and contains four integers (0 < a ≤ N) , (0 < b ≤ N) , (0 ≤ c ≤ 10000) , (). Which means that there is a connection between intersection a and intersection b that takes c minute of time. However if k is equal to 1 then it's a pedestrian-road, otherwise it's a cars-road. All connections are bidirectional. Meaning that you can use it to go both from a to b and from b to a. It's guaranteed that (a ≠ b).

Follows a line containing two integers (0 < x ≤ N), (0 < y ≤ N). which means that we are interested in the optimal path between intersection x and intersection y. It's guaranteed that (x ≠ y).

Output

For each test case, if there is a path between x and y, you should print two integers on a separated line.

The first one should be the walking time in the optimal path. The second one should be the total time of the optimal path. If there isn't any path between x and y then you should print -1 on a separated line. See the sample output for more details.

Example
Input
3
3 3
1 2 5 1
1 3 5 2
3 2 4 1
1 2
2 2
1 2 5 2
1 2 3 1
1 2
3 1
1 2 5 1
1 3
Output
4 9
0 5
-1
Note

Large I/O files. Please consider using fast input/output methods.

D. Max or Min .. that is the question!
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Omar is a very lucky person. One day he found an array of five integers in the middle of the street!

Because Omar loves pre-calculations, he looked at the numbers and immediately marked the maximum number and the minimum number among them, just in case someone asked him about such information!

The next day people started asking questions about the array. Most people asked about the maximum number and the minimum number as expected, but one question was beyond all Omar's expectations! The question was: "what is the maximum number we can get from choosing two distinct numbers from the array, such that their multiplication is as large as possible ?"

It's a sure thing that Omar can easily calculate this information, but as everyone knows .. he is a very busy person. Can you help him answering the question?

Input

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

Each test case is represented with five integers on a single line separated by spaces, the numbers that Omar found. All numbers are positive, distinct integers and less than 1000.

Output

For each test print one integer. The answer to the question above.

Example
Input
2
1 2 3 4 5
50 40 30 20 10
Output
20
2000

E. Playing with numbers
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Folan and Eltan are brothers. However, as all brothers are, they always fight. One day their mom had to go to work, so she decided to give them a task to keep them busy while she is away.

She gave them two numbers S and N.

She told Folan that he has to delete exactly N digits from the number S, so that the resulting number is as small as possible.

Then, she told Eltan that he has to delete exactly N digits from the number S, so that the resulting number is as big as possible.

Folan and Eltan are ex ACMers. They decided to write a program to solve this problem, so they can go back to fighting again.

When their mom heard the evil plan, she decided to make the number S very big, and she may have added leading zeros to it.

The boys were really upset because they couldn't find a way to write a program that would solve this problem fast enough before their mom returns, so they asked for your help.

Can you help them with this program, so they can go back to fighting again?

Input

The first line of the input consists of a single integer t, the number of test cases. Each test case consists of two numbers S and N separated by a single space. where (0 ≤ S < 10100000) and it may contain leading zeros, and (0 ≤ N < |S|).

Note that |S| means the length of the number S.

Output

For each test case, print two lines.

The first line should contain the smallest number Folan can get after deleting exactly N digits from S.

The second line should contain the biggest number Eltan can get after deleting exactly N digits from S.

Please note that in case some of the leading zeros were not deleted, you have to print the resulting number with the remaining leading zeros.

Example
Input
3
00123 2
00123 3
234714812741111111111111111111 4
Output
001
123
00
23
14812741111111111111111111
74812741111111111111111111

F. Fairness
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Dwik and his brother Samir both received scholarships from a famous university in India. Their father, Besher, wants to send some money with each of them.

Besher has n coins, the ith coin has a value of ai. He will distribute these coins between his two sons in n steps. In the ith step, he chooses whether to give the ith coin to Dwik or to Samir.

Let xi be the absolute difference between the sum of Dwik's and Samir's coins after the ith step. The unfairness factor of a distribution is max({x1, x2, ..., xn}). Besher wants to minimize the unfairness factor, can you help him?

Input

The first line of the input consists of a single integer t, the number of test cases. Each test case consists of 2 lines:

The first line contains an integer n (1 ≤ n ≤ 100).

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100).

Output

Print t lines, ith line containing a single integer, the answer to the ith test case.

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

In the first sample test, besher has 5 coins (1, 2, 1, 4, 3), he can distribute them in the following way:

Step 1: Give the first coin to dwik , d = 1, s = 0 x1 = |1 - 0| = 1

Step 2: Give the second coin to samir, d = 1, s = 2 x2 = |1 - 2| = 1

Step 3: Give the third coin to samir, d = 1, s = 3 x3 = |1 - 3| = 2

Step 4: Give the fourth coin to dwik, d = 5, s = 3 x4 = |5 - 3| = 2

Step 5: Give the fifth coin to samir, d = 5, s = 6 x5 = |5 - 6| = 1

max({x1, x2, x3, x4, x5}) = 2

G. Repeat it
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Jad has bought a new computer, a really weird computer!!

Every time he copies some number from the screen and pastes it, the computer pastes it many times instead of once!

Jad tested his computer many times, and now he knows how many times the computer will paste each copied number.

For example, In case the new computer repeated each copied number 4 times. When Jad copies the number 31 and pastes it, the number that appears on the screen would be 31313131.

Given N the number that Jad copied, and M the number of times the new computer is pasting each copied number. you have to print the number that will appear on the screen.

Since the number might be very big, you are asked to print it modulo 1000000007.

Input

The first line of the input consists of a single integer t, the number of test cases. Each test case consists of two numbers M and N separated by a single space:

(1 ≤ M ≤ 109) is the number of times the new computer pasted the number N.

(0 ≤ N ≤ 109) is the number Jad had copied.

Output

For each test case print one line, the number that will appear on the screen modulo 1000000007.

Example
Input
3
4 31
8 1
123 123
Output
31313131
11111111
388853804

H. Robocon Club
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Ahmed thought that robotics is fun so he quit ACM and joined Robocon club ! Unfortunately his first task at the Robocon Club did not go as well as he expected. He was supposed to build a robot that moves in a straight line.

The robot he had built consists of a line segment of length L with a wheel of radius R on each of it's endpoints. He placed the robot on the x axis, such that the center of the robot was the point (0, 0) , facing the positive y axis (the left and right wheels are located on and respectively).

The two wheels started moving at the same time, however, instead of moving at the same speed, the left wheel rotated at VL revolutions per second(RPS), while the right wheel rotated at VR RPS. both wheels stopped moving after S seconds. Can you help Ahmed locate the center of his robot?

Input

The first line of the input consists of a single integer T , the number of test cases. T lines follow , each describing a test case consisting of five integers L , R , VL , VR , S . indicating the length of the robot , the radius of each wheel , the speed of the left wheel in (RPS), the speed of the right wheel in (RPS) and the duration that the robot had moved , respectively . where (1 ≤ L ≤ 100 ,1 ≤ R ≤ 100 ,0 ≤ VL ≤ 100 ,0 ≤ VR ≤ 100 , 1 ≤ S ≤ 100 ) .

Output

for each test case print two real numbers on a line separated by a space denotes the coordinates of the center of the robot rounded to three decimal places .

Example
Input
4
1 1 1 1 1
7 3 2 3 2
10 1 2 1 1
4 3 2 0 1
Output
0.000 6.283
-6.589 -13.682
2.865 8.817
4.000 0.000

I. Playing with strings
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Taboush is a 10 year-old school boy. On his birthday, his parents got him a new Alphabet blocks game.

Alphabet blocks game consists of cubes. Each cube has a letter written on it, and each letter is written on an infinite number of cubes.

Taboush wasted no time and he immediately started forming his magical string S1. He spent all day forming the string. At the end, he was so tired, so he felt asleep.

While he was asleep, his naughty cat Basbouse - as he called her - found the magical string. She started to add, delete and shuffle letters in S1, and she ended up forming a new string S2.

When Taboush finally woke up, he was upset that Basbouse had ruined his magical string. Now, he wants to form his magical string all over again.

In one move, Taboush can add a letter to S2 or delete a letter from S2. At the end, Taboush can shuffle the letters to any order he wants.

Can you help Taboush by telling him what is the minimum number of moves he needs to do, in order to convert S2 into S1?

Please note that shuffling the letters is not counted as a move.

Input

The first line of the input consists of a single integer t denoting the number of test cases.

Each test case consists of 2 lines. The first line contains S1, and the second line contains S2 (1 ≤ |S1|, |S2| ≤ 105) consisting of lower case English letters only.

Output

For each test case print a single line containing the minimum number of moves Taboush needs in order to convert S2 into S1.

Example
Input
3
abc
abd
abcde
bdcea
taboush
basbouse
Output
2
0
5
Note

|S| means the length of the string S.

In the first test case, Taboush has to delete the letter d, then add the letter c. Thus, he needs 2 moves.

In the second test case, Taboush has to shuffle the letters only. Thus, he doesn't need any number of moves.

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

At Cola factory there is N bottles on a line. Also, there is a machine that pour cola in these bottles one by one. Every thing was working well. Suddenly, the machine started acting in a strange way !!

It started choosing a random bottle and pour a random quantity of cola in this bottle.

When a bottle is full, the rest of the cola goes to the bottle on the right of it, and if it was the last bottle, then the rest of the cola will be wasted .

As an engineer in this factory, you were given the capacity of every bottle in Litters. Also, you know the record of machine moves because it is stored in the Microcontroller memory of the machine. You are asked to compute the amount of wasted cola, and the amount of cola every bottle has at the end.

Input

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

Every test case starts with two numbers N and M (1 ≤ N ≤ 105), (1 ≤ M ≤ 105) denoting the number of bottles, and the number of moves the machine had did.

Then follow N integers on a line separated by spaces. The integer Ci denotes the capacity of the ith bottle (1 ≤ Ci ≤ 109) where (1 ≤ i ≤ N).

M lines follow denoting the moves. Each line contains two integers X and Y (1 ≤ X ≤ N), (1 ≤ Y ≤ 109) means that the machine poured Y liters of cola in the Xth bottle .

Output

For each test case print two lines.

First line contains the amount of wasted cola.

The second line contains N integers separated by spaces denoting the amount of cola in every bottle at the end.

Example
Input
2
5 3
5 4 3 2 1
3 4
4 4
1 2
6 3
3 4 5 5 6 7
3 3
1 8
5 9
Output
2
2 0 3 2 1
0
3 4 4 0 6 3

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

When HIAST CPC 2016 was finally over, Feras found himself taking the last place !!

He went home exhausted from all the hard problems he had tried to solve in the contest. In order to take his mind off the problems for a while, he decided to play a PC game. Yes, he decided to play his favorite game Army (Army is an advanced version of the well known game Red Alert).

Rules for Army are quite simple. On the battlefield you have the following 3 concepts:

  1. N soldiers numbered from 1 to N.
  2. M places numbered from 1 to M.
  3. W type of weapons numbered from 1 to W.

Each one of your soldiers may guard exactly one place, and each place may be guarded by exactly one soldier. In order for a soldier to guard a certain place, he needs to have exactly one weapon. Your job is to cover as many places as possible. However, it's not that simple.

On one hand, your soldiers are a bit moody. For the ith soldier you are given two lists:

  1. The first list is for places consisting of Yi places. It means that the ith soldier prefers exactly Yi places. Therefore, the ith soldier will only guard one of the places mentioned in his places list.
  2. The second list is for weapons consisting of Zi weapons. It means that the ith soldier prefers exactly Zi weapons. Therefore, the ith soldier will only guard one of the places that has one of the weapons mentioned in his weapons list.

On the other hand, for each place you are given a list consisting of Ck weapons indicating the weapons available at the kth place. Therefore, if you assign soldier x to guard place y, then he can only have one of the weapons available at place y. Please note that it's possible that many places have the same kind of weapons. i.e. 2 places may have the same kind of weapons.

Place y is called "guarded" if there is a soldier x standing on place y and carrying a weapon z, such that:

  1. Weapon z is one of the weapons available at place y.
  2. Weapon z is one of the weapons preferred by soldier x.
  3. Place y is one of the places preferred by soldier x.

Feras is exhausted from HIAST CPC, and he felt frustrated because he couldn't find the perfect distribution for soldiers in order to guard as many places as possible, so he asked for your help. Can you help poor Feras to feel better about him self? Help him calculate the maximum number of places that could be guarded.

Input

The first line of input contains a single integer T, indicating the number of test cases.

The second line of input consists of three integers (1 ≤ N ≤ 100), (1 ≤ M ≤ 100) and (1 ≤ W ≤ 100), indicating the number of soldiers, the number of places and the number of weapons, respectively.

Then N lines follow. The ith line of them describes the places which the ith soldier prefers. Each line starts with an integer Yi denoting the number of the places, followed by Yi distinct integers (1 ≤ yi ≤ M) separated by spaces indicating the list of places which the ith soldier prefers.

N lines follow. The ith line of them describes the weapons which the ith soldier prefers. Each line starts with an integer Zi denoting the number of the weapons, followed by Zi distinct integers (1 ≤ zi ≤ W) separated by spaces indicating the list of weapons which the ith soldier prefers.

M lines follow. The kth line of them describes the weapons available at the kth place. Each line starts with an integer Ck denoting the number of the weapons, followed by Ck distinct integers (1 ≤ ck ≤ W) separated by spaces indicating the list of the weapons available at the kth place.

Output

For each test case print a single line containing the maximum number of places that can be guarded.

Example
Input
2
3 4 5
2 1 2
2 1 4
2 3 4
1 3
2 2 5
3 1 3 4
2 3 2
1 2
1 4
3 5 1 3
2 2 2
1 1
1 2
1 1
1 2
1 2
1 1
Output
3
0