원 위의 알파벳

한은 혼자 공부하기 싫어서 친구 도미니크를 집으로 불렀다. 전자공학 문제를 기록적으로 많이 푼 저녁을 보내고 도미니크는 집으로 돌아갔다. 그런데 경찰이 도미니크를 술에 취한 사람으로 보고 불러 세웠다. 이런 상황에서는 인지 능력을 시험하는 문제를 몇 개 풀어서 맨정신임을 증명한다. 도미니크의 말을 믿는다면 대화는 이렇게 흘러갔다.

• 경찰: 쉬운 것부터 갑시다. 버블 정렬의 시간 복잡도는 얼마입니까?
• 도미니크: 그건 정말 쉽죠. $O(n^2)$입니다.
• 경찰: 영어 알파벳을 거꾸로 말해 보세요.
• 도미니크: 시시하네요. zyxwvutsrqponmlkjihgfedcba
• 경찰: 통째로 외웠군요. 이번에는 영어 알파벳 a부터 z까지가 원 위에 시계 방향으로 차례대로 적혀 있다고 생각하세요. 글자 a에서 시작해 시계 방향으로 글자를 말합니다. 글자를 하나 말할 때마다 나는 반대 방향으로 이어서 말하라고 지시하거나, 지금까지 어떤 글자를 몇 번 말했는지 물어볼 수 있습니다. 준비됐습니까? 3, 2, 1, 시작!
• 도미니크: 음... a, b, c...

도미니크의 문제를 풀어 주는 프로그램을 작성하시오.

첫째 줄에 경찰이 내리는 지시의 개수 $Q$ ($1 \le Q \le 100\,000$)가 주어진다. 다음 $Q$개의 줄에 지시가 한 줄에 하나씩 "SMJER n" 또는 "UPIT n x" 형태로 주어진다. SMJER는 크로아티아어로 방향, UPIT는 질의를 뜻한다. "SMJER n"은 $n$번째 글자를 말한 뒤부터 도미니크가 알파벳을 반대 방향으로 말해야 한다는 뜻이고, "UPIT n x"는 도미니크가 처음 $n$개의 글자 중에서 글자 $x$를 몇 번 말했는지 답해야 한다는 뜻이다.

지시는 시간 순서대로 주어진다. 즉 지시에 나오는 수 $n$ ($1 \le n \le 10^9$)은 엄격하게 증가한다. "UPIT n x" 형태의 지시에 나오는 문자 $x$는 영어 소문자다.

"UPIT n x" 형태의 지시마다 도미니크가 처음 $n$개의 글자 중에서 글자 $x$를 몇 번 말했는지 한 줄에 하나씩 출력한다. 질의는 입력에 주어진 순서대로 답한다.

예를 들어 네 번째 글자를 말한 뒤에 방향이 바뀌면 도미니크가 말하는 글자는 a, b, c, d, c, b, a, z, y, x 순서가 된다.