Задана строка $$$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
Название |
---|