지뢰

수직선 위에 지뢰가 $N$개 있다. 지뢰 $i$는 위치 $p_i$에 있고, 폭발 반경은 $r_i$이다. 지뢰 $i$를 터뜨리는 데 처음 드는 비용은 $c_i$이다. 지뢰 $i$를 터뜨리면 구간 $[p_i - r_i, p_i + r_i]$에서 폭발이 일어나고, 이 구간에 속한 지뢰(양 끝점 포함)는 비용 없이 함께 터져 연쇄 반응을 일으킨다.

$Q$개의 연산을 차례로 처리해야 한다. 연산 $(m, c)$는 지뢰 $m$을 터뜨리는 비용을 $c$로 바꾼다. 변경된 비용은 이후 연산에도 그대로 유지된다. 매 연산 뒤에 모든 지뢰를 터뜨리는 데 필요한 최소 비용을 출력한다.

첫 줄에 정수 $N$과 $Q$가 주어진다 (1 ≤ N, Q ≤ 200000). 이어지는 $N$개의 줄에는 정수 $p_i$, $r_i$, $c_i$가 주어진다 (1 ≤ p_i, r_i, c_i ≤ 1000000000). 이어지는 $Q$개의 줄에는 정수 $m$과 $c$가 주어진다 (1 ≤ m ≤ N, 1 ≤ c ≤ 1000000000).

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 연산 뒤에 모든 지뢰를 터뜨리는 데 필요한 최소 비용을 출력한다.