Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mink


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 -> 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 -> 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 , ... 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 -> vị k
Phương án 2 : Vân Tiên phải đấu với vị 2 -> vị k+1

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

( 1 <= N <= 17000 , chỉ số APM của 1 giám khảo >= 1 và <= 2 tỉ , 1 <= K <= N ) .

Bài này O(N) mới thực sự coi là accept . Còn lại O(NlogN) hay O(N*K) thì bạn chỉ may mắn accept thôi .

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[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 .

Example

Input:
2
4 2
3 2 4 1
3 3
1 2 3
Output:
2 2 1
1

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-01-31
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2021-05-27 18:01:55
Tham khảo: https://vnspoj.github.io/problems/MINK
2020-06-11 10:47:12
nhật hào bẩn
2019-09-09 13:53:32
segment bth thôi cũng ac :)
2019-02-03 04:53:03
cài deque 0.08, chuyển sang list => 0.03 ==
2018-10-18 16:00:56
sao O(N) mà 0.09s luôn
2018-09-08 15:59:01
Dành cho ai muốn tham khảo thuật O(n) :3
http://bit.ly/2spxa0s

Last edit: 2019-01-11 17:25:44
2017-11-22 04:57:34
nhật hào sạch
2017-07-25 10:37:10 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE BÀI NÀY TẠI: http://yeulaptrinh.pw/785/mink-spoj/
2017-04-24 15:35:26
Bài này IT 0.08s đủ dùng.
2017-01-20 03:13:42


Last edit: 2017-01-20 03:14:04
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.