랭크 승급

Quiz Solver는 인기 있는 온라인 컴퓨터 게임이다. 플레이어가 모바일 앱을 열 때마다 새로운 퀴즈가 표시된다. 플레이어가 퀴즈에 답을 제출하면 정답 또는 오답으로 판정되고, 그 결과가 데이터베이스에 누적된다. 플레이어가 여러 퀴즈에서 높은 정확도를 보이면 게임 내 랭크가 오른다.

플레이어의 랭크는 0 이상의 정수이며, 모든 플레이어는 랭크 $0$에서 시작한다. 랭크 승급은 정수 $c$와 유리수 $p/q$로 정의된다. $e$번째 퀴즈를 마친 후, 다음 조건을 만족하는 정수 $s$가 존재하면 랭크가 1 증가한다.

• $1 \le s \le e - c + 1$.
• $s$번째 퀴즈를 시작하기 전에 플레이어가 이미 현재 랭크에 있었다.
• $s$번째부터 $e$번째까지 퀴즈의 정답률이 $p/q$ 이상이다.

조건을 만족하는 $s$가 없으면 랭크는 그대로 유지된다.

어느 날 Quiz Solver 관리자는 데이터베이스 장애로 플레이어들의 랭크 데이터가 유실된 것을 알게 되었다. 다행히 퀴즈 풀이 기록은 온전히 남아 있다. 각 플레이어의 풀이 기록으로부터 그 플레이어의 랭크를 다시 계산하라.

입력은 다음 형식의 테스트케이스 하나로 구성된다.

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

$S_1$ $\cdots$ $S_n$

첫 줄에는 네 정수가 주어지며, $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_i$는 $i$번째 퀴즈의 답이 맞았으면 Y, 틀렸으면 N이다.

$n$번째 퀴즈를 마친 후 플레이어의 최종 랭크를 한 줄에 출력한다.

샘플 입력 1에서 플레이어는 4번째 퀴즈를 마친 뒤 랭크 1로 승급한다. 정답률 3/4가 $p/q = 4/7$보다 높기 때문이다. 3번째 퀴즈 뒤에는 푼 퀴즈가 3개뿐이어서 $c = 4$보다 적으므로 승급하지 않는다. 11번째 퀴즈를 마친 뒤 랭크 2로 승급한다.

그림 B.1. 샘플 입력 1의 랭크 승급 시점