CF1710B.Rain

You are the owner of a harvesting field which can be modeled as an infinite line, whose positions are identified by integers.

It will rain for the next $n$ days. On the $i$-th day, the rain will be centered at position $x_i$ and it will have intensity $p_i$. Due to these rains, some rainfall will accumulate; let $a_j$ be the amount of rainfall accumulated at integer position $j$. Initially $a_j$ is $0$, and it will increase by $\max(0,p_i-|x_i-j|)$ after the $i$-th day's rain.

A flood will hit your field if, at any moment, there is a position $j$ with accumulated rainfall $a_j \gt m$.

You can use a magical spell to erase exactly one day's rain, i.e., setting $p_i=0$. For each $i$ from $1$ to $n$, check whether in case of erasing the $i$-th day's rain there is no flood.

你拥有一片可建模为无限长直线的收割田地，其位置由整数标识。

接下来 $n$ 天将有降雨。第 $i$ 天的降雨中心位于位置 $x_i$，强度为 $p_i$。受这些降雨影响，部分雨水将累积；设 $a_j$ 表示整数位置 $j$ 处累积的雨量。初始时所有 $a_j = 0$，而在第 $i$ 天降雨后，每个位置 $j$ 的累积雨量将增加 $\max(0,p_i-|x_i-j|)$。

若在任意时刻存在某个位置 $j$ 满足累积雨量 $a_j > m$，则你的田地将遭遇洪灾。

你可以使用一个魔法咒语，恰好消除某一天的降雨（即令该天的 $p_i = 0$）。对每个 $i$（从 $1$ 到 $n$），请判断：若消除第 $i$ 天的降雨，是否能避免洪灾。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq m \leq 10^9$) — the number of rainy days and the maximal accumulated rainfall with no flood occurring.

Then $n$ lines follow. The $i$-th of these lines contains two integers $x_i$ and $p_i$ ($1 \leq x_i,p_i \leq 10^9$) — the position and intensity of the $i$-th day's rain.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \leq t \leq 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq m \leq 10^9$）—— 分别表示降雨天数和不发生洪水时的最大累计降雨量。

接下来是 $n$ 行。其中第 $i$ 行包含两个整数 $x_i$ 和 $p_i$（$1 \leq x_i,p_i \leq 10^9$）—— 分别表示第 $i$ 天降雨的位置和强度。

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output a binary string $s$ length of $n$. The $i$-th character of $s$ is 1 if after erasing the $i$-th day's rain there is no flood, while it is 0, if after erasing the $i$-th day's rain the flood still happens.

对于每个测试用例，输出一个长度为 $n$ 的二进制字符串 $s$。其中，$s$ 的第 $i$ 个字符为 1，表示删除第 $i$ 天的降雨后不会发生洪水；若删除第 $i$ 天的降雨后洪水仍然发生，则该字符为 0。

In the first test case, if we do not use the spell, the accumulated rainfall distribution will be like this:

If we erase the third day's rain, the flood is avoided and the accumulated rainfall distribution looks like this:

In the second test case, since initially the flood will not happen, we can erase any day's rain.

In the third test case, there is no way to avoid the flood.

在第一个测试用例中，如果不使用魔法，累积降雨量分布如下所示：

如果擦除第三天的降雨，则可避免洪水，此时累积降雨量分布如下所示：

在第二个测试用例中，由于初始状态下不会发生洪水，因此可以擦除任意一天的降雨。

在第三个测试用例中，不存在避免洪水的方法。