Matrix Maximum Sum `MTMXSUM`

All submissions for this problem are available.<h3> Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.</h3>

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 sub-matrices 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 sub-matrices of size 2 x 2.


[20, 30]      [30, 20]      [12, 18]      [18, 12]
[12, 18]      [18, 12]      [48, 72]      [72, 48]

M₁ = 30      M₂ = 30      M₃ = 72      M₄ = 72

Therefore, for K = 2, S = M₁ + M₂ + M₃ + M₄ = (30 + 30 + 72 + 72) % (10⁹ + 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 space-separated integers denoting the array A. Third line of input also contains N space separated integers, denoting the array B.

Output

Output N space-separated integers, where the i^th integer in the output denotes the required answer considering all sub-matrices of size i x i.

Constraints

1 ≤ N ≤ 10⁵

1 ≤ A_i, B_j ≤ 10⁹

Subtasks

1 ≤ N ≤ 10⁴ : ( 40 pts )

1 ≤ N ≤ 10⁵ : ( 60 pts )

Example

Input
3
4 1 9
3 4 1

Output
280 204 72

Matrix Maximum Sum MTMXSUM