17443번 - 여우 퀴즈

관악산 기슭에 살던 달빛 여우는 마침내 달빛을 받아 구미호가 되었지만, 구미호의 상징인 여우구슬이 없어 힘이 약한 꼬마 구미호가 되었다. 달빛 여우는 완전한 구미호로 거듭나기 위해서 근처 대학에 들어가 "여우구슬 만들기'' 강의를 듣기로 했다.

이 강의에서는 첫 주에 OX 문제 목록을 주고, 그 뒤로 매주 그 목록의 연속된 일부분을 골라서 퀴즈를 본다. 이 문제들은 정말 어려워서 학생들의 정답률은 처참하다. 대신 이 퀴즈에는 보너스 점수를 얻을 수 있는 특별한 규칙이 있다. 학생들은 문제의 답으로 O나 X 대신 F를 적을 수 있고, 연속한 세 문제의 답을 F, O, X 순으로 적으면 보너스 점수를 얻는다. 그래서 문제 풀기를 포기하고 답을 "F, O, X, F, O, X, …''로 적어 내는 학생들도 자주 나온다.

부지런한 달빛 여우는 미리 모든 문제의 답을 생각해 놓았다. 그러나 답에 확신이 없기 때문에 퀴즈를 볼 때는 몇몇 문제에 자신이 생각한 답 대신 F를 적어서 보너스 점수를 노리려고 한다. 또한 강의를 들으면서 새로운 것을 배우면 달빛 여우의 생각이 중간에 달라질 수도 있다.

매 퀴즈에서 달빛 여우가 얻을 수 있는 최고 점수를 구해 보자.

첫 줄에 목록에 있는 문제의 수를 의미하는 정수 N(1 ≤ N ≤ 250,000), 문제 하나를 맞혔을 때 얻는 점수를 의미하는 정수 A, 보너스 점수를 의미하는 정수 B(0 ≤ A, B ≤ 100)가 공백을 사이에 두고 주어진다.

두 번째 줄에 각 문제의 정답을 의미하는 문자열 S가 주어진다. S의 길이는 N글자이며 문자 O와 X로만 이루어져 있다.

세 번째 줄에 달빛 여우가 생각한 각 문제의 답을 의미하는 문자열 T가 S와 같은 형식으로 주어진다.

네 번째 줄에는 쿼리의 개수를 의미하는 정수 Q(1 ≤ Q ≤ 250,000)가 주어진다.

다음 Q개의 줄에 걸쳐 각 줄에 쿼리가 하나씩 주어진다. 쿼리는 다음의 두 종류가 있다.

• Q a b: a번부터 b번까지의 문제로 퀴즈를 본다(1 ≤ a ≤ b ≤ N, a, b는 정수).
• C n: 달빛 여우가 n번 문제의 답을 반대로 바꾼다(1 ≤ n ≤ N, n은 정수). 즉 기존에 생각했던 답이 O였다면 X로, X였다면 O로 바꾼다.

Q 쿼리는 한 개 이상 주어짐이 보장된다.

각각의 Q 쿼리에 대해 달빛 여우가 얻을 수 있는 최고 점수를 한 줄에 하나씩 출력한다.

첫 번째 쿼리에서는 3번 문제의 답을 F로 바꾸면 세 문제를 맞혀 9점을 받고 보너스 점수 5점을 추가로 얻을 수 있다.

두 번째 쿼리에서는 달빛 여우가 생각한 7번 문제의 답이 O에서 X로 바뀐다.

세 번째 쿼리에서는 3번 문제와 8번 문제의 답을 F로 바꾸면 두 문제를 맞혀 6점을 받고 보너스 점수 10점을 추가로 얻을 수 있다.