Một khu vui chơi gần bờ biển trải dài và hẹp, được chia thành ~n~ khu vực, đánh số từ ~1~ đến ~n~ và các khu vực được xem như nằm trên cùng một đường thẳng.

Để giám sát an ninh và các hoạt động trong các khu vui chơi, Ban quản lý đã lắp đặt các camera tại một số khu vực. Họ đã lắp ~q~ cameras tại các khu vực ~c_1,c_2,...,c_q~. Một khu vực có thể lắp đặt một hoặc nhiều camera hoặc không. Nếu có camera lắp đặt tại khu vực ~i~ thì camera đó sẽ giám sát các khu vực ~i-r,...,i-1,i,i+1,...,i+r~; tức là ngoài khu vực ~i~ thì camera có thể giám sát ~r~ khu vực bên trái và ~r~ khu vực bên phải của nó (nếu có ít hơn r khu vực bên trái hoặc bên phải của ~i~ thì camera sẽ chỉ giám sát các khu vực có trong phạm vi đó).

Yêu cầu: Hãy giúp Ban quản lý xác định xem tại mỗi khu vực trong khu vui chơi được giám sát bởi bao nhiêu cameras?

Input

Vào từ file văn bản CAU4.INP gồm:

• Dòng đầu tiên chứa số nguyên ~n(1 \leq n \leq 10 ^ 5)~;

• Dòng thứ hai chứa hai số nguyên ~q, r(1 \leq q \leq 10 ^ 5, 0 \leq r < n)~;

• Dòng thứ ba chứa q số nguyên ~c_1 ,c_2 ,...,c_q (1 \leq c_{i} \leq n, i = 1, 2 ,...,q)~.

Output

Ghi ra file văn bản CAU4.OUT gồm một dòng ghi ~n~ số nguyên cách nhau dấu cách, số thứ ~i~ là số lượng cameras giám sát khu vực ~i~.

Scoring

• Subtask ~1~ ~(20\%)~ số tests tương ứng với ~20\%~ số điểm của bài có ~r=0~;

• Subtask ~2~ ~(40\%)~ số tests khác tương ứng với ~40\%~ số điểm của bài có ~n,q \leq 7000~;

• Subtask ~3~ ~(20\%)~ số tests khác tương ứng với ~20\%~ số điểm của bài có ~n \leq 7000~;

• Subtask ~4~ ~(20\%)~ số tests còn lại tương ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Example input 1

8
5 2
5 3 7 1 3

Example output 1

3 3 4 3 4 2 2 1

Example input 2

5
4 0 
1 2 1 3

Example output 2

2 1 1 0 0

Note 1

• Có ~8~ khu vực trong khu vui chơi, có ~5~ cameras và bán kính giám sát của chúng là ~2~. Camera thứ nhất tại khu vực ~5~ sẽ giám sát các khu vực ~3, 4, 5, 6, 7~. Camera thứ hai tại khu vực ~3~ sẽ giám sát các khu vực ~1, 2, 3, 4, 5~. Camera thứ ba tại khu vực ~7~ sẽ giám sát các khu vực ~5, 6, 7, 8~. Camera thứ tư tại khu vực ~1~ sẽ giám sát các khu vực ~1, 2, 3~. Camera cuối cùng tại khu vực ~3~ sẽ giám sát các khu vực ~1, 2, 3, 4, 5~.

Note 2

• Bán kính giám sát của các cameras bằng ~0~ nên camera được lắp đặt tại khu vực nào chỉ giám sát khu vực đó.