← 返回题目列表

Codeforces · 66/E

E. 佩蒂亚和波斯特

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

小瓦夏的叔叔是一名邮递员。邮局位于一条环形道路上。此外,每个邮局旁边都有自己的加油站。 Petya 的叔叔的工作方式如下:早上他应该离开家去某个邮局。在办公室里,他收到了一部分信件和一辆汽车。然后他必须驾驶给定的汽车沿着环形路正好行驶一圈并返回起始邮局(叔叔可以沿着环形路向任何方向行驶,逆时针或顺时针)。此外,由于汽车属于城市邮政,因此也只能在邮局加油站加油。

站总数等于n。在第 i 个加油站为汽车加油的量不超过 ai 升汽油。此外,每个加油站最多只能给汽车加油一次。另外,第 1 站和第 2 站之间的距离为 b1 公里,第 2 站和第 3 站之间的距离为 b2 公里,……,第 (n - 1) 站和第 n 站之间的距离为 bn - 1 公里,第 n 站和第 1 站之间的距离为 bn 公里。佩蒂亚叔叔的高科技汽车每公里仅使用一升汽油。已知站点的位置使得所有 ai 的总和等于所有 bi 的总和。第 i 个加油站和第 i 个邮局距离很近,因此它们之间的距离为 0 公里。

因此,很明显,如果我们从某些邮局出发,那么并不总是可以沿着环形道路行驶一圈。叔叔面临着这样的问题:早上他可以去哪些站,以便能够沿着环路正好骑一圈并参观沿途所有的邮局?

Petya 曾经参加过编程课程,他自愿帮助他的叔叔,但他的知识不够,所以他要求你帮助他编写解决所提出问题的程序。

输入

第一行包含整数 n (1 ≤ n ≤ 105)。第二行包含 n 个整数 ai — 第 i 个加油站的汽油量。第三行包含n个整数b1,b2,...,bn。它们分别是第 1 个和第 2 个加油站之间、第 2 个和第 3 个加油站之间、...、第 n 个和第 1 个加油站之间的距离。所有bi之和等于所有ai之和且不大于109。每个数字ai、bi不小于1且不大于109。

输出

在第一行打印数字 k — 可能的邮局数量,汽车可以从这些邮局沿着环形道路行驶一圈。在第二行按升序打印 k 个数字——汽车可以从哪个办公室出发。

示例

输入 #1

4
1 7 2 3
8 1 1 3

输出 #1

2
2 4

输入 #2

8
1 2 1 2 1 2 1 2
2 1 2 1 2 1 2 1

输出 #2

8
1 2 3 4 5 6 7 8