小 A ผู้มีความสามารถสูงได้รับเลือกให้เป็นผู้ออกโจทย์ของ ION2018 และตอนนี้เขาต้องแก้ปัญหาเรื่องการตั้งชื่อโจทย์
คำอธิบาย
小 A ได้รับเลือกให้เป็นผู้ออกโจทย์ของ ION2018 เขาเตรียมโจทย์คุณภาพสูงมากข้อหนึ่งอย่างพิถีพิถัน และทำงานทุกอย่างเสร็จแล้ว ยกเว้นการตั้งชื่อโจทย์
เนื่องจาก ION จัดขึ้นมาหลายครั้งแล้ว จึงมีกฎเกี่ยวกับการตั้งชื่อโจทย์ คู่มือการออกโจทย์ของ ION กำหนดว่า ในแต่ละปีคณะกรรมการออกโจทย์จะกำหนดสตริงอักษรตัวพิมพ์เล็กขึ้นมาหนึ่งสตริง ซึ่งเราเรียกว่าสตริงสำหรับตั้งชื่อของปีนั้น ชื่อของโจทย์แต่ละข้อต้องเป็นสตริงย่อยต่อเนื่องที่ไม่ว่างของสตริงสำหรับตั้งชื่อของปีนั้น และต้องไม่เหมือนกับชื่อโจทย์ข้อใดของปีก่อนหน้า
ด้วยเหตุผลพิเศษบางประการ 小 A ไม่ทราบชื่อโจทย์แต่ละข้อของ ION2017 แต่เขาได้สตริงสำหรับตั้งชื่อของ ION2017 มาด้วยวิธีพิเศษบางอย่าง ตอนนี้ 小 A มีคำถาม $Q$ ข้อ: ในแต่ละคำถาม กำหนดสตริงสำหรับตั้งชื่อของ ION2017 และ ION2018 ให้ จงหาว่ามีวิธีตั้งชื่อโจทย์กี่วิธีที่รับประกันว่าชื่อนั้นเป็นไปตามกฎของคณะกรรมการ กล่าวคือ เป็นสตริงย่อยต่อเนื่องที่ไม่ว่างของสตริงสำหรับตั้งชื่อของ ION2018 และแน่นอนว่าจะไม่เหมือนกับชื่อโจทย์ข้อใดของ ION2017
ด้วยเหตุผลพิเศษบางประการ สตริงสำหรับตั้งชื่อของ ION2017 ที่กำหนดให้ในทุกคำถามล้วนเป็นสตริงย่อยต่อเนื่องของสตริงหนึ่งสตริง ดูรายละเอียดในส่วนข้อมูลนำเข้า
ข้อมูลนำเข้า
บรรทัดแรกเป็นสตริง $S$ โดยสตริงสำหรับตั้งชื่อของ ION2017 ที่กำหนดให้ในคำถามต่อ ๆ ไปทั้งหมดเป็นสตริงย่อยต่อเนื่องของ $S$
บรรทัดที่สองเป็นจำนวนเต็มบวก $Q$ แทนจำนวนคำถาม
จากนั้นมี $Q$ บรรทัด แต่ละบรรทัดประกอบด้วยสตริง $T$ และจำนวนเต็มบวกสองจำนวน $l,r$ ซึ่งถามว่า หากสตริงสำหรับตั้งชื่อของ ION2017 คือ $S[l..r]$ และสตริงสำหรับตั้งชื่อของ ION2018 คือ $T$ จะมีวิธีตั้งชื่อกี่วิธีที่รับประกันว่าเป็นไปตามกฎ
รับประกันว่าสตริงทั้งหมดในข้อมูลนำเข้าประกอบด้วยอักษรตัวพิมพ์เล็ก
ข้อมูลส่งออก
ส่งออก $Q$ บรรทัด โดยบรรทัดที่ $i$ ประกอบด้วยจำนวนเต็มไม่เป็นลบหนึ่งจำนวน แทนคำตอบของคำถามที่ $i$
ตัวอย่าง
ข้อมูลนำเข้า 1
scbamgepe 3 smape 2 7 sbape 3 8 sgepe 1 9
ข้อมูลส่งออก 1
12 10 4
ตัวอย่าง 2
ดู name/name2.in และ name/name2.ans ในไดเรกทอรีของผู้เข้าแข่งขัน
งานย่อย
| กรณีทดสอบ | $\lvert S\rvert\le$ | $Q\le$ | $\sum\lvert T\rvert\le$ | ข้อจำกัดของคำถาม | ข้อจำกัดอื่น ๆ |
|---|---|---|---|---|---|
| $1$ | $200$ | $200$ | $40000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le 200$ |
| $2$ | $1000$ | $200$ | $40000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le 200$ |
| $3$ | $1000$ | $200$ | $40000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le 200$ |
| $4$ | $1000$ | $200$ | $500000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | ไม่มี |
| $5$ | $1000$ | $200$ | $500000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | ไม่มี |
| $6$ | $500000$ | $1$ | $500000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | ไม่มี |
| $7$ | $500000$ | $1$ | $500000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | ไม่มี |
| $8$ | $100000$ | $1$ | $200000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | ไม่มี |
| $9$ | $100000$ | $100000$ | $200000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | สตริงสุ่ม |
| $10$ | $200000$ | $100000$ | $400000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | ไม่มี |
| $11$ | $200000$ | $100000$ | $400000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | สตริงสุ่ม |
| $12$ | $300000$ | $100000$ | $600000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | ไม่มี |
| $13$ | $300000$ | $100000$ | $600000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | สตริงสุ่ม |
| $14$ | $400000$ | $100000$ | $800000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | ไม่มี |
| $15$ | $400000$ | $100000$ | $800000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | สตริงสุ่ม |
| $16$ | $500000$ | $100000$ | $1000000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | ไม่มี |
| $17$ | $500000$ | $100000$ | $1000000$ | สำหรับทุกคำถาม $l=1,r=\lvert S\rvert$ | สตริงสุ่ม |
| $18$ | $200000$ | $100000$ | $1000000$ | ไม่มี | ไม่มี |
| $19$ | $300000$ | $100000$ | $1000000$ | ไม่มี | ไม่มี |
| $20$ | $400000$ | $100000$ | $1000000$ | ไม่มี | ไม่มี |
| $21$ | $500000$ | $100000$ | $1000000$ | ไม่มี | ไม่มี |
| $22$ | $500000$ | $100000$ | $1000000$ | ไม่มี | ไม่มี |
| $23$ | $500000$ | $100000$ | $1000000$ | ไม่มี | ไม่มี |
| $24$ | $500000$ | $100000$ | $1000000$ | ไม่มี | ไม่มี |
| $25$ | $500000$ | $100000$ | $1000000$ | ไม่มี | ไม่มี |
สำหรับข้อมูลทั้งหมด รับประกันว่า $1\le l\le r\le |S|$, $1\le |T|\le 5\times 10^5$