Самый похожий чек

Система анализа чеков сравнивает состав нового чека с ранее сохранёнными чеками. Каждый товар задаётся кодом, а количество купленных единиц считается координатой вектора.

Во входных данных приведены две таблицы. Первая таблица содержит новый чек: код товара и количество. Вторая таблица содержит строки сохранённых чеков: номер чека, код товара и количество. Одинаковые коды товаров из двух таблиц обозначают одну и ту же координату векторов. Если товар отсутствует в некотором чеке, его количество считается равным нулю.

Для каждого сохранённого чека вычисляется косинусная близость с новым чеком:

cos(A, B) = (Σ A_i · B_i) / (sqrt(Σ A_i²) · sqrt(Σ B_i²)),

где сумма берётся по всем товарам, встретившимся хотя бы в одном из двух чеков. Требуется вывести номер сохранённого чека с наибольшей косинусной близостью к новому чеку.

Если наибольшая косинусная близость достигается у нескольких чеков, выводится лексикографически наименьший номер чека. Округление не выполняется, так как выводится номер чека. В новом чеке есть хотя бы один товар, а каждый сохранённый чек содержит хотя бы одну строку, поэтому деления на ноль не возникает.

Формат ввода

В первой строке даны два целых числа n и m — число строк в таблице нового чека и число строк в таблице сохранённых чеков.

В следующих n строках записаны код товара product и целое количество count в новом чеке.

В следующих m строках записаны номер сохранённого чека receipt, код товара product и целое количество count в этом чеке.

Коды товаров в первой таблице не повторяются. Пара из номера чека и кода товара во второй таблице не повторяется.

Формат вывода

Выведите номер сохранённого чека с наибольшей косинусной близостью к новому чеку.

Ограничения

1 ≤ n ≤ 2000.

1 ≤ m ≤ 2000.

n + m ≤ 2000.

Количество товаров в каждой строке: целое число от 1 до 10000.

Коды товаров и номера чеков состоят из заглавных латинских букв, цифр и символа _, имеют длину от 1 до 12.

Число различных сохранённых чеков — от 1 до m.