Дан массив из n целых чисел, отсортированный по неубыванию, и k запросов. Числа в массиве могут повторяться; массив может быть пустым.
Для каждого числа-запроса x найдите две позиции вставки: перед всеми элементами, равными x, и после всех таких элементов. В обоих случаях после вставки должен сохраняться порядок по неубыванию.
Позиции нумеруются от 1 до n + 1. Позиция i при 1 ≤ i ≤ n означает место перед элементом с номером i; позиция n + 1 — место после последнего элемента.
Если x отсутствует в массиве, обе позиции совпадают. Для пустого массива обе позиции равны 1.
Саму вставку выполнять не нужно. Все запросы относятся к исходному массиву.
Входные данные
В первой строке содержатся два целых числа n и k (0 ≤ n ≤ 105, 1 ≤ k ≤ 105) — длина массива и количество запросов.
Во второй строке содержатся n целых чисел — элементы массива, отсортированного по неубыванию. Если n = 0, вторая строка пустая.
В третьей строке содержатся k целых чисел — запросы. Все элементы массива и запросы по модулю не превосходят 2 · 109.
Выходные данные
Для каждого запроса выведите в отдельной строке два числа через пробел: сначала позицию вставки перед равными, затем позицию вставки после равных.
| № | Входные данные | Выходные данные |
|
1
|
7 6
2 4 7 7 7 9 12
7 8 2 12 1 20
|
3 6
6 6
1 2
7 8
1 1
8 8
|
|
2
|
0 3
-1 0 1
|
1 1
1 1
1 1
|