Description

By 2100, space travel will be a reality for the Milky Way (Solar Galaxy) residents. The Interstar Transport Travel agency operates scheduled direct space transports (flights) between some of the most popular planet destinations in the Milky Way. The cost of these scheduled direct transports are predetermined in Galaro (Galaxy Currency unit) and are published in many different languages. For travel to planets that is not on the schedule, there are slower, yet free, space flights from the closest planet that is on the direct transport list. To help travelers plan their itinerary, the Interstar Transport wants to offer a mobile application that can find the best traveling option, based on the total cost of the direct transports on the itinerary. Given the starting and destination planets on the itinerary, find the sequence of direct transports that has the lowest total traveling cost. Output all the planets in sequence that one must pass through on this best route. If two or more routes exist with the same cost, then the route that goes through the least number of intermediate planets is considered a better route. There will always exist a unique best route for any of the given test cases.

Technical Specification

1. The number of planets on the direct transport list is at most s, 1 ≤ s ≤ 26. The planets are labeled using capital letters of the English alphabets, i.e., “A”, “B”, “C”, ..., “Z”, in no particular order.
2. The Interstar Transport operates at most p, 1 ≤ p ≤ 200, direct transports between planets. There is at most one (could be none) direct transport between any two distinct planets.
3. The cost of any transport is given as a natural number less than or equal to 100 Galaros.

Input

The first line of the input file contains two integers, s and p, separated by a space. The next p lines each contains two letters, e_i and e_j , followed by a natural number, d_ij , indicating that there exists a direct transport between planets e_i and e_j with a cost of d_ij . The next line contains an integer n ≤ 20, indicating the number of queries to follow. For each of the next n lines, each line contains two letters e_k and e_m, indicating a user is looking for a best (lowest cost) way to get from planet e_k to planet e_m.

Output

For each of the n queries in the input, output on one line the best route to take, in the sequence of starting planet, the intermediate planets in sequence along the route and the destination planet; all separated by one blank space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are going to buy a house and hence communicated with a real estate development company, which has just started their business and you are going to be the first buyer. So they are offering you something special.

The real estate company has a rectangular shaped land of width W and height H. They are using co­ordinate system for measuring lands. (0, 0) is the lower left corner of their land and any point which has distance x from lower edge of the land and distance y from left edge of the land is known as (x, y) in the co­ordinate system.

The real estate company has already built some houses in that piece of land. All of them are rectangular shaped and their edges are parallel to edges of the main land. The location of a house can be addressed by four integers x1, y1, x2, y2. Where (x1, y1) is the lower left corner and (x2, y2) upper right corner of the house.

The special offer is that you can choose any rectangular shaped region that contains exactly one house with any amount of adjacent open space. You may not have enough money to afford open space and choose to buy only the region that a house occupies. If you have enough money, you can keep open space in front of your house for gardening! 

But still there are some restrictions. For the ease of their future use of rest of their land you can only choose a rectangular shaped region and the edges of which are parallel to the edges of the main land. The corners of your selected region should be integer coordinates. It can be (3, 2) but cannot be (3.5, 2). You cannot chose a region for which part of a house is inside the region and another part of that house is outside the region. You cannot choose a region having more than one house and a region having no house. How many ways you can choose your land following the above rules?

Input

Input will start with an integer T (T is around 500), the number of test cases. Each of the test cases starts with two integers W and H (1 <= W, H <= 1000000000), width and height of the land and the next line contains an integer N (1 <= N <= 50), the number of houses in the land.  Each of the next N lines will contain four integer x1, y1, x2, y2 ( 0 <= x1 < x2 <= W and  0 <= y1 < y2 <= H ), which describes the location of the house. Note that no house can overlap with another house and all the given coordinates will be non negative integers.

Output

For each input, print a single line of the form “Case #: W”, where ‘#’ will be replaced by the case number and W will be replaced by the number of ways you can choose your land. Here W can be very large, so you should print the number of ways modulo 1000000007 as W.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a science laboratory, scientists found a new kind of tiny lifeforms and named them “synnergs”. Until now, few knowledge about synnergs are known. Some of these knowledge are as follow.

