Problem description

Jasio dostał od taty długopis (oczywiście z logiem Januszex S.A.). Niewiele myśląc napisał na kartce ciąg cyfr (pisząc cyfry nie trzeba się martwić o przypadkowe napisanie wulgaryzmów tak jak martwił się wcześniej przy okazji zadania Napis bez wulgaryzmów). Jasio podszedł do taty i mówi mu tak: Napisałem tutaj wszystkie liczby naturalne! Tacie Jasia oczywiście nie chce się w to wierzyć, jako że Jasio napisał (co prawda długi) skończony ciąg cyfr. Oczywiście, zanim tata wyrazi swoją opinię, wypadałoby znaleźć konkretną liczbę, której Jasio nie napisał na swojej kartce. Dobrze byłoby, gdyby była to stosunkowo mała liczba – może to lepiej przemówi Jasiowi do rozsądku, aby nie rzucał pochopnie słów na wiatr.

Tata oczywiście wie, że gdy powie, że na przykład w ciągu cyfr 123 nie występuje liczba 13 to Jasio szybko zakryje palcem cyfrę 2 i powie, że chodziło mu o występowanie liczb jako podciągi (czyli niekoniecznie spójne ciągi cyfr). Hmm, po chwili namysłu tata jednak nie ma pewności czy Jasio będzie aż taki sprytny. Może jednak stwierdzi, że rzeczywiście chodzi o podsłowa (spójne podciągi), a w takiej sytuacji może można mu podać mniejszą liczbę. Lepiej być chyba gotowym na obie opcje.

Napisz program, który: wczyta ciąg cyfr napisany przez Jasia, wyznaczy najmniejszą liczbę, która nie występuje jako podciąg oraz najmniejszą liczbę, która nie występuje jako podsłowo w napisanym ciągu cyfr i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się ciąg cyfr napisany przez Jasia. Cyfry nie są oddzielone żadnymi odstępami.

Wyjście

W pierwszym wierszu wyjścia należy wypisać najmniejszą liczbę naturalną, która nie występuje jako podciąg w napisanym przez Jasia ciągu cyfr. W drugim wierszu wyjścia należy wypisać najmniejszą liczbę naturalną, która nie występuje jako spójny podciąg w napisanym przez Jasia ciągu cyfr.

Uwaga

W zadaniu tym należy założyć, że 0 jest liczbą naturalną. Liczby z nadmiarowymi zerami wiodącymi (np. 00 lub 01) nie są akceptowane przez Jasia jako sensowne liczby.

Ograniczenia

Długość ciągu cyfr z wejścia nie przekracza 500 000.

Przykład

15032

4
4

21234567891011

32
13