给定两个字符串 $$$S,T$$$，你需要判断 $$$S$$$ 是否同时是 $$$T$$$ 的前缀$$$^\dagger$$$且是 $$$T$$$ 的后缀$$$^\ddagger$$$。

$$$\dagger$$$ 前缀：指从字符串第一个字符开始，连续截取到任意位置所组成的字符串。例如：prefix 的前缀有 p，pre，prefix 等。

$$$\ddagger$$$ 后缀：指从字符串任意位置字符开始，连续截取到最后一位所组成的字符串。例如：suffix 的后缀有 x，fix，ffix，suffix 等。

给定一棵包含 $$$n$$$ 个节点的有根树 $$$T$$$，根节点为 $$$1$$$。

每个节点 $$$u$$$ 都有一个初始点权 $$$w_u$$$，且序列 $$$w_1, w_2, \dots, w_n$$$ 是 $$$0, 1, \dots, n-1$$$ 的一个排列$$$^\dagger$$$。

对于树上的任意节点 $$$u$$$，定义其子树权值 $$$V(u)$$$ 为： $$$$$$V(u) = \max_{v \in T_u} \Big( \text{MEX}^\ddagger \bigl( \text{path}(u, v) \bigr) \Bigr)$$$$$$

其中：$$$T_u$$$ 表示以 $$$u$$$ 为根的子树节点集合。$$$\text{path}(u, v)$$$ 表示从节点 $$$u$$$ 到节点 $$$v$$$ 的简单路径上的所有节点权值的集合。你的任务是求出所有 $$$1 \le u \le n$$$ 对应的 $$$V(u)$$$。

$$$\ddagger\ \text{MEX}(S)$$$：表示集合 $$$S$$$ 中未出现的最小非负整数。例如：$$$\text{MEX}(\{0, 1, 3\}) = 2$$$，$$$\text{MEX}(\{1, 2\}) = 0$$$。

$$$\ddagger$$$ 排列：由 $$$0, 1, \dots, n-1$$$ 共 $$$n$$$ 个不同整数组成的序列。每个数字在序列中恰好出现一次。例如：$$$(1,2,0,3)$$$ 是排列，而 $$$(1,2,2,0,1),(1,0,4,5),(0,2)$$$ 均不是排列。

给定一个 $$$n\times m$$$ 方格，其中坐标 $$$(x,y)$$$ 的高度表示为 $$$h_{x,y}$$$，初始均为高度为 $$$0$$$，超出边界外均属于围墙。

现在进行 $$$q$$$ 次操作，每次操作进行以下操作中的一种：

1. 将坐标 $$$(x_1,y_1)$$$ 到 $$$(x_2,y_2)$$$ 之间所有坐标 $$$h_{i,j}$$$ 高度增加 $$$k$$$。
2. 查询坐标 $$$(x,y)$$$ 十字范围内能看到$$$^\ast$$$的空地格子个数（包括自身位置）。

$$$\ast$$$ 对于两个格子 $$$(x_1,y_1),(x_2,y_2)$$$，如果 $$$(x_1,y_1)$$$ 能看到 $$$(x_2,y_2)$$$，则需要同时满足：

• $$$1\le x_2\le n$$$ 且 $$$1\le y_2 \le m$$$
• $$$x_1 = x_2$$$ 或者 $$$y_1 = y_2$$$。
• $$$h_{x_1,y_1} \ge h_{x_2,y_2}$$$。
• $$$(x_2,y_2)$$$ 四周至少一个格子是能被 $$$(x_1,y_1)$$$ 看到。即 $$$(x_2+1,y_2)$$$、$$$(x_2-1,y_2)$$$、$$$(x_2,y_2+1)$$$ 和 $$$(x_2,y_2-1)$$$ 中至少有一个格子可以被 $$$(x_1,y_1)$$$ 看到。

特别地，任何格子 $$$(x,y)$$$ 都能看到其所在位置的格子，即 $$$(x,y)$$$ 本身。

Kendieer 现在手头上有一个 $$$n\times m$$$ 的网格矩形，他觉得太空旷了，于是他决定塞一些 $$$2\times 2$$$ 的正方形进入该矩形之中。

不过对于每一个被填入矩形的正方形而言，都需要满足：

• 每个 $$$2 \times 2$$$ 的正方形必须恰好覆盖网格中的 $$$4$$$ 个完整小方格。
• 正方形不能超出 $$$n \times m$$$ 的矩形边界。
• 对于其他任意一个 $$$2\times 2$$$ 的正方形，与当前正方形接触的长度不超过 $$$1$$$。

例如以下放置方式：

不合法	合法	合法

Duanhen 看到这个问题之后，觉得太简单了，于是他破坏了 $$$k$$$ 个格子，使得这些格子均不可被正方形覆盖。

