[AdditionalFile5492.zip](file://AdditionalFile5492.zip?type=additional_file)

#5492. 「COI 2023」Sličnost

标签: 传统 | 时间限制: 3000 ms | 内存限制: 1024 MiB |

题目描述

译自 COI 2023 T4「Sličnost」

她手中拿着一些令人反感的黄色花朵。尽管如此，他仍然觉得她很有魅力。

根据一个众所周知的定理，一个人的性格由一个长度为 $N$ 的排列决定。因此，我们故事的主人公——「大师」的性格，就由这样一个排列 $p$ 决定。同样，吸引了他注意力的那位女士——玛格丽特的性格，则由排列 $q$ 表示。

两个排列 $p$ 和 $q$ 的相似度定义为：$p$ 的一个长度为 $K$ 的子区间与 $q$ 的一个长度为 $K$ 的子区间的交集可能达到的最大大小。请注意，交集是按集合来计算的，即子区间中元素的顺序无关紧要。例如，如果 $N=4, K=3$，排列 $(2, 4, 1, 3)$ 和 $(1, 2, 3, 4)$ 的相似度是 $2$，可以通过选择任意一对子区间得到。

自从见到玛格丽特后，大师就对他们两人排列的相似度着了迷，他的性格也变得非常不稳定。因此，每天他排列中的两个相邻元素都会交换位置。请注意，这种改变是永久性的，即在接下来的日子里，这些元素将保持交换后的状态。现在，大师想知道他和她的排列在初始时以及接下来 $Q$ 天里每次变化后的相似度。

输入格式

第一行包含整数 $N, K$ 和 $Q$。

第二行包含 $N$ 个数字，其中第 $i$ 个表示 $p_{i}$。

第三行包含 $N$ 个数字，其中第 $j$ 个表示 $q_{j}$。

接下来的 $Q$ 行描述了这些变化。第 $i$ 行包含一个整数 $t_{i}$ $(1 \leq t_{i}<N)$，表示大师排列中位置 $t_{i}$ 和 $t_{i}+1$ 上的数字交换了位置。

输出格式

在第一行，输出排列的初始相似度以及达到该相似度的子区间对的数量。

在接下来的 $Q$ 行中，再次输出这两个值，但应是在当天变化之后的结果。

样例 1

输入

2 1 1
1 2
1 2
1

输出

1 2
1 2

样例 2

输入

4 3 0
2 4 1 3
1 2 3 4

输出

2 4

样例 3

输入

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

输出

2 5
2 6
3 1
3 1

数据范围与提示

对于所有输入数据，满足 $2 \leq N \leq 100000, 1 \leq K \leq N$ 且 $0 \leq Q \leq 100000$。

详细子任务附加限制及分值如下表所示：