Весь рік Вася не ходив до університету, тому не здав екзамени, і його відрахували. Так він потрапив до армії. А одне із самих популярних занять в армії — стояти в строю.

У Васиному взводі n солдат, рахуючи його. Солдати стоять в одну шеренгу, кожен із них дивиться або вліво, або вправо, а також має свій порядковий номер від 1 до n, що дорівнює його місцю в шерензі. Ріст i-го солдата дорівнює hi. Вася вважає, що солдат з номером i бачить солдата з номером j, якщо виконується наступні умови:

• солдат i дивиться в сторону солдата j;

• всі солдати, що стоять між ними, не вище солдата j.

Так, наприклад, якщо в шерензі стоять 4 солдата ростом h1 = 178, h2 = 180, h3 = 170, h4 = 190, а також всі солдати дивляться вліво, то 2-й солдат буде бачити тільки 1-го, 3-й — тільки 2-го (так як між ним і першим є більш високий другий солдат), 4-й буде бачити 2-го і 3-го солдат.

Так як зайнятися в строю все одно нічим, Вася хоче порахувати, скільки людей бачить кожен із солдат.

Вхідні дані

Перший рядок вхідних даних містить число n — кількість солдат в шерензі (1 ≤ n ≤ 105).

Другий рядок містить n чисел h1; h2; ... ; hn — ріст солдат в шерензі (1 ≤ hi ≤ 109).

Третій рядок містить n символів, що описує напрямок, в який дивляться солдати:

i-й символ дорівнює «L», якщо i-й солдат дивиться вліво, тобто може побачити тільки солдат з номерами 1; 2; ... ; i - 1, або «R», якщо i-й солдат дивиться вправо може побачити тільки солдат з номерами i + 1; i + 2; ... ; n.

Вихідні дані

Виведіть n цілих чисел, i-те з виведених чисел повинне дорівнювати кількості солдат, яких бачить i-й солдат в строю.