Description

Please create a binary search tree, and support insert operation. Please ignore the repeat number and print out the tree with preorder, inorder and postorder sequence. (The root node is greater than the node in the left subtree and smaller than the node in the right subtree.)

Pre-order:

1. Check if the current node is empty / null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function

In-order:

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

Post-order:

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

Input

The input contains mutilple lines. The first line is an non-negative integer T (T<5) that specifies the number of testcases. The first line of each testcases is an integer N (N<=8000), and the second line contains N integer V (-32767<=V<32768). (The first number in the second line is the root.)

Output

Please print out the tree with preorder, inorder and postorder. (Totally three lines.)
Each lines has a newline character '\n' in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an article, calculate the value of each character and output them in the descending order of their values.  The price of characters is calculated as follows:  one dollar for a letter ‘a’, two dollars for a letter ‘b’ … and 26 dollars for a letter ‘z’. 'A' and 'a' are not the same in this problem, just count the lowercase letters.

The input length (do not contain '\n' character) is smller than 65536.

Input

The input contains an article, which is terminated by EOF.

Output

Output the total value of each character in the descending order.  Do not print the character not in the article.  If two characters have the same value, output the one with smaller ASCII code first.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

An undirected graph is a forest if it contains no cycle.

Given an undirected graph, output "Yes" if it is a forest, otherwise "No".

Input

The input contains at most 20 test cases. For each test case, the first line contains two positive integers N (2 <= N <= 500000) and M (0 <= M <= 500000) separated by a space; N is the number of vertices and M is the number of edges in the undirected graph G. The vertices in G are denoted by v1, v2, ..., vN. (1 <=vi <= N) In the next M lines, each line contains two integers i and j separated by a space, which means that there is an edge between vi and vj.

There is a blank line after each test case. The last test case is followed by two zeros in one line.  

Output

For each test case, output "Yes" if it's a forest, otherwise "No".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There is a list of English words. Output them in lexicographic order. We compare the first character of two strings S1and S2. If the ASCII code of the first character of S1 is smaller than the first character of S2, we said that S1 is smaller than S2. Otherwise, if their first characters are the same, we compare their second characters, so on so forth until we can determine their order.  If S1 is S2’s prefix, S1 is smaller than S2 and vice versa.

Hint: Because of large input size, please use scanf and printf for efficiency.

Input

There are multiple test cases.  Each case begins with an integer N (1 <= N <= 1000) in a line, and then N words follow, each word in a line.  The maximum length of words is 50.  The alphabets are 26 small English letters ‘a’ to ‘z’. The input is terminated if N = 0.

Output

For each test case, print the words in lexicographic order.    Print a blank line after each case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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).

Hint: We have a very large input. Please use scanf and printf.

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.

Case 1: 0 < #operations <= 10^4

Case 2: 0 < #operations <= 10^5

Case 3: 0 < #operations <= 10^6

Case 4: 0 < #operations <= 10^7

Output

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

Sample Input  Download

Sample Output  Download

Tags

Discuss