AIOC Banner

Problem: Safe Cracking

Want to try solving this problem? You can submit your code online if you log in or register.


Safe Cracking

Input File: safein.txt
Output File: safeout.txt
Time Limit: 1 second

Over the centuries many wars have been won, not through a battle of strength but a battle of wits. Your sources have recently informed you that your mother has purchased a pre-release copy of the latest computer game, WheeZork, and is hiding it in the safe at home. To open the safe, one must enter a long sequence of numbers by rotating the circular dial to each number in the correct order.

If the correct sequence of numbers is entered into the safe, the safe opens and you can sneak your Christmas present out early. If you get the sequence wrong the alarm system is activated and you will be grounded for life! Luckily, you know that your mother has written the code down on a sheet of paper in her bedside drawer, which she likes to call the "code sheet".

She often boasts about how clever she is and explains to you that the numbers on the sheet are indeed the code to the safe, however each number in the sequence has been increased by a constant non-negative integer, k, which only she knows. Without this value the sheet is useless, and thus only she can open the safe ... or so she thinks!

In order to determine the correct code, you have spied on your mother when she unlocks the safe and you have managed to remember part of the code that she entered. You are not sure which part of the code this corresponds to, but it is definitely a consecutive sequence of numbers in the code. Armed with this knowledge, you set out to determine the full code to the safe.

Your task is, given the full list of numbers your mother has written down on her code sheet, and the shorter sequence that you know appears in the actual code, determine the entire sequence to unlock the safe.

For example, if the code to the safe was 7, 9, 4, 6, 8, 12, and your mother had incremented all numbers by 4, her code sheet would read 11, 13, 8, 10, 12, 16. This is because 7 + 4 = 11, giving the first number 11. The second number is obtained by adding 9 + 4 = 13. The third number is obtained by adding 4 + 4 = 8, and so forth. You may have caught a glimpse of her entering the numbers 4, 6, 8, in order. With this knowledge, you can determine the entire code.

Input

The first line of the input file will contain two integers, a b, separated by a space. The integer a is the length of the sequence written on your mother's code sheet ( 2  <= a  <= 100000). The integer b is the length of the sequence that you know is contained within the code to the safe ( 2  <= b  <= 30).

Following this will be a lines, each containing a single integer between 1 and 1000000. These lines are the sequence written on your mother's code sheet, in the order they are entered into the safe.

Following this will be b lines, each containing a single integer, also between 1 and 1000000. These lines describe the glimpse of the actual code to the safe.

You are guaranteed that there will only be one possible solution for any given input scenario.

Output

Your output file should consist of a lines. Each of these lines should contain a single integer, representing the full sequence of numbers required to open the safe.

Sample Input

6 3
11
13
8
10
12
16
4
6
8

Sample Output

7
9
4
6
8
12

Scoring

The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 24 May 2019,  3:20am AEST