Huyền thoại Lục Vân Tiên

View as PDF

Submit solution


Points: 0.08 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Dạo này tivi cũng đang chiếu phim Lục Vân Tiên, sẵn tiện lấy luôn làm tiêu đề.

Lục Vân Tiên cũng giống Samurai Jack, bị Quan Thái Sư đẩy vào vòng xoáy thời gian và bị chuyển tới tương lai của những năm 2777.

Ở thời đại này, Tráng sỹ phải là người thông thạo máy tính, gõ bàn phím lia lịa như đấu sỹ thời xưa múa kiếm ấy và phải qua một cuộc thi lập trình mới được phong danh hiệu.

Để vượt qua vòng loại, Vân Tiên cần tham gia cuộc thi sát hạch. Ban Giám Khảo cuộc thi sát hạch gồm có ~N~ người, họ đều là các cao thủ trong giới IT. Các thành viên trong Ban Giám Khảo được đánh số từ ~1~ ~\rightarrow~ ~N~ và mỗi người lại có một chỉ số sức mạnh gọi là APM (Actions Per Minute). Các giám khảo sẽ xếp hàng lần lượt từ ~1~ ~\rightarrow~ ~N~. Mỗi thí sinh sẽ phải đấu với ~K~ vị giám khảo và ~K~ vị giám khảo này phải đứng liền thành ~1~ đoạn (Tức là ~i, i+1, i+2, \dots, i+K-1~), chỉ cần thắng ~1~ vị giám khảo thì sẽ vượt qua vòng loại.

Tuy nhiên thí sinh kô được chọn xem những giám khảo nào sẽ đấu với mình.

Vân Tiên rất lo vì lỡ may đụng độ với những vị giám khảo nào "khó nhằn" thì sẽ tiêu mất. Nên chiến thuật của Vân Tiên là tập trung hạ vị giám khảo có chỉ số APM thấp nhất trong số ~K~ vị. Bạn hãy lập trình để giúp Lục Vân Tiên xác định được ở tất cả các phương án thì chỉ số APM của vị giám khảo thấp nhất sẽ là bao nhiêu (Có tất cả ~N-k+1~ phương án:

Phương án ~1~: Vân Tiên phải đấu với vị ~1~ ~\rightarrow~ vị ~k~

Phương án ~2~: Vân Tiên phải đấu với vị ~2~ ~\rightarrow~ vị ~k+1~ ...

Phương án ~N-k+1~: Vân Tiên phải đấu với vị ~N-k+1~ ~\rightarrow~ vị ~N~).

~(1 \leq N \leq 17000~, chỉ số APM của 1 giám khảo ~\geq 1~ và ~\leq 2~ tỉ, ~1 \leq K \leq N)~.

Input

Dòng 1: số ~T~ là số test.

Tiếp theo là ~T~ bộ test, mỗi bộ test có format như sau:

Dòng ~1~: ~N~ ~k~

Dòng ~2~: ~N~ số nguyên dương ~A_1~, ~A_2~, ...~A_N~.

Output

Kết quả mỗi test ghi ra trên dòng, dòng thứ ~i~ gồm ~N-k+1~ số, số thứ ~j~ tương ứng là chỉ số APM của vị giám khảo yếu nhất trong phương án ~j~.

Sample Input

2
4 2
3 2 4 1
3 3
1 2 3

Sample Output

2 2 1 
1

Comments

Please read the guidelines before commenting.



  • -3
    hieubecclc01   commented on Oct. 6, 2022, 9:40 p.m. edited

    2777 - 2022 = 755 năm nữa địa cầu sẽ được dân IT thống trị


  • -14
    ntkiet   commented on May 1, 2022, 8:33 p.m.

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


  • -48
    nngovannhhungg   commented on Jan. 14, 2022, 1:56 p.m.

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


  • 9
    I_love_Hoang_Yen   commented on April 9, 2021, 10:21 p.m.

    Nên giảm time limit để thuật n*log không AC :D


    • 11
      leduykhongngu   commented on April 10, 2021, 12:25 p.m.

      Em nghĩ nên tăng giới hạn n, tại vì 17000 thì nlogn với n nó không khác nhau mấy :v