Train Passenger Query (Hard)

問題文

mogu王国には、東西の町を繋ぐ一本の大きな鉄道が敷かれている。この鉄道のとある列車は、$N$ 個の駅を繋いでおり、その始発駅は 駅 $1$ 、終着駅は 駅 $N$ である。

次の $Q$ 個のクエリに答えよ。

この列車の時間帯 $i$ における乗車記録は、 $M_i(1 \leq i \leq Q)$ 個のログから構成されており、 $j(1 \leq j \leq M_i)$ 個目のログには次の情報が残っている。

• 駅 $s_j$ で乗車し、 駅 $t_j$ で降車した人数は $c_i$ 人である。$(1 \leq s_j < t_j \leq N)$

駅 $S_i$ について、時間帯 $i$ までに駅 $S_i$ を通過した(駅 $S_i$ が乗車地や降車地の場合も含める)人数を求めよ。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq M_i$
• $\displaystyle \sum_{i=1}^{Q}M_i \leq 2 \times 10^5$
• $1 \leq s_j < t_j \leq N (1 \leq j \leq M_i)$
• $1 \leq c_i \leq 10^9(1 \leq i \leq M_i)$
• $1 \leq S_i \leq N$

入力

入力はすべて整数である。

N Q
Query_1
Query_2
...

各クエリは以下のようにして与えられる。

M_i
s_1 t_1 c_1
s_2 t_2 c_2
...
s_{M_i} t_{M_i} c_{M_i}
S_i

出力

各クエリについて、それぞれ答えを一行づつ合計 $N$ 行出力せよ。

サンプル

3 3
1
1 2 10
1
2
2 3 5
1 3 5
2
3
1 2 10
2 3 10
1 3 20
3

10
20
40

時間帯 $1$ までに各駅を通過した人数は、それぞれ $10,10,0$ です。クエリ $1$ では駅 $1$ の通過人数である $10$ を出力します。

時間帯 $2$ までに各駅を通過した人数は、それぞれ $15,20,10$ です。クエリ $2$ では駅 $2$ の通過人数である $20$ を出力します。

時間帯 $3$ までに各駅を通過した人数は、それぞれ $45,60,40$ です。クエリ $3$ では駅 $3$ の通過人数である $40$ を出力します。

4 3
1
1 2 10
4
1
2 3 20
4
1
1 3 30
4

0
0
0

誰も駅 $4$ を利用していません。