Kecleon

카멜레온과 비슷하게 케클레온의 피부도 여러 가지 색으로 바뀔 수 있습니다. 이 문제에서는 케클레온의 몸 색이 26가지 중 하나이고, 각 색은 서로 다른 소문자 영문자로 표시한다고 가정합니다.

여러 케클레온이 한 줄을 이루려고 합니다. 처음에 줄은 비어 있습니다. 다음 두 종류의 쿼리를 처리해야 합니다.

• 첫 번째 종류: 지정된 색의 케클레온 한 마리가 줄의 오른쪽 끝에 와서 그곳에 계속 머무릅니다.
• 두 번째 종류: 정수 k가 주어집니다. 줄에서 연속한 k마리로 이루어진 구간을 하나씩 보고, 각 구간의 색을 왼쪽부터 읽어 수열을 만듭니다. 이 수열이 줄의 처음 k마리의 색 수열과 정확히 같은 구간의 개수를 구해야 합니다.

케클레온이 줄에 서는 순서는 미리 알 수 없으므로, 쿼리는 온라인으로 처리해야 합니다.

입력은 암호화되어 있습니다. 처음에 0인 변수 last를 유지해야 합니다. 두 번째 종류의 쿼리를 처리할 때마다 last는 방금 계산한 답으로 바뀝니다.

첫 줄에 정수 q (2 ≤ q ≤ 300 000)가 주어집니다. 이는 쿼리의 개수입니다.

다음 q줄에는 각 쿼리가 다음 형식 중 하나로 주어집니다.

• add ci′ (ci′는 소문자 영문자): ci = char((asc(ci′) + last) mod 26)으로 정합니다. 여기서 asc(x)는 영문자 x의 알파벳 내 0 기준 번호이고, char(x)는 0 기준 x번째 영문자입니다. 이 연산은 색이 ci인 케클레온을 줄의 오른쪽 끝에 추가합니다.
• get ki′ (1 ≤ ki′ ≤ n): n은 현재 줄에 있는 케클레온의 수입니다. ki = ((ki′ − 1 + last) mod n) + 1로 정합니다. 길이가 ki인 구간 중 줄의 처음 ki마리와 색 수열이 같은 구간의 개수를 구해야 합니다.

첫 번째 쿼리는 반드시 add이며, get 쿼리가 최소 하나 있다고 보장됩니다.

두 번째 종류의 각 쿼리에 대해, 답을 한 줄에 정수 하나로 출력합니다.

이 예시에서 케클레온은 abcababca 순서로 줄에 섭니다. 복호화된 ki 값은 1, 3, 2, 1, 2, 3, 4입니다.

'a' = , 'b' = , 'c' = 로 정합니다. 쿼리의 정확한 순서는 다음과 같습니다.