시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB236755635.220%

문제

알파벳 대소문자로 구성된 문자열 \(S\)가 주어진다. 문자열 \(S\)에 대한 \(n\)개의 질의가 저장된 질의 목록 \(A\)가 주어진다. 질의 목록 \(A\)에 저장된 \(n\)개의 질의는 아래 두 가지 유형으로 구분된다. 첫 번째가 유형 \(1\)을 나타내고 두 번째가 유형 \(2\)를 나타낸다.

  • \(1\ i_1\ i_2\) : 문자열 \(S\)에 존재하는 모든 문자 \(i_1\)을 문자 \(i_2\)로 변경한다. 문자열 \(S\)에 문자 \(i_1\)이 없으면 문자열 \(S\)는 변경되지 않는다.
  • \(2\) : 현재까지 주어진 유형 \(1\)을 순서대로 문자열 \(S\)에 적용한 경우 변경된 문자열 \(S\)를 출력한다.

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

입력

첫 번째 줄에 문자열 \(S\)와 정수 \(n\)이 순서대로 주어진다.

다음 줄부터 \(n\)개의 줄에 걸쳐서 질의 목록 \(A\)에 저장된 \(n\)개의 질의가 첫 번째 질의부터 마지막 질의까지 순서대로 주어진다. 한 줄에 하나의 질의가 주어진다. 유형 \(1\)은 정수 \(1\), 문자 \(i_1,\ i_2\)가 공백을 사이에 두고 순서대로 주어진다. 유형 \(2\)는 정수 \(2\)가 주어진다.

출력

첫 번째 줄부터 유형 \(2\)의 질의 결과를 순서대로 출력한다. 한 줄에 하나의 질의 결과를 출력한다.

제한

  • \(1\ \le\ \)문자열 \(S\) 길이\(\ \le\ 100,000\)
  • 문자열 \(S\)는 알파벳 대소문자로 구성되어 있다.
  • \(1\ \le\ n\ \le\ 300,000\)
  • 질의 목록 \(A\)에 저장된 질의는 유형 \(1\)과 유형 \(2\)만 존재한다.
  • 질의 목록 \(A\)에는 유형 \(2\)의 질의가 \(1\)개 이상 저장되어 있다.
  • \(1\ \le\ \)유형 \(2\)로 출력되는 문자의 총수\(\ \le\ 10^7\)
  • 유형 \(2\)로 출력되는 문자의 총수에서 줄바꿈 문자는 문자로 세지 않는다.
  • \(i_1,\ i_2\)는 알파벳 대소문자이다.

서브태스크

번호배점제한
110

\(1\ \le\ \)문자열 \(S\) 길이\(\ \le\ 100\)

\(1\ \le\ n\ \le\ 1,000\)

220

\(1\ \le\ \)문자열 \(S\) 길이\(\ \le\ 1,000\)

\(1\ \le\ n\ \le\ 300,000\)

370

추가 제약 조건 없음

예제 입력 1

abac 8
2
1 a d
1 d c
2
1 A b
1 c c
2
1 c Z

예제 출력 1

abac
cbcc
cbcc

첫 번째 질의는 유형 \(2\)다. 아직 주어진 유형 \(1\)이 없으므로 입력으로 주어진 \(S\ =\) "abac"를 그대로 출력한다.

두 번째 질의는 유형 \(1\)이다. \(S\ =\) "abac"에 존재하는 모든 문자 'a''d'로 변경한다. \(S\ =\) "dbdc"가 된다.

세 번째 질의는 유형 \(1\)이다. \(S\ =\) "dbdc"에 존재하는 모든 문자 'd''c'로 변경한다. \(S\ =\) "cbcc"가 된다.

네 번째 질의는 유형 \(2\)다. 현재까지 주어진 유형 \(1\)을 입력 문자열 \(S\)에 순서대로 적용하면 문자열 \(S\ =\) "cbcc"가 된다.

다섯 번째 질의는 유형 \(1\)이다. 문자열 \(S\ =\) "cbcc"에 존재하는 모든 문자 'A''b'로 변경한다. 문자열 \(S\)에 문자 'A'가 없으므로 문자열 \(S\)는 변경되지 않는다.

여섯 번째 질의는 유형 \(1\)이다. 문자열 \(S\ =\) "cbcc")에 존재하는 모든 문자 'c''c'로 변경한다. 동일한 문자로 변경하므로 문자열 \(S\)는 변경되지 않는다.

일곱 번째 질의는 유형 \(2\)다. 현재까지 주어진 유형 \(1\)을 입력 문자열 \(S\)에 순서대로 적용하면 문자열 \(S\ =\) "cbcc"가 된다.

여덟 번째 질의는 유형 \(1\)이다. 문자열 \(S\ =\) "cbcc"에 존재하는 모든 문자 'c''Z'로 변경한다. 문자열 \(S\ =\) "ZbZZ"가 된다.

출처

채점 및 기타 정보

  • 예제는 채점하지 않는다.