题目描述

给定 $n$ 个模式串 $S_i$ 和一个文本串 $T$。 你需要支持 $q$ 次操作： 1 l r k ：把 $T[l,r]$ 的 $k$ 次重复接到 $T$ 的末尾。 2 l r ：询问所有模式串在 $T[l,r]$ 中的出现次数之和。

输入格式

第一行两个整数 $n,q$。 接下来 $n$ 行，每行一个字符串，表示所有的模式串。 接下来一行一个字符串，表示文本串。 接下来 $q$ 行，每行表示一次操作。

输出格式

对于每个询问，输出一行一个整数表示答案对 $998244353$ 取模的值。

样例

3 2
a
aba
bb
abbaba
1 3 5 2
2 3 11

7

大样例

数据范围

$n,\sum|S_i|,q\le 5\times 10^5,q\le 10^5$，初始时 $|T|\le 10^5$，保证任意时刻 $|T|\le 10^{18},l,r\le |T|$，字符集为小写字母