Description

Quiz Solver 是一款流行的在线电脑游戏。每次玩家打开游戏的移动应用程序，都会显示一个新的测验。玩家提交测验的答案，然后会被判断为正确或错误，结果会累积到数据库中。当玩家在多个测验中表现出高准确率时，玩家在游戏中的 等级 就会提升。

玩家等级是非负整数，每个玩家以等级 0 开始游戏。当玩家在足够长的测验序列中达到较高的正确率时，玩家将被提升到下一个等级。更精确地说，等级提升系统由两个参数定义：一个整数 $c$ 和一个有理数 $p/q$。在第 $e$ 个测验结束后，如果存在一个整数 $s$ 满足以下条件，玩家的等级会立即增加一：

• $1 \le s \le e - c + 1$。
• 玩家在第 $s$ 个测验开始之前已经处于当前等级。
• 从第 $s$ 个到第 $e$ 个测验的正确率高于或等于 $p/q$。

否则，等级保持不变。

有一天，Quiz Solver 的管理员发现由于数据库故障，玩家的等级数据丢失了。幸运的是，测验解答记录日志完全无损地保存了下来。你的任务是根据玩家的解答记录重新计算每个玩家的等级。

Input Format

输入由单个测试用例组成，格式如下。

$$\begin{aligned} &n\ c\ p\ q \\ &S_1 \cdots S_n \end{aligned}$$

第一行包含四个整数，满足以下约束：$1 \le n \le 5 \times 10^5$，$1 \le c \le 200$，以及 $1 \le p \le q \le 5 \times 10^5$。第一个整数 $n$ 是一个玩家解答的测验数量。参数 $c$、$p$ 和 $q$ 的含义在题目描述中说明。

$S_1 \cdots S_n$ 是一个字符串，描述了玩家的测验解答记录。每个 $S_i$ 要么是 Y，表示玩家对第 $i$ 个测验的答案正确；要么是 N，表示错误。

Output Format

在一行中输出玩家在第 $n$ 个测验结束后的最终等级。

12 4 4 7
YYYNYYNNNYYN

2

10 1 1 1
YNYNYNYNYN

5

17 5 250000 500000
YYYYYYYYYYYYYYYYY

3

8 3 2 3
YNNYYYYN

2

Hint

在样例输入 1 中，玩家在完成第四个测验后晋升到等级 1，因为正确率 $3/4$ 高于 $p/q = 4/7$。注意，在第三个测验时没有晋升，因为只回答了三个测验，少于 $c = 4$。然后，在第十一个测验后，玩家晋升到等级 2。

:::align{center}

图 B.1. 样例输入 1 的等级晋升时间点 :::