Có n camera quan sát, đánh số tuần tự từ 1 đến n, được đặt lần lượt thẳng hàng trên đường cao tốc từ Tây sang Đông. Camera thứ i được đặt ở độ cao hi và hướng về một trong hai hướng: Tây hoặc Đông. Camera thứ i có thể quan sát được camera thứ j nếu camera thứ i nhìn về phía camera thứ j và không có bất kỳ camera nào ở giữa hai camera này có độ cao vượt quá độ cao của camera thứ j.

Yêu cầu: Cho biết độ cao và hướng nhìn của n camera. Hãy cho biết mỗi camera có thể quan sát được bao nhiêu camera khác.

Input

• Dòng đầu chứa số nguyên dương 𝑛;
• Dòng thứ hai gồm n số nguyên dương ℎ[1], ℎ[2], … , ℎ[𝑛] là độ cao của mỗi camera (1 ≤ℎ[𝑘] ≤10^9 với 1 ≤ 𝑘 ≤ 𝑛);
• Dòng thứ ba chứa một xâu gồm n ký tự cho biết hướng nhìn của các camera với quy ước: W là nhìn sang hướng Tây, E là nhìn sang hướng Đông.

Output

Gồm một dòng ghi n số tự nhiên, số thứ 𝑘 cho biết số lượng camera mà camera thứ 𝑘 (𝑘 = 1,2, … , 𝑛) có thể quan sát được.

Sample Input

5 
1 2 2 3 1 
EEWWE

Sample Output

3 2 1 2 0

Ràng buộc

- Có 20% số test có 𝑛 ≤ 10^3; 
- Có 40% số test còn lại có 𝑛 ≤ 10^5.