Digital row
Once upon a time, a boy named Vova, who had just learned to count and write, decided to practice these skills by writing down all natural numbers starting from one in a continuous sequence on a sheet of paper. His older brother, Petya, noticed this infinite sequence of digits, which we'll call S:
Figure №1. Digital sequence.
Petya, who is interested in programming, wanted to explore the properties of this sequence. For any given pair of integers (i, j) where i ≤ j, a substring of the sequence S is defined as the sequence of digits 'S_iS_i_{+1}…S_j'. For instance, the pair (1, 3) corresponds to the substring '123', and the pair (9, 12) corresponds to the substring '9101'.
Figure №2. Examples of substrings.
A pattern is defined as a string T consisting of digits from 0 to 9, and the characters '?' and '*'. A string Q is said to match the pattern T if Q can be derived from T by replacing each '?' with a single digit and each '*' with any sequence of digits, which can also be empty.
Petya's task is to find a substring of the sequence S that matches the given pattern T. For example, the pattern '?1*1' is matched by substrings corresponding to the pairs (9, 12), (9, 13), (9, 14), (9, 16), (11, 13), (11, 14), (11, 16), and so on. Help Petya solve this intriguing challenge!
Figure №3. Description of the second example.
Input
The first line of the input file contains a single natural number N (1 ≤ N ≤ 20) – the length of the string T.
The second line of the input file contains one string T, consisting of N characters from '0' to '9', '?', and '*'.
Output
The output should be a single line containing two integers i and j, separated by a space, where (i, j) is a pair such that the corresponding substring of the sequence S matches the pattern T.
If there are multiple pairs (i, j) that match the pattern T, output the smallest pair. A pair (i_1, j_1) is considered smaller than (i_2, j_2) if i_1 < i_2, or i_1 = i_2 and j_1 < j_2.
If no substring of the sequence S matches the pattern T, output '0 0'.