Hard MEX#5875
Вам дана колекція з пронумерованих предметів, позначених від до P - 1. Процес вибирає (можливо з повтореннями) предметів із колекції згідно з наступним правилом:
Перший вибраний предмет має номер x_1. Кожен наступний вибраний предмет обчислюється як
де та — задані цілі числа, а позначає залишок від ділення. Процес може вибирати один і той же предмет більше одного разу. Після того, як обрано предметів, визначте найменше невід'ємне ціле число менше за , яке не було вибрано під час процесу.
У першому рядку містяться два цілі числа і (1 \le N < P \le 10^9, N \le 10^7) — загальна кількість предметів і кількість виборів.
У другому рядку містяться два цілі числа і (0 \le a, b \le 10^9), які визначають правило вибору.
У третьому рядку міститься одне ціле число x_1 — номер першого вибраного предмета.
Виведіть одне ціле число — найменший номер від до P - 1, який не був вибраний під час процесу.
Приклад 1