시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB52191640.000%

문제

어느 날 뉴로는 길이 $N$의 수열 $A, B$를 발견했다. 각 수열의 원소는 $10^5$ 이하의 음이 아닌 정수로 이루어져 있었고, 수열은 아름다운 색을 띠고 있었다. 뉴로는 두 수열 $A,B$의 다채로움을 판단하기 위해, 두 수열의 다채로움을 다음과 같이 정의했다.

$\max\limits_{1 \le i, j \le N} (A_i\cdot B_j - B_i\cdot A_j)$

하지만 사악한 이블이 수열을 마음대로 바꿔버렸다! 이블은 총 $Q$번의 변형을 수행했으며, $i$번째 변형에서는 처음에 주어졌던 두 수열의 모든 원소에 어떤 정수 $k_i$를 더했다. 뉴로를 도와 각 변형이 적용된 수열의 다채로움을 계산하자.

각 변형은 이전 변형의 결과에 영향을 받지 않는다. 즉, 모든 변형은 서로 독립적이다.

입력

첫 번째 줄에 수열의 길이 $N$이 주어진다.

두 번째 줄에 수열 $A$의 원소 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

세 번째 줄에 수열 $B$의 원소 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다.

네 번째 줄에 이블이 수열을 변형한 횟수 $Q$가 주어진다.

다섯 번째 줄부터 $Q$개의 줄에 걸쳐 $k_i$가 주어진다.

출력

총 $Q$개의 줄에 걸쳐, $i$번째 줄에 $i$번째 변형을 적용했을 때의 다채로움을 출력하라.

제한

  • $2 \le N \le 5 \times 10^5$
  • $0 \le A_i \le 10^5$ $(1 \le i \le N)$
  • $0 \le B_i \le 10^5$ $(1 \le i \le N)$
  • $1 \le Q \le 2 \times 10^5$
  • $-10^5 \le k_i \le 10^5$ $(1 \le i \le Q)$

서브태스크

번호배점제한
12

$N, Q \le 100$

216

$Q=1$

313

$N \le 1 \, 000$

439

$A_i , B_i \le 300 \, (1 \le i \le N); Q \le 1 \, 000$

530

추가 제약 조건 없음

예제 입력 1

4
1 5 7 4
8 4 2 6
2
3
-2

예제 출력 1

90
30

두 번째 변형은 수열 $A$를 $[-1,3,5,2]$로, 수열 $B$를 $[6,2,0,4]$로 바꾼다. 여기에서 $i=3$, $j=1$을 고르면 수열의 다채로움은 $5 \cdot 6 \, - \, (-1) \cdot 0 = 30$이 된다.

예제 입력 2

4
20 23 9 9
20 24 5 18
4
20
22
12
19

예제 출력 2

377
403
294
364

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.