Sum-up the Primes (II)
We all know from Goldbach’s conjecture that any even number greater than 2 can be expressed as a summation of two primes. Some odd numbers can also be expressed as summation of two primes. In this problem you will have to express a number as a summation of arbitrary number of primes less than 300. The conditions in detail are as follows:
- You have to express a number N (0 ≤ N ≤ 800) as a summation of t (t ≤ 12) primes.
- Among the t primes any single odd primes pi can be present maximum fi times, where (0 < fi < 5). 2 can be present at most once. The details regarding presence of 2 are given in the sample input description.
- All the prime numbers used must be less than 300.
- When there is more than one solution print the lexicographically smallest one.
- If there is no such expression of primes print the string ‘No Solution.’ without the quotes.
Input
The input file contains several blocks of input. The first line of the input file contains an integer B (B ≤ 500), which indicates the number of blocks in the input file. The description of each block is given below:
Each block starts with four lines, which contains 61 integers in total. These integers are the values fi (for i = 1 . . . 61, as there are 61 odd primes less than 300. For example the maximum frequency of 3 is f1, frequency of 5 is f2, etc). The first three of the four lines will have 16 integers and the last one will have 13 integers. The next line contains a positive integer Q (Q ≤ 100) that indicates the number of queries in this block. Next Q lines contain Q queries. Each query consists of three integers N, t, flag. The meaning of N and t is given in the problem statement. The integer flag is actually Boolean. When flag is 1 you can use 2 once in your summation expression but otherwise you cannot.
Output
For each block of input print a line indicating the serial of the block. For each query, print maximum two lines of output. The first line contains the query serial and the next line contains the lexicographically smallest way of expressing the prime as summation. If there is no possible ways, print the line ‘No Solution.’. Look at the sample output for details. Print a blank line after the output for each block of input.
Sample Input
2 1121213134221331 1434441244442333 3312132232421231 3331422223321
5
12 3 1
26 1 1
2/3
26 3 0
30 4 1
44 2 0 1121213134221331 1434441244442333 3312132232421231 3331422223321
10
53 10 0
56 8 0
586 12 0
595 7 1
659 3 1
739 3 1
747 4 0
753 8 1
761 12 0
763 4 0
Sample Output
Block 1:
Query 1:
2+3+7
Query 2:
No Solution.
Query 3:
No Solution.
Query 4:
11+5+7+7
Query 5:
13+31
Block 2:
Query 1:
No Solution.
Query 2:
No Solution.
Query 3:
101+101+101+101+103+11+13+13+23+5+7+7
Query 4:
101+101+101+101+103+17+71
Query 5:
101+277+281
Query 6:
163+283+293
Query 7:
No Solution.
Query 8:
101+101+101+101+103+107+137+2
Query 9:
3/3
No Solution.
Query 10:
No Solution.