단조 행렬과 제곱 비용 최적화

양의 정수 $N$과 음이 아닌 정수 $M$에 대해 다음 두 문제를 함께 풀어 보자.

먼저 항의 번호가 $0$부터 $N$까지인 두 정수 수열 $A_0, A_1, \cdots, A_N$과 $B_0, B_1, \cdots, B_N$이 주어진다. 수열 $A$는 비감소하며 $A_0=0$이다. 다음 점화식을 만족하는 수열 $D_0, D_1, \cdots, D_N$과 $E_0, E_1, \cdots, E_N$을 구한다.

\[ \begin{aligned} D_0&=E_0=0,\\ D_i&=\min_{0\le j<i}\left(D_j+(A_i-A_j)^2+B_j\right),\\ E_i&=\max_{0\le j<i}\left(E_j-(A_i-A_j)^2-B_j\right) \qquad(1\le i\le N). \end{aligned} \]

다음으로 길이가 $N$인 정수 수열 $R_0, R_1, \cdots, R_{N-1}$과 길이가 $M$인 두 정수 수열 $C_0, C_1, \cdots, C_{M-1}$, $V_0, V_1, \cdots, V_{M-1}$이 주어진다. 각 수열의 항 번호는 $0$부터 시작한다.

행 번호가 $0$부터 $N-1$까지, 열 번호가 $0$부터 $M-1$까지인 행렬 $F$의 원소를 $F_{i,j}=R_iC_j+V_j$로 정의한다. $F$의 각 행에서 최댓값이 나타나는 가장 작은 열 번호를 구한다.

첫 번째 줄에 정수 $N$, $M$이 공백으로 구분되어 주어진다. $(1\le N\le200\,000; 0\le M\le200\,000)$

두 번째 줄에 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(0\le A_1\le A_2\le\cdots\le A_N\le10^6)$

세 번째 줄에 정수 $B_0, B_1, \cdots, B_N$이 공백으로 구분되어 주어진다. $(\lvert B_i\rvert\le10^6)$

네 번째 줄에 정수 $R_0, R_1, \cdots, R_{N-1}$이 공백으로 구분되어 주어진다. $(-10^6\le R_0\le R_1\le\cdots\le R_{N-1}\le10^6)$

다섯 번째 줄에 정수 $C_0, C_1, \cdots, C_{M-1}$이 공백으로 구분되어 주어진다. $(\lvert C_j\rvert\le10^6; C_j\le C_{j+1}\ (0\le j<M-1))$

여섯 번째 줄에 정수 $V_0, V_1, \cdots, V_{M-1}$이 공백으로 구분되어 주어진다. $(\lvert V_j\rvert\le10^6)$

$M=0$이면 마지막 두 줄은 빈 줄이다.

첫 번째 줄부터 $N+1$개의 줄에 걸쳐 $i=0$부터 $N$까지의 $D_i$와 $E_i$를 공백으로 구분하여 한 줄씩 출력한다.

그다음 줄부터 $N$개의 줄에 걸쳐 행 번호 순서대로 $F$의 각 행에서 최댓값이 나타나는 가장 작은 열 번호를 출력한다. $M=0$이면 각 행에 대해 $-1$을 출력한다.