#include <bits/stdc++.h>

//_ ******************* Policy Based Data Structure ****************************

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


template <class T>
using ordered_set = tree<
	T,
	null_type,
	less<T>,
	rb_tree_tag,
	tree_order_statistics_node_update
>;

//_ ****************************************************************************


#define int              long long int
#define double           long double
#define print(a)         for(auto x : a) cout << x << " "; cout << endl
inline int power(int a, int b) {
    int x = 1;
    while (b) {
        if (b & 1) x *= a;
        a *= a;
        b >>= 1;
    }
    return x;
}


const int M = 1000000007;
const int N = 3e5+9;
const int INF = 2e9+1;
const int LINF = 2000000000000000001;

//_ ***************************** START Below *******************************




typedef pair<int, int> pii;





vector<int> a;


//* Using Set 

vector<double> consistency1(int n, int k) {
    vector<double> ans;
    
	set<pii> rightMin; // max heap
	set<pii, greater<pii>> leftMax; //* min heap
	
	
    int s = 0, e = 0;    
    while(e<n){
        leftMax.insert({a[e], e});
        
        //* rebalance now
        if(leftMax.size() > k/2){
            auto x = *leftMax.begin();
            leftMax.erase(x);
            rightMin.insert(x);
        }        if(e-s+1 < k){
            e++;
        }
        else{
            int x = (*leftMax.begin()).first;
            int y = (*rightMin.begin()).first;
            double median = (x + 0.0 +y)/2.0;
            if(k & 1){
                median = y;
            }
            ans.push_back(median);            
            leftMax.erase({a[s], s});
            rightMin.erase({a[s], s});
            
            //* rebalance now
            if(leftMax.size() < k/2){
                auto y = *rightMin.begin();
                rightMin.erase(y);
                leftMax.insert(y);
            }
            s++;
            e++;
        }
    }
    return ans;
}







//* Using Set 

void rebalance(set<pii, greater<pii>>& leftMax, set<pii>& rightMin){

    if(!leftMax.empty() && !rightMin.empty() && (*rightMin.begin()).first < (*leftMax.begin()).first ){
        auto leftTop = *leftMax.begin();
        auto rightTop = *rightMin.begin();

        leftMax.erase(leftTop);
        rightMin.erase(rightTop);

        leftMax.insert(rightTop);
        rightMin.insert(leftTop);
    }

    if(leftMax.size() > rightMin.size()){
        auto leftTop = *leftMax.begin();
        leftMax.erase(leftTop);
        rightMin.insert(leftTop);
    }
    else if(rightMin.size() > leftMax.size()+1 ){
        auto rightTop = *rightMin.begin();
        rightMin.erase(rightTop);
        leftMax.insert(rightTop);
    }
}


vector<int> consistency2(int n, int k) {
    vector<int> ans;
    
	set<pii, greater<pii> > leftMax;
	set<pii> rightMin;

    int s = 0, e = 0;
    while(e < n){
        leftMax.insert({a[e], e});
        rebalance(leftMax, rightMin);


        if(e - s + 1 < k){
            e++;
        }
        else{
            auto rightTop = *rightMin.begin();
            double median = rightTop.first;
            
            if( !(k & 1) ) {
                auto leftTop = *leftMax.begin();
                median = (leftTop.first + 0.0 + rightTop.first) / 2.0;
            }

            ans.push_back(median);

            if(leftMax.count({a[s], s})){
                leftMax.erase({a[s],s});
            }
            else {
                rightMin.erase({a[s],s});
            }
            rebalance(leftMax, rightMin);

            s++;
            e++;
        }
    }

    return ans;
}






//? Using Ordered set from Policy based ds 

vector<double> consistency3(int n, int k) {
    vector<double> ans;
    
    ordered_set<pair<int, int>> window;
    
    int s = 0, e = 0;
    while(e<n) {
        window.insert({a[e], e});
        
        if (e-s+1 < k) {
        	e++;
        }
        else{
        	if (k & 1) {
                auto it = window.find_by_order(k / 2);
                ans.push_back((double)it->first);
            } else {
                auto it1 = window.find_by_order(k / 2 - 1);
                auto it2 = window.find_by_order(k / 2);
                double median = (it1->first + 0.0 + it2->first) / 2.0;
                ans.push_back(median);
            }
            window.erase({a[s], s});
        	s++;
        	e++;
        }
    }
    
    return ans;
}





