---
# System prepended metadata

title: KOI 23 Meat party
tags: [statement]

---

https://www.acmicpc.net/problem/28326

# KOI 23 Meat party 

Today is the day of the meat party. In preparation for the party, well-cooked meat is placed on a grill, a total of $N$ pieces.

Let's consider the grill as a segment of length $10^9$, with the left end at coordinate $0$ and the right end at coordinate $10^9$. Each piece of meat occupies a specific interval on the grill and has a taste value expressed as a positive integer. The $i$-th piece of meat ($1 \le i \le N$) occupies the interval $[s_i, e_i]$ on the coordinate axis, and its taste value is $t_i$. Multiple pieces of meat may overlap.

$M$ people are attending the party. Starting from person $1$ to person $M$, each person stands in front of the grill and takes their share of meat. The process of taking meat is as follows:

- Person $j$ ($1 \le j \le M$) brings two long skewers and inserts them at coordinates $a_j + 0.1$ and $b_j + 0.9$ ($a_j \le b_j$). The skewer inserted at coordinate $x$ will pierce all meats satisfying $s_i \le x \le e_i$.
- Next, they hold the skewers and return to their seat. At this point, all meats pierced by one or more skewers are collectively taken and disappear from the grill.
- Meats pierced by only one skewer are dropped while being carried. Only meats pierced by both skewers can be taken and eaten.

As the host of the party, you are curious about which meat each person will take and eat. Let's calculate the sum of taste values of the meats each person will take. Note that dropped meats should be excluded from the sum

# Input

The first line contains two integers, the number of meats $N$ and the number of people $M$.

The following $N$ lines describe each meat. For the $i$-th meat, the $i$-th line contains three integers $s_i$, $e_i$, and $t_i$, representing the interval and taste value of the $i$-th meat.

Following that, the next $M$ lines describe the actions of each person. For the $j$-th person, the $j$-th line contains two integers $a_j$ and $b_j$ indicating the coordinates where they will insert the skewers.

# Output

Print $M$ lines. Each line $j$ represents the sum of taste values of the meats that the $j$-th person will take and eat.

# Constraints

- All given numbers are integers.
- $1 \le N, M \le 250,000$
- $0 \le s_i < e_i \le 10^9$ for $1 \le i \le N$
- $1 \le t_i \le 10^9$ for $1 \le i \le N$
- $0 \le a_j \le b_j \le 10^9 - 1$ for $1 \le j \le M$

# Subtasks

![image](https://hackmd.io/_uploads/SkT2_O-KT.png)

See the original statement for samples

