欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~

问题 1085. -- 锘爷与粉丝

1085: 锘爷与粉丝

时间限制: 3 Sec  内存限制: 128 MB
提交: 11  解决: 1
[提交][状态][讨论版]

题目描述

大家都知道锘爷是西电最吊的ACMer,所以都来Orz他。锘爷的宿舍周围有2k个建筑物,排成一个环,按顺时针顺序编号为0~2k-1,每个建筑物里面都有一些ACMerOrz锘爷。 下图是k=2的情况。

因为锘爷太吊了,每个正在Orz锘爷的ACMer每分钟都会叫来更多的ACMer,一起Orz锘爷。对于每个ACMer,在一单位时间内,他会叫来biACMer,到顺时针方向距离他自己i的建筑物去Orz锘爷(0≤i<2k)。
我们已经知道一开始在编号为i0≤i<2k)的建筑物有aiACMerOrz锘爷,那么t单位时间后,每个建筑物中有多少ACMerOrz锘爷呢?

因为Orz锘爷的ACMer很多,而且人数随t指数增加,最后会多到高精度都存不下的地步,你只要求出答案对99993601的模就行了。

对于100%的数据有0≤k≤100≤ai, bi<999936010≤t≤109

输入

多组数据(最多20组),以EOF结束。

每组数据,第一行2个整数k, t,以空格分割。
第二行2k个整数ai,以空格分割。
第三行2k个整数bi,以空格分割。

输出

对于每组数据,先输出一行”Orz”(不含引号),之后输出一行,包含2k个整数,表示t分钟后第0, 1, …, (2k-1)个建筑中Orz锘爷的人数对99993601的模,用空格分割。

样例输入

0 2
1
1
2 2
1 0 0 0
0 0 0 1

样例输出

Orz
4
Orz
1 0 1 2

提示

样例解释:

对于第一组样例,1ACMer在第1分钟叫来了另一个ACMer,第2分钟两个ACMer各叫来1ACMer,最后共有4个。

对于第二组样例,位于0ACMer在第1分钟叫来另一个ACMer,位于位置3。第2分钟两人各叫来1ACMer,分别位于位置32(从3顺时针数3个是3-0-1-2)。所以最后位置01ACMer,位置21ACMer,位置32ACMer


注意:

不要把”Orz”打成”orz”或者”OTZ”

行末不要有多余的空格。

来源

[提交][状态][讨论版]