你正从计算机科学转向农业，你的新工作是在一个地下温室里种植向日葵。温室里有 $n$ 株向日葵，排成一条直线，从左到右依次编号为 $1$ 到 $n$。两盏灯为向日葵提供生长所需的光和热：灯 $A$ 位于左端，灯 $B$ 位于右端。

每天恰好有一盏灯开启，这会导致所有的向日葵转向光源，其中一些会生长。当且仅当向日葵正前方（朝向光源的方向）的向日葵更高时，该向日葵才会生长。生长是连续的，速率恒定为每天正好 $1$ 厘米。注意，当一株向日葵开始生长时，它可能会导致其后方紧邻的向日葵立即开始生长。

示例输入：周期前三天的生长情况

给定向日葵的初始高度以及接下来 $m$ 天的灯光计划，求出所有向日葵的最终高度。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 300\,000$)，分别表示向日葵的数量和周期内的天数。下一行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$ ($1 \le h_k \le 10^9$)，表示从左到右向日葵的初始高度（单位为厘米）。

最后一行包含一个由 $m$ 个字符 'A' 或 'B' 组成的字符串，表示从周期第一天开始的灯光计划。

输出格式

输出一行，包含 $n$ 个整数，表示从左到右向日葵的最终高度。

样例

输入 1

6 5
4 3 5 3 6 6
BABAA

输出 1

5 5 6 6 6 6