Domácí kolo

F: Zapletená slova

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Soutež skončila. Získané body již nejdou do výsledků.

Zadání (Řešení)

Při psaní zbrusu nového kompilátoru C++ si Vašek uvědomil, že by se mu mnohem lépe prováděly optimalizace stringových funkcí, kdyby sčítání stringů bylo komutativní (tedy aby pro každé dva stringy A, B platilo A + B = B + A, kde X + Y je řetězec vzniklý napsáním X a Y za sebe). Rozhodl se, že napíše komisi pro standardizaci nových featur do C++, aby komutativitu sčítání stringů zavedli v nové verzi C++. Ve svém otevřeném dopise by chtěl uvést nějaký příklad dvou stringů, které spolu komutují. Samozřejmě chce, aby příklad byl co nejpřesvědčivější, takže stringy v příkladu musí být v nějakém smyslu co nejhezčí.

Konkrétně Vašek hledá dva řetězce A a B složené z malých písmen anglické abecedy o předem dané délce, |A| = N, |B| = M, které splňují A + B = B + A. Nehledá však jen tak ledajaké dva řetězce: ze všech validních dvojic chce tu nejkrásnější. Krása dvojice je definovaná jako součet krásy obou řetězců a krása řetězce je definovaná pomocí krásové tabulky (ne nutně stejné pro A i B). Krásová tabulka má pro každou dvojici (pozice v řetězci, písmeno abecedy) zadáno nezáporné celé číslo, které určuje, jak krásné je, když má řetězec na dané pozici dané písmeno. Krása celého řetězce je pak součtem krás jednotlivých pozic.

Tvar vstupu

Na prvním řádku vstupního souboru je číslo T, počet problémů, které musíte vyřešit.

Pro každý problém dostanete na prvním řádku dvě čísla: N a M – délku prvního a druhého řetězce.

Na dalších N řádcích je popsána krásová tabulka pro první řetězec. Na i-tém řádku je 26 přirozených čísel, j-té z nich určující, jak krásné by to bylo, kdyby na i-té pozici prvního řetězce bylo právě j-té písmeno od začátku abecedy.

Na dalších M řádcích je podobným způsobem popsána krásová tabulka pro druhý řerězec.

Tvar výstupu

Pro každý problém vypište na samostatný řádek dva řetězce A a B oddělené mezerou: hledanou nejkrásnější dvojici podle podmínek popsaných v zadání. Pokud existuje více správných odpovědí, vyberte si libovolnou.

Lehká verze

  • T ≤ 10
  • N ≤ 100 000
  • čísla v krásové tabulce jsou menší než 10 000
  • N = M, tedy oba řetězce jsou stejně dlouhé

Těžká verze

  • T ≤ 10
  • N,M ≤ 100 000
  • čísla v krásové tabulce jsou menší než 10 000

Ukázkový vstup

2
2 2
1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 3
1 6 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 2 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 3 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 8 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Ukázkový výstup

ab ab
bb bbb

Vysvětlení ukázkového vstupu a výstupu

V prvním případě je A = ab, B = ab. Krása A je 1 + 2 = 3, krása B je 3 + 2 = 5. Celková krása obou řetězců je tedy 8. Všimněte si, že bb bb by byl také správný výstup. Naopak třeba výstup bc aa by sice měl větší krásu, ale neplatilo by A + B = B + A, proto je neplatný.

Ve druhém případě je A = bb a B = bbb. Krása dvojice je (6 + 2) + (3 + 8 + 2) = 21.

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)