U190681 [ljoi2077]xljznwwt

定义两个数列之间的运算： 对于数列 $A=\{a_1,a_2,...,a_n\}$, $B=\{b_1,b_2,...,b_m\}$而言： 定义 $A\times B$ ： 当且仅当 $m=n$ 时，有 $A\times B=\{a_1*b_1,a_2*b_2,...,a_n*b_n\}$ ，否则为将短的位数用1补齐以后的结果。 定义 $A \% B$ ：当且仅当 $m=n$ 时，定义 $F(i)=\sum_{1\leq j\leq n} ^ {j≠i}a_jb_j$ ，则 $A \% B= \{F(i)-a_ib_i\}$ ，否则为将短的位数用1补齐的结果。 定义 $(A \% B)^k=(A \% B) \times (A \% B)\times ...\times (A \% B)$ ， 乘 $k$ 次 定义 $A \%B ^k = A\%B\%B\%...\%B$，模 $k$ 次 定义 $|A|=\sum_{i=1}^n a_i$ 现在给定一个数列 $A=\{a_1,a_2,...,a_n\}$ ，定义 $A(l,r)$ 表示 $A$ 的 $l$ 到 $r$ 位所组成的数列，你需要维护三种， $q$ 个操作： 1. `1 l1 r1 l0 r0 k` 表示将 $A(l_1,r_1)$ 变为 $A(l_1,r_1)\%B(l_0,r_0)^k$ 2. `2 l1 r1 l0 r0` 表示输出 $|A(l_1,r_1)*B(l_0,r_0)|$ 的结果 3. `3 l r k` 对于 $l,r$ ，若 $r-l+1$ 为奇，令 $mid=floor(\dfrac {l+r} 2)$ ，则输出 $|(A(l,mid+1)\%B(mid+1,r))^k|$ ，否则输出 $|(A(l,mid)\%B(mid+1,r))^k|$ 。

第一行一个整数 $T$ 表示数据组数。 对于每组数据，都有第一行为两个数 $n,q$ ，分别表示序列长度与操作组数。 接下来 $q$ 行，可能会有 `1 l1 r1 l0 r0 k` ， `2 l1 r1 l0 r0` ， `3 l r k` 三种情况。

输出每一个 `2` 操作与 `3` 操作的结果，结果对 $998244353$ 取模。

$1 \leq T \leq 50,1\leq n \leq 20, 1\leq q\leq2*10^6 , 1\leq l