410050: GYM103931 L Last Warning of the Competition Finance Officer

L. Last Warning of the Competition Finance Officertime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

As you might know, people from the ancient always stick to the old form, like the famous Kong Yiji. The Competition Finance Officer from the great Qin dynasty – who chose the Hot Spring Hotel without cell phone signal and clean tap water for Easter Chicken Finals – always speaks in an odd manner. For example, whenever you present some facts to him that he is unwilling to see, he would shout out 'QFMYQ!!!!!! QFMYQ!!!!!! QFMYQ!!!!!!' (QFMYQ means violation of the right of reputation, and its Chinese pronunciation is 'qin fan ming yu quan').

The competition participants, known as Easter Chicken predators, understand statistics and probabilities well and use them as weapons. As other predators are practicing how to use randomness and constructions to kill the intermediate boss Hash, AntiLeaf, the No. 1 seed, is already planning to kill the final boss Easter Chicken. To do so, he wants to analyze the frequency of words spoken by the Finance Officer in order to imitate him by some machine learning tricks – something not ancient at all. After that, AntiLeaf can easily sneak into the arena without triggering warnings by imitating the Finance Officer, who considers the Easter Chicken his own property and wants to make money from it.

A sample sentence said by the Finance Officer can be represented by a string $$$s$$$ containing lowercase English letters. AntiLeaf has already selected $$$n$$$ lowercase English words $$$\{t_i\}$$$ as the dictionary of Finance Officer's classic quotes. For $$$t_i$$$, it has a corresponding value $$$v_i$$$, denoting how classic it is.

To predict the Finance Officer's behavior, AntiLeaf want to calculate the score of each prefix of $$$s$$$, which is defined as follows:

• The score of a string $$$u$$$ is defined as the sum of values of all possible extractions.
• An extraction of a string $$$u$$$, is a set of disjoint substrings in $$$u$$$, each of which is in the dictionary.
• The value of an extraction is the product of values of all substrings it has chosen. The the value of empty set is defined as $$$1$$$.
• Two substrings of $$$u$$$ are considered different by their positions in $$$u$$$, so a string in the dictionary can appear more than once in an extraction, and they would all contribute to the product.
• Two extractions from $$$u$$$ are different, if one contains a substring that the other doesn't have.

Since the answers may be very huge, you just need to output the answers modulo $$$998\,244\,353$$$.

Input

The first line of input contains a string $$$s$$$ ($$$1\le |s| \le 2 \times 10^5$$$), which contains only lowercase English letters.

The second line contains a positive integer $$$n$$$, denoting the number of classical quotes.

In the following $$$n$$$ lines, the $$$i$$$-th line contains a lowercase English string $$$t_i$$$ ($$$1 \le |t_i| \le 2 \times 10^5$$$) and a positive integer $$$v_i$$$ ($$$0 < v_i < 998\,244\,353$$$), denoting the $$$i$$$-th classical word and the value of it.

It is guaranteed that all of $$$t_i$$$ are pairwise distinct, and the sum of their lengths does not exceed $$$2 \times 10^5$$$, and

Output

Output $$$|s|$$$ numbers separated with spaces in a single line, the $$$i$$$-th of which represents the answer of the prefix of $$$s$$$ with length $$$i$$$, modulo $$$998\,244\,353$$$.

ExamplesInput

ababa
2
aba 2
ba 3

Output

1 1 6 6 26

Input

qfmyqqfmyqqfmyq
2
qfmyq 111111
myqq 404968002

Output

1 1 1 1 111112 405079114 405079114
405079114 405079114 771912310
239058268 239058268 239058268
239058268 31169271

Input

wwwsoupunetcom
2
money 999999
soup 998244352

Output

1 1 1 1 1 1 0 0 0 0 0 0 0 0

Note

Here is the explanation of the last answer of the first example. Let us denote the unused letters with dots, and different substrings are denoted by underlines and overlines.

• $$$\underline{\texttt{aba}}\overline{\texttt{ba}}$$$ $$$6 = 2 \times 3$$$
• $$$\underline{\texttt{aba}}\texttt{..}$$$ $$$2$$$
• $$$\texttt{..}\underline{\texttt{aba}}$$$ $$$2$$$
• $$$\texttt{.}\underline{\texttt{ba}}\texttt{..}$$$ $$$3$$$
• $$$\texttt{.}\texttt{..}\underline{\texttt{ba}}$$$ $$$3$$$
• $$$\texttt{.}\underline{\texttt{ba}}\overline{\texttt{ba}}$$$ $$$9 = 3 \times 3$$$
• $$$\texttt{.....}$$$ $$$1$$$

The answer is $$$$$$(6 + 2 + 2 + 3 + 3 + 9 + 1) \bmod 998\,244\,353 = 26.$$$$$$

The second sample's output is wrapped for the convenience of printing, in real test data it contains no extra line breaks.