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.

Input

Each line contains two integers. The first line contains the numbers $n$ and $m(1\le n,m\le 5\cdot 10^5)$. Then follow $n$ lines; the $k$-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 $n$ pairs $(t_k,p_k)$ are pairwise distinct), which are the scores of the dish $k$ on taste and on plating. Then come $m$ more lines; the $l$-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 $m$ pairs $(T_l,P_l)$ are pairwise distinct), which are the weights of person $l$ on taste and on plating.

Output

Print $m$ lines. The $l$-th such line should contain one number: the number of the favourite dish of person $l$.

Examples

Sample 1. Here is the score table for each person on each dish. Each person's favourite dish is indicated with a ⋆. Person $3$ has three tied favourite dishes, so we chose the first one.

Sample 2. Here is the score table for each person on each dish. Each person's favourite dish is indicated with a ⋆.