Цифровая строка
Однажды мальчик Вова, который совсем недавно научился считать и писать, решил объединить эти два умения и выписать на листке бумаги подряд все натуральные числа начиная с единицы. Петя, старший брат Вовы, обратил внимание на получившуюся бесконечную строку символов из цифр S:
Рисунок №1. Цифровая строка.
Так как Петя увлекается программированием, он решил исследовать свойства этой строки. Подстрокой строкиS для заданной пары целых чисел (i, j), i ≤ j, будем называть строку из цифр 'S_iS_i_{+1}…S_j'. Например, паре (1, 3) соответствует подстрока '123', а паре (9, 12) подстрока '9101'.
Рисунок №2. Примеры подстрок.
Шаблоном будем называть строку T, состоящую из цифр от 0 до 9, символов '?' и '*'. Будем говорить, что строка Q удовлетворяет шаблону T, если строку Q можно получить из T заменой каждого символа '?' на одну цифру, а символы '*' на последовательность цифр, возможно пустую.
Пете необходимо для заданного шаблона T найти подстроку строки S, удовлетворяющую заданному шаблону. Например, шаблону '?1*1' удовлетворяют подстроки, соответствующие парам чисел (9, 12), (9, 13), (9, 14), (9,16), (11, 13), (11, 14), (11, 16) и т.д. Помогите Пете в решении этой непростой задачи!
Рисунок №3. Описание второго примера.
Входные данные
Первая строка входного файла содержит одно натуральное число N (1 ≤ N ≤ 20) – длину строки T.
Вторая строка входного файла содержит одну строковую величину T, содержащую N символов '0'-'9', '?' и '*'.
Выходные данные
Первая и единственная строка выходного файла должна содержать два целых числа i и j, разделенных одиночным пробелом, где (i, j) – пара целых чисел, таких, что соответствующая им подстрока строки S удовлетворяет заданному шаблону T.
Если существует несколько пар целых чисел (i, j), таких, что соответствующие им подстроки удовлетворяют шаблону T, то необходимо вывести наименьшую пару. Будем считать, что пара (i_1, j_1) меньше пары (i_2, j_2), если i_1<i_{2 }либо i_1= i_2 и j_1< j_{2.}
Если не существует подстроки строки S, удовлетворяющей заданному шаблону T, то выведите '0 0'.