• There are more than one types of synnerg. 
• Any new born synnerg have the same lifetime. 
• Two synnergs (of certain types) can extend their lifetimes by unifying themselves together which will also transform them into a new target synnerg. The lifetime of this new target is the summation of both sources' lifetimes multiplied with an amplification factor. The type of this new target may vary from its sources.  From many experiments, scientists found a set of rules to describe the unification of each synnerg pair . Some of these rules can be shown as the following table.
  
• When scientists arrange two or more of new born synnergs into a sequence, each synnerg in this sequence will try to unify itself with the one on its left or its right (and make the sequence shorter).   This unification process will continue again and again (recursively).  There might be lots of possible ways to unify an input sequence which also affect  the lifetime of each unified synnerg.

For example of unification steps, please see the following table.

In the first example, at the first step there is a sequence of 4 new born synnergs “a a b b” where their lifetimes are “1 1 1 1” respectively. In the second step, these synnergs unify themselves into a sequence of two synnergs “aa[a a] bb[b b]” (using rule no.1 and 3) where aa's lifetime is 2=(1+1)*1 and bb's lifetime is 6=(1+1)*3. In the third step, “aa bb” unify themselves into “x[aa bb] (using rule no. 4) where its lifetime is 16=(6+2)*2.

In the second example, at the first step, the beginning sequence is the same sequence in the first example. But they alternatively unify themselves into “AA[a a] bb[b b]” (using rule no.2 and 3 instead) where their lifetimes are 34=(1+1)*17 and 6(1+1)*3 respectively. This sequence is also the final sequence which means that it is unable to unify furthermore but it is not a completely unified sequence. However, this alternative final sequence has longer life time comparing to the final sequence in the first example.

The third and fourth example also show the alternative ways of unifying the sequence “a c a c”. Please be notify that each rule is not sensitive to the order of its sources.

Goal 

The scientists would like you to create a program that can find all highest lifetime synnergs that can be created by unifying a given sequence of newborn synnergs. The solution may not always be the one that is completely unified. Only part or sub sequence unification is also acceptable.

Input

Input is a standard input which contains 2 parts of data which are separated by a blank line.

The first part is a set of unification rules. 

• Each line in this first part contains one of unification rule.
• Each rule consists of 4 fields separated by spaces. 
• The first 3 fields are target, source #1 and source #2 respectively. Each fields is a synnerg name which is represented by a string of at most 20 alpha­numeric characters. 
• The last field is the amplification factor which is a positive integer less than or equal to 100.

The second part is a set of input sequences of synnergs.

• Each line in this second part contains one input sequence of synnergs
  
• Each input sequence is a sequence of synnergs separated by spaces.The blank line after the second part is the termination of the input.

The blank line after the second part is the termination of the input.

Output

 For each sequence of input, write 2 parts of output as follows

• In the first line, write the total of number of highest synnergs followed by a space and then the maximum lifetime of these synnergs.
• In the following lines, write each of the solutions in each line. Each solution contains 3 fields separated by spaces. These fields are a synnerg, its starting and finishing offset. If there are two or more solutions, they must be sorted by ascending order. The priority of comparison in sorting is the 2^nd field, the 3^rd field and the 1^st field (or the starting offset, the finishing offset and the synnerg). For comparisons in sorting, the 2^nd and 3^rd field comparison is based on numerical values, and the 1st field is based on alphabetical/lexicographical (ASCII) order.

More Explanations

There are 6 rules and 5 input sequences in this sample input.

For the first case, even though there is a completed unification “x[aa[a a] bb[b b]]” (starting from 1 to 4),  its lifetime is only 16 (= {(1+1)*1 + (1+1)*3}*2) times of a newborn, which is less than 34 of “AA[a a]” starting from 1 to 2.

For the second case, there are 2 solutions. The first is “AA” starting from 1 to 2. The second is “x” starting from 1 to 5.For the third case, there is only one solution. “x” now is the only winner (with 70 points).

