23887번 - 프린트 전달 서브태스크

$N×M$ 크기의 직사각형 모양인 교실의 각 칸에는 책상이 하나씩 놓여있다. 북과고의 학생들은 뒤쪽에 몰려 앉거나 서로 떨어져 앉는 등 자리에 제멋대로 앉는다. 선생님은 종종 수업 자료를 프린트로 나눠주시는데, 학생들의 불규칙한 자리 배치 탓에 프린트를 줄별로 나눠주는 등의 평범한 방법으로는 모든 학생에게 프린트를 전달할 수 없다. 그래서 선생님과 학생들은 다음과 같은 방법으로 프린트를 분배한다.

1. 먼저, 선생님이 $S$번 학생에게 프린트 $K$장을 전달한다. 이때, $K$는 전체 학생 수와 같다.
2. 프린트를 가진 학생은 본인과 상하좌우 혹은 대각선으로 인접한 $8$칸에 위치한 학생 중 아직 프린트를 받지 못한 학생 모두에게 동시에 자신의 프린트를 뺀 모든 프린트를 전달한다. 이때 걸리는 시간은 프린트의 수와 관계없이 일정하다.
3. 어떤 학생이 두 명 이상의 학생에게 동시에 프린트를 받을 수 있다면 항상 번호가 가장 작은 학생에게만 받는다.
4. 모든 학생이 프린트를 가능한 한 빨리 받을 수 있도록 전달이 이루어진다.
5. 모든 학생이 프린트를 하나씩 소지하고 있을 때까지 위 과정을 반복한다.

하지만 이 방법으로는 각 학생이 받는 프린트의 수에 따라 프린트를 받지 못하는 학생이 생기거나 프린트가 남을 수 있다. 모든 학생이 프린트를 받을 수 있도록 각 학생이 받아야 하는 프린트의 수를 구해 학생들에게 미리 알려주자.

파란색은 각 학생이 받은 프린트의 수, 빨간색은 전달되는 프린트의 수.

선생님이 3번 학생에게 프린트 9장을 전달한 상황이다.

3번 학생이 잘못 전달해서 4번 학생은 프린트가 남고, 8번 학생은 프린트를 받지 못한다.

올바른 분배. 모든 학생이 한 장의 프린트를 가진다.

첫째 줄에 교실의 크기 $N$, $M$, 학생 수 $K$가 주어진다.

둘째 줄부터 $K$개의 줄에 $i$번 학생의 좌표 $X_i$, $Y_i$가 주어진다. 단, 모든 학생의 좌표는 다르다.

마지막 줄에 선생님께 프린트를 받은 학생의 번호 $S$가 주어진다.

프린트를 받을 수 없는 학생이 존재하는 경우 -1을 출력하고 종료한다. 그렇지 않다면 각 학생이 받아야 하는 프린트의 수를 번호순으로 출력한다.

• $1 ≤ N, M ≤ 500$
• $1 ≤ K ≤ N×M$
• $1 ≤ X_i ≤ N$, $1 ≤ Y_i ≤ M$ $(1 ≤ i ≤ K)$
• $1 ≤ S ≤ K$