اختير 小 A الماهر جدًا ليكون واضع مسائل ION2018، وعليه الآن حل مشكلة تسمية المسائل.
وصف المسألة
اختير 小 A ليكون واضع مسائل ION2018. وقد أعد بعناية مسألة ذات جودة عالية جدًا، وأنجز كل العمل المتعلق بها عدا تسميتها.
ولأن ION أُقيمت مرات عديدة، توجد قواعد لتسمية المسائل أيضًا. ينص دليل وضع مسائل ION على أن لجنة إعداد المسائل تحدد كل عام سلسلة من الأحرف الصغيرة نسميها سلسلة التسمية لذلك العام. يجب أن يكون اسم كل مسألة سلسلة جزئية متصلة غير فارغة من سلسلة التسمية لذلك العام، وألا يطابق اسم أي مسألة من العام السابق.
لأسباب خاصة، لا يعرف 小 A أسماء مسائل ION2017، لكنه حصل بوسائل خاصة على سلسلة التسمية الخاصة بـ ION2017. ولديه الآن $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 في مجلد المتسابق.
المهام الفرعية
| حالة الاختبار | $|S|\le$ | $Q\le$ | $\sum |T|\le$ | قيود الاستعلامات | قيود أخرى |
|---|---|---|---|---|---|
| $1$ | $200$ | $200$ | $40000$ | لكل الاستعلامات، $l=1,r=|S|$ | $|T|\le200$ |
| $2$ | $1000$ | $200$ | $40000$ | لكل الاستعلامات، $l=1,r=|S|$ | $|T|\le200$ |
| $3$ | $1000$ | $200$ | $40000$ | لكل الاستعلامات، $l=1,r=|S|$ | $|T|\le200$ |
| $4$ | $1000$ | $200$ | $5\times10^5$ | لكل الاستعلامات، $l=1,r=|S|$ | لا توجد |
| $5$ | $1000$ | $200$ | $5\times10^5$ | لكل الاستعلامات، $l=1,r=|S|$ | لا توجد |
| $6$ | $5\times10^5$ | $1$ | $5\times10^5$ | لكل الاستعلامات، $l=1,r=|S|$ | لا توجد |
| $7$ | $5\times10^5$ | $1$ | $5\times10^5$ | لكل الاستعلامات، $l=1,r=|S|$ | لا توجد |
| $8$ | $10^5$ | $10^5$ | $2\times10^5$ | لكل الاستعلامات، $l=1,r=|S|$ | لا توجد |
| $9$ | $10^5$ | $10^5$ | $2\times10^5$ | لكل الاستعلامات، $l=1,r=|S|$ | سلاسل عشوائية |
| $10$ | $2\times10^5$ | $10^5$ | $4\times10^5$ | لكل الاستعلامات، $l=1,r=|S|$ | لا توجد |
| $11$ | $2\times10^5$ | $10^5$ | $4\times10^5$ | لكل الاستعلامات، $l=1,r=|S|$ | سلاسل عشوائية |
| $12$ | $3\times10^5$ | $10^5$ | $6\times10^5$ | لكل الاستعلامات، $l=1,r=|S|$ | لا توجد |
| $13$ | $3\times10^5$ | $10^5$ | $6\times10^5$ | لكل الاستعلامات، $l=1,r=|S|$ | سلاسل عشوائية |
| $14$ | $4\times10^5$ | $10^5$ | $8\times10^5$ | لكل الاستعلامات، $l=1,r=|S|$ | لا توجد |
| $15$ | $4\times10^5$ | $10^5$ | $8\times10^5$ | لكل الاستعلامات، $l=1,r=|S|$ | سلاسل عشوائية |
| $16$ | $5\times10^5$ | $10^5$ | $10^6$ | لكل الاستعلامات، $l=1,r=|S|$ | لا توجد |
| $17$ | $5\times10^5$ | $10^5$ | $10^6$ | لكل الاستعلامات، $l=1,r=|S|$ | سلاسل عشوائية |
| $18$ | $2\times10^5$ | $10^5$ | $10^6$ | لا توجد | لا توجد |
| $19$ | $3\times10^5$ | $10^5$ | $10^6$ | لا توجد | لا توجد |
| $20$ | $4\times10^5$ | $10^5$ | $10^6$ | لا توجد | لا توجد |
| $21$ | $5\times10^5$ | $10^5$ | $10^6$ | لا توجد | لا توجد |
| $22$ | $5\times10^5$ | $10^5$ | $10^6$ | لا توجد | لا توجد |
| $23$ | $5\times10^5$ | $10^5$ | $10^6$ | لا توجد | لا توجد |
| $24$ | $5\times10^5$ | $10^5$ | $10^6$ | لا توجد | لا توجد |
| $25$ | $5\times10^5$ | $10^5$ | $10^6$ | لا توجد | لا توجد |
لجميع البيانات، يُضمن أن $1\le l\le r\le|S|$ و$1\le|T|\le5\times10^5$.