Description

A supermarket in Tehran is open 24 hours a day every day and needs a number of cashiers to fit its need. The supermarket manager has hired you to help him, solve his problem. The problem is that the supermarket needs different number of cashiers at different times of each day (for example, a few cashiers after midnight, and many in the afternoon) to provide good service to its customers, and he wants to hire the least number of cashiers for this job.

The manager has provided you with the least number of cashiers needed for every one-hour slot of the day. This data is given as R(0), R(1), ..., R(23): R(0) represents the least number of cashiers needed from midnight to 1:00 A.M., R(1) shows this number for duration of 1:00 A.M. to 2:00 A.M., and so on. Note that these numbers are the same every day. There are N qualified applicants for this job. Each applicant i works non-stop once each 24 hours in a shift of exactly 8 hours starting from a specified hour, say ti (0 <= ti <= 23), exactly from the start of the hour mentioned. That is, if the ith applicant is hired, he/she will work starting from ti o'clock sharp for 8 hours. Cashiers do not replace one another and work exactly as scheduled, and there are enough cash registers and counters for those who are hired.

You are to write a program to read the R(i) 's for i=0..23 and ti 's for i=1..N that are all, non-negative integer numbers and compute the least number of cashiers needed to be employed to meet the mentioned constraints. Note that there can be more cashiers than the least number needed for a specific slot.

Input

The first line of input is the number of test cases for this problem (at most 20). Each test case starts with 24 integer numbers representing the R(0), R(1), ..., R(23) in one line (R(i) can be at most 1000). Then there is N, number of applicants in another line (0 <= N <= 1000), after which come N lines each containing one ti (0 <= ti <= 23). There are no blank lines between test cases.

Output

For each test case, the output should be written in one line, which is the least number of cashiers needed.
If there is no solution for the test case, you should write No Solution for that case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Somewhere in the world, there are two tribes separated by mountains. The two tribes are named Kulolo and Gulolo, respectively, where Kulolo is at a higher altitude and Gulolo is at a lower altitude. Due to the limitation of geography, Gulolo has fewer resources than Kulolo. In order to transport resources from Kulolo to Gulolo efficiently, several tunnels were built inside the mountains between these two tribes. There are also some rest stations built for people to take a break during the transportation in the tunnels. More specifically, each terminal of a tunnel is either Kulolo, Gulolo, or a rest station.

The structure of those tunnels is not stable. A dangerous degree has been estimated for each tunnel, due to its stability, in advance. A tunnel with a higher dangerous degree is considered to be more dangerous; that is, it is more probably to collapse. Kinglolo, the chief of Kulolo, would like to select some paths through the tunnels to Gulolo with little risk. In Kinglolo's opinion, the dangerous degree of a path is equal to the maximum dangerous degree of the tunnels in the path; and the dangerous degree of a set of paths is equal to the maximum dangerous degree of the paths in it. For example, consider Figure 1. The dangerous degrees of P₁, P₂ , and P₃ are, respectively, 3, 5, and 6. And, the dangerous degree of {P₂, P₃} is 6.

Since all tunnels are narrow, a limited quantity of resources can be transported along a path in one day. Therefore, every day, depending on the amount of resources needed to be transported, a different number, say k, of paths is required. Moreover, to avoid congestion, these k selected paths cannot pass any rest station in common. For example, in Figure 1, P₂ and P₃

Figure 1: An example.

can be selected at the same time; however, P₁ and P₂ cannot be selected at the same time, since they both pass r₂ . Kulolo has a higher altitude than all rest stations while Gulolo has a lower altitude than all rest stations. Kinglolo is a thoughtful chief. It is ensured that the altitudes of the rest stations on each selected path are non-increasing, so that the path is more suitable for transportation. For example, in Figure 1, the path (Kulolo, r₃ , r₁ , Gulolo) will never be selected, since r₁ is higher than r₃ .

People in Kulolo believe that Kinglolo is the most brilliant man in the world, since he always selects a set of k paths that is as little dangerous as possible (i.e., the maximum dangerous degree of the selected paths is minimized). Now, given the data of the constructed tunnels, you are asked to find k paths that Kinglolo may select. In summary, the k selected paths, if exist, should satisfy the following:

1. all paths are from Kulolo to Gulolo,
2. no two paths pass the same rest station,
3. the altitudes of the rest stations on each path are non-increasing, and
4. the maximum dangerous degree of the paths is minimized.

For simplicity, only the maximum dangerous degree of the selected paths should be reported.

Input

The input consists of multiple test cases. The first line of each case contains a positive integer n (0 < n ≤ 200) which indicates that there are n rest stations r₁, r₂,..., r_n . For ease of description, Kulolo and Gulolo are denoted by r₀ and r_n+1 , respectively. We assume that r_i is higher than r_j for any 0 ≤ i < j ≤ n + 1 . The second line of each case contains a positive integer t (t > 0) that specifies the number of tunnels. Each of the following t lines contains three integers p, q, d (0 ≤ p ≤ n + 1, 0 ≤ q ≤ n + 1, p ≠ q, 1 ≤ d ≤ 100000) separated by white space, which indicate there is a tunnel with dangerous degree d connecting r_p and r_q . Then, a line containing a positive integer k (1 ≤ k ≤ 10) is provided, which is the number of paths that should be selected. You can assume that there is at most one tunnel between any two rest stations. The last test case is followed by a line containing a zero.

Output

For each test case, print a line containing the test case number (beginning with 1) followed by the maximum dangerous degree of the k paths that Kinglolo may select. If the solution does not exist, print ``no solution". Use the format of the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are going on a long trip. Initially, you stay at hotel 0. Along the way, there are n hotels. The only place you are allowed to stop are at these hotels. The distance from hotel i - 1 to hotel i is ai . You can choose which of the hotels you stop at. You must stop at the final hotel, which is your destination.

You would ideally like to travel 100 kilometers a day. However, this may not be possible. It depends on the spacing of the hotels. There is no limit on the distance you traveled in a day. If you travel x kilometers during a day, the penalty for that day is (x - 100)² . You want to plan your trip so as to minimize the total penalty -- that is, the sum, over all travel days, of the daily penalty. Write a program to determine the optimal sequence of hotels at which to stop.

Input

The input file contains a set of test data. Each test data consists of two parts. The first part is the number of hotels n . The second part is a sequence of n integers a1, a2,..., an . Each ai is the distance between hotel i - 1 and hotel i . Assume that 0 < ai < 200 . They may be written in many lines. Assume that n < 1000 , and n = 0 signals the end of the test data.

Output

