Задана строка \(s\), состоящая из строчных латинских букв.
Курсор изначально находится между двумя соседними буквами строки. Курсор не может стоять до первой или после последней буквы.
Вы можете совершить любое количество действий с курсором (возможно, ноль). Каждое действие должно быть одного из трех типов:
Вы должны обработать \(m\) запросов. В каждом запросе задаются два целых числа \(f\) и \(t\), описывающих корректные позиции курсора в строке; в качестве ответа на запрос вы должны вывести минимальное количество действий, требуемое, чтобы переместить курсор из позиции \(f\) в позицию \(t\).
В первой строке записана строка \(s\) (\(2 \le |s| \le 5 \cdot 10^4\)), состоящая из строчных латинских букв.
Во второй строке записано одно целое число \(m\) (\(1 \le m \le 5 \cdot 10^4\)) — количество запросов.
В \(i\)-й из следующих \(m\) строк записаны два целых числа \(f\) и \(t\) (\(1 \le f, t \le |s| - 1\)) — начальная и конечная позиции курсора в \(i\)-м запросе. Позиция \(x\) означает, что курсор находится между \(x\)-й и \((x+1)\)-й буквами строки (в \(1\)-индексации).
На каждый запрос выведите одно целое число — минимальное количество действий, необходимое, чтобы передвинуть курсор из позиции \(f\) в позицию \(t\).
codecode 3 1 7 3 5 3 6
3 2 2
abcdefghij 3 1 9 9 1 5 5
8 8 0
aaaaaaaaaaaa 4 10 8 3 7 6 1 11 11
1 1 1 0
5000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач