Matrix Maximum Sum

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Devu and Churu love to play with numbers. Today, each of them has an 1  based array consisting of N positive integers. Devu named his array as A while Churu called his array B. They have decided to construct a matrix C of size N × N using given arrays A and B where an entry C_{i,j} in the matrix is given by following expression.
where C_{i,j} denotes the value of the j^{th} cell in the i^{th} row of matrix C, A_{i} denotes the i^{th} element of the array A and B_{j} denotes the j^{th} element of the array B.
For example, consider the following arrays A and B each containing 3 elements.
A = [4, 1, 9] B = [3, 4, 1] Constructed matrix C will look like: [20, 30, 20], C = [12, 18, 12], [48, 72, 48],
Then, for a given K, they will create a list L_{K} of all submatrices of size K x K from the constructed matrix C and compute the following expression over the created list L_{K}.
where max( X ) denotes the maximum element present in the matrix X.
For example, consider the above matrix C and K = 2. Here, L_{K} contains following 4 submatrices of size 2 x 2.
[20, 30] [30, 20] [12, 18] [18, 12] [12, 18] [18, 12] [48, 72] [72, 48] M_{1} = 30 M_{2} = 30 M_{3} = 72 M_{4} = 72
Therefore, for K = 2, S = M_{1} + M_{2} + M_{3} + M_{4} = (30 + 30 + 72 + 72) % (10^{9} + 7) = 204.
Devu and Churu like the task very much and decided to compute the above expression for all possible values of K such that 1 ≤ K ≤ N but suddenly their mom called them for some urgent work and they had to leave the task in between. Can you help them completing this task?
Input
The first line of input contains a single integer N denoting the size of both arrays A and B. Second line of input contains N spaceseparated integers denoting the array A. Third line of input also contains N space separated integers, denoting the array B.
Output
Output N spaceseparated integers, where the i^{th} integer in the output denotes the required answer considering all submatrices of size i x i.
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ A_{i}, B_{j} ≤ 10^{9}
Subtasks
 1 ≤ N ≤ 10^{4} : ( 40 pts )
 1 ≤ N ≤ 10^{5} : ( 60 pts )
Example
Input 3 4 1 9 3 4 1 Output 280 204 72
Author:  ma5termind 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/MTMXSUM 
Tags  easymedium, feb16, ma5termind 
Date Added:  22102015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions