← 返回题目列表

Codeforces · 39/F

F. 和平青蛙

中文机器翻译题面 查看原题

拇指姑娘出了事故。她发现自己身处沼泽中间的一座小岛上,非常想回到岸边。

人们只能通过沿着连接小岛和海岸的直线的山丘到达海岸。假设山丘从 1 到 n 编号,山丘的编号等于它与岛屿之间的距离(以米为单位)。第n座山丘与海岸的距离也是1米。

拇指姑娘太小了,无法进行这样的跳跃。幸运的是,沼泽里的青蛙一家建议帮助她。每只青蛙都同意载拇指姑娘,但拇指姑娘只能选择一只青蛙。每只青蛙都有一定的跳跃长度。如果拇指姑娘同意接受跳跃长度为 d 的青蛙的帮助,青蛙将从 d 山上的岛上跳下,然后 - 2d 山上,然后 3d 山上,依此类推,直到到达岸边(即发现自己超出了 n 山)。

然而,还有一个问题:沼泽地里也生活着蚊子。此刻他们正在午睡,正在一些小山上小憩。如果青蛙带着蚊子跳上山,青蛙就会把蚊子踩碎。拇指姑娘遇到的青蛙都是和平主义者,所以每只蚊子的死亡他们都会感到非常悲伤。帮助拇指姑娘选择一只青蛙,将她带到岸边并消灭尽可能少的蚊子。

输入

第一行包含三个整数 n、m 和 k (1 ≤ n ≤ 109, 1 ≤ m, k ≤ 100)——分别是山、青蛙和蚊子的数量。第二行包含 m 个整数 di (1 ≤ di ≤ 109) — 青蛙跳跃的长度。第三行包含 k 个整数——每只蚊子睡觉的山丘的编号。每座山上最多只能睡一只蚊子。行中的数字由单个空格分隔。

输出

在第一行中输出击碎最少数量蚊子的青蛙数量,在第二行中输出它们的数量按升序排列,并用空格分隔。青蛙按照输入数据中给出的跳跃长度的顺序从 1 到 m 编号。

示例

输入 #1

5 3 5
2 3 4
1 2 3 4 5

输出 #1

2
2 3

输入 #2

1000000000 2 3
2 5
999999995 999999998 999999996

输出 #2

1
2