Các nhà khoa học hành tinh Olimpia hàng năm tiến hành khảo sát các dạng đột biến khác nhau của bộ gen của các sinh vật nguyên thuỷ. Bộ gen của các sinh vật như vậy có thể biểu diễn bởi dãy gồm ~N~ số nguyên không âm, được đánh số từ trái sang phải bắt đầu từ ~1~ đến ~N~, mỗi số không vượt quá ~N~. Các bộ gen luôn đột biến không ngừng. Ở mỗi giai đoạn bộ gen biến đổi như sau:

• Ở vị trí đầu tiên sẽ ghi số lượng số ~1~ trong bộ gen ban đầu;

• Ở vị trí thứ hai sẽ ghi số lượng số ~2~ trong bộ gen ban đầu;

• ...

• Ở vị trí thứ ~N~ sẽ ghi số lượng số bằng ~N~ trong bộ gen ban đầu.

Chẳng hạn, bộ gen [1, 2, 3] gồm một số ~1~, một số ~2~ và một số ~3~ sau khi đột biến sẽ trở thành [1, 1, 1]. Một số ví dụ khác nữa:

• [1, 2, 2, 3, 3, 3] -> [1, 2, 3, 0, 0, 0].

• [7, 7, 7, 4, 7, 4, 4] -> [0, 0, 0, 3, 0, 0, 4].

Tiếp theo bộ gen lại tiếp tục biến đổi theo qui tắc đã nêu.

Yêu cầu: Cho biết thông tin về bộ gen ở trạng thái ban đầu, hãy xác định bộ gen sau ~K~ lần đột biến

Input

Dòng đầu tiên chứa hai số nguyên ~N, K~ thỏa ~1 \le N \le 10^5, 1 \le K \le 10^9~.

Dòng thứ hai chứa ~N~ số nguyên không âm, mỗi số không vượt quá ~N~ mô tả trạng thái ban đầu của bộ gen.

Output

Gồm ~N~ số nguyên không âm được ghi cách nhau bởi dấu cách là bộ gen sau ~K~ lần biến đổi.

Samples

Sample Input 1

4 2
1 3 1 4

Sample Output 1

2 1 0 0

Note

Đầu tiên bộ gen [1, 3, 1, 4] đột biến thành [2, 0, 1, 1], sau đó bộ gen tiếp tục đột biến thành [2, 1, 0, 0].