Quido a Hugo bydlí v téže ulici. Ulice vede kolem břehu jezera, a tak má jen jednu řadu domečků. Domečky mají různé barvy a také jejich střechy mají různé barvy, které mnohdy s barvou domečku ladí nebo neladí, podle vkusu majitelů a také podle toho, která nejlacinější barva byla k dostání, když se domeček nebo střecha naposled opravovaly.

Na jedné ze svých cest za Hugem si Quido nedávno všiml, že mezi jeho a Hugovým domečkem se najdou všechny možné barvy domečků, které jsou v ulici. Započítal přitom i svůj a Hugův domeček. Hugo v podobné situaci o den později si naopak všiml, že totéž platí o barvách střech: Ze všech barev střech v ulici se najde každá na některé střeše domečku mezi Hugem a Quidem včetně střech na domečcích obou přátel.

Na procházce příštího dne pak zkontrolovali, že se opravdu nemýlili, a Quido řekl:

“Kdybych ale nezapočítal buďto můj nebo tvůj domeček, tak by už moje zjištění o barvách domečků neplatilo.”

“Vidíš,” odpověděl Hugo, “o barvách střech se dá říci přesně totéž.”

Obrázek 1. Pohled z jezera na ulici, kde bydlí Quido a Hugo. Pro přehled jsou u domečků uvedena jejich čísla. Quido a Hugo bydlí v číslech 7 a 12, nevíme sice, kdo ve kterém, ale to nám teď nevadí.

Je dána posloupnost barev domečků v pořadí, jak vedle sebe stojí v ulici a také je dána posloupnost barev střech domečků ve stejném pořadí. Máme určit všechny možné dvojice domečků, ve kterých mohou Quido a Hugo bydlet.

Zkontrolujte si uvedené příklady a najděte správné řešení pro vstupní data dole na stránce pod příklady.

Vstup obsahuje tři textové řádky.

První řádek obsahuje jedno celé kladné číslo N představující počet domečků v ulici. Na druhém řádku je uvedeno bez mezer N malých znaků anglické abecedy, každý znak kóduje jednu barvu domečku. Na třetím řádku je opět uvedeno bez mezer N malých znaků anglické abecedy, tentokrát každý znak kóduje jednu barvu střechy odpovídajícího domečku. Pořadí znaků na obou řádcích odpovídá pořadí domečků v ulici. Pořadí je číslováno od jedničky. Hodnota N nepřesáhne 1000000.

Výstup obsahuje několik textových řádků, na každém řádku jsou uvedena dvě celá čísla oddělená mezerou. Čísla představují dvojici domečků, ve kterých mohou Quido a Hugo bydlet.
Na řádku je vždy napřed menší číslo a řádky mohou být uvedeny v libovolném pořadí.
Je zaručeno, že hledaná dvojice domečků je vždy alespoň jedna.

17
ccbdbacddbdadacbd
iikkmimiihhkkiimm

7 12

Schéma ilustrující situaci v příkladu 1 je znázorněno na obrázku 1.

9
abcabcabc
kkmookmom

2 4
5 7
6 8

80
sydhhppyphydyppyyppyppppppypphyppppsdydhsdhppyspsphydyhdphppysysdpyppphpypppyssy
qyrkyyqyryrqrrrryrrrrrykrrrrrkrrrrrdqdqyrddqrrqrkdyrydqkqqykyydkqrkykrykkryrydkr 

12 36
65 78

V příkladu 4 je 10 000 domečků, v příkladu 5 jich je 1 000 000, můžete si je stáhnout zazipované i s výsledky: tady.

• Stáhněte si soubory zadani1.txt a zadani2.txt. Každý obsahuje jedna vstupní data ve stejném formátu jako uvedené příklady. V prvním souboru je 20 000 domečků a ve druhém souboru je 1 000 000 domečků.
  
• Vytvořte dva textové soubory reseni1.txt a reseni2.txt a do každého zapište odpovídající řešení ve správném formátu.
  
• Oba soubory zazipujte do jednoho archivu (s příponou .zip, na jeho jménu nesejde) a odevzdejte do odevzdávacího systému Hapky.

Za každé správně vyřešené zadání získáte 10 bodů, takže za obě správně vyřešená zadání získáte celkem 20 bodů.