AT_joi2024ho_c マラソン大会 2 (Marathon Race 2)

JOI 街道は東西に伸びる長さ $ L $ メートルの道路であり，道路の西端から $ l $ メートル ( $ 0 \leqq l \leqq L $ ) 進んだ場所は地点 $ l $ と呼ばれている． さて，今年は JOI 街道で初めてマラソン大会が開催されることとなった．このマラソン大会は通常のルールとは異なり，次のようなルールに基づいて行われる． - 道路上に $ N $ 個のボールが置かれており， $ i $ 番目 ( $ 1 \leqq i \leqq N $ ) のボールは地点 $ X_i $ に置かれている．複数のボールが同じ地点に置かれていることもある． - 参加者は定められたスタート地点から出発する． - $ N $ 個のボールをすべて持った状態で，定められたゴール地点に制限時間内にたどり着くと**完走**となる．ただし，一度持ったボールを地面に置くと失格となる． この大会のスタート地点，ゴール地点および制限時間はまだ公開されていないが， $ Q $ 個のシナリオのいずれかになることは既に公開されている． $ j $ 番目 ( $ 1 \leqq j \leqq Q $ ) のシナリオでは，スタート地点が地点 $ S_j $ ，ゴール地点が地点 $ G_j $ ，制限時間が $ T_j $ 秒である． マラソン大会の参加者である理恵さんは，ボールを $ 1 $ 個拾うのに $ 1 $ 秒かかり， $ x $ 個のボールを持った状態で道路上を $ 1 $ メートル走るのに $ x+1 $ 秒かかる． JOI 街道，ボール，シナリオに関する情報が与えられたとき，それぞれのシナリオについて，理恵さんが完走する方法が存在するかを判定するプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ L $ $ X_1 $ $ X_2 $ $ \cdots $ $ X_N $ $ Q $ $ S_1 $ $ G_1 $ $ T_1 $ $ S_2 $ $ G_2 $ $ T_2 $ $ \vdots $ $ S_Q $ $ G_Q $ $ T_Q $

標準出力に $ Q $ 行で出力せよ． $ j $ 行目 ( $ 1 \leqq j \leqq Q $ ) には， $ j $ 番目のシナリオにおいて理恵さんが完走する方法が存在する場合 `Yes`，そうでない場合 `No` を出力せよ． ---

### 小課題 1. ( $ 7 $ 点) $ N \leqq 7 $ ， $ Q \leqq 10 $ ， $ S_j = 0 $ ， $ G_j = 0 $ ( $ 1 \leqq j \leqq Q $ )． 2. ( $ 7 $ 点) $ N \leqq 7 $ ， $ Q \leqq 10 $ ． 3. ( $ 10 $ 点) $ N \leqq 14 $ ， $ Q \leqq 10 $ ． 4. ( $ 28 $ 点) $ N \leqq 100 $ ， $ Q \leqq 10 $ ． 5. ( $ 10 $ 点) $ N \leqq 2\,000 $ ， $ Q \leqq 10 $ ． 6. ( $ 19 $ 点) $ N \leqq 2\,000 $ ． 7. ( $ 19 $ 点) 追加の制約はない． --- ### Sample Explanation 1 $ 1 $ 番目のシナリオでは，スタート地点は地点 $ 0 $ ，ゴール地点は地点 $ 100 $ ，制限時間は $ 403 $ 秒である．以下のようにして，制限時間内の $ 263 $ 秒で完走することができる．よって， $ 1 $ 行目には `Yes` を出力する． 順番行動消費時間累計時間1地点 $ 0 $ から出発し，地点 $ 30 $ に移動する． $ 30 $ 秒 $ 30 $ 秒2 $ 1 $ 番目のボールを拾う． $ 1 $ 秒 $ 31 $ 秒3 $ 3 $ 番目のボールを拾う． $ 1 $ 秒 $ 32 $ 秒4地点 $ 30 $ から地点 $ 80 $ に移動する． $ 150 $ 秒 $ 182 $ 秒5 $ 2 $ 番目のボールを拾う． $ 1 $ 秒 $ 183 $ 秒6地点 $ 80 $ から地点 $ 100 $ に移動し，完走する． $ 80 $ 秒 $ 263 $ 秒 $ 2 $ 番目のシナリオでは，スタート地点とゴール地点は $ 1 $ 番目のシナリオと同じであるが，制限時間は $ 300 $ 秒となっている．前と同じ方法で，制限時間内の $ 263 $ 秒で完走することができる．よって， $ 2 $ 行目には `Yes` を出力する． $ 3 $ 番目のシナリオでは，スタート地点とゴール地点は $ 1, 2 $ 番目のシナリオと同じであるが，制限時間は $ 262 $ 秒となっている．制限時間内に完走する方法は存在しない．よって， $ 3 $ 行目には `No` を出力する． この入力例は小課題 $ 2, 3, 4, 5, 6, 7 $ の制約を満たす． --- ### Sample Explanation 2 $ 1 $ 番目のシナリオでは，スタート地点は地点 $ 0 $ ，ゴール地点は地点 $ 0 $ ，制限時間は $ 403 $ 秒である．以下のようにして，制限時間内の $ 403 $ 秒で完走することができる．よって， $ 1 $ 行目には `Yes` を出力する． 順番行動消費時間累計時間1地点 $ 0 $ から出発し，地点 $ 30 $ に移動する． $ 30 $ 秒 $ 30 $ 秒2 $ 1 $ 番目のボールを拾う． $ 1 $ 秒 $ 31 $ 秒3地点 $ 30 $ から地点 $ 80 $ に移動する． $ 100 $ 秒 $ 131 $ 秒4 $ 2 $ 番目のボールを拾う． $ 1 $ 秒 $ 132 $ 秒5地点 $ 80 $ から地点 $ 30 $ に移動する． $ 150 $ 秒 $ 282 $ 秒6 $ 3 $ 番目のボールを拾う． $ 1 $ 秒 $ 283 $ 秒7地点 $ 30 $ から地点 $ 0 $ に移動し，完走する． $ 120 $ 秒 $ 403 $ 秒 $ 2, 3 $ 番目のシナリオでは，スタート地点とゴール地点は $ 1 $ 番目のシナリオと同じであるが，制限時間はそれぞれ $ 300 $ 秒， $ 262 $ 秒となっている．どちらについても，制限時間内に完走する方法は存在しない．よって， $ 2 $ 行目には `No` を， $ 3 $ 行目には `No` を出力する． この入力例は小課題 $ 1, 2, 3, 4, 5, 6, 7 $ の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 2, 3, 4, 5, 6, 7 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 500\,000 $ ． - $ 1 \leqq L \leqq 500\,000 $ ． - $ 0 \leqq X_i \leqq L $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq Q \leqq 500\,000 $ ． - $ 0 \leqq S_j \leqq L $ ( $ 1 \leqq j \leqq Q $ )． - $ 0 \leqq G_j \leqq L $ ( $ 1 \leqq j \leqq Q $ )． - $ 1 \leqq T_j \leqq 500\,000 $ ( $ 1 \leqq j \leqq Q $ )． - 入力される値はすべて整数である．