You are given an array of N positive integers. Find a non-empty subset of numbers from the given array with the property that the sum of all numbers in the subset is divisible by N.
Input
On the first line of the input there will be number N. On the next line there will be N integer numbers with the semnification above.
Output
The number of elements in the solution, M, followed on the second line by M space separated numbers, denoting the positions of the elements of the input array which form the solution.
The positions are one-based.
Constraints
- 1 ≤ N ≤ 4 * 105
- 0 ≤ all elements in the array ≤ 109
- If there are multiple solutions, output any of them.
Sample
| Input | Output |
|---|---|
| 10 10 9 8 4 3 2 5 7 6 1 | 2 3 6 |
Consider the array of partial sums si = (a1 + a2 + … + ai) % N, (1 ≤ i ≤ N). Clearly, this array contains exactly N values between 0 and N-1.
If there exists an index i such that si = 0, then we can construct our subset by choosing all elements aj (1 ≤ j ≤ i). Otherwise, it follows from Dirichlet's principle that at least one value occurs multiple times. Denote by i and j two indices such that i < j, si = sj. Then we can construct our subset by choosing all elements ak (i < k ≤ j).
Note that this solution proves another property of the problem: besides the fact that any array of size N contains at least one subset whose sum is divisible by N, it also contains at least one such subset that is also a continuous subsequence of the array.
