AAROHAN

2010

OVERNITE MAINS

PROBLEM :1

There are 3 kinds of money in a planet far away from the earth: Mone, Luck, and Rpin.

There's a money exchange company in this planet. You must go to this company if you want

to do some money exchange, and, more autocratically, this company regulate the exchange

rate of each pair of these 3 kinds of money.

The money exchange will be done in the following two ways:

(A)

You give the company a real number x in the range (0,100], the company will exchange x%

of your Mone and x% of your Luck to equal Rpin according to the exchange rate of that day.

(B)

You give the company a real number x, the company will exchange your x Rpin to some

Mone and Luck, whose value is equal to x Rpin according to the exchange rate of that day,

and, the value of Mone is Rate times of the value of Luck.

You can do many exchange operations in the same day.

Now, as the excellant spy in this planet, you know the exchange rate between Mone and

Rpin of each of the next n days(ai Mone per Rpin), and the exchange rate between Luck and

Rpin of each of the next n days(bi Luck per Rpin), and, each Rate of the next n days( Ratei).

you have S Rpin in the start, and you want to get most Rpin in the nth day later.

Input: Multiple test cases, the number of them( <=5 ) is given in the very first line.

For each test case:

The first line contains a integer number n(1<=n<=100000) and a real number S.n lines

follow, each contains 3 real numbers: ai(between 0 and 10), bi(between 0 and 10),

Ratei(between 0 and 100).

Output:For each test case, output one line contains a real number with 3 digits after

decimal point, which denotes to the answer. You can assume it is less than 1000000000.

Example

Input:

1

3 100

1 1 1

1 2 2

2 2 3

Output:

225.000

PROBLEM 2. ALL DIFFERENT

Input:

1. Enter the size of grid.

2. Enter the number of coins.

Output:

Find the distance between the coins and it must be different and efficient

Problem 3

Create a program that takes in a wordsearch board, and list of words and finds the

location of all the words hidden.

Input:

Input consists of 50 lines of 50 characters each (all uppercase), this is the game board.

Following it, untill the end of file is the list of words that are hidden in the board.

Output:

Output consists of you printing the board back out to the screen, with all the characters

that were not part of a hidden word removed and replaced with a space.

ex. input:

Quote

word: "the"

board:

TJK

BHQ

ERE

ex. output

T

H

E

PROBLEM :4

N large empty boxes (assume they are of type:1) are initially placed on a table. An

unknown number of boxes (type:1) are selected and in each of them K smaller boxes

(type:2) are placed. Again an unknown number of type:2 boxes are selected and K boxes of

type:3 are placed inside. This process is repeated T times. Now a box is assumed to be

empty when it has no smaller boxes inside it. Finally after all the processes are complete let

there be Fempty boxes in total.

LIMITS

1< N,K,T,F <1000000

Input

First line of the input file contains the number of test cases. Then each line contains 4

integers N,K,T,F as described above.

Output

Each line should contain the total number of boxes on the table.

Example

Input:

1

11 8 2 102

Output:

115

Problem 5

The Sarcophagus itself is locked by a secret numerical code. When somebody wants to open

it, he must know the code and set it exactly on the top of the Sarcophagus. A very intricate

mechanism then opens the cover. If an incorrect code is entered, the tickets inside would

catch fire immediately and they would have been lost forever. The code (consisting of up to

100 integers) was hidden in the Alexandrian Library but unfortunately, as you probably

know, the library burned down completely.

But an almost unknown archaeologist has obtained a copy of the code something during the

18th century. He was afraid that the code could get to the wrong people'' so he has encoded

the numbers in a very special way. He took a random complex number B that was greater

(in absolute value) than any of the encoded numbers. Then he counted the numbers as the

digits of the system with basis B. That means the sequence of numbers an, an-1,

...,a1, a0 was encoded as the number X = a0 + a1B + a2B2 + ...+ anBn.

Your goal is to decrypt the secret code, i.e. to express a given number X in the number

system to the base B. In other words, given the numbers X and Byou are to determine

thedigit'' a0 through an.

Input

The input consists of T test cases (equal to about 100000). The number of them (T) is given

on the first line of the input file. Each test case consists of one single line containing four

integer numbers Xr, Xi, Br, Bi (|Xr|,|Xi| <= 1000000, |Br|,|Bi| <= 16). These numbers

indicate the real and complex components of numbers X and B, i.e. X = Xr + i.Xi, B = Br +

i.Bi. B is the basis of the system (|B| > 1), X is the number you have to express.

Output

Your program must output a single line for each test case. The line should contain

the digits''an, an-1, ..., a1, a0, separated by commas. The following conditions must be

satisfied:

• for all i in {0, 1, 2, ...n}: 0 <= ai < |B|

• X = a0 + a1B + a2B2 + ...+ anBn

• if n > 0 then an <> 0

• n <= 100

If there are no numbers meeting these criteria, output the sentence "The code cannot be

decrypted.". If there are more possibilities, print any of them.

Example

Sample Input

4

-935 2475 -11 -15

1 0 -3 -2

93 16 3 2

191 -192 11 -12

Sample output:

8,11,18

1

The code cannot be decrypted.

16,15

Problem 6

You are given a list of cities. Each direct connection between two cities has its

transportation cost (an integer bigger than 0). The goal is to find the paths of minimum cost

between pairs of cities. Assume that the cost of each path (which is the sum of costs of all

direct connections belongning to this path) is at most 200000. The name of a city is a string

containing characters a,...,z and is at most 10 characters long.

Input

s [the number of tests <= 10]

n [the number of cities <= 10000]

NAME [city name]

p [the number of neighbours of city NAME]

nr cost [nr - index of a city connected to NAME (the index of the first city

is 1)]

[cost - the transportation cost]

r [the number of paths to find <= 100]

NAME1 NAME2 [NAME1 - source, NAME2 - destination]

[empty line separating the tests]

Output

cost [the minimum transportation cost from city NAME1 to city NAME2 (one per

line)]

Example

Input:

1

4

gdansk

2

2 1

3 3

bydgoszcz

3

1 1

3 1

4 4

torun

3

1 3

2 1

4 1

warszawa

2

2 4

3 1

2

gdansk warszawa

bydgoszcz warszawa

Output:

3

2

Problem 7

On a rectangular mesh comprising n*m fields, n*m cuboids were put, one cuboid on each

field. A base of each cuboid covers one field and its surface equals to one square inch.

Cuboids on adjacent fields adhere one to another so close that there are no gaps between

them. A heavy rain pelted on a construction so that in some areas puddles of water

appeared.

Task

Write a program which:

• reads from the standard input a size of the chessboard and heights of cuboids put on

the fields,

• computes maximal water volume, which may gather in puddles after the rain,

• writes results in the standard output.

Input

The number of test cases t is in the first line of input, then t test cases follow separated by

an empty line. In the first line of each test case two positive integers 1 <= n <= 100, 1

<=m <= 100 are written. They are the size of the mesh. In each of the following n lines

there are m integers from the interval [1..10000]; i-th number in j-th line denotes a height

of a cuboid given in inches put on the field in the i-th column and j-th raw of the

chessboard.

Output

Your program should write for each tes case one integer equal to the maximal volume of

water (given in cubic inches), which may gather in puddles on the construction.

Example

Sample input:

1

3 6

3 3 4 4 4 2

3 1 3 2 1 4

7 3 1 6 4 1

Sample output:

5

The picture below shows the mesh after the rain (seen from above). Puddles are drawn in

gray.