$M=2$

显然 $M=2$ 是比较好做的。
正着移除显然不好做，那就反着加入矩形。
每次加入一个矩形 $i$ 之后需要求它的右上角的左下区域是否存在至少一个矩形的左下角。显然如果一个矩形的左下角在范围里那它一定有一部分在范围里。

这比较好统计，拿一个树状数组求 $[1,x]$ 前缀的最小 $y$ 值即可。

$M=1$

这相当于求拓扑序。
考虑用“出栈序”推出一个拓扑序。
设当前 dfs 到矩形 $u$，每次随便找一个矩形 $v$，满足需要先扔掉 $u$ 才能扔掉 $v$，即 $v$ 的右上角在 $u$ 的左下角的右上区域中，然后往 $v$ dfs。

最后把出栈序反过来就是拓扑序。
这很好理解，因为 $u$ 的后继 $v$ 在出栈序里必须在 $u$ 前面，反之，在拓扑序里必须在 $u$ 的后面。

这里“随便找一个 $v$”比较玄学，并不好维护，所以可以选择直接取 $y$ 最大的。
但是访问过的不能再访问，树状数组求最大值并不支持“删除”。
因此对于矩形的右上角，把 $x$ 相同的 $y$ 进行“错开”操作，即令它们离散化后的 $x$ 不同且相邻，这样删除一个点相当于把它的 $y$ 置为 $0$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, INF = 0x3f3f3f3f;
int T, n, m;

struct Subtask1 {
    struct node {
        int x, y, opt, id;
        bool operator < (const node b) const {
            if (x == b.x) {
                if (opt ^ b.opt) return opt < b.opt;
                return y < b.y;
            }
            return x < b.x;
        }
    } a[N << 1];

    int ID[N << 1], X[N << 1], tx, Y[N << 1], ty;
    int xx[N], yy[N], xxx[N], yyy[N];   // 编号为 i 的矩形左下角、右上角坐标

    struct Tree {
        int l, r;
        int id; // y 坐标最大的点的编号
    } tr[N << 2];
    int getmx(int a, int b) {
        if (a == -1) return b;
        if (b == -1) return a;
        return yyy[a] > yyy[b] ? a : b;
    }
    void pushup(int u) { tr[u].id = getmx(tr[u << 1].id, tr[u << 1 | 1].id); }
    void build(int u, int l, int r) {
        tr[u].l = l, tr[u].r = r;
        if (l == r) return tr[u].id = ID[l], void();
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
    void del(int u, int x) {
        if (tr[u].l == tr[u].r) return tr[u].id = -1, void();
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) del(u << 1, x);
        else del(u << 1 | 1, x);
        pushup(u);
    }
    int query(int u, int l, int r) {
        if (l > r) return -1;
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].id;
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        if (l > mid) return query(u << 1 | 1, l, r);
        return getmx( query(u << 1, l, r), query(u << 1 | 1, l, r) );
    }

    int ans[N], anst = 0;
    bool st[N];

    void dfs(int u) {
        st[u] = 1, del(1, xxx[u]);
        while (1) {
            int nxt = query(1, xx[u] + 1, tx);
            if (nxt == -1 || yyy[nxt] < yy[u]) break;
            // cout << '\t' << u << ' ' << nxt << endl;
            dfs(nxt);
        }
        ans[++anst] = u;
    }

    void clr() {
        for (int i = 1; i <= n; i++) st[i] = 0; anst = 0;
        tx = ty = 0;
        for (int i = 1; i <= n * 2; i++) a[i].x = a[i].y = a[i].opt = a[i].id = 0, X[i] = Y[i] = xx[i] = yy[i] = xxx[i] = yyy[i] = 0;
    }

    void solve() {
        scanf("%d", &n), ++n;
        clr();
        for (int i = 1; i <= (n - 1) * 2; i++) scanf("%d%d", &a[i].x, &a[i].y), a[i].opt = (i & 1) ? 1 : 2, a[i].id = (i + 1) >> 1;
        a[n * 2 - 1] = {0, 0, 1, n}, a[n * 2] = {0, 0, 2, n};
        sort(a + 1, a + 1 + n * 2);
        int cc = 0, lst = 0;
        for (int i = 1; i <= n * 2; i++) {
            int now = a[i].x;
            if (a[i].x == lst) ++cc;  //错开
            a[i].x += cc;
            lst = now;
        }
        for (int i = 1; i <= n * 2; i++) X[i] = a[i].x, Y[i] = a[i].y;

        sort(X + 1, X + 1 + n * 2), tx = unique(X + 1, X + 1 + n * 2) - X - 1;
        sort(Y + 1, Y + 1 + n * 2), ty = unique(Y + 1, Y + 1 + n * 2) - Y - 1;
        for (int i = 1; i <= n * 2; i++) a[i].x = lower_bound(X + 1, X + 1 + tx, a[i].x) - X, a[i].y = lower_bound(Y + 1, Y + 1 + ty, a[i].y) - Y, ID[a[i].x] = (a[i].opt == 2) ? a[i].id : -1;
        for (int i = 1; i <= n * 2; i++)
            if (a[i].opt == 2) xxx[a[i].id] = a[i].x, yyy[a[i].id] = a[i].y;
            else xx[a[i].id] = a[i].x, yy[a[i].id] = a[i].y;

        // for (int i = 1; i <= n * 2; i++) cout << a[i].x << ' ' << a[i].y << ' ' << a[i].opt << ' ' << a[i].id << endl;
        build(1, 1, tx);

        dfs(n);
        for (int i = n - 1; i >= 1; i--)
            printf("%d ", ans[i]); puts("");
    }
} sub1;

struct Subtask2 {
    int X[N << 1], tx, Y[N << 1], ty;
    struct node { int x, y; } a[N << 1];   // opt=1 左下角；opt=2 右上角
    bool ans[N];

    int tr[N << 1];
    inline void add(int x, int d) { for ( ; x < N; x += x & -x) tr[x] = min(tr[x], d); }
    inline int ask(int x) { if (!x) return INF; int res = INF; for ( ; x ; x -= x & -x) res = min(res, tr[x]); return res; }

    void solve() {
        scanf("%d", &n);
        for (int i = 1, x, y; i <= n * 2; i++) scanf("%d%d", &x, &y), X[i] = a[i].x = x, Y[i] = a[i].y = y;
        sort(X + 1, X + 1 + n * 2), tx = unique(X + 1, X + 1 + n * 2) - X - 1;
        sort(Y + 1, Y + 1 + n * 2), ty = unique(Y + 1, Y + 1 + n * 2) - Y - 1;
        for (int i = 1; i <= n * 2; i++) a[i].x = lower_bound(X + 1, X + 1 + tx, a[i].x) - X, a[i].y = lower_bound(Y + 1, Y + 1 + ty, a[i].y) - Y;
        memset(tr, INF, sizeof tr);
        for (int i = n; i >= 1; i--) ans[i] = (ask(a[i * 2].x - 1) > a[i * 2].y), add(a[i * 2 - 1].x, a[i * 2 - 1].y);
        for (int i = 1; i <= n; i++) putchar(ans[i] ^ 48); putchar('\n');
    }
} sub2;

int main() {
    scanf("%d%d", &T, &m);
    while (T--) {
        if (m == 1) sub1.solve();
        else sub2.solve();
    }
    return 0;
}