title: [GESP202312 六级] 工作沟通

description:
某公司有 $N$ 名员工，编号从 $0$ 至 $N-1$。其中，除了 $0$ 号员工是老板，其余每名员工都有一个直接领导。我们假设编号为 $i$ 的员工的直接领导是 $f_i$。

该公司有严格的管理制度，每位员工只能受到本人或直接领导或间接领导的管理。具体来说，规定员工 $x$ 可以管理员工 $y$，当且仅当 $x=y$，或 $x=f_y$，或 $x$ 可以管理 $f_y$。特别地，$0$ 号员工老板只能自我管理，无法由其他任何员工管理。

现在，有一些同事要开展合作，他们希望找到一位同事来主持这场合作，这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工，他们希望找到编号最大的员工。你能帮帮他们吗？

inputFormat:
第一行一个整数 $N$，表示员工的数量。

第二行 $N - 1$ 个用空格隔开的正整数，依次为 $f_1,f_2,\dots f_{N−1}$。

第三行一个整数 $Q$，表示共有 $Q$ 场合作需要安排。

接下来 $Q$ 行，每行描述一场合作：开头是一个整数 $m$（$2 \le m \le N$），表示参与本次合作的员工数量；接着是 $m$ 个整数，依次表示参与本次合作的员工编号（保证编号合法且不重复）。

保证公司结构合法，即不存在任意一名员工，其本人是自己的直接或间接领导。

outputFormat: 输出 $Q$ 行，每行一个整数，依次为每场合作的主持人选。

hint:
**样例解释 1**

对于第一场合作，员工$3,4$ 有共同领导 $2$ ，可以主持合作。

对于第二场合作，员工 $2$ 本人即可以管理所有参与者。

对于第三场合作，只有 $0$ 号老板才能管理所有员工。

**数据范围**

对于 $50\%$ 的测试点，保证 $N \leq 50$。

对于所有测试点，保证 $3 \leq N \leq 300$，$Q \leq 100$。

------------
2024/1/28 添加一组 hack 数据。


title: [GESP202312 七级] 商品交易

type: P

description:
市场上共有 $N$ 种商品，编号从 $0$ 至 $N-1$ ，其中，第 $i$ 种商品价值 $v_i$ 元。

现在共有 $M$ 个商人，编号从 $0$ 至 $M-1$ 。在第 $j$ 个商人这，你可以使用你手上的第 $x_j$ 种商品交换商人手上的第 $y_j$ 种商品。每个商人都会按照商品价值进行交易，具体来说，如果 $v_{x_j}>v_{y_j}$，他将会付给你 $v_{x_j}-v_{y_j}$元钱；否则，那么你需要付给商人 $v_{x_j}-v_{y_j}$ 元钱。除此之外，每次交易商人还会收取 $1$ 元作为手续费，不论交易商品的价值孰高孰低。

你现在拥有商品 $a$ ，并希望通过一些交换来获得商品 $b$ 。请问你至少要花费多少钱？（当然，这个最小花费也可能是负数，这表示你可以在完成目标的同时赚取一些钱。）

inputFormat:
第一行四个整数 $N , M , a , b$，分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证 $0 \le a,b < N$ ，保证 $a \ne b$。

第二行 $N$ 个用单个空格隔开的正整数 $v_0,v_1,…,v_{N-1}$ ，依次表示每种商品的价值。保证 $1≤v_i≤10^9$。

接下来 $M$ 行，每行两个整数 $x_j,y_j$ ，表示在第 $j$ 个商人这，你可以使用第 $x_j$ 种商品交换第 $y_j$ 种商品。保证 $0≤x_j,y_j<N$，保证 $x_j≠y_j$ 。

outputFormat: 输出一行一个整数，表示最少的花费。特别地，如果无法通过交换换取商品 $b$ ，请输出 `No solution`。

hint:
**数据范围**

对于30%的测试点，保证 $N ≤ 10$ ，$M ≤ 20$。

对于70%的测试点，保证 $N ≤10^3$ ，$M≤10^4$。

对于100%的测试点，保证 $N≤10^5$，$M≤2×10^5$。


title: [GESP202312 七级] 纸牌游戏

description:
你和小杨在玩一个纸牌游戏。

你和小杨各有 $3$ 张牌，分别是 $0、1、2$ 。你们要进行 $N$ 轮游戏，每轮游戏双方都要出一张牌，并按 $1$ 战胜 $0$，$2$ 战胜 $1$，$0$ 战胜 $2$ 的规则决出胜负。第 $i$ 轮的胜者可以获得 $2×a_i$ 分，败者不得分，如果双方出牌相同，则算平局，二人都可获得 $a_i$ 分$（i=1,2,…,N）$ 。

玩了一会后，你们觉得这样太过于单调，于是双方给自己制定了不同的新规则。小杨会在整局游戏开始前确定自己全部 $n$ 轮的出牌，并将他的全部计划告诉你；而你从第 $2$ 轮开始，要么继续出上一轮出的牌，要么记一次“换牌”。游戏结束时，你换了 $t$ 次牌，就要额外扣 $b_1+…+b_t$ 分。

请计算出你最多能获得多少分。

inputFormat:
第一行一个整数 $N$，表示游戏轮数。

第二行 $ N$ 个用单个空格隔开的非负整数 $a_1,…,a_N$ ，意义见题目描述。

第三行 $N-1$ 个用单个空格隔开的非负整数 $b_1,\cdots,b_{N-1}$ ，表示换牌的罚分，具体含义见题目描述。由于游戏进行 N 轮，所以你至多可以换 $N-1$ 次牌。

第四行 $N$ 个用单个空格隔开的整数 $c_1,,\cdots,c_N$ ，依次表示小杨从第 $1$ 轮至第 $N$ 轮出的牌。保证 $c
_i\in{0,1,2}$ 。

outputFormat: 一行一个整数，表示你最多获得的分数。

hint:
**样例解释 1**

你可以第 $1$ 轮出 $0$，并在第 $2,3$ 轮保持不变，如此输掉第 $1,2$ 轮，但在第 $3$ 轮中取胜，获得 $2×10=20$ 分；

随后，你可以在第 $4$ 轮中以扣 $1$ 分为代价改出 $1$ ，并在第 $4$ 轮中取得胜利，获得 $2×100=200$ 分。

如此，你可以获得最高的总分 $20+200-1=219$。

**数据范围**

对于 $30\%$ 的测试点，保证 $N<=15$。

对于 $60\%$ 的测试点，保证 $N<=100$。

对于所有测试点，保证 $N \le 1,000$；保证 $0 \le a_i,b_i \le 10^6$。


title: [GESP202312 八级] 奖品分配

description:
班上有 $N$ 名同学，学号从 $0$ 到 $N-1$。有 $M$ 种奖品要分给这些同学，其中，第 $i$ 种奖品总共有 $a_i$ 个 （$i=0,1, \cdots ,M-1$）。

巧合的是，奖品的数量不多不少，每位同学都可以恰好分到一个奖品，且最后剩余的奖品不超过 $1$ 个（即：$N\le a_0+a_1+ \cdots +a_{M-1}\le N+1$）。

现在，请你求出每个班级礼物分配的方案数，所谓方案，指的是为每位同学都分配一个种类的奖品。

只要有一位同学获得了不同种类的奖品，即视为不同的方案。方便起见，你只需要输出方案数对 $10^{9}+7$ 取模后的结果即可。

共有 $T$ 个班级都面临着奖品分配的问题，你需要依次为他们解答。

inputFormat:
第一行一个整数 $T$，表示班级数量。

接下来 $T$ 行，每行若干用单个空格隔开的正整数。首先是两个正整数$N,M$，接着是 $M$ 个正整数 $a_0,a_1...a_{M-1}$。保证 $N \le a_0+a_1+\cdots+a_{M-1} \le N+1 $。

outputFormat: 输出 $T$ 行，每行一个整数，表示该班级分配奖品的方案数对 $10^{9}+7$ 取模的结果。

hint:
**样例解释 1**

对于第 $1$ 个班级，学号为 $0,1,2$ 的同学可以依次分别获得奖品 $0,1,1$，也可以依次分别获得奖品 $1,0,1$，也可以依次分别获得奖品 $1,1,0$ ，因此共有 $3$ 种方案。

对于第 $2$ 个班级，学号为 $0,1,2$ 的同学可以依次分别获得奖品 $0,1,1$ ，也可以依次分别获得奖品 $1,0,1$，也可以依次分别获得奖品 $1,1,0$，也可以依次分别获得奖品 $1,1,1$，因此共有 $4$ 种方案。

对于第 $3$ 个班级，可以把编号为 $0$ 的奖品分配给 $5$ 名同学中的任意一名，共有 $5$ 种方案；再把编号为 $2$ 的奖品分配给剩余 $4$ 名同学中的任意一名，共有$4$ 种方案；最后给剩余 $3$ 名同学自然获得 $1$ 号奖品。因此，方案数为 $5 \times 4 = 20$。

**数据范围**

对于 $30\%$ 的测试点，保证 $N \le 10$。

对于另外 $30\%$ 的测试点，保证 $M=2$。

对于所有测试点，保证 $N \le 1000$；保证 $T \le 1000$ ；保证 $M \le 1001$。


title: [GESP202312 八级] 大量的工作沟通

inputFormat:
第一行一个整数 $N$ ，表示员工的数量。

第二行 $N-1$ 个用空格隔开的正整数，依次为 $f_1, f_2, \dots f_{N-1}$。

第三行一个整数 $Q$ ，表示共有 $Q$ 场合作需要安排。

接下来 $Q$ 行，每行描述一场合作：开头是一个整数 $m$（$2 \leq m \leq N$），表示参与本次合作的员工数量；接着是 $m$ 个整数，依次表示参与本次合作的员工编号（保证编号合法且不重复）。

保证公司结构合法，即不存在任意一名员工，其本人是自己的直接或间接领导。

outputFormat: 输出 $Q$ 行，每行一个整数，依次为每场合作的主持人选。

hint:
**样例解释 1**

对于第一场合作，员工 $3,4$ 有共同领导 $2$ ，可以主持合作。

对于第二场合作，员工 $2$ 本人即可以管理所有参与者。

对于第三场合作，只有 $0$ 号老板才能管理所有员工。

**数据范围**

对于 $25\%$ 的测试点，保证 $N \leq 50$。

对于 $50\%$ 的测试点，保证 $N \leq 300$。

对于所有测试点，保证 $3 \leq N \leq 10^5$，$Q \leq 100$，$m \leq 10^4$。

------------
2024/2/8 添加一组 hack 数据。


title: 『STA - R4』And

description:
给定非负整数 $A, B$，定义有序非负整数对 $(x, y)$ 为好的当且仅当：

- $0 \le x \le y$；
- $x + y = A$；
- $x \operatorname{AND} y = B$。

其中 $\operatorname{AND}$ 代表按位与运算。在 C++ 语言中由 `&` 运算符表示。

你需要求出所有好的有序非负整数对 $(x, y)$ 的 $y - x$ 的和。

由于该值可能很大，你只需要输出其对 $M$ 取模后的结果。

形式化的，你需要求出

$$\left(\sum\limits_{x \ge 0}\sum\limits_{y \ge 0}\left(y - x\right)\left[\operatorname{good}(x, y)\right]\right)\bmod M$$

其中 $\operatorname{good}(x, y)$ 为真与有序非负整数对 $(x, y)$ 为好的等价。

inputFormat:
**本题单个测试点内含有多组询问。**

第一行两个整数 $T, M$，分别代表询问组数和模数。

接下来 $T$ 行，每行两个非负整数 $A, B$，代表一组询问。

outputFormat: 对于每组测试数据，输出一行一个整数，代表答案。

hint:
**【样例 #1 解释】**

对于第一组询问，好的数对有 $\left(1, 7\right)$ 和 $\left(3, 5\right)$，因此答案为 $\left(7 - 1\right) + \left(5 - 3\right) = 8$。

对于第二组询问，好的数对只有 $\left(4, 6\right)$，因此答案为 $6 - 4 = 2$。

对于第三组询问，好的数对有 $\left(0, 6\right)$ 和 $\left(2, 4\right)$，因此答案为 $\left(6 - 0\right) + \left(4 - 2\right) = 8$。

**【样例 #2 解释】**

其所有询问均满足子任务 1 的限制，且后两组询问同时满足子任务 3 的限制。

特别的，在第三组询问的限制下，不存在好的有序非负整数对，因此答案为 $0$。

**【样例 #3 解释】**

其所有询问均满足子任务 2 的限制。

**【样例 #4 解释】**

其所有询问均满足子任务 4 的限制。

特别的，在第四、五组询问的限制下，不存在好的有序非负整数对，因此答案为 $0$。

**【数据范围】**

**本题采用捆绑测试。**

对于 $100\%$ 的数据：

- $1 \le T \le 3 \times 10^5$；
- $0 \le A, B < 2^{60}$；
- $5 \le M \le 1.1 \times 10^9$；
- $M$ 为质数。

具体部分分分配如下：

|Subtask 编号|数据范围|分值|
|:--------:|:--------:|:--------:|
|1|$T \le 200, 0 \le A, B \le 8 \times 10^5$|$15$|
|2|对于每组询问，好的数对个数不超过 $1000$ 个|$25$|
|3|$B = 0$|$25$|
|4|无特殊限制|$35$|


title: [集训队互测 2023] Grievous Lady

background:
对立从那灰暗的塔楼进入，逐步踏入这个扭曲的迷宫深处。

对立的心突然绞痛起来。

对立后退了一步，扑腾了一下便跪倒下来。

未及碰到，灰黑的地板就突然崩裂瓦解，先一步向下坠落。

先前收集的纷争碎片，连同塔楼本身，一同化作了一场倾盆大雨，包围在对立四周。

异象骤起，对立的思维也陷入一片混乱。

塔楼落入了先前的由光芒碎片组成的欢乐海洋，但对立却被纷争碎片紧紧地包裹着。

在那由光芒和纷争碎片交错的风暴之中，对立所见的只有那些令人厌恶的纷争碎片。

那枚世界尽头的记忆映入了对立的视野。

面对着世界一点点地走向终结的景象，对立的理性在碎裂。

对立意识到，一切美好的记忆不过是须臾，最终都会走向破灭。

四周的碎片依旧在飞旋，对立试图看清那些玻璃碎片的变换。

对立意识到，现在围绕着的那些碎片，正以最恐怖的方式运转。

这个碎片风暴所带来的「忧郁度」，可以被简单地描述为外侧碎片的旋转速度之和乘上内侧碎片的旋转速度之和。

一片玻璃碎片在外侧总是以一种速度正旋，而在内侧总是以另一种速度逆旋。

每片碎片都是是来自不同世界的刹那记忆，故而其转速总可以认为是独立随机指定的。

在残存无几的希望将尽未尽之时，对立只想知道，现在的碎片风暴的忧郁度，也就是最大可能的忧郁度，究竟是多少。

description:
共有 $n$ 个元素，标号 $1\sim n$，每个元素 $j$ 有两个正整数权值 $a_j,b_j$。

你要确定一个 $[1,n]\cap\mathbb N$ 的子集 $S$，从而最大化

$$
(\sum_{k=1}^na_k[k\in S])(\sum_{k=1}^nb_k[k\notin S])
$$

这个问题显然不可做，因此**保证每个 $a_j,b_j$ 分别在 $[1,A]\cap\mathbb N,[1,B]\cap\mathbb N$ 内独立均匀随机生成**。

现在给定 $n,A,B$ 和每个元素的两个权值 $(a_j,b_j)$，请求出这个最大的答案。

inputFormat:
本题每个测试点中有多组测试数据。

第一行四个整数，$T,n,A,B$，$T$ 表示该组数据内的数据组数，$n,A,B$ 表示该测试点内的所有数据均对应此 $n,A,B$。

接下来每组数据占 $n$ 行，其中第 $j$ 行两个整数 $a_j,b_j$。

保证 $a_j,b_j$ 在对应范围内独立均匀随机生成。

outputFormat:
对于每组数据输出一行一个整数，表示其答案。

注意这个答案可能很大，你可能需要使用 `__int128` 类型来进行中间存储与运算，并最后输出。注意你可能需要使用一些正确的输出方式。


title: 大娱乐至上

background:
> 闪光，黑洞，万众瞩目之星。
>
> 美丽的国度之中最美丽的梦。
>
> 她的发丝比金箔更贵，她的唇印可抵成捆钞票。
>
> 而她的心呀，心呀，心呀，
>
> 不值一枚金币，不值一枚金币，不值一瞧。

description:
给出一个由小写字母组成、长度为 $n$ 的字符串 $S$ 和一个长度为 $n$ 的 $01$ 串 $b$，$b_i=1$ 表示 $S_i$ 是可修改的。

给出 $m$ 个子串 $S_{[l,r]}$，定义一个子串 $str$ 是**非偏序**的，当且仅当可以通过修改 $S$ 的至多一个位置，使得 $m$ 个子串中原先 $<str$ 的子串都 $\ge str$。

形式化地说，一个二元组 $(l_i,r_i)$ 是**非偏序**的，当且仅当存在一个字符串 $T$（由 $S$ 修改至多一个字符得到），使得 $\forall\,1 \le j \le m,[S_{[l_j,r_j]}<S_{[l_i,r_i]}]+[T_{[l_j,r_j]}<T_{[l_i,r_i]}]\not=2$。

询问哪些子串是**非偏序**的。

注意，修改后出现比 `a` 小或比 `z` 大的字符是**允许的**。

inputFormat:
第一行两个数 $n,m$。

第二行一个字符串 $S$。

第三行一个 $01$ 串 $b$。

接下来 $m$ 行，每行一个二元组 $(l_i,r_i)$。

outputFormat: 输出为一个长度为 $m$ 的 $01$ 串 $ans$。$ans_i=1$ 表示 $(l_i,r_i)$ 是 `非偏序` 的，$ans_i=0$ 表示不是。

hint:
### 样例一解释

为了方便表述，钦定比 `a` 小的字符为 `#`，比 `z` 大的字符为 `*`。

- $(1,5):$ 无论如何修改，恒有 $S_{[1,3]}<S_{[1,5]},T_{[1,3]}<T_{[1,5]}$。

- $(7,10):$ $T$ 可以为 `abbcababaa`。

- $(1,3):$ $T$ 可以为 `a#baababaa`。

- $(3,7):$ $T$ 可以为 `ab#aababaa`。

- $(4,8):$ $T$ 可以为 `abbaababaa`。

### 数据范围与约定

**本题采用捆绑测试**。

$\text{subtask1(10pt):}$ $1 \le n,m \le 100$。

$\text{subtask2(30pt):}$ $1 \le n,m \le 1000$。

$\text{subtask3(10pt):}$ $b_i=1$。

$\text{subtask4(50pt):}$ 无特殊限制。

对于所有数据，$1\le n,m \le 2\times 10^5,1 \le l_i \le r_i \le n$，输入均为整数和小写字母。


title: [YDOI R1] Running

background:
**建议使用较快速的输入方式。**

小 Z 要去跑步，他想开学后拉爆他的同学。

description:
小 Z 在一条公路上跑步，公路上有 $n$ 个超市，第 $i$ 个超市的位置为 $a_i$。当小 Z 经过一个超市的时间为奇数时，他就会去逛超市，从而被同学拉爆。

小 Z 最开始位于位置为 $0$ 的点。他会在每个单位时间向右跑 $v$ 个单位长度。

请求出：能够使小 Z 经过 $n$ 个超市中每一个超市时，都不去逛超市的 $v$ 的最大值。

规定 $v$ 必须是正整数，且小 Z 到达任意一个超市时，花费的时间必须为整数，换言之，你需要保证小 Z 到达任意一个超市的时间都是偶数。注意时间初始为 $0$。

inputFormat:
输入共 $n+1$ 行。

第 $1$ 行，$1$ 个正整数 $n$。

第 $2\sim n+1$ 行，每行 $1$ 个正整数，第 $i+1$ 行输入的正整数是 $a_i$。

outputFormat:
输出共 $1$ 行。

输出符合条件的 $v$ 的最大值。如果无解则输出 $-1$。


title: [LMXOI Round 1] Random

background: LMX 给 HQZ 一个有趣的序列，HQZ 为了了解 LMX 的爱好，想要解决下面的问题。

description:
给出一个初始全为 $0$ 长为 $n$ 的序列，我们会进行如下操作 $q$ 次。

+ 任意选择一个位置 $t$ 并把上面的数字修改成任意一个 $1$ 到 $k$ 之间的数。

也就是说我们一共会有 $(nk)^q$ 种不同的询问序列，而对于每一种不同的询问序列，对应的也就拥有了 $(nk)^q$ 个结果序列。

接着，给出一个长度为 $m$ 匹配序列 $B$，需要求出这个匹配序列在每一个结果序列中出现的次数和。注意，一个结果序列中若出现多个匹配序列应当重复计算。

由于答案太大，你只需要输出答案对 $998244353$ 取模后的结果。

**本题使用特定方式生成输入数据。**

生成格式如下： $x_i=(a \times i+b)\bmod k +1$ ，其中 $x_i$ 表示序列 $B$ 第 $i$ 位所需求的数字。

inputFormat:
第一行四个整数 $n,m,q,k$ 其中 $m$ 为 $B$ 序列的长度。

第二行二个整数 $a,b$。

outputFormat: 一行一个整数表示答案。


title: [LMXOI Round 1] Dreamer

