← 返回题目列表

Codeforces · 1860/E

E. 快速旅行文本编辑器

中文机器翻译题面 查看原题

给你一个字符串 $$$s$$$,由小写拉丁字母组成。

有一个光标,最初放置在字符串的两个相邻字母之间。光标不能放置在第一个字母之前或最后一个字母之后。

在一次移动中,您可以执行以下三个操作之一:

- 将光标向左移动一个位置(如果没有将其放置在第一个字母之前);
- 将光标向右移动一个位置(如果没有将其放置在最后一个字母之后);
- 令 $$$x$$$ 为紧邻光标左侧的字母,$$$y$$$ 为紧邻光标右侧的字母。选择字符串中任意一对相邻字母,使其左侧为 $$$x$$$,右侧为 $$$y$$$,并将光标移动到这两个字母之间的位置。

系统会向您询问 $$$m$$$ 个问题。在每个查询中,都会给出两个整数 $$$f$$$ 和 $$$t$$$,它们对应于字符串中光标的两个有效位置。为了响应该查询,您必须计算将光标从位置 $$$f$$$ 移动到位置 $$$t$$$ 所需的最少操作数。

输入

第一行包含一个字符串 $$$s$$$ ($$$2 \le |s| \le 5 \cdot 10^4$$$),由小写拉丁字母组成。

第二行包含一个整数 $$$m$$$ ($$$1 \le m \le 5 \cdot 10^4$$$) — 查询数。

接下来的 $$$m$$$ 行的第 $$$i$$$ 行包含两个整数 $$$f$$$ 和 $$$t$$$ ($$$1 \le f, t \le |s| - 1$$$) — 第 $$$i$$$ 查询中光标的初始位置和目标位置。位置 $$$x$$$ 表示光标位于字符串的第 $$$x$$$ 和第 $$$(x+1)$$$ 个字母之间($$$1$$$ 索引)。

输出

对于每个查询,打印将光标从位置 $$$f$$$ 移动到位置 $$$t$$$ 所需的最少操作数。

示例

输入 #1

codecode
3
1 7
3 5
3 6

输出 #1

3
2
2

输入 #2

abcdefghij
3
1 9
9 1
5 5

输出 #2

8
8
0

输入 #3

aaaaaaaaaaaa
4
10 8
3 7
6 1
11 11

输出 #3

1
1
1
0