题目描述

你从计算机科学转向农业，你的新工作包括在一个地下温室种植向日葵。在温室中有 $n$ 个排列在一条直线的向日葵植株，从左向右编号为 $1$ 到 $n$。有 $A,B$ 这 $2$ 个照射器为向日葵的生长提供光和热，且照射器 $A,B$ 分别放置在向日葵的左右两端。

每天只有 $1$ 个照射器被打开，使所有向日葵转向光源，并使部分向日葵生长。向日葵会生长当且仅当其朝向的相邻植株比它更高，其每天的生长高度为 $1$ 厘米。请注意，一个植株的生长将使其背后的植株立刻开始生长。

你将被给出向日葵的初始高度和接下来 $m$ 天的光照计划，请计算所有向日葵最终的高度。

输入格式

第一行有 $2$ 个整数 $n$ 和 $m$——植株数和天数。

接下来一行包括 $n$ 个整数 $h_1$，$h_2$，$\dots$，$h_n$——从左到右向日葵的初始高度。

接下来一行包括一个仅含字母 A/B，长度为 $m$ 的字符串——从第一天开始的光照计划。

输出格式

$n$ 个整数——从左到右每株向日葵最终的高度。

6 5
4 3 5 3 6 6
BABAA

5 5 6 6 6 6

数据范围与约定

对于 $100 \%$ 的数据，$1 \le n, m \le 3\times 10^5$，$1 \le h_k \le 10^9$