Unfair Contest

tahsin_protik Replay of Ada Lovelace Na...
Limits 1s, 512 MB

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 NN participants indexed from 11 to NN. To make the contest unfair, the surveillance team of the company has collected three attributes of the strategy of each contestant, Li,Ri,XiL_i, R_i, X_i.

It means ithi^{th}contestant will choose Li+(j1)×XiL_i+(j-1)\times X_i as the guess for the jthj^{th}round as long as the guess is less than or equal to RiR_i. If the guess exceeds RiR_i then the contestant will quit the contest.

Moreover, the team discovered a pattern in the strategies of the contestants, that is, LiL_i is always divisible by XiX_i.

The CEO of the company is very determined to make the contest unfair. So, he will ask QQ 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, NN and QQ, the number of contestants and the number of queries, respectively.

Each of the next NNlines contains three space-separated integers, Li,RiL_i, \, R_i and XiX_i, three attributes for the ithi^{th} contestant.

Each of the next QQ lines contains a single integer MjM_j, the magic number for the jthj^{th}query.

Constraints

1N1061 \leq N \leq 10^6

1Q1061 \leq Q \leq 10^6

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

1Xi1061 \leq X_i \leq 10^6

1Mj1061 \leq M_j \leq 10^6

Output

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

Sample

InputOutput
3 3
4 6 2
3 9 3
2 6 2
2
3
6
3
2
1

Submit

Login to submit.

Statistics

50% Solution Ratio
serotoninEarliest, 7M ago
serotoninFastest, 0.5s
serotoninLightest, 184 MB
serotoninShortest, 1016B
Toph uses cookies. By continuing you agree to our Cookie Policy.