Удаление одного элемента 2
Дан список из
n целых чисел. Требуется удалить один элемент так, чтобы произведение оставшейся последовательности по модулю m было равно p. Формально, если индекс удаляемого элемента равен r:Программа должна найти индекс такого числа или вывести
Impossible, если подходящий элемент не существует.Входные данные
В первой строке задаются 3 целых числа
n (1 ≤ n ≤ 10^5), m (1 ≤ m ≤ 10^9) и p (0 ≤ s < m).Во второй строке содержатся
n целых чисел a_1, a_2, ..., a_n, разделённые пробелами (0 ≤ a_i ≤ 10^9).Выходные данные
Если такого элемента не существует, нужно вывести
Impossible. В противном случае программа должна вывести индекс первого подходящего элемента в данном списке. Индексация начинается с 1.Примеры
Входные данные | Выходные данные |
3 8 5
5 0 9 | 2 |
3 8 5
5 10 7 | Impossible |
Пояснение
- 5 * 9 = 45 ⇒ 45 mod 8 = 5 ⇒ можно удалить элемент со значением 0, находящийся на позиции 2.
- Невозможно убрать какой-либо элемент так, чтобы произведение оставшихся чисел по модулю 8 стало равно 5.
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB