Favourite Dish

France is a country of gastronomy. For a dish, both the taste and the plating matter. Still, when different people evaluate a dish, some focus more on taste and others focus more on plating. The Olympic Village dining hall serves $N$ dishes, numbered from $1$ to $N$. Each dish has a score for taste and a score for plating. There are also $M$ persons, numbered from $1$ to $M$. Each person has a weight for taste and a weight for plating. A person's final score for a dish is the weighted average of the dish's taste and plating scores.

The chefs want to give everyone their favourite dish on the evening of the closing ceremony. Find the favourite dish of each person. If several dishes tie for the highest score, choose the one with the smallest number.

Each line contains two space-separated integers. The first line contains $N$ and $M$. The next $N$ lines follow, where the $k$th line contains $t_k$ and $p_k$, the taste and plating scores of dish $k$. The next $M$ lines follow, where the $\ell$th line contains $T_\ell$ and $P_\ell$, the taste and plating weights of person $\ell$.

Output $M$ lines. The $\ell$th line contains 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