给你一个字符串 $$$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