Строка t называется красивой, если строка «2017» встречается в t в качестве подпоследовательности, а строка «2016» не встречается в t в качестве подпоследовательности. Например, строки «203434107» и «9220617» являются красивыми, а строки «20016», «1234» и «20167» не являются красивыми.
Уродством строки называется минимальное количество символов, которые надо удалить, чтобы получить красивую строку. Если получить красивую строку удаляя символы невозможно, то её уродство равняется - 1.
У Лимака есть строка s длины n, символы которой пронумерованы от 1 до n. Также у него есть q запросов. В i-м запросе выведите уродство подстроки (непрерывной подпоследовательности) s начинающейся с позиции номер ai и заканчивающейся в позиции номер bi (включительно).
В первой строке входных данных записаны два числа n и q (4 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) — длина строки s и количество запросов соответственно.
Во второй строке записана строка s длины n. Каждый из символов этой строки является цифрой «0»–«9».
В i-й из последующих q строк записаны два целых числа ai и bi (1 ≤ ai ≤ bi ≤ n), описывающих подстроку из i-го запроса.
Для каждого запроса выведите уродство соответствующей подстроки.
Рассмотрим первый пример. Далее запись ugliness(t) означает уродство строки t.
Во втором примере:
8 3 20166766 1 8 1 7 2 8
4 3 -1
15 5 012016662091670 3 4 1 14 4 15 1 13 10 15
-1 2 1 -1 -1
4 2 1234 2 4 1 2
-1 -1
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач