Multi
Задача от Интервюта
Time Limit: 0.1s, Memory Limit: 64MiB
Докато играеше на DotA, Ели сглоби много странен предмет. Когато е активиран, той променя силата на всички приятелски единици в определен радиус в зависимост от първоначалната сила на всички други единици без текущата. По-точно ако има N единици (включително героя на Ели), имащи първоначална сила A1, A2, ..., AN, то след активирането на предмета всяка единица има сила равна на произведението на силите на всички други единици. Тоест силата на i-тата единица ще стане равна на A1 * A2 * ... * Ai-1 * Ai+1 * ... * AN-1 * AN.

По зададени броят на единиците N и началните им сили А1, А2, ..., АN, изчислете силата на всяка от единиците след активирането на предмета.
Вход
Стандартният вход ще се състои от два реда, като на първия ще бъдат зададени броят единици N, а на втория - числата А1, А2, ..., АN.
Изход
На единствен ред на стандартния изход изведете по N числа – крайната сила на всяка от единиците (в същия ред, в който са зададени във входа). Тъй като тези числа могат да бъдат много големи, изпечатайте само техните последни девет цифри (остатъка им при деление на 1,000,000,000).
Ограничения
  • 1 ≤ N ≤ 100,000
  • 1 ≤ Ai ≤ 1,000,000
Примерен Вход Примерен Изход
5 5 1 3 2 7 42 210 70 105 30
8 42 666 1337 13 1234 111111 4321 7819 810246996 645691252 402416136 617721064 787706948 238635512 323080392 284567128
В първия пример за първа позиция имаме 1 * 3 * 2 * 7 = 42, за втора имаме 5 * 3 * 2 * 7 = 210 и т.н. Във втория пример не забравяйте да печатате само остатъка на числата при деление на 1,000,000,000.
Мрън!