描述

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

音乐盒最关键的设计当然是在那水珠。不过设计者们已经有所打算，他们希望设计一个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个）。