Rank Promotion

Quiz Solver is a popular online computer game. Each time a player opens the mobile app, a new quiz appears. The player submits an answer, which is judged correct or incorrect and recorded in the database. When a player shows high accuracy over many quizzes, the player's rank is promoted.

Player ranks are non-negative integers, and every player starts at rank $0$. Promotion is defined by an integer $c$ and a rational number $p/q$. After the $e$-th quiz, the player's rank increases by one if there is an integer $s$ such that:

• $1 \le s \le e - c + 1$.
• The player was already at the current rank before the $s$-th quiz started.
• The ratio of correct answers from the $s$-th through the $e$-th quiz is at least $p/q$.

Otherwise, the rank stays the same.

One day, the administrator of Quiz Solver found that the rank data of the players was lost in a database failure. The log of quiz solving records was completely intact. Recompute each player's rank from that player's solving records.

The input is a single test case in this format.

$n$ $c$ $p$ $q$

$S_1$ $\cdots$ $S_n$

The first line has four integers with $1 \le n \le 5 \times 10^5$, $1 \le c \le 200$, and $1 \le p \le q \le 5 \times 10^5$. $n$ is the number of quizzes answered by one player, and $c$, $p$, $q$ have the meanings given in the problem statement. Each $S_i$ is Y if the answer to the $i$-th quiz was correct, or N if it was incorrect.

Output the player's final rank after the $n$-th quiz on one line.

In Sample Input 1, the player is promoted to rank 1 after the fourth quiz, because the correct ratio 3/4 is higher than $p/q = 4/7$. No promotion happens at the third quiz, since only three quizzes have been answered, fewer than $c = 4$. After the eleventh quiz, the player is promoted to rank 2.

Figure B.1. Rank promotion timings for Sample Input 1