Every day as the sun sets, quantum opens up his terminal and connects to the DMOJ site server. Like any sysadmin, quantum 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 programs, identified , appear to have memory leaks. That is, program 's memory usage increases by KB every second, each starting from a distinct KB. Finding this race of programs fun to watch, quantum would like to answer queries: for each query , he'd like to know which program has the greatest memory usage after seconds. There might be multiple, in which case he'd like to know the one with the smallest identifier.
For all subtasks, , , and .
Subtask 1 [20%]
Subtask 2 [80%]
The first line of input will contain the space-separated integers and .
For the next lines of input, line will contain two integers , and .
Finally, the last 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 second, program uses KB of memory, while uses only KB. Following seconds, program is in the lead, with KB of memory used.