Любимое блюдо

Франция — страна гастрономии. Для блюда важны как вкус, так и его подача. Тем не менее, при оценке блюда разные люди могут уделять больше внимания либо вкусу, либо подаче. В столовой Олимпийской деревни есть $n$ блюд, пронумерованных от $1$ до $n$; каждое блюдо имеет оценку за вкус и оценку за подачу. Также есть $m$ человек, пронумерованных от $1$ до $m$; каждый человек имеет весовой коэффициент для вкуса и весовой коэффициент для подачи. Итоговая оценка блюда для конкретного человека — это взвешенное среднее значений оценок блюда за вкус и подачу.

Шеф-повара на Олимпиаде хотят предоставить каждому его любимое блюдо на вечере церемонии закрытия. Ваша задача — определить любимое блюдо каждого человека. Если несколько блюд имеют одинаково высокую оценку для конкретного человека, выберите блюдо с наименьшим номером.

Входные данные

Первая строка содержит два целых числа $n$ и $m(1\le n,m\le 5\cdot 10^5)$. Далее следуют $n$ строк; $k$-я из таких строк содержит два целых числа $t_k$ и $p_k(1\le t_k,p_k\le 10^6,(t_k,p_k)\ne (0,0)$ для всех $k\le n$, $n$ пар $(t_k,p_k)$ попарно различны), которые представляют оценки $k$-го блюда за вкус и за подачу. Затем идут ещё $m$ строк; $l$-я из таких строк содержит два целых числа $T_l$ и $P_l(1\le T_l,P_l\le 10^6,(T_l,P_l)\ne (0,0)$ для всех $l\le m$, $m$ пар $(T_l,P_l)$ попарно различны), которые представляют весовые коэффициенты $l$-го человека для вкуса и подачи.

Выходные данные

Выведите $m$ строк. $l$-я строка должна содержать одно число: номер любимого блюда $l$-го человека.

Примеры

Пример 1. Ниже представлена таблица оценок каждого человека для каждого блюда. Любимое блюдо каждого человека отмечено ⋆. У человека $3$ три блюда с одинаковой наивысшей оценкой, поэтому мы выбрали первое из них.

Пример 2. Ниже представлена таблица оценок каждого человека для каждого блюда. Любимое блюдо каждого человека отмечено ⋆.