#include <bits/stdc++.h>

using namespace std;

void tryMerge(vector<priority_queue<int, vector<int>, greater<int>>>& s, vector<int>& merged) {
  if (merged.size() < 2) return;
  int x = merged[merged.size() - 2];
  int y = merged[merged.size() - 1];
  while (merged.size() >= 2 && s[x].top() >= s[y].top()) {
    if (s[x].size() < s[y].size()) {
      swap(x, y);
    }
    while (!s[y].empty()) {
      s[x].push(s[y].top());
      s[y].pop();
    }
    merged.pop_back();
    merged.pop_back();
    merged.push_back(x);
    if (merged.size() < 2) return;
    x = merged[merged.size() - 2];
    y = merged[merged.size() - 1];
  }
}


pair<vector<vector<int>>, vector<int>> fastSimulate(const vector<int>& a) {
  int n = a.size();
  vector<priority_queue<int, vector<int>, greater<int>>> s(n);

  vector<int> par(n, -1), alive(n);
  iota(alive.begin(), alive.end(), 0);
  for (int i = 0; i < n; ++i) {
    s[i].push(a[i]);
  }
  vector<vector<int>> result;

  while (!alive.empty()) {
    vector<int> merged;
    for (int i: alive) {
      merged.push_back(i);
      tryMerge(s, merged);
    }

    vector<int> tmp, nxtAlive;
    for (int i: merged) {
      assert(!s[i].empty());
      int x = s[i].top();
      s[i].pop();

      tmp.push_back(x);
      if (!s[i].empty()) {
        nxtAlive.push_back(i);
        par[s[i].top()] = x;
      }
    }

    result.push_back(tmp);
    alive.swap(nxtAlive);
  }

  return make_pair(result, par);
}

array<int, 2> findFirstDiffOfNextPermutation(const vector<int>& a, int l, int r) {
  if (l >= r) {
    return {INT_MAX, INT_MAX};
  }

  int maxVal = a[r];
  for (int i = r - 1; i >= l; --i) {
    if (a[i] < maxVal) {
      int p = lower_bound(a.begin() + i + 1, a.begin() + r + 1, a[i], greater<int>()) - a.begin() - 1;
      return {-i, a[p]};
    } else {
      maxVal = a[i];
    }
  }
  return {INT_MAX, INT_MAX};
}

void validatePermutation(const vector<int>& a) {
  vector<int> p(a.size()), tmp = a;
  iota(p.begin(), p.end(), 0);
  sort(tmp.begin(), tmp.end());
  assert(p == tmp);
}

vector<int> solve(const vector<int>& a) {
  validatePermutation(a);

  const int n = a.size();
  vector<vector<int>> state;
  vector<int> par, pos(n);
  tie(state, par) = fastSimulate(a);
  for (int i = 0; i < n; ++i) {
    pos[a[i]] = i;
  }

  // find best prefix
  vector<int> lowestPar = par;
  array<int, 2> best = {INT_MAX, INT_MAX}; // (-pos, value)

  best = min(best, findFirstDiffOfNextPermutation(a, 0, pos[state[0][0]] - 1));
  for(int i = 0; i + 1 < (int) state[0].size(); ++i) {
    best = min(best, findFirstDiffOfNextPermutation(a, pos[state[0][i]] + 1, pos[state[0][i + 1]] - 1));
  }

  for (auto x: state[0]) {
    lowestPar[x] = x;
  }
  for (int i = 1; i < (int) state.size(); ++i) {
    int last = -1, ptr = 0;
    for (auto x : state[i]) {
      lowestPar[x] = lowestPar[par[x]];
      while (state[i - 1][ptr] != par[x]) {
        assert(++ptr < (int) state[i - 1].size());
      }
      if (last < ptr - 1) {
        assert(x > lowestPar[state[i - 1][ptr - 1]]);
        best = min(best, {-pos[lowestPar[state[i - 1][ptr - 1]]], x});
      }
      last = ptr;
    }
  }

  // check if solution exists
  if (best[0] == INT_MAX) {
    return {-2};
  }

  // construct min from prefix :))
  int firstDiffPos = -best[0];
  int firstDiffValue = best[1];
  vector<int> prefix(a.begin(), a.begin() + firstDiffPos);
  prefix.push_back(firstDiffValue);

  vector<bool> deleted(n, false);
  for (int i = 0; i < firstDiffPos; ++i) {
    deleted[a[i]] = true;
  }
  deleted[firstDiffValue] = true;

  // find new par
  // - par of i < firstDiff: unchanged
  // - par of i = firstDiff: inferred from prefix
  // - par of i > firstDiff: gready

  // find par for firstDiff
  vector<priority_queue<int, vector<int>, greater<int>>> s(prefix.size());
  vector<int> alive;
  for (int i = 0; i < (int) prefix.size(); ++i) {
    s[i].push(prefix[i]);
    alive.push_back(i);
  }
  par[firstDiffValue] = -1;
  int index = 0;
  while (!alive.empty()) {
    vector<int> merged;
    for (int i: alive) {
      merged.push_back(i);
      tryMerge(s, merged);
    }

    int ptr = 0;
    assert(index < (int) state.size());
    for (auto x: merged) {
      assert(ptr < (int) state[index].size());
      if (state[index][ptr] == s[x].top()) {
        ++ptr;
      } else {
        assert(ptr < (int) state[index].size());
        s[merged.back()].push(state[index][ptr]);
        tryMerge(s, merged);
        assert((int) merged.size() == ptr + 1);
        break;
      }
    }

    vector<int> nextAlive;
    ptr = 0;
    for (auto x: merged) {
      assert(ptr < (int)state[index].size() && s[x].top() == state[index][ptr]);
      ++ptr;

      int p = s[x].top();
      s[x].pop();
      if (!s[x].empty()) {
        par[s[x].top()] = p;
        nextAlive.push_back(x);
      }
    }

    ++index;
    alive.swap(nextAlive);
  }

  // find par for the rest
  for (int i = 1; i < (int)state.size(); ++i) {
    int ptr = state[i - 1].size() - 1;
    for (int j = state[i].size() - 1; j >= 0; --j) {
      if (deleted[state[i][j]]) {
        break;
      }
      while (ptr >= 0 && state[i - 1][ptr] > state[i][j]) {
        --ptr;
      }
      assert(ptr >= 0);
      par[state[i][j]] = state[i - 1][ptr];
      --ptr;
    }
  }

  // find minimum suffix
  for (auto x: state[0]) {
    lowestPar[x] = x;
  }
  for (int i = 1; i < (int) state.size(); ++i) {
    for (auto x: state[i]) {
      lowestPar[x] = lowestPar[par[x]];
    }
  }

  vector<int> suffix;
  vector<vector<int>> suffixSegs(n);
  for (int i = 0; i < n; ++i) {
    if (!deleted[i] && lowestPar[i] != i) {
      suffixSegs[lowestPar[i]].push_back(i);
    }
  }
  for (auto x: state[0]) {
    if (deleted[x]) {
      continue;
    }
    sort(suffixSegs[x].begin(), suffixSegs[x].end());
    suffixSegs[x].push_back(x);
    for (int y: suffixSegs[x]) {
      suffix.push_back(y);
    }
  }

  vector<int> res(n);
  copy(prefix.begin(), prefix.end(), res.begin());
  copy(suffix.begin(), suffix.end(), res.begin() + prefix.size());

  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int tc;
  cin >> tc;
  while (tc--) {
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    for (auto& x : a) {
      cin >> x;
      --x;
    }
    for (auto x: solve(a)) {
      cout << x + 1 << ' ';
    }
    cout << '\n';
  }

  return 0;
}