给出两棵大小均为 $n$ 的树，节点编号均为 $1 \sim n$，边带正权。

有 $Q$ 次询问，每次询问给出两个正整数 $a, b$ ($1 \leq a, b \leq n$)，你需要找到一个节点 $x$，使得 $x$ 在第一棵树上到 $a$ 的距离加上 $x$ 在第二棵树上到 $b$ 的距离之和最大，你只需要求出这个最大值即可。

数据范围：$1 \leq n \leq 10^5$，$1 \leq q \leq 5 \times 10^5$，$1 \leq w \leq 10^9$。

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

给出一棵包含 $n$ 个点的有根树 $T$，根节点为 $1$。给出一个大小为 $m$ 的关键点集合 $S$。

你需要求出有多少个不同的有根树 $T'$，满足对于任意 $x, y \in S$，均有 $\mathrm{LCA}_T(x, y) = \mathrm{LCA}_{T'}(x, y)$。答案对 $998244353$ 取模。

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

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

对于一棵树 $T$，定义 $P(T)$ 表示对 $T$ 生成 Prufer 序列时，最后剩下的两个节点之中不是 $n$ 的那一个。

给出一个包含 $n$ 个点 $m$ 条边的森林。对于每一个 $v$ ($1 \leq v \leq n$)，计算有多少种加边方式，使得原图变成一棵树 $T$，且 $P(T) = v$。答案对 $998244353$ 取模。

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

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

有三种类型的礼物，价值分别为 $a, b, c$。初始时，恰好拥有每一种礼物各一份。

给出两个整数 $m$ 与 $k$。你可以进行若干次操作，每次操作形如以下的两种：

• 创造：选择一种礼物类型，并额外制作一份该类型的礼物。消耗 $x$ 点法力值，其中 $x \in \{ a, b, c \}$ 为所选礼物类型的价值。
• 复制：选择一种礼物类型，并复制该类型的所有礼物。消耗 $k$ 点法力值。

你需要求出，使得礼物价值总和是 $m$ 的倍数时，所需的最小法力值。

数据范围：$1 \leq a < b < c < m \leq 5 \times 10^5$，$1 \leq k \leq 5 \times 10^5$，$1 \leq \sum m, \sum k \leq 5 \times 10^5$。

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

圆环上有 $2n$ 个等间距的点，按顺时针顺序标记为 $1, 2, \cdots, 2n$。有 $n$ 条具有不同端点的弦，其中第 $i$ 条弦连接 $a_i, b_i$。现在按照顺序依次连接这 $n$ 条弦。

每当连接完前 $\ell$ 条弦以后，考虑这 $\ell$ 条弦的任意非空子集 $S$。设 $S$ 中元素的索引分别为 $c_1, c_2, \cdots, c_m$，若对于所有的 $1 \leq i < m$，都满足弦 $c_i$ 与弦 $c_{i + 1}$ 相交，则称 $S$ 为一条链。

当且仅当，每一条弦在前 $\ell$ 条弦的所有子集链中出现偶数次时，称这些弦是紧密连接的。

对于 $1$ 到 $n$ 的每一个 $\ell$，你都需要判断前 $\ell$ 条弦是否紧密连接。

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

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

This is an interactive problem.

对于 $1, \cdots, n$，有一个隐藏的序列 $a_i$，其中 $a_i$ 表示数字 $i$ 的颜色。

有一个队列（初始为空），可以进行以下两种操作：

• + id：将元素 $\mathrm{id}$ 加入队列末尾。
• -：将队列开头的元素弹出。

每次操作之后，你都会得知当前队列中共有多少种不同的元素。

你的目标是，将所有元素按照颜色分组，依次给出每个组中的元素。

数据范围：$1 \leq n \leq 500$，操作至多进行 $35000$ 次。交互器不自适应。

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

给出一个长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$。有一个指针 $p$（初始时 $p = 1$）。

有 $Q$ 次操作，每次操作为以下三种之一：

• <：令 $p \gets p - 1$。
• >：令 $p \gets p + 1$。
• ! v：令 $a_p \gets v$，求出整个序列的严格最长上升子序列（LIS）。

数据范围：$2 \leq n \leq 2\times 10^5$，$1 \leq Q \leq 5 \times 10^5$，$1\leq a_i, v \leq 10^6$。

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

已知一个字符串 $S$ 的长度为 $n$，字符集大小为 $m$。现在均匀随机地生成该字符串 $S$。

记随机变量 $X$ 表示该字符串 $S$ 中回文子串的数量，求 $E(X^2)$。答案对给定质数 $p$ 取模。

数据范围：$1 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 10^7$，$m < p < 10^9$。

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

给出一个包含 $n$ 个点 $m$ 条边的带权无向图。

你需要找出 $n - 1$ 条边，使得这些边的权值之和最小，且不构成一棵树。

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

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

给出一个长度为 $n$ 的非递增序列 $a_1, a_2, \cdots, a_n$（满足 $a_1 \geq a_2 \geq \cdots \geq a_n$）。

有 $Q$ 次查询，每次查询给出 $l, r, x$，你会依次遍历 $a_l, a_{l + 1}, \cdots, a_r$，你有一个计数器 $s$（初始 $s = 0$），每次将当前遍历到的数累加进 $s$，若任意时刻 $s \geq x$，你就会将 $s$ 清零。你需要求出遍历结束时，将 $s$ 清零的次数以及最后 $s$ 的值。

数据范围：$1 \leq n, Q \leq 1.5 \times 10^5$，$1 \leq a_i, x \leq 10^9$，$1 \leq l \leq r \leq n$。

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