## PERIOD3 - Periodic function, trip 3

no tags

Solar cycle predictions are used by various agencies and many industry groups. The solar cycle is important for determining the lifetime of satellites in low-Earth orbit, as the drag on the satellites correlates with the solar cycle [...]. (NOAA) (Solar Cycle)

Sunspot Number Progression : Observed data through May 2008 ; Dec 2012 ; Nov 2014   The goal of the problem is to propose a perfect prediction center, with weak constraints.

Let us consider periodic functions from Z to R.

```	def f(x): return [4, -6, 7][x%3] # (with Python notations)
# 4, -6, 7, 4, -6, 7, 4, -6, 7, 4, -6, 7, 4, -6, 7, ...
```

For example, f is a 3-periodic function, with f(0) = f(3) = f(6) = f(9) = 4.
With a simplified notation we will denote f as [4, -6, 7].
For two periodic functions (with integral period), the quotient of periods will be rational, in that case it can be shown that the sum of the functions is also a periodic function. Thus, the set of all such functions is a vector space over R.

For that problem, we consider a function that is the sum of several periodic functions all with as period an integer N at maximum. You will be given some starting values, you'll have to find new ones.

### Input

On the first line, you will be given an integer N.
On the second line, you will be given integers y : the first (0-indexed) N×N values of a periodic function f that is sum of periodic functions all with as period an integer N at maximum.
On the third line, you will be given N×N integers x.

### Output

Print f(x) for all required x. See sample for details.

### Example

```Input:
3
15 3 17 2 16 4 15 3 17
10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

Output:
16 16 16 16 16 16 16 16 16
```

### Explanation

For example f can be seen as the sum of three periodic functions :  + [5, -8] + [0, 1, 2] (with simplified notations ; periods are 1,2 and 3)
In that case f(10) = [10%1] + [5, -8][10%2] + [0, 1, 2][10%3] = 10 + 5 + 1 = 16, and so on.

### Constraints

```N < 51
abs(y) < 10^9
0 < x < 10^9
```

### Informations

The problem is not simple, but constraints allow easy coding with C-like languages. You can safely assume output fit in a signed 32bit container. Time limit is at least ×4 my basic C timing. It could be hard with slow languages. There's 4 input files, with increasing value of N. You may first try the easy edition PERIOD4. Have fun ;-)

edit(09/06/2016) If it's too easy ; PERIOD5 is made for you.

Edit(2017-02-11) TL updated ; compiler changes. Michael Kharitonov: 2017-02-04 15:48:32 Can I assume that f(x) would fit in 32-bit signed integer for all x, or just for given values? You know how to construct the worst test cases that might be very tricky, why haven't you included any? =(Francky)=>For all values, f(x) fit in 32-bit signed integer. Tricky cases depend on the method ; I now have a method without tricky cases. Consider that old assert as irrelevant. Good luck. =(Michael)=>Thanks, got AC. I don't know any tricky cases for my solution. Is algorithm for PERIOD5 an improvement to PERIOD3, or it requires a completely different approach? =(Francky)=> A new complexity is required. There are several new methods : mine is different from min_25 one's. Take a look at the end of PERIOD5 description ; there are some informations after constraints section... Good luck. Last edit: 2017-02-05 22:48:16 Francky: 2016-06-09 19:12:55 I've found a new method ; 0.00s with C, 0.54s with PY3.4. PERIOD5 is my new task. Francky: 2015-03-19 23:17:42 Congrats to Min_25 as the first solver. Francky: 2015-01-06 01:31:59 Time limit could be very strict for slower languages, because there's several methods with the same complexity except the constant. So I stick to a basic C-code time with some margin for your convenience. I plan a new problem that will be made for Python users ; my todo list is yet overloaded... --edit(francky)--> I know how to construct the worst test cases that might be very tricky ; I didn't include any. Consider input as random. Last edit: 2015-01-06 10:53:11