Description

Given a,b, output a+b.

Input

a,b<=100000000.

Output

a+b

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two integer sequences A, B. Add them in some specific order O.
O is described via a representation of the location relationship from input.

For example, O = 100101 means A[i] + B[i+2] write to result C[i+1];
O = 111 means A[i] + B[i] write to C[i].

Note that if index is out of the length of B or C, imagine that B,C are circular.

Input

N
L
A
B
O

N is the number of total test data.
L is the number of element in A,B.

A,B sequences have the same number of elements, each element e:
0< e < 1000000
1<= num. of A,B <= 1000

O is the description of the order
3 <= length of O < 1000
there are exactly three ones in O, and the leading one is always happen!

Output

Output your result by the same format of input sequence.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a string S, output the reverse of S.

Input

The input consists of many lines. Each line is a string S with length <= 1000000.
The string S does not contain any spaces.

Output

Output the the reverse of S. One in each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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

Jasio is a little boy - he is only three years old and enjoys playing with toy cars very much. Jasio has n different cars. They are kept on a shelf so high, that Jasio cannot reach it by himself. As there is little space in his room, at no moment may there be more than k toy cars on the floor.

Jasio plays with one of the cars on the floor. Jasio's mother remains in the room with her son all the time. When Jasio wants to play with another car that is on the floor, he reaches it by himself. But when the toy is on the shelf, his mummy has to hand it to him. When she gives Jasio one car, she can at the same time pick any car from the floor and put it back on the shelf (so that there remains sufficient space on the floor).

The mother knows her child very well and therefore can predict perfectly which cars Jasio will want to play with. Having this knowledge, she wants to minimize the number of times she has to hand Jasio a toy from the shelf. Keeping that in mind, she has to put the toys off on the shelf extremely thoughtfully.

Write a programme that:

• reads from the standard input the sequence of toy cars in order in which Jasio will want to play with them,
• calculates the minimal number of times the mother has to pick cars from the shelf,
• writes the result to the standard output.

Input

In the first line of the standard input there are three integers: n, k, p (1 <= k <= n <= 100,000, 1 <= p <= 500,000), separated by single spaces. These denote respectively: the total number of cars, the number of cars that can remain on the floor at once and the length of the sequence of cars which Jasio will want to play with. Each of the following p lines contains one integer. These integers are the numbers of cars Jasio will want to play with (the cars are numbered from 1 to n ). 

Output

In the first line of the standard output one integer should be written - the minimal number of times his mother has to pick a car from the shelf.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A binary search tree is a binary tree with root k such that any node v in the left subtree of k has label (v) <label (k) and any node w in the right subtree of k has label (w) > label (k).

When using binary search trees, one can easily look for a node with a given label x: After we compare x to the label of the root, either we found the node we seek or we know which subtree it is in. For most binary search trees the average time to find one of its n nodes in this way is O(log n).

Given a number n, can you tell how many different binary search trees may be constructed with a set of numbers of size n such that each element of the set will be associated to the label of exactly one node in a binary search tree?

Input

The input will contain a number 1 <= i <= 1000 per line representing the number of elements of the set.

Output

You have to print a line in the output for each entry with the answer mod 32767 to the previous question.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

For his birthday present little Johnny has recieved from his parents a new plaything which consists of a tube and a set of disks. The aforementioned tube is of unusual shape. Namely, it is made of a certain number of cylinders (of equal height) with apertures of different diameters carved coaxially through them. The tube is closed at the bottom, open at the top. An exemplary tube consisting of cylinders whose apertures have the diameters: 5cm, 6cm, 4cm, 3cm, 6cm, 2cm and 3cm is presented in the image bellow.

The disks in Johnny's plaything are cylinders of different diameters and height equal to those forming the tube.

Johnny has invented a following game: having a certain set of disks at his disposal, he seeks to find what depth the last of them would stop at, assuming that they are being thrown into the centre of the tube. If, for instance, we were to throw disks of consecutive diamaters: 3cm, 2cm and 5cm, we would obtain the following situation:

As you can see, upon being thrown in, every disk falls until it gets stuck (which means that it lies atop a cylinder, aperture of which has a diameter smaller than the diameter of the disk) or it is stopped by an obstacle: the bottom of the tube or another disk, which has already stopped.

The game being difficult, Johnny constantly asks his parents for help. As Johnny's parents do not like such intelectual games, they have asked you - an acquaintance of theirs and a programmer - to write a programme which will provide them with answers to Johnny's questions.

Write a programme which:

