H. Harana
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Puno ang langit ng bituin

At kay lamig pa ng hangin

Sa 'yong tingin ako'y nababaliw giliw

At sa awitin kong ito

Sana'y maibigan mo

Ibubuhos ko ang buong puso ko...

Tonight, Bob has decided that he is going to serenade Cindy with a traditional harana outside her bedroom. Let's ignore the fact that Cindy lives on the 12th floor of a condo—he'll figure out the logistics later. For now, he needs to focus on his singing!

We can massively simplify and describe each note as a single integer, and so describe a song as a sequence of integers (Chord her? I barely know her!) Bob's song consists of the $$$n$$$ notes $$$s_1, s_2, \dots, s_n$$$, and by his practice, the best he can do is sing the notes $$$b_1, b_2, \dots, b_n$$$.

The off-key-ness of his singing is calculated as the sum of the absolute difference between each of his notes and the corresponding note in the song. In symbols: $$$$$$ \text{off-key-ness} = \sum_{i=1}^n |b_i - s_i|. $$$$$$ Bob has a sneaky trick he can do. Instead of fixing his singing, he can just change the key of the backing music! Right now, it is in key $$$0$$$. If a part is to be sung in key $$$k$$$, we add $$$k$$$ to the $$$s_i$$$ of all notes in that part (this $$$k$$$ can be negative, but it must be an integer).

Also, Bob wants to do a key shift at some note $$$m$$$, meaning he will sing notes $$$1$$$ to $$$m$$$ in key $$$k_1$$$, and then sing notes $$$m+1$$$ to $$$n$$$ in key $$$k_2$$$. Note that it is allowed to have $$$k_1 = k_2$$$, if you determine that it would be optimal.

For each $$$m$$$ from $$$1$$$ to $$$n-1$$$: Determine the minimum off-key-ness of Bob's singing if the key shift happens at note $$$m$$$, and the two keys ($$$k_1$$$ and $$$k_2$$$) are chosen optimally.

Input

The first line of input contains a single integer $$$n$$$.

The second line of input contains the $$$n$$$ space-separated integers $$$s_1, s_2, \dots, s_n$$$.

The third line of input contains the $$$n$$$ space-separated integers $$$b_1, b_2, \dots, b_n$$$.

Output

Output a single line containing $$$n-1$$$ space-separated integers, the $$$m$$$th of which is the minimum off-key-ness if the key shift happens at note $$$m$$$.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 2 \leq n \leq 2 \times 10^5 \\ -10^9 \leq s_i, b_i \leq 10^9 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{50} & \text{$0 \leq s_i, b_i \lt 8$ and $n \leq 1000$} \\ \hline 2 & \mathbf{20} & 0 \leq s_i, b_i \lt 8 \\ \hline 3 & \mathbf{20} & n \leq 1000 \\ \hline 4 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Example
Input
4
7 2 2 7
5 1 0 6
Output
1 2 1
Note

For the sample input, let's consider what to do when the key change is at note $$$m=1$$$. Here is an optimal series of steps.

  • For the first part, choose $$$k_1 = -2$$$, changing the first note to $$$[5]$$$
  • For the second part, choose $$$k_2 = -1$$$, changing the second to fourth notes to $$$[1, 1, 6]$$$.
We end with notes $$$[5, 1, 1, 6]$$$, and the off-key-ness is $$$|5-5| + |1-1| + |0-1| + |6-6| = 1$$$, which we can show is minimal.

We get minimal off-key-ness answers of $$$2$$$ and $$$1$$$ for the remaining values of $$$m$$$.