如你所知，古人总是拘泥于旧形式，就像著名的孔乙己一样。来自大秦王朝的竞赛财务官——他为“复活节鸡”决赛选择了没有手机信号且没有干净自来水的温泉酒店——总是以一种奇怪的方式说话。例如，每当你向他展示一些他不愿意看到的真相时，他就会大喊“QFMYQ!!!!!! QFMYQ!!!!!! QFMYQ!!!!!!”（QFMYQ 意味着侵犯名誉权，其中文发音为“侵犯名誉权”）。

竞赛参与者，被称为“复活节鸡捕食者”，精通统计学和概率论，并将它们作为武器。当其他捕食者正在练习如何使用随机性和构造来击败中级 Boss Hash 时，头号种子选手 AntiLeaf 已经计划击败最终 Boss“复活节鸡”。为了做到这一点，他想要分析财务官所说词汇的频率，以便通过一些机器学习技巧来模仿他——这可一点也不古老。之后，AntiLeaf 可以通过模仿财务官轻松潜入竞技场而不触发警报，财务官将“复活节鸡”视为自己的财产并想从中获利。

财务官说的一个样本句子可以用一个包含小写英文字母的字符串 $s$ 表示。AntiLeaf 已经选择了 $n$ 个小写英文字母单词 $\{t_i\}$ 作为财务官经典语录的字典。对于 $t_i$，它有一个对应的价值 $v_i$，表示其经典程度。

为了预测财务官的行为，AntiLeaf 想要计算 $s$ 的每个前缀的得分，其定义如下：

• 字符串 $u$ 的得分定义为所有可能的提取方式的价值之和。
• 字符串 $u$ 的一个提取方式是 $u$ 中一组不相交的子串，其中每个子串都在字典中。
• 一个提取方式的价值是它所选择的所有子串的价值乘积。空集的价值定义为 $1$。
• $u$ 的两个子串如果位置不同，则被视为不同，因此字典中的一个字符串可以在一次提取中出现多次，它们都将计入乘积。
• 如果一个提取方式包含另一个提取方式所没有的子串，则这两个提取方式不同。

由于答案可能非常大，你只需要输出答案对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个字符串 $s$ ($1 \le |s| \le 2 \times 10^5$)，仅包含小写英文字母。 第二行包含一个正整数 $n$，表示经典语录的数量。 在接下来的 $n$ 行中，第 $i$ 行包含一个小写英文字母字符串 $t_i$ ($1 \le |t_i| \le 2 \times 10^5$) 和一个正整数 $v_i$ ($0 < v_i < 998\,244\,353$)，分别表示第 $i$ 个经典词汇及其价值。

保证所有 $t_i$ 两两不同，且它们的长度之和不超过 $2 \times 10^5$。

输出格式

在一行中输出 $|s|$ 个用空格分隔的数字，第 $i$ 个数字表示长度为 $i$ 的 $s$ 的前缀的答案，对 $998\,244\,353$ 取模。

样例

样例输入 1

ababa
2
aba 2
ba 3

样例输出 1

1 1 6 6 26

样例输入 2

qfmyqqfmyqqfmyq
2
qfmyq 111111
myqq 404968002

样例输出 2

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

样例输入 3

wwwsoupunetcom
2
money 999999
soup 998244352

样例输出 3

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

说明

以下是第一个样例最后一个答案的解释。让我们用点号表示未使用的字母，并用下划线和上划线表示不同的子串。

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

答案为： $(6 + 2 + 2 + 3 + 3 + 9 + 1) \pmod{998\,244\,353} = 26$。

第二个样例的输出为了打印方便进行了换行，在实际测试数据中它不包含额外的换行符。