409160: GYM103447 L Karshilov's Matching Problem

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Karshilov's Matching Problemtime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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?

Input

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.

Output

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

ExampleInput
2
479 1
666 2
666479
5
2 6
1 3 6
2 5
1 4 2
2 4
Output
3
6
0

加入题单

上一题 下一题 算法标签: