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

Input is a permutation of 1, 2, ..., n. For instance, 3, 2, 1. We are provided with a stack, and want to ask if we supply the numbers according to the permutation order, and at each step we can either 

(i) get the next number from the supply, and output the number, or
(ii) get the next number from the supply, and push the number to the stack, or 
(iii) pop from the stack, and output that number.

Can we obtain the output sequence as 1, 2, 3, ..., n.

So for the case of 3, 2, 1, the answer is YES (we push, push, output, then pop, pop).
Similarly, for the case of 1, 3, 2, the answer is YES, since we output, push, output, pop.
But for 2, 3, 1, the answer is NO.

Hint: 
Our strategy could be as follows. 
First, we try operation (iii). 
If it is invalid, then we try operation (i). 
If it cannot produce what we want, try operation (ii). 
If we run out of the supply and the stack is not empty. The answer is NO.

Input

There are multiple testcases in the input.
Each case contains two lines. First line contains a positive integer N indicating the length of permutation. The next line contains N distinct numbers (range 1~N) separated by a blank, which describe the given permutation.
The input is terminated by end-of-file (EOF).

Case 1: N <= 10
Case 2: N <= 100
Case 3: N <= 500
Case 4: N <= 1000

Output

For each case, outupt a single line.
If the given permutation can be sorted by a stack, output "YES", otherwise, output "NO".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A directed graph is called “DAG” if it has no cycles. Given a DAG, find the shortest path from a starting point to a target point.

Input

The input consists of several test cases. Each test case, begins with three integers N, A, B indicating the number of nodes in the graph (indexing from 0 to N-1), the number of the starting point and the number of the target point. ( 0 < N <= 1000, 0 <= A, B < N ) In the second line, there is an integer K representing K edges. In the next K lines, there are two integers R, T in each line which means there is a directed edge from node R to node T and R is be equal to T. ( 0 <= R, T < n ) When N, A and B all equal to 0, the input ends.

Output

In each test case, please print “Case”, a space, the case number, a colon and a space orderly shown in the sample output. And then print the shortest path. In the shortest path, print a dash between each node. If there are two or more shortest paths, print the one with minimum number order. And If the shortest path does not exist, please print “INVALID”.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Compute C = A × B, where A, B and C are matrices of size n × m, m × p, and n × p, respectively.

Input

There are multiple (≤50) test cases in each data set.

Each case begins with a line of three integers n, m and p, which denote the dimensions of the matrices defined in the problem description. Each of the following n lines contains m integers aij, representing the elements in matrix A, and then m lines of p integers bij, representing the elements in matrix B.

There is a blank line between two successive test cases, and the input is terminated by end-of-file.

For data set #1, 1 ≤ n, m, p ≤ 5 and |aij|, |bij| ≤ 1000.

For data set #2, 1 ≤ n, m, p ≤ 20 and |aij|, |bij| ≤ 1000.

For data set #3, 1 ≤ n, m, p ≤ 50 and |aij|, |bij| ≤ 1000.

For data set #4, 1 ≤ n, m, p ≤ 100 and |aij|, |bij| ≤ 10000.

Output

For each test case, output n lines of p integers representing the elements of matrix C.

Please use single space to separate two successive elements in the same line, and do not output any leading or trailing space characters.

Also, please output a blank line after each matrix.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given three positive integers x, y, and z, compute their greatest common divisor (GCD) and least common multiple (LCM). The GCD of two or more numbers is the largest positive integer that can divide each of those numbers. The LCM of two or more numbers is the smallest positive integer that can be divided by each of those numbers.

hint : gcd(a,b,c) = gcd(gcd(a,b),c)

Input

The first line contains a positive integer N (N<=3000), which indicates the number of test cases in the input. In the next N lines, each line contains three positive integers x, y, and z, each of which is not greater than 10^6.

case 1 : 1<=numbers <= 10^2

case 2 : 1<=numbers <= 10^3

case 3 : 1<=numbers <= 10^5

case 4 : 1<=numbers <= 10^6

Output

For each case, output the GCD and LCM of x, y, and z in a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss