TSOC '15 Contest 2 #5 - Bebiliths

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 0.6s
Memory limit: 100M

Problem type

Regroup! Regroup!

The caves have been completely traversed, and Mr. Benum has been located! However, the quest is not over. Swarms of bebiliths, or spider-monsters the size of elephants, are swiftly decimating the ex-convicts! It is up to Max to command the remaining ex-convicts so that they can exterminate the bebilith army. But first, Max has to ensure that the ex-convicts will stay alive!

There are N (1 \le N \le 50\,000) bebiliths in pursuit of one of the groups of ex-convicts. Each bebilith has a speed B (0 \le B \le 10^9), a venom-spitting distance D (0 \le D \le 10^9) and a claw sharpness C (0 \le C \le 10^9) (where the bebilith with the sharpest claw has the highest value of C). Meanwhile, the ex-convicts are running at a uniform speed S (0 \le S \le 10^9).

If two bebiliths have the same speed and are faster or at pace with the ex-convicts, the bebilith with the sharpest claws is more dangerous. However, if two bebiliths have the same speed but are slower than the ex-convicts, the bebilith that spits venom the farthest is more dangerous. Otherwise, if two bebiliths have different speeds, the faster one is more dangerous. Max numbers each bebilith from 1 to N. If there is a tie between two bebiliths in terms of how dangerous they are, the one that is numbered the lowest is considered more dangerous. Help Max determine what number represents the i^\text{th} most dangerous bebilith Q (1 \le Q \le N) times!

Input Specification

First line: S

Second line: N

Next N lines: Three space-separated integers B_j D_j C_j on each line. Line j represents the characteristics of the (j-2)^\text{th} bebilith.

Line N+2: Q

Next Q lines: A single integer i on each line, indicating that the i^\text{th} most dangerous bebilith's number should be reported back to Max.

Output Specification

Q lines of the i^\text{th} most dangerous bebilith's number as queried.

Sample Input

7 29 61
7 42 59
4 1 441221001
3 7 9996999

Sample Output



Bebiliths 1 and 2 have the same speed, and both are the fastest. Their speed is greater than Max's speed. Bebilith 1 has sharper claws, so it is the most dangerous, while bebilith 2 is the 2^\text{nd} most dangerous. Bebilith 3 is faster than bebilith 4, so they are the 3^\text{rd} and 4^\text{th} most dangerous, respectively.


There are no comments at the moment.