• reads the description of the tube and the disks which Johnny will throw into it from the standard input,
• computes the depth which the last disk thrown by Johnny stops at,
• writes the outcome to the standard output.

Input

The first line of the standard input contains two integers n and m ( 1n, m300 000) separated by a single space and denoting the height of Johnny's tube (the number of cylinders it comprises) and the number of disks Johnny intends to throw into it, respectively. The second line of the standard input contains n integers r₁, r₂,...,r_n ( 1r_i1 000 000 000 for 1i n) separated by single spaces and denoting the diameters of the apertures carved through the consecutive cylinders (in top-down order), which the tube consists of. The third line contains m integers k₁, k₂,..., k_m ( 1k_j1 000 000 000 for 1j m) separated by single spaces and denoting the diameters of consecutive disks which Johnny intends to throw into the tube.

Output

The first and only line of the standard output should contain a single integer denoting the depth which the last disk stops at. Should the disk not fall into the tube at all, the answer should be 0.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given N points, find the convex hull

.

Input

Each testcase starts with 3<= N <= 10^6, which represents the number of points. Following N lines describe N points x, y-coordinate, where |x|, |y| <= 1000, and x, y are intergers. Input file ends up with a single 0.

There are no such cases that one line can pass through every point.

Output

Each testcase contains two lines.

Frist line prints Case #: , where # is the number of testcases.

Second line output the index of the points in counterclockwise order(index is the order of input, and the first point has index "1"). Start from the leftmost point, or the lowest one in case of a tie.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A number of K balls are dropped one by one from the root of a fully binary tree structure FBT. Each time the ball being dropped first visits a non-terminal node. It then keeps moving down, either follows the path of the left subtree, or follows the path of the right subtree, until it stops at one of the leaf nodes of FBT. To determine a ball's moving direction a flag is set up in every non-terminal node with two values, either false or true. Initially, all of the flags are false. When visiting a non-terminal node if the flag's current value at this node is false, then the ball will first switch this flag's value, i.e., from the false to the true, and then follow the left subtree of this node to keep moving down. Otherwise, it will also switch this flag's value, i.e., from the true to the false, but will follow the right subtree of this node to keep moving down. Furthermore, all nodes of FBT are sequentially numbered, starting at 1 with nodes on depth 1, and then those on depth 2, and so on. Nodes on any depth are numbered from left to right.

For example, Fig. 1 represents a fully binary tree of maximum depth 4 with the node numbers 1, 2, 3, ..., 15. Since all of the flags are initially set to be false, the first ball being dropped will switch flag's values at node 1, node 2, and node 4 before it finally stops at position 8. The second ball being dropped will switch flag's values at node 1, node 3, and node 6, and stop at position 12. Obviously, the third ball being dropped will switch flag's values at node 1, node 2, and node 5 before it stops at position 10.



Fig. 1: An example of FBT with the maximum depth 4 and sequential node numbers.


Now consider a number of test cases where two values will be given for each test. The first value is D, the maximum depth of FBT, and the second one is I, the Ith ball being dropped. You may assume the value of I will not exceed the total number of leaf nodes for the given FBT.

Please write a program to determine the stop position P for each test case.


For each test cases the range of two parameters D and I is as below:

Input

Contains l+2 lines.

Line 1 I the number of test cases
Line 2 D₁ I₁
test case #1, two decimal numbers that are separatedby one blank
...
Line k+1 D_k I_k
test case #k
Line l+1 D_l I_l
test case #l
Line l+2 -1 a constant -1 representing the end of the input file

Output

Contains l lines.

Line 1 the stop position P for the test case #1
...
Line k the stop position P for the test case #k
...
Line l the stop position P for the test case #l

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2…Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another. For example, the first 80 digits of the sequence are as follows:
11212312341234512345612345671234567812345678912345678910123456789101112345678910

Input

The first line of the input file contains a single integer t (1 <=t <=25), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 <=i <=2147483647)

Output

There should be one output line per test case containing the digit located in the position i.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

ICPC (International Collegiate Programming Contest), as you might know, is a team programming contest for college students. Each team consists of exactly three students and they will work on a number of programming problems.

Andi, Budi and Chandra plan to participate in this year ICPC as a team. As for their team strategy, they come up with a simple one:

In the first 20 minutes of 5 hours contest, they will read through all problems. Then each of them will assign a number to each problem. This number indicates how many minute(s) it will take for him to get the problem accepted (correct solution). Then they will start to code, meaning that they only have 280 minutes to really work on the problems. You may assume that they always get accepted on time whenever they work on a problem.
There's only one computer for each team, so it's not possible for them to code two different problems simultaneously.
To avoid any brain fatigue and adrenaline rush (because they attend competitions so frequently), they decided to switch role after each problem, such that none of them will work at the computer for more than one problem consecutively.
They want to solve as many problems as they can. The order of problem to be solved does not matter.

