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

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

What:

The Data Structures TAs enjoy making word puzzles. Ron has challenged Eva to find all combinations of letters matching the following rule:

c(v)+(c(v)+)+c

Where c is a consonant and v is a vowel. This means: all strings of concatenations of at least two groups of one consonant followed by one or more vowels, followed by a consonant at the end (ex.: papap, paaaapaaaaap, papapap). Notice that the minimum length for this pattern is length=5.

Eva wants to check her answers. Help them build that program!

How:

You will be given 2 things: the word puzzle dimension and the word puzzle. You should traverse the matrix from left to right, from top to bottom. For each cell, output all possible paths matching the pattern in the traversal order. To change direction, use the following priorities: down, right, up, left.

You should also output the rearranged version of the word, where vowels go first and consonants after (example: apple turns into aeppl).

Example:

For example, take the word puzzle below:

Let’s take a look at some combinations:

XS is not valid, because you have 2 consonants in a row

AD is not valid, because it begins with a vowel

CAT is not valid, because there should be a vowel and a consonant to match the pattern

COZDP is not valid, because there are three consonants together

COZOB is valid, because it is of length>=5 and matches the pattern

XUVAIC is valid, because it is of length>=5 and matches the pattern

NIAVUX is valid, because it is of length>=5 and matches the pattern

Input

1 line: What: an integer n and a new line character

           Why: matrix dimension will be (n*n)

n lines:     What: n lines of n characters followed by a new line character

                 Why: word puzzle layout

(n+1 lines in total)

Output

You should all ‘words’ matching this pattern, followed by a space, the rearranged version of the words(vowels before consonants) and a newline character. Output should match the traversal order:

1)down

2)right

3)up

4)left

Sample Input  Download

Sample Output  Download

Tags

Discuss