题目描述

:::align{center}

:::

法国是一个美食之国。对于一道菜来说，味道和摆盘都很重要。然而，不同的人在评价一道菜时，有的人更注重味道，有的人更注重摆盘。在奥运村的餐厅里，有 $N$ 道菜，编号从 $1$ 到 $N$；每道菜都有一个味道分数和一个摆盘分数。同时有 $M$ 个人，编号从 $1$ 到 $M$；每个人都有一个味道权重和一个摆盘权重。某个人对一道菜的最终评分是该菜的味道分数和摆盘分数的加权平均值。

奥运会的厨师们希望在闭幕式晚宴上为每个人提供他们最喜欢的菜。你的任务是计算出每个人最喜欢的菜。如果有多道菜在某个人心中的评分并列最高，则选择编号最小的那一道。

输入格式

每行包含两个用空格分隔的整数。第一行包含两个整数 $N$ 和 $M$。接下来有 $N$ 行，第 $k$ 行包含两个整数 $t_k$ 和 $p_k$，分别表示第 $k$ 道菜的味道分数和摆盘分数。之后还有 $M$ 行，第 $l$ 行包含两个整数 $T_l$ 和 $P_l$，分别表示第 $l$ 个人的味道权重和摆盘权重。

数据范围

• $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$，且对所有 $k \leq N$，$(t_k, p_k) \neq (0, 0)$；
• $0 \leq T_l \leq 1\,000\,000, 0 \leq P_l \leq 1\,000\,000$，且对所有 $l \leq M$，$(T_l, P_l) \neq (0, 0)$；
• $N$ 个 $(t_k, p_k)$ 两两不同；
• $M$ 个 $(T_l, P_l)$ 两两不同。

输出格式

输出应包含 $M$ 行。第 $l$ 行输出一个数字，表示第 $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

提示

样例解释 1

下表为每个人对每道菜的评分。每个人最喜欢的菜用 $^\ast$ 标出；第 3 个人有三道菜评分并列最高，因此选择编号最小的那一道。

样例解释 2

下表为每个人对每道菜的评分。每个人最喜欢的菜用 $^\ast$ 标出。

由 ChatGPT 4.1 翻译