#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 *******************************









vector<int> a;

vector<double> consistency1(int n, int k) {
    vector<double> ans;
    
	set<pair<int,int>> rightMin; // max heap
	set<pair<int,int>, greater<pair<int,int>>> 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 Ordered set from Policy based ds 

vector<double> consistency2(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;
}


















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& it : ans1 ) {
    	cout << it << " ";
    }
    cout << "   :   ";
    
    auto ans2 = consistency2(n, k);
    for(auto& it : ans2 ) {
    	cout << it << " ";
    }
    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;
}