The first line of the output is the minimum penalty p . The second line of the output is the indexes of the hotels to stop at. If the solution is not unique, print the one with fewer stops. If there are more then one solutions with the same number of stops, print the one which is the lexicographically smallest one. For example (1 2 4) < (1 3 4) . Print 30 stops in each line, except the last line which may contain less stops. Print a blank line between datasets.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Sometimes, if you are searching for ladybugs, all you find are tree fleas. An old tree near the anthill serves as a home of two fleas who sometimes steal honeydew from aphids living on the tree. On the old tree, branches connect the forks (spaces where two or more branches meet) and leaves where the fleas can rest. Fleas are so small that the ants cannot see them and thus fleas are safe. Because of their size, the fleas satiate their appetite pretty quickly and then have a lot of energy to jump. They decide to jump toward each other complying with the following rules:

There is exactly one way for the fleas to go from one leaf or fork in the tree to another leaf or fork without ever turning back. Each of the fleas starts jumping along such a route to the current location of the other flea.
The fleas can only jump from one fork or leaf of the tree to another fork or leaf if they are connected by a branch.
If the two fleas land at the same time in the same place then they decide to sit and chat for quite a while.
If the two fleas land at the same time in two neighboring places on the tree (forks or leaves) then they keep jumping forever.
The input file contains multiple test cases. Each test case starts with an integer n, the number of leaves and forks in the tree, 1≤n≤5000. We assume that leaves and forks are numbered from 1 to n. Each of the following n-1 lines describe tree branches; each branch is described by two integers a and b, meaning that the branch connects the fork or leaf labeled a and the fork or leaf labeled b. In the (n+1)-st line there is one integer l, 1≤l≤500, saying how many starting positions of the fleas you are to consider for the tree. Each of the following l lines contains two positive integers (not greater than n). These numbers define the tree places in which the fleas start their jumping. Input is terminated by the case with n equal to 0.
Your program should output l lines for each test case. The i-th line for a case should look like

The fleas meet at p.

where p identifies the place where the fleas meet, or

The fleas jump forever between p and r.

where p and r are two neighboring places on the tree with p ≤ r

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

“How am I ever going to solve this problem?” said the pilot.

Indeed, the pilot was not facing an easy task. She had to drop packages at specific points scattered in a dangerous area. Furthermore, the pilot could only fly over the area once in a straight line, and she had to fly over as many points as possible. All points were given by means of integer coordinates in a two-dimensional space. The pilot wanted to know the largest number of points from the given set that all lie on one line. Can you write a program that calculates this number?

Your program has to be efficient!

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The input consists of N pairs of integers, where 1 < N < 700. Each pair of integers is separated by one blank and ended by a new-line character. The list of pairs is ended with an end-of-file character. No pair will occur twice.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
The output consists of one integer representing the largest number of points that all lie on one line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Erin is an engineer. She drives trains. She also arranges the cars within each train. She prefers to put the cars in decreasing order of weight, with the heaviest car at the front of the train.

Unfortunately, sorting train cars is not easy. One cannot simply pick up a car and place it somewhere else. It is impractical to insert a car within an existing train. A car may only be added to the beginning and end of the train.

Cars arrive at the train station in a predetermined order. When each car arrives, Erin can add it to the beginning or end of her train, or refuse to add it at all. The resulting train should be as long as possible, but the cars within it must be ordered by weight.

Given the weights of the cars in the order in which they arrive, what is the longest train that Erin can make?

Input

The first line is the number of test cases to follow. The test cases follow, one after another; the format of each test case is the following:

The first line contains an integer 0 <= n <= 2000, the number of cars. Each of the following n lines contains a non-negative integer giving the weight of a car. No two cars have the same weight.

Output

Output a single integer giving the number of cars in the longest train that can be made with the given restrictions.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Institute of Bioinformatics and Medicine (IBM) of your country has been studying the DNA sequences of several organisms, including the human one. Before analyzing the DNA of an organism, the investigators must extract the DNA from the cells of the organism and decode it with a process called ``sequencing''.


A technique used to decode a DNA sequence is the ``shotgun sequencing''. This technique is a method applied to decode long DNA strands by cutting randomly many copies of the same strand to generate smaller fragments, which are sequenced reading the DNA bases (A, C, G and T) with a special machine, and re-assembled together using a special algorithm to build the entire sequence.


Normally, a DNA strand has many segments that repeat two or more times over the sequence (these segments are called ``repetitions''). The repetitions are not completely identified by the shotgun method because the re-assembling process is not able to differentiate two identical fragments that are substrings of two distinct repetitions.


The scientists of the institute decoded successfully the DNA sequences of numerous bacterias from the same family, with other method of sequencing (much more expensive than the shotgun process) that avoids the problem of repetitions. The biologists wonder if it was a waste of money the application of the other method because they believe there is not any large repeated fragment in the DNA of the bacterias of the family studied.


The biologists contacted you to write a program that, given a DNA strand, finds the largest substring that is repeated two or more times in the sequence.

Input

The first line of the input contains an integer T specifying the number of test cases ( 1 <= T <= 100 ). Each test case consists of a single line of text that represents a DNA sequence S of length n ( 1 <= n <= 1000 ).


You can suppose that each sequence S only contains the letters A, C, G and T.

Output

For each sequence in the input, print a single line specifying the largest substring of S that appears two or more times repeated in S , followed by a space, and the number of ocurrences of the substring in S .


If there are two or more substrings of maximal length that are repeated, you must choose the least according to the lexicographic order.


If there is no repetition in S , print ``No repetitions found!''

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Alfred wants to plan what to cook in the next days. He can cook various dishes. For each dish the costs of the ingredients and the benefit value is known. If a dish is cooked the second time in a row, the benefit value for the second time is 50 percent of the benefit value of first time, if it is prepared for the third or higher time in a row, the benefit value is 0. For example cooking a dish with benefit value v three times in a row leads to a total benefit value of 1.5*v.
Help him to build the menu which maximizes the benefit value under the constraint that his budget is not exceeded.

Input

The input consists of several test cases. Each test case begins with 3 integers in a line: The number of days k (1<=k<=21) Alfred wants to plan for, the number of dishes n (1<=n<=50) he can cook and his budget m (0<=m<=100).
The following n lines describe the dishes Alfred can cook. The i-th line contains two integers: the costs c (1<=c<=50) and the benefit value v (1<=v<=10000) of the i-th dish.
The end of the input is signaled by a test case with k = n = m = 0. You don't need to process this test case.

Output

