Description

During class, some students always whisper with the people in front, behind, to the left, or to the right of them. This is very troubling for the primary school homeroom teacher. However, the teacher Xiaoxue noticed something interesting: once the seating positions are fixed, only a limited number $D$ of pairs of students will whisper during class.

Students sit in $M$ rows and $N$ columns. The student in row $i$ and column $j$ sits at position $(i, j)$. To make it easier for students to enter and exit, there are $K$ horizontal aisles and $L$ vertical aisles in the classroom.

Clever Xiaoxue came up with an idea that might reduce whispering: she plans to rearrange the desks and chairs by changing the positions of the aisles. If an aisle separates two students who would whisper, they will stop whispering.

Please help Xiaoxue write a program to output the best aisle placement. Under this plan, the number of whispering pairs during class is minimized.

Input Format

The first line contains $5$ space-separated integers: $M,N,K,L,D(2 \le N,M \le 1000,0 \le K<M,0 \le L<N,0\le D \le 2000)$.

The next $D$ lines each contain $4$ space-separated integers. On the $i$-th line, the $4$ integers $X_i,Y_i,P_i,Q_i$ indicate that the two students at positions $(X_i,Y_i)$ and $(P_i,Q_i)$ will whisper (the input guarantees they are adjacent either front/back or left/right).

The input guarantees that the optimal solution is unique.

Output Format

Output two lines. The first line contains $K$ integers $a_1,a_2,\ldots,a_K$, indicating that aisles are to be placed between row $a_1$ and row $a_1+1$, between row $a_2$ and row $a_2+1$, …, and between row $a_K$ and row $a_K+1$, where $a_i< a_{i+1}$. Integers are separated by single spaces, with no trailing space.

The second line contains $L$ integers $b_1,b_2,\ldots,b_L$, indicating that aisles are to be placed between column $b_1$ and column $b_1+1$, between column $b_2$ and column $b_2+1$, …, and between column $b_L$ and column $b_L+1$, where $b_i< b_{i+1}$. Integers are separated by single spaces, with no trailing space.

4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4

2
2 4

Hint

In the figure, the symbols *, ※, and + mark $3$ pairs of students who will whisper. The $3$ bold lines indicate aisles. The shown aisle arrangement is the unique optimal solution.

2008 Junior, problem 2.

Translated by ChatGPT 5