Input

The first line of input contains an integer T , number of test cases to follow. Each case begins with an integer N (1N12) in one line, denoting the number of problems. The second line contains N integers, A1..N (1Ai300) , denoting the total time (in minutes) needed by Andi to solve ith problem. The third and fourth line will correspond to the total time needed by Budi and Chandra respectively and will have the same input format as the second line.

Output

For each case, print in a single line containing the maximum total number of problem that can be solved by that team.


Explanation for 1st sample case:

Actually Andi could solve all the three problems alone, but the team has decided that none of them should work at the computer for more than one problem consecutively.


Explanation for 2nd sample case:

The team can solve all the problems. Here is one solution:

Let Budi work on Problem-2 (100 minutes).
Switch to Andi and let him work on Problem-1 (50 minutes).
Switch to Budi again and let him work on Problem-3 (30 minutes).
Finally, switch to Chandra and let him work on Problem-4 which (100 minutes).
Overall, they need 100 + 50 + 30 + 100 = 280 minutes.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Astronomers have been looking for living beings in the outer planets. Recently the Hobble telescope has picked up binary (black and white) images from the Zkrets planet (1 light-years away). Each image contains exactly one symbol. Together the sequence of symbols (images) represents a message for aliens from other planets. A team of deciphering experts has found some decoding scheme that assigns an English alphabet to each symbol. The decoding process would be easy if each received image were in perfect condition. Unfortunately, due to long distance transmission, the images received usually contain some noise, meaning that some white pixels are turned into black pixels and vise versa. Furthermore, due to self-rotation of the Hobble telescope, the images, when captured, might be rotated 0, 90, 180 or 270 degrees. To expedite the message decoding process, please write a program to decode the received sequence of images automatically.


Technical Specification

The number of images received is n, where 1n100 . The size of the image is always scaled to 10×10 . Within the image, `1' represents a black pixel (part of the symbol) and `0' represents a white pixel (not part of the symbol).
Each received image may contain at most 20% noise. This means that at most 20 pixels may have their gray levels changed (from black to white or from white to black) during transmission. Each image is rotated 0, 90, 180 or 270 degrees in clockwise direction.
The number of matching symbols and English Alphabets is m , where 1m52 . The matching English Alphabets can be either upper-case or lower-case letters.

Input

There are two parts of input, one follows the other. For the first part, it contains the matching English alphabets and image symbols. Thus, the first line contains an integer m , the number of matching alphabets and symbols. The next 11m lines define the m sets of matching alphabets and symbols. The first line of each set contains a single unique English letter. The next 10 lines give the matching symbol in a perfect (no noise, no rotation) 10×10 image of 0's and 1's. For the second part, it contains a sequence of received images. The first line contains an integer n , the number of 10×10 images received. The next 10n lines present the n images received. Every 10 lines define one image. Each line contains exactly 10 consecutive 0's and 1's.

Output

Please print out the corresponding English letters of the received input images in sequence, all on one line. If more than one match is possible for a given input image, output the matching one with the least number of noise pixels. If there is still a tie, output the one that appears first in the input sequence of English alphabets.

Explanations for the Sample:

There are 2 deciphered matching codes.
The first is coded as letter a. The corresponding image is giving in 10 rows of consecutive 0's and 1's.

The second image is coded as letter X. The corresponding image is giving in 10 rows of consecutive 0's and 1's.

There are 3 received images waiting to be decoded.
The first received image has 10 rows of consecutive 0's and 1's. It matches with the corresponding image of the coded symbol 'X' perfectly without any noise. The image is either not rotated or perhaps rotated by 180 degrees.

The second image has also 10 rows of consecutive 0's and 1's. It also matches with the corresponding image of the coded symbol 'X' perfectly without any noise. However, the image is either rotated by 90 or 270 degrees.

The third image has also 10 rows of consecutive 0's and 1's. It contains 12 noise pixels. The image is also rotated by 90 degrees. It matches with the corresponding image of the coded symbol 'a'.

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

In a sensational scene in the 8-th installment of the Voldemort book series, the robot Weighd was attacked and its rotating top and wings were severely damaged. Weighd cannot rotate its famous top and can only fly forward or make a right-turn. However, the brave Weighd must still navigate a magically created series of mazes to deliver its precious message to Ttoper.

