Similarity

She was holding yellow flowers that were ugly and disturbing. Still, he liked her.

According to a well-known theorem, the personality of each person can be represented by a permutation of length $N$. So the personality of our hero, Majstor, can be represented by a permutation $p$, and the personality of Margarita, the lady who caught his eye, can be represented by a permutation $q$.

The similarity of two permutations, which measures how well a marriage will go, is the largest size of the intersection of a subinterval of length $K$ of $p$ and a subinterval of length $K$ of $q$. The intersection is taken as sets, so the order of numbers inside the subintervals does not matter. For example, when $N = 4$ and $K = 3$, the similarity of $(2\,4\,1\,3)$ and $(1\,2\,3\,4)$ is $2$, and this value is obtained for any choice of subintervals.

Since he saw Margarita, Majstor has been obsessed with the similarity between his permutation and hers, and his personality has become very changeable. Every day, two adjacent elements of his permutation are swapped. The change is permanent, so the two elements stay swapped on the following days. He wants to know the similarity when he first saw her, and the similarity after each of the next $Q$ days of changes. He also wants to know the number of pairs of subintervals that achieve this similarity. Help him with his lovesick problem.

The first line contains the numbers $N$, $K$, and $Q$.

The second line contains $N$ numbers, where the $i$-th number is $p_i$.

The third line contains $N$ numbers, where the $j$-th number is $q_j$.

Each of the next $Q$ lines describes a change. The $i$-th of these lines contains a number $t_i$ ($1 \le t_i < N$), which means that the numbers at positions $t_i$ and $t_i + 1$ in Majstor's permutation $p$ are swapped.

On the first line, print the initial similarity and the number of pairs of subintervals that achieve it.

On each of the next $Q$ lines, print the same two values after the change of that day.

These are the subintervals of length three. In the first permutation they are $(2\,4\,1)$ and $(4\,1\,3)$, and in the second they are $(1\,2\,3)$ and $(2\,3\,4)$. The intersections are:

$\{2, 4, 1\} \cap \{1, 2, 3\} = \{1, 2\}, \quad \{2, 4, 1\} \cap \{2, 3, 4\} = \{2, 4\},$

$\{4, 1, 3\} \cap \{1, 2, 3\} = \{1, 3\}, \quad \{4, 1, 3\} \cap \{2, 3, 4\} = \{3, 4\},$

So the similarity is 2, and it is achieved by four pairs of subintervals.