實力強勁嘅小 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$ | $5\times 10^5$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 無 |
| $5$ | $1000$ | $200$ | $5\times 10^5$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 無 |
| $6$ | $5\times 10^5$ | $1$ | $5\times 10^5$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 無 |
| $7$ | $5\times 10^5$ | $1$ | $5\times 10^5$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 無 |
| $8$ | $10^5$ | $10^5$ | $2\times 10^5$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 無 |
| $9$ | $10^5$ | $10^5$ | $2\times 10^5$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 字串隨機 |
| $10$ | $2\times 10^5$ | $10^5$ | $4\times 10^5$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 無 |
| $11$ | $2\times 10^5$ | $10^5$ | $4\times 10^5$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 字串隨機 |
| $12$ | $3\times 10^5$ | $10^5$ | $6\times 10^5$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 無 |
| $13$ | $3\times 10^5$ | $10^5$ | $6\times 10^5$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 字串隨機 |
| $14$ | $4\times 10^5$ | $10^5$ | $8\times 10^5$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 無 |
| $15$ | $4\times 10^5$ | $10^5$ | $8\times 10^5$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 字串隨機 |
| $16$ | $5\times 10^5$ | $10^5$ | $10^6$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 無 |
| $17$ | $5\times 10^5$ | $10^5$ | $10^6$ | 所有查詢都滿足 $l=1,r=\lvert S\rvert$ | 字串隨機 |
| $18$ | $2\times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $19$ | $3\times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $20$ | $4\times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $21$ | $5\times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $22$ | $5\times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $23$ | $5\times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $24$ | $5\times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
| $25$ | $5\times 10^5$ | $10^5$ | $10^6$ | 無 | 無 |
所有數據都保證 $1\le l\le r\le |S|$，$1\le |T|\le 5\times 10^5$。