Z-KMP Pattern Matching

Z language is a peculiar language with an extremely large character set (up to \(2^{31}\) possible characters). In Z language, every word is a sequence of pairwise distinct characters (represented by integers) and even though characters can be compared for equality and order, two words that look completely different may in fact be considered equivalent.

Two words of the same length \(m\) are deemed equivalent if, after sorting their characters in descending order, the positions of the \(k\)-th largest characters are identical for every \(1 \le k \le m\). For example, the words \(\{1, 2, 3, 4, 5\}\) and \(\{2, 3, 23, 233, 23333\}\) are equivalent since if you sort each in descending order, the positions where the largest, second largest, third largest, etc., characters occur are exactly the same.

Now, consider the following algorithmic problem inspired by Z language:

Given a text string \(A\) and a pattern string \(B\) (both following the rules of Z language, i.e. all characters are distinct within the word), count the number of substrings of \(A\) that are equivalent to \(B\) under the above equivalence relation.

Furthermore, there will be \(Q\) queries. In each query, a single character of \(B\) is modified. After each modification, you are to output the number of occurrences of the new \(B\) in \(A\) (i.e. the number of substrings of \(A\) that are equivalent to \(B\)).

Note on equivalence: Two words \(X\) and \(Y\) of length \(m\) are equivalent if, when sorted in descending order, the indices (positions within the word) of the sorted characters are identical. For example, for a word \(S = [s_0, s_1, \dots, s_{m-1}]\), let \(p_1, p_2, \dots, p_m\) be a permutation of \(\{0, 1, \dots, m-1\}\) such that \(S[p_1] > S[p_2] > \cdots > S[p_m]\). The word is represented by the pattern \((p_1, p_2, \dots, p_m)\). Two words are equivalent if their corresponding pattern tuples are equal.

inputFormat

The input begins with three integers \(n\), \(m\) and \(Q\) on one line, representing the length of string \(A\), the length of string \(B\), and the number of modification queries, respectively.

The second line contains \(n\) space-separated integers representing the text string \(A\). It is guaranteed that \(A\) is a valid Z language word (all characters are distinct).

The third line contains \(m\) space-separated integers representing the initial pattern string \(B\) (also all characters are distinct).

Each of the following \(Q\) lines contains two integers \(pos\) and \(val\), indicating that the character at position \(pos\) (1-indexed) in \(B\) is to be changed to \(val\). After each query, output the number of occurrences of the updated \(B\) in \(A\) (i.e. count the number of substrings of \(A\) of length \(m\) that are equivalent to \(B\)).

outputFormat

For each query, output one line containing a single integer: the number of substrings of \(A\) that are equivalent to the current \(B\) according to the Z language matching rule.

sample

5 3 2
1 3 2 5 4
3 1 2
2 4
1 5

0
0