Little F has decided to design a language with an extremely large character set—the Z language—even if the extra characters are sometimes useless.

The characteristics of this language are:

• The character set is very large, potentially containing $2147483648 (2^{31})$ distinct characters;
• Each word consists of a sequence of pairwise distinct characters;
• Characters can be compared for equality and inequality, and can also be ordered. Therefore, we represent the peculiar characters of the Z language using integers;
• Two words that look completely different may actually be the same word because: if the positions of the $K$-th largest characters in two words are the same for all $K$, then the words are essentially the same. For example, $\{1, 2, 3, 4, 5\}$ and $\{2, 3, 23, 233, 23333\}$ are identical. (This makes the Z language very convenient for encrypting information!)

Now, Little F intends to apply the Z language to a practical scenario. For instance, he opened an algorithmic problem on his computer:

Given two strings $A$ and $B$, find the number of times $B$ occurs as a substring in $A$.

Little F knows that this is a basic problem that can be solved using KMP. However, he encountered a problem while implementing Z-KMP using the Z language's matching rules. Can you help him?

To verify that you truly understand what Little F is talking about, he will modify string $B$ many times and ask you for the result. Don't be lazy!

The operations your program needs to support are detailed in the Input and Output sections.

Input

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

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

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

The next $q$ lines each contain two positive integers $x_i, c_i$ ($1 \leq c_i \leq 2147483647 = 2^{31} - 1$), representing the modification of the character at position $x_i$ in string $B$ from $B_{x_i}$ to $c_i$.

It is guaranteed that at any time, both $A$ and $B$ are valid Z-strings satisfying the aforementioned requirements.

Output

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

Examples

Input 1

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

Output 1

0
3

Note

Explanation of Example 1

After the first modification, $\{3, 5, 1\}$ cannot be matched by any substring in $A$.

After the second modification, $\{6, 5, 1\}$ can be matched by all substrings of length $3$ in $A$. This is because $A$ is monotonically decreasing and $B$ is also monotonically decreasing, so for all substrings of length $3$ in $A$, the characters with the same relative rank as in $B$ are in the same positions.

Subtasks

Subtask $1 (31 \text{ pts}): n, m \leq 100, q \leq 1000$;

Subtask $2 (41 \text{ pts}): n, m \leq 1000, q \leq 5 \times 10^4$;

Subtask $3 (78 \text{ pts}): n, m, q \leq 10^5$.