Description

Given several fractions, compute their sum and express the answer in the simplest fraction form

Input

There are many test cases in one subtask.

The first line of each test case contains an integer t, which indicates the number of fractions in the input. Each of the following t lines contains two integers a and b, which represent the numerator and the denominator of a fraction.

subtask 1 : t<=2. 1<=a,b<=10.
subtask 2 : t<=5. 1<=a,b<=10.
subtask 3 : t<=5. 1<=a,b<=50.
subtask 4 : t<=10. 1<=a,b<=100.

Output

Each test case outputs one line.

The output is the sum reduced to the simplest fraction form. You need to print a '/' between the numerator and the denominator.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given the relationship of the nodes in a tree, construct the tree and output it in the pre-order.  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, denoting the number of relations in the tree.  In the following N lines, each line contains two integers a and b, which means node a is node b’s parent.   After that, 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.

Case 1: 1 <= N <=10 , 1 <= a,b <= 20

Case 2: 1 <= N <=100 , 1 <= a,b <= 200

Case 3: 1 <= N <=1000 , 1 <= a,b <= 2000

Case 4: 1 <= N <=1000 , 1 <= a,b <= 2000000

Output

For each test case, print the pre-order of the tree.  In each level, traverse the node with smaller ID first.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

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

(1) The string is an empty string.

(2) If a string S is valid, then {S}, [S], (S) and <S> are valid.

(3) If strings S1 and S2 are both valid, then S1S2 is valid.

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

Input

The first line of the input contains an integer N (N ≤ 10000) denoting the number of test cases followed by. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length will be no more than 1000. Note that an empty string (a line which contains the newline character only) may be contained in the input and it should be considered as a valid string according to rule (1).

Output

For each test case, print “Case i:” and then “Yes” or “No” to indicate that the string is valid or not, separated by a space character. i is the test case number starting from 1.

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

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