暂无测试数据。

题目描述

有一个 \(M\) 行 \(N\) 列的教室座位中，
有 \(D\) 对同学总爱凑在一起讲话。
现老师要用走廊隔开他们。
但只能在行之间加入 \(K\) 条走廊，
在列中加入 \(L\) 条走廊，
问加在哪里能使效果最佳。
（一对爱讲话的同学只有左右相邻或上下相邻）。

输入

第一行，有 5 个用空格隔开的整数，
分别是 \(M，N，K，L，D\)。
接下来 \(D\) 行，每行有4个用空格隔开的整数，
第 \(i\) 行的 4 个整数 \(X_i\)，\(Y_i\)，\(P_i\)，\(Q_i\)，
表示坐在位置 \((X_i,Y_i)\) 与 \((P_i,Q_i)\) 的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。
输入数据保证最优方案的唯一性。

输出

共两行。

第一行包含 \(K\) 个整数，\(a_1 a_2 \cdots a_K\)，
表示第 \(a_1\) 行和 \(a_1+1\) 行之间、第 \(a_2\) 行和第 \(a_2+1\) 行之间、
\(\cdots\)、
第 \(a_K\) 行和第 \(a_K+1\) 行之间要开辟通道，
其中 \(a_i < a_i+1\)，
每两个整数之间用空格隔开（行尾没有空格）。

第二行包含\(L\) 个整数，
\(b_1b_2 \cdots b_k\)，
表示第 \(b_1\) 列和 \(b_1+1\) 列之间、第 \(b_2\) 列和第 \(b_2+1\) 列之间、
\(\cdots\)、
第 \(b_L\) 列和第 \(b_L+1\) 列之间要开辟通道，
其中 \(b_i < b_i+1\)，
每两个整数之间用空格隔开（行尾没有空格）。
若有多组答案，
输出字典序最小的一组。

样例输入

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

样例输出

2
2 4

数据范围限制

\(2 \leq N，M \leq 1000\)，
\(0 \leq K < M\)，
\(0 \leq L < N，D \leq 2000\).

来源

入门篇练习5.6.5