Greenhouse Growth

You have left computer science for agriculture, and your new job is growing sunflowers in an underground greenhouse. The greenhouse holds $n$ sunflowers planted in a straight line, numbered $1$ through $n$ from left to right. Two lamps supply the light and heat the sunflowers need. Lamp $A$ is at the left end of the line, lamp $B$ is at the right end.

Every day exactly one of the two lamps is on. All the sunflowers turn towards the light, and some of them grow. A sunflower grows if and only if the sunflower directly in front of it, towards the light, is taller. The growth is continuous at a uniform rate of exactly $1$ centimeter per day. When a sunflower starts to grow, the sunflower directly behind it can start to grow at that same instant.

On a day with lamp $A$, the sunflower directly in front of sunflower $k$ is sunflower $k-1$. On a day with lamp $B$ it is sunflower $k+1$. The sunflower at the end next to the lit lamp has nothing in front of it, so it does not grow that day.

Growth during the first three days of the period for one example input

You are given the initial heights of the sunflowers and the lamp schedule for the next $m$ days. Find the height of every sunflower after the last day.

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 300\,000$), the number of sunflowers and the number of days in the period.

The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_k \le 10^9$), the initial heights of the sunflowers in centimeters, from left to right.

The third line contains a string of exactly $m$ characters A or B. The $i$-th character is the lamp that is on during day $i$, counting from the first day of the period.

Print one line with $n$ integers, the heights of the sunflowers after the last day, from left to right, separated by single spaces.