Ghép cặp theo tổng khối lượng · canuc80k6802

Có $n$ quả táo và $m$ quả chuối; mỗi vật có trọng lượng nguyên từ $1$ đến $k$ . Với từng tổng $w = 2, \dots, 2 k$ , hãy đếm số cách chọn một quả táo và một quả chuối sao cho tổng trọng lượng bằng $w$ . Input: $k$ $n$ $m$ , dãy trọng lượng táo, dãy trọng lượng chuối. Output: $2 k - 1$ đáp án.

Input

Dòng đầu chứa $k$ $n$ $m$ .
Dòng tiếp theo chứa trọng lượng của $n$ quả táo.
Dòng cuối chứa trọng lượng của $m$ quả chuối.

Output

In lần lượt số cặp có tổng $2, 3, \dots, 2 k$ .

Constraints

$1 \leq k, n, m \leq 2 \cdot 1 0^{5}$ .
Mỗi trọng lượng thuộc $[1, k]$ .

Scoring

Subtask $1$ ( $50$ điểm): Đại lượng $k$ không vượt $2000$ .
Subtask $2$ ( $50$ điểm): Không có ràng buộc bổ sung.

Example

Test 1

Input

6 4 5
2 5 4 5
4 1 2 5 5

Output

0 1 1 1 4 4 1 4 4 0 0

Giải thích: Ta đếm trực tiếp mọi cặp táo-chuối của mẫu rồi nhóm chúng theo tổng trọng lượng từ $2$ đến $2 k$ .

Thuật toán: Tạo A[x] là số táo nặng x, B[y] là số chuối nặng y. Tính C=A*B. Theo định nghĩa convolution,
Thuật toán: C[w] = sum_x A[x] B[w-x].
Thuật toán: Mỗi tích A[x]B[w-x] đếm mọi cặp vật có hai trọng lượng đó. In C[2]..C[2k]. Mã dùng CRT nguyên để không phụ thuộc vào modulus.
Chứng minh đúng: Mỗi cặp táo-chuối có tổng w thuộc đúng một hạng x+(w-x)=w; ngược lại mọi lựa chọn được đếm trong hạng tương ứng. Các nhóm rời nhau, nên tổng hệ số bằng đúng số cặp cần tìm.
Độ phức tạp: O(k log k+n+m) thời gian, O(k) bộ nhớ.