1864B.cpp

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        string s;
        cin >> s;

        vector<int> even;
        vector<int> odd;

        if (k % 2 != 0)
        {
            for (int i = 0; i < n; i++)
            {
                if (i % 2 == 0)
                    even.push_back(s[i]);
                else
                    odd.push_back(s[i]);
            }
            sort(even.begin(), even.end());
            sort(odd.begin(), odd.end());
            int even_idx = 0, odd_idx = 0;
            for (int i = 0; i < n; i++)
            {
                if (i % 2 == 0)
                {
                    s[i] = even[even_idx++];
                }
                else
                {
                    s[i] = odd[odd_idx++];
                }
            }
        }
        else
        {
            sort(s.begin(), s.end());
        }
        cout << s << endl;
    }
}