시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 1024 MB 48 14 11 57.895%

문제

관악산 깊은 곳에는 여우들과 너구리들이 살고 있는 마을이 있다. 이 동물들은 변신에 능하기 때문에, 자주 사람으로 변신해서 근처 대학교에 놀러 가곤 한다.

어느 날, 마을에서 학교로 내려가는 길에 장인 여우가 국수 가게를 차렸다. 이 가게의 대표 메뉴는 유부가 들어간 여우 국수와 튀김 부스러기가 들어간 너구리 국수이다. 이 가게는 곧 마을의 여우들과 너구리들에게 큰 인기를 끌게 되었다. 물론 여우들은 가게에 방문하면 반드시 여우 국수를 주문하고, 너구리들은 반드시 너구리 국수를 주문한다.

장인 여우는 오랜 경험으로 하루에 몇 마리의 여우와 너구리가 올지 정확히 예측할 수 있다. 장인 여우는 내친김에 이 손님들의 순서까지 맞추는 연습도 하고 있지만, 아직은 많이 서투르다. 그래도 장인 여우는 매일 아침 손님들의 순서를 예측하고, 반드시 그 순서에 따라서 국수를 조리한다. 또한 장인 여우는 국수가 만들어진 시점을 구분하기 위해 한 그릇을 조리할 때마다 1번부터 차례대로 번호를 매긴다.

만약 예측한 순서가 틀리면, 국수를 조리되는 대로 손님에게 내어 주면 어떤 손님들은 주문과 다른 국수를 받게 된다. 이를 방지하기 위해, 장인 여우는 음식을 올려놓으면 맛과 온도를 오랫동안 유지해 주는 마법 진열대를 마련했다. 장인 여우는 국수를 조리하면 즉시 진열대 위에 올려놓고, 손님에게 국수를 내놓을 때는 항상 진열대 위에 있는 국수들 중 가장 나중에 조리된 것, 즉 번호가 가장 큰 것을 꺼내서 내놓는다. 매 시점에 새로운 국수를 조리할지, 아니면 손님에게 국수를 내놓을지는 장인 여우가 마음대로 선택할 수 있다.

이 국수 가게에는 항상 첫 번째로 찾아오는 단골 손님이 있다. 장인 여우는 이 손님에게 소소한 행운의 번호 이벤트를 제공하기로 했다. 첫 번째 손님이 어떤 번호 $n$을 부르면, 장인 여우는 $n$번 국수를 이 손님에게 내어야 한다. 이때, $n$번 국수가 첫 번째 손님이 주문한 메뉴가 아니거나, 장인 여우가 아무리 노력하더라도 그 뒤로 찾아온 모든 손님의 주문을 만족시킬 수 없다면 판정을 받는다. 그렇지 않을 경우는 당첨 판정을 받고, 첫 번째 손님은 열렬한 축하를 선물로 받는다.

장인 여우가 예측한 손님들의 순서와 실제로 찾아온 손님들의 순서가 주어질 때, 가능한 당첨 번호들을 모두 구해 보자.

입력

첫째 줄에 하루 동안 찾아온 손님들의 총 마릿수를 나타내는 정수 $N$($1 \leq N \leq 5\,000\,000$)이 주어진다.

둘째 줄에 장인 여우가 예측한 손님들의 순서를 나타내는 $N$글자의 문자열이 주어진다. 이 문자열은 알파벳 YN으로만 구성되어 있으며, Y는 여우, N은 너구리를 의미한다.

셋째 줄에 실제로 찾아온 손님들의 순서를 나타내는 $N$글자의 문자열이 두 번째 줄과 같은 형식으로 주어진다.

두 문자열에 들어 있는 알파벳 Y의 개수는 서로 같으며, 자연히 알파벳 N의 개수 역시 서로 같다.

출력

첫째 줄에 첫 번째 손님이 부를 수 있는 당첨 번호의 총합을 출력한다. 만약 어떤 번호를 불러도 꽝 판정을 받게 된다면 0을 출력한다.

예제 입력 1

3
YNN
NNY

예제 출력 1

5

예제 입력 2

4
NYNY
YNNY

예제 출력 2

2

노트

첫 번째 예시에서 행운의 번호로 1을 부를 경우, 첫 번째 손님은 너구리인데 여우 국수를 받게 되므로 꽝 판정을 받는다.

2를 부를 경우는 다음과 같은 방법으로 장인 여우가 모든 주문을 처리할 수 있으므로 당첨 판정을 받는다.

마찬가지로 3도 당첨 번호임을 쉽게 알 수 있으며, 답으로 $2+3=5$를 출력한다.

두 번째 예시에서 행운의 번호로 4를 부를 경우 메뉴는 올바르지만, 이후 진열대 위에 남은 국수들을 너구리 → 여우 → 너구리 순으로 내놓게 되므로 남은 손님들의 주문을 만족시킬 수 없다.