Description

请注意，hard和easy版本的区别在于字符串的长度、询问次数、字符串中的字符类型以及不需要修改时的回答

给定一个长度为 $n$ 的字符串$s$（仅含大小写字母和数字），以及 $q$ 次独立的区间查询。每次查询给出一对整数 $(l, r)$，表示子串
$s_l\,s_{l+1}\,\dots\,s_r.$ 你需要输出让该区间变得可回文的 最少字符修改数量。

我们称一个区间是可回文的当且仅当至少存在一种对该区间内的字符进行重新排列的方法，使该区间重新排列之后是回文串。

每次修改是独立的，即仅针对本次查询，与之后的询问无关。

Format

Input

第一行包含两个整数 $1 \le n, q \le 2*10^6$——字符串长度和查询次数。
第二行是长度为 $n$ 的字符串 $s$，仅由 'a'–'z','A'-'Z','0'-'9' 组成。
接下来 $q$ 行，每行给出一对整数 $(l_i, r_i)$（$1 \le l_i \le r_i \le n$）。

Output

对每个查询 $(l_i,r_i)$，输出最少字符修改数量，若不需要修改，则输出"YES"。

注意，此处的"YES"为全大写字母，没有spj。

Samples

10 5
abacabaaxy
1 7
4 6
1 10
8 10
2 9

YES
1
2
1
1