For each output, print the maximum benefit value reachable with 1 digit after the decimal point. Then print k integers with i-th integer being the number of the dish to cook on day i. Dishes are numbered from 1 to n. Print at least one space or new line character after each integer.
If there are several possible menus reaching the maximum benefit value, select the one with minimum costs, if there are several with minimum costs, you can print any of them.
If every menu exceeds the budget, print only the benefit value of 0.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Consider a square area with edge length N. The lower left corner is (0,0) and the upper right corner is (N,N). There is one person stand on each point (x,y). (0 <= x,y <= N) x and y are integers. Suppose you are the one at (0,0), please calculate the number of people you can see directly. For example, the edge length of the sqaure is 2. You can see (0,1),(1,0),(1,2),(2,1) and (1,1) directly.

Input

There are multiple test cases. The first line contains an integer T (T <= 100) which represents the number of test case. The next T lines, each line contains an interger N (0 < N <= 1000), which represents the length of the square.

Output

Please output the number of people for each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Consider a square area with edge length N. The lower left corner is (0, 0) and the upper right corner is (N, N). There is one person stand on each point (x, y). (0 ≤ x, y ≤ N) x and y are integers. Suppose you are the one at (0, 0), please calculate the number of people you can see directly. For example, the edge length of the sqaure is 2. You can see (0, 1), (1, 0), (1, 2), (2, 1) and (1, 1) directly.

Input

There are multiple test cases. The first line contains an integer T (T ≤ 100) which represents the number of test case. The next T lines, each line contains an interger N (0 < N ≤ 1000000), which represents the length of the square.

Output

Please output the number of people for each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You will be given a square grid of size N × N. The top-left square has a coordinate of (1, 1) and that of bottom-right is (N, N). Your job is to walk from (1, 1) to (N, N). Very easy, right? That’s why you have to follow some rules when walking.

1. You can only move left, right or down.
2. (i, j-1) is left of (i, j), (i, j+1) is right of (i, j) and (i+1, j) is down of (i, j).
   
3. You can never move outside the grid.
   
4. You can not step on a cell more than once.
   
5. Every cell has an integer associated with it.
   
6. You have to make sure the sum of integers of the path is maximized.
   
7. You can step on at most k negative integers from source to destination.
   

Input

Each case will start with two integers N and k. N ≤ 75 and k ≤ 5. Each of the next N lines will contain N integers each given in row major order. That is, the first integer of the first row is (1, 1) and the last integer of last row is (N, N). Input terminates with two zeros on a line.

Output

For every case output the case number. If it’s not possible to reach the destination meeting the above rules then output “impossible”, else print the maximum sum of integers of the path.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Our friend Victor participates as an instructor in an environmental volunteer program. His boss asked Victor to distribute N T-shirts to M volunteers, one T-shirt each volunteer, where N is multiple of six, and N>=M. There are the same number of T-shirts of each one of the six available sizes: XXL, XL, L, M , S, and XS. Victor has a little problem because only two sizes of the T-shirts suit each volunteer.


You must write a program to decide if Victor can distribute T-shirts in such a way that all volunteers get a T-shirt that suit them. If N != M, there can be some remaining T-shirts.

Input

The first line of the input contains the number of test cases. For each test case, there is a line with two numbers N and M. N is multiple of 6, 1<=N<=36, and indicates the number of T-shirts. Number M, 1<=M<=30, indicates the number of volunteers, with N>=M. Subsequently, M lines are listed where each line contains, separated by one space, the two sizes that suit each volunteer (XXL, XL, L, M , S, or XS).

Output

For each test case you are to print a line containing YES if there is, at least, one distribution where T-shirts suit all volunteers, or NO, in other case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

When participating in programming contests, you sometimes face the following problem: You know how to calcutale the output for the given input values, but your algorithm is way too slow to ever pass the time limit. However hard you try, you just can't discover the proper break-off conditions that would bring down the number of iterations to within acceptable limits.

Now if the range of input values is not too big, there is a way out of this. Let your PC rattle for half an our and produce a table of answers for all possible input values, encode this table into a program, submit it to the judge, et voila: Accepted in 0.000 seconds! (Some would argue that this is cheating, but remember: In love and programming contests everything is permitted).

Faced with this problem during one programming contest, Jimmy decided to apply such a 'technique'. But however hard he tried, he wasn't able to squeeze all his pre-calculated values into a program small enough to pass the judge. The situation looked hopeless, until he discovered the following property regarding the answers: the answers where calculated from two integers, but whenever the two input values had a common factor, the answer could be easily derived from the answer for which the input values were divided by that factor. To put it in other words:

Say Jimmy had to calculate a function Answer(x, y) where x and y are both integers in the range [1, N].  When he knows Answer(x, y), he can easily derive Answer(k*x, k*y), where k is any integer from it by applying some simple calculations involving Answer(x, y) and k. For example if N=4, he only needs to know the answers for 11 out of the 16 possible input value combinations: Answer(1, 1), Answer(1, 2), Answer(2, 1), Answer(1, 3), Answer(2, 3), Answer(3, 2), Answer(3, 1), Answer(1, 4), Answer(3, 4), Answer(4, 3) and Answer(4, 1). The other 5 can be derived from them (Answer(2, 2), Answer(3, 3) and Answer(4, 4) from Answer(1, 1), Answer(2, 4) from Answer(1, 2), and Answer(4, 2) from Answer(2, 1)). Note that the function Answer is not symmetric, so Answer(3, 2) can not be derived from Answer(2, 3).

Now what we want you to do is: for any values of N from 1 upto and including 50000, give the number of function Jimmy has to pre-calculate.

Input

The input file contains at most 600 lines of inputs. Each line contains an integer less than 50001 which indicates the value of N. Input is terminated by a line which contains a zero. This line should not be processed.

Output

For each line of input produce one line of output. This line contains an integer  which indicates how many values Jimmy has to pre-calculate for a certain value of N.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Uncle Magnus has planted some young saplings on his farm as part of his reforestation project. Unfortunately, deer like to eat tender sapling shoots and leaves, making it necessary to build protective fences around them. Since deer and other sapling nibblers can reach partway over the fence, every fence must lie at least a minimum distance (a margin) from each sapling.

Deer-proof fencing is quite expensive, so Uncle Magnus wants to minimize the total length of fencing used. Your job is to write a program that computes the minimum length of fencing that is required to enclose and protect the saplings. Fences may include both straight and curved segments. You may design a single fence that encloses all saplings or multiple fences that enclose separate groups of saplings.

Figure 6 shows two example configurations, each consisting of three saplings with different margin requirements. In the top configuration, which corresponds to the first sample input, the minimum-length solution consists of two separate fences. In the bottom configuration, which corresponds to the second sample input, the minimum-length solution consists of a single fence.

Input

