DNA Evolution

누구나 DNA 가닥이 뉴클레오타이드로 구성된다는 것을 알고 있다. 뉴클레오타이드에는 네 가지 종류가 있다: "A", "T", "G", "C". A DNA 가닥은 뉴클레오타이드의 수열이다. 과학자들은 희귀종의 진화를 추적하기로 했으며, 이 종의 DNA 가닥은 처음에 문자열 s였다.

이 종의 진화는 DNA에서 일어나는 일련의 변화로 설명된다. 각 변화는 어떤 뉴클레오타이드 하나의 변화이다. 예를 들어, DNA 가닥 "AAGC"에서 다음과 같은 변화가 일어날 수 있다: 두 번째 뉴클레오타이드가 "T"로 바뀌어, 그 결과 DNA 가닥이 "ATGC"이 될 수 있다.

과학자들은 DNA 가닥의 일부 구간이 정체를 알 수 없는 감염의 영향을 받을 수 있다는 것을 알고 있다. 감염은 뉴클레오타이드의 수열로 나타낼 수 있다. 과학자들은 어떤 감염으로 인해 발생한 변화가 있는지에 관심이 있다. 따라서 과학자들은 때때로 어떤 감염이 DNA의 어떤 구간에 미치는 영향의 값을 알고 싶어 한다. 이 값은 다음과 같이 계산한다:

• 감염이 문자열 e로 표현되고, 과학자들이 위치 l부터 위치 r까지 양 끝을 포함하는 DNA 가닥의 구간에 관심이 있다고 하자.
• 문자열 eee... (즉, 문자열 e가 무한히 많이 반복되어 이루어진 문자열)의 접두사를 위치 l부터 위치 r까지 양 끝을 포함하여 문자열 s 아래에 적는다.
• 영향의 값은 문자열 s의 문자가 그 아래에 적힌 문자와 일치하는 위치의 개수이다.

개발자인 Innokenty 역시 생물정보학에 관심이 있어서, 과학자들은 그에게 도움을 요청했다. Innokenty는 VK Cup을 준비하느라 바쁘기 때문에 이 문제를 참가자들에게 맡기기로 했다. 과학자들을 도와주자!

첫 번째 줄에는 초기 DNA 가닥을 나타내는 문자열 s (1 ≤ |s| ≤ 105)가 주어진다. 이 문자열은 대문자 영문자 "A", "T", "G", "C"로만 구성된다.

다음 줄에는 이벤트의 수를 나타내는 하나의 정수 q (1 ≤ q ≤ 105)가 주어진다.

그다음에는 각각 하나의 이벤트를 설명하는 q개의 줄이 주어진다. 각 줄은 다음 두 형식 중 하나이다:

• 1 x c. 여기서 x는 정수 (1 ≤ x ≤ |s|)이고, c는 문자 "A", "T", "G", "C" 중 하나이다. 이는 DNA에 변화가 생겨 위치 x의 뉴클레오타이드가 이제 c임을 의미한다.
• 2 l r e. 여기서 l, r는 정수 (1 ≤ l ≤ r ≤ |s|)이고, e는 문자 "A", "T", "G", "C"로 이루어진 문자열 (1 ≤ |e| ≤ 10)이다. 이는 과학자들이 위치 l부터 위치 r까지 양 끝을 포함하는 DNA 가닥의 구간에 감염 e가 미치는 영향의 값에 관심이 있음을 의미한다.

과학자들의 각 질의(두 번째 유형의 질의)마다 감염이 DNA에 미치는 영향의 값을 나타내는 하나의 정수를 새 줄에 출력한다.

첫 번째 예제를 살펴보자. 첫 번째 두 번째 유형 질의에서는 모든 문자가 일치하므로 답은 8이다. 두 번째 질의에서는 문자열 "TTTTT..."와 부분 문자열 "TGCAT"를 비교한다. 일치하는 위치는 두 곳이다. 세 번째 질의에서는 DNA 변경 이후 문자열 "TATAT..."'와 부분 문자열 "TGTAT"를 비교한다. 일치하는 위치는 4곳이다.