由于合法的填充方案太多了，Kendieer 多得数不过来，于是他向你请教一下一共有多少种本质不同$$$^\dagger$$$的合法放置方案，这个答案可能很大，你需要将答案对 $$$998244353$$$ 取模。

$$$\dagger$$$：两种方案被视为不同，当且仅当存在至少一个 $$$2 \times 2$$$ 的正方形位置，在一种方案中被放置而在另一种方案中未被放置。

Kendieer 有一个 $$$n\times m$$$ 的方格纸，初始时所有格子是白色的。

他涂黑了若干个格子，若我们将这些涂黑的格子视作一整个图形，他想知道这些格子所围成的图形的周长是多少。

给定一个长度为 $$$n$$$ 的序列 $$$a$$$，且这个序列保证单调不递减，即 $$$\forall 1\le i\lt n,a_i\le a_{i+1}$$$。

现在进行 $$$q$$$ 次询问，对于每次询问，求值为 $$$x$$$ 在序列 $$$a$$$ 中的索引，如果存在多个符合条件的索引任意一个即可，如果不存在则输出 -1。

自从上次之后，Kendieer 领略了更多关于哈密顿路径的知识，现在他决定向你提出一个挑战：

给定一个由 $$$n$$$ 个顶点组成的有向无环图 $$$G$$$，求对于该图 $$$G$$$，共有多少条不同的哈密顿路径$$$^\ast$$$，这个结果可能很大，你需要将结果对 $$$10^9 + 7$$$ 取模后输出。

$$$\ast$$$ 哈密顿路径：对于一个图上的路径，如果该路径满足过图上所有点有且仅有一次，则称这个路径为哈密顿路径。

将图中的每条边视为唯一的对象（例如按照输入顺序编号为 $$$1, 2, \dots, m$$$）。两条路径不同，当且仅当它们使用的边的编号序列不同。

给定一个长度为 $$$n$$$ 的合法括号串$$$^\dagger$$$ $$$S$$$，现在可以进行任意次以下操作（包含零次）：

