Bedao Regular Contest 10 - DOGS

View as PDF

Submit solution


Points: 0.60 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

illya là chủ một trang trại huấn luyện chó. Hiện tại, trong trại có ~n~ con chó đã hoàn thành bài các bài huấn luyện và sẵn sàng được nhận nuôi. Mặc dù cùng hoàn thành bài huấn luyện giống nhau, nhưng do nhiều yếu tố: giống loài, độ tuổi, giới tính, v.v nên sức mạnh của các con chó có thể khác nhau. Con chó thứ ~i~ đánh số từ trái sang phải có sức mạnh ~a_i~.

Trong đàn chó của illya, một con chó sẽ thường xuyên đi kiếm cớ gây sự với những con chó có sức mạnh chia hết cho sức mạnh của nó. Độ hổ báo của một con chó trong đoạn từ ~l~ đến ~r~ là số con chó nó sẽ trêu ghẹo trong đoạn từ ~l~ đến ~r~.

illya nhận được một cuộc hẹn của người chăn cừu để đến chọn mua một số con chó để về giúp trông coi đàn cừu. Người chăn cừu cho biết ông sẽ mua ~k~ con chó liên tiếp nhau. Để chất lượng đàn chó gửi đến người chăn cừu là tốt nhất có thể, illya quyết định sẽ cho các con chó trải qua thêm một đợt huấn luyện nữa. Nhưng vì thời gian có hạn, với mỗi dãy liên tiếp ~k~ con chó, illya chỉ có thể chọn ra con chó hổ báo nhất để huấn luyện lại nó, nếu có nhiều con chó cùng độ hổ báo, illya sẽ huấn luyện con có sức mạnh nhỏ nhất.

Với mỗi dãy liên tiếp ~k~ con chó, hãy giúp illya tính sức mạnh của con chó anh sẽ phải huấn luyện lại. Lưu ý một con chó có thể được huấn luyện lại nhiều lần.

Input

  • Dòng đầu tiên chứa số 2 nguyên dương ~n~ và ~k~ lần lượt là số lượng con chó trong trang trại của illya và số lượng chó người chăn cừu sẽ mua ~(1 \leq k \leq n \leq 10^5)~.

  • Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ lần lượt là sức mạnh của ~n~ con chó ~(1 \leq a_i \leq 10^5)~.

Output

Gồm ~n - k + 1~ số nguyên dương ngăn cách bởi dấu cách, số nguyên dương thứ ~i~ là sức mạnh của con chó con chó cần được huấn luyện lại trong dãy ~k~ con chó liên tiếp bắt đầu từ con chó thứ ~i~.

Subtask

  • ~20\%~ số test khác có ~n \leq 3000~.

  • ~20\%~ số test khác có ~a_1, a_2, ..., a_n~ là số nguyên tố.

  • ~60\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

6 3
1 3 2 6 4 8

Sample Output 1

1 2 2 4

Sample Input 2

7 4
2 6 12 3 9 11 8

Sample Output 2

2 3 3 3

Sample Input 3

7 4
1 3 2 8 3 2 4

Sample Output 3

1 2 2 2

Comments

Please read the guidelines before commenting.



  • -14
    aRandomGuy   commented on Sept. 26, 2022, 2:38 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.