Description

Lindsay is a shopaholic. Whenever there is a discount of the kind where you can buy three items and only pay for two, she goes completely mad and feels a need to buy all items in the store. You have given up on curing her for this disease, but try to limit its effect on her wallet.

You have realized that the stores coming with these offers are quite selective when it comes to which items you get for free; it is always the cheapest ones. As an example, when your friend comes to the counter with seven items, costing 400, 350, 300, 250, 200, 150, and 100 dollars, she will have to pay 1500 dollars. In this case she got a discount of 250 dollars. You realize that if she goes to the counter three times, she might get a bigger discount. E.g. if she goes with the items that costs 400, 300 and 250, she will get a discount of 250 the first round. The next round she brings the item that costs 150 giving no extra discount, but the third round she takes the last items that costs 350, 200 and 100 giving a discount of an additional 100 dollars, adding up to a total discount of 350.

Your job is to find the maximum discount Lindsay can get.

Input

The first line of input gives the number of test scenarios, 1 ≤ t ≤ 20. Each scenario consists of two lines of input. The first gives the number of items Lindsay is buying, 1 ≤ n ≤ 20000. The next line gives the prices of these items, 1 ≤ p_i ≤ 20000.

Output

For each scenario, output one line giving the maximum discount Lindsay can get by selectively choosing which items she brings to the counter at the same time.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We can describe detailed direction by repeating the directional names: north, south, east and west. For example, northwest is the direction halfway between north and west, and northnorthwest is between north and northwest.

In this problem, we describe more detailed direction between north and west as follows.

• "north" means 0 degrees.
• "west" means 90 degrees.
• If the direction dir means a degrees and the sum of the occurrences of "north" and "west" in dir is n (≥ 1), "north"dir (the concatenation of "north" and dir) means a − 90 / 2ⁿ degrees and "west"dir means a + 90 / 2ⁿ degrees.

Your task is to calculate the angle in degrees described by the given direction.

Input

The input contains several datasets. The number of datasets does not exceed 100.

Each dataset is described by a single line that contains a string denoting a direction. You may assume the given string can be obtained by concatenating some "north" and "west", the sum of the occurrences of "north" and "west" in the given string is between 1 and 20, inclusive, and the angle denoted by the given direction is between 0 and 90, inclusive. The final dataset is followed by a single line containing only a single "#".

Output

For each dataset, print an integer if the angle described by the given direction can be represented as an integer, otherwise print it as an irreducible fraction. Follow the format of the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.

Input

The input consists of multiple data sets. A data set starts with a line containing two positive integers w and h; w and h are the numbers of tiles in the x- and y- directions, respectively. w and h are not more than 20.

There are h more lines in the data set, each of which includes w characters. Each character represents the color of a tile as follows.

. - a black tile
# - a red tile
@ - a man on a black tile (appears exactly once in a data set)

The end of the input is indicated by a line consisting of two zeros.

Output

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Playfair cipher is a manual symmetric encryption technique and was the first digraph substitution cipher. The scheme was invented in 1854 by Charles Wheatstone, but bears the name of Lord Playfair who promoted the use of the cipher.

The Playfair cipher uses a 5 by 5 table containing each letter in the English alphabet exactly once (except 'Q' which is missing). The table constitutes the encryption key. To more easily remember the table, it is typically generated from a key phrase. First fill in the spaces in an empty table with the letters of the key phrase (dropping spaces and duplicate letters), then fill the remaining spaces with the rest of the letters of the alphabet in order. The key phrase is written in the top rows of the table, from left to right. For instance, if the key phrase is "playfair example", the encryption key becomes

P L A Y F
I R E X M
B C D G H
J K N O S
T U V W Z

To encrypt a message, one would remove all spaces and then break the message into digraphs (groups of 2 letters) such that, for example, "Hello World" becomes "HE LL OW OR LD". Then map them out on the key table, and apply the rule below that matches the letter combination:

