تلقت Bessie مؤخرًا مجموعة أدوات للرسم، وتريد طلاء السياج الطويل عند أحد أطراف مرعاها. يتكون السياج من $N$ مقاطع متتالية طول كل منها متر واحد ($1\le N\le 10^5$). لدى Bessie 26 لونًا مختلفًا، تسميها بالحروف من 'A' إلى 'Z' بترتيب ازدياد قتامة اللون ('A' لون فاتح جدًا، و'Z' داكن جدًا). لذلك تستطيع وصف اللون المطلوب لكل مقطع بسلسلة طولها $N$، كل محرف فيها حرف.

في البداية، جميع المقاطع بلا لون. تستطيع Bessie تلوين أي نطاق متصل من المقاطع بلون واحد بضربة فرشاة واحدة، بشرط ألا تطلي لونًا أفتح فوق لون أغمق مطلقًا (يمكنها فقط طلاء الألوان الأغمق فوق الألوان الأفتح).

مثلًا، يمكن تلوين مقطع طوله أربعة وبلا لون في البداية كما يلي:

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

مع ضيق الوقت، تعتقد Bessie أنها قد تحتاج إلى ترك نطاق متتالٍ من مقاطع السياج بلا طلاء! تفكر حاليًا في $Q$ نطاقات مرشحة ($1\le Q\le 10^5$)، يصف كلًا منها عددان صحيحان $(a,b)$ بحيث $1 \leq a \leq b \leq N$، يعطيان فهرسي طرفي نطاق المقاطع $a \ldots b$ الذي سيبقى بلا طلاء.

لكل نطاق مرشح، ما أقل عدد من ضربات الفرشاة اللازمة لطلاء كل مقطع خارج النطاق بلونه المطلوب مع إبقاء جميع المقاطع داخله بلا لون؟ لاحظ أن Bessie لا تطلي شيئًا بالفعل أثناء هذه العملية، لذا فإن إجابات النطاقات المرشحة مستقلة.

الإدخال

يحتوي السطر الأول على $N$ و$Q$.

يحتوي السطر التالي على سلسلة طولها $N$ تمثل اللون المطلوب لكل مقطع من السياج.

يحتوي كل سطر من الأسطر $Q$ التالية على عددين صحيحين $a$ و$b$ مفصولين بمسافة، يمثلان نطاقًا مرشحًا قد يبقى بلا طلاء.

الإخراج

لكل مرشح من المرشحين $Q$، أخرج الإجابة في سطر جديد.

أمثلة

الإدخال 1

8 2
ABBAABCB
3 6
1 4

الإخراج 1

4
3

ملاحظة

في هذا المثال، يتطلب استثناء النطاق الفرعي الموافق للنمط المطلوب $\texttt{BAAB}$ أربع ضربات فرشاة للطلاء، بينما يتطلب استثناء $\texttt{ABBA}$ ثلاثًا فقط.

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

المهام الفرعية

• تحقق حالات الاختبار 1–4 الشرط $N,Q\le 100$.
• تحقق حالات الاختبار 5–7 الشرط $N,Q\le 5000$.
• لا توجد قيود إضافية على حالات الاختبار 8–13.

صاحبا المسألة: Andi Qu وBrian Dean