Description

After getting destroyed by the judge, Little L reflected and decided to use a safer password. Little L designed a password that may be as long as $200{,}000$ characters and consists only of lowercase letters, and he guarantees that nobody can remember it, guess it, or brute-force it (including Little L himself).

To avoid forgetting the whole password string (no need to avoid it; he has already forgotten it), Little L wrote a program that can store his password string $T$, but cannot output it directly (because others might use this program). The first time, Little L reconstructs a string $P$ of length $l$ from memory. Later, he will modify one character of $P$ based on the program’s output. This program can compute the mismatch degree between the current guess string $P$ and the substring of $T$ with the same length.

Define the value of character a as $1$, character b as $2$, and so on, up to character z as $26$. Define the mismatch degree of two strings $s,t$ as the sum of the squares of the differences of their values at corresponding positions.

Now, Little L wants to know whether his program is correct. Please write a similar program as well.

Input Format

The first line contains three integers $n,l,m$, representing the length $n$ of the password string $T$, the length $l$ of the guess string $P$, and the number of operations $m$.

The next two lines contain two strings, which are $T$ and $P$.

The next $m$ lines each start with an integer $op$, indicating the type of operation:

• If $op=1$, then an integer $x$ follows, meaning you need to query the mismatch degree between $P$ and the substring of $T$ of length $l$ starting from position $x$.
• If $op=2$, then an integer $x$ and a character $c$ follow, meaning you modify the $x$-th character of $P$ to make it equal to $c$.

Output Format

For each operation of type $1$, output one line containing the required value.

8 5 3
iamangry
anger
1 4
2 2 m
1 2

218
238

Hint

Please note the special time limit of this problem.

The data size is large, so please optimize constants carefully.

To prevent the problem from being too strict on runtime, this problem provides Bajuyang. You can paste it directly at the very beginning of your code and submit.

In this problem, all indices start from $1$.

• Subtask #1: $30$ points, guaranteed $n,m\le 5\times 10^3$.
• Subtask #2: $30$ points, guaranteed there is no operation type $2$.
• Subtask #3: $40$ points, guaranteed $n,m\le 2\times 10^5$.

For $100\%$ of the testdata, it is guaranteed that $1\le l\le n$ and $1\le x$.

For all operations of type $1$, it is guaranteed that $x-1+l\le n$.

For all operations of type $2$, it is guaranteed that $x\le l$.

Sample Explanation

$(a-a)^2+(n-n)^2+(g-g)^2+(r-e)^2+(y-r)^2=13^2+7^2=218$.

$(a-a)^2+(m-m)^2+(a-g)^2+(n-e)^2+(g-r)^2=6^2+9^2+11^2=238$。

Translated by ChatGPT 5