31488번 - Favourite dish 다국어

문제

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 $N$ dishes, numbered from 1ドル$ to $N$; each dish has a score on its taste and a score on its plating. There are also $M$ persons, numbered from 1ドル$ to $M$; 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.

입력

Each line contains two space-separated integers. The first line contains the numbers $N$ and $M$. Then follow $N$ lines; the $k$^th such line contains two integers $t_k$ and $p_k,ドル which are the scores of the dish $k$ on taste and on plating. Then come $M$ more lines; the $\ell$^th such line contains two integers $T_\ell$ and $P_\ell,ドル which are the weights of person $\ell$ on taste and on plating.

출력

The output should contain $M$ lines. The $\ell$^th such line should contain one number: the number of the favourite dish of person $\ell$.

제한

• 1ドル \le N \le 500,円 000$
• 1ドル \le M \le 500,円 000$
• 0ドル \le t_k \le 1,円 000,円 000,ドル 0ドル \le p_k \le 1,円 000,円 000,ドル and $(t_k , p_k) \ne (0, 0)$ for all $k \le N$
• 0ドル \le T_\ell \le 1,円 000,円 000,ドル 0ドル \le P_\ell \le 1,円 000,円 000,ドル and $(T_\ell , P_\ell) \ne (0, 0)$ for all $\ell \le M$
• the $N$ pairs $(t_k , p_k)$ are pairwise distinct
• the $M$ pairs $(T_\ell , P_\ell)$ are pairwise distinct

힌트