Description

You must write a program that simulates placing spherical balloons into a rectangular box.

The simulation scenario is as follows. Imagine that you are given a rectangular box and a set of points. Each point represents a position where you might place a balloon. To place a balloon at a point, center it at the point and inflate the balloon until it touches a side of the box or a previously placed balloon. You may not use a point that is outside the box or inside a previously placed balloon. However, you may use the points in any order you like, and you need not use every point. Your objective is to place balloons in the box in an order that maximizes the total volume occupied by the balloons.

You are required to calculate the volume within the box that is not enclosed by the balloons.

Input

The input consists of several test cases. The first line of each test case contains a single integer n that indicates the number of points in the set (1 ≤ n ≤ 6). The second line contains three integers that represent the (x, y, z) integer coordinates of a corner of the box, and the third line contains the (x, y, z) integer coordinates of the opposite corner of the box. The next n lines of the test case contain three integers each, representing the (x, y, z) coordinates of the points in the set. The box has non-zero length in each dimension and its sides are parallel to the coordinate axes.

The input is terminated by the number zero on a line by itself.

Output

For each test case print one line of output consisting of the test case number followed by the volume of the box not occupied by balloons. Round the volume to the nearest integer. Follow the format in the sample output given below.

Place a blank line after the output of each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The company Pacific Island Net (PIN) has identified several small island groups in the Pacific that do not have a fast internet connection. PIN plans to tap this potential market by offering internet service to the island inhabitants. Each groups of islands already has a deep-sea cable that connects the main island to the closest internet hub on the mainland (be it America, Australia or Asia). All that remains to be done is to connect the islands in a group to each other. You must write a program to help them determine a connection procedure.

For each island, you are given the position of its router and the number of island inhabitants. In the figure, the dark dots are the routers and the numbers are the numbers of inhabitants. PIN will build connections between pairs of routers such that every router has a path to the main island. PIN has decided to build the network such that the total amount of cable used is minimal. Under this restriction, there may be several optimal networks. However, it does not matter to PIN which of the optimal networks is built.

PIN is interested in the average time required for new customers to access the internet, based on the assumption that construction on all cable links in the network begins at the same time. Cable links can be constructed at a rate of one kilometer of cable per day. As a result, shorter cable links are completed before the longer links. An island will have internet access as soon as there is a path from the island to the main island along completed cable links. If mi is the number of inhabitants of the ith island and ti is the time when the island is connected to the internet, then the average connection time is:

Input

The input consists of several descriptions of groups of islands. The first line of each description contains a single positive integer n, the number of islands in the group (n ≤ 50). Each of the next n lines has three integers x_i, y_i, m_i, giving the position of the router (x_i, y_i) and number of inhabitants m_i (m_i > 0) of the islands. Coordinates are measured in kilometers. The first island in this sequence is the main island.

The input is terminated by the number zero on a line by itself.

Output

For each group of islands in the input, output the sequence number of the group and the average number of days until the inhabitants are connected to the internet. The number of days should have two digits to the right of the decimal point. Use the output format in the sample given below.

Place a blank line after the output of each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Let x and y be two strings over some finite alphabet A. We would like to transform x into y allowing only operations given below:

Deletion: a letter in x is missing in y at a corresponding position.

Insertion: a letter in y is missing in x at a corresponding position.

Change: letters at corresponding positions are distinct

Certainly, we would like to minimize the number of all possible operations.

Illustration

A G T A A G T * A G G C
| | |       |   |   | |
A G T * C * T G A C G C

Deletion: * in the bottom line
Insertion: * in the top line
Change: when the letters at the top and bottom are distinct

This tells us that to transform x = AGTCTGACGC into y = AGTAAGTAGGC we could be required to perform 5 operations (2 changes, 2 deletions and 1 insertion). If we want to minimize the number operations, we should do it like
A G T A A G T A G G C
| | |     |   |   | |
A G T C T G * A C G C
and 4 moves would be required (3 changes and 1 deletion).

In this problem we would always consider strings x and y to be fixed, such that the number of letters in x is m and the number of letters in y is n where n ≤ m.

Assign 1 as the cost of an operation performed. Otherwise, assign 0 if there is no operation performed.

Write a program that would minimize the number of possible operations to transform any string x into a string y.

Input

Input contains several datasets. Each dataset consists of the strings x and y prefixed by their respective lengths, one in each line.

Output

For each dataset, an integer representing the minimum number of possible operations to transform any string x into a string y.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You have been tasked to infiltrate a tight-lipped society for fun and profit: the ACM ICPC regional judges. Through the PC² ``submission" software, you know that classified information is accessible through the log-ins of the judges tasked to a particular ``regional site". However, you are not certain that any particular judge has access to all the relevant information, so several log-ins will be required. You have been handed down a list of usernames, and the passwords used can be derived from these usernames, as follows:

