Problem Description

She held the annoying, unsettling yellow flowers in her hand. However, he liked them.

According to a known theorem, everyone's personality can be represented as a permutation of length $N$. Therefore, our protagonist "Craftsman" can have his personality represented by permutation $p$, and Margaret's personality can be represented by permutation $q$.

Measuring the similarity of permutations to find luck and happiness in marriage can be expressed as the maximum intersection of a permutation $p$ of length $K$ with a permutation $q$ of length $K$. The intersection here is considered in the set sense, i.e., without considering the order within the subinterval. For example, in the case of $N = 4, K = 3$, the similarity between permutations $(2\ 4\ 1\ 3)$ and $(1\ 2\ 3\ 4)$ is $2$, which can be achieved by selecting any subinterval.

Since seeing Margaret, Craftsman has been troubled by the similarity of his permutation, and his personality has become very changeable. Therefore, every day, two elements in his permutation will swap places. It should be noted that these changes are random. Each day, the swap of these two elements will occur in the next $Q$ days. Now he is interested in knowing the similarity of the permutation each day after seeing Margaret. Additionally, he also wants to know how many pairs of subintervals achieve this similarity. In his love troubles, he asks for your help!

Input Format

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

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

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

The next $Q$ lines describe the changes. The $i$-th line contains the integer $t_i$ ($1 \leq t_i < N$), indicating that on the $i$-th day, the numbers at positions $t_i$ and $t_i + 1$ in Craftsman's permutation $p$ are swapped.

Output Format

The first line should output the initial permutation similarity and the number of subinterval pairs that achieve this similarity.

The next $Q$ lines should output the similarity and the number of subinterval pairs after the changes on that day.

Sample Input and Output

Input Sample #1

2 1 1
1 2
1 2
1

Output Sample #1

1 2
1 2

Input Sample #2

4 3 0
2 4 1 3
1 2 3 4

Output Sample #2

2 4

Input Sample #3

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

Output Sample #3

2 5
2 6
3 1
3 1

Notes

[Sample Explanation]

Explanation of the second sample: In the first permutation, the subintervals of length $3$ are $(2\ 4\ 1)$ and $(4\ 1\ 3)$, and in the second permutation, they are $(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 can see that the similarity is $2$, and this similarity is achieved on four pairs of subintervals.

[Data Range]

In all subtasks, $2 \leq N \leq 10^5$, $1 \leq K \leq N$, $0 \leq Q \leq 10^5$.

见题面 Input 部分

见题面 Output 部分