Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Unfair Contest

By tahsin_protik · 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.


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.


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


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


3 3
4 6 2
3 9 3
2 6 2



40% Solution Ratio

serotoninEarliest, 1M ago

serotoninFastest, 0.5s

serotoninLightest, 184 MB

serotoninShortest, 1016B


Login to submit


Observation: For a particular magic number mjm_jmj​ , among two participant with same XiX_iXi​ and L...

Toph uses cookies. By continuing you agree to our Cookie Policy.