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 
~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, quantum 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.
Constraints
For all subtasks:
~1 \le M_i \le 1\,000~
~1 \le S_i \le 1\,000\,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_i \le 500\,000~
Input Specification
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.
Output Specification
For each query, the id of the program using the most memory at the given time.
Sample Input
2 2
400 100
200 200
1
10
Sample Output
0
1
Explanation
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.
Comments
i used scanf and printf and it passed for me.