cho.sh

편지 배달 2

아직 제출이 없습니다시간 제한3초메모리 제한1024 MB

문제

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

쉬는 시간마다 복도를 산책하는 것을 좋아하는 동규는, 산책하는 김에 학생들의 편지도 배달해 주기로 했다. 동규가 산책하는 방법은 다음과 같다. 먼저 동규는 L+1L+1개의 반 번호 c_0,c_1,…,c_L−1,c_Lc\_0,c\_1,\dots ,c\_{L-1},c\_L을 정한다. 이때 c_0=c_Lc\_0=c\_L은 동규의 반 번호로, 동규는 이곳에서 출발해서 이곳으로 도착해야 한다. 산책은 총 LL번의 이동으로 이루어진다. ii번째 이동에서는 현재 위치에서 c_ic\_i반을 향해 일직선으로 이동한다. 교실이 직선 형태의 복도를 따라 나열되어 있기 때문에, 동규가 c_i−1c\_{i-1}반에서 c_ic\_i반을 향해 이동하는 동안 두 반 사이에 있는 모든 반을 지나게 된다.

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

  • 먼저 A가 B에게 보낼 편지를 준비한다. 동규는 산책 도중 처음으로 aa반을 지날 때 A의 편지를 건네받는다.
  • 동규는 A의 편지를 받은 이후 처음으로 bb반을 지날 때 B에게 편지를 전달하고, B는 편지를 받은 즉시 답장 편지를 작성해서 동규에게 건넨다.
  • 동규는 B의 편지를 받은 이후 처음으로 aa반을 지날 때 A에게 편지를 전달하고, A는 편지를 받은 즉시 답장 편지를 작성해서 동규에게 건넨다.
  • 동규가 산책을 끝낼 때까지 두 학생은 계속 번갈아서 답장 편지를 보낸다.

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

입력

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

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

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

출력

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

제한

  • 2≤N≤200 0002\le N\le 200\ 000
  • 1≤L,M≤200 0001\le L,M\le 200\ 000
  • 1≤c_i≤N1\le c\_i\le N
  • 모든 학생 쌍에 대해서, 1≤a,b≤N1\le a,b\le N이고 a≠ba\ne b를 만족한다.