Maxtrix

Two integer arrays $A, B$ of length $N$ are given. Define an $N \times N$ matrix $C$ as follows.

$C\_{ij} = A\_i + B\_j - ij$

For every integer $k$ with $1 \le k \le N$, compute $\max\_{1 \le i \le k \le j \le N} C\_{ij}$.

The first line contains the integer $N$, the length of both arrays.

The second line contains $A\_1, A\_2, \cdots, A\_N$, separated by spaces.

The third line contains $B\_1, B\_2, \cdots, B\_N$, separated by spaces.

Print $N$ lines with the answers.

• $1 \le N \le 250\,000$
• The absolute value of every element of $A$ and $B$ is at most $10^{18}$.