给定 $N$ 个天平，天平两侧的质量忽略不计。天平的编号为 $1$ 到 $N$。在天平的每一侧，要么是另一个天平，要么是一个单个砝码（具有非零质量）。编号为 $1$ 的天平放置在地面上，而其他所有天平都放置在另一个天平上。注意，这意味着总共有 $N+1$ 个砝码。砝码的编号为 $1$ 到 $N+1$，每个砝码都有一个整数质量：$w_1, w_2, \dots, w_{N+1}$。

下图展示了本题末尾样例测试用例中三个天平和四个砝码的设置。正体数字表示天平和砝码的编号，斜体数字表示砝码的质量。例如，编号为 $2$ 的天平位于编号为 $1$ 的天平的左侧，而编号为 $2$ 且质量为 $6$ 的砝码位于编号为 $1$ 的天平的右侧。

如果一个天平左侧的总质量与右侧的总质量相同，我们称该天平是平衡的。如果一个天平是平衡的，且其两侧要么是超平衡天平，要么是砝码，我们称该天平是超平衡的。

例如，在上图中，只有天平 $3$ 是平衡的（也是超平衡的），但如果我们把砝码 $3$ 和 $4$ 的质量都增加到 $1.5$，那么所有三个天平都将变得超平衡。然而，如果我们改为将砝码 $1$ 的质量增加到 $4$，天平 $1$ 将变得平衡但不是超平衡，因为天平 $2$ 仍然不平衡。

我们现在需要处理 $Q$ 次操作，操作分为两种类型：

• $1 \ k \ w$：将砝码 $k$ 的质量更改为整数 $w$。
• $2 \ s$：假设我们想让天平 $s$ 变得超平衡。我们可以使用魔法让一些砝码变得更重！注意，这些新的质量值不一定是整数。为了使 $s$ 变得超平衡，天平 $s$ 上的最小总质量是多少？由于这个数字可能非常大，请输出其对 $998\,244\,353$ 取模的结果。可以证明，在给定约束条件下，结果总是一个整数。

注意，类型 $1$ 的操作会改变树的结构，而类型 $2$ 的操作不会。

输入格式

第一行包含两个整数：$N$ 和 $Q$。

接下来的 $N$ 行中，第 $i$ 行（$i \in \{1, \dots, N\}$）包含两对字符和数字，每对描述了第 $i$ 个天平的一侧：字符为 'S'（天平）或 'W'（砝码），表示天平给定侧物体的类型，整数表示对应项的编号。保证天平永远不会放置在编号更大的天平上。

接下来一行包含 $N+1$ 个整数 $w_1, w_2, \dots, w_{N+1}$，表示砝码的质量。

最后 $Q$ 行表示操作。每行要么是 $1 \ k \ w$ 的形式，要么是 $2 \ s$ 的形式，如题目描述中所述。

输出格式

对于每种类型的第二个操作，在单独的一行中输出相应的最小总质量对 $998\,244\,353$ 取模的结果。

数据范围

• $1 \le N \le 2 \cdot 10^5$
• $1 \le Q \le 2 \cdot 10^5$
• $1 \le w_i \le 10^9$
• 对于类型 $1$ 的操作：$1 \le k \le N+1$
• 对于类型 $1$ 的操作：$1 \le w \le 10^9$
• 对于类型 $2$ 的操作：$1 \le s \le N$

子任务

对于子任务 $2-4$，定义砝码的深度为它所放置的天平数量（直接或间接）。

1. (9 分) 每个天平的至少一侧都有一个砝码。
2. (8 分) 每个砝码的深度相同。
3. (24 分) 每个砝码的深度小于 $30$。此外，$N, Q \le 5000$。
4. (14 分) 每个砝码的深度小于 $30$。
5. (14 分) $N, Q \le 5000$。
6. (31 分) 无附加约束。

样例

输入 1

3 5
S 2 W 2
W 1 S 3
W 4 W 3
3 6 1 1
2 2
2 1
1 3 2
2 1
2 3

输出 1

6
12
16
4

说明

为了使天平 $2$ 超平衡，我们将砝码 $3$ 和 $4$ 的质量都增加到 $1.5$。结果，天平 $2$ 和 $3$ 都将平衡，因此 $2$ 是超平衡的。天平 $2$ 上的总质量为 $3 + 1.5 + 1.5 = 6$。当我们这样做时，天平 $1$ 也将平衡，因此它也是超平衡的，总质量为 $6 + 3 + 1.5 + 1.5 = 12$。当我们把砝码 $3$ 的质量改为 $2$ 时，这不再有效。因此，为了使天平 $1$ 超平衡，我们可以使砝码 $1$ 的质量为 $4$，砝码 $2$ 的质量为 $8$，砝码 $4$ 的质量为 $2$。总质量将为 $8 + 4 + 2 + 2 = 16$。