$N$ коров $(1 \le N \le 50,000)$ с удобными номерами $1..N$ учат шифрование. Изучив примеры, решили создать своё! Неопытные, выбрали простой алгоритм:
Корова $i$ получает начальное число $C_i$ $(0 \le C_i < 90,000,000)$, все параллельно выполняют:
- Сначала каждая суммирует числа остальных $N-1$ коров.
- Когда все закончат, каждая заменяет своё число вычисленной суммой. Во избежание огромных чисел хранят остаток по модулю $98,765,431$.
В ноябре рассказали лосю Canmuu, он был впечатлён.
Туманным вечером накануне Рождества Canmuu сказал:
«Слишком легко взломать! Повторяйте $T$ раз $(1 \le T \le 1,414,213,562)$».
Коровы огорчились столькими повторениями скучного алгоритма. После часов споров с Canmuu договорились: вы вычисляете числа после шифрования!
*Для первых 10 посылок задачи будет дополнительная обратная связь.
Входные данные
Читайте стандартный ввод.
- Строка 1: целые $N$, $T$ через пробел.
- Строки $2..N+1$: строка $i+1$ содержит целое $C_i$.
Выходные данные
Пишите в стандартный вывод.
- Строки $1..N$: строка $i$ содержит целое, число коровы $i$ после шифрования по модулю $98,765,431$.
Примеры
Входные данные 1
3 4 1 0 4
Выходные данные 1
26 25 29
Примечание
Три коровы, начальные $1$, $0$, $4$, четыре повторения.
Таблица чисел коров по раундам:
| Раунд | Корова $1$ | Корова $2$ | Корова $3$ |
|---|---|---|---|
| $0$ | $1$ | $0$ | $4$ |
| $1$ | $4$ | $5$ | $1$ |
| $2$ | $6$ | $5$ | $9$ |
| $3$ | $14$ | $15$ | $11$ |
| $4$ | $26$ | $25$ | $29$ |
Благодарности: Neal Wu, 2007