Задача . Аптека

Сеть аптек держит все товары в специальном хранилище. Хранилище состоит из ячеек, нумерация которых начинается с единицы. В каждой ячейке находится строго одно лекарство. Одинаковые лекарства хранятся в идущих подряд ячейках. Лекарства в хранилище отсортированы по алфавиту.

В хранилище имеется \(n\) ячеек. Ячейки объединяются в камеры хранения, по \(m\) ячеек в каждой. Камеры хранения нумеруются так же, как и ячейки, начиная с единицы. То есть ячейки с номерами с 1 по \(m\) находятся в первой камере, с \(m+1\) по \(2m\) — во второй камере, и так далее.

Вам дана информация о лекарствах, хранящихся во всех \(n\) ячейках данного хранилища. Напишите программу, определяющую номер камеры, в которой хранится каждое из \(k\) лекарств из рецепта одного больного. Гарантируется, что все лекарства из списка имеются в наличии в хранилище. Если лекарство хранится сразу в нескольких соседних камерах, то требуется вывести номер первой из них.

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

В первой строке вводятся натуральное число \(n\) — количество ячеек в рассматриваемом хранилище и натуральное число \(m\) — количество ячеек в камере хранения (\(1\leqslant n\leqslant 10^6\), \(2\leqslant m\leqslant 10^5\)).

В последующих \(n\) строках вводятся названия лекарств, хранящихся в ячейках рассматриваемого хранилища (в порядке возрастания номеров ячеек), — слова, состоящие из строчных латинских букв.

Далее в отдельной строке вводится натуральное число \(k\) — количество лекарств, указанных в рецепте больного (\(1\leqslant k\leqslant 10^5\)).

В последующих \(k\) строках вводятся названия лекарств из списка.

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

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

Гарантируется, что все лекарства из списка имеются в наличии в хранилище. Если лекарство хранится сразу в нескольких соседних камерах, то требуется вывести номер первой из них.

2
1