title: 「GMOI R2-T3」粒子环游

background: 热爱珂学的小 Z 正在进行一项无聊的实验。

description:
实验室中有一个由 $n$ 个实验腔连接而成的环形轨道，其中第 $i$ 个实验腔顺时针连向第 $i+1$ 个实验腔（特别的，第 $n$ 个实验腔连向第 $1$ 个实验腔）。同时还有一个标号为 $n+1$ 的新建实验腔要接入这个环形轨道。它可以接在任意两个原本相连的实验腔之间。

第 $i$ 个实验腔可以将带电荷量为 $Q$ 的粒子运输到它的下一个实验腔，这个过程花费的能量为 $\vert Q \vert \times c_i$。除此之外，第 $i$ 个实验腔本身就存储了量为 $e_i$ 的电荷（电荷量有正负）。由于众所周知的电荷守恒定律，第 $n+1$ 个实验腔储存的电荷量与前 $n$ 个实验腔储存的总电荷量的代数和为 $0$。

小 Z 有一个原本不带电的粒子。等到第 $n+1$ 个实验腔接入轨道后，他要任选一个实验腔（包括第 $n+1$ 个）作为出发点，将粒子放入，并使之在实验腔的能量驱动下顺时针环游一周回到出发点。粒子每到达一个实验腔（包括出发点），它所带电荷量就会变成原来所带的电荷量和这个实验腔所储存的电荷量的代数和。

**注意：电荷量会先加上实验腔所含电荷量，再计算能量贡献。**

现在，小 Z 想知道，在所有接入新建实验腔并选定出发点的方案中，粒子环游一周所需的能量最少为多少？

inputFormat:
第一行为一个正整数 $n$ ，表示环形轨道原有实验腔数。

第二行有 $n+1$ 个非负整数，依次表示 $c_1,c_2,...,c_{n+1}$。

第三行有 $n$ 个整数，依次表示 $e_1,e_2,...,e_{n}$。

outputFormat: 输出共一行，包括一个数，表示粒子环游一周所需的最少能量。


title: [YsOI2022] 道路修建

type: P

background: Ysuperman 正在给他幼儿园里的小朋友们准备一场模板测试，下面是一道模板题，他希望你可以帮他验一下题目。

description:
某地新建了 $n$ 座城市，拟定建造 $m$ 条**单向**道路，其中第 $i$ 条道路起点为 $u_i$，终点为 $v_i$，建造费用为正整数 $w_i$。

然而在道路开始修建之前突发紧急情况，需要马上选择这些道路中的一些来修建使得所有城市的人都可以走到某 $k$ 座城市中（也就是说，所有城市的人都可以走到这 $k$ 座城市中的**至少一座**城市中），你想要知道，如果这 $k$ 座城市是等概率随机在 $n$ 座城市中的选定的，那么期望的最小修建费用是多少。

为了避免分数输入输出，你只需要输出答案对 $998244353$ 取模的结果。

inputFormat:
第一行三个非负整数 $n,m,k$ 表示城市数量、拟定建造公路数量以及待选定的城市数量。

接下来 $m$ 行，每行三个正整数 $u_i,v_i,w_i$ 描述一条拟定建造的单向公路。

outputFormat:
特别的，如果存在一种选定 $k$ 座城市的方式使得无论如何修建道路都总存在某座城市无法到达这 $k$ 座城市中的任意一座，请输出 `-1`。

否则输出一行一个整数表示答案对 $998244353$ 取模的结果。

hint:
#### 样例 1 解释

总共有三种选定集合城市的方案：

1. 选定集合在城市 $1$，那么选择建造 $2\to 1,3\to 1$ 两条道路花费最少，为 $2+4=6$。

2. 选定集合在城市 $2$，那么选择建造 $1\to 2,3\to 1$ 两条道路花费最少，为 $1+4=5$。

3. 选定集合在城市 $3$，那么选择建造 $1\to 2,2\to 3$ 两条道路花费最少，为 $1+3=4$。

所以期望最小花费为 $(6+5+4)/3=5$。

#### 样例 2 解释

有 $6$ 种选择集合城市的方法：

1. 选城市 $1,2$，最小花费 $9$。

2. 选城市 $1,3$，最小花费 $6$。

3. 选城市 $1,4$，最小花费 $7$。

4. 选城市 $2,3$，最小花费 $5$。

5. 选城市 $2,4$，最小花费 $6$。

6. 选城市 $3,4$，最小花费 $3$。

所以期望最小花费为 $(9+6+7+5+6+3)\div 6=6$。

#### 样例 3 解释

这里太小写不下，只配个图算了：

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

#### 样例 4 解释

当集合城市选在 $1,2,3$ 时，城市 $4$ 无论如何都无法达到 $1,2,3$ 中的任意一个，所以答案为 $-1$。

#### 数据范围

对于 $10\%$ 的数据，满足 $n\le 15$，$m\le 30$。

对于 $30\%$ 的数据，满足 $n\le 20$，$m\le 50$。

另有 $5\%$ 的数据，满足所有 $w_i$ 相等。

另有 $5\%$ 的数据，满足 $k=n$。

另有 $5\%$ 的数据，满足 $k=n-1$。

另有 $10\%$ 的数据，满足 $m=n$。

另有 $20\%$ 的数据，满足 $k=1$。

对于 $100\%$ 的数据，满足 $2\le n\le 10^5$，$1\le m\le 2\times 10^5$，$1\le k\le n$，$1\le u_i,v_i\le n$，$0\le w_i\le 998244352$。


title: Reverse and Rotate

description:
给定一个字符串 $S$ 和 $n$ 次操作，每次操作为以下 $3$ 种形式之一：

1. `< x` 表示将 $S$ 向左循环移动 $x$ 位。例如：$\mathtt{abcde}$ 执行 `< 2` 后变成 $\mathtt{cdeab}$。

2. `> x` 表示将 $S$ 向右循环移动 $x$ 位。例如：$\mathtt{abcde}$ 执行 `> 2` 后变成 $\mathtt{deabc}$。

3. `rev` 表示将 $S$ 翻转。例如：$\mathtt{abcde}$ 执行 `rev` 后变成 $\mathtt{edcba}$。

求 $S$ 在**依次**执行这 $n$ 次操作后得到的字符串 $S'$。

注：对于 $S=s_0s_1\cdots s_{k-1}$，将其向左循环移动 $x$ 位，会变成 $s_{-x}S_{-x+1}\cdots S_{-x+k-1}$；向右循环移动 $x$ 位，会变成 $s_{x}S_{x+1}\cdots S_{x+k-1}$。对于 $x\equiv y\pmod k$，有 $s_x=s_y$。

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

第二行一个整数 $n$。

接下来 $n$ 行，每行一个操作。

outputFormat: 一行一个字符串 $S'$，表示**依次**执行 $n$ 次操作后得到的字符串。

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

- 原字符串为 $\mathtt{abcde}$；
- 第一次操作后，字符串变为 $\mathtt{deabc}$；
- 第二次操作后，字符串变为 $\mathtt{cbaed}$；
- 第三次操作后，字符串变为 $\mathtt{aedcb}$。

**【数据规模与约定】**

记 $|S|$ 表示字符串 $S$ 的长度。

| 测试点编号 | 特殊性质 |
| :----------: | :----------: |
| $1\sim3$ | $\vert S\vert,n,x \le 1000$ |
| $4$ | 没有 `rev` 操作 |
| $5$ | $S=\mathtt{aa...abb...b}$ |
| $6\sim10$ | 无 |

对于 $100\%$ 的数据，$1 \le |S|,n \le 10^6$，$0 \le x \le 10^9$，$S$ 仅由小写字母组成。


title: [yLOI2023] 腐草为萤

background:
> 于盛夏之末，入夜仍灼热。
> 又一场离合，开始凄恻。
> 是扇底闪躲，或雨水摧折。
> 哪里都值得，恋恋不舍。

——银临《腐草为萤》

description:
夜幕降临，在树林中的一条平直的小径上，萤火虫们受到夜晚的呼唤，纷纷外出行动。

将小径视作数轴，一开始，共计 $n$ 只萤火虫在数轴的一些整点上，从左到右依次标号为 $1 \sim n$，第 $i$ 只萤火虫的初始坐标为 $x_i$。每个萤火虫有不同的亮度值，$i$ 号萤火虫的亮度为 $a_i$。

在任意时刻，对任意存活的萤火虫 $i$，它会按如下规则飞行：

- 在当前仍存活的萤火虫中，找到与 $i$ 相邻的萤火虫（可能是一只或两只）中亮度最大的一只，记其编号为 $j$。如果 $a_i < a_j$，则 $i$ 会朝着 $j$ 飞行，否则 $i$ 留在原地。
- 这里两只萤火虫『相邻』的定义是：若两只萤火虫之间不存在任何仍存活的萤火虫，则它们相邻。
- 萤火虫飞行的速度均为每秒一个单位长度。

萤火虫生命短暂，当两只萤火虫相遇之时（即两个萤火虫的坐标相同时），亮度值较低的萤火虫将耗尽生命，在小径上消失。显然，最后只会剩余 $1$ 只萤火虫。对其余的每只萤火虫，请分别求出它们耗尽生命时的坐标。

inputFormat:
第一行是一个整数，表示萤火虫数量 $n$。
第二行有 $n$ 个整数，第 $i$ 个整数表示标号为 $i$ 的萤火虫初始坐标 $x_i$。数据保证 $x_i$ 单调递增。
第三行有 $n$ 个整数，第 $i$ 个整数表示标号为 $i$ 的萤火虫的亮度值 $a_i$。数据保证亮度值互不相同。

outputFormat: 输出一行 $n$ 个以单个空格隔开的整数，第 $i$ 个整数表示编号为 $i$ 的萤火虫生命耗尽时的坐标。如果 $i$ 号萤火虫最后存活下来了，则第 $i$ 个数输出 0。

hint:
### 样例 1 解释

- 在第一秒时，标号为 $1$ 的萤火虫向右移动，标号为 $2$ 的萤火虫位置不变，标号为 $3$ 的萤火虫向右移动，标号为 $4$ 的萤火虫位置不变。
- 第二秒开始时，萤火虫 $1$ 遇到萤火虫 $2$，前者亮度更低，耗尽生命，此时其坐标为 $2$；萤火虫 $3$ 遇到萤火虫 $4$，前者亮度更低，耗尽生命，此时其坐标为 $4$。
- 接下来，萤火虫 $2$ 向右移动，直到在坐标 $4$ 遇到萤火虫 $4$，耗尽生命。

### 数据规模与约定

- 对于 $5\%$ 的数据，$n = 2$。
- 对于 $30\%$ 的数据，$n \leq 100$，$x_i \leq 200$。
- 对于 $60\%$ 的数据，$n \leq 10^3$。
- 另有 $5\%$ 的数据，满足特殊约定 A。
- 另有 $5\%$ 的数据，满足特殊约定 B。
- 对 $100\%$ 的数据，保证 $2 \leq n \leq 5 \times 10^5$，$1 \leq x_i \leq 10^9$，$1 \leq a_i \leq n$。且 $x_i < x_{i + 1}$，$a_i$ 是长度为 $n$ 的排列。

其中：

- 特殊约定 A：数列 $a$ 单调递增。
- 特殊约定 B：数列 $a$ 是单峰的，仅有一个极大值。即：存在 $p$ 满足 $1 \leq p < n$，使得 $a_1 \sim a_p$ 单调递增，$a_p \sim a_n$ 单调递减.

### 提示

- **请注意大量数据的读入输出对程序效率造成的影响，选择合适的读入输出方式，避免超时**。
- **请注意时间复杂度的常数因子对程序运行效率造成的影响**。

### 说明

本题共有 7 个附加样例文件，见题目附件中的 glowworm.zip。


title: 无限循环？

background:
你是一只小青蛙。

你被关进了塞拉飞舞监狱。

生活有点压抑，小青蛙幻想自己走出了塞拉飞舞监狱。

生活过于压抑，小青蛙开始反抗塞拉飞舞监狱。

小青蛙孤立无援，又被关进了塞拉飞舞监狱。

……

循环不是无限的。如此往复，总有一天，他会将塞拉飞舞这黑暗的牢笼冲破！

description:
小青蛙暂时被困在了循环里，这个循环可以看作一个有 $n$ 个点的环（$n$ 为奇数），每个点 $i$ 有点权 $a_i$。

对于所有的 $1 \leq i < n$，点 $i$ 和点 $i+1$ 之间有一条边，边权为 $w_i$；点 $1$ 和点 $n$ 之间有一条边，边权为 $w_n$。

这个环的边权和点权有奇妙的关系：对于任意一条边 $i$，其边权 $w_i$ 都必然满足关系 $w_i=\dfrac12(a_i+a_{i+1})$，其中 $w_n=\dfrac12(a_1+a_{n})$，当环中任意一条边的边权改变的时候，它的所有点点权会**随之改变**，直到所有点权都能与边权满足上述关系。

现在青蛙掌握了 $w_1\sim w_n$ 的值，而且他可以交换其中任意两条边的权值任意次（即任意打乱边权）。现在青蛙需要给出两组安排 $w_1\sim w_n$ 的方案，分别使得 $1$ 号点点权**在所有的排列方案中最大** / **最小**。

然而由于青蛙陷入了无限循环，他的脑子十分混乱，于是他向你寻求帮助，你需要帮他构造这样两组方案。

**题目保证 $\boldsymbol n$ 为奇数**。

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

第二行共 $n$ 个整数，第 $i$ 个数 $w_i$ 表示第 $i$ 条边的权值。

outputFormat:
两行，每行 $n$ 个整数表示答案。

第一行 $n$ 个整数从 $w_1'\sim w_n'$ 表示一组方案使得 $1$ 号点权值最大。

第二行 $n$ 个整数从 $w_1''\sim w_n''$ 表示一组方案使得 $1$ 号点权值最小。

本题采用 `special judge` 评测，也就是说，如果有多种可能的答案，你可以输出任意一种。

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

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

其中红色数字表示点权，黑色数字表示边权，蓝色数字表示点的编号。

可以证明，这种方案下的 $1$ 号点权既最小，又最大。

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

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

其中红色表示点权，黑色表示边权，蓝色表示点的号码。

可以证明，这两种方案下的 $1$ 号点权分别取到最大和最小。需要注意的是，这**不一定**是**唯一解**。

---

**【数据规模与约定】**

**本题开启捆绑测试。**

| $\text{Subtask}$ | 数据范围 | 分数 | 特殊性质 |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $n=3$ | $20$ | $\rm A$ |
| $2$ | $n=3$ | $20$ | 无 |
| $3$ | $n\leq 10^6$ | $20$ | $\rm B$ |
| $4$ | $n\leq 10^6$ | $20$ | $\rm C$ |
| $5$ | $n\leq 10^6$ | $20$ | 无 |

- 特殊性质 $\rm A$ ：保证 $\{w\}$ 是由 $\{-1,0,1\}$ 任意打乱之后得到的一个序列。
- 特殊性质 $\rm B$ ：保证 $n \ge 3$，且对于所有 $i\in [2,n]$，有 $w_i$ 相同。
- 特殊性质 $\rm C$ ：保证 $n\ge 3$，且对于所有 $i\in [3,n]$，有 $w_i$ 相同。
- 对于 $100\%$ 的数据， $1\leq n\leq 10^6$ 且为奇数， $|w_i|\leq 10^9$。


title: 【MX-X3-T3】「RiOI-4」GCD 与 LCM 问题

background:
「既然你说你不了解她，为什么又可以断言她一定是因为……」

是呀，自己对零羽还了解的确实不够多……泠珞这样想着。

在残缺的记忆当中，她只能想起，她和零羽的最大公约数，就是「音乐」。

还缺了什么呢？泠珞不知道。她只知道，那所缺失的，和「音乐」加起来，就是她的一切。一切的总和。

**滴答，滴答**。叮咚，叮咚。如果把长短不一、断断续续的钢琴声拼接在一起，能够回忆起什么吗。

description:
给定一个正整数 $a$，请你构造三个正整数 $b,c,d$ 使得 $a+b+c+d=\gcd(a,b)+\operatorname{lcm}(c,d)$。一个测试点内有多组数据。

由于出题人想把自己 QQ 号写题目里，你需要保证 $b,c,d\le 1\,634\,826\,193$。

**如有多种可能的答案，输出任意一个均可。**

inputFormat:
**第一行一个正整数 $t$ 表示数据组数。**

接下来 $t$ 行每行一个正整数 $a$。

outputFormat:
输出 $t$ 行，每行三个正整数 $b,c,d$。

**如有多种可能的答案，输出任意一个均可。**


title: 「RiOI-2」hacker

background:
在小树丛边坐落着一个幻想的城堡。这里是 E 国的领地，而小 E，则是 E 国之王。

现在，伟大的 E 国之王正在披挂出征。

不过听说 E 国之王遇见了两个叫 ACCEPT 和 BOTH 的人，他们是谁？

description:
现在有正整数 $n$，有以下操作；