For the fourth and the fifth cases, (parts of) the results has been unified according to the last rule. Since each rule is not sensitive to the order of its sources, any rule is applicable if both of its source are found. (“c c a 3” equals “c a c 3”.)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In Nowhere town, people use “coin and slot” as their money. There are 2 types of coins called size1 and size2. Size2 coin is twice the thickness of size1. People stack their coins in slots and use them as money. There are many size of slots. The slot of size n is able to stack up n size1 coins. Only filled­up slot is considered as legal money. The value of each filled­up slot is the distinct ways its can stack coins inside. For example, for size­1 slot, there is only one way to stack a single size1 coin inside. For size­2 slot, there are 2 ways to stack two size1 coins or one size2 coin inside. And for size­5 slot, there are 8 ways to stack coins inside, which can be illustrated as follow: 1 1 1 1 1, 1 1 1 2, 1 1 2 1, 1 2 1 1, 2 1 1 1, 1 2 2, 2 1 2, 2 2 1. So the value of filled up slot with size­1, size­2 and size­5 are 1, 2 and 8 (monetary) units respectively (regardless of the type of coins or the ways they are stacked). 

Mr.Thinktwice is an owner of a grocery store in this town. He noticed that customers are likely to go to the shop that can return the (money) change in the form that suits their customer. And from his little survey, he found that most customers would like to get their amount of change in the form according to these 2 simple constraints.

1. The number of slots is minimum.
2. The size of each slot must be different from each other by at least 2. 
   -This means that customers does not want any slots with the same size and it will be easier for them to distinguish these differences if the sizes are not too close.

So Mr.Thinktwice ask you to write a program that can give him a series of slot sizes for a given amount of change according to the previous constraints. Moreover, the series must be sorted in descending order. For more specific, any amount of change can be written in this formula.

For example:

Input

Input is a standard input which contains a set of integer. Each line of the input is an amount of change which represents by a positive integer less than or equal to 5,000,000,000,000,000,000 or  5 x 1018.  The input is terminated when the EOF (End­Of­File) is reached.

Output

For each amount of change, generate 4 lines of output data. The first line is the amount of change itself. The second line is a series of slot sizes (in descending order) separated by spaces. (The maximum slot size is less than or equal to 90.) The third line is a series of corresponding slot values. The fourth line is a blank line.

Note: The output about end of second and third line need contain one space. The standard of outputs will let the judge system show “Presentation Error＂.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Crimes in city of Megacity are going high. To fight the crimes, the authorities have created a highway patrol. The city consists of a number of one­way roads. At the ends of each road, there is a base station for the patrol troops. Each base station has a number of troops. At the beginning,  each station sends a troop along all the outgoing highways from that station. The troop patrols the highway and whenever it reaches the station on the other side of the highway, it waits there, and the troop that has been waiting there the most, is sent along the highway that has not been patrolled the longest time. 

Soon, they faced some difficulties, cause, the frequency of patrolling a highway is more and more dependent on the number of highways that started and ended at the base station. If the number of highways started at a base station is more than the number of highways ended there, the roads are patrolled less frequently. And if, no highways end at some base station, then, the highways started from there, will not be patrolled more than once.

In this situation, the highway patrol decided to remove some highways from the patrolling schedule, so that, at each base station, the number of highways started and ended at any base station will be equal. The rest of the highways will be monitored using video surveillance. But, due to some security issues, there are some highways that have to be patrolled. 

Now, given the cost of patrolling highways, and that of installing video surveillance, find the minimum cost of monitoring the whole city. Please keep in mind that, video surveillance can not substitute the highway patrol completely. So, there has to be at least one highway that will be patrolled. 

Input

 First line of the input contains an integer T(T≤ 70), the number of test cases. This is followed by T test cases. Each test case starts with two integers N(1 ≤ N ≤ 100) and M(1 ≤ M ≤ 1000), the number of base stations and highways. This is followed by M lines, each containing 5 integers, u,v,p,s,x(1 ≤ u,v ≤ N,0 ≤ p,s ≤ 1000000) where u and v means, the highway starts from base station u, and ends at v, p is the cost of patrolling and s is the cost of installing video surveillance. If the highway must be patrolled, then x will be one. Otherwise it will be zero.

Output

