P7424 [THUPC 2017] Daily Shooting

Xiao C has fallen in love with a game called “Daily Shooting”. As shown in the figure, there are some wooden boards parallel to the $x$ axis in this game. Now there are some bullets, which are shot in order along the $y$ axis direction toward these boards. After the $i$-th board is penetrated by $S_i$ bullets, it will break and disappear. A bullet can penetrate all boards on its trajectory. In particular, if a bullet touches the edge of a board, it is also considered to have penetrated the board. Xiao C now knows the positions of $n$ boards in the game, and also knows the shooting positions of $m$ bullets. You are asked: after each bullet is fired, how many boards will break?

Read input from standard input. The first line contains two integers $n$ and $m$, representing the number of boards and the number of bullets. $1\le n,m\le 2\times 10^5$. The next $n$ lines each contain three integers $x_1,x_2,s$, representing the $x$ coordinate of the left endpoint, the $x$ coordinate of the right endpoint, and how many penetrations are needed for the board to break. It is guaranteed that $1\le x_1\le x_2\le 2\times 10^5$ and $1\le s\le 2\times 10^5$. The next $m$ lines each contain one integer $x$, representing the $x$ coordinate of each bullet. The bullets are given in firing order. It is guaranteed that $1\le x\le 2\times 10^5$.

Write to standard output. Output $m$ lines, each containing one integer, indicating how many boards break after each bullet is fired.

 #### Copyright Information From THUPC (THU Programming Contest, Tsinghua University Programming Contest) 2017. $\text{upd}2021.7.6$：Thanks to @[jiangbowen](https://www.luogu.com.cn/user/366807) for providing a set of hack testdata. It is not scored, but if you do not pass the hack testdata, you will not be considered to have passed this problem. Translated by ChatGPT 5