고기 파티

문제

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

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

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

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

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

입력

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

다음 줄부터 $NN$개의 줄에 걸쳐, 이 중 $ii$번째 줄에는 $ii$번째 고기가 차지하는 구간과 맛 수치를 나타내는 세 정수 $s_{i}s\_i$, $e_{i}e\_i$, $t_{i}t\_i$가 주어진다.

다음 줄부터 $MM$개의 줄에 걸쳐, 이 중 $jj$번째 줄에는 $jj$ 번 사람이 꼬치를 어느 좌표에 찔러 넣을지를 나타내는 두 정수 $a_{j}a\_j$, $b_{j}b\_j$가 주어진다.

출력

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

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