[SHOI2001]小狗散步

题目描述

Grant 喜欢带着他的小狗 Pandog 散步。Grant 以一定的速度沿着固定路线走,该路线可能自交。Pandog 喜欢游览沿途的景点,不过会在给定的 $N$ 个点和主人相遇。小狗和主人同时从 $(X_1,Y_1)$ 点出发,并同时在 $(X_n,Y_n)$ 点汇合。小狗的速度最快是 Grant 的两倍。当主人从一个点以直线走向另一个点时,Pandog 跑向一个它感兴趣的景点。Pandog 每次与主人相遇之前最多只去一个景点。 你现在的任务是:为 Pandog 寻找一条路线(有可能与主人的路线部分相同),使它能够游览最多的景点,并能够准时与主人在给定地点相遇或者汇合。

输入输出格式

输入格式


第一行是两个整数 $N$ 和 $M$。 第二行的 $N$ 个坐标给出了 Grant 的散步路线,即 Pandog 和主人相遇地点。 第三行的 $M$ 个坐标给出了所有 Pandog 感兴趣的景点。

输出格式


输出小狗的移动路线。 第一行是经过的点数,第二行依次为经过的点的二维坐标。

输入输出样例

输入样例 #1

4 5
1 4 5 7 5 2 -2 4
-4 -2 3 9 1 2 -1 3 8 -3

输出样例 #1

6
1 4 3 9 5 7 5 2 1 2 -2 4

说明

对于所有数据,有 $1\le N,M\le 100$,所有输入的坐标均不相同,且绝对值不超过 $10^3$。