D2. Шифрование сообщений
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Умный Бобер из ABBYY придумал новый вид шифрования сообщений и хочет проверить его работу. Делать это вручную долго и трудоемко, поэтому он решил обратиться к участникам ABBYY Cup.

Сообщение представляет собой n целых чисел a1, a2, ..., an. Для шифрования используется ключ, который представляет собой m целых чисел b1, b2, ..., bm (m ≤ n). Все числа из сообщения и из ключа лежат в интервале от 0 до c - 1, включительно, и все последующие вычисления проводятся по модулю c.

Шифрование проводится в n - m + 1 этапов. На первом этапе к каждому из чисел a1, a2, ..., am прибавляются соответствующие числа b1, b2, ..., bm. На втором этапе к числам a2, a3, ..., am + 1 (измененным на предыдущем этапе) прибавляются числа b1, b2, ..., bm. И так далее: на этапе номер i к числам ai, ai + 1, ..., ai + m - 1 прибавляются числа b1, b2, ..., bm. Результатом шифрования является последовательность a1, a2, ..., an после n - m + 1 этапов шифрования.

Помогите Бобру: напишите программу, которая будет осуществлять шифрование сообщений описанным способом.

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

Первая строка входных данных содержит три целых числа n, m и c, разделенных единичными пробелами.

Вторая строка входных данных содержит n целых чисел ai (0 ≤ ai < c), разделенных единичными пробелами, — исходное сообщение.

Третья строка входных данных содержит m целых чисел bi (0 ≤ bi < c), разделенных единичными пробелами, — ключ шифрования.

Ограничения на входные данные для получения 30 баллов:

  • 1 ≤ m ≤ n ≤ 103
  • 1 ≤ c ≤ 103

Ограничения на входные данные для получения 100 баллов:

  • 1 ≤ m ≤ n ≤ 105
  • 1 ≤ c ≤ 103
Выходные данные

Выведите n целых чисел, разделенных пробелами, — результат шифрования сообщения.

Примеры
Входные данные
4 3 2
1 1 1 1
1 1 1
Выходные данные
0 1 1 0
Входные данные
3 1 5
1 2 3
4
Выходные данные
0 1 2
Примечание

В первом примере шифрование проводится в два этапа: после первого этапа a = (0, 0, 0, 1) (вычисления производятся по модулю 2), после второго — a = (0, 1, 1, 0), что и будет ответом.