Migrated from Lutece 1172 三句话题意

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

有n个数围成一圈，每次操作后每个数变成和他距离在d以内的数字之和，求k次操作后每个数字模m分别是多少~

Input

第一行四个数n,m,d,k (1 ≤ n ≤ 500, 1 ≤ m ≤ 1 000 000, 0 ≤ d < n / 2 , 1 ≤ k ≤ 10 000 000),第二行有n个数，每个的大小都在0 ~ m-1之间。

Output

一行n个数，表示结果。

Samples

5 3 1 1
1 2 2 1 2

2 2 2 2 1

5 3 1 10
1 2 2 1 2

2 0 0 2 2

Note

Resources

2015 UESTC ACM Training for Math