알파벳 소문자로 이루어진 초기 문자열 s가 주어집니다.
초기 문자열에 포함된 모든 문자들은 고유한 번호를 가지며, n번 문자는 초기 문자열의 n번째 문자를 의미합니다.
예를 들어, 초기 문자열이 "aba"라면 1번 문자는 a, 2번 문자는 b, 3번 문자는 a입니다. 그 후, 초기 문자열에서 1번 문자를 분리해 "a" / "ba" 두 개의 문자열로 나눠졌다면, "a"는 1번 문자로 이루어진 문자열이고 "ba"는 2번 문자와 3번 문자로 이루어진 문자열입니다.

당신은 주어진 문자열에 대해 다음과 같은 5가지 쿼리를 수행해야 합니다. 쿼리는 모두 문자열로 주어집니다.

• 1 x y : 숫자 1과 정수 x, y가 공백 하나를 사이에 두고 주어집니다. x번 문자와 y번 문자가 같은 문자열에 포함돼 있는지 확인합니다. 같은 문자열에 포함되어 있으면 "YES"를, 포함되어있지 않으면 "NO"를 result 배열의 뒤에 추가합니다.
  
• 2 x word : 숫자 2와 정수 x, 문자열 word가 공백 하나를 사이에 두고 주어집니다. x번 문자가 있는 문자열을 찾습니다. 해당 문자열에서 word에 포함된 알파벳을 모두 새로 생성한 빈 문자열로 옮깁니다.
• 3 x y word : 숫자 3과 정수 x, y가 공백 하나를 사이에 두고 주어집니다. 빈 문자열을 생성한 뒤, x~y번 문자들 중 word에 포함된 알파벳을 모두 새로 생성한 빈 문자열로 옮깁니다.
• 4 x y : 숫자 4와 정수 x, y가 공백 하나를 사이에 두고 주어집니다. x번 문자가 포함된 문자열과 y번 문자가 포함된 문자열을 하나의 문자열로 합칩니다. 먼저 생성된 문자열에 늦게 생성된 문자열이 합쳐지는 형식으로 먼저 생성된 문자열만 남고 늦게 생성된 문자열은 사라집니다.
• 5 : 숫자 5가 주어집니다. 항상 쿼리의 마지막에 한 번만 주어집니다. 존재하는 모든 문자열에 대해 문자열의 알파벳 구성을 각각 result 배열의 뒤에 추가합니다. 모든 문자열의 알파벳 구성을 문자열이 먼저 생성된 순으로 result 배열의 뒤에 추가합니다.

유의 사항은 다음과 같습니다.

• 같은 문자열 안에 있는 문자들은 항상 번호순으로 정렬합니다.
• 문자열의 길이가 0이 되면 해당 문자열은 사라집니다.

문자열의 알파벳 구성은 다음과 같습니다.

• 문자열의 알파벳 구성은 하나의 문자열입니다.
• a부터 z까지 사전 순으로 알파벳과, 해당 알파벳이 문자열에 포함된 개수를 공백 하나로 구분한 형태입니다.
• 예를 들어, "abaebae" 처럼 a 3개, b 2개, e 2개로 이루어진 문자열의 알파벳 구성은 "a 3 b 2 e 2"입니다.

초기 문자열 s와 쿼리를 담고 있는 문자열 배열 query가 주어집니다. 쿼리를 주어진 순서대로 모두 마친 후의 result 배열을 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ s의 길이 ≤ 100,000
  • s의 원소는 알파벳 소문자로만 이루어져 있습니다.
• 1 ≤ query의 길이 ≤ 200,000
  • 1 ≤ x, y ≤ s의 길이
  • 3번 쿼리의 경우 x ≤ y
  • 1 ≤ word의 길이 ≤ 26
  • word의 원소는 알파벳 소문자로만 이루어져 있습니다.

테스트 케이스 구성 안내

아래는 테스트 케이스 구성을 나타냅니다. 각 그룹 내의 테스트 케이스를 모두 통과하면 해당 그룹에 할당된 점수를 획득할 수 있습니다.

입출력 예

입출력 예 설명

입출력 예 #1

초기 문자열은 "programmers"입니다.

1. 1 1 5 쿼리를 실행하면 1번 문자 p와 5번 문자 r은 같은 문자열에 있으므로 result에 "YES"를 추가합니다.
2. 2 1 rm 쿼리를 실행하면 빈 문자열을 추가로 생성하고, 1번 문자 p가 속한 문자열 "programmers"에 존재하는 r과 m을 추가로 생성한 문자열에 옮깁니다. 쿼리를 수행한 후에 존재하는 문자열은 "pogaes"와 "rrmmr" 두 문자열입니다. "pogaes"는 1, 3, 4, 6, 9, 11번 문자들로 이루어져 있고, "rrmmr"는 2, 5, 7, 8, 10번 문자들로 이루어져 있습니다.
3. 1 1 5 쿼리를 실행하면 1번 문자 p는 문자열 "pogaes"에 속하고 5번 문자 r은 "rrmmr"에 속합니다. 따라서, result에 "NO"를 추가합니다.
4. 5 쿼리를 실행하면 문자열이 생성된 순서인 "pogaes", "rrmmr" 순으로 알파벳 구성을 result에 추가하게 됩니다. "pogaes"의 알파벳 구성인 "a 1 e 1 g 1 o 1 p 1 s 1"와 "rrmmr"의 알파벳 구성인 "m 2 r 3"를 차례로 result에 추가합니다.

쿼리를 모두 수행한 후의 result는 ["YES", "NO", "a 1 e 1 g 1 o 1 p 1 s 1", "m 2 r 3"]가 됩니다.

입출력 예 #2

초기 문자열은 "abacadae"입니다.

1. 3 1 4 aa 쿼리를 실행하면 빈 문자열을 추가로 생성하고, 1번 문자부터 4번 문자 중에서 존재하는 a를 빼내 추가로 생성한 문자열에 옮깁니다. 쿼리를 수행한 후에 존재하는 문자열은 "bcadae"와 "aa" 두 문자열입니다. "bcadae"는 2, 4, 5, 6, 7, 8번 문자들로 이루어져 있고, "aa"는 1, 3번 문자들로 이루어져 있습니다.
2. 1 1 5 쿼리를 실행하면 1번 문자 a는 문자열 "aa"에 속하고 5번 문자 a는 문자열 "bcadae"에 속합니다. 따라서, result에 "NO"를 추가합니다.
3. 4 1 7 쿼리를 실행하면 1번 문자가 속한 문자열 "aa"와 7번 문자가 속한 "bcadae"를 합칩니다. "aa"가 상대적으로 늦게 생성됐으므로 "aa"가 사라지고 "bcadae"에 합쳐집니다. 쿼리를 수행한 후에 존재하는 문자열은 "abacadae" 하나입니다.
4. 1 1 5 쿼리를 실행하면 1번 문자와 5번 문자가 "abacadae" 문자열에 속하므로 "YES"를 result에 추가합니다.
5. 5 쿼리를 실행하면 유일하게 존재하는 문자열인 "abacadae"의 알파벳 구성을 result에 추가합니다. "a 4 b 1 c 1 d 1 e 1"가 result에 추가됩니다.

쿼리를 모두 수행한 후의 result는 ["NO”, "YES", "a 4 b 1 c 1 d 1 e 1"]가 됩니다.