• If both letters are the same (or only one letter is left), add an 'X' after the first letter. Encrypt the new pair and continue (note that this changes all the remaining digraphs).
• If the letters appear on the same row of your table, replace them with the letters to their immediate right respectively (wrapping around to the left side of the row if a letter in the original pair was on the right side of the row). With the table above, the digraph 'CH' would be encrypted 'DB'.
• If the letters appear on the same column of your table, replace them with the letters immediately below respectively (wrapping around to the top side of the column if a letter in the original pair was on the bottom side of the column). With the table above, the digraph 'VA' would be encrypted 'AE'.
• If the letters are not on the same row or column, replace them with the letters on the same row respectively but at the other pair of corners of the rectangle defined by the original pair. The order is important -- the first letter of the encrypted pair is the one that lies on the same row as the first letter of the plaintext pair. With the table above, the digraph 'KM' would be encrypted 'SR'.

Write a program that reads a key phrase and a plaintext to encrypt, and outputs the encrypted text.

The text to encrypt will not contain two 'x's following each other, or an 'x' as the last character, as this might cause the first rule above to repeat itself indefinitely.

Input

The first line of the input file contains an integer n (n ≤ 25) which denotes the total number of test cases. The description of each test case is given below:

The input for each test case is given in two lines. The first line contains the key phrase. The second line contains the text to encrypt. Each line will contain between 1 and 1000 characters, inclusive. Each character will be a lower case English letter, 'a' - 'z' (except 'q'), or a space character. Neither line will start or end with a space.

Output

For each test case the output should be a single line containing the encrypted text, in upper case. There should be no spaces in the output. Look at the output for sample input for details.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

International Center for Picassonian Cubism is a Spanish national museum of cubist artworks, dedicated to Pablo Picasso. The center held a competition for an artwork that will be displayed in front of the facade of the museum building. The artwork is a collection of cubes that are piled up on the ground and is intended to amuse visitors, who will be curious how the shape of the collection of cubes changes when it is seen from the front and the sides.

The artwork is a collection of cubes with edges of one foot long and is built on a flat ground that is divided into a grid of one foot by one foot squares. Due to some technical reasons, cubes of the artwork must be either put on the ground, fitting into a unit square in the grid, or put on another cube in the way that the bottom face of the upper cube exactly meets the top face of the lower cube. No other way of putting cubes is possible.

You are a member of the judging committee responsible for selecting one out of a plenty of artwork proposals submitted to the competition. The decision is made primarily based on artistic quality but the cost for installing the artwork is another important factor. Your task is to investigate the installation cost for each proposal. The cost is proportional to the number of cubes, so you have to figure out the minimum number of cubes needed for installation.

Each design proposal of an artwork consists of the front view and the side view (the view seen from the right-hand side), as shown in Figure 1.

Figure 1. An example of an artwork proposal

The front view (resp., the side view) indicates the maximum heights of piles of cubes for each column line (resp., row line) of the grid.

There are several ways to install this proposal of artwork, such as the following figures.

In these figures, the dotted lines on the ground indicate the grid lines. The left figure makes use of 16 cubes, which is not optimal. That is, the artwork can be installed with a fewer number of cubes. Actually, the right one is optimal and only uses 13 cubes. Note that, a single pile of height three in the right figure plays the roles of two such piles in the left one.

Notice that swapping columns of cubes does not change the side view. Similarly, swapping rows does not change the front view. Thus, such swaps do not change the costs of building the artworks. For example, consider the artwork proposal given in Figure 2.

Figure 2. Another example of artwork proposal

An optimal installation of this proposal of artwork can be achieved with 13 cubes, as shown in the following figure, which can be obtained by exchanging the rightmost two columns of the optimal installation of the artwork of Figure 1.

Input

The input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space. Each dataset is formatted as follows.

w d
h₁ h₂ … h_w
h'₁ h'₂ … h'_d

