Có một số táo và chuối và mỗi quả có trọng lượng nguyên từ \(1…k\). Việc của bạn là tính với mỗi trọng lượng \(w\) trong khoảng \(2...2k\) số cách ta có thể chọn một quả táo và một quả chuối có tổng trọng lượng là \(w\).

Input

Dòng đầu tiên là ba số nguyên \(k, n\) và \(m\) : con số \(k\), số táo và số chuối.

Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2,…, a_n\): trọng lượng của mỗi quả táo.

Dòng cuối cùng chứa \(m\) số nguyên \(b_1, b_2,…, b_m\): trọng lượng của mỗi quả chuối.

Output

Với mỗi số nguyên \(w\) nằm trong khoảng \(2… 2k\), in ra số cách chọn một quả táo và một quả chuối có tổng trọng lượng là \(w\).

Giới hạn

• \(1 \le k,n,m \le 2 \cdot 10^5\)
• \(1 \le a_i \le k\)
• \(1 \le b_i \le k\)

Ví dụ

Input

5 3 4
5 2 5
4 3 2 3

Ouput

0 0 1 2 1 2 4 2 0