T139824 「Beta2020」魔法祭坛

**本题时限已开至2s** lzqy 是一名魔法师，ta 控制着一个祭坛。现在，有些数学上的问题需要你的帮助。

祭坛上有 $n$ 个魔法嵌位。目前，lzqy 手中有 $m$ 种宝石，第 $i$ 种宝石有无限颗，价值为 $w_i$。lzqy 需要在祭坛的每个魔法嵌位上摆放一颗宝石。设第 $i$ 个魔法嵌位所放的魔法石的价值为 $G(i)$，则此祭坛运法之后可获得的魔法力为： $$\prod_{i=1}^{n}G(i)$$ 显然，魔法石的摆放方式不止一种，所有摆放方式可以获得的魔法力的和即为祭坛可获得的最终魔法力。 （**其中，若 $n=0$，祭坛可获得的最终魔法力为 $1$**） ---- 天有不测风云，在祭坛周围经常会有暗势力出没。暗势力有一个非常强大的神器——“恶魔戟”。“恶魔戟”可以毁灭掉 $2^k$ 个魔法嵌位。而且暗势力每次都要尽量毁灭掉最多的魔法嵌位（如果魔法嵌位归零，则无法毁灭）。 所幸，lzqy 也有一个非常强大的神器——“天乩”。“天乩”可以召唤 $2^k$ 个魔法嵌位。但因为 lzqy 实在太蒻了，以至于 ta 最多可以召唤大于现有魔法嵌位的最少魔法嵌位。 lzqy 与暗势力共会使用他们的神器 $s$ 次，其神器的表示如下： 恶魔戟： `DH` 天乩：`CS` 对于 lzqy 和暗势力的每一次行动，输出祭坛可获得的最终魔法力。

第一行三个数 $n,m,s$，其中 $s$ 代表 lzqy 和暗势力共行动 $s$ 次。 第二行 $m$ 个数，第 $i$ 个数为 $w_i$。 接下来 $s$ 行，每行一个操作 （`DH` 或 `CS`）。

输出共 $s+1$ 个数，即未操作时的最终魔法力与每次操作过后祭坛可获得的最终魔法力，每行一个数。 **注：每一次操作时，祭坛的魔法嵌位数量继承上次操作后的数量。**

**为了方便选手们进行高精度运算，我们提供 [**NTT高精乘**](https://www.luogu.com.cn/paste/acwytjy6) 模板，选手们可根据自己的需要使用该类。** ### 数据范围与约定 |Subtask|分值|数据范围|特殊条件| |:-:|:-:|:-:|:-:| |$1$|$5$|$1≤w_i≤10\quad 1≤n≤10 \quad 1≤m≤10$|$s=0$ |$2$|$20$|$1≤w_i≤10\quad 1≤n≤10 \quad 1≤m≤100\quad 0≤s≤100$|无 |$3$|$75$|$1≤w_i≤10^{4}\quad 1≤n≤100 \quad 1≤m≤100\quad 0≤s≤100$|无