Description

Nayiz最近在家闲得没事，一口气买进了 n棵向日葵，并把它们都放进了一个温棚中。

温棚中植物的阳光来源是温棚两侧的日照灯，假设位于左侧的日照灯是灯4,右侧的日照灯是灯B,则 在Nayiz的控制下，每天会恰好开一盏日照灯4或B ,当然向日葵总是会面向日照灯的。

而每天一颗向日葵会长高一个单位当且仅当它前面的向日葵（如果有的话）比它高，避免了灯光的直接照 射。注意，如果一颗向日葵开始生长一个单位时，它可能会导致它后面的向日葵开始马上生长。 （图见PDF文件）

图1:向日葵生长的例子 假设给出n棵向日葵的初始高度，以及往后m天Nayiz开灯的控制，你能计算出m天后每颗向日葵的 高度吗？

Input Format

输人第一行两个整数n,m,表示向日葵的数量以及需要计算的天数。

第二行共n个整数，其中第i个整数hi表示第i棵向日葵的初始高度。

第三行是一个长度为m的字符串s,其中第i个字符si表示第i天Nayiz开的是灯A还是灯B.

Output Format

输出n个整数，表示m天后每颗向日葵的高度。

Sample

样例输人

10 10  
5 7 8 9 6 3 2 1 4 5  
AABBABBAAB
10 10  
8 7 4 1 5 9 5 4 7 8  
ABABBABAAA

样例输出

9999988888
8888999999

Hint

对于20%的数据，1 =< n,m <= 2000。

对于另外20%的数据，si = A。

对于 100% 的数据，1 =< n,m <= 300000, 1 =<hi <= 10^9。