Encryption(C)
Time Limit:5S Memory Limit:32768K
Description
Country C recently intercepts a telegram from enemy army, but the telegram is encrypted. Analysis indicates that it is encrypted in WLE method. The decoding team spends a week to make a decoding solution:
The encrypted message is a non-decreasing nonnegative integer sequence with the length of m. The decoding solution consists of several steps, each of which is one of the following cases:
1. Subtract a positive integer from every number in the sequence, then delete negative terms.
2. Delete the first t terms of the sequence (t is a positive integer). If t is bigger than the length of the sequence, the sequence is empty.
3. Generate a new sequence with the same length as the original one. The nth term in the new sequence is the number of terms that are smaller than n in the original sequence. (n=1,2,...)
As a senior software engineer of Country C, you need to make a decoder.
Input
Input consists of multiple test cases.
Each case begins with a line containing n (100<=n<=10000), the length of the encrypted sequence, followed by n nonnegative integers in non-decreasing order. The next line contains m (100<=m<=10000), the number of decoding steps. The following m lines specify the operation of each step in such format as (corresponding to the problem description):
The first case: a single character 'M' followed by a positive integer.
The second case: a single character 'D' followed by a positive integer.
The third case: a single character 'N'.
There is no blank between the character and the integer. Every positive integer except m and n is less than or equal to 50.
The last case is followed by a line containing a zero.
Output
For each case, output the decoded sequence. If the decoded sequence is empty, output 'Empty'.
Sample Input
5
1 2 3 4 5
3
M1
D1
N
5
1 2 3 4 5
3
M1
D1
N
5
1 2 3 4 5
1
D10
0
Sample Output
Case 1: 0 1 2 3
Case 2: 0 1 2 3
Case 3: Empty

Genius(D)
Time Limit:1.5S Memory Limit:65536K
Description
For each natural number N (N>0),
Primary school students know if there exists an integer a, such that a2=N, then N is a perfect square.
Junior school students know if sqrt(N) is an irrational number, N is not a perfect square(square-free). High school students know that N is a perfect square if and only if there exists two positive integers X and Y, such that N=X2/Y2.
College students know that N is square-free if and only if there exists two positive integers X and Y, such that N=(X2-1)/Y2.
As a mathematics and programming genius, you know far more than them. Not only are the above four simple propositions a piece of cake to you, but also you can tell them how much X and Y are for each square-free N, such that (X2-1)/Y2=N.
You need to write a program which inputs an integer N and outputs X and Y.
Such X and Y may be multiple. Please output the minimum X and Y.
Input
The input consists of several test cases. Each test case is in a separate line, and consists of a single integer in the range 1 ... 10^8.
The last case is followed by a line containing an integer zero.
Output
For each test case, display a line that contains X and Y. if either X or Y is greater than or equal to 10^1000, output 'No solution!'.
Sample Input
3
57
81
0
Sample Output
Case 1:
2 1
Case 2:
151 20
Case 3:
No solution!