Fun Jumps
Limits: 3 sec., 512 MiB
This statement was translated automatically from Ukrainian.
Zenyk and Marichka are having fun. They have a string \(s\) consisting of Latin alphabet letters, and every day they try to reach one position of this string from another in the minimum number of operations. To do this, they can make one of two types of jumps:
Normal jump: move to the adjacent position on the left or right. If the current position is at the edge of the string, it is of course impossible to jump in that direction.
Fun jump: move to the nearest position on the left or right that contains the same letter as the current position. If there is no such letter in one of the directions, then a fun jump in that direction is not possible.
Zenyk and Marichka are very happy when they manage to make a successful fun jump that significantly reduces the number of operations to reach the goal. However, they believe that excessive happiness is not very good, so they allow themselves at most one fun jump per day.
Given the string \(s\), as well as the starting and ending positions for each day, find the minimum number of operations required to reach the target position using at most one fun jump.
Input
The first line contains the string \(s\).
The second line contains a single integer \(q\) — the number of days.
The next \(q\) lines each contain two space-separated integers \(a_i\), \(b_i\) — the starting and ending positions for the \(i\)-th day.
Output
Output \(q\) lines. In the \(i\)-th of them, output a single integer — the minimum number of operations for the \(i\)-th day.
Constraints
\(2 \le |s| \le 5 \cdot 10^5\),
\(1 \le q \le 5 \cdot 10^5\),
\(1 \le a_i, b_i \le |s|\),
\(a_i \neq b_i\),
\(s\) contains only lowercase Latin letters.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| abdacaba 7 6 1 1 8 5 8 5 3 7 4 7 3 7 2 | 3 3 2 2 2 2 1 |
Notes
The picture shows:
All possible jumps for the string \(s\) from the example.
Optimal jumps for positions \(6\) and \(1\).
Optimal jumps for positions \(7\) and \(3\).
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|