Favourite dish#11751
France is a country of gastronomy. For a dish, both the taste and plating are important. Nevertheless, when different people evaluate a dish, some focus more on taste and some focus more on plating. At the Olympic Village dining hall, there are dishes, numbered from to ; each dish has a score on its taste and a score on its plating. There are also persons, numbered from to ; each person has a weight on taste and a weight on plating. One person's final score of a dish is the weighted average of the dish's scores on taste and plating.
The chefs at the Olympics want to provide everyone with their favourite dish on the evening of the closing ceremony. Your task is to calculate everyone's favourite dish. If multiple dishes tie for the highest score as a person's favourite, choose the one with the smallest number.
The first line contains the numbers and m~(1 \le n, m \le 5 \cdot 10^5). Then follow lines; the -th such line contains two integers t_k and p_k~(1 \le t_k, p_k \le 10^6, (t_k, p_k) \ne (0, 0) for all k \le n, the pairs (t_k, p_k) are pairwise distinct), which are the scores of the dish on taste and on plating. Then come more lines; the -th such line contains two integers T_l and P_l~(1 \le T_l, P_l \le 10^6, (T_l, P_l) \ne (0, 0) for all l \le m, the pairs (T_l, P_l) are pairwise distinct), which are the weights of person on taste and on plating.
Print lines. The -th such line should contain one number: the number of the favourite dish of person .
Example 1
Example 2
In sample 1, here is the score table for each person on each dish. Each person's favourite dish is indicated with a ⋆. Person has three tied favourite dishes, so we chose the first one.
In sample 2, here is the score table for each person on each dish. Each person's favourite dish is indicated with a ⋆.