For each test case, output the case number, followed by the minimum cost to monitor the highways. If it is not possible to patrol satisfying the given constraints, output “impossible” (without quotes). 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Secret agent Maria was sent to Algorithms City to carry out an especially dangerous mission. After several thrilling events we find her in the first station of Algorithms City Metro, examining the time table. The Algorithms City Metro consists of a single line with trains running both ways, so its time table is not complicated.Maria has an appointment with a local spy at the last station of Algorithms City Metro.

Maria knows that a powerful organization is after her. She also knows that while waiting at a station, she is at great risk of being caught. To hide in a running train is much safer, so she decides to stay in running trains as much as possible, even if this means traveling backward and forward. Maria needs to know a schedule with minimal waiting time at the stations that gets her to the last station in time for her appointment. You must write a program that finds the total waiting time in a best schedule for Maria. 

The Algorithms City Metro system has N stations, consecutively numbered from 1 to N. Trains move in both directions: from the first station to the last station and from the last station back to the first station. The time required for a train to travel between two consecutive stations is fixed since all trains move at the same speed.Trains make a very short stop at each station, which you can ignore for simplicity. Since she is a very fast agent, Maria can always change trains at a station even if the trains involved stop in that station at the same time.

Input

The input file contains several test cases. Each test case consists of seven lines with information as follows.

The integer N ( 2 ≤ N ≤ 50), which is the number of stations.

Line 2.

The integer T ( 0 ≤ T ≤ 200), which is the time of the appointment.

Line 3.

N - 1 integers: t1, t2,..., tN - 1 ( 1 ≤ ti ≤ 70), representing the travel times for the trains between two consecutive stations: t1 represents the travel time between the first two stations, t2 the time between the second and the third station, and so on.

Line 4.

The integer M1 ( 1 ≤ M1 ≤ 50), representing the number of trains departing from the first station.

Line 5.

M1 integers: d1, d2,..., dM1 ( 0 ≤ di ≤ 250 and di < di + 1), representing the times at which trains depart from the first station.

Line 6.

The integer M2 ( 1≤M2≤50), representing the number of trains departing from the N-th station.

Line 7.

M2 integers: e1, e2,..., eM2 ( 0 ≤ ei ≤ 250 and ei < ei + 1) representing the times at which trains depart from the N-th station.

The last case is followed by a line containing a single zero.

Output