Weighd enters each maze at the top-left square of the maze, takes one unit of time to travel between adjacent squares in the magic maze (forward or right), and cannot stay in one square to rotate itself, and thus change direction, for fear of evil jinx. Your task is to write a program to calculate the smallest number of squares that Weighd must travel to reach a certain square in each maze. Do not you worry about how? Weighd will feel its correct way through the force. Examples are:



Weighd can reach the location marked ``X" of the top maze in ``19" steps, but it cannot reach the marked location in the bottom maze at all.

Input

Input consists of multiple mazes. Each maze description starts with two integers, on a separate line, that represent its dimensions. The first integer N (1<=1000) represents the number of rows and the second M (1<=1000) represents the number of columns. The last maze is followed by a line containing two zeros that indicate the end of the input data and should not be processed as a valid situation.

The second line contains two integers, C (1<=N) and R (1<=M), that represent the column number and the row number of the square where Weighd must reach in the maze. Consecutive integers are separated by a blank space.

Each of the following N lines contains a sequence of 0s and 1s. The sequence is M characters long. The sequence does not contains blank spaces. A value one (1) represents a wall in the maze (that is, a square into which Weighd cannot fly).

Output

Output consists of one line for each maze. It will be in one of the following two formats:

1. an integer that represents the number of steps to be taken, inside the maze, by Weighd to reach its destination.
2. The string ``NOOO!", if no path can be found.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A positive integer may be expressed as a sum of different prime numbers (primes), in one way or another. Given two positive integers n and k, you should count the number of ways to express n as a sum of k different primes. Here, two ways are considered to be the same if they sum up the same set of the primes. For example, 8 can be expressed as 3 + 5 and 5 + 3 but they are not distinguished.

When n and k are 24 and 3 respectively, the answer is two because there are two sets {2, 3, 19} and {2, 5, 17} whose sums are equal to 24. There are no other sets of three primes that sum up to 24. For n = 24 and k = 2, the answer is three, because there are three sets {5, 19}, {7, 17} and {11, 13}. For n = 2 and k = 1, the answer is one, because there is only one set {2} whose sum is 2. For n = 1 and k = 1, the answer is zero. As 1 is not a prime, you shouldn't count {1}. For n = 4 and k = 2, the answer is zero, because there are no sets of two different primes whose sums are 4.

Your job is to write a program that reports the number of such ways for the given n and k.

Input

The input is a sequence of datasets followed by a line containing two zeros separated by a space. A dataset is a line containing two positive integers n and k separated by a space. You may assume that n<=1120 and k<=14.

Output

The output should be composed of lines, each corresponding to an input dataset. An output line should contain one non-negative integer indicating the number of ways for n and k specified in the corresponding dataset. You may assume that it is less than 2³¹.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Wavio is a sequence of integers. It has some interesting properties.
· Wavio is of odd length i.e. L = 2*n + 1.
· The first (n+1) integers of Wavio sequence makes a strictly increasing sequence.
· The last (n+1) integers of Wavio sequence makes a strictly decreasing sequence.
· No two adjacent integers are same in a Wavio sequence.
For example 1, 2, 3, 4, 5, 4, 3, 2, 0 is an Wavio sequence of length 9. But 1, 2, 3, 4, 5, 4, 3, 2, 2 is not a valid wavio sequence. In this problem, you will be given a sequence of integers. You have to find out the length of the longest Wavio sequence which is a subsequence of the given sequence. Consider, the given sequence as :

1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1.

Here the longest Wavio sequence is : 1 2 3 4 5 4 3 2 1. So, the output will be 9.

Input

The input file contains less than 75 test cases. The description of each test case is given below: Input is terminated by end of file.

Each set starts with a postive integer, N(1<=N<=10000). In next few lines there will be N integers.

Output

For each set of input print the length of longest wavio sequence in a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

One of our best friends is getting married and we all are nervous because he is the first of us who is doing something similar. In fact, we have never assisted to a wedding, so we have no clothes or accessories, and to solve the problem we are going to a famous department store of our city to buy all we need: a shirt, a belt, some shoes, a tie, etcetera.

We are offered different models for each class of garment (for example, three shirts, two belts, four shoes, ..). We have to buy one model of each class of garment, and just one.

As our budget is limited, we cannot spend more money than it, but we want to spend the maximum possible. It's possible that we cannot buy one model of each class of garment due to the short amount of money we have.

Input

