問題描述 Description

我們知道，哈希（hash）算法被廣泛應用于字符串處理領域之中。現有如下哈希函數： f(s,l,r)=∏i?lrord(si)modp $$f(s,l,r)=/<a >PR</a>od_{i-l}^r ord(s_i) /mod p$$ 公式中，ord$ord$代表的是字符的ascii碼，mod$/text{mod}$代表的是求余操作，∏$/prod$則是求積操作，意為求l$l$到r$r$之間所有字符的積。 現在給定一個長度為N$N$的字符串，并給出p$p$，之后會有若干組詢問，每次詢問這個字符串相對于那個區間的子串的哈希值。

輸入 Input

輸入文件包括若干行，其中第一行是一個字符串 ，數據保證其中只會出現小寫英文字母。 第二行是一個整數p$p$。 第三行是一個整數m$m$，表示詢問的次數。 接下來的m$m$行，每行有兩個整數l,r(1≤l≤r≤n)$l,r(1≤l≤r≤n)$，表示詢問從第l$l$位到第r$r$位的哈希值。

輸出 Output

輸出文件包括m$m$行，依次給出輸入文件中相應的詢問對應的答案.

樣例輸入 Sample Input

efqzvcowdormnslhjzznubn 56 4 17 18 7 20 14 16 15 23

樣例輸出 Sample Output

52 0 40 0

限制 Limits

對于30%$30/%$的數據，1≤N≤100，1≤m≤10$1≤N≤100 ，1≤m≤10$； 對于70%$70/%$的數據，1≤N≤105，1≤m≤104$1≤N≤10^5 ，1≤m≤10^4$； 對于100%$100/%$的數據，1≤N≤105，1≤m≤105$1≤N≤10^5 ，1≤m≤10^5$。 Time Limit : 1s$1s$ & Memory Limit : 128MB$128MB$

黑歷史題，只有查詢的線段樹 Code 只有查詢？先求前綴積，再求個逆元，搞一搞就好了…… 但是并不知道p$p$有多大，題中也沒說，題解說可以寫也是一種優化方法吧。 時間O(nlogn+Tlogn)$O(nlogn+Tlogn)$