Fișierul intrare/ieșire	ab.in, ab.out	Sursă	Baraj Shumen juniori 2014
Autor	Cristian Frâncu	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.6 sec	Limită de memorie	131072 KB
Scorul tău	N/A	Dificultate	4

Vezi soluțiile trimise | Statistici

AB (clasa a 8-a)

Fie două secvențe de numere intregi A = a₁a₂...a_k și B = b₁b₂...b_n. Spunem că secvența A “încape” în secvența B la poziția i dacă a₁ ≤ b_i, a₂ ≤ b_i+1, ... a_k ≤ b_i+k-1, unde i ≤ n-k+1.

Secvența A are proprietatea că a_i = (p*a_i-1 + q*a_i-2) % r, pentru i ≥ 3.

Secvența B are proprietatea că b_i = b_i-1 + (s*b_i-1 + t*b_i-2) % u pentru i ≥ 3.

Cerință

Date două secvențe A și B specificate prin numerele care le definesc unic, k, a₁, a₂, p, q, r, n, b₁, b₂, s, t, u să se găsească cea mai mică poziție i unde secvența A încape în secvența B.

Date de intrare

Pe prima linie a fisierului de intrare ab.in se va găsi k, număr zecimal, lungimea secvenței A. Pe cea de-a doua linie se vor găsi numerele a₁, a₂, p, q și r, numere ce determină unic secvența A. Pe a treia linie se va găsi n, număr zecimal, lungimea secvenței B. Pe a patra linie se vor găsi numerele b₁, b₂, s, t și u, numere ce determină unic secvența B.

Date de ieșire

Fișierul de ieșire ab.out va conține un singur număr, și anume poziția i unde secvența A încape în secvența B. Dacă nu există nici o astfel de poziție veți afișa valoarea 0.

Restricții

• 2 ≤ k ≤ n ≤ 4000000
• 0 ≤ a₁, a₂, r, s, t ≤ 2 miliarde
• -1 miliard ≤ p, q ≤ 1 miliard
• 0 ≤ b₁ ≤ b₂ ≤ 1000
• 0 ≤ u ≤ 500
• se garantează că toate elementele secvenței A sînt non-negative
• pozițiile în secvențele A și B se numerotează începînd cu unu (nu cu zero)

Exemple