온실 해바라기의 성장

전산학을 그만두고 농업으로 진로를 바꾼 당신은 지하 온실에서 해바라기를 키우는 일을 맡았다. 온실에는 해바라기 $n$그루가 일직선으로 심겨 있고, 왼쪽부터 오른쪽으로 $1$번부터 $n$번까지 번호가 붙어 있다. 해바라기가 자라는 데 필요한 빛과 열은 램프 두 개가 공급한다. 램프 $A$는 줄의 왼쪽 끝에, 램프 $B$는 줄의 오른쪽 끝에 있다.

매일 두 램프 중 정확히 하나만 켜진다. 램프가 켜지면 모든 해바라기가 빛이 오는 쪽으로 고개를 돌리고, 그중 일부가 자란다. 해바라기는 빛 쪽으로 바로 앞에 있는 해바라기가 자기보다 클 때에만 자란다. 성장은 연속적으로 일어나고, 속도는 하루에 정확히 $1$센티미터다. 해바라기 하나가 자라기 시작하면 바로 뒤에 있는 해바라기도 그 즉시 자라기 시작할 수 있다.

램프 $A$가 켜진 날에는 $k$번 해바라기의 바로 앞이 $k-1$번이고, 램프 $B$가 켜진 날에는 $k+1$번이다. 켜진 램프 쪽 끝에 있는 해바라기는 앞에 아무것도 없으므로 그날은 자라지 않는다.

예제 입력에서 기간의 처음 사흘 동안 일어나는 성장

해바라기의 처음 높이와 앞으로 $m$일 동안의 램프 일정이 주어진다. 마지막 날이 끝난 뒤 모든 해바라기의 높이를 구하라.

첫째 줄에 해바라기의 수 $n$과 기간의 길이 $m$이 주어진다 ($1 \le n, m \le 300\,000$).

둘째 줄에 해바라기의 처음 높이 $h_1, h_2, \dots, h_n$이 왼쪽부터 순서대로 주어진다. 단위는 센티미터이고 $1 \le h_k \le 10^9$이다.

셋째 줄에 길이가 정확히 $m$인 문자열이 주어진다. 이 문자열은 문자 A와 B로만 이루어져 있으며, $i$번째 문자는 첫날부터 세어 $i$번째 날에 켜지는 램프를 나타낸다.

마지막 날이 끝난 뒤 해바라기의 높이를 왼쪽부터 차례로 $n$개, 공백으로 구분해 한 줄에 출력한다.