問題文

$N$ 個の仕事があり、あなたはこの中からいくつかの仕事を選んで行おうとしています。

$i$ 番目の仕事を行う場合、$L_i$ 日目から $R_i$ 日目までの期間中、毎日その仕事を行う必要があります。また、$i$ 番目の仕事を行うと $C_i$ の報酬を得られます。

なお、同じ日に複数の仕事を行うことはできません。

さて、あなたには、必ず行わなければならない大事な仕事が二つあることが分かっています。

$Q$ 個のクエリが与えられるので、それぞれについて次の問題に答えてください。$j$ 番目のクエリの内容は以下のようなものです。

• 大事な仕事が $a_j$ 番目と $b_j$ 番目であるときの、得られる報酬の合計の最大値を出力する。両方の大事な仕事を行うことができない場合は -1 を出力する。

制約

• $2 \leq N,Q \leq 2 \times 10^5$
• $1 \leq L_i \leq R_i \leq N$
• 任意の整数 $p$ について、$L_i \leq p \leq R_i$ を満たす整数 $i$ は高々 $5$ 個
• $1 \leq C_i \leq 10^9$
• $1 \leq a_j < b_j \leq N$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

$N$ $Q$
$L_1$ $R_1$ $C_1$
$L_2$ $R_2$ $C_2$
$\vdots$
$L_N$ $R_N$ $C_N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_Q$ $b_Q$

出力

$Q$ 行出力してください。

$i$ 行目には、$i$ 番目のクエリに対する答えを出力してください。

サンプル

5 4
1 2 4
3 4 5
2 3 10
5 5 2
1 1 3
1 2
1 3
2 5
3 4

11
-1
10
15

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

-1
60
60