Description

  Alexander was a strict king. He asked the army not only had to win but defeat the enemy in the way he wanted. Because of stern discipline, the force he had was fighting and winning repeatedly.

  One of training was marching on a grid map. The army was on the northwestern square at first, and he gave some orders to the army. They would move into the southeastern square in the end. Alexander only gave them two types of orders: go east or go south. Then they would move along the direction to the next adjacent square on the map. Since Alexander would boil over when they made any mistake and probably killed somebody, they moved as Alexander’s commands in order to survive.

  However, the map was not safe since an ancient wizard set magic traps in some squares. Once the army moved into the trap, all of them would be wiped out. As a wisdom king, Alexander knew which square was not safe so that the force could pass the map without any casualty. You, as a loyal retainer, were asked to count the number of ways to pass through the map.

Input

   The first line is an integer T followed by T test cases. Each case will start with two integers N and M represented the number of row and column in a map. The next line is an integer K followed by K positions (r_i, c_i) in next K lines contained traps on the map.

   T < 20 and 1 < N, M < 18

   Notice that the first sample input is corresponding to the example above.

Output

   For every case, output the case number and the number of way to pass through the map. See sample output for more details.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

  Weather reporting is a tough job.  Most of time, it is too hard to predict whether it will rain 2 weeks later even with the most powerful computer system since the atmosphere is a typical chaos system.

  Modeling is a typical way to solve such a complex system.  In today’s case, we check whether it rains for the past 5 days and determine the probability that the 6^th day rains.  You are given the rainfall probability of the 1^st, 2^nd, 3^rd, 4^th, and 5^th day, and have to answer the rainfall probability of the N^th day.

  The predicted rainfall probability is a linear combination of the past 5 days. i.e., the rainfall probability of the N^th day:

P(N) = a₁×P(N-5) + a₂×P(N-4) + a₃×P(N-3) + a₄×P(N-2) + a₅×P(N-1).

  Given the number N, please answer the corresponding rainfall probability P(N) of the N^th day. 

Input

The first line of input contains a positive integer T, T ≤ 10, which is the number of cases.

For each case, there are 3 lines.

There are 5 non-negative real numbers in the first line, denote the rainfall probability of day 1, day 2, day 3, day 4, and day 5. All probabilities are between 0.0 and 1.0.

The second line also contains 5 non-negative real numbers, which are a₁, a₂, a₃, a₄, a₅. a_{1 +} a_{2 +} a_{3 +} a_{4 +} a₅ = 1.0

There is only one integer N, 1 ≤ N ≤ 100, denoting the N^th day.

Output

For each input case, output a real number with one digit after the decimal point as P(N).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

  Dr. Hon is an extraordinary researcher in indexing. As the best programmers of his students, you are given a task to help his research. First, you should have some basic knowledge of what his reaching area.

  Given a string T with N characters, we define “suffixes” of T as the strings “start at every possible character, and ends until T ends”. For example, for T=”NTHU-ZZ”, all suffixes of S are:

    S₁=”NTHU_ZZ”,
    S₂=”THU_ZZ”,
    S₃=”HU_ZZ”,
    S₄=”U_ZZ”,
    S₅=”_ZZ”,
    S₆=”ZZ”,
    S₇=”Z”,
    S₈=””.

  We can compare every 2 suffixes in lexical order. For example, S₃<S₂ because ‘H’<’T’. If suffix S_i ends earlier before S_j while comparing, S_i is smaller. For example, S₇<S₆ and S₈ is the smallest suffix.

  For a string T, we will transform it to another string T’, which composed of also N characters, either ‘S’ or ‘L’. If S_i<S_i+1, the i^th character of T’ is ‘S’; if S_i>S_i+1, the i^th character of T’ is ‘L’.

  Given a string T, your task is to answer what the corresponding T’ is.

Input

There are several cases. Each case contains one line of string, the string is composed of the character set {A~Z, a~z, 0~9, _ }, so there will be no any spaces in the input.

The end of input will be a line contains only 1 character ‘#’.

Each case will not exceed 100,000 characters, and there will be no more than 100 cases.

Output

For each case T, output the T’ in a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The graduate season has coming. As a gift for his girlfriend, David Huffman wants to build a golden chain.  After hard trying to look for cheap chains, he has gathered several chains in the same style.  And now, he has to link these chains into one chain.

