在塔的底部，你看到了一扇門，這是距你獲得自由的最后一道屏障了。當(dāng)然，打開(kāi)這扇門是需要密碼的，密碼可抽象為一個(gè)只包含小寫字母的字符串。你并不知道密碼具體是多少，但通過(guò)某種方式得到了生成密碼的模版串s，并且知道密碼一定是模板串的一個(gè)子串。你會(huì)嘗試若干次，每次將得到一個(gè)字符串 t 和一段區(qū)間 [l,r]，你會(huì)從選出 t 的一個(gè)子串去和 sl...r 匹配，定義兩個(gè)字符串的匹配度為兩個(gè)字符串的最長(zhǎng)公共后綴長(zhǎng)度 (最大的 x 使得兩個(gè)串的后 x位相同)。你準(zhǔn)備隨機(jī)選出 t 的一個(gè)子串和 s 的這段區(qū)間匹配，并想知道匹配度的期望是多少，為了防止浮點(diǎn)誤差，只需求出所有方案的匹配度的和即可。有時(shí)，你會(huì)發(fā)現(xiàn)你求的模板串出現(xiàn)了一些問(wèn)題，需要對(duì)其中的一位進(jìn)行修改，這個(gè)修改將會(huì)應(yīng)用到以后的嘗試上。更形式化地說(shuō)，你需要維護(hù)以下兩個(gè)操作：
? 1 x c，表示將 sx (即 s 的第 x 個(gè)字符) 修改為字符 c，保證 c 是小寫字母；
? 2 t l r，表示給出一個(gè)字符串 t，求 t 的所有子串和 sl...r 的匹配度之和，匹配度的定義見(jiàn)上。
你決定玩一玩這個(gè)無(wú)聊的游戲，畢竟閑著也是閑著。
輸入格式
輸入的第一行包含一個(gè)只包含小寫字母的字符串 s，表示生成密碼的模板。
第二行包含一個(gè)正整數(shù) n，表示操作次數(shù)。
接下來(lái) n 行，每行形如 1 x c 或者 2 t l r，意義如題目所述。
輸出格式
對(duì)于每組詢問(wèn)，輸出一個(gè)整數(shù)，表示 t 的所有子串和 sl...r 的匹配度之和。