Background

“Finally escaped from this damned tower.”.

Problem Description

At the bottom of the tower, you see a door. This is the last barrier before you gain freedom. Of course, opening this door requires a password, which can be seen as a string containing only lowercase letters. You do not know the exact password, but by some method you obtained a template string $s$ used to generate the password, and you know that the password must be a substring of the template string.

You will try several times. Each time you are given a string $t$ and an interval $[l,r]$. You will choose a substring of $t$ to match with $s_{l...r}$. Define the matching score of two strings as the length of their longest common suffix (the largest $x$ such that the last $x$ characters of the two strings are the same). You plan to randomly choose a substring of $t$ to match with this interval of $s$, and you want to know the expected matching score. To avoid floating-point errors, you only need to compute the sum of matching scores over all choices. Sometimes, you may find that the template string you got has some problems, and you need to modify one character in it. This modification will apply to future attempts.

More formally, you need to maintain the following two operations:

• 1 x c, meaning to modify $s_x$ (the $x$-th character of $s$) to the character $c$, and it is guaranteed that $c$ is a lowercase letter;

• 2 t l r, meaning to give a string $t$, and compute the sum of matching scores between all substrings of $t$ and $s_{l...r}$, where the matching score is defined above.

You decide to play this boring game for a while, since you have nothing better to do.

Input Format

The first line contains a string $s$ consisting only of lowercase letters, representing the password generation template.

The second line contains a positive integer $n$, representing the number of operations.

The next $n$ lines each have the form 1 x c or 2 t l r, with meanings as described in the statement.

Output Format

For each query, output an integer representing the sum of matching scores between all substrings of $t$ and $s_{l...r}$.

bcca
4
2 acba 1 2
2 cab 1 4
1 2 b
2 bca 2 4

2
3
6

Hint

Let $S$ be the number of characters in the input.

For $10\%$ of the testdata, $S \leq 100, n \leq 10$;

For $20\%$ of the testdata, $S \leq 1000, n \leq 100$;

For $30\%$ of the testdata, $S \leq 10000, n \leq 1000$;

For $50\%$ of the testdata, $S \leq 10^5, n \leq 10^5$;

For $70\%$ of the testdata, $S \leq 10^{6}$;

For another $14\%$ of the testdata, there are no modification operations;

For all testdata, $S \leq 10^{7}, n \leq 10^{6}$.

It is guaranteed that the input is valid, and the testdata has a certain gradient.

It is guaranteed that the answer to each query fits in a 64-bit signed integer.

Lanqiao Cup 2019 National Contest Group A Problem J.

Translated by ChatGPT 5