Задача F. Строка

Автор:Фёдор Царёв   Ограничение времени:2 сек
Входной файл:string.in   Ограничение памяти:256 Мб
Выходной файл:string.out  

Условие

В математике часто встречаются так называемые рекуррентные соотношения. Обычно они применяются для задания числовых последовательностей — очередное число в последовательности некоторым образом выражается через предыдущие. Примером такой последовательности являются числа Фибоначчи (в них очередное число равно сумме двух предыдущих).

С помощью соотношений такого типа можно задавать не только последовательности чисел, но и последовательности строк. В этой задаче рассматривается последовательность строк s0, s1, , задаваемая следующим образом.

Строка s0 пуста, а каждая строка si (i ≥ 1) получается из si − 1 по следующему правилу: если десятичная запись числа i входит как подстрока в si − 1, то si = si − 1, иначе si получается приписыванием к si − 1 в конец десятичной записи числа i.

Задано число n. Необходимо найти строку sn.

Формат входного файла

Входной файл содержит целое число n (1 ≤ n ≤ 500).

Формат выходного файла

В выходной файл выведите строку sn.

Примеры тестов

Входной файл (string.in) Выходной файл (string.out)
1
1
1
2
3
123
3
13
123456789101113

0.099s 0.039s 13