Meat Party

Today is the day of a meat party. To suit the party, $N$ well-grilled pieces of meat are placed on a long grill.

Treat the grill as a line 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 range on the grill and has a positive integer tastiness value. The $i$-th piece occupies the coordinates in the interval $[s_i, e_i]$ and has tastiness $t_i$. Several pieces may overlap.

$M$ people attend the party. Person 1 through person $M$ step up to the grill in order and each takes the meat they will eat. The process is as follows.

• Person $j$ brings two long skewers and pushes them into the grill at coordinates $a_j + 0.1$ and $b_j + 0.9$ ($a_j \le b_j$). A skewer pushed in at coordinate $x$ pierces every piece of meat that satisfies $s_i \le x \le e_i$.
• Then the person carries the skewers back to their seat. Every piece pierced by at least one skewer is carried away together and disappears from the grill.
• A piece pierced by only one of the two skewers falls to the floor while being carried. Only pieces pierced by both skewers can be taken to the seat and eaten.

As the host, you want to know which meat each person ends up eating. Find the sum of tastiness values of the meat each person takes and eats. Exclude any meat that fell to the floor from the sum.

The first line contains the number of meat pieces $N$ and the number of people $M$.

The next $N$ lines each contain three integers $s_i$, $e_i$, $t_i$, the interval and tastiness of the $i$-th piece.

The next $M$ lines each contain two integers $a_j$, $b_j$, the coordinates where person $j$ pushes the skewers.

Print $M$ lines. On the $j$-th line, print the sum of tastiness values of the meat that person $j$ takes and eats.

• All input values are integers.
• $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$)