该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师很明确的告诉你，他出了一道数据结构题！（大概也许可能 $Maybe$ 吧）

题目内容很简单，徐老师会给定一个 $k$ 进制的 $n$ 位正整数 $A$（可能含有前导 $0$），然后需要你对这个数字进行 $m$ 次操作，操作一共有四种：

• 1 l r：将第 $l$ 位上的数字替换为 $r$
• 2 l r：将第 $l$ 位到第 $r$ 位这个区间内的数字进行 升序排序
• 3 l r：将第 $l$ 位到第 $r$ 位这个区间内的数字进行 降序排序
• 4 l r：求第 $l$ 位到第 $r$ 位这个区间数字组成的 $k$ 进制数字输出，由于数字可能较大，请将这个数字 转化为十进制，并对 $998244353$ 取模后输出

现在徐老师需要你完成这个任务

输入格式

输入第一行包含三个整数 $n,m,k$ 含义如题

输入第二行包含一个正整数，表示给定的 $k$ 进制数字 $A$

接下来 $m$ 行，每行包含三个数字 $op,l,r$ 根据题目规定描述一种操作

输出格式

对于每个操作 $4$，输出一个正整数表示答案

数据范围

对于全部测试点满足：$1 \leq n,m\leq 50000，2 \leq k \leq 10$，且保证所有操作输入均合法

样例输入

8 4 3
20112021
1 2 2
2 2 7
3 1 4
4 1 7

样例输出

1808

样例解释

第一次操作后数字变为 $22112021$

第二次操作后数字变为 $20112221$

第三次操作后数字变为 $21102221$

第四次操作时，第 $1$ 到 $7$ 位构成的 $k$ 进制数为 $(2110222)_3$，将它转为十进制数，答案为 $(1808)_{10}$