2015 Damascus Collegiate Programming Contest (DCPC 2015)
A. Random Fightings
time limit per test
4 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Nodar is a very famous gangster in Euroland, he has hundreds of friends but only N of them are gangsters like him, after his many successful heists in Linearland, Squareland and Cubeland, he decided to form a new gang called “The Nodar ACMers”.

He invited his N gangster friends and formed the gang very quickly, but all of his N friends are professional gangsters, and they’re very greedy.

Since gang leader will get 60% of the gang’s net income, all of them want that position.

Alex (Nodar's best friend) has 173 IQ points so he foresaw the bloodshed that will happen if each new leader is assassinated, so he devised a master plan to save his gang from all that terror thus having the freedom to terrorize the citizens of Euroland, and he said “Chess determines the skills of the true leader”, and then Nodar gave each of his friends a unique number from 1 to n, Nodar will host n - 1 matches, in each match the following will happen:

A pair of the remaining gangsters will be chosen at random ( the likelihood of choosing all pairs is uniform) The loser will be kicked out of the competition.

The remaining gangster will become the unquestioned boss of the gang, and will probably arrange Nodar’s “Accidental” death if he didn’t like him, Thus Nodar started to collect more information about his gang.

He found out that the probability of gangster i beating gangster j is Aij, it is guaranteed that Aij = 1 - Aji (Gangsters don’t believe in draws).

As Nodar’s personal programming assistant he asked you to write a program that would determine for each gangster, his probability of becoming the boss.

Input

The first line of the input contans one integer T , the number of testcases.

The first line of each testcase contains an integer N (1 ≤  N ≤  20) — the number of gang members.

Then there follows N lines with N real numbers each — matrix A.

Aij (0  ≤  Aij ≤  1) — the probability that gangster with index i beats gangster with index j. It's guaranteed that the main diagonal contains zeros only , and for other elements the following is true: Aij  =  1  -  Aji.

Output

For each test case print a single line containing "Case t:" (without the quotes) where t is the test case number (starting from 1) followed by a single space, followed by n space-separated real numbers with exactly 6 decimal places.

Number with index i should be equal to the probability that gangster with number i will win to be the leader of gang.

Examples
Input
2
1
0.0
2
0.0 0.5
0.5 0.0
Output
Case 1: 1.000000 
Case 2: 0.500000 0.500000
Note

You should print exactly 6 decimal places (even if zeroes).

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

You have N rectangles, all of their sides are either parallel to X axis or to Y axis, and you want to cover them all using one big rectangle.

what is the minimum area of the big rectangle you need in order to cover all the rectangles.

Input

The first line contains number of test cases T

Each test case consists of an integer N (1 ≤ N ≤ 1000), followed by N lines, each line describes a rectangle with four pairs of integers representing the X coordinate and Y coordinate of the vertices.  - 1000 ≤ Xcoordinate, Ycoordinate ≤ 1000

Output

For each test case print one integer which is the size of the rectangular cover.

Examples
Input
2
1
1 1 2 2 2 1 1 2
2
0 0 10 5 0 5 10 0
0 1 1 1 1 0 0 0
Output
1
50
C. Too Many Coins
time limit per test
4 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Your friend has C coins in his pocket, each coin has a value Vi, and you know that he will not need that amount of money, he will only need M.

You want to help him not to carry all these coins, so you decided to tell him to take the coins of specific values, in a way that he will have at least the amount of money he needs.

You will tell him that it will be enough for him if he carried coins of types X1, X2, ..., Xn.

Note that if you tell him to carry coins of type Xi, he will carry all the coins with values Vi = Xi.

Input

The first line contains an integer T representing the number of test cases.

Each test case consists of two lines, the first line has two integers C (1 ≤ C ≤ 1000000) and M (1 ≤ M ≤ 109), and the other line contains C integers representing the values of the coins (1 ≤ Vi ≤ 1000000).

Output

For each test case print the types of coins which your friend must carry,if there are multiple solutions, print the solution with the minimum number of types, if there are still multiple solutions print the one which makes your friend carry more money, if there are still multiple solutions print the solution with the bigger types.

print the types in increasing order. If he doesn't have enough money print "Impossible" without the quotations.

Examples
Input
3
10 7
1 1 1 1 1 2 2 2 5 4
10 11
1 1 1 1 1 1 1 1 1 1
10 6
1 1 1 1 1 1 2 2 2 3
Output
2 5
Impossible
2
D. Card Game
time limit per test
3 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You're playing a card game with K friends of yours, and since you're a champion in this game, they will play together and you will only play with the winner.

And now when they are playing your job is just to deal N cards and distribute them among your friends, you can choose how to distribute them, but the distribution should satisfy these rules:

1- Each player must have a continuous subsequence of the original set.

2- Each card must be dealt to some player.

3- Each player must have at least one card.

Note that it is not important that players have the same number of cards.

You know that all of them are playing using the same strategy so the player with the maximum card group power will win. Each card has a power P the power of group of cards is calculated as (the number of cards in that group) * (the maximum value in the same group).

Since the winner will play with you, and he will play using the same group of cards, you decided to minimize the power of his cards as much as you can.

Write a program to help you to do so.

Input

In the first line one integer T the number of test cases.

For each test case there will be two integers N and K (1 ≤ N ≤ 1000000 , 1 ≤ K ≤ min(N, 20000)), then N integers representing the power of the cards in the original set and their order. (1 ≤ Pi ≤ 1000000).

Output

For each test case print a single line containing one integer which is the minimum group power you can make the winner player have.

Examples
Input
1
10 3
1 2 3 4 5 6 7 8 9 10
Output
25
E. xortion
time limit per test
3 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

Hussain doesn't like long statements’ problems, so he will describe his problem in a nutshell.

Hussain will give you an array A[1….N] that consists of N positive integers.

Hussain will ask you Q Queries each one consists of an integer number X .

He wants you to find a number P : 1 ≤ P ≤ N such that (A[P]^X  ≥  A[I]^X ) for each (1 ≤ I ≤ N).

^ Refers to “XOR” operation in computer science .

In case of many possible values of P , take the minimum.

Input

The first line contains one number T – the number of testcases.

The second line contains two space-separated numbers, N and Q (1  ≤  N ≤  105, 1  ≤  Q  ≤  3×105) — the size of the array and the number of queries .

The next line contains N space-separated integers the elements of the array A . All of them will fit into 32 bit signed integer.

Next Q lines contain one integer X (also fits in 32 bit signed integer) which was described above.

Output

For each testcase output Q lines . The Ith line will contain the answer of the Ith query.

Separate testcases by a blank line .

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

Note

Use fast I/O methods

F. Print Mix Strings
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

While I was working in the company, the internet broke. I didn't have anything to do without internet, so I decided to write this ACM problem.

We need to mix between two strings and also we should keep the same order for both strings.

Example: if we have s1 = "ab" and s2 = "cd", we can generate six strings:

abcd acbd

acdb cdab

cadb cabd

thank you for your help in ”Count Mix Strings” problem. now I can calculate the complexity and make input and output files. You will be given the two strings and you should print all the distinct strings that could be generated in the alphabetical order.

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 (1 ≤ T ≤ 100).

Followed by the test cases, each test case is on one line. it contains two strings s1 and s2, both strings consist of at least 1 and at most 8 lower case English letters (from ‘a’ to ‘z’).

Output

For each test case, print all the distinct strings that could be generated in the alphabetical order.

print a blank line after each test case.

Examples
Input
2
a aa
ab cd
Output
aaa

abcd
acbd
acdb
cabd
cadb
cdab

G. Count Mix Strings
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

While I was working in the company, the internet broke. I didn't have anything to do without internet, so I decided to write this ACM problem.

We need to mix between two strings and also we should keep the same order for both strings.

example: if we have s1 = "ab" and s2 = "cd", we can generate six strings:

abcd acbd

acdb cdab

cadb cabd

but now I have a problem. I need to calculate the complexity for this problem to make input and output files.

you will be given the length of two strings and you should help me to find the number of strings that could be generated (if there is a repeated string, count it every time).

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 (1 ≤ T ≤ 10000). Followed by the test cases, each test case is on one line. it contains two numbers N and M the length of s1 and s2 where 1 ≤ N, M ≤ 10000

Output

For each test case, print a single line which contains a single integer that is representing the number of strings that could be generated MOD 10^9+7.

Examples
Input
3
1 1
1 2
2 2
Output
2
3
6
H. tourists
time limit per test
2 seconds
memory limit per test
24 megabytes
input
standard input
output
standard output

On one of the Caribbean Islands there are N tourists and you want to move them from this island to another one.

There are only two boats on this island, the first one can hold n1 tourists and cost c1 to move exactly n1 tourists from one Island to another, and the second one can hold n2 and cost c2.

The boat will not sail unless it is fully booked. Moreover, you want to minimize the total cost of moving all tourists from one island to another. You can use any boat several times.

Input

The input may contain multiple test cases. Each test case begins with a line containing an integer N (1 ≤ N ≤ 2 * 109).

The second line contains c1 and n1, and the third line contains c2 and n2.

Here, c1, c2, n1 and n2 are all positive integers having values smaller than 2 * 109.

A test case containing a zero for N in the first line terminates the input.

Output

For each test case in the input, print a line containing the minimum cost solution: two non-negative integers m1 and m2, where m1 is the number of times to use the first boat, and m2 is the number of times to use the second boat) if one exists.

