之前TLE#2，卡常之后能勉强过，但#4还是T

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define int ll
#define up(i, a, b) for (int i = a; i <= b; i++)
#define clr(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();}
    return x * f;
}
const int N = 1e6 + 5;
int n, m, x[N], p[N], mp[N], a[N], b[N], na, nb, num[N], tot; // a++,b-=2
signed main() {
    int T = read();
    while (T--) {
        clr(mp, 0);
        na = nb = tot = 0;
        n = read(), m = read();
        up(i, 1, n) {
            x[i] = read(), p[i] = read();
            a[++na] = x[i] - p[i] + 1;
            a[++na] = x[i] + p[i] + 1;
            b[++nb] = x[i] + 1;
        }
        up(i, 1, na) num[++tot] = a[i];
        up(i, 1, nb) num[++tot] = b[i];
        sort(num + 1, num + tot + 1);
        tot = unique(num + 1, num + tot + 1) - (num + 1);
        up(i, 1, na) {
            int now = lower_bound(num + 1, num + tot + 1, a[i]) - num;
            mp[now] ++;
        }
        up(i, 1, nb) {
            int now = lower_bound(num + 1, num + tot + 1, b[i]) - num;
            mp[now] -= 2;
        }
        int b = 0, k = 0;
        int b1 = -1e18, b2 = -1e18;
        up(i, 1, tot) {
            b += k * (num[i] - num[i - 1]);
            k += mp[i];
            if (b > m) {
                b1 = max(b1, b - num[i] + 1);
                b2 = max(b2, b + num[i] - 1);
            }
        }
        up(i, 1, n) putchar(((p[i] - x[i] + m >= b1) && (p[i] + x[i] + m >= b2)) ? '1' : '0');
        puts("");
    }
    return 0;
}