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
2014-07-24 14:18:30 Human Immunodeficiency Virus
bài này dùng stack 1 đầu thôi. rồi chạy từ k -> n để xét đoạn i-k
2014-07-01 08:08:24 Xiao Lang
IT vẫn qua bình thường mà
2014-06-17 10:12:38 Thcs Ðặng Chánh Kỷ
tịnh tiến stack o(N)
2014-06-03 10:58:22 Lollipop
làm IT mà k đk may mắn :))
2014-05-20 04:47:50 ♥*.*♥MTP♥*.*♥
:)
2014-04-13 15:04:23 Duc M. Pham
Bài này sao lại là Stack nhỉ? Phải là Queue mới đúng chứ :D

Đã AC với Queue :D
2013-12-17 15:26:08 Xiao Lang
Bài này đúng như nói dùng IT ăn may thì AC :))
O(t*N*Log(2,N))
2013-08-21 17:26:23 NTIT_Trường Kỳ
stack 2 đầu rồi mà vẫn chạy quá lâu là sao :(
2013-03-11 13:58:36 law
T max la bao nhieu vay
2013-01-10 16:19:35 a;slkfjasl;fkj
Ko có giới hạn của T à o.O

Last edit: 2013-01-10 16:47:54
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.