問題文

縦 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君の嬉しさの最大値を求めてください。

制約

• 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)
• 入力は全て整数

入力例 1

4
6 14
1 5 1 2 3
4 6 3 4 4
2 4 5 7 8
1 1 4 13 3
4
1
5
11
13

出力例 1

38
27
9
3

マス目は以下のようになります。

例えば 1 列目から発射する場合、

• 1 行目に設置した場合、嬉しさは 36
• 2 行目に設置した場合、嬉しさは 30
• 3 行目に設置した場合、嬉しさは 30
• 4 行目に設置した場合、嬉しさは 38
• 5 行目に設置した場合、嬉しさは 14
• 6 行目に設置した場合、嬉しさは 8

となるため、 38 を出力してください。

入力例 2

10
100 100
69 94 13 36 36
37 83 82 86 31
20 32 60 60 14
56 63 57 58 93
87 92 68 70 72
88 90 76 95 75
55 66 2 3 74
2 7 77 92 30
82 83 67 74 37
21 76 52 53 4
10
93
29
57
6
82
88
95
79
59
3

出力例 2

225
2004
1716
2580
1050
600
75
1275
1716
2580