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:
1) You have to express a number N (0<=N<=800) as a summation of t(t<=12) primes.
2) 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.
3) All the prime numbers used must be less than 300.
4) When there is more than one solution print the lexicographically smallest one.
5) 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
1 1
2 1 2 1 3 1 3 4 2 2 1 3 3 1
1 4
3 4 4 4 1 2 4 4 4 4 2 3 3 3
3 3
1 2 1 3 2 2 3 2 4 2 1 2 3 1
3 3
3 1 4 2 2 2 2 3 3 2 1
5
12
3 1
26
1 1
26
3 0
30
4 1
44
2 0
1 1
2 1 2 1 3 1 3 4 2 2 1 3 3 1
1 4
3 4 4 4 1 2 4 4 4 4 2 3 3 3
3 3
1 2 1 3 2 2 3 2 4 2 1 2 3 1
3 3
3 1 4 2 2 2 2 3 3 2 1
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:
No
Solution.
Query
10:
No
Solution.
Problem setter: Shahriar Manzoor, ACM Valladolid Online
Judge Team