Таблица

Рассмотрим прямоугольную таблицу размером n×m. Занумеруем строки таблицы числами от 1 до n, а столбцы – числами от 1 до m. Будем такую таблицу последовательно заполнять числами следующим образом.

Обозначим через a_ij число, стоящее на пересечении i-ой строки и j-ого столбца. Первая строка таблицы заполняется заданными числами – a₁₁, a₁₂, …, a_1m. Затем заполняются строки с номерами от 2 до n. Число a_ij вычисляется как сумма всех чисел таблицы, находящихся в «треугольнике» над элементом a_ij. Все вычисления при этом выполняются по модулю r.

Более точно, значение a_ij вычисляется по следующей формуле:

Например, если таблица состоит из трех строк и четырех столбцов, и первая строка состоит из чисел 2,3,4,5, а r = 40 то для этих исходных данных таблица будет выглядеть следующим образом (взятие по модулю показано только там, где оно приводит к изменению числа):

Требуется написать программу, которая по заданной первой строке таблицы (a₁₁, a₁₂, …, a_1m), вычисляет последнюю строку, как описано выше.

Входные данные

Первая строка входного файла INPUT.TXT содержит числа n, m и r (2 ≤ n, m ≤ 2000, 2 ≤ r ≤ 10⁹) – число строк и столбцов таблицы соответственно, а так же число, по модулю которого надо посчитать ответ. Следующая строка содержит m целых чисел – первую строку таблицы: a₁₁, a₁₂, …, a_1m. Все a_1i неотрицательны и не превосходят 10⁹.

Выходные данные

В первой строке выходного файла OUTPUT.TXT необходимо вывести m чисел – последнюю строку таблицы: a_n1, a_n2, …, a_nm.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]