나는 행복합니다

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

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

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

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

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

두 번째 줄에 아인따가 비밀번호를 조작하면서 취한 행동의 수 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]의 정수는 9967이므로 이를 출력한다.
• 쿼리 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를 출력한다.