Print Distribution

A classroom is a rectangle of size $N×M$, and each cell holds one desk. The students of Bukgwago sit wherever they like: crowded at the back, or scattered apart from each other. The teacher often hands out class materials as printouts, but because the students are seated irregularly, ordinary methods such as passing printouts row by row cannot deliver a printout to every student. So the teacher and the students distribute printouts as follows.

1. First, the teacher gives student $S$ a stack of $K$ printouts. Here $K$ equals the total number of students.
2. A student who has printouts simultaneously gives every printout except their own to all students in the $8$ cells adjacent to them horizontally, vertically, or diagonally who have not yet received a printout. The time this takes is constant regardless of the number of printouts.
3. If a student can receive printouts from two or more students at the same time, they always receive only from the student with the smallest number.
4. Deliveries are made so that every student receives printouts as quickly as possible.
5. The process repeats until every student holds exactly one printout.

With this method, however, some students may fail to receive a printout or printouts may be left over, depending on how many printouts each student receives. Find the number of printouts each student must receive so that every student can receive one, and tell the students in advance.

Blue is the number of printouts each student received, red is the number of printouts being delivered.

The teacher has given student 3 a stack of 9 printouts.

Student 3 hands them out incorrectly, so student 4 is left with extra printouts and student 8 receives none.

A correct distribution. Every student holds one printout.

The first line gives the size of the classroom $N$, $M$ and the number of students $K$.

The next $K$ lines give the coordinates $X_i$, $Y_i$ of student $i$. All students have distinct coordinates.

The last line gives the number $S$ of the student who received printouts from the teacher.

If any student cannot receive a printout, print -1 and terminate. Otherwise, print the number of printouts each student must receive, in order of student number.

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