15005 - 排座椅

上课时总会有一些同学和前后左右的人交头接耳，这一现象令班主任十分头疼。不过，班主任小哈发现了一些有趣的现象，只有有限的D对同学上课时会交头接耳。教室中座位是M行N列的，坐在第i 行第j 列的同学的位置是(i, j)，为了方便同学们进出，还设置了K条横向的通道，L条纵向的通道。 
于是，小哈想到一个可以减少上课时学生交头接耳的办法：他打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了2个会交头接耳的同学，那么他们就不会交头接耳了。请你帮忙给小哈编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生的对数最少。

样例理解：

• 用符号*、⋇、+ 标出了3 对会交头接耳的学生的位置 
• 图中3 条粗线的位置表示通道，图示划分方案是唯一的最 
  佳方案

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

共两行。第一行包含K 个整数a1, a2, . . . , aK，表示第a1 行和a1 + 1 行之间、第a2 行和a2 + 1 行之间、⋯ 、第aK 行和第aK + 1 行之间要开辟通道，其中ai < ai+1，每两个整数之间用空格隔开(行尾没有空格)。第二行包含L个整数b1, b2, . . . , bL，表示第b1 列和b1 + 1 列之间、第b2列和b2 + 1 列之间、⋯、第bL 列和第bL + 1 列之间要开辟通道，其中bi < bi+1，每两个整数之间用空格隔开(列尾没有空格)