• 选择一个区间 $$$[l,r]$$$，且满足子串$$$^\ddagger$$$ $$$S[l\dots r]$$$ 是 RBS。
• 翻转该区间。即将 $$$s_ls_{l+1}\dots s_{r-1}s_{r}$$$ 变成 $$$s_r,s_{r-1}\dots s_{l+1}s_l$$$。
• 将该区间原本的 ( 变成 )，) 变成 (。

例如：()(()) 选择区间 $$$[1,6]$$$ 操作后变成 (())()，(()(())) 选择区间 $$$[2,7]$$$ 操作后变成 ((())())。

求操作任意次括号串后，一共有多少种可能的合法括号串结果，这个答案可能很大，你需要输出答案对 $$$998244353$$$ 取模后的结果。

$$$\dagger$$$ 合法括号串（RBS）：我们定义以下字符串为 RBS。

• 空字符串是一个 RBS；
• 如果 $$$S$$$ 是一个 RBS，那么 $$$(S)$$$ 也是一个 RBS；
• 如果 $$$S$$$ 和 $$$T$$$ 都是 RBS，那么 $$$ST$$$（即 $$$S$$$ 和 $$$T$$$ 拼接）也是一个 RBS。

• ()() 是 RBS。
• (()()) 是 RBS。
• )(()() 不是 RBS。

$$$\ddagger$$$ 子串：字符串 $$$S$$$ 的一个子串是由 $$$S$$$ 中连续的一段字符组成的序列。具体地，对于字符串 $$$S = s_1s_2\dots s_n$$$，其子串 $$$S[i \dots j]$$$ ($$$1 \le i \le j \le n$$$) 定义为字符串 $$$s_i s_{i+1} \dots s_j$$$。

Kendieer 根本就不强！所以他要变得强起来，他想到了一个办法。

他有一个长度为 $$$n$$$ 序列 $$$a$$$，我们定义一个序列的能量为 $$$\sum_{i=1}^n a_i$$$，即这个序列所有元素的总和。

你可以对任意一个无前导零的数字执行任意次（包括 $$$0$$$ 次）以下操作，其代价为累加：

• 将该数字任意一个数位从 $$$x$$$ 修改到 $$$y$$$，其需要代价为 $$$|x-y|$$$，允许操作后的数字含有前导零。

例如：

• 从 $$$123$$$ 修改成 $$$223$$$ 代价为 $$$1$$$。
• 从 $$$235$$$ 修改成 $$$295$$$ 代价为 $$$6$$$。
• 从 $$$235$$$ 修改成 $$$325$$$ 代价为 $$$2$$$。

此外，我们定义最终能量为修改后的序列能量减去修改操作所需的代价。

现在，Kendieer 想最大化最终能量，从而显得他很强（其实并非强），请你输出这个序列可能的最大最终能量。

本题定义、输入格式、输出格式均与困难版本相同，在这个版本中，$$$n\le 2\times 10^5$$$，但你只需构造出任意符合条件的树即可。

排列：长度为 $$$n$$$ 的定义为由 $$$1\sim n$$$ 以不同顺序组成的序列，且每个元素恰好出现一次。例如 $$$[2,1,3],[2,4,1,3]$$$ 都是排列，而 $$$[4,1,2]$$$ 不是排列，因为 $$$3$$$ 没有出现，$$$[1,2,3,2]$$$ 不是排列，因为 $$$2$$$ 出现了 $$$2$$$ 次。

树的dfs序：对一棵树进行深度优先遍历（DFS），每当我们第一次访问某个节点时，就将该节点编号加入序列中。得到的访问顺序称为DFS 序。例如：

对于给定的树，$$$[1,2,3,4,5,6,7],[1,3,4,7,5,6,2],[3,4,1,2,7,5,6]$$$ 均是这棵树能形成的 dfs 序。$$$[1,2,4,3,5,6,7]$$$ 不是这棵树的 dfs 序，因为 $$$2$$$ 号点到 $$$4$$$ 号点存在未访问的 $$$3$$$ 号点，$$$[1,2,3,4,5,7,6]$$$ 不是这棵树的 dfs 序，因为子树 $$$5$$$ 不满足 DFS 遍历性质。

现在，给定 $$$2$$$ 个 $$$1\sim n$$$ 组成的排列，现在要求你构造一棵树，使得这棵树包含这两种dfs序，可以证明这样的树总是存在的。

本题定义、输入格式、输出格式均与简单版本相同，在这个版本中，$$$n\le 5000$$$，但你需要构造出符合条件的树且每个节点深度总和最大化的方案。

排列：长度为 $$$n$$$ 的定义为由 $$$1\sim n$$$ 以不同顺序组成的序列，且每个元素恰好出现一次。例如 $$$[2,1,3],[2,4,1,3]$$$ 都是排列，而 $$$[4,1,2]$$$ 不是排列，因为 $$$3$$$ 没有出现，$$$[1,2,3,2]$$$ 不是排列，因为 $$$2$$$ 出现了 $$$2$$$ 次。

树的dfs序：对一棵树进行深度优先遍历（DFS），每当我们第一次访问某个节点时，就将该节点编号加入序列中。得到的访问顺序称为DFS 序。例如：

对于给定的树，$$$[1,2,3,4,5,6,7],[1,3,4,7,5,6,2],[3,4,1,2,7,5,6]$$$ 均是这棵树能形成的 dfs 序。$$$[1,2,4,3,5,6,7]$$$ 不是这棵树的 dfs 序，因为 $$$2$$$ 号点到 $$$4$$$ 号点存在未访问的 $$$3$$$ 号点，$$$[1,2,3,4,5,7,6]$$$ 不是这棵树的 dfs 序，因为子树 $$$5$$$ 不满足 DFS 遍历性质。

树的深度：我们定义根节点的深度为 $$$1$$$。对于其他任意节点 $$$u$$$，其深度为 $$$u$$$ 的父节点的深度加 $$$1$$$。

现在，给定 $$$2$$$ 个 $$$1\sim n$$$ 组成的排列，现在要求你构造包含这两种dfs序的树，且使得每个节点深度总和最大化。可以证明无论序列如何，总是存在对应的树。

给定一个长度为 $$$n$$$ 的序列 $$$a$$$，我们定义一个子区间$$$^\dagger$$$ $$$[l,r]$$$ 的权值 $$$f(a[l\dots r]) = \max_{i=l}^{r} a_i+\min_{i=l}^r a_i$$$，即区间最大值与区间最小值之和。

你需要求出所有子区间权值的总和，即求 $$$\sum_{i=1}^n\sum_{j=i}^n f(a[i\dots j])$$$。

$$$\dagger$$$ 子区间：一个序列 $$$a$$$ 的子区间 $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$) 定义为原序列中连续的一段元素：$$$a_l, a_{l+1}, \dots, a_r$$$，记作 $$$a[l\dots r]$$$ 的总和值。

Kendieer 遇到了一个困难的图论问题，这个问题同时涉及到了完全图和二分图概念问题，这令他这个图论新手头晕目眩。

我们定义如果数量为 $$$n$$$ 个顶点的完全图 $$$^\dagger$$$ 是二分图$$$^\ddagger$$$，则这个图则被称之为完全好图。

现在你需要求对于顶点个数 $$$l\le n\le r$$$ 所有 $$$n$$$ 的情况下，其中完全好图的个数。

$$$\dagger$$$ 完全图：对于一个由 $$$m$$$ 个顶点组成的完全图，满足任意两个不同顶点 $$$u,v$$$ 之间都存在边 $$$(u,v)$$$。

$$$\ddagger$$$ 二分图：对于一个图，将所有点划分至两个集合，若存在一种划分方式，所有边都满足 $$$(u,v)$$$ 连接的两个顶点 $$$u,v$$$ 不属于同一个集合，则这样的图称之为二分图。