Sunflower Growth Simulation in an Underground Greenhouse

You have been transferred from computer science to agriculture. In your new job you are managing an underground greenhouse where n sunflower plants are arranged in a straight line and numbered 1 through n (from left to right). There are two lamps: lamp A at the left end and lamp B at the right end. Every day exactly one lamp is turned on. When a lamp is on, all the sunflowers turn toward that lamp. The rule for growth on that day is as follows:

• If lamp A is on, then for each plant i (2 ≤ i ≤ n), the plant will grow if and only if the plant immediately to its left (plant i-1) is higher than it.
• If lamp B is on, then for each plant i (1 ≤ i ≤ n-1), the plant will grow if and only if the plant immediately to its right (plant i+1) is higher than it.

The growth process is continuous over one day at a uniform rate of 1 centimeter per day. In addition, when a sunflower starts growing it may cause the sunflower immediately behind it (i.e. further away from the light source) to start growing instantaneously. More formally, consider a day when the lamp is on. For the appropriate direction (leftward for A and rightward for B), define for each affected plant a start time s_i (with 0 ≤ s_i < 1) at which it begins growing. Its final height at the end of the day will be:

if it grows, and remains h_i if it does not. The growth start times are determined as follows for a day:

When lamp A is on:

1. Plant 1 has no plant in front of it and will not grow.
2. For each plant i (2 ≤ i ≤ n):
   • If plant i-1 did not grow (remained constant), then plant i will begin growing at time 0 if and only if \(h_{i-1} > h_i\). Otherwise, it does not grow.
   • If plant i-1 did grow starting at time \(s_{i-1}\), its height at time \(t\) is \(h_{i-1} + (t - s_{i-1})\) for \(t \ge s_{i-1}\). Then plant i will start growing at the smallest time \(t\) satisfying $$h_{i-1} + (t - s_{i-1}) > h_i.$$ This gives \(s_i = \max(0, h_i - h_{i-1} + s_{i-1})\) if \(s_i < 1\); otherwise, plant i does not grow.

When lamp B is on:

1. Plant n does not grow.
2. For each plant i (from n-1 down to 1):
   • If plant i+1 did not grow, then plant i will start growing at time 0 if and only if \(h_{i+1} > h_i\). Otherwise, it does not grow.
   • If plant i+1 did grow starting at time \(s_{i+1}\), then plant i will start growing at \(s_i = \max(0, h_i - h_{i+1} + s_{i+1})\) provided \(s_i < 1\); otherwise, it does not grow.

You are given the initial heights of the sunflowers and a lamp schedule for the next m days. For each day, update the heights according to the day’s lamp (either A or B) using the above rules. Output the final heights of all sunflowers after m days.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10⁵), the number of sunflowers and the number of days.

The second line contains n integers representing the initial heights of the sunflowers.

The third line contains a string of length m consisting only of characters 'A' and 'B', representing the lamp that is turned on each day.

outputFormat

Output a single line with n numbers, the final heights of the sunflowers after m days. The heights should be output in order from left to right, separated by spaces.

sample

5 1
5 4 3 2 1
A

5 5 4 3 2