3796: 任务(第四轮02)
题目描述
白浅妹妹有 n 个任务和一个长度为 n 的数组 a，数组中的第 i 个数字记为 ai 。
白浅妹妹的第 i 个任务是用一个字符串 si 描述的，意思是需要构造一个长度为 ai 的字 符串 S，使得 si 是 S 的子序列。
现在给定 q 次操作，每次给出三个正整数。其中第一个正整数为 0 或 1，表示操作类 型。
操作类型 0：给定 0, pos, val，表示将 apos 修改为 val
操作类型 1：给定 1, l, r，表示询问白浅妹妹从第 l 个任务一直完成到第 r 个任务，她总 共有多少种方案构造字符串。
请注意，在白浅妹妹完成 l ~ r 这些字符串的过程的若干方案中，只要有任何一个任务构 造的字符串不同，我们则认为这是不同的方案。
由于答案可能很大，请输出答案对 998244353 取模之后的结果。
大样例属于 50% 的数据范围：sample.zip
输入
第一行输入两个正整数 n, q
接下来 n 行，分别表示所有的 si
接下来一行给出 n 个由空格隔开的正整数，表示数组 a，
接下来 q 行， 每行给出三个正整数， 意义如题面所示。三个正整数中的第一个正整数为 0 或 1，表示两种操作。
输出
对于每个操作 1，输出一行一个正整数表示答案对 998244353 取模之后的结果。
样例输入 复制
3 4
ab
b
c
3 2 1
1 1 1
1 2 2
1 1 2
1 3 3样例输出 复制
76
51
3876
1提示
【样例 1 输入】
3 4
ab
b
c
3 2 1
1 1 1
1 2 2
1 1 2
1 3 3
【样例 1 输出】
76
51
3876
1
【样例 2 输入】
2 3
a
bc
2 6
1 1 2 0 2 3 1 2 2
【样例 2 输出】
315251451
76
【备注】
对于 20% 的数据，有 1 ≤ n, q ≤ 10， 1 ≤ ai, |si | ≤ 5
对于 50% 的数据，有 1 ≤ n, q ≤ 10^3, ∑ |si | ≤ 1000
对于 70% 的数据，有 1 ≤ n, ai ≤ 10^5, 1 ≤ q ≤ 5 ∗ 10^5, 1 ≤ |si | ≤ 10^3
对于 100% 的数据，有 1 ≤ n, ai ≤ 10^5, 1 ≤ q ≤ 5 ∗ 10^5, ∑ |si | ≤ 3 ∗ 10^5