Description

Little F decides to design a language with a huge character set — the Z language — even if extra characters are sometimes useless.

Features of this language:

• The character set is extremely large, possibly with $2147483648\ (2^{31})$ distinct characters.
• Each word is made of a sequence of pairwise distinct characters.
• Characters can be compared for equality and order, so we will use numbers to represent the strange characters in the Z language.
• Two words that look completely different can still be the same word because: as long as the positions of the $K$-th largest characters are the same in both words for every $K$, then they are essentially the same word. For example, $\{1, 2, 3, 4, 5\}$ and $\{2, 3, 23, 233, 23333\}$ are the same. (So you can conveniently use the Z language to encrypt information!)

Now, Little F plans to apply the Z language to a real task. For example, he opens an algorithm problem on a computer:

Given two strings $A$ and $B$, find how many times $B$ is matched as a substring in $A$.

Little F knows this is a basic problem solvable with KMP. However, when implementing Z-KMP for matching in the Z language, he ran into trouble. Can you help him?

To verify you really understand what Little F means, he will modify string $B$ many times and ask you. No slacking!

See the input and output formats for the operations your program must support.

Input Format

The first line contains two integers $n, m, q$ ($1 \leq n, m, q \leq 10^5$), the lengths of strings $A$ and $B$, and the number of operations.

The second line contains $n$ non-negative integers. The $i$-th is the $i$-th character $A_i$ of string $A$ ($0 \leq A_i \leq 2147483647 = 2^{31}-1$).

The third line contains $m$ non-negative integers. The $i$-th is the $i$-th character $B_i$ of string $B$ ($0 \leq B_i \leq 2147483647 = 2^{31}-1$).

Then follow $q$ lines. Each line contains two positive integers $x_i, c_i$ ($1 \leq c_i \leq 2147483647 = 2^{31}-1$), meaning the character at position $x_i$ in $B$ is changed from $B_{x_i}$ to $c_i$.

The testdata guarantees that at any time, both $A$ and $B$ are valid Z strings that satisfy the above requirements.

Output Format

After each modification, output the number of times $B$ is Z-matched as a substring in $A$.

5 3 2
11 7 5 3 2
3 2 1
2 5
1 6

0
3

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477 (partially uploaded).

Sample 1 Explanation:

• After the first modification, $\{3, 5, 1\}$ cannot be matched by any substring of $A$.
• After the second modification, $\{6, 5, 1\}$ can be matched by every length-$3$ substring of $A$, because $A$ is strictly decreasing and $B$ is also strictly decreasing, so positions of characters with the same ranks coincide.

Subtasks:

• Subtask $1$ (31 pts): $n, m \leq 100$, $q \leq 1000$.
• Subtask $2$ (41 pts): $n, m \leq 1000$, $q \leq 5 \times 10^4$.
• Subtask $3$ (78 pts): $n, m, q \leq 10^5$.

Translated by ChatGPT 5