Little C has fallen in love with a game called "Everyday Shooting." As shown in the figure, the game features several wooden boards parallel to the $x$-axis. There are bullets that are fired in order along the $y$-axis towards these boards. The $i$-th board will break and disappear after being penetrated by $S_i$ bullets. A single bullet can penetrate all boards along its trajectory. Specifically, if a bullet touches the edge of a board, it is also considered to have penetrated the board.

Little C now knows the positions of $n$ boards in the game, as well as the shooting positions of $m$ bullets. You are asked to determine how many boards break after each bullet is fired.

Input

The first line contains two integers $n$ and $m$, representing the number of boards and the number of bullets, where $1 \le n, m \le 2 \times 10^{5}$.

The next $n$ lines each contain three integers $x_1, x_2, s$, representing the left $x$-coordinate, the right $x$-coordinate, and the number of penetrations required 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 an integer $x$, representing the $x$-coordinate of each bullet. The bullets are given in the order they are fired. It is guaranteed that $1 \le x \le 2 \times 10^{5}$.

Output

Output $m$ lines, each containing an integer representing the number of boards that break after each bullet is fired.

Examples

Input 1

3 2
1 3 1
2 4 2
3 4 1
2
3

Output 1

1
2