2020年新形冠状病毒袭卷全球，波及所有人生活的方方面面，包括只能在家网上比赛的你。

冠状病毒基因组为线性单股正链的 RNA，RNA 的碱基主要有4种，即 A (腺嘌呤)、 G (鸟嘌呤)、 C (胞嘧啶)、 U (尿嘧啶)。因此冠状病毒的 RNA 序列可以由包含 A,G,C,U 四种字母组成的序列表示。

病毒的合成蛋白的过程是由 RNA 指导的。假设每种碱基对应的一种氨基酸，氨基酸通过RNA序列指导组装成蛋白质，组装蛋白质只能从 RNA 序列某个位置开始一直组装到末尾。因此 RNA 尾部序列决定着病毒能合成的蛋白质的结构和种类。自然的鬼斧神工很擅长对称美。即使是对人类凶狠残暴的病毒也遵循对称美的。冠状病毒合成的蛋白全都是对称的。例如 RNA 序列 ACGGUGG ，氨基酸能从第三个碱基 G 开始组装，通过 GGUGG 序列组装出一种蛋白，或者从第六个碱基 G 开始，通过 GG 序列组装出一种蛋白。

也就是说，冠状病毒的 RNA 序列的尾部如果是  ，只有当满足以下条件时才能合成蛋白：

• 当 n 为奇数时：对于所有的  有
• 当 n 为偶数时：对于所有的  有

病毒合成的蛋白对人类危害程度是有蛋白的氨基酸种类和数量决定的,一种蛋白危害程度等于组成它的所有氨基酸决定危害的和。如果 A,C,G,U 对应的氨基酸决定的危害程度分别为 1,2,3,4 ，那么 GGUGG 序列指导合成的蛋白的危害程度为 16 ， GG 序列指导合成的危害程度为 6，一种冠状病毒对人类的危害程度是它能合成的所有种类的蛋白的危害程度的和。

如果冠状病毒一成不变，那么只要经过足够长时间的研究，人类一定能战胜它。但棘手的是冠状病毒是不断变异的，2019 年出现的 COVID-19 最为棘手。经过对已发现的冠状病毒进行研究，人类观察出了各种冠状病毒的变异的路线，它们都从一种古老的冠状病毒变异而来，它的 RNA 序列长度只有 1 。也就是说，除了最古老的种类之外，每个种类都是由一个先于它存在的一个种类变异而来的，并且它们变异的途径都是在 RNA 序列的末端新增一个碱基。为了研究方便，人类对各种冠状病毒进行了编号，最古老的编号为 1 。

为了实时监测冠状病毒对人类的影响，人类需要你在每产生一种变异的冠状病毒时，实时地计算每一种冠状病毒能合成的危害程度最大的蛋白的危害程度，并在最后计算出所有种类的冠状病毒的危害程度，也就是每种冠状病毒危害程度的总和。

第一行输入四个整数  ()，表示每种碱基对应氨基酸决定的危害程度。

第二行输入一个字符  ()，表示最古老种类的 RNA 序列。

从第三行开始，第 i 行输入一个整数  () 和一个字符  ，分别表示当前出现了第 i-1 号冠状病毒由  号病毒在RNA序列末端新增  变异产生了。() ，保证  是已出现的冠状病毒的编号。

 时是停止监测的信号，当出现  时，你应该停止监测，后面不会再有其他输入。

保证变异不会超过 500000 次

你需要在线地处理每次监测。为了体现这一点，本题的输入数据经过了加密。对每次输入的  ，记你的的上次输出为 lastans，则  的真实值应为 。其中  表示逻辑异或运算。特别地，如果当前未有过输出，lastans 的值为 0 。

第一行输出一个整数表示 1 号冠状病毒能合成的危害程度最大的蛋白的危害程度。

在出现每个  时，输出一个整数表示该种冠状病毒能合成的危害程度最大的蛋白的危害程度。

最后一行再输出一个整数表示已发现的所有冠状病毒对人类的危害程度。为防止输出数据过大，你只需要输出答案对 998244353 取模的结果。

1 2 3 4
A
0 C
0 A
6 C
6 U
0 A
6

1
2
4
4
4
6
25

4 3 2 1
A
5 A
10 A
14 A
14 A
12

4
8
12
12
12
88

第一个测试用例已经过加密，其真实情况如下：

1 号冠状病毒的RNA序列为 A ，能指导合成 1 种蛋白{ A }；

2 号冠状病毒从 1 号变异来，RNA 序列为 AC ，能指导合成 1 种蛋白{ C }；

3 号冠状病毒从 2 号变异来，RNA 序列为 ACA ，能指导合成 2 种蛋白{ A，ACA }；

4 号冠状病毒从 2 号变异来，RNA 序列为 ACC ，能指导合成 2 种蛋白{ C ， CC }；

5 号冠状病毒从 2 号变异来，RNA 序列为 ACU ，能指导合成 1 种蛋白{ U }；

6 号冠状病毒从 4 号变异来，RNA 序列为 ACCA ，能指导合成 2 种蛋白{ A ，ACCA }；