链接: https://cses.fi/problemset/task/2111

板块: Advanced Techniques

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有 $n$ 个苹果和 $m$ 根香蕉，每个的重量都是 $1 \ldots k$ 之间的整数。你的任务是：对 $2 \dots 2k$ 之间的每个重量 $w$，计算有多少种方式可以选择一个苹果和一根香蕉，使它们的重量之和为 $w$。

输入

第一行有三个整数 $k$、$n$ 和 $m$：$k$ 的值、苹果的数量和香蕉的数量。

下一行有 $n$ 个整数 $a_1,a_2,\ldots,a_n$：每个苹果的重量。

最后一行有 $m$ 个整数 $b_1,b_2,\ldots,b_m$：每根香蕉的重量。

输出

对 $2 \ldots 2k$ 之间的每个整数 $w$，输出选择重量之和为 $w$ 的苹果与香蕉的方案数。

数据范围

$1 \le k,n,m \le 2 \cdot 10^5$ $1 \le a_i \le k$ $1 \le b_i \le k$

样例输入

5 3 4
5 2 5
4 3 2 3

样例输出

0 0 1 2 1 2 4 2 0