小 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 בתיקיית המתחרה.
תתי־משימות
| מקרה בדיקה | $\lvert S\rvert\le$ | $Q\le$ | $\sum \lvert T\rvert\le$ | מגבלות על השאילתות | מגבלות נוספות |
|---|---|---|---|---|---|
| $1$ | $200$ | $200$ | $40000$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| $2$ | $1000$ | $200$ | $40000$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| $3$ | $1000$ | $200$ | $40000$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| $4$ | $1000$ | $200$ | $5\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | אין |
| $5$ | $1000$ | $200$ | $5\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | אין |
| $6$ | $5\times10^5$ | $1$ | $5\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | אין |
| $7$ | $5\times10^5$ | $1$ | $5\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | אין |
| $8$ | $10^5$ | $10^5$ | $2\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | אין |
| $9$ | $10^5$ | $10^5$ | $2\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | המחרוזות אקראיות |
| $10$ | $2\times10^5$ | $10^5$ | $4\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | אין |
| $11$ | $2\times10^5$ | $10^5$ | $4\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | המחרוזות אקראיות |
| $12$ | $3\times10^5$ | $10^5$ | $6\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | אין |
| $13$ | $3\times10^5$ | $10^5$ | $6\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | המחרוזות אקראיות |
| $14$ | $4\times10^5$ | $10^5$ | $8\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | אין |
| $15$ | $4\times10^5$ | $10^5$ | $8\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | המחרוזות אקראיות |
| $16$ | $5\times10^5$ | $10^5$ | $8\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | אין |
| $17$ | $5\times10^5$ | $10^5$ | $8\times10^5$ | בכל השאילתות $l=1,r=\lvert S\rvert$ | המחרוזות אקראיות |
| $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 \lvert S\rvert$ ו־$1\le \lvert T\rvert\le5\times10^5$.