# [Solution] Rain solution codeforces – You are the owner of a harvesting field which can be modeled as an infinite line, whose positions are identified by integers.

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

## [Solution] Rain solution codeforces

It will rain for the next 𝑛n days. On the 𝑖i-th day, the rain will be centered at position 𝑥𝑖xi and it will have intensity 𝑝𝑖pi. Due to these rains, some rainfall will accumulate; let 𝑎𝑗aj be the amount of rainfall accumulated at integer position 𝑗j. Initially 𝑎𝑗aj is 00, and it will increase by max(0,𝑝𝑖|𝑥𝑖𝑗|)max(0,pi−|xi−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 𝑎𝑗>𝑚aj>m.

You can use a magical spell to erase exactly one day’s rain, i.e., setting 𝑝𝑖=0pi=0. For each 𝑖i from 11 to 𝑛n, check whether in case of erasing the 𝑖i-th day’s rain there is no flood.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡1041≤t≤104). The description of the test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑚m (1𝑛21051≤n≤2⋅1051𝑚1091≤m≤109) — 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 𝑥𝑖xi and 𝑝𝑖pi (1𝑥𝑖,𝑝𝑖1091≤xi,pi≤109) — the position and intensity of the 𝑖i-th day’s rain.

The sum of 𝑛n over all test cases does not exceed 21052⋅105.

## [Solution] Rain solution codeforces

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.

Example
input

Copy
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

output

Copy
001
11
00
100110


## [Solution] Rain solution codeforces

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.