For each test case, print a line containing the case number (starting with 1) and an integer representing the total waiting time in the stations for a best schedule, or the word `impossible' in case Maria is unable to make the appointment. Use the format of the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Air fares are crazy! The cost of a ticket is determined by numerous factors, and is usually not directly related to the distance traveled. Many travelers try to be creative, sometimes using only parts of tickets with stops in various cities to achieve lower-cost travel. However, the airlines are aware of this behavior, and usually require that the travel covered by a ticket be completed in order and without intervening travel. For example, if you have a ticket for travel from City-1 to City-2 then to City-3, you are not allowed to use only the portion of the ticket for travel from City-2 to City-3. You must always start at the first city on the ticket. In addition, you are not allowed to travel from City-1 to City-2, fly elsewhere and return, and then continue your journey from City-2 to City-3.

Let's consider an example. Suppose you are allowed to purchase three types of tickets:

Suppose you wanted to travel from City-1 to City-3. There are two ways to get there using only the available ticket choices:

Purchase Ticket #1 for $225.00 and use only the first leg of the ticket.

Purchase Ticket #2 for $200.00 and Ticket #3 for $50.

The first choice is the cheapest.

Given a set of airline ticket offers, and one or more trip itineraries, you must determine how to purchase tickets in order to minimize the cost of travel. Each trip will be possible.

Input

Input consists of multiple test cases, each describing a set of ticket offers and a set of trip itineraries.

Each case begins with a line containing NT, the number of ticket offers, followed by NT offer descriptions, one to a line. Each description consists of a positive integer specifying the price of the ticket, the number of cities in the ticket's route, and then that many cities. Each city in a case has an arbitrary, but unique, integer identification number. Note that several tickets may be purchased from the same offer.

The next line contains NI, the number of trips that are to have their cost minimized. NI lines follow, giving the itineraries for each trip. Each line consists of the number of cities in the itinerary (including the starting city), followed by that many city identification numbers, given in the order they are to be visited.

There will be no more than 20 ticket offers or 20 itineraries in a test case. Each offer and itinerary lists from 2 to 10 cities. No ticket price exceeds $10,000. Adjacent cities in a route or itinerary will be distinct. Tickets and trips are numbered sequentially in each set, starting with 1.

The last case is followed by a line containing a zero.

Output

For each trip, output two lines containing the case number, the trip number, the minimum cost of the trip, and the numbers of the tickets used for the trip, in the order they will be used. Follow the output format shown below. The output will always be unique.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Can you cover a round hole with a square cover? You can, as long as the square cover is big enough. It obviously will not be an exact fit, but it is still possible to cover the hole completely.

The Association of Cover Manufacturers (ACM) is a group of companies that produce covers for all kinds of holes - manholes, holes on streets, wells, ditches, cave entrances, holes in backyards dug by dogs to bury bones, to name only a few. ACM wants a program that determines whether a given cover can be used to completely cover a specified hole. At this time, they are interested only in covers and holes that are rectangular polygons (that is, polygons with interior angles of only 90 or 270 degrees). Moreover, both cover and hole are aligned along the same coordinate axes, and are not supposed to be rotated against each other - just translated relative to each other.

Input

The input consists of several descriptions of covers and holes. The first line of each description contains two integers h and c ( 4h50 and 4c50), the number of points of the polygon describing the hole and the cover respectively. Each of the following h lines contains two integers x and y, which are the vertices of the hole's polygon in the order they would be visited in a trip around the polygon. The next c lines give a corresponding description of the cover. Both polygons are rectangular, and the sides of the polygons are aligned with the coordinate axes. The polygons have positive area and do not intersect themselves.

The last description is followed by a line containing two zeros.

Output

For each problem description, print its number in the sequence of descriptions. If the hole can be completely covered by moving the cover (without rotating it), print `Yes' otherwise print `No'. Recall that the cover may extend beyond the boundaries of the hole as long as no part of the hole is uncovered. Follow the output format in the example given below.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Hugh Samston owns the ``You Want It, Hugh Got It" catering service, which has been asked to supply desserts for the participants in this year's ICPC World Finals. Hugh will provide pie slices topped with ice cream at the various social functions scheduled throughout the week. As with any other dedicated entrepreneur, Hugh would like to offer the best service possible, so he has ordered a wide variety of pies and ice creams to satisfy even the most eclectic tastes.

Hugh plans to serve each pie slice with a single scoop of ice cream, leaving the exact combination up to the whim of the customer. But of course, as with any other dedicated entrepreneur, Hugh would also like to make as much profit as possible from this enterprise. He knows ahead of time how much profit he can make on each combination of pie slice and ice cream scoop, as well as which combinations of pie and ice cream should never be put together (example: Peppermint Banana Chunk ice cream on Key Lime pie).

Given this information, along with the number of slices and scoops he has of each variety of pie and ice cream, Hugh figures he can determine both the minimum and maximum profits he can expect. Since he hopes to be the caterer at subsequent World Finals, he would like a general program to solve this and future problems.

Input

Input will consist of multiple problem instances. Each problem instance will start with a line containing two integers P (P50) and I (I50), indicating the number of types of pie and ice cream, respectively. The next line will contain P integers indicating the number of slices available for each of the pie types. The line after that will contain I integers indicating the number of scoops available for each of the ice cream types. The total number of pie slices will always equal the total number of ice cream scoops available, and it is assumed that all pie slices and ice cream scoops will be used.

Each problem instance will end with P lines each containing I floating point numbers indicating the profit for each pie/ice cream combination: the first value indicates the profit if a slice of pie type 0 is topped with a scoop of ice cream type 0; the next value indicates the profit if a slice of pie type 0 is topped with a scoop of ice cream type 1, and so on. A profit value of `-1' indicates that no combinations of that pie type and ice cream type should ever be sold. All other integers (number of slices for each type of pie and number of scoops for each type of ice cream) will be less than or equal to 100 and the profit on each one of the pie/ice cream combinations (other than `-1') will be larger than 0 and less than or equal to 10, with at most two digits after the decimal point.

The last problem instance is followed by a line containing two zeroes.

Output