The first line of the input contains an integer, N, indicating the number of test cases. For each test case, some lines appear, the first one contains two integers, M and C, separated by blanks (1<=M<=200, and 1<=C<=20), where M is the available amount of money and C is the number of garments you have to buy. Following this line, there are C lines, each one with some integers separated by blanks; in each of these lines the first integer, K (1<=K<=20), indicates the number of different models for each garment and it is followed by K integers indicating the price of each model of that garment.

Output

For each test case, the output should consist of one integer indicating the maximum amount of money necessary to buy one element of each garment without exceeding the initial amount of money. If there is no solution, you must print "no solution".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You have to cut a wood stick into pieces. The most affordable company, The Analog Cutting Machinery, Inc. (ACM), charges money according to the length of the stick being cut. Their procedure of work requires that they only make one cut at a time.
It is easy to notice that different selections in the order of cutting can led to different prices. For example, consider a stick of length 10 meters that has to be cut at 2, 4 and 7 meters from one end. There are several choices. One can be cutting first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 meters, the resulting of 8 and the last one of 6. Another choice could be cutting at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 = 20, which is a better price.

Your boss trusts your computer abilities to find out the minimum cost for cutting a given stick.

Input

The input will consist of several input cases. The first line of each test case will contain a positive number l that represents the length of the stick to be cut. You can assume l < 1000. The next line will contain the number n (n < 50) of cuts to be made.
The next line consists of n positive numbers ci ( 0 < ci < l) representing the places where the cuts have to be done, given in strictly increasing order.

An input case with l = 0 will represent the end of the input.

Output

You have to print the cost of the optimal solution of the cutting problem, that is the minimum cost of cutting the given stick. Format the output as shown below.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a given a sequence of non-negative integers you will have to find such a sub-sequence in it whose summation is maximum.

Input

The input file contains several input sets. The description of each set is given below:
Each set starts with an integer N (N<1000) that indicates how many numbers are in that set. Each of the next N lines contains a single non-negative integer. All these numbers are less than 10000.
Input is terminated by a set where N=0. This set should not be processed.

Output

For each set of input produce one line of output. This line contains one or more integers which is are taken from the input sequence and whose summation is maximum. If there is more than one such sub-sequence print the one that has minimum length. If there is more than one sub-sequence of minimum length, output the one that occurs first in the given sequence of numbers. A valid sub-sequence must have a single number in it. Two consecutive numbers in the output are separated by a single space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

An evil professor has just assigned you the following problem.
A sequence is defined by the following recurrence:

Determine x_1000000.

Input

Input consists of a number of lines, each containing one integer, a value of i, no less than zero and no greater than one million. Input is followed by a single line containing the integer -1. This last line is not a value of i and should not be processed.

Output

For each value of i in the input (but not the final -1), output the corresponding value of xi modulo 1000000.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In the German Lotto you have to select 6 numbers from the set {1,2,...,49}.
A popular strategy to play Lotto - although it doesn't increase your chance of winning - is to select a subset S containing k (k>6) of these 49 numbers, and then play several games with choosing numbers only from S.
For example, for k=8 and S = 1,2,3,5,8,13,21,34 there are 28 possible games: [1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34].
Your job is to write a program that reads in the number k and the set S and then prints all possible games choosing numbers only from S.

Input

The input file will contain one or more test cases.
Each test case consists of one line containing several integers separated from each other by spaces. The first integer on the line will be the number k (6 < k < 13). Then k integers, specifying the set S, will follow in ascending order.
Input will be terminated by a value of zero (0) for k.

Output

For each test case, print all possible games, each game on one line.
The numbers of each game have to be sorted in ascending order and separated from each other by exactly one space. The games themselves have to be sorted lexicographically, that means sorted by the lowest number first, then by the second lowest and so on, as demonstrated in the sample output below.
The test cases have to be separated from each other by exactly one blank line. Do not put a blank line after the last test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Write a program that will select the longest strictly increasing subsequence from a sequence of integers.

Input

The input file will contain a sequence of integers (positive, negative, and/or zero). Each line of the input file will contain one integer.

Output

The output for this program will be a line indicating the length of the longest subsequence, a newline, a dash character ('-'), a newline, and then the subsequence itself printed with one integer per line. If the input contains more than one longest subsequence, the output file should print the one that occurs last in the input file.
Notice that the second 8 was not included -- the subsequence must be strictly increasing.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The problem is to multiply two integers X, Y. (0<=X,Y<10²⁵⁰)

Input

The input will consist of a set of pairs of lines. Each line in pair contains one multiplyer.

Output

For each input pair of lines the output line should consist one integer the product.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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