AT_joi2026_semifinal_b 宝石商 (Jeweler)

JOI 君は宝石店を経営している． 宝石店には宝石を買おうとしている客が $ N $ 人おり，これらの客には $ 1 $ から $ N $ までの番号が付けられている． 客 $ i $ ( $ 1 \leqq i \leqq N $ ) は時刻 $ L_i $ から時刻 $ R_i $ までの間の任意の時刻に店を訪れることができ，宝石を $ C_i $ 個購入しようとしている． JOI 君は忙しいため，常に店を開けておくことができない． そこで，店を開ける時間について $ M $ 個の案を考えた． 案には $ 1 $ から $ M $ までの番号が付けられており，案 $ j $ ( $ 1 \leqq j \leqq M $ ) は，時刻 $ S_j - 0.1 $ から時刻 $ T_j + 0.1 $ までの間店を開けるというものである． それぞれの案について，客 $ i $ ( $ 1 \leqq i \leqq N $ ) は，自分が訪れることができる時間帯に店が開いている時刻があれば，店を訪れ宝石を $ C_i $ 個購入する． 逆にそうではない場合，客 $ i $ は店を訪れず，宝石を購入しない． ただし，JOI 君の店には十分な数の宝石があり，宝石が売り切れることはないものとする． JOI 君の店の客の情報と店を開けておく時間の案が与えられたとき，それぞれの案について，宝石が合計でいくつ売れるかを求めるプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ L_1 $ $ R_1 $ $ C_1 $ $ L_2 $ $ R_2 $ $ C_2 $ $ \vdots $ $ L_N $ $ R_N $ $ C_N $ $ M $ $ S_1 $ $ T_1 $ $ S_2 $ $ T_2 $ $ \vdots $ $ S_M $ $ T_M $

標準出力に $ M $ 行出力せよ． $ j $ 行目 ( $ 1 \leqq j \leqq M $ ) には，案 $ j $ において宝石が合計でいくつ売れるかを出力せよ． ---

### 小課題 1. ( $ 12 $ 点) $ N \leqq 1\,000 $ ， $ M \leqq 1\,000 $ ． 2. ( $ 17 $ 点) $ S_j = T_j $ ( $ 1 \leqq j \leqq M $ )． 3. ( $ 21 $ 点) $ S_j = 1 $ ( $ 1 \leqq j \leqq M $ )． 4. ( $ 23 $ 点) $ S_j \leqq S_{j+1} $ ， $ T_j \leqq T_{j+1} $ ( $ 1 \leqq j < M $ )． 5. ( $ 27 $ 点) 追加の制約はない． --- ### Sample Explanation 1 案 $ 1 $ では，時刻 $ 3.9 $ から時刻 $ 6.1 $ まで店を開ける． 客 $ 1 $ は時刻 $ 4 $ に，客 $ 2 $ は時刻 $ 5 $ に，客 $ 3 $ は時刻 $ 6 $ に店で宝石を買うことができ，宝石は合計で $ 10 + 20 + 30 = 60 $ 個売れる． 案 $ 2 $ では，時刻 $ 0.9 $ から時刻 $ 2.1 $ まで店を開ける． どの客も店が開いている時刻に訪れることができないため，宝石は合計で $ 0 $ 個売れる． 案 $ 3 $ では，時刻 $ 5.9 $ から時刻 $ 8.1 $ まで店を開ける． 客 $ 2 $ ，客 $ 3 $ ともに時刻 $ 7 $ に店で宝石を買うことができ，宝石は合計で $ 20 + 30 = 50 $ 個売れる． この入力例は小課題 $ 1,5 $ の制約を満たす． --- ### Sample Explanation 2 案 $ 1 $ では，客 $ 1 $ と客 $ 3 $ が店で宝石を買うことができ，宝石は合計で $ 1 + 4 = 5 $ 個売れる． 案 $ 2 $ では，客 $ 1 $ ，客 $ 2 $ ，客 $ 3 $ が店で宝石を買うことができ，宝石は合計で $ 1 + 2 + 4 = 7 $ 個売れる． 案 $ 3 $ では，すべての客が店で宝石を買うことができ，宝石は合計で $ 1 + 2 + 4 + 8 = 15 $ 個売れる． この入力例は小課題 $ 1,3,4,5 $ の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 1,5 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 300\,000 $ ． - $ 1 \leqq L_i < R_i \leqq 1\,000\,000 $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq C_i \leqq 10^9 $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq M \leqq 300\,000 $ ． - $ 1 \leqq S_j \leqq T_j \leqq 1\,000\,000 $ ( $ 1 \leqq j \leqq M $ )． - 入力される値はすべて整数である．