题目背景

题目来源：https://hsin.hr/hio2023/。

题目描述

她手里捧着一束令人作呕、令人不安的黄花。但他却喜欢上了她。

根据一个著名的定理，每个人的个性都可以用一个长度为 $N$ 的排列来表示。因此，我们主人公——大师 (Majstor) 的个性，可以用一个排列 $p$ 来表示。而那位吸引了他目光的女士——玛格丽特 (Margarita) 的个性，则可以用一个排列 $q$ 来表示。

两个排列的 相似度 (sličnost)，也即婚姻生活的幸福度，可以表示为：从排列 $p$ 中取一个长度为 $K$ 的子区间，再从排列 $q$ 中取一个长度为 $K$ 的子区间，计算这两个子区间所含元素的交集大小，所有可能的取法中，这个交集大小的最大值就是相似度。在此，交集是在集合的意义上考虑的，也就是说，子区间内数字的顺序无关紧要。例如，在 $N = 4, K = 3$ 的情况下，排列 $(2\ 4\ 1\ 3)$ 和 $(1\ 2\ 3\ 4)$ 的相似度是 2，这个值对于任意一对子区间的选择都能达到。

自从见到玛格丽特，大师就对他们俩排列的相似度念念不忘，他的个性也因此变得非常多变。每一天，他排列中的两个相邻元素都会互换位置。需要注意的是，这个变化是永久性的，也就是说，这两个元素在接下来的日子里会保持互换后的状态。现在，他想知道在他刚见到她时，他和她的排列的相似度是多少，以及在接下来的 $Q$ 天里，每天发生变化后的相似度是多少。此外，他还想知道，这个最大的相似度是由多少对子区间达成的。在他爱情的苦恼中，他请求您的帮助！

输入格式

第一行是三个整数 $N, K$ 和 $Q$。

第二行是 $N$ 个数字，构成了排列 $p$。

第三行是 $N$ 个数字，构成了排列 $q$。

接下来的 $Q$ 行是变化的描述。第 $i$ 行包含一个整数 $t_i$ ($1 \le t_i < N$)，表示在大师的排列 $p$ 中，位置为 $t_i$ 和 $t_i + 1$ 的数字交换了位置。

输出格式

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

在接下来的 $Q$ 行中，每行输出当天变化发生后，同样的两项信息。

2 1 1
1 2
1 2
1

1 2
1 2

4 3 0
2 4 1 3
1 2 3 4

2 4

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

2 5
2 6
3 1
3 1

提示

【样例解释】

第二个样例的解释：在第一个排列中长度为 $3$ 的子区间有 $(2\ 4\ 1)$ 和 $(4\ 1\ 3)$，在第二个排列中有 $(1\ 2\ 3)$ 和 $(2\ 3\ 4)$。对于交集，我们有：

• $\{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\}$；

所以我们可以看到相似度是 $2$，并且这种相似度在四对子区间上得以实现。

【数据范围】

在所有子任务中，$2 \leq N\leq 10^5$，$1 \leq K \leq N$，$0 \leq Q \leq 10^5$。