Description

Given two polynomials

please calculate the result of adding these two polynomials.

9340 : 0 < n,m <= 15 , absolute value of all coefficients are less or equal than 105

9341 : 0 < n,m <= 105 , absolute value of all coefficients are less or equal than 1005

9342 : 0 < n,m <= 1005 , absolute value of all coefficients are less or equal than (10^7 + 5)

9343 : 0 < n,m <= 1005 , absolute value of all coefficients are less or equal than (2*10^9 + 5)

The input size is very large, don't use cin for input.

Input

The first line contains an integer t , which indicates the number of test cases in the input.

For each case, the first line contains two integers n, m. Integer n means the highest power of the first polynomial. Integer m means the highest power of the second polynomial. In the next 2 lines, the first line contains n+1 integers, which means the coefficients of the polynomial A from high to low. The second line contains m+1 integers, which means the coefficients of the polynomial B from high to low.

Output

For each case, output a line with the coefficients of the polynomial A+B. There is a space between two consecutive numbers.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Consider the following algorithm:
step 1. Input n
step 2. Set Count to be 0
step 3. If n is equal to 1, then STOP
Else Set
step 4. Count = Count +1
step 5. GOTO Step 3.
Given one integer n. Please output the count after processing the algorithm.

For example:
If n = 22, then according to the algorithm. You will get 22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1. Thus the count for 22 is 15.

Input

The input contains several test cases and will end with EOF. In each test case, there is only one line contains an integer n.
Case1: 1<=n<=1500
Case2: 1<=n<=9000
Case3: 1<=n<=100000
Case4: 1<=n<=1000000
[Hint]
For Case1, the value during operation will not exceed 10^6.
For Case2, the value during operation will not exceed 10^7.
For Case3, the value during operation will not exceed 2^31.
For Case4, the value during operation will not exceed 2^63.
For Case3~4, you may need to store the count of n that has already been calculated.

Output

For each test case, output the count of n.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given two strings, output them in alphabetical order.
Note: the order is AaBbCcDd ... YyZz.

Input

For each case a line, there are two strings separated by a single space. The lengths of the strings are no more than 30.
Case 1: line <= 500
Case 2: line <= 15000
Case 3: line <= 25000
Case 4: line <= 35000

Output

For each case a line, output the two strings in alphabetical order, separated by a single space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Calculate R = (B^P) mod M for large B, P, and M. Integer B is in the range 0 to 2³² inclusive. Integer P is in the range 0 to 2³¹ inclusive. Integer M is in the range 1 to 65600 inclusive. Note that you cannot calculate R directly because B^P is too large.

Input

There are multiple test cases. Each test case is given in three lines, containing B, P, and M in each line.

Case 1: 0 <= B <= 2¹⁵, 0 <= P <= 2¹⁵, 1 <= M <= 46340
Case 2: 0 <= B <= 2¹⁵, 0 <= P <= 2³¹, 1 <= M <= 46340
Case 3: 0 <= B <= 2³¹, 0 <= P <= 2³¹, 1 <= M <= 46340
Case 4: 0 <= B <= 2³², 0 <= P <= 2³¹, 1 <= M <= 65600

Output

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

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 <= 50), 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 integers in the range [-2²⁰, 2²⁰].


Case 1: m, n, p <=50, All elements of A and B are integers in the range [-2¹⁰, 2¹⁰].
Case 2: m, n, p <=100, All elements of A and B are integers in the range [-2¹⁰, 2¹⁰].
Case 3: m, n, p <=50, All elements of A and B are integers in the range [-2²⁰, 2²⁰].
Case 4: m, n, p <=100, All elements of A and B are integers in the range [-2²⁰, 2²⁰].

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 after each case.

Sample Input  Download

Sample Output  Download

Tags

Discuss