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

Please find the frequency of the most frequent alphabetical character (ignore case) in the given string.

Input

There will be multiple test cases,
each test case contains a line of string with length N (N<=10000)
There will be no more than 10000 test cases.
Test cases will terminate by an EOF.

Output

For each test cases,
output a line with a number representing the frequency.

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, respectivily.

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 a_ij, representing the elements in matrix A, and then m lines of p integers b_ij, 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| ≤ 30.

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

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

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 seperate 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 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

We can encrypt a string into other string.  One method is to put a string into an n×n array first, where n is the smallest number such that n^2 is equal to or larger than the length of the string.  Each character is put into a cell of the array, from the top left cell of the array and along neighboring cells in the counterclockwise order.  The encrypted string is the output of the row major order.  For example, the input string "Greed is good", whose length is 13, are put into a 4×4 array, as shown in the following figure.

The output string is "Googrd  e  sed i".

If the end of the encrypted string are spaces, don't output them.  For example, the output of "Bass GG" is "B Ga Gss".

Input

The input consists of multiple lines. Each line is a test case, containing a string S. The number of test case is less than 200.

Case 1: the length of S is not more than 30.
Case 2: the length of S is not more than 100.
Case 3: the length of S is not more than 500.
Case 4: the length of S is not more than 1000.

Output

For each test case, output the encrypted string of S.

Sample Input  Download

Sample Output  Download

Tags

Discuss