Description

S="ABCDEFG...XYZabcdefg...xyz"
Given two intergers M and N, output all different possible sets of N characters from the first M characters in S. Print the sets in ASCII order(i.e. 'A'<'B'<'C'...<'Z'<'a'<'b'...<'z'). Each set should only be printed once, and the elements in the set should also be sorted in ASCII order.

For example, given M=3, N=2, you should output C(3,2)=3 lines, representing different sets of 2 characters from the set {A,B,C}(first 3 characters in S). The correct output is:
AB
AC
BC

Note that set {A,B} = {B,A}, thus should only be output once.

Input

The first line of input contains a positive integer T(T<=30), which indicates the number of test case. For the next T lines, each line contains two positive integers M, N (M^N<10^7, M>=N).

case1: 1<=M<=10, 1<=N<=2
case2: 1<=M<=26, 1<=N<=10
case3: 1<=M<=52, 1<=N<=10
case4: 1<=M<=52, 1<=N<=20

Output

For each test case, output all different possible sets of N characters from the first M characters in S. Each set a line, sorted in ASCII order.
Print a blank line after each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Compute C=AB, where A is a matrix of size m×n, B is a matrix of size n×p, and C is a matrix of size m×p.

Input

First line contains a positive integer t (t <= 100), which indicates the numbers of test cases in the input. The first line of each test case contains three positive integers m, n, p (m, n, p <= 100) for the dimension of matrices. In the next m lines, each line contains n integers, representing the elements of matrix A. Followed by n lines, each line containing p integers, represent the elements of matrix B. All elements of A and B are 32-bit signed integers.


Case 1: m, n, p <=5
Case 2: m, n, p <=10
Case 3: m, n, p <=50
Case 4: m, n, p <=100

Output

For each case, output an m*p matrix in m lines and each line contains p integers.
Use one space between two consecutive integers. Output a blank line between each case.

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 are <S> 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 ≤ 1000) 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).

Case 1 ~ Case 3 would not contain any empty line.

Output

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

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Lagrange's four-square theorem says that any natural number can be represented as the sum of four integer squares.
Here are some examples:
3 = 1*1 + 1*1 + 1*1 +0*0
5 = 2*2 + 1*1 + 0*0 + 0*0
14 = 3*3 + 2*2 + 1*1 + 0*0
Note that there may be more than one representation. For example, 21 can be represented in the following two ways:
21 = 3*3 + 2*2 + 2*2 + 2*2
21 = 4*4 + 2*2 + 1*1 + 0*0

Our task:
Among all of the four-square representations of a given natural number N, find the largest sum of the four integers. In the case of N=21, the answer is 9 because 3+2+2+2 is greater than 4+2+1+0.

Input

The first line contains an integer T that indicates the number of test cases. (1<=T<=10)
The next T lines are the T test cases.
Each test case provides an integer N (0<=N<=50000) for deriving the four-square representations.

Case 1: 0<=N<=200.
Case 2: 0<=N<=1000.
Case 3: 0<=N<=10000.
Case 4: 0<=N<=50000.

Output

For each test case, output the answer in a single line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

1. A group of n students are arranged to sit in a circular table.
We assume that student j (mod n) is sitting on the
right of student j+1 (mod n).

2. Each student is given some amount of candies initially.
In particular, let A[1...n] be an array such that A[j] denotes
the candies of student j have, and the value A[j] is set to
a certain number at the beginning.

3. Then we repeat the following procedures until all students have the
same number of candies:

(i) [everyone-gets-even-candies]
If a student has odd number of candies, the student receives
one extra candy from the teacher. Else, no change.
(ii) [everyone-passes-half]
Each student passes half of his/her candies to the student on
its right.

Example: n = 3, A[1] = 2, A[2] = 4, A[3] = 8.

In the first round:
student 1 passes one candy to student 3;
student 2 passes two candies to student 1;
student 3 passes four candies to student 2.

After the first round, the array A is updated to:
A[1] = 3, A[2] = 6, A[3] = 5;

In the second round:
We first make the entries of A even:
A[1] = 4, A[2] = 6, A[3] = 6;

Next, the passing step:
student 1 passes two candies to student 3;
student 2 passes three candies to student 1;
student 3 passes three candies to student 2.

After the second round, the array A is updated to:
A[1] = 5, A[2] = 6, A[3] = 5;

In the third round:
We first make the entries of A even:
A[1] = 6, A[2] = 6, A[3] = 6;

Next, the passing step:
student 1 passes three candies to student 3;
student 2 passes three candies to student 1;
student 3 passes three candies to student 2.

After the third round, the array A is updated to:
A[1] = 6, A[2] = 6, A[3] = 6;

Now everyone gets the same number of candies, and we stop.

Input

The first line contains the number t of test cases.
Each test case is described by
(i) the number n of students and
(ii) a sequence of n integers for A[1...n].

Case 1. 1<=t<=3, 1<=n<=10, 1<=A[j]<=10
Case 2. 2<=t<=6, 1<=n<=20, 1<=A[j]<=20
Case 3. 3<=t<=9, 1<=n<=50, 1<=A[j]<=50
Case 4. 4<=t<=10, 1<=n<=100, 1<=A[j]<=100

Output

The output contains t lines.
Each line prints the number of candies of student 1 (A[1]) when we stop.

Sample Input  Download

Sample Output  Download

Tags

Discuss