Every day as the sun sets,opens up his terminal and connects to the DMOJ site server. Like any sysadmin, likes statistics about anything and everything. Today, he's interested in the memory usages of all the applications running on the server.
As he runs
top, he notices that ~N~ programs, identified ~0, \dots, N-1~, appear to have memory leaks. That is, program ~i~'s memory usage increases by ~M_i~ KB every second, each starting from a distinct ~S_i~ KB. Finding this race of programs fun to watch, would like to answer ~Q~ queries: for each query ~i~, he'd like to know which program has the greatest memory usage after ~Q_i~ seconds. There might be multiple, in which case he'd like to know the one with the smallest identifier.
For all subtasks, ~1 \le M_i \le 1\,000~, ~1 \le S_i \le 1\,000\,000~, and ~1 \le Q_i \le 500\,000~.
Subtask 1 [20%]
~1 \le N \le 500~
~1 \le Q \le 500~
Subtask 2 [80%]
~1 \le N \le 100\,000~
~1 \le Q \le 500\,000~
The first line of input will contain the space-separated integers ~N~ and ~Q~.
For the next ~N~ lines of input, line ~i~ will contain two integers ~S_i~, and ~M_i~.
Finally, the last ~Q~ lines will each contain a query.
For each query, the id of the program using the most memory at the given time.
2 2 400 100 200 200 1 10
After the ~1~ second, program ~1~ uses ~500~ KB of memory, while ~2~ uses only ~400~ KB. Following ~10~ seconds, program ~2~ is in the lead, with ~2200~ KB of memory used.