Vaxt yoxdur çəkməyə

Bəsi yaxınlarda rəng dəsti alıb və otlaq sahəsinin bir tərəfindəki uzun hasarı boyamaq istəyir. Hasar n ardıcıl 1-metrlik seqmentlərdən ibarətdir. Bəsinin 26 fərqli rəngi var və onları 'A'-dan 'Z'-yə qədər artan tündlük sırasına görə işarələyib ('A' - ən açıq rəng, 'Z' - ən tünd rəng). Beləliklə, o, hasarın boyanmasını n simvoldan ibarət bir sətir kimi təsvir edə bilər (hər bir simvol 'A'-dan 'Z'-yə qədər olan hərflərdən biridir).

Əvvəlcə bütün seqmentlər boyanmamışdır. Bəsi hər hansı bir ardıcıl seqment aralığını bir rənglə bir fırça toxunuşu ilə boyaya bilər, lakin o, heç vaxt açıq rəngi tünd rəngin üzərinə boyamaz (o, tünd rəngi açıq rəngin üzərinə boyaya bilər).

Məsələn, əvvəlcə boyanmamış uzunluğu 4 olan bir seqmenti belə boyaya bilər:

.... -> BBB. -> BBLL -> BQQL

Vaxt məhdudiyyətinə görə, Bəsi bəzi ardıcıl seqmentləri boyanmamış buraxa bilər. İndi o, q namizəd seqmentləri nəzərdən keçirir, hər biri iki tam ədədlə (a, b) (1 ≤ a ≤ b ≤ n) verilmişdir, bu da boyanmamış qalmalı olan seqmentlərin son nöqtələrinin indekslərini göstərir.

Hər bir namizəd üçün, bu aralıqdan kənarda olan bütün seqmentləri istənilən rəngə boyamaq üçün lazım olan minimum toxunuş sayını göstərin, aralıqdakı seqmentləri boyanmamış saxlayın. Qeyd edək ki, Bəsi əslində heç nə boyamır, buna görə hər bir aralıq-namizəd üçün cavablar müstəqildir.

Giriş məlumatları

Birinci sətir n (1 ≤ n ≤ 10^5) və q (1 ≤ q ≤ 10^5) ehtiva edir.

Növbəti sətir hasarın hər bir seqmentinin istənilən rəngini təmsil edən uzunluğu n olan bir sətir ehtiva edir.

Növbəti q sətirin hər biri iki tam ədəd a və b ehtiva edir, bu da boyanmamış qala biləcək seqmentlərin aralığını təmsil edir.

Çıxış məlumatları

Hər bir q namizəd üçün cavabı yeni sətirdə çıxarın.

Nümunə

Bu nümunədə, aralığın istisna edilməsi istənilən nümunəyə uyğundur. Bu nümunədə BAAB aralığının istisna edilməsi boyama üçün dörd toxunuş tələb edir, ABBA aralığının istisna edilməsi isə yalnız üç.

.... -> AA.. -> ABBB -> ABCB