您是一块收割田的所有者,该田地可以建模为一条无限线,其位置由整数标识。
接下来 $$$n$$$ 天将会下雨。在第 $$$i$$$ 天,降雨将集中在位置 $$$x_i$$$,强度为 $$$p_i$$$。由于这些降雨,部分降雨量将会累积;令 $$$a_j$$$ 为整数位置 $$$j$$$ 处累积的降雨量。最初 $$$a_j$$$ 为 $$$0$$$,第 $$$i$$$ 天下雨后,$$$\max(0,p_i-|x_i-j|)$$$ 会增加 $$$。
如果在任何时刻,某个位置 $$$j$$$ 的累积降雨量为 $$$a_j>m$$$,洪水就会袭击你的田地。
你可以使用魔法咒语准确地消除一天的雨,即设置$$$p_i=0$$$。对于从$$$1$$$到$$$n$$$的每个$$$i$$$,检查在消除第$$$i$$$天的降雨的情况下是否没有洪水。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出一个二进制字符串 $$$s$$$ 长度为 $$$n$$$。如果清除第$$$i$$$天的降雨后没有发生洪水,则$$$s$$$的第$$$i$$$字符为1;如果清除第$$$i$$$天的降雨后仍然发生洪水,则$$$i$$$的第$$$i$$$字符为0。
示例
输入 #1
4 3 6 1 5 5 5 3 4 2 3 1 3 5 2 2 5 1 6 10 6 6 12 4 5 1 6 12 5 5 5 9 7 8 3
输出 #1
001 11 00 100110
注意
在第一个测试用例中,如果我们不使用该咒语,累计降雨量分布将是这样的:
如果我们消除第三天的降雨,就可以避免洪水,累积降雨量分布如下:
在第二个测试用例中,由于最初不会发生洪水,因此我们可以消除任何一天的降雨。
在第三个测试用例中,没有办法避免洪水。