Description

"Otaku" is a Japanese term used to refer to people with obsessive interests, particularly anime,
manga, and video games. Otaku usually has much features such that you can recognize someone as
a otaku with those features.

Dr.Davidsu now want to do a research about Otaku. First he wants a program to help him.
The program should read the list of characteristics of many people and to determine how possible
they are Otaku.

Although Dr.Davidsu is a great programmer, but since he realizes so much knowledge about Otaku
with his research, now he also becomes a OTAKU!! So he only plays games day and night and could
not write program anymore. Please help the great Ota.. uh.. great Dr. Davidsu!!

Input

There are two positive integer N, M in the first line of input following N lines of the features of Otaku.
Each line has a distinct string describes the feature. And then there are M people's describing below.
In each people's data, first line there is a positive integer K which is the number of the people's characteristics
and K lines below are the K features of the people. 

Limits

1 <= N <= 10000
1 <= M <= 1000
1 <= K <= 1000

the string describes the feature of otaku or people is consecutive characters only contains uppercase
letter or underline char "_"  and no more than 16 characters.

Output

For each people, if more than half of its characteristics is a feature of OTAKU, then output 'Y'.
Otherwise output 'N' on each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Ordering

Background

Order is an important concept in mathematics and in computer science. For example, Zorns Lemma states: a partially ordered set in which every chain has an upper bound contains a maximal element. Order is also important in reasoning about the fix-point semantics of programs.
This problem involves neither Zorns Lemma nor fix-point semantics, but does involve order.

Problem

Given a list of variable constraints of the form A < B, you are to write a program that prints all orderings of the variables that are consistent with the constraints. For example, given the contraints A < B and A < C there are two orderings of the variables A, B and C that are consistent with these constraints: ABC and ACB.

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 two lines: a list of variables on one line, followed by a list of constraints of the form A < B on the next line. Variables and contraints are separated by single spaces.
All variables are single character, upper-case letters. There will be at least two variables, and no more than 20 variables. There will be at least one constraint, and no more than 50 constraints. There will be no more than 300 orderings consistent with the contraints in a specification.

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.

All orderings consistent with the constraints should be printed. Orderings are printed in alphabetical order, one per line. Characters on a line are separated by a space. If no ordering is possible, the output is a single line with the word NO.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

These days, you can do all sorts of things online. For example, you can use various websites to make virtual friends. For some people, growing their social network (their friends, their friends' friends, their friends' friends' friends, and so on), has become an addictive hobby. Just as some people collect stamps, other people collect virtual friends.

Your task is to observe the interactions on such a website and keep track of the size of each person's network.

Assume that every friendship is mutual. If Fred is Barney's friend, then Barney is also Fred's friend.

Input

The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer F, the number of friendships formed, which is no more than 100 000. Each of the following F lines contains the names of two people who have just become friends, separated by a space. A name is a string of 1 to 20 letters (uppercase or lowercase).

Output

Whenever a friendship is formed, print a line containing one integer, the number of people in the social network of the two people who have just become friends.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Joko is taking part in a fire drill which is held by the Jakarta Fire Department to recruit new firemen. The drill is about rescuing volunteers (who act as unconscious people) trapped in a building in a limited time. The building has several floors, and the volunteers are scattered throughout the building. Each volunteer has points assigned to her. The fireman candidate should rescue volunteers through carrying them to the exit. The candidate will earn the assigned points for each volunteer he rescued.

Each floor of a building can be seen as a grid of cells. Each cell can be an obstacle, an empty space, a stair or an entry/exit point.

A candidate starts at the entry point which exists only at one single cell of the first floor of the building. The candidate can move to any adjacent non-obstacle cells (north, south, west or east) or climb up or down a stair in 1 second. The movement slows down to 2 seconds when the candidate carries a volunteer. When a candidate finds a volunteer, he may decide to rescue her or not, but if he decides to rescue her, he has to carry her back to the exit without stopping. He can only carry at most one volunteer at a time.

Joko has the floor plan of the test building. Help him plan his moves, so he can get the highest possible score.

Input

The first line of input contains an integer T (T<=100) denoting the number of case. Each case has five integers L (1<=L<=10), H (1<=H<=100), W (1<=W<=100), N (1<=N<=100) and S (1<=S<=10, 000) denoting the number of floors, height and weight of each floor, the number of unconscious people, and the given time respectively.

The next L blocks describe the map of each floor from the 1st floor to the L-th floor respectively. Each floor consists of H lines each contains W characters. Characters that may appear in each floor are:

``S" : The starting point, also serves as the exit point. There will be only one starting/exit point and it will appear in the first floor.
``X" : Obstacle, cell that cannot be visited (wall, fire, etc.).
``U" : Stair that connect to the upper floor. There will be a ``D" character at the same place in the upper level. This character will not appear in the highest level of the building.
``D" : Stair that connect to the lower floor. There will be a ``U" character at the same place in the lower level. This character will not appear in the lowest level of the building.
``." : Empty space, cell that can be visited.

The next N lines each contains four integers f_i (1<=f_i<=L), r_i (1<=r_i<=H), c_i (1<=ci<=W), pi (1<=pi<=1, 000) denoting the location of each volunteer (floor, row, column) and the point assigned to this volunteer respectively. You can assume that each volunteer will be located in empty space and no two volunteer occupy the same location.

Output

For each case, output in a line a single integer the highest point that he can earn by rescuing unconscious people within the given time.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In this problem, we will play with four 2 x 2 squared pieces, an 8 x 8 board, few obstacles and gravity(!!!).

Initially the board contains few obstacles and the 4 colored pieces randomly placed. An example of an initial configuration is shown in the above diagram. The black squares represent the obstacles and the 4 colored pieces are shown with labels A, B, C and D - (in order to help the colorblind people). Initially there is no gravity and thus the pieces remain at a steady position. We can enable `gravity' in any of the four directions to move the pieces. The pieces move in the direction of gravity. A piece continues to move until it hits an edge of the board, an obstacle or any other piece. The obstacles aren't affected by gravity and so remains in their initial position at all times. We can enable at most one `gravity' at a time. The gravitational direction can only be changed when all the pieces are static.

The diagram above shows the positions of the pieces after the `gravity' from the right is enabled.

How many different static states can be reached by enabling at least one `gravity'? Two states are different if there is at least once cell that has a different color. A static state is one in which all the pieces are steady!

Input

The first line of input is an integer T (T<=100) that indicates the number of test cases. Each case consists of 8 lines with 8 characters in each line. Every character will be from the set {A, B, C, D, ., #}. Dots(.) represent empty spaces, hashes(#) represent obstacles and the alphabets represents the pieces. The frequencies of each letter (A,B,C,D) will be exactly 4 and each letter will occupy positions so that they form squares of size 2 x 2. There is a blank line before every case.

Output

For each case, output the case number followed by the number of different static states that can be reached from the original position by enabling at least one ``gravity".

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

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

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

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

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