편지 배달 2

Hello 고등학교에서는 다른 반 친구와 편지를 주고받는 것이 유행이다. Hello 고등학교에는 $1$반부터 $N$반까지 총 $N$개의 반이 있고, 각 반의 교실은 반 번호 순서대로 직선 형태의 복도를 따라 늘어서 있다.

쉬는 시간마다 복도를 산책하는 것을 좋아하는 동규는 산책하는 김에 학생들의 편지도 배달해 주기로 했다. 산책은 다음과 같이 진행한다. 먼저 동규가 $L+1$개의 반 번호 $c_0, c_1, \dots, c_{L-1}, c_L$을 정한다. 이때 $c_0 = c_L$은 동규의 반 번호이며, 동규는 이 반에서 출발해서 이 반으로 돌아와야 한다. 산책은 총 $L$번의 이동으로 이루어진다. $i$번째 이동에서는 현재 위치에서 $c_i$반을 향해 일직선으로 걷는다. 교실이 직선 형태의 복도를 따라 늘어서 있으므로, 동규가 $c_{i-1}$반에서 $c_i$반으로 이동하는 동안 두 반 사이에 있는 모든 반을 지나게 된다.

학생들은 두 명씩 쌍을 이뤄 편지를 주고받는다. 두 학생은 서로 다른 반에 있어야 한다. $a$반 학생 A와 $b$반 학생 B가 편지를 주고받는 방법은 다음과 같다.

• 먼저 A가 B에게 보낼 편지를 쓴다. 동규는 산책 도중 처음으로 $a$반을 지날 때 A의 편지를 건네받는다.
• 동규는 A의 편지를 받은 뒤 처음으로 $b$반을 지날 때 B에게 편지를 전달한다. B는 편지를 받은 즉시 답장을 써서 동규에게 건넨다.
• 동규는 B의 답장을 받은 뒤 처음으로 $a$반을 지날 때 A에게 편지를 전달한다. A는 편지를 받은 즉시 답장을 써서 동규에게 건넨다.
• 동규가 산책을 끝낼 때까지 두 학생은 계속 번갈아 답장을 보낸다.

총 $M$쌍의 학생들이 편지를 주고받고자 한다. 동규는 편지를 동시에 몇 개든지 지닐 수 있다. 산책을 시작할 때와 끝낼 때에도 자기 반에서 편지를 건네받거나 전달할 수 있다. 산책이 끝났을 때 동규에게 남은 편지는 배달하지 못한 것으로 간주한다. $i=1,\dots,L$에 대해, 동규가 $i$번째 이동을 마쳤을 때까지 전달한 편지의 개수를 구하시오.

첫 번째 줄에 정수 $N$, $L$, $M$이 공백으로 구분되어 주어진다.

두 번째 줄에 동규의 산책 경로를 나타내는 $L$개의 정수 $c_0, \dots, c_{L-1}$이 공백으로 구분되어 주어진다. $c_L$은 $c_0$과 같으므로 주어지지 않음에 유의하라.

세 번째 줄부터 $M$개의 줄에 편지를 주고받을 학생 쌍의 정보 $a$, $b$가 공백으로 구분되어 주어진다. 이는 $a$반 학생과 $b$반 학생이 서로 편지를 주고받고자 함을 나타내며, $a$반 학생이 먼저 편지를 보낸다.

총 $L$개의 줄을 출력한다. $i$번째 줄에는 동규가 $i$번째 이동을 마쳤을 때까지 배달한 편지의 개수를 출력한다.

• $2 \le N \le 200\,000$
• $1 \le L, M \le 200\,000$
• $1 \le c_i \le N$
• 모든 학생 쌍에 대해 $1 \le a, b \le N$이고 $a \ne b$이다.