Input

The input will only have capital letters (denoting the usernames) and carriage returns. Each line (thus each username) will not be longer than twenty characters, and there will not be more than 12 ``judges" whose log-ins you will need to infiltrate. Strangely, no username uses any letter more than once.

Output

For each username, you must produce a line containing the password which that username uses. The password for a given username is determined from the twenty-one lexicographically consecutive permutations of the username, the eleventh (middle) of which is the username itself. For example, if the username is WORDFISH, the lexicographic permutations of WORDFISH contain, in order:

..., WOISHRFD, WOISRDFH, WOISRDHF, WOISRFDH, WOISRFHD, WOISRHDF, WOISRHFD, WORDFHIS, WORDFHSI, WORDFIHS, WORDFISH, WORDFSHI, WORDFSIH, WORDHFIS, WORDHFSI, WORDHIFS, WORDHISF, WORDHSFI, WORDHSIF, WORDIFHS, WORDIFSH, ...

The password is then the permutation among the twenty-one lexicographically consecutive permutations of the username which has the largest minimum absolute distance between consecutive letters (and the first amongst the lexicographically ordered, if several permutations have the largest minimum absolute distance), followed by that minimum absolute distance. For the username WORDFISH, the password is WORDHSFI3¹ .

¹ Disclaimer: The above story is completely fictional, and in no way represents any fact, regarding ACM regional judges, their passwords or world domination.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mobile phones have changed our lifestyle dramatically in the last decade. Mobile phones have a variety of protocols to connect with one another. One of the most popular networks for mobile phones is the GSM (Global System for Mobile Communication) network.

In a typical GSM network, a mobile phone connects with the nearest BTS (Base Transceiver Station). A BSC (Base Station Center) controls several BTSs. Several BSCs are controlled by one MSC (Mobile Services Switching Center), and this MSC maintains a connection with several other MSCs, a PSTN (Public Switched Telecom Network) and an ISDN (Integrated Services Digital Network).

This problem uses a simplified model of the conventional GSM network. Our simplified network is composed of up to fifty BTS towers. When in use, a mobile phone always connects to its nearest BTS tower. The area covered by a single BTS tower is called a cell. When an active mobile phone is in motion, as it crosses cell boundaries it must seamlessly switch from one BTS to another. Given the description of a map consisting of cities, roads and BTS towers, you must determine the minimum number of BTS switches required to go from one city to another.

Figure: Cities here are represented by squares and BTS towers by trapezoids. Solid lines are roads. The dotted lines show 9 different cells. The minimum number of switches required to go from city 1 to city 6 is (2+1+0)=3. Note that city 7 is isolated and cannot be reached.

Each tower and each city location is to be considered as a single point in a two-dimensional Cartesian coordinate system. If there is a road between two cities, assume that the road is a straight line segment connecting these two cities. For example, in the figure, traveling on the road from city 1 to city 2 will cross two cell boundaries and thus requires two switches. Traveling from city 2 to city 5 crosses one cell boundary and traveling from city 5 to city 6 requires no switch. Traveling this route from city 1 to city 6 requires three total switches. Note than any other path from city 1 to city 6 requires more than three switches. If there is more than one possible way to get from one city to another, your program must find the optimal route.

Input

The input file contains several test cases. The first line of each test case contains four integers: B(1 ≤ B ≤ 50), the number of BTS towers; C(1 ≤ C ≤ 50), the number of cities; R(0 ≤ R ≤ 250), the number of roads; and Q(1 ≤ Q ≤ 10), the number of queries. Each of the next B lines contains two floating-point numbers x and y, the Cartesian coordinates of a BTS tower. Each of the next C lines contains two floating-point numbers x_i, y_i that indicate the Cartesian coordinates of the ith city (1 ≤ i ≤ C). Each of the next R lines contains two integers m and n (1 ≤ m, n ≤ C), which indicate that there is a road between the m-th and the n-th city. Each of the next Q lines contains two integers s and d (1 ≤ s, d ≤ C), the source and destination cities.

No coordinate will have an absolute value greater than 1000. No two towers will be at the same location. No two cities will be at the same location, and no city will lie on a cell boundary. No road will be coincident with a cell boundary, nor contain a point lying on the boundary of three or more cells.

The input will end with a line containing four zeros.

Output

For each input set, you should produce Q + 1 lines of output, as shown below. The first line should contain the number of the test case. Q lines should follow, one for each query, each containing an integer indicating the minimum number of switches required to go from city s to city d. If it is not possible to go from city s to city d, print the line `Impossible' instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss