Цифровий рядок#3029

Цифровий рядок

3 секунди

256 мегабайтів

Дуже складна

Жив-був хлопчик на ім'я Вова, який щойно навчився рахувати і писати, і вирішив потренувати ці навички, записуючи всі натуральні числа починаючи з одиниці у безперервній послідовності на аркуші паперу. Його старший брат Петя помітив цю нескінченну послідовність цифр, яку ми назвемо $S$ :

Рисунок №1. Цифрова послідовність.

Петя, якому цікаве програмування, захотів дослідити властивості цієї послідовності. Для будь-якої даної пари цілих чисел $(i, j)$ , де $i \leq j$ i \leq j, підрядком послідовності $S$ називається послідовність цифр $S_{i} S_{i + 1} \dots S_{j}$ S_i S_{i+1} \dots S_j. Наприклад, парі $(1, 3)$ відповідає підрядок $123$ , а парі $(9, 12)$ — підрядок $9101$ .

Рисунок №2. Приклади підрядків.

Взірцем (шаблоном) визначається рядок $T$ , що складається з цифр від $0$ до $9$ , а також символів $?$ і $*$ . Рядок $Q$ вважається таким, що відповідає взірцю $T$ , якщо $Q$ можна отримати з $T$ , замінивши кожен $?$ на одну цифру, а кожен $*$ — на будь-яку (можливо, порожню) послідовність цифр.

Завдання Петі — знайти підрядок послідовності $S$ , який відповідає заданому шаблону $T$ . Наприклад, шаблону $? 1 * 1$ ?1*1 відповідають підрядки, що відповідають парам $(9, 12)$ , $(9, 13)$ , $(9, 14)$ , $(9, 16)$ , $(11, 13)$ , $(11, 14)$ , $(11, 16)$ і так далі. Допоможіть Петі розв'язати цю цікаву задачу!

Рисунок №3. Опис другого прикладу.

Вхідні дані

У першому рядку вхідного файлу міститься одне натуральне число $N$ ( $1 \leq N \leq 20$ 1 \leq N \leq 20) — довжина рядка $T$ .

У другому рядку вхідного файлу знаходиться рядок $T$ , що складається з $N$ символів: цифри від $0$ до $9$ , $?$ та $*$ .

Вихідні дані

У вихідний файл слід вивести в одному рядку два цілих числа $i$ і $j$ , розділені пробілом, де $(i, j)$ — пара така, що відповідний підрядок послідовності $S$ відповідає шаблону $T$ .

Якщо є кілька пар $(i, j)$ , що підходять під шаблон $T$ , виведіть найменшу пару. Вважається, що пара $(i_{1}, j_{1})$ (i_1, j_1) менша за $(i_{2}, j_{2})$ (i_2, j_2), якщо $i_{1} < i_{2}$ i_1 < i_2 або $i_{1} = i_{2}$ i_1 = i_2 та $j_{1} < j_{2}$ j_1 < j_2.

Якщо жоден із підрядків послідовності $S$ не задовольняє шаблон $T$ , виведіть 0 0.

Приклади

Приклад 1