Submit Best Submissions All Submissions

136. Time Jumper (Hard)

Problem Statement:
Long time ago, time traveling was possible, it was called time jumping, there was highly sophisticated machines called "time jumpers", you sit in one of those and relax, then you walk up in a different era!

Amazing ha? However in that time there was no electronic devices, those machines were taking special stones in a special compatible slots called USB (Universal Stones Bus) (the machine can take any number of stones), more important is that each stone had its own value, this value represents an amount of years.

For example, if I have a stone which its value is 200, I can travel 200 years in one step. If I have two stones which their values are 100 and 50 I can travel 50, 100 or 150 in one step.

I can insert any number of stones into the machine and it will simply sum the values of these stones and jump in time corresponding to that sum.

Given the current year, the number of stones and the value of each stone, your job is to find all the years that you can jump to in one step.

In this problem we only jump forward in time so these years must be greater than the current year (you should use at least one stone).

Input Format:
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 13). Followed by the test cases, each test case is exactly two lines, the first line contains two integers y and n (the current year and the number of available stones, respectively). The next line contains exactly n positive integers separated by single space representing the values of these stones (the value of each stone is less then 1000). (0 < y < 10000) (0 < n ≤ 100).

Output Format:
For each test case output all the different years that I can jump to (forward in time) in increasing order, each one in a line.

Sample Input:
2 1100 1 200 2000 2 50 150

Sample Output:
1300 2050 2150 2200

Added by: feras_kassar
Added at: 2014-02-28 18:58:51 UTC
Time Limit: 3 seconds
Partial score: No
Source:Damascus University First Training Contest 2014