Description

In the Ancient Clash of Mystic Pandas (ACM Pandas) game, the player plays the role of a Panda Knight who needs to defend Panda Land by defeating evil Panda Wizards. As the wizards have special magical powers, they need to be defeated using specific types of Mystic Sticks (regular bamboo sticks are ineffective against them). To obtain a Mystic Stick, Panda Knight needs to craft it by infusing his regular bamboo stick with several different kinds of magic shards according to the known recipe for that particular type of Mystic Stick.

Normally, all kinds of shards can be purchased for 1 gold/piece from the Panda Magic Store (therefore Panda Knight will have no problem of acquiring the shards, as long as he has enough gold to buy them all from the Store). However due to the recent invasion, to conceal the shards from the incoming Panda Wizards, Panda Magic Store has packaged all the shards into inconspicuous Mystery Boxes. A Mystery Box contains a random piece of magic shard which type can be determined prior to buying and opening the box, which Panda Knight can also buy for the same price (1 gold/box).

As his Panda Knight character is not rich, Mr. Wah is concerned about the possibility that he unable to buy all the necessary shards due to not getting the required amount of a specific type of shard. He needs your help! Your task as Mr. Wah's best programmer friend is to compute the probability that he will be able to get all the shards and craft the Mystic Stick, so that he can plan his playing strategy accordingly. You can safely assume that all the required shards are available on the store via the Mystery Boxes, that the boxes will only contain the needed types of shard, and that each type of shard has equal probability of being contained inside any particular Mystery Box.

Input

The first line of input contains an integer T (1 <= T <= 100), the number of test cases follow. Each test case begins with two integers G and N (1 <= N <= G <= 32) in one line, denoting the amount of Panda Knight's gold and the number of needed magic shard types respectively. The next line contains N integers, denoting how many magic shards of each type (1 <= M₁ ... M_N <= 32; M₁ + ... + M_N <= G) are needed to craft the Mystic Stick.

Output

For each of the test cases, print the test case number followed by the probability (in percentage, correct to 6 decimal places – Mr. Wah is paranoid about this game) that Panda Knight will be able to craft the Mystic Stick, with the format as shown by the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a dictionary containing less than N = 20000 words labeled from 1 to N. Each word consists of lowercase characters (from 'a' to 'z') with arbitrary length. The total number of characters in the dictionary is at most 100,000. Your task is to answer at most Q = 100000 queries. Each query q_i is also a word (as defined above). For each query, you have to print the "Top 10" words in the dictionary with the following rules:

• All the words in the "Top 10" have to contain the substring q_i.
• All the words in the "Top 10" have to be sorted in this order:
  1. The words with shorter length come first, if they have equal length then
  2. The lexicographically smaller words come first, otherwise
  3. The words with smaller label come first.
• If the number of words in the dictionary that contains the substring q_i is less than 10 then print all the words otherwise, print only the top-10 words (note: the words are printed using their labels).
• If there is no word in the dictionary that contains the substring q_i then print "-1" (without the quotes).

Input

The first line contains the number N. The next N lines contains the N words in the dictionary (the i^th line is the word with label i). The next line contains the number Q followed by the Q lines containing the queries.

Output

For each query, print one line containing the labels of the "Top 10" words (separated by a space) in the dictionary using the rules defined above.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given N (3 <= N <= 10,000) non-collinear triplewise points on a 2-D plane, select K (3 <= K <= N) points and order them such that the ordered points form a simple K-sided polygon. A polygon is called simple if no pair of its sides cross each other.

Input

First line of the input contains a positive integer T (1 <= T <= 10), the number of cases. Follows afterwards are the description of each case. For each case, the first line contains two integers N and K. Each of Nfollowing lines contains two integers, xi, yi (1 <= xi, yi <= 1,000,000), one of the given points. For simplicity, all points are numbered from 1 to N according to the order of appearance in the input. There is no blank line separating each case.

Output

For each case, output K integers, each on a line, the selected points in the order how the K-sided simple polygon is constructed. If there are more than one possible ordered selection that fits the criteria, output any one. It is always possible to form at least one simple K-sided polygon. There is no blank line separating each case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

It is 2050 and human live with alien. There are two kind of alien: good alien and evil alien. Good alien were our friend because they help us to develop good technology for our earth. Evil alien were very very bad, they develop heavy and dangerous weapons that can destroy earth. Alien were very hard to kill because of their ultra regeneration skill. Luckily, we have developed a kind of bomb that can kill alien in an instant. This weapon is very expensive so we must use it wisely.

