Statement
어느 날 뉴로는 길이 의 수열 를 발견했다. 각 수열의 원소는 이하의 음이 아닌 정수로 이루어져 있었고, 수열은 아름다운 색을 가지고 있었다. 뉴로는 두 수열 의 다채로움을 판단하기 위해, 두 수열의 다채로움을 다음과 같이 정의하였다.
하지만 사악한 이블이 수열을 마음대로 바꿔버렸다! 이블은 총 번의 변형을 수행했으며, 번째 변형에서는 처음에 주어졌던 두 수열의 모든 원소에 어떤 정수 를 더했다. 뉴로를 도와 각 변형이 적용된 수열의 다채로움을 계산하자.
각 변형은 이전 변형의 결과에 영향을 받지 않는다. 즉, 모든 변형은 독립적이다.
Input
첫 번째 줄에 수열의 길이 이 주어진다.
두 번째 줄에 수열 의 원소를 뜻하는 개의 정수 이 공백으로 구분되어 주어진다.
세 번째 줄에 수열 의 원소를 뜻하는 개의 정수 이 공백으로 구분되어 주어진다.
네 번째 줄에 이블이 수열을 변형한 횟수 가 주어진다.
다섯 번째 줄부터 개의 줄에 걸쳐 가 주어진다.
Output
총 개의 줄에 걸쳐, 번째 줄에 번째 변형을 적용했을 때의 다채로움을 출력한다. 각 변형은 이전 변형의 결과에 영향을 받지 않음에 유의하라.
Subtasks
Samples
예제 1
입력
4
1 5 7 4
8 4 2 6
2
-2
3
출력
30
90
첫 번째 예제의 첫 번째 변형은 수열 를 로, 수열 를 로 바꾼다. 여기에서 , 을 고르면 수열의 다채로움은 이 된다.
예제 2
입력
5
4 1 1 6 9
5 3 2 3 2
4
-10
14
0
-5
출력
65
151
37
24