她手里拿着令人厌恶、令人不安的黄色花朵。然而，他还是喜欢上了她。

根据一个著名的定理，每个人的个性都可以用一个长度为 $N$ 的排列来表示。因此，我们主角“大师”（Majstor）的个性可以用排列 $p$ 来表示。而吸引他注意的女士玛格丽特（Margarita）的个性可以用排列 $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 \le t_i < N$)，表示大师的排列 $p$ 中位置 $t_i$ 和 $t_i + 1$ 的数字发生了交换。

输出格式

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

接下来的 $Q$ 行，每行输出相同的信息，表示当天发生变化后的结果。

数据范围

在所有子任务中，满足 $2 \le N \le 100\,000$，$1 \le K \le N$ 且 $0 \le Q \le 100\,000$。

样例

输入格式 1

2 1 1
1 2
1 2
1

输出格式 1

1 2
1 2

输入格式 2

4 3 0
2 4 1 3
1 2 3 4

输出格式 2

2 4

输入格式 3

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

输出格式 3

2 5
2 6
3 1
3 1

说明

第二个样例的解释：

第一个排列中长度为 $3$ 的子区间为 $(2, 4, 1)$ 和 $(4, 1, 3)$，第二个排列中长度为 $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$，且有 $4$ 对子区间达到了该相似度。