Let F(s) be a function which returns an integer value where s is a string.
Initially, F(s) = 0 for all possible strings.
Given a string S , you have to perform Q operations of 2 types:
i. given val and x, y : add val to F(S[x:y]) where S[x:y] is the substring of S from position x to y
ii. given string T, find summation of F(s) for all substrings of T (if substring occurs more than once in T, it must be added more than once to the sum)
First Line contains t, number of test cases. t test cases follow:
First line of each test case contains the string S.
Second line contains Q, the number of operations to be handled. Operations follow, in the following format:
1 val x y denoting an operation of type 1
2 T denoting an operation of type 2
Output the answer for each operation of type 2 on a new line, in the order present in the input.
1<= T <= 5
1<= |S| <= 100000
1<= Q <= 100000
1<= val <= 1000000000
1<= x <= y <= |S|
sum of |T| over all queries <= 100000