// Lazy Deletion on Priority queue

void rebalance2(priority_queue<pii>& leftMax, priority_queue<pii, vector<pii>, greater<pii>>& rightMin, vector<bool>& deleted, vector<bool>& in_left, int& validLeft, int& validRight) {

    while(!leftMax.empty() && deleted[leftMax.top().second]) leftMax.pop();
    while(!rightMin.empty() && deleted[rightMin.top().second]) rightMin.pop();

    if(!leftMax.empty() && !rightMin.empty() && rightMin.top().first < leftMax.top().first) {
        auto left = leftMax.top();
        auto right = rightMin.top();

        leftMax.pop();
        rightMin.pop();

        // Update tracking states since they swapped heaps
        in_left[left.second] = false;
        in_left[right.second] = true;

        leftMax.push(right);
        rightMin.push(left);
    }

    while(!leftMax.empty() && deleted[leftMax.top().second]) leftMax.pop();
    while(!rightMin.empty() && deleted[rightMin.top().second]) rightMin.pop();

    if(validLeft > validRight) {
        auto left = leftMax.top();
        leftMax.pop();
        
        in_left[left.second] = false;
        validLeft--;
        validRight++;
        
        rightMin.push(left);
    }
    else if(validRight > validLeft + 1) {
        auto right = rightMin.top();
        rightMin.pop();
        
        in_left[right.second] = true;
        validRight--;
        validLeft++;
        
        leftMax.push(right);
    }
}


vector<double> consistency4(int n, int k) {
    vector<double> ans; 
    
    priority_queue<pii> leftMax;
    priority_queue<pii, vector<pii>, greater<pii>> rightMin;
    
    vector<bool> deleted(n, false);
    vector<bool> in_left(n, false);
    int validLeft = 0, validRight = 0;

    int s = 0, e = 0;
    
    while(e < n) {
        leftMax.push({a[e], e});
        in_left[e] = true;
        validLeft++;
        
        rebalance2(leftMax, rightMin, deleted, in_left, validLeft, validRight);

        if(e-s+1 < k) {
            e++;
        }
        else {
            while(!leftMax.empty() && deleted[leftMax.top().second]) leftMax.pop();
            while(!rightMin.empty() && deleted[rightMin.top().second]) rightMin.pop();
            
            double x = leftMax.empty() ? 0 : leftMax.top().first;
            double y = rightMin.empty() ? 0 : rightMin.top().first;
            
            double median = y; 
            
            if( !(k & 1) ) {
                median = (x + y) / 2.0;
            }

            ans.push_back(median);

            deleted[s] = true;
            if (in_left[s]) validLeft--;
            else validRight--;
            
            rebalance2(leftMax, rightMin, deleted, in_left, validLeft, validRight);

            s++;
            e++;
        }
    }

    return ans;
}

















vector<double> practice(int n, int k) {

	return {};
	
}




void solve() {
    
    int n, k;
    cin>>n >> k;
	
	a.resize(n);
    for(int i=0; i<n; i++) cin >> a[i];
    
    auto ans1 = consistency1(n, k);
    for(auto& t : ans1 )	cout << t << " ";	cout << "   :   ";
    
    auto ans2 = consistency2(n, k);
    for(auto& t : ans2 )	cout << t << " ";	cout << "   :   ";
    
    auto ans3 = consistency3(n, k);
    for(auto& t : ans3 )	cout << t << " ";	cout << "   :   ";
    
    auto ans4 = consistency4(n, k);
    for(auto& t : ans4 )	cout << t << " ";	cout << endl;
    
    
    // auto p = practice(n, k);
    // cout << " -> ";
    // for(auto& it : ans1 ) {
    // 	cout << it << " ";
    // }
    // cout << endl;
    


}





int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}