Problem H
Hard Array Problem

This is an array problem.

Given two arrays of $N$ numbers with values $A_1, \dots , A_ N$ and $B_1, \dots , B_ N$. Let $A_{L, R}$ be the sum of elements in the subarray of $A$ from index $L$ to $R$ inclusive. Let $B_{L, R}$ be defined similarly.

Minimise $A_{L, R}^2 + B_{L, R}^2$ across all $1\leq L \leq R \leq N$.

Constraints

$1 \leq N \leq 5 \times 10^5$
$-10^9 \leq A_ i, B_ i \leq 10^9$

Input

The first line contains a single integer, $N$, the length of both arrays.
The second line contains $N$ space-separated integers, $A_1, A_2, \dots , A_ N$.
The second line contains $N$ space-separated integers, $B_1, B_2, \dots , B_ N$.

Output

Output a single integer, the minimised sum.

3
4 -1 -1 
-1 -1 4 

2

2
4 -4 
1 1 

4