Unfair Contest

There is a company that is very famous for arranging unfair contests. They are arranging a new weird contest.

The contest is about guessing a number. The company will call it the magic number. The magic number for the contest is yet to be decided by the company.

The contest consists of an infinite number of rounds. In each round, every participant will guess a number and submit it to the judge. If at least one of the submissions of that particular round contains the magic number, the contest ends. Then the winner of the contest will be the contestant who guessed it correctly in that particular round. If there are several contestants who have guessed it correctly, then the contestant with the lowest index will be the winner.

There are $N$ participants indexed from $1$ to $N$. To make the contest unfair, the surveillance team of the company has collected three attributes of the strategy of each contestant, $L_i, R_i, X_i$.

It means $i^{th}$contestant will choose $L_i+(j-1)\times X_i$ as the guess for the $j^{th}$round as long as the guess is less than or equal to $R_i$. If the guess exceeds $R_i$ then the contestant will quit the contest.

Moreover, the team discovered a pattern in the strategies of the contestants, that is, $L_i$ is always divisible by $X_i$.

The CEO of the company is very determined to make the contest unfair. So, he will ask $Q$ queries. Note that, each query is independent.

In each query, he will choose a magic number and he is eager to know who will be the winner if he chooses it for the contest. As his helping hand, determine the winner for that specific magic number or say there will be no winner.

Input

The first line of input contains two space-separated integers, $N$ and $Q$, the number of contestants and the number of queries, respectively.

Each of the next $N$lines contains three space-separated integers, $L_i, \, R_i$ and $X_i$, three attributes for the $i^{th}$ contestant.

Each of the next $Q$ lines contains a single integer $M_j$, the magic number for the $j^{th}$query.

Constraints

$1 \leq N \leq 10^6$

$1 \leq Q \leq 10^6$

$1 \leq L_i \leq R_i \leq 10^6$

$1 \leq X_i \leq 10^6$

$1 \leq M_j \leq 10^6$

Output

For each query, if there is no winner, print $-1$, otherwise, print the index of the winner.

Sample

Input	Output
3 3 4 6 2 3 9 3 2 6 2 2 3 6	3 2 1