Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

String Sorting

By Arghya · Limits 2s, 512 MB

You'll be given a string $s = s_1s_2.....s_n$ of length $n$ consisting of lowercase english letters and $q$ queries. In each query you'll be given two integers $l$ and $r$, you've to report the minimum number of operations you need to make in order to sort the substring $s_ls_{l+1}.....s_r$. In one operation you can take two adjacent indices and swap the characters.

Input

First line of input contains the string $s (1≤|s|≤10^6)$
Second line of input contains the number of queries $q (1≤q≤10^6)$.
Next $q$ lines contain two integer $l, r (1≤l≤r≤|s|)$ .

Output

For each query output one integer, the minimum number of operations you need to make.

Sample

InputOutput
bcab
3
1 2
2 3
1 4

0
1
3


Note that, you just have to answer how many operation it takes to sort the substring, you are not making any operation in the string. So the original string doesn't change over queries.

Statistics

0% Solution Ratio