你需要动态维护一个字符串 $S$，有 $n$ 次操作：

• 1 x c：在 $S$ 末尾加上 $x$ 个字符 $c$，保证操作前 $S$ 末尾字符不为 $c$；
• 2 x：撤销第 $x$ 次操作后的所有操作；

输出每次操作结束 $S$ 的每个前缀的最长真 Border 的长度的和。

$1\le n\le 10^5$，$1\le x\le 10^4$。

给定一张 $n$ 个点的边集为 $E$ 的无向图和一个正整数 $K$，你要给每个点分配一个非负实数点权 $s_i$，满足 $\sum s_i=K$ 且 $\sum\limits_{(u,v)\in E}s_u\times s_v$ 最大。输出该式子的最大值（保留 $6$ 位小数）。

$1\le n\le 40$，$1\le K\le 1000$。

给定 $n,m$ 和一个 $n$ 的排列 $P$。重复进行如下操作 $m$ 次：

• 选定 $1\le i\le j\le n$，并将 $P_i,P_{i+1},..,P_j$ 翻转。

对于所有 $(\frac{n(n+1)}{2})^m$ 种方案，计算 $\sum_{i<j}[P_i>P_j](j-i)$ 的值的和。

$1\le n,m\le 2\times 10^5$。

给你两个 $2n$ 的排列 $P,Q$，你要构造一个长 $2n$ 的括号序列 $S$。定义一个 $2n$ 的排列 $C$ 是合法的，当且仅当按照 $S_{C_1}S_{C_2}\cdots S_{C_{2n}}$ 是合法括号序列。你构造的 $S$ 要满足 $P$ 是字典序最小的合法排列，$Q$ 是最大的。

$1\le n\le 2\times 10^5$。

黑板上有 $n$ 个正整数 $a_i$，再给定一个正整数 $k$，可进行操作如下：

• 选择一个黑板上的正整数 $x$ 和两个满足 $y+z=x+k$ 的正整数 $y,z$，删掉 $x$，在黑板上写上 $y$ 和 $z$；

求最少进行多少次操作可以让黑板上的数相等，或报告无解。

$1\le n\le 2\times 10^5$，$1\le a_i,k\le 10^{12}$。

有 $m$ 个卡，第 $i$ 个卡每次抽到的概率都是 $\frac{a_i}{n}$，其中 $n=\sum\limits_{i=1}^m a_i$，求集齐所有卡期望需要多少次，对 $998244353$ 取模。

$1\le n,m\le 10^5$，$1\le a_i\le n$。

有 $m$ 种货币，第 $i$ 种面值为 $2^{i-1}$，求凑出 $n$ 元钱有多少种方案数，对 $998244353$ 取模。

Ex：求 $n$ 有多少种 $m$ 位 $k$ 进制表示（每一位的数字无上限）。

$1\le m\le 30$，$0\le n\le 10^{18}$，$2\le k\le 16$。