Задача . Подарки в хранилище 2

Вы уже знаете, что Дед Мороз хранит запасы подарков в своих тайных хранилищах. Напомним, что хранилище состоит из ячеек, нумерация которых начинается с единицы. В каждой ячейке находится строго один подарок. Одинаковые подарки хранятся в идущих подряд ячейках. Подарки в хранилище отсортированы по алфавиту.

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