background:
[加强版链接](https://www.luogu.com.cn/problem/U402756)。

这是一道数学题，可是 LMX 给 HQZ 出的。

description:
定义积性函数 $f(n)=(\mu \ast\operatorname{Id_2})(n)$。

给定 $n,k$，你需要求出

$$\sum_{i_1\mid n}\sum_{i_2\mid i_1}\cdots\sum_{i_k\mid i_{k-1}}f(i_k)i_1i_k\mu^2\left(\dfrac{i_1}{i_k}\right)$$

#### Tips：

$\mu$ 表示莫比乌斯函数。

关于 $f$，$f(n)=\displaystyle \sum_{d\mid n}\mu(d)\left(\dfrac{n}{d}\right)^2$。

inputFormat:
本题有多组数据，第一行输入一个正整数 $T$，表示数据组数。

考虑到 $n$ 很大，所以我们会给出 $n$ 的标准质因子分解 $n=\displaystyle \prod_{i=1}^t p_i^{\alpha_i}$。

对于每一组询问，我们首先给出两个整数 $k,m$。

第二行给出 $t$，下面 $t$ 行每行两个整数表示 $p_i,\alpha_i$。

（保证 $p_i\ge p_{i-1},i\ge 2$，$\alpha_i\ge 1$）。

outputFormat: 对于每个询问，输出一行表示答案 $\mod m$ 的值。


title: 「OICon-02」maxiMINImax

description: 给出一个长度为 $n$ 的排列 $a$。定义一个子区间 $[l,r]$ 中 $a_i$ 的最小值为 $\min_{[l,r]}$，$a_i$ 的最大值为 $\max_{[l,r]}$。对于所有子区间三元组 $([l_1,r_1],[l_2,r_2],[l_3,r_3])$ 使得 $1\leq l_1\leq r_1<l_2\leq r_2<l_3\leq r_3\leq n$，求 $\max(0,\min_{[l_2,r_2]}-\max_{[l_1,r_1]})\times\max(0,\min_{[l_2,r_2]}-\max_{[l_3,r_3]})$ 之和，对 $9712176$ 取模。

inputFormat:
第一行，一个正整数 $n$，表示排列的长度。

第二行，$n$ 个正整数 $a$，表示给出的排列 $a$。


title: [语言月赛 202401] 分饼干 I

type: B

description:
洛谷网校举行了期末考试，同学们经过课程的学习，考出了优异的成绩。

Z 在考试中获得了第一名，yz 在考试中获得了第二名，老师决定买一些饼干奖励两名小朋友。

老师买了三盒饼干，第一盒有 $a$ 块饼干，第二盒有 $b$ 块饼干，第三盒有 $c$ 块饼干。老师决定将这三盒饼干奖励给 Z 和 yz，三盒饼干不可以被拆开奖励。

老师希望 Z 拿到的饼干块数不少于 yz，但又希望两人拿到的饼干数量差距尽可能小，请问 Z 和 yz 各拿到几块饼干？

inputFormat: 输入一行三个整数，分别为 $a,b,c$。

outputFormat: 输出一行两个整数，由空格分隔。第一个整数代表 Z 拿到的饼干数量，第二个整数代表 yz 拿到的饼干数量。

hint:
### 样例解释 1

Z 拿走 $5$ 块饼干，yz 拿走 $3+1=4$ 块饼干。

### 样例解释 2

Z 拿走 $3+3=6$ 块饼干，yz 拿走 $5$ 块饼干。

### 数据范围与约定

- 对于 $30\%$ 的测试数据，$a=b=c$；
- 对于 $100\%$ 的测试数据，$1 \le a,b,c \le 1000$。


title: 城市化发展委员会

background:
MLE 大帝曾说过：

![](https://cdn.luogu.com.cn/upload/image_hosting/kce8kpx3.png)

所以为了应对这种情况我们设立了**城市化发展委员会**。

description:
在高中的校园里我们常常能看到随机刷新的小情侣，对于他们之间的情感，对于 OIer 来说还是太过于高深了，即使是退役的 AzureHair 也无法理解这一行为，但是作为自命的城市化发展委员会的常委，他有自己的一套理解方法。

他认为，女生往往对男生十分的严格。一天开始时男生在女生的心里的积分会加 $1$，而如果当天惹女生生气了 $x$ 次，积分就会在此基础上减 $x$。积分会不断累计，一旦小于等于 $0$ 就可能导致去城市化的严重后果。

现在 **威廉** 在和 **珂朵莉** 进行一种城市化行为，**威廉** 在~~纳西妲~~的帮助之下获得了超能力：一是他可以预知到接下来一个周期的积分变化情况，初始的周期长度为 $n$；二是他可以选择从任意一天开始，开始前的日子将会被拼接到最后一天之后。

他从每一天开始都尝试过一次后，发现了 $a$ 个能使得他不被去城市化的起始日期。随后他会将这若干种情况下的序列按照起始日期的先后拼在一起，变成一个长度为原先 $a$ 倍的周期。他如此重复操作 $k$ 次，由于一天天地试太累了，**威廉** 只想知道最后一次操作后有多少个起始日期能让自己不被去城市化，对 $998244353$ 取模。

---

形式化地说，我们称满足前缀和始终大于 $0$ 的数列为 “安全的”。

对于一个长为 $n$ 的数列 $A_i$，根据以下算法构造出数列 $A_{i+1}$，初始时 $A_{i+1}$ 为空。

- 重复执行 $n$ 次：

1. 若 $A_i$ 是安全的，将其整个接到 $A_{i+1}$ 末尾。

2. 将 $A_i$ 循环左移一位，即令 $A_{i_j} ← A_{i_{j+1 \bmod n}}$。

现在给定 $A_0$，**满足其各项均不大于 1**。

从 $A_0$ 开始按上述规则生成数列 $A_1$ 到 $A_{k+1}$，请求出 $A_{k+1}$ 与 $A_k$ 的长度比，这个值只要存在就一定是整数，请输出它对 $998244353$ 取模的值。特别地，如果 $A_k$ 为空，请输出 ```0```。

inputFormat:
普通题意：

共两行，第一行两个整数 $n$ 和 $k$，表示初始的周期长度和操作次数。

第二行 $n$ 个小于等于 1 的整数，表示每天的积分变化。

形式化题意：

共两行，第一行两个整数为 $A_0$ 的长度 $n$ 以及 $k$。

第二行是 $A_0$。

outputFormat: 一行一个整数，表示答案对 $998244353$ 取模的结果。


title: 「LAOI-4」Colors

background:
做这个题：

![](https://cdn.luogu.com.cn/upload/image_hosting/6053fe2y.png)

description:
给定长度为 $n$ 的字符串 $A$。
- 若 $A_{i-1}=A_{i+1}$，则称 $A_i$ 为 「可消除的」。

定义一次操作为：消除 $A$ 中所有「可消除的」字符。

请你输出操作 $k$ 次后的 $A$。

inputFormat:
第一行一个正整数 $T,id$，表示数据组数和子任务编号。

对于每组数据，第一行一个正整数 $n$ 和一个整数 $k$。

接下来一行是一个长为 $n$ 的字符串。

outputFormat: 对于每组数据，输出一行一个字符串表示答案。


title: 「OICon-02」Subtree Value

description: 给出一棵 $n$ 个节点的树，每个点有点权 $a_v$。定义一棵树的一个子连通块为一个树中点的**非空集合**，满足这些点在树上形成一个连通块。定义子连通块 $S$ 的权值为 $\prod_{v\in S}(a_v+|S|)$。求所有子连通块的权值之和对 $U^V$ 取模。

inputFormat:
第一行，三个正整数 $n,U,V$，分别表示节点个数，以及模数（$U^V$）。

第二行，$n-1$ 个正整数 $f_2,f_3,\dots,f_n$，分别表示以 $1$ 节点为根节点的情况下第 $i$ 个点的父亲节点。

第三行，$n$ 个非负整数 $a_i$，表示每个点的点权。

outputFormat: 一行，一个正整数，表示所有子联通块的权值之和，对 $U^V$ 取模。


title: 实力派

description:
来自全国各地的 $n$ 位 OIer 组成了一个名为“实力派”的团队，每个人有一个实力值 $a_i$。共有 $m$ 场比赛向他们发送了参赛邀请，其中第 $i$ 场比赛要求 $k_i$ 个人组成一个队伍参加。为了决定他们是否应该参加某场比赛，他们想出了如下两个衡量实力的数据：

- 定义 $x$ 阶最低实力表示从这 $n$ 个人中选出 $x$ 个人，使得这 $x$ 个人实力值的 $\gcd=1$ 的方案数；

- 定义 $x$ 阶最高实力表示从这 $n$ 个人中选出 $x$ 个人，所有方案的 $x$ 个人的 $\gcd$ 之和。

请你对于每场比赛，告诉他们他们在这场比赛中的 $k_i$ 阶最低实力和最高实力。对了，为了不让别人听懂，你需要将答案对一个秘密模数 $p$ 取模。

inputFormat:
第一行三个整数 $n,m,p$，分别表示团队人数，比赛场数及秘密模数；

第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个人的实力值 $a_i$。

接下来 $m$ 行，第 $i$ 行一个整数 $k_i$，表示第 $i$ 场比赛的要求参赛人数。

outputFormat: 输出共 $m$ 行，第 $i$ 行两个整数 $min_i,max_i$，分别表示他们在第 $i$ 场比赛中的最低实力和最高实力，答案对 $p$ 取模。


title: [湖北省选模拟 2024] 时与风 / wind

background: 风带来故事的种子，时间使之神话。

description:
你在 $N$ 个锚点间，沿着 $M$ 条有向航道，使用风之翼进行飞行。锚点依次编号为 $1,2,\cdots,N$，有向航道依次编号为 $1,2,\cdots,M$。第 $i$ 条航道的出发锚点为 $u_i$，到达锚点为 $v_i$。

由于巴巴斯托与时间存在神秘的联系，第 $i$ 条航道将在时刻 $O_i$ 开启，在时刻 $C_i$ **后**关闭。**也就是说，对于任意的 $O_i \le t \le C_i$，你可以在时刻 $t$ 由锚点 $u_i$ 进入航道 $i$。**进入航道后，空间上，你将直接到达锚点 $v_i$，时间上，时间将**等概率**的变化为 $[L_i,R_i]$ 中的一个实数对应的时刻。**注意到达一个锚点后，你必须在同一时刻立刻进入下一段航道，否则你必须在此结束飞行。**

你将从锚点 $S$ 出发，尝试访问锚点 $i(1\le i\le N)$，你需要对于锚点 $i$ 确定一条路径 $E_1,E_2,E_3,\cdots,E_k$，其中 $E_x(1\le x\le k)$ 表示一条航道。要求 $E_1$ 从锚点 $S$ 出发，$E_k$ 到达锚点 $i$，且对于 $1\le j<k$，满足 $E_j$ 的到达锚点与 $E_{j+1}$ 的出发锚点相同。一条路径是**稳定路径**，当且仅当无论每次通过航道后时间如何变化，都可以走完整条路径。一条**稳定路径的到达时间**是通过路径前往锚点 $i$ 时，**最晚的**可能到达锚点 $i$ 的时刻。访问**锚点 $i$ 的稳定到达时间 $T_i(i \neq S)$** 是所有到达 $i$ 的稳定路径中到达时间的**最小值**。你可以在任意非负时刻出发。**如果不存在访问锚点 $i$ 的稳定路径或 $i=S$，则 $T_i=0$。**

请你求出 $T_i(1\le i\le N)$ 的最大值。

inputFormat:
输入共 $M+1$ 行。

输入的第一行为三个整数 $N,M,S$，分别表示锚点数、航道数和起点锚点。

接下来 $M$ 行，每行包含六个整数 $u_i,v_i,O_i,C_i,L_i,R_i$，描述了第 $i$ 条航道的有关信息，变量具体含义见题目描述部分。

outputFormat: 输出一行一个整数，表示 $T_i$ 的最大值。


title: [湖北省选模拟 2024] 花神诞日 / sabzeruz

background:
传说，之所以这个日子会叫做「花神诞日」，其实最早是「花神祝诞」的意思。

在很久很久以前，有一次树王大人过生日，她的朋友们举办了宴席为她祝寿。

宴席上，几位神明大人都喝醉了，其中一位便乘兴弹奏起了乐器，于是树王大人唱歌，花神大人就跳起舞来。

在花神大人起舞时，她踏过的草地上，长出了无数美丽的帕蒂沙兰……

啊，若是时间能永驻此刻就好了。

description:
你正在为花神诞日准备宴席。你一共有 $N$ 种食材，依次编号为 $1,2,\cdots, N$，第 $i$ 种食材的味道为 $a_i$，任意两种食材的味道都不相同。你希望用这 $N$ 种食材做两道菜，每种食材必须被在**恰好**一道菜中使用。每道菜至少使用一种食材。

同一道菜中不同食材的味道会**两两发生反应**。食材 $i$ 与食材 $j$ 反应，将产生 $a_i \oplus a_j$ 的味道，其中 $\oplus$ 表示异或运算。一道菜最终的味道为**两两反应产生的味道的最小值**。例如，一道菜使用了味道分别为 $2,3,4$ 的三种食材，食材将会两两反应产生 $1(2 \oplus 3)$，$6(2\oplus 4)$，$7(3\oplus 4)$ 三种味道，这道菜的味道为 $\min(1,6,7)=1$。

本真的味道最为美味。**如果一道菜只使用了一种食材，这道菜的味道为 $+\infty$。**

你希望第一道菜的味道不低于 $k_1$，第二道菜的味道不低于 $k_2$。请问，你一共有多少种做菜的方案？

**请注意：相同集合的食材，分别作为第一道菜与第二道菜是两种不同的方案。** 例如，第一道菜使用食材 $1,2,3$，第二道菜使用食材 $4,5$，与第一道菜使用食材 $4,5$，第二道菜使用食材 $1,2,3$ 是两种不同的方案。

由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模的值。

inputFormat:
输入共两行。

输入的第一行为三个正整数 $N,k_1,k_2$，分别表示食材的种类数、第一道菜与第二道菜要求的味道。

输入的第二行包含 $N$ 个正整数 $a_1,a_2,\cdots,a_N$，$a_i$ 表示第 $i$ 种食材的味道。

outputFormat: 输出一行一个整数，表示做菜的方案数对 $10^9+7$ 取模的结果。

samples: 见选手目录下的 sabzeruz/sabzeruz3.in 与 sabzeruz/sabzeruz3.ans。

samples: 该样例符合测试点 9 ∼ 11 的限制。

samples: 见选手目录下的 sabzeruz/sabzeruz4.in 与 sabzeruz/sabzeruz4.ans。

samples: 该样例符合测试点 12 ∼ 15 的限制。

samples: 见选手目录下的 sabzeruz/sabzeruz5.in 与 sabzeruz/sabzeruz5.ans。

hint:
### 样例解释 2

做菜的五种方式列举如下：

- 第一道菜使用食材 $1,2,3$，第二道菜使用食材 $4$。
- 第一道菜使用食材 $1,2$，第二道菜使用食材 $3,4$。
- 第一道菜使用食材 $1,3$，第二道菜使用食材 $2,4$。
- 第一道菜使用食材 $2,3,4$，第二道菜使用食材 $1$。
- 第一道菜使用食材 $3,4$，第二道菜使用食材 $1,2$。

### 子任务

对于所有测试数据，保证 $1 \le N \le 2\times 10^5$，$1 \le k_1,k_2,a_i <2^{60}$。对于任意的 $1 \le i<j \le N$，有 $a_i \neq a_j$。

| 测试点编号 | $N\le$ | 特殊性质 |
| :--:|:--:|:--:|
| $1$ | $18$ | 无 |
| $2\sim 3$ | $5\times 10^3$ | A |
| $4\sim 8$ | $5\times 10^3$ | 无 |
| $9\sim 11$ | $2\times 10^5$ | A |
| $12\sim 15$ | $2\times 10^5$ | B |
| $16\sim 25$ | $2\times 10^5$ | 无 |

特殊性质 A：保证 $k_1=k_2$。

特殊性质 B：保证 $k_1=1$。


title: [湖北省选模拟 2024] 永恒 / eternity

background: 总有地上的生灵，敢于直面雷霆的威光。

description:
稻妻的地图可以被划分为 $N$ 行 $M$ 列的网格，第 $i$ 行第 $j$ 列的区域用 $(i,j)$ 表示。曾经，每一块区域中都有一位神之眼拥有者，其元素力编号为 $c_{i,j}$（$0 \le c_{i,j} \le 9$）。

雷电将军降下雷霆的威光，收缴了一部分神之眼。神之眼被收缴的区域，被称为**雷电封锁区**，其他区域称为**非雷电封锁区**。由于你反对眼狩令而遭到通缉，你不能进入**雷电封锁区**，也无法离开稻妻地图区域。

你正在积蓄力量，你可以在**相邻的非雷电封锁区**自由移动。假设你现在在 $(i,j)$，你可以移动到 $(i+1,j),(i-1,j),(i,j+1),(i,j-1)$ 四个区域中的任意一个**非雷电封锁区**。在一次移动中，你积蓄的力量为，经过的所有区域的神之眼元素力编号**依次相连**，对 $1\ 145\ 141$ 取模的结果。例如，你经过的区域神之眼元素力编号依次为 $3,1,0,3,3,3,2,1$，那么你积蓄的力量为 $31033321 \bmod 1145141 = 114514$。**请注意，你的一次移动可以经过相同的非雷电封锁区。重复经过相同的非雷电封锁区将重复积蓄力量。**

常道恢宏，鸣神永恒。永恒的愿望终为南柯一梦，变化的趋势岂可阻挡。稻妻会随时间发生变化。在 $1\sim Q$ 秒，每秒发生了一个事件，事件有如下两种：

- `1 x y c`：若 $c$ 为 `#`，表示 $(x,y)$ 的神之眼已经**被收缴**，$(x,y)$ 为雷电封锁区；若 $c$ 为数字字符，则表示 $(x,y)$ 的神之眼拥有者重获元素力编号为 $c$ 的神之眼，或其神之眼元素力编号变化为 $c$，$(x,y)$ 为非雷电封锁区。

- `2 sx sy tx ty v`：请判断是否存在由 $(sx,sy)$ 出发，到达 $(tx,ty)$ 的移动方式，使得你积蓄了恰好为 $v$ 的力量。保证 $(sx,sy)$ 与 $(tx,ty)$ 均为非雷电封锁区。

请回答全部事件 2，保证至少有一次事件 2。

inputFormat:
输入共 $N+Q+1$ 行。

第一行为四个整数 $N,M,Q,id$，其中 $id$ 表示该测试点编号。

接下来 $N$ 行，每行 $M$ 个字符，描述了稻妻的地图。若第 $i$ 行第 $j$ 个字符为 `#`，则表示 $(i,j)$ 是**雷电封锁区**；若第 $i$ 行第 $j$ 个字符为数字字符，则 $(i,j)$ 为**非雷电封锁区**，该数字字符描述了 $(i,j)$ 神之眼拥有者的神之眼元素力编号。

接下来 $Q$ 行，依照时间顺序描述了每一秒的事件，描述格式如题目描述所示。

outputFormat:
输出若干行，对于每一个事件 2 输出一行：

- 若存在积蓄力量为 $v$ 的移动方式，输出 `Yes`；
- 若不存在积蓄力量为 $v$ 的移动方式，输出 `No`。

samples: 见选手目录下的 eternity/eternity2.in 与 eternity/eternity2.ans。

samples: 该样例符合测试点 9 ∼ 11 的限制。

samples: 见选手目录下的 eternity/eternity3.in 与 eternity/eternity3.ans。


title: [湖北省选模拟 2024] 沉玉谷 / jade

background: 倘若天下无神，这里便是人的国度。

description:
你将主持一场祭祀，祭祀会使用到 $N$ 块排成一列的玉石，玉石从左至右依次编号为 $1,2,\cdots,N$。玉石 $i$ 的颜色为 $a_i$。

每一轮祭祀，你需要选择一段颜色相同的玉石 $a_l \sim a_r(1\le l \le r\le N\le 50)$，并将它们沉入水中。本次祭祀的仙力值 $K$ 将变为 $10000\cdot K+100\cdot l+r$，$K$ 的初始值为 $0$。

一段玉石被沉入水中后，右侧的玉石会向左移动。**同时，编号也会发生变化**，从左至右依次编号为 $1,2,\cdots$。例如，共有 $7$ 块玉石，颜色依次为 $1,1,2,2,2,3,2$。一开始，颜色为 $3$ 的玉石编号为 $6$，在 $3\sim 5$ 号玉石被沉入水中后，其编号将变为 $3$。

当所有玉石被沉入水中，祭祀完成，此时的仙力值即为本次祭祀的仙力值。请问祭祀完成后，一共可能得到多少种不同的仙力值？

由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模的值。

inputFormat:
输入共两行。

输入的第一行为一个正整数 $N$，表示玉石的个数。

输入的第二行为 $N$ 个正整数 $a_1,a_2,\cdots,a_N$，其中 $a_i$ 表示第 $i$ 块玉石的颜色。

outputFormat: 输出一行一个整数，表示不同仙力值的种数对 $10^9+7$ 取模的结果。

samples:
见选手目录下的 jade/jade4.in 与 jade/jade4.ans。
该样例满足测试点 5 ∼ 8 的限制。

samples:
见选手目录下的 jade/jade5.in 与 jade/jade5.ans。
该样例满足测试点 9 ∼ 12 的限制。

samples:
见选手目录下的 jade/jade6.in 与 jade/jade6.ans。
该样例满足测试点 13 ∼ 16 的限制。


title: [湖北省选模拟 2024] 玩具销售员 / tartaglia

background: 孩童时期的梦是最易碎的东西，哪怕放着不管，也总有一天会自己碎掉，所以，一定要有人来保护才行吧。

description:
“独眼小宝”是托克最喜欢的玩具，作为璃月最好的玩具销售员，达达利亚共招募了 $N$ 位经销商负责分销“独眼小宝”，$N$ 位经销商依次编号为 $1,2,\cdots,N$。

$N$ 位经销商中共形成了 $M$ 对交易关系，依次编号为 $1,2,\cdots,M$，第 $i$ 对交易关系联系起经销商 $u_i,v_i$。对于第 $i$ 对交易关系，当一方获知“独眼小宝”的生产情报时，将有 $\dfrac{p_i}{q_i}$ 的概率告知另一方。形式化地，经销商和他们之间的交易关系构成了一张无向图，**数据保证这张无向图是连通的、无自环的和无重边的。**

一些经销商 $a_1,a_2,\cdots,a_k(k>2)$ 构成**商业集团**，**当且仅当**存在 $k$ 组不同的交易关系，使得第 $w$ 组关系联系起经销商 $a_w,a_{w \bmod k+1}$。形式化地，一个商业集团对应 $k$ 名经销商和他们的交易关系图中的一个简单环。**一名经销商最多属于一个商业集团。**

现在，达达利亚希望对这些经销商进行测试，他共进行了 $Q$ 次**独立的**测试。对于第 $i$ 次测试，达达利亚将“独眼小宝”的生产情报告知了经销商 $S_i$，请问期望条件下，共有多少名经销商会得知该情报？

**可以证明，期望一定可以被表示为 $\dfrac{p}{q}$ 的形式，你需要输出 $p\cdot q^{-1}\pmod {998\ 244\ 353}$ 的值。**

inputFormat:
输入共 $M+Q+1$ 行。

输入的第一行为三个正整数 $N,M,Q$，分别表示经销商数量、交易关系数量和测试次数。

接下来 $M$ 行，每行四个正整数 $u_i,v_i,p_i,q_i$，表示第 $i$ 条交易关系联系的经销商与告知概率。

接下来 $Q$ 行，每行一个整数 $S_i$，表示第 $i$ 次测试所告知的经销商。

outputFormat: 输出 $Q$ 行。对于每组询问，输出一行一个整数，表示期望对 $998\ 244\ 353$ 取模的结果。

samples: 见选手目录下的 tartaglia/tartaglia3.in 与 tartaglia/tartaglia3.ans。

samples: 该样例满足测试点 1 ∼ 2 的限制。

samples: 见选手目录下的 tartaglia/tartaglia4.in 与 tartaglia/tartaglia4.ans。

samples: 该样例满足测试点 10 ∼ 13 的限制。

samples: 见选手目录下的 tartaglia/tartaglia5.in 与 tartaglia/tartaglia5.ans。

samples: 该样例满足测试点 14 ∼ 19 的限制。

samples: 见选手目录下的 tartaglia/tartaglia6.in 与 tartaglia/tartaglia6.ans。


title: [湖北省选模拟 2024] 白草净华 / buer

background:
**由于洛谷评测环境限制，请勿使用 C++ 14 (GCC 9) 语言提交本题，否则可能会导致编译错误。**

**这是一道交互题。**

神明只送给人类填饱肚子的知识，人类却借此制作了工具，书写了文字，壮大了城邦，现在又放眼星辰与深渊……

他们每时每刻都在创造全新的「知识」，也令我再也无法移开双眼。

我自认为我擅长提问和回答问题，但我渐渐明白，有很多人是揣着明白装糊涂，问题的答案并不能帮上他们的忙。是不是随着年龄增长，大家都会失去面对质问和答案的勇气呢……

description:
智慧之神布耶尔的知识可以用长度为 $N$ 的数列 $a_0,a_1,\cdots,a_{N-1}$ 表示（请注意，下标从 $0$ 开始）。很遗憾，凡人难以窥探智慧之神的知识，你既不知道 $N$ 的大小，又不知道任何 $a_i$ 的值。

智慧之神是善良的，纳西妲愿意告诉你关于知识的一切：

- 对于任意的 $0 \le i < N$，$a_i \neq a_{(i+1)\bmod N}$。
- **有且仅有一个** $i(0 \le i < N)$，使 $a_i>a_{(i+1)\bmod N}$ 与 $a_i > a_{(i+N-1)\bmod N}$ 同时成立。

你可以向智慧之神提问，每次提问，你可以向纳西妲提供一个 $0\sim10^9$ 范围内的整数 $k$，纳西妲将回答你 $a_{(d+k)\bmod N}$ 的值。其中，$d$ 是上一次纳西妲回答的元素的下标。$d$ 的初始值设定为 $0$。例如，$N=5$，你依次向纳西妲提供了 $1,2,3$，纳西妲回答的数字依次为 $a_1,a_3,a_1$。

你有 $333$ 次提问的机会，你需要求出数列 $a$ 中的最大值。

你，还有质问与提问的勇气吗？

### 实现细节

交互库实现了如下函数，**选手需要在程序中声明这些函数，但不应该实现其函数体**：

```cpp
int ask(int k);
```

- 这个函数返回  $a_{(d+k)\bmod N}$ 的值，并将 $d$ 的值修改为 $d+k$。

```cpp
int cheat();
```

- 这个函数返回 $N$ 的值。
- **调用该函数，将不能得到测试点全部的分数，详见评分方式部分。**

**你不需要，也不应该实现主函数。** 你需要实现函数 `buer`：

```cpp
int buer(int T);
```

- `T` 表示测试点编号。
- 你需要在函数结束时，返回数列 $a$ 的最大值。

**此外，你提交的程序不应试图从或向任何文件或标准控制流读取或写入信息，否则本题以零分计。** 你的程序需要引用全部你所需要的头文件与命名空间。

最终测试时，在每个测试点，交互库会恰好调用一次 `buer` 函数，并将其返回值作为你程序的结果。

下面是一个示例程序，其功能是获取 $a_1 \sim a_9$ 并返回 $\max(a_1,a_2)$。选手可以在此基础上继续实现本题。

```cpp
#include <vector>
using std::max;
using std::vector;
// 引用所需头文件与命名空间中的函数
int ask(int k);
int cheat();
// 声明 ask 与 cheat 函数
int buer(int T) {
	vector <int> vec;
	for(int i = 1; i <= 9; i++) {
		int p = ask(1);
		vec.push_back(p);
	}
	return max(vec[0], vec[1]);
}
```

**保证在 `ask` 函数调用不超过 $3333$ 次的情况下，最终测试的交互库运行所需时间不超过 $0.2$ 秒，交互库本身所消耗的内存不超过 $10$ MiB。**

### 测试程序方式

本题目录下提供了交互库的参考实现 `grader.cpp`。最终测试时所使用的交互库实现与该实现有所不同，因此选手的解法**不应依赖交互库的具体实现**。

选手实现程序 `buer.cpp` 后，将 `grader.cpp` 与 `buer.cpp` 放置在同一目录下，使用如下命令编译得到可执行程序：

```plain
g++ -c grader.cpp -O2 -std=c++14
g++ -c buer.cpp -O2 -std=c++14
g++ grader.o buer.o -o buer -O2 -std=c++14
```

其中第一行命令会编译 `grader.cpp` 得到目标文件 `grader.o`，第二行命令会编译 `buer.cpp` 得到目标文件 `buer.o`，第三行命令会将 `grader.o` 与 `buer.o` 链接起来，生成可执行文件 `buer`。

按上述方法编译得到的可执行文件 `buer`，其运行方式如下：

- 可执行文件将从 `buer.in` 读入以下格式的数据：

- - 第一行为两个正整数 $N,T$，分别表示 $a$ 的长度与测试点编号。

- - 第二行为 $N$ 个正整数 $a_0,a_1,\ldots,a_{N-1}$，表示数列 $a$。

- 若你的程序正常运行完毕，可执行文件将向 `buer.out` 写入以下内容：

- - 输出一行两个整数，分别表示你的询问次数与 `buer` 函数的返回值。

选手在调试时需要保证输入可执行文件 `buer` 的数据满足上述格式，否则不保证交互库正确运行。

inputFormat: 你提交的程序不应试图从或向任何文件或标准控制流读取或写入信息。

outputFormat: 你提交的程序不应试图从或向任何文件或标准控制流读取或写入信息。

hint:
### 样例解释 1

本题提供的样例输入中，第一行为两个整数 $N,T$，分别表示 $N$ 与测试点编号，样例测试点编号均为 $0$。第二行为 $N$ 个整数 $a_0,a_1,\cdots,a_{N-1}$，表示数列 $a$。样例输出为一行一个正整数，表示数列 $a$ 的最大值。

**请注意，你的程序不应试图从或向任何文件或标准控制流读取或写入信息。**

### 评分方式

最终评测**只**收取 `buer.cpp`，请不要提交选手目录下其他文件。

**本题首先会受到和传统题相同的限制**，例如编译错误会导致整道题目得 $0$ 分，运行
时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。

在上述条件以外，在一个测试点中，若程序执行了非法的函数调用或 `buer` 函数返回了错误答案，该测试点将会获得 $0$ 分。否则，假设你的程序调用了 $Q$ 次 `ask` 函数：

- 若 $0 \le Q \le 333$，且没有调用 `cheat` 函数，该测试点得 $5$ 分。

- 若 $333<Q\le 3333$，且没有调用 `cheat` 函数，该测试点得 $3$ 分。

- 若 $0\le Q \le 333$，但调用了 `cheat` 函数，该测试点得 $2$ 分。

- 若 $333<Q\le 3333$，但调用了 `cheat` 函数，该测试点得 $1$ 分。
- 若 $Q>3333$，该测试点得 $0$ 分。

### 子任务

对于所有测试数据，保证 $2 \le N \le 10^6$，$1 \le a_i \le 10^9$。

| 测试点编号 | $N\le$ |
| :--: | :--: |
| $1$ | $333$ |
| $2\sim 20$ | $10^6$ |


title: [CCPC 2023 北京市赛] 游戏

description:
小 I 和小 J 又在玩游戏。

小 J 找来了一棵 $n$ 个点的树。树上的每条边有开启和关闭两个状态，初始树上每条边都是开启的。

初始树上有一颗棋子放在 $1$ 号节点。小 I 可以移动棋子，目标是将棋子移动到一个度数**恰好**为 $1$ 的节点上；小 J 可以关闭树上的边，目标是阻止小 I 将棋子移动到度数恰好为 $1$ 的节点上。

游戏分为若干轮，每轮有如下环节：

1. 小 I 任务判定：如果棋子在度数恰好为 $1$ 的节点上，小 I 获胜，否则进入第 2 步；
2. 小 J 行动：小 J 将一条目前开启的边，将这条边永久关闭，进入第 3 步，如果目前不存在开启的边则直接跳过行动进入第 3 步；
3. 小 I 行动：小 I 选择一条连接当前棋子所在节点且开启的边，将棋子移动到这条边的另一个节点上。如果没有这样的边，小 J 获胜，否则进入新的一轮，回到第 1 步。

小 J 想知道，如果小 I 和小 J 知道这棵树的形态且绝顶聪明，谁会获胜。

inputFormat: 第一行一个整数 $n (1 \le n \le 10^5)$ 表示树的节点数，接下来 $n-1$ 行每行两个整数 $u,v (1 \le u, v \le n)$，表示树上的一条边。

outputFormat: 如果小 I 获胜，输出 `You win, temporarily.`，否则输出 `Wasted.`。

hint:
【样例解释 1】

小 J 的策略如下：

- 小 J 将 $(1,2)$ 关闭，这样小 I 只能移动到 $5$；
- 小 J 将 $(5,6)$ 关闭，这样小 I 只得移动回 $1$；
- 小 J 将 $(1,5)$ 关闭，于是小 I 无法移动。


title: [CCPC 2023 北京市赛] 替换

description:
给定一个长度为 $n$、字符集为 `01?` 的字符串 $s_1s_2 \cdots s_n$。

对于任意 $k \in [1,n]$，考察字符串 $T_k = t_1 t_2 \cdots t_n$，其中对于 $1 \le i \le n$，

- 若 $s_i \ne$ `?`，则 $t_i = s_i$；
- 否则，若 $i \le k$，$t_i =$ `0`；
- 否则 $t_i = t_{i-k}$，你可以通过递归地算出 $t_{i-k}$ 得到 $t_i$。

容易发现 $T_k$ 的字符集为 `01`。你需要对所有 $k \in [1,n]$ 求出 $T_k$ 中 `1` 的个数。

inputFormat: 输入的第一行一个整数 $n (1 \le n \le 10^5)$ 表示字符串长度，第二行一个长度为 $n$、字符集为 `01?` 的字符串 $s_1s_2\cdots s_n$。

outputFormat: 输出 $n$ 行，第 $i$ 行一个整数表示 $T_i$ 中 `1` 的个数。


title: [CCPC 2023 北京市赛] 史莱姆工厂

description:
有 $n$ 个史莱姆排成一行，其中第 $i$ 个的颜色为 $c_i$，质量为 $m_i$。

你可以执行任意次把一个史莱姆的质量增加 $1$ 的操作，需要花费 $w$ 的价钱。

但是一旦史莱姆的质量达到 $k$ 或以上，就会变得不稳定而必须在下一次操作之前被卖掉。你只能卖出质量大于等于 $k$ 的史莱姆。根据市场价，卖掉一个质量为 $i$ 的史莱姆可以得到 $p_i$ 的收入。保证 $p_i-p_{i-1}<w$。但不保证 $p_i$ 单调不降。

卖掉一个史莱姆之后，它两边的史莱姆会被挤压继而靠在一起。如果这两个史莱姆颜色相同，那么就会互相融合成一个史莱姆，其质量是二者的质量之和。这个新的史莱姆也有可能需要被卖掉从而接着进行这个过程。

你想知道卖掉所有史莱姆最多可以净赚多少。

inputFormat:
第一行三个正整数 $n,k,w(1\le n\le 150, 2\le k\le 10, 1\le w\le 10^6)$。

第二行 $n$ 个正整数，其中第 $i$ 个表示 $c_i(1\le c_i\le n)$。保证 $c_i\not=c_{i-1}$。

第三行 $n$ 个正整数，其中第 $i$ 个表示 $m_i(1\le m_i<k)$。

第四行 $k-1$ 个整数，分别表示卖出质量为 $k$ 到 $2k-2$ 的史莱姆的收入，即 $p_k$ 到 $p_{2k-2}$，保证 $0\le p_i\le 10^9$，且 $p_i-p_{i-1}<w$。

保证相邻两个史莱姆的颜色不同。

outputFormat: 一行一个整数，表示卖出所有史莱姆最大的净利润。

hint:
先增加颜色为 $3$ 的史莱姆的质量。然后它被卖掉，获得 $5$ 的收入。

然后增加颜色为 $1$ 的史莱姆的质量两次。然后它被卖掉，获得 $5$ 的收入。接着两个颜色为 $2$ 的史莱姆融合在一起卖掉，获得 $7$ 的收入。

操作了三次需要 $18$ 的花费，所以净利润为 $-1$。可以证明不存在更好的方案。


title: [CCPC 2023 北京市赛] 三染色

description:
我有一个调色盘，总共 $n$ 行 $m$ 列，形成了 $n\times m$ 个格子，每个格子里要放一朵花。可以放置的花有 $3$ 种颜色可以选择，分别用 $0,1,2$ 表示。

花朵注视着它周围的花，并想要变成其他花朵的样子。如果在一个时刻，一朵颜色为 $c$ 的花的上、下、左、右之一，有至少一朵花的颜色为 $c-1$，那么这朵花在下一个时刻会变成颜色 $c-1$，否则它在下一个时刻的颜色仍然是 $c$。其中颜色 $\bmod 3$ 考虑。

对于一个初始的在调色盘中放花的方案，如果经过有限个时刻之后，所有花都变成同一颜色，我们称这个放花的方案是**美好的**。

不难看出，对于一个美好的放花方案，每朵花都有一个最早的时刻，它在这个时刻之后一直不变色。我们称这个时刻为这朵花的**稳定时刻**。
我们从第 $0$ 时刻开始计时，所以一朵花如果从未改变颜色，那么它的稳定时刻就是 $0$。

现在我已经在调色盘的一些格子中放置了花朵，也有一些格子是空的。我想知道，有多少种给剩余的格子放花的方案，使得这个方案是美好的？以及，对于这些美好的方案，位于第 1 行第 1 列格子中花朵的稳定时刻的总和是多少？

你只需要回答我这两个结果对 $998244353$ 取模的值。

inputFormat:
输入第一行为两个正整数 $n,m$（$2 \le n \le 5$，$2 \le m \le 50$）。

接下来 $n$ 行，每一行 $m$ 个整数，第 $i$ 行第 $j$ 个整数 $a_{i,j}\in \{0,1,2,3\}$ 表示对应方格的状态。其中 $a_{i,j}\in \{0,1,2\}$ 表示有一朵花，以及这朵花的颜色，$a_{i,j}=3$ 表示没有花。

outputFormat: 输出一行两个整数，表示美好的方案数，和左上角格子中花朵稳定时刻的总和。

hint:
**【样例解释 1】**

只有在未知格子放入花朵颜色为 $0$ 的时候会结束，并且在两个时刻之后所有花朵的颜色全部变为 $2$，此时左上角方格中的花朵颜色变成 $2$ 并不再改变，因此它的稳定时刻就是 $2$。


title: [CCPC 2023 北京市赛] 广播

description:
小 I 正在学习使用 Pytorch。这是一个非常热门的用于机器学习训练的 Python 库。

小 I 注意到，Pytorch 中对于张量运算有称作“广播”(broadcast)的机制。你可以认为张量是高维数组。对于一个 $k$ 维张量 $A$，我们用长度为 $k$ 的序列 $(a_1,a_2,\cdots,a_k)$ 表示其各个维度的长度，也就是说 $A$ 是一个 $a_1 \times a_2 \times \cdots \times a_k$ 的张量。

对于两个张量 $A$ 和 $B$，设它们的维度分别为 $(a_1,a_2,\cdots,a_m)$ 和 $(b_1,b_2,\cdots,b_n)$，称 $A$ 和 $B$ 是 **可广播的**，当且仅当以下性质成立：

- 对于任意整数 $0 \le i \le \min(n,m) - 1$，要么 $a_{m-i} = b_{n-i}$，要么 $a_{m-i}$ 和 $b_{n-i}$ 中至少有一个是 $1$。

现在小 I 有两个张量，它们的维度分别是 $(p_1,p_2,\cdots,p_m)$ 和 $(q_1,q_2,\cdots,q_n)$，它们不一定是可广播的。

为此，小 I 可以使用 Pytorch 内置的函数进行若干次操作（可以不做操作），每次操作对序列 $p$ 或 $q$ 进行以下修改：

- 选择 $p$ 或 $q$，在选定序列的任意一个位置插入一个 $1$。

小 I 想知道他最少要多少次操作才能让两个张量变为可广播的。

inputFormat:
输入的第一行两个整数 $m,n(1 \le m,n \le 2000)$ 表示两个张量的维度。

第二行 $m$ 个整数 $p_1,p_2,\cdots,p_m (1 \le p_i \le 2000)$ 描述第一个张量每个维度的长度。

第三行 $n$ 个整数 $q_1,q_2,\cdots,q_n (1 \le q_i \le 2000)$ 描述第二个张量每个维度的长度。

outputFormat: 输入一行一个整数表示最少的插入 $1$ 的数量使得两个张量变为可广播的。

hint: 在序列 $q$ 的第二个位置之前插入一个 $1$（得到 `4 1 2`），两个张量就会变为可广播的。


title: [CCPC 2023 北京市赛] 最小环

description:
小 I 发明了 $O(n + m)$ 的有向图最小环，于是他想考考你。

给定一个 $n$ 个节点、$m$ 条边的有向图，每条边有正整数边权。你需要求出图上的一个环使得环上边的边权和最小。求出这个最小值，或者报告不存在环。

当然，由于你不会 $O(n + m)$ 的有向图最小环，于是小 I 放宽了条件：保证输入的图是弱连通的，且 $m-n$ 不会很大。一个图是弱连通的当且仅当将有向边换为无向边后图连通。

inputFormat:
第一行两个整数 $n,m (1 \le n \le 3 \times 10^5, -1 \le m-n \le 1500)$，表示图的点数和边数。

接下来 $m$ 行每行三个整数 $u_i,v_i,w_i (1 \le u_i,v_i \le n, 1 \le w_i \le 10^9)$，表示一条从 $u_i$ 到 $v_i$、边权为 $w_i$ 的有向边。保证图是弱连通的。

outputFormat: 如果图中不存在环，输出 `-1`，否则输出一个整数表示最小环的长度和。

hint:
**【样例解释 1】**

最小环为 $1 \to 2 \to 4 \to 3 \to 1$。

**【样例解释 3】**

最小环为 $1 \to 1$。


title: [CCPC 2023 北京市赛] 线段树

description:
有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，保证 $a_i$ 为**奇数**。

有两种操作：

1. 给定 $l,r,x$，将 $a_l,a_{l+1},\cdots,a_r$ 加上**偶数** $x$；

2. 给定 $l,r$，求 $a_l,a_{l+1},\cdots,a_r$ 的乘积，答案对 $2^{20}$ 取模；

inputFormat:
第一行两个正整数 $n,q$ 表示序列的长度和询问的个数. 保证 $1 \le n,q \le 2\times 10^5$。

第二行 $n$ 个**奇数** $a_1,a_2,\cdots,a_n$. 保证 $1 \le a_i < 2^{20}$。

接下来 $q$ 行，每一行表示一个操作，格式为以下两种之一：

- $1 ~ l ~ r ~ x$：表示进行第一种操作. 保证 $1 \le l \le r \le n$，$0 \le x < 2 ^ {20}$。
- $2 ~ l ~ r$：表示进行第二种操作. 保证 $1 \le l \le r \le n$。

outputFormat: 对于每一次 $2$ 操作，输出一行一个整数表示答案。


title: [CCPC 2023 北京市赛] 哈密顿

description:
给出 $n$ 个二元组 $(a_i,b_i)$。

考虑 $n$ 个节点的带权有向完全图 $G$，其中从 $i (1 \le i \le n)$ 到 $j (1 \le j \le n)$ 的边边权为 $|a_i-b_j|$。

求 $G$ 的一条哈密顿回路使得其经过的边的边权和最大，并给出这个最大值。

inputFormat: 输入的第一行一个整数 $n(2 \le n \le 10^5)$ 表示二元组个数，接下来 $n$ 行每行两个整数 $a_i,b_i(0 \le a_i,b_i \le 10^9)$ 表示每个二元组。保证输入的 $n$ 个二元组中的总共 $2n$ 个数两两不同。

outputFormat: 输出一行一个整数表示最大的哈密顿回路边权和。

hint:
考察哈密顿回路 $1 \to 2 \to 3 \to 1$，其边权和为 $|1-2| + |
8-5| + |4-10| = 10$。可以证明不存在哈密顿回路边权和超过 $10$，因此答案为 $10$。


title: [CCPC 2023 北京市赛] 勿蹖宠物

description:
Ene 喜欢回文。

Ene 现在有一些单词。她想选出若干个单词并将它们首尾相连，形成长度恰好为 $L$ 的回文串。每个单词都可以选择多次，也可以不选。

Ene 想知道这样做的方案数。Ene 认为两个方案不同，当且仅当各单词出现次数不同或它们的排列顺序不同，注意多种不同的方案可能会得到同一个回文串。由于答案可能会很大，你需要将答案对 $1,000,000,007$ 取模。

inputFormat:
输入的第一行包含两个正整数 $N, L$，分别表示单词的数量和需要组成的回文串的长度。保证 $1\le N\le 333$，$1\le L\le 1000$。

接下来 $N$ 行，每行输入一个字符串 $s_i$，表示一个单词。保证 $1\le |s_i| \le L$，$\sum_{i=1}^N |s_i| \le 600$；输入的单词仅包含小写字符，且互不相同。

outputFormat: 输出一个非负整数，表示组成回文串的方案数对 $1,000,000,007$ 取模后的结果。

hint:
**【样例解释 1】**

有以下五种方案：

- `stack` `cats`
- `evil` `olive`
- `eel` `eve` `lee`
- `lee` `eve` `eel`
- `eve` `eve` `eve`

**【样例解释 2】**

有以下两种方案：

- `a` `a`
- `aa`


title: [CCPC 2023 北京市赛] 图

description: 给定一个 $n$ 个点的无向正权完全图，请对于每一条边 $(a,b)$，求出是否存在一个点对 $(x,y)$ 使得 $x\rightarrow y$ 的所有最短路都经过 $(a,b)$。

inputFormat:
第一行一个正整数 $n (1 \le n \le 500)$ 表示图的点数。

接下来 $n$ 行每行 $n$ 个数，构成一个大小为 $n\times n$ 的矩阵，第 $i$ 行第 $j$ 个数 $a_{i,j}(1\leq a_{i,j}\leq 10^6)$ 表示 $(i,j)$ 之间的边长度，特别地，$a_{i,i} = 0$.

保证 $a_{i,j}=a_{j,i}$。

outputFormat:
输出一个大小为 $n$ 的 $01$ 矩阵，其中第 $i$ 行第 $j$ 列为 $1$ 表示边 $(i,j)$ 满足题目中提出的要求，$0$ 表示不满足。

特别的，当 $i=j$ 时输出 $0$。


title: [CCPC 2023 北京市赛] 报数 IV

background: 这是小 R 和小 Z 第四次玩报数游戏了，因此他们决定不再编冗长的题面了。你只需要知道，他们又编了一个奇怪的报数规则，然后想算一下有哪些数字可以报出来。

description:
对于任意正整数 $n$，定义函数 $f(n)$ 为 $n$ 在十进制下各个数位之和，如 $f(114514)=1+1+4+5+1+4=16$。显然 $f(n)$ 也是正整数，因此可以嵌套地考虑 $f(f(n)),f(f(f(n)))$ 等等。进而对于正整数 $n,k$ 可以定义 $g(n,k)=f(f(...f(n)))$（共有 $k$ 层 $f$）。

为了让报数游戏不再每局都是一模一样的，小 R 和小 Z 决定为每局游戏设置两个正整数 $k,m$，然后规定：在这一局游戏中，所有满足 $g(n,k)=m$ 的正整数 $n$ 都是不能报出的。

因为两人都是游戏高手，为防止游戏无限进行下去，每局游戏中还给出了一个正整数 $N$ 表示报数的上界。两人想知道：在不超过 $N$ 的正整数中，有多少是按这个规则不能报出的。

inputFormat:
第一行：一个正整数 $T$，表示小 R 和小 Z 进行的游戏轮数，保证 $1 \le T \le 5$。

接下来 $T$ 行，每行 $3$ 个正整数 $N,k,m$，描述一局游戏，含义如上文所述。保证 $1 \le N \le 10^{1000}, 1 \le k,m \le 10^9$。

outputFormat: 输出 $T$ 行，每行一个整数，表示这局游戏中不能报出的数的个数，对 $10^9+7$ 取模。


title: 机器人

background:
![](https://cdn.luogu.com.cn/upload/image_hosting/sub3kd3c.png)

> 画师：白森 さわ（from pixiv），侵删。

description:
真寻连清理炸弹都懒得自己使用，于是美波里又发明了一款全自动扫地机器人来清理房间。

真寻的房间由 $n$ 行 $m$ 列的方砖组成，第 $i$ 行第 $j$ 列的方砖上的灰尘数量为 $a_{i,j}$。美波里的机器人每天会从房间的左上角出发，每次随机往右或往下走一步。

若机器人在没有撞墙的情况下走到了右下角，那么它会返回**它经过的所有方砖的灰尘数量的异或和**给美波里；若机器人在走到右下角之前撞了墙，即某一步的目标位置不存在，那么机器人会返回一个错误值 $x$ 并结束移动。

现给出某一天真寻的房间中每一块方砖上的灰尘数量，请你求出机器人返回值的期望值。

形式化地，给定一 $n\times m$ 的矩阵 $a$，第 $i$ 行第 $j$ 列的权值为 $a_{i,j}$，现有一机器人从 $(1,1)$ 出发，每次各有 $\frac{1}{2}$ 的概率从 $(i,j)$ 移动至 $(i,j+1)$ 或 $(i+1,j)$；若机器人移动至 $(n,m)$，则返回**路径点权异或和**；若在移动至 $(n,m)$ 前有任意时刻移动至矩阵外，则返回 $x$；求返回值的期望值。

答案对 $10^9+7$ 取模。

inputFormat:
第一行三个整数 $n,m,x$，分别表示方砖行数、列数及错误值；

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数表示 $a_{i,j}$，描述每一块方砖上的灰尘数量。

outputFormat:
一行一个整数 $ans$，表示期望值在模 $10^9+7$ 意义下的值。

若对有理数取余有疑惑，请参照 [P2613 【模板】有理数取余](https://www.luogu.com.cn/problem/P2613)。

hint:
**样例** $\mathbf{1}$ **解释**

若机器人第一步往下走，则：

- 若机器人第二步往下走，则撞墙，返回 $5$，概率为 $\frac{1}{4}$；

- 若机器人第二步往右走，则：

	- 若机器人第三步往下走，则撞墙，返回 $5$，概率为 $\frac{1}{8}$；

    - 若机器人第三步往右走，则到达右下角，返回 $7\oplus 10\oplus 6\oplus 3=8$，概率为 $\frac{1}{8}$；

若机器人第一步往右走，则：

- 若机器人第二步往下走，则：

	- 若机器人第三步往下走，则撞墙，返回 $5$，概率为 $\frac{1}{8}$；

    - 若机器人第三步往右走，则到达右下角，返回 $7\oplus 18\oplus 6\oplus 3=16$，概率为 $\frac{1}{8}$；

- 若机器人第二步往右走，则：

    - 若机器人第三步往下走，则到达右下角，返回 $7\oplus 18\oplus 4\oplus 3=18$，概率为 $\frac{1}{8}$；

    - 若机器人第三步往右走，则撞墙，返回 $5$，概率为 $\frac{1}{8}$；

因此，返回值的期望值为 $\frac{3\times 5+8+16+18}{8}+\frac{5}{4}=\frac{67}{8}$，在模 $10^9+7$ 意义下为 $375000011$。

**数据范围**

对于所有数据，$1\leq n,m\leq 10^3$，$0\leq a_{i,j},x\leq 10^9$。

本题共 $22$ 个测试点，**采用捆绑测试**，子任务及数据点分配如下：

| 子任务编号 | 数据点编号 | 特殊性质 | 分值 |
| :-: | :-: | :-: | :-: |
| $0$ | $1\sim 4$ | $n,m\leq 12$ | $10$ |
| $1$ | $5\sim 8$ | $n,m\leq 20$ | $20$ |
| $2$ | $9\sim 12$ | $a_{i,j}\leq 20$ | $20$ |
| $3$ | $13\sim 16$ | $x=0$ | $20$ |
| $4$ | $17\sim 22$ | 无特殊限制 | $30$ |

**提示**

$\oplus$ 表示异或（bitwise xor），$x_1,x_2,x_3,\cdots,x_n$ 的异或和为 $x_1\oplus x_2\oplus x_3\oplus\cdots \oplus x_n$。


title: [LMXOI Round 1] Size

background: 在漆黑的夜晚，魔女带走了 LMX，HQZ 为了拯救 LMX。要完成魔女给出的任务。

description:
魔女给出一个长度为 $n$ 的序列 $d$，魔女想要求得：

$$\sum\limits_{i=1}^{ n}\sum\limits_{j=1}^{n}{((d_i\oplus d_j)+(d_i \otimes d_j))}$$

其中定义 $\oplus$ 代表二进制下两数相加的和数位上 $1$ 的个数， $\otimes$ 代表二进制下较大减较小的差数位上 $1$ 的个数。

inputFormat:
一行一个整数 $n$ 表示序列的长度。

第二行 $n$ 个非负整数，表示序列 $d$。


title: 漫长悄悄话

background:
> 故事从哪一页起始？
>
> 小石头，红土地，遥远的火。
>
> 摸索的轮廓，夜空之中，扑火的人。
>
> 手与手的相握，心与心碰触。
>
> 涌动在喉咙深沉，我温暖的火。

description:
一些前置定义：

- $\text{Rev}(S):$ $S_{|S|},S_{|S|-1},\dots,S_1$ 顺次相连形成的字符串。即将 $S$ 翻转。

- $\text{lcp}(i,j):$ 第 $i$ 个位置开始的后缀与第 $j$ 个位置开始的后缀的最长公共前缀**对应的字符串**。

- $\text{lcs}(i,j):$ 第 $i$ 个位置结束的前缀与第 $j$ 个位置结束的前缀的最长公共后缀**对应的字符串**。

- $\text{LCP}(S,T):$ $S$ 和 $T$ 的最长公共前缀。
----

给出长度为 $n$ 的字符串 $S$，求：

$$\max\limits_{1 \le i < j \le n}\{\text{LCP}(\text{Rev}(\text{lcs}(i,j)),\text{lcp}(i,j))\}$$

inputFormat:
第一行一个整数 $n$。

第二行一个长度为 $n$ 的字符串 $S$。

outputFormat: 输出为一个数，即答案。

hint:
### 样例一解释

$\text{lcp}(3,7):$ `bba`。

$\text{lcs}(3,7):$ `abb`。

$\text{LCP}(\text{Rev}(\texttt{\color{blue}abb}),\texttt{\color{blue}bba}):$ `bba`。

可以证明，没有比 $i=3,j=7$ 更优的方案。

### 数据范围与约束

对于 $30\%$ 的数据，$1 \le n \le 2\times 10^3$。

对于 $60\%$ 的数据，$1 \le n \le 10^5$。

对于另外 $10\%$ 的数据，$\forall 1 \le i \le n-2,S_{i}\not=S_{i+2}$。

对于 $100\%$ 的数据 $1 \le n \le 10^6$，输入均为整数和小写字母。


title: 【MX-X3-T6】「RiOI-4」TECHNOPOLIS 2085

background:
![](https://cdn.luogu.com.cn/upload/image_hosting/931ql7zi.png)

（图片来自 phigros 曲绘，侵删。）

啊～啊～啊咦～啊咦～哦→啊↑啊↓啊～嗯～哎哎↑哎哦哎嗯～哦啊~爱↖爱↑爱↗爱↑爱↑啊～啊～啊咦～啊咦～啊→啊↑啊↓啊～嗯嗯↓嗯↓滴嘚滴嘚唔↑～～嘟←嘟↖嘟↑嘟↗嘟→嘟↘嘟↓

你说得对，但是这里是梦熊周赛题，不是出题人用来发电的地方，所以你需要做一道图论题。

description:
约定 $\operatorname{lca}_G(u,v)$ 表示编号为 $u,v$ 的结点在有标号有根树 $G$ 上的最近共同祖先。给定一棵根编号为 $1$，大小为 $n$ ，结点编号为 $1\sim n$ 的有根树 $T$ 与一个大小为 $m$ 的点集 $S$。你需要求出有多少个**不同的**大小为 $n$ 的结点编号为 $1\sim n$ 的有根树 $T'$，满足对于任意 $u,v\in S$，有 $\operatorname{lca}_T(u,v)=\operatorname{lca}_{T'}(u,v)$。

答案对 $998\,244\,353$ 取模。

我们称两颗大小为 $n$ 的有标号有根树是**不同的**，当且仅当以下二者至少一个成立：

- 它们的根节点不同。
- 存在一条边，在一棵树中未出现，而在另一棵树中出现。

inputFormat:
第一行两个正整数 $n,m$。

第二行 $n-1$ 个正整数 $p_2,p_3,\cdots,p_n$ 表示编号为 $2\sim n$ 的结点的父亲编号。

最后一行 $m$ 个正整数，表示选出的集合 $S$ 中结点的编号。

outputFormat: 一行一个整数，表示答案对 $998\,244\,353$ 取模的值。


title: [IOI2021] 修改 DNA

background:
**滥用本题评测将被封号**

**由于技术限制，请不要使用 C++ 14 (GCC 9) 语言提交本题。**

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数

description:
Grace 是一名生物学家，在新加坡的一个生物信息学公司工作。她的一部分工作是分析不同有机体的 DNA 序列。DNA 序列是包含字符 A、T 和 C 的字符串。注意在本题中，DNA 序列不包含字符 G。

定义一次修改是把 DNA 序列中的两个元素交换位置的操作。例如，通过交换加粗的字符 A 和 C，一次修改可以把 A**C**T**A** 转化为 A**A**T**C**。

两个序列的修改距离是把一个序列转化为另一个序列所用的最少修改次数。如果不能通过修改把一个序列转化为另一个序列，那么这两个序列的修改距离为 $-1$。

Grace 正在分析两个 DNA 序列 $a$ 和 $b$，每个都由 n 个元素组成，下标从 $0$ 到 $n - 1$。你的任务是帮助 Grace 回答以下形式的 $q$ 个问题：子串 $a[x \ldots y]$ 和 $b[x \ldots y]$ 的修改距离是多少？这里，DNA 序列 $s$ 的子串 $s[x \ldots y]$ 定义为 $s$ 的下标从 $x$ 到 $y$（包括 x 和 y）的连续字符序列。也就是说，$s[x \ldots y]$ 是序列 $s[x] s[x + 1] \ldots s[y]$。

inputFormat:
你要实现以下函数：
```cpp
void init(string a, string b)
  ```
- $a, b$：长度为 $n$ 的字符串，表示两个待分析的 DNA 序列。
恰好调用此函数一次，且发生在任何对 `get_distance` 的调用之前。
```cpp
int get_distance(int x, int y)
```
- $x, y$：待分析的子串的开始和结束下标。
此函数应返回子串 $a[x \ldots y]$ 和 $b[x \ldots y]$ 的修改距离。
恰好调用此函数 $q$ 次。

hint:
对于所有数据：

- $1 \le n, q \le 100 \, 000$
- $0 \le x \le y \le n - 1$
- $a$ 和 $b$ 的每个字符都是 A、T 和 C 之⼀

子任务|分值|特殊限制
:-:|:-:|:-:
$1$	|$21$|$y - x \le 2$
$2$	|$22$|	$q \le 500$，$y - x \le 1000$，$a$ 和 $b$ 的每个字符是 A 或 T
$3$	|$13$|	$a$ 和 $b$ 的每个字符是 A 或 T
$4$	|$28$|	$q \le 500$，$y - x \le 1000$
$5$	|$16$|	没有额外的约束条件

## 样例解释

如果评测程序调用 `get_distance(1, 3)`，那么该调用应返回 $a[1 \ldots 3]$ 和 $b[1 \ldots 3]$（也就是序列 TAC 和 CTA）之间的修改距离。通过 $2$ 次修改可以把 TAC 转化为 CTA：TAC $\to$ CAT，然后是 CAT $\to$ CTA。无法通过比 $2$ 次更少的修改完成该转化。

因此，该调用应返回 $2$。

如果评测程序调用 `get_distance(4, 5)`，那么该调用应返回序列 AT 和 TA 之间的修改距离。 通过一次修改可以把 AT 转化为 TA，而且显然至少需要一次。

因此，该调用应返回 $1$。

最后，如果评测程序调用 `get_distance(3, 5)`，由于无法通过修改将序列 CAT 转化为 ATA，因此该调用应返回 $-1$。


title: [IOI2021] 位移寄存器

background:
**滥用本题评测将被封号**

**由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。**

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。

你的代码需要在开头添加以下代码：

```cpp
#include<vector>
void append_move(int t, int y);
void append_store(int t, std::vector<bool> v);
void append_and(int t, int x, int y);
void append_or(int t, int x, int y);
void append_xor(int t, int x, int y);
void append_not(int t, int x);
void append_left(int t, int x, int p);
void append_right(int t, int x, int p);
void append_add(int t, int x, int y);
void append_print(int t);
```

description:
工程师 Christopher 在开发一款新的计算机处理器。

这个处理器可以访问 $m$ 个不同的 $b$ 位存储单元（本题中 $m = 100$ 且 $b = 2000$）。它们被称作寄存器，编号从 $0 $ 到 $m - 1$。我们把这些寄存器记为 $r[0], r[1], \ldots , r[m - 1]$。每个寄存器都是 $b$ 个比特的数组，这些比特从 $0$（最右的比特）到 $b - 1$（最左的比特）编号。对所有的 $i$（$0 \le i \le m - 1$）和 $j$（$0 \le j \le b - 1$），我们将寄存器 $i$ 的第 $j$ 个比特记为 $r[i][j]$。

对所有的比特序列 $d_0, d_1, \ldots , d_{l - 1}$（具有某个长度 $l$），该序列的整数值等于 $2^0 \cdot d_0 + 2^1 \cdot d_1 + \cdots + 2^{l - 1} \cdot d_{l - 1}$。我们说存储在某个寄存器中的整数值就是寄存器中比特序列的整数值，也就是说，该整数值为 $2^0 \cdot r[i][0] + 2^1 \cdot r[i][1] + \cdots + 2^{b - 1} \cdot r[i][b - 1]$。

该处理器有 $9$ 种类型的指令，可以用来修改寄存器中的比特。每条指令操作一个或多个寄存器，并将其输出存储到其中的一个寄存器。下面我们用 $x := y$ 表示一个修改 $x$ 的值并将其变成 $y$ 的操作。每种类型的指令所做的操作描述如下：

$\operatorname{\mathit{move}}(t, y)$：将寄存器 $y$ 中的比特数组拷贝到寄存器 $t$。对所有的 $j$（$0 \le j \le b - 1$），设置 $r[t][j] := r[y][j]$。

$\operatorname{\mathit{store}}(t, v)$：设置寄存器 t 等于 $v$，这里 $v$ 是某个 $b$ 个比特的数组。对于所有的 $j$（$0 \le j \le b - 1$），设置 $r[t][j] := v[j]$。

$\operatorname{\mathit{and}}(t, x, y)$：取寄存器 $x$ 和 $y$ 的按位与，并将结果存到寄存器 $t$ 中。对于所有的 $j$（$0 \le j \le b - 1$），如果 $r[x][j]$ 和 $r[y][j]$ 同时为 $1$ 则设置 $r[t][j] := 1$，否则设置 $r[t][j] := 0$。

$\operatorname{\mathit{or}}(t, x, y)$：取寄存器 $x$ 和 $y$ 的按位或，并将结果存到寄存器 $t$ 中。对于所有的 $j$（$0 \le j \le b - 1$），如果 $r[x][j]$ 和 $r[y][j]$ 至少有一个为 1 则设置 $r[t][j] := 1$，否则设置 $r[t][j] := 0$。

$\operatorname{\mathit{xor}}(t, x, y)$：取寄存器 $x$ 和 $y$ 的按位异或，并将结果存到寄存器 $t$ 中。对于所有的 $j$（$0 \le j \le b - 1$），如果 $r[x][j]$ 和 $r[y][j]$ 恰好有一个为 1 则设置 $r[t][j] := 1$，否则设置 $r[t][j] := 0$。

$\operatorname{\mathit{not}}(t, x)$：取寄存器 $x$ 的按位非，并将结果存到寄存器 $t$ 中。对于所有的 $j$（$0 \le j \le b - 1$），设置 $r[t][j] := 1 - r[x][j]$。

$\operatorname{\mathit{left}}(t, x, p)$：左移寄存器 $x$ 中的所有比特 $p$ 位，并将结果存到寄存器 $t$ 中。将寄存器 $x$ 中的比特左移 $p$ 位的结果，是一个包含 $b$ 个比特的数组 $v$。对于所有的 $j$（$0 \le j \le b - 1$），如果 $j \ge p$ 则 $v[j] = r[x][j - p]$，否则 $v[j] = 0$。对所有的 $j$（$0 \le j \le b - 1$），设置 $r[t][j] := v[j]$。

$\operatorname{\mathit{right}}(t, x, p)$：右移寄存器 $x$ 中的所有比特 $p$ 位，并将结果存到寄存器 $t$ 中。将寄存器 $x$ 中的比特右移 $p$ 位的结果，是一个包含 $b$ 个比特的数组 $v$。对于所有的 $j$（$0 \le j \le b - 1$），如果 $j \le b - 1 - p$ 则 $v[j] = r[x][j + p]$，否则 $v[j] = 0$。对所有的 $j$（$0 \le j \le b - 1$），设置 $r[t][j] := v[j]$。

$\operatorname{\mathit{add}}(t, x, y)$：将寄存器 $x$ 和 $y$ 中的整数值加起来，并将结果存到寄存器 $t$ 中。加法是在模 $2^b$ 下做的。正式一些来说，设 $X$ 是操作前存在寄存器 $x$ 中的整数值，而 $Y$ 是操作前存在寄存器 $y$ 中的整数值。设 $T$ 为操作后存在寄存器 $t$ 中的整数值。如果 $X + Y < 2^b$，设置 $t$ 中的比特使得 $T = X + Y$。否则，设置 $t$ 中的比特使得 $T = X + Y - 2^b$。

Christopher 希望你用这个新处理器解决两种任务。任务的类型用整数 $s$ 来表示。对所有类型的任务，你需要创建一个程序，其为上文所定义的指令构成的序列。

程序的输入包括 $n$ 个整数 $a[0], a[1], \ldots , a[n - 1]$，而每个整数都有 $k$ 个比特，也就是说，$a[i] < 2^k$（$0 \le i \le n - 1$）。在程序执行前，输入的所有的数都依次存储在寄存器 $0$ 中，使得对所有的 $i$（$0 \le i \le n - 1$），$k$ 比特序列 $r[0][i \cdot k], r[0][i \cdot k + 1], \ldots , r[0][(i + 1) \cdot k - 1]$ 的整数值等于 $a[i]$。注意 $n \cdot k \le b$。寄存器 $0$ 中所有其他的比特（其下标在 $n \cdot k$ 和 $b - 1$ 之间，包括 $n \cdot k$ 和 $b - 1$），以及其他所有寄存器中的所有比特，都初始化为 $0$。

执行某个程序就是按序执行其所包含的指令。在最后一条指令执行完毕后，程序的输出将根据寄存器 $0$ 中比特最终的值计算出来。具体来说，输出是 $n$ 个整数 $c[0], c[1], \ldots , c[n - 1]$ 的序列，这里对所有 $i$（$0 \le i \le n - 1$）来说，$c[i]$ 都是寄存器 $0$ 中比特 $i \cdot k$ 到 $(i + 1) \cdot k - 1$ 所构成的序列的整数值。注意，在程序运行结束后，寄存器 $0$ 中其余的比特（下标不小于 $n \cdot k$），以及其他寄存器中的所有比特，可能是任意值。

第一个任务（$s = 0$）是要找出输入整数 $a[0], a[1], \ldots , a[n - 1]$ 中的最小值。 具体来说，$c[0]$ 必须是 $a[0], a[1], \ldots , a[n - 1]$ 中的最小值。$c[1], c[2], \ldots , c[n - 1]$ 的值可以是任意的。

第二个任务（$s = 1$）是要将输入整数 $a[0], a[1], \ldots , a[n - 1]$ 进行非降序排序。具体来说，对于所有的 $i$（$0 \le i \le n - 1$），$c[i]$ 应当等于 $a[0], a[1], \ldots , a[n - 1]$ 中第 $1 + i$ 小的整数（也就是说，$c[0]$ 是输入整数中的最小整数）。

请帮 Christopher 写一下解决这些任务的程序。每个程序至多只能包含 $q$ 条指令。

inputFormat:
你要实现如下函数：

```cpp
void construct_instructions(int s, int n, int k, int q)
 ```
- $s$：任务类型。
- $n$：输入中的整数的数量。
- $k$：输入中的每个整数的比特数。
- $q$：允许的最大的指令数。
该函数将被恰好调用一次，并应当为所要解决的任务创建一个指令序列。

该函数应当调用以下函数中的一或多个，以创建指令序列：

```cpp
void append_move(int t, int y)
void append_store(int t, std::vector<bool> v)
void append_and(int t, int x, int y)
void append_or(int t, int x, int y)
void append_xor(int t, int x, int y)
void append_not(int t, int x)
void append_left(int t, int x, int p)
void append_right(int t, int x, int p)
void append_add(int t, int x, int y)
```
- 每个函数分别往程序追加一条 $\operatorname{\mathit{move}}(t, y)$、$\operatorname{\mathit{store}}(t, v)$、$\operatorname{\mathit{and}}(t, x, y)$、$\operatorname{\mathit{or}}(t, x, y)$、$\operatorname{\mathit{xor}}(t, x, y)$、$\operatorname{\mathit{not}}(t, x)$、$\operatorname{\mathit{left}}(t, x, p)$、$\operatorname{\mathit{right}}(t, x, p)$ 或 $\operatorname{\mathit{add}}(t, x, y)$ 指令。
- 对于所有相关的指令，$t$、$x$、$y$ 必须至少为 $0$ 且至多为 $m - 1$。
- 对于所有相关的指令，$t$、$x$、$y$ 不必是两两之间不同的。
- 对于指令 `left` 和 `right`，$p$ 必须至少为 $0$ 且至多为 b。
- 对于指令 `store`，$v$ 的长度必须为 $b$。

你还可以调用以下函数，以帮助测试你的答案：

```cpp
void append_print(int t)
```
- 在评测你的答案时，对该函数的所有调用都将被忽略。
- 在评测程序示例中，该函数将往程序追加一个 $\operatorname{\mathit{print}}(t)$ 操作。
- 当评测程序示例在执行某个程序过程中遇到一个 $\operatorname{\mathit{print}}(t)$ 操作时，它会打印出由寄存器 $t$ 中前 $n \cdot k$ 比特构成的 $n$ 个 $k$-比特整数。
- $t$ 必须满足 $0 \le t \le m - 1$。
- 对该函数的任何调用，都不会算到你所创建的指令的数量里面。

在追加最后一条指令之后，`construct_instructions` 应当返回。随后你创建的程序将在一定数量的测试用例上评测，其中每个测试用例给出的输入数据为 $n$ 个 $k$-比特整数 $a[0], a[1], \ldots , a[n - 1]$。如果程序对给定输入数据的输出结果 $c[0], c[1], \ldots , c[n - 1]$ 满足如下条件，你的答案就将被视为通过了对应的样例：

- 如果 $s = 0$，$c[0]$ 应当为 $a[0], a[1], \ldots , a[n - 1]$ 中的最小值。
- 如果 $s = 1$，对所有 $i$（$0 \le i \le n - 1$）来说，$c[i]$ 应当是 $a[0], a[1], \ldots , a[n - 1]$ 中第 $1 + i$ 小的整数。

在评测你的答案时，可能会给出下面的错误信息之一：

- `Invalid index`：在调用某些函数时的参数 $t$、$x$ 或 $y$ 所给出的寄存器下标是不正确的（可能是负数）。
- `Value to store is not b bits long`：提供给 `append_store` 的 $v$ 的长度不等于 $b$。
- `Invalid shift value`：提供给 `append_left` 或 `append_right` 的 $p$ 的值不在 $0$ 和 $b$ 之间（包括 $0$ 和 $b$）。
- `Too many instructions`：你的函数试图追加超过 $q$ 条指令。


title: [JOISC 2021 Day2] 逃走経路 (Escape Route)

background:
本题**不是**交互题，请注意提交方式。

[英文题面](https://www2.ioi-jp.org/camp/2021/2021-sp-tasks/day2/escape_route-en.pdf)。

description:
IOI 王国的国民使用 Byou 作为时间单位。

IOI 王国中，一天被划分为 $S$ Byou，其中第 $x$ 个 Byou($0\leq x < S$) 被称为时刻 $x$。

IOI 王国中有 $N$ 个城市（标号 $0\sim N-1$）和 $M$ 条双向道路（标号 $0 \sim M-1$），你可以通过道路从一个城市移动到另一个城市。第 $i$ 条道路直接连接着城市 $A_i$ 和 $B_i$，通过这条道路需要 $L_i$ Byou。每天，从时刻 $C_i$ 开始要对第 $i$ 条道路进行检查，直到这一天结束。

JOI 集团是 IOI 王国中的一个秘密组织，出于其保密性，JOI 集团的成员不应该在道路上受到检查，这意味着如果 JOI 王国的成员如果想要通过道路 $i$，那么他必须在时刻 $C_i-L_i$ 之前踏上这条路。

现在有 $Q$ 名 JOI 集团的成员（标号 $0 \sim Q-1$），第 $j$ 名成员在某一天的时刻 $T_j$ 想要从城市 $U_j$ 出发旅行去城市 $V_j$。成员可以在城市内停留任意长的时间。这名成员可能要花费多天才能到达城市 $V_j$。

现要求计算每个成员完成旅行所需要的最少时间。

inputFormat:
第一行四个正整数 $N,M,S,Q$。

接下来 $M$ 行，第 $i$ 行四个正整数表示 $A_{i-1},B_{i-1},L_{i-1},C_{i-1}$。

接下来 $Q$ 行，第 $i$ 行三个正整数表示 $U_{i-1},V_{i-1},T_{i-1}$。

outputFormat: 输出共 $Q$ 行，第 $i$ 行表示第 $i$ 名成员旅行所需的最少时间。

hint:
对于 $100\%$ 的数据，保证：

- $2 \leq N \leq 90$。
- $N-1 \leq M \leq \dfrac{N(N-1)}{2}$。
- $2 \leq S \leq 10^{15}$。
- $1 \leq Q \leq 3 \times 10^6$。
- $0 \leq A_i,B_i \leq N-1 (0 \leq i \leq M-1)$。
- $A_i \ne B_i(0 \leq i \leq M-1)$。
- $\forall i,j \in [0,M-1]$，若 $i \ne j$，则有 $(A_i,B_i) \ne (A_j,B_j),(A_i,B_i) \ne (B_j,A_j)$。。
- $1 \leq L_i \leq C_i < S$。
- 你可以从某个城市经过若干条道路到达任意另一个城市。
- $0\leq U_j,V_j \leq N-1(0 \leq J \leq Q-1)$。
- $U-j \ne V_j$。
- $0 \leq T_j < S$。

此外，有 $5 \%$ 的分数，满足 $N \leq 40,Q \leq 1000$。

另有 $20 \%$ 的分数，满足 $N \leq 40,U_j=0$。

另有 $10 \%$ 的分数，满足 $N \leq 40$。

另有 $35 \%$ 的分数，满足 $N \leq 60$。

**建议使用较快的 IO 方式。**


title: [IOI2021] 地牢游戏

background:
**滥用本题评测将被封号**

**由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。**

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。

description:
Robert 正在设计一款新的电脑游戏。游戏中有一位英雄、$n$ 个敌人和 $n + 1$ 个地牢。敌人从 $0$ 到 $n - 1$ 编号，地牢从 $0$ 到 $n$ 编号。敌人 $i$（$0 \le i \le n - 1$）处在地牢 $i$，其能力值为 $s[i]$。地牢 $n$ 里没有敌人。

英雄一开始进入地牢 $x$，初始能力值为 $z$。每次英雄进入地牢 $i$（$0 \le i \le n - 1$）时，都需要面对敌人 $i$，且会发生以下情况中的一种：

如果英雄的能力值大于等于敌人 $i$ 的能力值 $s[i]$，那么英雄会胜出。这使得英雄的能力值增加 $s[i]$（$s[i] \ge 1$）。这种情况下，下一步英雄将会进入地牢 $w[i]$（$w[i] > i$）。

否则英雄会战败，这使得英雄的能力值增加 $p[i]$（$p[i] \ge 1$）。在这种情况下，下一步英雄将会进入地牢 $l[i]$。

注意 $p[i]$ 可能会小于、等于、大于 $s[i]$，$l[i]$ 可能会小于、等于、大于 $i$。无论对战结果如何，敌人 $i$ 始终处在地牢 $i$，且能力值为 $s[i]$。

当英雄进入地牢 $n$ 的时候，游戏结束。可以看出无论英雄的起始地牢和初始能力值如何，游戏一定会在有限次对战之后结束。

Robert 希望你通过 $q$ 次模拟来对游戏进行测试。对于每次模拟，Robert 输入英雄的起始地牢 $x$ 和初始能力值 $z$。你需要做的是对于每次模拟给出游戏结束时英雄的能力值。

inputFormat:
你要实现以下函数：
```cpp
void init(int n, int[] s, int[] p, int[] w, int[] l)
```
- $n$：敌人的数量。
$s$、$p$、$w$、$l$：长度为 $n$ 的序列。对于每一个 $i$（$0 \le i \le n - 1$）：
  + $s[i]$ 是敌人 $i$ 的能力值，也是击败敌人 $i$ 后英雄增加的能力值。
  + $p[i]$ 是英雄被敌人 $i$ 击败后增加的能力值。
  + $w[i]$ 是英雄击败敌人 $i$ 后进入的下一个地牢的编号。
  + $l[i]$ 是英雄被敌人 $i$ 击败后进入的下一个地牢的编号。
- 恰好调用此函数一次，且发生在任何对如下的 simulate 函数的调用之前。
```cpp
int64 simulate(int x, int z)
```
- $x$：英雄的起始地牢编号。
- $z$：英雄的初始能力值。
- 假设英雄的起始地牢编号为 $x$，初始能力值为 $z$，函数的返回值是相应情况下游戏结束时英雄的能力值。
- 恰好调用此函数 $q$ 次。


title: [YDOI R1] Necklace

background: hdkk 正在做项链。

description:
hdkk 有 $n$ 种颜色的珠子，每种珠子有 $a_i$ 颗，他可以选出任意颗珠子串成一串项链。

每种珠子有一个漂亮值 $v_i$，hdkk 认为项链有一个美丽度，若第 $i$ 种珠子在项链中有 $cnt$ 颗并且 $cnt\ge1$，则这串项链的美丽度会加上 $(v_i)^{cnt}$。

现在他想知道，所有不同的项链的美丽度总和是多少，请你求出答案，并对 $10^9+7$ 取模。

定义两串项链是不同的，当且仅当存在一颗珠子，它在一串项链中出现，在另一串中没有出现。

注意：每颗珠子都是互不相同的，即使颜色一样。

inputFormat:
第 $1$ 行有 $1$ 个正整数 $n$。

第 $2$ 行有 $n$ 个整数，第 $i$ 个数表示 $a_i$。

第 $3$ 行有 $n$ 个整数，第 $i$ 个数表示 $v_i$。

outputFormat: 一个整数，所有不同项链的美丽度的总和对 $10^9+7$ 取模的结果。


title: [语言月赛 202406] 数组交换

description:
小 B 有一个 $n$ 行 $m$ 列的数组 $a$，现在它要操作 $q$ 次，每次的内容如下：

- $\textbf{1 x y}$，交换第 $x$ 行和第 $y$ 行，若 $x = y$ 则表示不交换。
- $\textbf{2 x y}$，交换第 $x$ 列和第 $y$ 列，若 $x = y$ 则表示不交换。
- $\textbf{3 x y}$，查询当前 $a_{x, y}$ 的值。

对于每个操作 $3$，你需要回答。在所有操作结束后，你还需要输出最终的数组 $a$。你快告诉小 B 这些内容吧！

inputFormat:
第 $1$ 行，输入 $3$ 个整数 $n,m,q$，以空格隔开。
第 $2 \sim n + 1$ 行，每行输入 $m$ 个整数 $a_{i, j}$，没有空格。
第 $n + 2 \sim n + q + 1$ 行，每行输入 $3$ 个整数，以空格隔开，表示一次询问。

outputFormat:
设操作 $3$ 一共执行了 $w$ 次。
第 $1 \sim w$ 行，每行输出一个整数，表示每次询问的答案。
第 $w + 1 \sim w + n$ 行，每行输出 $m$ 个整数 $a_{i, j}$，没有空格，表示所有操作后的数组 $a$。

hint:
### 数据规模与约定

对于 $20\%$ 的数据，$1 \leq n, m, q \le 100$。
对于另外 $20\%$ 的数据，没有操作 $1$。
对于另外 $20\%$ 的数据，没有操作 $2$。
对于另外 $20\%$ 的数据，没有操作 $3$。
对于 $100\%$ 的数据，$1 \leq n, m \leq 10^3$，$1 \leq q \leq 10^5$，$0 \leq a_{i, j} \leq 9$。


title: 「LAOI-5」拼图

description:
Alice 和 Shinobu 在玩一个游戏。现在有 $n$ 个点，点有黑白两种颜色。初始每个点都是孤立的白点，Alice 和 Shinobu 轮流操作，Alice 先手：
- 每轮 Alice 选择一对没有边的点对 $u,v$ 并连无向边 $(u,v)$，不能连自环。
- 每轮 Shinobu 选择一个点并翻转其颜色（黑变白，白变黑）。

当某一次操作后图中存在同色三元环（即存在点 $a,b,c$ 使 $a,b,c$ 同色且 $(a,b),(b,c),(c,a)$ 都已经连上）或者对手无法操作时，操作者获胜。假设两人都绝顶聪明，问谁存在必胜策略？

inputFormat:
**本题有多组询问。**

第一行一个正整数 $T$ 表示询问组数。

后 $T$ 行，每行一个正整数 $n$ 表示游戏的点数。

outputFormat: $T$ 行，每行一个 `Alice` 或 `Shinobu`，表示最后谁会赢。


title: [YDOI R1] Lattice

background: jjh 喜欢点阵。

description:
jjh 有一个正方形点阵，这个点阵以 $(1,1)$ 为左下角，以 $(n,n)$ 为右上角。

jjh 还有一条直线，其表达式为 $y=kx$，其中 $k\in(0,\infty)$。

对于任意一个 $k$，设该直线经过了 $cnt$ 个点阵中的点，jjh 对这条直线有一个喜爱程度，为 $cnt^2$。

jjh 想知道所有直线的喜爱程度和对 $10^9+7$ 取模的结果，请你告诉 jjh。

inputFormat: 一行一个整数 $n$。

outputFormat: 输出一个整数，表示喜爱程度和对 $10^9+7$ 取模的结果。


title: [CCO2022] Alternating Heights

description:
Troy 计划给 CCO 的学生拍一张合影，他向你寻求帮助。

有 $K$ 个学生，编号从 $1$ 到 $K$。Troy 忘记了学生的身高，但他记得没有两个学生的身高相同。

Troy 有一个序列 $A_{1}, A_{2}, \ldots, A_{N}$，表示合影中从左到右的学生顺序。一个学生可能在 $A$ 中出现多次。你不确定这张合影会怎么拍，但你不愿意认为 Troy 犯了错误。

Troy 会给你 $Q$ 个形式为 $x,y$ 的询问，每个询问为「给定学生序列 $A_{x}, A_{x+1}, \ldots, A_{y}$，他们的身高能否形成一个交替序列？」更具体地说，我们用 $h_i$ 表示第 $i$ 个学生的身高。如果存在一种身高分配$ h_1, h_2, \ldots, h_K$，使得 $h_{A_{x}}>h_{A_{x+1}}<h_{A_{x+2}}>h_{A_{x+3}}<\ldots h_{A_{y}}$，回答 `YES`；否则回答 `NO`。

注意，每个查询都是独立的：也就是说，询问 $i$ 的身高分配与询问 $j$ 的身高分配无关 $(i\neq j)$。

inputFormat:
第一行包含三个用空格分隔的整数 $N, K$ 和 $Q$。

第二行包含 $N$ 个整数，表示 $A_{1}, A_{2}, \ldots, A_{N}\left(1 \leq A_{i} \leq K\right)$。

接下来的 $Q$ 行，每行包含两个用空格分隔的整数 $x$ 和 $y (1 \leq x<y \leq N)$，表示一组查询。

outputFormat: 输出 $Q$ 行。第 $i$ 行，输出 `YES` 或者 `NO`，表示 Troy 的第 $i$ 个查询的答案。


title: [CCO2022] Rainy Markets

background: ## 由于数据包过大，本题无法上传全部数据。

description:
有 $N$ 个公交车站，标号为 $1, \ldots, N$。第 $i$ 个公交车站可以容纳 $B_{i}$ 个人。

对于每个 $i \in\{1, \ldots, N-1\}$，有一条人行道连接公交车站 $i$ 和公交车站 $i+1$，中间有一个露天市场。第 $i$ 个市场有 $U_{i}$ 把雨伞出售，每把雨伞的价格为 $\$ 1$。

现在，有 $P_{i}$ 个人在第 $i$ 个市场里面，所有的公交车站都是空的。

突然，天开始下雨，市场 $i$ 的每个人都必须在三种方案中选择一种：

- 去公交车站 $i$；
- 去公交车站 $i+1$；
- 留下来买一把雨伞。

如果一个人无法在某个公交车站下或者买一把雨伞，他们就会淋湿。

你需要回答如果在最优的安排方案下，能否确保每个人都能不被雨淋湿。如果是的话，你需要给出他们需要花费的最少的钱，以及每个人应该移动到哪个公交车站。

inputFormat:
第一行包含一个整数 $N$。

第二行包含 $N$ 个用空格分隔的整数 $B_{i}\ (1 \leq i \leq N)$，表示公交车站 $i$ 的容量。

第三行包含 $N-1$ 个用空格分隔的整数 $P_{i}\ (1 \leq i \leq N-1)$，表示市场 $i$ 的人数。

第四行包含 $N-1$ 个用空格分隔的整数 $U_{i}\ (1 \leq i \leq N-1)$，表示市场 $i$ 出售的雨伞的数量。

outputFormat:
如果每个人都能在雨伞或公交车站下，输出 $N+1$ 行：

- 第一行输出一行 `YES`。
- 第二行输出一个整数，表示包含在雨伞上花费的最少的钱。
- 接下来的 $N-1$ 行，每行输出三个用空格分隔的整数分别表示市场 $i\ (1\leq i \leq N-1)$ 移动到公交车站 $i$ 的人数，市场 $i$ 买雨伞的人数，市场 $i$ 移动到公交车站 $i+1$ 的人数。

如果有多种合法方案，你可以输出任意一种。

否则，输出一行 `NO`。


title: [CCO2022] Double Attendance

description:
由于你的学校课程安排过于抽象，你的两门课程将在两个不同的教室里同时开始！你一次只能在一个地方，所以你只能在两个教室之间来回溜达，希望能够抓住两门课程的重点。

两个教室的编号分别是 $1$ 和 $2$。在教室 $i$，老师将在课堂上展示 $N_{i}$ 张不同的幻灯片，第 j 张幻灯片将在时间区间 $\left(A_{i, j}, B_{i, j}\right)\left(0 \leq A_{i, j}<B_{i, j}\right)$ 内展示，其中 $A_{i, j}$ 和 $B_{i, j}$ 是从课堂开始后以秒为单位计算的时间。在两个教室里，不会在某个时间点同时展示多张幻灯片。例如，一个课堂可能在 $(1,2)$ 和 $(5,6)$ 这两对时间区间内有幻灯片展示，或者在 $(10,20)$ 和 $(20,30)$ 这两对时间区间内有幻灯片展示，但不会在 $(10,20)$ 和 $(19,30)$ 这两对时间区间有幻灯片展示。

你在教室 $1$ 开始一天的课程，两门课程都在时刻 $0$ 开始。在那之后，你可以在任何时间点（不一定是整数秒）花费 $K$ 秒从你当前的教室移动到另一个教室。如果你在展示幻灯片的时间区间内在其教室里花费了正数时间，你就认为自己看到了这张幻灯片。当你在两个教室之间移动的 $K$ 秒内，你不在任何一个教室里，因此无法看到任何幻灯片。

例如，如果教室 $1$ 在时间区间 $(10,20)$ 展示一张幻灯片，教室 $2$ 在时间区间 $(15,25)$ 展示一张幻灯片，而 $K=8$，那么如果你在时间 $11.5$ 秒时从教室 $1$ 移动到教室 $2$（到达时间为 $19.5$ 秒），你就能看到两张幻灯片。另一方面，如果你在时间 $17$ 秒时离开教室 $1$（到达时间为 $25$ 秒），那么你将在教室 $2$ 的幻灯片停止展示后才进入教室，因此你会错过它。

你想要知道你能看到的不同幻灯片的最大数量是多少。

inputFormat:
第一行包含三个用空格分隔的整数，$N_{1}, N_{2}$ 和 $K$。

接下来的 $N_{1}$ 行，每行包含两个用空格分隔的整数 $A_{1, i}$ 和 $B_{1, i}\left(1 \leq i \leq N_{1}\right)$。

接下来的 $N_{2}$ 行，每行包含两个用空格分隔的整数，$A_{2, i}$ 和 $B_{2, i}\left(1 \leq i \leq N_{2}\right)$。

outputFormat: 输出一个整数，表示你能看到的不同幻灯片的最大数量。

hint:
## 样例 1 解释

一种可能的最优策略是在教室 $1$ 一直待到时间 $11.5$，然后移动到教室 $2$（到达时间为 $19.5$），一直待到时间 $19.6$，最后返回教室 $1$（到达时间为 $27.6$）。在这个过程中，你将看到除了第 $3$ 张幻灯片以外的所有幻灯片。你不可能看到所有的 $4$ 张幻灯片。

## 样例 2 解释

即使你在课程开始时立即移动到教室 $2$（例如，在时间 $0.0001$），你也会错过那里展示的前两张幻灯片。因此，你最多可以看到四张幻灯片。

## 数据范围
对于所有的数据，有 $1 \leq N_{i} \leq 3\times 10^5$，$0 \leq A_{i, j}<B_{i, j} \leq 10^{9}$，$1 \leq K \leq 10^{9}$。

子任务编号|分值|$N_{i}$|$A_{i, j},B_{i, j}$
:-:|:-:|:-:|:-:
$1$|$20$|$1 \leq N_{i} \leq 10$|$0 \leq A_{i, j}<B_{i, j} \leq 2000$
$2$|$40$|$1 \leq N_{i} \leq 2000$|$0 \leq A_{i, j}<B_{i, j} \leq 2000$
$3$|$24$|$1 \leq N_{i} \leq 2000$|$B_{i, j}-A_{i, j} \leq 2 K$
$4$|$16$|$1 \leq N_{i} \leq 3\times 10^5$|$0 \leq A_{i, j}<B_{i, j} \leq 10^{9}$


title: [CCO2022] Bi-ing Lottery Treekets

description:
在一个平行宇宙里，每个人都在 CCO 上得了满分。因此，Troy 需要根据抽奖来选出获胜者。每个参赛者将选择一些数字来创建一张彩票。一张彩票是一个大小为 $N$ 的数组，从 $1$ 到 $N$ 编号，其中每个元素是从 $0$ 到 $K$ 的一个数字。

中奖彩票是由将 $K$ 个球（编号为 $1$ 到 $K$）按随机顺序投入一个有根二叉树来确定的。这棵树有 $N$ 个节点（编号为 $1$ 到 $N$），并以节点 $1$ 为根。

每个球都有一个指定的投放节点，它将在那里投放。当一个球投放在一个空节点或进入一个空节点时，会发生以下三种情况之一：

1. 如果当前节点的所有子节点都被球占据（或者如果一个节点没有子节点），那么当前球就会停留在当前节点。也就是说，它会留在那里，不再移动。
2. 如果当前节点只有一个空的子节点，那么当前球将移动到这个子节点。
3. 如果当前节点有两个空的子节点，而且如果当前球刚刚被投放，它可以向左或向右移动。否则，它将继续沿着它之前的移动方向移动。

如果 $K$ 个球不能全部被投放，那么就没有确定的中奖彩票。这种情况发生在一个球被投放时，它的投放节点被另一个球占据了。

如果所有 $K$ 个球都被投放了，那么球的停留位置就决定了中奖彩票。中奖彩票的第 $i$ 个元素是停留在节点 $i$ 的球的编号，或者如果没有球停留在节点 $i$，就是 $0$。

Troy 想知道可能的中奖彩票的数量。因为答案可能很大，你只需要求数量对 $10^9+7$ 取模的结果。

inputFormat:
第一行包含两个用空格分隔的整数 $N$ 和 $K$，表示二叉树中的节点数和球的数目。

第二行包含 $K$ 个用空格分隔的整数，其中第 $i$ 个整数表示编号为 $i$ 的球的指定投放节点。

最后 $N$ 行，每行包含两个用空格分隔的整数。第 $i$ 行包含 $L_{i}$ 和 $R_{i}$，表示第 $i$ 个节点的左子节点和右子节点，其中 $0$ 表示子节点不存在。

outputFormat: 输出中奖彩票的数量模 $10^{9}+7$。

hint:
## 样例 1 解释

![](https://cdn.luogu.com.cn/upload/image_hosting/ts1yicyn.png)

考虑当球 $1$ 先被投放时。如果球 $1$ 向左移动，那么它将停留在节点 $2$。之后，球 $2$ 被投放，可以停留在节点 $4$ 或 $5$。如果球 $1$ 向右移动，它将停留在节点 $5$。然后，球 $2$ 将停留在节点 $4$。

考虑当球 $2$ 先被投放时。球 $2$ 可以向左或向右移动，分别停留在节点 $4$ 或 $5$。然后如果球 $1$ 在被投放后向左移动，它将停留在节点 $2$。然而，如果球 $1$ 向右移动，它将停留在节点 $4$ 或 $5$，取决于球 $2$ 没有占据的位置。

可能的中奖彩票是 $[0,1,0,2,0],[0,1,0,0,2],[0,0,0,1,2]$ 和 $[0,0,0,2,1]$。

## 样例 2 解释

![](https://cdn.luogu.com.cn/upload/image_hosting/r5ih52s1.png)

这个样例满足第二个子任务的条件。

球 $3$ 必须先被投放，因为如果球 $1$ 或球 $2$ 在球 $3$ 之前被投放，它会停留在节点 $4$，这不会让球 $3$ 被投放。

因此，我们可以先投放球 $3$，然后投放球 $2$，最后投放球 $1$，或者我们可以先投放球 $3$，然后投放球 $1$，最后投放球 $2$。对应的中奖彩票是 $[0,1,2,3]$ 和 $[0,2,1,3]$。

## 数据范围

对于所有的数据，有 $1\leq N,K \leq 4000$。

子任务编号|分值|$N$ 的范围|$K$ 的范围|额外的约束
:-:|:-:|:-:|:-:|:-:
$1$|$12$|$1 \leq N \leq 12$|$1 \leq K \leq 6$|无
$2$|$16$|$1 \leq N \leq 4000$|$1 \leq K \leq 4000$|所有节点都没有左子节点
$3$|$36$|$1 \leq N \leq 4000$|$1 \leq K \leq 4000$|$N$ 个投放节点是不同的
$4$|$36$|$1 \leq N \leq 4000$|$1 \leq K \leq 4000$|无


title: [CCO2022] Phone Plans

description:
CCOland 的市长 Jason 想要在 $N$ 个住户之间安装电话线，这些住户从 $1$ 到 $N$ 编号。为此，他向两家竞争对手 Keenan 移动电话和 Chris 家庭电话询问了他们的电话套餐。一个公司的电话套餐对应于一个特定的等级，每条电话线都有一个等级和一个与之相关的公司。如果你从一个公司购买了等级为 $l$ 的电话套餐，那么你就能够使用该公司所有等级小于或等于 $l$ 的电话线。等级为 $l$ 的电话套餐的价格为 $l$，你不能选择价格低于 $0$ 的电话套餐。

两个住户只有在通过同一家公司的电话线的路径连接时才能相互通信。Jason 想要从每家公司购买一个最低成本的电话套餐，使得至少有 $K$ 对不同的住户能够相互通信。

inputFormat:
第一行包含四个用空格分隔的整数 N, A, B 和 K，分别表示住户的数量，Keenan 移动电话的电话线的数量，Chris 家庭电话的电话线的数量，以及需要能够相互通信的最小住户对数。

接下来的 $A$ 行，每行包含三个用空格分隔的整数 $u, v$ 和 $l$，表示一条 Keenan 移动电话的电话线。它连接了住户 $u$ 和 $v\ (1 \leq u, v \leq N)$，等级为 $l\ (1 \leq l \leq 10^{9})$。

接下来的 $B$ 行，每行包含三个用空格分隔的整数 $u, v$ 和 $l$，表示一条 Chris 家庭电话的电话线，它连接了住户 $u$ 和 $v\ (1 \leq u, v \leq N)$，等级为 $l\ (1 \leq l \leq 10^{9})$。

outputFormat: 输出连接至少 $K$ 对不同住户所需的最低成本，如果不可能，则输出 $-1$。

hint:
## 样例解释

![](https://cdn.luogu.com.cn/upload/image_hosting/v7y9k0vk.png)

如果 Jason 从 Keenan 移动电话购买等级为 $3$ 的电话套餐，从 Chris 家庭电话购买等级为 $30$ 的电话套餐，那么 $(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$ 可以通过 Keenan 移动电话的线路相互通信，而 $(1,5),(2,6),(3,6),(2,3)$ 可以通过 Chris 家庭电话的线路相互通信。没有更便宜的方法。

## 数据范围

对于所有的数据，有 $1 \leq N \leq 2\times 10^5，0 \leq A, B \leq 2\times 10^5$，$0 \leq K \leq \frac{N(N-1)}{2}$。

子任务编号|分值|$N$|$A, B$|附加限制
:-:|:-:|:-:|:-:|:-:
$1$|$24$|$1 \leq N \leq 2000$|$0 \leq A, B \leq 2\times 10^5$|无
$2$|$20$|$1 \leq N \leq 2\times 10^5$|$1 \leq N \leq 2\times 10^5$|Keenan 移动电话只连接编号为奇数的住户；Chris 家庭电话只连接编号为偶数的住户
$3$|$24$|$1 \leq N \leq 2\times 10^5$|$0 \leq A \leq 10$|无
$4$|$32$|$1 \leq N \leq 2\times 10^5$|$0 \leq A, B \leq 2\times 10^5$|无


title: [CCO2022] Good Game

description:
Finn 正在玩一个叫做 Twos and Threes 的游戏。Twos and Threes 是一个单人游戏，它在一维棋盘上进行。在初始位置，有 $N$ 个方块排成一行，每个方块标有 $\tt{A}$ 或 $\tt{B}$。方块从左到右编号为 $1$ 到 $N$。Finn 可以进行以下操作：

- 选择 $2$ 或 $3$ 个连续的方块，它们有相同的标签，将它们从棋盘上移除并将剩余的方块连接起来，从左到右重新编号方块。

如果棋盘上的所有方块都被移除，Finn 就赢得了游戏。你的任务是帮助 Finn 确定一个赢得游戏的操作序列，或者确定游戏无法获胜。

inputFormat:
第一行包含一个整数 $N$。

第二行包含一个字符串 $S$，表示游戏开始时的标签。$S$ 中有 $N$ 个字符，$S$ 中的每个字符都是 $\tt{A}$ 或 $\tt{B}$。

outputFormat:
如果存在赢得游戏的操作序列，第一行输出 $K$，即移动序列中的移动次数。在接下来的 $K$ 行中，输出两个空格分隔的整数 $i,j$ 表示移除位于 $[i,i+j-1]$ 的方块的一次操作。

如果没有赢得游戏的操作序列，输出 $-1$。

如果有多个赢得游戏的操作序列，你可以输出任何一个。

hint:
## 样例解释

操作如下：
$$
\begin{aligned}
&\tt{ABAAB\underline{BB}AA}\\
&\tt{AB\underline{AA}BAA}\\
&\tt{A\underline{BB}AA}\\
&\tt{\underline{AAA}}\\
\end{aligned}
$$

## 数据范围

对于所有的数据，有 $1 \leq N \leq 10^{6}$。

子任务编号|分值|$N$ 的范围
:-:|:-:|:-:
$1$|$12$|$1 \leq N \leq 15$
$2$|$24$|$1 \leq N \leq 300$
$3$|$28$|$1 \leq N \leq 6000$
$4$|$36$|$1 \leq N \leq 10^6$


title: [LSOT-2] 笼中鸟

background:
> 「笼中鸟，笼中鸟」
>
> 「笼中有只小小鸟」
>
> 「何时才能出囚笼」
>
> 「黎明时分的夜晚」
>
> 「仙鹤灵龟都滑倒」
>
> 「猜猜身后是何人」

description:
榎本在 SPHIA 的小黑屋内实验神秘转移装置。

实验体是 $m$ 个长度为 $n$ 的数列，他要在这些数列上验证转移装置是否能够正常运行。

这个转移装置的主要功能是将两个序列的部分交换，也就是说他会选择 $(i,j),[l,r]$，然后将序列 $i$ 的 $[l,r]$ 与序列 $j$ 的 $[l,r]$ 交换。

当然了，为了验证是否成功交换，他会查询某个序列的某个区间的和与预期值是否相同，并且为了避免偶然现象，他会给某个序列的某个区间加上一个值。

榎本知道 self 非常喜欢斐波那契数列，于是为了更好的困住 self，他还加了一个功能，就是判断数列 $f$ 的某个区间是不是满足 $f_i\equiv\sum_{j=1}^kf_{i-j}\pmod p$ 的特殊数列。

形式化题面：

1. 给定 $x,l,r$，求 $\sum_{i=l}^ra_{x,i}\bmod p$。

2. 给定 $x,l,r,f$，询问命题 $\forall i\in[l+f,r],a_{x,i}\equiv \sum_{j=1}^fa_{x,i-j}\pmod p$ 是否是真命题。
3. 给定 $x,l,r,k$，$\forall i\in[l,r],a_{x,i}← a_{x,i}+k$。
4. 给定 $x,y,l,r$，$\forall i\in[l,r],\text{swap}(a_{x,i},a_{y,i})$。

inputFormat:
第一行四个正整数 $n,m,q,p$，$q$ 代表榎本的操作数。

接下来 $m$ 行每行 $n$ 个整数，第 $i$ 行的第 $j$ 个数代表 $a_{i,j}$。

接下来 $q$ 行，每行四个或五个整数。

若输入为 `1 x l r` 则代表对区间 $[l,r]$ 进行一次 $1$ 操作，若输入为 `2 x l r f` 则代表对区间 $[l,r]$ 进行一次 $2$ 操作，若输入为 `3 x l r k` 则代表对区间 $[l,r]$ 进行一次 $3$ 操作，若输入为 `4 x y l r ` 则代表对区间 $[l,r]$ 进行一次 $4$ 操作。

outputFormat:
对于每个 $1$ 操作，一行一个正整数表示答案。

对于每个 $2$ 操作，如果是真命题输出 `where is self?`，否则输出 `infinity loop!`。

hint:
**「本题采用捆绑测试」**

$\texttt{Subtask 1(20pts)：}n,q\le100$。

$\texttt{Subtask 2(25pts)：}n,q\le10^5$。

$\texttt{Subtask 3(25pts)：}$不存在 $2$ 操作。

$\texttt{Subtask 4(30pts)：}$无特殊性质。

对于所有数据，$1\le n,q\le5\times10^5$，$1\le m\le10$，$0\le a_{i,j},k< p$，$1\le l\le r\le n$，$1\le f\le n$，$1\le x,y\le m$，$x\not=y$。保证 $p$ 是 $10^{9}$ 到 $2\times 10^9$ 中随机生成的质数。

------------
2024/2/13 本题赛后添加两组 hack 数据（Subtask #5）


title: 好奇心宝贝

background:
> 道路，由人亲手制造。
>
> 酒与面包，靠劳作取得。
>
> 幼小的新芽舒展叶片，
>
> 与成堆魔药中抵抗困意。
>
> 多一点，再多一点时间，
>
> 再看看书的下一页。

description:
给出一个 $n\times m$ 的矩阵，每个位置 $(i,j)$ 都是一个小写字母。

定义一条路径对应的字符串为路径上字符顺次连接所形成的字符串。

请找出两条从 $(1,1)$ 到 $(n,m)$ 的路径，要求只能向下或向右走，最小化两条路径对应字符串的最长公共前缀。

inputFormat:
第一行两个数 $n,m$。

接下来 $n$ 行，每行 $m$ 个字符，描述整个矩阵。

outputFormat: 输出为一个数，即最短的最长公共前缀长度。

hint:
### 样例一解释

选择的两条路径分别为：

- $(1,1)\rightarrow (1,2)\rightarrow (1,3)\rightarrow (2,3)\rightarrow (3,3):$ `abexy`。

- $(1,1)\rightarrow (1,2)\rightarrow (2,2)\rightarrow (2,3)\rightarrow (3,3):$ `abcxy`。

它们的最长公共前缀为 $2$。可以证明没有更优的方案。

### 数据范围与约定

对于 $30\%$ 的数据，$1\le n,m \le 5$。

对于 $50\%$ 的数据，$1 \le n,m \le 50$。

对于另外 $20\%$ 的数据，矩阵随机生成且只含字母 `a,b`。

对于 $100\%$ 的数据，$1 \le n,m \le 2\times 10^3$，输入均为整数和小写字母。


title: 在四方城外

background:
> 柳花、青山与月光。
>
> 诗中的酒香与诗外的酒香。
>
> 城中的天空与城外的天空。
>
> 一字一句，一笔一划，所知晓的，尚懵懂的。
>
> 	看呀看，学呀学，世界正如浊酒，滋味饮酌方知。

description:
定义字符串 $S$ 的**扩展**操作为：

- 求出 $S$ 的最长 $\text{border}$ $T$。

- $S'\leftarrow S+T$。

**注意，本题的 $\text{border}$ 指真 $\text{border}$（即字符串本身不计入 $\text{border}$）**。

设**扩展**操作的权值为**扩展**后字符串的长度 $|S'|$，请求出字符串 $S$ 第 $L$  次**扩展**到第 $R$ 次**扩展**的权值之和。

由于结果可能很大，请输出答案对 $998244353$ 取模的结果。

inputFormat:
第一行一个字符串 $S$。

第二行两个整数 $L,R$。

outputFormat: 输出为一个数，即答案对 $998244353$ 取模的结果。

hint:
### 样例一解释

第 $1$ 次扩展操作：`ababcab[ab]`，权值为 $9$。

第 $2$ 次扩展操作：`ababcabab[abab]`，权值为 $13$。

第 $3$ 次扩展操作：`ababcabababab[abab]`，权值为 $17$。

权值之和为 $9+13+17=39$。

### 数据范围与约束

对于 $30\%$ 的数据，$1 \le |S| \le 100,1 \le L,R \le 10$。

对于 $60\%$ 的数据，$1 \le L,R \le 10^6$。

对于另外 $10\%$ 的数据，$\text{border}_{S}=|S|-1$。

对于 $100\%$ 的数据，$1 \le |S| \le 10^6,1 \le L \le R \le 10^9$，输入均为整数和小写字母。


title: 【MX-S3-T4】「FeOI Round 1」醒餞の鳥 (feat. Feryquitous)

description:
有 $n$ 个学生（编号为 $1 \sim n$）参加了一场有 $m$ 门学科（编号为 $1 \sim m$）的考试，现在你知道，学生 $i$ 的第 $j$ 门学科考试的成绩为 $a_{i, j}$。

现在你想要给这些学生排名。由于成绩不形成偏序关系的两个学生实力难以比较，所以你打算设置 $m$ 个实数 $p_{1 \sim m}$（要求满足 $\sum_{i = 1}^m p_i = 1$，且 $p_i \ge 0$）作为权值。定义学生 $i$ 的加权总分为 $\sum_{j = 1}^m a_{i, j} \times p_j$，则按照加权总分降序排名，加权总分相等的则排名并列。

现在这 $m$ 个学科的老师都向你提出了要求，第 $k$ 个学科的老师想让你所设置的 $p$ 满足：

- 以这个 $p$ 得到的排名结果中，不存在一对学生 $(x, y)$（$x \ne y$），使得 $x$ 排名更靠前（并列不算），但是 $a_{x, k} < a_{y, k}$；

因为你想要尽量自由的分配权值，所以你需要对于每个 $k$（$1 \le k \le m$），都**分别**求出：

- $p_k$ 至少要为多少，才能保证**无论如何分配其他 $\boldsymbol{p_i}$ 的权值，都能满足**第 $k$ 个学科的老师的要求？请输出答案对 $998244353$ 取模的结果。

inputFormat:
**本题单个测试点内包含多组数据。**

第一行一个整数 $T$ 表示数据组数。

接下来，对于每组数据，格式如下：

第一行两个整数，分别为 $n, m$。

第二行到第 $n + 1$ 行每行 $m$ 个整数，第 $i + 1$ 行第 $j$ 列的整数表示 $a_{i, j}$。

outputFormat:
对于每组测试数据，输出 $m$ 行，每行一个非负整数，第 $i$ 行表示 $k = i$ 时，$p_k$ 的最小值对 $998244353$ 取模的结果。

即设答案化为最简分式后的形式为 $\frac{a}
{b}$，其中 $a$ 和 $b$ 互质。输出整数 $x$ 使得 $bx \equiv a \pmod{998244353}$ 且 $0 \le x < 998244353$。可以证明这样的整数 $x$ 是唯一的。


title: [LSOT-2] 基于二分查找与插入的快速排序

background:
小 H 不会排序，但是会二分！

于是他创造了一个基于二分查找与插入的快速排序。

本题存在可带修做法，因为这题是这场考试的签到题所以良心出题人没有加上。

description:
给定一个排列 $p$。每次可以选择一个数 $p_i$，你需要找到最小的 $j$，使得 $j>i$ 且 $p_j>p_i$，并将 $p_i$ 插入到 $p_j$ 前面。你需要最小化使得 $p_i=i$ 的操作次数。

若不存在这样的 $j$，则无法进行操作。

inputFormat:
第一行一个整数 $n$，表示排列的长度。

接下来一行 $n$ 个整数描述排列 $p$，第 $i$ 个数为 $p_i$。

outputFormat: 一行一个整数表示最小的操作次数。若无法完成排序输出 $-1$。

hint:
**「本题采用捆绑测试」**

- $\texttt{Subtask 1(20pts)：}n\le10$。
- $\texttt{Subtask 2(20pts)：}$保证 $p_i=n-i+1$。
- $\texttt{Subtask 3(20pts)：}n\le1000$。
- $\texttt{Subtask 4(40pts)：}$无特殊性质。

对于全部的数据，$1\le n\le2\times 10^6$，$p$ 是一个 $1$ 到 $n$ 的排列。


title: [USACO18FEB] Teleportation B

description:
Farmer John 最讨厌的农活是运输牛粪。为了精简这个过程，他制造了一个伟大的发明：便便传送门！与使用拖拉机拖着装满牛粪的大车从一个地点到另一个地点相比，他可以使用便便传送门将牛粪从一个地点瞬间传送到另一个地点。

Farmer John 的农场沿着一条长直道路而建，所以他农场上的每个地点都可以简单地用该地点在道路上的位置来表示（相当于数轴上的一个点）。一个传送门可以用两个数 $x$ 和 $y$ 表示，被拖到地点 $x$ 的牛粪可以瞬间传送到地点 $y$，反之亦然。

Farmer John 想要将牛粪从地点 $a$ 运输到地点 $b$，他建造了一个可能对这一过程有所帮助的传送门（当然，如果没有帮助，他也可以不用）。请帮助他求出他需要使用拖拉机运输牛粪的总距离的最小值。

inputFormat: 输入仅包含一行，为四个用空格分隔的整数：$a$ 和 $b$，表示起始地点和结束地点，后面是 $x$ 和 $y$，表示传送门。所有的位置都是范围为 $0\ldots 100$ 的整数，不一定各不相同。

outputFormat: 输出一个整数，为 Farmer John 需要用拖拉机运输牛粪的最小距离。

hint: 在这个样例中，最佳策略是将牛粪从位置 $3$ 运到位置 $2$，传送到位置 $8$，再运到位置 $10$。 所以需要用拖拉机的总距离为 $1 + 2 = 3$。


title: [USACO18FEB] Hoofball B

description:
为了准备即将到来的蹄球锦标赛，Farmer John 正在训练他的 $N$ 头奶牛（方便起见，编号为 $1\ldots N$，其中 $1\le N\le 100$）进行传球。这些奶牛在牛棚一侧沿直线排列，第 $i$ 号奶牛位于距离牛棚 $x_i$ 的地方（$1\le x_i\le 1000$）。每头奶牛都在不同的位置上。

在训练开始的时候，Farmer John 会将若干个球传给不同的奶牛。当第 $i$ 号奶牛接到球时，无论是从 Farmer John 或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会传给其中距左边最远的那头奶牛）。为了使所有奶牛都有机会练习到传球，Farmer John 想要确保每头奶牛都持球至少一次。帮助他求出为了达到这一目的他开始时至少要传出的球的数量。假设他在开始的时候能将球传给最适当的一组奶牛。

inputFormat: 输入的第一行包含 $N$。第二行包含 $N$ 个用空格分隔的整数，其中第 $i$ 个整数为 $x_i$。

outputFormat: 输出 Farmer John 开始的时候最少需要传出的球的数量，使得所有奶牛至少持球一次。

hint:
在上面的样例中，Farmer John 应该将球传给位于 $x=1$ 的奶牛和位于 $x=11$ 的奶牛。位于 $x=1$ 的奶牛会将她的球传给位于 $x=3$ 的奶牛，在此之后这个球会在位于 $x=3$ 的奶牛和位于 $x=4$ 的奶牛之间来回传递。位于 $x=11$ 的奶牛会将她的球传给位于 $x=7$ 的奶牛，然后球会被传给位于 $x=4$ 的奶牛，在此之后这个球也会在位于 $x=3$ 的奶牛和位于 $x=4$ 的奶牛之间来回传递。这样的话，所有的奶牛都会至少一次接到球（可能从 Farmer John，也可能从另一头奶牛）。

可以看出，不存在这样一头奶牛，Farmer John 可以将球传给她之后所有奶牛最终都能被传到球。


title: [USACO18FEB] Taming the Herd B

description:
一大清早，Farmer John 就被木材破裂的声音吵醒了。是这些奶牛们干的，她们又逃出牛棚了！

Farmer John 已经厌烦了奶牛在清晨出逃，他觉得受够了：是时候采取强硬措施了。他在牛棚的墙上钉了一个计数器，追踪从上次出逃开始经过的天数。所以如果某一天早上发生了出逃事件，这一天的计数器就为 $0$；如果最近的出逃是 $3$ 天前，计数器读数就为 $3$。Farmer John 一丝不苟地记录了每一天计数器的读数。

年末到了，Farmer John 准备做一些统计。他说，你们这些奶牛会付出代价的！然而意想不到的是，他的记录的一些条目竟然丢失了！

Farmer John 确信他是在发生出逃的某一天开始记录的。请帮助他确定，在所有与残留记录条目一致的事件序列中，基于记录的时间，最少和最多可能发生的出逃次数。

inputFormat:
输入的第一行包含一个整数 $N$（$1\le N\le 100$），表示从 Farmer John 开始对奶牛出逃计数器进行计数以来已经经过的天数。

第二行包含 $N$ 个空格分隔的整数。第 $i$ 个整数是 $−1$，表示第 $i$ 天的记录丢失了，或者是一个非负整数 $a_i$（不超过 $100$），表示在第 $i$ 天计数器的数字是 $a_i$。

outputFormat: 如果没有事件序列与 Farmer John 的残留记录以及他所确定的奶牛在第 $1$ 天清晨出逃这一事实相一致，输出一个整数 $−1$。否则，输出两个空格分隔的整数 $m$ 和 $M$，其中 $m$ 为所有事件序列中出逃的最少次数，$M$ 为最多次数。

hint: 在这个样例中，我们可以推断第 $3$ 天必然有出逃发生。我们已经知道在第 $1$ 天也发生了出逃，所以最后不确定的只有第 $2$ 天是否发生了出逃。因此，总共发生了 $2$ 至 $3$ 次出逃。


title: 「OICon-02」Pick Stone

description: 小 S 有一个 $n\times m$ 的棋盘。初始每个位置都有一个棋子。每次，小 S 可以取走一个周围（四连通）被取走棋子数不超过 $1$ 的棋子。求小 S 最多能取走多少棋子，并构造一种合法的取棋子方案。

inputFormat: 一行，两个正整数 $n,m$，表示棋盘大小。

outputFormat:
第一行一个正整数，表示最多能取走的棋子数 $ans$。

接下来 $n$ 行，每行 $m$ 个 $-1\sim ans$ 之间的整数。每个位置的数表示这个位置的棋子是第几个取走的。如果该位置的棋子没被取走，请输出 $-1$。

hint:
### 样例解释

对于样例 $1$，取出 $(1,1)$ 时周围有 $0$ 个已取出位置，取出 $(1,2),(2,1)$ 时周围有 $1$ 个已取出位置，故原构造符合要求。

容易证明没有更优答案。

### 数据范围

**本题采用捆绑测试。**

| $\text{Subtask}$ | 特殊性质 | $\text{Score}$ |
|:--:|:--:|:--:|
| $1$ | $n=1$ | $20$ |
| $2$ | $n=2$ | $30$ |
| $3$ | $n=3$ | $50$ |

对于 $100\%$ 的数据：$\bm{1\leq n\leq3}$，$1\leq m\leq10^5$。

如果你答对了第一问最多能取走的棋子数而没有正确地构造，你将获得 $70\%$ 的分值。一个子任务你的得分是所有测试点得分的最小值。注意，你仍需要按格式输出 $n\times m$ 个数表示构造方案，我们推荐你全部输出 $-1$。

保证 `checker.cpp` 在符合格式要求的输出下用时不超过 $0.5$ 秒。


title: [集训队互测 2023] Axium Crisis

background:
在那灰暗的塔楼前，对立见到了些许光芒碎片。

那些光芒碎片萦绕在对立身旁，宛如繁花点缀。

步入那扭曲的迷宫，对立试图收集其中的纷争碎片，并尝试摧毁这个迷宫。

对立的身旁充斥着光芒和纷争碎片，交错纷飞。

终于，对立来到了那迷宫的最深处。

在那片形状极其古怪的记忆残片上，反射的，是一个世界走向灭亡的回忆。

末日来临，天空撕裂，大地崩坠。

由于这块残片上所承载的「能量」实在过于巨大，对立试图使用其身旁的光芒和纷争碎片来缓和这份巨大的精神上的冲击。

具体的，这块扭曲的残片形成一个「树」的结构，对立将在树的每条边上放上一片光芒或者纷争碎片。

对立将会把这颗树上的边切割成若干条链，使得最终每条边恰好属于其中的某一条链。由于残片的特殊结构，树上的一个节点可以同时属于多条链。

对立会取出一部分链，将放置碎片相同的前缀段进行合并，最后形成一颗新的树，也就是所谓的「Trie 树」。

这颗新的树上的节点越多，就越能缓和对立的情绪，让其冷静下来。

在疯狂中，对立已经给残片上的某些边放上了光芒碎片或者纷争碎片。

一刹那的清醒间，对立意识到了些许不对。因此对立还可以往剩下的边上任意选择光芒或者纷争碎片。

在恍惚间，对立发现自己并不知道如何放置并切割是最优的。

思绪飞快地运转起来。怎样是最优的呢？

相信你已有答案。

description:
给定一颗 $n$ 个节点的树，节点编号 $0\sim n-1$。

边有边权，边权一般为 $0$ 或者 $1$；但有的边的边权还未确定。

你要给每条未被确定边权的边确定一个 $0$ 或者 $1$ 的边权，然后从树上取出若干条有向路径，使得这些链两两之间满足**边不相交**。

然后你会把这些路径插入一颗 0/1-Trie，你希望最大化这颗 0/1-Trie 上的节点数。（0/1-Trie 定义略）

你可能需要构造具体的选择方案。

inputFormat:
本题每个测试点中有多组测试数据。

第一行两个整数 $T,o$，其中 $T$ 表示测试数据组数，$o$ 表示该测试点的一些特殊性质（请参见「数据范围与提示」一节的描述）。

接下来有 $T$ 组测试数据。

每组数据第一行一个整数 $n$，表示点的个数。

接下来 $n-1$ 行，每行三个整数 $u,v,w$，表示一条连接点 $u,v$ 的边。当 $0\le w\le 1$ 时，表示这条边边权为 $w$；否则总有 $w=2$，表示这条边的边权还未确定。

保证这些边形成一颗点集为 $0\sim n-1$ 的树。

outputFormat:
开头应当输出一个数 $c$（$c\in\{0,1\}$），表示你是否选择在该测试点输出方案，我们会使用 Special Judge 来校验你的输出是否正确。**注意这将影响你在该测试点的得分上限，详见「数据范围与提示」一节的描述**。

对于每组测试数据，首先输出一行一个数 $A$，表示该组数据的答案。

当 $c=1$ 时，还需要继续按如下格式输出你所构造的方案：
* 先输出一行一个数 $m$，表示你构造的方案中路径的数目。
* 接下来一行 $n-1$ 个数，每个数为 $0$ 或者 $1$，表示按输入顺序各边的边权。**对于边权本身已经确定的边，请原样输出。**
* 接下来 $m$ 行，每行两个数 $u,v$，表示树上一条从 $u$ 到 $v$ 的路径。要求 $u\neq v$，且路径两两**边不相交**。

hint:
#### 样例解释

这组样例对应的答案文件为：

```plain
8
9
5
16
14
16
15
16
18
```

样例输出即 `.out` 文件，也就是你要输出的结果，在 $c=1$ 时需要构造一组合法方案。

样例答案即 `.ans` 文件，该文件中仅会给出每组数据的答案，不会给出构造方案。

接下来依次附上这 $9$ 组样例的图示（选择边权前 / 后各一张）。

![sample0_1_1.png](https://sy.hhwdd.com/RequireFile.do?fid=01t7zGM4)![sample0_1_2.png](https://sy.hhwdd.com/RequireFile.do?fid=EHOyk2Uz)

![sample0_2_1.png](https://sy.hhwdd.com/RequireFile.do?fid=FP2WnHn3)![sample0_2_2.png](https://sy.hhwdd.com/RequireFile.do?fid=c4cKvUgH)

![sample0_3_1.png](https://sy.hhwdd.com/RequireFile.do?fid=U4UoWyyU)![sample0_3_2.png](https://sy.hhwdd.com/RequireFile.do?fid=59JlIWvn)

![sample0_4_1.png](https://sy.hhwdd.com/RequireFile.do?fid=cm5NQIRx)![sample0_4_2.png](https://sy.hhwdd.com/RequireFile.do?fid=jM6lGPo8)

![sample0_5_1.png](https://sy.hhwdd.com/RequireFile.do?fid=7jKRZ9i9)![sample0_5_2.png](https://sy.hhwdd.com/RequireFile.do?fid=Fb1HkD1s)

![sample0_6_1.png](https://sy.hhwdd.com/RequireFile.do?fid=CbEmirO0)![sample0_6_2.png](https://sy.hhwdd.com/RequireFile.do?fid=4GrzzBbe)

![sample0_7_1.png](https://sy.hhwdd.com/RequireFile.do?fid=hRWoM1xi)![sample0_7_2.png](https://sy.hhwdd.com/RequireFile.do?fid=8OgPPrFB)

![sample0_8_1.png](https://sy.hhwdd.com/RequireFile.do?fid=ws6t9q9g)![sample0_8_2.png](https://sy.hhwdd.com/RequireFile.do?fid=RkDgZv7G)

![sample0_9_1.png](https://sy.hhwdd.com/RequireFile.do?fid=MlI0m1pW)![sample0_9_2.png](https://sy.hhwdd.com/RequireFile.do?fid=KJLtHLs7)

#### 更多样例

**因为本题数据规模太大，直接提交评测会对评测机带来很大压力，本题将提供很多大样例；请尽量减少本题的提交次数。**

更多样例请参见下发文件 `axiumcrisis*.in/ans`，共 $20$ 组，基本按照部分分的方法造。

注意下发的答案文件中**没有给出构造方案**，仅会给出每组数据的答案。

下发了一个 `checker.cpp`，你可以自行编译并在终端运行校验合法性。具体使用方法请参考「数据范围与提示」一节的描述。正式测评时使用的 Special Judge 与其并不相同。

为了方便你更好地理解题意，此处额外附一个手搓的样例，这份样例未被放入下发文件。

**建议使用该组样例及样例解释校验你对题意的理解，以免误读**。

#### 数据范围与提示

与[互测实际使用的版本](https://qoj.ac/problem/7769)不同，本题此处将采用数据范围更大的版本。

对于所有的数据，保证 $2\le n\le18$，$1\le T\le3000$。

具体的数据规模分布可以见下表，**各子任务等分，即满分均为 $\rm5pts$**。其中形如 $(l,r)$ 的一列对应的数据表示 $l\le n\le r$ 的数据组数，「无限制」表示无额外限制。

各子任务**捆绑评测**，其分数为该子任务各测试点分数最小值。子任务依赖意味着只有所依赖的子任务分数均非 $0$ 才会评测当前子任务，且分数与所依赖的子任务也取最小值。$o$ 的含义将在之后注明。

|子任务|$(2,4)$|$(5,6)$|$(7,8)$|$(9,11)$|$(12,14)$|$(15,17)$|$(18,18)$|$o$|子任务依赖|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|$1$|$\le1000$|$=0$|$=0$|$=0$|$=0$|$=0$|$=0$|$=0$|无|
|$2$|无限制|$\le15$|$=0$|$=0$|$=0$|$=0$|$=0$|$=0$|$1$|
|$3$|无限制|$\le500$|$\le10$|$=0$|$=0$|$=0$|$=0$|$=0$|$2$|
|$4$|无限制|$\le1000$|$\le50$|$\le10$|$=0$|$=0$|$=0$|$=2$|无|
|$5$|无限制|$\le1000$|$\le50$|$\le10$|$=0$|$=0$|$=0$|$=3$|无|
|$6$|无限制|$\le1000$|$\le50$|$\le10$|$=0$|$=0$|$=0$|$=4$|$4$|
|$7$|无限制|$\le1000$|$\le50$|$\le10$|$=0$|$=0$|$=0$|$=0$|$3,5,6$|
|$8$|无限制|无限制|$\le1000$|$\le60$|$\le10$|$=0$|$=0$|$=2$|$4$|
|$9$|无限制|无限制|$\le1000$|$\le60$|$\le10$|$=0$|$=0$|$=3$|$5$|
|$10$|无限制|无限制|$\le1000$|$\le60$|$\le10$|$=0$|$=0$|$=4$|$6,8$|
|$11$|无限制|无限制|$\le1000$|$\le60$|$\le10$|$=0$|$=0$|$=0$|$7,9,10$|
|$12$|无限制|无限制|无限制|$\le300$|$\le30$|$\le10$|$=0$|$=2$|$8$|
|$13$|无限制|无限制|无限制|$\le300$|$\le30$|$\le10$|$=0$|$=3$|$9$|
|$14$|无限制|无限制|无限制|$\le300$|$\le30$|$\le10$|$=0$|$=4$|$10,12$|
|$15$|无限制|无限制|无限制|$\le300$|$\le30$|$\le10$|$=0$|$=0$|$11,13,14$|
|$16$|无限制|无限制|无限制|$\le500$|$\le60$|$\le20$|$\le10$|$=1$|无|
|$17$|无限制|无限制|无限制|$\le500$|$\le60$|$\le20$|$\le10$|$=2$|$12$|
|$18$|无限制|无限制|无限制|$\le500$|$\le60$|$\le20$|$\le10$|$=3$|$13,16$|
|$19$|无限制|无限制|无限制|$\le500$|$\le60$|$\le20$|$\le10$|$=4$|$14,16,17$|
|$20$|无限制|无限制|无限制|$\le500$|$\le60$|$\le20$|$\le10$|$=0$|$15,18,19$|

接下来阐述关于 $o$ 的特殊性质。
* $o=0$ 时，不保证特殊性质。
* $o=1$ 时，保证输入中 $w=0$。
* $o=2$ 时，保证输入中 $w=2$。
* $o=3$ 时，保证输入中 $w=0$ 或 $w=1$。
* $o=4$ 时，保证输入中 $w=0$ 或 $w=2$。

接下来阐述是否输出方案对答案带来的影响。
* 如果选择了 $c=0$，则答案正确时，你将获得该测试点 $80\%$ 的分数，否则该测试点不得分。
* 如果选择了 $c=1$，则答案和构造方案**均正确**时，你将获得该测试点的全部分数，**否则该测试点不得分**。

因此如果你的输出方案可能写错，请慎重考虑是否改为不输出方案。

接下来介绍 `checker.cpp` 使用方法。

`checker.cpp` 使用类似于 Testlib 的命令行格式，但是并不基于 Testlib，因此**不需要 `testlib.h` 文件**；同时**兼容 Lemon 格式**。具体的，你可以这么使用：

打开终端，进入 `checker.cpp` 所在文件夹后，首先使用 `g++ checker.cpp -o checker` 命令生成可执行文件（需要本地默认采用 C++11 及以上标准）。

假设输入文件为 `data.in`，输出文件为 `data.out`，标准答案文件为 `data.ans`，则你需要将可执行文件 `checker` 和 `data.in/out/ans` 文件放置于同一文件夹下，然后在终端中输入如下命令执行：
* 如果你使用 Windows 操作系统，请在 cmd 中使用 `checker data.in data.out data.ans 5` 执行。
* 如果你使用 Linux 操作系统，请在 bash 中使用 `./checker data.in data.out data.ans 5` 执行。

如命令中去掉最后的这个 `5` 将认为 $c=0$ 时也为 AC。

稍等片刻即会返回提示信息。

如果你使用 Lemon 来进行本地评测，可以把 `checker.cpp` 的可执行文件直接作为 Lemon 中的「自定义校验器」使用。

#### 后记

透过指缝观看着那世界末日之景。对立咽了口口水，靠着那股不知名的勇气，将手从自己的脸上移开。

对立伸出了手，把那世界尽头收入了自己所搜集的无数回忆之中。

其余的悲惨记忆，在这枚残片的映衬下显得不足一提。

对立确信自己已经变得足够强大，理所当然地想立刻把一切都摧毁。

就这样，伴随着那抹真诚的微笑与疲惫的笑声，对立从天空中降落到了地面上。

那座古老的塔楼在这般力量驱使下逐渐陨落。

而对立则怀抱着英雄般的信念，坚定不移地迈步向前。


title: 「OICon-02」Native Faith

description:
本题字符串下标从 $1$ 开始。

定义两个字符串相加的结果为将这两个字符串首尾拼接形成的新字符串。

令 $f(a,b,c)=\sum\limits_{i=1}^{|a|}\sum\limits_{j=i}^{|a|}\sum\limits_{k=1}^{|b|}\sum\limits_{l=k}^{|b|}[a_{i,i+1,\cdots,j}+b_{k,k+1,\cdots,l} = c]$（$a,b,c$ 均为字符串）。

即有多少种方式从 $a,b$ 中分别选出一个非空子串使两个子串的和为 $c$。

给定 $n$ 个字符串 $s_1,s_2,s_3,\cdots,s_n$。

有 $q$ 次询问，每次询问给出三个正整数 $l,r,k$，求 $\sum\limits_{i=l}^r\sum\limits_{j=l}^rf(s_i,s_j,s_k)$。

inputFormat:
第一行包含两个整数 $n,q$。

下面 $n$ 行，每行一个只包含小写字母的非空字符串表示 $s_1,s_2,\cdots,s_n$。

下面 $q$ 行，每行三个正整数 $l,r,k$，表示一次询问。

outputFormat: 对于每个询问，每行输出一个整数表示答案。

samples:
10 10
aabb
aba
abbba
abaccaab
abbba
ababababab
aaaaa
bbbbbb
aaba
abbba
1 10 10
1 4 5
3 6 4
2 8 1
1 5 4
2 10 7
2 9 2
4 5 5
5 5 6
8 9 10


title: [USACO24JAN] Majority Opinion B

description:
Farmer John 有一项重要的任务——弄清楚要为他的奶牛们购买什么类型的干草。

Farmer John 的 $N$ 头奶牛（$2\le N\le 10^5$）编号为 $1$ 到 $N$，每头奶牛喜欢恰好一种类型的干草 $h_i$（$1\le h_i\le N$）。他希望他的所有奶牛都喜欢同一种干草。

为了实现这一目标，Farmer John 可以主持焦点小组访谈。一次焦点小组访谈为让编号从 $i$ 到 $j$ 的连续范围内的所有奶牛聚集在一起参加一次访谈。如果有一种干草是小组中超过一半的奶牛喜欢的，则此次焦点小组访谈结束后，所有奶牛最终都会喜欢这种干草。如果不存在这种类型的干草，那么奶牛们不会改变她们喜欢的干草类型。例如，在由 $16$ 头奶牛组成的焦点小组访谈中，需要有其中 $9$ 头或更多的奶牛具有相同的干草喜好，才能使其余奶牛改变其喜好以与之一致。

Farmer John 想知道哪些类型的干草有可能变为同时受到所有奶牛的喜爱。他一次只能主持一个焦点小组访谈，但为了使所有奶牛都喜欢同一类型的干草，他可以根据需要任意多次地主持焦点小组访谈。

inputFormat:
输入的第一行包含一个整数 $T$，为独立的测试用例的数量（$1\le T\le 10$）。

每一个测试用例的第一行包含 $N$。

第二行包含 $N$ 个整数，为奶牛们喜爱的干草类型 $h_i$。

输入保证所有测试用例的 $N$ 之和不超过 $2\cdot 10^5$。

outputFormat:
输出 $T$ 行，对于每个测试用例输出一行。

如果可能使所有奶牛同时喜欢同一种干草，则以升序输出所有可能的此类干草的类型，否则输出 $-1$。在同一行内输出一列整数时，相邻的数用空格分隔，并确保行末没有多余空格。

hint:
### 样例解释

在输入样例中，有 5 个测试用例。

在第一个测试用例中，仅可能使所有奶牛喜欢种类 $2$。FJ 可以通过主持一次所有奶牛的焦点小组访谈达到这一目的。

在第二个测试用例中，可以证明没有奶牛会改变她们喜爱的干草种类。

在第三个测试用例中，有可能使所有奶牛喜欢种类 $1$，可以通过主持三次焦点小组访谈达到这一目的——首先使奶牛 $1$ 到 $4$ 进行一次焦点小组访谈，随后使奶牛 $1$ 到 $5$ 进行一次焦点小组访谈，随后使奶牛 $1$ 到 $6$ 进行一次焦点小组访谈。以类似的逻辑，依次操作奶牛 $3$ 到 $6$，随后是奶牛 $2$ 到 $6$，随后是奶牛 $1$ 到 $6$，我们可以使所有奶牛喜欢种类 $2$。

在第四个测试用例中，有可能使所有奶牛喜欢种类 $3$，可以通过主持一次所有奶牛的焦点小组访谈达到这一目的。

在第五个测试用例中，可以证明没有奶牛会改变她们喜爱的干草种类。

### 测试点性质

- 测试点 $2$：$N=2$。
- 测试点 $3-4$：$N\le 50$。
- 测试点 $5-6$：对于所有的 $1\le i\le N−1$，有 $h_i\le h_i+1$。
- 测试点 $7-15$：没有额外限制。


title: [USACO24JAN] Cannonball B

description:
Bessie 已经精通了变成炮弹并沿着长度为 $N$（$1\le N\le 10^5$）的数轴弹跳的艺术，数轴上的位置从左到右编号为 $1,2,\cdots,N$。她从某个整数位置 $S$（$1\le S\le N$）开始，以 $1$ 的起始能量向右弹跳。 如果 Bessie 的能量为 $k$，则她将弹跳至距当前位置向前距离 $k$ 处进行下一次弹跳。

从 $1$ 到 $N$ 的每个整数位置上均有炮击目标或跳板。每个炮击目标和跳板都有一个在 $0$ 到 $N$ 范围内的整数值。一个数值为 $v$ 的跳板会使 Bessie 的能量增加 $v$ 并反转她的方向。一个数值为 $v$ 的炮击目标会当着陆时能量不小于 $v$ 时被击破。着陆在炮击目标上不会改变 Bessie 的能量和方向。被击破的炮击目标将保持击破状态，Bessie 依然可以该炮击目标上弹跳，同样不会改变能量和方向。

如果 Bessie 弹跳无限长的时间或直到她离开数轴，她会击破多少个炮击目标？

如果 Bessie 开始时位于一个她可以击破的炮击目标，她会立刻这样做。类似地，如果 Bessie 开始时位于一个跳板，跳板的效果将在她第一次跳跃之前生效。

inputFormat:
输入的第一行包含 $N$ 和 $S$，其中 $N$ 为数轴的长度，$S$ 为 Bessie 的起始位置。

以下 $N$ 行描述了每一个位置。其中第 $i$ 行包含整数 $q_i$ 和 $v_i$，如果位置 $i$ 上有一个跳板则 $q_i=0$，位置 $i$ 上有一个炮击目标则 $q_i=1$，$v_i$ 是位置 $i$ 上的跳板或炮击目标的数值。

outputFormat: 输出一个整数，为将被击破的炮击目标数量。

hint:
### 样例解释 1

Bessie 从坐标 $2$ 开始，这是一个数值为 $1$ 的炮击目标，所以她立刻击破了它。然后她弹跳至坐标 $3$，这是一个数值为 $2$ 的炮击目标，所以她无法击破它。她继续弹跳至坐标 $4$，这改变了她的方向并将她的能量增加了 $1$，达到 $2$。她跳回至坐标 $2$，这是一个已经被击破的炮击目标，所以她继续弹跳。此时，她弹跳至了坐标 $0$，因此她停了下来。她击破了恰好一个炮击目标，位于坐标 $2$。

### 样例解释 2

Bessie 经过的路径为 $4\to 5\to 3\to 1\to 6$，下一次弹跳将会使她离开数轴（$11$）。她依次击破了炮击目标 $4,3,6$。

### 测试点性质

 - 测试点 $3-5$：$N\le 100$。
 - 测试点 $6-10$：$N\le 1000$。
 - 测试点 $11-20$：没有额外限制。


title: [USACO24JAN] Balancing Bacteria B

description:
Farmer John 有 $N$（$1\le N\le 2\cdot 10^5$）块草地排成一行，其中草地 $i$ 的细菌水平与健康草的细菌水平相差 $a_i$（$−10^{15}\le a_i\le 10^{15}$）。例如，如果 $a_i=−3$，则草地 $i$ 的细菌水平比正常水平低 $3$，需要额外添加恰好 $3$ 个单位的细菌才能将其提高到被认为是健康的程度。

Farmer John 想要确保每一块草地都被修复至健康的细菌水平。方便的是，他有两种品牌的农药可以喷洒在他的田地里，一种可以添加细菌，另一种可以去除细菌。当 Farmer John 喷洒任一类型的农药时，他站在草地 $N$（最右边的草地）并为他的喷雾器选择功率等级 $L$（$1\le L\le N$）。

喷雾器对靠近 Farmer John 的草地效果最大，随着距离增加效果逐渐减弱。如果 Farmer John 选择添加细菌的农药，则 $L$ 单位的细菌将被添加至草地 $N$，$L−1$ 单位添加至草地 $N−1$，$L−2$ 单位添加至草地 $N−2$，以此类推。草地 $1\ldots N−L$ 不会得到任何细菌，因为喷雾器设置的功率不足以到达它们。类似地，如果 Farmer John 选择去除细菌的农药，则 $L$ 单位的细菌将被从草地 $N$ 去除，$L−1$ 单位被从草地 $N−1$ 去除，以此类推。同样，草地 $1\ldots N−L$ 将不受影响。

求 Farmer John 使用喷雾器的最少次数，使得每块草地都具有健康草的推荐细菌值。输入保证答案不超过 $10^9$。

**注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。**

inputFormat:
输入的第一行包含 $N$。

第二行包含 $N$ 个整数 $a_1\ldots a_N$，为每块草地的初始细菌水平。

outputFormat: 输出一个整数，为使每块草地都具有健康草的推荐的细菌值所需使用喷雾器的最少次数。

hint:
### 样例解释 1

使用去除细菌的农药，功率等级为 $1$，使用五次。然后使用添加细菌的农药，功率等级为 $2$，使用一次。

### 测试点性质

- 测试点 $3-5$：$N\le 10^3$，答案不超过 $10^3$。
- 测试点 $6-10$：$N\le 10^3$。
- 测试点 $11-15$：没有额外限制。


title: [USACO24JAN] Cowmpetency S

description:
Farmer John 正在为他的奶牛们雇用一位新的牛群领队。为此，他面试了 $N$（$2\le N\le 10^5$）头奶牛来担任该职位。在面试第 $i$ 个候选牛后，他会为候选牛分配一个 $1$ 到 $C$（$1\le C\le 10^9$）范围内的整数「牲任力」分数 $c_i$，与她们的领导能力相关。

由于 Farmer John 面试了如此多的奶牛，他没能记得所有奶牛的牲任力分数。然而，他确实记得 $Q$（$1\le Q<N$）对数字 $(a_j,h_j)$，其中奶牛 $h_j$ 是第一头比奶牛 $1$ 到 $a_j$ 拥有严格更高牲任力分数的奶牛（所以 $1\le a_j<h_j\le N$）。

Farmer John 现在告诉你序列 $c_1,\ldots,c_N$
（其中 $c_i=0$ 表示他忘记了奶牛 $i$ 的牲任力分数）和 $Q$ 对 $(a_j,h_j)$。帮助他求出与此信息一致的最小字典序的牲任力分数序列，或者判断不存在这样的序列！如果一个分数序列比另一个分数序列于这两个序列不同的第一个位置上的奶牛分配了更小的分数，则这个分数序列的字典序更小。

每个测试点包含 $T$（$1\le T\le 20$）个独立的测试用例。输入保证所有测试用例的 $N$ 之和不超过 $3\cdot 10^5$。

inputFormat:
输入的第一行包含 $T$，独立的测试用例的数量。每个测试用例描述如下：

 1. 第一行包含 $N$，$Q$ 和 $C$。
 2. 第二行包含序列 $c_1,\ldots,c_N$（$0\le c_i\le C$）。
 3. 最后 $Q$ 行，每行包含一个数对 $(a_j,h_j)$。输入保证同一测试用例内的所有 $a_j$ 各不相同。

outputFormat: 对于每个测试用例，输出一行，包含与 Farmer John 记忆一致的最小字典序牲任力分数序列，或者如果这样的序列不存在时输出 $−1$。

hint:
### 样例解释 1

我们可以看到给定的输出满足所有 Farmer John 记得的数对。

- $\max(c_1)=1$，$c_2=2$ 且 $1<2$，故第一个数对是满足的
- $\max(c_1,c_2,c_3)=2$，$c_4=3$ 且 $2<3$，故第二个数对是满足的
- $\max(c_1,c_2,c_3,c_4)=3$，$c_5=4$ 且 $3<4$，故第三个数对是满足的

存在一些其他的序列与 Farmer John 的记忆相一致，如

$1\ 2\ 2\ 3\ 5\ 4\ 1$
$1\ 2\ 2\ 3\ 4\ 4\ 5$

然而，其中没有序列比给定的输出字典序更小。

### 样例解释 2

在测试用例 $3$ 中，由于 $C=1$，唯一可能的序列是

$1\ 1$

然而，在这种情况下，奶牛 $2$ 的分数并不比奶牛 $1$ 高，因此我们无法满足条件。

在测试用例 $5$ 中，$a_1$ 和 $h_1$ 告诉我们奶牛 $6$ 是第一头分数严格高于奶牛 $1$ 到 $4$ 的奶牛。因此，奶牛 $1$ 到 $6$ 的最高得分是奶牛 $6$，为 $5$。由于奶牛 $7$ 的分数为 $7$，所以奶牛 $7$ 是第一头比奶牛 $1$ 到 $6$ 得分更高的奶牛。因此，第二个陈述「奶牛 $9$ 是第一头比奶牛 $1$ 到 $6$ 得分更高的奶牛」不能成立。

### 测试点性质

 - 测试点 $3$：$N \le 10$ 且 $Q,C\le 4$。
 - 测试点 $4-8$：$N\le 1000$。
 - 测试点 $9-12$：没有额外限制。


title: [USACO24JAN] Potion Farming S

description:
你正在玩你最喜欢的手机游戏。为了有机会击败传说中的奶牛 Boss，你正在试着刷药水。游戏地图是由 $N$（$2\le N\le 10^5$）个编号为 $1\ldots N$ 的房间组成，由 $N−1$ 条边连接，形成一棵树。

你可以通过一系列的「遍历」来探索地图。一次遍历是从房间 $1$ 到树中任何其他房间的一条简单路径。当你完成一次遍历后，你可以从房间 $1$ 再次开始遍历。一旦地图的每个房间都被至少一次遍历访问过，这个地图就通关了。你的主要目标是以最小的遍历次数通关这一地图。

你的次要目标是刷到尽可能多的药水。在一次遍历开始前，地图上的某个房间内会生成一瓶药水。你可以通过在当次遍历中访问生成药水的房间来拾取药水。如果你没有拾取药水，那么当次遍历结束它就会消失，你无法在未来的遍历中拾取它。

由于你是一位聪明的程序员，在查看游戏文件后，你成功知道了在接下来的 $N$ 次遍历之前药水的出现位置。如果你以最小的遍历次数通关地图，你可以从地图内刷到的最大药水数量是多少？

inputFormat:
输入的第一行包含一个整数 $N$，为地图内的房间数量。

以下一行包含 $N$ 个空格分隔的整数 $p_1p_2\ldots p_N$，其中 $p_i$ 为第 $i$ 次遍历之前药水出现的房间。

最后 $N−1$ 行每行包含两个空格分隔的整数 $a\ b$（$1\le a,b\le N$），表示房间 $a$ 和 $b$ 之间的一条边。输入保证所有边形成一棵树。

outputFormat: 输出一行，包含一个整数，为以最小的遍历次数可以从地图内刷到的最大药水数量。

hint:
### 样例解释 1

在这个测试用例中，通关地图所需的最小遍历次数为 $3$。

一个在三次遍历中拾取两瓶药水的最佳方案如下：

- 遍历 $1$：$1\to 3\to 5$（于房间 $5$ 拾取药水）
- 遍历 $2$：$1\to 3\to 4$（于房间 $4$ 拾取药水）
- 遍历 $3$：$1\to 2$（被迫通关地图，无视房间 $3$ 的药水）

或者，我们也可以计划我们的遍历如下：

- 遍历 $1$：$1\to 2$（没有药水）
- 遍历 $2$：$1\to 3\to 4$（于房间 $4$ 拾取药水）
- 遍历 $3$：$1\to 3\to 5$（于房间 $3$ 拾取药水）

### 测试点性质

- 测试点 $2-7$：$N\le 1000$。
- 测试点 $8-15$：没有额外限制。


title: [USACO24JAN] Cowlendar S

description:
Bessie 在一个陌生的星球上醒来。这个星球上有 $N$（$1\le N\le 10^4$）个月，分别有 $a_1,\ldots,a_N$ 天（$1\le a_i\le 4\cdot 10^9$，所有 $a_i$ 均为整数）。此外，这个星球上还存在周，一周为 $L$ 天，其中 $L$ 是一个正整数。有趣的是，Bessie 知道以下事情：

- 对于正确的 $L$，每个月至少有 $4$ 周。
- 对于正确的 $L$，$a_i\bmod L$ 至多有 $3$ 个不同值。

不幸的是，Bessie 忘记了 $L$ 是多少！请通过输出 $L$ 的所有可能值之和来帮助她。

**注意这个问题涉及到的整数可能需要使用 64 位整数型（例如，C/C++ 中的 "long long"）。**

inputFormat: 输入的第一行包含一个整数 $N$。第二行包含 $N$ 个空格分隔的整数 $a_1,\ldots,a_N$。

outputFormat: 输出一个整数，为 $L$ 的所有可能值之和。

hint:
### 样例解释 1

$L$ 的可能值为 $1$，$2$，$3$，$4$，$5$，$6$ 和 $7$。例如，$L=7$ 是合法的，因为每个月的至少有 $4\cdot 7=28$ 天，且每个月的天数模 $7$ 的余数均为 $0$，$2$ 或 $3$。

### 样例解释 2

$L$ 的可能值为 $1$，$2$，$3$，$4$，$6$ 和 $7$。例如，$L=6$ 是合法的，因为每个月的至少有 $4\cdot 6=24$ 天，且每个月的天数模 $6$ 的余数均为 $1$，$4$ 或 $5$。

### 测试点性质

- 测试点 $3-4$：$1\le a_i\le 10^6$。
- 测试点 $5-14$：没有额外限制。


title: Pairing Pairs

background: 本题为赛时原始数据。如果想要测试 $O(n)$，可以参考[加强版](https://www.luogu.com.cn/problem/P10248)。

description: 你有 $m$ 个数对 $(u_i,v_i)$（保证 $1\le u_i<v_i\le n$ 且 $m$ 个数对两两不同），对于每个 $i$ 找一个 $j$ 使得 $u_i,v_i,u_j,v_j$ 四个数两两不同，或报告不存在。

inputFormat:
输入的第一行有两个正整数 $n,m$ 表示数对中数字的范围和数对的个数。

之后 $m$ 行，其中的第 $i$ 行有两个正整数 $u_i,v_i$ 表示第 $i$ 个数对。

outputFormat:
输出一行 $m$ 个自然数，其中第 $i$ 个数表示你对这个 $i$ 找到的 $j$。若对应的 $j$ 不存在则输出 $0$。

若符合题意的 $j$ 有多个，任意输出一个都可以通过本题。


title: 高效清理

background:
清理炸弹设计理念图：

![](https://cdn.luogu.com.cn/upload/image_hosting/mjfmevu2.png)

description:
真寻的房间太大了，但是作为家里蹲，她又懒得打扫，于是美波里发明了一款清理炸弹给真寻使用。

真寻的房间由 $n$ 行 $m$ 列的方砖组成，第 $i$ 行第 $j$ 列的方砖上的灰尘数量为 $a_{i,j}$。

真寻将会使用 $k$ 次清理炸弹，第 $i$ 次她会在第 $x_i$ 行第 $y_i$ 列的方砖上使用能量值为 $p_i$ 的清理炸弹，这将会使 $(x_i,y_i)$ 的灰尘数量减少 ${p_i}^2$，$(x_i,y_i)$ 外围第一圈的方砖上的灰尘数量减少 $(p_i-1)^2$，外围第二圈的方砖上的灰尘数量减少 $(p_i-2)^2$ $\cdots$ 外围第 $(p_i-1)$ 圈的方砖上的灰尘数量减少 $1$。

当然，灰尘数量不能为负数，所以若某次操作前，某块方砖上的灰尘数量小于它将要减少的灰尘数量，那么它的灰尘数量将变为 $0$。

请你输出真寻使用完 $k$ 次清理炸弹后，每块方砖上的灰尘数量。

inputFormat:
第一行三个整数 $n,m,k$，分别表示方砖行数、列数及操作次数；

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数表示 $a_{i,j}$，描述每一块方砖上的灰尘数量；

接下来 $k$ 行，第 $i$ 行三个整数 $x_i,y_i,p_i$，描述一次操作。

outputFormat: 共 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数表示方砖 $(i,j)$ 上最终的灰尘数量。


title: [语言月赛 202401] 图像变换

description:
一张字符图片由 $n$ 行 $m$ 列，共 $n\times m$ 个字符组成，第 $i$ 行第 $j$ 列的字符为 $s_{i,j}$。如下图所示，为一个 $4\times 3$ 的字符图片。

```plain
%%%
$$$
@w@
!!!
```

现在，需要将图像放大 $k$ 倍，得到 $kn \times km$ 的图片。原图片的每个字符都需要重复 $k^2$ 次，作为新图像中 $k\times k$ 的一个区域，各字符的相对位置不变。

将上面给出的例子放大 $2$ 倍，将得到如下图像：

```plain
%%%%%%
%%%%%%
$$$$$$
$$$$$$
@@ww@@
@@ww@@
!!!!!!
!!!!!!
```

inputFormat:
输入 $n+1$ 行。

输入的第一行为三个整数 $n,m,k$。

接下来 $n$ 行，每行 $m$ 个字符，表示字符图片。

outputFormat: 输出 $nk$ 行，每行 $mk$ 个字符，表示变换后的字符图片。

hint:
- 对于 $30\%$ 的测试数据，输入的字符画仅包含一种字符；
- 对于 $100\%$ 的测试数据，$1 \le n, m \le 100$，$1 \le k \le 10$，输入的字符仅包含 ASCII 码不超过 127 的可见字符。


title: 「CZOI-R1」消除威胁

background: **本题数据已修复。**

description:
给定一个序列 $\{A_n\}$。

我们称序列 $A$ 中的一个区间 $[l,r]$ 具有威胁，当且仅当 $1\le l<r\le n$ 且 $A_l=A_r$，且 $\forall i\in[l,r]$ 满足 $|A_i|\le|A_l|$。

你可以操作 $A$ 任意次，每次操作选择一个 $A_i$ 修改为 $-A_i$。请问最后序列 $A$ 中具有威胁的**不同**区间**最少**有多少个？

两个区间 $[l_1,r_1]$ 和 $[l_2,r_2]$ 不同，当且仅当 $l_1 \ne l_2$ 或 $r_1 \ne r_2$。

inputFormat:
第一行一个整数 $n$ ，表示 $A$ 的长度。

第二行 $n$ 个整数，表示 $\{A_n\}$。

outputFormat: 第一行一个正整数，表示**最少**的具有威胁的区间个数。

hint:
**【数据范围】**

**本题采用捆绑测试**。
- Subtask #1（$10\text{ pts}$）：$n\le10$。
- Subtask #2（$10\text{ pts}$）：$n\le10^3$。
- Subtask #3（$10\text{ pts}$）：$|A_i|\le60$。
- Subtask #4（$10\text{ pts}$）：$|A_i|$ 均相等。
- Subtask #5（$20\text{ pts}$）：$n\le10^5$。
- Subtask #6（$40\text{ pts}$）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le5\times10^5$，$|A_i|\le10^9$。


title: Swimming Pool

background: **请注意，四边形 $ABCD$ 中，四个点必须*顺次*是 $A,B,C,D$**，不允许 $AB$ 是一条对角线之类的情况。

description:
小 J 想要建一个四边形游泳池 $ABCD$。他希望有一组对边互相平行（方便搞一些家庭比赛），另外一组对边不平行（否则会显得太没有个性）。换言之，**他需要让这个游泳池是个梯形**。

给出四个正整数 $p,q,r,s$，判断他能否造一个符合题意的游泳池，使得 $AB=p,BC=q,CD=r,DA=s$。

inputFormat:
**本题有多组数据。** 输入的第一行有一个正整数 $T$ 表示数据组数。

之后 $T$ 行，每行有用空格隔开的四个正整数 $p,q,r,s$。

outputFormat: 对于每组数据输出 $T$ 行，其中若可以构成梯形则输出 `yes`，否则输出 `no`。

hint:
【样例解释】

第一组数据显然无法构成四边形。

第二组数据只能构成平行四边形。

第三组数据确实可以构成梯形。

【数据范围】

本题共 $6$ 个测试点，注意测试点不等分。

|测试点编号|特殊性质|分值|
|:-:|:-:|:-:|
|$1$|可构成梯形当且仅当可构成四边形|$19$|
|$2$|$p<r<s$ 且 $q<s$|$17$|
|$3$|$p,q,r,s\le 2$|$7$|
|$4$|$p<r$ 且 $q<s$|$12$|
|$5$|输入必能构成四边形|$18$|
|$6$|无特殊性质|$27$|

对于全体数据，保证 $1\le T\le 10^4$，$1\le p,q,r,s\le 5\times 10^8$，输入皆为正整数。


title: [YDOI R1] whk

background: 小 Z ~~只~~考了年级第六，要卷 whk 了。

description:
小 Z 一共要卷 $n$ 门科目，第 $i$ 门科目他有且只有 $a_i$ 道题。有无数天时间，每天小 Z 可以做无数道题。

如果小 Z 认为一天是有趣的，仅当他在这一天**至少**做了 $t$ 门科目的题。

小 Z 想知道最多有多少天是有趣的。

inputFormat:
第一行，$2$ 个正整数 $n,t$。

接下来一行，有 $n$ 个整数，分别 $a_1,a_2,a_3,\dots,a_{n-1},a_n$。

outputFormat: 一个整数，输出小 Z 认为有趣的天数的最大值。


title: [USACO24JAN] Walking in Manhattan G

description:
Farmer John 和他的 $Q$（$1\le Q\le 2\cdot 10^5$）头奶牛在曼哈顿度假，但奶牛们逃跑了，现在正在城市里自由走动！曼哈顿很大——大到它的 $N$（$1\le N\le 2\cdot 10^5$）条道路在 $x-y$ 平面上无限延伸，但简单的是，这些道路都完全水平或垂直。每条水平和垂直道路都可以用形式为 $y=c_i$ 或 $x=c_i$ 的方程表示，其中 $c_i$ 是 $0$ 到 $10^9$ 范围内的整数。

Farmer John 准确地知道每头奶牛从哪里开始行走，以及她们多久之前逃跑的。奶牛们很容易被预测，因此每头奶牛都是按照以下模式行走：

- 她们只会以每秒一个单位的速度向北（$+y$）或向东（$+x$    ）行走。
- 如果她们当前在一条道路上，她们会继续沿着道路的方向行走。
- 如果她们在两条道路的交叉口处，如果她们行走了偶数秒，则向北行走，否则向东行走。

给定曼哈顿的布局以及每头奶牛的信息，帮助 Farmer John 求出他的奶牛们现在在哪里！

inputFormat:
输入的第一行包含 $N$ 和 $Q$。

以下 $N$ 行描述道路。每条道路由方向（`H` 或 `V`）和坐标 $c_i$ 表示。输入保证道路各不相同。

以下 $Q$ 行描述奶牛。每头奶牛由三个整数 $(x_i,y_i,d_i)$ 表示，意味着她们在 $d_i$ 秒前从 $(x_i,y_i)$ 开始行走。输入保证 $(x_i,y_i)$ 位于某条道路上，且 $0\le x_i,y_i,d_i\le 10^9$。

outputFormat: 输出 $Q$ 行，其中第 $i$ 行包含第 $i$ 头奶牛当前的位置。


title: [USACO24JAN] Cowmpetency G

description:
Farmer John 正在为他的奶牛们雇用一位新的牛群领队。为此，他面试了 $N$（$2\le N\le 10^9$）头奶牛来担任该职位。在每次面试后，他会为候选牛分配一个 $1$ 到 $C$（$1\le C\le 10^4$）范围内的整数「牲任力」分数 $c_i$，与她们的领导能力相关。

由于 Farmer John 面试了如此多的奶牛，他已经忘记了所有奶牛的牲任力分数。然而，他确实记得 $Q$
（$1\le Q\le \min(N-1,100)$）对数字 $(a_i,h_i)$，其中奶牛 $h_i$ 是第一头比奶牛 $1$ 到 $a_i$ 拥有**严格**更高牲任力分数的奶牛（所以 $1\le a_i<h_i\le N$）。

Farmer John 现在告诉你这 $Q$ 个数对 $(a_i,h_i)$。请帮助他数一下有多少个牲任力分数序列与此信息一致！输入保证存在至少一个这样的序列。由于这个数字可能非常大，输出该值模 $10^9+7$ 的余数。

inputFormat:
输入的第一行包含 $N$，$Q$ 和 $C$。

以下 $Q$ 行，每行包含一个数对 $(a_i,h_i)$。输入保证所有 $a_i$ 各不相同。

outputFormat: 输出与 Farmer John 记忆一致的牲任力分数序列的数量，对 $10^9+7$ 取模。


title: [USACO24JAN] Nap Sort G

description:
Bessie 正在尝试使用她自己的排序算法对一个整数数组进行排序。她有一堆共 $N$（$1\le N\le 2\cdot 10^5$）个整数 $a_1,a_2,\ldots,a_N$（$1\le a_i\le 10^{11}$），她将会按排序顺序将这些数放入一个单独的数组中。她反复查找这堆数中的最小数，将其删除，同时将其添加到数组的末尾。Bessie 在 $p$ 个数的堆中找到最小数需要花费 $p$ 秒。

Farmer John 命令了农场中其他一些奶牛帮助 Bessie 完成任务，她们很懒，然而 Bessie 利用了这一点。她将整数分成两堆：Bessie 堆和助手堆。对于 Bessie 堆中的每个整数，她会正常执行她的算法。对于助手堆中的每个整数，她将其分配给不同的助手奶牛。Farmer John 有一个很大的农场，所以 Bessie 可以找来任意多的助手奶牛。如果助手收到整数 $a_i$，Bessie 会指示该牛小睡 $a_i$ 秒，并在她们醒来时立即将该整数添加到数组末尾。如果 Bessie 和一个助手同时向数组添加整数，Bessie 的整数将优先被添加，因为她是领导者。如果多个助手被分配了相同的整数，她们会同时将多个该整数添加到数组中。

请帮助 Bessie 划分她的数，使得最终得到的数组是排序的，并使得排序该数组所需的时间最少。

inputFormat:
输入的第一行包含 $T$，为独立的测试用例的数量（$1\le T\le 10$）。

每个测试用例的格式如下：

每个测试用例的第一行包含 Bessie 的数组中的数的数量 $N$。

下一行包含 $a_1,a_2,\ldots,a_N$，为 Bessie 将要排序的整数。相同的数值可能会多次出现。

输入保证所有测试用例的 $N$ 之和不超过 $2\cdot 10^5$。

outputFormat: 对于每个测试用例输出一行，包含当 Bessie 以最优方案划分她的数时，排序该数组所需要的最小时间。

hint:
### 样例解释 1

在第一个测试用例中，Bessie 可以将 $1,2$ 分配给助手，将 $4,5,10^{11}$ 留给自己。

| 时间 | 事件 |
| :-----------:| :----------- |
| $1$ | 助手添加了 $1$ |
| $2$ | 助手添加了 $2$ |
| $3$ | Bessie 添加了 $4$ |
| $5$ | Bessie 添加了 $5$ |
| $6$ | Bessie 添加了 $10^{11}$ |

在第二个测试用例中，Bessie 的最优方案是自己对所有数进行排序。一个不正确的划分是 Bessie 将 $4$ 分配给助手，其余的分配给她自己，因为助手将 $4$ 添加到数组之前 Bessie 就会将 $17$ 添加到数组中。

在第三个测试用例中，Bessie 可以将所有数都分配给助手。

在第四个测试用例中，Bessie 可以将 $1,4,5$ 分配给助手，将 $2,5,100$ 留给自己。

| 时间 | 事件 |
| :-----------:| :----------- |
| $1$ | 助手添加了 $1$ |
| $3$ | Bessie 添加了 $2$ |
| $4$ | 助手添加了 $4$ |
| $5$ | Bessie 添加了 $5$ |
| $5$ | 助手添加了 $5$ |
| $6$ | Bessie 添加了 $100$ |

### 测试点性质

- 测试点 $2$：$N\le 16$。
- 测试点 $3-5$：$N\le 150$。
- 测试点 $6-8$：$\sum N\le 5000$。
- 测试点 $9-11$：没有额外限制。


title: [USACO24JAN] Island Vacation P

description:
Bessie 正在一个 $N$（$2\le N\le 10^4$）座岛组成的岛屿网络中度假，编号为 $1\ldots N$，由 $M$ 座双向通行的桥连接，每座桥连接两座岛（$N−1\le M\le \dfrac{3(N-1)}{2}$）。保证所有桥形成连通的简单图（具体地说，没有两座桥连接同一对岛屿，也没有一座桥连接一座岛到其自身）。

另外保证没有一座桥处在多于一个简单环上。一个简单环是一个不包含重复岛的环。

Bessie 从岛 $1$ 开始，按以下过程旅行。假设她目前在岛 $i$ 上，

1. 如果不存在连接岛 $i$ 的她尚未穿过的桥，则她的度假结束。
2. 否则，以 $p_i \pmod {10^9+7}$ 的概率，她的度假结束。
3. 否则，在连接岛 $i$的所有她还没有穿过的桥中，她均匀地随机选择一座并穿过它。

对于每座岛，输出她在该岛上结束度假的概率，对 $10^9+7$ 取模。

inputFormat:
输入的第一行包含独立的测试用例的数量 $T$（$1\le T\le 10$）。相邻的测试用例之间以一个空行分隔。

每一个测试用例的第一行包含 $N$ 和 $M$，其中 $N$ 为岛的数量，$M$ 为桥的数量。输入保证所有测试用例的 $N$ 之和不超过 $10^4$。

第二行包含 $p_1,p_2,\ldots,p_N$（$0\le p_i<10^9+7$）。

以下 $M$ 行描述所有的桥。第 $i$ 行包含整数 $u_i$ 和 $v_i$（$1\le u_i<v_i\le N$），表示第 $i$ 座桥连接岛 $u_i$ 和 $v_i$。输入保证所有桥满足上文中的限制。

outputFormat: 对于每个测试用例输出一行，包含在岛 $1$ 到 $N$ 的每一座岛上结束度假的概率模 $10^9+7$ 的余数，用空格分隔。

hint:
### 样例解释 1

在第一个测试用例中，$p_3\equiv \frac{1}{9}\pmod {10^9+7}$。Bessie 有 $\frac{1}{9}$ 的概率在岛 $3$ 结束（经过路径 $1\to 3$），$\frac{8}{9}$ 的概率在岛 $2$ 结束（经过路径 $1\to 3\to 2$）。

在第二个测试用例中，$p_1\equiv \frac{1}{2}\pmod {10^9+7}$。Bessie 有 $\frac{1}{2}$ 的概率在岛 $1$ 结束，各 $\frac{1}{6}$ 的概率在岛 $2$ 和 $3$ 结束，各 $\frac{1}{12}$ 的概率在岛 $4$ 和岛 $6$ 结束。

### 样例解释 2

在第一个测试用例中，$p_1\equiv p_2\equiv \frac{1}{3}\pmod {10^9+7}$。Bessie 有 $\frac{7}{9}$ 的概率在岛 $1$ 结束（经过路径 $1$，$1\to 2\to 3\to 4\to 5\to 1$ 与 $1\to 5\to 4\to 3\to 2\to 1$ 之一），$\frac{2}{9}$ 的概率在岛 $2$ 结束。

在第二个测试用例中，Bessie 有 $\frac{1}{3}$ 的概率在岛 $3$ 结束，$\frac{2}{3}$ 的概率在岛 $5$ 结束。

### 测试点性质

- 测试点 $4-5$：$N\le 11$。
- 测试点 $6-7$：不存在简单环。
- 测试点 $8-11$：没有一座岛处在多于一个简单环上。
- 测试点 $12-15$：没有一座岛处在多于 $5$ 个简单环上。
- 测试点 $16-19$：没有一座岛处在多于 $50$ 个简单环上。
- 测试点 $20-23$：没有额外限制。


title: [USACO24JAN] Merging Cells P

background: **注意：本题的内存限制为 512MB，通常限制的两倍。**

description:
Bessie 正在玩一个著名的在线游戏，游戏中有许多不同编号和大小的细胞。细胞会被其他细胞吞噬，直到只剩下一个胜利者。

有 $N$（$2\le N\le 5000$）个细胞从左到右排成一行，编号为 $1\ldots N$，初始大小为 $s_1,s_2,\ldots,s_N$（$1\le s_i\le 10^5$）。当存在多个细胞时，均匀地随机选择一对相邻细胞，并根据以下规则合并为一个新的细胞：

如果编号为 $a$ 且当前大小为 $c_a$ 的细胞与编号为 $b$ 且当前大小为 $c_b$ 的细胞合并，则合并成的细胞的大小为 $c_a+c_b$，且编号等于较大细胞的编号，并列时则为编号较大的细胞的编号。形式化地说，合并成的细胞的编号为 $\begin{cases}a & c_a>c_b\\b & c_a<c_b\\ \max(a,b) & c_a=c_b \end{cases}$。

对于 $1\ldots N$ 范围内的每个编号 $i$，最终的细胞具有编号 $i$ 的概率可以以 $\frac{a_i}{b_i}$ 的形式表示，其中 $b_i\not \equiv 0 \pmod {10^9+7}$。输出 $a_ib_i^{-1}\pmod {10^9+7}$。

inputFormat:
输入的第一行包含 $N$。

第二行包含 $s_1,s_2,\ldots,s_N$。

outputFormat: 对于 $1\ldots N$ 内的每个 $i$ 输出一行，为输出最终的细胞具有编号 $i$ 的概率模 $10^9+7$ 的余数。


title: [USACO24JAN] Mooball Teams III P

description:
Farmer John 在他的农场上有 $N$ 头牛（$2\le N\le 2\cdot 10^5$），编号为 $1\ldots N$。奶牛 $i$ 位于整数坐标 $(x_i,y_i)$（$1\le x_i,y_i\le N$）。Farmer John 想要挑选两支队伍来玩哞球游戏！

其中一支队伍将是「红队」；另一队将是「蓝队」。对组队只有很少的要求。两队都不能为空，并且 $N$ 头奶牛中的每一头至多只能在一个队中（可以两队都不在）。唯一的其他要求是基于哞球独特的特点：一个无限长的网，必须将其放置为平面中非整数坐标的水平或垂直直线，例如 $x=0.5$。FJ 挑选队伍必须使得可以用网将两队分开。奶牛们不愿意为此进行移动。

帮帮农夫吧！为 Farmer John 计算选择满足上述要求的红队和蓝队的方法数，对 $10^9+7$ 取模。

inputFormat:
输入的第一行包含一个整数 $N$。

以下 $N$ 行每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。输入保证 $x_i$ 组成 $1\ldots N$ 的一个排列，$y_i$ 类似。

outputFormat: 输出一个整数，为选择满足上述要求的红队和蓝队的方法数，对 $10^9+7$ 取模。

hint:
### 样例解释 1

我们可以选择红队为牛 1，蓝队为牛 2，或者相反。无论哪种情况，我们都可以用一个网将两支球队分开（例如，$x=1.5$）。

### 样例解释 2

以下是所有的十种可能的将奶牛分队的方法；第 $i$ 个字符表示第 $i$ 头奶牛的队伍，`R` 表示红队，`B` 表示蓝队，或 `.` 表示第 $i$ 头奶牛不在一个队伍中。

```plain
RRB
R.B
RB.
RBB
.RB
.BR
BRR
BR.
B.R
BBR
```

### 样例解释 3

以下是所有的十二种可能的将奶牛分队的方法：

```plain
RRB
R.B
RBR
RB.
RBB
.RB
.BR
BRR
BR.
BRB
B.R
BBR
```

### 样例解释 4

确保输出答案对 $10^9+7$ 取模。

### 测试点性质

- 测试点 $5$：$N\le 10$。
- 测试点 $6-9$：$N\le 200$。
- 测试点 $10-13$：$N\le 3000$。
- 测试点 $14-24$：没有额外限制。


title: 「MYOI-R3」极差

description: 对于一个序列 $c$ ，定义 $c$ 的极差为 $c$ 中最大值与最小值之差。现在给定一个长度为 $n$ 的序列 $a$，问是否能将其分成至少两个长度大于 $1$ 的子序列，使得每个子序列的极差都相等（注意，所有元素都必须分配且每个元素仅能分配到一个子序列中）。

inputFormat:
**本题包含多组数据**。

第一行两个整数 $T,id$，表示数据组数和子任务编号。

对于每组数据，

第一行一个正整数 $n$，表示数组长度。

第二行 $n$ 个整数表示序列 $a$。

outputFormat: 对于每组数据，输出一行一个字符串 `Yes` 或 `No`。

hint:
### 样例 $\small\text{1}$ 解释

样例符合子任务 1 的约束，$id=1$。

询问一：

可以证明，没有任何方案满足条件。

询问二：

合法分配的一种子序列集合如下：
- $\{1,9\}$。
- $\{1,9\}$。
- $\{8,1,0\}$。

答案不唯一。

### 数据规模与约定

**本题采用捆绑测试**。

- Subtask 1（20 points）：$4\le \sum n\le 20,a_i\ge 0$。
- Subtask 2（20 points）：$4\le \sum n\le 100,a_i\ge 0$。
- Subtask 3（20 points）：$4\le \sum n\le 10^3,a_i\ge 0$。
- Subtask 4（10 points）：$a$ 数组中元素相等。
- Subtask 5（30 points）：无特殊限制。

对于 $100\%$ 的数据，$4\le \sum n\le 10^6,0\le |a_i|\le 10^9,1\le T\le 300$。


title: [语言月赛 202401] Genshin 玩家

description:
在洛谷入门赛/语言月赛出题 QQ 群里，著名洛谷管理员蓝边铅球老师的群名片是『原神玩家』。这个群名片的含义是，蓝边铅球因为沉迷玩原神，在语言月赛出了不少锅。

现在，扶苏给了你一个字符串 $s$，她想请你求出：有多少种方案可以在 $s$ 中取出两个子串 $s[l_1, r_1], s[l_2, r_2]$，满足：

- $1 \leq l_1 \leq r_1 \leq l_2 \leq r_2 \leq |s|$，这里 $|s|$ 表示字符串 $s$ 的长度。
- $s[l_1, r_1]$ 表示由 $s$ 的第 $l_1$ 个字符到第 $r_1$ 个字符构成的字符串，$s[l_1, r_1] = \texttt{Genshin}$。
- $s[l_2, r_2]$ 表示由 $s$ 的第 $l_2$ 个字符到第 $r_2$ 个字符构成的字符串，$s[l_2, r_2] = \texttt{player}$。

两个方案不同，当且仅当两个方案中 $l_1, r_1, l_2, r_2$ 至少有一个对应不同。

inputFormat: 输入只有一行，包含一个字符串 $s$。

outputFormat: 输出一行一个整数表示答案。

hint:
### 数据规模与约定

- 对 $30\%$ 的数据，保证 $|s| \leq 50$。
- 对 $60\%$ 的数据，保证 $|s| \leq 200$。
- 对 $100\%$ 的数据，保证 $1 \leq |s| \leq 2000$，$s$ 中仅含大小写英文字母。


title: [SNOI2024] 树 V 图

description:
你有一棵 $n$ 个点的无根树，节点的编号为 $1, 2, \ldots, n$。定义树上两点之间的距离 $\operatorname{dis}(i, j)$ 为树上 $i$ 点到 $j$ 点的简单路径上的边数。

现在有 $k$ 个关键点 $a_1, a_2, \ldots, a_k$，对于每个点，我们想求出距离它最近的关键点是哪个点。也就是对于一个点 $v$，令 $f(v)$ 表示令 $\operatorname{dis}(v, a_i)$ 最小的 $i$，如果有多个 $i$ 满足条件，那么我们会选择其中最小的 $i$。

现在，我们给出了 $f(1), f(2), \ldots, f(n)$，问有多少组可能的 $(a_1, a_2, \ldots, a_k)$ 满足条件。由于答案可能很大，输出对 $998244353$ 取模的结果。

inputFormat:
多组测试数据，第一行一个整数 $T$ 表示数据组数。
对于每组测试数据，第一行两个整数 $n, k$，表示节点个数和关键点个数。
接下来 $n - 1$ 行，每行两个整数 $u, v$，表示一条树边 $(u, v)$。
接下来一行，$n$ 个整数，$f(1), f(2), \ldots, f(n)$。注意：数据**不保证**一定存在一组可能的 $(a_1, a_2, \ldots, a_k)$。

outputFormat: 对于每组数据，输出一个整数，表示答案对 $998244353$ 取模的结果。

hint:
**【样例 \#1 解释】**

在第一个样例中，对于第二组数据，一个解为 $(1, 2)$。对于第三组数据，两个解为 $(2, 1), (3, 1)$。

注意，当多个点距离相同时，我们选择的是最小的 $i$ 而不是 $a_i$。

---

**【样例 \#3】**

见附件中 `voronoi/voronoi3.in` 与 `voronoi/voronoi3.ans`，这个样例满足测试点 $3 \sim 4$ 的条件限制。

---

**【样例 \#4】**

见附件中 `voronoi/voronoi3.in` 与 `voronoi/voronoi3.ans`，这个样例满足测试点 $7 \sim 10$ 的条件限制。

---

**【数据范围】**

对于所有的数据，保证 $1 \le T \le 10$，$2 \le k \le n \le 3 \times {10}^3$，$1 \le f(i) \le k$。

具体如下：

| 测试点编号 | $n \le$ | 特殊性质 |
|:-:|:-:|:-:|
| $1 \sim 2$ | $15$ | 无 |
| $3 \sim 4$ | $3000$ | A |
| $5 \sim 6$ | $3000$ | B |
| $7 \sim 10$ | $3000$ | 无 |

特殊性质 A：保证树是一条链。
特殊性质 B：保证 $k = 2$。


title: [SNOI2024] 矩阵

description:
你要维护一个 $n \times n$ 的矩阵 $A$，其中第 $i$ 行第 $j$ 列的元素记作 $A_{i, j}$。行和列从 $1$ 开始标号。一开始，有 $A_{i, j} = (i + 1)^j \bmod 998244353$。

你需要支持 $q$ 个操作，每个操作是下面两种操作中的一种。

- $1\ x_1\ y_1\ x_2\ y_2$，这里保证 $y_2 - x_2 = y_1 - x_1$。将子矩形 $[x_1, x_2] \times [y_1, y_2]$ 逆时针旋转 $90$ 度。
  - 具体地，令 $d = x_2 - x_1 + 1$。
  - 首先提取 $d \times d$ 的子矩阵 $A'$，对于所有的 $i, j$（$1 \le i, j \le d$），令 $A'_{i, j} \gets A_{x_1 + i - 1, y_1 + j - 1}$。
  - 然后将 $A'$ 旋转，得到一个 $d \times d$ 的子矩阵 $B'$，令 $B'_{i, j} \gets A'_{j, d - i + 1}$。
  - 然后将 $B'$ 填回到 $A$ 中，对所有的 $i, j$（$1 \le i, j \le d$），令 $A_{i + x_1 - 1, j + y_1 - 1} \gets B'_{i, j}$。
- $2\ x_1\ y_1\ x_2\ y_2\ d$。将子矩形 $[x_1, x_2] \times [y_1, y_2]$ 内所有的元素加 $d$。
  - 具体地，对于每个 $i$（$x_1 \le i \le x_2$）、$j$（$y_1 \le j \le y_2$），令 $A_{i, j} \gets A_{i, j} + d$。

你需要在所有操作结束之后，输出这个矩阵。由于输出可能很大，请输出
$$ \Biggl( \sum_{i = 1}^{n} \sum_{j = 1}^{n} A_{i, j} \times {12345}^{(i - 1) n + j} \Biggr) \bmod 1000000007 $$
的结果。

inputFormat:
第一行两个整数 $n, q$ 表示矩阵大小和操作个数。
接下来 $q$ 行，每行若干个数，表示上面的某种操作。

outputFormat: 输出一个整数，表示答案对 $1000000007$ 取模的结果。

hint:
**【样例 \#1 解释】**

对于第一个样例，矩阵分别为
$$\begin{bmatrix} 2 & {\textcolor{red}{4}} & {\textcolor{red}{8}} & {\textcolor{red}{16}} \\ 3 & {\textcolor{red}{9}} & {\textcolor{red}{27}} & {\textcolor{red}{81}} \\ 4 & {\textcolor{red}{16}} & {\textcolor{red}{64}} & {\textcolor{red}{256}} \\ 5 & 25 & 125 & 625 \end{bmatrix} \to \begin{bmatrix} 2 & 16 & 81 & 256 \\ {\textcolor{blue}{3}} & {\textcolor{blue}{8}} & 27 & 64 \\ {\textcolor{blue}{4}} & {\textcolor{blue}{4}} & 9 & 16 \\ {\textcolor{blue}{5}} & {\textcolor{blue}{25}} & 125 & 625 \end{bmatrix} \to \begin{bmatrix} 2 & 16 & 81 & 256 \\ {\textcolor{red}{6}} & {\textcolor{red}{11}} & 27 & 64 \\ {\textcolor{red}{7}} & {\textcolor{red}{7}} & 9 & 16 \\ 8 & 28 & 125 & 625 \end{bmatrix}$$
$$\to \begin{bmatrix} {\textcolor{blue}{2}} & {\textcolor{blue}{16}} & {\textcolor{blue}{81}} & {\textcolor{blue}{256}} \\ 11 & 7 & 27 & 64 \\ 6 & 7 & 9 & 16 \\ 8 & 28 & 125 & 625 \end{bmatrix} \to \begin{bmatrix} 7 & 21 & 86 & 261 \\ 11 & 7 & 27 & 64 \\ 6 & 7 & 9 & 16 \\ 8 & 28 & 125 & 625 \end{bmatrix}$$
其中每个旋转操作对应的数字用红色表示，加操作对应的数字用蓝色表示。

---

**【样例 \#3】**

见附件中 `matrix/matrix3.in` 与 `matrix/matrix3.ans`，这个样例满足测试点 $5 \sim 6$ 的条件限制。

---

**【样例 \#4】**

见附件中 `matrix/matrix3.in` 与 `matrix/matrix3.ans`，这个样例满足测试点 $9 \sim 10$ 的条件限制。

---

**【数据范围】**

对于所有的数据，保证 $1 \le n \le 3000$，$1 \le q \le 3000$。
对于每个操作，保证 $1 \le x_1 \le x_2 \le n$，$1 \le y_1 \le y_2 \le n$，$1 \le d \le {10}^9$。

具体如下：

| 测试点编号 | $n \le$ | $q \le$ | 特殊性质 |
|:-:|:-:|:-:|:-:|
| $1$ | $100$ | $3000$ | 无 |
| $2$ | $3000$ | $3000$ | A |
| $3 \sim 4$ | $3000$ | $2000$ | B |
| $5 \sim 6$ | $3000$ | $3000$ | B |
| $7 \sim 8$ | $3000$ | $2000$ | 无 |
| $9 \sim 10$ | $3000$ | $3000$ | 无 |

特殊性质 A：保证没有第一类旋转操作。
特殊性质 B：保证没有第二类加法操作。


title: [SNOI2024] 拉丁方

description:
我们定义一个 $n \times n$ 的矩阵 $A$ 为拉丁方，当且仅当，每行每列都是一个 $1 \sim n$ 的排列。

现在给你一个矩阵 $A$ 左上角的一个 $R \times C$ 的子矩阵，也就是 $A_{i, j}$（$1 \le i \le R$，$1 \le j \le C$）。问能不能将剩下的位置填上数使得它是一个拉丁方。

inputFormat:
多组测试数据，第一行一个整数 $T$ 表示测试数据组数。
对于每组测试数据，第一行三个整数 $n, R, C$ 表示矩阵大小和已知的矩阵大小。
接下来 $R$ 行，每行 $C$ 个数，其中第 $i$ 行的第 $j$ 个数表示 $A_{i, j}$。

outputFormat:
对于每组数据，第一行输出一个字符串 `Yes` 或者 `No`，表示能否找到满足条件的拉丁方。
如果能找到满足条件的拉丁方，那么在接下来 $n$ 行，每行输出 $n$ 个数，表示一个满足条件的拉丁方。如果有多组满足条件的方案，输出任意一种即可。

hint:
**【样例 \#1 解释】**

在第一个样例中，对于第二组数据，根据前两行可以发现，$A_{1, 3} = A_{2, 3} = 3$，所以不存在满足条件的拉丁方。

对于第三组数据，可以发现输出是一个满足条件的拉丁方，并且左上角是输入的矩阵。下面也是一个满足条件的方案。
$$\begin{bmatrix} 1 & 2 & 3 & 5 & 4 \\ 4 & 3 & 2 & 1 & 5 \\ 3 & 5 & 1 & 4 & 2 \\ 2 & 4 & 5 & 3 & 1 \\ 5 & 1 & 4 & 2 & 3 \end{bmatrix}$$

---

**【样例 \#2】**

见附件中 `latin/latin2.in` 与 `latin/latin2.ans`，这个样例满足测试点 $6 \sim 7$ 的条件限制。

---

**【样例 \#3】**

见附件中 `latin/latin3.in` 与 `latin/latin3.ans`，这个样例满足测试点 $11 \sim 12$ 的条件限制。

---

**【数据范围】**

对于所有的数据，保证 $1 \le T \le 10$，$1 \le n \le 500$，$1 \le R, C \le n$，$1 \le A_{i, j} \le n$，保证输入的子矩阵不存在一行或者一列有两个相同的数。

具体如下：

| 测试点编号 | $n \le$ | 特殊性质 |
|:-:|:-:|:-:|
| $1 \sim 2$ | $6$ | 无 |
| $3 \sim 4$ | $10$ | 无 |
| $5$ | $500$ | A |
| $6 \sim 7$ | $100$ | B |
| $8 \sim 9$ | $300$ | B |
| $10$ | $500$ | B |
| $11 \sim 12$ | $500$ | C |
| $13 \sim 14$ | $100$ | 无 |
| $15 \sim 16$ | $300$ | 无 |
| $17 \sim 20$ | $500$ | 无 |

特殊性质 A：保证 $R = 1$。
特殊性质 B：保证 $C = n$。
特殊性质 C：保证 $R, C \le \frac{n}{2}$。


title: [SNOI2024] 平方数

background:
原题时间限制为 1.5 s。

由于 hack 数据难以通过，改为 10 s。

description: 你有一个正整数序列 $a_1, a_2, \ldots, a_n$。请问有多少个区间的乘积是完全平方数。也就是有多少对 $(l, r)$（$1 \le l \le r \le n$），满足 $\prod_{i = l}^{r} a_i$ 是完全平方数。

inputFormat:
第一行一个整数 $n$ 表示数字个数。
接下来一行，每行 $n$ 个数，表示 $a_1, a_2, \ldots, a_n$。

outputFormat:
输出一个整数，表示有多少对区间的乘积是完全平方数。
接下来按照字典序输出这些区间，也就是按照 $l$ 从小到大输出。
如果有多个 $l$ 相同的区间，按照 $r$ 从小到大输出。如果区间个数超过 ${10}^5$ 个，输出前 ${10}^5$ 个即可。


title: [SNOI2024] 公交线路

description:
给定一棵 $n$ 个点的无根树。我们希望在一些点对之间修建公交线路，满足任意两个点之间只需要至多两条公交线路就能到达。

形式化地说，考虑树上的所有 $\frac{n (n - 1)}{2}$ 条两个端点不同的简单路径。对于这些路径的一个子集 $S$，称它是好的当且仅当：
- 考虑一张新的图 $G$，对于一对点 $u, v$，当且仅当存在 $S$ 中的一条路径 $P$，满足 $u$ 和 $v$ 都在 $P$ 上，我们会在 $u, v$ 之间连上边权为 $1$ 的无向边。
- 要求 $G$ 中任意两点之间的距离都不超过 $2$。

你需要求出有多少个子集 $S$ 是好的。由于答案可能很大，输出对 $998244353$ 取模的结果。

inputFormat:
第一行，一个正整数 $n$ 表示节点个数。
接下来 $n - 1$ 行，每行两个正整数 $u, v$，表示一条树边 $(u, v)$。

outputFormat: 输出一个整数，表示答案对 $998244353$ 取模的结果。


title: [SNOI2024] 字符树

description:
给你一个 $n$ 个点的有根树，根为 $1$。每条边上有一个字符 $c = \{0, 1\}$。$S_u$ 表示从根到 $u$ 的路径上每条边的字符依次写下来组成的字符串。保证每个节点向儿子的边上的字符互不相同。

对每个点 $u$，有一个价值 $\mathit{val}_u$ 和一个限制 $a_u$。对每个点 $u$，如果点 $v$ 满足 $S_u$ 是 $S_v$ 的后缀。那么我们认为 $v$ 是的 $u$ 扩展点。

Alice 手里有一个字符串 $S$，初始令 $S = S_u$，现在他可以删掉若干末尾的字符，使得 $S$ 变成 $S'$。并将 $S'$ 告诉给 Bob。

Bob 获得了一个字符串 $S'$，他需要在 $S'$ 之后加入若干字符，并获得 $S''$。对于某个 $u$ 的扩展点 $v$，满足 $S'' = S_v$，并且 $\lvert S' \rvert \ge a_v$，那么 Bob 就获得了 $\mathit{val}_v$ 的收益，当然 Bob 只能进行一次这样的操作，所以他会选择符合条件的 $v$ 里，$\mathit{val}_v$ 最大的那个。如果没有符合条件的 $v$，Bob 只能获得 $0$ 的收益。

现在 Alice 想知道，对于删除 $0 \sim \lvert S \rvert$ 个字符，总计 $\lvert S \rvert + 1$ 种删除方式里 Bob 能获得权值之和是多少？

对于每个 $u$，你都需要回答 Alice 的询问。

形式化地说：

我们需要对每个点 $u$ 求出 $\mathit{ans}_u = \sum\limits_{0 \le i \le \lvert S_u \rvert} \max\limits_{i \ge a_v \land S_u = S_v[\lvert S_v \rvert - \lvert S_u \rvert + 1, \lvert S_v \rvert] \land S_u[1, i] = S_v[1, i]} \mathit{val}_v$。

特殊的，如果对于某个 $u$，不存在任何 $v$ 满足条件，那么 $\max = 0$。

其中 $S[l, r]$ 表示字符串 $S$ 的第 $l$ 到第 $r$ 个字符组成的字符串。特殊的，$S[x + 1, x]$ 表示空串。$\lvert S \rvert$ 表示字符串 $S$ 的长度，$\land$ 表示且。

inputFormat:
多组测试数据，第一行一个整数 $T$ 表示数据组数。
对于每组测试数据，第一行一个正整数 $n$，表示节点个数。
接下来 $n - 1$ 行，每行两个整数 $\mathit{fa}_i, c_i$ 表示第 $i$ 个点的父亲编号，以及边上的字符。
接下来一行 $n$ 个正整数 $\mathit{val}_1, \mathit{val}_2, \ldots, \mathit{val}_n$。
接下来一行 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$。

outputFormat: 输出一行 $n$ 个整数 $\mathit{ans}_1, \mathit{ans}_2, \ldots, \mathit{ans}_n$。


title: 『STA - R4』保险丝

background:
APJ：「？我家保险丝怎么又没了」

UPD. 已经更换模数（$998244353\to994007158$）

description:
给一棵 $n$ 个点的有根树，根是 $1$ 号结点。

定义两个点集 $S_1,S_2$ 的距离为从两个集合分别选出一个点，能得到两点间距离的最小值，即 $\displaystyle\operatorname{dist}(S_1,S_2)=\min_{\substack{u\in S_1\\v\in S_2}}\operatorname{dist}(u,v)$，其中 $\operatorname{dist}(u,v)$ 是点 $u,v$ 间的距离。

定义 $\operatorname{path}(u,v)$ 是 $u$ 到 $v$ 的简单路径上的所有点组成的集合，$\mathcal L$ 是所有叶子组成的集合。

对于固定正整数 $u$，定义满足如下条件的结点 $v$ 构成 $u$ 的半邻域 $\mathring U(u)$：
- $v$ 在 $u$ 子树内；
- $\operatorname{dist}(u,v)\le\operatorname{dist}(\operatorname{path}(1,v),\mathcal L)$。

即 $u$ 的半邻域 $\mathring U(u)$ 包含 $u$ 的子树内所有满足到 $u$ 的距离不大于它到根的路径上任意一点离最近叶子节点的距离的点。

进而定义：
$$f(x)=\sum_{u\in\mathring U(x)}\prod_{\substack{v\in\operatorname{subtree}(u)\\v\in\mathring U(x)}}F_{\deg v}$$
其中 $\operatorname{subtree}(u)$ 是 $u$ 子树中所有点组成的集合，$\deg u$ 是 $u$ 的度数，$F$ 是 Fibonacci 数列：
$$F_n=\begin{cases}1&n\le 2\\F_{n-1}+F_{n-2}&n\ge 3\end{cases}$$

即 $f(x)$ 对应 $x$ 的半邻域中点对 $x$ 的贡献之和。而一个点 $u$ 对 $x$ 的贡献的计算方式为：取出每个 $u$ 子树内处在 $x$ 半邻域中的点 $v$，若 $v$ 的度数为 $d$，则将 $u$ 的贡献乘上 $F_d$，所有 $u$ 的贡献之和为结果。

你需要求出 $f(1),f(2),\cdots,f(n)$ 的值，为减少输出量，你只需要输出它们模 $994007158$ 后的异或和，即 $\bigoplus_{x=1}^n(f(x)\bmod 994007158)$ 即可。

inputFormat:
第一行一个正整数 $n$ 表示点数。

第二行 $n - 1$ 个正整数，第 $i$ 个正整数代表了结点 $i + 1$ 的父亲结点。

outputFormat: 一行，表示 $\bigoplus_{x=1}^n(f(x)\bmod 994007158)$ 的值。

hint:
**本题采用捆绑测试。**
- Subtask 1 (10pts)：$n\le 5000$。
- Subtask 2 (20pts)：树的叶子个数不大于 $30$。
- Subtask 3 (20pts)：树中没有恰有一个儿子的结点。
- Subtask 4 (50pts)：无特殊限制。

对于全部数据，$2\le n,q\le 10^6$，每个非根结点父亲的编号小于它的编号。