유사도

그녀는 손에 징그럽고 거슬리는 노란 꽃을 들고 있었다. 그래도 그는 그녀가 마음에 들었다.

유명한 정리에 따르면 사람의 성격은 길이 $N$인 순열로 나타낼 수 있다. 주인공 마이스터의 성격은 순열 $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 \le t_i < N$)가 주어지며, 이는 마이스터의 순열 $p$에서 위치 $t_i$와 $t_i + 1$의 수가 서로 바뀌었다는 뜻이다.

첫째 줄에 처음 유사도와 그 유사도를 얻는 부분구간 쌍의 개수를 출력한다.

이어서 $Q$개의 줄에 각 날의 변화 뒤 같은 두 값을 출력한다.

길이가 3인 부분구간은 첫 번째 순열에서 $(2\,4\,1)$, $(4\,1\,3)$이고, 두 번째 순열에서 $(1\,2\,3)$, $(2\,3\,4)$이다. 교집합은 다음과 같다.

$\{2, 4, 1\} \cap \{1, 2, 3\} = \{1, 2\}, \quad \{2, 4, 1\} \cap \{2, 3, 4\} = \{2, 4\},$

$\{4, 1, 3\} \cap \{1, 2, 3\} = \{1, 3\}, \quad \{4, 1, 3\} \cap \{2, 3, 4\} = \{3, 4\},$

따라서 유사도는 2이고, 부분구간 쌍 네 개에서 이 값이 나온다.