## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Rain Codeforces Solution | Solution Codeforces

D. Rain
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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\left(0,{p}_{i}-|{x}_{i}-j|\right)$ 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}>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.

Input

Solution Click Below:-  👉
👇👇👇👇👇

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

The first line of each test case contains two integers $n$ and $m$ ($1\le n\le 2\cdot {10}^{5}$$1\le m\le {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\le {x}_{i},{p}_{i}\le {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}$.

Output

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.