The integers w and d separated by a space are the numbers of columns and rows of the grid, respectively. You may assume 1 ≤ w ≤ 10 and 1 ≤ d ≤ 10. The integers separated by a space in the second and third lines specify the shape of the artwork. The integers h_i (1 ≤ h_i ≤ 20, 1 ≤ i ≤ w) in the second line give the front view, i.e., the maximum heights of cubes per each column line, ordered from left to right (seen from the front). The integers h'_i (1 ≤ h'_i ≤ 20, 1 ≤ i ≤ d) in the third line give the side view, i.e., the maximum heights of cubes per each row line, ordered from left to right (seen from the right-hand side).

Output

For each dataset, output a line containing the minimum number of cubes. The output should not contain any other extra characters.

You can assume that, for each dataset, there is at least one way to install the artwork.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The king in Utopia has died without an heir. Now several nobles in the country claim the throne. The country law states that if the ruler has no heir, the person who is most related to the founder of the country should rule.

To determine who is most related we measure the amount of blood in the veins of a claimant that comes from the founder. A person gets half the blood from the father and the other half from the mother. A child to the founder would have 1/2 royal blood, that child's child with another parent who is not of royal lineage would have 1/4 royal blood, and so on. The person with most blood from the founder is the one most related.

Input

The input file contains several test cases, each of them as described below.

The first line contains two integers, n (2 ≤ n ≤ 50) and m (2 ≤ m ≤ 50).

The second line contains the name of the founder of Utopia.

Then follows n lines describing a family relation. Each such line contains three names, separated with a single space. The first name is a child and the remaining two names are the parents of the child.

Then follows m lines containing the names of those who claim the throne.

All names in the input will be between 1 and 10 characters long and only contain the lowercase English letters 'a' - 'z'. The founder will not appear among the claimants, nor be described as a child to someone else.

The family relations may not be realistic when considering sex, age etc. However, every child will have two unique parents and no one will be a descendent from themselves. No one will be listed as a child twice.

Output

Output a single line containing the name of the claimant with most blood from the founder. The input will be constructed so that the answer is unique.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Animal School is a primary school for animal children. You are a fox attending this school.

One day, you are given a problem called "Arithmetical Restorations" from the rabbit teacher, Hanako. Arithmetical Restorations are the problems like the following:

• You are given three positive integers, A, B and C.
• Several digits in these numbers have been erased.
• You should assign a digit in each blank position so that the numbers satisfy the formula A + B = C.
• The first digit of each number must not be zero. It is also the same for single-digit numbers.

You are clever in mathematics, so you immediately solved this problem. Furthermore, you decided to think of a more difficult problem, to calculate the number of possible assignments to the given Arithmetical Restorations problem. If you can solve this difficult problem, you will get a good grade.

Shortly after beginning the new task, you noticed that there may be too many possible assignments to enumerate by hand. So, being the best programmer in the school as well, you are now trying to write a program to count the number of possible assignments to Arithmetical Restoration problems.

Input

The input is a sequence of datasets. The number of datasets is less than 100. Each dataset is formatted as follows.

A
B
C

Each dataset consists of three strings, A, B and C. They indicate that the sum of A and B should be C. Each string consists of digits ('0' – '9') and/or question mark ('?'). A question mark ('?') indicates an erased digit. You may assume that the first character of each string is not '0' and each dataset has at least one '?'.

It is guaranteed that each string contains between 1 and 50 characters, inclusive. You can also assume that the lengths of three strings are equal.

The end of input is indicated by a line with a single zero.

Output

For each dataset, output the number of possible assignments to the given problem modulo 10⁹ + 7. Note that there may be no way to solve the given problems because Ms. Hanako is a careless rabbit.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

We're building an old-school back-to-basics computer game. It's a very simple text based adventure game where you walk around and try to find treasure, avoiding falling into traps. The game is played on a rectangular grid and the player gets very limited information about her surroundings.

The game will consist of the player moving around on the grid for as long as she likes (or until she falls into a trap). The player can move up, down, left and right (but not diagonally). She will pick up gold if she walks into the same square as the gold is. If the player stands next to (i.e., immediately up, down, left, or right of) one or more traps, she will "sense a draft'' but will not know from what direction the draft comes, or how many traps she's near. If she tries to walk into a square containing a wall, she will notice that there is a wall in that direction and remain in the position where she was.

