Нека е дадена низа со N елементи, односно даден ви е елементот R[0], а вие самите можете да си ги пресметате останатите елементи од низата со следната релација:

R[i]=(R[i-1]*P1 + P2) mod M.
(За дадени два цели броја А и B, A mod B е остатокот кој се добива при делење на A со B. На пример, 7 mod 3 = 1.)

Замислете дека има кружна патека со N точки, нумерирани последователно од 0 до N-1 (распоредени на еднакви растојанија на патеката). Растојанието меѓу секои 2 точки е 1. Од секоја точка i, Вие може да скокнете до точка на оддалеченост најмногу R[i] во која било насока на патеката. На пример, ако R[i]=2, Вие може да скокнете на која било од позициите {i-2,i-1,i,i+1,i+2} .

Вие сте на точката S и Ваша задача е да дојдете на точката T. Во колку најмалку скокови можете да го направите тоа? Ако тоа не е можно (сте заглавиле на точка на која R[i]=0), отпечатете -1.

Забелешка: Ако на почетокот веќе стоите на точката на која треба да стигнете, вие всушност стигнувате со 0 скокови.

Влез

Во првиот ред има 3 цели броеви одделени со по едно празно место: N (1 ≤ N ≤ 10 000 000), S (0 ≤ S < N) и T (0 ≤ Т < N).
Во вториот ред има 4 цели броеви одделени со празни места, R[0], P1 , P2 и M (1 ≤ M ≤ N, 0 ≤ R[0] < M, 0 ≤ P1 < M , 0 ≤ P2 < M).

Излез

Во првиот ред отпечатете го минималниот број на скокови што ќе ве донесе до целната позиција. Ако не е можно да се стигне до неа, отпечатете -1.

Ограничувања

Временско ограничување: 2 seconds
Мемориско ограничување: 256 megabytes

Примери

влез
9 0 2
1 3 4 7

излез
2

влез
9 7 2
1 3 4 7

излез
-1

Објаснување за првиот пример: Низата од 9 елементи за дадените вредности R[0]=1, P1=3 , P2=4 и M=7 e:
R[0]=1
R[1]=(R[0]*3 + 4) mod 7=(1*3 + 4) mod 7=0
R[2]=(R[1]*3 + 4) mod 7=4
R[3]=(R[2]*3 + 4) mod 7=2
R[4]=(R[3]*3 + 4) mod 7=3
R[5]=(R[4]*3 + 4) mod 7=6
R[6]=(R[5]*3 + 4) mod 7=1
R[7]=(R[6]*3 + 4) mod 7=0
R[8]=(R[7]*3 + 4) mod 7=4

На кружната патека Вие од почетната точка каде што сте (во 0) потребни ви се најмалку 2 чекори за да стигнете до точка 2. На пример:
- Во првиот чекор од точката 0 може да стигнете во точка 8 или точка 1 бидејќи R[0]=1, а точката 8 и точката 1 се на растојание 1 од точка 0 (патеката е кружна). Одбираме да отидеме во 8.
- Во вториот чекор од точката 8 може да стигнете до точка 2. Бидејќи R[8]=4, од точката 8 може да скокнете до точка на оддалеченост 3 надесно на патеката и така ќе стигнете до точка 2 (8->0->1->2).

Објаснување за вториот пример: Низата од 9 елементи е R[0]=1, R[1]=0,… (исто како во првиот тест пример). На кружната патека Вие сте на точка 7, а треба да стигнете на точка 2. Затоа што R[7]=0, Вие не можете никако да стигнете на друга точка, а потоа не може да стигнете до точката 2.