#201 colorful

Loading problem...

Preparing the statement, recent submissions, and submit form.

#201 colorful | DOJ

School/경기과학고등학교/IamCoder Qualification Test/IamCoder Qualification Test 2026

Time limit: 2000 ms
Python time limit: 2000 ms
Memory limit: 1024 MB
Checker: CUSTOM
Solve threshold: 100

Statement

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

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

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

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

Input

첫 번째 줄에 수열의 길이 $N$ 이 주어진다. $(2 \le N \le 500 \, 000)$

두 번째 줄에 수열 $A$ 의 원소를 뜻하는 $N$ 개의 정수 $A_1, A_2, \cdots, A_N$ 이 공백으로 구분되어 주어진다. $(0 \le A_i \le 100 \, 000)$

세 번째 줄에 수열 $B$ 의 원소를 뜻하는 $N$ 개의 정수 $B_1, B_2, \cdots, B_N$ 이 공백으로 구분되어 주어진다. $(0 \le B_i \le 100 \, 000)$

네 번째 줄에 이블이 수열을 변형한 횟수 $Q$ 가 주어진다. $(1 \le Q \le 200 \, 000)$

다섯 번째 줄부터 $Q$ 개의 줄에 걸쳐 $k_i$ 가 주어진다. $(-100 \, 000 \le k_i \le 100 \, 000)$

Output

총 $Q$ 개의 줄에 걸쳐, $i$ 번째 줄에 $i$ 번째 변형을 적용했을 때의 다채로움을 출력한다. 각 변형은 이전 변형의 결과에 영향을 받지 않음에 유의하라.

Subtasks

#	Score	Constraints
1	2	$N, Q \le 100$
2	16	$Q=1$
3	13	$N \le 1 \, 000$
4	39	$A_i , B_i \le 300 \, (1 \le i \le N), Q \le 1 \, 000$
5	30	추가 제한 조건 없음.

Samples

Sample 1

Input

Output

30
90

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

Sample 2

Input

Output

Colorful Array

Statement

Input

Output

Subtasks

Samples