27442번 - 문자열 변환과 쿼리 3 서브태스크

대문자 한 글자를 소문자 문자열로 변환하는 작업을 하고 있다. 대문자로 구성된 문자열 \(S\), 대문자를 소문자 문자열로 변환하는 변환 정보가 \(n\)개 저장된 테이블 \(T\)가 주어진다. 문자열 \(S\)는 테이블 \(T\)에 주어진 대문자로 구성되어 있다. 예를 들어, \(S\) = "AB", \(T\) = {'A': "ab", 'B': "cd"}인 경우 문자열 "AB"는 문자열 "abcd"로 변환된다.

문자열 \(S\)와 변환 테이블 \(T\)에 대한 \(q\)개의 질의가 저장된 질의 목록 \(Q\)가 주어진다. 질의 목록 \(Q\)에 저장된 \(q\)개의 질의는 아래 두 가지 유형으로 구분된다. 첫 번째가 유형 \(1\)을 나타내고 두 번째가 유형 \(2\)를 나타낸다.

• \(1\ s\ e\) : 변환 테이블 \(T\)를 이용하여 문자열 \(S\)를 변환한 문자열을 \(P\)라고 하자. \(P\)의 \(s\)번째 문자부터 \(e\)번째 문자까지 출력한다.
• \(2\ s\ e\) : 변환 테이블 \(T\)를 이용하여 문자열 \(S\)를 변환한 문자열을 \(P\)라고 하자. \(P\)의 \(s\)번째 문자부터 \(e\)번째 문자로 구성된 문자열에서 가장 많이 출현한 문자의 출현 횟수를 출력한다.

질의 목록 \(Q\)에 저장된 첫 번째 질의부터 \(q\)번째 질의까지 순서대로 처리하면서 질의 결과를 출력하자.

첫 번째 줄에 문자열 \(S\)가 주어진다.

두 번째 줄에 \(n\)이 주어진다.

다음 \(n\)개의 줄에 테이블 \(T\)의 정보가 주어진다. 한 줄에 하나의 변환 정보가 주어진다. 하나의 변환 정보는 대문자와 소문자 문자열이 순서대로 주어진다.

다음 줄에 질의의 수 \(q\)가 주어진다.

다음 \(q\)개의 줄에 질의 정보가 주어진다. 한 줄에 하나의 질의 정보가 주어진다. 유형 \(1\)은 정수 \(1,\ s,\ e\)가 공백을 사이에 두고 순서대로 주어진다. 유형 \(2\)는 \(2,\ s,\ e\)가 공백을 사이에 두고 순서대로 주어진다.

첫 번째 줄부터 질의 결과를 순서대로 출력한다. 한 줄에 하나의 질의 결과를 출력한다.

• \(1\ \le\ \)문자열 \(S\) 길이\(\ \le\ 100,000\)
• 문자열 \(S\)는 테이블 \(T\)에 주어진 대문자로 구성되어 있다.
• \(1\ \le\ n\ \le\ 26\)
• 테이블 \(T\)에 같은 대문자가 두 번 이상 주어지지 않는다.
• \(1\ \le\ \)테이블 \(T\)에 있는 하나의 소문자 문자열 길이\(\ \le\ 100,000\)
• 테이블 \(T\)에 있는 문자열은 알파벳 소문자로 구성되어 있다.
• \(1\ \le\ q\ \le\ 100,000\)
• 질의 목록 \(Q\)에 저장된 질의는 유형 \(1\)과 유형 \(2\)만 존재한다.
• \(1\ \le\ s\ \le\ e\ \le\ \)변환 테이블 \(T\)를 이용하여 문자열 \(S\)를 변환한 문자열의 길이
• \(1\ \le\ \)유형 \(1\)로 출력되는 문자의 총수\(\ \le\ 10^7\)
• 유형 \(1\)로 출력되는 문자의 총수에서 줄바꿈 문자는 문자로 세지 않는다.