Задача B. Важнейшая часть

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Компания X желает разработать программу для автоматического поиска интересной информации на веб-страницах. В частности, было замечено, что авторы веб-сайтов любят выделять важную информацию при помощи курсива, жирного шрифта, подчёркивания и т.д. Директор компании высказал предположение, что самая важная информация будет выделена сильнее всего. Поэтому вам поручено написать программу, которая в данном тексте найдёт участок с наибольшим количеством выделений.

Исходными данными для программы будет строка символов, содержащая пары тегов <i> ... </i>, <u> ... </u>, <b> ... </b>, ограничивающие выделенные различным образом подстроки. Теги могут повторяться и вкладываться друг в друга, например This <b>is <i>a <u>sample of <b>very</b></u> important</i> text</b>. Ваша программа должна найти подстроку, вложенную в наибольшее количество тегов. Если таких подстрок несколько, следует вывести самую левую из них. В приведённом примере ответом будет подстрока very.

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

Во входном файле находится исходная строка текста.

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

В выходном файле должна содержаться наиболее выделенная подстрока. Подстроку следует выводить целиком: от символа, следующего за открывающим тегом, до символа, предшествующего закрывающему тегу.

Ограничения

Длина исходной строки не превосходит 10000 символов. Открывающие и закрывающие теги образуют правильную скобочную последовательность (каждому открывающему тегу соответствует парный закрывающий, и наоборот). Например, последовательность <i>a<u>b</i></u> не может встретиться во входном файле. Между открывающим и закрывающим тегом есть по крайней мере один символ.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
no selection
no selection
2
<b>test</b><b>simple</b>
test

0.073s 0.011s 13