Description

  Farmer Jiang has n (1 ≤ n ≤ 200) cows. He loves the cows so much that for every single cow he prepares a huge “food court” – actually it’s an area fulfilled with foods and drinks. There are exactly n food courts, with distinct themes.

Everyday Farmer Jiang takes his cows to the food courts and put exactly one cow in one food court. He knows that some cows is favoring with some specific food court. He does not want to see cows feeling sad, so he decided only taking the cows into one of their favored food courts.

In how many ways that Farmer Jiang can let his cows pick favored food court and each food court is having at most one cow? Farmer Jiang knows that there are always less than 200,000 possible configurations in total.

Input

 The file begins with an integer T (T ≤ 25) indicating the number of test cases follows. For each test case, first line contains two integers n, m (1 ≤ n ≤ 200, 1 ≤ m ≤ n^2). Each of the next m lines contains 2 integers u, v (1 ≤ u, v ≤ n) means that u-th cow loves v-th food court. You may assume each (u, v) pair in a single test case never occurs more than once. There may be white spaces and empty lines everywhere in the input file.

Output

For each test case, please output “Case #x:” with x being the case number starting from 1 and output the number of total ways.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

  There was an ancient encryption method called ‘Vigenère cipher’. The one who wants to read a message encrypted need a secret word, the key to the plaintext. The encryption method is shown below. Your task is to write a program that can decode a set of characters into a valid string. Of course, keys are given.

Let   A=0, B=1, C=2 … Z=25, add operation of two character is to convert each of them into numbers. The sum of two characters is the sum of two numbers modulo 26 and converts it back to character.

Ex: T=19   S=18

T+S = 19+18(mod 26) = 11 = L

Vigenère cipher involves adding the plaintext to a letter of duplicated key. For Example,

Plaintext:   this is a test message

Key:  sesame

Input

There are several test cases.

The first line of each case is a string, key. All keys are in capital alphabet set ‘A’ – ‘Z’.

The second line to the end of each test case is cipher-text you should decode.

Each test case is separated by a single ‘#’ symbol in a line.

You have to do nothing to the words without capital alphabet set ‘A’ – ‘Z’, in another words, ignore those symbol not in the set.

Output

For each test, output several lines of plaintext. Each case is separated by a blank line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

  Gray Code is a binary numeral system where two successive values differ in only one bit. The n-bit-width gray code is the sequence consisting of numbers between 0 and 2^n-1. 

For example, 2-bit-width gray code is the sequence of {00, 01, 11, 10}. 3-bit-width gray code is the sequence of {000, 001, 011, 010, 110, 111, 101, 100}.

Now, we want you to construct the n-bit-width gray code by using the following algorithm.

1. If n = 1, Return {0,1}
2. Let S1 be the sequence of Gray(n-1).
3. Let S2 be the reverse of S1.
4. Add “0” to the head of every element in S1.
5. Add “1” to the head of every element in S2.
6. Return S1 + S2. 

Input

The input includes multiple test cases. 

In each test case, the first line contains one integer n. 

1 ≤ n ≤ 11

Output

The multiply lines contains 2^n integers, which indicate the n-bit-width gray code.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

  The king of the Sky-Dragon Kingdom likes the trading of houses. If there are some houses on sell, he buys the houses and sells them at high price. If there are no houses on sell, he will buy some land to build houses and then sell all them.

One day, the king wants to do something interesting. Since he loves the business transaction between houses so much, he decides to hold a big business that all people in the kingdom to trade their houses between each other.

There are N people in the kingdom, all they have his own house. There are K types of house, and the type of the each N houses is one of them.

In order to make sure that the big trading business is going on well, the kings make the price of each type of house. All the price of the N houses should comply with the rule of the king. After making the prices, the king will first buy all the N houses and sell them to the N people with the same price.

To avoid people unhappy, the N people give their preference list of the types of house. And the king wants to make prices of each type of house such that all N people each can buy a house and all houses are sold. And for each people, the type of the house he buys is in his preference list and it's the favorite type in the types whose price is no more than his originally own house. That is, after obtaining the money by selling his house, he buys the house of favorite type in all the types he can pay with the money.

Please write a program to help the king that gives the type of house each N people own, and their preference list, tell the king if it's possible to make a price of each type of house?

Input

The first line of the input file contains an integer T (T ≤ 20) indicating the number of

test cases. For each test case, the first line contains two integers N and K (1 ≤ N,K ≤ 30000), the number of people and number of types. The types are numbered from 1 to K. In the i-th line of following N lines, the first integer is the type of his own house of i-th people, the second integer mi (1 ≤ mi  ≤ 50) is the length of his preference list and following mi integer are the types of his list start from the favorite one in order.

