영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
There are n apples and m bananas, and each of them has an integer weight between 1 … k. Your task is to calculate, for each weight w between 2 … 2k, the number of ways we can choose an apple and a banana whose combined weight is w.
Input
The first input line contains three integers k, n and m: the number k, the number of apples and the number of bananas.
The next line contains n integers a_1,a_2,…,a_n: weight of each apple.
The last line contains m integers b_1,b_2,…,b_m: weight of each banana.
Output
For each integer w between 2 … 2k print the number of ways to choose an apple and a banana whose combined weight is w.
Constraints
- 1 ≤ k,n,m ≤ 2 · 10^5
- 1 ≤ a_i ≤ k
- 1 ≤ b_i ≤ k
Example
Explanation: For example for w = 8 there are 4 different ways: we can pick an apple of weight 5 in two different ways and a banana of weight 3 in two different ways.
예제
예제 1
5 3 4 5 2 5 4 3 2 3
0 0 1 2 1 2 4 2 0