Задача №1150. Таблица
Рассмотрим прямоугольную таблицу размером n m. Занумеруем строки таблицы числами от 1 до n, а столбцы – числами от 1 до m. Будем такую таблицу последовательно заполнять числами следующим образом.
Обозначим через aij число, стоящее на пересечении i-ой строки и j-ого столбца. Первая строка таблицы заполняется заданными числами – a11, a12, …, a1m. Затем заполняются строки с номерами от 2 до n. Число aij вычисляется как сумма всех чисел таблицы, находящихся в «треугольнике» над элементом aij. Все вычисления при этом выполняются по модулю r.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| ai,j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Более точно, значение aij вычисляется по следующей формуле:
Например, если таблица состоит из трех строк и четырех столбцов, и первая строка состоит из чисел 2,3,4,5, а r = 40 то для этих исходных данных таблица будет выглядеть следующим образом (взятие по модулю показано только там, где оно приводит к изменению числа):
| 2 | 3 | 4 | 5 |
| 5 = 2 + 3 | 9 = 2 + 3 + 4 | 12 = 3 + 4 + 5 | 9 = 4 + 5 |
| 23 = 2 + 3 + 4 + 5 + 9 | 0 = (2 + 3 + 4 + 5 + 5 + 9 + 12) mod 40 = 40 mod 40 | 4 = (2 + 3 + 4 + 5 + 9 + 12 + 9) mod 40 = 44 mod 40 | 33 = 3 + 4 + 5 + 12 + 9 |
Требуется написать программу, которая по заданной первой строке таблицы (a11, a12, …, a1m), вычисляет последнюю строку, как описано выше.
Первая строка входного файла содержит числа n, m и r (2 ≤ n, m ≤ 2000, 2 ≤ r ≤ 109) – число строк и столбцов таблицы соответственно, а так же число, по модулю которого надо посчитать ответ. Следующая строка содержит m целых чисел – первую строку таблицы: a11, a12, …, a1m. Все a1i неотрицательны и не превосходят 109.
В первой строке выходного файла необходимо вывести m чисел – последнюю строку таблицы: an1, an2, …, anm.
2 3 10 1 2 3
3 6 5
3 3 10 1 1 1
8 0 8
3 4 40 2 3 4 5
23 0 4 33