Polygonal Chain

• Time limit: 1.00 s
• Memory limit: 512 MB

A polygonal chain consists of $n$ horizontal line segments and $n-1$ vertical line segments. The horizontal segments are numbered $1,2,\dots,n$ in order, and adjacent horizontal segments are connected by vertical segments. The first horizontal segment is directed from left to right and the following horizontal segments alternate in opposing directions.

The lengths of the horizontal lines and the directions of the vertical lines are known but the lengths of the vertical lines are not. Can the vertical lengths be chosen such that the polygonal chain does not intersect itself?

Input

The first line of input contains one integer: the number of horizontal line segments $n$.

The second line describes the lengths of the horizontal segments, $p_1, p_2, \dots, p_n$.

The final line contains a string with $n-1$ characters. Each character describes the direction of the respective horizontal line: U (up) or D (down).

Output

On the first line, print YES if a solution exists and NO otherwise.

If it does exist, also print $n-1$ positive integers describing the solution: the length of each vertical line. The lengths may not exceed $10^9$ but you may print any valid solution.

Example

Input:
4
4 3 2 3
UDD

Output:
YES
3 1 1

Explanation: The length and direction of each line segment is marked in the image.

Subtask 1 (7 points)

• $2 \le n \le 8$
  
• $1 \le p_i \le 10$
  

Subtask 2 (19 points)

• $2 \le n \le 15$
  
• $1 \le p_i \le 100$
  

Subtask 3 (15 points)

• $2 \le n \le 1000$
  
• $1 \le p_i \le 2$
  
• The polygonal chain fits in an area which is two units wide.
  

Subtask 4 (33 points)

• $2 \le n \le 1000$
  
• $1 \le p_i \le 10^6$
  

Subtask 5 (26 points)

• $2 \leq n \leq 10^5$
  
• $1 \leq p_i \leq 10^9$