16124번 - 나는 행복합니다

한국 프로야구단 이글스의 열렬한 팬인 아인따는 올해는 분명 이글스의 가을 야구를 볼 수 있을 거라는 희망에 부풀어 있다. 그의 바람대로 올해 이글스가 포스트시즌에 진출한다면 드디어 10자리의 비밀번호를 끊을 수 있게 된다!

한국 프로야구에서 비밀번호란 어떤 팀의 연도별 순위를 나열한 문자열을 말하는데, 오랜 기간 동안 포스트시즌에 진출하지 못한 팀들의 비밀번호는 놀림감이 되곤 한다. 아인따가 응원하는 이글스의 비밀번호는 5886899678이고, 그 외에도 트윈스의 6668587667, 자이언츠의 8888577 등이 유명하다. 한국 프로야구 리그는 10개의 팀으로 구성되어 있기 때문에 1위부터 10위까지 순위가 매겨진다. 이때 10위를 기록한 해는 비밀번호에 0으로 표기한다.

현실 세계의 이글스는 고작 10자리의 비밀번호를 찍고 있지만, 이글스가 100만 자리의 비밀번호를 찍고 있는 미래를 상상하는 것은 그다지 어렵지 않다. 미래의 아인따는 모든 것에서 해탈해서 특별한 능력을 쓸 수 있게 되었다. 아인따는 어떤 기간 동안 이글스가 A등을 기록한 모든 해의 경기 내용을 조작해서 이글스를 B등으로 바꿀 수 있다. 이때 순위가 너무 부자연스러우면 다른 팀의 팬들에게 의심을 살 수 있기 때문에, 능력을 쓰는 중간중간에 어떤 기간의 비밀번호가 얼마나 자연스러운지를 자신만의 방법으로 확인한다.

미래의 이글스의 비밀번호와 아인따가 비밀번호를 조작하는 과정이 주어질 때, 이에 따라 비밀번호를 조작하는 프로그램을 작성해 보자.

첫 줄에 이글스의 비밀번호를 의미하는 문자열 S가 주어진다. 문자열은 숫자로만 이루어져 있으며, 문자열의 길이는 1 이상 10⁶ 이하이다.

두 번째 줄에 아인따가 비밀번호를 조작하면서 취한 행동의 수를 의미하는 정수 Q(1 ≤ Q ≤ 100,000)가 주어진다.

세 번째 줄부터 Q개의 줄에 걸쳐 각 줄에 아인따의 행동이 한 줄에 하나씩 순서대로 주어진다. 아인따의 행동은 다음과 같은 두 가지 형식이 있다.

• 1 i j from to (1 ≤ i ≤ j ≤ |S|, from, to는 숫자): 비밀번호의 i번째 위치부터 j번째 위치까지의 범위에 있는 숫자 from을 전부 to로 바꾼다.
• 2 i j (1 ≤ i ≤ j ≤ |S|): 비밀번호의 i번째 위치부터 j번째 위치까지의 숫자를 이어 붙여 하나의 정수로 볼 때, 이 정수를 998,244,353으로 나눈 나머지를 구한다.

두 번째 행동이 한 번 이상 주어짐이 보장된다.

각각의 두 번째 행동에 대한 결과를 순서대로 한 줄에 하나씩 출력한다.

• 쿼리 1: 입력된 수 중 [6, 9] 범위의 정수는 9,967이므로 이를 출력한다.
• 쿼리 2: [2, 9] 범위에 있는 8을 5로 바꾸므로 5556599678이 된다.
• 쿼리 3: [1, 3] 범위에 있는 5를 0으로 바꾸므로 0006599678이 된다.
• 쿼리 4: [1, 6] 범위의 정수인 659를 출력한다.
• 쿼리 5: [1, 10] 범위에 있는 0을 2로 바꾸므로 2226599678이 된다.
• 쿼리 6: [5, 8] 범위에 있는 8을 1로 바꾸는데, 이 범위에는 8이 없으므로 아무 일도 일어나지 않는다.
• 쿼리 7: [1, 10] 범위의 정수는 2,226,599,678이므로 이를 998,244,353으로 나눈 나머지인 230,110,972를 출력한다.