AT_pakencamp_2024_day1_p Bombard

縦 $ H $ 行、横 $ W $ 列のマス目があります。以下、左上のマスを $ (1, 1) $ とし、上から $ x $ 行目、左から $ y $ 列目のマスを $ (x, y) $ とします。 このマス目の上に長方形の構造物が $ N $ 個立っています。 $ i $ 個目の構造物は、 $ U_i \leq x \leq D_i, L_i \leq y \leq R_i $ を満たすマス $ (x, y) $ をすべて覆っており、それ以外のマスは覆っていません。ここで、 $ 1 $ つのマスを覆う構造物はたかだか $ 1 $ つであることが保証されています。また、それぞれの構造物は値 $ C_i $ を持っています。 それぞれのマスの価値を、そのマスを覆う構造物の値と定義します。ただし、マスを覆う構造物が存在しない場合、そのマスの価値は $ 0 $ であるとします。 Falcon君は、発射した位置から右にあるマスを全て破壊する波動砲を持っています。厳密には、マス $ (x, y) $ で波動砲を発射すると、 $ y \leq j \leq W $ を満たす全ての整数 $ j $ について、マス $ (x, j) $ を破壊することができます。 このとき、Falcon君の嬉しさは破壊したマスの価値の合計となります。 この波動砲は上下には自由に動かすことができますが、左右には動かすことができません。波動砲を設置する列の候補を $ Q $ 個定め、それぞれ $ K_i $ 列目としました。それぞれの場合においてFalcon君の嬉しさの最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ H $ $ W $ $ U_1 $ $ D_1 $ $ L_1 $ $ R_1 $ $ C_1 $ $ U_2 $ $ D_2 $ $ L_2 $ $ R_2 $ $ C_2 $ $ \vdots $ $ U_N $ $ D_N $ $ L_N $ $ R_N $ $ C_N $ $ Q $ $ K_1 $ $ K_2 $ $ \vdots $ $ K_Q $

答えを出力せよ。

### Sample Explanation 1 マス目は以下のようになります。  例えば $ 1 $ 列目から発射する場合、 - $ 1 $ 行目に設置した場合、嬉しさは $ 36 $ - $ 2 $ 行目に設置した場合、嬉しさは $ 30 $ - $ 3 $ 行目に設置した場合、嬉しさは $ 30 $ - $ 4 $ 行目に設置した場合、嬉しさは $ 38 $ - $ 5 $ 行目に設置した場合、嬉しさは $ 14 $ - $ 6 $ 行目に設置した場合、嬉しさは $ 8 $ となるため、 $ 38 $ を出力してください。 ### Constraints - $ 1 \leq N \leq 10^5 $ - $ 1 \leq H,W \leq 10^9 $ - $ 1 \leq U_i \leq D_i \leq H $ ( $ 1 \leq i \leq N $ ) - $ 1 \leq L_i \leq R_i \leq W $ ( $ 1 \leq i \leq N $ ) - $ 2 $ つ以上の構造物が同じマスを覆うことはない - $ 1 \leq C_i \leq 10^9 $ ( $ 1 \leq i \leq N $ ) - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq K_i \leq W $ ( $ 1 \leq i \leq Q $ ) - 入力は全て整数