#include <bits/stdc++.h>
using namespace std;
template <typename T>
class Hungarian {
  const T FINF = numeric_limits<T>::max() / 2.0;

 public:
  int n, m;
  vector<T> u, v, p, way;
  Hungarian(){};
  Hungarian(vector<vector<T> > a) {
    n = a.size() - 1;
    m = a[0].size() - 1;
    u.resize(n + 2);
    v.resize(m + 2);
    p.resize(m + 2);
    way.resize(m + 2);
    for (int i = 1; i <= n; ++i) {
      p[0] = i;
      int j0 = 0;
      vector<T> minv(m + 1, FINF);
      vector<bool> used(m + 1, false);
      do {
        used[j0] = true;
        int i0 = p[j0], j1;
        T delta = FINF;
        for (int j = 1; j <= m; ++j)
          if (!used[j]) {
            int cur = a[i0][j] - u[i0] - v[j];
            if (cur < minv[j]) minv[j] = cur, way[j] = j0;
            if (minv[j] < delta) delta = minv[j], j1 = j;
          }
        for (int j = 0; j <= m; ++j)
          if (used[j])
            u[p[j]] += delta, v[j] -= delta;
          else
            minv[j] -= delta;
        j0 = j1;
      } while (p[j0] != 0);
      do {
        int j1 = way[j0];
        p[j0] = p[j1];
        j0 = j1;
      } while (j0);
    }
  }
  T getCost() { return -v[0]; }
  vector<int> getAns() {
    vector<int> ans(n + 1);
    for (int j = 1; j <= m; ++j) ans[p[j]] = j;
    return ans;
  }
};
int main() {
  int test;
  scanf("%d", &test);
  while (test--) {
    int n, k;
    scanf("%d %d", &n, &k);
    vector<int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
      scanf("%d %d", &a[i], &b[i]);
    }
    vector<vector<int> > cost(n, vector<int>(n));
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        cost[i][j] = (j < k) ? -(a[i] + j * b[i]) : -((k - 1) * b[i]);
      }
    }
    Hungarian<int> g(cost);
    vector<int> out;
    for (int i = 1; i < k; ++i) {
      out.emplace_back(g.p[i] + 1);
    }
    for (int i = k + 1; i <= n; ++i) {
      out.emplace_back(g.p[i] + 1);
      out.emplace_back(-g.p[i] - 1);
    }
    out.emplace_back(g.p[k] + 1);
    for (int i = 0; i < out.size(); ++i) {
      printf("%d%c", out[i], " \n"[i + 1 == out.size()]);
    }
  }
  return 0;
}
