AT_abc434_c [ABC434C] Flapping Takahashi

Takahashi has decided to fly in the sky with balloons. Takahashi is at altitude $ H $ at time $ 0 $ (the unit is seconds), and will fly for $ 10^9 $ seconds from now. Takahashi can change his flying altitude by up to $ 1 $ per second. However, he cannot make his altitude $ 0 $ or less. - In other words, if $ F(t) $ denotes Takahashi's altitude at time $ t $ , then $ F(t) $ satisfies all of the following conditions: - $ F(0) = H $ - $ -1 \leq \dfrac{F(u) - F(t)}{u - t} \leq 1 $ for $ 0 \leq t \lt u \leq 10^9 $ . - $ F(t) \gt 0 $ for $ 0 \leq t \leq 10^9 $ . There are $ N $ goals regarding altitude. The $ i $ -th goal is to make the altitude at time $ t_i $ at least $ l_i $ and at most $ u_i $ . Is it possible for Takahashi to fly in a way that achieves all goals? You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format, where $ \mathrm{case}_i $ denotes the $ i $ -th test case. > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ H $ $ t_1 $ $ l_1 $ $ u_1 $ $ t_2 $ $ l_2 $ $ u_2 $ $ \vdots $ $ t_N $ $ l_N $ $ u_N $

Output $ T $ lines. The $ i $ -th line should contain `Yes` if it is possible to fly in a way that achieves all goals in the $ i $ -th test case, and `No` otherwise.

### Sample Explanation 1 For the first test case, Takahashi can achieve all goals by flying as follows: - At time $ 0 $ , he is at altitude $ 5 $ . - From time $ 0 $ to time $ 2 $ , he descends at a rate of $ 0.5 $ per second. - At time $ 2 $ , he is at altitude $ 5 - 0.5 \times 2 = 4 $ . - From time $ 2 $ to time $ 3 $ , he stays at the same altitude. - At time $ 3 $ , he is at altitude $ 4 $ . He satisfies the first goal. - From time $ 3 $ to time $ 8 $ , he ascends at a rate of $ 1 $ per second. - At time $ 8 $ , he is at altitude $ 4 + 1 \times 5 = 9 $ . He satisfies the second goal. For the second test case, he cannot achieve all goals no matter how he flies. ### Constraints - $ 1 \leq T \leq 10^5 $ - $ 1 \leq N \leq 10^5 $ - $ 1 \leq H \leq 10^9 $ - $ 1 \leq t_1 \lt t_2 \lt \dots \lt t_N \leq 10^9 $ - $ 1 \leq l_i \leq u_i \leq 10^9 $ - The sum of $ N $ over all test cases is at most $ 10^5 $ . - All input values are integers.