페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5755
서브태스크

고기 파티 3초 1024MB

문제

오늘은 고기 파티가 열리는 날이다. 파티에 걸맞도록, 기다란 그릴 위에 잘 구워진 고기가 총 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 가 주어진다.

[제약 조건]

  • 주어지는 모든 수는 정수이다.

  • 1 \le N,M \le 250,000

  • 0 \le s_i \le 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 \le j \le M)


출력

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


부분문제

번호 점수 조건
#15점

N, M \le 1,000

#29점

e_i - s_i \le 5 (1 \le i \le N)

#311점

s_i < s_{i+1}, e_i > e_{i+1} (1 \le i \le N-1)

#423점

e_i - s_i = e_1 - s_1 (2 \le i \le N)

#552점

추가 제약 조건이 없음


예제1

입력
53
273
569
352
136
487
36
24
55
출력
3
0
9

예제2

입력
63
1121
21110
310100
491000
5810000
67100000
111
59
68
출력
1
110
0

예제3

입력
52
155
262
483
594
7116
45
810
출력
5
6

태그

출처

KOI 2023 2차 초 4번, 중 3번

역링크