The store charges for every welding and only two chains can be linked together. Any time two chains are linked, the length of new chain is the sum of two chains. If David wants to link N chains, he must link N-1 times. You might be guessing how the store charges for linking 2 chains. As most of you are thinking, if the length of the first golden chain is L₁ and the length of the second golden chain is L₂, linking these 2 chains will take David (L₁+L₂) dollars.

Since David wants to save money, he wants to know what the cheapest way to link all chains into one is.

Then, what is the cheapest way to link all chains? Only follow an easy rule. Pick up the shortest 2 chains, and link them together until there is only one chain are left. Just like the Huffman tree and Huffman code.

Input

The first line in the input file is an integer T( ≤ 20) followed by T test cases. Each test case describes the chains David purchases. The description consists of two parts:

1. The first part is an integer N( 1 ≤ N ≤ 40,000) describing the number of chains he purchases in a line.
2. There are N integers L₁, L₂, ..., L_N, describing the length of N chains in N lines for each of them.

Output

For each test case, output the cheapest cost that David need to spend in a single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In this problem, you are to solve a game which is composed of numbers on cards and a board.

Given a board which contains 2×N grids and 2N cards which are written the numbers 1~2N.  These grids are named a₁, b₁, a₂, b₂, …, a_N, b_N.  The rules of the game are listed as following:

1. Put these 2N cards onto these 2N grids.
2. For each adjacency pair of grids, i.e. (a_i, b_i), (a_i, a_i+1) or (b_i, b_i+1), the sum of numbers on cards should be a prime number.
3. After you finishing put all cards on the board, your solution is presented by listing the cards on a₁, a₂, …, a_N, b₁, b₂, …, b_N. If there are more than 1 solution, the solution starting with smaller number is better.

Given the number N, please output the best solution.

In mathematics, a prime number is a nature number that can only be divided by 1 and itself.

Input

The first line contains one positive integer T, T ≤ 10, denoting the number of cases.

There are T lines following, each line contains one positive integer denoting N for this case. N ≤ 10.

Output

For each case, there are 2 lines for output. The first line contains N integers, which are a₁, a₂, …, and a_N, separated by a space. The second line contains N integers, which are b₁, b₂, …, and b_N, also separated by a space.

There are no spaces at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

  There are so many buildings constructing in our campus! Instead of constructing a complicated structure, a modern building is made up of square modules, and every room is in the same shape and with same size. Following figure show a 3×4 model.

  Now we want to set up a conveyor belt to put some stuff onto it. In every floor, there are two special rooms that must be the beginning and terminal of conveyor belt. The start room is at the northern-west corner, and the end room is at the southern-west corner. Because of the reachability and reduce cost, the conveyor belt has to pass through each room once and only once.

  It’s important to know whether it is possible to have such configuration, so they ask you to answer it. Moreover, they also want to know how many ways to achieve such configuration. Following is an 3×3 example that has two ways.

Input

  There are no more than 5,000 test cases. Every test case contains two integers, n and m, representing a n × m model, where 2 ≤ n ≤ 4, 1 ≤ m ≤ 10⁹.

Output

  Output the number of way to achieve such configuration. Since the number maybe very large, you should take modulo by 7,777,777.If there is no such configuration, output “Impossible”.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

   Monkey Hunter is an interplanetarily renowned online game. It provides a platform for all kinds of player, and the role they controlled can be stronger and stronger by making their effort on it. Players can get virtual props by completing some missions or defeating monkeys. The harder mission you complete, the rarer props you get.

   They enjoy hunting in Monkey Hunter not only because of the game realistic senses, but the cooperation between players provides an almost real way to interact. Players have to talk to each other to make an efficient communication; otherwise they might have great difficulty to complete a team mission. A team can be divided into several small groups, and each group can contain any the number of roles.

   In recently update, Monkey Hunter designed a new challenge “Paoxiao monkey” to be one of the most difficult challenges. Jelly’s team has spent a lot of time to challenge but they all failed. One of the failed reasons is the total power of defense in whole team is not high enough. When the two roles in the same group, there will be a bonus, additional increase or decrease in power of defense, due to the difference between the equipments, classes, races, and talents of two roles. The power of defense for whole team is the sum of all the characters’ power of defense and the sum of extra bonus.

  Fortunately, Jelly has setup an additional plug-ins to compute the bonus between the two roles, but he still doesn’t know the possible maximum power of his team. You should find out the maximum power of defense in a certain grouping configuration.

