小 A yang sangat cakap terpilih menjadi pembuat soal ION2018. Kini dia perlu menyelesaikan masalah penamaan soal.
Deskripsi Soal
小 A terpilih menjadi pembuat soal ION2018. Dia telah menyiapkan dengan saksama sebuah soal berkualitas sangat tinggi dan telah menyelesaikan semua pekerjaan selain memberi nama soal.
Karena ION sudah diselenggarakan berkali-kali, penamaan soal pun memiliki aturan. Buku panduan penyusunan soal ION menetapkan bahwa setiap tahun panitia penyusun soal menentukan sebuah string huruf kecil, yang kita sebut string penamaan tahun tersebut. Nama setiap soal harus merupakan substring berurutan yang tidak kosong dari string penamaan tahun tersebut, dan tidak boleh sama dengan nama soal mana pun pada tahun sebelumnya.
Karena alasan tertentu, 小 A tidak mengetahui nama setiap soal ION2017, tetapi dengan cara-cara khusus dia memperoleh string penamaan ION2017. Sekarang 小 A memiliki $Q$ kueri: untuk setiap kueri diberikan string penamaan ION2017 dan ION2018. Carilah banyaknya cara menamai soal sehingga nama itu pasti memenuhi aturan panitia penyusun soal, yaitu merupakan substring berurutan yang tidak kosong dari string penamaan ION2018 dan pasti tidak sama dengan nama soal mana pun pada ION2017.
Karena alasan tertentu, semua string penamaan ION2017 yang diberikan dalam kueri merupakan substring berurutan dari suatu string. Lihat format masukan untuk perinciannya.
Masukan
Baris pertama berisi sebuah string $S$. Semua string penamaan ION2017 yang diberikan dalam kueri berikutnya merupakan substring berurutan dari $S$.
Baris kedua berisi sebuah bilangan bulat positif $Q$, yang menyatakan banyaknya kueri.
Masing-masing dari $Q$ baris berikutnya berisi sebuah string $T$ dan dua bilangan bulat positif $l,r$. Baris tersebut menanyakan banyaknya cara penamaan yang pasti memenuhi aturan jika string penamaan ION2017 adalah $S[l..r]$ dan string penamaan ION2018 adalah $T$.
Dijamin semua string yang diberikan dalam masukan terdiri atas huruf kecil.
Keluaran
Keluarkan $Q$ baris. Baris ke-$i$ berisi sebuah bilangan bulat nonnegatif yang menyatakan jawaban kueri ke-$i$.
Contoh
Masukan 1
scbamgepe 3 smape 2 7 sbape 3 8 sgepe 1 9
Keluaran 1
12 10 4
Contoh 2
Lihat name/name2.in dan name/name2.ans di direktori peserta.
Subtugas
| Kasus uji | $\lvert S\rvert\le$ | $Q\le$ | $\sum\lvert T\rvert\le$ | Batasan kueri | Batasan lainnya |
|---|---|---|---|---|---|
| 1 | $200$ | $200$ | $40000$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| 2 | $1000$ | $200$ | $40000$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| 3 | $1000$ | $200$ | $40000$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | $\lvert T\rvert\le200$ |
| 4 | $1000$ | $200$ | $5\times10^5$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | Tidak ada |
| 5 | $1000$ | $200$ | $5\times10^5$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | Tidak ada |
| 6 | $5\times10^5$ | $1$ | $5\times10^5$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | Tidak ada |
| 7 | $5\times10^5$ | $1$ | $5\times10^5$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | Tidak ada |
| 8 | $10^5$ | $10^5$ | $2\times10^5$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | Tidak ada |
| 9 | $10^5$ | $10^5$ | $2\times10^5$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | String acak |
| 10 | $2\times10^5$ | $10^5$ | $4\times10^5$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | Tidak ada |
| 11 | $2\times10^5$ | $10^5$ | $4\times10^5$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | String acak |
| 12 | $3\times10^5$ | $10^5$ | $6\times10^5$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | Tidak ada |
| 13 | $3\times10^5$ | $10^5$ | $6\times10^5$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | String acak |
| 14 | $4\times10^5$ | $10^5$ | $8\times10^5$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | Tidak ada |
| 15 | $4\times10^5$ | $10^5$ | $8\times10^5$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | String acak |
| 16 | $5\times10^5$ | $10^5$ | $10^6$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | Tidak ada |
| 17 | $5\times10^5$ | $10^5$ | $10^6$ | Untuk semua kueri, $l=1,r=\lvert S\rvert$ | String acak |
| 18 | $2\times10^5$ | $10^5$ | $10^6$ | Tidak ada | Tidak ada |
| 19 | $3\times10^5$ | $10^5$ | $10^6$ | Tidak ada | Tidak ada |
| 20 | $4\times10^5$ | $10^5$ | $10^6$ | Tidak ada | Tidak ada |
| 21 | $5\times10^5$ | $10^5$ | $10^6$ | Tidak ada | Tidak ada |
| 22 | $5\times10^5$ | $10^5$ | $10^6$ | Tidak ada | Tidak ada |
| 23 | $5\times10^5$ | $10^5$ | $10^6$ | Tidak ada | Tidak ada |
| 24 | $5\times10^5$ | $10^5$ | $10^6$ | Tidak ada | Tidak ada |
| 25 | $5\times10^5$ | $10^5$ | $10^6$ | Tidak ada | Tidak ada |
Untuk semua data, dijamin $1\le l\le r\le\lvert S\rvert$, $1\le\lvert T\rvert\le5\times10^5$.