For each problem instance, output the problem number (starting at 1) followed by the minimum and maximum profits, using the format shown in the sample output. Display all numbers with two fractional digits. All problem instances are guaranteed to have at least one solution using all of the pie slices and ice cream scoops.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a connected undirected graph, tell if its minimum spanning tree is unique. 

Definition 1 (Spanning Tree): Consider a connected, undirected graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'), with the following properties: 
1. V' = V. 
2. T is connected and acyclic. 

Definition 2 (Minimum Spanning Tree): Consider an edge-weighted, connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E') of G is the spanning tree that has the smallest total cost. The total cost of T means the sum of the weights on all the edges in E'. 

Input

The first line contains a single integer t (1 <= t <= 20), the number of test cases. Each case represents a graph. It begins with a line containing two integers n and m (1 <= n <= 100), the number of nodes and edges. Each of the following m lines contains a triple (xi, yi, wi), indicating that xi and yi are connected by an edge with weight = wi. For any two nodes, there is at most one edge connecting them.

Output

For each input, if the MST is unique, print the total cost of it, or otherwise print the string 'Not Unique!'

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B 
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school. 

Input

The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.

Output

Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Sindbad the Sailor sold 66 silver spoons to the Sultan of Samarkand. The selling was quite easy; but delivering was complicated. The items were transported over land, passing through several towns and villages. Each town and village demanded an entry toll. There were no tolls for leaving. The toll for entering a village was simply one item. The toll for entering a town was one piece per 20 items carried. For example, to enter a town carrying 70 items, you had to pay 4 items as toll. The towns and villages were situated strategically between rocks, swamps and rivers, so you could not avoid them.

Figure 1: To reach Samarkand with 66 spoons, traveling through a town followed by two villages, you must start with 76 spoons.

Figure 2: The best route to reach X with 39 spoons, starting from A, is A->b->c->X, shown with arrows in the figure on the left. The best route to reach X with 10 spoons is A->D->X, shown in the figure on the right. The figures display towns as squares and villages as circles.

Predicting the tolls charged in each village or town is quite simple, but finding the best route (the cheapest route) is a real challenge. The best route depends upon the number of items carried. For numbers up to 20, villages and towns charge the same. For large numbers of items, it makes sense to avoid towns and travel through more villages, as illustrated in Figure 2.   You must write a program to solve Sindbad’s problem. Given the number of items to be delivered to a certain town or village and a road map, your program must determine the total number of items required at the beginning of the journey that uses a cheapest route. You will also have to find the cheapest route. If there is more than one such route, print the lexicographically smallest one (A-n-d is smaller than a-n-d).

Input

The input consists of several test cases. Each test case consists of two parts: the roadmap followed by the delivery details.

The first line of the roadmap contains an integer n, which is the number of roads in the map (0 <= n). Each of the next n lines contains exactly two letters representing the two endpoints of a road. A capital letter represents a town; a lower case letter represents a village. Roads can be traveled in either direction.

Following the roadmap is a single line for the delivery details. This line consists of three things: an integer p (0 < p < 1000000000) for the number of items that must be delivered, a letter for the starting place, and a letter for the place of delivery. The roadmap is always such that the items can be delivered.

The last test case is followed by a line containing the number -1.

Output

The output consists of three lines for each test case. First line displays the case number, second line shows the number of items required at the beginning of the journey and third line shows the path according to the problem statement above. Actually, the path contains all the city/village names that Sindbad sees along his journey. Two consecutive city/village names in the path are separated by a hyphen.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A bonus plan is one of the most effective tools to motivate employees, therefore most companies take it seriously to decide the amount of the bonus for each employee. BonBonus is a company striving on automatic bonuses calculation software and serves many international companies. For international companies, each employee has two reporting lines, one for the regional office and the other for the functional head. And each employee's performance is based on the evaluations of the regional office and the functional head. For example, Mr. Doe is working in Taiwan office as a marketing manager, then his bonus is decided by the evaluations of Taiwan office and the marketing division in the head quarter.

