Greenhouse Growth#7778
You are switching from computer science to agriculture, and your new job involves growing sunflowers in an underground greenhouse. The greenhouse contains sunflower plants arranged in a straight line and numbered with integers from to , from left to right. Two lamps provide the light and heat that the sunflowers need to grow: lamp is positioned at the left end of the line, while lamp is positioned at the right end.
Every day, exactly one of the lamps is turned on, causing all the sunflowers to turn towards the light, and some of them to grow. A sunflower will grow if and only if the sunflower directly in front of it (in the direction of the light) is taller. Growth is continuous at a uniform rate of exactly centimeter per day.
Notice that when a sunflower starts to grow, it may cause the sunflower directly behind it to start growing instantaneously as well.
You are given the initial heights of the sunflowers and the lamp schedule for the following -day period. Determine the final heights of all the sunflowers.
The first line contains two integers and m~(1 \le n, m \le 300,000) — the number of sunflowers and the number of days in the period.
The following line contains integers h_1, h_2, \ldots, h_n~(1 \le h_k \le 10^9) — the initial heights of the sunflowers, given from left to right.
The following line contains a string consisting of exactly characters, each of which is either or . The -th character specifies which lamp is turned on during the -th day of the period.
Print one line containing integers — the final heights of the sunflowers, from left to right.
Example 1