Description

Calculate N! = 1×2×...×(N-1)×N. Note the number may exceed the range of integer or long long data type. Need to define a data structure to store the computed results. Note that 0! is defined as 1.

Input

There are multiple test cases. The first line contains an integer t, which indicates the number of test cases. Each test case is in a line, containing a number N (0<= N <= 114).

Output

For each case, output N!

9400 : N! < 2^31-1, 0 < t <= 15 
9401 : N! < 2^63-1, 0 < t <= 25
9402 : N! < 10^200, 0 < t <= 150 
9403 : N! < 10^200, 0 < t <=10^5 (Since t >> N, N! should be counted only one time and save it. Otherwise, you might got TLE!)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In a tree data structure where each node points to its parent, the lowest common ancestor of A an B can be easily determined by finding the first intersection of the paths from A and B to the root.
Given a rooted tree, please output the lowest common ancestor for each query.
For example, the lowest common ancestor of A and B is C.

Input

The first line contains a positive integer T (T <= 40), which indicates how many cases in the input. For each case, the first line contains a positive integer N, denoting the amount of node in the tree (labeled from 1 to N). The second line contains exactly N numbers. The first number denotes the parent of node 1, and the second number denotes the parent of node 2 ..., etc. The parent of the root will be labeled as -1.
Then multiple queries (query < 100) follow. Each line contains two positive integers A and B. The query is terminated by two zeros.
Each case is separated by a blank line.

Case 1: 1 <= N <= 10
Case 2: 1 <= N <= 100
Case 3: 1 <= N <= 1000
Case 4: 1 <= N <= 100000

Output

For each case a line, print the case number first, then output the node number of the least common ancestor for each query. Each answer should be separated by a single space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are many ways to calculate a value of a polynomial. One of them is Horner’s rule:

Given a polynomial and some parameters x, compute P(x) by Horner’s rule.

Input

First line contains a positive integer t(t<=1000), which indicates the number of test cases in the input. In each case, the first line gives an integer n. The second line contains n+1 integers, which are the coefficients of P(x) arranged from the highest power term to the constant term. The third line gives an integer m , which is the number of parameters. In next m lines, each line contains an integer, which indicate the parameter x.

Note : abs(x) means the absolute value of x.

case 1:
1 <= n <= 10
0 <= coefficient <= 10
1 <= m <= 10
0 <= x <= 10

case 2:
1 <= n <= 100
0 <= coefficient <= 100
1 <= m <= 100
0 <= x <= 100

case 3:
1 <= n <= 100
0 <= coefficient <= 10^6
1 <= m <= 100
0 <= x <= 10^6

case 4:
1 <= n <= 100
abs(coefficient) <= 10^6
1 <= m <= 100
abs(x) <= 10^6

Output

For each case, output the case number like “Case 1:” in a line, each value of m parameters is output in a line and mod 10000007. Please refer to sample output.

Note : -1 % 5 should output 4.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Maintain a doubly linked list, which supports the following operations:

(1) IH i : Insert a new integer i to the head of the list.

(2) IT i : Insert a new integer i to the tail of the list.

(3) RH : Print and remove the element in the head of the list. If the list is empty, print a blank line.

(4) RT : Print and remove the element in the tail of the list. If the list is empty, print a blank line.

(5) S : Swap the first floor(k/2) elements and the last k - floor(k/2) elements, where k is the total number of elements in the list. For example, if k = 5, the result of swapping a1, a2, a3, a4, a5 will be a3, a4, a5, a1, a2.

To improve the performance, it is suggested that three pointers be maintained in case4: head, tail and middle, where middle points to the floor(k/2) + 1-th element. With the help of these pointers, all of the operations can be done in constant time.

Input

There is only a single set of input and each operation will occupy a line. There will be a space between “IH” and “i”, and “IT” and “i”. The input contains OP operations, and it is terminated by end-of-file (EOF). You may assume that i is a nonnegative integer not greater then 100000. The list is initially empty.
For case1, 1<=OP<=100, test case contains only IT and RH operation. That is, you may use “queue” to pass this test case. And guaranteed that RH operation only appears when the list is not empty.
For case2, 1<=OP<=1000, test case contains only IH, IT, RH, RT operation. That is, no S operation will appear in this test case.
For case3, 1<=OP<=10000, test case contains all kinds of operation. For each S operation, O(n) is also accepted.
For case4, 1<=OP<=500000, each operation should be done in O(1).

Output

For each “RH” or “RT” operation, print a line containing the removed integer as commanded by the operation.
Recall for case2~4, for RH and RT operation: if the list is empty, print a blank line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There is a list of English words. Output them in lexicographic order. We compare the first character of two strings S1 and S2. If the ASCII code of the first character of S1 is smaller than the first character of S2, we said that S1 is smaller than S2. Otherwise, if their first characters are the same, we compare their second characters, so on so forth until we can determine their order.  If S1 is S2’s prefix, S1 is smaller than S2 and vice versa.

Input

 There are multiple test cases.  Each case begins with an integer N in a line, and then N words follow, each word in a line.  The maximum length of words is 50.  The alphabets are 26 small English letters ‘a’ to ‘z’. The input is terminated if N = 0.

Case 1: 1 <= N <= 10
Case 2: 1 <= N <= 100
Case 3: 1 <= N <= 500
Case 4: 1 <= N <= 1000

Output

 For each test case, print the words in lexicographic order.    Print a blank line after each case.

Sample Input  Download

Sample Output  Download

Tags

Discuss