310617: CF1860E. Fast Travel Text Editor

E. Fast Travel Text Editortime limit per test5 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You are given a string $s$, consisting of lowercase Latin letters.

There's a cursor, initially placed between two adjacent letters of the string. The cursor can't be placed before the first or after the last letter.

In one move, you can perform one of three actions:

• move a cursor one position to the left (if that doesn't place it before the first letter);
• move a cursor one position to the right (if that doesn't place it after the last letter);
• let $x$ be the letter immediately to the left of the cursor, and $y$ be the letter immediately to the right of the cursor. Choose any pair of adjacent letters in the string such that the left of them is $x$ and the right of them is $y$, and move the cursor to the position between these two letters.

You are asked $m$ queries. In each query, you are given two integers $f$ and $t$, which correspond to two valid positions of the cursor in the string. In response to the query, you have to calculate the minimum number of operations required to move the cursor from position $f$ to position $t$.

Input

The first line contains a string $s$ ($2 \le |s| \le 5 \cdot 10^4$), consisting of lowercase Latin letters.

The second line contains a single integer $m$ ($1 \le m \le 5 \cdot 10^4$) — the number of queries.

The $i$-th of the next $m$ lines contains two integers $f$ and $t$ ($1 \le f, t \le |s| - 1$) — the initial and the target positions of the cursor in the $i$-th query. Position $x$ means that the cursor is between the $x$-th and the $(x+1)$-st letters of the string ($1$-indexed).

Output

For each query, print the minimum number of actions required to move the cursor from position $f$ to position $t$.

ExamplesInput

codecode
3
1 7
3 5
3 6

Output

3
2
2

Input

abcdefghij
3
1 9
9 1
5 5

Output

8
8
0

Input

aaaaaaaaaaaa
4
10 8
3 7
6 1
11 11

Output

1
1
1
0

题目大意：
你有一个由小写拉丁字母组成的字符串 s。有一个光标，最初放在字符串相邻的两个字母之间。光标不能放在第一个字母之前或最后一个字母之后。每次操作你可以执行以下三种动作之一：将光标向左移动一个位置（如果不会移动到第一个字母之前）；将光标向右移动一个位置（如果不会移动到最后一个字母之后）；让 x 成为光标左侧的字母，y 成为光标右侧的字母。在字符串中选择任意一对相邻的字母，使得左边的字母是 x，右边的字母是 y，并将光标移动到这两个字母之间。你将得到 m 个查询。每个查询给你两个整数 f 和 t，它们对应字符串中的两个有效的光标位置。对于每个查询，计算将光标从位置 f 移动到位置 t 所需的最小操作数。

输入数据格式：
第一行包含一个字符串 s（2 ≤ |s| ≤ 5 × 10^4），由小写拉丁字母组成。
第二行包含一个整数 m（1 ≤ m ≤ 5 × 10^4）——查询的数量。
接下来 m 行，每行包含两个整数 f 和 t（1 ≤ f, t ≤ |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
```

注意：由于这是一个翻译的题目描述，所以所有的 LaTeX 格式公式在这里都是用文本形式表示的。题目大意： 你有一个由小写拉丁字母组成的字符串 s。有一个光标，最初放在字符串相邻的两个字母之间。光标不能放在第一个字母之前或最后一个字母之后。每次操作你可以执行以下三种动作之一：将光标向左移动一个位置（如果不会移动到第一个字母之前）；将光标向右移动一个位置（如果不会移动到最后一个字母之后）；让 x 成为光标左侧的字母，y 成为光标右侧的字母。在字符串中选择任意一对相邻的字母，使得左边的字母是 x，右边的字母是 y，并将光标移动到这两个字母之间。你将得到 m 个查询。每个查询给你两个整数 f 和 t，它们对应字符串中的两个有效的光标位置。对于每个查询，计算将光标从位置 f 移动到位置 t 所需的最小操作数。 输入数据格式： 第一行包含一个字符串 s（2 ≤ |s| ≤ 5 × 10^4），由小写拉丁字母组成。 第二行包含一个整数 m（1 ≤ m ≤ 5 × 10^4）——查询的数量。 接下来 m 行，每行包含两个整数 f 和 t（1 ≤ f, t ≤ |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 ``` 注意：由于这是一个翻译的题目描述，所以所有的 LaTeX 格式公式在这里都是用文本形式表示的。