Задача . Хранилище магазина

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

В одном из хранилищ имеется \(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