60040 고기 파티 Gold I

문제

오늘은 고기 파티가 열리는 날이다. 파티에 걸맞도록, 기다란 그릴 위에 잘 구워진 고기가 총 $N$개 놓여 있다.

그릴을 $10^9$ 의 길이를 가진 선분이라고 하고, 그릴의 왼쪽 끝을 좌표 $0$, 오른쪽 끝을 좌표 $10^9$ 이라고 하자. 각 고기는 그릴 위에서 특정 구간을 차지하고 있으며, 양의 정수로 표현되는 맛 수치를 각각 가진다. $i$번째 고기는 ($1 \le i \le N$) 구간 $[s_i, e_i]$에 해당하는 좌표를 차지하고 있으며 맛 수치는 $t_i$이다. 여러 고기가 겹쳐 있을 수 있다.

파티에는 $M$ 명의 사람이 참석하였다. $1$ 번 사람부터 $M$ 번 사람까지 번호 순서대로 그릴 앞에 서서 각자 먹을 고기를 가져간다. 고기를 가져가는 방법은 다음과 같다.

• $j$ 번 사람은 ($1 \le j \le M$) 긴 꼬치 두 개를 가지고 와서 각각 $a_j + 0.1$, $b_j + 0.9$ 좌표에 찔러 넣는다. ($a_j \le b_j$) 좌표 $x$에 찔러 넣은 꼬치는 $s_i \le x \le e_i$를 만족하는 모든 고기에 꽂히게 된다.
• 그다음, 꼬치를 통째로 들고 자리로 돌아간다. 이때 하나 이상의 꼬치가 꽂힌 고기는 모두 같이 들려 가고, 그릴 위에서 사라진다.
• 둘 중 하나의 꼬치만 꽂힌 고기는 들고 가다 바닥에 떨어진다. 두 꼬치가 모두 꽂힌 고기만 자리로 가져가서 먹을 수 있다.

파티의 주최자인 당신은 각 사람이 어떤 고기를 가져가서 먹게 될지가 궁금하다. 각 사람이 가져가서 먹게 되는 고기의 맛 수치의 합을 구하여 보자. 들고 가다 떨어트린 고기는 합에서 제외해야 함에 유의하라.

입력

첫 번째 줄에 고기의 수 $N$과 사람의 수 $M$이 주어진다.

다음 줄부터 $N$개의 줄에 걸쳐, 이 중 $i$번째 줄에는 $i$번째 고기가 차지하는 구간과 맛 수치를 나타내는 세 정수 $s_i$, $e_i$, $t_i$가 주어진다.

다음 줄부터 $M$개의 줄에 걸쳐, 이 중 $j$번째 줄에는 $j$ 번 사람이 꼬치를 어느 좌표에 찔러 넣을지를 나타내는 두 정수 $a_j$, $b_j$가 주어진다.

출력

$M$개의 줄에 걸쳐, 이 중 $j$번째 줄에는 $j$ 번 사람이 가져가서 먹게 되는 고기의 맛 수치의 합을 출력한다.

제한

• 주어지는 모든 수는 정수이다.
• $1 \le N, M \le 250\,000$
• $0 \le s_i < e_i \le 10^9$ ($1 \le i \le N$)
• $1 \le t_i \le 10^9$ ($1 \le i \le N$)
• $0 \le a_j \le b_j \le 10^9 - 1$ ($1 \le j \le M$)

서브태스크

번호	배점	제한
1	5	$N, M \le 1,000$
2	9	$e_i - s_i \le 5$ ($1 \le i \le N$)
3	11	$s_i < s_{i+1}$, $e_i > e_{i+1}$ ($1 \le i \le N-1$)
4	23	$e_i - s_i = e_1 - s_1$ ($2 \le i \le N$)
5	52	추가 제약 조건이 없음.

5 3
2 7 3
5 6 9
3 5 2
1 3 6
4 8 7
3 6
2 4
5 5

3
0
9

6 3
1 12 1
2 11 10
3 10 100
4 9 1000
5 8 10000
6 7 100000
1 11
5 9
6 8

1
110
0

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

5
6