跳动的水珠(csapc)

跳动的水珠(csapc)

测试数据来自 system/1477

描述

广场的夜晚并不宁静漆黑,蜂拥而至的人们早被那中央的喷泉所着迷。水柱时高时低,再伴上点轻盈的音乐,点缀些多彩的夜灯,激情、浪漫,全都弥漫在这湿润的空气中。留恋于此的人们多想在家就拥有这精神的盛宴。于是,一种拥有着跳动的水珠的音乐盒被设计诞生了。

音乐盒最关键的设计当然是在那水珠。不过设计者们已经有所打算,他们希望设计一个N*M大小的音乐盒,而它恰好被分成了N行M列相同大小的单元。每个单元都有各自的水珠跳动走向系统,上面所有的水珠都会按照这个时刻所设定的走向进行跳跃。走向指令有五种类型:C、U、D、L、R,分别表示这个位置上将出现X粒新的水珠,这个位置上的水珠将跳到上一个单元、下一个单元、左一个单元、右一个单元,如果水珠跳出了音乐盒,它将被装在音乐盒上的特殊装置回收。而且要注意的是,任意水珠之间都是互不影响的。

例如下面这个指令C只能产生1粒水珠,大小2*2的音乐盒:时刻1到时刻2,原本在左上的水珠跳到了左下,原本在左下的水珠跳到了右下,而原本没水珠的右下新出现一粒水珠,最后左下有一粒水珠而右下有两粒。

|0 0 C U| |1 0 D U| |0 0 C L| |1 0 ……
|0 0 C U| |1 0 R C| |1 2 C D| |2 0 ……
时刻0 时刻1 时刻2 时刻3
注:每个时刻左边的是当时每个单元上的水珠数目,右边的是当时的走向指令

音乐盒启动时,每个单元上都没有水珠,所有的单元都执行各自走向系统中设置的第一个指令,每L个为一个循环。

不过音乐盒每个单元上能够存在的水珠个数也是有限的,如果某个单元上的水珠数目一旦超过或恰好为P,则通过音乐盒的特殊装置,水珠瞬间会减少P粒。这样,音乐盒的每个单元可以始终保持在P粒水珠之内,也可以保证整个音乐盒不需要无限多的水来维持其正常工作。

音乐盒设计者希望在设计之初能够确定某个音乐盒在启动(时刻0)后的时刻T的状态,这也便是你的任务。对于音乐盒的任意一行,我们用一个PQ序列“P1 Q1 P2 Q2…Pk Qk”来描述其时刻T的状态,表示这一行的状态先是P1个Q1,再是P2个Q2……最后是Pk个Qk。当然,这里∑Pi=M,Pi≠0,Pi≠Pi+1。

格式

输入格式

第一行五个正整数N,M,X,P和T,分别表示音乐盒相关参数,以及你所求的时刻T。相邻数字之间由一个空格隔开。

接下来N行,每行M项内容,相邻两项之间有一个空格。每项内容先是一个整数Li,j表示音乐盒至上而下第i行,从左往右第j列的走向指令的循环节长度,然后是长度为Li,j的一个由C、U、D、L、R组成的字符串,描述指令序列的循环节,其中串的第一个字符是时刻0时那一个单元对应的指令。Li,j和串之间由一个空格隔开。

输出格式

共N行,每行一个PQ序列来描述这一行对应的状态,相邻两个数用一个空格隔开。

样例1

样例输入1

2 2 1 100 3
3 CDC 3 UUL
3 CRC 7 UCDLULL

样例输出1

1 1 1 0
1 2 1 0

提示

【数据范围】
对于60%的数据,保证N,M≤8且T≤10^4;
对于80%的数据,保证N,M≤8且T≤10^9;
对于50%的数据,保证所有的Lij都相等;
对于100%的数据,保证2≤N,M≤100,X,P,T≤10^9,Li,j是集合{3,7,9}中的一个,且拥有指令C的单元不超过20个(例如,样例拥有3个)。

信息

ID
1569
难度
(无)
分类
模拟 | 图结构 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者