title: [POI2022~2023R1] zbo

background: 题目译自 [POI2022~2023R1 zbo](https://sio2.mimuw.edu.pl/c/oi30-1/p/zbo/)。

description:
远古时期有一个国王，他统治了 $n$ 个村庄，这些村庄以 $n-1$ 条道路连接，原来的国王城堡在 $1$ 号村庄。

国王的儿子不久就要成年了，作为成年的王子们，其需要自己的城堡，所以在一些村庄会有**新的城堡**。

每座城堡都需要进行通讯，但是无奈距离太过遥远，为此，每个城堡每天都会派出若干个信鸽，向其他每个城堡发送消息。一只信鸽每行驶一公里就要吃一克谷物。

请你实现一个程序，求出按照输入顺序建造的每个城堡建造完之后所有城堡都能通讯的最少花费谷物数量。

具体的，定义 $dis(x,y)$ 为 $x$ 到 $y$ 所花费的谷物数，求每个城堡 $i$ 建造完后的 $\sum ^{i} _{x=1} \sum ^{i}_{y=1} dis(x,y)$。

注意上述式子默认两个相同的地点所花费为 $0$。

inputFormat:
输入第一行两个数字 $n$ 和 $k \ (1 \leq k < n \leq 10^5)$，分别表示村庄数量和即将建造的城堡数量。

接下来 $n-1$ 行，每行三个整数 $a,b,c \ (1 \leq a,b \leq n, a \neq b, 1 \leq c \leq 1000)$，表示 $a$ 到 $b$ 存在一条长度为 $c$ 的无向边。

再接下来 $k$ 行，每行一个整数 $d_{i}$，表示第 $i$ 个城堡建设在 $d_{i}$ 位置上，注意城堡不会重复建在一个位置。

outputFormat: 对于每个建造完的城堡，输出最小花费。


title: [HUSTFC 2023] 序列配对

type: P

description:
你有一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$，初始序列内任意元素 $a_i=0$。

之后会告诉你 $n$ 组配对信息，每组配对信息形如整数对 $(l,r)$，表示将 $a_l$ 和 $a_r$ 进行配对。在配对之后，你必须执行下面两种操作之一（不可全选）：
- 令 $a_l$ 加 $1$，随后 $a_r$ 减 $1$。
- 令 $a_r$ 加 $1$，随后 $a_l$ 减 $1$。

你得知这些配对信息遵循着一个奇妙的规定：在 $n$ 组整数对内的 $2n$ 个整数中，每个序列的下标都恰好出现 $2$ 次！

此时你想知道，在所有操作方案中，使 $\sum_{i=1}^n{a_i}^2=k$ 的方案数，由于答案可能会很大，你只需要求出其对 $998\,244\,353$ 取模后的结果。

inputFormat:
第一行包含一个整数 $n\ (1\le n\le 2\cdot 10^5)$，表示序列的长度。

接下来 $n$ 行，其中第 $i$ 行包含两个整数 $l_i,r_i\ (1\le l\le r \le n)$，表示第 $i$ 组配对信息。保证输入的这 $2n$ 个整数符合题目要求。

最后一行包含一个整数 $k\ (0\le k \le 10^9)$，其含义如题目所述。

outputFormat: 输出一个整数，表示使 $\sum_{i=1}^n{a_i}^2=k$ 的方案数对 $998\,244\,353$ 取模后的结果。


title: [HUSTFC 2023] 近似递增序列

description:
对于一个长度为 $m\ (m\ge 1)$ 的整数序列 $a_1,a_2,\cdots,a_m\ (a_i>0)$，如果**最多**只存在一个整数 $p\ (1\le p<m)$ 满足 $a_p\ge a_{p+1}$，则可以称这样的序列为近似递增序列，同时我们定义这个近似递增序列的权值为 $\prod_{i=1}^m a_i$。

设 $f(i)$ 表示权值为 $i$ 的近似递增序列的数量，duoluoluo 想知道 $\sum_{i=1}^n f(i)$ 的值，但是他连 $f(2)$ 都不会计算，你可以帮帮他吗？由于答案可能会非常大，你只需要求出其对 $998\,244\,353$ 取模后的值。

inputFormat: 一行包含一个整数 $n\ (1\le n\le 10^8)$，其含义如题目所述。


title: 「Cfz Round 3」Circle

description:
给定一个长度为 $n$ 的 $\tt{01}$ 串 $S$ 和一个非负整数 $l$。

我们定义，对于一个 $1\sim n$ 的排列 $t$ 和非负整数 $k$：

$$f_{t,k}(i)=\begin{cases}i & k=0\\f_{t,k-1}(t_i) & k \neq 0\end{cases}$$

你需要构造一个 $1\sim n$ 的排列 $p$，满足：

- 对于任意一个不大于 $n$ 的正整数 $i$，都满足 $p_i \neq i$；
- 若 $S_i$ 为 $\tt1$，则 $f_{p,l}(i)=i$（若 $S_i$ 为 $\tt0$ 则没有限制）；

或报告无解。

其中，$1\sim n$ 的排列指满足所有不大于 $n$ 的正整数恰好出现一次的序列。

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

第一行输入一个整数 $T$，表示测试数据组数。

接下来依次输入每组测试数据。对于每组测试数据：

- 第一行输入两个整数 $n,l$。
- 第二行输入一个长度为 $n$ 的 $\tt{01}$ 串表示 $S$。

outputFormat:
对于每组数据，输出一行：

- 若存在满足条件的排列 $p$，则输出用空格分隔的 $n$ 个整数，表示你构造的排列 $p$；
- 若不存在满足条件的排列 $p$，则输出 $-1$。

**所有满足要求的输出均可通过。**

hint:
#### 「样例解释 #1」

对于第 $1$ 组数据，$f_{p,3}(1)=f_{p,2}(4)=f_{p,1}(5)=f_{p,0}(1)=1$，其余数同理，所以 $p$ 为 $\{4,3,2,5,1\}$ 时满足条件。

对于第 $2$ 组数据，可以证明不存在满足条件的排列 $p$。

对于第 $3$ 组数据，$\{2,1,4,5,3\}$ 等也为满足条件的排列 $p$。

#### 「数据范围」

设 $\sum n$ 表示单个测试点中 $n$ 的和。

对于所有数据，$1 \le T \le 100$，$2 \le n \le 5\times 10^5$，$0 \le l \le 10^{18}$，$\sum n \le 5\times 10^5$，保证 $S$ 中只包含 $\tt{0}$ 和 $\tt{1}$。

**只有你通过本题的所有测试点，你才能获得本题的分数。**


title: [COCI2022-2023#3] Estimathon

background: Paula 和 Domagoj 正要组织一场激动人心的名为 Estimathon 的团队比赛。他们已经准备好了问题，现在为此布置房间。

description:
眨眼间，Domagoj 已经在屋里放置了 $n$ 张桌子。现在他们需要增置椅子。他们有五颜六色的椅子。一共有 $m$ 种颜色并且第 $i$ 种颜色的椅子有 $a_i$ 把。参赛每队由**四**人组成。因此对于每张桌子来说，Paula 和 Domagoj 需要增置 $4$ 把椅子。他们想把房间布置地尽可能好。为此，他们约定以下条件：
- 每张桌子的椅子颜色需要相同
- 每种颜色的椅子至少有一张桌子用到了

由于过分关心房间的完美程度，他们突然发现考核其实已然开始了。请你帮他们寻找是否有一种可能的安排方式。

inputFormat:
第一行包含两个整数 $n,m$，分别表示桌子的数量和椅子的颜色数。

第二行包含 $m$ 个整数 $a_i$，第 $i$ 个数表示第 $i$ 种颜色的椅子的数量。

outputFormat:
一行一个字符串。

如果可以找到满足条件的方案，输出 `DA`；

否则输出 `NE`。

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

我们可以有 $5$ 张分别拥有相同颜色椅子的桌子，但是我们没法使得一张桌子有第四种颜色，所以第二个条件没法满足。

**【数据范围】**

|$\text{Subtask}$|分值|特殊性质|
|:-:|:-:|:-:|
|$1$|$11$|$a_1=... =a_m=4$
|$2$|$39$|无特殊限制|

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

**本题满分 $50$ 分。**


title: [CSP-J 2023] 小苹果

description:
小 Y 的桌子上放着 $n$ 个苹果从左到右排成一列，编号为从 $1$ 到 $n$。

小苞是小 Y 的好朋友，每天她都会从中拿走一些苹果。

每天在拿的时候，小苞都是从左侧第 $1$ 个苹果开始、每隔 $2$ 个苹果拿走 $1$ 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。

小苞想知道，多少天能拿完所有的苹果，而编号为 $n$ 的苹果是在第几天被拿走的？

inputFormat: 输入的第一行包含一个正整数 $n$，表示苹果的总数。

outputFormat: 输出一行包含两个正整数，两个整数之间由一个空格隔开，分别表示小苞拿走所有苹果所需的天数以及拿走编号为 $n$ 的苹果是在第几天。

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

小苞的桌上一共放了 $8$ 个苹果。
小苞第一天拿走了编号为 $1$、$4$、$7$ 的苹果。
小苞第二天拿走了编号为 $2$、$6$ 的苹果。
小苞第三天拿走了编号为 $3$ 的苹果。
小苞第四天拿走了编号为 $5$ 的苹果。
小苞第五天拿走了编号为 $8$ 的苹果。

**【样例 $2$】**

见选手目录下的 apple/apple2.in 与 apple/apple2.ans。

**【数据范围】**

对于所有测试数据有：$1\leq n\leq 10^9$。

| 测试点 | $n\leq$ | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1\sim 2$ | $10$ | 无 |
| $3\sim 5$ | $10^3$ | 无 |
| $6\sim 7$ | $10^6$ | 有 |
| $8\sim 9$ | $10^6$ | 无 |
| $10$ | $10^9$ | 无 |

特殊性质：小苞第一天就取走编号为 $n$ 的苹果。


title: [CSP-J 2023] 公路

description:
小苞准备开着车沿着公路自驾。

公路上一共有 $n$ 个站点，编号为从 $1$ 到 $n$。其中站点 $i$ 与站点 $i + 1$ 的距离为 $v_i$ 公里。

公路上每个站点都可以加油，编号为 $i$ 的站点一升油的价格为 $a_i$ 元，且每个站点只出售整数升的油。

小苞想从站点 $1$ 开车到站点 $n$，一开始小苞在站点 $1$ 且车的油箱是空的。已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进 $d$ 公里。问小苞从站点 $1$ 开到站点 $n$，至少要花多少钱加油？

inputFormat:
输入的第一行包含两个正整数 $n$ 和 $d$，分别表示公路上站点的数量和车每升油可以前进的距离。

输入的第二行包含 $n - 1$ 个正整数 $v_1, v_2\dots v_{n-1}$，分别表示站点间的距离。

输入的第三行包含 $n$ 个正整数 $a_1, a_2 \dots a_n$，分别表示在不同站点加油的价格。

outputFormat: 输出一行，仅包含一个正整数，表示从站点 $1$ 开到站点 $n$，小苞至少要花多少钱加油。


title: [CSP-J 2023] 一元二次方程

background:
众所周知，对一元二次方程 $ax ^ 2 + bx + c = 0, (a \neq 0)$，可以用以下方式求实数解：

- 计算 $\Delta = b ^ 2 - 4ac$，则:
	1. 若 $\Delta < 0$，则该一元二次方程无实数解。
  	2. 否则 $\Delta \geq 0$，此时该一元二次方程有两个实数解 $x _ {1, 2} = \frac{-b \pm \sqrt \Delta}{2a}$。

例如：

- $x ^ 2 + x + 1 = 0$ 无实数解，因为 $\Delta = 1 ^ 2 - 4 \times 1 \times 1 = -3 < 0$。
- $x ^ 2 - 2x + 1 = 0$ 有两相等实数解 $x _ {1, 2} = 1$。
- $x ^ 2 - 3x + 2 = 0$ 有两互异实数解 $x _ 1 = 1, x _ 2 = 2$。

在题面描述中 $a$ 和 $b$ 的最大公因数使用 $\gcd(a, b)$ 表示。例如 $12$ 和 $18$ 的最大公因数是 $6$，即 $\gcd(12, 18) = 6$。

description:
现在给定一个一元二次方程的系数 $a, b, c$，其中 $a, b, c$ **均为整数且 $a \neq 0$**。你需要判断一元二次方程 $a x ^ 2 + bx + c = 0$ 是否有实数解，并按要求的格式输出。

**在本题中输出有理数 $v$ 时须遵循以下规则：**

- 由有理数的定义，存在唯一的两个整数 $p$ 和 $q$，满足 $q > 0$，$\gcd(p, q) = 1$ 且 $v = \frac pq$。
- 若 $q = 1$，**则输出 `{p}`，否则输出 `{p}/{q}`**，其中 `{n}` 代表整数 $n$ 的值；
- 例如：

	- 当 $v = -0.5$ 时，$p$ 和 $q$ 的值分别为 $-1$ 和 $2$，则应输出 `-1/2`；
   - 当 $v = 0$ 时，$p$ 和 $q$ 的值分别为 $0$ 和 $1$，则应输出 `0`。

**对于方程的求解，分两种情况讨论：**

1. 若 $\Delta = b ^ 2 - 4ac < 0$，则表明方程无实数解，此时你应当输出 `NO`；
2. 否则 $\Delta \geq 0$，此时方程有两解（可能相等），记其中较大者为 $x$，则：
	1. 若 $x$ 为有理数，则按有理数的格式输出 $x$。
   2. 否则根据上文公式，$x$ 可以被**唯一**表示为 $x = q _ 1 + q _ 2 \sqrt r$ 的形式，其中：

   		- $q _ 1, q _ 2$ 为有理数，且 $q _ 2 > 0$；
      - $r$ 为正整数且 $r > 1$，且不存在正整数 $d > 1$ 使 $d ^ 2 \mid r$（即 $r$ 不应是 $d ^ 2$ 的倍数）；

   此时：

   1. 若 $q _ 1 \neq 0$，则按有理数的格式输出 $q _ 1$，并再输出一个加号 `+`；
   2. 否则跳过这一步输出；

   随后：

   1. 若 $q _ 2 = 1$，则输出 `sqrt({r})`；
   2. 否则若 $q _ 2$ 为整数，则输出 `{q2}*sqrt({r})`；
   3. 否则若 $q _ 3 = \frac 1{q _ 2}$ 为整数，则输出 `sqrt({r})/{q3}`；
   4. 否则可以证明存在唯一整数 $c, d$ 满足 $c, d > 1, \gcd(c, d) = 1$ 且 $q _ 2 = \frac cd$，此时输出 `{c}*sqrt({r})/{d}`；

   上述表示中 `{n}` 代表整数 `{n}` 的值，详见样例。

   如果方程有实数解，则按要求的格式输出两个实数解中的较大者。否则若方程没有实数解，则输出 `NO`。

inputFormat:
输入的第一行包含两个正整数 $T, M$，分别表示方程数和系数的绝对值上限。

接下来 $T$ 行，每行包含三个整数 $a, b, c$。

outputFormat:
输出 $T$ 行，每行包含一个字符串，表示对应询问的答案，格式如题面所述。

**每行输出的字符串中间不应包含任何空格**。


title: [CSP-J 2023] 旅游巴士

description:
小 Z 打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。

旅游景点的地图共有 $n$ 处地点，在这些地点之间连有 $m$ 条道路。其中 $1$ 号地点为景区入口，$n$ 号地点为景区出口。我们把一天当中景区开门营业的时间记为 $0$ 时刻，则从 $0$ 时刻起，每间隔 $k$ 单位时间便有一辆旅游巴士到达景区入口，同时有一辆旅游巴士从景区出口驶离景区。

所有道路均只能**单向通行**。对于每条道路，游客步行通过的用时均为恰好 $1$ 单位时间。

小 Z 希望乘坐旅游巴士到达景区入口，并沿着自己选择的任意路径走到景区出口，再乘坐旅游巴士离开，这意味着他到达和离开景区的时间都必须是 **$k$ 的非负整数倍**。由于节假日客流众多，**小 Z 在旅游巴士离开景区前只想一直沿着景区道路移动，而不想在任何地点（包括景区入口和出口）或者道路上停留**。

出发前，小 Z 忽然得知：景区采取了限制客流的方法，对于每条道路均设置了一个
“开放时间”$a _ i$，游客只有**不早于 $a _ i$ 时刻**才能通过这条道路。

请帮助小 Z 设计一个旅游方案，使得他乘坐旅游巴士离开景区的时间尽量地早。

inputFormat:
输入的第一行包含 3 个正整数 $n, m, k$，表示旅游景点的地点数、道路数，以及旅游巴士的发车间隔。

输入的接下来 $m$ 行，每行包含 3 个非负整数 $u _ i, v _ i, a_ i$，表示第 $i$ 条道路从地点 $u _ i$ 出发，到达地点 $v _ i$，道路的“开放时间”为 $a _ i$。

outputFormat: 输出一行，仅包含一个整数，表示小 Z 最早乘坐旅游巴士离开景区的时刻。如果不存在符合要求的旅游方案，输出 `-1`。


title: [CSP-S 2023] 密码锁

description:
小 Y 有一把五个拨圈的密码锁。如图所示，每个拨圈上是从 $0$ 到 $9$ 的数字。每个拨圈都是从 $0$ 到 $9$ 的循环，即 $9$ 拨动一个位置后可以变成 $0$ 或 $8$，

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

因为校园里比较安全，小 Y 采用的锁车方式是：从正确密码开始，随机转动密码锁仅一次；每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。

当小 Y 选择同时转动两个相邻拨圈时，两个拨圈转动的幅度相同，即小 Y 可以将密码锁从 $\tt{0\;0\;1\;1\;5}$ 转成 $\tt{1\;1\;1\;1\;5}$，但不会转成 $\tt{1\;2\;1\;1\;5}$。

时间久了，小 Y 也担心这么锁车的安全性，所以小 Y 记下了自己锁车后密码锁的 $n$ 个状态，注意这 $n$ 个状态都不是正确密码。

为了检验这么锁车的安全性，小 Y 有多少种可能的正确密码，使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部 $n$ 个状态。

inputFormat:
输入的第一行包含一个正整数 $n$，表示锁车后密码锁的状态数。

接下来 $n$ 行每行包含五个整数，表示一个密码锁的状态。

outputFormat: 输出一行包含一个整数，表示密码锁的这 $n$ 个状态按照给定的锁车方式能对应多少种正确密码。

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

一共有 $81$ 种可能的方案。

其中转动一个拨圈的方案有 $45$ 种，转动两个拨圈的方案有 $36$ 种。

**【样例 2】**

见选手目录下的 lock/lock2.in 与 lock/lock2.ans。

**【数据范围】**

对于所有测试数据有：$1 \leq n \leq 8$。

| 测试点 | $n\leq$ | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1\sim 3$ | $1$ | 无 |
| $4\sim 5$ | $2$ | 无 |
| $6\sim 8$ | $8$ | A |
| $9\sim 10$ | $8$ | 无 |

特殊性质 A：保证所有正确密码都可以通过仅转动一个拨圈得到测试数据给出的 $n$ 个状态。


title: [CSP-S 2023] 消消乐

description:
小 L 现在在玩一个低配版本的消消乐，该版本的游戏是一维的，一次也只能消除两个相邻的元素。

现在，他有一个长度为 $n$ 且仅由小写字母构成的字符串。我们称一个字符串是可消除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。

其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。

小 L 想知道，这个字符串的所有非空连续子串中，有多少个是可消除的。

inputFormat:
输入的第一行包含一个正整数 $n$，表示字符串的长度。

输入的第二行包含一个长度为 $n$ 且仅由小写字母构成的的字符串，表示题目中询问的字符串。

outputFormat: 输出一行包含一个整数，表示题目询问的答案。

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

一共有 $5$ 个可消除的连续子串，分别是 `cc`、`acca`、`cc`、`bccb`、`accabccb`。

**【样例 2】**

见选手目录下的 `game/game2.in` 与 `game/game2.ans`。

**【样例 3】**

见选手目录下的 `game/game3.in` 与 `game/game3.ans`。

**【样例 4】**

见选手目录下的 `game/game4.in` 与 `game/game4.ans`。

**【数据范围】**

对于所有测试数据有：$1 \le n \le 2 \times 10^6$，且询问的字符串仅由小写字母构成。

| 测试点 | $n\leq$ | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1\sim 5$ | $10$ | 无 |
| $6\sim 7$ | $800$ | 无 |
| $8\sim 10$ | $8000$ | 无 |
| $11\sim 12$ | $2\times 10^5$ | A |
| $13\sim 14$ | $2\times 10^5$ | B |
| $15\sim 17$ | $2\times 10^5$ | 无 |
| $18\sim 20$ | $2\times 10^6$ | 无 |

特殊性质 A：字符串中的每个字符独立等概率地从字符集中选择。

特殊性质 B：字符串仅由 `a` 和 `b` 构成。


title: [CSP-S 2023] 结构体

background: 在 C++ 等高级语言中，除了 int 和 float 等基本类型外，通常还可以自定义结构体类型。在本题当中，你需要模拟一种类似 C++ 的高级语言的结构体定义方式，并计算出相应的内存占用等信息。

description:
在这种语言中，基本类型共有 $4$ 种：`byte`、`short`、`int`、`long`，分别占据 $1$、$2$、$4$、$8$ 字节的空间。

定义一个结构体**类型**时，需要给出**类型名**和**成员**，其中每个成员需要按顺序给出**类型**和**名称**。类型可以为基本类型，也可以为**先前定义过**的结构体类型。注意，定义结构体**类型**时不会定义具体元素，即不占用内存。

定义一个**元素**时，需要给出元素的**类型**和**名称**。元素将按照以下规则占据内存：

- 元素内的所有成员将按照**定义时给出的顺序**在内存中排布，对于类型为结构体的成员同理。
- 为了保证内存访问的效率，元素的地址占用需要满足**对齐规则**，即任何类型的**大小**和该类型元素在内存中的**起始地址**均应对齐到该类型对齐要求的**整数倍**。具体而言：
  - 对于基本类型：对齐要求等于其占据空间大小，如 `int` 类型需要对齐到 $4$ 字节，其余同理。
  - 对于结构体类型：对齐要求等于其成员的对齐要求的**最大值**，如一个含有 `int` 和 `short` 的结构体类型需要对齐到 $4$ 字节。

以下是一个例子（以 C++ 语言的格式书写）：

```cpp
struct d {
    short a;
    int b;
    short c;
};
d e;
```

该代码定义了结构体类型 `d` 与元素 `e`。元素 `e` 包含三个成员 `e.a`、`e.b`、`e.c`，分别占据第 $0 \sim 1$、$4 \sim 7$、$8 \sim 9$ 字节的地址。由于类型 `d` 需要对齐到 $4$ 字节，因此 `e` 占据了第 $0 \sim 11$ 字节的地址，大小为 $12$ 字节。

你需要处理 $n$ 次操作，每次操作为以下四种之一：

1. 定义一个结构体类型。具体而言，给定正整数 $k$ 与字符串 $s, t_1, n_1, \dots, t_k, n_k$，其中 $k$ 表示该类型的成员数量，$s$ 表示该类型的类型名，$t_1, t_2, \dots, t_k$ 按顺序分别表示每个成员的类型，$n_1, n_2, \dots, n_k$ 按顺序分别表示每个成员的名称。你需要输出该结构体类型的大小和对齐要求，用一个空格分隔。

2. 定义一个元素，具体而言，给定字符串 $t, n$ 分别表示该元素的类型与名称。所有被定义的元素将按顺序，从内存地址为 $0$ 开始依次排开，并需要满足地址对齐规则。你需要输出新定义的元素的起始地址。

3. 访问某个元素。具体而言，给定字符串 $s$，表示所访问的元素。与 C++ 等语言相同，采用 `.` 来访问结构体类型的成员。如 `a.b.c`，表示 `a` 是一个已定义的元素，它是一个结构体类型，有一个名称为 `b` 的成员，它也是一个结构体类型，有一个名称为 `c` 的成员。你需要输出如上被访问的**最内层**元素的起始地址。

4. 访问某个内存地址。具体而言，给定非负整数 $addr$，表示所访问的地址，你需要判断是否存在一个**基本类型**的元素占据了该地址。若是，则按操作 3 中的访问元素格式输出该元素；否则输出 `ERR`。

inputFormat:
第 $1$ 行：一个正整数 $n$，表示操作的数量。

接下来若干行，依次描述每个操作，每行第一个正整数 $op$ 表示操作类型：

- 若 $op = 1$，首先输入一个字符串 $s$ 与一个正整数 $k$，表示类型名与成员数量，接下来 $k$ 行每行输入两个字符串 $t_i, n_i$，依次表示每个成员的类型与名称。

- 若 $op = 2$，输入两个字符串 $t, n$，表示该元素的类型与名称。

- 若 $op = 3$，输入一个字符串 $s$，表示所访问的元素。

- 若 $op = 4$，输入一个非负整数 $addr$，表示所访问的地址。

outputFormat: 输出 $n$ 行，依次表示每个操作的输出结果，输出要求如题目描述中所述。

samples:
5
1 a 2
short aa
int ab
1 b 2
a ba
long bb
2 b x
3 x.ba.ab
4 10

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

结构体类型 `a` 中，`short` 类型的成员 `aa` 占据第 $0 \sim 1$ 字节地址，`int` 类型的成员 `ab` 占据第 $4 \sim 7$ 字节地址。又由于其对齐要求为 $4$ 字节，可得其大小为 $8$ 字节。由此可同理计算出结构体类型 `b` 的大小为 $16$ 字节，对齐要求为 $8$ 字节。

#### 【样例 2】

见选手目录下的 struct/struct2.in 与 struct/struct2.ans。

#### 【样例 2 解释】
第二个操作 4 中，访问的内存地址恰好在为了地址对齐而留下的 “洞” 里，因此没有基本类型元素占据它。

#### 【样例 3】
见选手目录下的 struct/struct3.in 与 struct/struct3.ans。

#### 【数据范围】
对于全部数据，满足 $1 \le n \le 100$，$1 \le k \le 100$，$0 \le addr \le 10^{18}$。

所有定义的结构体类型名、成员名称和定义的元素名称均由不超过 $10$ 个字符的小写字母组成，且都不是 `byte,short,int,long`（即不与基本类型重名）。

所有定义的结构体类型名和元素名称互不相同，同一结构体内成员名称互不相同。但不同的结构体可能有相同的成员名称，某结构体内的成员名称也可能与定义的结构体或元素名称相同。

保证所有操作均符合题目所述的规范和要求，即结构体的定义不会包含不存在的类型、不会访问不存在的元素或成员等。

保证任意结构体大小及定义的元素占据的最高内存地址均不超过 $10^{18}$。

| 测试点 | 特殊性质 |
| :----------: | :----------: |
| $1$ | A、D |
| $2\sim 3$ | A |
| $4\sim 5$ | B、D |
| $6\sim 8$  | B |
| $9\sim 10$ | C、D|
| $11\sim 13$ | C|
| $14\sim 16$ |D|
|$17\sim 20$| 无|

特殊性质 A：没有操作 $1$；

特殊性质 B：只有一个操作 $1$；

特殊性质 C：所有操作 $1$ 中给出的成员类型均为基本类型；

特殊性质 D：基本类型只有 `long`。

#### 【提示】

对于结构体类型的对齐要求和大小，形式化的定义方式如下：

- 设该结构体内有 $k$ 个成员，其大小分别为 $s_1,...,s_k$，对齐要求分别为 $a_1,...,a_k$;
- 则该结构体的对齐要求为 $a=\max\{a_1,...,a_k\}$；
- 再设这些成员排布时的**地址偏移量**分别为 $o_1,...,o_k$，则：
  - $o_1 = 0$;
  - 对于 $i=2,...,k$，$o_i$ 为满足 $o_{i-1}+s_{i-1}\le o_i$ 且 $a_i$ 整除 $o_i$ 的最小值；
  - 则该结构体的大小 $s$ 为满足 $o_k+s_k\le s$ 且 $a$ 整除 $s$ 的最小值；

对于定义元素时的内存排布，形式化的定义方式如下：

- 设第 $i$ 个被定义的元素大小为 $s_i$，对齐要求为 $a_i$，起始地址为 $b_i$;
- 则 $b_1 = 0$，对于 $2\le i$， $b_i$ 为满足 $b_{i-1} + s_{i-1}\le b_i$ 且 $a_i$ 整除 $b_i$ 的最小值。


title: [CSP-S 2023] 种树

description:
你是一个森林养护员，有一天，你接到了一个任务：在一片森林内的地块上种树，并养护至树木长到指定的高度。

森林的地图有 $n$ 片地块，其中 $1$ 号地块连接森林的入口。共有 $n-1$ 条道路连接这些地块，使得每片地块都能通过道路互相到达。最开始，每片地块上都没有树木。

你的目标是：在每片地块上均种植一棵树木，并使得 $i$ 号地块上的树的高度生长到不低于 $a_i$ 米。

你每天可以选择一个未种树且**与某个已种树的地块直接邻接**（**即通过单条道路相连**）的地块，种一棵高度为 $0$ 米的树。如果所有地块均已种过树，则你当天不进行任何操作。特别地，第 $1$ 天你只能在 $1$ 号空地种树。

对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在第 $x$ 天，$i$ 号地块上的树会长高 $\max(b_i + x \times c_i, 1)$ 米。注意这里的 $x$ 是从整个任务的第一天，而非种下这棵树的第一天开始计算。

你想知道：最少需要多少天能够完成你的任务？

inputFormat:
输入的第一行包含一个正整数 $n$，表示森林的地块数量。

接下来 $n$ 行：每行包含三个整数 $a_i, b_i, c_i$，分别描述一片地块，含义如题目描述中所述。

接下来 $n-1$ 行：每行包含两个正整数 $u_i, v_i$，表示一条连接地块 $u_i$ 和 $v_i$ 的道路。

outputFormat: 输出一行仅包含一个正整数，表示完成任务所需的最少天数。

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

第 $1$ 天：在地块 $1$ 种树，地块 $1$ 的树木长高至 $2$ 米。

第 $2$ 天：在地块 $3$ 种树，地块 $1, 3$ 的树木分别长高至 $5, 3$ 米。

第 $3$ 天：在地块 $4$ 种树，地块 $1, 3, 4$ 的树木分别长高至 $9, 6, 4$ 米。

第 $4$ 天：在地块 $2$ 种树，地块 $1, 2, 3, 4$ 的树木分别长高至 $14, 1, 9, 6$ 米。

第 $5$ 天：地块 $1, 2, 3, 4$ 的树木分别长高至 $20, 2, 12, 7$ 米。

**【样例 2】**

见选手目录下的 `tree/tree2.in` 与 `tree/tree2.ans`。

**【样例 3】**

见选手目录下的 `tree/tree3.in` 与 `tree/tree3.ans`。

**【样例 4】**

见选手目录下的 `tree/tree4.in` 与 `tree/tree4.ans`。

**【数据范围】**

对于所有测试数据有：$1 ≤ n ≤ 10^5,1 ≤ a_i ≤ 10^{18}, 1 ≤ b_i ≤ 10^9,0 ≤ |c_i| ≤ 10^9, 1 ≤ u_i, v_i ≤ n$。保证存在方案能在 $10^9$ 天内完成任务。

![T4](https://cdn.luogu.com.cn/upload/image_hosting/aqqd4l0y.png?x-oss-process=image/resize,m_lfit,h_400,w_300)

特殊性质 A：对于所有 $1 ≤ i ≤ n$，均有 $c_i = 0$；

特殊性质 B：对于所有 $1 ≤ i < n$，均有 $u_i = i$、$v_i = i + 1$；

特殊性质 C：与任何地块直接相连的道路均不超过 $2$ 条；

特殊性质 D：对于所有 $1 ≤ i < n$，均有 $u_i = 1$。


title: [COCI2022-2023#3] Dirigent

description:
信息学冬令营以一场传统舞蹈结营。一共有 $n$ 名学生参与。他们每个人都有分别有一个 $1\sim n$ 之间的编号。

一开始，指挥者 Kreso 要求学生们围成一个圈，使得每个学生都与另外两个学生拉着手。

Alenka 想知道是否有可能通过将且仅将一对相邻同学分开手，使得这样形成的同学序列按照编号排序。例如，如果他们的顺序是 `3 4 1 2`，那么圈可以从 `4` `1` 两个同学间断开；但是如果顺序是 `2 1 4 3`，那么没有一种合理的方式。

在这一晚，Kreso 准备下达 $q$ 条指令。在每条指令中，他会要求两个学生交换位置。在每一次交换之后你需要帮助 Alenka 回答他的问题。

inputFormat:
第一行包含两个整数 $n,q$，表示学生的数量和交换数。

第二行包含 $n$ 个整数 $a_i$，描述第 $i$ 个位置的学生编号。

在接下来的 $q$ 行中，每行两个整数 $x_i,y_i$，描述 Kreso 的第 $i$ 条指令，即标号 $x_i$ 的学生和标号 $y_i$ 的学生交换位置。

outputFormat:
共 $q$ 行。

在第 $i$ 行输出在第 $i$ 次交换后 Alenka 的问题的答案。

如果答案是肯定的，输出 `DA`，否则输出 `NE`。


title: [COCI2022-2023#3] Baltazar

description:
Baltazar 准备去度假。他现在在 Baltazargrad，正想去 Primosten 旅游。为了抵达那里，他需要穿过许多个城市。一共有 $n$ 个城市，被 $m$ 条双向道路所联接。Baltazargrad 编号为 $1$，Primosten 编号为 $n$。

Baltazar 不确定从 Baltazargrad 去 Primosten 的路线，所以他将会使用 GPS，这会指引他以最短路线抵达。

但 Blatazar 真的很爱旅游，而且他可以将魔法药水使用在任何一条路上（即使他没有经过），从而将路的长度增长 $2$ 千米。但他仅能使用一次药水。

不久他意识到，他必须在中午之前在 Primosten 的 Zora 旅馆入住。所以他不能过分增加最短路的总长度。他现在想知道，一共有多少条路可以让他使用药水，使得最短路的长度恰好增加 $1$ 千米。

inputFormat:
多组数据。

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

接下来对于每组数据，第一行两个整数 $n,m$，分别表示城市的数量和城市之间道路的数量。

接下来的 $m$ 行，每行三个整数 $a_i,b_i,w_i$，表示一条连接城市 $a_i,b_i$ 且长度为 $w_i$ 的道路。两个城市间最多只有一条道路。

保证所有城市是相互联通的。也就是说，任何一对城市，都有一条相互可达的路径，但不一定是直接相连。

保证所有数据的 $n, m$ 各自之和均不超过 $300000$。

outputFormat:
第一行输出一个整数 $c$，表示 Baltazar 可以使用魔法药水的道路数量。

接下来一行 $c$ 个整数，以编号升序输出所有满足条件的道路。

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

城市和道路如图所示。如果 Baltazar 把他的魔法药水使用在第二条道路上（连接城市 $3$ 和 $5$ 的），那么城市 $1$ 和 $n$ 之间最短的距离将会增加 $1$。

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

**【数据范围】**

| 子任务 | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1$ | $15$ | $n,m \leq 1000$ |
| $2$ | $30$ | 有一条在起点终点之间的道路，这条道路的长度满足恰好比两个城市之间的最短路线长 $1$ 千米。 |
| $3$ | $65$ | 无特殊性质 |

对于 $100\%$ 的数据，满足 $1\le t \le 10000,2\leq n \leq 3\times10^5,1\le m\le \min(3\times 10^5,\dfrac{n\times (n-1)}{2}), 1\le a_i,b_i\le n,a_i\neq b_i,1\le w_i\le 10^9$。

本题满分 $110$ 分。


title: [COCI2022-2023#3] Bomboni

description:
Iva 是一个狂热的糖果迷！在她面前是一块填满糖果和障碍的 $n\times n$ 的土地。Iva 目前在左上角。通过向右或向下移动，她要前往右下角。Iva 目前所在的格子没有障碍。

在每个格子中写了一个数字表示此地为糖果或障碍。Iva 会吃掉所有经过的糖果（包括起点和终点的糖果）并且将糖果对应的数字相乘。Iva 知道她自己最喜欢的数字是 $k$，所以她希望这个乘积结果能被 $k$ 整除。她想知道一共有多少条这样的路径。由于答案可能很大，她只想知道答案模 $998244353$ 的结果。

inputFormat:
第一行两个整数 $n,k$，表示土地的边长和 Iva 的最喜欢的数字。

在接下来的 $n$ 行中，每一行 $n$ 个数字，描述这片土地。如果 $a_{i,j}=-1$，那么这块土地就是障碍物，否则满足这块土地包含一个 $1\le a_{i,j}\le 10^6$ 的数。

outputFormat: 一行一个整数表示结果。


title: [COCI2022-2023#3] Skrivača

description:
Marin 和 Luka 正在他们的房子里玩一个流行的儿童游戏——捉迷藏。这个房子共有 $n$ 个房间，有 $m$ 对房间通过一扇门连接。房间从 $1$ 到 $n$ 编号，并且任意两个房间之间是存在道路相连通的。

Luka 想出了一个躲藏策略：当 Marin 进入房间 $v$ 时，Luka 会躲在房间 $a_v$ 里。在游戏的开始 Marin 选择他开始找人的房间 $v_0$，Luka 躲在房间 $a_{v_0}$里。在游戏的每一个回合，首先由 Marin 选择一个与当前相邻房间 $u$ 并进入。随后 Luka 知道 Marin 在房间 $u$ 中所以参照他的躲藏方式他会躲到房间 $a_u$ 中。注意到 Luka 可以选择任何抵达房间 $a_u$ 的路线并且在游戏的一个回合中他可以经过任意数量的房间。

定义 Marin 找到了 Luka 为当他们两个都在同一个房间中的时候，这时游戏结束。

Marin 发现了 Luka 的躲藏策略，所以她想要你考虑从每一个房间出发时，她是否可以在有限回合找到 Luka。如果可以，计算在理想状态下（Marin 尽可能减少回合数，Luka 尽可能增加回合数）最少需要的回合数。

inputFormat:
第一行两个整数 $n,m$，分别表示房间的数量和相连房间的对数。

第二行 $n$ 个整数 $a_i$，表示 Luka 的躲藏策略。

在接下来的 $m$ 行中，每行两个整数 $x_i,y_i$，表示这两个房间是相连的。任意两个房间最多只有一条直接相连的道路。

outputFormat: 一行 $n$ 个数，表示最少需要的回合数。如果无法在有限步中结束游戏，输出 $-1$。

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

Marin 第一回合从房间 $4$ 进入房间 $8$，第二回合回到房间 $4$。Luka 需要经过房间 $4$ 才能从房间 $7$ 到房间 $1$。所以可以在两个回合找到。

**【数据范围】**

| 子任务 | 分值 | 特殊性质 |
| :----------: | :----------: | :----------: |
| $1$ | $15$ | $n\le 1000,m\le2000$ |
| $2$ | $25$ | $m=n-1$ |
|$3$ | $30$| Luka 的躲藏策略满足他永远不会躲在与 Marin 当前所在房间相邻或相同的房间，并且房子的结构满足游戏可以在最多有 $5$ 个不同房间独立于 Luka 的躲藏策略之外的情况下结束游戏。
| $4$ | $40$ | 无特殊性质 |

对于 $100\%$ 的数据，满足 $1\leq n \leq 2\times10^5,n-1\le m\le \min(5\times 10^5,\dfrac{n\times (n-1)}{2}), 1\le a_i,x_i,y_i\le n,x_i\neq y_i$。

本题满分 $110$ 分。


title: [集训队互测 2023] 矩阵快速幂

background: 请注意：**本题不是矩阵快速幂模板题**。

description:
给定一张 $n$ 个点 $m$ 条边的边带权有向图，可能有重边和自环。求从 $1$ 出发到每个点恰好走 $k$ 条边的路径权值的最小值 **对 $998244353$ 取模后的结果**。若路径不存在则输出 $-1$。多组数据。

路径权值的定义是路径上所有边的权值之和。

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

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

对于每组数据：

- 第一行三个整数 $n, m, k$。
- 接下来 $m$ 行，每行三个整数 $u, v, w$ 表示一条有向边。

outputFormat: 对于每组数据，输出一行 $n$ 个由空格隔开的整数表示答案。

samples:
见下发文件 ex_matrix1.in
见下发文件 ex_matrix1.ans

samples:
见下发文件 ex_matrix2.in
见下发文件 ex_matrix2.ans

hint:
- Subtask #1（$10$ 分）：$\sum n ^ 3\leq 10 ^ 6$，$k\leq 10 ^ {18}$。
- Subtask #2（$15$ 分）：$m = 2n - 2$，且对任意 $1\leq i < n$，存在权值相等的 $(i, i + 1)$ 和 $(i + 1, i)$。
- Subtask #3（$20$ 分）：$m\geq 2n - 2$，且对任意 $(u, v)$，存在权值相等的 $(v, u)$，注意 $u$ 可以等于 $v$。依赖于 Subtask #2。
- Subtask #4（$15$ 分）：$\sum n ^ 3\leq 10 ^ 6$，依赖于 Subtask #1。
- Subtask #5（$15$ 分）：$k\leq 10 ^ {18}$，依赖于 Subtask #1。
- Subtask #6（$25$ 分）：无特殊性质。依赖于 Subtask #3，#4，#5。

对于所有数据，$1\leq S\leq 6$，$1\leq T\leq 10 ^ 4$，$2\leq n\leq 300$，$1\leq m\leq 2n$，$1\leq k\leq 10 ^ {64}$，$1\leq u, v\leq n$，$1\leq w\leq 10 ^ {18}$。保证 $\sum n \leq 2\times 10 ^ 5$ 且 $\sum n ^ 3 \leq 2.7 \times 10 ^ 7$。

题解在附件 `paper.pdf` 中。


title: [ICPC2020 Shanghai R] Wowoear

description:
Wowo is a solo adventurer who completed many dangerous journeys on his own foot in forests, deserts and even glaciers. The Shanghai ICPC (Shanghai Invitational Contest on Programmable Cheating) committee invited Wowo as a tester of their new running trial.

The trial can be described as a 2D simple polyline $(p_1,\ldots, p_n)$. In other words, the trial consists of $n-1$ line segments $(p_1, p_2),\ldots, (p_{n-1}, p_n)$. The line segments do not intersect with each other except that two consecutive line segments $(p_i, p_{i+1})$ and $(p_{i+1}, p_{i+2})$ intersect at the point $p_{i+1}$. Any two consecutive segments have different directions. The committee wants Wowo to run from $p_1$ to $p_n$ along the line segments $(p_1,p_2),\ldots, (p_{n-1}, p_n)$ in order.

However, Wowo has a smart device that can hack the committee's system for an interval of time. Wowo is able to choose $2$ points $a, b$ on the trial and run directly from $a$ to $b$ along the line segment $(a, b)$. Each of these $a$ and $b$ can be some $p_i$ ($1\le i\le n$) and can be some point on some line segment $(p_i, p_{i+1})$ ($1\le i<n$) as well. Before reaching $a$ and after reaching $b$, Wowo has to run along the original trial. Wowo does not want to be caught cheating, so he decided that the line segment $(a, b)$ should not intersect or touch any line segment of the trial at any point other than $a$ and $b$. Help Wowo to choose $a$ and $b$ wisely and output the shortest distance Wowo need to run from $p_1$ to $p_n$ using his smart cheating device.

inputFormat:
The first line includes a single integer $n$ indicating the number of points on the running trial ($2\le n\le 200$).

The $i+1$-th line ($1\le i\le n$) contains two integers $x$ and $y$ separated by a single space indicating the coordinates of $p_i$ ($-1000\le x, y\le 1000$).

It is guaranteed that the line segments do not intersect with each other except that two consecutive line segments $(p_i, p_{i+1})$ and $(p_{i+1}, p_{i+2})$ intersect at the point $p_{i+1}$. In other words, $(p_i, p_{i+1})\cap (p_{j}, p_{j+1})=\left\{\begin{array}{cc}\emptyset & i\neq j-1\\ \{p_{j}\} & i = j-1\end{array}\right.$ holds for any integers $i, j$ satisfying $1\le i< j<n$. Here $(s, t)$ represents all points on the line segment from $s$ to $t$ including $s$ and $t$.

It is guaranteed that each line segment has nonzero length. In other words, $p_i\neq p_{i+1}$ for any integer $i\in [1, n)$.

It is guaranteed that adjacent line segments are not collinear. In other words, for any integer $i\in [1,n-2]$ and any real number $\lambda$, $p_i - p_{i+1}$ is $\textbf{not}$ equal to $\lambda(p_{i+1}-p_{i+2})$.

outputFormat: Output the shortest distance Wowo needs to run. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

translation:
### 题目描述
Wowo 是一位单人冒险家，他曾独自一人在森林、沙漠甚至冰川中完成过许多危险的旅程。ICPC（上海市可编程作弊邀请赛）组委会邀请 Wowo 作为新的跑步测试员。

该试验可描述为二维简单折线 $(p_1,\ldots, p_n)$。换句话说，试验由 $n-1$ 条线段 $(p_1, p_2),\ldots, (p_{n-1}, p_n)$ 组成。除了两个连续的线段 $(p_i, p_{i+1})$ 和 $(p_{i+1}, p_{i+2})$ 相交于点 $p_{i+1}$ 外，其他线段互不相交。任何两条连续的线段都有不同的方向。委员会希望 Wowo 从 $p_1$ 到 $p_n$ 依次沿着线段 $(p_1,p_2),\ldots, (p_{n-1}, p_n)$ 运行。

然而，Wowo 拥有一个智能设备，可以在一段时间内侵入委员会的系统。Wowo 能够在试验中选择 $2$ 点 $a, b$ ，并沿着线段 $(a, b)$ 直接从 $a$ 跑到 $b$ 。其中每个 $a$ 和 $b$ 都可以是某个 $p_i$ （$1\le i\le n$）。($1\le i\le n$) ，也可以是线段 $(p_i, p_{i+1})$ 上的某一点。($1\le i \le n$)上的某一点。在到达 $a$ 之前和 $b$ 之后，Wowo 必须沿着原来的试验路线运行。沃沃不想被发现作弊，所以他决定线段 $(a, b)$ 不能与试验中的任何线段相交，也不能接触到 $a$ 和 $b$ 以外的任何点。请帮助 Wowo 明智地选择 $a$ 和 $b$ ，并利用他的智能作弊装置输出 Wowo 需要从 $p_1$ 跑到 $p_n$ 的最短距离
### 输入格式

第一行包含一个整数 $n$ ，表示运行试验中的点数（ $2\le n\le 200$ ）。

第 $i+1$（$1\le i\le n$）行包含两个整数 $x$ 和 $y$，中间用一个空格隔开，表示 $p_i$（$-1000\le x, y\le 1000$）的坐标。

除了两条连续的线段 $(p_i, p_{i+1})$ 和 $(p_{i+1}, p_{i+2})$ 相交于点 $p_{i+1}$ 之外，其他线段保证互不相交。换句话说，对于满足 $1 \le i\lt j \lt n$ 的任何整数 $i, j$，$(p_i, p_{i+1})\cap (p_{j}, p_{j+1})=\left\{\begin{array}{cc}\emptyset & i\neq j-1\\ \{p_{j}\} & i = j-1\end{array}\right.$ 都成立。这里的 $(s, t)$ 代表从 $s$ 到 $t$ 的线段上的所有点，包括 $s$ 和 $t$。
可以保证每条线段的长度都不为零。换句话说，$p_i\neq p_{i+1}$ 满足任意整数 $i\in [1, n)$。

保证相邻线段不相交。换句话说，对于任意整数 $i\in [1,n-2]$ 和任意实数 $\lambda$，$p_i - p_{i+1}$ 不**等于**$\lambda(p_{i+1}-p_{i+2})$。
### 输出格式
输出 Wowo 需要运行的最短距离。如果答案的绝对误差或相对误差不超过 $10^{-6}$，则认为答案正确。
Translation by [nightwatch_ryan](/user/961351)


title: [ICPC2020 Shanghai R] Mine Sweeper II

description:
A mine-sweeper map $X$ can be expressed as an $n\times m$ grid. Each cell of the grid is either a mine cell or a non-mine cell. A mine cell has no number on it. Each non-mine cell has a number representing the number of mine cells around it. (A cell is around another cell if they share at least one common point. Thus, every cell that is not on the boundary has $8$ cells around it.) The following is a $16\times 30$ mine-sweeper map where a flagged cell denotes a mine cell and a blank cell denotes a non-mine cell with number 0.

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

Given two mine-sweeper maps $A, B$ of size $n\times m$, you should modify at most $\left\lfloor\frac{nm}{2}\right\rfloor$ (i.e. the largest nonnegative integer that is less than or equal to $\frac{nm}{2}$) cells in $B$ (from a non-mine cell to a mine cell or vice versa) such that the sum of numbers in the non-mine cells in $A$ and the sum of numbers in the non-mine cells in $B$ are the same. (If a map has no non-mine cell, the sum is considered as $0$.)

If multiple solutions exist, print any of them. If no solution exists, print ``-1`` in one line.

inputFormat:
The first line contains two integers $n, m\,(1\le n,m \le 1000)$, denoting the size of given mine-sweeper maps.

The $i$-th line of the following $n$ lines contains a length-$m$ string consisting of  ``.`` and ``X`` denoting the $i$-th row of the mine-sweeper map $A$. A ``.`` denotes for a non-mine cell and an ``X`` denotes for a mine cell.

The $i$-th line of the following $n$ lines contains a length-$m$ string consisting of  ``.`` and ``X`` denoting the $i$-th row of the mine-sweeper map $B$. A ``.`` denotes for a non-mine cell and an ``X`` denotes for a mine cell.

outputFormat:
If no solution exists, print ``-1`` in one line.

Otherwise, print $n$ lines denoting the modified mine-sweeper map $B$. The $i$-th line should contain a length-$m$ string consisting of  ``.`` and ``X`` denoting the $i$-th row of the modified map $B$. A ``.`` denotes for a non-mine cell and an ``X`` denotes for a mine cell.

Please notice that you need not print the numbers on non-mine cells since these numbers can be determined by the output mine-sweeper map.

translation:
一张扫雷地图 $X$ 可以被视为一个 $n \times m$ 的网格，每个格子要么是地雷格，要么不是地雷格。地雷格上没有数字，而每个非地雷格上都有一个数字，代表周围相邻 $8$ 个格子中地雷格的数目。下图是一个 $16\times 30$ 的扫雷地图，地雷格由小红旗表示，一个空白的格子代表一个数字为 $0$ 的非地雷格。

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

给出两张尺寸均为 $n\times m$ 的扫雷地图 $A,B$。每次修改可以将一个地雷格改为非地雷格，或者将一个非地雷格改为地雷格。你可以修改最多 $\lfloor \dfrac{nm}{2} \rfloor$ 个地图 $B$ 中的格子，请给出一种方案，使得 $A,B$ 中非地雷格上数字之和相同。若无解，输出 $-1$。

hint: We modify one cell in $B$. Then the sums of the numbers on non-mine cells in $A$ and $B$ both equal $10$.


title: [ICPC2020 Shanghai R] Sum of Log

description:
Given two non-negative integers $X$ and $Y$, determine the value of
$$ \sum_{i=0}^{X}\sum_{j=[i=0]}^{Y}[i\&j=0]\lfloor\log_2(i+j)+1\rfloor $$
modulo $10^9+7$ where
- $\&$ denotes bitwise AND;
- $[A]$ equals 1 if $A$ is true, otherwise $0$;
- $\lfloor x\rfloor$ equals the maximum integer whose value is no more than $x$.

inputFormat:
The first line contains one integer $T\,(1\le T \le 10^5)$ denoting the number of test cases.

Each of the following $T$ lines contains two integers $X, Y\,(0\le X,Y \le 10^9)$ indicating a test case.

outputFormat: For each test case, print one line containing one integer, the answer to the test case.

translation:
给定两个非负整数 $X,Y$，计算下列式子对 $10^9+7$ 取模的值：
$$
\sum\limits_{i=0}^{X}{\sum\limits_{j=[i=0]}^{Y}{[i \& j=0]\lfloor \log_2(i+j)+1\rfloor}}
$$
其中：

- $\&$ 表示按位与。
- $[A]$ 等于 $1$，当且仅当表达式 $A$ 为真；否则 $[A]$ 等于 $0$。
- $\lfloor x \rfloor$ 表示不大于 $x$ 的最大整数。

hint:
For the first test case:
- Two $(i,j)$ pairs increase the sum by 1: $(0, 1), (1, 0)$
- Six $(i,j)$ pairs increase the sum by 2: $(0, 2), (0, 3), (1, 2), (2, 0), (2, 1), (3, 0)$

So the answer is $1\times 2 + 2\times 6 = 14$.


title: [ICPC2020 Shanghai R] Walker

description:
As a world-famous traveler, Prof. Pang's research interest is to travel as many places as possible in his life.

We have a segment $[0, n]$. There are two travelers on it. The first one is on position $p_1$ with velocity $v_1$ (which means s/he can walk $v_1$ unit on the segment per second). The second one is on position $p_2$ with velocity $v_2$.

From their respective beginning points, travelers can walk on the segment. They cannot walk outside the segment. Whenever they want to change their direction, they can turn around immediately.

Please help Prof. Pang to calculate the minimum  possible time by which every position of the segment is passed by at least one traveler.

inputFormat:
The first line contains one integer $test~(1\le test\le 10000)$ -- the number of test cases.

The $i$-th of the next $test$ lines contains five numbers $n, p_{1, i}, v_{1, i}, p_{2, i}, v_{2, i}$ ($0 < n \le 10000$, $0\le p_{1, i},p_{2, i} \le n$, $0.001 \le v_{1, i},v_{2, i} \le 1000$). All numbers have at most $3$ digits after the decimal point.

outputFormat:
For each test case, we should output one number -- the minimum time that every position of the segment is passed by at least one traveler.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.

translation:
作为著名的旅行者，Prof. Pang 的研究兴趣是在一生中到尽可能多的地方旅游。

在一条 $[0,n]$ 的线段上有两名旅行者，第一名在位置 $p_1$ 以 $v_1$ （每秒钟可以走 $v_1$ 单位的距离）的速度开始运动，第二名在位置 $p_2$ 以 $v_2$ 的速度开始运动。

从他们分别的起始点出发，旅行者可以在线段上移动，但不可以走出线段。他们可以随时改变自己的方向。

请帮助 Prof. Pang 计算至少需要多少时间，线段上的每个位置都至少被一名旅行者经过。


title: [ICPC2020 Shanghai R] The Journey of Geor Autumn

description:
Once upon a time, there was a witch named Geor Autumn, who set off on a journey across the world. Along the way, she would meet all kinds of people, from a country full of ICPC competitors to a horse in love with dota---but with each meeting, Geor would become a small part of their story, and her own world would get a little bit bigger.

Geor just arrived at the state of Shu where people love poems. A poem is a permutation $(a_1,\ldots, a_n)$ of $[n]$. ($(a_1,\ldots, a_n)$ is a permutation of $[n]$ means that each $a_i$ is an integer in $[1,n]$ and that $a_1,\ldots, a_n$ are distinct.) One poem is $\textit{good}$ if for all integer $i$ satisfying $i> k$ and $i\le n$, $a_i>\min(a_{i-k}, \ldots, a_{i-1})$. Here $\min(a_{i-k}, \ldots, a_{i-1})$ denotes the minimum value among $a_{i-k}, \ldots, a_{i-1}$.

Help Geor calculate how many good poems there are, given $n$ and $k$. To avoid huge numbers, output the answer modulo $998244353$.

inputFormat: The first line contains two integers $n$ and $k$ separated by a single space ($1\le n\le 10^7$, $1\le k\le 10^7$).

outputFormat: Output only one integer in one line---the number of good poems modulo $998244353$.

translation:
### 题意简述
给定 $1 \le k \le n$，我们规定满足以下性质的 $1 \sim n$ 的排列称之为“好排列”：

$\forall k<i \le n,~a_i > \min{a_{i-k},a_{i-k+1},...,a_{i-1}}$

求好排列的个数。对 $998244353$ 取模。
### 输入格式
一行，两个整数 $n,k$。
### 输出格式
一行，为好排列的个数对 $998244353$ 取模的值。


title: 少项式复合幂

background:
> I have won everything except your heart.

终于，小 Z 可以玩一年原神了。但在此之前，他决定做出这道题，以纪念自己对【数据删除】的感情。

description:
给定多项式 $f(x)=\sum_{i=1}^ma_ix^{b_i}$。定义 $f_1(x)=f(x)$，$f_n(x)=f(f_{n-1}(x))$。

给定模数 $p$。有 $q$ 次询问，每次给出 $x,y$，查询 $f_y(x)\bmod p$ 的值。

**请注意 $m,p$ 的特殊数据范围。**

inputFormat:
输入的第一行包含三个正整数 $m,q,p$，分别为 $f$ 的项数，询问次数和给定模数。

随后 $m$ 行，每行读入两个非负整数 $a_i,b_i$，用于描述多项式 $f$。

随后 $q$ 行，每行两个正整数 $x,y$，表示一次询问。

outputFormat: 输出共 $q$ 行，每行包含对应询问的答案。


title: [ICPC2020 Shanghai R] Fountains

description:
Suppose you and your teammate Mixsx will attend the Namomo Camp. The Namomo Camp will happen in $n$ consecutive days. We name the $i$-th day as day $i$ ($1\le i\le n$). The cost of day $i$ is $s_i$.

Unfortunately, the schedule of the Namomo Camp conflicts with Mixsx's final exams. Mixsx has final exams every day between day $L$ and day $R$. The exact value of $L$ and $R$ have not been announced by his college so we assume that every pair of integers $L$ and $R$ satisfying $1\le L\le R\le n$ will be chosen with probability $1/(n(n+1)/2)$. He decides to take all the exams and thus be absent from the Namomo Camp from day $L$ to day $R$. His $\textit{loss}$ will be $\sum_{i=L}^R s_i$ in this case.

As Mixsx's teammate, you want Mixsx to give up his final exams and come back to the Namomo Camp. You can prepare $k$ plans before $L$ and $R$ are announced. In the $i$-th plan ($1\le i\le k$), you shut the electricity off to his college every day from day $l_i$ to day $r_i$. You can choose the values of $l_i$ and $r_i$ as long as they are two integers satisfying $1\le l_i\le r_i\le n$.

Once $L$ and $R$ are announced, you can choose a plan $x$ ($1\le x\le k$) such that $L\le l_x\le r_x\le R$. Then Mixsx will come back to the Namomo Camp on every day from day $l_x$ to day $r_x$. His loss becomes $\sum_{i=L}^R s_i-\sum_{i=l_x}^{r_x} s_i$ in this case. You will choose a plan that minimizes Mixsx's loss. If no plan $x$ satisfies $L\le l_x\le r_x\le R$, Mixsx will attend his final exams normally and his loss is $\sum_{i=L}^R s_i$.

Please calculate the minimum possible expected loss $ans_k$ of Mixsx if you choose the $k$ plans optimally. Output $ans_k\cdot n(n+1)/2$ for every $k$ from $1$ to $n(n+1)/2$.

Formally, given a list of $n$ numbers $s_i$ $(1 \leq i \leq n)$, define a loss function $C(L, R) = \sum_{i=L}^R s_i$. Given an integer $k$ ($1 \leq k \leq n (n + 1) / 2$), you should select $2k$ integers $l_1, \ldots, l_k, r_1,\ldots, r_k$ satisfying $1\le l_i\le r_i\le n$ for all $1 \leq i \leq k$, such that

$$\sum_{1\leq L\leq  R\leq n} \left[C(L, R) - \max_{1\le i\le k, L \leq l_i \leq r_i \leq R} C(l_i, r_i) \right]$$

 is minimized. ($\max_{1\le i\le k, L \leq l_i \leq r_i \leq R} C(l_i, r_i)$ is defined as $0$ if no $i$ satisfies $1\le i\le k$ and $L \leq l_i \leq r_i \leq R$.) Output the minimized value for every integer $k$ in $[1, n(n + 1) / 2]$.

inputFormat: The first line contains an integer $n~(1 \leq n \leq 9)$. The second line contains $n$ space separated integers $s_i~(1 \leq s_i \leq 10^9)$.

outputFormat: The output contains $n (n + 1) / 2$ integers in their own lines, the expectations when $k = 1, \ldots, n (n + 1) / 2$ multiplied by $n (n + 1) / 2$. It can be shown that the results are always integers.

translation:
给出一个长度为 $n$ 的序列 $s$，定义 $C(l,r)=\sum\limits_{i=l}^r s_i$。

对于每个 $1 \le k \le n(n+1)/2$，找出 $k$ 个二元组 $(l_1,r_1),\dots,(l_k,r_k)$，满足 $1 \le l_i \le r_i \le n$，最小化：

$$\sum_{1\leq L\leq  R\leq n} \left[C(L, R) - \max_{1\le i\le k, L \leq l_i \leq r_i \leq R} C(l_i, r_i) \right]$$

您只需要对于每个 $k$ 输出对应的值，不需要输出方案。

hint:
For the first test case, we only need to consider the case $k = 1$. We can only choose $l_1=r_1=1$. Then the expected loss is $C(1, 1) - C(1, 1) = 0$ and the result is $0 \times 1 \times (2) / 2 = 0$.

For the third test case, consider the case when $k = 3$. We choose $l_1=r_1=1$, $l_2=r_2=3$ and $l_3=1, r_3=3$. The expected loss is $2$. And the result is $2 \times 6 = 12$.


title: [ICPC2020 Shanghai R] Fibonacci

description:
In mathematics, the Fibonacci numbers, commonly denoted as $f_n$, is a sequence such that each number is the sum of the two preceding numbers, starting with $1$ and $1$. That is, $f_1 = 1, f_2 = 1$ and $f_n = f_{n-2} + f_{n-1}~(n \ge 3)$.

Thus, the beginning of the sequence is $1, 1, 2, 3, 5, 8, 13, 21,\ldots$ .

Given $n$, please calculate $\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{g(f_i,f_j)}}$, where $g(x,y) = 1$ when $x \cdot y$ is even, otherwise $g(x,y) = 0$.

inputFormat: The only line contains one integer $n~(1\le n\le 10^9)$.

translation:
在数学中，斐波拉契数列常被记为数列 $f_n$。该数列的首项 $f_1,f_2$ 均为 $1$，并满足递推公式 $f_n=f_{n-2}+f_{n-1}(n\ge 3)$。

因此，数列的前一些项为 $1,1,2,3,5,8,13,21,\cdots$。

若 $x\cdot y$ 为偶数，则函数 $g(x,y)=1$，否则 $g(x,y)=0$。求 $\sum\limits_{i=1}^n{\sum\limits_{j=i+1}^n{g(f_i,f_j)}}$ 的值。


title: [ICPC2020 Shanghai R] Rice Arrangement

description:
Wowo is a hospitable Xinjiang uncle. $k$ guests will have Uyghur Polo (a traditional Uyghur food) in Wowo's house around a big round table. $n$ ($n\ge k$) chairs are placed around the table uniformly. Each guest sits on a chair and no two guests sit on the same chair. $k$ bowls of Uyghur Polo are on the table. Each bowl is next to some chair ($\textbf{with or without}$ some guest sitting on it). No two bowls locate at the same position.

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

As a waiter, you are supposed to assign each person with exactly one bowl of Uyghur Polo. The table can be rotated, so each time you can turn it $\frac{2\pi}{n}$ degrees clockwise or counterclockwise. The bowls turn with the table while the chairs and guests do not move. When one bowl of Uyghur Polo is in front of a guest, he can either take it or wait for another.

You want to minimize the total times of table rotating so that everybody can have meals as quickly as possible.

(Formal definition: The boundary of the table is a circle. $n$ chairs are at $n$ points on the circle whose convex hull is a regular polygon with $n$ vertices. We name the points $0,\ldots, n-1$ in counterclockwise order. The $i$-th bowl is at point $b_i$ ($0\le b_i<n$) initially. The $i$-th guest is at point $a_i$ ($0\le a_i < n$) initially. If you turn the table counterclockwise, the bowl at point $b_i$ ($1\le i\le k$) will be moved to point $(b_i+ 1) \bmod n$ after the rotation. If you turn the table clockwise, the bowl at point $b_i$ ($1\le i\le k$) will be moved to point $(b_i-1) \bmod n$ after the rotation. ($x\bmod n$ is defined as the smallest nonnegative integer $r$ such that $x-r$ is a multiple of $n$.))

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n,k$ ($1\le n \le 10^9,1 \le k \le \min(n,1000)$) indicating the size of the table and the number of persons and bowls of Uyghur Polo.

In the second line, there are $k$ integers $a_1,a_2,\dots,a_k$ ($0 \le a_i < n$), indicating the positions of the persons. No two guests share the same position.

In the third line, there are $k$ integers $b_1,b_2,\dots,b_k$ ($0 \le b_i < n$), indicating the initial positions of the bowls. No two bowls of Uyghur Polo locate at the same position.

It is guaranteed that the sum of $k$ over all test cases does not exceed $5000$.

outputFormat: For each test case, output the minimal total times of rotations such that each guest can have exactly one bowl of Uyghur Polo.

translation:
Wowo 是一名好客的新疆大叔。$k$ 名客人将在 Wowo 的房子里，围在圆桌旁享用新疆抓饭。$n(n \ge k)$ 把椅子已经被均匀的放置在桌子周围，每个客人坐在一把椅子上，没有两名客人坐在同一把椅子上。$k$ 份新疆抓饭已经放在了桌子上，每份抓饭都放在了一把椅子面前（可能没有客人坐在这把椅子上），没有两份抓饭放在同一个位置上。

作为服务员，你需要为每一名客人指定正好一碗抓饭。桌子可以旋转，每次你可以顺时针或逆时针旋转桌子 $\dfrac{2\pi}{n}$ 度。碗随着桌子旋转，但客人和椅子不会随之移动。当一碗饭转到某个客人面前时，他可以选择拿走这碗饭，或等待另一碗。

你想要最小化旋转桌子的次数，使得每个人可以最快得到饭。


title: [ICPC2020 Shanghai R] Sky Garden

description:
Prof. Du and Prof. Pang plan to build a sky garden near the city of Allin. In the garden, there will be a plant maze consisting of straight and circular roads.

On the blueprint of the plant maze, Prof. Du draws $n$ circles indicating the circular roads. All of them have center $(0, 0)$. The radius of the $i$-th circle is $i$.

Meanwhile, Prof. Pang draws $m$ lines on the blueprint indicating the straight roads. All of the lines pass through $(0, 0)$. Each circle is divided into $2m$ parts with equal lengths by these lines.

Let $Q$ be the set of the $n+m$ roads. Let $P$ be the set of all intersections of two different roads in $Q$. Note that each circular road and each straight road have two intersections.

For two different points $a\in P$ and $b\in P$, we define $dis(\{a, b\})$ to be the shortest distance one needs to walk from $a$ to $b$ along the roads. Please calculate the sum of $dis(\{a, b\})$ for all $\{a, b\}\subseteq P$.

inputFormat: The only line contains two integers $n,m~(1\le n,m\le 500)$.

outputFormat:
Output one number -- the sum of the distances between every pair of points in $P$.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.

translation:
Prof. Du 和 Prof. Pang 计划在 Allin 城周围建立一个天空花园。在花园中，将有一个由直路和圆弧路组成的植物迷宫。

在植物迷宫的蓝图上，Prof. Du 画了 $n$ 个圆来表示所有的圆弧路，所有的 $n$ 个圆的圆心均为 $(0,0)$，第 $i$ 个圆的半径为 $i$。

同时，Prof. Pang 在蓝图上画了 $m$ 条直线，表示所有的直路。这 $m$ 条直线将所有的圆均分为 $2m$ 份。

假定集合 $Q$ 是所有 $n+m$ 条路的集合，集合 $P$ 是 $Q$ 中任意两条不相同的路的交点的集合。请注意，每条直线和每个圆有两个交点。

对于任意两个不同的点 $a\in P$，$b\in P$，定义 $\operatorname{dis}(\{a,b\})$ 为从点 $a$ 走到点 $b$ 的最短距离。对于所有 $\{a,b\} \subseteq P$，计算 $\operatorname{dis}(\{a,b\})$ 的和。


title: [ICPC2020 Shanghai R] Octasection

description:
At the Namomo Camp, a cute volunteer celebrates her birthday. Wowo buys her a huge cake. (The cake is so big that it has a 3D coordinate system inside.) There are $n$ cuboid shaped pieces of chocolates $\textbf{in}$ the cake. The $i$-th ($1\le i\le n$) chocolate consists of all points $(x,y,z)$ such that $min\_x[i]\le x\le max\_x[i], min\_y[i]\le y\le max\_y[i], min\_z[i]\le z\le max\_z[i]$. $min\_x,max\_x, min\_y,max\_y, min\_z, max\_z$ are $6$ arrays of integers. Chocolates may overlap or touch each other.

The volunteer wants to distribute the cake to the campers of the Namomo Camp. To show off his knife skill, Wowo decides to cut the cake into pieces by exactly $3$ cuts such that:

- The first cut is a plane whose equation is $x=a$ for some integer $a$ decided by Wowo.
- The second cut is a plane whose equation is $y=b$ for some integer $b$ decided by Wowo.
- The third cut is a plane whose equation is $z=c$ for some integer $c$ decided by Wowo.
- Each chocolate is $\textbf{touched}$ by at least one cut (i.e. each cuboid has a nonempty intersection with at least one plane).

Decide whether Wowo can cut the cake under the rules. If the answer is yes, output any possible solution.

inputFormat:
The first line contains a single integer $n$ ($1\le n\le 100000$).

The $i$-th line of the next $n$ lines contains $6$ integers $min\_x[i],max\_x[i], min\_y[i],max\_y[i], min\_z[i], max\_z[i]$ ($-10^9\le min\_x[i],max\_x[i], min\_y[i],max\_y[i], min\_z[i], max\_z[i]\le 10^9$, $min\_x[i]<max\_x[i]$, $min\_y[i]<max\_y[i]$, $min\_z[i]< max\_z[i]$).

outputFormat: If Wowo can cut the cake under the rules, the first line of the output should contain ``YES`` and the second line should contain $3$ integers $a$, $b$ and $c$ ($-10^9\le a, b, c\le 10^9$). If Wowo cannot cut the cake under the rules, output only one line containing ``NO``.

translation:
有一个巨大的蛋糕，蛋糕里面有$n$块立方体形状的巧克力，每块巧克力的位置由它的对角线坐标定义。一个人想通过三个平面切割这个蛋糕，每个平面的方程分别是$x=a$，$y=b$和$z=c$，其中$a$、$b$和$c$是整数。目标是选择$a$、$b$和$c$这样每块巧克力至少被一个切割平面触及。

输入由一个整数$n$开始，表示巧克力的数量，后面跟着$n$行，每行六个整数，分别代表每块巧克力在三维坐标系中的最小和最大$x$、$y$、$z$坐标。

输出要求是如果存在这样的三个切割平面，第一行输出``YES``，第二行输出三个整数$a$、$b$和$c$。如果不存在，只输出``NO``。


title: [SEERC2020] Archeologists

description: 你在玩一个寻宝类游戏，一共有 $n$ 个格子，编号为 $1 \sim n$，你每在 $i$ 号格子上下挖一层便会获得 $p_i$ 的价值，其中你需要保证每个格子相邻的两个格子都与其下挖的深度的差值不超过 $1$（注意此时 $1$ 和 $n$ 号点最多只能挖一层），请最大化总价值。

inputFormat:
第一行一个整数 $n\ (1 \leq n \leq 2.5 \times 10^5)$。

接下来一行 $n$ 个整数 $p_i\ (-10^6 \leq p_i \leq 10^6)$。

outputFormat: 输出最大价值。


title: [SEERC2020] Reverse Game

description:
Alice 和 Bob 在玩一个游戏，规则如下：

- 游戏开始前给定一个字符串 $s$。

- 每次行动，选择 $s$ 的一个子串 $t$，$t$ 只能是 `10`、`100`、`110`、`1010` 中的一个，反转 $t$ 的每个字符，例如 `100` 翻转为 `001`。

- 不能操作者输掉游戏。

Alice 先手，问双方同时采取最优策略的情况下，谁能赢。

inputFormat: 一个仅包含 $01$ 的字符串 $s\ (1 \leq |s| \leq 10^6)$。

outputFormat: 如果 Alice 胜利输出 `Alice`，Bob 胜利输出 `Bob`。

hint: 对于样例 $1$，选择子串 `10` 进行反转后 Bob 无法操作。


title: [SEERC2020] 3-colorings

description:
**这是一道仅有输出的题。**

定义一个图的有效“三色”染色为：

- 每个点的颜色只能属于 $\{1,2,3\}$。

- 对于每个有边相连的顶点 $(u,v)$，$u$ 的颜色需要与 $v$ 不同。

可以证明，一个图最多的“三色”染色总数为 $3^n$ 种。

现在你需构造一个图，一开始它存在 $n \ (1 \leq n \leq 19)$ 个顶点 $m \ (1 \leq m \leq \frac{n(n-1)}{2})$ 条无向边，然后对于每个 $1 \leq k \leq 500$ 的 $k$，你可以添加至多 $17$ 条无向边使得此图的“三色”染色总数为 $6k$ 种。

inputFormat: 无。

outputFormat:
第一行 $n,m$，表示你构造图的点数和边数。

然后 $m$ 行，一行两个整数 $u,v$，表示 $(u,v)$ 存在一条无向边。

然后 $k$ 从 $1$ 到 $500$，每个 $k$ 输出你要添加的边数，然后再是对应行添加的边 $(u,v)$。

hint: 样例仅给出 $k=1$ 和 $k=2$ 的示例。


title: [SEERC2020] Disk Sort

description:
你有 $n+1$ 根棍子，一开始 $1 \sim n$ 的每根棍子上面都会存在 $3$ 个盘，颜色不超过 $n$ 种。

每次操作，你可以选择一对 $(a_i,b_i)$，表示将 $a_i$ 最顶上的圆盘放到 $b_i$ 最上面（$a_i$ 的圆盘数量至少为 $1$，$b_i$ 的数量至多为 $2$）。

你需要构造出一种合法方案使得操作结束后每个盘上的颜色都一样且 $n+1$ 号为空。

inputFormat:
第一行一个整数 $n\ (1 \leq n \leq 1000)$，表示共有 $n$ 根棍子。

接下来 $3$ 行，每行 $n$ 个整数 $c_{i,j}\ (1 \leq c_{i,j} \leq n)$，表示第 $j$ 个棍子上面自上向下数第 $i$ 个的颜色。

outputFormat:
第一行一个整数 $k\ (1 \leq k \leq 6n)$，表示操作次数。

然后 $k$ 行，每行一对 $(a_i,b_i)$，表示交换的对象。


title: [SEERC2020] Divisible by 3

description:
定义一个序列 $b$ 的权重为 $\sum_{i=1}^n \sum_{j=1}^{i-1} b_i \times b_j$。

现在你有一个长度为 $n$ 的数组 $a$，求一共存在多少种 $(l,r)$ 使得 $1 \leq l \leq r \leq n$ 且 $[a_l, a_{l+1},\ldots,a_r]$ 的权重能被 $3$ 整除。

inputFormat:
第一行一个整数 $n\ (1 \leq n \leq 5 \times 10^5)$。

然后 $n$ 个整数 $a_i\ (0 \leq a_i \leq 10^9)$。

outputFormat: 输出方案总数。


title: [SEERC2020] Fence Job

description:
Fred 有一个长度为 $n$ 的排列 $h$，每次操作他可以选择一段区间 $[l,r]$，令 $h_i = \min_{j=l}^{r}h_j\ (i \in [l,r])$。

问进行若干次操作（可以为 $0$ 次）后不同的数组数量，对 $10^9 + 7$ 取模。

inputFormat:
第一行一个整数 $n\ (1 \leq n \leq 3000)$。

接下来一行 $n$ 个整数 $h_i\ (1 \leq h_i \leq n)$。

outputFormat: 输出操作后不同数组的数量模 $10^9+7$ 的值。


title: [SEERC2020] Simple Hull

description:
Gary 创造了一个含有 $n$ 个点的多边形，每个点的坐标形如 $(x,y)$。

你需要进行一些连边，保证包含所有的点，同时连出来的图是一条“多边形链”（即任何一个点只能连向或被连向 $2$ 个点，且连出来的边可以在图中与其他边相交）。

你还需要保证每两个存在连边的点 $i$ 和 $j$，这两个点形成的边在图中是垂直或水平的。

输出连出来的图的最小面积。

inputFormat:
第一行一个整数 $n\ (1 \leq n \leq 10^5)$，表示点的个数。

然后 $n$ 行，每行两个整数 $x_i,y_i\ (1 \leq x_i,y_i \leq 10^6)$。

outputFormat: 输出连出的 $n$ 边形的面积。

hint:
三个样例画出的图依次为：

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

（上述图未按比例画图）


title: [SEERC2020] AND = OR

description:
一个数组 $b$ 被称为“好的数组”当且仅当可以将 $b$ 划分为两个非空的子数组，这两个子数组中第一个子数组的 $\mathtt{OR}$ 结果与第二个子数组的 $\mathtt{AND}$ 结果相等，例如 $\{1,7,3,11\}$，将其划分为 $\{1,3\}$ 与 $\{7,11\}$，$1\ \mathtt{OR}\ 3 = 3$，$7\ \mathtt{AND}\ 11 = 3$，所以它是一个好的数组。

现在给定一个长度为 $n$ 的数组 $a$，$q$ 组询问，每次给定 $[l,r]$，为 $\{a_l, a_{l+1},\ldots,a_{r-1},a_{r}\}$ 是不是一个好的数组。

inputFormat:
第一行两个整数 $n\ (1 \leq n \leq 10^5)$ 和 $q\ (1 \leq q \leq 10^5)$。

然后一行 $n$ 个整数表示序列 $a\ (0\leq a_i \leq 2^{30}-1)$。

接下来 $q$ 行，一行两个整数 $l,r\ (1 \leq l \leq r \leq n)$，表示一组询问。

outputFormat: 对于每个询问，如果该子数组是好的输出 `YES`，否则输出 `NO`。

samples:
NO
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
YES
NO
NO
NO


title: [SEERC2020] Modulo Permutations

description: 求长度为 $n$ 的 $1 \sim n$ 的所有排列总数，其中满足 $p_i \bmod p_{i+1} \leq 2$ 的（此处 $p_{n+1} = p_1$），对 $10^9 + 7$ 取模后的值。

inputFormat: 一个整数 $n\ (1 \leq n \leq 10^6)$。

outputFormat: 输出答案模 $10^9+7$ 后的值。


title: [SEERC2020] One Piece

description:
有一个图，它是一个 $n$ 个点的树，每条边都是形如 $(u,v)$ 的边长为 $1$ 的无向边。

你有一个寻宝器，当你在点 $i$ 时，它会返回一个最远距离 $x$，表示存在宝藏的位置距 $i$ 点最远长度为 $x$，一个图可能存在多个宝藏。

现在你知道了对于 $1 \leq i \leq n$ 时的寻宝器返回结果，问你确定每个点是否存在宝藏的概率从大到小依次排序后的数组。

inputFormat:
第一行一个整数 $n\ (1 \leq n \leq 2.5 \times 10^5)$，表示点数。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条边。

再一行 $n$ 个数，表示在 $i$ 点调用寻宝器的返回值。

outputFormat:
输出每个点是否存在宝藏的概率从大到小依次排序后的数组。

同概率下标升序排序。


title: [SEERC2020] Codenames

description:
有 $q$ 个 $5 \times 5$ 的图表，给出每个点的颜色（只可能是 `r`、`b`、`n`、`x`），具体颜色分配为：$9$ 个 `r`，$8$ 个 `b`，$5$ 个 `n`，一个 `x`。

图表中每个点对应的字符始终确定，分别为：

```
abcde
fghij
klmno
pqrst
uvwxy
```

图表中某些颜色已经翻开来了（用其颜色的大写字母表示已显示），然后你需要从一个 $n$ 个字符串的列表内选择一个字符串 $w$ 和一个数字 $g$，按下述规则进行操作 $g$ 次。

- 如果当前 $w_i$ 字符代表的格子颜色已经被公示，不进行操作，令 $i \gets i + 1$。
- 否则，翻开 $w_i$ 代表的格子，如果 $w_i$ 的颜色为 `n`、`b` 或 `x`，就输了。然后再令 $i \gets i+1$。
- 当 $g$ 次操作完成或所有 `r` 色块都翻出来时结束操作。

你想要使得所有 `r` 色块都翻出来，求一组满足条件的 $w$ 与 $g$。

inputFormat:
第一行一个整数 $n\ (1 \leq n \leq 10^5)$。

然后 $n$ 行，每行一个字符串，描述了一整个字符串列表。

第 $n+2$ 行，整数 $q\ (1 \leq q \leq 10^5)$，表示表格个数。

然后 $q$ 组图表，每个图表占据 $5 \times 5$ 的大小，描述了第 $i$ 个图表的颜色。

outputFormat: 对于每个图表，如果有解，输出一组合法的 $w$ 和 $g\ (1 \leq g \leq 9)$，无解输出 `IMPOSSIBLE`。

samples:
3
actor
cheat
zeta
1
rBBnR
NRnbB
nRRnR
NRxBr
nBRbB

hint: 答案还可能是 `actor 4`，`zeta 2` 等。


title: [SEERC2020] Neo-Robin Hood

description:
你是一个大盗，镇上一共有 $n$ 户人家，对于每户人家 $i$，你在如下的选择里选一样。

- 盗窃他的 $m_i$ 元钱，他会对你起仇恨。

- 给他 $p_i$ 元钱，他会让你盗窃的一个人取消对你的仇恨。

- 什么也不做。

初始时你没有钱，你想知道，在没人对你有仇恨且你手中的钱非负的情况下，你最多能盗窃多少户人家。

注：你可以按任意顺序依次访问每户人家。

inputFormat:
第一行一个整数 $n\ (1 \leq n \leq 10^5)$。

第二行一个长度为 $n$ 的序列 $m\ (1 \leq m_i \leq 10^9)$。

第三行一个长度为 $n$ 的序列 $p\ (1 \leq p_i \leq 10^9)$。

outputFormat: 输出最多能盗窃的人家数。


title: [SEERC2020] Mistake

description:
你有 $k$ 个机器，每个机器都**未按序**存储了 $1 \sim n$ 共 $n$ 个数，当你启动某个机器时，该机器会将其存储的数最前面的数打印出来，然后删除它。

但是很幸运，你知道 $m$ 对 $(a_i,b_i)$，表示每个存储的 $a_i$ 都在 $b_i$ 前面。

你还知道你依次启动的机器输出了哪些，请对于每个打印的数，确定一种方案表示它是由哪个机器启动得来，保证每个数出现的次数 $=n$。

存在多种可行解，输出任何都可以得分。

inputFormat:
第一行三个整数 $n,k,m\ (1 \leq n,k\leq 5 \times 10^5, 0 \leq m \leq 2.5 \times 10^5, 1 \leq n \times k \leq 5 \times 10^5)$。

然后 $m$ 行每行两个 $a_i,b_i\ (1 \leq a_i,b_i \leq n)$，保证不存在环。

然后一行 $n \times k$ 的数，表示依次启动的机器输出的序列。

outputFormat: 输出一种合法的启动方案。


title: [ICPC2020 Shanghai R] Traveling Merchant

description:
Mr. Lawrence is a traveling merchant who travels between cities and resells products. Basically, to earn from it, he needs to buy products at a very low price and sell them at a higher price. Your task is to tell him whether there exists an endless traveling path that can earn money all the time.

To make things simple, suppose there are $n$ cities named from $0$ to $n-1$ and $m$ undirected roads each of which connecting two cities. Mr. Lawrence can travel between cities along the roads. Initially he is located at city $0$ and each of the city $i$ has a starting price $c_i$, either $\text{Low}$ or $\text{High}$. Due to the law of markets, the price status at city $i$ will change (i.e. $\text{High}$ price will become $\text{Low}$ price, or vice versa) after he departs for a neighboring city $j$ from $i$. (City $j$ is a neighboring city of city $i$ when one of the $m$ roads connects city $i$ and city $j$.) For some reasons (e.g. product freshness, traveling fee, tax), he $\textbf{must}$:

- Start at city $0$ and buy products at city $0$. It is guaranteed that $c_0$ is $\text{Low}$.
- When he arrives some city, he either sells products or buys products. It is not allowed for him to do nothing before he leaves the city.
- After buying products at some city $i$, he must travel to some neighboring city $j$ whose price $c_j$ is $\text{High}$ and sell the products at city $j$.
- After selling products at some city $i$, he must travel to some neighboring city $j$ whose price $c_j$ is $\text{Low}$ and buy the products at city $j$.

As a result, the path will look like an alternation between ``buy at low price'' and ``sell at high price''.

An endless earning path is defined as a path consisting of an endless sequence of cities $p_0, p_1,\dots$ where city $p_i$ and city $p_{i+1}$ has a road, $p_0=0$, and the price alternates, in other words $c_{p_{2k}}=\text{Low}$ (indicates a buy-in) and $c_{p_{2k+1}}=\text{High}$ (indicates a sell-out) for $k\geq0$. Please note here $c_{p_i}$ is the price when $\textbf{arriving}$ city $p_i$ and this value may be different when he arrives the second time.

Your task is to determine whether there exists any such path.

inputFormat:
There are several test cases. The first line contains a positive integer $T$ indicating the number of test cases. Each test case begins with two positive integers $n$ and $m$ indicating the number of cities and the number of roads.

The next line is a string $c$ of length $n$ containing `H' or `L'. The $i$-th ($0\le i<n$) charactor of $c$ is $H$ if the starting price $c_i$ at city $i$ is $\text{High}$. The $i$-th ($0\le i<n$) charactor of $c$ is $L$ if the starting price $c_i$ at city $i$ is $\text{Low}$.

The $i$-th line ($1\le i\le m$) of the following $m$ lines contains two different cities $u_i$ and $v_i$, indicating a road between $u_i$ and $v_i$.

The sum of the values of $n$ over all test cases is no more than $200,000$. The sum of the values of $m$ over all test cases is no more than $200,000$. For each test case, $c_i\in\{\text{H},\text{L}\}$ holds for each $i\in \{0, \ldots, n-1\}$. $c_0$ is always $L$. $0\leq u_i,v_i<n$ and $u_i\neq v_i$ hold for each $i\in \{1,\ldots, m\}$. No two roads connect the same pair of cities.

outputFormat: For each test case, output a line of ``yes`` or ``no``, indicating whether there exists an endless earning path.

translation:
### 题目描述

劳伦斯先生是一位在不同城市转售商品的旅行商人。基本地，为了赚钱，他需要以低价买进商品，再以高价卖出。现在请你为他规划一条可以一直盈利的旅行路线。

简单地说，假设有 $n$ 座城市，标号为 $0$ 到 $n-1$ ，以及 $m$ 条连接特定两座城市的路，劳伦斯先生可以通过这些路到访每座城市。最初劳伦斯先生位于第 $0$ 座城市，并且对于城市 $i$ 都有一个起始价格 $c_i$ 。根据市场规律，当他从城市 $i$ 来到相邻的城市 $j$ 时（当且仅当城市 $i$ 与城市 $j$ 之间有路径相连时，才称 $i$ 与 $j$ 为相邻城市），城市 $i$ 的价格状况会发生变化（高价会变成低价，低价也可能变成高价）。而因为一些原因（比如商品的新鲜程度，旅行费用，税务等），他**必须**：

- 从城市 $0$ 出发并在城市 $0$ 购买一些商品。保证城市 $0$ 的起始价格很**低**。
- 每当他到达一座城市后，他**必须**售卖**或**购买一些商品。
- 若他在城市 $i$ 购买了商品，他就必须去一座与 $i$ 相邻且价格 $c_j$ **高于** $c_i$ 的城市 $j$ ，并在那里卖掉手中来自城市 $i$ 的商品。
- 若他在城市 $i$ 售卖了商品，他就必须去一座与 $i$ 相邻且价格 $c_j$ **低于** $c_i$ 的城市 $j$，并在那里购买一些商品。

因此，最终路径会始终重复 ``低价购入`` 和 ``高价卖出`` 。

一条无尽的盈利路线由无尽的城市序列 $p_0,p_1 \dots$ 组成。其中，城市 $p_i$ 与城市 $p_{p+1}$ 之间有路径相连，$p_0 = 0$，且价格高低是交替循环的，也就是说当 $k \ge 0$ 时，城市 $p_{2k}$ 的价格 $c_{p_{2k}} = \text{Low}$ (要在这个城市购买商品) 而相邻城市 $p_{2k+1}$ 的价格 $c_{p_{2k+1}} = \text{Hign}$ (要在这个城市卖出商品)。

**注意**：$c_{p_i}$ 是 **到达** 城市 $p_i$ 时的价格，而当他第二次到达城市 $p_i$ 时，这个价格可能会因为市场规律而变化。

你需要写一个程序，判断是否有这样一条永远盈利的路径存在。
### 输入格式

输入有多组数据。所有数据的第一行是一个整型 $T$ 表示数据组数。每组数据的第一行是两个整型 $n$ 和 $m$，表示城市的数量和道路的数量。

每组数据的第二行是一个长度为 $n$ ，由 $H$ 或 $L$ 组成的字符串 $c$ 。字符串 $c$ 的第 $i$ 个字符若为 $H$，则表示城市 $i$ 的起始价格 $c_i$ **高**，反之若为 $L$ 则表示城市 $i$ 的起始价格 $c_i$ **低**。

接下来 $m$ 行，每行输入一组 $u_i$ 和 $v_i$ ，表示一条连接城市 $u_i$ 和城市 $v_i$ 的双向路径。

所有数据中 $n$ 的总和不超过 $200,000$ ，$m$ 的总和也不超过 $200,000$ 。对于每组数据，$c_i\in\{\text{H}, \text{L}\}$ 对应每个 $i\in\{0, \dots, n-1\}$ ，保证 $c_0$ 总为 $L$ 。保证对于每个 $i\in\{1,\dots,m\}$ ，都有 $0 \leq u_i,v_i < n$ 且 $u_i \neq v_i$ 。保证每两座城市之间只有一条路径相连。

### 输出格式
对于每组数据，输出一行 ``yes`` 或者 ``no`` ，表示是否存在一条无尽的盈利路径。

hint:
In the first sample test case, the endless earning path is $0\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow \dots$. In the illustration, cities with $\text{Low}$ price are filled with stripe.

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

In the second sample test case, Mr. Lawrence can only make one move from city $0$ and after that all cities will have $\text{High}$ price. Thus, no further moves can be made.

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


title: [ICPC2020 Shanghai R] Traveling in the Grid World

description:
Consider a grid pattern with $n$ rows and $m$ columns. There are $(n+1)\times(m+1)$ grid points in total which is the intersections of $n+1$ horizontal lines and $m+1$ vertical lines. We number the horizontal lines from $0$ to $n$ from top to bottom. We number the vertical lines from $0$ to $m$ from left to right. The intersection of horizontal line $i$ and vertical line $j$ is named $(i, j)$ ($0\le i\le n, 0\le j\le m$).

There are some constraints when you travel in the grid world. When you are located at point $(x,y)$, you can choose a destination $(x',y')$ and walk to it along the line segment between $(x, y)$ and $(x', y')$. We call this operation a $\textit{walk}$. A walk is forbidden if there exists another grid point different from $(x, y)$ and $(x', y')$ lying on the line segment between them. You can walk as many times as you want but the directions of two consecutive walks cannot be the same. (Specifically, if you walk from $(x_0, y_0)$ to $(x_1, y_1)$ and then walk from $(x_1, y_1)$ to $(x_2, y_2)$, you must make sure that $(x_0-x_1)(y_1-y_2)\neq (x_1-x_2)(y_0-y_1)$.) The length of a walk from $(x, y)$ to $(x', y')$ is defined as the Euclidean distance between the two endpoints, $\sqrt{(x-x')^2+(y'-y)^2}$.

Starting from $(0,0)$, you are planning to arrive at $(n,m)$ by several walks. Because of the annoying rules, you may need some turning points to achieve your goal. Please find the minimum total length of your walks.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n,m$ ($1\le n,m \le 10^6$) indicating the size of the grid graph.

It is guaranteed that the sum of the values of $\max(n,m)$ over all test cases does not exceed $10^6$.

outputFormat: For each test case, output the minimum total length of walks. Your answer will be considered correct if its absolute or relative error does not exceed $10 ^{-9}$.

translation:
### 题目描述

考虑具有 $n$ 行和 $m$ 列的网格模式。总共有$（n+1）\times（m+1）$网格点，即$n+1$水平线和$m+1$垂直线的交点。我们将水平线从上到下从 $0$ 到 $n$ 编号。我们将垂直线从左到右编号从 $0$ 到 $m$。水平线 $i$ 和垂直线 $j$ 的交点命名为 $(i,j)$($0 \le i \le n， 0 \le j \le m$)。

当您在网格世界中旅行时，会有一些限制。当您位于点 $(x,y)$ 时，您可以选择一个目的地 $(x',y')$ 并沿着 $(x,y)$ 和 $(x',y')$ 之间的线段步行到该目的地。我们将此操作称为 $\textit{walk}$。如果它们之间的线段上存在另一个不同于 $(x,y)$ 和 $(x', y')$ 的网格点，则禁止行走。您可以随心所欲地走很多次，但连续两次步行的方向不能相同。（具体来说，如果从 $(x_0,y_0)$ 到 $(x_1, y_1)$，然后从 $(x_1, y_1)$ 到 $（x_2， y_2）$，则必须确保 $(x_0-x_1)(y_1-y_2) \neq (x_1-x_2)(y_0-y_1)$。从 $(x,y)$ 到 $(x',y')$ 的步行长度定义为两个端点之间的欧几里得距离 $\sqrt{(x-x')^2+(y'-y)^2}$。

从 $(0,0)$ 开始，您计划通过几次步行到达 $(n，m)$。由于烦人的规则，您可能需要一些转折点来实现您的目标。请找到您步行的最小总长度。

### 输入格式

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例，
第一行包含两个整数 $n,m$ （$1 \le n,m \le 10^6$），表示网格图的大小。

保证所有测试用例中 $\max(n,m)$ 的值之和不超过 $10^6$。


title: [ICPC2020 Shanghai R] Gitignore

description:
Your git project (you don't need to be familiar with git to solve this problem) has some files that should be ignored from synchronizing. You need to calculate the minimum number of lines needed for gitignore.

Formally, your project is a folder. A folder can have files and sub folders. There are no empty folders (i.e. folders without any files or sub folders inside). Initially, the git software will synchronize all the files in your project. However, you can specify some files and folders in the settings (which is called gitignore) to exclude them from synchronizing. For each line in gitignore, you can specify either a file or all the files in a folder. You can $\textbf{not}$  ignore the whole project folder (i.e. an empty line in gitignore).

You are given paths for all the files in the project and whether they should be ignored or shouldn't. Your task is to calculate the minimum number of lines for gitignore.

inputFormat:
The input contains several test cases. The first line contains a single positive integer $T$ which is the number of test cases. For each test case, you are first given two non-negative numbers $n$ and $m$. And then $n$ non-empty lines of file paths that should be $\textbf{ignored}$, and $m$ non-empty lines of file paths that should $\textbf{not}$ be ignored.

The paths are strings containing lower-cased English alphabets and slashes (`/`) only. Slashes are used to separate folders, sub folders and file name. For exapmle, ``a/b/c/d`` indicates folder ``a`` in the project folder, folder ``b`` in folder ``a``, folder ``c`` in ``b`` and file ``d`` in folder ``c``. All the paths are valid, specifically:

- The path is non-empty and it always indicates a file (i.e. the path does not end with a slash).
- The path does not start with a slash.
- Folder names and file names are non-empty (i.e. there are no consecutive slashes).
- File paths are always unique (i.e. all the paths in a test case are different).
- In a folder, no sub folders and files share the same names. For example, there won't be two files ``a/b/a`` and ``a/b/a/d`` in one test case. However, files ``a/b/a`` and ``a/b/b`` are allowed.

$1\leq n+m\leq 100$ holds and in the whole input there are no more than $1,000$ characters in file paths (i.e. the sum of lengths of file path strings in the whole input file is no more than $1,000$).

outputFormat: $T$ lines of non-negative integers, the minimum number of gitignore lines for each test case.

translation:
你使用 git 管理的一个项目有一些需要被忽略的文件。你需要计算 .gitignore 文件中至少写入多少行。

详细来说，你的项目是一个文件夹，文件夹可以含有文件或子文件夹。在本题中，不会出现空文件夹（不含文件或子文件夹的文件夹）。git 软件会同步你项目中所有的文件，但是，你可以在 .gitignore 中写入一些信息，使某些文件或文件夹不被同步。在 .gitignore 文件中的一行，你可以指定一个文件或者一个文件夹，使得这个文件或这个文件夹中的所有文件不被同步。**你不可以忽略整个项目文件夹。**

你会得到项目中所有文件的路径，以及他们是否应该被同步，你的任务是计算 .gitignore 文件中最少的行数。

samples:
2
3 0
data/train
data/test
model
3 1
data/train
data/test
model
data/sample

hint:
In the first sample test case, the corresponding gitignore file contains $2$ lines: a folder line ``data/`` and a file name ``model``.

In the second sample test case, the corresponding gitignore file contains $3$ file lines: ``data/train``, ``data/test`` and ``model``.


title: [ROIR 2020 Day1] 平方

description:
**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day1 T1.** ***[Разность квадратов](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day1.pdf)，译者 ShineEternal***

你参与了字符计算系统软件模块的开发，将用于求解一类特殊的丢番图方程，具体内容如下：

给定一个非负整数 $n$，正在开发的模块需要找到两个正整数 $x$ 和 $y$，使得 $x^2-y^2=n$，其中 $x,y$ 不超过 $2^{62}-1$。

你需要编写一个程序，对于给定的非负整数 $n$，求出两个自然数 $x$ 和 $y$，使得它们都不超过 $2^{62}-1$ 且其平方差为 $n$。

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

outputFormat:
如果存在可能的 $x,y$，则打印两行，第一行为一个单独的字符串 `Yes`，第二行打印任意一组 $x,y$。

如果不存在则输出 `No`。


title: [ROIR 2020 Day1] 对常规的斗争

description:
**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day1 T3.** ***[Борьба с рутиной
](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day1.pdf)，译者ShineEternal***

判断员工业绩的一个重要因素就是处理日常事务的能力。

我们考虑员工连续 $n$ 天的工作情况，第 $i$ 天执行的工作为 $a_i$。

为了评估员工的工作业绩，使用以下方法：

选定一个整数 $d$，考虑所有 连续 $d$ 天的日期段，对于每一段这样的日子，我们统计员工完成的不同工作的种类数。

记 $S_d$ 表示每一段这样连续 $d$ 天的日期段完成的不同种类工作数之和。

现在需要你来统计出 $S_{1\sim n}$ 的值。

inputFormat:
输入共两行:

第一行为一个整数 $n$，表示工作的总天数。

第二行 $n$ 个整数，表示每天所做的工作种类编号。

outputFormat: 输出共 $n$ 个数，为 $S_{1\sim n}$。


title: [ROIR 2020 Day1] 机器人锦标赛

description:
**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day1 T4.** ***[Олимпиада для роботов
](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day1.pdf)，译者 alpha1022***

机器人高速布尔函数计算锦标赛的任务由评委会准备。

机器人的一个任务是一张 $m$ 行 $n$ 列的表格，其中每个格子有一个整数权值，且记第 $i$ 行 $j$ 列的格子的权值为 $x_{i,j}$。
对于每一列，该列中所有格子的权值组成了一个 $0\ldots m-1$ 的排列。换句话说，每列中所有格子的权值互不相同：
若 $i \ne k$，则对于所有的 $j$ 有 $x_{i,j} \ne x_{k,j}$，且有 $0 \le x_{i,j} < m$。

对于每一列，评委会设置了一个阈值 —— 一个在 $[0,m]$ 内的非负整数 $z_j$。你需要以所有形如 $x_{i,j} < z_j$ 的逻辑表达式的值为参数计算布尔函数的值。一个逻辑表达式的值为 $1$ 当且仅当这个表达式成立，否则为 $0$。

在比赛中，选手们需要计算 $m$ 个布尔函数的值 —— 对每一行计算一次。每个布尔函数以一个**非重复单调线性规划**（NMLP）定义。

考虑第 $i$ 行的 NMLP。
这是由 $n-1$ 条以 $1 \ldots n-1$ 编号的指令组成的一个序列，第 $p$ 条指令给定三个数：$a_p, b_p, op_p$。$op_p$ 只有两种取值：$1$ 表示与运算，$2$ 表示或运算。
而 $a_p,b_p$ 则是第 $p$ 个指令的参数，满足 $1 \le a_p,b_p < n+p$。

考虑一个仅包含 $0$ 和 $1$ 的数组 $val[1\ldots 2n-1]$。对于 $1 \le j \le n$，$val[j] = [x_{i,j} < z_j]$，其中 $[P]$ 表示表达式 $P$ 的值。
而 $val[n+p]$ 的值通过第 $p$ 条指令计算。
 - 对于 $op_p = 1$，$val[n+p] = (val[a_p]\ \texttt{and}\ val[b_p])$。
 - 对于 $op_p = 2$，$val[n+p] = (val[a_p]\ \texttt{or}\ val[b_p])$。

该规划是非重复的，也就是说，对于 $p = 1\ldots n-1$，所有 $2n-2$ 个 $a_p,b_p$ 的值互不相同。

程序执行的结果即为 $val[2n-1]$。

目前评委会已经准备好了所有的 $x_{i,j}$，需要由你来确定每一列的阈值才能完整地准备这个任务。
评委会认为一个任务是平衡的，当且仅当所有 $m$ 行中恰有 $s$ 行的布尔函数最后得到的结果为 $1$，其余 $m-s$ 行得到 $0$。
你的任务即为替评委会找到合适的阈值。

对于此题，可以证明一定存在至少一种选择阈值的方案满足上述条件。

inputFormat:
第一行，三个整数 $n,m,s$。
以下 $m(n-1)$ 行，第 $i \cdot (n-1) + p\;(1 \le p \le n-1)$ 行包含三个整数 $a_p,b_p,op_p$，表示第 $i$ 行的第 $p$ 个操作。
以下 $m$ 行，每行 $n$ 个整数，表示所有的 $x_{i,j}$。

outputFormat:
输出 $n$ 个整数 $z_1, z_2, \ldots, z_n\;(0 \le z_j \le m)$。
如有多解，任意输出一个即可。


title: [ROIR 2020 Day2] 最大乘积

description:
**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day2 T1.** ***[Максимальное произведение](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day2.pdf)***，译者ShineEternal

给定一个自然数组成的数组 $[a_1,a_2,\ldots,a_n]$。
定义一个数组的权值为这个数组中所有数的和。

请把这个数组划分为两个非空数组 $[a_1,a_2,\ldots,a_i]$ 和 $[a_{i+1},a_{i+2},\ldots,a_n]$，使得它们的权值之积尽量大。
你需要确定能够使得两个数组权值之积最大的 $i$。

inputFormat:
第一行，一个整数 $n$，表示元素的个数。
第二行，$n$ 个整数 $a_1,a_2,\ldots,a_n$，表示数组中的元素。

outputFormat:
输出能使得 $[a_1,a_2,\ldots,a_i]$ 和 $[a_{i+1},a_{i+2},\ldots,a_n]$ 权值之积最大的 $i$。
若有多解，随意输出一解即可。


title: [ROIR 2020 Day2] 区域规划

description:
**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day2 T2.** ***[Планировка участка](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day2.pdf)***，译者Alpha1022

*译者注：由于原题面有点令译者难以理解，所以此处直接抽象题意。*

你有四个变量 $a,b,c,d$ 须满足：
 - $a,b,c,d \in \mathbb N^*$。
 - $a \ne x, b \ne x$。
 - $a > c, b > d$。
 - $a \cdot b - c \cdot d = n$。

对于给定的 $x,n$，请求出 $a,b,c,d$ 有多少种取值方案。

inputFormat:
第一行，两个整数 $n,x$。
若 $x=0$，则表示忽略第二个条件。

outputFormat: 一行，表示 $a,b,c,d$ 的取值方案数。


title: [ROIR 2020 Day 2] ATM

description:
**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day2 T3.** ***[Банкомат](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day2.pdf)***,译者ksyx

你正在开发一个多面额 ATM，称为 Universal ATM。具体地说，现在有 $n$ 种升序排序的面额分别为 $a_1,~a_2,~\ldots,~a_n$ 的纸币，即对于 $i>2$，有 $a_{i-1}<a_i$。除此之外，还保证 $a_1=1$。

假设客户要取总额为 $c$ 的纸币，你开发的 ATM 将使用如下算法进行纸币的分配：每次选取一个选取后发给用户的总金额不超过 $c$ 最大面额，直至总金额达到 $c$。因为存在面额为 $1$ 的纸币，我们可以发现这个算法总是能够结束。

为了评估这个算法的效率，你想知道对于总额不超过 $b$ 的请求最大需要多少张纸币。因为业务场景不同，你总共需要回答 $q$ 个场景下的询问 $b_1,~b_2,~\ldots,~b_q$。

你的任务是编写一个程序，根据给出的面额列表确定在不同业务场景下最大需要多少张纸币。

inputFormat:
第一行一个整数 $n$，表示面额的数量。

接下来一行 $n$ 个整数 $a_i$。

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

接下来 $q$ 行每行一个整数 $b_i$。

outputFormat: 对于每一个询问，输出两个整数，分别表示取出纸币数量最多的情况下客户取出的总额和取出纸币的数量。如果多个不超过输入中最大总额的取款请求都对应这个纸币数量，输出任意一个。


title: [ROIR 2020 Day 2] 海报

description:
**译自 [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day2 T4.** ***[Плакаты](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day2.pdf)***,译者ksyx

你的朋友们为了会见 IOI 回来的国家队选手准备了很多漂亮的海报，现在就还差要考虑些细节了。

为了欢迎这些选手，你的 $n$ 个朋友会拿着海报站成一个圈。为了方便描述，我们把他们编号为朋友 $1\ldots n$，其中对于 $i\in [1,n-1]$，朋友 $i$ 和朋友 $i+1$ 站在一起，且朋友 $n$ 和朋友 $1$ 站在一起。

每张海报都有一个美观度，其中朋友 $i$ 拿着的海报的美观度为 $a_i$。当开始庆祝时，一些朋友会举起他们的海报。为了美观，不能有 $4$ 个或以上排在一起的朋友同时举起他们的海报。

为了能够丰富节目效果，你的朋友们还打算在庆祝过程中更换 $q$ 次海报。每次更换后，海报 $p_i$ 的美观度将变为 $q_i$。你的朋友想知道每次更换后在符合上述条件下的最大美观度之和。

你的任务是给出初始的美观度，求出初始以及各次更换后的最大美观度之和。

*译者注：题面省略了部分难以理解的不必要细节。*

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

接下来一行 $n$ 个整数 $a_i$，表示初始美观度。

第三行 $q$ 个整数表示海报更换次数。

接下来 $q$ 行每行两个整数 $p_i,~v_i$，描述一次更换。

outputFormat: 输出 $q+1$ 行，表示初始时及各次更换后最大的美观度之和。


title: 永恒（Eternity）

background:
>$$行走人间的，$$
>
>$$不一定是天使。$$
>
>$$带来灾厄的，$$
>
>$$不一定是恶魔。$$
>
>$$恶魔的眼泪被天使珍藏 ， $$
>
>$$天使的纯净由恶魔守护。$$
>
>$$或许，$$
>
>$$这是最好的结局。$$

description:
一些前置定义：

- 可重集中的元素必须是非负整数。

- 可重集的大小为可重集中元素的个数。

- 对于一个大小为 $x$ 的可重集，设其中的元素为 $a_1,a_2\dots a_x$，那么这个可重集的**权值**就为 $a_1\oplus a_2\oplus \dots \oplus a_x$，即可重集中所有元素的**异或和**。

现在给出 $n,m$。

问有多少不同的大小为 $n$ 的可重集 $S$ 满足：

$$\max\limits_{T \subseteq  S,T\ne \emptyset}{Q_T}=m$$

其中 $Q_T$ 为可重集 $T$ 的**权值**。

**注意：根据可重集的性质，数字相同但数字顺序不同的可重集算同一种可重集，即 $\left \{ 1,2,3 \right \} $ 与 $\left \{ 3,2,1 \right \} $ 算同一种可重集。**

求出不同可重集的个数 $\bmod\ 998244353$ 的结果。

可以证明这样的可重集个数是有限的。

inputFormat: 第一行两个整数，分别表示 $n$ 和 $m$。

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


title: [SHOI2006] 作业 Homework

description:
给定一个集合为 $S$，初始为空，你需要执行以下两个操作共 $N$ 次。

操作一，在集合 $S$ 中加入一个新元素，其代号为 $X$，保证 $X$ 在当前集合中不存在。

操作二，在当前的集合 $S$ 中询问所有元素 $\bmod\ Y$ 最小的值。

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

接下来 $N$ 行，每行一个字符和一个正整数，如字符为 `A`，表示这个操作是操作一。若字符为 `B`，则这个操作为操作二。

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

hint: 对于 $100\%$ 的数据，$N\leq10^5$，$X,Y\leq3\times10^5$。数据保证，第一个操作为操作一。


title: [ICPC2021 Nanjing R] Oops, It's Yesterday Twice More

description:
After the great success in 2018, 2019, and 2020, Nanjing University of Aeronautics and Astronautics (NUAA) will host the $\textit{International Collegiate Programming Contest}$ (ICPC) Nanjing regional for the fourth time.

Team $\textbf{\textit{Power of Two}}$ and team $\textbf{\textit{Three Hold Two}}$ won the champion for Tsinghua University in 2018 and 2019. In 2020, team $\textbf{\textit{Inverted Cross}}$ from Peking University won the champion. In 2021, there are around $700$ teams including $\textbf{the defending champion}$ participating in the contest. We are so excited to see who will win this year!

Although we can't gather in Nanjing this time due to the pandemic, we should still be grateful for the hard work done by all staff and volunteers for this contest. Thank you all for your great contribution to this contest!

In the 2018 contest, problem K, $\textbf{\textit{Kangaroo Puzzle}}$, requires the contestants to construct an operation sequence for the game:

> The puzzle is a grid with $n$ rows and $m$ columns ($1 \le n, m \le 20$) and there are some (at least $2$) kangaroos standing in the puzzle. The player's goal is to control them to get together. There are some walls in some cells and the kangaroos cannot enter the cells with walls. The other cells are empty. The kangaroos can move from an empty cell to an adjacent empty cell in four directions: up, down, left, and right.
>
> There is exactly one kangaroo in every empty cell in the beginning and the player can control the kangaroos by pressing the button U, D, L, R on the keyboard. The kangaroos will move simultaneously according to the button you press.
>
> The contestant needs to construct an operating sequence of at most $5 \times 10^4$ steps consisting of U, D, L, R only to achieve the goal.

In the 2020 contest, problem A, $\textbf{\textit{Ah, It's Yesterday Once More}}$, requires the contestants to construct an input map to hack the following code of the problem described before:

```cpp
#include <bits/stdc++.h>
using namespace std;
string s = "UDLR";
int main()
{
  srand(time(NULL));
  for (int i = 1; i <= 50000; i++) putchar(s[rand() % 4]);
  return 0;
}
```

Now in the 2021 contest, Paimon prepares another version of the problem for you. You are given a grid with $n$ rows and $n$ columns ($2 \leq n \leq 500$). All cells are empty and there is one kangaroo standing in each cell.

Similarly, you can control the kangaroos by pressing the button U, D, L, R on the keyboard. The kangaroos will move simultaneously according to the button you press. Specifically, for any kangaroo located in the cell on the $i$-th row and the $j$-th column, indicated by $(i,j)$:

- Button U: it will move to $(i-1,j)$ if $i>1$. Otherwise, it will stay in the same grid.
- Button D: it will move to $(i+1,j)$ if $i<n$. Otherwise, it will stay in the same grid.
- Button L: it will move to $(i,j-1)$ if $j>1$. Otherwise, it will stay in the same grid.
- Button R: it will move to $(i,j+1)$ if $j<n$. Otherwise, it will stay in the same grid.

You need to construct an operating sequence consisting only of characters `U`, `D`, `L`, and `R`. After applying it, you must make sure every kangaroo will gather at the specific cell $(a,b)$. The length of the operating sequence cannot exceed $3(n-1)$.

inputFormat:
There is only one test case in each test file.

The first and only line of the input contains three integers $n$, $a$, $b$ ($2 \leq n \leq 500$, $ 1 \leq a,b \leq n$) indicating the size of the grid and the target cell.

outputFormat: Output a string consisting only of characters `U`, `D`, `L` and `R` in one line. And its length mustn't exceed $3(n-1)$. It can be proved that the answer always exists.

translation:
有一张 $n\times n$ 的网格图，每个格子上都有一只袋鼠。对于一只在 $(i,j)$ 的袋鼠，有下面四个按钮：

- 按钮 `U`：如果 $i>1$，移动到 $(i-1,j)$，否则，原地不动；
- 按钮 `D`：如果 $i<n$，移动到 $(i+1,j)$，否则，原地不动；
- 按钮 `L`：如果 $j>1$，移动到 $(i,j-1)$，否则，原地不动；
- 按钮 `R`：如果 $j<n$，移动到 $(i,j+1)$，否则，原地不动。

每次按下按钮，都会对**所有的**袋鼠生效。请输出一种使得所有袋鼠最终都在 $(a,b)$ 的操作序列，并且序列的长度小于等于 $3\times(n-1)$。

samples:
3 3 3
RRDD

samples:
4 3 2
DLDLDLUR


title: [ICPC2021 Nanjing R] Puzzle in Inazuma

description:
Every traveler knows that they'll be rewarded with a treasure box after solving the puzzles in Inazuma, but few know that these puzzles are designed by Yae Miko, the Guuji of the Grand Narukami Shrine, to test whether the traveler is strong enough to save her friend Raiden Shogun and people of Inazuma.

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

After a traveler passes the test Yae will have to reset the puzzles to the initial state. But this time she has some troubles and even doubts that whether some of them are already broken.

Yae's puzzle can be considered as a weighted undirected complete graph $G$ before resetting. We also denote the initial state as another weighted undirected complete graph $H$. Both $G$ and $H$ have exactly $n$ vertices, and these vertices are labeled from $1$ to $n$.

To reset graph $G$ to $H$ Yae can perform the following operation any number of times:
- First select four distinct vertices $a$, $b$, $c$, $d$ and an integer $x$. Note that she can select a different set of $a$, $b$, $c$, $d$ and $x$ each time.
- Let $(i, j)$ be the edge between vertices $i$ and $j$. Increase the weight of $(a, b)$, $(a, c)$ and $(a, d)$ by $x$ and also decrease the weight of $(b, c)$, $(b, d)$ and $(c, d)$ by $x$.

Please help Yae determine whether she can change graph $G$ to graph $H$. If yes you also shall tell her the detailed steps.

inputFormat:
There is only one test case in each test file.

The first line of the input contains an integer $n$ ($4 \leq n \leq 100$) indicating the number of vertices in graph $G$ and $H$.

For the following $(n - 1)$ lines, the $i$-th line contains $(n - i)$ integers $w_{i, i + 1}, w_{i, i + 2}, \cdots, w_{i, n}$ ($-100 \le w_{i, j} \le 100$) where $w_{i, j}$ indicates the weight of the edge connecting vertices $i$ and $j$ in graph $G$.

For the following $(n - 1)$ lines, the $i$-th line contains $(n - i)$ integers $v_{i, i + 1}, v_{i, i + 2}, \cdots, v_{i, n}$ ($-100 \le v_{i, j} \le 100$) where $v_{i, j}$ indicates the weight of the edge connecting vertices $i$ and $j$ in graph $H$.

outputFormat:
If Yae cannot change $G$ to $H$, output `-1`.

Otherwise first output an integer $m$ ($0 \le m \le 10^5$) in one line indicating the number of operations Yae needs.

For the following $m$ lines, output five integers $a_i$, $b_i$, $c_i$, $d_i$ and $x_i$ in the $i$-th line separated by a space, indicating that for the $i$-th operation Yae choose vertices $a_i$, $b_i$, $c_i$, $d_i$ and integer $x_i$. Note that $a_i$, $b_i$, $c_i$, $d_i$ must be distinct and $-10^9 \le x_i \le 10^9$.

It can be proved that if graph $G$ can be changed to graph $H$ there exists a solution with no more than $10^5$ operations.

Note that you don't have to minimize $m$. If there are multiple solutions, output any of them.

translation:
给定一个 $n$ 个点的带权完全图 $G$，现在你可以对这个图做至多 $10^5$ 次如下操作，使其变成另一张带权完全图 $H$：
- 选取四个点 $a,b,c,d$ 与权值 $x$，使得边 $(a,b),(a,c),(a,d)$ 加上 $x$，边 $(b,c),(b,d),(c,d)$ 减去 $x$。

构造一组方案或判断无解。
$4\le n\le 100$，边权在 $-100\sim 100$ 之间。


title: [ICPC2021 Nanjing R] Klee in Solitary Confinement

description:
Since the traveler comes, People in Monstadt suddenly raise great interest in computer programming and algorithms, including Klee, the Spark Knight of the Knights of Favonius.

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

Being sent to solitary confinement by Jean again, Klee decides to spend time learning the famous Mo's algorithm, which can compute with a time complexity of $\mathcal{O}(n^{1.5})$ for some range query problem without modifications.

To check whether Klee has truly mastered the algorithm (or in fact making another bombs secretly), Jean gives her a problem of an integer sequence $a_1, a_2, \cdots, a_n$ along with some queries $[l_i, r_i]$ requiring her to find the mode number in the contiguous subsequence $a_{l_i}, a_{l_i + 1}, \cdots, a_{r_i}$. The mode number is the most common number (that is to say, the number which appears the maximum number of times) in the subsequence.

With the help of Mo's algorithm, Klee solves that problem without effort, but another problem comes into her mind. Given an integer sequence $a_1, a_2, \cdots, a_n$ of length $n$ and an integer $k$, you can perform the following operation at most once: Choose two integers $l$ and $r$ such that $1 \le l \le r \le n$ and add $k$ to every $a_i$ where $l \le i \le r$. Note that it is OK not to perform this operation. Compute the maximum occurrence of the mode number of the whole sequence if you choose to perform (or not perform) the operation optimally.

inputFormat:
There is only one test case in each test file.

The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 10^6$, $-10^6 \le k \le 10^6$) indicating the length of the sequence and the additive number.

The second line of the input contains $n$ integers $a_1, a_2, \cdots, a_n$ ($-10^6 \le a_i \le 10^6$) indicating the original sequence.

outputFormat: Output one line containing one integer indicating the maximum occurrence of the mode number of the whole sequence after performing (or not performing) the operation.

translation: 给定 $n,k$ 和一个长为 $n$ 的序列，你可以选择对区间 $[l, r]$ 的数整体加上 $k$，也可以不加。最大化众数出现次数并输出。

hint:
For the first sample test case, choose $l = 1$ and $r = 2$ and we'll result in the sequence $\{4, 4, 4, 4, 4\}$. The mode number is obviously $4$ which appears $5$ times.

For the second sample test case, choose $l = 4$ and $r = 6$ and we'll result in the sequence $\{3, 2, 3, 3, 3, 3, 3\}$. The mode number is $3$ which appears $6$ times.

For the fourth sample test case, choose not to perform the operation. The mode number is $1$ and $-2$ which both appear $3$ times.


title: [ICPC2021 Nanjing R] Paimon Sorting

description:
Paimon just invents a new sorting algorithm which looks much like $\textit{bubble sort}$, with a few differences. It accepts a $1$-indexed sequence $A$ of length $n$ and sorts it. Its pseudo-code is shown below.

```cpp
// The Sorting Algorithm
SORT(A)
  for i from 1 to n // n is the number of elements if A
    for j from 1 to n
      if a[i] < a[j] // a[i] is the i-th element in A
        Swap a[i] and a[j]
```

If you don't believe this piece of algorithm can sort a sequence it will also be your task to prove it. Anyway here comes the question:

Given an integer sequence $A = a_1, a_2, \cdots, a_n$ of length $n$, for each of its prefix $A_k$ of length $k$ (that is, for each $1 \le k \le n$, consider the subsequence $A_k = a_1, a_2, \cdots, a_k$), count the number of swaps performed if we call $\text{SORT}(A_k)$.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$) indicating the length of the sequence.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$) indicating the given sequence.

It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

outputFormat:
For each test case output one line containing $n$ integers $s_1, s_2, \cdots, s_n$ separated by a space, where $s_i$ is the number of swaps performed if we call $\text{SORT}(A_i)$.

Please, DO NOT output extra spaces at the end of each line or your solution may be considered incorrect!

translation:
给出一个排序算法（用伪代码表示）：

```cpp
// 排序算法
SORT(A)
  for i from 1 to n // n 是序列 A 的元素个数
    for j from 1 to n
      if a[i] < a[j] // a[i] 是序列 A 的第 i 个元素
        Swap a[i] and a[j]

```

请你算出对于一个序列 $A=a_1,a_2,\cdots,a_n$ 的所有前缀 $A_k=a_1,a_2,\cdots,a_k$（$1\le k\le n$），$\operatorname{SORT}(A_k)$ 中的交换（Swap）操作将会被执行几次。


title: [ICPC2021 Nanjing R] Paimon Segment Tree

description:
Paimon just learns the persistent segment tree and decides to practice immediately. Therefore, Lumine gives her an easy problem to start:

Given a sequence $a_1, a_2, \cdots, a_n$ of length $n$, Lumine will apply $m$ modifications to the sequence. In the $i$-th modification, indicated by three integers $l_i$, $r_i$ ($1 \le l_i \le r_i \le n$) and $x_i$, Lumine will change $a_k$ to $(a_k + x_i)$ for all $l_i \le k \le r_i$.

Let $a_{i, t}$ be the value of $a_i$ just after the $t$-th operation. This way we can keep track of all historial versions of $a_i$. Note that $a_{i,t}$ might be the same as $a_{i,t-1}$ if it hasn't been modified in the $t$-th modification. For completeness we also define $a_{i, 0}$ as the initial value of $a_i$.

After all modifications have been applied, Lumine will give Paimon $q$ queries about the sum of squares among the historical values. The $k$-th query is indicated by four integers $l_k$, $r_k$, $x_k$ and $y_k$ and requires Paimon to calculate

$$\sum\limits_{i=l_k}^{r_k}\sum\limits_{j=x_k}^{y_k} a_{i, j}^2$$

Please help Paimon compute the result for all queries. As the answer might be very large, please output the answer modulo $10^9 + 7$.

inputFormat:
There is only one test case in each test file.

The first line of the input contains three integers $n$, $m$ and $q$ ($1 \le n, m, q \le 5 \times 10^4$) indicating the length of the sequence, the number of modifications and the number of queries.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($|a_i| < 10^9 + 7$) indicating the initial sequence.

For the following $m$ lines, the $i$-th line contains three integers $l_i$, $r_i$ and $x_i$ ($1 \le l_i \le r_i \le n$, $|x_i| < 10^9 + 7$) indicating the $i$-th modification.

For the following $q$ lines, the $i$-th line contains four integers $l_i$, $r_i$, $x_i$ and $y_i$ ($1 \le l_i \le r_i \le n$, $0 \le x_i \le y_i \le m$) indicating the $i$-th query.

outputFormat: For each query output one line containing one integer indicating the answer modulo $10^9 + 7$.

translation:
## 题目描述

派蒙刚刚学习了可持久化线段树，她想马上练习一下。因此，荧决定给她出一道简单的问题：

给定数列$a_1, a_2, \cdots, a_n$，并进行$m$次操作。操作包含3个参数$l_i$, $r_i$ ($1 \le l_i \le r_i \le n$) 和 $x_i$，代表对该序列第$l_i$到第$r_i$个元素加上$x_i$。

记$a_{i, t}$为$t$次操作后$a_i$的值。注意若$a_i$未被修改，则$a_{i,t}$的值与$a_{i,t-1}$相同。定义$a_{i, 0}$是$a_i$的初始值。

完成所有操作后，荧进行$q$次询问，询问包含4个整数$l_k$, $r_k$, $x_k$ and $y_k$，派蒙需要回答

$$\sum\limits_{i=l_k}^{r_k}\sum\limits_{j=x_k}^{y_k} a_{i, j}^2$$

请将答案对$10^9 + 7$取模后输出。

## 输入格式
每个测试点含一组测试数据。

第一行3个整数$n$,$m$,$q$ ($1 \le n, m, q \le 5 \times 10^4$) 分别表示数列的长度，操作的次数和询问的次数。

第2行$n$个整数 $a_1, a_2, \cdots, a_n$ ($|a_i| < 10^9 + 7$) ，表示原始数列。

接下来$m$行每行3个整数 $l_i$, $r_i$ $x_i$ ($1 \le l_i \le r_i \le n$, $|x_i| < 10^9 + 7$)，表示区间加操作。

接下来$q$行每行包含四个整数 $l_i$, $r_i$, $x_i$  $y_i$ ($1 \le l_i \le r_i \le n$, $0 \le x_i \le y_i \le m$)，表示询问。

## 输出格式

对每个询问单起一行输出答案模$10^9 + 7$的结果。


title: [ICPC2021 Nanjing R] Paimon Polygon

description:
Paimon just puts $(n+1)$ distinct points on the plane, one of which is a special point $O=(0,0)$, and denote the group of remaining points as $\mathbb{S}$.

We call a point set $\mathbb{U}$ $\textit{strict convex set}$, if and only if $|\mathbb{U}| \ge 3$ and all the points from $\mathbb{U}$ lie exactly on the convex hull built from $\mathbb{U}$, with no three points lying on the same line.

You should divide $\mathbb{S}$ into two sets $\mathbb{A}$ and $\mathbb{B}$ so that:
- $\mathbb{A} \cap \mathbb{B}=\emptyset$.
- $\mathbb{A} \cup \mathbb{B}=\mathbb{S}$.
- $|\mathbb{A}| \ge 2, |\mathbb{B}| \ge 2$.
- The point set $\mathbb{A} \cup \{O\}$ is a $\textit{strict convex set}$, and denote its convex hull as $C_{\mathbb{A} \cup \{O\}}$.
- The point set $\mathbb{B} \cup \{O\}$ is a $\textit{strict convex set}$, and denote its convex hull as $C_{\mathbb{B} \cup \{O\}}$.
- The outlines(edges) of $C_{\mathbb{A} \cup \{O\}}$ and $C_{\mathbb{B} \cup \{O\}}$ only intersect at point $O$. That is, only one point $O$ satisfies that it lies both on the outlines of $C_{\mathbb{A} \cup \{O\}}$ and $C_{\mathbb{B} \cup \{O\}}$.

Please help Paimon to maximize the sum of the perimeters of these two convex hulls. That is, find a valid division $\mathbb{A}$ and $\mathbb{B}$ which maximizes $(L(C_{\mathbb{A} \cup \{O\}}) + L(C_{\mathbb{B} \cup \{O\}}))$, where $L(\text{polygon})$ means the perimeter of that polygon.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains one integer $n$ ($4 \le n \le 5 \times 10^5$) indicating the number of points in $\mathbb{S}$.

For the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$, $(x_i, y_i) \ne (0, 0)$) indicating the location of the $i$-th point in $\mathbb{S}$.

It's guaranteed that the points given in the same test case are pairwise different. However, there may be three points lying on the same line.

It's also guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

outputFormat:
For each test case output one line containing a number indicating the maximum total perimeter. If there does not exist a valid division output `0` instead.

Your answer will be accepted if the relative or absolute error is less than $10^{-6}$.

translation:
## 题目描述

派蒙在平面上放置了$n+1$个互异的点，其中有一特殊点$O=(0,0)$，并记其余点为$\mathbb{S}$。

我们称一个点集 $\mathbb{U}$ 为$\textit{strict convex set}$，当且仅当点集中点的个数大于等于3（$|\mathbb{U}| \ge 3$）且$\mathbb{U}$中的所有点位于$\mathbb{U}$构成的凸包上，且任意三点不共线。

你需要将$\mathbb{S}$划分为两个集合 $\mathbb{A}$ 和$\mathbb{B}$，使其满足
- $\mathbb{A} \cap \mathbb{B}=\emptyset$.
- $\mathbb{A} \cup \mathbb{B}=\mathbb{S}$.
- $|\mathbb{A}| \ge 2, |\mathbb{B}| \ge 2$.

- 点集 $\mathbb{A} \cup \{O\}$ 是 $\textit{strict convex set}$，并记它的凸包为$C_{\mathbb{A} \cup \{O\}}$。
- 点集 $\mathbb{B} \cup \{O\}$是 $\textit{strict convex set}$，并记它的凸包为 $C_{\mathbb{B} \cup \{O\}}$。
- $C_{\mathbb{A} \cup \{O\}}$和 $C_{\mathbb{B} \cup \{O\}}$ 的轮廓 仅在 $O$相交。 这也就是说，仅有点$O$既在$C_{\mathbb{A} \cup \{O\}}$的轮廓上，又在$C_{\mathbb{B} \cup \{O\}}$的轮廓上。

请协助派蒙计算出这两个凸包周长之和的最大值。
这也就是说，找到一个合法的划分方案$\mathbb{A}$ 和 $\mathbb{B}$，使得 $(L(C_{\mathbb{A} \cup \{O\}}) + L(C_{\mathbb{B} \cup \{O\}}))$最大，其中$L(\text{polygon})$代表多边形的周长。

## 输入格式

多组测试数据，第一行给出数据组数 $T$。

第一行给出一个整数 $n$ ($4 \le n \le 5 \times 10^5$) ，表示 $\mathbb{S}$ 中点的个数。

接下来$n$行，第$i$行 包含两个整数 $x_i$ 和 $y_i$ ($-10^9 \le x_i, y_i \le 10^9$, $(x_i, y_i) \ne (0, 0)$) 表示 $\mathbb{S}$ 中第 $i$个点的坐标。

保证同一组测试数据中的点互异，但可能存在三点共线。

保证 所有测试数据中$n$之和不超过 $10^6$.

## 输出格式

每组测试数据单起一行输出一个整数，表示两个凸包的周长之和的最大值。如不存在合法的划分方案，输出`0`。
与标准答案的相对或绝对误差小于 $10^{-6}$的答案会被视作正确答案。

hint:
A valid division (left) and an invalid division (right) of the first sample test case are shown below.

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


title: [ICPC2021 Nanjing R] Paimon's Tree

description:
Paimon has found a tree with $(n + 1)$ initially white vertices in her left pocket and decides to play with it. A tree with $(n + 1)$ nodes is an undirected connected graph with $n$ edges.

Paimon will give you an integer sequence $a_1, a_2, \cdots, a_n$ of length $n$. We first need to select a vertex in the tree and paint it black. Then we perform the following operation $n$ times.

During the $i$-th operation, we select a white vertex $x_i$ which is directly connected with a black vertex $y_i$ by an edge, set the weight of that edge to $a_i$ and also paint $x_i$ in black. After these $n$ operations we get a tree whose edges are all weighted.

What's the maximum length of the diameter of the weighted tree if we select the vertices optimally? The diameter of a weighted tree is the longest simple path in that tree. The length of a simple path is the sum of the weights of all edges in that path.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 5 \times 10^3$) indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 150$) indicating the length of the sequence.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$) indicating the sequence.

For the following $n$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n + 1$) indicating that there is an edge connecting vertex $u_i$ and $v_i$ in the tree.

It's guaranteed that there is at most $10$ test cases satisfying $n > 20$.

outputFormat: For each test case output one line containing one integer indicating the maximum length of the diameter of the tree.

translation:
# Paimon's Tree

## Translation

### 题目描述

派蒙在她的左口袋中找到了一颗有 $(n+1)$ 个白色节点的树。一颗有 $(n+1)$ 个节点的树是一个有 $n$ 条边的无向连通图。

派蒙会给你一个长度为 $n$ 的整数序列 $a_1,a_2,...,a_n$ 。我们首先需要选择这棵树中的一个节点并将它涂黑。接下来进行以下操作 $n$ 次。

> 在第 $i$ 次操作中，我们选择一个与一个黑色节点 $y_i$ 直连的白色节点 $x_i$ ，将这条边的权值设为 $a_i$ ，并且将节点 $x_i$ 涂黑。

进行上述的 $n$ 次操作后，我们会得到一棵每条边都有权值的树。

在最优的选择节点策略下，这颗树的直径最大是多少？一棵树的直径是这棵树中的最长简单路径的长度。一条简单路径的长度是这条路径中所有边的权值之和。

### 输入格式

一次运行将会给出多个测试数据。输入的第一行包含一个整数 $T$ ，表示测试数据的组数。

对于每个测试数据：

> 第一行包括一个整数 $n$ ，表示序列 $a$ 的长度。
>
> 第二行包括 $n$ 个整数 $a_1,a_2,...,a_n$ ，表示序列 $a$ 的内容。
>
> 在接下来的 $n$ 行中，第 $i$ 行包括两个整数 $u_i$ 与 $v_i$ ，表示在这棵树上 $u_i$ 与 $v_i$ 有一条连边。

### 输出格式

对于每个测试数据，输出一行，表示这棵树在最优操作下的直径长度。

### 数据范围

* $1\le T\le 5\times 10^3$
* $1\le n\le 150$
* $1\le a_i\le 10^9$
* $1\le u_i,v_i\le n+1$
* 保证每个样例中最多有 $10$ 组测试数据满足 $n>20$ 。

hint:
For the first sample test case, we select the vertices in the order of $1, 3, 4, 5, 2, 6$, resulting in the weighted tree of the following image. It's obvious that the longest simple path is of length $16$.

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


title: [ICPC2021 Nanjing R] Crystalfly

description:
Paimon is catching crystalflies on a tree, which are a special kind of butterflies in Teyvat. A tree is a connected graph consisting of $n$ vertices and $(n - 1)$ undirected edges.

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

There are initially $a_i$ crystalflies on the $i$-th vertex. When Paimon reaches a vertex, she can catch all the remaining crystalflies on the vertex immediately. However, the crystalflies are timid. When Paimon reaches a vertex, all the crystalflies on the adjacent vertices will be disturbed. For the $i$-th vertex, if the crystalflies on the vertex are disturbed for the first time at the beginning of the $t'$-th second, they will disappear at the end of the $(t' + t_{i})$-th second.

At the beginning of the $0$-th second, Paimon reaches vertex $1$ and stays there before the beginning of the $1$-st second. Then at the beginning of each following second, she can choose one of the two operations:
- Move to one of the adjacent vertices of her current vertex and stay there before the beginning of the next second (if the crystalflies in the destination will disappear at the end of that second she can still catch them).
- Stay still in her current vertex before the beginning of the next second.

Calculate the maximum number of crystalflies Paimon can catch in $10^{10^{10^{10^{10}}}}$ seconds.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$) indicating the number of vertices.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$) where $a_i$ is the number of crystalflies on the $i$-th vertex.

The third line contains $n$ integers $t_1, t_2, \cdots, t_n$ ($1 \le t_i \le 3$) where $t_i$ is the time before the crystalflies on the $i$-th vertex disappear after disturbed.

For the next $(n - 1)$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) indicating an edge connecting vertices $u_i$ and $v_i$ in the tree.

It's guaranteed that the sum of $n$ of all the test cases will not exceed $10^6$.

outputFormat: For each test case output one line containing one integer indicating the maximum number of crystalflies Paimon can catch.

translation: 给定一个 $n(1\le n\le10^5)$ 个节点的树，每个节点上有 $a_i$ 只晶蝶。派蒙最初在 $1$ 号节点，并获得 $1$ 号节点的所有晶蝶，接下来每一秒她可以移动到相邻的节点上并获得节点上的所有晶蝶，但是当她每到达一个节点 $u$ 后，对于每个与 $u$ 相邻的节点 $v$，节点 $v$ 上的的晶蝶会在 $t_v(1\le t_v\le3)$ 秒内消失，在 $t_v$ 秒后再到达节点 $v$ 将无法获得节点上的晶蝶。现在需要你求出最多可以获得的晶蝶数。

hint:
For the first sample test case, follow the strategy below.
- During the $0$-th second
  - Paimon arrives at vertex $1$;
  - Paimon catches $1$ crystalfly;
  - Crystalflies in vertices $2$ and $3$ are disturbed.
- During the $1$-st second
  - Paimon arrives at vertex $3$;
  - Paimon catches $100$ crystalflies.
- During the $2$-nd second
  - Paimon arrives at vertex $1$;
  - Crystalflies in vertex $2$ disappears.
- During the $3$-rd second
  - Paimon arrives at vertex $2$;
  - Crystalflies in vertices $4$ and $5$ are disturbed.
- During the $4$-th second
  - Paimon arrives at vertex $5$;
  - Paimon catches $10000$ crystalflies;
  - Crystalflies in vertex $4$ disappears.

For the second sample test case, the optimal strategy is the same with the first sample test case. Crystalflies in vertex $2$ are scheduled to disappear at the end of the $3$-rd (instead of the $2$-nd) second, allowing Paimon to catch them.


title: [ICPC2021 Nanjing R] Cloud Retainer's Game

description:
Cloud Retainer, the builder of the Dwelling in the clouds above Qingyun Peak, is very interested in mechanics. Although there is more than one month away from the Lantern Rite Festival in Liyue, she has already started the design of a gaming event for it.

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

The game is mainly about releasing pinballs to get a score as high as possible. It is played on the 2-dimensional plane with two horizontal straight lines $y = 0$ and $y = H$. Between the two lines, there are $n$ tiny wooden boards and $m$ coins, both can be regarded as single points. The $i$-th wooden board is located at $(x_i, y_i)$ while the $i$-th coin is located at $(x'_i, y'_i)$.

A pinball is released from $(10^{-9}, 10^{-9})$ by the player. Let $\overrightarrow{v} = (v_x, v_y)$ be the velocity of the ball (that is to say, if the ball is currently located at $(x, y)$ it will move to $(x + v_x\epsilon, y + v_y\epsilon)$ after $\epsilon$ seconds). Initially $\overrightarrow{v} = (1, 1)$.

When the ball hits a wooden board or one of the two horizontal straight lines, $v_y$ will be negated (that is, $v_y$ becomes $-v_y$) while $v_x$ remains unchanged. If the ball hits a coin, the player's score is increased by $1$ and the velocity of the ball remains unchanged.

To gain a higher score, the player can choose to remove any number of wooden boards before the pinball is released. It is also OK not to remove any wooden board. Cloud Retainer wants you to help her estimate the difficulty by computing the maximum score the player can get after $10^{10^{10^{10^{10}}}}$ seconds under the best strategy?

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains one integer $H$ ($2 \le H \le 10^9$).

The second line contains one integer $n$ ($1 \le n \le 10^5$) indicating the number of wooden boards.

For the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i \le 10^9$, $1 \le y_i < H$) indicating a wooden board located at $(x_i, y_i)$.

The following line contains one integer $m$ ($1 \le m \le 10^5$) indicating the number of coins.

For the following $m$ lines, the $i$-th line contains two integers $x'_i$ and $y'_i$ ($1 \le x'_i \le 10^9$, $1 \le y'_i < H$) indicating a coin located at $(x'_i, y'_i)$.

It's guaranteed that the given $(n + m)$ points in the same test case will be distinct. It's also guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $5 \times 10^5$.

outputFormat: For each test case output one line containing one integer indicating the maximum score the player can get after removing some (or not removing any) wooden boards.

translation:
参考题中所给图片，有上下两根直线，之间的距离为 $H$，还有 $n$ 个镜子，可以反射光线，也可以让其穿过，有 $m$ 个物品，一开始有一束从原点出发四十五度向右上方射出的一条光线，请你控制每个镜子的开关，求这条光线最多能经过几个物品。

——By @紊莫

hint:
The two sample test cases are shown below. Solid diamonds represent the remaining wooden boards, while hollow diamonds represent the removed wooden boards and round dots represent the coins.

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

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


title: [ICPC2021 Nanjing R] Xingqiu's Joke

description:
Once again, Xingqiu hides Chongyun's ice cream into a box with a strange lock. Liyue's summer has been always very hot and Chongyun suffers more because of his excessive yang (positive) energy, so he needs that ice cream desperately.

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

There are two integers $a$ and $b$ on the lock. Chongyun can perform the following three types of operations any number of times:
- Minus $1$ from both $a$ and $b$;
- Plus $1$ to both $a$ and $b$;
- Divide both $a$ and $b$ by one of their common $\textbf{prime}$ factor (that is to say, divide them by a $\textbf{prime}$ $g$ where $a$ and $b$ are both divisible by $g$).

The box will be unlocked if either $a$ or $b$ or both become $1$. To help Chongyun gets the ice cream back as quickly as possible, please tell him the minimum number of operations needed to unlock the box.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 300$) indicating the number of test cases. For each test case:

The first and only line contains two integers $a$ and $b$ ($1 \le a, b \le 10^9$, $a \ne b$).

outputFormat: For each test case output one line containing one integer indicating the minimum number of operations to make $a$ or $b$ or both equal $1$.

translation:
## 题目描述
有 $T$ 个盒子，每盒子上有一个锁，锁上有两个整数 $a$ 和 $b$。你可以对这个锁做若干次以下 3 种操作：

- $a$ 和 $b$ 分别减去 $1$
- $a$ 和 $b$ 分别增加 $1$
- $a$ 和 $b$ 分别除以它们共同的素数因子

如果 $a$ 或 $b$ 或两者都变为 $1$，盒子就会解锁。请你编写一个程序，计算每个盒子的锁打开的最少步骤数量。

## 输入格式
第一行输入一个整数 $T(1≤T≤300)$。

接下来 $T$ 行，每行输入 $a$ 和 $b$，表示每个盒子的锁的信息。

## 输出格式

共输出 $T$ 行，每行输出对应盒子解锁的最少步骤。

hint:
For the first sample test case, the optimal way is $(4, 7) \rightarrow (3, 6) \rightarrow (1, 2)$.

For the second sample test case, the optimal way is to apply the first type of operation $7$ times.

For the third sample test case, the optimal way is $(32, 84) \rightarrow (16, 42) \rightarrow (15, 41) \rightarrow (14, 40) \rightarrow (13, 39) \rightarrow (1, 3)$.

For the fourth sample test case, the optimal way is $(11, 35) \rightarrow (12, 36) \rightarrow (6, 18) \rightarrow (2, 6) \rightarrow (1, 3)$.