Vasile s-a lansat în afaceri cu un produs inovativ: robotul WB, care joacă alba-neagra.
Jocul constă din K pahare identice, aşezate pe poziţii numerotate distinct de la 1 la K. WB ascunde iniţial o bilă sub paharul aflat pe poziţia S. Apoi execută foarte rapid N operaţii de interschimbare. La o interschimbare, WB selectează două poziţii şi interschimbă paharele plasate pe poziţiile selectate. Interschimbarea este făcută în aşa fel încât, dacă bila se află sub unul dintre paharele interschimbate, ea nu este vizibilă şi va fi mutată odată cu paharul sub care se află.
Fiind un robot, WB generează poziţiile paharelor implicate în interschimbări construind un şir de numere astfel: x₁=c; x_i=a*x_i-1+b, pentru orice i>1.
La cea de a i-a interschimbare, WB alege poziţiile (x_i%K+1) şi ((x_i+1)%K+1), unde cu x%y se notează restul împărţirii lui x la y.
După executarea celor N interschimbări, bila se află în paharul situat pe poziţia F.

Cerinţă

Scrieţi un program care determină numerele naturale a, b, c astfel încât după executarea celor N interschimbări paharul sub care se află bila să ajungă de pe poziţia S pe poziţia F.

Date de intrare

Fişierul de intrare wb.in conţine pe prima linie numerele naturale N K S F.

Date de ieşire

Fişierul de ieşire wb.out va conţine o singură linie pe care vor fi scrise numerele naturale a b c, separate prin câte un spaţiu, având semnificaţia din enunţ.

Restricţii

• 1 ≤ N ≤ 100000
• 2 ≤ K ≤ 10
• 1 ≤ S ≤ K
• 1 ≤ F ≤ K
• Numerele naturale a, b şi c nu vor depăşi valoarea 1000.
• Dacă există mai multe soluţii, se va alege soluţia în care a este minim. Dacă există mai multe soluţii cu a minim, se alege soluţia cu b minim. Dacă există mai multe soluţii pentru a şi b minime, se alege soluţia cu c minim.
• Pentru datele de test există soluţie.

Exemple

wb.in	wb.out	Explicaţii
3 4 2 4	2 0 1	Se execută N=3 interschimbări. Există 4 pahare, aşezate pe poziţii numerotate de la 1 la 4. Iniţial bila este plasată sub paharul aflat pe poziţia 2, iar după 3 interschimbări va ajunge pe poziţia 4. □ ■ □ □ Considerăm a=2 b=0 c=1 Interschimbarea 1: x1=1 Se interschimbă paharul de pe poziţia 2 cu paharul de pe poziţia 3 □ □ ■ □ Interschimbarea 2: x2=(2*x1+0)=2 Se interschimbă paharul de pe poziţia 3 cu paharul de pe poziţia 4 □ □ □ ■ Interschimbarea 3: x3=(2*x2+0)=4 Se interschimbă paharul de pe poziţia 1 cu paharul de pe poziţia 2 □ □ □ ■

autor: Prof. Emanuela Cerchez

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com