A company needs random numbers for its operation. random numbers have been generated using numbers as seeds and the following recurrence formula:
The numbers used as seeds are . is the term of the recurrence.
Due to a failure on the servers, the company lost its seed numbers. Now they just have the recurrence formula and the previously generated random numbers.
The company wants to recover the numbers used as seeds, so they have hired you for doing this task.
Input Format
The first line contains two space-separated integers, and , respectively.
The second line contains the space-separated integers describing (all these numbers are non-negative integers ).
The third line contains the space-separated coefficients of the recurrence formula, . All of these coefficients are positive integers .
Constraints
Output Format
The output must be one line containing the space-separated seeds of the random numbers - .
Sample Input
2 6
13 8
1 1
Sample Output
1 1
Explanation
This is the classic Fibonacci recurrence. We have the and terms, and, of course, the seeds are the numbers and .