PERIOD4 - Periodic function, trip 3 (easy)

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

The first line contains an integer T, the number of test cases, then each case will be given on three lines.
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:
2
2
5 7 5 7
6 7 8 9
3
15 3 17 2 16 4 15 3 17
10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

Output:
5 7 5 7
16 16 16 16 16 16 16 16 16

Explanation

Test case 1: for example f can be seen as the sum of two periodic functions : [5] + [0, 2] (with simplified notations)
We know that f(0)=5 and f(1)=7, we can deduce that f(6)=5, and so on...

Test case 2: for example f can be seen as the sum of three periodic functions : [10] + [5, -8] + [0, 1, 2] (with simplified notations). 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

0 < T < 1024
1 < N < 14 : uniform distribution
abs(y) < 10^9
0 < x < 10^9

Information

Constraints allow easy coding with various languages. (Edited 2017-02-11 ; with compiler changes)
There's two input files, a small one and a bigger.
My PY3.4 code ended in 0.02+0.28 = 0.30s. My C code in 0.01s.
If you find the constraints too weak, please consider PERIOD3. Have fun ;-)


hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2015-01-06 04:20:49

@Francky: Do you have proof that the answer will always be unique? and by the way, why SCM chicken is not allowed? does it mean only human has a chance to solve this problem, not a chicken? :-D
--Francky--> Yes, answer is unique. If you solve one of the trips, this implies that you can prove that the answer is unique. For the chicken, believe me, but I hesitate to check the box. Good luck ;-)

Last edit: 2015-01-06 09:26:29
Francky: 2015-01-05 20:16:06

I've set an easier edition for the trip3 that isn't too much related to others. You can solve it independently.


Added by:Francky
Date:2015-01-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Own problem