Улюблена страва

Франція — країна гастрономії. Для страви важливі як смак, так і її подача. Тим не менш, при оцінці страви різні люди можуть надавати більше значення або смаку, або подачі. У їдальні Олімпійського селища є $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. Нижче представлено таблицю оцінок кожної особи для кожної страви. Улюблена страва кожної особи позначена ⋆.