Description

Every person's blood has 2 markers called ABO alleles. Each of the markers is represented by one of three letters: A, B, or O. This gives six possible combinations of these alleles that a person can have, each of them resulting in a particular ABO blood type for that person.

Likewise, every person has two alleles for the blood Rh factor, represented by the characters + and -. Someone who is ``Rh positive" or ``Rh+" has at least one + allele, but could have two. Someone who is ``Rh negative" always has two - alleles.

The blood type of a person is a combination of ABO blood type and Rh factor. The blood type is written by suffixing the ABO blood type with the + or - representing the Rh factor. Examples include A+, AB-, and O-.

Blood types are inherited: each biological parent donates one ABO allele (randomly chosen from their two) and one Rh factor allele to their child. Therefore 2 ABO alleles and 2 Rh factor alleles of the parents determine the child's blood type. For example, if both parents of a child have blood type A-, then the child could have either type A- or type O- blood. A child of parents with blood types A+ and B+ could have any blood type.

In this problem, you will be given the blood type of either both parents or one parent and a child; you will then determine the (possibly empty) set of blood types that might characterize the child or the other parent.

Note: an uppercase letter ``Oh" is used in this problem to denote blood types, not a digit (zero).

Input

The input consists of multiple test cases. Each test case is on a single line in the format: the blood type of one parent, the blood type of the other parent, and finally the blood type of the child, except that the blood type of one parent or the child will be replaced by a question mark. To improve readability, whitespace may be included anywhere on the line except inside a single blood type specification.

The last test case is followed by a line containing the letters E, N, and D separated by whitespace.

Output

For each test case in the input, print the case number (beginning with 1) and the blood type of the parents and the child. If no blood type for a parent is possible, print ``IMPOSSIBLE". If multiple blood types for parents or child are possible, print all possible values in a comma-separated list enclosed in curly braces. The order of the blood types inside the curly braces does not matter.

The sample output illustrates multiple output formats. Your output format should be similar.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A seaport container terminal stores large containers that are eventually loaded on seagoing ships for transport abroad. Containers coming to the terminal by road and rail are stacked at the terminal as they arrive.

Seagoing ships carry large numbers of containers. The time to load a ship depends in part on the locations of its containers. The loading time increases when the containers are not on the top of the stacks, but can be fetched only after removing other containers that are on top of them.

The container terminal needs a plan for stacking containers in order to decrease loading time. The plan must allow each ship to be loaded by accessing only topmost containers on the stacks, and minimizing the total number of stacks needed.

For this problem, we know the order in which ships must be loaded and the order in which containers arrive. Each ship is represented by a capital letter between A and Z (inclusive), and the ships will be loaded in alphabetical order. Each container is labeled with a capital letter representing the ship onto which it needs to be loaded. There is no limit on the number of containers that can be placed in a single stack.

Input

The input file contains multiple test cases. Each test case consists of a single line containing from 1 to 1000 capital letters representing the order of arrival of a set of containers. For example, the line ABAC means consecutive containers arrive to be loaded onto ships A, B, A, and C, respectively. When all containers have arrived, the ships are loaded in strictly increasing order: first ship A, then ship B, and so on.

A line containing the word end follows the last test case.

Output

For each input case, print the case number (beginning with 1) and the minimum number of stacks needed to store the containers before loading starts. Your output format should be similar to the one shown here.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are the chief designer of a road race that will be held in a hilly area. The racecourse consists of N connected straight line segments; that is, the end of the k th segment coincides with the beginning of the (k + 1) st segment. During planning, these segments are laid out on a planar surface, so 2-dimensional Cartesian coordinates identify the endpoints. The first segment begins at the origin. Figure 1 shows the planar view of a racecourse with 6 segments.

The actual race is run on the side of a hill. For simplicity, assume the hill makes an angle Θ with the horizontal plane, as illustrated in Figure 2.

