After a long year of preparing presents for all of the little children of the world, Santa's elves are ready to go on their annual cottage vacation in Santa's private luxury winter retreat!
Santa's winter retreat consists of cottages numbered from to . In addition, the cottages are arranged in a circular fashion with the -th cottage being adjacent to the -th one for all and the first cottage being adjacent to the -th one.
Initially, the -th cottage has exactly elves in it. Since the elves want to check out the new features installed in the cottages, they will follow the following procedure for each of the next hours of their stay:
- Simultaneously, exactly elf from each cottage will move to the next cottage in the circle if and only if the cottage has a positive number of elves. Note that elves from cottage would move to cottage .
After repeating this procedure exactly times, please report to Santa how many elves are in each cottage!
The first line contains two space-separated integers and , denoting the number of cottages and hours respectively.
The second line contains space-separated integers , the initial number of elves in each cottage.
Output space-separated integers, the -th being the number of elves after hours at the -th cottage.
5 3 1 0 0 1 0
0 1 0 1 0