Задача. Бинарный поиск: проверка скорости

Та же задача, что и две предыдущие, только размер массива также до 100000.

Дан массив из N чисел, упорядоченный по неубыванию. И дано еще K чисел, каждое из которых надо найти в массиве или сказать, что такого числа в массиве нет.

Входные данные. Вводятся числа N и K (N и K не превышают 105). Затем вводится N чисел, являющихся элементами массива. Затем вводится K чисел, которые надо искать. Элементы массива целые, неотрицательные и не превосходят 109.

Выходные данные. Выведите K чисел, равные номерам искомых элементов в массиве. Если в массиве несколько искомых элементов, может быть выведен номер любого из них. Если искомого элемента в массиве нет, выведите -1.

Пример вводаПример вывода
8 5
1 3 4 7 8 11 15 19
9 4 20 11 1
-1
3
-1
6
1