题目背景

题目来源：https://hsin.hr/hio2023/。翻译来自 文心一言。如果有更好的翻译请在讨论区提供。

题目描述

她手里拿着讨厌的、令人不安的黄色花朵。然而，他喜欢它。

根据已知的定理，每个人的个性都可以表示为长度为 $N$ 的排列。因此，我们的主角“匠人”的个性可以表示为排列 $p$。而玛格丽特的个性，可以用排列 $q$ 来表示。

衡量排列的相似性，从而在婚姻生活中找到幸运与幸福，可以表示为某个长度为 $K$ 的排列 $p$ 与长度为 $K$ 的排列 $q$ 的最大交集。这里的交集是在集合意义上考虑的，即不考虑子区间中的顺序。例如，在 $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$），表示在第 $i$ 天匠人的排列 $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$。