Маніпулятор (manipul)
Після непорозуміння, що сталося з маніпулятором, яке налякало секретаря Лізоньку, професор Геній Євгенович вирішив його удосконалити і підключив до комп'ютера. Для управління маніпулятором він написав програму, яка представляла собою величезну таблицю А розміром NxN, що складається з нулів і одиниць, причому одиниці стояли тільки в тих комірках таблиці, у яких залишок від ділення номера рядка і номера стовпчика на деяке число М був однаковим, тобто A[row][column]=1 тільки якщо
row% M = column% M.
Вночі в лабораторію Генія Євгеновича заглянули фіксіки і випадково пересунули на його столі магніт так, що він зіпсував практично всю інформацію на вінчестері. Дивом уціліла рівно P-1 одиниця в програмі для маніпулятора, всі інші комірки обнулились. Сімка страшенно злякалася і спробувала відновити програму. Однак їй вдалося домогтися появи всього однієї додаткової одиниці в таблиці, причому на довільному місці. Оскільки програма була безнадійно зіпсована, професор запропонував вам знайти максимальне з усіх можливих значень М для вихідної таблиці.
Формат ведення-виведення:
Програма manipul спочатку читає з клавіатури (стандартного пристрою введення) два цілих числа N і P P (2 ≤ N ≤ 105; 2 ≤ P ≤ min(105,N2)). Потім зчитується Р пар цілих невід'ємних чисел, що не перевищують значення N-1 - позиції збережених одиничок. Правда, невідомо, яка з цих одиниць виникла як побічний ефект після маніпуляцій Сімки.
Програма manipul виводить на екран (стандартне пристрої виведення) єдине число - максимально можливе число М для початкової таблиці. Якщо максимальне значення однозначно не визначається, необхідно вивести «-1» (без лапок). Значення М вважається можливим, якщо в програмі для маніпулятора, принаймні на Р-1 позиції, заданих у вхідних даних, буде стояти одиниця.
Приклад вхідних та вихідних даних:
|
Введення |
Виведення |
|
3 5 0 0 0 1 1 0 2 2 2 1 |
1 |
|
5 5 0 0 1 1 0 3 1 3 4 4 |
3 |
|
3 2 0 0 0 1 |
-1 |
Пояснення до вхідних тестів:
У другому тесті таблиця після дії магніту має вигляд:
10010
01010
00000
00000
00001
Для такої таблиці можливі значення М=2 и М=3. При М=3 програма має такий вигляд:
10010
01001
00100
10010
01001
Тобто одиниця в позиції 00 (1,3) була побічним ефектом.
В третьому тесті таблиця після дії мала вигляд:
110
000
000
Для такої таблиці підходять всі цілі числа, тому відповідь «-1». Для М>1 вважається, що друга одиниця в першому рядку – побічний ефект.