Description

Lucy loves stars very much. There are N (1 <= N <= 1000) stars in the sky. Assume the sky is a flat plane. All of the stars lie on it with a location (x, y), -10000 <= x, y <= 10000. Now, Lucy wants you to tell her how many squares with each of four vertices formed by these stars, and the edges of the squares should parallel to the coordinate axes.

Input

The first line of input is the number of test case.
The first line of each test case contains an integer N. The following N lines each contains two integers x, y, meaning the coordinates of the stars. All the coordinates are different.

Output

For each test case, output the number of squares in a single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

It's a game with two players. Given a dictionary of words, a word S chosen from the dictionary to start with, and a word T also chosen from the dictionary as the winning word, which will be described below, the two players take turns to choose a word from the dictionary, satisfying that the first letter of the chosen word is the same as the last letter of previous word. Each word could be chosen more than once.

Suppose they play exactly n rounds. At the last round, if the player (the first one if n is odd, the second one otherwise) chooses the winning word T, he wins. To your surprise that, the two players are not so clever that they choose words randomly.

Here comes the question. How many different ways will the first player win if they play no more than N rounds, among all the possible ways satisfying all the conditions above?

Input

An integer C, indicates the number of test cases.
Then comes C blocks, formatted like this:
An integer M, indicates the number of words in the dictionary, M <= 30.
M string consisting of only lowercase letters, represent the words in the dictionary. The length of each word is no more than 10. There are no duplicated words.
String S, the word to start with.
String T, the winning word.
A positive integer N, indicates the maximum number of rounds to play. N fits in a signed 32-bit integer.

Output

For each test case, print a line with an integer W, indicating how many possible ways the first player wins.
Output the answer modulo 10001.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Mr. Pote's shop sells beans now. He has N bags of beans in his warehouse, and he has numbered them with 1, 2, …, N according to their expired dates. The i-th bag contains Wi units of beans. For selling at retail makes only a little profit, Mr. Pote want to pack beans in small packets with certain size and sell them in packets. Here comes his packing way:

Suppose the size of the packet is P units. Firstly, Mr. Pote selects some bags (at least one) of beans with consecutive number in his warehouse. Then he takes out the beans from all selected bags, and puts them together on the desktop. To pack the beans, he take P units of beans from desktop and fill in a new packet each time, until the beans left are less than P units. Finally the beans left on the desktop are eaten by a lucky dog.

Mr. Pote doesn't want the dog eat too many beans, so he prefers to solutions that resulting no more than K units of beans eaten by the dog. Moreover, he also wants to pack as many packets as possible. Could you tell him how many packets he can pack at most without breaking his preference?

Input

On the first line of input, there is a single positive integer T <= 20 specifying the number of test cases to follow.
Each test case contains two lines.
There are three integers in the first line, N, P, K as described above. (0 < N, P < 1000001, 0 <= K < P)
Next follow a line with N integers W₁, W₂, ..., W_N. The i-th integers describes the amount of beans in the bags numbered i. (0 <= W_i < 32768)
Numbers are separated by spaces.

Output

For each test case you should output a single line containing "Case X: Y" (quotes for clarity) where X is the number of the test case (starting at 1) and Y is the maximum number of packets that Mr. Pote can pack following his way.
In case there's no solution avoiding the dog eats more than K units of beans, Y should be equal to -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Yes. Counting problem comes again.
Given a chess board of N*N (N<=500), how many ways are there to put N queens on it so that no queen can attack another?
Luckily this is not the problem you should solve in this contest. Instead, we have a much easier one here.
Given a chess board of N*N (N<=500), how many ways are there to put 2*N queens on it so that there are exactly two queens in each row and each column?
To make it even easier, we will consider one way to be the same with another if it can be transformed to the other one by swapping rows and swapping columns.

Input

The first line of the input is an integer T indicating the number of cases.
Line 2..T+1 will contain an positive integer N (N <=500) each.

Output

T lines containing your counting results respectively.
For the number may be very large, you just have to output its module by 1000007.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The Farey sequence F_n for any positive integer n is the set of irreducible rational numbers a/b with 0 < a < b <= n and (a, b) = 1 arranged in increasing order. Here (a, b) mean the greatest common divisor of a and b. For example:

          F₂ = {1/2}
          F₃ = {1/3, 1/2, 2/3}

Given two positive integers N and K, with K less than N, you need to find out the K-th smallest element of the Farey sequence F_N.

Input

