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