У DZY есть хэш-таблица с p ячейками, пронумерованными от 0 до p - 1. Он хочет записать в хэш-таблицу n чисел в заданном порядке: i-е число xi DZY хочет записать в ячейку хеш-таблицы с номером h(xi), где h(x) — хэш-функция. В этой задаче мы будем считать, что h(x) = x mod p. Операция a mod b означает взятие остатка от деления a на b.
Однако каждая ячейка хеш-таблицы может содержать не более одного элемента. Если DZY хочет записать число в уже занятую ячейку, то происходит «коллизия». Вам нужно найти номер первого элемента, при вставке которого произойдет коллизия.
Если первая коллизия происходит сразу после вставки i-го элемента, надо вывести i. Если коллизия вовсе не произойдет, выведите -1.
Выходные данные
Выведите единственное целое число — ответ на задачу.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 5
0
21
53
41
53
|
4
|
|
2
|
5 5
0
1
2
3
4
|
-1
|