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$ ซึ่งสำหรับทุก $1\le j<i$ มี $a[j]=b[j]$ และมี $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]=\mathtt{a}$ และ $R(s[i+l:i+l+l-1])=\mathtt{b}$
- เมื่อ $l=2$ มี $s[i:i+l-1]=\mathtt{ab}$ และ $R(s[i+l:i+l+l-1])=\mathtt{ca}$
- เมื่อ $l=3$ มี $s[i:i+l-1]=\mathtt{aba}$ และ $R(s[i+l:i+l+l-1])=\mathtt{bac}$
- เมื่อ $l=4$ มี $s[i:i+l-1]=\mathtt{abac}$ และ $R(s[i+l:i+l+l-1])=\mathtt{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\sim 25$
ข้อจำกัด
สำหรับข้อมูลทดสอบทั้งหมด รับประกันว่า $1\le t\le 5,1\le n\le 10^5,1\le q\le 10^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\times 10^4$ | $\le 5\times 10^4$ | A |
| 12 | $\le 75000$ | $\le 75000$ | A |
| 13 | $\le 9\times 10^4$ | $\le 9\times 10^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\times 10^4$ | $\le 9\times 10^4$ | B |
| 18 | $\le 10^5$ | $\le 10^5$ | B |
| 19 | $\le 23333$ | $\le 23333$ | ไม่มี |
| 20 | $\le 5\times 10^4$ | $\le 5\times 10^4$ | ไม่มี |
| 21 | $\le 75000$ | $\le 75000$ | ไม่มี |
| 22 | $\le 9\times 10^4$ | $\le 9\times 10^4$ | ไม่มี |
| 23 | $\le 95000$ | $\le 95000$ | ไม่มี |
| 24 | $\le 10^5$ | $\le 10^5$ | ไม่มี |
| 25 | $\le 10^5$ | $\le 10^5$ | ไม่มี |
- คุณสมบัติพิเศษ A: รับประกันว่าสตริงมีเฉพาะอักขระ
aและbโดยแต่ละอักขระเลือกจากaกับbอย่างอิสระและมีโอกาสเท่ากัน - คุณสมบัติพิเศษ B: รับประกันว่าอักขระที่อยู่ติดกันในสตริงแตกต่างกันเสมอ