**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.

Table of Contents

## [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.

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≤𝑛≤2⋅1051≤n≤2⋅105, 1≤𝑚≤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 2⋅1052⋅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.

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

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:

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