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)

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 : [10] + [5, -8] + [0, 1, 2] (with simplified notations ; periods are 1,2 and 3)
In that case f(10) = [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.


hide comments
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

Added by:Francky
Date:2014-12-29
Time limit:1s-10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem