409160: GYM103447 L Karshilov's Matching Problem

This season, Karshilov was forced to retirec since he was abandoned by his teammates. However, it does not affect his enthusiasm for studying matching problems.

There are $$$n$$$ lucky digital strings $$$t_1, t_2, \cdots, t_n$$$, where the $$$i$$$-th string has a lucky value $$$w_i$$$.

For any string $$$S$$$, define that $$$f(S)=\sum_{i=1}^n occur(S,t_i)\cdot w_i \pmod {998244353}$$$, where $$$occur(S,t_i)$$$ is the number of occurrences of string $$$t_i$$$ in $$$S$$$. For example, $$$occur(12121,121)=2$$$ and $$$occur(000,0)=3$$$.

Now, Karshilov has a string $$$S$$$ and he will do $$$m$$$ operations one by one. Each operation is of one of the following two types:

1. $$$1\;l\;c$$$. Change all the last $$$l$$$ characters of $$$S$$$, that is, $$$S_{|S|-l+1},S_{|S|-l+2},\cdots,S_{|S|}$$$ into $$$c$$$.
2. $$$2\;l$$$. Determine the value of $$$f(S[1,l])$$$, where $$$S[1,l]$$$ means the string formed by first $$$l$$$ characters of $$$S$$$, which is $$$S_1S_2\cdots S_l$$$.

Can you help Karshilov to find the answers to all operations of the second type?

The first line contains one integer $$$n\,(1\le n \le 10^5)$$$, denoting the number of lucky strings.

Next $$$n$$$ lines each contains one string $$$t_i\,(1\le|t_i|\le 10^5)$$$ and one integer $$$w_i\,(0\le w_i< 998244353)$$$, denoting the given lucky strings and the lucky values.

The next line contains one string $$$S\,(1\le |S| \le 3\times 10^5)$$$, denoting the string given by Karshilov.

The next line contains one integer $$$m\,(1\le m \le 3\times 10^5)$$$, denoting the number of operations.

Next $$$m$$$ lines each is of one of following two types:

1. $$$1\;l\;c\,(1\le l \le |S|,c\in\{0,1,\cdots 9\})$$$
2. $$$2\;l\,(1\le l \le |S|)$$$

It is guaranteed that $$$\sum |t_i| \le 10^5$$$ and the given strings only contain digitals.

For each operation of the second type, output one line containing one integer, denoting the answer.

2
479 1
666 2
666479
5
2 6
1 3 6
2 5
1 4 2
2 4

3
6
0