Der leistungsstarke 小 A wurde als Aufgabenautor für die ION2018 ausgewählt. Nun muss er das Problem lösen, seiner Aufgabe einen Namen zu geben.
小 A wurde als Aufgabenautor für die ION2018 ausgewählt. Er hat sorgfältig eine Aufgabe von sehr hoher Qualität vorbereitet und bereits alle Arbeiten außer der Namensgebung abgeschlossen.
Da die ION schon viele Male stattgefunden hat, gibt es auch Regeln für die Aufgabennamen. Das Handbuch für Aufgabenautoren der ION schreibt vor: Jedes Jahr legt das Aufgabenkomitee eine Zeichenkette aus Kleinbuchstaben fest, die wir die Namenszeichenkette dieses Jahres nennen. Der Name jeder Aufgabe muss eine nichtleere zusammenhängende Teilzeichenkette der Namenszeichenkette dieses Jahres sein und darf mit keinem Aufgabennamen des Vorjahres übereinstimmen.
Aus bestimmten besonderen Gründen kennt 小 A die Namen der einzelnen Aufgaben der ION2017 nicht. Mit besonderen Mitteln hat er jedoch die Namenszeichenkette der ION2017 erhalten. Nun hat 小 A $Q$ Anfragen: Für jede Anfrage sind die Namenszeichenketten der ION2017 und der ION2018 gegeben. Gesucht ist die Anzahl verschiedener Aufgabennamen, die die Regeln des Aufgabenkomitees mit Sicherheit erfüllen, also nichtleere zusammenhängende Teilzeichenketten der Namenszeichenkette der ION2018 sind und mit Sicherheit mit keinem Aufgabennamen der ION2017 übereinstimmen.
Aus bestimmten besonderen Gründen sind alle in den Anfragen angegebenen Namenszeichenketten der ION2017 zusammenhängende Teilzeichenketten einer bestimmten Zeichenkette. Einzelheiten stehen im Abschnitt Eingabe.
Eingabe
Die erste Zeile enthält eine Zeichenkette $S$. Alle in den folgenden Anfragen angegebenen Namenszeichenketten der ION2017 sind zusammenhängende Teilzeichenketten von $S$.
Die zweite Zeile enthält eine positive ganze Zahl $Q$, die Anzahl der Anfragen.
Die nächsten $Q$ Zeilen enthalten jeweils eine Zeichenkette $T$ und zwei positive ganze Zahlen $l,r$. Die Anfrage lautet: Wie viele Namen erfüllen mit Sicherheit die Regeln, wenn die Namenszeichenkette der ION2017 $S[l..r]$ und die der ION2018 $T$ ist?
Es ist garantiert, dass alle eingegebenen Zeichenketten nur aus Kleinbuchstaben bestehen.
Ausgabe
Gib $Q$ Zeilen aus. Die $i$-te Zeile enthält eine nichtnegative ganze Zahl, die Antwort auf die $i$-te Anfrage.
Beispiele
Eingabe 1
scbamgepe 3 smape 2 7 sbape 3 8 sgepe 1 9
Ausgabe 1
12 10 4
Beispiel 2
Siehe name/name2.in und name/name2.ans im Teilnehmerverzeichnis.
Teilaufgaben
| Testpunkt | $\lvert S\rvert\le$ | $Q\le$ | $\sum\lvert T\rvert\le$ | Einschränkung der Anfragen | Weitere Einschränkungen |
|---|---|---|---|---|---|
| 1 | $200$ | $200$ | $40000$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| 2 | $1000$ | $200$ | $40000$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| 3 | $1000$ | $200$ | $40000$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| 4 | $1000$ | $200$ | $5\cdot10^5$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Keine |
| 5 | $1000$ | $200$ | $5\cdot10^5$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Keine |
| 6 | $5\cdot10^5$ | $1$ | $5\cdot10^5$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Keine |
| 7 | $5\cdot10^5$ | $1$ | $5\cdot10^5$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Keine |
| 8 | $10^5$ | $10^5$ | $2\cdot10^5$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Keine |
| 9 | $10^5$ | $10^5$ | $2\cdot10^5$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Zufällige Zeichenketten |
| 10 | $2\cdot10^5$ | $10^5$ | $4\cdot10^5$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Keine |
| 11 | $2\cdot10^5$ | $10^5$ | $4\cdot10^5$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Zufällige Zeichenketten |
| 12 | $3\cdot10^5$ | $10^5$ | $6\cdot10^5$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Keine |
| 13 | $3\cdot10^5$ | $10^5$ | $6\cdot10^5$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Zufällige Zeichenketten |
| 14 | $4\cdot10^5$ | $10^5$ | $8\cdot10^5$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Keine |
| 15 | $4\cdot10^5$ | $10^5$ | $8\cdot10^5$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Zufällige Zeichenketten |
| 16 | $5\cdot10^5$ | $10^5$ | $10^6$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Keine |
| 17 | $5\cdot10^5$ | $10^5$ | $10^6$ | Für alle Anfragen gilt $l=1,r=\lvert S\rvert$ | Zufällige Zeichenketten |
| 18 | $2\cdot10^5$ | $10^5$ | $10^6$ | Keine | Keine |
| 19 | $3\cdot10^5$ | $10^5$ | $10^6$ | Keine | Keine |
| 20 | $4\cdot10^5$ | $10^5$ | $10^6$ | Keine | Keine |
| 21 | $5\cdot10^5$ | $10^5$ | $10^6$ | Keine | Keine |
| 22 | $5\cdot10^5$ | $10^5$ | $10^6$ | Keine | Keine |
| 23 | $5\cdot10^5$ | $10^5$ | $10^6$ | Keine | Keine |
| 24 | $5\cdot10^5$ | $10^5$ | $10^6$ | Keine | Keine |
| 25 | $5\cdot10^5$ | $10^5$ | $10^6$ | Keine | Keine |
Für alle Daten gilt $1\le l\le r\le\lvert S\rvert$ und $1\le\lvert T\rvert\le5\cdot10^5$.