Print "failed" otherwise. If a solution exists, you may assume that it is unique.

Examples
Input
43
1 3
2 4
40
5 9
5 12
0
Output
13 1
failed
I. Teleportia
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

You have moved to a city called teleportia and you are looking for a job.

This city has a network of streets such that every two streets are either parallel or perpendicular and the distance between every two consecutive parallel streets is 1 meter. So you can consider the network of streets as an infinite 2D grid. The scientists in this city invented an advanced teleportation system , it consists of a set of teleportation stations, each station is located on an intersection of two streets the teleportation stations work as follows :

Each teleportation station Si has a power Pi. We define targets of a teleportation station A with power PA as : all the teleportation stations which are inside or on the border of a circle centered at A with a radius of PA.

Once you enter a teleportation station you'll have to wait for 2 seconds until you are teleported to one of its target teleportation stations.

The government is planning to develop a system that finds the minimum time required to go from a starting point Xs, Ys to an ending point Xe, Ye considering an average person walks with a speed of 1 meter per second. since you are a programmer who is looking for a job , can you implement this system ?

Input

The input starts with T the number of test Cases.

Each test case starts with a number n (0 ≤ n ≤ 100), the number of teleportation stations.

Then n lines follow each describing a teleportation station Si. A teleportation station description consists of three integers Xi, Yi, Pi : the 2D coordinates of the teleportation station , and its power. The next line contains four integers: Xs, Ys, Xe, Ye : the 2d coordinates of a starting point and an ending point.

 - 109 ≤ Xi, Yi, Xs, Ys, Xe, Ye ≤ 109

0 ≤ Pi ≤ 109

Output

for each test case you have to print the minimum time required to move from the starting point to the ending point

Examples
Input
1
3
5 5 5
9 5 3
11 7 2
4 6 11 8
Output
7
J. palprime
time limit per test
4 seconds
memory limit per test
24 megabytes
input
standard input
output
standard output

A palindromic prime (sometimes called a palprime) is a prime number that is also a palindromic number. Palindromicity depends on the base of the numbering system and its writing conventions, while primality is independent of such concerns.

The sequence of binary palindromic primes begins(in binary):

11, 101, 111, 10001, 11111, 1001001 You are given a number b (in binary), you should output the first palprime greater than or equal to b.

Input

The input consists of multiple test cases, each test case consists of a number b in binary.

We guarantee b will be no Longer than 21 bits

Output

The first palprime greater than or equal to b

Examples
Input
10
100
110
1000
Output
11
101
111
10001