题目描述

You are switching from computer science to agriculture and your new job involves growing sunflowers in an underground greenhouse. The greenhouse contains n sunflower plants arranged in a straight line and numbered with integers 1 through n, from left to right. Two lamps provide the light and heat the sunflowers need to grow: the lamp A is positioned at the left end, while the lamp B is positioned at the right end of the line.

Every day exactly one of the lamps is on, causing all of the sunflowers to turn towards the light and some of them to grow. The sunflower will grow if and only if the sunflower directly in front of it (towards the light) is higher. The growth is continuous with a uniform rate of exactly 1 centimeter per day. Notice that, when a sunflower starts to grow, it may cause the sunflower directly behind it to start to grow instantaneously.

You are given initial heights of the sunflowers and the lamp schedule for the following m day period, find the final heights of all the sunflowers.

输入格式

The first line contains two integers n and m (1≤n, m≤300000) – the number of sunflowers and the number of days in the period. The following line contains n integers h1,h2,...,hn (1≤ hk ≤$10^9$) – the initial heights (in centimeters) of the sunflowers, from left to right.

The following line contains a string consisting of exactly m characters A or B – the lamp schedule starting from the first day of the period.

输出格式

Output a single line containing n integers – the final heights of the sunflowers, from left to right.

题目大意

有两盏灯在最左边和最右边。有 $n$ 盏向日葵在中间。

每一天都一定会有一个灯开着。向日葵仅仅当它前面的（朝向灯的方向）向日葵比它高时它才会成长，成长速度为 $1$。注意，当一个向日葵开始成长时，它还可能使得在它后面的向日葵瞬间成长。

给你每株向日葵的高度，还有每天开灯的时间表，求出最后所有的向日葵的高度。

$n,m\le 3\times 10^5$，$h \leq 10^9$。

6 5 
4 3 5 3 6 6 
BABAA

5 5 6 6 6 6

提示

Central Europe Regional Contest 2015 Problem G