She was carrying disgusting, disturbing yellow flowers in her hands. Still, he liked her.

According to a well-known theorem, the personality of every person can be represented by a permutation of length $N$. Thus, the personality of our hero, the Master, 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 measure of similarity between permutations, and thus the happiness in married life, can be represented as the maximum size of the intersection of some subinterval of length $K$ of permutation $p$ and a subinterval of length $K$ of permutation $q$. Here, the intersection is considered in the set-theoretic sense, i.e., the order of numbers in the subintervals does not matter. For example, in the case $N = 4, K = 3$, the similarity of permutations $(2, 4, 1, 3)$ and $(1, 2, 3, 4)$ is $2$, and it is achieved for any choice of subintervals.

Ever since he saw Margarita, the Master has been obsessed with the similarity of his and her permutation, and his personality has become very changeable. Thus, every day, two adjacent elements in his permutation will be swapped. Note that this change is permanent, i.e., those two elements remain swapped during the following days. Now he is interested in the similarity of his and her permutation when he first saw her, as well as the similarity after the change during each of the following $Q$ days. Additionally, he is interested in how many pairs of subintervals achieve such similarity. In his romantic woes, he has asked you for help!

Input

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

The second line contains $N$ numbers where the $i$-th denotes $p_i$.

The third line contains $N$ numbers where the $j$-th denotes $q_j$.

The next $Q$ lines contain descriptions of the changes. The $i$-th line contains the number $t_i$ ($1 \le t_i < N$) which indicates that the numbers at positions $t_i$ and $t_i + 1$ in the Master's permutation $p$ have been swapped.

Output

In the first line, you must print the initial similarity of the permutations and the number of pairs of subintervals for which that similarity is achieved.

In the next $Q$ lines, you must print the same, after the change of that day.

Subtasks

In all subtasks, $2 \le N \le 100\,000$, $1 \le K \le N$, and $0 \le Q \le 100\,000$.

Examples

Input 1

2 1 1
1 2
1 2
1

Output 1

1 2
1 2

Input 2

4 3 0
2 4 1 3
1 2 3 4

Output 2

2 4

Input 3

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

Output 3

2 5
2 6
3 1
3 1

Note

Explanation of the second example: The subintervals of length three in the first permutation are $(2, 4, 1)$ and $(4, 1, 3)$, and in the second $(1, 2, 3)$ and $(2, 3, 4)$. For the intersections we have: $\{2, 4, 1\} \cap \{1, 2, 3\} = \{1, 2\}$, $\{2, 4, 1\} \cap \{2, 3, 4\} = \{2, 4\}$, $\{4, 1, 3\} \cap \{1, 2, 3\} = \{1, 3\}$, $\{4, 1, 3\} \cap \{2, 3, 4\} = \{3, 4\}$, so we see that the similarity is $2$ and that it is achieved for four pairs of subintervals.