Задача C. Марсианский заголовок

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

Условие

Марсианский журнал решил опубликовать статью о жизни на других планетах. Статья представляет собой строку из заглавных и строчных латинских букв. Пробелы и знаки препинания на Марсе не используют.

По традиции, заголовок статьи должен быть непустой подстрокой её текста. Кроме этого известно, что строчные буквы в заголовке привлекают низкорослых марсиан, а заглавные — высокорослых.

Маркетинговый отдел журнала определил, что оптимальная доля высокорослых читателей (и, следовательно, заглавных букв) составляет M процентов.

Требуется написать программу, которая по данному тексту статьи определит наилучший заголовок — то есть такую подстроку, процент заглавных букв в которой как можно ближе к M.

Если несколько заголовков одинаково подходят, следует выбрать самый короткий, а если и таких несколько — встречающийся в тексте статьи как можно раньше.

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

Первая строка входного файла содержит целое число M.

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

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

Выходной файл должен содержать одну строку — наилучший заголовок.

Ограничения

1 ≤ M ≤ 99

Длина текста составляет от 2 до 5000 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
50
aAb
aA
2
30
xxxxXXxxX
xxxxXXx
3
99
ab
a

0.042s 0.007s 15