Є \(n\) яблук і \(m\) бананів, і кожне з них має цілу вагу між \(1…k\).

Ваше завдання полягає в тому, щоб обчислити для кожної ваги \(w\) між \(2…2k\) кількість способів, якими ми можемо вибрати яблуко та банан, сукупна вага яких дорівнює \(w\).

Обмеження

• \(1≤k,n,m≤2⋅10^5\)
• \(1≤a_i ​ ≤k\)
• \(1≤b_i ​ ≤k\)

Формат вхідних даних

Перший рядок містить три цілі числа \(k\), \(n\) і \(m\): число \(k\), кількість яблук і кількість бананів.

Наступний рядок містить \(n\) цілих чисел \(a_1 ​ ,a_2 ​ ,…,a_n ​\) : вага кожного яблука.

Останній рядок містить \(m\) цілих чисел \(b_1 ​ ,b_2 ​ ,…,b_m\) ​ : вага кожного банана.

Формат вихідних даних

Для кожного цілого числа \(w\) між \(2…2k\) виведіть кількість способів вибрати яблуко та банан, сукупна вага яких дорівнює \(w\).

Пояснення:

наприклад, для \(w = 8\) є 4 різні способи: ми можемо зірвати яблуко вагою 5 двома різними способами, а банан вагою 3 двома різними способами.

Приклад вхідних даних

5 3 4
5 2 5
4 3 2 3

Приклад вихідних даних

0 0 1 2 1 2 4 2 0