Description

[[Category: Binary Search]]

Given is a set of integers and then a sequence of queries.
A query gives you a number and asks to find a sum of two distinct numbers from the set, which is closest to the query number.

Input

Input contains multiple cases (at most 800 cases).
Each case starts with an integer n (1 < n ≤ 1000), which indicates, how many numbers are in the set of integer.
Next n lines contain n numbers (1<= each integer <=10⁹). Of course there is only one number in a single line.
The next line contains a positive integer m giving the number of queries, 0 < m < 25.
The next m lines contain an integer (1<= each integer <2³¹) of the query, one per line.
Input is terminated by a case whose n = 0. Surely, this case needs no processing.

Output

Output should be organized as in the sample below. For each query output one line giving the query value and the closest sum in the format as in the sample. Inputs will be such that no ties will occur.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

[[Category: Sorting]]

One measure of  "unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence "DAABEC'', this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence "AACEDGG'' has only one inversion (E and D)--it is nearly sorted--while the sequence "ZWQM'' has 6 inversions (it is as unsorted as can be--exactly the reverse of sorted).


You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of  "sortedness'', from "most sorted'' to "least sorted''. All the strings are of the same length.

Input

The first line of the input is an integer M (M<=200), then a blank line followed by M datasets. There is a blank line between datasets.
The first line of each dataset contains two integers: a positive integer n (0 < n <=50) giving the length of the strings; and a positive integer m (0 < m <=100) giving the number of strings. These are followed by m lines, each containing a string of length n.

Output

For each dataset, output the list of input strings, arranged from "most sorted'' to "least sorted''. If two or more strings are equally sorted, list them in the same order they are in the input file.
Print a blank line between consecutive test cases.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

[[Category: Big Numbers]]

In these days you can more and more often happen to see programs which perform some useful calculations being executed rather then trivial screen savers. Some of them check the system message queue and in case of finding it empty (for examples somebody is editing a file and stays idle for some time) execute its own algorithm.

As an examples we can give programs which calculate primary numbers.


One can also imagine a program which calculates a factorial of given numbers. In this case it is the time complexity of order O(n) which makes troubles, but the memory requirements. Considering the fact that 500! gives 1135-digit number no standard, neither integer nor floating, data type is applicable here.


Your task is to write a programs which calculates a factorial of a given number.

Assumptions: Value of a number "n" which factorial should be calculated of does not exceed 1000 (although 500! is the name of the problem, 500! is a small limit).

Input

Any number of lines, each containing value "n" for which you should provide value of n!

Output

2 lines for each input case. First should contain value "n" followed by character '!'. The second should contain calculated value n!.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

[[Category: Prime]] 

Webster defines prime as:

prime (prim) n.[ME, fr. MF, fem. of prin first, L primus; akin to L prior] 

1 :first in time: original

2 a : having no factor except itself and one 3 is a   number  b : having no common factor except one  12 and 25 are relatively  

3 a : first in rank, authority or significance : principal b : having the highest quality or value   television time  [from Webster's New Collegiate Dictionary]

The most relevant definition for this problem is 2a: An integer g>1 is said to be prime if and only if its only positive divisors are itself and one (otherwise it is said to be composite). For example, the number 21 is composite; the number 23 is prime. Note that the decompositon of a positive number g into its prime factors, i.e., 

is unique if we assert that f_i > 1 for all i and  for i<j.

One interesting class of prime numbers are the so-called Mersenne primes which are of the form 2^p- 1. Euler proved that 2³¹ - 1 is prime in 1772 -- all without the aid of a computer.

Input

 The input will consist of a sequence of numbers (at most 800 numbers). Each line of input will contain one number g in the range -2³¹ < g <2³¹, but different of -1 and 1. The end of input will be indicated by an input line having a value of zero.

Output

 For each line of input, your program should print a line of output consisting of the input number and its prime factors. For an input number , where each f_i is a prime number greater than unity (with  for i<j), the format of the output line should be

When g < 0, if , the format of the output line should be 

Sample Input  Download

Sample Output  Download

Tags

Discuss