Personality Intersection in Permutations

In this problem, each person’s personality is represented as a permutation of length (N). Our protagonist, the Craftsman, has personality permutation (p) and Margaret has personality permutation (q). The similarity between two permutations is measured by the maximum size of the intersection (as sets) between any two contiguous subarrays of length (K) selected from (p) and (q) respectively.

For example, when (N=4, K=3), let (p=(2\ 4\ 1\ 3)) and (q=(1\ 2\ 3\ 4)). There are two contiguous subarrays of length 3 from each permutation: for (p): ((2,4,1)) and ((4,1,3)); for (q): ((1,2,3)) and ((2,3,4)). The intersection sizes (ignoring order) are as follows:

• Intersection of ({2,4,1}) and ({1,2,3}) is ({1,2}) with size 2,
• Intersection of ({2,4,1}) and ({2,3,4}) is ({2,4}) with size 2,
• Intersection of ({4,1,3}) and ({1,2,3}) is ({1,3}) with size 2,
• Intersection of ({4,1,3}) and ({2,3,4}) is ({3,4}) with size 2.

Thus, the maximum similarity is 2.

After seeing Margaret, the Craftsman becomes temperamental. Over the next (Q) days, his personality permutation (p) changes: each day two elements of (p) are swapped (the swap positions are given as input). The permutation (q) remains constant. Your task is to determine, for each day, the maximum similarity between a contiguous subarray (of length (K)) of the current permutation (p) and any contiguous subarray of (q) and count the number of subarray pairs that achieve this similarity.

The similarity between two subarrays is defined as the size of the intersection of the two sets of numbers from these subarrays.

inputFormat

The first line contains three integers \(N\), \(K\), and \(Q\) representing the length of the permutations, the subarray length for comparison, and the number of days (swaps) respectively.

The second line contains \(N\) distinct integers representing the permutation \(p\) (the Craftsman’s personality).

The third line contains \(N\) distinct integers representing the permutation \(q\) (Margaret’s personality).

Each of the next \(Q\) lines contains two integers \(a\) and \(b\) (1-indexed) indicating that the elements at positions \(a\) and \(b\) in \(p\) will be swapped on that day.

outputFormat

For each day, output a line containing two space‐separated integers. The first integer is the maximum similarity (i.e. maximum intersection size) between any pair of contiguous subarrays (of length \(K\)) from \(p\) and \(q\). The second integer is the number of pairs of subarrays that achieve this maximum similarity.

sample

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

3 1
3 2