#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
struct element{
int position ;
int age ;
string name ;
element(int position, int age, string name)
: position(position), age(age), name(name)
{
}
} ;
// position will be different so two people cannot be totally same
bool comparator(element &a, element &b){
if(a.age == b.age){
if(a.name == b.name){
return a.position < b.position ;
} else
return a.name < b.name ;
} else
return a.age < b.age ;
}
void solve(){
deque < element > q ; q.clear() ;
vector < element > vec ; vec.clear() ;
int n, m ; cin >> n >> m ;
for(int i = 0 ; i < n ; i++){
int age ; string name ;
cin >> name >> age ;
q.push_back(element(i, age, name)) ;
}
for(int i = 0 ; i < m ; i++){
bool flag = comparator(q.front(), q.back()) ;
if(flag == 1){
vec.push_back(q.front()) ;
q.pop_front() ;
} else{
vec.push_back(q.back()) ;
q.pop_back() ;
}
}
sort(vec.begin(), vec.end(), comparator) ;
for(int i = 0 ; i < m ; i++){
cout << vec[i].position << " " ;
}
cout << "\n" ;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("sample input.txt", "r", stdin) ;
freopen("outputc.txt", "w", stdout) ;
#endif
ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
int t ; cin >> t ;
while(t--) solve() ;
return 0 ;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQgOwp0eXBlZGVmIGxvbmcgbG9uZyBsbCA7CgpzdHJ1Y3QgZWxlbWVudHsKCglpbnQgcG9zaXRpb24gOwoJaW50IGFnZSA7CglzdHJpbmcgbmFtZSA7CgoJZWxlbWVudChpbnQgcG9zaXRpb24sIGludCBhZ2UsIHN0cmluZyBuYW1lKQoJCTogcG9zaXRpb24ocG9zaXRpb24pLCBhZ2UoYWdlKSwgbmFtZShuYW1lKQoJewoJfQoKfSA7CgovLyBwb3NpdGlvbiB3aWxsIGJlIGRpZmZlcmVudCBzbyB0d28gcGVvcGxlIGNhbm5vdCBiZSB0b3RhbGx5IHNhbWUKYm9vbCBjb21wYXJhdG9yKGVsZW1lbnQgJmEsIGVsZW1lbnQgJmIpewoKCWlmKGEuYWdlID09IGIuYWdlKXsKCgkJaWYoYS5uYW1lID09IGIubmFtZSl7CgoJCQlyZXR1cm4gYS5wb3NpdGlvbiA8IGIucG9zaXRpb24gOwoKCQl9IGVsc2UKCQkJcmV0dXJuIGEubmFtZSA8IGIubmFtZSA7CgoJfSBlbHNlCgkJcmV0dXJuIGEuYWdlIDwgYi5hZ2UgOwoKfQoKdm9pZCBzb2x2ZSgpewoKCWRlcXVlIDwgZWxlbWVudCA+IHEgOyBxLmNsZWFyKCkgOwoJdmVjdG9yIDwgZWxlbWVudCA+IHZlYyA7IHZlYy5jbGVhcigpIDsKCglpbnQgbiwgbSA7IGNpbiA+PiBuID4+IG0gOwoJZm9yKGludCBpID0gMCA7IGkgPCBuIDsgaSsrKXsKCQlpbnQgYWdlIDsgc3RyaW5nIG5hbWUgOwoJCWNpbiA+PiBuYW1lID4+IGFnZSA7CgkJcS5wdXNoX2JhY2soZWxlbWVudChpLCBhZ2UsIG5hbWUpKSA7Cgl9CgoJZm9yKGludCBpID0gMCA7IGkgPCBtIDsgaSsrKXsKCgkJYm9vbCBmbGFnID0gY29tcGFyYXRvcihxLmZyb250KCksIHEuYmFjaygpKSA7CgoJCWlmKGZsYWcgPT0gMSl7CgkJCXZlYy5wdXNoX2JhY2socS5mcm9udCgpKSA7CgkJCXEucG9wX2Zyb250KCkgOwoJCX0gZWxzZXsKCQkJdmVjLnB1c2hfYmFjayhxLmJhY2soKSkgOwoJCQlxLnBvcF9iYWNrKCkgOwoJCX0KCgl9CgoJc29ydCh2ZWMuYmVnaW4oKSwgdmVjLmVuZCgpLCBjb21wYXJhdG9yKSA7CgoJZm9yKGludCBpID0gMCA7IGkgPCBtIDsgaSsrKXsKCQljb3V0IDw8IHZlY1tpXS5wb3NpdGlvbiA8PCAiICIgOwoJfQoKCWNvdXQgPDwgIlxuIiA7Cgp9CgppbnQgbWFpbigpewoKCSNpZm5kZWYgT05MSU5FX0pVREdFCgkJZnJlb3Blbigic2FtcGxlIGlucHV0LnR4dCIsICJyIiwgc3RkaW4pIDsKCQlmcmVvcGVuKCJvdXRwdXRjLnR4dCIsICJ3Iiwgc3Rkb3V0KSA7CgkjZW5kaWYKCglpb3M6OnN5bmNfd2l0aF9zdGRpbygwKSA7IGNpbi50aWUoMCkgOyBjb3V0LnRpZSgwKSA7CgoJaW50IHQgOyBjaW4gPj4gdCA7Cgl3aGlsZSh0LS0pIHNvbHZlKCkgOwoKCXJldHVybiAwIDsKfQo=