For scoring purposes, we want to show the player how much gold she could have gotten safely. That is, how much gold can a player get playing with an optimal strategy and always being sure that the square she walked into was safe. The player does not have access to the map and the maps are randomly generated for each game so she has no previous knowledge of the game.

Input

The input file contains several test cases, each of them as described below.

The first line of input contains two positive integers w and h, neither of them smaller than 3 or larger than 50, giving the width and the height of the map, respectively. The next h lines contain w characters each, giving the map. The symbols that may occur in a map are as follows:

P - the player's starting position
G - a piece of gold
T - a trap
# - a wall
. - normal floor

There will be exactly one 'P' in the map, and the border of the map will always contain walls.

Output

For each test case, write to the output the number of pieces of gold the player can get without risking falling into a trap, on a line by itself.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A bee larva living in a hexagonal cell of a large honeycomb decides to creep for a walk. In each "step" the larva may move into any of the six adjacent cells and after n steps, it is to end up in its original cell.

Your program has to compute, for a given n, the number of different such larva walks.

Input

The first line contains an integer giving the number of test cases to follow. Each case consists of one line containing an integer n, where 1 ≤ n ≤ 14.

Output

For each test case, output one line containing the number of walks. Under the assumption 1 ≤ n ≤ 14, the answer will be less than 2³¹.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an undirected weighted graph G, you should find one of spanning trees specified as follows.

The graph G is an ordered pair (V, E), where V is a set of vertices {v₁, v₂, ... , v_n} and E is a set of undirected edges {e₁, e₂, …, e_m}. Each edge e ∈ E has its weight w(e).

A spanning tree T is a tree (a connected subgraph without cycles) which connects all the n vertices with n − 1 edges. The slimness of a spanning tree T is defined as the difference between the largest weight and the smallest weight among the n − 1 edges of T.

Figure 3. A graph G and the weights of the edges

For example, a graph G in Figure 3(a) has four vertices {v₁, v₂, v₃, v₄} and five undirected edges {e₁, e₂, e₃, e₄, e₅}. The weights of the edges are w(e₁) = 3, w(e₂) = 5, w(e₃) = 6, w(e₄) = 6, w(e₅) = 7 as shown in Figure 3(b).

Figure 4. Examples of the spanning trees of G

There are several spanning trees for G. Four of them are depicted in Figure 4(a)-(d). The spanning tree T_a in Figure 4(a) has three edges whose weights are 3, 6 and 7. The largest weight is 7 and the smallest weight is 3 so that the slimness of the tree T_a is 4. The slimnesses of spanning trees T_b, T_c and T_d shown in Figure 4(b), (c) and (d) are 3, 2 and 1, respectively. You can easily see the slimness of any other spanning tree is greater than or equal to 1, thus the spanning tree T_d in Figure 4(d) is one of the slimmest spanning trees whose slimness is 1.

Your job is to write a program that computes the smallest slimness.

Input

The input consists of multiple datasets, followed by a line containing two zeros separated by a space. Each dataset has the following format.

n m
a₁ b₁ w₁
.
.
.
a_m b_m w_m

Every input item in a dataset is a non-negative integer. Items in a line are separated by a space.

n is the number of the vertices and m the number of the edges. You can assume 2 ≤ n ≤ 100 and 0 ≤ m ≤ n(n − 1)/2. a_k and b_k (k = 1, …, m) are positive integers less than or equal to n, which represent the two vertices v_ak and v_bk connected by the k^th edge e_k. w_k is a positive integer less than or equal to 10000, which indicates the weight of e_k. You can assume that the graph G = (V, E) is simple, that is, there are no self-loops (that connect the same vertex) nor parallel edges (that are two or more edges whose both ends are the same two vertices).

Output

For each dataset, if the graph has spanning trees, the smallest slimness among them should be printed. Otherwise, -1 should be printed. An output should not contain extra characters.

Sample Input  Download

Sample Output  Download

Tags

Discuss