The input consists of multiple test cases. The first line of each test case contains integers N (0 < N<=9), which is the number of saplings, and M (0 < M<=200), which is the margin required around each sapling. This line is followed by N additional lines. Each of these N lines contains two integers x and y that describe the Cartesian coordinates of a sapling ( | x|<=100 and | y|<=100). No two saplings are in the same location. For simplicity the saplings can all be considered as points and the thickness of deer-proof fences can be considered zero.

The last test case is followed by a line containing two zeros.

Output

For each test case, print the case number (starting with 1) followed by the minimum total length of fencing required to protect the saplings with the given margin. Print the length with two digits to the right of the decimal point. Follow the format of the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A war is being lead between two countries, A and B. As a loyal citizen of C, you decide to help your country’s espionage by attending the peace-talks taking place these days (incognito, of course). There are n people at the talks (not including you), but you do not know which person belongs to which country. You can see people talking to each other, and through observing their behaviour during their occasional one-to-one conversations, you can guess if they are friends or enemies. In fact what your country would need to know is whether certain pairs of people are from the same country, or they are enemies. You may receive such questions from C’s government even during the peace-talks, and you have to give replies on the basis of your observations so far. Fortunately nobody talks to you, as nobody pays attention to your humble appearance.

Abstract

Now, more formally, consider a black box with the following operations:

• setFriends(x, y): shows that x and y are from the same country

• setEnemies(x, y): shows that x and y are from different countries

• areFriends(x, y): returns true if you are sure that x and y are friends

• areEnemies(x, y): returns true if you are sure that x and y are enemies

The first two operations should signal an error if they contradict with your former knowledge. The two relations ‘friends’ (denoted by ~) and ‘enemies’ (denoted by *) have the following properties:

~ is an equivalence relation, i.e.

1. If x ~ y and y ~ z then x ~ z (The friends of my friends are my friends as well.)

2. If x ~ y then y ~ x                (Friendship is mutual.)

3. x ~ x                                   (Everyone is a friend of himself.)

* is symmetric and irreflexive

4. If x * y then y * x                (Hatred is mutual.)

5. Not x * x                             (Nobody is an enemy of himself.)

Also

6. If x * y and y * z then x ~ z  (A common enemy makes two people friends.)

7. If x ~ y and y * z then x * z  (An enemy of a friend is an enemy.)

Operations setFriends(x, y) and setEnemies(x, y) must preserve these properties.

Input

The first line contains a single integer, n, the number of people.

Each of the following lines contains a triple of integers, c x y, where c is the code of the operation:

            c = 1, setFriends

            c = 2, setEnemies

            c = 3, areFriends

            c = 4, areEnemies

and x and y are its parameters, which are integers in the range [0, n), identifying two (different) people. The last line contains 0 0 0.

All integers in the input file are separated by at least one space or line break.

Output

For every ‘areFriends’ and ‘areEnemies’ operation write 0 (meaning no) or 1 (meaning yes) to the output. Also for every ‘setFriends’ or ‘setEnemies’ operation which contradicts with previous knowledge, output a –1 to the output ; note that such an operation should produce no other effect and execution should continue. A successful ‘setFriends’ or ‘setEnemies’ gives no output.

All integers in the output file must be separated by at least one space or line break.

Constraints

n < 10000, the number of operations is unconstrained.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The ultimate Tantra is said to have been kept in the most distinguished temple deep in the sacred forest somewhere in Japan. Paleographers finally identified its location, surprisingly a small temple in Hiyoshi, after years of eager research. The temple has an underground secret room built with huge stones. This underground megalith is suspected to be where the Tantra is enshrined.

The room door is, however, securely locked. Legends tell that the key of the door lock was an integer, that only highest priests knew. As the sect that built the temple decayed down, it is impossible to know the integer now, and the Agency for Cultural Affairs bans breaking up the door. Fortunately, a figure of a number of rods that might be used as a clue to guess that secret number is engraved on the door.

Many distinguished scholars have challenged the riddle, but no one could have ever succeeded in solving it, until recently a brilliant young computer scientist finally deciphered the puzzle. Lengths of the rods are multiples of a certain unit length. He found that, to find the secret number, all the rods should be placed on a grid of the unit length to make one convex polygon. Both ends of each rod must be set on grid points. Elementary mathematics tells that the polygon's area ought to be an integer multiple of the square of the unit length. The area size of the polygon with the largest area is the secret number which is needed to unlock the door.

For example, if you have five rods whose lengths are 1, 2, 5, 5, and 5, respectively, you can make essentially only three kinds of polygons, shown in Figure 7. Then, you know that the maximum area is 19.

Figure 7: Convex polygons consisting of five rods of lengths 1, 2, 5, 5, and 5 16

Your task is to write a program to find the maximum area of convex polygons using all the given rods whose ends are on grid points.

Input

The input consists of multiple datasets, followed by a line containing a single zero which indicates the end of the input. The format of a dataset is as follows.

n 
r1    r2     ...     rn

n is an integer which means the number of rods and satisfies 3n6. ri is an integer which means the length of the i-th rod and satisfies 1<=ri<=300.

Output

For each dataset, output a line containing an integer which is the area of the largest convex polygon. When there are no possible convex polygons for a dataset, output ``-1''.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

During their honeymoon, Mrs and Mr Smith went to the Himalayas. How they were surprised when they observed that, during the sunset, all the snow touched by the sunbeams turned red.

Such a magnificent landscape leaves everyone plenty of emotion, but Mr Smith's number obsession overcame all this. He rapidly began evaluating distances, which made Mrs Smith quite upset.

Your work is to help him calculate the size, in meters, of the mountainsides that became red as the sun sets. Mr Smith's honeymoon depends on you! Please be quick and efficient.

For the sake of simplicity, consider that, during the sunset, the sunbeams are horizontal and assume that the landscape is described by the set of coordinates of the mountain peaks and cols. This can be depicted by the following figure. A landscape, in this context, is then a sequence of peaks and cols (i.e., only a col follows a peak and conversely).

Note that, in this picture, the sunny mountainsides are emphasized by bold lines and the coordinates of the landscape are emphasized by bold points.

Thus, the goal of this problem is to calculate the total length in meters of the bold lines.

For this task consider that: (1) for all coordinates (x, y), 0 <= x <= 30000 and 0 <= y <= 8848; (2) the unit is the meter; (3) all the X-coordinates are pair-wise distinct; (4) the leftmost point has 0 as X-coordinate and the rightmost point has 0 as Y-coordinate; (5) The total number of coordinates given is n <= 100.

Input

The first line of input contains C (0 < C < 100 ), the number of test cases that follows.

