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),这就是答案。