Let us skip all the complicated details of the bonus calculation. The final output of the BonBonus program is a two dimensional m×n table, where each row corresponds to a region and each column corresponds to a functional coding, and the entry in a_{i, j} is the bonus for the employee in the region i and for the function j . As usual, there is no negative bonus. Naturally, the row sums and column sums are the performance for regions and functions. Companies usually announce the performance of regions and functions while they keep the individual's bonus secret.

BonBonus was doing very well until a phone call brought the stormy bad news. A company ran the BonBonus program and happily announced the performance for each region and each function. Later, they found out that the entries in the table were not all integers, it had at most two digits after the decimal point. ``Not every country has cents! And we have already announced the performance for regions and functions," shouted at the other end of the phone line. ``Didn't you notice the fractional number problem when you announced them?" asked the BonBonus chief technology officer. ``The row sums and column sums are all integers!" replied with the mixture of anger and amusement. ``How may I help you?" explored the CTO. ``You make all the entries integers! Keep the row sums and column sums intact. And moreover, the difference between the final adjusted bonus and the true bonus must be strictly less than one! And you have 24 hours to fix the problem." That was the last sentence of the phone call. As you had expected, many companies do business in countries without cents. The phone calls rushed in and you, the guru of programming, was called in. ``You fix the problem," demanded the CTO. ``But, sir. Can it be fixed?" you asked. ``If it cannot be fixed, then you have an even bigger problem," said the CTO. You remained silent as if you were pondering. ``Fix it and you will get a bonus which will make you beyond happiness." ``Okay, sir. I will try my best." You are to write a program to solve the problem above.

Technical Specification

1. Each company has at least 2 regions and functions and at most 50 regions and functions, i.e., 2 ≤ n, m ≤ 50 .
2. The entries for the original table are greater than or equal to zero and less than or equal to 100 with at most two digits after the decimal point, i.e., 0 ≤ ai, j ≤ 100 .

Input

The first line of the input file contains an integer indicating the number of test cases to follow. The first line for each test case contains two integers m , n separated by a space and the following m lines contain nnumbers each. And the j -th number in the i -th line is a_ij

Output

Output the adjusted bonuses for each case in order. Use a space to separate each column and a line to separate each row. Or output two characters ``no" if no such adjustment exists for that case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Kamal is a Motashota guy. He has got a new job in Chittagong. So, he has moved to Chittagong from Dinajpur. He was getting fatter inDinajpur as he had no work in his hand there. So, moving to Chittagong has turned to be a blessing for him. Every morning he takes a walk through the hilly roads of charming city Chittagong. He is enjoying this city very much. There are so many roads in Chittagong and every morning he takes different paths for his walking. But while choosing a path he makes sure he does not visit a road twice not even in his way back home. An intersection point of a road is not considered as the part of the road. In a sunny morning, he was thinking about how it would be if he could visit all the roads of the city in a single walk. Your task is to help Kamal in determining whether it is possible for him or not.

Input

Input will consist of several test cases. Each test case will start with a line containing two numbers. The first number indicates the number of road intersections and is denoted by N (2 ≤ N ≤ 200). The road intersections are assumed to be numbered from 0 to N-1. The second number Rdenotes the number of roads (0 ≤ R ≤ 10000). Then there will be R lines each containing two numbers c₁ and c₂ indicating the intersections connecting a road.

Output

Print a single line containing the text “Possible” without quotes if it is possible for Kamal to visit all the roads exactly once in a single walk otherwise print “Not Possible”.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

When a radio station is broadcasting over a very large area, repeaters are used to retransmit the signal so that every receiver has a strong signal. However, the channels used by each repeater must be carefully chosen so that nearby repeaters do not interfere with one another. This condition is satisfied if adjacent repeaters use different channels. 

Since the radio frequency spectrum is a precious resource, the number of channels required by a given network of repeaters should be minimised. You have to write a program that reads in a description of a repeater network and determines the minimum number of channels required.

Input

The input consists of a number of maps of repeater networks. Each map begins with a line containing the number of repeaters. This is between 1 and 26, and the repeaters are referred to by consecutive upper-case letters of the alphabet starting with A. For example, ten repeaters would have the names A,B,C,...,I and J. A network with zero repeaters indicates the end of input. 

Following the number of repeaters is a list of adjacency relationships. Each line has the form: 