Each test case starts with a line containing the number N of coordinate pairs. The remaining  N lines for each test case contain the coordinates defining the landscape. Each of these lines contains two integers, x and y, separated by a single space. The first integer, x, is the X-coordinate, and the second, y, is the Y-coordinate of the considered point.

Output

The output is formed by a sequence of lines, one for each test case. Each line contains a single real number with exactly two decimal digits. This number represents the length in meters of the sunny mountainsides for the corresponding test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are constructing a triangular pyramid with a sheet of craft paper with grid lines. Its base and sides are all of triangular shape. You draw the base triangle and the three sides connected to the base on the paper, cut along the outer six edges, fold the edges of the base, and assemble them up as a pyramid.

You are given the coordinates of the base's three vertices, and are to determine the coordinates of the other three. All the vertices must have integral X- and Y-coordinate values between -100 and +100 inclusive. Your goal is to minimize the height of the pyramid satisfying these conditions. Figure 3 shows some examples.

Input

The input consists of multiple datasets, each in the following format.

X0 Y0 X1 Y1 X2 Y2

They are all integral numbers between -100 and +100 inclusive. (X0, Y0) , (X1, Y1) , (X2, Y2) are the coordinates of three vertices of the triangular base in counterclockwise order.

The end of the input is indicated by a line containing six zeros separated by a single space.

Output

For each dataset, answer a single number in a separate line. If you can choose three vertices (Xa, Ya) , (Xb, Yb) and (Xc, Yc) whose coordinates are all integral values between -100 and +100 inclusive, and triangles (X0, Y0) - (X1, Y1) - (Xa, Ya) , (X1, Y1) - (X2, Y2) - (Xb, Yb) , (X2, Y2) - (X0, Y0) - (Xc, Yc) and (X0, Y0) - (X1, Y1) - (X2, Y2) do not overlap each other (in the XY-plane), and can be assembled as a triangular pyramid of positive (non-zero) height, output the minimum height among such pyramids. Otherwise, output `-1'.

You may assume that the height is, if positive (non-zero), not less than 0.00001. The output should not contain an error greater than 0.00001.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Alex has a puzzle her father gave her last Christmas. It has nine numbered squares arranged in a 3×3 matrix (three rows and three columns) and it's mechanically designed to allow the following types of movements:

• A horizontal right move shifts one position to the right each of the squares in the corresponding horizontal row (circularly).
• A vertical up move shifts one position upwards each of the squares in the corresponding vertical column (circularly).

Alex's troublemaker little brother Jim snuck last night into his sister's bedroom and somehow tore the puzzle apart and put it back together. However, when Jim assembled the puzzle back, he might have done it in a configuration different from the original configuration of the puzzle.

The next morning, when Alex found her puzzle had been scrambled, she called you to help her to reset her puzzle to its original configuration (shown below) as quickly as possible, so her father won't realize that the puzzle was torn and scrambled. Of course, you should do it using only valid movements, as above described.

Your task is to write a program that, given a configuration, finds a way to set the puzzle to its original configuration spending the minimum possible number of moves to accomplish it, if the given puzzle is solvable. If this is not the case, the program should point it out.

Input

The problem input consists of several cases, each one defined by three lines that describe a puzzle configuration. That is, lines correspond to a top-down description of the rows of the given configuration, and each line consist of three digits, separated by one blank character.

The end of the input is indicated by a line with a number 0.

Output

For each puzzle in the input, you must print a line containing S , the minimum number of moves required to set the puzzle to its original configuration, followed by a space and 2*S characters indicating any sequence of S moves that solves the puzzle.

A move is described by two characters: the first one must be H or V (H specifies a horizontal move, and V a vertical move), and the second one must be 1, 2, or 3 to indicate the row or the column to move.

If the puzzle is not solvable, you must output a line with the text ``Not solvable''.

Hint: Consider each state as a node of the graph, transistion is an edge of graph.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

This year, there have been many problems with population calculations, since in some cities, there are many emigrants, or the population growth is very high. Every year the ACM (for Association for Counting Members) conducts a census in each region. The country is divided into N^2 regions, consisting of an N x N grid of regions. Your task is to find the least, and the greatest population in some set of regions. Since in a single year there is no significant change in the populations, the ACM modifies the population counts by some number of inhabitants.

Input

In the first line you will find N (0 <= N <= 500), in following the N lines you will be given N numbers, which represent, the initial population of city C [i, j]. In the following line is the number Q (Q <= 40000), followed by Q lines with queries: 

There are two possible queries: 

- "x1 y1 x2 y2" which represent the coordinates of the upper left and lower right of where you must calculate the maximum and minimum change in population. 

- "x y v" indicating a change of the population of city C [x, y] by value v.

Output

For each query, "x1 y1 x2 y2" print in a single line the greatest and least amount of current population. Separated each output by a space. 

Notice: There is only a single test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Let's consider a string s of length n (0 < n < 10000) containing only characters from a to z. We define a cut ci (0 < i < n) is an action splitting the string s into 2 substrings s1 and s2 so that s1 consists of first i characters of s and s2 consists of remaining characters from s. Each cut is associated with a cost which equals to the total number of characters consisted in either s1 or s2 but not in both. For example, let s = `abcbacbd', the cut c5 will break s into s1 = `abcba' and s2 = `cbd' with the cost of 2.

The original string can be cut into k + 1 substrings after applying k cuts sequentially to the string and its subsequent substrings. In order to simply describe these k cuts, we specify the position of the cuts with regard to the original string.

Let's consider an example where we sequentially apply 3 cuts at positions 5, 3 and 6 to the string s = `ababccd'. After the first cut at position 5, we have two substrings s1 = `ababc' and s2 = `cd' with the cost of 3. The second cut at position 3 breaks s1 into two substrings s11 = `aba' and s12 = `bc' with the cost of 2. The last cut at position 6 breaks s2 into two substrings s21 = `c' and s22 = `d' with the cost of 2. The total cost for the 3 cuts is 3+2+2=7. Given a string and their cuts, your task is to write a program to compute the total cost for the cut.

Input

The input consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets.

For each data set, the first line contains the integer number k (1<=k<=1000). The second line contains k positive integer numbers describing the position of k cuts. The third line contains the string which will be cut.

Output

For each test case, write in one line the total cost of the cuts.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A few kids are standing around an old tree playing a game. The tree is so huge that each kid can only see the kids close to him/her.

The game consists many ‘turns’. At the beginning of each turn of the game, a piece of paper is given to a randomly chosen kid. This kid writes the letter “B” if he is a boy or the letter “G” if a girl. Then he chooses a direction to pass the paper (clockwise or counter-clockwise), and gives the paper to his neighbor in that direction. The kid getting the paper writes down his sex too, and gives the paper to his neighbor in the same direction. In this way, the paper goes through the kids one by one, until one kid stops passing the paper and announces the end of this turn.

