- Time limit: 1.00 s
- Memory limit: 512 MB
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.
- $2 \le n \le 8$
- $1 \le p_i \le 10$
- $2 \le n \le 15$
- $1 \le p_i \le 100$
- $2 \le n \le 1000$
- $1 \le p_i \le 2$
- The polygonal chain fits in an area which is two units wide.
- $2 \le n \le 1000$
- $1 \le p_i \le 10^6$
- $2 \leq n \leq 10^5$
- $1 \leq p_i \leq 10^9$