A:BCDH 

which indicates that the repeaters B, C, D and H are adjacent to the repeater A. The first line describes those adjacent to repeater A, the second those adjacent to B, and so on for all of the repeaters. If a repeater is not adjacent to any other, its line has the form 

A: 

The repeaters are listed in alphabetical order. 

Note that the adjacency is a symmetric relationship; if A is adjacent to B, then B is necessarily adjacent to A. Also, since the repeaters lie in a plane, the graph formed by connecting adjacent repeaters does not have any line segments that cross. 

Output

For each map (except the final one with no repeaters), print a line containing the minumum number of channels needed so that no adjacent channels interfere. The sample output shows the format of this line. Take care that channels is in the singular form when only one channel is required.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Gappu has a very busy weekend ahead of him. Because, next weekend is Halloween, and he is planning to attend as many parties as he can. Since it’s Halloween, these parties are all costume parties, Gappu always selects his costumes in such a way that it blends with his friends, that is, when he is attending the party, arranged by his comic-book-fan friends, he will go with the costume of Superman, but when the party is arranged contestbuddies, he would go with the costume of ‘Chinese Postman’.

Since he is going to attend a number of parties on the Halloween night, and wear costumes accordingly, he will be changing his costumes a number of times. So, to make things a little easier, he may put on costumes one over another (that is he may wear the uniform for the postman, over the superman costume). Before each party he can take off some of the costumes, or wear a new one. That is, if he is wearing the Postman uniform over the Superman costume, and wants to go to a party in Superman costume, he can take off the Postman uniform, or he can wear a new Superman uniform. But, keep in mind that, Gappu doesn’t like to wear dresses without cleaning them first, so, after taking off the Postman uniform, he cannot use that again in the Halloween night, if he needs the Postman costume again, he will have to use a new one. He can take off any number of costumes, and if he takes off k of the costumes, that will be the last k ones (e.g. if he wears costume A before costume B, to take off A, first he has to remove B).

Given the parties and the costumes, find the minimum number of costumes Gappu will need in the Halloween night.

Input

First line contains T (T ≤ 2500), the number of test cases.

Each test case starts with two integers, N and M(1≤N,M≤100), the number of parties, and number of different types of costumes. Next line contains N integers, ci (1 ≤ ci ≤ M), the costume he will be wearing in party i. He will attend the party 1 first, then party 2, and so on.

There is a blank line before each test case.

Output

For each test case, output the minimum number of required costumes. Look at the output for sample input for details.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The game of Yahtzee involves 5 dice, which are thrown in 13 rounds. A score card contains 13 categories; each round may be scored in a category of the player's choosing, but each category may be scored only once in the game. The 13 categores are scored as follows:

• ones - sum of all ones thrown
• twos - sum of all twos thrown
• threes - sum of all threes thrown
• fours - sum of all fours thrown
• fives - sum of all fives thrown
• sixes - sum of all sixes thrown

• chance - sum of all dice

• three of a kind - sum of all dice, provided at least three have same value
• four of a kind - sum of all dice, provided at least four have same value
• five of a kind - 50 points, provided all five dice have same value
• short straight - 25 points, provided four of the dice form a sequence (that is, 1,2,3,4 or 2,3,4,5 or 3,4,5,6)
• long straight - 35 points, provided all dice form a sequence (1,2,3,4,5 or 2,3,4,5,6)
• full house - 40 points, provided three of the dice are equal and the other two dice are also equal. (for example, 2,2,5,5,5)

Each of the last six categories may be scored as 0 if the criteria are not met.

The score for the game is the sum of all 13 categories plus a bonus of 35 points if the sum of the first six categores (ones to sixes) is 63 or greater.

Your job is to compute the best possible score for a sequence of rounds.

Input

Each line of input contains 5 integers between 1 and 6, indicating the values of the five dice thrown in each round. There are 13 such lines for each game, and there may be any number of games in the input data.

Output

Your output should consist of a single line for each game containing 15 numbers: the score in each category (in the order given), the bonus score (0 or 35), and the total score. If there is more than one categorization that yields the same total score, any one will do.

Sample Input  Download

Sample Output  Download

Tags

Discuss