Output

For each test case, output 'Y' if it's possible to make a price for each type in a

single line. Otherwise output 'N'.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Robot Lab is a lab filled with a lot of NPCs. In the lab, there is more devices needed power. Therefore, there is two power supply lines x=0 and y=0.

You need to buy some horizontal or vertical cables to connect these devices to one of the power supply lines. But you can't connect two cables. It means you should connect the devices to the power supply line "directly" with the cable. What is the minimum length of the total cables you buy? To simplify the problem, we guarantee every two devices must be at different x-coordinate and different y-coordinate.

Input

The input includes multiple test cases. 

In each test case, the first line contains one integer n. 

In the next n lines, every line contains two integers xi, yi.

1 ≤ n ≤ 100

-10000 ≤ xi, yi ≤ 10000

Output

The one line contains one integer, which indicates the minimum value of the sum.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Tetris Battle is a hot and funny game on the that you can train your skill and challenge your friend. 

At the last of the story, you will receive the name that “God of Tetris” and everybody’s respecting. But this problem is not about Tetris Battle. 

We will talk the other funny game, “Step Mania”!

“Step Mania” is an engine of the music game.

For each meter, there is four floating up arrows, and we can use keyboard to “hit” it on fixed positions. And there is a system for rewarding, we called “Combo” if you hit arrows in continued meter and get extra score.

NOW there is a new “Step Mania EX” had at most 10 arrows you should hit for each meter.(It’s OK because the keyboard has 108 keys and you have ten fingers.)

You are an extreme player of the “Step Mania” and you can hit every arrow in every meter!

But your keyboard is so bad that is unlike your skill, it cannot detect the continued hits on same key.

Now there is a score for a song in “Step Mania EX”, what score you will have?

