#CS2111. 苹果与香蕉

苹果与香蕉

题目背景

翻译自 CSES-21 题。

题目描述

给定 n 个苹果和 m 个香蕉，每个苹果和香蕉的重量在 1 到 k 之间。你的任务是计算，对于每个权重 w 在 2 到 2k2k2k 之间，选择一个苹果和一个香蕉，使得它们的总重量为 w 的方式有多少种。

输入格式

第一行输入三个整数 k、n 和 m，分别表示苹果的最大重量、苹果的数量和香蕉的数量。

第二行输入 n 个整数 a1,a2,...,ana_1, a_2, ..., a_na1​,a2​,...,an​，表示每个苹果的重量。

第三行输入 m 个整数 b1,b2,...,bmb_1, b_2, ..., b_mb1​,b2​,...,bm​，表示每个香蕉的重量。

输出格式

对于每个整数 w 在 2 到 2k2k2k 之间，输出选择一个苹果和一个香蕉，使得它们的总重量为 w 的方式数。

样例

5 3 4
5 2 5
4 3 2 3

0 0 1 2 1 2 4 2 0

样例1解释 例如，对于 w=8w = 8w=8，有 4 种不同的方式：可以选择一个重量为 5 的苹果（有两种选择），和一个重量为 3 的香蕉（也有两种选择）。

说明/提示

$1 \leq k, n, m \leq 2 \times 10^5$

1≤ai≤k1 \leq a_i \leq k1≤ai​≤k；

1≤bi≤k1 \leq b_i \leq k1≤bi​≤k。