Input

  The input consists of multiple test cases. The first line of each test case contains an integer N (0 < N ≤ 12), which is the number of characters. The next line contains N integers dps₁, dps₂, …, dps_N, where dps_i represents i^th character’s power of defense. This line is followed by N lines, each of which contains N integers. The i^th integer at j^th line implies the bonus between i^th role and j^th role.

  The last test case is followed by a line containing a single zero. There should be no more than 30 test cases.

Output

  For each test case, print the case number (starting with 1) followed by the maximum power of defense for whole team. Follow the format of the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

  Walking around the campus has become a part of our life. We attend class in CS building, have a meal in restaurant, and go back to sleep in your dorm.

  Peter thinks that it takes too much time to move between two places. He always wants to reach a place as fast as possible. So he often cuts the corner between two places by passing lawn. However, it is harmful to walk on lawn. Since he doesn’t want to do more harm on lawn, Peter makes a trade-off. He hopes to reach destination without using more than a certain time, so he might not need to pass every short-cut. As a friend of Peter, you want to compute the minimum number of short-cut he has to take to encourage him.

Input

   There are no more than 50 test cases. The first line of each test case contains an integer n, indicating the number of places. (1 ≤ n ≤ 100) The parts are numbered from 1 to n. The second line contains an integer M, indicating the number of roads. Then M lines in the form "a b c", which mean there is a road between the a^th place and the b^th place and takes c minutes to walk along it. Then an integer S and S lines follow, describing the short-cuts with the same way as the roads. The next contains two integers indicating the places to which the start and the destination. The last line contains one integer T, the time limit to reach the destination. (0 ≤ T ≤ 1,000,000,000)

   The roads and the shortcuts are all bidirectional. There is at most one road between any two places. There is at most one shortcut between any two places. The time cost of each road or shortcut do not exceed 1,500,000 but at least 1.

Output

   Output the minimum number of short-cuts Peter has to take in one line. If it’s impossible to reach on time, print “Impossible” in a single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Wireless communication has become a more and more popular issue in the EECS studies, even though almost all commercial applications are based on a “wired” backbone infrastructure. As the best engineer of the company Hexagonal Electrical eXample (HEX corp.), you are to solve the wire routing problem for the new wireless service of the company.

The HEX corp. is building a new wireless service in a city. As what we told you, the HEX corp. has decided where to build the Access Point (AP) for wireless communication. The APs are distributed depending on the population, geography, and some other issues, and then use the cable to connect them together. In order to keep the maintenance more easily, HEX corp. wishes to route the cables by the streets in the city. Except two ends of cable, any other parts on the cable are insulated. Therefore, two cables on the same street would not affect each other and not be merged into one cable.

The layout of streets in city is very special. There are 3 types of street, which are called type 1, type 2, and type 3. Within each type, streets are parallel. The distances between every 2 parallel streets are the same, and there must be 3 streets cross each intersection.

Any APs are built on the intersections of streets. Assume the length of each street segment is 1; the total cost of the routing is the sum of lengths of cables used. Any APs can be connected indirectly, i.e. if there is a cable connecting AP1 and AP2, and another cable connects AP2 and AP3, then AP1 and AP3 are connected.

You are to determine what is the minimum cost required to connect all APs, by telling the HEX corp. what is the minimum sum of lengths of cables required.

Input

There are several cases in the input. There is an integer T, T ≤ 100, in first line of input, which indicates the number of cases.

For each case following, the first line contains a number N, N ≤ 1000, which indicates the number of APs.

There are N lines following. For the i^th line of these lines, there are 3 integers, S_(i,1), S_(i,2), and S_(i,3), which indicate the streets of type 1, type 2, and type 3 which cross the intersection. All these numbers are between 1 and 1000.

Output

For each case, output one line with one integer to indicate the minimum cost of network.

Sample Input  Download

Sample Output  Download

Tags

Discuss