The first line of input is the number of test case T, 1<=T<=1000. Then each test case contains two positive integers N and K. 1<=K⁹

Output

For each test case output the K^th smallest element of the Farey sequence F_N in a single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

One day, Tom traveled to a country named BGM. BGM is a small country, but there are N (N <= 100) towns in it. Each town products one kind of food, the food will be transported to all the towns. In addition, the trucks will always take the shortest way. There are M (M <= 3000) two-way roads connecting the towns, and the length of the road is 1.
Let SUM be the total distance of the shortest paths between all pairs of the towns. Please write a program to calculate the new SUM after one of the M roads is destroyed.

Input

The input contains several test cases.
The first line contains two positive integers N, M. The following M lines each contains two integers u, v, meaning there is a two-way road between town u and v. The roads are numbered from 1 to M according to the order of the input.
The input will be terminated by EOF.

Output

Output M lines, the i-th line is the new SUM after the i-th road is destroyed. If the towns are not connected after the i-th road is destroyed, please output “INF” in the i-th line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Uno is a famous card game played with a specially printed deck. It's very popular as a funny game in a party.
A so-called "official rules" is presented at the Wikipedia, but there are a lot of different extended rules all over the world according to their specific needs.

In this problem, you are required to obey our rules introduced below:
The Uno deck consists of cards of 4 colors: red(R), green(G), blue(B), and yellow(Y).
Each color has two kinds of cards, number cards and action cards.
The ranks in number cards are 0-9. There are 3 "action" cards in each color, labeled "skip"(S), "draw two"(D), and "reverse"(R).
The functions of the actions will be described afterwards.
For each color, there are two copies of each positive number card and action card, but only one zero card, producing 25 cards in total.
Besides, there are also special black action cards called "wild cards", "wild"(WC) and "wild draw four"(WF).
There are four "wild" and "wild draw four" cards each. Hence, there are 108 cards in total.
In this problem, a card is marked with an ID of two characters length, the first is the color (R, G, B, Y, W) while the second is the rank (0-9, S, D, R, C, F).

For example, the ID of red 2 is R2, the yellow reverse is YR, the wild cards are WC and WF.
Supposed there are n players numbered from 1 to n clockwise.
Before playing, players take turns(in the order of 1, 2, ... n) to pick seven successive cards from the stock.
The top card of the remaining stock is exposed to start the game, treated as if player 1 dropped that card.
The exposed card will never be WC or WF in this problem.
Then the game begins clockwise (next player is 2), or counter-clockwise (next player is n) if the top exposed card is a reverse.
At each turn, a player may drop a card from their hand that matches the color or rank of the top exposed card (e.g., if the top card is R3, you can drop R5 or G3;
if the top card is RD, you can drop R3 or GD) or play a WC.
What's more, if the player has a WF and no other legal cards to drop, he can drop the WF.
Then the card dropped just now becomes the top exposed card.
If a player has no legal cards, he must draw the top card of the stock and place it in his hand.
After dropping a single card or drawing, the next player clockwise takes a turn, or counter-clockwise when the reverse is in effect.
When a player drops down to only one card, that player is required to say "uno" to warn other players.
The game ends when a player drops all his/her cards, or the stock is emptied but the current player has to draw a card.
If the last card is an action card, the special effect still occurs.
When the game ends, all players count the number of points pertaining to the values of the cards in their hands.
Number cards worth the face value on them, colored special cards worth twenty, and wilds worth fifty, e.g., R2 worth 2, G0 worth 0, BD and YS worth 20, WC and WF worth 50.

The descriptions of the action cards:

Now here comes the problem.
There are N people playing Uno under the rules mentioned above. Given the sequence of the 108 cards of the stock, you are asked to simulate a Uno game.
At each turn, the player will always drop a card if permitted.
If there are more than one choices, the player will drop the card with the largest point.
If still a tie, he will choose the one whose ID is the smallest alphabetical order.
When a player drops WC or WF, he has to name a color.
The first time he will name red, the second time he will name green, the third time blue, the fourth time yellow, the fifth time red again, and so on.
When the game ends, you should output the final score of each player, and we also want to know how many times each player calls "Uno".

Input

The first line of the input file contains a single number: the number of test
cases to follow. Each test case has two lines:
The first line contains the number of players N , with 2<=N<=10.
The second line contains 108 IDs of the Uno cards, separated by one space.
Each ID is two characters long as introduced in the description above.

Output