The plane of the hill and the horizontal plane intersect in the y -axis. Each 2-dimensional Cartesian coordinate (x_i, y_i) corresponds to a 3-dimensional form (x_i^', y_i^', z_i^') , with z_i^' representing the height of the endpoint of the i th linear segment. The height of the origin is 0.

This particular race is intended for novice drivers, so the racecourse must not include any segments that require downhill travel. That is, if the height of the endpoint of segment k is z_k^' , then the height of the endpoint of each segment after segment k must not be less than z_k^' . Formally we can write z_k^'≤z_m^' , for m≤k .

If a proposed racecourse includes downhill segments, it might be possible to transform it into a racecourse with no downhill segments by rotating the planar view of the entire course about the origin, without changing the angle between consecutive pairs of segments. However there may be proposed racecourses that cannot be made acceptable by such a rotation.

In this problem you must determine if a proposed racecourse is acceptable (that is, if it does not contain any downhill segments). If it is not acceptable, you must determine the minimum angle through which the racecourse must be rotated to make it acceptable, if that is possible.

Input

 The input consists of multiple test cases. Each test case is a description of a proposed racecourse and the slope of the hillside on which it will be run. The first line of each description contains two integers N (1 ≤ N ≤ 10000) and θ (0^o≤ θ ≤45^o) . N denotes the number of segments in the course and θ denotes the angle (in degrees) that the hillside makes with the horizontal plane. Each of the next N lines contains a pair of integers (x_i, y_i) , (1≤i≤N) , which are the endpoints of the linear segments comprising the racecourse. The first segment begins at the origin, and segment k + 1begins at the endpoint of segment k . No segment has zero length.

Output

 For each test case, print a line containing the test case number (beginning with 1). If the proposed course is acceptable without rotation, print ``Acceptable as proposed". If the course is not acceptable as proposed, but can be made acceptable by rotating it about the origin, print ``Acceptable after clockwise rotation of X degrees" or ``Acceptable after counterclockwise rotation of X degrees". The value X should be an unsigned number. For our purposes, a clockwise rotation would rotate the positive y -axis toward the positive x -axis. If both a clockwise and a counterclockwise rotation can make the course acceptable, choose the one with the smaller angle. If both rotations have the same angle, then choose the clockwise rotation. If the course cannot be made acceptable by any rotation, print ``Unacceptable". Display the angles of rotation rounded to two fractional digits.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 Lately, there is one serious problem with Panda Land Safe Box: several safes have been robbed! The safes are using old 4-digits rolling lock combination (you only have to roll the digit, either up or down, until all four of them match the key). Each digit is designed to roll from 0 to 9. Rolling-up at 9 will make the digit become 0, and rolling-down at 0 will make the digit become 9. Since there are only 10000 possible keys, 0000 through 9999, anyone can try all the combinations until the safe is unlocked.

• Initially the digits are at 0000.
• Keys can be unlocked in any order, by setting the digits in the lock to match the desired key and then pressing the UNLOCK button.
• A magic JUMP button can turn the digits into any of the unlocked keys without doing any rolling.
• The safe will be unlocked if and only if all the keys are unlocked in a minimum total amount of rolling, excluding JUMP (yes, this feature is the coolest one).
• If the number of rolling is exceeded, then the digits will be reset to 0000 and all the keys will be locked again. In other word, the state of the lock will be reset the cracking is failed.

Input

 The first line of input contains an integer T , the number of test cases follow. Each case begins with an integer N (1≤N≤500) , the number of keys. The next N lines, each contains exactly four digits number (leading zero allowed) representing the keys to be unlocked.

Output

For each case, print in a single line the minimum number of rolls needed to unlock all the keys.

• Turn 0000 into 1111, rolls: 4
• Turn 1111 into 1155, rolls: 8
• Jump 1155 into 1111, we can do this because 1111 has been unlocked before.
• Turn 1111 into 5511 rolls: 8

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In Jollybee Chess Championship 2008, there are a number of players who have withdrawn themselves from the championship of 64 players (in this problem, we generalized it into 2^N players). Due to the nature of the competition, which is a regular knock-out tournament, and also the short notice of the withdrawals, some matches had been walkover matches (also known as a w/o, a victory due to the absent of the opponent).

Input

 The first line of input contains an integer T , the number of test cases to follow. Each case begins with two integers, N (1≤N≤10) and M (0≤M≤2^N) . The next line contains M integers, denoting the players who have withdrawn themselves right before the tournament. The players are numbered from 1 to 2^N , ordered by their position in the tournament draw.

Output

 For each case, print in a single line containing the number of walkover matches.

Sample Input  Download

Sample Output  Download

Tags

Discuss