数轴上有 $N$ 个地雷。第 $i$ 个地雷位于位置 $p_i$，爆炸半径为 $r_i$。引爆它的初始代价为 $c_i$。如果引爆了第 $i$ 个地雷，会产生一个覆盖区间 $[p_i - r_i, p_i + r_i]$ 的爆炸，该区间内（包含端点）的所有地雷都会被免费引爆，从而引发连锁反应。你需要处理 $Q$ 次操作，每次操作格式为 $(m, c)$：将引爆第 $m$ 个地雷的代价修改为 $c$。在每次修改后，输出引爆所有地雷所需的最小代价。注意，每次修改都是永久性的。

输入格式

第一行包含整数 $N$ 和 $Q$ ($1 \le N, Q \le 200\,000$)。接下来的 $N$ 行包含地雷的信息。其中第 $i$ 行包含整数 $p_i, r_i$ 和 $c_i$ ($1 \le p_i, r_i, c_i \le 10^9$)。接下来的 $Q$ 行，每行包含两个空格分隔的整数 $m$ 和 $c$ ($1 \le m \le N, 1 \le c \le 10^9$)。

输出格式

输出 $Q$ 行。第 $i$ 行应包含第 $i$ 次操作后引爆所有地雷所需的最小代价。

样例

样例输入 1

4 2
1 1 1
6 3 10
8 2 5
10 2 3
1 1
4 11

样例输出 1

4
6