如果一个字符串可以被拆分为 $\text{AABB}$ 的形式，其中 $\text{A}$ 和 $\text{B}$ 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。

一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

• 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
• 在一个拆分中，允许出现 $\text{A}=\text{B}$ 。
• 字符串本身也是它的一个子串。

NOI2018 前的联考第一场。

走上计算几何的漫漫不归路（雾）。

小 N 是蔬菜仓库的管理员，负责设计蔬菜的销售方案。

在蔬菜仓库中，共存放有 $n$ 种蔬菜，小 N 需要根据不同蔬菜的特性，综合考虑各方面因素，设计合理的销售方案，以获得最多的收益。

在计算销售蔬菜的收益时，每销售一个单位第 $i$ 种蔬菜，就可以获得 $a_i$ 的收益。特别地，由于政策鼓励商家进行多样化销售，第一次销售第 $i$ 种蔬菜时，还会额外得到 $s_i$ 的额外收益。

在经营开始时，第 $i$ 种蔬菜的库存为 $c_i$ 个单位。然而，蔬菜的保鲜时间非常有限，一旦变质就不能进行销售，不过聪明的小 N 已 经计算出了每个单位蔬菜变质的时间：对于第 $i$ 种蔬菜，存在保鲜值 $x_i$，每天结束时会有 $x_i$ 个单位的蔬菜变质，直到所有蔬菜都变质。（注意：每一单位蔬菜的变质时间是固定的，不随销售发生变化）

形式化地：对于所有的满足条件 $d\times x_i \leq c_i$ 的正整数 $d$ ，有 $x_i$ 个单位的蔬菜将在 第 $d$ 天结束时变质。 特别地，若 $(d-1)\times x_i \le c_i < d\times x_i$ ，则有 $c_i-(d-1)\times x_i$ 单位的蔬菜将在第 $d$ 天结束时变质。

注意，当 $x_i = 0$ 时，意味着这种蔬菜不会变质。 同时，每天销售的蔬菜，总量也是有限的，最多不能超过 $m$ 个单位。

现在，小 N 有 $k$ 个问题，想请你帮忙算一算。每个问题的形式都是：对于已知的 $p_j$ ，如果需要销售 $p_j$ 天，最多能获得多少收益？

小 L 计划进行 $n$ 场游戏，每场游戏使用一张地图，小 L 会选择一辆车在该地图上完成游戏。

小 L 的赛车有三辆，分别用大写字母 $A$、$B$、$C$ 表示。地图一共有四种，分别用小写字母 $x$、$a$、$b$、$c$ 表示。

其中，赛车 $A$ 不适合在地图 $a$ 上使用，赛车 $B$ 不适合在地图 $b$ 上使用，赛车 $C$ 不适合在地图 $c$ 上使用，而地图 $x$ 则适合所有赛车参加。适合所有赛车参加的地图并不多见，最多只会有 $d$ 张。

$n$ 场游戏的地图可以用一个小写字母组成的字符串描述。

小 L 对游戏有一些特殊的要求，这些要求可以用四元组 $(i, h_i, j, h_j)$ 来描述，表示若在第 $i$ 场使用型号为 $h_i$ 的车子，则第 $j$ 场游戏要使用型号为 $h_j$ 的车子。

你能帮小 L 选择每场游戏使用的赛车吗？如果有多种方案，输出任意一种方案。如果无解，输出 $-1$ 。

久莲是个爱玩的女孩子。

暑假终于到了，久莲决定请她的朋友们来游泳，她打算先在她家的私人海滩外圈一块长方形的海域作为游泳场。然而大海里有着各种各样的危险，有些地方水太深，有些地方有带毒的水母出没。她想让圈出来的这一块海域都是安全的。

经过初步分析，这块海域可视为一个底边长为 $N$ 米，高为 $1001$ 米的长方形网格。其中网格的底边对应着她家的私人海滩，每一个 $1m\times 1m$ 的小正方形都代表着一个单位海域。她拜托了她爸爸明天去测量每一个小正方形是否安全。在得知了信息之后，她要做的就是圈出她想要的游泳场啦。

她心目中理想的游泳场满足如下三个条件：

• 必须保证安全性。即游泳场中的每一个单位海域都是安全的。
• 必须是矩形。即游泳场必须是整个网格中的一个 $a\times b$ 的子网格。
• 必须和海滩相邻。即游泳场的下边界必须紧贴网格的下边界。

为了让朋友们玩的开心，她想让游泳场的面积尽可能的大。

虽然她要明天才能知道每一个单位海域是否安全，但是她现在就想行动起来估计一下她的游泳场面积有多大。经过简单的估计，她假设每一个单位海域都有独立的 $q$ 的概率是安全的， 1−q 的概率是不安全的。她想要知道她能选择的最大的游泳场的面积恰好为 $K$ 的概率是多少。

然而久莲对数学并不感兴趣，因此她想让你来帮她计算一下这个数值。

蚯蚓幼儿园有 $n$ 只蚯蚓。幼儿园园长神刀手为了管理方便，时常让这些蚯蚓们列队表演。

