Вам даны две строки \(a\) и \(b\) длиной \(n\). Затем вам (против вашей воли) придется ответить на \(q\) запросов.
Для каждого запроса вам дан отрезок, ограниченный позициями \(l\) и \(r\). За одну операцию вы можете выбрать целое число \(i\) (\(l \leq i \leq r\)) и установить \(a_i = x\), где \(x\) — любой символ, который вы захотите. Выведите минимальное количество операций, которые вам нужно выполнить, чтобы \(\texttt{sorted(a[l..r])} = \texttt{sorted(b[l..r])}\). Операции, которые вы выполняете в одном запросе, не влияют на другие запросы.
Для произвольной строки \(c\), \(\texttt{sorted(c[l..r])}\) обозначает подстроку, состоящую из символов \(c_l, c_{l+1}, ... , c_r\), отсортированных в лексикографическом порядке.
Выходные данные
Для каждого запроса выведите целое число, минимальное количество операций, которые вам нужно выполнить, на новой строке.
Примечание
Для первого запроса \(\texttt{sorted(a[1..5])} =\) abcde и \(\texttt{sorted(b[1..5])} =\) abcde, поэтому операции не требуются.
Для второго запроса вам нужно установить \(a_1 = \) e. Тогда \(\texttt{sorted(a[1..4])} = \texttt{sorted(b[1..4])} = \) bcde.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 3
abcde
edcba
1 5
1 4
3 3
4 2
zzde
azbe
1 3
1 4
6 3
uwuwuw
wuwuwu
2 4
1 3
1 6
|
0
1
0
2
2
1
1
0
|