For example, there are five kids around the tree, and their genders are shown in Figure-1. The paper first goes to Kid1, after writing a “B” he passes it to Kid2, and Kid2 to Kid3. After Kid3 writes down a “G”, she ends up this turn, and we get the paper with a string “BBG”.

After N turns, we get N pieces of paper with strings of “B”s and/or “G”s. One of the kids will get all these papers, and has to figure out at least how many kids are around the tree playing the game. It's known that there are at least two kids. Please write a program to help him.

Input

There are several test cases. Each case starts with a line containing an integer N, the number of papers (2 ≤ N ≤ 16). Each of the following N lines contains a string on a paper, which is a nonempty string of letter “B”s and/or “G”s. Each string has no more than 100 letters.

A test case of N = 0 indicates the end of input, and should not be processed.

Output

For each test case, output the least possible number of kids in a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3138  

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/external/7/719.html 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/external/114/11492.html 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/external/118/11800.html 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3274 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4322

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/external/102/10245.html 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/external/8/866.html 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3624 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/external/1/186.html 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You probably never heard of the painter Peer. He is not well known, much to his regret. Peer was one of the inventors of monochromy, which means that each of his paintings has a single color, but in different shades. He also believed in the use of simple geometric forms.

During his triangle period, Peer drew triangles on a rectangular canvas, making sure their borders did not intersect. He would then choose a color, and fill the regions. Peer would paint the outermost region (the canvas itself) with the lightest shade of the color chosen. Then step by step, he would fill more inner regions with a darker shade of the same color. The image below is one of his ``Forms in Green" paintings

In a way the process was quite mechanical. The only thing Peer considered difficult was to decide, after drawing the triangles, how many different shades he would need. You must write a program to do that calculation for him. Your program will have a collection of triangles as its input. It should calculate the number of different shades needed to paint the regions according to the given rule.

Your program must also detect the rare times that Peer makes a mistake and draws triangles that intersect. Two triangles are considered intersecting if the edges of one triangle have at least one point in common with the edges of the other. In that case, the collection of triangles is invalid.

Input

The input file contains multiple test cases. The first line of each test case contains a single non-negative integer n (n ≤ 100000) , which is the number of triangles in the test case. The following n lines of the test case contain the descriptions of triangles in the format x₁ y₁ x₂ y₂ x₃ y₃ , where x_i , y_i are integers (- 100000 < x_i, y_i < 100000) that are the coordinates of the vertices of the triangles. The three points are guaranteed not to be collinear.

The last test case is followed by `-1' on a line by itself.

Output

For each test case, print the case number (beginning with 1) and the number of shades needed to fill the regions if the test case is valid. Print the word `ERROR' if the test case is invalid (two or more triangles in the test case intersect).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Like most modern cities, Stockholm has a well-developed public transportation system. The heart of public transportation in Stockholm is the subway. A topological map of the subway system illustrates the different subway lines and how they are connected, as illustrated in Figure 8. For this problem you should assume that a subway map is always tree-shaped, even though this is not quite true for Stockholm because of the cycle formed by the green and blue lines.

Figure 8: Stockholm subway map

A topological map says very little about the geometry of a subway system, such as the distances (and consequently travel times) between different subway stations. For instance, as most students in Stockholm know, the distance between “Tekniska Högskolan” (The Royal Institute of Technology) and “Universitetet” (Stockholm University) is quite large, even though there is no indication of this on the map.

You must write a program that can augment a topological map by writing down the time required to travel between every pair of adjacent subway stations. Fortunately, those travel times are known, so you do not have to measure the times yourself. But the actual travel times are given in seconds, while the times must be written on the map as estimates of integral numbers of minutes.

A natural way of estimating times might be to simply round all the travel times to the nearest minute. However, this can cause huge cumulative errors. For instance, in the Stockholm map, this estimation method could result in an error as large as 15 minutes in the total travel time between some pairs of stations. In order to counter this, your program may choose to round some travel times up and round other travel times down. The rounding must be done in such a way that the largest cumulative error between any pair of stations is minimized.

Input

The input consists of several test cases. Each test case starts with an integer N (1 ≤ N ≤ 100), which is the number of subway stations. The N stations are identified using the integers from 1 to N. Each of the next N − 1 lines contains three integers a, b and t (1 ≤ a, b ≤ N, and 1 ≤ t ≤ 300), indicating that stations a and b are adjacent and that it takes t seconds to travel between them. For simplicity, ignore the time a train spends standing still at a station.

The last test case is followed by the integer zero on a line by itself.

Output

For each test case, print the case number (starting with 1) then the largest rounding error in seconds of travel time between any pair of stations when the times for adjacent pairs of stations are rounded optimally. Follow the format of the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Association of Children Machines (ACM) is planning to build up a new type of puzzle for children. All the puzzles will have dimension (3×N) and has some or all of the following pieces. Some pieces can occur more than once. Since the puzzles made by ACM are in very high demand so many other companies have released counterfeit products which look just like puzzles made by ACM.

To prevent such counterfeit products ACM has taken up a measure which they hope will help the sellers to prevent the counterfeit products in their shop. As all puzzles are initially available in a box in a solved format and a (3×N) puzzle can have zillions of solutions for larger values of N. All the puzzles from ACM factory will have only some specific solutions when sold; they will be unique and only small fractions of all possible solutions. So it is more likely that the counterfeit products won’t have these orientations. You have to help them in the initial part: given the value of N you will have to find how many different solutions are there with the given pieces. You are not allowed to rotate the pieces while solving the puzzle but you can use any piece any number of time. Of course some of the pieces are mere rotation of another but they also cannot be rotated to make it look like the other. For example the piece with shape upside down T (the brown piece) cannot be rotated to look like a normal T (the pink piece).

Input

