J21 习题-4 欢乐万圣节

题目描述

每年万圣节都有同样的问题：无论有多少孩子来拜访，每个邻居都只愿意在那一天给他一定数量的糖果，所以如果太晚了，孩子可能一无所获。为了避免冲突，孩子们决定把所有的糖果放在一起，然后在自己中间平均分配。从去年万圣节的经历中，他们知道从每个邻居那里得到多少糖果。因为他们更关心公平而不是他们得到的糖果数量，所以他们想选择邻居的一个连续子集来拜访，这样在分享时，每个孩子都会得到相同数量的糖果。如果他们还有不能分的糖果，他们将不会满意。

你的工作是帮助孩子并提出解决方案。

输入格式

输入包含几个测试用例。

每个测试用例的第一行包含两个整数 $c$ 和 $n$，表示儿童数量和邻居数量。

下一行包含 $n$ 个空格分隔的整数 $a_1,a_2,\ldots a_n$，其中 $a_i$ 表示孩子访问邻居i时获得的糖果数量。

最后一个测试用例后面是两个零。

输出格式

对于每个测试用例输出，一行包含孩子应该选择的邻居的索引（这里，索引 $i$ 对应于给出 $a_i$ 糖果总数的邻居 $i$ ）。如果没有解决办法，每个孩子至少得到一份甜食，那就打印“no sweets”。请注意，如果有几个解决方案，每个孩子至少得到一个糖果，你可以打印起始索引最小的一个。

样例输入

4 5
1 2 3 7 5
3 6
7 11 2 5 13 17
0 0

样例输出

3 5
2 3 4

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1 \le c \le n \le 100000$，$1 \le a_i \le 100000$ 。