Một khu vui chơi được chia thành ~n~ khu vực đánh số từ ~1~ đến ~n~. Ban quản lý lắp ~q~ cameras tại các khu vực ~c_1,c_2,\ldots,c_q~. Một khu vực có thể có nhiều cameras.

Một camera đặt tại khu vực ~c~ sẽ giám sát các khu vực từ ~\max(1,c-r)~ đến ~\min(n,c+r)~.

Yêu cầu

Với mỗi khu vực, hãy xác định có bao nhiêu cameras giám sát khu vực đó.

Input

• Dòng đầu chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa hai số nguyên ~q,r~ ~(1 \le q \le 10^5, 0 \le r < n)~.
• Dòng thứ ba chứa ~q~ số nguyên ~c_i~ ~(1 \le c_i \le n)~.

Output

In ra một dòng gồm ~n~ số nguyên, số thứ ~i~ là số lượng cameras giám sát khu vực ~i~.

Subtask

• Có ~20\%~ số test tương ứng ~20\%~ số điểm có ~r=0~.
• Có ~40\%~ số test khác tương ứng ~40\%~ số điểm có ~n,q \le 7000~.
• Có ~20\%~ số test khác tương ứng ~20\%~ số điểm có ~n \le 7000~.
• Có ~20\%~ số test còn lại không có ràng buộc gì thêm.

Ví dụ 1

8
5 2
5 3 7 1 3

3 3 4 3 4 2 2 1

Ví dụ 2

5
4 0
1 2 1 3

2 1 1 0 0