The input file contains several lines of input. Each line contains an integer N (0

Output

For each value of N produce one line of output. This line contains the serial of output followed by an integer which denotes the value (S % 1000000000000). Here S denotes the number of solutions for a (3×N) puzzle. Look at the output for sample input for details. 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mickey is assigned a task to help the puppies to escape by travelling from the south-west corner of a grid to the north-east corner undetected by the set of motion detectors deployed by Cruella. There are k motion detectors (1<=k<=300) which are placed on the grid points and can detect any motion within a given distance, d , from the detector. Here we adopt L1 metrics for distance measurements, i.e., the distance between two points (x₁, y₁) and (x₂, y₂) is | x₁ - x₂| + | y₁ - y₂| . For example, consider the 9×9 grid in the figure below, if the detecting distance of the two detectors, marked with a solid circle, is 3, there exists a tour from (0, 0) to (8, 8) (for example the diagonal is an undetectable tour); however, if the distance is four, there would be no such tour. 

Cruella decides to make it more difficult to escape by setting the detecting distance of the detectors randomly. For each grid, Cruel would flip coins to decide the detecting distance for all the detectors in that grid. Given the probability distribution of the detecting distance d and a series of grids, your task is to write a program to decide for each input grid the probability that it contains an undetectable tour.

Each grid is N×N where 3<=N<=10000 , and each grid point in the grid is denoted by a pair of integers, (x, y) , where 0<=x , y<=N - 1 . The probability distribution is specified by a sequence of ordered pair (d₁, p₁),(d₂, p₂),...,(d_m, p_m) where 1<=m<=100, 1<=d_i<=2(N - 1) , and each p_i has at most three digits after the decimal point. To make it a probability distribution we also have the property that Σp_i = 1 .
 

Input

The first line of the input file contains an integer indicating the number of test cases to follow, there will be at most 5 test cases. For each test case, the first line contains two integers, N and m separated by a space. Followed by m lines to specify the probability distribution, each line consists d_i, p_i . Followed by k lines of the positions of detectors in the form x ,y which is the coordination of the detector. The case ends with a line containing `-1'. 

Output

For each test case, output the probability that the grid contains a undetectable tour. 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A traveller, Yuan-Ling is visiting Tainan City. This city is located Southern TAIWAN, famous for traditionally old cities. There are several historic sites in Tainan city, some of which are connected by shopping streets. For convenience, we can view the historic sites and streets as a graph such that historic sites are represented by nodes and streets are represented by edges. The edges have nonnegative weights representing distance or time. Yuan-Ling would like to traverse all the streets, starting and ending at historic site ``Tainan Main Station". Your task is to help Yuan-Ling seek a closed walk that minimizes the total weight (the sum of the edges' weights in the walk) such that all the streets are traversed at least once. We call such a walk as a minimum closed walk. A walk is a list v₀, e₁, v₁,..., e_k, v_k of nodes and edges such that, for 1<=i<=k , the edge ei has endpoints v_i-1 and v_i . Note that a walk may repeat nodes and edges. A walk is closed if its end-nodes are the same. 

Given a graph G = (V, E) , we use 1, 2,...,| V| to represent the nodes. Each edge (u, v) is associated with the weight w(u, v) that is a positive integer. Your task is to write a computer program to compute the weight of a minimum closed walk that traverses all the edges at least once.

Technical Specification

1. G = (V, E) is connected.
2. 2<=| V|<=100 . 
3. 1<=| E|<=4950 
4. For each edge (u, v) , 1<=w(u, v)<=1000 .

Input

The first line of the input file contains an integer indicating the number of test cases to follow. The input consists of a number of test cases. Each test case consists of a graph G = (V, E) , which has the following format: the first line contains two numbers, n(= | V|) and m(= | E|) , separated by a single space. The next m lines contain the description of m edges and the corresponding weights such that one line contains two end-nodes of an edge and the corresponding weight. Each line is represented by three positive numbers separated by a single space; the first number representing one end-node, the second representing the other end-node, and the third representing its weight. Finally, a 0 at the (m + 2) th line indicates the end of this test case.

The next test case starts after the previous ending symbol `0'. A `-1' signals the end of the whole inputs.

Output

The output contains one line for each test case. Each line contains an integer, which is the weight of a minimum closed walk that traverses all the edges at least once. 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The rail roads of Japan are being redesigned. So the governent is planning to install ultra-modern Magnetic trains instead of the current normal trains. As fuel price have gone high and nations have shut down their nuclear plants so the price of electricity/battery is also sky high. To reduce power consumption the Japanese government is trying to descourage people from riding trains – as a result the ticket price is also kept sky high and it is strictly proportional to the square of the distance between two stations.

All the trains move in clockwise or counter clockwise order in a closed triangular track. These triangular tracks can be formed by connecting any three stations in clockwise or counterclockwise order. For simplicity you can assume that a station is denoted by a point in a two dimensional Cartesian Coordinate system. But these triangular tracks and ticket pricing policy can create new troubles. As the ticket price between two stations is proportional to the square of the distance, people often avoid the shortest route to destination and rather choose the longer one through another station. This causes more electricity expense per passenger and creates unwanted crowd in the stations. So the government would prefer not to make such tracks.

For example in the figure on the following you can see a closed triangular track marked with green. If someone wants to go from station D to station E he can go directly by riding a clockwise train or can go via station C by riding a counter clockwise train: That is he first buys ticket from station D to C and then he buys ticket of station C to E. But in the current ticket pricing system the route via C (which is also much longer) will be cheaper. So this site CED is not a place to build a track. For the similar reasons AEB is a valid site for building track. On a valid track the shortest distance between any two stations is also the unique cheapest route between them. Given the coordinate of all stations you will have to find the number of sites (a group of three places) for valid tracks.

Input

The input file contains at most 15 sets of inputs. The description of each set is given below:

Each set starts with an n (2i, y_i (0≤x_i, y_i≤10000) which denotes the Cartesian coordinate of the i-th station. You can assume that a track can be built via through any three stations, no three places will be collinear to avoid the problem of degenerate tracks and the connecting railroad between two stations can always be represented by the straight line connecting them.

Output

For each set of input produce two line of output. The first line contains the serial of output and the second line displays the total number of sites where a track can be built. Look at the output for sample input for details.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Simple ASCII characters can form a figure containing nested squares: as shown in Figure-1 below. Here the outer most square is formed by character a, the next square is formed by character b and the innermost square is formed by character c.

Such a square can be denoted uniquely by a characteristics string “abc”: that is the first character forms the outermost square, the next character forms the next square and so on. So a string of length 50000 can actually denote a (99999X99999) square grid, which will require around 9 Gigabyte of memory to be stored normally. In this problem you will be asked to print a small portion of such a huge square.

The different characters that form a (N*N) square are numbered in row major order, the upper left character is at position (1,1) and the lower right character is at position (N,N). This is shown in Figure 2.
 

Input

The first line contains an integer N(0

The first line of each set contains a string S (1≤|S|≤50000) and an integer Q (1≤Q≤50). Here S is the characteristic string of a nested square pattern and |S| is the length of string S. This string contains only alphabets and decimal digits. The integer Q denotes the total number of query.

Each of the next Q lines contain four integers r1, c1, r2, c2, which actually denotes a bounding box whose upper left corner is (r1, c1) and lower right corner is (r2, c2). You can assume that (1 ≤ r1, c1, r2, c2 ≤ 2*|S|-1) , 0 ≤ r2-r1 ≤ 100 and 0 ≤ c2-c1 ≤ 100.

There is a blank line between two consecutive input cases.

Output

For each set of input produce several lines of output.

The first line of output for each set contains the serial of the set. Then for each query produce the serial of query followed by the contents within the required bounding box. 

Print a blank line after the output for each test case.

Look at the output for sample input for details.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

On a small planet named Bandai, a landing party of the starship Tadamigawa discovered colorful cubes traveling on flat areas of the planet surface, which the landing party named beds. A cube appears at a certain position on a bed, travels on the bed for a while, and then disappears. After a longtime observation, a science officer Lt. Alyssa Ogawa of Tadamigawa found the rule how a cube travels on a bed.

A bed is a rectangular area tiled with squares of the same size.

• One of the squares is colored red,
• one colored green,
• one colored blue,
• one colored cyan,
• one colored magenta,
• one colored yellow,
• one or more colored white, and
• all others, if any, colored black.
  

Initially, a cube appears on one of the white squares. The cube's faces are colored as follows.

       top red 
bottom cyan
   north green 
   south magenta 
     east blue 
    west yellow

The cube can roll around a side of the current square at a step and thus rolls on to an adjacent square. When the cube rolls on to a chromatically colored (red, green, blue, cyan, magenta or yellow) square, the top face of the cube after the roll should be colored the same. When the cube rolls on to a white square, there is no such restriction. The cube should never roll on to a black square.

Throughout the travel, the cube can visit each of the chromatically colored squares only once, and any of the white squares arbitrarily many times. As already mentioned, the cube can never visit any of the black squares. On visit to the final chromatically colored square, the cube disappears. Somehow the order of visits to the chromatically colored squares is known to us before the travel starts.

Your mission is to find the least number of steps for the cube to visit all the chromatically colored squares in the given order.

Input

The input is a sequence of datasets. A dataset is formatted as follows:

w d  
c₁₁ ... c_w1
  ...       ...
c_1d ... c_wd
v₁v₂v₃v₄v₅v₆

The first line is a pair of positive integers w and d separated by a space. The next d lines are w -character-long strings c11 ... cw1, ... , c1d ... cwd with no spaces. Each character cij is one of the letters r, g, b, c, m, y, w and k, which stands for red, green, blue, cyan, magenta, yellow, white and black respectively, or a sign #. Each of r, g, b, c, m, y and # occurs once and only once in a dataset. The last line is a six-character-long string v1v2v3v4v5v6 which is a permutation of ``rgbcmy".

The integers w and d denote the width (the length from the east end to the west end) and the depth (the length from the north end to the south end) of a bed. The unit is the length of a side of a square. You can assume that neither w nor d is greater than 30.

Each character cij shows the color of a square in the bed. The characters c11 , cw1 , c1d and cwd correspond to the north-west corner, the north-east corner, the south-west corner and the southeast corner of the bed respectively. If cij is a letter, it indicates the color of the corresponding square. If cij is a #, the corresponding square is colored white and is the initial position of the cube.

The string v1v2v3v4v5v6 shows the order of colors of squares to visit. The cube should visit the squares colored v1, v2, v3, v4, v5 and v6 in this order. The end of the input is indicated by a line containing two zeros separated by a space.

Output

For each input dataset, output the least number of steps if there is a solution, or ``unreachable" if there is no solution. In either case, print it in one line for each input dataset.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Jisung is the student representative of the Department of Computer Engineering in ACM University. A few days later, the annual festival will be held for the students in the department. He is preparing some events for the festival. Since Jisung likes to make and solve puzzles, he decides to devise some interesting puzzle for the festival.

The followings are the rules for the puzzle made by Jisung:

(1)

The players will be given an integer n . Then they should use the first n capital letters from the Roman alphabet. For example, if n = 4 , the four characters A, B, C, and D will be used to solve this puzzle.

(2)

The players will be given s forbidden strings. No forbidden string contains another forbidden string as a substring. The winner is the student who makes the longest string that does not include a forbidden string as a substring.

(3)

If such a longest string does not exist, i.e., if we can make arbitrarily long strings that satisfy the above condition, or if we cannot make any string that satisfies the above condition, `No' should be answered.

For example, suppose the given number n = 2 , i.e., the players can use the two characters A and B. Assume that the forbidden strings are {AAA, AB, BA, BB}. In this case, the longest string that does not include any of the four forbidden strings as substrings is AA. But if the given forbidden strings are {AAA, BBB, ABAB, BBAA}, we cannot make such a longest string since arbitrarily long concatenations of ABA, i.e., ABAABAABA ... do not include any forbidden string.

Input

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers n (1 ≤ n ≤ 26) and s (1 ≤ s ≤ 1,000) which represent the number of characters and the number of forbidden strings, respectively. From the second line to (s + 1) -st line of the test case, the forbidden strings are given one by one. The length of a forbidden string does not exceed 50.

Output

Your program is to write to standard output. Print exactly one line for each test case. Print the longest string that does not include any forbidden string as a substring if it exists, otherwise, just print `No' as output. When there exists more than one such longest string with the same length, print the lexicographically largest string among them.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You're addicted to a little game called `remember the melody': you hear some notes, and then you repeat it. In most cases, the longer the melody, the harder to repeat, but it isn't always true. Also, melodies of the same length are usually not equally easy to remember. To find a way to define the remember difficultyof a melody, you invented a statistics-based model:

Suppose you're investigating melodies of a particular length. If a melody appeared in p games, among which you successfully repeated q games, the smaller q/p , the more difficult the melody. If there is more than one melody having the minimal ratio, the one with larger p is considered more difficult. But there is an exception: if p is smaller than a threshold m , you simply ignore it (you can't call it difficult if you haven't tried it a lot of times, can you?). The melody appears in a game if its string representation is a consecutive substring occurring at least once in that game.

Write a program to find the most difficult melody of length k , given n games you've played.

Input

The input contains several test cases. Each case consists of three integers n, m, k (1<=m<=n100, 1<=k<=20) , the next n lines each contain two strings separated by exactly one space: the game, and whether you successfully repeated it. The first string will contain at least one at most 100 upper case letters `C', `D', `E', `F', `G', `A', `B'. The second string will be either `Yes' or `No' (case sensitive). The last test case is followed by a single zero, which should not be processed.

Output

For each test case, print the case number and the most difficult melody. If there is more than one solution, output the lexicographically smallest one. If there is no solution, output the string `No solution'.

Sample Input  Download

Sample Output  Download

Tags

Discuss