所有蚯蚓用从 $1$ 到 $n$ 的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示，根据入园要求，所有蚯蚓的长度都不超过 $6$ 。神刀手希望这些蚯蚓排成若干个队伍，初始时，每只蚯蚓各自排成一个仅有一只蚯蚓的队伍，该蚯蚓既在队首，也在队尾。

神刀手将会依次进行 $m$ 次操作，每个操作都是以下三种操作中的一种：

• 给出 $i$ 和 $j$ ，令 $i$ 号蚯蚓与 $j$ 号蚯蚓所在的两个队伍合并为一个队伍，具体来说，令 $j$ 号蚯蚓紧挨在 $i$ 号蚯蚓之后，其余蚯蚓保持队伍的前后关系不变。
• 给出 $i$ ，令 $i$ 号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍，具体来说，在分离之后， $i$ 号蚯蚓在其中一个队伍的队尾，原本紧挨其后的那一只蚯蚓在另一个队伍的队首，其余蚯蚓保持队伍的前后关系不变。
• 给出一个正整数 $k$ 和一个长度至少为 $k$ 的数字串 $s$ ，对于 $s$ 的每个长度为 $k$ 的连续子串 $t$ （这样的子串共有 $|s|-k+1$ 个，其中 $|s|$ 为 $s$ 的长度），定义函数 $f(t)$ ，询问所有这些 $f(t)$ 的乘积对 $998244353$ 取模后的结果。其中 $f(t)$ 的定义如下：

对于当前的蚯蚓队伍，定义某个蚯蚓的向后 $k$ 数字串为：从该蚯蚓出发，沿队伍的向后方向，寻找最近的 $k$ 只蚯蚓（包括其自身），将这些蚯蚓的长度视作字符连接而成的数字串；如果这样找到的蚯蚓不足 $k$ 只，则其没有向后 $k$ 数字串。

而 $f(t)$ 表示所有蚯蚓中，向后 $k$ 数字串恰好为 $t$ 的蚯蚓只数。

在人类智慧的山巅，有着一台字长为 $1048576$ 位的超级计算机，著名理论计算机科学家 P 博士正用它进行各种研究。 不幸的是，这天台风切断了电力系统，超级计算机无法工作，而 P 博士明天就要交实验结果了，只好求助于学过 OI 的你……

P 博士将他的计算任务抽象为对一个整数的操作。

具体来说，有一个整数 $x$ ，一开始为 $0$。

接下来有 $n$ 个操作，每个操作都是以下两种类型中的一种：

• $1$ $a$ $b$ ：将 $x$ 加上整数 $a \cdot 2 ^ b$ ，其中 $a$ 为一个整数，$b$ 为一个非负整数
• $2$ $k$ ：询问 $x$ 在用二进制表示时，位权为 $2 ^ k$​​ 的位的值（即这一位上的 $1$ 代表 $2 ^ k$ ）

保证在任何时候，$x \ge 0$ 。

$G$ 是一张由 $n$ 个点和 $n$ 条边组成的无向图。 $G$ 中没有自环和重边。每条边有两种状态“开”和“关”。一开始，所有的边都是“关”着的。

现在有 $m$ 个操作 $(v,u)$ ，表示将从 $v$ 到 $u$ 的最短路上的边改变状态（如果状态为“开”则变成“关”，反之，变成“开”）。如果 $v$ 到 $u$ 存在多条最短路，则我们选取点序列字典序最小的那一条。

比如，将所有从 $v$ 到 $u$ 的路径上的点表示成序列为 $v,v_1,v_2,\cdots ,u$ 。那么我们从中取字典序最小的那一条。

在每一次操作后，你需要计算在图中由所有点和状态为“开”的边所组成图的连通块的数目。

华沙收集车票已经有一段时间了。他收集了上千张的车票。华沙已经厌倦了传统幸运车票的定义。所以他想寻找一个不一样的定义。华沙不理解为什么所有的车票要分为幸运的和不幸运的。他认为所有的车票都是幸运的，只是幸运的程度不一样。有了这个想法，他重新定义了车票的幸运程度。一张车票有 $2n$ 位数字。数字 $0-9$ 的书写如图。

就像在电子时钟里看到的数字一样，用 $7$ 根线条表示数字。每根线条有两种状态，着色或不着色。着色的线条组成一个数字。华沙认为所有的数字都是这么书写的。把车票号码的右半部分放在左半部分上面，那么第 $1$ 位数字就会和第 $n+1$ 位重合，第 $2$ 位就会和第 $n+2$ 重合…，第 $n$ 位数字和第 $2n$ 位数字重合。对于每对重合的数字，统计这两个数字重合后都着色的线条数量。然后把每对统计的结果加起来，就是车票的幸运程度了。

现在，给定一个 $2n$ 位数字的车票号码。找出一个 $2n$ 位数字的车票号码，使得这个号码在数值上大于给定的号码，在幸运程度上也大于给定的号码。如果存在多个这样的号码，我们选择数值最小的那个号码。