24361번 - ДЪЖД 다국어

От външната страна на прозореца си Ели има продълговата, но тясна саксия с красиви цветя. Всеки път когато завали, момичето почва с интерес да следи къде падат дъждовните капки. Ако по някое време на дъжда не остане подинтервал на саксията с дължина по-голяма от D, в който да не е попаднала капка, момичето счита цветята си за напоени и спира да следи капките. За целите на тази задача ще считаме саксията за отсечка с дължина L, а капките дъжд – като точки върху тази отсечка.

Не веднъж, когато сте били на гости на Ели, се е случвало да завали и тя тотално да спре да ви слуша, концентрирайки се върху падащите капки. Затова вие решавате да напишете програма agrain, която, ако знае къде ще паднат всички капки (в реда на тяхното падане), ви казва след коя от тях Ели ще спре да следи дъжда и отново ще ви обърне внимание.

На първия ред на стандартния вход ще бъдат зададени целите числа N, L, и D – съответно брой капки, паднали по време на дъжда (в реда на тяхното падане), дължината на саксията и максималната дължина на подинтервал, в който не е паднала нито една капка. На втория ред ще бъдат зададени целите числа X₁, A, и B. Първата капка пада в позиция X₁. Всяка следваща пада на позиция X_i = (X_i-1 * A + B) % (L + 1).

На един ред на стандартния изход изведете едно цяло число – брой капки, които трябва да паднат, преди Ели да спре да следи дъжда (тоест да счете цветята за напоени). Ако дори след падането на всички N капки остане подинтервал с дължина по-голяма или равна на D, изведете -1.

• 1 ≤ N ≤ 10 000 000
• 1 ≤ D < L ≤ 1 000 000 000
• 0 ≤ X₁, A, B ≤ L

В първия пример са паднали 12 капки, чиито координати са съответно (14, 19, 12, 17, 10, 15, 8, 13, 6, 11, 4, 9). До падането на 9-тата капка интервалът [0, 8) е бил без паднала капка. След като тя падне в позиция 6, обаче, всички "сухи" подинтервали стават с дължина ≤ 7.

Във втория пример пада точно една капка дъжд, но тя успява да напои цветята на Ели.