PS1. You have gotten one point if you hit an arrow and (#theNumberOfCombo-1) for bonus.

PS2. If the computer does not detect any arrow in a meter, the number of combo will be reset.

PS3. Though you will get higher score if you do not hit some arrow, you still hit EVERY arrow  because the spirit of “Step Mania” tell you not to do it!

PS4. At fact, it not yet sells.

PS5. You can buy the keyboard called “RealForce” and you can win the game easily though it’s  very expensive.

HINT: Each arrow hiting will have its bonus score.

For sample data,

you will get score as following:

1 0 0 1

0 2 2 0

0 X 0 1

1 X 1 0

HINT2:

If there a meter contains no arrow, you will not hit any key and the number of combos will be same such that it can be higher when you have a nice hiting in next meter.

Input

 There is multiple dataset, for each data:

The first line contains two integers n, m , which mean the number of meters and the number of the arrow type. (0 < n ≤ 10⁵, 0 < m ≤ 10)

The line 2 to the line n+1, each line has m numbers split by space means the arrows if the number is 1.

Output

Print out a line contains the number of the score for each dataset.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Don’t worry. It’s just a very simple problem. See the recursive function below.

The only thing you should do is to showand nothing else. Easy, right?

Input

There are several test cases. Each line contains one integer, n

Output

 For each test, output a line containing a single, (modulo 100000007).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Jobz is a special kid. He likes painting. One day, he paints a lot of segments in 1-D line with many color pens. In every round, he will choose one color c and one integer interval [xi, yi]. Then he draws the interval with the color. Now, we know what he did in every round. And we want to know the final result what 1-D line looks like. Please write a program to solve the problem.

Input

The input contains multiple test cases. The first line contains one integer n. In the next n lines, every line contains three integers ci, xi and yi. It represents he draw the interval [xi, yi] with the color ci in the i-th round.

n ≤ 100000

0 ≤ xi < yi ≤ 200000

ci is a 32-bit signed integer.

Output

Output every maximum-length intervals with the same color.

Sort them by the increasing order of the xi value.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

  The Evil Terran, Dreamoon Zero, is going to attack our planet!

As a smart cerebrate, you have dispatched the scouts for discover the status of the enemies. You discovered that the force of enemies are all small vanguards composed by “marine”, so the best way to bear them up is using the “baneling landmine”!

“Baneling” can see as a remote-controlled bomb, it can kill the enemies who are in the range of two blocks from the boom.

You propose to kill all Dreamoon’s vanguards by “baneling”, then Dreamoon probably cannot dispatch new troop to attack such that you can discuss the plan to defeat Dreamoon with other cerebrates.

Of course, you hope use the least “baneling” to ***** the goal.

Input

There are multiple test data, for each test data:

The first line contains two integer, H and W. (1 ≤ H, W ≤ 50 )

The following H lines, each line contains W characters, are meaning that the lineup of the enemies, “m” means “Marine” and “.” means nothing.

The next line contains a integer H’ (1 ≤ H’ ≤ 50) that you can have H’ x W sized place to put “Baneling”.

And the following H’ lines, each line contains W characters, are meaning that your place, ‘X’ means that the soil is too hard to put “Baneling” and “.” means you can put “Baneling” completely.

The enemies will move forward(v) by the speed of 1 block/second, you can control the time of the explosion of each baneling freely.

A block can put more than 1 “Baneling” and the explosion will not effect on other “Baneling”.

By the way, there are at most twenty marines.

Output

For each test case, output a line contains a integer that the minimum number of “Baneling” to kill all the enemies. If we cannot do it, please output “impossible”(Do need output the symbol of the double quote.)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

  Some day, Doraemon Hon sends you a new problem as homework. He designs an n*n chessboard and every grid is one of three states. States are “empty”, “star”, and “broken”. You can put the balls on the grids, whose state is “empty” or “star”. The problem is to find the maximum value of the balls you can put on the chessboard. You are easy to solve the problem. 

So, Doraemon Hon adds two constraints. One is that the number of the balls on the row i should be equal to the number of the balls on the column i. Another one is that you must put the ball on the “star” grid.

To get the higher grade, you should solve the problem quickly.

If he designs an chessboard with no solutions, please output “impossible”.

Input

The input includes multiple test cases. In each test case, the first line contains one integer n. In the following n lines, every line contains n characters.

1 ≤ n ≤ 40

‘C’ means the “star” grid

‘/’ means the “broken” grid

‘.’ means the “empty” grid 

Output

The one line contains one integer, which indicates the maximum value.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

  The king of the Sky-Dragon Kingdom likes the trading of houses. If there are some houses on sell, he buys the houses and sells them with high price. If there are no houses on sell, he will buy some land to build houses and then sell them.

One day, the king buys some houses and wants to sell some of them as a house set together. And he wants the price of this set as high as possible.

Each house has its profit pi and cost ci that if we add a house into our house set, the price of the set will increase pi and decrease ci. Moreover, for some pair of house i and j, if we pick one of them, but not another, that is, we sell them separately, the price of the set will decrease Si,j.
And for some personal interest of the king, some houses must be included in the set to sell. Please write a program to help the king that gives pi, ci, 1 ≤ i ≤ N of his N houses, and the costs Si,j between some pair of houses. Please compute the highest price of a set of houses.

Input

  The first line of the input file contains an integer T (T ≤ 5) indicating the number of testcases. For each test case, the first line contains three integers N (1 ≤ N ≤ 200) and M, K (0 ≤ K ≤ N) represents the number of house, the number of pair that they have separation cost and the number of houses must be included in the set. Following N lines each has two positive integer

pi and ci (0 ≤ pi, ci ≤ 10000) . And next M lines each contains three integer i, j, Si,j (1 ≤ i, j ≤ N, 1 ≤ Si,j ≤ 10000) represent that there is a separation cost Si,j between house i and house j. Then there is one integer in each next K lines represent the number of houses must be included in the set.

Output

For each test case, output the highest price of a set of house. Output 0 if there are no set with positive price

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Here is a well-known game, ‘ 彈水阿給’（=瘋狂阿給=爆爆王). This is very similar to Bomber Man. The range of explosion of each water-ball is a cross shape on the map, and it will trigger any water-ball on the path of that cross.

Illustrated by following pictures:

,

Now you are in this intense “Rising Green Pepper Contest”, trying to play this exciting game. We redefined the rule as following:

0. You are playing on an N * M map. There’s no obstacles on that map, only several  placed water-balls.

1. Assume that every water-ball have infinite explosion range, that is to say, it would explode until the bound of the map.

2. The horizontal explosion of the water-ball will trigger water-balls on the same row, while doing no damage.

3. The vertical explosion of the water-ball will NOT trigger water-ball on the same column, while bringing damage.

Now things you are trying to do is:

0. Choose several water-balls to make them explode, and the number of choosing water-balls should be a minimum.

1. The total DAMAGE range should cover the whole map.

2. We want to be eco-friendly, so the DAMAGE range cannot be overlapped, or we would waste water.

Input

There are several testcases.

The first line of each testcases indicates N, M, which represents an N * M map.

Following will be N lines, each consists of M number(0 or 1), representing the state of the map. 0 means null, while 1 means water-ball.

1 <= N,M <= 100

Output

Print a positive integer, the minimum number of your choose.

If the goal cannot be achieved, print -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss