給定一個長度為 n 的字串 s=s1s2…sn,請你回答 q 筆詢問。
對於每筆詢問 l,r,請輸出字串 s[l…r] 中有幾個子字串為回文。換句話說,請找到有幾組 (i,j) 滿足 l≤i≤j≤r 且 s[i…j] 為回文。
定義字串 s[i,j]=sisi+1…sj。
定義字串 s[i,j] 為 s[l,r] 的子字串若且唯若 l≤i≤j≤r。
定義長度為 m 的字串 t 為回文若且唯若 t=t1t2…tm=tmtm−1…t1。
輸入第一行共有兩個整數 n,q,變數意義與題目敘述相同。
輸入第二行有一個字串 s。
接下來 q 行,每行有兩個整數 l,r,代表該次詢問的範圍。
輸出 q 行,每行代表該次詢問的答案。