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

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

输入格式

每行包含两个空格分隔的整数。第一行包含数字 $N$ 和 $M$。接下来有 $N$ 行；第 $k$ 行包含两个整数 $t_k$ 和 $p_k$，分别是第 $k$ 道菜的口味评分和摆盘评分。随后有 $M$ 行；第 $\ell$ 行包含两个整数 $T_\ell$ 和 $P_\ell$，分别是第 $\ell$ 个人对口味和摆盘的权重。

输出格式

输出应包含 $M$ 行。第 $\ell$ 行应包含一个数字：第 $\ell$ 个人最喜欢的菜的编号。

数据范围

• $1 \leqslant N \leqslant 500\,000$；
• $1 \leqslant M \leqslant 500\,000$；
• $0 \leqslant t_k \leqslant 1\,000\,000$，$0 \leqslant p_k \leqslant 1\,000\,000$，且对于所有 $k \leqslant N$，$(t_k, p_k) \neq (0, 0)$；
• $0 \leqslant T_\ell \leqslant 1\,000\,000$，$0 \leqslant P_\ell \leqslant 1\,000\,000$，且对于所有 $\ell \leqslant M$，$(T_\ell, P_\ell) \neq (0, 0)$；
• $N$ 个二元组 $(t_k, p_k)$ 两两不同；
• $M$ 个二元组 $(T_\ell, P_\ell)$ 两两不同。

样例

输入格式 1

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

输出格式 1

2
4
1

说明

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

输入格式 2

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

输出格式 2

2
2
1
1

说明

下表为每个人对每道菜的评分表。每个人的最爱菜品用 $\star$ 标出。