给出一棵包含 $n$ 个节点的树。每个节点都有一个显示值（初始均为 $0$）。定义 $dist(u, v)$ 表示节点 $u, v$ 之间的边数。

有 $Q$ 次操作，每次操作形如以下的两种：

• 1 v l r k $w_0 \ w_1 \ \dots \ w_k$：表示从节点 $v$ 发起广播，对于所有满足 $l \leq dist(u, v) \leq r$ 的节点 $u$，记 $d = dist(u, v)$，将节点 $u$ 的显示值修改为

$$\left(\sum_{i = 0}^k w_id^i\right) \bmod 998244353$$

• 2 x：查询节点 $x$ 当前的显示值。

数据范围：$1 \leq n, Q \leq 10^5$，$0 \leq k \leq 10$，$0 \leq w_i < 998244353$。

时空限制：$10$s / $512$MiB。

有一排相连的 $n$ 块石头，第 $i$ 块石头的高度为 $h_i$。每当下雨时的水位高度 $H$ 大于 $h_i$ 时，第 $i$ 块石头就会被淹没。所有露出的石头会形成若干个连续段。

有 $Q$ 次询问，每次询问给出 $l, r$，你需要求出：只考虑区间 $[l, r]$ 内的石头，当使得露出的石头形成至少 $k$ 个连续段时，下雨的水位 $H$ 最高是多少。

数据范围：$1 \leq n, Q, k \leq 10^6$，$1 \leq h_i \leq 10^6$，$1 \leq l \leq r \leq n$。

时空限制：$5$s / $512$MiB。

给出一个数组 $a_1, \dots, a_n$，其中 $-1 \leq a_i \leq n$。

对于每个 $i$ ($1 \leq i \leq n$)，求出 $f([a_1, \dots, a_i])$，其中 $f(s)$ 对于数组 $s$ 定义如下：

• 对于所有将 $s$ 中的 $-1$ 替换成 $[0, n]$ 之间整数的不同方案，$f(s)$ 为这些方案对应数组的 MEX 之和。

保证 $-1$ 的数量不超过 $300$。

数据范围：$1 \leq n \leq 2\times 10^5$，$-1 \leq a_i \leq n$。

时空限制：$5$s / $512$MiB。

对于一个长度为 $n$ 的排列 $p$，记 $a_i$ 表示有多少个区间 $[l, r]$ ($1 \leq l \leq r \leq n$) 满足 $p_l, \dots, p_r$ 中的最小值为 $p_i$。

现给出 $a_1, \dots, a_n$，求出有多少个可能的排列 $p$。

数据范围：$1 \leq n \leq 5\times 10^5$，$1 \leq a_i \leq 10^{12}$。

时空限制：$2$s / $256$MiB。

一瓶饮料售价 $1$ 元。

每次小明喝完一瓶饮料，他会以 $p = \frac{a}{b}$ 的概率获奖。如果获奖，他将得到 $c$ 元；否则，他什么也得不到。

他得到的钱可以用来购买更多饮料。每瓶饮料的获奖事件相互独立。小明一开始有 $n$ 元。求他恰好喝完 $m$ 瓶饮料后花光所有钱的概率。答案对 $998244353$ 取模。

数据范围：$1 \leq T \leq 2\times 10^5$，$1 \leq n, m, c \leq 2 \times 10^6$，$0 \leq a < b \leq 998244353$。

时空限制：$2$s / $1024$MiB

给出一个长度为 $n$ 的字符串 $S$ 和一个长度为 $n$ 的序列 $a_1, \dots, a_n$。有 $Q$ 次询问。每次询问给出一个字符串 $t$：

如果一个区间 $[l, r]$ ($1 \leq l \leq r \leq n$) 满足 $t$ 是 $S[l : r]$ 的子串，那么称这个区间为好区间。

求所有好区间的区间和的最大值，以及所有好区间的区间和之和（对 $998244353$ 取模）。保证至少存在一个好区间。

数据范围：$1 \leq n \leq 10^5$，$1 \leq q \leq 3\times 10^5$，$-10^9 \leq a_i\leq 10^9$，$1 \leq \sum |t| \leq 3\times 10^5$。

时空限制：$5$s / $1024$MiB。

对于一个长度为 $m$ 的非负数组 $b$，定义 $f(b)$ 等于

$$\max_{x\geq 0}\left\{ \max_{i = 1}^m(b_i \operatorname{|} x) - \min_{i = 1}^m(b_i \operatorname{|} x) \right\}$$

给出值域上限 $n$ 以及操作次数 $Q$，初始时数组 $a$ 为空，有 $Q$ 次强制在线的操作：每次操作在数组 $a$ 的末尾加入一个数 $v$ ($0 \leq v < n$)，你需要求出此时的 $f(a)$。

数据范围：$1 \leq n \leq 2^{22}$，$1 \leq Q \leq 10^6$。

时空限制：$3$s / $256$MiB

有一个长度为 $n$ 的数组 $a$，初始满足 $a_i = i$。对于一个参数 $k$ ($1 \leq k \leq \lfloor \frac{n - 1}{2} \rfloor$)，你可以对 $a$ 进行任意次数（可能为 $0$ 次）的以下操作：

• 从 $a$ 中选择一个长度为 $2k + 1$ 的子序列，然后删除其中的前 $k$ 个元素和后 $k$ 个元素。

求对于每个 $k$ ($1 \leq k \leq \lfloor \frac{n - 1}{2} \rfloor$)，最终可以得到多少个不同的数组 $a$。

数据范围：$3 \leq n \leq 10^6$。

时空限制：$3$s / $256$MiB

给出一棵包含 $n$ 个点的树。

定义 $f(l, r)$ 表示包含 $l, \dots, r$ 的最小连通块的大小，求 $\sum_{1 \leq l \leq r \leq n} f(l, r)$。

数据范围：$1 \leq n \leq 10^5$。

时空限制：$1$s / $512$MiB。

对于一个长度为 $n$ 的排列 $p$，记 $k = \lceil \log_2(n + 1) \rceil$。

系统原本会生成 $k$ 个长度为 $n$ 的 $01$ 串，对于第 $j$ ($0 \leq j < k$) 个二进制位，$01$ 串的第 $i$ 个字符表示 $p_i$ 的第 $j$ 个二进制位的值。

现在，这 $k$ 个 $01$ 串被打乱，因此不知道每个 $01$ 串对应哪个二进制位。

给定打乱后的 $k$ 个 $01$ 串，求有多少个不同的关于 $n$ 的排列 $p$，使得至少存在一种 $01$ 串与二进制位的对应关系，能够还原出 $p$。

数据范围：$1 \leq n \leq 2\times 10^5$。

时空限制：$2$s / $512$MiB。