Излом инерции для жанров фильмов

Онлайн-кинотеатр строит тематические подборки фильмов отдельно для каждого жанра. Для каждого жанра заранее рассчитана инерция при числе подборок от 1 до m. Чем меньше инерция, тем компактнее получаются подборки.

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

Для каждого жанра из запроса требуется определить число подборок после наиболее сильного относительного уменьшения инерции. Для каждого k от 2 до m, если известны обе инерции I(k-1) и I(k), вычисляется относительное уменьшение

D(k) = (I(k-1) - I(k)) / I(k-1).

Искомым считается такое k, для которого D(k) максимально. Если максимальное относительное уменьшение достигается при нескольких k, выбирается наименьшее k. Для каждого жанра гарантируется существование хотя бы одной пары соседних известных значений инерции. Пустых жанров во входных данных нет, а каждый жанр из запроса присутствует среди описанных жанров.

Формат ввода

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

В следующих n строках записаны описание жанра и m значений. Сначала идёт код жанра, затем инерции I(1), I(2), ..., I(m). Каждая инерция задана положительным целым числом или символом -.

Затем дано целое число q — число запросов. В следующих q строках записаны коды жанров, для которых требуется найти ответ.

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

Для каждого запроса выведите в отдельной строке одно целое число k — номер числа подборок после наибольшего относительного уменьшения инерции.

Выводится целое число, округление не применяется.

Ограничения

1 ≤ n ≤ 2000.

2 ≤ m ≤ 20.

1 ≤ q ≤ 2000.

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

Каждое числовое значение инерции находится в диапазоне от 1 до 10^9. Для каждого жанра среди позиций от 2 до m существует хотя бы одна позиция k, у которой I(k-1) и I(k) известны.