Stejný tvar stromu

Nechť T je binární strom. Řekneme že binární strom U je podstrom stromu T, pokud jsou splněny obě následující podmínky:
1. Každý uzel stromu U je také uzlem stromu T a každá hrana stromu U je také hranou stromu T.
2. Pro každý uzel x stromu T platí: Jestliže kořen U leží na cestě z x do kořene T, pak x je také uzlem U.
Připomeňme, že uzel leží na nějaké cestě právě tehdy, když je totožný s některým jejím uzlem, ať už krajním nebo vnitřním.

Výšku binárního stromu T definujeme jako počet hran na nejdelší možné cestě z kořene T do některého listu T.

Nechť jsou T1 a T2 dva binární stromy. Řekneme, že T1 a T2 mají stejný tvar, pokud pro ně platí následující rekurzivní vztah: Buďto jsou oba stromy T1 a T2 prázdné nebo jsou oba neprázdné a pak zároveň levý podstrom kořene T1 má stejný tvar jako levý podstrom kořene T2 a zároveň pravý podstrom kořene T1 má stejný tvar jako pravý podstrom kořene T2.

Nechť S a H jsou celá nezáporná čísla. Řekneme, že dva binární stromy T1 a T2 jsou slabě (S, H)-podobné, pokud v T1 existuje podstrom U1 s S uzly a výškou H a v T2 existuje podstrom U2 mající stejný tvar jako U1.
Řekneme, že dvojice binárních stromů (T1, T2) má (S, H)-index, pokud jsou T1 a T2 jsou slabě (S, H)-podobné a pro každou dvojici čísel (S1, H1) lexikograficky větší než (S, H) platí, že T1 a T2 nejsou slabě (S1, H1)-podobné.

Úloha
Pro dané dva binární stromy T1 a T2 máme určit dvojici čísel (S, H) tak, aby dvojice (T1 a T2) měla (S, H)-index.

Nechť (Z, A, C, M, D) je pětice celých kladných čísel. Označme F celočíselnou funkci
F: F(n) = (A*n + C) mod M.
Řekneme že binární strom T je popsán pěticí (Z, A, C, M, D), pokud platí:
1. Každý uzel x stromu T obsahuje celočíselný klíč, označme ho K(x).
2. Nechť x je uzel T. Tento uzel má
    a. žádného potomka, pokud K(x) mod 4 = 0,
    b. pouze levého potomka, pokud K(x) mod 4 = 1,
    c. pouze pravého potomka, pokud K(x) mod 4 = 2,
    d. levého i pravého potomka, pokud K(x) mod 4 = 1.
3. Klíč kořene T je roven Z. Klíč levého uzlu potomka uzlu x je roven F(K(x)+1), klíč pravého uzlu potomka uzlu x je roven F(K(x)+2).
4. Hloubka T nepřesáhne hodnotu D.

Vstup

Na vstupu je jeden textový řádek s šesti celými čísly Z1, Z2, A, C, M, D navzájem oddělenými mezerou

Výstup

Na výstupu je jeden textový řádek obsahující dvě celá čísla S, H, oddělená mezerou. Tato čísla představují (S, H)-index dvojice binárních stromů (T1, T2), přičemž T1 je popsán pěticí (Z1, A, C, M, D) a T2 je popsán pěticí (Z2, A, C, M, D).

Příklad 1

Vstup:

Výstup:

Příklad 2

Vstup:

Výstup:

Příklad 3

Vstup:

Výstup:

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