Mediány

V této úloze budeme uvažovat neprázdné posloupnosti celých čísel, číslované počínaje indexem 1.
Uspořádáním posloupnosti A = (a₁, a₂, ..., a_n) rozumíme posloupnost B = (b₁, b₂, ..., b_n), jejíž prvky jsou uspořádány v neklesajím pořadí a přítom B je permutací prvků A.
Pro každou posloupnost A = (a₁, a₂, ..., a_n), kde n je liché číslo, definujeme spodní celočíselný medián A jako číslo rovné prvku s indexem (n+1)/2 v uspořádání A.
Pro každou posloupnost A = (a₁, a₂, ..., a_n), kde n je sudé číslo, definujeme spodní celočíselný medián A jako dolní celou část aritmetického průměru prvků s indexy n/2 a n/2+1 v uspořádání A.
Spodní celočíselný medián posloupnosti A označíme symbolem SCM(A).

Pro danou posloupnost A = (a₁, a₂, ..., a_n), kde n > 1, definujeme levou částečnou mediánovou posloupnost C = (c₁, c₂, ..., c_n−1) takto:
Pro 1 ≤ i ≤ n−1 je c_i = SCM(a₁, a₂, a₃, ..., a_i+1).
Levou částečnou mediánovou posloupnost posloupnosti A označíme symbolem LCMP(A).

Pro danou posloupnost A = (a₁, a₂, ..., a_n) a pro kladné celé číslo k (k < n) rekurzivně definujeme k-iterovanou levou částečnou mediánovou posloupnost, kterou označíme symbolem LCMP(A)^(k), takto:
1. Pro k = 1, je LCMP(A)^(k) = LCMP(A),
2. pro k > 1, je LCMP(A)^(k) = LCMP(LCMP(A)^(k−1)).

Posloupnost A definujeme pomocí pěti celých kladných čísel P, Q, R, M, N takto:
1. a₁ = P,
2. a_i = (Q×a_i−1 + R) mod M, pro 2 ≤ i ≤ N.

Úloha
Pro danou posloupnost A a pro dané číslo k máme určit první a poslední prvek posloupnosti LCMP(A)^(k).

Vstup

Na vstupu je jeden řádek obsahující šest kladných celých čísel P, Q, R, M, N, k v tomto pořadí oddělených navzájem mezerou. Význam čísel je popsán v textu úlohy.
Hodnoty P, Q, R, M, nepřekročí 10⁵, hodnota N nepřekročí 10⁶, hodnota k nepřekročí 10, P < M, k < N.

Výstup

Na výstupu je jeden textový řádek s dvěma celými čísly oddělenými mezerou. První číslo představuje první prvek posloupnosti LCMP(A)^(k) a druhé číslo představuje její poslední prvek.

Příklad 1

Vstup:

3 4 5 10 6 2

Výstup:

4 5

A = (3, 7, 3, 7, 3, 7),
LCMP(A)⁽¹⁾ = (5, 3, 5, 3, 5),
LCMP(A)⁽²⁾ = (4, 5, 4, 5).

Příklad 2

Vstup:

8 2 5 11  8 2

Výstup:

8 5

A = (8, 10, 3, 0, 5, 4, 2, 9),
LCMP(A)⁽¹⁾ = (9, 8, 5, 5, 4, 4, 4),
LCMP(A)⁽²⁾ = (8, 8, 6, 5, 5, 5).

Příklad 3

Vstup:

1401 14087 30211 98191 1000000 10

Výstup:

22664 49407

Veřejná data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data