小 Y طالب جامعي يدرس مؤخرا مسائل تتعلق بالسلاسل النصية.
تعرف 小 Y إلى التعريفات التالية المتعلقة بالسلاسل النصية:
- لسلسلة $s[1:n]$ طولها $n$، نعرف السلسلة الجزئية $s[l:r]$، حيث $1\le l\le r\le n$، بأنها السلسلة الجديدة الناتجة عن اختيار $s[l],s[l+1],\ldots,s[r]$ ووصلها بالترتيب.
- لسلسلة $s[1:n]$ طولها $n$، نعرف ناتج عكسها $R(s)$ بأنه وصل $s[n],s[n-1],\ldots,s[1]$ بالترتيب، أي السلسلة الناتجة عن وصل المحارف بترتيب معكوس.
- لسلسلتين $a[1:n],b[1:n]$ طول كل منهما $n$، نعرف أن $a$ أصغر معجميا من $b$ إذا وفقط إذا وجد $1\le i\le n$ بحيث يكون $a[j]=b[j]$ لكل $1\le j<i$، ويكون $a[i]<b[i]$.
بعد التعرف إلى هذه التعريفات، فكر 小 Y في المسألة التالية:
تعطى سلسلة $s[1:n]$ طولها $n$. يوجد $q$ استعلاما، يعطي كل منها معاملين $i,r$. عليك إيجاد عدد قيم $l$ التي تحقق الشروط التالية:
- $1\le l\le r$.
- تكون $s[i:i+l-1]$ أصغر معجميا من $R(s[i+l:i+2l-1])$.
يريد 小 Y مساعدتك في حل هذه المسألة.
الإدخال
اقرأ البيانات من الملف string.in.
تتضمن هذه المسألة عدة حالات اختبار.
يحتوي السطر الأول من الإدخال على عددين صحيحين $c,t$ يمثلان رقم حالة التقييم وعدد حالات الاختبار على الترتيب. تعني $c=0$ أن حالة التقييم مثال.
تلي ذلك حالات الاختبار بالترتيب. ولكل حالة اختبار:
يحتوي السطر الأول على عددين صحيحين موجبين $n,q$ يمثلان طول السلسلة وعدد الاستعلامات.
يحتوي السطر الثاني على سلسلة $s$ طولها $n$ تتكون من أحرف صغيرة فقط.
تحتوي الأسطر $q$ التالية على عددين صحيحين موجبين $i,r$ في كل سطر، يمثلان استعلاما واحدا. يضمن أن $i+2r-1\le n$.
الإخراج
اكتب الإخراج في الملف string.out.
لكل استعلام في كل حالة اختبار، أخرج سطرا يحتوي على عدد صحيح يمثل عدد قيم $l$ التي تحقق الشروط.
أمثلة
الإدخال 1
0 2 9 3 abacababa 1 4 2 4 3 3 9 3 abaabaaba 1 4 2 4 3 3
الإخراج 1
4 0 3 2 0 2
ملاحظة
للاستعلام الأول في حالة الاختبار الأولى:
- عندما $l=1$، تكون $s[i:i+l-1]=\mathrm{a}$ و$R(s[i+l:i+l+l-1])=\mathrm{b}$.
- عندما $l=2$، تكون $s[i:i+l-1]=\mathrm{ab}$ و$R(s[i+l:i+l+l-1])=\mathrm{ca}$.
- عندما $l=3$، تكون $s[i:i+l-1]=\mathrm{aba}$ و$R(s[i+l:i+l+l-1])=\mathrm{bac}$.
- عندما $l=4$، تكون $s[i:i+l-1]=\mathrm{abac}$ و$R(s[i+l:i+l+l-1])=\mathrm{baba}$.
في الحالات الأربع كلها، تكون $s[i:i+l-1]$ أصغر معجميا من $R(s[i+l:i+2l-1])$، ولذلك تكون الإجابة $4$.
أمثلة 2
انظر string/string2.in وstring/string2.ans في دليل المتسابق.
يستوفي نطاق بيانات هذا المثال قيود حالة التقييم $5$.
أمثلة 3
انظر string/string3.in وstring/string3.ans في دليل المتسابق.
أمثلة 4
انظر string/string4.in وstring/string4.ans في دليل المتسابق.
يستوفي نطاق بيانات هذا المثال قيود حالتي التقييم $24\sim25$.
القيود
يضمن لجميع بيانات الاختبار أن $1\le t\le5$ و$1\le n\le10^5$ و$1\le q\le10^5$ و$1\le i+2r-1\le n$، وأن السلسلة $s$ تتكون من أحرف صغيرة فقط.
| رقم حالة التقييم | $n$ | $q$ | الخصائص الخاصة |
|---|---|---|---|
| $1$ | $\le 5$ | $\le 5$ | A |
| $2$ | $\le 10$ | $\le 10$ | A |
| $3$ | $\le 20$ | $\le 20$ | A |
| $4$ | $\le 50$ | $\le 50$ | A |
| $5$ | $\le 10^2$ | $\le 10^2$ | A |
| $6$ | $\le 10^3$ | $\le 10^3$ | لا توجد |
| $7$ | $\le 2000$ | $\le 2000$ | لا توجد |
| $8$ | $\le 3000$ | $\le 3000$ | لا توجد |
| $9$ | $\le 4000$ | $\le 4000$ | لا توجد |
| $10$ | $\le 23333$ | $\le 23333$ | A |
| $11$ | $\le 5\times10^4$ | $\le 5\times10^4$ | A |
| $12$ | $\le 75000$ | $\le 75000$ | A |
| $13$ | $\le 9\times10^4$ | $\le 9\times10^4$ | A |
| $14$ | $\le 10^5$ | $\le 10^5$ | A |
| $15$ | $\le 23333$ | $\le 23333$ | B |
| $16$ | $\le 75000$ | $\le 75000$ | B |
| $17$ | $\le 9\times10^4$ | $\le 9\times10^4$ | B |
| $18$ | $\le 10^5$ | $\le 10^5$ | B |
| $19$ | $\le 23333$ | $\le 23333$ | لا توجد |
| $20$ | $\le 5\times10^4$ | $\le 5\times10^4$ | لا توجد |
| $21$ | $\le 75000$ | $\le 75000$ | لا توجد |
| $22$ | $\le 9\times10^4$ | $\le 9\times10^4$ | لا توجد |
| $23$ | $\le 95000$ | $\le 95000$ | لا توجد |
| $24$ | $\le 10^5$ | $\le 10^5$ | لا توجد |
| $25$ | $\le 10^5$ | $\le 10^5$ | لا توجد |
- الخاصية الخاصة A: يضمن أن السلسلة لا تحتوي إلا على المحرفين
aوb، ويختار كل محرف منهما بصورة مستقلة وباحتمالين متساويين. - الخاصية الخاصة B: يضمن أن كل محرفين متجاورين في السلسلة مختلفان.