Kravaiche
Time limit1sMemory limit1024 MB
Choose a non-empty subset of the n houses whose total equals a multiple of k, and print the house indices.
- Level
Medium7 of 10
- Topics
- Prefix sum, Combinatorics, Math, Hash map
- Solved
- No attempts yet
Problem
By an old tradition, the koledari of the village of Kyulevcha receive kravaiche (traditional pastries) from the homeowners of the village at Christmas. Each homeowner has decided how many kravaiche to give. This number does not depend on the number of koledari and is the same every year. It is possible that the kravaiche from some house are not enough for all the koledari. So the koledari decided to gather all the kravaiche in one place and in the morning divide them equally, if that is possible.
The koledari know how many kravaiche they will take from each house. They must decide which houses to visit so that the total number of kravaiche received can be divided equally among them.
Help them by writing a program kravaiche that decides which houses the koledari should visit so that they can divide the kravaiche they take equally.
Input
The first line of the standard input contains two numbers: k, the number of koledari, and n, the number of houses in the village. Then follow n numbers: a1, a2, a3, …, an, where ai is the number of kravaiche the koledari will take if they visit the i-th house.
Output
On one line of the standard output, print the numbers of the houses the koledari should visit so that they can divide the collected kravaiche equally (the first house is number 1, the second is number 2, and so on). If more than one solution exists, print any of them. If the problem has no solution, print "no kravaiche".
Constraints
- 1 ≤ k ≤ n ≤ 100000
- 1 ≤ ai ≤ 100000