Given a map of 10 × 10, each element in the map will be:

• '.' represents empty region.
• 'g' represents good alien.
• 'e' represents evil alien.

Calculate how many evil alien that can be killed without killing any good alien, and how many bombs we need to do that. A bomb has a 3 × 3 area of effect, so all of the 8 adjacent neighbors will also be destroyed. You can put bomb anywhere in the map, even if there is an alien in that cell. For example,

e..
.Xe
..e

Bombing at X will kill three evil aliens.

Our spy has reported that the number of alien groups from each side is less than 16.

Input

First line in the input will be T (1 ≤ T ≤ 100) number of cases. Each case will have a map of 10 × 10 represent the city. Between each city will be separated by a blank line.

Output

For each case, output two numbers: a and b, where a is the maximum number of evil aliens that you can kill and b is the minimum number of bombs you need to do that.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two integers A and B that are not necessarily in base-10, find the smallest possible A + B in base-10.

For example,

A = 213, possibly base-4 (39 in base-10)
B = 4721, possibly base-8 (2513 in base-10)

A + B = 39 + 2513 = 2552

Input

First line of the input contains a positive integer T (1 <= T <= 100), the number of cases. Each case contains two positive integers A and B. A and B will contain at most 5 digits, each digit will be between 0 and 9, inclusive, and no leading zeroes.

Output

For each case, output an integer in base-10 denoting the smallest possible A + B.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Do you know Lotto? Lotto is a game of probability. Six numbers are drawn from a range of numbers (such as 42, 47, 47, 49, 51, and 54). Michigan, for instance, has a 6-out-of-47 game (6/47), meaning that six numbers are drawn from possible 47. Florida's Lotto is 6/53, meaning that six numbers are drawn from a possible 53.

To play Lotto, indicate your six chosen numbers by marking the numbered squares on a play slip. Then take the play slip to a lottery retailer (or agent). The retailer enters your selection in the on-line terminal, which produces your game ticket. The ticket, not the play slip, is the official receipt and must be presented and validated in the event of a win. Always check to make sure that the correct date and numbers are on the game ticket before you leave. Lottery agents are found in convenience stores, gas stations, and grocery stores.

The cost for one chance at Lotto is still $1 in many states. So for one chance, or play, at Lotto, you would pay $1. For five plays -- that is, to play five sets of numbers--you would pay $5. Illinois offers a bargain: two plays for $1.

Typically, Lotto drawings are held twice a week, usually on Wednesday and Saturday nights. However, this may not be true for every state.

The lottery officials use special ball-drawing machines, and the balls are numbered. The machine randomly shoots out six selected balls; these balls display the winning numbers for that evening's lottery drawing. If all six of your numbers exactly match the numbers drawn, you win the jackpot. In Lotto, your numbers don't need to be listed in any particular order, as long as they match those drawn. (taken from http://entertainment.howstuffworks.com/how-to-play-the-lottery1.htm)

In most case of lottery they don't draw same number, but in our problem here same number are allowed. So here, you can play number "42 42 45 45 45" which is not allowed in common lottos.

They say there's more chance of you getting hit by a car on your way to buy a lotto ticket than the chance of winning one. Is the probability to win really that small? You are about to help me find out.

Input

Input starts with an integer T (1 <= T <= 10), the number of test cases. T input blocks follows. Each input blocks starts with an integer M (1 <= M <= 50), meaning that the game involves M distinct numbers particularly from 1 to M. You don't know how the ball-drawing machine works, but you do know that for there is a constant probability for each number to pop up. The second line of each input blocks will consists of M real-numbers P₁, P₂, P₃, P₄, ..., P_M, where P_i denotes the probability of ball with number i to pop-up. You can safely assume that the total probability is equal to 1.

The third line of input is an integer Q (1 <= Q <= 100), the number of queries. Q lines follow with each line begins with an integer N (1 <= N <= M). So if N is 6, you are playing 6-out-of-M game in this particular query.N numbers follows, those are your chosen number. You are to determine what is the probability of that number winning the lottery. Since the probabilities can be very low, output them in scientific notation: a x 10^bwhere a should be between 1.00000 and 9.99999, inclusive. Output a in 5 decimal places.

Output

For each query, you are to determine the probability of that number winning the lottery.

Sample Input  Download

Sample Output  Download

Tags

Discuss