For each test case, output two lines:
The first line are N integers, the ith integer is the final score of player i.
The second lines are also N integers, the ith integer shows how many times
player i calls "Uno".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There is a sea.
There are N islands in the sea.
There are some directional bridges connecting these islands.
There is a country called Country One located in Island 1.
There is another country called Country Another located in Island N.
There is a war against Country Another, which launched by Country One.
There is a strategy which can help Country Another to defend this war by destroying the bridges for the purpose of making Island 1 and Island n disconnected.
There are some different destroying costs of the bridges.
There is a prophet in Country Another who is clever enough to find the minimum total destroying costs to achieve the strategy.
There is an architecture in Country One who is capable enough to rebuild a bridge to make it unbeatable or build a new invincible directional bridge between any two countries from the subset of island 2 to island n-1.
There is not enough time for Country One, so it can only build one new bridge, or rebuild one existing bridge before the Country Another starts destroying, or do nothing if happy.

There is a problem: Country One wants to maximize the minimum total destroying costs Country Another needed to achieve the strategy by making the best choice. Then what’s the maximum possible result?

Input

There are multiple cases in this problem.
There is a line with an integer telling you the number of cases at the beginning.
The are two numbers in the first line of every case, N(4<=N<=100) and M(0<=M<=n*(n-1)/2), indicating the number of islands and the number of bridges.
There are M lines following, each one of which contains three integers a, b and c, with 1<=a, b<=N and 1<=c<=10000, meaning that there is a directional bridge from a to b with c being the destroying cost.
There are no two lines containing the same a and b.

Output

There is one line with one integer for each test case, telling the maximun possible result.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In physical simulations, video games and computational geometry, collision detection involves algorithms for checking for collision, i.e. intersection, of two given objects. Collision detection algorithms are a basic component of 3D video games. Without them, characters could go through walls and other obstacles.
Here comes an interesting problem, given a ball and a cuboid, you need to detect whether they collide. We say that two objects collide if and only if they share at least one point.

Input

The first line of input is the number of test cases.
Each test case contains two lines, the first line contains 24 integers X1, Y1, Z1, …, X8, Y8, Z8, representing the 8 vertexes of the cuboid. Vertexes are given in random order and you can make sure that all edges of the cuboid are parallel to coordinate axes; the second line contains 4 integers X,Y,Z,R representing the central point of the ball and its radius. All integers given are non-negative and will be less than 100000.

Output

For each case output "Yes" Or "No" on a single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Jerboas are small desert-living animals, which resemble mice with a long tufted tail and very long hind legs. Jerboas shelter in well-hidden burrows. They create two types of burrow: temporary and permanent. The temporary burrows are plain tubes while the permanent burrows are sealed with a plug of sand to keep heat out and moisture in.

As far as we know, jerboa burrows in the desert are connected with one-way tunnels. What's more, for some unknown reasons, it's true that start from any burrow, follows the tunnels you can not go back to the starting burrow.
Summer means last-minute of offers on good times, so of course jerboas could not stay behind. One day, a little jerboa Alice who lived in a temporary burrow S wants to migrate to a permanent one. There are different routes she can take, but Alice is so odd that she only selects those whose total travel distances is a multiple of K. Among all routes that Alice may select, we are interested in the shortest one. Can you help to find it out? Of course different routes may lead to different destinations.

Input

On the first line of input, there is a single positive integer T <= 20 specifying the number of test cases to follow.
Each test case starts with four integers in the first line: N, M, S, K.
N is the number of burrows in the desert (burrows are numbered with 1, 2, …, N);
M is the number of tunnels connecting the burrows;
S is where Alice lived and K is as described above.
(0 < N <= 1000, 0 <= M <= 20000, 0 < S <= N, 0 < K <= 1000)
The second line contains N characters each could be ‘T’ or ‘P’. The i-th character specifying the type of the burrow i. ‘T’ means temporary burrow, ‘P’ means permanent burrow. It’s guaranteed that the S-th character is ‘T’.
Next follow M lines, each line with 3 integers A, B, C. Specifying that there is a tunnel from burrow A to burrow B, and its length is C.
(0 < A, B <= N, A != B, 0 < C < 40000)

Output

For each test case you should output a single line containing "Case X: Y Z" (quotes for clarity) where X is the number of the test case (starting at 1) and Y is the length of the shortest route Alice can select and Z is the destination of the selected route.
Notice that burrow Z should be a permanent burrow.
In case there’s more than one solution, Z should be the minimum.
In case there's no solution, Y and Z should be both equal to -1.

Sample Input  Download

Sample Output  Download

Tags

Discuss