题目描述

:::align{center}

:::

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^\text{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 $l^\text{th}$ such line contains two integers $T_l$ and $P_l$, which are the weights of person $l$ on taste and on plating.

Limits

• $1 \leq N \leq 500~000$;
• $1 \leq M \leq 500~000$;
• $0 \leq t_k \leq 1~000~000, 0 \leq p_k \leq 1~000~000$, and $(t_k, p_k) \neq (0, 0)$ for all $k \leq N$;
• $0 \leq T_l \leq 1~000~000, 0 \leq P_l \leq 1~000~000$, and $(T_l, P_l) \neq (0, 0)$ for all $l \leq M$;
• the $N$ pairs $(t_k, p_k)$ are pairwise distinct;
• the $M$ pairs $(T_l, T_l)$ are pairwise distinct.

输出格式

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

4 3
2 5
3 4
4 2
1 6
6 4
2 8
5 5

2
4
1

3 4
1 0
0 2
0 1
1 1
2 2
2 1
1 0

2
2
1
1

提示

Sample Explanation 1

Here is the score table for each person on each dish. Each person's favourite dish is indicated with a $^\ast$; person 3 has three tied favourite dishes, so we chose the first one.

	Dish	<
Person	1	2	3	4
1	$3.2$	$3.4^\ast$	$3.2$	$3$
2	$4.4$	$3.8$	$2.4$	$5^\ast$
3	$3.5^\ast$	$3.5$	$3$	$3.5$

Sample Explanation 2

Here is the score table for each person on each dish. Each person's favourite dish is indicated with a $^\ast$.

	Dish	<
Person	1	2	3
1	$0.5$	$1^\ast$	$0.5$
2
3	$2/3^\ast$	$2/3$	$1/3$
4	$1^\ast$	$0$