- 「ACCEPT」。花费 $1$ 的代价，将 $n$ [二进制](https://oi-wiki.org/math/base/#%E4%BA%8C%E8%BF%9B%E5%88%B6)**按位或**上 一个正整数。
- 「BOTH」。花费 $1$ 的代价，将 $n$ [二进制](https://oi-wiki.org/math/base/#%E4%BA%8C%E8%BF%9B%E5%88%B6)**按位与**上 一个正整数。

两种操作均可使用多次（或不用），请求出将 $n$ 变为 $m$ 最小的代价。

[帮助：什么是按位与和按位或](https://oi-wiki.org/math/bit/#%E4%B8%8E%E6%88%96%E5%BC%82%E6%88%96)

inputFormat:
**本题有多组数据。**

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

接下来 $T$ 行，每行两个正整数 $n, m$ 以空格隔开。

outputFormat: 输出 $T$ 行，每行一个整数，表示答案。


title: 「GLR-R4」夏至

background:
  「柳庭风静人眠昼，昼眠人静风庭柳」

---

  老 V 说为大家准备了特别的粽子，所以天依来了；

  天依来了，所以阿绫来了；

  阿绫来了，龙牙也不敢不来；

  到了快一半了，于是剩下的大家都来了……

  所以，为什么要在模拟演出训练结束后来补文化课啊！

  “天依，这数学老师真的在讲数学？”

  “摩柯，我和阿绫就靠你了！”天依戳戳前排摩柯的肩膀。

  “要推出来了，要推出来了……”，摩柯大概是第一次把草稿纸写得快满，“我知道我很急，但我先别急……这像是在做噩梦一样。”

---

  **夏至** 「允许我这一次片刻逃离　偶尔也试着用背影　去面对未来不确定」

description:
  为了鉴定摩柯是不是在做噩梦，请你来解决黑板上的一道简单的数学问题吧！

  令积性函数 $f(n)$ 满足 $f(p^c)=p^{\gcd(c,k)}$，其中 $k$ 为给定常数，$p$ 为素数，$c$ 为正整数。现在，给定 $n,m,k$，请求出
$$
\left(\sum_{i=1}^n\sum_{j=1}^mf(i\cdot j)\right)\bmod(10^9+7).
$$

  对于积性函数的定义，请参考「题意解释」。

inputFormat: 输入只有一行包含三个整数，分别表示 $n,m,k$。

outputFormat: 一行一个整数，表示答案对 $10^9+7$ 取模后的值。


title: [yLOI2023] 云梦谣

background:
> 归来且做云梦梦一场 大梦好
> 栽花闻酒香 醒醒醉醉笑笑
> 天地偌大复路远山高 最难得偷半日逍遥
> 偶尔糊涂不问世事不知晓

——银临 & 慕寒《云梦谣》

description:
“喂，枸杞，你这只笨狗，又偷吃！看我不收拾你！”

朵一气呼呼地从院子里跑出来，手中握着掸子，而枸杞早已不见踪影。

云梦庭可以看作一个 $n$ 行 $m$ 列的方格阵，第 $i$ 行第 $j$ 列的格子被记作 $(i,j)$。每个格子 $(i,j)$ 要么有一个高度 $h_{i,j}$（$h_{i,j}$ 为正整数），要么是障碍物，不能通过。（方便起见，约定障碍物的 $h_{i,j}$ 用 $0$ 表示。）另外，云梦庭上有 $k$ 个指定的格子上可以进行**御剑飞行**。开始时，朵一和枸杞分别位于方格 $(1,1)$ 和 $(n,m)$。

朵一的御剑飞行还不是很熟练，现在她还控制不好御剑的高度。因此在任意时刻，朵一在方格 $(i,j)$ 上可以做如下行动之一：

- 移动到与该方格相邻的方格 $(i-1,j)$、$(i+1,j)$、$(i,j-1)$、$(i,j+1)$ 之一上（不能移动出方格边界，也不能移动到障碍物上）；
- 如果方格 $(i,j)$ 上允许御剑飞行，则朵一可以御剑飞行至另一个**同样允许御剑飞行且与方格 $(i,j)$ 高度相等的方格上**；
- 使用仙法将当前格子的高度 $h_{i,j}$ 改变为任一正整数。

进行上述每项行动均需花费 $1$ 个单位时间。

“哼，笨狗子你再跑！”说罢，朵一便追了出去。朵一接下来还要尽快继续今天的修行，因此她想知道到达 $(n,m)$ 格子所需的最短时间是多少。

inputFormat:
输入的第一行有三个整数，依次表示方格阵的行数 $n$、列数 $m$ 和能御剑飞行的方格个数 $k$。
接下来 $n$ 行，每行 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数表示方格 $(i,j)$ 的高度 $h_{i,j}$。数据保证 $h_{1,1}$ 和 $h_{n,m}$ 不为 $0$。
接下来 $k$ 行，每行两个整数 $x$ 和 $y$，表示一个允许御剑飞行的方格的坐标 $(x, y)$。数据保证这 $k$ 个方格的坐标互不相同。

outputFormat: 一行一个整数，表示朵一到达 $(n,m)$ 所需的最小时间。如果朵一无法到达，输出 ```-1```。

hint:
### 样例 1 解释

第 $1$ 个单位时间，朵一将当前方格 $(1,1)$ 的高度修改为 $4$；
第 $2$ 个单位时间，朵一从方格 $(1,1)$ 御剑飞行至 $(3,4)$；
第 $3$ 个单位时间，朵一从方格 $(3,4)$ 移动到 $(4,4)$，追上了枸杞。

### 样例 2 解释

第 $1$ 个单位时间，朵一从方格 $(1,1)$ 御剑飞行至 $(4,1)$；
第 $2$ 个单位时间，朵一从方格 $(4,1)$ 移动到 $(4,2)$；
第 $3$ 个单位时间，朵一从方格 $(4,2)$ 移动到 $(4,3)$；
第 $4$ 个单位时间，朵一从方格 $(4,3)$ 移动到 $(4,4)$，追上了枸杞。

### 数据规模与约定

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

对全部的测试点，保证 $1 \leq n, m \leq 3 \times 10^3$，$0 \leq k,h_{i,j} \leq n \times m$。
### 提示

请注意大量数据读入对程序效率造成的影响，选择合适的读入方式，避免超时。

### 说明

本题共有 5 个附加样例文件，见附件里的 dream.zip。

### 后记

不过，别看朵一现在一副生气的样子，可当她追上枸杞后，大抵是不舍得真的动手吧。“嘿嘿，今日的修行结束后，该吃什么好呢？”在这飞瀑悬挂、翠竹怀抱的云梦庭中，修仙炼体，不羡尘嚣，应是这世上最逍遥的事了。


title: 「RiOI-03」3-2

background: > Heart beat to death[.](https://www.luogu.com.cn/problem/P9304)

description:
给定一个正整数 $n$。将 $[0,2^n)$ 中每个整数的二进制最低 $n$ 位**从低到高**依次写在一个 $2^n\times n$ 的矩阵上。**矩阵两维的下标都从 $0$ 开始。** 如，当 $n=3$ 时，矩阵是这样的：

![](https://cdn.luogu.com.cn/upload/image_hosting/5f6v9pru.png?x-oss-process=image/resize,m_lfit,h_200,w_265)

给定 $q$ 次询问，每次询问这个矩阵下标为 $(x,y)$ 的格子所在的四连通块大小对 $998244353$ 取模的值。

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

接下来 $q$ 行，每行两个非负整数 $x,y$，表示一次询问。

outputFormat: 输出 $q$ 行，每行一个正整数，表示每次询问答案对 $998244353$ 取模的值。


title: [yLOI2023] 苦竹林

background:
> 悬挂在屋檐下的风铃，摇晃的声音很动听。
> 思念就像梅雨下不停，我的心境一片泥泞。
> 散落在天际里的繁星，闪烁着你我的宿命。
> 当枫叶轻盈落入湖心，近看山水一片宁静。

——银临 & 涵昱《苦竹林》

description:
共有 $n$ 个风铃悬挂在屋檐下，每个风铃都能发出一定音调的声音。从左到右给风铃从 $1$ 至 $n$ 编号，第 $i$ 个风铃的音调是 $a_i$。

为了表达内心的思念，扶苏决定在 $n$ 个的风铃中取出 $m$ 个，送给远方的朋友。

请你找到最小的整数 $\varepsilon$，使得存在一种方案，能够从 $n$ 个风铃中挑出 $m$ 个，设挑出风铃的音调为 $b_1, b_2, \dots b_m$，满足对任意的 $1 \leq i, j \leq m$，都有 $|b_i - b_j| \leq \varepsilon$。

inputFormat:
第一行是两个整数，表示风铃的个数 $n$ 和挑选出风铃的个数 $m$。
第二行有 $n$ 个整数，表示每个风铃的音调。第 $i$ 个整数表示 $a_i$。

outputFormat: 输出一行一个整数，表示最小的 $\varepsilon$。

hint:
### 样例 2 解释

一种选择的方案是选择第 $2,4,5,6$ 四个风铃，音调依次为 $7,3,4,6$。可以得到对任何的 $1 \leq i, j\leq 4$，都有 $|b_i - b_j| \leq 4$。

另一种方案是选择第 $2,3,5,6$ 四个风铃，同样计算得到的 $\varepsilon$ 为 $4$。

### 数据规模与约定

- 对 $10\%$ 的数据，$m = 2$。
- 另有 $10\%$ 的数据，$m = n$。
- 对 $40\%$ 的数据，$n \leq 5$。
- 对 $60\%$ 的数据，保证对所有的 $2 \leq i \leq n$，满足 $a_{i - 1} \leq a_i$，即 $a_i$ 单调不降。
- 对 $80\%$ 的数据，$n \leq 10^3$。
- 对 $100\%$ 的数据，$2 \leq m \leq n \leq 10^5$，$1 \leq a_i \leq 10^9$。

### 说明

本题共有三个附加样例文件，见题目附件中的 `ring.zip`。


title: [yLOI2022] 枕万梦

background:
> 岁月冥冥之中 星移物换 将韶华歌颂
> 人潮冥冥之中 一眼望穿 日月去无踪
> 你我冥冥之中 心有灵犀 何止几万梦
> 忘情在这久违的重逢
> 天地冥冥之中 云烟奔涌 摩肩又接踵
> 万籁冥冥之中 不肯缄默 盛大到无穷
> 你我冥冥之中 对坐天涯 灵犀才一动
> 就相遇在咫尺的时空

银临《枕万梦》

description:
天亮了，扶苏不敌困意，早早地进入了梦乡。在失去引力的梦里，扶苏遇到了好多串漂浮着的数列，它们的长度都相等，而且都是美妙的等比数列！出于本能，扶苏想要把这些数列按照字典序排序，可是在梦里扶苏失去了思考的能力，请你来帮帮她！

具体地，有 $n$ 个编号从 $1$ 到 $n$ 的数列 $a_1, a_2, \dots a_n$，每个数列的长度均为 $m + 1$。第 $i$ 个数列 $a_i$ 满足递推式 $a_{i,j} = a_{i,j - 1} \times i$，其中 $1 \leq j \leq m$。而扶苏会告诉你每个序列的首项 $a_{i,0}$，你需要帮助她把这些数列按字典序排序。

inputFormat:
输入的第一行是两个整数，依次表示 $n$ 和 $m$。
接下来 $n$ 行，每行一个整数，第 $i$ 行的整数表示数列 $a_i$ 的首项 $a_{i,0}$。

outputFormat: 输出一行 $n$ 个整数，第 $i$ 个整数表示字典序第 $i$ 小的数列的**编号**。

samples:
见附加文件中的 B4.in
见附加文件中的 B4.ans

hint:
### 样例 1 解释

共有两个数列，每个数列的长度均为 $2+1=3$。

对第一个数列 $a_1$：
- 已知其首项 $a_{1,0} = 1$。
- 根据 $a_{i,j} = a_{i,j - 1} \times i$，取 $i=1,j = 1$ 可以得到 $a_{1,1} = a_{1,0} \times 1 = 1$。
- 根据 $a_{i,j} = a_{i,j - 1} \times i$，取 $i=1,j = 2$ 可以得到 $a_{1,2} = a_{1,1} \times 1= 1$。

所以数列 $a_1$ 是 $1,1,1$。

对第二个数列 $a_2$：
- 已知其首项 $a_{2,0} = 2$。
- 根据 $a_{i,j} = a_{i,j - 1} \times i$，取 $i=2,j = 1$ 可以得到 $a_{2,1} = a_{2,0} \times 2 = 2 \times 2 = 4$。
- 根据 $a_{i,j} = a_{i,j - 1} \times i$，取 $i=2,j = 2$ 可以得到 $a_{2,2} = a_{2,1} \times 2= 4 \times 2 = 8$。

所以数列 $a_2$ 是 $2,4,8$。

比较字典序可得数列 $a_1$ 是字典序最小的数列。所以输出 $1$。

### 样例 2 解释

数列 $a_1$ 为 $1,1,1,1$，数列 $a_2$ 为 $-1, -2,-4,-8$。

### 数据规模与约定
本题共 $10$ 个测试点，各测试点信息如下表：

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

特殊约定 A：保证 $a_{i,0}$ 均相等。
特殊约定 B：保证 $a_{i,0}$ 互不相等。

对全部的测试点，保证 $1 \leq n \leq 10^5$，$1 \leq m \leq 10^9$，$1 \leq |a_{i,0}| \leq 10^9$。

### 提示

对两个数列 $a_i, a_j$，按如下方式比较其字典序：

找到**最小的**满足 $a_{i,p} \neq a_{j, p}$ 的下标 $p$，比较 $a_{i, p}$ 和 $a_{j, p}$ 的大小：

- 如果 $a_{i,p} < a_{j, p}$，则称 $a_i$ 的字典序比 $a_j$ 的小。
- 如果 $a_{i,p} > a_{j, p}$，则称 $a_i$ 的字典序比 $a_j$ 的大。

可以证明，在本题的限制下，这样的 $p$ 一定存在。


title: 「HCOI-R1」孤独的 sxz

background: sxz 不擅长与人交往，于是他平常都喜欢找偏僻的地方坐着。今天，sxz 来到了食堂，他依旧想找一个偏僻的地方坐着，让他与其他所有人的曼哈顿距离之和最大。

description:
食堂的座位可以看成一个被划分为 $n\times m$ 的格子的矩形，长为 $n$，宽为 $m$，矩形内的每一个格子 $(i, j)(i \in [1, n], j \in [1, m])$ $(i,j$ 为整数$)$ 都是一个座位。

现在，食堂里已经有了 $k$ 个人，其中第 $i(1 \leq i \leq k)$ 个人坐在 $(x_i, y_i)$ 处。sxz 想要找到一个座位，使得该座位与 $k$ 个人的曼哈顿距离之和最大。请你帮他找到这个最大值，剩下的就交给 sxz 吧！

假设 sxz 坐在点 $(a,b)$，那么他和 $k$ 个人的曼哈顿距离之和是 $\sum_{i=1}^{k}|a-x_i|+|b-y_i|$。

**很显然，sxz 不能和 $\bm k$ 个人中的任何一个人坐在同一个地方**。

inputFormat:
第一行包含三个整数 $n, m, k$。

接下来 $k$ 行，第 $i$ 行两个整数描述 $x_i, y_i$。

outputFormat: 仅一行一个整数，描述这个值。注意它可能很大。

hint:
### 样例解释 1

最佳位置为 $(2,5)$，对于 $3$ 个人的曼哈顿距离分别为 $5, 3, 2$。

### 数据规模与约定

**本题采用捆绑测试。**
+ Subtask 0（15 pts）：$n, m \leq 100$。
+ Subtask 1（25 pts）：$n, m \leq 10000$。
+ Subtask 2（20 pts）：$k = 3$。
+ Subtask 3（40 pts）：无特殊限制。

对于所有数据，$1 \leq n, m \leq 10^9$，$1\leq k \leq \min\{4 \times 10^5, n\times m-1\}$，$1 \leq x_i \leq n$，$1 \leq y_i \leq m$，保证所有 $(x_i, y_i)$ 互不相同。


title: 『GROI-R2』 紫水晶

description:
爱丽丝不曾忘记过她曾经存在于纸牌的世界。

于是魔法让她的手里出现了一些牌，同时魔法也让坦尼尔手里出现了一些牌，而且每张牌上都写着一个正整数——尽管他们如今所处的，是玻璃王国的世界中。

牌张很快一消而散，而他们也准备启程。爱丽丝只记住了每相邻两张牌的**最大公约数之和**，坦尼尔只记住了每相邻两张牌的**最小公倍数之和**。

你还在这个宫殿里，你想重现当时的牌张。

**形式化题面**

给定 $q$ 次询问，每次询问为以下两种之一：

- ``1 n x`` 表示要求输出一长度为 $n$ 的**正整数**序列 $\{a_n\}$，使得 $\sum\limits_{i=1}^{n-1} \gcd(a_i,a_{i+1})=x$。

- ``2 n x`` 表示要求输出一长度为 $n$ 的**正整数**序列 $\{a_n\}$，使得 $\sum\limits_{i=1}^{n-1} \operatorname{lcm}(a_i,a_{i+1})=x$。

且对于任意输出的 $a_i$ 不应超出 C++ 语言中 ``int`` 的存储范围。

其中 $\gcd$ 和 $\operatorname{lcm}$ 分别为最大公约数和最小公倍数，如有多解，输出任意一个即可。如果无解，输出 ``-1``。

inputFormat:
第一行输入一个正整数 $q$ 表示询问次数。

接下来 $q$ 行，每行输入三个正整数 $op,n,x$。

- 当 $op=1$ 时表示爱丽丝的牌张数为 $n$，她记住的和为 $x$，要求还原她的牌张。

- 当 $op=2$ 时表示坦尼尔的牌张数为 $n$，他记住的和为 $x$，要求还原他的牌张。

outputFormat:
一共 $q$ 行，每行输出一个整数序列对应每次询问你构造的牌张序列，序列中相邻的两个数用一个空格隔开。

如有多解，你可以输出任意一个。如果无解，输出 ``-1``。


title: 「蓬莱人形」

background:
不老不死的妹红，还能称之为「人类」吗？

超脱了生死的人类，本来就是不可思议的啊。

description:
为了证明人类的可能性，你需要解决一个问题。

给定序列 $a=[a_1,a_2,\cdots,a_n]$。现在有 $q$ 次询问：

- 每次给定二元组 $(x,y)$、模数 $m$，以及一个区间 $[l,r]$。求出有多少 $i\in [l,r]$ 满足 $(a_i+x)\bmod m<(a_i+y)\bmod m$。

inputFormat:
第一行有两个正整数 $n, q$，表示序列长度及询问次数。

第二行有 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，描述序列 $a$。

接下来 $m$ 行，每行有五个整数 $l_i,r_i,x_i,y_i,m_i$，描述一组询问。

outputFormat: 输出共 $m$ 行。第 $i$ 行输出第 $i$ 次询问的结果。

hint:
### 样例解释

- 对于第一组询问，符合条件的元素的下标为 $1, 2, 7, 8$；
- 对于第二组询问，没有符合条件的元素；
- 对于第三组询问，符合条件的元素的下标为 $2, 3, 4, 5, 6, 7$；
- 对于第四组询问，符合条件的元素的下标为 $5, 6, 9$；
- 对于第五组询问，符合条件的元素的下标为 $1, 2$。

### 数据范围及约定

对于全部数据，$1\le n\le 10^5$，$1\le q\le 5\times 10^5$，$1\le a_i,x_i,y_i,m_i\le 10^5$，$1\le l_i\le r_i\le n$。


title: [入门赛 #9] 神树大人挥动魔杖 (Hard Version)

background: **本题与 Easy Version 题意完全相同，仅有 $n,k$ 的数据范围有所不同。**

description:
神树大人挥动魔杖，召唤出了 $9 \times 10^{n-1}$ 只家养小精灵。每只家养小精灵都有一个互不相同的 $n$ 位数编号 $a_i$。

神树大人希望将这些家养小精灵分为 $k$ 组。第 $p$ 组的所有家养小精灵满足编号 $a_i$ 对 $k$ 取模余 $p-1$，即 $a_i \equiv p-1 \pmod k$。

神树大人想要知道，每一组小精灵分别有多少只。由于答案可能很大，你只需要输出答案对 $100,000,007$ 取模的结果

inputFormat: 输入共一行两个整数，依次为 $n,k$。

outputFormat: 输出一行 $k$ 个整数，由空格分隔。第 $i$ 个整数代表第 $i$ 组小精灵的个数。


title: [语言月赛202302]  最澄澈的空与海

type: B

background:
材料 1：

> 请小心地计算下面的算式：$138 - 108 \div 6 = ?$
>
> 你大概难以置信，这个算式的计算结果竟然是 $5!$

材料 2：

> 对于一个正整数 $x$，$x! = 1 \times 2 \times \cdots \times (x - 1) \times x$。我们称 $x!$ 为 $x$ 的阶乘。
>
> 特别的，$0! = 1$。

显然，「$138 - 108 \div 6 = 5$」是错误的，而「$(138 - 108) \div 6 = 5$」是正确的，所以对材料 1 中的内容，部分读者会认为「作者没有搞清加减乘除的运算优先级关系而犯错」。

然而，材料 1 最后一行的叹号并不是标点符号，而是材料 2 提到的「阶乘」。

考虑到这一点，「$138 - 108 \div 6 = 5! = 1 \times 2 \times \cdots \times 5 = 120$」显然就是正确的了。

description:
有关「上述等式为何正确」的问题解决了，然而「如何构造出上述那种让人啼笑皆非的正确等式」成为了一个新的问题。

我们认为这个问题太难了，因此我们把解决这个问题的任务交给了你，相信你可以完成这个任务。

我们会给你一个整数 $n$，请你帮助求出一组整数 $x, y, z$，满足 $x - y \div z = n!$ 且 $(x - y) \div z = n$。

---

实际上可以发现，当 $z = 2$ 时，原式变为 $\begin{cases} x - \cfrac y2 = n! \\ \cfrac x2 - \cfrac y2 = n\end{cases}$，这时，只需要让 $x = 2 \times (n! - n)$，并根据任何一个式子计算出 $y$ 的值（为 $2 \times (n! - 2n)$），即可构成一组合法答案。这样的答案是总是存在的。

因此，按照我们给出的这种方式直接输出 $2 \times (n! - n)$、$2 \times (n! - 2n)$、$2$ 即可通过本题，难点便来到了计算出对应的值上。

当然，你也可以使用其他方法计算出符合要求的 $x, y, z$。

inputFormat: 输入共一行一个整数 $n$。

outputFormat:
输出共一行三个整数 $x, y, z$，代表满足 $x - y \div z = n!$ 且 $(x - y) \div z = n$ 的一组整数。

三者两两之间以一个空格隔开。

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

对于 $100\%$ 的数据，保证 $0 \leq n \leq 11$。

我们会使用自定义校验器检验你的答案是否正确，因此如果有多组答案，你可以输出其中任意一组。

你需要保证 $x, y, z$ 均为整数且 $-10 ^ {18} \leq x, y \leq 10 ^ {18}$，$1 \leq z \leq 10 ^ {18}$，否则自定义校验器将直接认定您的答案错误。

请注意式子中的 $\div$ 不是向下取整的整除，这显然意味着你需要保证 $y \div z$ 和 $(x - y) \div z$ 为整数。

容易证明，满足条件的 $x, y, z$ 一定存在。


title: 梦幻 | Reopening of  Dream

background:
_望你没有因此而功亏一篑过_

花开不是为了花落，而是为了更加灿烂。

最初拥有的只是理想和自信，但所有的一切都从这里交错着生长，在努力与汗水铺成的路上走下去不会是错误的选择——至少你为此喜怒哀乐过。

**祝每一位有理想的参赛者都能取得理想的成绩！**

description:
PION2202 的选手代码公布了。作为一个~~连续编写了十年迷惑行为大赏~~的人，你当然是要抢先把代码中的各种事迹发出来啦。

首先关注的肯定是大家的文件输入输出有没写对。你已经让小 E 把每道题的题目名称和每位选手的 `freopen` 语句整理出来了。

PION2202 一共有 $m$ 道题，有 $n$ 位选手参与。你决定把选手分成三类：

1. 普通人：最正常不过的 `freopen` 语句；
2. 见祖宗人：被注释的 `freopen` 语句；
3. 乐子人：其他形式的 `freopen` 语句。

形式化地，普通人的所有题目的 `freopen` 语句都应该恰好是

```cpp
freopen("<title>.in","r",stdin);
freopen("<title>.out","w",stdout);
```

其中的 `<title>` 应替换成对应的题目名称。

见祖宗人的 `freopen` 语句中存在至少一道题的至少一行语句以 `//freopen(` 开头，以 `);` 结尾。

如果一位选手的 `freopen` 语句不满足上面两种情况，则称这位选手为乐子人。

你需要判断每位选手是普通人，见祖宗人还是乐子人。

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

第二行两个正整数 $n,m$，分别表示选手数和题目数。

接下来 $m$ 行，每行包含一个仅由小写字母构成的字符串，其中第 $i$ 行表示第 $i$ 道题目的题目名称。保证题目名称的长度在 $1$ 到 $10$ 之间。

接下来 $n\times(2m+1)$ 行，在每 $2m+1$ 行中，第一行为空行，后 $2m$ 行表示一位选手的所有题目的 `freopen` 语句，按照题目顺序给出。前两行为第一题的 `freopen` 语句，依次类推，最后两行为最后一题的 `freopen` 语句。

保证所有的 `freopen` 语句的每个字符的 ASCII 码均在 $33$ 到 $126$ 之间，即不含空格等不可见字符。

保证每一行 `freopen` 语句的长度在 $1$ 到 $100$ 之间。

outputFormat:
输出 $n$ 行，其中第 $i$ 行表示第 $i$ 位选手的分类。

如果是普通人，就要祝他 RP++，所以就输出一行 `PION2202 RP++.`。

如果是见祖宗人，那就只好输出一行 `Wrong file operation takes you to your ancestors along with your 3 years' efforts on OI.`。

如果是乐子人，就祝他在玩得开心的同时注意不要弄错了，于是输出一行 `Good luck and have fun.`。

samples:
3
4 4
tnalp
woem
kcarrab
hctam

freopen("tnalp.in","r",stdin);
freopen("tnalp.out","w",stdout);
freopen("woem.in","r",stdin);
freopen("woem.out","w",stdout);
freopen("kcarrab.in","r",stdin);
freopen("kcarrab.out","w",stdout);
freopen("hctam.in","r",stdin);
freopen("hctam.out","w",stdout);

freopen("tnalp.in","r",stdin);
freopen("tnalp.out","w",stdout);
//freopen("woem.in","r",stdin);
freopen("woem.out","w",stdout);
freopen("kcarrab.in","r",stdin);
//I_AK_IOI!!!
freopen("hctam.in","r",stdin);
freopen("hctam.out","w",stdout);

freopen("tnalp.in","r",stdin);
freopen("tnalp.out","w",stdout)
freopen("owem.in","r",stdin);
freopen("woem.out","w",stdout);
freopen("kcarrab.in","r",stdout);
freopen("kcarrab.out","w",stdin);
freopen("hctam.out","w",stdout);
freopen("hctam.in","r",stdin);

freopen("tnalp.in","r",stdin);//I_LOVE_CCF
freopen("tnalp.out","w",stdout);
freopen("woem.in","r",stdin);//I_HATE_THIS
freopen("woem.out","w",stdout);
freopen("kcarrab.in"/*I_FORGET_HOW_TO_FIND_BRIDGES!!!!!!*/,"r",stdin);
freopen("kcarrab.out","w",stdout);
freopen("hctam.in","r",stdin);//I_CAN_GET_ONLY_8PTSqwq
freopen("hctam.out","w",stdout);

samples:
PION2202 RP++.
Wrong file operation takes you to your ancestors along with your 3 years' efforts on OI.
Good luck and have fun.
Good luck and have fun.

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

第一位选手所有的 `freopen` 语句都很正常，所以是普通人。

第二位选手注释了题目 `woem` 的输入文件语句，所以是见祖宗人。虽然该选手在题目 `kcarrab` 中有乐子行为但由于已经满足了见祖宗人的条件，所以该选手被分类为见祖宗人。

第三位选手四道题的 `freopen` 语句都不是正常的。`tnalp` 的输出文件语句少了分号；`woem` 被打成了 `owem`；打反了 `kcarrab` 一题中的 `stdin` 和 `stdout`；交换了 `hctam` 的两个语句的顺序。在本题中算作乐子人。

第四位选手的 `freopen` 语句虽然能够正常工作，但是因为与正常的 `freopen` 语句不同而在本题中被算作乐子人。

---

**【数据范围】**

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

子任务 1（30 分）：$T = 1$。$m = 1$ 且题目名称为 `yxalag`。但是，如果你输出 `No, general!` 是不能得到分数的。
子任务 2（30 分）：$T = 2$。保证没有见祖宗人。
子任务 3（40 分）：$T = 3$。无特殊性质。

对于 $100\%$ 的数据：

- 保证 $1\le T \le 3$。
- 保证 $1\le n\le 1000$。
- 保证 $1\le m \le 4$。
- 保证题目名称的长度在 $1$ 到 $10$ 之间。
- 保证每一行 `freopen` 语句的长度在 $1$ 到 $100$ 之间。


title: 坠梦 | Falling into Dream

background:
神明愚弄凡间，所谓命运，不过是神明掷出的一颗骰子而已。

花朵等不到的蝴蝶，终究成了一分蹊跷的梦，一轮轮再次重启。

神明的提线木偶一次又一次的被扼住脖颈, 以爱的名义，消逝在时间的花海里。

无数的执念背后，都有一个被扭曲的“真理”。

 你所承诺的没有出现，彻夜无眠，或许我只是自作主张的，替你爱了一次人间

“最虔诚者只祝祷，不虔诚者才有所求。”

没有过信仰，因为舍命救了一个人，有幸来到了天堂。

description:
给定一棵 $n$ 个结点的无根树，每条边有非负整数边权。结点由 $1 \sim n$ 编号。

对于每一个点对 $(x, y)$，定义 $(x, y)$ 的距离 $\operatorname{dis}(x, y)$ 为 $x,y$ 两点之间唯一简单路径上边权的异或和。

给定两个结点 $x, y$，定义点 $i$ 的价值 $\operatorname{val}_{x, y}(i)$ 为 $(x, i)$ 与 $(y, i)$ 的距离的异或和，即

$$ \operatorname{val}_{x, y}(i) = \operatorname{dis}(x, i) \oplus \operatorname{dis}(y, i) \textsf{。} $$

现在有 $q$ 次询问，每次询问给出四个整数 $x, y, l, r$，求 $\displaystyle \bigoplus_{i = l}^{r} \operatorname{val}_{x, y}(i)$ 的值，即求

$$ \operatorname{val}_{x, y}(l) \oplus \operatorname{val}_{x, y}(l + 1) \oplus \cdots \oplus \operatorname{val}_{x, y}(r - 1) \oplus \operatorname{val}_{x, y}(r) \textsf{。} $$

上述公式中，$\oplus$ 表示二进制按位异或。

inputFormat:
第一行，两个整数 $n, q$。

接下来 $n - 1$ 行，每行三个整数 $u, v, w$，表示 $u, v$ 之间有一条权值为 $w$ 的边。

接下来 $q$ 行，每行四个整数 $x,y,l,r$，表示一次询问。

outputFormat: 输出 $q$ 行，每行一个整数，为每次询问的答案。

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

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

输入给出的树如上图所示。对于点对的距离，有

- $\operatorname{dis}(1, 1) = \operatorname{dis}(1, 3) = \operatorname{dis}(2, 2) = \operatorname{dis}(3, 1) = \operatorname{dis}(3, 3) = 0$ 以及
- $\operatorname{dis}(1, 2) = \operatorname{dis}(2, 1) = \operatorname{dis}(2, 3) = \operatorname{dis}(3, 2) = 1$。

第 $1$ 问：$\operatorname{val}_{1, 2}(1) \oplus \operatorname{val}_{1, 2}(2) \oplus \operatorname{val}_{1, 2}(3) = (0 \oplus 1) \oplus (1 \oplus 0) \oplus (0 \oplus 1) = 1 \oplus 1 \oplus 1 = 1$。

第 $2$ 问：$\operatorname{val}_{2, 3}(2) \oplus \operatorname{val}_{2, 3}(3) = (0 \oplus 1) \oplus (1 \oplus 0) = 1 \oplus 1 = 0$。

---

**【数据范围】**

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

| 子任务编号 | $n \le$ | $q \le$ | 分值 |
| :----------: | :----------: | :----------: | :----------: |
| 1 | $100$ | $10$ | 24 |
| 2 | $10^6$ | $10$ | 14 |
| 3 | $100$ | $10^6$ | 14 |
| 4 | $10^6$ | $10^6$ | 48 |

对于 $100\%$ 的数据，保证 $1 \le n, q \le {10}^6$，$1 \le u, v, x, y \le n$，$1 \le l \le r \le n$，$0 \le w < 2^{31}$。

---

**【提示】**

本题最大 I/O 量达到 60 MiB，请注意 I/O 效率。


title: 觅光 | Searching for Hope (easy ver.)

background:
**这是本题的简单版本。两个版本在 $\bm{100 \%}$ 数据范围的唯一区别是关于 $\bm{n}$ 的限制。此版本中 $\bm{n \le 1000}$。**

---

有梦中所向往的地方，也有现实中可望不可触及的远方。

我们正等待无数次的希望，新的纪元，生命不曾奏响终章。

顷刻间颠覆中的一切，天空坠落到海底，死死卡住呼吸者的全部。羽翼裹满刺骨的海水，悲伤到从此遗忘呼吸的意义。

明明与空气只隔着毫厘，却不想再尝试去呼吸。我开始明白，悲伤到了极点，也许不会流泪

神明借着生的名义，捏造出灰暗的真理。

泪水模糊眼眶，身躯坠进天空，泛白的天光，不得已照亮这一日的希望。

description:
现在有一棵 $n$ 个节点的有根二叉树。

凡人与神明在这棵树上进行一个游戏。凡人需要从根投下若干个球，每个球带 $1$ 单位正电荷或带 $1$ 单位负电荷。

树上每一个点有容量，第 $i$ 个点可以容纳 $c_i$ 个球。初始每一个点容纳的球数为 $0$。我们称一个点被充满当且仅当它容纳的球的个数等于它的容量。

每一次一个球下落到一个点时：

- 如果该点没有孩子节点或者所有孩子节点上都已经充满球，则停止，该点容纳的球的个数 $+1$；
- 如果该点恰有一个孩子节点未充满，则向那个孩子下落；
- 如果有 $2$ 个孩子节点均未充满：
	- 如果左侧子树中所有球的电荷代数和大于右侧子树所有球的电荷代数和，则如果当前球带正电则向右下落，否则向左下落；
   - 如果左侧子树中所有球的电荷代数和小于右侧子树所有球的电荷代数和，则如果当前球带正电则向左下落，否则向右下落；
   - 如果左侧子树中所有球的电荷代数和等于右侧子树所有球的电荷代数和，则由神明决定向哪个方向下落。

其中，电荷代数和指的是正电荷的数量减去负电荷的数量。

在游戏开始前，双方约定目标点 $u$。在一个回合中，凡人选择这次投下的球的电性，神明按上述规则控制球的下落过程。当 $u$ 被充满时，游戏结束。

凡人希望游戏回合数尽量少，神明希望游戏回合数尽量多。假设双方足够聪明。

对所有：$1\leq u\leq n$，求游戏轮数 $r_u$。

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

第二行，$n-1$ 个整数 $f_2, f_3, \ldots, f_n$，其中 $f_i$ 代表 $i$ 的父亲的编号。

第三行，$n$ 个整数 $c_1, c_2, \ldots, c_n$。

outputFormat: 输出一行，$n$ 个整数 $r_1, r_2, \ldots, r_n$。


title: 追寻 | Pursuit of Dream

background:
“遇到自己喜欢的人或事情的时候，千万不要放弃”

“要一直追寻下去…”

“因为即使成功希望渺茫，也有可能”

有谁和我说过这句话，脑海中忽然闪过一下，被当做无用的激励一同忘却了。现在想要回忆，却总也记不起来。

好不容易来人间一趟，那就别留下遗憾。

房檐落下的雨滴有规律的敲着石砖，那夜的雨声中，却也悄无声息了。

逆着风吹干眼泪，说不出口的痛越藏越多，腐烂在肚子里，却又不知道彼此心知且肚明，所以无法孕育出美好的结局，只会是恋者相残的戏码不停上演。

---

 看见了漫天星野坠落在你的眼底，从此甘愿在那海底般低压的梦境中堕落。

三千尺星空的光辉映照不出那人的身影，璀璨中徒留神明思故人；那人却散入了或许碎散的星辰大海，让神明寻觅了一生。

那些无法兑现的渴望，会日渐荒芜，然后梦境会失去生机，裂缝中会蔓出黑暗，泪无葬身之地。

是神明告诉我的，可是我不信，因为没有时间还等着我空想了。

神明还说，人死了以后，提前离开的亲人都会在另外一个世界等你。

其实，我也会想，这一定就是另外一个世界。

description:
在 $n$ 维空间中有一个梦想。这梦想坐落在 $(d_1, d_2, \ldots, d_n)$ 的地方。而你从 $(0, 0, \ldots, 0)$ 开始，开启寻梦的旅程。

你的步伐轻缓，每一步只能走一个单位长度。你并不知道你的梦想位于哪里，所以你只能随机选择 $n$ 个正方向中的一个，然后向这个方向走一步。也就是说，在 $[1, n]$ 中均匀随机选择一个正整数 $h$，然后，使你在第 $h$ 维的坐标变成原来的坐标加一。

然而，天有不测风云。在你走每一步的过程中，你会有 $p = \sum_{i = 1}^k p_i$ 的概率散入天际，并开始一段新的旅程。你会在 $k$ 个地点中的一个重新开始这段旅程，其中第 $i$ 个地点的坐标是 $(a_{i,1}, a_{i,2}, \ldots, a_{i,n})$，从这里重新开始的概率为 $p_i$。

那么，期望下，你离到达这个梦想还需要多少步呢？

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

第二行，$n$ 个非负整数 $d_1, d_2, \ldots, d_n$。

接下来 $k$ 行，第 $i$ 行 $n + 1$ 个整数 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}, x_i$，每行最后一个整数 $x_i$ 表示 $p_i=x_i\times 10^{-8}$。

输入的 $x_i$ 保证了 $p_i > 0$ 且 $p < 1$。

保证每个 $x_i$ 在所有可能的组合中等概率随机生成。

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

如果你不知道如何进行实数取模：可以说明答案一定是有限的，且是有理数，设它的最简分数形式为 $\frac{p}{q}$。如果存在一个整数 $x$ 满足 $x \cdot q \equiv p \pmod{998244353}$ 且 $0 \le x < 998244353$，那么你只需输出 $x$ 的值即可。

由于保证了 $x_i$ 是随机生成的，可以说明以接近 $1$ 的概率答案在模意义下存在。事实上，一个当 $x_i$ 尚不确定时以合理地高的概率给出正确答案的算法足以通过本题，考察复杂的模意义下的有理数的处理不是我们的本意。

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

这是你的一种追寻梦想的方式：

你从 $(0,0)$ 出发，走一步到 $(1,0)$，再走一步到 $(2,0)$，再走一步到 $(3,0)$，但是在路上散入天际，从 $(0,0)$ 重新开始旅程。

然后继续从 $(0,0)$ 出发，走一步到 $(0,1)$，再走一步到 $(1,1)$，但是在路上散入天际，从 $(0,0)$ 重新开始旅程。

接着从 $(0,0)$ 出发，走一步到 $(1,0)$，再走一步到 $(1,1)$，找到了你的梦想。

在这种情况下，你需要 $7$ 步到达这个梦想。发生这种情况的概率是 $4^{-7}$。

---

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

答案为 $\frac{505}{24} \approx 21.041667$。
不难验证 $291154624 \times 24 \equiv 505 \pmod{998244353}$，故应输出 $291154624$。

---

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

答案为 $\frac{1399505}{21519} \approx 65.035782$。

---

**【数据范围】**

**本题采用捆绑测试且使用子任务依赖。**

| 子任务编号 | 特殊限制 | 分值 |
| :----------: | :----------: | :----------: |
| 1 | $n=1$，$k=1$ | 11 |
| 2 | $n=1$ | 12 |
| 3 | $k=1$ | 12 |
| 4 | $n=2$，$1 \le d_1 \cdot d_2 \le 200$ | 13 |
| 5 | $k \le 200$ | 22 |
| 6 | 无特殊限制 | 30 |

对于 $100 \%$ 的数据：

- $1 \le n \le 100$，$1 \le k \le 10000$。
- $d_i \ge 0$，$\sum_i d_i \le 10^7$。
- $0 \le a_{i, j} \le {10}^7$。
- $x_i \ge 1$，$\sum_i x_i < {10}^8$。此即保证了 $p_i > 0$ 和 $p < 1$。
- 保证存在一个 $i \in [1, k]$ 使得对于每个 $j \in [1, n]$ 均有 $a_{i,j} \le d_j$。
- 保证每个 $(a_{i, 1}, a_{i, 2}, \ldots, a_{i, n})$ 作为空间中的点互不相同。
- 保证每个 $x_i$ 在所有可能的组合中等概率随机生成。

---

**【提示】**

由于保证了 $x_i$ 是随机生成的，可以说明以接近 $1$ 的概率答案在模意义下存在。事实上，一个当 $x_i$ 尚不确定时以合理地高的概率给出正确答案的算法足以通过本题，考察复杂的模意义下的有理数的处理不是我们的本意。

样例中的 $x_i$ 不是随机生成的，仅为理解题意所用。


title: 觅光 | Searching for Hope (hard ver.)

background:
**这是本题的困难版本。两个版本在 $\bm{100 \%}$ 数据范围的唯一区别是关于 $\bm{n}$ 的限制。此版本中 $\bm{n \le {10}^6}$。**

---

有梦中所向往的地方，也有现实中可望不可触及的远方。

我们正等待无数次的希望，新的纪元，生命不曾奏响终章。

顷刻间颠覆中的一切，天空坠落到海底，死死卡住呼吸者的全部。羽翼裹满刺骨的海水，悲伤到从此遗忘呼吸的意义。

明明与空气只隔着毫厘，却不想再尝试去呼吸。我开始明白，悲伤到了极点，也许不会流泪

神明借着生的名义，捏造出灰暗的真理。

泪水模糊眼眶，身躯坠进天空，泛白的天光，不得已照亮这一日的希望。


title: 幻梦 | Dream with Dynamic

background:
“那以后见到她，会不会笑出来啊？”

“哈，一时半会见不到她的。”

小时候说要一起去看尘寰间的人间烟火，有人欣然接受，长大了说遗忘过去，那人也没有反驳。

其实吧，她们彼此明白，小时候在意的不是什么人间烟火，而是一起。

黑夜里，没有早晨的绯红，也褪去了天边的白光，留下的是她心头的散不去的灰暗。没有星光璀璨，没有满天繁星，她不在乎。她在乎的是那个人心中闪烁的星辰大海。

----

察觉所谓规则秘密，不过取悦于创世神明，早已知晓光明同黑暗般腥风血雨

description:
有一个长度为 $n$ 的序列，开始时第 $i$ 位为 $a_i$。你需要完成 $q$ 次操作：

- `A l r x`，对于所有的 $l\le i\le r$，令 $a_i\gets a_i+x$。
- `P l r`，对于所有的 $l\le i\le r$，令 $a_i\gets\operatorname{popcount}(a_i)$。
- `J p`，查询 $a_p$ 的值。

注：$\operatorname{popcount}(x)$ 为 $x$ 的二进制表示中 $1$ 的个数。

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

第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。

接下来 $q$ 行，每行描述一个操作，形如以下三种中的一种：

- `A l r x`
- `P l r`
- `J p`

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

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

- 开始时，$a = [1, 2, 3, 4, 5]$。
- 对询问 `J 2`，应回答 $a_2 = 2$。
- 操作 `A 2 4 3` 后，$a = [1, 5, 6, 7, 5]$。
- 对询问 `J 4`，应回答 $a_4 = 7$。
- 操作 `P 1 4` 后，$a = [1, 2, 2, 3, 5]$。
- 对询问 `J 3`，应回答 $a_3 = 2$。

---

**【数据范围】**

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

| 子任务编号 | 特殊限制 | 分值 |
| :----------: | :----------: | :----------: |
| 1 |$n,q\le 2000$| 3 |
| 2 |没有 `P` 操作| 7 |
| 3 |没有 `A` 操作| 15 |
| 4 |数据随机生成| 15 |
| 5 |无特殊限制| 60 |

对于全部数据，保证 $1\leq n\leq 3\times 10^5$，$1 \le q \le 10^6$，$1 \le l \le r \le n$，$1 \le p \le n$，$1\le a_i, x\le 10^9$。

子任务 4 的随机方式：

- 取 $n=3\times 10^5$，$q=10^6$；
- $a_i$ 从 $[1,10^9]$ 均匀随机选取；
- 对于每一个操作：
	- 从 3 种操作中均匀随机选取一个；
   - 如果是 `A` 操作，均匀随机从 $[1,n]$ 中选取 2 个整数，将较小的作为区间左端点，较大的作为区间右端点，再从 $[1,10^9]$ 中选取一个整数作为参数 `x`；
   - 如果是 `P` 操作，均匀随机从 $[1,n]$ 中选取 2 个整数，将较小的作为区间左端点，较大的作为区间右端点；
   - 如果是 `J` 操作，均匀随机从 $[1,n]$ 中选取一个整数作为参数 `p`。

---

**【提示】**

本题最大 I/O 量达到 30 MiB，请注意 I/O 效率。


title: 宿命 | Regulation of Destiny

background:
压抑是有实质的，从躯壳到内脏，密不透风地包裹，药物仅仅像缝隙里挤进去的一滴水，浇不灭深幽的火焰。

时间治愈不了一切，它只把泥泞日复一日地堆积。她的眼睛没有焦点，偶尔仿佛睡梦中惊醒，喊我的名字。

街道乱糟糟，各家店铺放着音乐，公交车轮胎碾过柏油路，小孩打闹，玻璃瓶砸碎，电瓶车相撞……但我清楚地听见自己的呼吸声。后视镜里，我又一次看到她没有焦点的眼神，裹住眼球的眼泪，水的表面张力“嗒”的一声失效。

撕开雨天，潜入他乡，所向往的尽头是天堂。

浅蓝天光，云层泛紫，微弱的灯光嵌进夕阳。

----

 “…你知道吗，所谓的力量，其实，就是心中的执念。”

 “执念？”

 “是啊…就是，必须要做的事，必须守护的人，必须…”

 “实现的心愿。”

 “那么…你心中有这样的执念吗？”

 “呃……有啊！我的执念，就是保护姐姐！”

 “傻小子，想保护你姐，等下辈子再说吧”

description:
A 国为了防御 B 国的进攻，准备兴建一系列防御措施。

A 国有 $n$ 艘恒星级战舰，这些战舰无论如何都是要被保护的。为了节省材料，总司令用了 $n-1$ 条双向加速通道将这些战舰连接了起来。每个战舰有两个属性 $a_i,b_i$，分别代表战舰的人口数，科技程度。

在每艘战舰上有两种防御措施可以选择。你可以选择建设其中的一种，也可以选择不建设，但不能两种都建设。

在 $i$ 号战舰上建设 I 类防御措施需要 $a_i$ 的金钱，可以保护 $i$ 号战舰本身和与其直接相连的战舰。

在 $i$ 号战舰上建设 II 类防御措施需要 $b_i$ 的金钱，可以保护 $i$ 号战舰本身以及所有与 $i$ 号战舰的距离**恰好**为 $r$ 的战舰。

定义战舰 $u$ 和战舰 $v$ 的距离为从 $u$ 到 $v$ 需要经过最少多少条加速通道。

现在，请你求出保护所有战舰需要的最少金钱。

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

接下来 $n-1$ 行，每行两个正整数 $u, v$，代表一条通道所连接的两艘战舰编号为 $u, v$。

接下来 $n$ 行，第 $i$ 行两个正整数 $a_i, b_i$，分别表示在 $i$ 号战舰上建设 I 类和 II 类防御措施所需要的金钱。

outputFormat: 一行，一个整数，表示保护所有战舰需要的最少金钱。


title: 「DROI」Round 2 构造与取模

background: 与其编写苍白无力的背景，不如出更有质量的题。

description:
对于整数 $n,k$，若存在**非负整数** $x$ 与 **正整数** $y$ 满足：

$$x + y = n\ \land\ x \bmod y =k$$

则我们称有序数对 $(x,y)$ 是 $n$ 的一个 **优秀拆分**（其中 $\land$  是**并且**的意思）。

现给定非负整数 $n,k$，请你构造**任意**一组 $n$ 的优秀拆分，并分别输出你构造方案中的 $x$ 和 $y$。特殊地，若不存在这样的拆分，则输出 `-1`。

inputFormat:
**本题有多组数据。**

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

接下来 $T$ 行，每行两个非负整数，分别为 $n,k$。

outputFormat: 输出共 $T$ 行，第 $i$ 行表示第 $i$ 组数据的答案。

hint:
#### 样例解释

对于第一组数据，只存在唯一的构造方式。

对于第二组数据，$(3,10)$ 也是一组合法的构造。

对于第三组数据，可以证明不存在一组合法的构造。

------------

#### 数据范围

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

- $\operatorname{Subtask} 1(20\%)$：$n \leq 10^6$。

- $\operatorname{Subtask} 2(40\%)$：$n \leq 10^{12}$。

- $\operatorname{Subtask} 3(40\%)$：无特殊限制。

对于 $100\%$ 的数据：$T \leq 5$，$0 \leq n,k \leq 10^{18}$。


title: [USACO23JAN] Moo Operations B

description:
Because Bessie is bored of playing with her usual text string where the only characters are `C`, `O`, and `W`, Farmer John gave her $Q$ new strings $(1 \le Q \le 100)$, where the only characters are `M` and `O`. Bessie's favorite word out of the characters `M` and `O` is obviously `MOO`, so she wants to turn each of the $Q$ strings into `MOO` using the following operations:

1. Replace either the first or last character with its opposite (so that 'M' becomes 'O' and 'O' becomes 'M').
2. Delete either the first or last character.

Unfortunately, Bessie is lazy and does not want to perform more operations than absolutely necessary. For each string, please help her determine the minimum number of operations necessary to form `MOO` or output $−1$ if this is impossible.

inputFormat:
The first line of input contains the value of $Q$.

The next $Q$ lines of input each consist of a string, each of its characters either `M` or `O`. Each string has at least $1$ and at most $100$ characters.

outputFormat: Output the answer for each input string on a separate line.

translation:
## 题目描述

农夫约翰给了奶牛贝西 $Q$ 个新字符串 $(1\le Q\le100)$ ，其中只有字符 `M` 和 `O` ，她想将 $Q$ 个字符串都变成 `MOO`。

贝西可以用如下的方式改变字符串：
- 用相反的字符替换第一个或最后一个字符（将 `M` 变成 `O` ，将 `O` 变成 `M` ）。
- 删除第一个或最后一个字符。

贝西只想用最少的次数完成改变。请你帮她找到需要的最小改变次数。如果不可能在有限的步数中完成这个任务，请输出 `-1` 。

## 输入格式

输入数据的第一行是一个正整数 $Q$ 。

接下来的 $Q$ 行中，每行一个只包含大写字母 `M` 或 `O` 的字符串 $S$ ，保证 $ 1\le |S| \le 100$ 。

## 输出格式

输出 $Q$ 行，每行为该测试点最小操作次数，如果不可能在有限的步数中完成这个任务，请输出 `-1` 。

## 提示

### 样例解释 1
将第一个字符串转换为 `MOO`的 $4$ 个操作序列如下：
- 用O替换最后一个字符（操作1）
- 删除第一个字符（操作2）
- 删除第一个字符（操作2）
- 删除第一个字符（操作2）

可以证明，第二个字符串无法转换为 `MOO`。

第三个字符串已经是 `MOO`，因此无需执行任何操作。

### 数据范围
对于 $100\%$ 的测试点，保证 $1 \le Q \le 100$, $ 1\le |S| \le 100$ 。

hint:
### Explanation for Sample 1

A sequence of $4$ operations transforming the first string into `MOO` is as follows:

Replace the last character with `O` (operation 1)
Delete the first character (operation 2)
Delete the first character (operation 2)
Delete the first character (operation 2)

The second string cannot be transformed into `MOO`. The third string is already `MOO`, so no operations need to be performed.

### Scoring

 - Inputs $2-4$: Every string has length at most $3$.
 - Inputs $5-11$: No additional constraints.


title: [USACO23JAN] Find and Replace S

description:
Bessie is using the latest and greatest innovation in text-editing software, miV! She starts with an input string consisting solely of upper and lowercase English letters and wishes to transform it into some output string. With just one keystroke, miV allows her to replace all occurrences of one English letter $c_1$ in the string with another English letter $c_2$. For example, given the string `aAbBa`, if Bessie selects $c_1$ as `a` and $c_2$ as `B`, the given string transforms into `BAbBB`.

Bessie is a busy cow, so for each of $T
(1 \le T \le 10)$ independent test cases, output the minimum number of keystrokes required to transform her input string into her desired output string.

inputFormat:
The first line contains $T$, the number of independent test cases.

The following $T$ pairs of lines contain an input and output string of equal length. All characters are upper or lowercase English letters (either `A` through `Z` or `a` through `z`). The sum of the lengths of all strings does not exceed $10^5$.

outputFormat: For each test case, output the minimum number of keystrokes required to change the input string into the output string, or $−1$ if it is impossible to do so.

translation:
### 题目描述

Bessie 正在使用世界上最先进最伟大的文本编辑器：miV！她想将一个仅由大写和小写英文字母组成的字符串转换为一个新的字符串。每一次操作，miV 可以将字符串中所有的字母  $c_1$ 替换成另一种字母 $c_2$。例：对于字符串`aAbBa`, 如果将其中的 `a` 替换成 `B`, 那么字符串会变为`BAbBB`。

Bessie 非常地忙碌, 所以对于给出的 $T
(1 \le T \le 10)$ 组测试数据, 请输出她至少需要多少次操作才能把原字符串转换为新字符串。

### 输入格式

第一行是一个整数 $T$, 表示测试数据的数量。

接下来有 $T$ 对长度相等的字符串。字符串中所有的字符都是大写或小写的字母。字符串的长度不会超过 $10^5$。

### 输出格式

对于每组测试数据，输出转换字符串需要的最小操作数。

如果这不可能做到，输出 $-1$。

### 样例 1 解释

第一组数据：两个字符串相等，所以不需要任何操作。

第二组数据：你不可能在把其中一个 `B` 转换为 `A`的同时保持剩下一个 `B` 不变。

第三组数据：你可以把字符串中所有的 `a` 转换为 `b`。

第四组数据：你可以按 $\texttt{ABCD} \rightarrow \texttt{EBCD} \rightarrow \texttt{EACD} \rightarrow \texttt{BACD}$ 的方式转换。

### 数据范围

 - 对于 $ 40 \% $ 的数据，字符串的长度不超过 $50$。
 - 对于另外 $ 20\% $ 的数据，所有的字符串仅包含从 `a` 到 `e` 的小写字母。
 - 对于 $ 100\% $ 的数据，字符串的长度不超过 $10^5$，$1 \le T \le 10$。

hint:
### Explanation for Sample 1

The first input string is the same as its output string, so no keystrokes are required.

The second input string cannot be changed into its output string because Bessie cannot change one `B`' to `A` while keeping the other as `B`.

The third input string can be changed into its output string by changing `a` to `b`.

The last input string can be changed into its output string like so: $\texttt{ABCD} \rightarrow \texttt{EBCD} \rightarrow \texttt{EACD} \rightarrow \texttt{BACD}$.

### Scoring

 - Inputs $2-6$: Every string has a length at most $50$.
 - Inputs $7-9$: All strings consist only of lowercase letters `a` through `e`
 - Inputs $10-15$: No additional constraints.


title: [USACO23JAN] Following Directions S

description:
**Note: The time limit for this problem is 8s, four times the default.**

Farmer John has a big square field split up into an $(N+1) \times (N+1) (1 \le N \le 1500)$ grid of cells. Let cell $(i,j)$ denote the cell in the $i$-th row from the top and $j$-th column from the left. There is one cow living in every cell $(i,j)$ such that $1 \le i,j \le N$, and each such cell also contains a signpost pointing either to the right or downward. Also, every cell $(i,j)$ such that either $i=N+1$ or $j=N+1$, except for $(N+1,N+1)$, contains a vat of cow feed. Each vat contains cow feed of varying price; the vat at $(i,j)$ costs $c_{i,j} (1 \le c_{i,j} \le 500)$ to feed each cow.

Every day at dinner time, Farmer John rings the dinner bell, and each cow keeps following the directions of the signposts until it reaches a vat, and is then fed from that vat. Then the cows all return to their original positions for the next day.

To maintain his budget, Farmer John wants to know the total cost to feed all the cows each day. However, during every day, before dinner, the cow in in some cell $(i,j)$ flips the direction of its signpost (from right to down or vice versa). The signpost remains in this direction for the following days as well, unless it is flipped back later.

Given the coordinates of the signpost that is flipped on each day, output the cost for every day (with $Q$ days in total, $1 \le Q \le 1500$).

inputFormat:
The first line contains $N (1 \le N \le 1500)$.

The next $N+1$ lines contain the rows of the grid from top to bottom, containing the initial directions of the signposts and the costs ci,j of each vat. The first $N$ of these lines contain a string of $N$ directions `R` or `D` (representing signposts pointing right or down, respectively), followed by the cost $c_{i,N+1}$. The $(N+1)$-th line contains $N$ costs $c_{N+1,j}$.

The next line contains $Q(1 \le Q \le 1500)$.

Then follow $Q$ additional lines, each consisting of two integers $i$ and $j (1 \le i,j \le N)$, which are the coordinates of the cell whose signpost is flipped on the corresponding day.

outputFormat: $Q+1$ lines: the original value of the total cost, followed by the value of the total cost after each flip.

translation:
## 题目描述

**注：本题时限为 8s，是默认时限的四倍。**

Farmer John 有一个正方形的草地，草地被划分为了 $(N + 1) \times (N + 1)(1 \leq N \leq 1500)$ 的格子。设 $(i, j)$ 为从上到下、从左到右第 $i$ 行，第 $j$ 列的格子。每个满足 $1 \leq i, j \leq n$ 的格子 $(i, j)$ 之中都住着一头牛，而且每个这样的格子上都有一个路标指向右或下。除此之外，所有满足 $i = N + 1$ 或 $j = N + 1$ 的格子，除了 $(N + 1, N + 1)$ 都会有一个饲料桶。牛在每个饲料桶进食需要的价格不同；位置 $(i, j)$ 上的桶喂饱一只牛需要价格 $c_{i, j}(1 \leq c_{i, j} \leq 500)$。

每天晚饭时间，Farmer John 摇响晚餐铃时，所有牛都沿着路标的指向前进，直到它们遇到了饲料桶，之后它们会在它们自己遇到的饲料桶那里进食。第二天，所有牛又会回到自己原来的位置。

为了维持预算，Farmer John 想要知道每天喂食需要的价钱。然而，每天晚饭之前，总会有一头牛 $(i, j)$ 翻转它那里的路标（原来向下则变成向右，反之亦然）。被翻转的路标指向将在后面的日子里保持不变，除非它又被进行了翻转。

给出每天被翻转的路标的坐标，请输出每天喂食需要的价格（总共有 $Q$ 天，$1 \leq Q \leq 1500$）。

## 输入格式

第一行为 $N(1 \leq N \leq 1500)$

接下来的 $N + 1$ 行从上到下输入初始的路标朝向和每个饲料桶的价格 $c_{i, j}$。前 $N$ 行每行包含一个长度为 $N$ 的字符串，其中每个字符只能是 `R` 或 `D`（`R` 表示向右，`D` 表示向下），之后是一个数，表示价格 $c_{i, N + 1}$，第 $(N + 1)$ 行包含 $N$ 个数，依次表示价格 $c_{N + 1, j}$。

接下来的一行为 $Q(1 \leq Q \leq 1500)$。

之后的 $Q$ 行，每行有两个整数 $i$ 和 $j(1 \leq i, j \leq N$，表示每天被翻转的路标的坐标。

## 输出格式

共 $Q + 1$ 行：第一行是初始的总价格，之后 $Q$ 行依次是每次被翻转后的总价格。

## 说明/提示

### 样例 1 解释

在第一次翻转之前，喂养在位置 $(1, 1)$ 和 $(1, 2)$ 的牛需要的价格都为 $1$，喂养在 $(2, 1)$ 的牛需要的价格为 $100$，喂养在 $(2, 2)$ 的牛需要的价格为 $500$。总价格为 $602$。第一次翻转后，在 $(1, 1)$ 处的路标由 `R` 变为 `D`，此时在位置 $(1, 1)$ 的牛喂养的价格变为 $100$（其它牛的价格没有变化），所以总价为 $701$。第二次和第三次翻转都在来回翻转同一个路标。第四次翻转后，在位置 $(1, 1)$ 和位置 $(2, 1)$ 的牛喂养的价格变为 $500$，总价变为 $1501$。

### 数据范围

- 测试点 $2 - 4$ 中：$1 \leq N, Q \leq 50$。

- 测试点 $5 - 7$ 中：$1 \leq N, Q \leq 250$。

- 测试点 $2 - 10$ 中：每个路标初始朝向以及被翻转的路标为随机生成。

- 测试点 $11 - 15$ 中：无特殊条件。

hint:
### Explanation for Sample 1

Before the first flip, the cows at $(1,1)$ and $(1,2)$ cost $1$ to feed, the cow at $(2,1)$ costs $100$ to feed, and the cow at $(2,2)$ costs $500$ to feed, for a total cost of $602$. After the first flip, the direction of the signpost at $(1,1)$ changes from `R` to `D`, and the cow at $(1,1)$ now costs $100$ to feed (while the others remain unchanged), so the total cost is now $701$. The second and third flips switch the same sign back and forth. After the fourth flip, the cows at $(1,1)$ and $(2,1)$ now cost $500$ to feed, for a total cost of $1501$.

### Scoring

 - Inputs $2-4$: $1 \le N,Q \le 50$
 - Inputs $5-7$: $1 \le N,Q \le 250$
 - Inputs $2-10$: The initial direction in each cell, as well as the queries, are uniformly randomly generated.
 - Inputs $11-15$: No additional constraints.


title: [USACO23JAN] Moo Route S

description:
Farmer Nhoj dropped Bessie in the middle of nowhere! At time $t=0$, Bessie is located at $x=0$ on an infinite number line. She frantically searches for an exit by moving left or right by $1$ unit each second. However, there actually is no exit and after $T$ seconds, Bessie is back at $x=0$, tired and resigned.

Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses $x=0.5,1.5,2.5, \cdots ,(N−1).5$, given by an array $A_0,A_1, \cdots ,A_{N−1} (1 \le N \le 10^5, 1 \le A_i \le 10^6, \sum A_i \le 10^6)$. Bessie never reaches $x>N$ nor $x<0$.

In particular, Bessie's route can be represented by a string of $T= \sum\limits_{i=0}^{N-1}A_i$
$L$s and $R$s where the $i$-th character represents the direction Bessie moves in during the ith second. The number of direction changes is defined as the number of occurrences of $LR$s plus the number of occurrences of $RL$s.

Please help Farmer Nhoj find any route Bessie could have taken that is consistent with A
and minimizes the number of direction changes. It is guaranteed that there is at least one valid route.

inputFormat: The first line contains $N$. The second line contains $A_0,A_1,\cdots ,A_{N−1}$.

outputFormat: Output a string $S$ of length $T=\sum\limits_{i=0}^{N-1}A_i$ where $S_i$ is `L` or `R`, indicating the direction Bessie travels in during second $i$. If there are multiple routes minimizing the number of direction changes, output any.

translation:
奶牛贝西开始在一条数轴上原点的位置，每次会向左或向右移动一个单位长度，最后回到了原点。

给定贝西经过 $0.5,1.5,\ldots,(N-1)+0.5$ 的次数（用数组 $A$ 表示，$A_i$ 表示经过 $i+0.5$ 的次数）。

请构造出一条可能的移动路径（由 $\texttt{L}$ 和 $\texttt{R}$ 构成，表示向左 / 向右走），使得中途**改变方向的次数尽量少**。

题目保证有解，若有多解，输出**任意**一组解即可。

翻译自 @[zyc212303](https://www.luogu.com.cn/user/556366)

hint:
### Explanation for Sample 1

There is only $1$ valid route, corresponding to the route $0 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 0$. Since this is the only possible route, it also has the minimum number of direction changes.

### Explanation for Sample 2

There are $3$ possible routes:

RRLRRLRLLL
RRRLRLLRLL
RRRLLRRLLL

The first two routes have $5$ direction changes, while the last one has only $3$. Thus the last route is the only correct output.

### Scoring

 - Inputs $3-5$: $N \le 2$
 - Inputs $3-10$: $T=A_0+A_1+ \cdots +A_{N−1} \le 5000$
 - Inputs $11-20$: No additional constraints.


title: [USACO23JAN] Find and Replace G

description:
Bessie is using the latest and greatest innovation in text-editing software, miV! Its powerful find-and-replace feature allows her to find all occurrences of a lowercase English letter $c$ and replace each with a nonempty string of lowercase letters $s$. For example, given the string `ball`, if Bessie selects $c$ to be `l` and $s$ to be `na`, the given string transforms into `banana`.

Bessie starts with the string `a` and transforms it using a number of these find-and-replace operations, resulting in a final string $S$. Since $S$ could be massive, she wants to know, given $l$ and $r$ with $1 \le l \le r \min(|S|,10^{18})$, what $S_{l\cdots r}$ (the substring of $S$ from the $l$-th to the $r$-th character inclusive) is.

It is guaranteed that the sum of $|s|$
over all operations is at most $2 \cdot 10^5$, and that $r−l+1 \le 2 \cdot 10^5$.

inputFormat:
The first line contains $l, r$, and the number of operations.

Each subsequent line describes one operation and contains $c$ and $s$ for that operation. All characters are in the range `a` through `z`.

outputFormat: Output the string $S_{l \cdots r}$ on a single line.

translation:
#### 【题目描述】
你有一个字符串 $S$，最开始里面只有一个字符 $\text{a}$，之后你要对这个字符串进行若干次操作，每次将其中每一个字符 $c$ 替换成某个字符串 $s$（例如对于字符串 $\text{ball}$，将其中的 $\text{l}$ 替换为 $\text{na}$ 后将会变为 $\text{banana}$）。现在给定 $l,r$，你需要输出 $S_{l\ldots r}$（也就是 $S$ 的第 $l$ 个字符到第 $r$ 个字符对应的子串）是什么。

#### 【输入格式】
第一行三个整数，分别表示 $l,r$ 和操作次数。

接下来每一行一个字符 $c$ 和一个字符串 $s$，意义见题目描述。

#### 【输出格式】
一行，表示对应的子串。

#### 【数据范围】
$l,r\le\min(\left | S \right |,10^{18})$；

$r-l+1\le2\times10^5$；

$\sum\left | s \right | \le 2\times 10^5$。

所有的字符串都只包含小写字母 $\text{a}-\text{z}$。

其中对于测试点 $2-7$，满足：

$r-l+1\le2000$，$\sum\left | s \right | \le 2000$。

hint:
### Explanation for Sample 1

The string is transformed as follows:

$$ \texttt{a} \rightarrow \texttt{ab} \rightarrow\texttt{bcb}\rightarrow \texttt{bdeb}\rightarrow \texttt{bbbdebbb} $$

### Scoring

 - Inputs $2-7$: $\sum |s|,r−l+1 \le 2000$
 - Inputs $8-15$: No additional constraints.


title: [USACO23JAN] Lights Off G

description:
**Note: The time limit for this problem is 4s, twice the default.**

Bessie wants to go to sleep, but the farm's lights are keeping her awake. How can she turn them off?

Bessie has two bit strings of length $N
(2 \le N \le 20)$, representing a sequence of lights and a sequence of switches, respectively. Each light is either on (1) or off (0). Each switch is either active (1) or inactive (0).

A **move** consists of the following sequence of operations:

1. Toggle exactly one switch (set it to active if it is inactive, or vice versa).
2. For each active switch, toggle the state of the corresponding light (turn it off if it is on, or vice versa).
3. Cyclically rotate the switches to the right by one. Specifically, if the bit string corresponding to the switches is initially $s_0s_1\cdots s_{N−1}$ then it becomes $s_{N−1}s_0s_1 \cdots s_{N−2}$.

For $T (1 \le T \le 2 \cdot 10^5)$ instances of the problem above, count the minimum number of moves required to turn all the lights off.

inputFormat:
First line contains $T$ and $N$.

Next $T$ lines each contain a pair of length-$N$ bit strings.

outputFormat: For each pair, the minimum number of moves required to turn all the lights off.

translation:
### 题目描述

给定正整数 $N$，和两个长为 $N$ 的 $01$ 序列 $a$ 和 $b$。定义一次操作为：

1. 将 $b$ 序列中的一个值翻转（即 $0$ 变成 $1$，$1$ 变成 $0$，下同）。
2. 对于 $b$ 序列中每个值为 $1$ 的位置，将 $a$ 序列中对应位置的值翻转。
3. 将 $b$ 序列向右循环移位 $1$ 位。即若当前 $b$ 序列为 $b_1b_2\cdots b_{n}$，则接下来变为 $b_{n}b_1b_2\cdots b_{n-1}$。

有 $T$ 次询问，对每一次询问，你需要回答出至少需要几次操作，才能使 $a$ 序列中每一个位置的值都变为 $0$。

### 输入格式

第一行为两个正整数 $T,N\;(1\leq T\leq 2\times10^5,2\leq N\leq 20)$。

接下来 $T$ 行，每行为两个长为 $N$ 的 $01$ 序列 $a$ 和 $b$，表示一组询问。

### 输出格式

共 $T$ 行，每行一个正整数，表示最少的操作次数。

hint:
### Explanation for Sample 1

 - First test case: the lights are already all off.
 - Second test case: We flip the third switch on the first move.
 - Third test case: we flip the first switch on the first move, the second switch on the second move, and the second switch again on the third move.
 - Fourth test case: we flip the first switch on the first move and the third switch on the second move.

It can be shown that in each case this is the minimal number of moves necessary.

### Explanation for Sample 2

It can be shown that $2$ moves are required to turn all lights off.

 - We flip the seventh switch on the first move and then again on the second move.

### Scoring

 - Inputs $3-5$: $N \le 8$
 - Inputs $6-13$: $N \le 18$
 - Inputs $14-20$: No additional constraints.


title: [入门赛 #9] 最澄澈的空与海 (Hard Version)

background:
材料 1：

> 请小心地计算下面的算式：$138 - 108 \div 6 = ?$
> 你大概难以置信，这个算式的计算结果竟然是 $5!$

材料 2：

> 对于一个正整数 $x$，$x! = 1 \times 2 \times \cdots \times (x - 1) \times x$。我们称 $x!$ 为 $x$ 的阶乘。
> 特别的，$0! = 1$。

显然，「$138 - 108 \div 6 = 5$」是错误的，而「$(138 - 108) \div 6 = 5$」是正确的，所以对材料 1 中的内容，部分读者会认为「作者没有搞清加减乘除的运算优先级关系而犯错」。

然而，材料 1 最后一行的叹号并不是标点符号，而是材料 2 提到的「阶乘」。

考虑到这一点，「$138 - 108 \div 6 = 5! = 1 \times 2 \times \cdots \times 5 = 120$」显然就是正确的了。

description:
然而，此题可能与上面的题目背景关系不是很大。

我们会给你 $T$ 组数据，每组数据包括一个正整数 $n$。

对于每组数据，请你帮助求出满足以下条件的整数三元组 $(x, y, z)$ 的组数：

1. $x \geq 0$，$z \geq 1$。
2. $x - y \div z = n!$ 且 $(x - y) \div z = \dfrac{n!}{n}$。

由于答案可能过大，因此你需要输出答案对 $998244353$ 取模后的结果。

不难注意到答案有可能为 $\infty$，这时请按照「输出格式」要求进行处理。

**请注意此处应满足 $(x - y) \div z = \dfrac{n!}{n}$ 而不是 $= n$。**

请注意这里的 $\div$ 不是向下取整的整除，这显然意味着你需要保证 $y \div z$ 和 $(x - y) \div z$ 为整数。

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

第一行为一个整数 $T$。

接下来 $T$ 行，每行一个整数 $n$。

outputFormat:
输出共 $T$ 行，每行一个整数或一个字符串。

对第 $i$ 行，如果对于输入数据中第 $i + 1$ 行的 $n$，满足 $x - y \div z = n!$ 且 $(x - y) \div z = \dfrac{n!}{n}$ 的整数三元组 $(x, y, z)$ 有无限个，则输出一行 `inf`，否则输出满足条件的三元组的数量对 $998244353$ 取模后的结果。


title: [USACO23JAN] Moo Route G

description:
Farmer Nhoj dropped Bessie in the middle of nowhere! At time $t=0$, Bessie is located at $x=0$ on an infinite number line. She frantically searches for an exit by moving left or right by $1$ unit each second. However, there actually is no exit and after $T$ seconds, Bessie is back at $x=0$, tired and resigned.

Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses $x=0.5,1.5,2.5,\cdots,(N−1).5$
, given by an array $A_0,A_1, \cdots ,A_{N−1} (1 \le N \le 10^5, 1 \le A_i \le 10^6)$. Bessie never reaches $x>N$ nor $x<0$.

In particular, Bessie's route can be represented by a string of $T=\sum\limits_{i=0}^{N-1}A_i$
Ls and Rs where the ith character represents the direction Bessie moves in during the ith second. The number of direction changes is defined as the number of occurrences of $LR$s plus the number of occurrences of $RL$s.

Please help Farmer Nhoj count the number of routes Bessie could have taken that are consistent with $A$
and minimize the number of direction changes. It is guaranteed that there is at least one valid route.

inputFormat: The first line contains $N$. The second line contains $A_0,A_1, \cdots ,A_{N−1}$.

outputFormat: The number of routes Bessie could have taken, modulo $10^9+7$.

translation:
#### 【题目描述】
现在有一条数轴，$t$ 表示当前时刻。在 $t=0$ 时 Bessie 恰好处在 $x=0$ 的位置。

接下来，每秒钟 Bessie 会向左或者向右移动一个单位距离，我们保证 Bessie 是在 $0-N$ 的位置之间移动并最终停在 $x=0$ 的位置。同时，我们有一个 $A_0,A_1,A_2\ldots A_{N-1}$ 的数列，分别表示 Bessie 经过 $0.5,1.5,2.5\ldots (N-1).5$ 这些点的次数。我们可以用一个由 $\text{L}$ 和 $\text{R}$ 组成的序列来表示 Bessie 的路径，我们称 Bessie 改变了一次方向为在序列中的相邻两个字符不同。现在我们不知道具体的移动序列是什么，但我们知道 Bessie 采用了让她改变方向次数最少的走法。现在请问 Bessie 的路径有多少种不同的可能情况？（我们称两条路径不同当且仅当这条路径对应序列中的某一位不同）

#### 【输入格式】
第一行一个正整数表示 $N$。

接下来一行有 $N$ 个用空格分隔的正整数表示 $A_0,A_1,A_2\ldots A_{N-1}$。

#### 【输出格式】
一行一个整数表示结果总数。由于这个值可能很大，请输出其对 $10^9+7$ 取模的结果。

#### 【数据范围】
$N\le10^5,\max(A_i)\le10^6$。

对于测试点 $2-4$，满足 $N\le2,\max(A_i)\le10^3$。

对于测试点 $5-7$，满足 $N\le2$。

对于测试点 $8-11$，满足 $\max(A_i)\le10^3$。

hint:
### Explanation for Sample 1

Bessie must change direction at least 5 times. There are two routes corresponding to Bessie changing direction exactly 5 times:

$\texttt{RRLRLLRRLL}$
$\texttt{RRLLRRLRLL}$

### Scoring

 - Inputs $2-4$: $N \le 2$ and $\max(A_i) \le 10^3$
 - Inputs $5-7$: $N \le 2$
 - Inputs $8-11$: $\max(A_i) \le 10^3$
 - Inputs $12-21$: No additional constraints.


title: [USACO23JAN] Tractor Paths P

description:
**Note: The time limit for this problem is 4s, twice the default. The memory limit for this problem is 512MB, twice the default.**

Farmer John has $N
(2 \le N \le 2 \cdot 10^5)$ tractors, where the $i$-th tractor can only be used within the inclusive interval $[l_i,r_i]$. The tractor intervals have left endpoints $l_1<l_2<\cdots <l_N$ and right endpoints $r_1<r_2< \cdots <r_N$. Some of the tractors are special.

Two tractors $i$ and $j$ are said to be adjacent if $[l_i,r_i]$ and $[l_j,r_j]$ intersect. Farmer John can transfer from one tractor to any adjacent tractor. A path between two tractors $a$ and $b$ consists of a sequence of transfers such that the first tractor in the sequence is $a$, the last tractor in the sequence is $b$, and every two consecutive tractors in the sequence are adjacent. It is guaranteed that there is a path between tractor $1$ and tractor $N$. The length of a path is the number of transfers (or equivalently, the number of tractors within it minus one).

You are given $Q (1 \le Q \le 2 \cdot 10^5)$ queries, each specifying a pair of tractors $a$ and $b (1 \le a<b \le N)$. For each query, output two integers:

 - The length of any shortest path between tractor $a$ to tractor $b$.
 - The number of special tractors such that there exists at least one shortest path from tractor $a$ to tractor $b$ containing it.

inputFormat:
The first line contains $N$ and $Q$.

The next line contains a string of length $2N$ consisting of Ls and Rs, representing the left and right endpoints in sorted order. It is guaranteed that for each proper prefix of this string, the number of Ls exceeds the number of Rs.

The next line contains a bit string of length $N$, representing for each tractor whether it is special or not.

The next $Q$ lines each contain two integers $a$ and $b$, specifying a query.

outputFormat: For each query, the two quantities separated by spaces.

translation:
### 题目描述

**注意：这个问题的时间限制是4秒，内存限制是512MB，是默认值的两倍。**

农民约翰有 $N
(2 \le N \le 2 \cdot 10^5)$ 台拖拉机, 其中第 $i$ 台拖拉机只能在序列 $[l_i,r_i]$ 内使用。拖拉机有左端点 $l_1<l_2<\cdots <l_N$ 和右端点 $r_1<r_2< \cdots <r_N$. 有一些拖拉机是特别的。

如果 $[l_i,r_i]$ 和 $[l_j,r_j]$ 相交，则两台拖拉机 $i$ 和 $j$ 是相邻的。 约翰可以从一辆拖拉机转移到任何相邻的拖拉机上。两台拖拉机 $a$ 和 $b$ 之间的路径由一个传输序列组成，这样序列中的第一个拖拉机是 $a$，序列中的最后一个拖拉机是 $b$，并且序列中的每两个连续的拖拉机相邻。 保证拖拉机 $1$ 和 拖拉机 $N$ 之间有一条路径。路径的长度是转移的数量 (或等价地，其中拖拉机的数量减去 $1$)。

给定 $Q (1 \le Q \le 2 \cdot 10^5)$ 组询问，每次给定 $a$ 和 $b (1 \le a<b \le N)$。 对于每组询问，你需要回答两个问题：

 - $a$ 到 $b$ 的最短路径。
 - 在保证传送次数的最少的情况下，有多少个特殊拖拉机的区间可能被某条最短路经过。

### 输入格式

第一行输入两个整数 $N$ 和 $Q$，表示有 $N$ 台拖拉机和 $Q$ 次询问。

第二行输入一个长度为 $2N$ 的字符串，由大写字母 `L` 和 `R` 组成，保证这个字符串的每个前缀中 `L` 的数量大于 `R` 的数量。

第三行输入一个长度为 $N$ 的字符串, 表示每个拖拉机是否特殊。

接下来 $Q$ 行输入两个整数 $a$ 和 $b$, 表示一次查询。

### 输出格式

对于每一组数据，一行两个数，表示答案。

### 提示

### 样例 $1$ 解释

$8$ 个拖拉机的时间间隔，按顺序，是 $[1,5],[2,10],[3,11],[4,12],[6,13],[7,14],[8,15],[9,16]$。

对于第四个查询, 第 $1$ 台和第 $5$ 台拖拉机之间有三条最短路径: $1 \rightarrow 2 \rightarrow 5$, $1 \rightarrow 3 \rightarrow 5$, 和 $1 \rightarrow 4 \rightarrow 5$。这些最短路径的长度都为 $2$。

另外, 拖拉机 $1,2,3,4,5$
都是前面提到的三条最短路径之一的一部分, 由于 $1,2,4,5$ 是特殊的，因此有 $4$ 台特殊拖拉机，这样存在至少一条包含拖拉机 $1$ 到 $5$ 的最短路径。

### 数据范围

 - 数据点 $2-3$： $N,Q \le 5000$
 - 数据点 $4-7$： 最多 $10$ 台特别的拖拉机。
 - 数据点 $8-16$： 没有额外的约束。

 翻译提供者：[shuqiang](https://www.luogu.com.cn/user/685964)

hint:
### Explanation for Sample 1

The $8$ tractor intervals, in order, are $[1,5],[2,10],[3,11],[4,12],[6,13],[7,14],[8,15],[9,16]$.

For the 4th query, there are three shortest paths between the 1st and 5th tractor: $1$ to $2$ to $5$, $1$ to $3$ to $5$, and $1$ to $4$ to $5$. These shortest paths all have length $2$.

Additionally, every tractor $1,2,3,4,5$
is part of one of the three shortest paths mentioned earlier, and since $1,2,4,5$ are special, there are $4$ special tractors such that there exists at least one shortest path from tractor $1$ to $5$ containing it.

### Scoring

 - Inputs $2-3$: $N,Q \le 5000$
 - Inputs $4-7$: There are at most $10$ special tractors.
 - Inputs $8-16$: No additional constraints.


title: [USACO23JAN] Mana Collection P

description:
**Note: The time limit for this problem is 5s, 2.5 times the default. The memory limit for this problem is 512MB, twice the default.**

Bessie has recently taken an interest in magic and needs to collect mana for a very important spell. Bessie has $N(1 \le N \le 18)$ mana pools, the ith of which accumulates $m_i$ mana per second $(1 \le m_i \le 10^8)$. The pools are linked by a collection of $M (0 \le M \le N(N−1))$ directed edges $(a_i,b_i,t_i)$, meaning that she can travel from $a_i$ to $b_i$ in $t_i$ seconds $(1 \le a_i,b_i \le N, a_i \neq b_i, 1 \le t_i \le 10^9)$. Whenever Bessie is present at a pool, she can collect all the mana stored at that location, emptying it. At time $0$, all mana pools are empty, and Bessie can select any pool to start at.

Answer $Q(1 \le Q \le 2 \cdot 10^5)$ queries, each specified by two integers $s$ and $e (1 \le s \le 10^9, 1 \le e \le N)$. For each query, determine the maximum amount of mana Bessie can collect in s seconds if she must be at mana pool $e$ at the end of the $s$-th second.

inputFormat:
First line contains $N$ and $M$.

Next line contains $m_1,m2, \cdots ,m_N$.

Next $M$ lines contain $a_i,b_i,t_i$. No ordered pair $(a_i,b_i)$ appears more than once in the input.

Next line contains $Q$.

Next $Q$ lines contain two integers $s$ and $e$.

outputFormat: $Q$ lines, one for each query.

translation:
## 题目背景

**注意：这个问题的时间限制是5秒，是默认的2.5倍。这个问题的内存限制是512MB，是默认值的两倍。**

## 题目描述

贝西需要为一个非常重要的法术收集法力。贝西有 $N$  $(1\le N\le 18)$ 个法力池，其中第 $i$ 个法力池每秒可积累 $m_i$ 法力 $(1\le m_i\le 10^8)$ 。这些池子由 $M$ $(0\le M\le N \cdot (N-1))$  条有向边 $(a_i,b_i,t_i)$ 连接，这意味着她可以在 $t_i$ 秒内从 $a_i$ 移动到 $b_i$ $(1\le a_i, b_i\le N$, $a_i\neq b_i$, $1\le t_i\le 10^9)$ 。每当贝西出现在一个池子里，她就可以收集储存在那个地方的所有法力，把它清空。在 $0$ 的时候，所有的法力池都是空的，贝西可以选择任何一个池子来开始收集。

回答 $Q$ $(1\le Q\le 2\cdot 10^5)$ 个查询，每个查询由两个整数 $s$ 和 $e$ 指定 $(1\le s\le 10^9$，$1\le e\le N)$ 。对于每个查询，如果贝西在第 $s$ 秒结束时必须在法力池 $e$ 处，请确定她在 $s$ 秒内能收集的最大法力值。

## 输入格式

第一行包含 $N$ 和 $M$ 。

下一行包含 $m_1,m_2,\dots, m_N$ 。

接下来的 $M$ 行每行包含 $a_i,b_i,t_i$ 。在输入中没有一对有序的 $(a_i,b_i)$ 出现超过一次。

下一行包含 $Q$ 。

接下来的 $Q$ 行每行包含两个整数 $s$ 和 $e$ 。

## 输出格式

输出 $Q$ 行，每个查询所对应的答案。

## 样例 #1

### 样例输入 #1

```
2 1
1 10
1 2 10
4
5 1
5 2
100 1
100 2
```

### 样例输出 #1

```
5
50
100
1090
```

## 样例 #2

### 样例输入 #2

```
4 8
50000000 100000000 20000000 70000000
1 2 20
2 1 50
2 3 90
1 3 40
3 1 10
4 1 25
1 4 5
4 3 70
3
8 3
1000000000 1
500000 4
```

### 样例输出 #2

```
160000000
239999988050000000
119992550000000
```

## 提示

对于第一个样例：

第一次询问。贝西在 $5$ 秒后从水池 $1$ 中取出 $5$ 个法力值。

第二次查询。 $5$ 秒后，贝西从水池 $2$ 中获取 $50$ 点法力。

第三次查询。 $100$ 秒后，贝西从水池 $1$ 中获取 $100$ 法力值。

第四次查询。 $90$ 秒后贝西从水池 $1$ 中获得 $90$ 法力， $100$ 秒后从水池 $2$ 中获得 $1000$ 法力。

测试点 $3-4$: $N\le 10, Q\le 100$ 。

测试点 $5-9$: $N\le 10$ 。

测试点 $10-14$: $Q\le 100$ 。

测试点 $15-17$: $N = 16$ 。

测试点 $18-20$: $N = 17$ 。

测试点 $21-24$：没有其他约束条件 。

hint:
### Explanation for Sample 1

First query: Bessie takes $5$ mana from pool $1$ after $5$ seconds.

Second query: Bessie takes $50$ mana from pool $2$ after $5$ seconds.

Third query: Bessie takes $100$ mana from pool $1$ after $100$ seconds.

Fourth query: Bessie takes $90$ mana from pool $1$ after $90$ seconds and $1000$ mana from pool $2$ after $100$ seconds.

### Explanation for Sample 2

An example where Bessie is able to collect much larger amounts of mana.

### Scoring

 - Inputs $3-4$: $N \le 10$,$Q \le 100$
 - Inputs $5-9$: $N \le 10$
 - Inputs $10-14$: $Q \le 100$
 - Inputs $15-17$: $N=16$
 - Inputs $18-20$: $N=17$
 - Inputs $21-24$: No additional constraints.


title: [USACO23JAN] Subtree Activation P

description:
For the New Year celebration, Bessie and her friends have constructed a giant tree with many glowing ornaments. Bessie has the ability to turn the ornaments on and off through remote control. Before the sun rises, she wants to toggle some of the ornaments in some order (possibly toggling an ornament more than once) such that the tree starts and ends with no ornaments on. Bessie thinks the tree looks cool if the set of activated ornaments is exactly a subtree rooted at some vertex. She wants the order of ornaments she toggles to satisfy the property that, for every subtree, at some point in time it was exactly the set of all turned on ornaments. Additionally, it takes energy to switch on and off ornaments, and Bessie does not want to waste energy, so she wants to find the minimum number of toggles she can perform.

Formally, you have a tree with vertices labeled $1 \cdots N (2 \le N \le 2 \cdot 10^5)$ rooted at $1$. Each vertex is initially inactive. In one operation, you can toggle the state of a single vertex from inactive to active or vice versa. Output the minimum possible length of a sequence of operations satisfying both of the following conditions:

 - Define the subtree rooted at a vertex $r$ to consist of all vertices $v$ such that $r$ lies on the path from $1$ to $v$ inclusive. For every one of the $N$ subtrees of the tree, there is a moment in time when the set of active vertices is precisely those in that subtree.
 - Every vertex is inactive after the entire sequence of operations.

inputFormat:
The first line contains $N$.

The second line contains $p_2 \cdots p_N
(1 \le p_i<i)$, where $p_i$ denotes the parent of vertex $i$ in the tree.

outputFormat: Output the minimum possible length.

translation:
## 题目描述

你有一棵根为 $1$ 的树，顶点标记为 $1 \dots N$ $(2 \le N \le 2 \cdot 10^5)$ 。每个顶点最初都是关闭的。在一次操作中，你可以将一个顶点的状态从关闭状态切换到开启状态，反之亦然。输出一个满足以下两个条件的操作序列的最小可能长度。

- 定义以顶点 $r$ 为根的子树由所有满足 $r$ 位于从 $1$ 到 $v$ 的路径上 $($包括 $v)$ , 的顶点 $v$ 组成。每一个顶点的子树，都有一个时刻，开启状态顶点的集合恰好是该子树中的顶点。
- 在整个操作序列之后，每个顶点都是关闭的。

## 输入格式

第一行包含 $N$ 。

第二行包含 $p_2 \dots p_N$ ， $p_i$ 是结点 $i$ 的父亲 $(1\le p_i < i)$ 。

## 输出格式

输出可能的最小长度。

## 提示

有三个子树，分别对应 $\{1,2,3\}、\{2\}、\{3\}$ 。下面是最小可能长度的一个操作序列。

- 开启 $2$ (激活的顶点形成以 $2$ 为根的子树) 。
- 开启 $1$ 。
- 开启 $3$ (激活的顶点形成以 $1$ 为根的子树) 。
- 关闭 $1$ 。
- 关闭 $2$ (激活的顶点形成以 $3$ 为根的子树) 。
- 关闭 $3$ 。

子任务：
- 测试点 $2-3$ : $N \le 8$
- 测试点 $4-9$ : $N \le 40$
- 测试点 $10-15$ : $N \le 5000$
- 测试点 $16-21$ ：没有额外的限制。

hint:
### Explanation for Sample 1

There are three subtrees, corresponding to $\{1,2,3\}$, $\{2\}$, and $\{3\}$. Here is one sequence of operations of the minimum possible length:

activate 2
(activated vertices form the subtree rooted at 2)
activate 1
activate 3
(activated vertices form the subtree rooted at 1)
deactivate 1
deactivate 2
(activated vertices form the subtree rooted at 3)
deactivate 3

### Scoring

 - Inputs $2-3$: $N \le 8$
 - Inputs $4-9$: $N \le 40$
 - Inputs $10-15$: $N \le 5000$
 - Inputs $16-21$: No additional constraints.


title: [Ynoi Easy Round 2022] 超人机械 TEST_95

background:
距今 300 年前，史前科学文明跨越了界限。出现了凌驾人类的人工智能，也就是超人机械。

不为人知的诞生，等察觉到时，世界已经在【他】的手中了。

究竟他身在何处，有什么样的外貌，虽然直到最后都没有人知道。但他好像可以出现在任何地方，化为任何样貌。

既非敌对，也非压制，单纯只是力量上占上风而已。也不太常出手进行干涉。我想一定是人类对他来说无所谓吧。

但即使如此，他还是会帮人实现愿望，魔人或魔龙，各式各样的不可思议，都是有人追求才被造出来的。

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

......

然而在某一天，超人机械消失了。

被腐铁菌干掉了，只是躲了起来，启程前往次元的另一端等，众说纷纭。留下的只有超人机械莫名其妙的发明品。和被世人自己弄得一团乱的世界。

这座树海一定也是超人机械的产物。魔力会一下子增幅，一下子又消耗掉对吧？魔法是从异次元将力量取出的能力，是超出人类理解范围的技术。

description:
给定一个序列 $a$ ，我们定义一个二元组 $(i,j)$ 为一个逆序对当且仅当 $i<j$ 且 $a_i>a_j$ 。定义两个逆序对 $(i_1,j_1),(i_2,j_2)$ **本质不同** 当且仅当 $a_{i_1}\ne a_{i_2}$ 或 $a_{j_1}\ne a_{j_2}$ 。

现在给出 $a$ 序列，问本质不同逆序对个数。

这还不够。

现在有 $q$ 组修改，每一次修改形如 $x~y$ 表示修改 $a_x$ 为 $y$ ，每一次修改 **不互相独立** ，即这一次修改会影响到后面的所有修改。

你需要对于每一次修改输出序列本质不同逆序对个数。

为了体现本题的不同解法，本题不同测试点拥有不同的时空限制。

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

第二行 $n$ 个整数 $a_i$ ，表示序列 $a$ 。

第三行一个整数 $q$ ，表示询问组数。

后面 $q$ 行每行两个整数表示一次修改。

outputFormat:
一行一个整数，表示初始序列中本质不同逆序对个数。

后面 $q$ 行每行一个整数，第 $i + 1$ 行表示第 $i$ 次修改后序列本质不同逆序对个数。


title: [Ynoi2003] 铃原露露

description:
给定一棵有根树，顶点编号为 $1,2,\dots,n$，对 $2\le i\le n$ 有 $f_{i}$ 为 $i$ 的父亲。$a_1,\dots,a_n$ 是 $1,\dots,n$ 的排列。

共 $m$ 次询问，每次询问给出 $l,r$，询问有多少个二元组 $L,R$，满足 $l\le L\le R\le r$，且对任意 $L\le a_x\le a_y\le R$，有 $x,y$ 在树上的最近公共祖先 $z$ 满足 $L\le a_z\le R$。

以上所有数值为整数。

inputFormat:
第一行两个整数 $n\ m$；

接下来一行，$n$ 个整数 $a_1,\dots,a_n$；

接下来 $n-1$ 行，依次为 $f_2,\dots,f_n$；

接下来 $m$ 行，每行 $l\ r$ 表示一个询问。

outputFormat: 对每个询问，输出一行，表示答案。

hint:
Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足 $1\le n,m\le 2\times 10^5$，$1\le f_i\le i-1$，$l\le r$。

对于 $25\%$ 的数据，满足 $n,m\le 100$。

对于另外 $25\%$ 的数据，满足 $n,m\le 3000$。

对于另外 $25\%$ 的数据，满足 $l=1,\;r=n,\;m=1$。

对于另外 $25\%$ 的数据，无特殊限制。


title: 「AWOI Round 2 A」最大和

description:
给你一个整数 $n$，你需要对这个数进行 $m$ 次操作。其中 $m$ 为当前需要操作的数的位数（默认自然数 $0$ 是一位数），且**可能随着 $n$ 的改变而改变**。

第 $i$ $(1\leqslant i \leqslant m)$ 次操作有以下三种选择：

1. $n\gets n+10^{i-1}$。
2. $n\gets n-10^{i-1}$。
3. $n$ 不变。

要求最大化操作后的各个数位上数字之和。

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

第一行一个正整数 $T$，代表有 $T$ 组数据。

接下来的 $T$ 行，每行包含一个整数 $n$。

outputFormat: 共 $T$ 行，每行一个整数，表示每组数据的 $n$ 经操作后最大的各个数位上数字之和。


title: 「DTOI-5」3-1

background:
——『太阳』这种东西，以前似乎是存在的。

传说是这么讲的——白色的火焰发出闪耀的光芒，天空则是清澄无比的蔚蓝。

据说诸神与其创造物所掀起的『大战』，使得大地化为焦土，灰烬遮蔽了苍穹。

灰烬冲击到天上流动的星辰之力——精灵回廊，发出了光芒，将天空染成红色。

而那样的红色，覆盖了仍然持续着互相残杀的每一块土地。

或者那是这个星球本身发出的悲鸣与流出的鲜血吧……

血色的天空上，只有——蓝色的灰飘然落下。

~~回来吧3579，我最骄傲的信仰/ll~~

description:
里克在视线可及的范围内发现了一颗古老的「神树」。

神树是一颗树，树上有 $n$ 个含有魔法装置的位置。经过初步「考察」，有 $n - 1$ 条魔法连接，第 $i(1 \leq i \leq n - 1)$ 条连接 $u_i, v_i$ 两个魔法装置，保证 $u_i \neq v_i$ 且 $1\leq u_i,v_i\leq n$。这两个装置可以相互**双向地**在 $1$ 单位时间内通行，保证仅由这 $n - 1$ 条连接，每个魔法装置都可以相互到达。

此外，有 $n - 1$ 条特殊连接，对于每个魔法装置 $i \in [2, n]$，可以**瞬间**传送到第 $1$ 个魔法装置，花费 $0$ 单位时间。**特殊连接总共只能使用一次**。

里克初始在魔法装置 $1$ 处。现在，给出这棵「神树」的结构，里克想要在若干时间内研究尽可能多的魔法装置。我们假定，研究一个魔法装置只需要到达该装置处，并且不需要花费额外时间。

里克想让你尽快计算出，对所有 $k \in [1, n]$，如果要恰好研究 $k$ 个不同的魔法装置，**并且随之返回魔法装置 $\bm 1$**，最少应花费多少时间。

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

接下来 $n - 1$ 行，每行两个整数 $u_i, v_i$。

outputFormat: 共 $n$ 行，第 $i$ 行一个整数表示 $k = i$ 的答案。

samples:
见下发的 hope/hope2.in
见下发的 hope/hope2.ans

hint:
**【样例解释 $\bm 1$】**

+ $k = 1$ 时，里克只需要呆在装置 $1$ 处。
+ $k = 2$ 时，里克的路径可以是 $1 \rightarrow 2 \Rightarrow 1$。
+ $k = 3$ 时，里克的路径可以是 $1 \rightarrow 2 \rightarrow 4 \Rightarrow 1$。
+ $k = 4$ 时，里克的路径可以是 $1 \rightarrow 2 \rightarrow 4 \Rightarrow 1 \rightarrow 3\rightarrow 1$。
+ $k = 5$ 时，里克的路径可以是 $1 \rightarrow 3\rightarrow 1 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 4 \Rightarrow 1$。

**【样例解释 $\bm 2$】**

这组数据满足测试点编号 $13 \sim 20$ 的性质。

**【数据规模与约定】**

| 测试点编号 | 特殊限制 |
| :--------: | :------: |
| $1 \sim 2$ | $n = 3$ |
| $3 \sim 4$ | $n = 5$ |
| $5 \sim 6$ | $n = 100$ |
| $7 \sim 8$ | $n = 1000$ |
| $9 \sim 10$ | $u_i = 1, v_i = i + 1$ |
| $11 \sim 12$ | $u_i = i, v_i = i + 1$ |
| $13 \sim 20$ | 无特殊限制 |

对于所有数据，$1 \leq n \leq 10^5$，$1 \leq u_i, v_i \leq n$。


title: variance

description:
给定序列 $a_1,a_2,\cdots,a_n$，定义 $f(l,r)=(a_l\oplus a_{l+1}\oplus \cdots \oplus a_r)+(a_l\vee a_{l+1}\vee \cdots \vee a_r)$，其中 $\oplus$ 表示 **按位异或** 运算，$\vee$ 表示 **按位或** 运算。

你需要求出所有满足 $1\le l \le r \le n$ 的 $f(l,r)$ 的方差 $v$。为避免精度误差，以及答案可能很大，请输出 $(v\times \frac{n^2\times (n+1)^2}{4}) \kern{3pt}\mathrm {mod}\kern{3pt} 998244353$。

**注意：运算过程中不取模，仅将结果取模。**

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

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$。

outputFormat: 输出一个整数 $(v\times \frac{n^2\times (n+1)^2}{4}) \kern{3pt}\mathrm {mod}\kern{3pt} 998244353$。

hint:
方差的定义：对于 $n$ 个数 $a_1,a_2,\cdots,a_n$，它们的方差是：

$$
\frac 1 n\sum_{i=1}^n (a_i-\bar{a})^2
$$

其中 $\bar{a}$ 为 $a_1,a_2,\cdots,a_n$ 的平均数，即 $\dfrac {1} {n} \displaystyle\sum\limits_{i=1}^n a_i$。

----

对于 $10\%$ 的数据，$n \le 50$。

对于 $30\%$ 的数据，$n \le 5000$。

对于另 $20\%$ 的数据，$a_i \le 100$。

对于 $100\%$ 的数据，$1\le n\le 10^5,1\le a_i < 2^{31}$。


title: 『GROI-R2』 Beside You

background:
記憶の森

始まりの謎 いつか

この未知の果てに告げ知らせて

——江口孝宏《Beside You》

description:
我相信所有读过这一段剧情的人都不想让别人也经历一样的痛苦，但是坦尼尔还是只能消失，对吗？

坦尼尔最后留下了一棵以 $1$ 为根的有根树，在树的每个结点上，都有一个记忆碎片。有的碎片表示着一个世界记忆的开始，而另外的碎片表示着一个世界记忆的终结。

这时，树上飞来了一只蝴蝶~~モリモリあつし~~。蝴蝶在树上飞舞的过程中，经过了一些结点。爱丽丝能确定蝴蝶经过的结点个数至少有 $2$ 个，但是她忘记了具体的点数。

爱丽丝发现，蝴蝶经过的所有点都是互相连通的。当她把目光朝向每一条经过点数大于 $1$ 的从连通块**深度最小的结点**通往**连通块的任意一个叶子结点**（一个点是连通块的叶子结点，当且仅当它在树上没有子结点，或者它在树上的任意子结点均不在该连通块内）的简单路径时，她发现这些路径上的记忆都是完整的。爱丽丝认为一条路径上的记忆是完整的，当且仅当这条路径上既没有出现一个世界的记忆**没开始就结束**（路径中途在没有未结束的记忆的时候，出现了表示记忆终结的碎片）的情况，也没有出现一个世界的记忆**开始之后没有终结**（路径结束之后还有没结束的记忆）的情况。

可惜她已经遗忘了蝴蝶经过了哪些点，所以你需要告诉她蝴蝶**最多**可能经过多少点。

**形式化题面**

给定一棵以 $1$ 为根的 $n$ 个节点的树 $T=(V,E)$，每个节点上的点权 $c_i$ 为一个**左括号或一个右括号**，节点编号为 $1\sim n$。

我们定义点集 $V'\subseteq V$ 合法，当且仅当 $|V'|>1$（**即 $V'$ 的大小大于 $1$**） 且 $\forall u,v \in V'$，从 $u$ 到 $v$ 的简单路径只经过 $V'$ 中的点。

同时我们定义 $E'\subseteq E$ 为能使得 $\forall u,v \in V'$，从 $u$ 到 $v$ 的简单路径，只经过 $E'$ 中的边的大小最小的边集。

定义一个合法点集 $V'$ 的根为 $V'$ 中深度最小的结点。

定义 $u$ 为合法点集 $V'$ 的叶子节点，当且仅当 $u$ 不是 $V'$ 的根，且满足 $v \in V', (u,v) \in E'$ 的 $v$ 的数量为 $1$。

求一个合法点集 $S$，**满足其根节点到其任意一个叶子的路径上，每个点的点权顺次相接为一个合法的括号序列**，并**最大化** $|S|$。

我们通过如下规则定义一个合法的括号序列：

- 空串（即长度为 $0$ 的串）是一个合法的括号序列。

- 若串 $\text{A,B}$ 都是合法的括号序列，则字符串 $\text{AB}$ （即将字符串 $\text{A}$ 与 $\text{B}$ 按顺序拼接起来）也是合法的括号序列。

- 若串 $\text{A}$ 是合法的括号序列，则字符串 $\text{(A)}$ 是一个合法的括号序列。

你需要输出符合要求的最大 $|S|$。

inputFormat:
第一行输入一个正整数 $n$ 表示树上结点个数。

第二行输入一个长度为 $n$ 的字符串 $c$。$c_i$ 为 ``(`` 表示这个结点上有一个标志着记忆开始的碎片，$c_i$ 为 ``)`` 表示这个结点上有一个标志着记忆终结的碎片。

接下来 $n-1$ 行，每行输入两个正整数 $u,v$，表示结点 $u,v$ 之间有一条边。

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


title: 「SiR-1」Lighthouse

description:
给定一棵 $n$ 个点的树，每个点有权值 $w_i$，初始为 $0$。初始得分 $s=0$。

进行 $m$ 次操作，每次操作选择一个点 $u$，给 $s$ 增加 $u$ 所在的同点权连通块的大小（即，假设只保留点权等于 $w_u$ 的点，和连接两个点权等于 $w_u$ 的点的边，对得分的贡献就是此时 $u$ 所在的连通块大小。注意这不会真的删去一部分树上的点和边），然后给 $w_u$ 增加 $1$。

请对所有 $n^m$ 种操作方式，求它们的得分 $s$ 之和，对 $10^9+7$ 取模。

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

其后 $n-1$ 行每行两个正整数，表示一条边的两个端点 $u,v$。

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

hint:
对于所有数据，满足 $1\leq n\leq 1000$，$1\leq m\leq 10^5$，$1\leq u,v\leq n$，保证输入是一棵树。

- Subtask 0（5 pts）：$n,m\le 7$。
- Subtask 1（20 pts）：$n,m\le 10$。
- Subtask 2（15 pts）：$n,m\le 50$。
- Subtask 3（15 pts）：$n,m\le 100$。
- Subtask 4（15 pts）：$n\le 50$。
- Subtask 5（15 pts）：树是一条链。
- Subtask 6（15 pts）：无特殊限制。

本题同时开启子任务依赖。具体地：

+ 对于子任务 $i(i \in [1, 3])$，依赖于子任务 $0 \sim (i -  1)$；
+ 对于子任务 $4$，依赖于子任务 $0 \sim 2$；
+ 对于子任务 $6$，依赖于子任务 $0 \sim 5$。


title: 「AWOI Round 2 D」数字三角形

description:
Glad 发现了一个 $n$ 层数字三角形，他发现可以用魔法来操纵这个三角形！

他可以先消耗 $nk_1$ 点消耗值，让将三角形旋转 $k_1$ 次。其中“旋转”指绕三角形中心顺时针旋转 $120^\circ$。

然后，他可以不停地进行下面操作：

- 消耗 $1$ 点消耗值，选择一层，调换这一层任意两个数的位置。

现在，Glad 要从三角形的最后一层走到最顶层，起点可以为最后一层的任意一个数，行走的每一步只能走到与当前数相邻的数上，且每一行只能经过一个数。

Glad 想在经过数之和最大的前提下让消耗的消耗值最小，你可以帮帮他吗？

inputFormat:
一个正整数 $n$，表示三角形的层数。

后面 $n$ 行，表示数字三角形。其中第 $i$ 层有 $i$ 个数（$1\leqslant i\leqslant n$）。

outputFormat: 两个整数，分别表示最大能经过的数之和以及最少要消耗多少消耗值。


title: [APC001] B - Checker

background: 小 K 正在出公开赛。他有一个 idea，但他担心重题，因此，他需要确认这题是不是重题。不过他还有很多事情要做，因此他把这个任务交给了你。

description:
题库里共有 $ n $ 道题目，每道题目的名称都是一个**长度不足 $ 10 $** 的字符串。设题目名称长度为 $k$，我们定义两道题为**重题**当且仅当两道题题目名称有 $\ge \left\lceil\frac{k}{2} \right\rceil$ 的相同位置的字符相同。

现在小 K 把这道题交给了你，希望你帮他查重（即，将自己的题目与其他的题目进行一一比对，判断是否为重题）。

inputFormat:
先输入一个正整数 $ n $ 表示题库中的题目数量，之后输入一个字符串 $ s $ 表示小 K 出的题目的名称。

之后 $ n $ 行每行一个字符串表示这些题目的名称。

**输入的每个字符串长度相同。**

outputFormat: 两行，第一行输出重题数量，若没有重题则第二行输出 `Good job!`，否则输出 `Make persistent efforts.`。

samples:
25
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z

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

题目名为 `chachong`，与第一题中的 $ 0 $ 个字符相同，与第二题中的 $ 3 $ 个字符相同，与第三题中的 $0$ 个字符相同，而每题都有 $ 8 $ 个字符，没有与小 K 出的题目有大于等于 $ 8 \times 50\% = 4 $ 个字符相同的题目。

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

请注意有可能在题库中也包含重题。

**【数据规模】**

对于 $100\%$ 的数据，保证 $ 1 \le n \le 10^4 ,1\le k\le10$，每个字符串长度相同，且不含不可见字符。


title: 「HCOI-R1」报名人数

background:
在一个电子展牌上，对于十进制数 $P$，从右到左，从 $P$ 的低位到高位，我们对每一位按照如下的方式进行显示：

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

所以，对于数位分别取 $0\sim 9$，该数位对应所用的短竖线数量分别是 $6, 2, 5, 5, 4, 5, 6, 3, 7, 6$。

description:
小 R 的家中有一个大型的电子展牌，上面记录着 HCOI-R1 的报名人数。

在小 R 布置完成的时候，HCOI-R1 的报名人数为 $l$。而现在，HCOI-R1 最终的报名人数为 $r$。

小 R 觉得这样的整数数对 $(i, j)$ 是**幸运**的，当且仅当在报名过程中，存在人数为 $i, i + 1, \dots, j$ 的时刻（也即 $l \leq i \leq j \leq r$），且在 **不含前导 $\bm 0$** 的情况下，表示 $i, i + 1 \dots j$ 这些数字所用的短竖线数量相同。

小 R 想知道，对于所有的幸运数对 $(i, j)$，其中 $j - i + 1$，也即数字个数——最大为多少。

inputFormat: 仅一行，两个整数 $l, r$，表示初始报名人数和最终报名人数。

outputFormat: 一行一个整数，表示所有数对 $(i, j)$ 中，$j - i + 1$ 的最大值。

hint:
### 样例解释 1

存在幸运数对 $(2, 3)$，表示它们均需要 $5$ 条短竖线。

### 数据规模与约定

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

+ Subtask 0（19 pts）：$r \leq 10^3$。
+ Subtask 1（33 pts）：$r \leq 10^6$。
+ Subtask 2（48 pts）：无特殊限制。

对于所有数据，保证 $1 \leq l \leq r \leq 10^{18}$。


title: [集训队互测 2018] 蜀道难

description:
「蜀道之难，难于上青天……」

一边背着新学的语文课文，A 与 B 走出北校门口。现在距离七点的放学时间已过很久，与十点四十五分晚自习后的人潮却还有些距离，巷里的行人稀稀落落的。

「明天早上就考试了呀。」A 小声而僵硬地说道。

「嗯……背这样的课文，还真有种文人墨客的潇洒豪气。」B 回应着。

「嗨，得了，我们学了什么『文』么？天天坐机房敲代码刷题，触景生情时也就靠语文课学的两三句诗过活了。」

「人艰不拆……你说，三千年前的古蜀国人真要凭『天梯石栈相勾连』往来吗？」

「人家住在四川盆地、天府之土好吗。住山里的，那是苗蛮，部落山野之人，怎么会天天翻山越岭走栈道呢？栈道那是几百年后，秦国经略蜀地才大规模修筑的。」

「那这前边的人，就跟黄土高原一样，说话靠吼么。」

「兴许他们是鸡犬之声相闻，老死不相往来，根本不用如此交流吧。」

「比起如此，我到更希望他们真有『地崩山摧壮士死』的英雄。」

「几千年前的事，谁又说得准呐。」

「不能这么说……我宁愿相信信息是守恒的，历史的一切都会留下痕迹。」

「那您考古嘞。」

「可你知道混沌吧。」

一时语塞的 A 带着两人在那棵槐树下停止了脚步。

突然他字正腔圆，有板有眼地念着：

「上有六龙回日之高标——下有冲波逆折之回川。黄鹤之飞——尚不得过，猿猱欲度，愁攀援。」

「青泥何盘盘，百步九折萦岩峦。扪参历井仰胁息，以手抚膺坐长叹。」正望着树干出神的 B 也轻声应和。

然后，一如往日，那名女孩也从树干背后现身了，仍是一袭白衣，头戴花冠，浅笑嫣然，缄口不言。A 仍是微微低头把玩衣角，B 也照常微笑。

她抚摸着他们的头，A 和 B 也没有再拨打 110 报警。倏忽间闪过恍惚。

面对眼前的高峰幽谷、连山绝壑，A 不禁想起了初中所学郦道元的「重岩叠嶂，隐天蔽日，自非亭午夜分，不见曦月。」刚刚讽刺 B 的，书到用时方恨少的发言，反而沁入自己的心脾了。远处的水滨石室隐约可见，似有人烟；山顶处则现出房屋的剪影。

突然手被 B 握住。陶醉在猿啼鸟鸣中的 A 这才惊觉，自己身处 LCR 带来的梦境。

「这好像是我们刚刚所讨论《蜀道难》的内容啊。」

A 也想到了，但他并未看到栈道的影子，看来这是比秦王更早的「苗蛮」了。

「那我们实际观察一下刚刚的问题吧。没有栈道的人如何交流。」

最直接的方法，当属攀藤附葛，翻山越岭而至，这也是靠山吃山的先民们固有的技能——但技艺的熟练并不能抵消山中蛇虫和失足的危险。如此传递信息，未免得不偿失。B 相信存在更专业的手段。

山谷渐渐明亮起来，眼尖的 A 注意到树木遮掩的山壁有些不寻常。二人攀援而至，多亏是梦境，他们并未费力。原来，山间绵延着一根被劈开的，用细小竹片固定的，宽约尺余的竹筒。泉水从中流过，大概是山民们引水的设施。

「不对啊。山下的人有峪中河水可取。何况要输送水流，应该用完整而不是劈开的管道才对。」

接着，一支系绳的小竹筒从他们面前流着泉水的槽中滑过。

「这是……」

「是了！这小筒是山上山下交流少量物品——包括信息载体——的工具。流水是为了清除淤尘。劈开而非封闭的竹筒也是为了防止卡住。」

「可是，小筒不是很容易从仅仅一半的槽中滑落吗？」

「仔细观察，小筒是两节的结构，这样就能在存贮信息的时候接受水。泉水同样起了引流的作用。并且上面的绳子也能回收——这意味着交流是双向的，尽管发起者总在高处，但只需等待便可解决相反方向的问题。」

「大概如此，不过这是 LCR 带来的世界，不知我们的先辈是否真的在秦巴山区中如此做过。」

「若有一泓稳定的清泉，这应该可行。」

「这样的创意，」B 说，「表明先民们懂得技术胜过科学。」

接着他突然沉默了。「真的是这样吗？」

接着二人飘飞了起来——提醒着他们身处梦境的现实。

A 注意到，在这座山附近，这样流水传物的「信道」有许多，它们构成了一张树状的大网。

「他们不仅发明了这样的方法，还做了符合科学原理的，充满智慧的规划。」

「瞧瞧吧。他们用最少段数的路线连接了所有的聚落，他们的所有聚落的高度排序后恰好等差，他们的任意两个聚落之间只需经不超过一个聚落的转达即可互相通信，他们的管道高差最为节省。」

不知是谁在说呢。

……

A 思考了一会，说道：

「也就是说，尽管聚落的位置受自然条件限制是无法转移的，但他们在管道连接方案上做出了最明智的选择。」

B 答道：

「是啊。刚刚 LCR 的意思，以我们学的 OI 来描述大概是这样的：管道可以看作两个聚落之间的边。

1. 它们以最小代价联通聚落，即构成一棵树；
2. 同一个聚落处的管道是互联的且有人管理，也即两个聚落只要满足其间的管道的高度方向是单调的——聚落高度一直递增或一直递减——就可以直接通信。
3. 任意两个聚落通信至多需要转发一次；
4. 所有聚落的高度排序后恰是等差数列；
5. 管道的代价正比与两端聚落的高差，而高差形成的代价和恰巧是所有聚落高度排列方式中最小的；」

「但聚落的高度并不是人决定的。」

「所以，这一点是数学的美，是大自然的巧合和人的智慧共同的结晶。没有什么比这更浪漫了。」

「很好……但如果新加入一个聚落的话，事情就被破坏了。」

「幸运的是，这是梦境世界。我们也许可以做做救世主，改变一下聚落的高度。」

「那该怎么做呢？」

**「首先是抽象。我们把聚落看成一棵 $n$ 个点的树，树的点被标号为 $1$ 到 $n$，一条边的边权为两端点标号的差的绝对值。整棵树的权值为所有边权和。另外树必须满足一个条件：任意两点，要么它们之间（包括端点）的路径的标号是单调（递增或递减）的，要么存在第三点分别与这两点满足此条件。**

**那么我们的任务是对于给定形态的树求出，在这些前提下通过改变点标号方法能得到的整棵树最小的权值。**

**并且，还需要在加入新的叶子后维护这一点。」**

……

十一点钟声即将敲响，学生们陆续经过那棵槐树。没有人能注意到，两小时前两名同学在树下酣眠的梦游。

请你完成 B 的设想。

---

#### 题意

对于一棵有标号有根树 $T=(V,E)$，标号 $p:v\rightarrow p(v),v\in V,p(v)\in [1,|V|]\cap \mathbb{Z}$ 是一个一一映射。令一条边 $e = (u,v),e\in E$ 的边权为：$w:e\rightarrow w(e) = \lvert p(u)-p(v) \rvert,e\in E,w(e)\in \mathbb{Z}$。令整棵树的权为：$W:T=(V,E)\rightarrow W(T)=\sum_{e\in E}w(e)$。

另外定义一个图 $G(T)=(V,E')$，其中 $(u,v)\in E'$ 当且仅当在 $T$ 中 $u$ 到 $v$ 路径上点的标号 $p_1,p_2,\cdots , p_l$，要么单调递增，要么单调递减。则 $p$ 必须使得 $G(T)$ 的直径不超过 $2$，即 $\mathop{\max}_{i,j\in V}SP(i,j)\le 2$，其中 $SP(i,j)$ 表示 $G(T)$ 中 $i,j$ 的最短路经过的边数。

现在给定 $T$，求 $M(T)=\mathop{\min}_{p}W(T)$。

并且有若干次操作：在 $T$ 中加入一个新的叶子 $v$（$V\gets V\cup \{v\}$，$E\gets E\cup \{(x,v)\}$，$x\in V_{old}$），每次操作后也要求 $M(T)$。这些操作是一脉相承的。

inputFormat:
第一行一个正整数 $n$ 表示初始的 $\lvert V\rvert$，这些点在接下来的格式中将以 $1$ 到 $n$ 的整数表示，请不要将其与待定的标号 $p$ 混淆；
接下来 $n-1$ 行中，第 $i$ 行两个正整数 $u_i,v_i$，表示初始的 $E=\{(u_i,v_i):i=1,2,\dots ,n-1\}$，保证 $u_i < v_i = i+1$；
接下来一行一个非负整数 $q$ 表示修改次数；
接下来 $q$ 行中，第 $i$ 行一个正整数 $f_i$，表示添加一个点（用 $n+i$ 表示）和一条新边 $(f_i,n+i)$。

outputFormat: 共 $q+1$ 行，每行一个非负整数，依次表示初始和每次修改之后的 $M(T)$。


title: [集训队互测 2018] 完美的队列

description:
小 D 有 $n$ 个 `std::queue<int>`，他把它们编号为 $1$ 到 $n$。

小 D 对每个队列有不同的喜爱程度，如果有他不怎么喜欢的队列占用了太大的内存，小 D 就会不开心。

具体地说，如果第 $i$ 个队列的 `size()` 大于 $a_i$，小 D 就会对这个队列一直执行 `pop()` 直到其 `size()` 小等于 $a_i$。

现在这些队列都是空的，小 D 觉得太单调了，于是他决定做一些操作。

每次操作都可以用 `l r x` 来描述，表示对编号在 $[l,r]$ 内的所有队列执行 `push(x)` 操作。当然，每次操作结束后，小 D 都会用之前提到的方法来避免这些队列占用太大的内存。

小 D 的队列很神奇，所以他能用 $O(1)$ 的时间执行每次操作。

相信大家的队列都能做到，于是小 D 把这道题出给大家送分。

为了证明你确实执行了这些操作，你需要在每次操作后输出目前还在队列内的权值种数。

inputFormat:
第一行两个正整数 $n,m$，分别表示队列个数和操作个数。

第二行 $n$ 个正整数，第 $i$ 个表示 $a_i$。

接下来 $m$ 行，每行三个正整数 `l r x`，其中第 $i$ 行表示第 $i$ 次操作。

outputFormat: 输出共 $m$ 行，每行一个非负整数，表示第 $i$ 次操作结束后所有队列中的权值种数。

hint:
### 样例解释

第一次操作后，队列变成 $\{1\}\{1\}\{\}$，还在队列内的权值有 $1$，共 $1$ 种。

第二次操作后，队列变成 $\{1\}\{1,2\}\{2\}$，还在队列内的权值 $1,2$，共 $2$ 种。

第三次操作后，队列变成 $\{3\}\{2,3\}\{2,3\}$，还在队列内的权值有 $2,3$，共 $2$ 种。

### 数据范围

对于所有数据，$n,m,a_i,x\leq 10^5$，$l\leq r$。

共 $20$ 个测试点，每个测试点 $5$ 分，其中第 $k$ 个测试点满足 $n,m,a_i,x\leq 5000k$。

特别地，以下几个测试点满足一些特殊性质：

测试点 $5$：$a_i=1$；
测试点 $7$：$a_i=2$；
测试点 $9$：$a_i=10$；
测试点 $11$：$a_i\leq 10$；
测试点 $13,15$：$\sum a_i\leq 10^6$。

对于每个测试点，你需要通过满足该点数据范围及性质的所有数据才能获得该点的分数。


title: [集训队互测 2018] 完美的集合

description:
小 A 有一棵 $N$ 个点的带边权的树，树的每个节点有重量 $w_i$ 和价值 $v_i$。

现在小 A 要从中选出若干个节点形成一个集合 $S$，满足这些节点重量之和 $\leq M$ 并且构成一个连通块。小 A 是一个完美主义者，因此他只会选择节点价值之和最大的那些 $S$。我们称这样的集合 $S$ 为完美的集合。

现在小 $A$ 要从所有完美的集合中选出 $K$ 个，并对这 $K$ 个完美的集合分别进行测试。在这 $K$ 次测试开始前，小 A 首先需要一个点 $x$ 来放置他的测试装置，这个测试装置的最大功率为 $Max$。

接下来的每次测试，小 A 会对测试对象 $S$ 中的所有点进行一次能量传输，对一个点 $y$ 进行能量传输需要的功率为 $dist(x,y)\times v_y$，其中 $dist(x,y)$ 表示点 $x,y$ 在树上的最短路长度。因此，如果 $S$ 中存在一个点 $y$，满足 $dist(x,y)\times v_y>Max$，测试就会失败。同时，为了保证能量传输的稳定性，测试装置所在的点 $x$ 需要在集合 $S$ 中，否则测试也会失败。

现在小 A 想知道，有多少种从所有完美的集合选出 $K$ 个的方法，使得他能找到一个放置测试装置的点，来完成他的测试呢？

你只需要输出方案数对 $11920928955078125$ 取模的结果。

inputFormat:
第一行四个正整数，表示 $N,M,K,Max$。

接下来一行 $N$ 个正整数，表示 $w_1,\dots,w_N$。

接下来一行 $N$ 个**非负**整数，表示 $v_1,\dots,v_N$。

接下来 $N-1$ 行，每行三个正整数 $A_i,B_i,C_i$，表示树上存在一条长度为 $C_i$ 的边连接节点 $A_i,B_i$。


title: [集训队互测 2018] 完美的旅行

description:
小 A 有一张 $n$ 个点的图，点的标号为 $0$ 到 $n-1$。点 $i$ 到点 $j$ 有 $A_{i,j}$ 条有向边。可能有自环。

现在小 A 要在图上进行若干次旅行。每次旅行都是选任意一个起点，走至少一步，走到任意一个终点。定义一次旅行的愉悦值为起点与终点编号按位与的值。

好奇的小 B 想要知道：对于所有 $x \in [1,m]$ 和 $y \in [0,n)$，小 A 进行了若干次旅行，总共走了 $x$ 步，且所有旅行的愉悦值的按位与为 $y$ 的方案数。

两种方案不同当且仅当旅行次数不同或某一次旅行不完全相同。

为了防止输出过多，你只需要输出这 $n\times m$ 个数对 $998244353$ 取模后的结果的按位异或值。

为方便起见，保证 $n$ 是 $2$ 的幂次。

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

后面一个 $n\times n$ 的矩阵，第 $i$ 行第 $j$ 列的数表示点 $i-1$ 到点 $j-1$ 的有向边的数量。

outputFormat: 输出一个数表示 $n\times m$ 个答案取模后的异或值。


title: 「DTOI-5」校门外的枯树

background: 某天放学，你走出了校门，发现校门外又双叒叕出现了一排树。只不过因为正值寒冬时节，树的叶子都掉光了，树们在寒风中瑟瑟发抖，让人担心它们会不会在某一时刻失去平衡，然后倒下来。

description:
给你校门外的一排 $T$ 棵无向有根树（每棵树的根节点编号均为 $1$），每棵树的每条边有其重量 $m_i$，现在请你算出每棵树的不平衡度 **或** 该树的**每个节点的子树**的不平衡度，好让校方帮忙加固。$\color{white}\sout{\text{不要问我为什么重量的字母是 }m\text。}$

注意这里的**树的边是有顺序的**，~~你总不可能把树枝掰断然后嫁接到另一个地方吧，这可是枯树啊喂~~。

---

对于一颗有根树，定义其不平衡度为该树被在根节点与某一叶子节点的一条最短路径分割为左右两部分（两个边集）后（两个边集均不含该最短路径中的边）两部分的边的总重之差的最小值。特别地，**单个点作为树的不平衡度为 $0$**；空边集内边的总重为 $0$。

inputFormat:
最开始一行读入两个正整数 $T,k$，$T$ 表示数据组数（即树的总数）。在每组测试数据中，如果 $k=1$，那么你只需要算出整个树的不平衡度即可；如果 $k=2$，**你需要分别对每个节点计算出其子树的不平衡度**。

对于每棵树，第一行读入一个正整数 $n$，$n$ 表示该树内的节点数。

后 $n$ 行，第 $u$ 行描述一个节点，该节点编号为 $u$：
- 第一个正整数，表示该点的儿子个数，记为 $x$。
- 后有 $2x$ 个正整数，第 $2i-1$ 个数表示 $u$ 点**从左往右**第 $i$ 个儿子 $v$，第 $2i$ 个数表示连接 $u$ 与 $v$ 的边的重量 $m_{u\leftrightarrow v}$。

outputFormat:
输出 $T$ 行：
- 如果 $k=1$，第 $i$ 行仅输出一个非负整数表示第 $i$ 棵树的不平衡度。
- 如果 $k=2$，第 $i$ 行输出 $n$ 个非负整数，第 $j$ 个数表示第 $i$ 棵树中的第 $j$ 号节点的子树的不平衡度。

hint:
**【数据范围】**

**不捆绑测试**，同一 $\text{Subtask}$ 内每个测试点等分。

$$
%\def\or{\operatorname{or}}
%这 arraystretch 咋老是拼错/oh
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|}\hline
\textbf{Subtask}&\sum n\leqslant&k=&\textbf{Special Constraints}&\textbf{Score}\cr\hline
\sf1&2\times10^5&1&\bf A&1\cr\hline
\sf2&20&1&T=1&5\cr\hline
\sf3&5000&1&&5\cr\hline
\sf4&10^5&2&\bf B&15\cr\hline
\sf5&3\times10^5&1&&30\cr\hline
\sf6&2\times10^5&2&\bf A'&4\cr\hline
\sf7&3\times10^5&2&&40\cr\hline
\end{array}
$$
- 特殊性质 $\bf A$ ~~限宽 2.6m~~：保证每棵树只有一个叶子节点（$n\geqslant2$）。
- 特殊性质 $\bf B$ ~~限高 4.5m~~：保证每棵树都为菊花图（根节点有 $n-1$ 个儿子）。
- 特殊性质 $\bf A'$：保证每棵树都是链（每个节点的度数不超过 $2$）。

关于 $\bf A$ 和 $\bf A'$ 的区别：$\bf A'$ 中有可能树的根的度数为 $2$，而 $\bf A$ 中根的度数显然为 $1$。

对于 $100\%$ 的数据，$T \leqslant 4000$，${\color{red}\textbf1}\leqslant n\leqslant 10^5$，$\sum n\leqslant 3\times10^5$，$1 \leqslant m_i \leqslant10^4$，$1\leqslant u, v\leqslant n$，$k\in\{1,2\}$。

---
叶子节点为没有儿子的节点，即除根节点以外在树中的度为 $1$ 的点。

样例输入中为方便阅读加上了空行，实际数据中没有空行。

**【样例 $\bm1-\bm1$ 解释】**

该树如下图所示，边权即边的重量。

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

最优解为选择 $1\to2\to7$ 作为分割路径，不平衡度为 ${\large\vert}(2+19+19)-7{\large\vert}=33$。

如果选择 $1\to2\to6$ 作为分割路径，那么两部分的边的总重之差为 ${\large\vert}(2+19)-(7+514){\large\vert}=500$，不为最小值。

$\color{transparent}\sout{不知道你们发现没有\begin{cases}114+2+19+19=154\\114+514+19+19=666\end{cases}}$

**【样例 $\bm1-\bm2$ 解释】**

该树如下图所示。

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

最优解为选择 $1\to7$ 作为分割路径，不平衡度为 ${\large\vert}(4+8+3+6)-(1+7+5+10){\large\vert}=2$。


title: 「AWOI Round 2 C」数组操作？数组操作！

description:
给定两个长度为 $n$ 的数组 $a,b$ ，将它们合并得到一个长度为 $2\times n$ 的数组 $c$。

设 $a$ 数组第 $i$ 个元素合并后位于 $c$ 数组第 $lb_i$ 个位置，$b$ 数组第 $i$ 个元素合并后位于 $c$ 数组第 $lc_i$ 个位置，合并后需要满足：$lb_1 < lb_2 < ...< lb_{n-1} < lb_n$ 且 $lc_1 < lc_2< ...< lc_{n-1}< lc_n$，即两个数组中元素的相对位置不变。

合并过后，你需要对 $c$ 数组进行下面操作：

1. 变换操作：选择一个区间 $[l,r]$，对于每一个 $i \in [l,r]$，如果 $c_i$ 为 $y$，则将其变成一个不同于 $y$ 的数，否则将其变为 $y$。
2. 翻转操作：选择一个区间 $[l,r]$，翻转该数组区间中的数。此操作**必须刚好**操作 $z$ 次。

请输出最少需要执行多少次变换操作才能使得 $c$ 数组中的数字都为 $y$。

inputFormat:
第一行包含三个整数 $n,y,z$。

第二行包含 $n$ 个整数，代表 $a$ 数组中的元素。

第三行包含 $n$ 个整数，代表 $b$ 数组中的元素。

outputFormat: 一个正整数，表示答案。


title: [入门赛 #9] 大碗宽面 (Hard Version)

background:
**本题与 Easy Version 题意完全相同，仅有 $n$ 的数据范围和空间限制不同**。

扶苏和她的朋友们在 Impart 酒店开派对。

description:
算上扶苏，本次派对共有 $n$ 个人。但是，并不是任何两个人都互相认识，并且互相认识的人关系也未必好。

具体而言，任意两个人可能是如下三种关系之一：
1. 敌人
2. 朋友
3. 陌生人

派对的一大重要活动是相互握手。对任意两个人 $u,v$，他们之间的握手情况遵循下面的规则：
1. 如果 $u$ 和 $v$ 是朋友关系，那么他们一定握手一次。
2. 如果 $u$ 和 $v$ 是敌人关系，那么他们一定**不**握手。
3. 如果 $u$ 和 $v$ 是陌生人关系，且存在一个人 $w$，使得 $w$ 是 $u$ 和 $v$ 之一的朋友，同时是 $u,v$ 中另一人的敌人，则 $u$ 和 $v$ **不会**握手，否则 $u$ 和 $v$ 一定握手一次。

对第三条规则，简单的说法是：一对陌生人之间，如果某一方的朋友是另一方的敌人，则不握手，否则握手。

已知共有 $p$ 对人是朋友关系，$q$ 对人是敌人关系。除了这 $p + q$ 对人，其他每对人均为陌生人关系。

请你求出本次派对一共握手了多少次。

inputFormat:
第一行是三个整数，依次表示参加派对的人数 $n$，朋友关系的条数 $p$ 和敌人关系的条数 $q$。
接下来 $p$ 行，每行两个整数 $u,v$，表示 $u$ 和 $v$ 是朋友关系。
接下来 $q$ 行，每行两个整数 $u, v$，表示 $u$ 和 $v$ 是敌人关系。

outputFormat: 输出一行一个整数，表示本次派对的握手次数。

hint:
### 样例 1 解释

共有 $(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)$ $6$ 对人。
- $(1,2)$ 是朋友，握手。
- $(1,3)$ 是敌人，不握手。
- $(1,4)$ 是敌人，不握手。
- $(2,3)$ 是朋友，握手。
- $(2,4)$ 是陌生人，但是 $1$ 是 $2$ 的朋友，也是 $4$ 的敌人，所以不握手。
- $(3,4)$ 是陌生人，但是不存在任何一个人既是 $3$ 和 $4$ 之一的敌人也是另一个人的朋友，故握手。

综上，一共握手 $3$ 次。

### 数据规模与约定

以下设 $m = p + q$，即 $m$ 是朋友和敌人关系条数之和。

- 对 $100\%$ 的数据，保证 $2 \leq n \leq 10^6$，$1 \leq u, v \leq n$，$0 \leq p,q \leq m \leq 10^3$，$u \neq v$。同一对敌人或朋友关系不会出现两次，不会有一对人同时是敌人或朋友关系。

By 一扶苏一


title: [语言月赛202302] 牵连的世界 (Easy Version)

description:
下面程序想要实现的功能为：

> 输入 $n$ 和 $n$ 个数，统计其中奇数的个数。

```cpp
#include <iostream>
using namespace std;

int main() {
  int n, ans = 0;
  cin >> n;
  for(int i = 1, x; i <= n; i++) {
    cin >> x;
    if(x % 2 == 1) ++ans;
  }
  cout << ans << endl;
}
```

但是这个程序存在一些问题，请你提交一个程序，**你提交的程序应当输出一组这道题的输入数据，使得上面的程序输出错误的结果**。

inputFormat: 无输入

outputFormat:
你提交的程序输出的输入数据应当符合下面的格式：

> $n$
>
> $a_1\ a_2\ \cdots \ a_n$

第一行为一个整数 $n(1 \le n \le 1000)$。

第二行为 $n$ 个整数 $a_i(-10^6 \le a_i \le 10^6)$，每两个整数之间由一个空格隔开。


title: [语言月赛202303] Carrot Harvest G

description:
有 $n$ 行 $m$ 列共 $n \times m$ 个坑，每个坑可能有一个萝卜，也可能没有。

现在 Farmer John 需要至少拔 $k$ 个萝卜，他只能挑一个矩形（长方形或正方形）区域的坑进行拔萝卜。

请你求出，为了至少拔 $k$ 个萝卜，他需要挑的矩形面积（坑的数量）最小是多少。

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

第一行为三个整数 $n, m, k$。

第二行至第 $n + 1$ 行，每行 $m$ 个只可能为 $0$ 或 $1$ 的整数。其中第 $i + 1$ 行的第 $j$ 个整数为 $a _ {i, j}$，代表第 $i$ 行第 $j$ 列的坑中是否有萝卜。$a _ {i, j} = 1$ 代表有萝卜，$a _ {i, j} = 0$ 代表没有萝卜。

outputFormat: 输出共一行一个整数，代表为了至少拔 $k$ 个萝卜，Farmer John 需要挑的矩形的最小面积（坑的数量）。


title: [信息与未来 2017] 龟兔赛跑

description:
兔子又来找乌龟赛跑啦！同样的错误兔子不会犯两次，所以兔子提出赛跑的时候，乌龟就觉得这场比赛很 不公平。于是兔子进一步放宽了条件，表示他可以在比赛开始以后先睡 $t$ 分钟再开始追乌龟。

乌龟这下没办法确定比赛到底公平不公平了，所以请你来帮忙。假设乌龟每分钟可以跑 $x$ 米，兔子每分钟跑 $y$ 米 $(x\lt y)$。他希望你计算最大的整数赛跑距离 (米)，满足乌龟能在兔子先睡 $t$ 分钟的前提下，比兔子更早或同时到达终点。

inputFormat: 三个整数 $x,y,t$。

outputFormat: 一个整数，表示要求的最长赛跑距离。

hint:
$1\leq x\lt y\leq 100,t\leq 1000$。

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2017] 密码锁

description:
乌龟给自己的贵重物品上了密码锁。密码锁上有 $5$ 个数字拨盘。每个数字拨盘每次向上拨使数字增加 $1$ （$9$ 向上拨得到 $0$），向下拨使数字减少 $1$ （$0$ 向下拨得到 $9$）。

拨盘上的数字组成一个 $5$ 位数。只要拨盘上的数字变为素数，密码锁就会被解开。素数 (又称质数) 是只能被 $1$ 和它自身整除的大于 $1$ 的自然数。因为乌龟动作实在太慢，他希望你帮他计算如何开锁，使得拨动的总次数最少。

inputFormat: 一个 $5$ 位数，表示拨盘的初始数字。

outputFormat: 一个 $5$ 位素数，表示开启密码锁使用的素数（拨动次数最少）。如有多组解，输出满足条件的最大数。

hint: >本题原始满分为 $15\text{pts}$。


title: [信息与未来 2017] 房屋积水

description:
乌龟家的屋顶是凹凸不平的，所以每次雨后都会积水。为了知道屋顶是否会在暴雨后塌掉，他把屋顶的形状给了你，希望你帮他计算暴雨后屋顶的积水总量。

乌龟的屋顶由顺次排在同一水平线上的 $n$ 个宽度为 $1$、高度为整数 (分别给出) 的瓦片组成。例如给定 $n=5$，瓦片的高度分别为 $4,2,3,5,1$，屋顶可以画在下图所示的网格中，灰色格子为瓦片。

暴雨过后，如果一个方格向左右两侧延伸都能到达瓦片占据的方格，它就会积水。所以图中波浪线格子在暴雨后会积水，屋顶的积水方格总数为 $3$。

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

---

试题中使用的生成数列 $R$ 定义如下：整数 $0\leq R_1\lt 201701$ 在输入中给出。

对于 $i\gt 1,R_i=(R_{i−1}\times 6807+2831)\mod 201701$。

inputFormat: 两个整数 $n,R_1$，表示屋顶的宽度和生成数列的首项。从左向右数第 $i(1\leq i\leq n)$ 个瓦片的高度 $a_i=R_i\mod 10$。

outputFormat: 一个整数，表示暴雨后屋顶积水方格的总数。

hint:
$1\leq n\leq100$。

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2017] 任务调度

description:
乌龟因为动作太慢，有 $n$ 个任务已经超过截止日期
了。乌龟处理第 $i$ 个任务需要 $a_i$ 单位时间。从 $0$ 时刻开始，乌龟可以选择某项任务，完成它，然后再开始另一项任务，如此往复直到所有任务都被完成。

由于已经超过截止日期，乌龟会为此受到一定的惩罚，惩罚值等于所有任务完成时刻之和。例如，有 2 个
任务分别需要 $10$ 和 $20$ 单位时间完成。如果先完成任务 1，惩罚值为 $10+30=40$；如果先完成任务 2，惩罚值为 $20+30=50$。

乌龟希望你求出惩罚值最小的完成任务的顺序。

---

试题中使用的生成数列 $R$ 定义如下：整数 $0\leq R_1\lt 201701$ 在输入中给出。

对于 $i\gt 1,R_i=(R_{i−1}\times 6807+2831)\mod 201701$。

inputFormat: 两个整数 $n,R_1$，表示任务的数量和生成数列的首项。处理任务 $i(1\leq i\leq n)$ 的时间 $a_i=(R_i\bmod 100)+1$。

outputFormat: 一个整数，表示完成所有任务的最小惩罚值。

hint:
对于 $100\%$ 的数据，$1\leq n\leq10^3$。

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2017] 基因组分析

description:
乌龟得到了他的基因组，一个只包含 $\tt{ATCG}$ 四种字母的字符串。乌龟想起科学家说，基因组中很多片段都多次重复出现，而且这种重复是很有意义的，于是他想计算一下自己基因组里片段的重复情况。

给定一个基因组，其中一个长度为 $k$ 的子串称为一个“$k$-片段”。乌龟希望你计算出基因组中不同的 $k$-片段数量。例如，基因组 $\tt{TACAC}$ 的 $2$-片段有 $\tt{TA,AC,CA,AC}$，其中不同的片段数量有 $3$ 个。

---

试题中使用的生成数列 $R$ 定义如下：整数 $0\leq R_1\lt 201701$ 在输入中给出。

对于 $i\gt 1,R_i=(R_{i−1}\times 6807+2831)\mod 201701$。

inputFormat:
整数 $n,k,R_1$，表示基因组的长度、片段的
长度和数列生成的首项。基因组第 $i(1\leq i\leq n)$ 个字符在 $R_i \mod 4$ 的值为 $0,1,2,3$ 时分别为 $\tt{A,T,C,G}$。

outputFormat: 一个整数，表示不同的 $k$-片段的数量。

hint:
$30\%$ 的数据满足 $n\leq100$；

$100\%$ 的数据满足 $1\leq n\leq 10^5,1\leq k\leq 10$。

>本题原始满分为 $20\text{pts}$。


title: [信息与未来 2017] 加强版密码锁

description:
乌龟偶然获得了一个宝箱，宝箱上又有一把密码锁。密码锁由  $n$ 个拨盘组成，每个拨盘初始时有一个 $0$ 到
$99$ 之间的整数。向上拨使数字 $x$ 变为 $(x+1) \bmod 100$，
向下拨使数字 $x$ 变为 $(x+99) \bmod 100$。

因为密码锁年久失修，拨盘拨动的次数越多越费力。
如果一个拨盘被拨动 $k$ 次，需要花费 $k^2$ 单位时间。

密码锁只有在所有的拨盘上的数字形成一个从左到
右严格递增的数列时才会解开。乌龟再次请你帮忙，求
解解开密码锁的最少时间。

---

试题中使用的生成数列 $R$ 定义如下：整数 $0\leq R_1\lt 201701$ 在输入中给出。

对于 $i\gt 1,R_i=(R_{i−1}\times 6807+2831)\bmod 201701$。

inputFormat: 两个整数 $n,R_1$，表示拨盘的数量和数列生成的首项。从左向右数第 $i(1\leq i\leq n)$ 个拨盘的初始数字为 $R_i \bmod 100$。

outputFormat: 一个整数，表示解开密码锁的最少时间。

hint:
$30\%$ 的数据满足 $n\leq3$，所有数据满足 $1\leq n\leq 100$。
>本题原始满分为 $20\text{pts}$。


title: [信息与未来 2018] 圣诞树

description:
圣诞树共有 $n$ 层，从上向下数第 $1$ 层有 $1$ 个星星、第 $2$ 层有 $2$ 个星星、以此类推，排列成下图所示的形状。

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

星星和星星之间用绳子连接。第 $1,2,\cdots, n - 1$ 层的每个星星都向下一层最近的两个星星连一段绳子，最后一层的相邻星星之间连一段绳子。

你能算出如果要布置一棵很大（$n$ 层）的圣诞树，需要买多少段绳子吗？

inputFormat: 输入一行一个整数 $n$，圣诞树的层数。

outputFormat: 输出一行一个整数，代表圣诞树中绳子的段数。

hint:
### 样例解释
#### 样例 $1$
$2$ 层的圣诞树只需 $3$ 段绳⼦。
#### 样例 $2$
参考题图。
### 数据规模
所有数据满足 $1 ≤ n ≤ 10^3$。
> 本题原始满分为 $15\text{pts}$。


title: [信息与未来 2018] 最大公约数

description: 输入三个正整数 $x,y,z$，求它们的最大公约数（Greatest Common Divisor）$g$：最大的正整数 $g ≥1$，满足 $x,y,z$ 都是 $g$ 的倍数，即 $(x \bmod g) = (y \bmod g) = (z \bmod g) = 0$。

inputFormat: 输入一行三个正整数 $x,y,z$。

outputFormat: 输出一行一个整数 $g$，表示 $x,y,z$ 的最大公约数。


title: [信息与未来 2018] 双十一

description:
每年 $11$ 月 $11$ 日，各大网上商店都会有促销活动，因此大家都希望 $11$ 月 $11$ 日在周末，就可以更愉快地购物啦。请你写一个程序计算一段时间中，$11$ 月 $11$ 日是周末（周六或周日）的数量。
以下关于日期的定义和事实能帮到你：
- $1900$ 年 $1$ 月 $1$ 日是星期一。
- 每年的 $1, 3, 5, 7, 8, 10, 12$ 月有 $31$ 天；$4, 6, 9, 11$ 月有 $30$ 天；闰年的 $2$ 月有 $29$ 天，非闰年的 $2$ 月有 $28$ 天。
- 闰年的计算方法：不能被 $100$ 整除的年份称为普通年。普通年能被 $4$ 整除的为闰年，因此$2004$ 年是闰年，$1999$ 年不是闰年；能被 $100$ 整除的年份称为世纪年。世纪年能被 $400$ 整除的是闰年，因此 $2000$ 年是闰年，$1900$ 年不是闰年。

inputFormat: 输入一行两个整数 $x,y$，代表需要计算的起止年份。

outputFormat: 输出一个整数，第 $x$ 年到第 $y$ 年中 $11$ 月 $11$ 日是周末的年数（包括第 $x$ 年和第 $y$ 年）。


title: [信息与未来 2018] 素数方阵

description:
把前 $n^2$ 个素数从左上角开始按右、下、左、上、右、下、左、上……的顺序填入 $n×n$ 的方阵就得到了蛇形素数方阵。以下是 $n = 4$ 和 $n = 5$ 的蛇形素数方阵：

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

给出 $n$，你的任务是求出 $n × n$ 的蛇形素数方阵，并输出其中某个方格中的数值。

素数，又称质数，是指除 $1$ 和其自身之外，没有其他约数的大于 $1$ 的正整数。

inputFormat: 输入一行三个正整数 $n,x,y$。

outputFormat: 输出一行一个整数，表示 $n×n$ 蛇形素数方阵第 $x$ 行第 $y$ 列中的数字。

hint:
### 样例解释
参考上图 $n = 5$。
### 数据规模
所有数据满足 $1 ≤ x,y\le n ≤ 20$。

> 本题原始满分为 $15\text{pts}$。


title: [信息与未来 2018] 整数乘方

description:
定义 $a$ 的 $n$ 次幂 $a^n = a × a × \cdots × a$（共 $n$ 个 $a$ 相乘）。记 $a^n$ 的十进制表示转换为字符串后奇数字符（阿拉伯数字 $1, 3, 5, 7, 9$）的个数为 $A$，偶数字符（阿拉伯数字 $0, 2, 4, 6, 8$）的个数为 $B$，求 $A-B$ 的数值。

例如，$a = 3, n = 12, a^n = 3^{12} = (531441)_{10}$。

奇数数位用方框标出：$\boxed{5}\boxed{3}\boxed{1}44\boxed{1}$，故 $A = 4$；

偶数数位用方框标出：$531\boxed{4}\boxed{4}1$, 故 $B = 2, A-B = 2$。

inputFormat: 输入一行两个整数 $a, n$。

outputFormat: 输出一行一个整数，代表 $A − B$ 的值。


title: [信息与未来 2018] 棋盘游戏

description:
给定一个十进制数 $x$，将它转换为二进制字符串并在高位填 $0$ 以补足 $16$ 位，就得到了
一个长度为 $16$ 的 $01$ 字符串，我们用这个字符串表示 $4 × 4$ 的棋盘，按从左到右、从上到下的顺序将 $0$（白子）、$1$（黑子）放入棋盘。

例如，$(447)_{10} = (0000 0001 1011 1111)_2$，按顺序填入棋盘（$0$ 白子、$1$ 黑子），得到如下棋盘（左边棋盘）：

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

我们现在可以交换棋盘中**相邻**（共享一条边的两个格子相邻，因此一个格子至多有 $4$ 个相邻的格子）的黑色和白色棋子。从左图的棋盘变为全部白子在上、全部黑子在下（右边棋盘所示）的棋盘，至少需要 $3$ 步。

对于给定的棋盘（保证棋盘中恰好有 $8$ 个白子和 $8$ 个黑子），求把棋盘变为全部白子在上、全部黑子在下最少的交换步数。

inputFormat: 输入一行一个整数 $x$，为十进制表示下的棋盘。

outputFormat: 输出一行一个整数，最少需要交换的步数。

hint:
### 样例解释
#### 样例 $1$
参考上图，将 $(2, 4)$ 处的⿊⼦移动到 $(3, 2)$ 需要 $3$ 步。
#### 样例 $2$
如下图所示，$(42405)_{10} =(1010 0101 1010 0101)_2$。

![](https://cdn.luogu.com.cn/upload/image_hosting/aie8kf0n.png)
### 数据规模
$50\%$ 的测试数据满足棋盘可以在 $6$ 次交换内变为白子在上、黑子在下。

所有数据保证 $0 ≤ x < 2^{16}$，且 $x$ 转换为二进制后恰好有 $8$ 个 $1$。

> 本题原始满分为 $20\text{pts}$。


title: [北大集训 2021] Datalab

background:
CTT2021 D2T2

**特别提醒，由于洛谷交互机制的特殊性，你不能在程序中引用 `datalab.h`，而需要把 `datalab.h` 中的内容加入文件的开头。即，在程序中 `solve` 函数的前面加入以下几行语句：**

```cpp
#include<bitset>
#include<vector>
typedef std::bitset<8192> Bitset;
Bitset Add(Bitset A,Bitset B);
std::vector<int> solve(int k,int LIMIT);
```

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

在 AutoLab 平台上有一台奇怪的 $k$ 位计算机，其中 $k$ 是一个固定的常数 $8192 = 2^{13}$。这台计算机的字长恰好为 $\frac{k}{8} = 1024 = 2^{10}$，且其存储整数的方式如下：

每个整数会存储在连续的 $k$ 个 bit 中。假设将这 $k$ 个连续 bit 的值按照下标从小到大顺次排列后得到的长度为 $k$ 的 01 字符串为 $S$。假设 $S$ 的下标从 $0$ 开始，则这个字符串 $S$ 对应的整数值为 $f(S) = \sum \limits_{i=0}^{k-1} [S_i=1] sgn_i 2^i$，其中 $sgn$ 是一个小 W 预先定义的长度为 $k$ 的数组，其下标从 $0$ 开始且 $\forall 0 \le i < k,sgn_i \in \{-1,1\}$。出于某些特殊的原因，这台计算机上保证了 $sgn_{k-1} = 1$，$sgn_{k-2} = -1$。而你不知道 $sgn_0,sgn_1,\cdots,sgn_{k-3}$ 的值。

假设 $L = \sum \limits_{i=0}^{k-1} \min\{0,sgn_i\} 2^i$，$R = \sum \limits_{i=0}^{k-1} \max\{0,sgn_i\} 2^i$，则发现 $\forall L \le x \le R$，恰好有一个长度为 $k$ 的 01 字符串 $f(T)$，使得 $f(T) = x$（证明略去）。不妨设所有 $[L,R]$ 内的整数构成的集合为 $S$，则 $f$ 是一个从 $\{0,1\}^n$ 到 $S$ 的双射。据此我们可以设 $f(x)$ 的反函数 $g(x)$ 存在，且其满足 $\forall x \in S,f(g(x)) = x$。

假设存在 $x,y \in S$ ，则在该计算机上两个整数之间的加法 $\oplus$ 被定义为 $x \oplus y \overset{def}{=} (x + y - L + 2^k) \bmod 2^k + L$。不难发现 $\forall x,y \in S,x \oplus y \in S$。因而在这台计算机上加法满足封闭性。同时按照如上规则定义的加法也满足交换律，结合律等性质。这些性质的证明也同样略去。

学生可以通过有限次的询问获得和 $sgn_i$ 相关的信息。每次询问你可以给计算机两个长度为 $k$ 的仅包含 $0,1$ 的字符串 $x,y$，而计算机会返回 $g(f(x) \oplus f(y))$ 的值。本次的作业要求是在不超过 $m$ 次的询问中求出 $sgn_0,sgn_1,\cdots,sgn_{k-3}$ 的准确值。

小 Z 是一名聪明绝顶的学生，因而他尝试使用他的 $10^3 \mathrm{Hz}$ 的超强大脑来手算出每次交互的值。但是他发现给他的处理速度还是跟不上庞大的数据规模。因而它请你帮忙写一个程序，帮助他更快速的完成本次的作业。

---

### 任务

你不需要，也不应该实现主函数，你只需要实现如下一个函数：

1. `std::vector<int> solve(int k,int m)`：

	- 传入数字的是计算机的字长 $k$ 和询问次数限制 $\mathrm{m}$。
	- 你需要返回一个大小为 $k$ 的 `vector`，其第 $i$ 个元素代表你确定的 $sgn_i$ 的值。

你可以通过如下函数调用 Autolab 上的加法操作。

1. `std::bitset<8192> Add(std::bitset<8192> x,std::bitset<8192> y)`：
	- 给定两个大小为 $k$ 的 bitset, 每个 bitset 自低位向高位阅读的结果代表了一个长度为 $k$ 的仅包含 01 的字符串。
	- 返回一个大小为 $k$ 的 bitset, 表示 $g(f(x) \oplus f(y))$ 的值。返回的格式和输入的格式相同。

根据题目要求，你至多只能询问 $\mathrm{m}$ 次两个整数在这台计算机上的加法结果。也就是说你至多只能调用 $\mathrm{m}$ 次 `Add` 函数。

评测时，交互库会**恰好**调用 `solve` 一次。

**本题保证所使用的数组 `sgn` 在开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。**

**数据保证在调用次数限制下，交互库运行所需的时间不超过 1s；交互库使用的内存大小固定，且不超过 128MB。**

---

### 如何测试你的程序

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

1. 你需要在本题目录下使用如下命令编译得到可执行程序：
   - `g++ grader.cpp sample.cpp -o sample -O2 -lm`

2. 对于编译得到的可执行程序：
   - 可执行文件将从**标准输入**读入以下格式的数据：
     - 第一行包含两个整数 $k,\mathrm{m}$。
     - 接下来一行 $k$ 个整数，第 $i$ 个数字表示 $sgn_i$。
   - 读入完成之后，交互库将调用恰好一次函数 $\texttt{solve}$ 你的函数正确返回后，交互库会判断你的计算是否正确，若正确则会输出 `Correct` 和交互函数调用次数相关信息，否则会输出相应的错误信息。

试题目录下有出题人提供的一份参考代码 `sample.cpp`，注意这份代码 **不保证可以通过所有的测试用例**。

---

### 样例一、二

见附件下载。

这两个样例满足可执行程序的输入格式，因而可以直接输入到可执行程序中。


title: [CEOI2022] Abracadabra

description:
Tin 是一位著名的魔术师，他的一个经典魔术与洗牌有关。

Tin 会准备一套牌，总共 $n$ 张（保证 $n$ 为偶数），各编号为 $1\sim n$，一开始的时候牌是乱的且倒扣在桌子上。紧接着他开始表演洗牌，在洗牌的任意时刻，观众都可以向 Tin 询问从底往上数第 $t$ 张牌是什么牌，很显然 Tin 一定会立即回答出正确答案。

事实上，Tin 采用如下方式来完成这个魔术，首先他记下了一开始的 $n$ 张牌的顺序，接着采用如下技巧洗牌：

1. 拿起自顶向下 $\frac{n}{2}$ 张牌放在右手，自底向上 $\frac{n}{2}$ 张牌放在左手，牌的正面对着桌子。
1. 借助他的记忆，将左右手最底下的牌进行比较，将编号较小的那张牌放下，重复这个操作直到左右手一边为空。
1. 将还有牌的那只手上的所有牌放下。

请你写一个程序模拟 Tin 的魔术。

inputFormat:
第一行两个整数 $N,Q$。

接下来一行 $N$ 个整数 $p_i$，从底向上描述了整个牌堆。

接下来 $Q$ 行，一行一个询问 $t,i$，表示询问 $t$ 次洗牌后自底向上第 $i$ 张牌编号是多少。

outputFormat: 对于每一个询问，输出你的答案。


title: [CEOI2022] Homework

description:
这是 Helena 的数学作业中的一道题：

我们定义合法表达式如下：

- `?` 是合法表达式，这表示一个未知数。
- 如果 $A,B$ 均为合法表达式，那么 `min(`$A$`,`$B$`)` 和 `max(`$A$`,`$B$`)` 均为合法表达式，这分别表示取左右两边的最大值/最小值。

设 `?` 的个数为 $N$，现在给出一个合法表达式，将每一个问号替换为 $1\sim N$ 中的任意一个数并且每一个数不能使用多次，可以得到多少种不同的答案？

可怜的 Helena 并不会做，请你帮帮她。

inputFormat: 仅一行一个字符串表示给出的合法表达式。

outputFormat: 输出一个整数，表示不同答案的个数。


title: [CEOI2022] Drawing

description:
给定平面上的 $N$ 个点，和一棵大小为 $N$ 的树 $T$，保证这棵树上每个点的度数至多为 $3$，树上节点按 $1\sim N$ 编号。

你需要为平面上的点使用 $1\sim N$ 的编号重编号之后，对于所有树上的边 $e=(u,v)$，将平面上的点 $u$ 和平面上的点 $v$ 用线段连接后，任意两条线段除了在端点上相交没有其他的相交点。

试构造一组方案，保证一定有解。

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

接下来 $N-1$ 行，一行两个整数 $a,b$，表示有一条从 $a$ 连向 $b$ 的边。

接下来 $N$ 行，一行两个整数 $x,y$，表示一个点的横纵坐标为 $(x,y)$。保证这 $N$ 个点两两不同，且没有任意三点共线。

outputFormat: 输出一行 $N$ 个整数，第 $i$ 个数应为原本的第 $i$ 个点的标号。


title: [CEOI2022] Measures

description:
有 $N$ 个站在数轴上的人，他们的初始位置分别为 $a_1,a_2,\ldots,a_N$，他们可以以 $1$ 个单位长度每秒的速度移动。

因为众所周知的原因，他们需要保持社交距离，也就是说在任两个人之间距离至少为 $D$。

Alenka 设计了一个 app 来快速求出这 $N$ 个人通过移动来保持社交距离的最小时间，现在她想要添加一个新功能：支持动态加入一个位置为 $b_i$ 的人。

你需要实现一个程序完成这个功能。

inputFormat:
第一行三个整数 $N,M,D$。

接下来一行 $N$ 个整数 $a_1,\ldots,a_N$，表示初始的 $N$ 个人。

接下来一行 $M$ 个整数 $b_1,\ldots,b_M$，表示顺次加入的 $M$ 个人。

outputFormat: 输出一行 $M$ 个数，第 $i$ 个数表示加入第 $i$ 个人之后所花费的最小时间，你需要输出这个时间的精确值，不含末尾多余的 $0$。


title: [CEOI2022] Parking

description:
Valerija 在一家饭店的停车场工作，她负责礼貌地接待重要的客人，保管他们的车钥匙并帮助他们停车。

一个晚上，她发现她管理的停车场中恰好有 $2N$ 辆车，它们共有 $N$ 种不同的颜色，每种颜色恰有两辆车。我们将颜色按 $1$ 到 $N$ 编号。

停车场共有 $M$ 个车位，按 $1$ 到 $M$ 编号，每一个车位可以停下两辆车，一个车位只有一个入口，我们称靠近入口的为「顶上的车」，远离入口的为「底下的车」，一辆车可以从入口开出当且仅当没有车挡着它。Valerija 在停车的时候，保证每个车位要么空，要么停满两辆车，要么只有一辆底下的车。

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

这张图描述的是第一个样例，同时呈现了唯一的第一次驾驶。

Valerija 想要重新停放车使得每一对相同颜色的车都在一个车位里。我们并不关心车位对应什么颜色以及哪辆车在顶上哪辆车在底下。Valerija 将执行如下操作：

- 驾驶一辆可以驶出车位的车，将车开到另一个车位，满足：
    - 这个车位是空的，并把车停在底下的车位，或者，
    - 这个车位有且只有一辆与当前驾驶的车颜色相同的车。

Valerija 想知道最少的操作次数与操作方案，请你解决这个问题。

inputFormat:
第一行两个整数 $N,M$。

接下来 $M$ 行，一行两个整数 $b_i,t_i$，$b_i$ 表示停在这个车位底下的车的颜色，$t_i$ 表示停在这个车位顶上的车的颜色，如为 $0$，则表示这个车位底下/顶上的位置没有车。

outputFormat:
如果没有办法完成要求，输出一行一个整数 $-1$。

否则，第一行一个整数 $K$，表示最少的操作次数。

接下来 $K$ 行，一行两个整数 $x_i,y_i$，表示第 $i$ 次操作将车位 $x_i$ 中可以驶出车位的车开到车位 $y_i$。

注意到最短解可能不唯一，你只需要输出任意一种即可。


title: 「DROI」Round 2 单图

background: 与其编写苍白无力的背景，不如出更有质量的题。

description:
我们称[简单有向图](https://www.luogu.com.cn/paste/4oz6fep2) $G,H$ **本质相同**，当且仅当：

- 对于任意点对 $(u,v)$，若在图 $G$ 中从 $u$ 出发能走到 $v$，则在图 $H$ 中从 $u$ 出发能走到 $v$。反之若在图 $H$ 中从 $u$ 出发能走到 $v$，则在图 $G$ 中从 $u$ 出发也能走到 $v$。

若对于简单有向图 $G$，不存在其他简单有向图 $H$ 与其本质相同，则我们称图 $G$ 为 **单图**。

$T$ 次询问，每次询问给定一个正整数 $n$，请你回答 $n$ 个点的**有标号**单图数。

inputFormat:
**本题采用多组输入。**

第一行输入两个整数 $T,mod$，表示数据组数与模数。

接下来 $T$ 行每行一个整数，表示这组数据的 $n$。

outputFormat: 输出 $T$ 行，第 $i$ 行表示第 $i$ 组数据的答案对 $mod$ 取模的值。

hint:
#### 数据范围

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

- $\operatorname{Subtask} 1(30\%)$：$T = 1$，$n \leq 5$。

- $\operatorname{Subtask} 2(50\%)$：$T \leq 10$。

- $\operatorname{Subtask} 3(20\%)$：无特殊限制。

对于 $100\%$ 的数据满足：$1 \leq T,n \leq 1000$，$1\leq mod \leq 10^9$。

#### 说明提示

这里给出一些例子来帮助理解单图的含义：

------------

![](https://cdn.luogu.com.cn/upload/image_hosting/kykl8fg8.png)[](https://www.luogu.com.cn/paste/0tbbkesd)

这是一张单图，可以证明不存在其他图与其本质相同。

------------

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

这不是一张单图，因为我们可以添加边 $(5,2)$ 构造出与其本质相同的图。

------------

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

这不是一张单图，因为我们可以删去边 $(1,3)$ 构造出与其本质相同的图。


title: [YsOI2023] 广度优先遍历

background:
Ysuperman 模板测试的图论题。

【数据删除】

description:
今天的模板测试是无向图上的广度优先遍历，【数据删除】马上写好了代码：

```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 100005;
vector<int> G[maxn];
queue<int> q;
int pa[maxn];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    memset(pa, -1, sizeof pa);
    q.push(1);
    pa[1] = 0;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto v : G[u])
        {
            if (pa[v] != -1)
                continue;
            pa[v] = u;
            q.push(v);
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        cout << pa[i];
        if (i != n)
            cout << " ";
    }
    cout << endl;
    return 0;
}
```

如你所见，这份代码会输入一个 $n$ 个点 $m$ 条边的无向图，并且求出这张图以 $1$ 为根的一棵“广度优先遍历树”，最后输出所有点的父亲节点编号。

不过值得注意的是，这棵“广度优先遍历树”的具体形态和“边的输入顺序”有关，也就是说，不同的输入顺序可能会得到不同的父亲节点编号。

现在【数据删除】告诉了你 $n,m$、这 $m$ 条边以及在某个“边输入顺序”情况下他的代码的输出，你需要还原出这个“边输入顺序”。如果有多种边输入顺序对应的都是这样的输出，你**只需要输出其中任意一种**即可。

特别的，保证有解，且无向图连通，无自环（但是有可能有重边）。

inputFormat:
第一行两个正整数 $n,m$ 分别表示无向图的点数和边数。

接下来 $m$ 行每行两个整数 $u,v$ 表示存在 $u$ 与 $v$ 之间存在一条无向边。

最后一行 $n$ 个整数表示【数据删除】代码的输出。（由题意可知他输出的是某个“边输入顺序”情况下他得到的“广度优先遍历树”中 $1\sim n$ 这些节点的父亲节点编号）

outputFormat:
输出包含 $m$ 行，每行两个整数 $u,v$ 表示 $u$ 和 $v$ 之间存在一条无向边，你的输出顺序表示你给出的“边输入顺序”。

请注意，你需要保证如果输入给出的图中 $u,v$ 间连了 $k$ 条边，那么你给出的图中 $u,v$ 间也要连有 $k$ 条边。

如果有多种“边输入顺序”合法，**输出其中任意一种都会被判断为正确**。另外，由于是无向边，所以你输出的**一条边两个点的排列顺序对答案判定没有影响**。

hint:
#### 样例 1 解释

直接运行【数据删除】的代码即可。

如果不改变边输入顺序，将下面数据输入【数据删除】的代码：

```
4 4
2 1
1 3
2 4
4 3
```

他的代码跑出来结果如下：

```
0 1 1 2
```

如果按照样例 1 输出给出的顺序，即，将下面数据输入他的代码：

```
4 4
1 3
3 4
1 2
2 4
```

输出为：

```
0 1 1 3
```

#### 数据范围

对于前 $10\%$ 的数据，满足 $n\le 8$，$m\le 10$。

对于前 $40\%$ 的数据，满足 $n\le 1000$，$m\le 2000$。

另有 $10\%$ 的数据，满足 $m=n-1$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^5$，$1\le m\le 2\times 10^5$。

#### 提示

为什么有可能会有重边，因为懒得去重了，这个家伙出图论题就是懒得判重边的（）

附件下发了本题 checker。


title: [YsOI2023] Prüfer 序列

background:
Ysuperman 模板测试的计数题。

众所周知，Prüfer 序列几乎没有在正赛中出现过，所以它需要出现在洛谷月赛中。

description:
众所周知，一棵 $n$ 个点的有标号无根树与他的 Prüfer 序列一一对应。如果你不知道 Prüfer 序列指的是什么，可以参考下面提示说明中对 Prüfer 序列的解释。

现在给你一个长度为 $m$ 的正整数序列 $a$，其中 $a_i\in[1,n]$。等概率随机选择这个序列的一个长度为 $n-2$ 的子序列（只要选择下标不同就认为两个子序列不同）作为 Prüfer 序列构造得到一棵树 $T$，对于所有 $1\le i<n$，你需要求出 $\mathrm{dist}(i,n)$ 的期望（$\mathrm{dist}(u,v)$ 定义为 $u,v$ 两点简单路径的边数）。

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

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

第二行 $m$ 个整数表示序列 $a$，保证 $1\le a_i\le n$。

outputFormat: 输出 $n-1$ 个非负整数，第 $i$ 个整数表示 $\mathrm{dist}(i,n)$ 的期望。