← 返回题目列表

Codeforces · 177/D2

D2. 加密消息

中文机器翻译题面 查看原题

ABBYY 的 Smart Beaver 发明了一种新的消息加密方法,现在想要检查其性能。手动检查既耗时又烦人,因此他决定向 ABBYY 杯参赛者寻求帮助。

一条消息是一个由 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。加密的结果是经过n - m + 1步后的序列a1,a2,...,an。

帮助海狸编写一个程序,以所描述的方式加密消息。

输入

第一个输入行包含三个整数 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 个空格分隔的整数 — 加密原始消息的结果。

示例

输入 #1

4 3 2
1 1 1 1
1 1 1

输出 #1

0 1 1 0

输入 #2

3 1 5
1 2 3
4

输出 #2

0 1 2

注意

在第一个示例中,加密分两步执行:第一步之后 a = (0, 0, 0, 1)(请记住,计算以模 2 执行),第二步之后 a = (0, 1, 1, 0),这就是答案。