#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; ++i)
#define _req(i, x, y) for(int i = x; i >= y; --i)
#define _rev(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define mst(f, i) memset(f, i, sizeof f)
using namespace std;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
typedef pair<int, int> PII;
namespace fastio{
    #ifdef ONLINE_JUDGE
    char ibuf[1 << 20],*p1 = ibuf, *p2 = ibuf;
    #define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++
    #else
    #define get() getchar()
    #endif
    template<typename T> inline void read(T &t){
        T x = 0, f = 1;
        char c = getchar();
        while(!isdigit(c)){
            if(c == '-') f = -f;
            c = getchar();
        }
        while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
        t = x * f;
    }
    template<typename T, typename ... Args> inline void read(T &t, Args&... args){
        read(t);
        read(args...);
    }
    template<typename T> void write(T t){
        if(t < 0) putchar('-'), t = -t;
        if(t >= 10) write(t / 10);
        putchar(t % 10 + '0');
    }
    template<typename T, typename ... Args> void write(T t, Args... args){
        write(t), putchar(' '), write(args...);
    }
    template<typename T> void writeln(T t){
        write(t);
        puts("");
    }
    template<typename T> void writes(T t){
        write(t), putchar(' ');
    }
    #undef get
};
using namespace fastio;
#define multitest() int T; read(T); _rep(tCase, 1, T)
namespace Calculation{
    const ll mod = 998244353;
    ll ksm(ll p, ll h){ll base = p % mod, res = 1; while(h){if(h & 1ll) res = res * base % mod; base = base * base % mod, h >>= 1ll;} return res;}
    void dec(ll &x, ll y){x = ((x - y) % mod + mod) % mod;}
    void add(ll &x, ll y){x = (x + y) % mod;}
    void mul(ll &x, ll y){x = x * y % mod;}
    ll sub(ll x, ll y){return ((x - y) % mod + mod) % mod;}
    ll pls(ll x, ll y){return ((x + y) % mod + mod) % mod;}
    ll mult(ll x, ll y){return x * y % mod;}
}
using namespace Calculation;
const int N = 1e6 + 5;
ll n, p, len, lsh[N << 1];
ll sum[N << 1], cnt[N << 1], f[N << 1], g[N << 1];
ll minx[N << 1][25], maxn[N << 1][25];
ll qmin(ll l, ll r){
    ll k = __lg(r - l + 1);
    return min(minx[l][k], minx[r - (1 << k) + 1][k]);
}
ll qmax(ll l, ll r){
    ll k = __lg(r - l + 1);
    return max(maxn[l][k], maxn[r - (1 << k) + 1][k]);
}
bool flag, flag2;
void solve(){
    read(n, p);
    map<int, ll> mp[2];
    vector<ll> vt[2];
    ll tot[2] = {0, 0};
    // if(flag && flag2) write(n, p), puts("");
    _rep(i, 1, n){
        ll a, b, c, d; read(a, b, c, d), a--;
        if(mp[a][b] == -1) continue;
        if(d){
            tot[a] += mp[a][b] * p + c, vt[a].pb(c);
            mp[a][b] = -1;
        }else mp[a][b]++;
        // if(flag && flag2) write(a + 1, b, c, d), puts("");
    }
    // _rep(i, 0, 1){
    //     for(auto &j : vt[i]) debug("%d ", j);
    //     debug("\n");
    // }
    // debug("[%d,%d]\n=============\n", tot[0], tot[1]);
    if(vt[0].size() != vt[1].size() || vt[0].empty()) return puts("-1"), void();
    ll k = 0;
    if(tot[0] <= tot[1]){
        k = tot[1] - tot[0] + 1;
        swap(vt[0], vt[1]);
    }else k = tot[0] - tot[1];
    len = 0; _rep(i, 0, 1) for(auto &j : vt[i]) lsh[++len] = j;
    lsh[++len] = 0;
    sort(lsh + 1, lsh + 1 + len), len = unique(lsh + 1, lsh + 1 + len) - lsh - 1;
    _rep(i, 0, 1){
        ll op = !i ? 1 : -1;
        for(auto &j : vt[i]){
            j = lower_bound(lsh + 1, lsh + 1 + len, j) - lsh;
            cnt[1] += op, cnt[j + 1] -= op;
            sum[1] += lsh[j] * op, sum[j + 1] -= lsh[j] * op;
        }
    }
    _rep(i, 1, len){
        cnt[i] += cnt[i - 1], sum[i] += sum[i - 1];
        f[i] = sum[i] - lsh[i] * cnt[i], g[i] = sum[i] - (lsh[i - 1] + 1) * cnt[i];
    }
    _rep(i, 1, len){
        minx[i][0] = f[i];
        maxn[i][0] = f[i];
    }
    _rep(i, 1, 20) _rep(j, 1, len - (1 << i) + 1){
        minx[j][i] = min(minx[j][i - 1], minx[j + (1 << i - 1)][i - 1]);
        maxn[j][i] = max(maxn[j][i - 1], maxn[j + (1 << i - 1)][i - 1]);
    }
    // debug("f[120]:%d f[160]:%d\n", f[120], f[160]);
    ll L = -1, R = 0;
    auto update = [&](ll i, ll j) -> void{
        if(L == -1 || (j - i) < (R - L) || (j - i) == (R - L) && i < L){
            L = i, R = j;
        }
    };
    _rep(i, 1, len){
        if(i < len){
            ll l = i + 1, r = len, res = 0, t = f[i];
            while(l <= r){
                ll mid = l + r >> 1ll, cur = qmin(i + 1, mid);
                if(t - cur >= k) res = mid, r = mid - 1;
                else l = mid + 1;
            }
            if(res){
                ll cur = t - f[res] - k, o = lsh[res] - lsh[res - 1], p = cnt[res];
                ll cl = lsh[i], cr = lsh[res] - min(o, cur / p);
                update(cl, cr);
            }
        }
        if(i > 1){
            ll l = 1, r = i - 1, res = 0, t = f[i];
            while(l <= r){
                ll mid = l + r >> 1ll, cur = qmax(mid, i - 1);
                if(cur - t >= k) res = mid, l = mid + 1;
                else r = mid - 1;
            }
            if(res){
                ll cur = f[res] - t - k, o = lsh[res + 1] - lsh[res], p = cnt[res + 1];
                ll cl = lsh[res] + min(o, cur / p), cr = lsh[i];
                update(cl, cr);
            }
        }
    }
    // if(!flag){
    if(L == -1) puts("-1");
    else{
        while(L > 0){
            ll tl = L - 1, tr = R - 1;
            ll pl = lower_bound(lsh + 1, lsh + 1 + len, tl) - lsh, pr = lower_bound(lsh + 1, lsh + 1 + len, tr) - lsh;
            if(sum[pl] - tl * cnt[pl] - sum[pr] + tr * cnt[pr] >= k) L--, R--;
            else break;
        }
        write(L, R), puts("");
    }
    // }
}
int main(){
    multitest(){
        flag = T == 1e4, flag2 = tCase == 6;
        solve();
        _rep(i, 0, len + 1) sum[i] = cnt[i] = lsh[i] = f[i] = g[i] = 0, mst(minx[i], 0), mst(maxn[i], 0);
        len = 0;
    }    
    return 0;
}