工厂中有 $2^n$ 台机器，编号从 $0$ 到 $2^n - 1$。第 $i$ 台机器消耗 $p_i$ 单位的电量。工厂使用一种称为“数字动态供电”（Digit Dynamic Powering，简称 Digit DP）的系统来控制机器的耗电量。

初始时，给定一个数组 $a_0, \dots, a_{n-1}$。系统会将初始的 $p_i$ 设置为 $\sum_{j \in S_i} a_j$，其中 $S_i$ 是 $i$ 的二进制表示中所有为 $1$ 的位的集合。

在此之后，可能会进行一些修改，每次修改会将某个区间内机器的耗电量增加一个特定值。形式化地说，给定三个整数 $\ell, r, x$，意味着编号在 $[\ell, r]$（包含边界）之间的每台机器的耗电量都应增加 $x$。区间的端点将以 $n$ 位二进制字符串的形式给出。

当使用三台不同的机器生产产品时，产品的价格始终为这三台机器的 $p_i$ 的乘积。

在这些修改过程中，管理者可能会询问关于某些区间的问题。如果我们尝试区间内所有可能的三台不同机器的组合来生产产品，价格的总和是多少？

形式化地说，给定两个整数 $\ell, r$，你需要报告满足 $\ell \le i < j < k \le r$ 的所有三元组 $(i, j, k)$ 的乘积 $p_i \cdot p_j \cdot p_k$ 之和。由于答案可能非常大，请将其对 $998\,244\,353$ 取模。区间的端点同样以 $n$ 位二进制字符串的形式给出。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 100; 1 \le q \le 5 \cdot 10^4$)。

第二行包含整数数组 $a_0, a_1, \dots, a_{n-1}$ ($0 \le a_i \le 10^9$)。

接下来的 $q$ 行包含查询。每行的第一个整数 $t$ 表示查询类型。

如果 $t = 1$，后面跟着三个整数 $\ell, r, x$ ($0 \le \ell \le r < 2^n, 0 \le x \le 10^9$)。

如果 $t = 2$，后面跟着两个整数 $\ell, r$ ($0 \le \ell \le r < 2^n$)。

注意：$\ell$ 和 $r$ 以 $n$ 位二进制字符串格式给出，最左侧的位为最高位。

输出格式

对于每个类型为 $2$ 的查询，输出一行，包含一个整数，即答案对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

3 3
1 2 4
2 000 111
1 010 101 1
2 000 111

样例输出 1

1960
3040

样例输入 2

2 2
1 1
2 00 10
2 00 11

样例输出 2

0
2