Description

You need to write a program to simulate a queue of names.  Each name is a string consisting of English letters only.  There are three operations:

1.         “Push [name]”, which means to enque name in the queue.

2.         “Pop”, which means to deque. If the queue is empty, this operation takes no effect.

3.         “Front”, which means to print out the name in the front of queue. If the queue is empty, print "empty" (without quotes).

Case1 : #operation <= 10^2, There will be no "Pop" and "Front" command when queue is empty.
Case2 : #operation <= 10^3. There will be no "Pop" and "Front" command when queue is empty.
Case3 : #operation <= 10^4.
Case4 : #operation <= 10^6.

Input

Each line contains one of the following operations. “Push [name]” (without quotes), “Pop” (without quotes), “Front”(without quotes). The length of each name is at most 10.

Output

For each “Front” operation, print out the name in the front of the queue.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two vectors of numbers, output their intersection set.

Note: the numbers of vectors need not to be unique.

Input

There are multiple test cases. Each case contains four lines. The first line begins with an integer N. The second line contains N integers, representing the numbers in the first set. The third line has one integer M, and the fourth line contains M integers, represent the numbers in the second set. All the numbers are 32 bit signed integers. The input is terminated if N = 0.

For case 1, 1 <= N, M <= 10³
For case 2, 1 <= N, M <= 10⁴
For case 3, 1 <= N, M <= 10⁵
For case 4, 1 <= N, M <= 10⁶

Output

For each test case, print the intersection of the two sets. Output them in ascending order. If the intersection of the two sets is an empty set, print “empty” (without quotes).

Note: There's a newline character at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are N numbers in a queue.  The origin sequence is from 1 to N. (1 is the head). The operation “Move a ” means to move the first two numbers to the back of a without changing order. Note that if "a" is the first two numbers then you don't need to do anything. Given several such operations and output the final status of the sequence.

For example:N = 5,then the sequence will be 1 2 3 4 5.  If Move 3, the sequence will be 3 1 2 4 5. Since that the first two numbers is 1 2,you have to move 1 2 in the back of 3.

Input

There will be only one test case. The test case begins with an integer N indicating the number of people.  There are several operations followed.  The format is “Move a” (without quote).  The test case is terminated by “Exit” (without quote).

subtask 1 : 1<=N<=100, you can use O(N) algo for each operation.

subtask 2 : 1<=N<=100, you can use O(N) algo for each operation.

subtask 3 : 1<=N<=100000, you need use O(1) algo for each operation.

subtask 4 : 1<=N<=1000000, you need use O(1) algo for each operation.

Output

Output the numbers from the first one to the last one, and separate two consecutive numbers by a space. You DON'T need to print "\n" or space at the end of the line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A string is said to be a SM string if it matches one of the following rules:

(1) An empty string is a SM string.

(2) If strings S1 and S2 are both SM strings, then S1S2 is SM string.

(3) If a string S is SM string, then {S}, [S], (S) and <S> are SM strings.

(4) If a string S is SM string, then "sm"S is a SM string.

Given a string consisting of parentheses, determine if it is a SM string.

Input

The input consists of several lines.

Each line contains a string S(1 <= |S| <= 10^6 ), where S consists of only '{', '}', '[', ']', '(', ')' and "sm".

Output

For each strings S, output "SM" if it is a SM string, "MS" if not.

There should be a '\n' in the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a tree, count the number of leaves in this tree. Each node has unique integer identification (ID), but all IDs may not be consecutive.

Input

There are multiple test cases. Each test case begins with an integer N (1 <= N <=1000). In the following N lines, each line has two integer a and b (1 <= a,b <= 1000), indicating node a is node b’s parent. The next line contains an integer R, which represents the root of the Tree. You can assume that all the nodes will be on the same tree. The input is terminated by N = 0.

Output

Print the number of the leaves for each test case.

Hint: All leaves have no children!

Sample Input  Download

Sample Output  Download

Tags

Discuss