Улюблена страва#11751
Франція — країна гастрономії. Для страви важливі як смак, так і її подача. Тим не менш, при оцінці страви різні люди можуть надавати більше значення або смаку, або подачі. У їдальні Олімпійського селища є страв, пронумерованих від до ; кожна страва має оцінку за смак і оцінку за подачу. Також є осіб, пронумерованих від до ; кожна особа має ваговий коефіцієнт для смаку і ваговий коефіцієнт для подачі. Підсумкова оцінка страви для конкретної особи — це зважене середнє значення оцінок страви за смак і подачу.
Шеф-кухарі на Олімпіаді хочуть надати кожному його улюблену страву на вечері закриття. Ваше завдання — визначити улюблену страву кожної особи. Якщо декілька страв мають однаково високу оцінку для конкретної особи, оберіть страву з найменшим номером.
Перший рядок містить два цілих числа і m~(1 \le n, m \le 5 \cdot 10^5). Далі йдуть рядків; -й з таких рядків містить два цілих числа t_k і p_k~(1 \le t_k, p_k \le 10^6, (t_k, p_k) \ne (0, 0) для всіх k \le n, пар (t_k, p_k) попарно різні), які представляють оцінки -ї страви за смак і подачу. Потім ідуть ще рядків; -й з таких рядків містить два цілих числа T_l і P_l~(1 \le T_l, P_l \le 10^6, (T_l, P_l) \ne (0, 0) для всіх l \le m, пар (T_l, P_l) попарно різні), які представляють вагові коефіцієнти -ї особи для смаку і подачі.
Виведіть рядків. -й рядок має містити одне число: номер улюбленої страви -ї особи.
Приклад 1
Приклад 2
У прикладі 1 представлено таблицю оцінок кожної особи для кожної страви. Улюблена страва кожної особи позначена ⋆. У особи три страви з однаковою найвищою оцінкою, тому ми обрали першу з них.
У прикладі 2 представлено таблицю оцінок кожної особи для кожної страви. Улюблена страва кожної особи позначена ⋆.