title: 「SvR-1」Hack Function!

background:
**Problem Number:** $\textit{63}$

小 C 坐在 J-PSC2077 的赛场（题目可于下方「**题目附件**」处下载）上，他早已年逾七旬，但作为 Z 队选手还是成功参赛。

description:
此时的 J-PSC 终于改成了 CF 赛制，小 C 迅速地 AK 了 Day 1，他发现 T2 function 比较好 Hack，题目的人话翻译如下：

> 对于一个数 $A$，定义函数 $f(A)$ 如下：
>
> 1. 先把 $A$ 变成 $k$ 进制数 $B$。
> 2. 将 $A$ 替换为 $B$ 各位之和。
> 3. 返回执行第 1 步，直到 $B$ 是一位数为止。
> 4. 记 $x$ 表示 $A$ 此时的值（十进制）。
> 此时 $f(A) = x$，$f(A)$ 称作 $A$ 关于 $k$ 的**位和函数**。
>
> 给定 $k, l, r, p$，求出 $\sum_{i = l}^r f(i^i) \bmod p$ 的值。
>
> **特别地，当 $\sum_{i = l}^r f(i^i) = p$ 时，输出 $\texttt{perfect}$。**

小 C 迅速秒了该题，当他翻看别人的代码时，发现他们用的全是暴力枚举。（因为机子跑得飞快）

好不容易看到一个人，他的代码里竟然没有一个  $\texttt{perfect}$！但由于数据过弱，竟然让他 pp 了。

小 C 突然脑子一热，忘记了怎么构造 Hack 数据，所以他通过 Luogu 6.0 求助于你。

小 C 会告诉你 $k, p$ 的值，你需要构造一组 $l, r$，**使答案输出为 $\texttt{perfect}$**。

**若无法构造，输出两个 $\texttt{-1}$。**

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

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

接下来 $T$ 行，每行两个整数 $k,p$，含义如题所述。

outputFormat:
共 $T$ 行，对于每组数据，输出你构造的 $l,r$ 的值。

若有多组解，输出任意一组。

hint:
#### 样例 1 说明

- 对于数据 $1$，在 $k = 10$ 下，有 $f(2^2) = f(4) = 4$，$f(3^3) = f(27) = 9$，显然 $l = 2, r = 3$ 时原题应该输出 $\texttt{perfect}$。
- 对于数据 $2$，在 $k = 10$ 下，发现不可能满足要求。
- 对于数据 $3$，在 $k = 2$ 下，显然有 $f(1^1) = 1$，但该样例仅用于理解，根据数据规模与约定，我们保证 $k \geq 10$。

#### 数据规模与约定

$$
\newcommand{\arraystretch}{1.5}
\begin{array}{c|c|c|c}\hline\hline
\textbf{Subtask} & \textbf{说明} & \textbf{时限} & \textbf{分值} \\\hline
\textsf{1} & \text{无解} & 1\text{ s} & 3 \\\hline
\textsf{2} & \text{有解且\textbf{\textsf{存在}}一组解使 }1\le l\le r\le 10^5 & 1\text{ s} & 16 \\\hline
\textsf{3} & 1\le p\le 10^7 & 1\text{ s} & 34 \\\hline
\textsf{4} & \text{无特殊限制} & 1.5\text{ s} & 47 \\\hline\hline
\end{array}
$$

对于 $100\%$ 的数据，$10 \leq k \leq 10^3$，$1 \leq p \leq 10^8$，$1 \leq T \leq 10$。

保证时限在 std 用时的 $4$ 倍以上。

#### 评测说明

**本题开启 Special Judge 和捆绑测试。**

你需要保证 $l = r = -1$ 或 $1 \leq l \leq r \leq 10^{18}$ 且 $r - l \leq 10^{15}$，否则 SPJ 会将你的答案判为 $0$ 分。


title: [JOI Open 2021] Monster Game

type: P

background:
**本题为交互题。**

交互库与 spj 提供者 @[Liking_Cpp_In_Luogu](https://www.luogu.com.cn/user/705620)，感谢他的贡献！

请不要在代码中加入头文件 `monster.h`，在 Solve 函数前加上 `extern "C"`，开头加上 `extern "C" bool Query(int,int);` 即可。

# 警告：滥用本题评测将被封号！

description:
你圈养了 $N$ 只书虫，这 $N$ 只书虫编号为 $0 \sim N-1$，第 $i$ 只书虫的力量值为 $S_i$，满足 $S_i \in [0,N-1]$，且没有两只书虫的力量值是相等的。

你可以调用最多 $25000$ 次「打架事件」：

- 选择两只编号不相同的书虫 $a,b$：
	- 如果 $|S_a-S_b|=1$，则力量值小的书虫获胜；
    - 如果 $|S_a-S_b|>1$，则力量值大的书虫获胜。

请最小化调用「打架事件」的次数，你可以得到每次「打架事件」的结果，求所有书虫的力量值。

#### 交互格式

你的程序需要实现以下函数：

- `std::vector<int> Solve(int N)`
	- 对于每组数据，该函数只能被调用一次；
    - $N$：书虫的个数；
    - 该函数返回这 $N$ 只书虫的力量值数组 $T$；
    - 应该满足 $|T|=N$，否则您的程序将会被判为 `Wrong
Answer [1]`；
	- 应该满足 $T_i\in [0,N-1]$，否则您的程序将会被判为 `Wrong Answer [2]`；
    - 应该满足 $T_i=S_i$，否则您的程序将会被判为 `Wrong Answer [3]`。

你的程序可以调用以下函数：

- `bool Query(int a, int b)`
	- 你可以用这个函数调用「打架事件」；
    - $a,b$：书虫 $a$ 与书虫 $b$ 打架；
    - 如果 $a$ 获胜了，则返回 `true` 否则返回 `false`；
    - 应该满足 $a \in [0,N-1]\land b \in [0,N-1]$，否则您的程序将会被判为 `Wrong Answer [4]`；
    - 应该满足 $a \ne b$，否则您的程序将会被判为 `Wrong Answer [5]`；
    - 调用 `Query` 函数应该不超过 $25000$ 次。否则您的程序将会被判为 `Wrong Answer [6]`。

**特殊说明**

1. 您的程序可以调用其他标准库里的函数，或者使用全局变量；
2. 您的程序不得使用标准输入与标准输出。

inputFormat: 见「交互格式」。

outputFormat: 见「交互格式」。

hint:
#### 样例 1 解释

样例的交互过程：

|调用|返回|调用|返回|
|:-:|:-:|:-:|:-:|
|`Solve(5)`||||
|||`Query(1, 0)`|`false`|
|||`Query(4, 0)`|`false`|
|||`Query(1, 3)`|`true`|
||`[3, 1, 4, 2, 0]`||

#### 评测程序示例（样例）

评测程序示例以如下格式读取输⼊数据：

第一行：$N$
第二行：$S_0\ S_1\ \cdots\ S_{N-1}$

评测程序示例以如下格式读取输出数据：

当程序成功结束运行后，样例交互器会在标准输出中输出以下内容：

- 如果你的程序被判为正确，样例交互器会输出类似 `Accepted: 100` 的信息，其中 $100$ 为你的程序调用 `Query` 函数的次数；
- 如果你的程序被判为错误，样例交互器的输出内容已在「交互格式」中描述。

如果你的程序有多数错误，样例交互器只会判断其中的一种。

注意，交互器在某些数据中是自适应性的，也就是实际的交互器刚开始并没有一个确定的答案，而是会随着之前 `Query` 函数的调用逐渐做出响应，能保证至少有一组答案满足交互库做出的响应。

（本来原题有一个工具可以用来检测，但是找不到检测文件了，所以就咕掉了）

#### 数据规模与约定

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

- Subtask 1（10 pts）：$N \le 200$；
- Subtask 2（15 pts）：实际使用的交互库并不是自适应性的；
- Subtask 3（75 pts）：无特殊限制。

对于 $100\%$ 的数据：

- $4 \le N \le 1000$；
- $0 \le S_i \le N-1$；
- $S_i$ 保证互不相同。

对于 Subtask 3，特有一套评分标准：

如果你的程序通过了所有测试数据，那：

- 设 $X$ 为 Subtask 3 中你的程序对每个测试点调用的 `Query` 函数的次数的最大值；
- 你的分数将按照下面的过程计算：
	- 如果 $10^4<X \le 2.5 \times 10^4$，你将得到 $\left\lfloor75 \times \dfrac{2.5 \times 10^4-X}{1.5 \times 10^4}\right\rfloor$ 分；
    - 如果 $X \le 10^4$，你将得到 $75$ 分。

#### 说明

翻译自 [JOI 2020 / 2021 Open Contest C Monster Game](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2021/monster/2021-open-monster-statement-en.pdf)。


title: [COCI2015-2016#2] ARTUR

description: 有 $n$ 根棍子放在桌面上，求一个将棍子向桌子 $x$ 轴边缘移动的顺序，使棍子不发生碰撞（棍子向桌子边缘移动的速度相同）。

inputFormat:
第一行一个整数 $N$，表示棍子的总数。

接下来 $N$ 行，每行四个整数 $x1_i,y1_i,x2_i,y2_i$，表示一根棍子两端的坐标。

outputFormat: 一行 $n$ 个整数，表示合法的棍子移动顺序。

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

如图，另一种移动顺序是 `2 1 4 3`。

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

**【数据范围】**

对于 $40\%$ 的数据，$1\le N\le 10$；

对于 $60\%$ 的数据，$1\le N\le 300$；

对于 $100\%$ 的数据，$1\le N\le 5000$，$0\le x1,y1,x2,y2\le 10^4$。

**【说明】**

**本题数据点得分依原题，满分 100**。

题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #2](https://hsin.hr/coci/archive/2015_2016/contest2_tasks.pdf) **T3 ARTUR**。


title: [COCI2015-2016#2] SAVEZ

description:
有一个秘密行星 S4 居住着一种奇特的动物，它们的学名是 Loda。Savez 协会派出了一个由 Henrik 将军领导的小组来研究 Loda。Henrik 发现，Loda 有心灵传输的能力，他想在他的军队里雇佣他们。

一只 Loda 由 $N$ 个字符串组成，其中第 $i$ 个字符串记为 $x_i$。研究表明，Loda 能进行的心灵传输次数取决于组成它的字符串的一个特殊子序列（不一定是连续的）。字符串 $x_i$ 和 $x_j$ $(i<j)$ 都可以在该子序列中，当且仅当字符串 $x_j$ 以 $x_i$ 开头并以 $x_i$ 结尾。一只 Loda 可以进行的心灵传输次数是组成它的字符串的合法的最长子序列的长度，而你就需要确定它可以进行心灵传输的次数。

inputFormat:
第一行一个整数 $N$，表示组成某一只 Loda 的字符串总数。

接下来 $N$ 行，每行一个仅由大写英文字母构成的字符串 $x_i$，表示构成这一只 Loda 的字符串。

outputFormat: 一行一个整数，表示这只 Loda 可以进行心灵传输的次数。

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

一个最长的子序列为 `A AA AAA`。

**【样例 3 解释】**

子序列中的字符串允许相等，因此一个最长的子序列为 `A A A B B`。

**【数据范围】**

对于 $100\%$ 的数据，$1\le N \le 2\times 10^6，1\le |x_i| \le 2\times 10^6$，**保证 $\sum |x_i|\le10^6$**。

**【说明】**

**本题数据点得分依原题，满分 120**。

题目译自 [COCI 2015-2016](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #2](https://hsin.hr/coci/archive/2015_2016/contest2_tasks.pdf) **T4 SAVEZ**。


title: 「dWoi R2」Elevator / 电梯

background:
zszz，主角总会在学级裁判前乘电梯下去的过程中在内心写小作文。

但万一写不出来怎么办 Zzz ……

于是最原开始想数学题了 ……

description:
现有正整数 $a,b,c$ 满足 $\alpha$ 式：$\dfrac{1}{a}-\dfrac{1}{b}=\dfrac{1}{c}$，且 $\gcd (a,b,c)=1$。

现给定正整数 $N$，请编程求出满足 $c \leq N$ 的 $\alpha$ 式的个数以及满足以下条件的一个 $b$：

对所有 $c=N$ 得到的 $\alpha$ 式中使得 $a$ 最小。

inputFormat:
第一行一个正整数 $T$，表示询问总数。

接下来 $T$ 行，每行一个正整数，表示给定的 $N$。

outputFormat:
$T$ 行，每行一个正整数，表示满足条件的 $\alpha$ 式的个数。若存在解，则空一格后再输出一个满足条件的 $b$。

可以证明，$N>1$ 时一定有这样的 $b$。

hint:
#### 样例 #2 解释

第一个询问中对应的式子为：$\dfrac{1}{232} - \dfrac{1}{54056} = \dfrac{1}{233}$，故后一个输出为 $54056$。

第二个询问中对应的式子为：$\dfrac{1}{1620} - \dfrac{1}{8181} = \dfrac{1}{2020}$，故后一个输出为 $8181$。

而这两个 $\alpha$ 式的 $a$ 在所有 $c=N$ 的情况中是最小的。
- - -
#### 数据规模与约定

对于 $10\%$ 的数据，有 $N\leq 100$，$T\leq 10$。

对于 $30\%$ 的数据，有 $N\leq 10^3$，$T\leq 100$。

对于 $70\%$ 的数据，有 $N\leq 10^5$，$T\leq 10^4$。

对于 $100\%$ 的数据，有 $N\leq 2\times 10^6$，$T\leq 10^5$。
- - -
#### 关于 Special Judge

**本题采用 Special Judge。**

如果你第一问都答对了而第二问有答错的，那么你将得到 $30\%$ 的分数，如果你第一问有答错的而第二问都答对了，那么你将得到 $70\%$ 的分数，但是如果你第一问和第二问都有部分或者全部错误，那么你将被判作 WA；此外，如果你输出残缺或者过多，例如只回答第一问却不输出第二问的答案（$N=1$ 除外）或者 $N=1$ 后多输出了一个数，那么你将同样不会得到分数。


title: 「CGOI-1」收税

background:
~~签到题~~

由于举办选丑大赛消耗了太多钱财，ac 决定派出 Push_Y 去收税。

description:
丑国由 $n$ 座城市组成，编号 $1$ 的为首都。这 $n$ 座城市由 $n-1$ 条长度为 $1$ 的双向道路连接。从编号为 $x$ 的城市出发，往**远离**首都的方向（即往儿子节点走），距离不超过 $h$ 的就是这座城市要收税的范围。

第 $i$ 座城市将要上缴 $a_i$ **元**的所得税。但由于收税官 Push_Y 很喜欢异或，因此每座城市最终上缴的所得税将是在其收税范围内每座城市**应缴税额**的异或和。

Push_Y 将向你提出 $m$ 个询问，他将问你城市 $x$ 在收税距离为 $h$ 时将收到多少**千元**的所得税。

**简化版题意：**

给定一棵 $n$ 个点的树，根节点为 $1$ 号点，第 $i$ 个点的点权为 $a_i$，$dep_u$ 表示 $u$ 点的深度，根节点的深度为 $1$，$q$ 次询问，每次给定两个整数 $x,h$，表示询问 $\bigoplus_{u\in son(x)\land dep_u-dep_x\le h}a_i$ 除以 $1000$ 后的值。

其中 $\bigoplus_{i=1}^ni$ 表示 $1\operatorname{xor} 2\operatorname{xor}\cdots\operatorname{xor} n$。

此处 $\land$ 是“且”，$\operatorname{xor}$ 是异或。

inputFormat:
第一行两个正整数 $n,m$，表示城市数和询问数。

第二行 $n$ 个正整数 $a_i$， 表示每座城市应缴的所得税额。

第三行 $n-1$ 个正整数，其中第 $i$ 个数 $f_i$ 表示城市 $i+1$ 与城市 $f_i$ 有一条路相连。

从第 $4$ 行开始 $m$ 行，每行两个正整数 $x,h$，表示一组询问。

outputFormat:
对于每组询问，输出一行，一个实数，表示这座城市收取的税额。

**答案保留三位小数。**


title: [JRKSJ R3] system

description:
定义对序列 $a$ 的一次操作为令 $b_i\gets a_{a_i}$，再令 $a_i\gets b_i$，其中 $i\in[1,n]$。

给你一个长为 $n$ 的序列 $a$，询问对 $a$ 进行 $k$ 次操作后的序列。

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

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

outputFormat: 一行共 $n$ 个整数，表示 $k$ 次操作后的序列 $a$。


title: 「JZOI-2」干大事

background:
团员们满脑子都是办周年庆，但小僖只想摸鱼。

于是小僖决定干一件大事（去摸一条大鱼）。

description:
小僖由于经常摸鱼，在摸鱼众中享有很高的人气。而今天小僖决定去鱼世界里最颓的树上直播。

这颗树非常颓，没有根，上面有 $n$ 个结点，每个结点从 $1,2,\dots,n$ 进行标号，还有 $n - 1$ 条边将它们连通。它会变换形态，边会移动、消失或生长。记 $k$ 为树中满足 $|u-v|=1$ 的边 $(u,v)$ 的数量，则该形态的价值为 $k \times c^k$ 。

小僖想要向咸鱼们介绍树的价值，他只想着摸鱼。所以他找到了你，要求你求出树所有不同形态的权值和，并将其对 $998244353$ 取模后输出。

**多组数据**。

inputFormat:
第一行，一个正整数 $T$，表示数据组数。
以下 $T$ 行，每行一个正整数 $n$ 和一个非负整数 $c$，表示一组数据。

outputFormat: $T$ 行，第 $i$ 行一个非负整数，表示第 $i$ 组数据的答案。


title: 「EVOI-RD1」摘叶子

description:
某日，小 A 和小 B 在一起开心地玩着游戏。

他们找了一棵以 $1$ 节点为根节点的树，很显然，作为一棵树，总有一个或好多个叶子节点。小 A 和小 B 玩的是回合制游戏。

每次小 A 或小 B 可以选择**任意数量**的叶子节点，将其从树中摘下（每次只能摘叶子节点，每次摘的数量不限制，但**不能不摘**，更不能摘的数量超过本来叶子节点的数量）。

很显然，把一些叶子摘下后，他们的父亲节点有可能会成为新的叶子节点，这时，这些新成为叶子节点的原父亲节点也变得可以被摘取了。

现在，小 A 先摘，小 B 再摘，往复循环。把 $1$ 号节点摘下的人获胜。我们知道，小 A 和小 B 总会按最优方式进行游戏，问谁会取得胜利。

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

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

每组数据的第二行一个正整数 $n$，表示这棵树有 $n$ 个节点。

每组数据的第三行，$n-1$ 个整数，代表从 $2$ 号节点到 $n$ 号节点的父亲节点编号。

outputFormat:
共 $T$ 行，每行一个整数 $1$ 或 $0$。

$1$ 代表小 A 会取得胜利，$0$ 代表小 B 会取得胜利。

hint:
本题数据随机，只要简单分析一下性质，就很好骗分，因此本题采用**捆绑测试**。

对于 $40\%$ 的数据：$1 \leq n \leq 100$。

对于 $100\%$ 的数据：$1 \leq n \leq 10^6$，$1 \leq T \leq 10$。

本题时空限制（尤其是空间）均非常宽松，不卡常，不毒瘤，请放心食用。


title: 「EVOI-RD1」无人机航拍

background: T 市举行活动需要拍摄高空俯瞰图，找来了一个无人机机队负责拍摄工作。 [一E孤行](https://www.luogu.com.cn/user/229919) 是队伍的队长，他根据广场的规模来安排无人机的位置。

description:
有一个广场，可以看做是一个 $n \times m$ 的矩形；一E孤行 一共有 $s$ 架无人机，每架无人机的拍摄范围也可以看做是一个矩形，无人机机队的拍摄范围为所有无人机拍摄范围的并。

一E孤行 负责安排无人机的位置，而总负责人 WuuTue 要验收~~她~~他的方案。WuuTue 的验收方法是列举出 $L$ 个重要的区域，每个重要区域也是一个矩形。 一E孤行 方案的优秀程度取决于有多少个重要区域完全在无人机机队的拍摄范围中。

因此，对于每一个重要区域， 一E孤行 想知道它是否完全在无人机机队的拍摄范围中。

inputFormat:
第一行，用空格隔开的两个整数 $n$ 和 $m$，用来描述广场的大小。

第二行，一个整数 $s$，表示无人机队伍中无人机的总数量。

第三行到第 $s+2$ 行，每行四个用空格隔开的整数，$a_1,b_1,a_2,b_2$，用来描述一架无人机的拍摄范围。其中 $a_1,b_1$ 表示矩形的左下角坐标，$a_2,b_2$ 表示右上角的坐标。

第 $s+3$ 行，一个整数 $L$，表示活动总负责人列出的重要区域的数量 $L$。

最后 $L$ 行，每行四个用空格隔开的整数 $r_1,c_1,r_2,c_2$，用来描述一个重要区域。其中 $r_1,c_1$ 表示矩形区域左下角坐标，$r_2,c_2$ 表示右上角坐标。

outputFormat: 输出 $L$ 行，对于每个重要区域，如果完全在机队的拍摄范围内就输出 `Yes`，否则出 `No`。每个答案占一行。

hint:
**样例说明**

如下图所示，区域 $A,B,C$ 分别是某某安排的无人机能够覆盖的范围，区域 $D,E$ 是 WuuTue 要验收时列举的重点区域，区域 $D$ 能够被完全覆盖，区域 $E$ 不能被全部覆盖。

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

**数据规模与约定**

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

对于 $40\%$ 的数据：$1 \le n \le 1000$，$1 \le s \le 100$ 。
对于 $100\%$ 的数据：

- $1 \le n, m \le 3 \times 10^{3}$。
- $1 \le s,L \le 10^6$。
- $1 \le x_1 < x_2 \le n$。
- $1 \le r_1 < r_2 \le n$。
- $1 \le y_1 < y_2 \le m$。
- $1 \le c_1 < c_2 \le m$。


title: [CCO2021] Swap Swap Sort

description:
你有一个长度为 $n$ 的序列，每项都是不超过 $k$ 的正整数。

你的朋友发明了一个排序算法，可以根据一个 $1 \sim k$ 的排列对序列进行排序，排序后序列中任意两个不相等的数的相对位置与排列中的相对位置相同。他的算法只使用了邻项交换的操作，且总是保证操作次数最少。为了方便描述，他将这个 $1 \sim k$ 的排列称为目标排列。

例如，序列为 $[1, 4, 2, 1, 2]$，目标排列为 $[4, 1, 2, 3]$，排序后为 $[4, 1, 1, 2, 2]$。

你对你朋友的排序算法在目标排列不同时执行 swap 的次数很感兴趣。为了研究其中的规律，你一开始将目标排列设置为 $1 \sim k$，并以此进行 $q$ 次操作，每次操作交换目标排列中相邻的两个数的位置。每次交换后，你想知道如果用他的排序算法对原序列进行排序会执行 swap 的次数。

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

第二行，$n$ 个正整数 $a_1, a_2, \cdots, a_n$，表示原序列。

接下来 $q$ 行，每行一个正整数 $b$，表示交换目标排列中的第 $b$ 和第 $b + 1$ 个数。

outputFormat: 对于每次询问，输出一个整数，表示所求的值。

hint:
#### 数据范围
**由于官方数据包过大，本题只节选了官方数据的 $\frac{20}{27}$。**

对于 $\frac{4}{27}$ 的数据，$1 \leq n, q \leq 5 \times 10^3$；

对于另外 $\frac{4}{27}$ 的数据，$1 \leq q \leq 100$；

对于另外 $\frac{7}{54}$ 的数据，$1 \leq k \leq 500$；

对于 $100\%$ 的数据，$1 \leq n, k \leq 10^5$，$1 \leq q \leq 10^6$，$1 \leq a_i \leq k$，$1 \leq b < k$。
#### 题目来源
[CCO2021](https://cemc.math.uwaterloo.ca/contests/computing/2021/index.html) D1T1


title: [CCO2021] Weird Numeral System

description:
Alice 正在思考一个关于 $k$ 进制整数的问题。

普通的 $k$ 进制可以将整数 $n$ 表示为 $d_{m - 1} d_{m - 2} \cdots d_0$，且满足：

1. $0 \leq d_i < k$；
2. $n = \displaystyle\sum_{i = 0}^{m - 1} d_i k^i$。

然而，普通的 $k$ 进制整数对于 Alice 来说太简单了，Alice 更喜欢奇怪的 $k$ 进制整数。它与普通 $k$ 进制整数的差别仅仅在于将 $0 \leq d_i < k$ 换成了 $d_i \in a$，其中 $a$ 为一个长为 $D$ 的数列。

现在有一组固定的 $a_1, a_2, \cdots, a_D$，Alice 想要将 $q$ 个十进制整数 $n_1, n_2, \cdots, n_q$ 全部转化为奇怪的 $k$ 进制整数，这种问题显然更适合写程序来解决。

inputFormat:
第一行，四个整数 $k, q, D, M$；

第二行，$D$ 个整数 $a_1, a_2, \cdots, a_D$；

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

outputFormat: $q$ 行，第 $i$ 行表示 $n_i$ 转化后的结果，按幂次从高到低的顺序输出每一位，两个位之间用单个空格间隔。当 $a_i$ 中包含 $0$ 时，你转化的结果可以包含前导零，但最好不要太多；当 $n_i = 0$ 时，你转化的结果也不能为空。如果有多种方案可以随便输出一种，如果无法转化输出 `IMPOSSIBLE`。

hint:
**本题由 @[Leasier](https://www.luogu.com.cn/user/201007) 提供 SPJ。**
#### 数据范围
对于 $100\%$ 的数据，$2 \leq k \leq 10^6$，$1 \leq q \leq 5$，$1 \leq D \leq 801$，$1 \leq M \leq 400$，$-M \leq a_i \leq M$，$-10^{18} \leq n_i \leq 10^{18}$。
#### 题目来源
[CCO2021](https://cemc.math.uwaterloo.ca/contests/computing/2021/index.html) D1T2


title: [CCO2021] Through Another Maze Darkly

background: **警告：滥用本题评测将被封号！**

description:
黑暗迷宫是一个树形结构，有 $n$ 个房间和 $n - 1$ 个走廊，房间编号 $1, 2, \cdots, n$。

黑暗迷宫里面漆黑一片，你看不见自己在哪里。为了辨别方向，每个房间有一个激光指示器，初始指向连接这个房间的某一个走廊。你重复执行如下策略行动：

- 将当前房间的激光指示器按顺时针方向旋转到下一个走廊
- 沿着激光指示器指向的走廊走到另一个房间

你打算从编号为 $1$ 的房间开始，将这个策略重复执行 $k$ 次，想知道自己会到达哪个房间。你觉得这个问题太简单了，于是进行了 $q$ 次询问。每次询问是相互独立的，即激光指示器每次都会回到初始状态。

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

接下来 $n$ 行，第 $i$ 行描述第 $i$ 个房间。首先，一个整数 $k$ 表示房间 $i$ 连接的走廊数量，接下来 $k$ 个整数 $c_1, c_2, \cdots, c_k$，表示按顺时针顺序每个走廊另一头的房间编号。第 $i$ 个房间的激光指示器初始指向通往房间 $c_1$ 的走廊。

接下来 $q$ 行，每行一个正整数 $k$。

outputFormat: 对于每组询问，输出一行，表示所求的值。

hint:
#### 样例 #1 解释
初始激光指示器的指向如图：

![](https://cdn.luogu.com.cn/upload/image_hosting/2k48xyl0.png)
#### 数据范围
对于 $\frac{7}{45}$ 的数据，第 $i$ 个房间连接第 $i - 1$ 和第 $i + 1$ 个房间（如果这两个房间存在）；

对于另 $\frac{14}{45}$ 的数据，$2 \leq n \leq 2 \times 10^3$，$1 \leq q \leq 2 \times 10^3$；

对于另 $\frac{4}{15}$ 的数据，$q = 1$；

对于 $100\%$ 的数据，$2 \leq n \leq 8 \times 10^5$，$1 \leq q \leq 8 \times 10^5$，$1 \leq k \leq 10^{15}$，保证数据给出的是**一棵树**。
#### 题目来源
[CCO2021](https://cemc.math.uwaterloo.ca/contests/computing/2021/index.html) D1T3


title: 『JROI-3』田径

background: 你准备玩起 MC。

description:
你需要用栅栏框住一个长方形区域，假设这个长方形区域大小为 $a \times b$ 个像素格，则需要长为 $a+1$，宽为 $b+1$ 规模的栅栏框住这个区域。

现在你发现他的羊和牛需要**恰好** $n$ 个像素格才够生存，而你的背包里有 $m$ 个栅栏，你想知道，你用你所拥有的的栅栏是否能框出 $n$ 个像素格？

不需要用光所有栅栏，只要框出区域大小为 $n$ 个像素格的长方形即可。

注意，上面的 $a,b,n,m$ 都应是整数。

inputFormat:
第一行一个整数 $T$，表示测试组数。

接下来 $T$ 行，一行两个整数 $n,m$，同题意。

outputFormat: 一行一个字符串，如果可行输出 `Good`，如果不可行输出 `Miss`。

hint:
#### 样例 1 解释

第一组数据：

实测可证，无法用 $1$ 个栅栏围出 $4$ 个像素格。

第二组数据：

可以考虑围出如下 $4=1 \times 4$ 的像素格。

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

用下方的方式只需要用 $14$ 个栅栏即可。

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

栅栏宽为 $1+1=2$，长为 $4+1=5$，$(2+5) \times 2=14$。

#### 数据规模与约定

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

- Subtask 1（30 pts）：$1\le n,m \le 10^4$，$T \leq 10^3$；
- Subtask 2（70 pts）：$1\le n,m \le 10^{8}$，$T \leq 10^3$。

----
在本题中栅栏是**抽象化**的而非具象化的，即栅栏将会**退化成一个点而非一个方格**，也就是我们可以通过**求周长的方式**求出一个栅栏框所需消耗的栅栏（如果不理解可以看看样例 1 解释）。


title: 「Stoi2033」园游会

background:
> 我顶着大太阳 只想为你撑伞
> 你靠在我肩膀 深呼吸怕遗忘
> 因为捞鱼的蠢游戏我们开始交谈
> 多希望话题不断园游会永不打烊
> 气球在我手上 我牵着你瞎逛
> 有话想对你讲 你眼睛却装忙
> 鸡蛋糕跟你嘴角果酱我都想要尝
> 园游会影片在播放 这个世界约好一起逛
> ——《园游会》

description:
设 $F(x)=(x+1)\bmod 3-1$，给定 $n$，求：

$$\sum_{l=0}^n \sum_{r=l}^n F\left(C_{r}^{l}\right)$$

对 $1732073999$ 取模。其中 $C_{r}^{l}$ 为组合数，具体地，

$$C_{r}^{l}=\dfrac{r!}{l!(r-l)!}$$

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

第一行两个正整数 $t,maxn$，表示询问组数与询问的最大可能值。

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

outputFormat: 共 $t$ 行，第 $i$ 行一个整数，为第 $i$ 次询问的答案对 $1\ 732\ 073\ 999$ 取模的结果。


title: 「MCOI-06」Eert Tuc Knil

description:
给定一颗 $n$ 个节点有根树，第 $i$ 节点权值为 $a_i$。

在这个树上支持一种询问：

 - 给定节点 $u$ 和参数 $x$，**假如** 所有节点点权加 $x$，**在这种情况下，求：** 对于所有完全在 $u$ 子树内并包含 $u$ 的连通点集，权值之和最大可能为多少？

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

第二行 $n-1$ 个正整数 $f_2,f_3,\dots,f_n$，依次为 $2,3,\dots,n$ 的父亲节点编号，其中保证 $1\le f_i<i$。

第三行 $n$ 个整数 $a_1,a_2,\dots,a_n$，依次为 $1,2,\dots,n$ 点权。

接下来 $m$ 行，每行一个正整数 $u$ 和一个整数 $x$，代表一组询问，其中保证 $1\le u\le n$。

outputFormat: 输出 $m$ 行，每行一个整数，为对应询问的答案。

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

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

 - Subtask 1（5 pts）：$n,m\le 1000$。
 - Subtask 2（10 pts）：$n,m\le 10^5$ 并且 $|a_i|,|x|\le 50$。
 - Subtask 3（15 pts）：$n\le 1000$。
 - Subtask 4（47 pts）：$n,m\le 10^5$。
 - Subtask 5（23 pts）：无特殊限制。

对于所有数据，$1\le n,m\le 10^6$，$|a_i|,|x|\le 10^8$，保证 $1\le u\le n$。


title: 「dWoi R2」FFT / 狒狒贴

background: 狱原权太正在尝试学习 FFT ……

description:
给定一个长度为 $2^n$ 的非负整数序列 $a_0,a_1,\cdots,a_{2^n-1}$，请计算序列 $A=\text{DFT}^k(a)$。

其中 $\text{DFT}(b)_i$ 定义为：

$$\text{DFT}(b)_i=\sum_{j=0}^{2^n-1}b_j\omega^{ij}\mod{998244353}$$
$$\omega\equiv3^{\frac{998244352}{2^n}}\pmod{998244353}$$

inputFormat:
第一行两个非负整数 $n,k$。

接下来一行 $2^n$ 个非负整数 $a_0,a_1,\cdots,a_{2^n-1}$。

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

 - Subtask 1（10 pts）：$n\le 11$ 且 $k\le 10$；
 - Subtask 2（10 pts）：$k\le 10$；
 - Subtask 3（20 pts）：$n\le 5$；
 - Subtask 4（30 pts）：$n\le 11$；
 - Subtask 5（30 pts）：无额外限制。

对于所有数据，$1\le n\le 17$，$1\le k\le10^{18}$，$0\le a_i\le 998244353$。


title: 〈 TREEのOI 2022 Spring 〉Absolutely Simple Game

background: rin 和 len 在玩一个绝对简单的游戏，pcq 为裁判。

description:
初始时给定范围 $[l,r]=[1,n]$，pcq 从中均匀随机选出一个自然数 $t$，之后 rin 和 len 两人轮流进行操作，rin 先行。

每次操作方猜测一个整数 $x\in[l,r]$，若 $x=t$，则游戏结束，该方负；若 $x<t$，则调整范围 $[l,r]$ 为 $[x+1,r]$；若 $x>t$，则调整范围 $[l,r]$ 为 $[l,x-1]$。

rin 和 len 两人均充分了解规则且无比可爱聪明（都会最大化自己的胜率），过程中谁都知道场上除了 $t$ 以外的一切信息，求 rin 的胜率。

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

outputFormat: 一行一个整数，表示 rin 的胜率，按分数 $\bmod~998244353$ 输出。


title: [CCO2021] Travelling Merchant

description:
一个国家有 $n$ 个城市和 $m$ 条单向道路，一个旅行商在这些城市之间旅行。

第 $i$ 条道路从城市 $a_i$ 到城市 $b_i$，只有当他的资产不少于 $r_i$ 元才可以走这条道路，走过这条道路之后他的资产会增加 $p_i$ 元。

他希望自己可以永远不停的游走下去，于是他想知道从任意一个城市出发至少需要多少元初始资产。

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

接下来 $m$ 行，第 $i$ 行有四个整数 $a_i, b_i, r_i, p_i$。

outputFormat: 一行，$n$ 个整数，若第 $i$ 个城市无解，第 $i$ 个整数为 $-1$；否则，为至少需要的初始资产（单位为元）。

hint:
#### 样例 #1 解释
以第 $2$ 座城市为例：从第 $2$ 座城市出发，初始资产 $3$ 元，则可以在第 $2, 1, 3$ 三座城市无限绕圈。
#### 数据范围
对于 $\frac{2}{7}$ 的数据，$2 \leq n, m \leq 2 \times 10^3$；

对于另 $\frac{15}{49}$ 的数据，$p_i = 0$；

对于 $100\%$ 的数据，$2 \leq n, m \leq 2 \times 10^5$，$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$0 \leq r_i, p_i \leq 10^9$，**保证没有自环但可能有重边**。
#### 题目来源
[CCO2021](https://cemc.math.uwaterloo.ca/contests/computing/2021/index.html) D2T1


title: [CCO2021] Bread First Search

description:
这个国家有 $n$ 个城市和 $m$ 条双向道路。

有一个人要游览这个国家，但他很讲究。他要求游览线路必须是一个 BFS（Bread First Search，面包优先搜索）序，必须访问每个城市各一次，且满足以下条件：

- 首个城市可以任选；
- 除了首个城市外，每个城市被访问前至少有一个相邻城市已经被访问过；
- 每个城市与首个城市的距离单调不降。其中两个城市的距离定义为它们路径边数的最小值。

这个人还有强迫症，一定要按照编号 $1 \sim n$ 的顺序将每个城市访问一次。为了使这条游览线路符合上述所有要求，政府需要新修若干条道路。请问最少需要新修多少条道路？

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

接下来 $m$ 行，每行两个整数 $a, b$，表示这个国家的一条双向道路。

outputFormat: 一行，一个整数，表示所求的值。

hint:
#### 样例 #2 解释
一种符合要求的方式是，在城市 $1, 2$ 之间修一条路，在城市 $1, 4$ 之间修一条路。此时城市 $1$ 与城市 $1 \sim 6$ 的距离分别是 $0, 1, 1, 1, 2, 2$。
#### 数据范围
对于 $\frac{11}{32}$ 的数据，$1 \leq n \leq 200$；

对于 $\frac{5}{8}$ 的数据，$1 \leq n \leq 5 \times 10^3$；

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$0 \leq m \leq \min(2 \times 10^5, \frac{n(n - 1)}{2})$，$1 \leq a, b \leq n$，**保证没有重边和自环**。
#### 题目来源
[CCO2021](https://cemc.math.uwaterloo.ca/contests/computing/2021/index.html) D2T2


title: [CCO2021] Loop Town

description:
循环镇有 $n$ 个公民、$n$ 座房子、$n$ 个办公室。每个公民住在一座房子中，并在一个办公室工作。没有两个公民住在同一座房子，也没有两个公民在同一个办公室工作。

循环镇是一个环形城市，绕城一圈路程为 $l$。循环镇的 $2n$ 栋建筑（房子和办公室）都在环上的整点上，其位置可以用 $[0, l - 1]$ 范围内的整数来描述，且这 $2n$ 栋建筑位置是互不相同的。

每天早上，每个公民同时从自己的房子出发，沿着环路走到自己的办公室。公民到达办公室之后不会立刻进去工作，而是要等到所有公民都到达办公室之后才会同时进入办公室开始工作。

一场疫情的到来打破了常规，领导人要求每个公民保持社交距离。围绕城市的环状道路很窄，两个公民的线路存在相互交叉时会很不方便（必须一个人暂时离开道路才能使另一个人通过），而三个人或以上禁止同时走到同一个地方。

领导人可以给每个公民规定上班路线，即走城市环路的哪一边。领导人的目标是任意两个公民线路交叉的总次数最小，求这个最小值。

inputFormat:
第一行，两个整数 $n, l$；

接下来 $n$ 行，每行两个整数 $a_i, b_i$，表示第 $i$ 个公民的房子和办公室的位置。

outputFormat: 一行，一个整数，表示所求的值。

hint:
#### 数据范围
对于 $\frac{4}{13}$ 的数据，$1 \leq n \leq 5 \times 10^3$；

对于 $\frac{8}{13}$ 的数据，$1 \leq n \leq 10^5$；

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$1 \leq l \leq 10^9$，$0 \leq a_i, b_i < l$，**保证 $a_i, b_i$ 互不相同**。
#### 题目来源
[CCO2021](https://cemc.math.uwaterloo.ca/contests/computing/2021/index.html) D2T3


title: [ONTAK2010] Peaks 加强版

background: 原题链接：[P4197 Peaks](https://www.luogu.com.cn/problem/P4197)

description:
给定一张 $n$ 个点、$m$ 条边的无向图，第 $i$ 个点的权值为 $a_i$，边有边权。

有 $q$ 组询问，每组询问给定三个整数 $u, x, k$，求从 $u$ 开始只经过权值 $\leq x$ 的边所能到达的权值第 $k$ 大的点的权值，如果不存在输出 $-1$。

**本题强制在线。即：每次查询输入的是 $u', x', k'$，则 $u = (u' \operatorname{xor} \text{lastans}) \bmod n + 1$，$k$ 的解密方式与之相同，$x = x' \operatorname{xor} \text{lastans}$**。

inputFormat:
第一行，三个整数 $n, m, q$；

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$；

接下来 $m$ 行，每行三个整数 $s, t, w$，表示一条边的两个端点和权值；

接下来 $q$ 行，每行三个整数 $u', x', k'$。

**注意：处理第一组数据和无解时的 $\text{lastans} = 0$。**

outputFormat: 对于每组询问，输出一行，一个整数，表示所求的值。


title: 「SvR-1」Five of Pentacles

background: UPD on 2023.2.5 by 出题人： 原题强制在线方式有问题，会使得一些依赖强制在线的方式通过，这并不是正解~~但是不想改了~~。

description:
**请仔细阅读数据范围和时间限制。**

有一个长度为 $m$ 的数轴，一开始，处于 $1$ 时刻的**开始**，小 Z 处于 $1$ 号点，此时数轴上每个点都有一个障碍。

每个时刻，若小 Z 处于 $i$ 号点，小 Z 可以指定一个 $d \geq 0$，然后移动到 $i + d$ 号点，并且会越过 $[i, i + d]$ 的每一个障碍。

当然，一切都是在变化的，一共会有 $k$ 次变化，第 $i$ 次会发生如下变化：

- $t_i$ 时刻内 $x_i$ 号点上的障碍将会消失。
- **请注意，此变化仅作用于 $t_i$ 时刻**

保证变化是**随时间倒序发生的**，也就是说 $t_i$ **单调不升**。

现在，对于每个 $1\le i\le k$，你都需要输出**在前 $i$ 个变化发生的条件下**、在保证第 $n$ 个时刻结束时小 Z 恰好处于 $m$ 号点的基础上，小 Z 越过的最小障碍数。

inputFormat:
**本题强制在线，同时请注意在线形式。**

第一行，三个整数 $n,m,k$。

接下来 $k$ 行，其中第 $i$ 行有两个数字 $t_i, p$。其中 $p$ 用于生成 $x_i$，即：$x_i = \min(x_{i - 1} + p \oplus (lastans \bmod 15) + 1, m)$，其中 $lastans$ 表示上次变化的答案。

**特别地，第一次变化之前 $lastans = 0$，$x_0 = 0$，且当 $x_{i - 1} = m$ 时，将 $x_{i - 1}$ 视作 $0$（注意这不会真的改变 $x_{i - 1}$ 的值）。**

outputFormat: $k$ 行，每行一个整数，表示所求的值。

hint:
#### 样例解释

样例解密后：

```plain
2 3 2
2 1
2 2
```

- 第一次变化后：小 Z 第一秒选择 $d = 0$，跨过一个障碍。第二秒选择 $d = 2$，原本跨过了 $3$ 个障碍，但是第 $2$ 秒第一个点没有障碍，所以只跨过了 $2$ 个障碍。一共 $1 + 2 = 3$ 个障碍。
- 第二次变化后：小 Z 第一秒选择 $d = 0$，跨过一个障碍。第二秒只有第三个位置有障碍，选择 $d = 2$，所以只跨过了一个障碍。一共 $1 + 1 = 2$ 个障碍。

#### 数据规模与约定

**本题自动开启捆绑测试和 O2 优化。**

$$
\newcommand{\arraystretch}{1.5}
\begin{array}{c|c|c}\hline\hline
\textbf{Subtask} & \bm{n,m,k\le} & \textbf{分值} \\\hline
\textsf{1} & 100 & 15 \\\hline
\textsf{2} & 2\times10^3 & 20 \\\hline
\textsf{3} & 5\times10^4 & 20 \\\hline
\textsf{4} & 10^6 & 20 \\\hline
\textsf{5} & \text{无特殊限制} & 25 \\\hline\hline
\end{array}
$$

对于 $100\%$ 的数据（解密后），$1 \leq n, m, k \leq 2 \times 10^6$，$1 \leq t_i \leq n$，$0 \leq p \leq 15$，$t_i$ **单调不升**，若 $t_i$ 相同，按 $x_i$ **升序**，且 $\forall 1 \leq i < j \leq k$，$(t_i, x_i)$ 和 $(t_j, x_j)$ 不同。

本题提供读入优化方式。

使用 `read(x);` 读入一个任意的整型 `x` 等价于 `scanf("%d", &x);`其中可以将 `%d` 自动识别为对应类型。

```cpp
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
	r=0;bool w=0; char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
	r=w?-r:r;
}
```


title: 「EVOI-RD2」大胃王

description:
又到了一日三度的吃饭时间，大胃王开始因为吃什么饭而犯难了。

现有 $n$ 个材料，每个材料有一定的质量。大胃王可以把这 $n$ 个材料分为**连续**的任意段，然后每一段配一段质量为 $L$ 的主食。每一段的不和谐度定义为这段材料的质量和减去该段主食的质量（就是 $L$）的平方。一顿饭的不和谐度为所有段的不和谐度之和。

不用担心饭的多少的问题，因为某Code 是大胃王，所以做多少他都能吃完。

接下来，某Code 向你发起了挑战，要求你回答前 $i$ 道菜所做出的一顿饭的**最小和第二小**不和谐度。如果你回答正确，你将获得与他共享这顿饭菜的机会。

当两种分配方法得出同样最小的不和谐度时，则输出两个最小的不和谐度。即所输出的并非严格第二小不和谐度。

inputFormat:
第一行，两个正整数 $n$ 和 $L$，分别表示有 $n$ 个材料和每份主食的质量 $L$。

第二行 $n$ 个整数，第 $i$ 个整数代表第 $i$ 个材料的质量 $a_i$。

outputFormat:
输出共 $n$ 行。

其中第一行一个整数，为前 $1$ 道菜做出的饭的最小不和谐度。

在第 $i$ 行输出两个整数，为前 $i$ 道菜所做出的一顿饭的**最小和第二小**不和谐度，中间用空格隔开。


title: 「PMOI-5」公约数变换

description:
给出一个常数 $m$ 和长度为 $n$ 的序列 $a$。

定义一次「公约数变换」为：
先令 $b_i\leftarrow a_i+\gcd(m,a_1,...,a_i)$，最后令 $a_i\leftarrow b_i$。（注意是先把每个 $b_i$ 都算出来再一一赋值，而不是边算边赋值）

请问最少做几次「公约数变换」使得 $\forall i \in[1,n]$，$m|a_i$。

**可以证明一定有解。**

inputFormat:
第一行两个整数 $n$ 和 $m$，表示序列长度和给出的常数。
接下来一行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

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

hint:
【样例解释 1】

第一次「公约数变换」后的序列为 $10,5,4,3,2$。
第二次「公约数变换」后的序列为 $15,10,5,4,3$。
第三次「公约数变换」后的序列为 $20,15,10,5,4$。
第四次「公约数变换」后的序列为 $25,20,15,10,5$。
可以得出答案为 $4$。

【数据范围】
**本题采用捆绑测试。**

- Subtask1（5pts）：$m=1$；
- Subtask2（10pts）：$m=2$；
- Subtask3（10pts）：$n=1$ 且 $m\le 500$；
- Subtask4（15pts）：$n=1$；
- Subtask5（10pts）：$n\le 5000$；
- Subtask6（20pts）：$n\le 5\times 10^4$；
- Subtask7（10pts）：$m,a_i\le 10^{9}$；
- Subtask8（20pts）：无特殊限制；

对于 $100\%$ 的数据，$1\le n\le 10^{5}$，$1\le m\le 10^{14}$，$1\le a_i\le 10^{18}$。保证答案在 `long long` 范围内。


title: 『JROI-3』删树

background:
**本题数据已加强，建议场上过了的同学再次提交确定做法正确性。**

> 千万不要看错题！

——command_block 《考前小贴士》

你在 2021 年在洛谷打了一场比赛叫做 EZEC Round
 6，其中里面有一道[造树题](https://www.luogu.com.cn/problem/P7390)你觉得特别水，随手就切了它。（所以没做过链接里题的人快来做啊！！！）

现在你在打 JROI-3 的月赛，你觉得造树太水了想删掉树，于是良心的出题人给了你一个机会。但是，在删除树之前，djy 想先知道树的边权和。

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

有一个 $n$ 个节点的带边权的树，编号为 $1-n$。每个点的度数是已知的。djy 想知道树上所有边的权值和，但他太菜了，不会去算如此简单的问题，因此把这个题扔给了您。

由于您很强，所以您可以对这棵树进行一些改变：删除所有度数为 $1$ 的节点，得到剩下点的个数和每个点的度数。

您可以向交互库进行三种类型的提问：

- 对于当前树上存在的一个点，询问它的 dfs 序$^1$。
- 对于当前树上存在的一对节点，询问它们之间的距离$^2$。
- 删除当前树上所有度数为 $1$ 的节点，同时删除与这些节点相邻的边，并且将所有未被删除的节点进行重新编号。**保证剩下的节点的编号分别为 $1-k$，其中 $k$ 是剩下的节点个数。**

你需要操作**不超过 142 次（包括提交答案）**，并在树**删空**之前求出**当前**树上所有边的权值和。

---
注：
- dfs 序$^1$：dfs 序指从当前的 $1$ 号节点进行 [深度优先搜索](https://baike.baidu.com/item/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2/5224976) ，每个节点被第一次访问的顺序。一棵树的 dfs 序不唯一。每次删除操作后 dfs 序会被重置。保证 dfs 序不随着其他操作而改变，即两次询问同一节点的 dfs 序的询问中间如果没有删除操作，保证回答相同的值。
- 距离$^2$：指在树上两点路径上的边权和。特别地，两个相同节点的距离为 $0$。

inputFormat:
**「交互模式」**

**本题采用 IO 交互模式。**

在开始交互前，您需要先读入 $n$，表示树中点的个数。

接下来一行 $n$ 个数，表示每个点的度数。

您可以进行三种类型的询问：

- `dfn u`: 询问交互库编号为 $u$ 的节点的 dfs 序。交互库返回一行一个整数，表示 $u$ 的 dfs 序。

- `dis u v`: 询问交互库编号为 $u$ 和 $v$ 的两个节点的距离。交互库返回一行一个整数，表示 $u$ 和 $v$ 的距离。

- `del`: 要求交互库删除度数为 1 的点以及与之相连的边。交互库将对点进行重编号，并重新跑一个 dfs 序，交互库返回第一行一个整数为树的大小 $m$，第二行 $m$ 个整数，第 $i$ 个表示编号为 $i$ 的点的度数。

如果您求出了当前树上所有边的边权和，按照 `! x` 的格式输出答案 $x$，并立刻结束程序。

请保证作为询问参数的节点未被删除且 del 操作后树不为空。

**如果您的操作不合法或次数大于 142 次，交互库会立刻终止程序，并将结果判定为 WA/RE/TLE/MLE。**

在每一次询问之后，请不要忘记输出换行符以及清空缓存区，否则将会出现未知的错误。为了避免这种情况，您可以使用：
- 对于 C++，使用 ```fflush(stdout)``` 或  ```cout.flush()```。
- 对于 Java，使用 ```System.out.flush()```。
- 对于 Python，使用 ```stdout.flush()```。
- 对于其他语言，请阅读相关文献。

outputFormat: 见 **「交互模式」**。

hint:
**样例仅供理解交互过程，可能不符合逻辑。**

【样例解释】

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

树的形态如上。

第一次询问节点 $1$ 的 dfs 序，为 $1$。

第二次询问节点 $2$ 与节点 $6$ 的距离，为 $5$。

当前树上所有边的边权和为 $17$。

-----
【数据范围】

**「本题采用捆绑测试」**
- Subtask 1（1pts）：$n \le 2$。
- Subtask 2（4pts）：$n \le 4$。
- Subtask 3（20pts）：$n\le 150$。
- Subtask 4（10pts）：树是一条链。
- Subtask 5（30pts）：保证度数为 $1$ 的点不超过 $50$ 个。
- Subtask 6（20pts）：$n\le 2000$。
- Subtask 7（15pts）：无特殊限制。

对于 $100\%$ 的数据，$1\le n\le 5000$，每条边的边权不大于 $10^5$ **且为正整数**。

**如果有假做法过了，请私信联系出题人加强数据。（如果有hack更好了）。**


title: [CoE R4 C] 网格

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

有一张 $n$ 个点的无向无权图。

这张图有一个特殊性质：存在一个点 $u \ (1 \leq u \leq n)$ 到正整数对 $(x, y) \ (1 \leq x \leq l, 1 \leq y \leq c)$ 的**一一对应**关系，使得 $n = l \cdot c$，且点 $u, v$ 间存在边当且仅当 $u, v$ 对应的数对 $(x_u, y_u), (x_v, y_v)$ 满足 $|x_u - x_v| + |y_u - y_v| = 1$。换而言之，这张图和 $l$ 行 $c$ 列的网格图同构。

现在，你要通过一些询问还原这张图的结构。每次询问时，你需要给定一个点 $u \ (1 \leq u \leq n)$。询问的返回值是一个长为 $n$ 的数组 $\{d_i\} \ (1 \leq i \leq n)$，表示点 $u, i$ 间的最短路径所经过的边数。

请你使用不超过 $q$ 次询问，还原出这张图的结构。

---

### 交互格式

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

首先输入一个整数 $T$，表示数据组数。

对于每组数据：

- 首先输入一个整数 $n$，表示图的点数。
- 接下来，你可以执行一些询问。对于每次询问，输出一个整数 $u$，为你询问的点。然后，输入 $n$ 个整数 $\{d_i\}$，为询问的返回值。
- 当你确定答案后，输出一个整数 $0$，然后输出答案。

在输出答案时：

- 第一行输出两个整数 $l, c$；
- 接下来，输出 $l$ 行 $c$ 列整数，为你还原的对应关系。第 $i$ 行 $j$ 列的数为 $(i, j)$ 对应的编号。

如果有多个答案，你可以输出任意一个。一个答案是正确的，当且仅当它和标准答案无法被任何询问区分：也就是，在这两个答案对应的网格图中，任意点对间的最短路径所经过的边数都是相同的。

---

请注意：**在每次执行询问或者输出答案后，你应该清空缓冲区：**

- 在 C++ 中，使用 `fflush(stdout)` 或 `cout.flush()`。
- 在 Java 中，使用 `System.out.flush()`。
- 在 Python 中，使用 `stdout.flush()`。
- 在 Pascal 中，使用 `flush(output)`。
- 对于其他语言，请自行查阅对应语言的帮助文档。

inputFormat: 见「交互格式」。

hint:
### 样例 $1$ 解释

对于样例，以下 $3$ 行 $2$ 列的网格图也是正确的输出。

```
3 2
4 2
3 5
6 1
```

左边是样例对应的网格图，右边是以上输出对应的网格图。

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

---

### 评分标准

对于一个子任务，令 $q_{\max}$ 为你在这个子任务的所有测试数据中的最大询问次数。

如果交互的格式不合法，运行超出了时间限制，或者你的答案不正确，或者 $q_{\max} > q$，你的得分为 $0$。

否则，对于子任务 $1 \sim 3$，你得满分；对于子任务 $4$，你的分数由下表给出：

| 条件 | 分数 |
| :-: | :-: |
| $q_{\max} \leq 3$ | $61$ |
| $q_{\max} = 4$ | $41$ |
| $q_{\max} = 5$ | $31$ |
| $q_{\max} = 6$ | $21$ |
| $q_{\max} \geq 7$ | $11$ |

---

### 数据规模

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

| 子任务 | 分值 | $n \leq$ | $q = $  | 特殊性质 |
| :-: | :-: | :-: | :-: | :-: |
| $1$ | $3$ | $4$ | $4$ | 无 |
| $2$ | $13$ | $10^5$ | $4$ | 存在解使得 $l = 1$ |
| $3$ | $23$ | $36$ | $36$ | 存在解使得 $2 \leq l, c \leq 6$ |
| $4$ | $61$ | $10^5$ | $12$ | 无 |

对于所有数据，保证 $1 \leq T \leq 10^3$，$1 \leq n \leq 10^5$，$\sum n \leq 3 \times 10^5$。

在部分测试数据中，交互器是自适应的。也就是，图的结构可能会根据你的询问而变化。但是可以保证：在每次询问之后，存在至少一个答案符合当前所有询问的返回值。


title: [LSOT-1] 逆序对

background: 逆序对真好玩

description:
你需要维护一个数列，支持以下 $4$ 种操作：

1. 区间交换；
2. 把一个区间**向后**移动到第 $k$ 个数字与第 $k+1$ 个数字之间；
3. 在最后插入一个数 $x$；
4. 在开头插入一个数 $x$。

每个数数的序号为新序列重新从第一个数到第 $k$ 个数编号为 $1$ 到 $k$。

现在每次操作过后，请你输出整个数列逆序对数量的奇偶性。

inputFormat:
第一行输入两个正整数 $n,m$，表示初始序列的长度与操作个数。

接下来一行输入 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示初始序列。

接下来 $m$ 行，每行先输入一个 $t$ 表示操作编号，之后：
- 若 $t=1$，则输入四个正整数 $l_1,r_1,l_2,r_2$，表示将区间 $[l_1,r_1]$ 与区间 $[l_2,r_2]$ 整体交换，保证 $l_1\le r_1< l_2\le r_2$；
- 若 $t=2$，则输入三个正整数 $l,r,k$，表示将区间 $[l,r]$ 移动至序列的第 $k$ 个数与第 $k+1$ 个数之间，保证 $r<k$；
- 若 $t=3$，则输入一个正整数 $x$，表示将 $x$ 插入到序列末端；
- 若 $t=4$，则输入一个正整数 $x$，表示将 $x$ 插入到序列首端。

outputFormat: 对于每一个指令执行后，如果逆序对数量是偶数，请输出 `even` ，否则输出 `odd`。

hint:
【样例解释】

第一次操作将区间 $[1,1]$ 和区间 $[2,2]$ 交换，序列变为 `3 4 5 7 2 6`。

第二次操作将区间 $[1,1]$ 移动到第 $3$ 和第 $4$ 个数中间。序列变为 `4 5 3 7 2 6`。

第三次操作在序列末端插入 $11$，序列变为 `4 5 3 7 2 6 11`。

第四次操作在序列开头插入 $1$，序列变为 `1 4 5 3 7 2 6 11`。

【数据范围】

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

- $\texttt{Subtask 1(10 pts): }n,m\le 10^2$；
- $\texttt{Subtask 2(15 pts): }n,m\le 10^3$；
- $\texttt{Subtask 3(20 pts): }$没有一二操作；
- $\texttt{Subtask 4(20 pts): }$没有三四操作；
- $\texttt{Subtask 5(35 pts): }$无特殊限制。

对于 $100\%$ 的数据，$1\le n,m \le 2\times 10^5,a_i\le 2\times10^6$，保证在任意时刻 $a$ 中的数均互不相同。


title: 「EVOI-RD2」昕昕的不等式组

description:
昕昕做到了一道解一元一次不等式组的数学题。

这个一元一次不等式组共有 $n$ 个一元一次不等式。她分别求出了每个不等式的解集，而她需要把它们合并为该不等式组的解集。

每个不等式解集都化简为了最简形式，都形如 $x<t_i$（或 $x>t_i$ 等），其中 $t_i$ 为常数项，$x$ 为未知数。未知数为一个小写英文字母，会在不等号左侧；常数项为一个整数，会在不等号右侧。

所有不等式使用的不等号只有 $<,>,\le,\ge$ 四种。在本题的输入输出中，$\le$ 和 $\ge$ 则分别用 $<=$ 和 $>=$ 代替。

现在昕昕需要你求出该不等式组的解集。

inputFormat:
第一行为一个正整数 $n$ 和一个小写英文字母 $x$，分别表示有 $n$ 个已简化的不等式解集，和不等式组中的未知数为 $x$。

接下来 $n$ 行，每行为一个已化简的一元一次不等式，也就是该不等式的解集。

对于每个解集，都由未知数、一个不等号和常数项 $t_i$ 依次排列而成，其中未知数为第一行给出的 $x$。

outputFormat:
输出一行，即这个不等式组的解集，形如“$a\ op1\ x\ op2\ b$”或“$x\ op\ a$”等，其中 $op1,op2$ 为 $<$ 或 $<=$，$op$ 为 $<,<=,>,>=$ 或 $=$，注意不要有多余的空格。

若该不等式组无解，则输出 `No Answer!`。

hint:
**【样例 $1$ 说明】**

如图，为数轴上各个不等式解集的公共部分，即为该不等式组的解集，$-3 < x \le 1$。注意 $\le$ 在输出中用 $<=$ 替换。

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

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

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

+ Subtask 1（5 pts）：$n=1$。
+ Subtask 2（25 pts）：$n=2$。
+ Subtask 3（10 pts）：$n \le 3$，$-4 \times 10^4 \le t_i \le 4 \times 10^4$。
+ Subtask 4（20 pts）：$n \le 10^4$，$-10^5 \le t_i \le 10^5$。
+ Subtask 5（10 pts）：$n \le 2 \times 10^4$。
+ Subtask 6（20 pts）：$n \le 5 \times 10^4$。
+ Subtask 7（10 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 6 \times 10^4$，$-10^6 \le t_i \le 10^6$，每个不等式中的未知数都是一个小写英文字母。

**【提示】**

以下为涉及到题目的一些数学知识。

+ 不等式：用不等号联系的关系式。
+ 不等式的解：在含有未知数的不等式中，能使不等式成立的未知数的值。
+ 不等式的解集：不等式的解的全体。
+ 不等式组的解集：不等式组中所有不等式的解集的公共部分。
+ 解不等式组：求不等式组的解集的过程。


title: 如何得到 npy

background: 作为年级第一大风流人物，Steve 总会给自己找很多东西，包括但不限于 npy。Steve 看上了 Ada，并试图接近她，然而 Ada 并不是那么乐意。

description:
**提示：你可以阅读题目描述末尾的形式化题面。**

Steve 所在的校园有 $n$ 间教室，编号为 $1$ 到 $n$，有 $n-1$ 条走廊将其连通。也就是说，教室和走廊构成了一棵树。每条走廊都有一定的长度 $w_i$，经过这条走廊的时间等于其长度的数值。

Steve 喜欢在校园里游荡。当然，他希望最后能走到自己的教室 $s$ 或 Ada 的教室 $t$。但由于学校过于错综复杂，且 Steve 不想走回头路，所以他想到了如下方案：

对于每个教室（Steve 和 Ada 的教室除外，这两个教室周围不应该有任何标牌），在一条与其相连的边立上标牌。每次走到这个教室，就从立了标牌的边出。

Steve 可能会在学校的任何一个教室出现，所以一方面，Steve 需要让他从每个教室都能跟着标牌回到他的或 Ada 的教室。另一方面，他希望从学校所有教室走到目的地的**时间总和**尽可能小。

由于 Steve 又要去找 Ada 了，所以请你帮他完成这个任务。

#### 形式化题意

给定一棵 $n$ 个节点的无根树和两个关键点 $s,t$，要求对所有边定向，满足：

- 每条边要么是有向边，要么被删除；
- 每个点（除 $s,t$）出度恰好为 $1$，$s,t$ 出度为 $0$；
- 每个点都可以顺着有向边到达 $s$ 或 $t$。

求每个点到 $s$ 或 $t$ 的距离总和最小值。

inputFormat:
第一行输入三个正整数 $n$，$s$，$t$。

接下来 $n-1$ 行，每行输入三个正整数 $u_i$，$v_i$，$w_i$，代表一条树边 $(u_i,v_i)$，权值为 $w_i$。

outputFormat:
输出第一行一个正整数，代表最小的权值和。

接下来一行，输出一个字符串 $S$，要求：

- $S_i=\texttt{0}$，指第 $i$ 条边两边均不立标牌；
- $S_i=\texttt{1}$，指第 $i$ 条边在 $u_i$ 处立标牌；
- $S_i=\texttt{2}$，指第 $i$ 条边在 $v_i$ 处立标牌。

本题使用自定义校验器评测。如果有多种方案，输出任意一种。

samples:
见下发文件 corridor/corridor3.in
见下发文件 corridor/corridor3.ans

samples:
见下发文件 corridor/corridor4.in
见下发文件 corridor/corridor4.ans

hint:
#### 样例 1 解释

`2011` 也是合法的答案，但 `2211`，`1102` 等都不是。

#### 样例 2 解释

下图是取到样例中最优解的状态（$(8,13)$ 这条边没有画出）:

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

#### 样例 3 解释

该样例满足子任务 2 的限制条件。

#### 样例 4 解释

该样例满足子任务 5 的限制条件。

---

下发文件中还有 `checker.cpp` 可判定答案是否合法。使用时，先编译（设二进制文件为 `checker`（Linux/MacOS）或 `checker.exe`（Windows）），然后在终端输入如下命令：

```
./checker in.txt out.txt ans.txt
```

如果你使用了 Windows 系统且无法运行上述命令，请尝试：

```
checker.exe in.txt out.txt ans.txt
```

其中 `in.txt`、`out.txt`、`ans.txt` 分别是放在同一目录下的输入文件、选手输出、标准答案。

结果可能有如下中的一种：

- `ok`：结果正确，可以得到满分；
- `wrong answer`：第一行答案错误；
- `points 0.60`：第一行答案正确，第二行答案错误。

对于所有非满分情况，会有附加消息，意义如下：

- `A x y`：第一行答案错误，标准答案是 $x$，选手答案是 $y$；
- `B`：第二行长度不符合条件；
- `C`：第二行出现非法字符；
- `D`：第二行给出的构造不满足题目中关于度数的限制；
- `E x y`：第二行给出的构造产生的答案是 $y$，而实际上答案是 $x$。

该校验器和最终评测时采用的校验器可能有所不同。

注意下发文件的输出样例中只有最优答案，没有构造方案。

### 数据规模与约定

**本题捆绑测试**。对于所有数据，$3\le n\le 3\times 10^5$，$1\le w_i\le2\times 10^8$，$1\le s,t\le n$，$s\neq t$。

$$
\def\arraystretch{1.5}
\begin{array}{c|c|c||c|c}\hline

\bf 子任务 & \bf 分值 & \bf 依赖 & n\le & \bf特殊性质
\\
\hline
\hline
1 & 10 & / & 10 & /\\\hline
2 & 15 & 1 & 18 & /\\\hline
3 & 15 & / & / & v_i=u_i+1\\\hline
4 & 10 & / & / & u_i=1\\\hline
5 & 20 & / & / & 存在边\ (s,t)\\\hline
6 & 30 & 2\sim5 &/ & /
\end{array}
$$

如果你计算出了正确的答案，但是你的构造是错误的，那你将得到该测试点 $60\%$ 的分数。注意即使你只实现了第一小问，请依旧在第二行输出任意一个非空字符串，否则可能会不计分。

本题中的依赖指：某子任务的得分占比不能超过其所依赖的子任务得分占比。比如，一选手子任务 $1$ 得到 $60\%$ 的分数，则他的子任务 $2$ 就不会超过对应的 $60\%$ 分数，即不超过 $9$ 分。

答案可能很大，请注意你使用的数据类型。

---

到毕业为止，Steve 也没有追到 Ada。What a sad story. :-(


title: 「EVOI-RD1」马戏团

background: WuuTue拥有一家马戏团，马戏团会在全国巡演，最近WuuTue的马戏团来到了T市。

description:
T市有一条专门的演出街，演出街是一条东西走向的笔直街道，街道上从西往东有 $n$ 个舞台，舞台的编号为 $1, 2, \dots, n$。

WuuTue计划在T市的演出街上进行 $M$ 场演出，其中第 $i$ 场演出要占用从 $l_i$ 到 $r_i$ 的连续舞台（包括 $l_i$ 和 $r_i$ ），同时WuuTue知道，第 $i$ 场比赛将会获得 $v_i$ 元的收益。

由于演出街的舞台都是设计给人表演使用的，如果要供动物表演使用的话，需要进行加固，其中加固第 $i$ 个舞台需要花费 $c_i$ 元钱，并且只需要加固一次，可以重复使用。也就是说如果有多个演出都用到了舞台 $i$，那么只需要花费一次加固的费用就可以了。

当然，如果WuuTue发现某场演出可能由于加固费用过高无法盈利，也可能会取消演出。

因为WuuTue太蒻了，所以请帮助WuuTue计算，他最多可以获得多少元钱的收入。

inputFormat:
第一行：两个空格分隔的整数 $n$ 和 $m$，分别表示舞台和演出的数量。

第二到 $n+1$ 行：每行 $1$ 个整数，其中第 $i+1$ 行的整数表示加固第 $i$ 个舞台需要的花费 $c_i$。

第 $n+2$ 行到第 $n+m+1$ 行：每行 $3$ 个空格分隔的整数，其中第 $n+i+1$ 行的 $3$ 个整数 $l_i$，$r_i$，$v_i$，表示第 $i$ 场演出需要占用第 $l_i$ 到 $r_i$ 的连续舞台，可以获得 $v_i$ 元的收益。

outputFormat: 一行：一个整数，表示WuuTue可以获得的最大收益。


title: 「EVOI-RD1」小昕昕

background:
一副扑克牌共有 $54$ 张牌，除去大小王后有 $52$ 张。在同一副牌中，一张牌只可能出现一次。

一副扑克牌中一共有四种花色：黑桃($\texttt{spade}$)、红桃($\texttt{heart}$)、梅花($\texttt{club}$)、方块($\texttt{diamond}$)。每个花色的牌共有 $13$ 张，分别为 $\texttt{A} \sim \texttt{K}$。

在题目中，以上四种花色分别以 $\texttt{S,H,C,D}$ 表示。

我们约定，任何一张牌，都以 **花色+点数** 表示，并且约定用 $\texttt{T}$ 表示 $\texttt{10}$，如 $\texttt{SA,D5,HT,CQ}$。

description:
昕昕手上有 **两副无大小王** 的扑克牌，她会从这些扑克牌里取出 $n$ 张牌。

昕昕创造了一个组合为 **“小昕昕”**，它的定义是，任意取出 $3$ 张牌，若这 $3$ 张牌的 **牌点一样** ，且花色有且仅有 **两种** ，则称为一对“小昕昕”。如 $\texttt{H3,S3,S3}$ 是一对“小昕昕”。

当这三张扑克牌组成 **“小昕昕”** 后，昕昕就会把它们从牌堆内拿出，**不可再次使用**。

现在，昕昕想让你帮她数数，这副牌里最多能组成多少对 **“小昕昕”**。

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

第二至 $n+1$ 行，每行为一张扑克牌。

outputFormat: 输出这 $n$ 张牌内，最多能组成多少对“小昕昕”。

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

+ $\texttt{Subtask 1 (10 pts)}$ ：$1 \le n \le 3$。
+ $\texttt{Subtask 2 (20 pts)}$ ：$1 \le n \le 5$。
+ $\texttt{Subtask 3 (30 pts)}$ ：$1 \le n \le 20$。
+ $\texttt{Subtask 4 (10 pts)}$ ：$1 \le n \le 70$。
+ $\texttt{Subtask 5 (30 pts)}$ ：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 104$，保证输入的牌都存在于两副无大小王的扑克牌中。


title: 「SvR-2」音符

description:
>本题中「子串」指：
>
>若字符串 $s$ 中有一段**连续的**字符构成字符串 $p$，则 $p$ 是 $s$ 的子串。

我们用一个字符串代替一份乐谱，用字符代替每一个音符。

我们定义「重音」表示乐谱中出现了两个**连续**的相同字符，如 $\tt eeeee$ 中存在 $4$ 个「重音」。

现在 Sept 准备写一份长度为 $n$ 的乐谱给 Tpes 看，他对乐谱的评价标准如下：

- 乐谱中每出现一个「重音」，他的愤怒值就会增加 $a$。
- 乐谱中每有一段长度为 $k$ 的**子串**中不存在「重音」，他的愤怒值就会增加 $b$。

现在已知 $n,k,a,b$，请你帮 Sept 构造出一份乐谱，使得 Tpes 的愤怒值 $x$ **最小**。

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

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

接下来 $T$ 行，每行两个整数 $n,k,a,b$，意义如题目所述。

outputFormat:
共 $2 \cdot T$ 行，对于每组数据都输出两行：

- 第 1 行表示 Tpes 最小的愤怒值 $x$。
- 第 2 行表示你构造出的乐谱。

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

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

| $\bf{Subtask}$ | $\bm{n\le}$ | $\bm{\sum n\le}$ | $\bm{T\le}$ | $\bf{Score}$ |
| :-: | :-: | :-: | :-: | :-: |
| $\sf 1$ | $6$ | $10$ | $3$ | $\tt 10$ |
| $\sf 2$ | $10^3$ | $2\times 10^3$ | 无特殊限制 | $\tt 30$ |
| $\sf 3$ | 无特殊限制 | 无特殊限制 | 无特殊限制 | $\tt 60$ |

对于 $100\%$ 的数据，有 $2\le T\le 100$，$2\le n,k\le 10^5$，$1\le a,b\le 10^9$。单组数据内保证 $\sum n\le 2\times 10^5$。

#### 输出注意事项

输出 $x$ 和构造乐谱可以看作是两个子问题，如果你只会完成其中的一个，请在另一个子问题对应的地方用**符合要求的字符或数字**占位。

乐谱中你可以输出任意字符，包括数字、大小写字母等，但**不能出现空格**。

#### Special Judge 返回信息说明

本题采用 Special Judge 判断你的答案是否正确。

checker.cpp 将会以 $\texttt{Score=}\text A,\texttt{Type=}\text B$ 的方式返回信息。

$\tt Score$ 类表示你的得分情况，$\text A$ 有以下取值：

- $\text A=1$，表示含义如下：\
  $\underline\text{Accepted.} \texttt{ Your Ans and SM are both proper.}$\
  代表 $T$ 组答案全部符合要求。
- $\text A=2$，表示含义如下：\
  $\underline\text{Partially Correct.}\texttt{ All Ans are right.}$\
  表示该测试点中你的回答中 $x$ 全部正确，你能得到该测试点 $20\%$ 的分数。
- $\text A=3$，表示含义如下：\
  $\underline\text{Partially Correct.}\texttt{ You pass 70\% tests!}$\
  表示该测试点中你的回答正确的组数**不少于**$\lfloor0.7\times T\rfloor$（$x$ 与乐谱均符合要求），你能得到该测试点 $10\%$ 的分数。
- $\text A=4$，表示该测试点你只能拿到 $0$ 分。

$\tt Type$ 类表示你的得分情况，$\text B$ 有以下取值：

- $\text B=0$，表示你的答案全部正确，与 $\text A=1$ 配对。
- $\text B=1$，表示含义如下：\
  $\underline\text{Wrong Answer.}\texttt{ The length of your SM is not right!}$\
  代表你在一组数据中构造的乐谱的长度不为 $n$。
- $\text B=2$，表示含义如下：\
  $\underline\text{Wrong Answer.}\texttt{ Your Ans is not right!}$\
  代表你在一组数据中 $x$ 的值错误。
- $\text B=3$，表示含义如下：\
  $\underline\text{Wrong Answer.}\texttt{ Your Ans and SM are not matched!}$\
  代表你在一组数据中构造的乐谱使 Tpes 产生的愤怒值不为 $x$。

这里 $\text{Ans, SM}$ 分别表示 Answer（$x$ 的值）和 Sheet Music（乐谱）。

注意到 $\tt Type$ 只会反映你在该测试点中**第一次错误**的类型。


title: 「Wdoi-4」芙兰？姆Q！贤者与谜题

background:
题目背景不包含解题的关键信息，可以跳过。

---

芙兰朵露·斯卡蕾特是曾居住在红魔馆地下室的吸血鬼。与众不同的是，芙兰朵露有着彩色结晶的特殊翅膀，与其他吸血鬼蝙蝠一般的翅膀不同：颜色各异的结晶按照顺序一字排开。

芙兰朵露翅膀的彩色结晶的颜色从内到外分别是天蓝、蓝、紫、粉、橙、黄、淡绿和天蓝。因此事实上，芙兰朵露的翅膀很可能就是帕秋莉的「贤者之石」组成的。

但是芙兰朵露并不关心这些，她只关心排列成翅膀形状的贤者之石之间发生的能量流动——如果一块贤者之石被赋予了能量，就会处于激发态。处于激发态的贤者之石很不稳定——它大量能量的爆发会波及周围的贤者之石，以造成能量的转移。

芙兰朵露非常感兴趣，并以此出了一个谜题来考考帕秋莉。但是作为贤者的帕秋莉不想思考只想摸鱼，于是任务就交给你啦！![](https://www.luogu.com.cn/paste/tkub6dq3)

description:
芙兰朵露从帕秋莉那里搞来了 $n$ 块贤者之石，并从左往右排成了一列。帕秋莉可以赋予每块贤者之石一定的能级，这会决定贤者之石之间能量的传递。值得注意的是，**能级必须要是正整数，并且不能有两块贤者之石能级相同**。

如果第 $i$ 块贤者之石被赋予了能量（处于激发态），它就会将能量传递给第 $i-1$ 和第 $i+1$ 块里**能级较小**的那一块。特别地，如果某块贤者之石周围只有一块，那么它只会向这一块发送能量。注意，即使第 $i$ 块的能级低于第 $i-1$ 和第 $i+1$ 块，它**照样可以传输能量**。

现在芙兰有 $q$ 个条件——每个条件给定两个正整数 $s,t$，表示如果芙兰激活了第 $s$ 块贤者之石的能量，那么能量最终会经过第 $t$ 块。

然而由于帕秋莉有哮喘的老毛病，设定贤者之石的能级是很费力的。因此，如果存在一种合法的赋予贤者之石能级的方案，请你找出其中**字典序最小**的那个方案。对于两种方案 $A,B$，我们称 $A$ 的字典序小于 $B$，当且仅当存在一个 $p$，使得 $\forall i<p$ 有 $A_i=B_i$，且 $A_p<B_p$。

如果存在合法方案，请你输出字典序最小的方案；否则输出 `QED`。

inputFormat:
第一行有两个整数 $n,q$，表示贤者之石的块数和芙兰的条件个数。
接下来 $q$ 行，每行有两个整数 $s_i,t_i$，描述一组条件。

outputFormat: 若不存在合法方案，输出 `QED`；否则输出 $n$ 个整数，表示字典序最小的那个方案。

hint:
输入/输出样例 $2$ 见下发的附件 $\textbf{\textit{qed2.in}/\textit{qed2.out}}$。

输入/输出样例 $3$ 见下发的附件 $\textbf{\textit{qed3.in}/\textit{qed3.out}}$。

---

### 数据范围及约定

对于 $100\%$ 的数据，$0\le q \le 3\times 10^5$，$3\le n \le 3\times 10^5$，$1\le s_i,t_i \le n$。

$$
\def{\arraystretch}{1.5}
\begin{array}{|c|c|c|c|} \hline
\textbf{测试点} & \bm{n\le} & \bm{q\le} & \textbf{特殊限制} \cr \hline
1\sim 3 & 7 & 7 & - \cr \hline
4\sim6 & 100 & 100 & - \cr \hline
7 & 10^5 & 1 & -\cr \hline
8\sim 10 & 3\times 10^5 & 3\times 10^5 & s_i\le t_i \cr \hline
11\sim 12 & 10^5 & 10 & - \cr \hline
13\sim 20 & 3\times 10^5 & 3\times 10^5 & -\cr \hline
\end{array}$$


title: [✗✓OI R1] 天动万象

description:
帝君给了你一棵以 $1$ 为根的有根树，每个点有一个点权 $a_i$，要求支持以下几种操作：

+ $\texttt{1 u}$ 表示查询以 $u$ 为根的子树的最大值。
+ $\texttt{2 u}$ 表示将 $u$ 为根的子树内每一个节点的权值 **同时变为** 其所有 **儿子** 的权值之和，即对这棵子树执行 $\forall x \in \operatorname{subtree}(u), a_x\gets \sum_{y\in \operatorname{son}(x)}a_y$。其中 **同时变为** 的意思是「某个点操作时认为其儿子停留在这次操作未进行前的状态」。

inputFormat:
第一行两个正整数 $n,q$ 表示树的大小和询问组数。
第二行 $n$ 个正整数，第 $i$ 个数表示表示第 $i$ 个点的初始点权 $a_i$。
第三行 $(n-1)$ 个整数，其中第 $i$ 个整数 $\mathit{fa}_{i+1}$ 表示第 $(i+1)$ 个节点的父亲编号。
接下来 $q$ 行，每行两个整数表示一次操作，具体格式见「题目描述」。

outputFormat: 对于每次 $\texttt{1}$ 操作输出一行一个整数表示答案。

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

修改前每个点的权值分别为 $1,1,4,5,1,4$。
第一次修改后变为 $1,1,4,1,0,4$。
第二次修改后变为 $1,5,0,0,0,4$。

[更直观的图片](https://www.luogu.com.cn/paste/blqun4u8)

**【数据范围】**

**本题数据量较大，请注意常数优化。**

对于 $100\%$ 的数据，满足 $1\le n, q \le 10^6$，$1 \le u \le n$，$0 \le a_i \le 10^9$，$\mathit{fa}_i < i$。

以下是子任务（留空则表示无特殊性质），你必须通过一个子任务中的所有测试点以及该子任务依赖的所有测试点，才能获得这个子任务的分数：

| 子任务编号 | $n, q$             | 子任务总分 | 特殊性质 | 依赖子任务 |
| :--------: | :----------------: | :------: | :------: | :--------: |
| 0   | $\le 5\times 10^3$ | 3        | E        |            |
| 1   | $\le 10^5$         | 6        | A, B     |            |
| 2   |                    | 8        | C        |            |
| 3   |                    | 4        | D        |            |
| 4   |                    | 13       | E        | Subtask0   |
| 5   |                    | 36       | B        | Subtask1   |
| 6   |                    | 30       |          | Subtask0~5 |

特殊性质：

+ 对于满足特殊性质 A 的测试点，保证每次 $1$ 操作 $u=1$。
+ 对于满足特殊性质 B 的测试点，保证每次 $2$ 操作 $u=1$。
+ 对于满足特殊性质 C 的测试点，保证对于所有节点 $i$， 满足 $\mathit{fa}_i=i-1$，换句话说树的形态是一条链。
+ 对于满足特殊性质 D 的测试点，保证对于所有节点 $i$， 满足 $\mathit{fa}_i=1$，换句话说树的形态是一个菊花。
+ 对于满足特殊性质 E 的测试点，保证数据随机，这里的数据随机指 $\texttt{1}$ 操作和 $\texttt{2}$ 操作等概率出现，$u$ 在 $[1, n]$ 内等概率随机，$\mathit{fa}_i$ 在 $[1, i - 1]$ 内等概率随机。

**提示：由于出题人很懒而且洛谷传不了很多数据点，因此本题数据可能较弱，而且为了避免赛事评测机压力导致的运行时间增加，本题放宽了时限，因此欢迎大家尝试用奇怪的乱搞通过本题。**

> 只愿荡涤四方，护得浮世一隅。


title: 「Wdoi-4」兔已着陆

background:
铃瑚和清兰是从月之都到达幻想乡的两只月兔。正因为降落到了幻想乡进行调查，因此她们通过开团子屋制作团子出售的方式，在幻想乡生活。

为了应对越发繁荣的市场，她们向河城荷取购置了一台团子机器，可以高效地生产出五颜六色的团子。不同颜色的团子的售价不尽相同。由于每天顾客数量很多，购买的团子数量也不少，所以清兰总是搞不清楚一大堆团子的售价如何。

清兰找到了你，希望你能告诉她每次售出团子时，这些团子的总价格。

description:
清兰使用河童的机器可以生产出各种各样颜色的团子。她发现，**对于颜色为** $\bm c$ **的团子，它的售价为** $\bm c$。同时，团子机器有个特性，那就是生产出来的团子的颜色必然是一段连续的整数。

为了储存已经生产出来的团子，清兰使用了一种类似于「栈」的结构。在一天的开始，这个栈为空栈。现在有 $n$ 次操作，分为两种：

1. $\colorbox{f0f0f0}{\verb!1 l r!}$ ：团子机器生产出来了颜色为 $l,l+1,\cdots r-1,r$ 的团子。清兰将这些团子**依次**入栈。也就是在栈顶依次加入 $l,l+1,l+2,\cdots r-1,r$ 。
2. $\colorbox{f0f0f0}{\verb!2 k!}$ ：有一位客人想要购买 $k$ 个团子。此时清兰会**依次**从栈顶取出 $k$ 个团子并售出。保证 $k$ 不大于当前栈内的团子个数。

你要做的，就是对于每个操作 $2$ 输出这些团子的总价格。

inputFormat:
第一行有一个整数 $n$，表示操作的个数。
接下来 $n$ 行描述一组询问。第一个整数 $op$ 表示询问的种类，若为 $1$ 则为操作 $1$，为 $2$ 则为操作 $2$。

- 对于操作 $1$，接下来有两个整数 $l,r$，含义如题面所示。
- 对于操作 $2$，接下来有一个整数 $k$，含义如题面所示。

outputFormat: 若干行。对于每次操作 $2$，输出这些团子的售价之和。

hint:
样例 $2$ 见下发的附件 $\textbf{\textit{stack2.in}/\textit{stack2.out}}$。

---

### 数据范围

- 对于前 $30\%$ 的数据，$n,l,r\le100$。
- 对于另外 $20\%$ 的数据，$l=r$。
- 对于另外 $20\%$ 的数据，$k\le 10$。
- 对于 $100\%$ 的数据，$1\le n\le 5\times 10^5$，$0\le l\le r \le 10^6$，$1\le k \le 10^{12}$。


title: C 图上的数

description:
给定一个 $n$ 个点 $m$ 条边的无向图（**保证无重边无自环但不保证连通**），每条边有一个 $1\sim m$ 的互不相同的编号。

定义一条边是孤边，当且仅当它的两端点均已经被删除。

您需要给定一个删点顺序，令 $P_i$ 表示第 $i$ 条变成孤边的边的编号，您需要最小化 $P_i$ 的字典序。

若某一时刻存在多条边变为孤边，我们认为，编号小的边先变为孤边。

inputFormat:
第一行两个正整数 $n,m$，表示图的点数和边数。

第 $2\sim m+1$ 行，第 $i$ 行两个正整数 $x,y$，表示编号为 $i-1$ 的边的两个端点。

outputFormat: 为减少输出量，请输出 $\bigoplus\limits_{i=1}^{m}i\times P_i$，其中 $\bigoplus$ 表示二进制下的按位异或。

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

数组 $P$ 为 $\{1,3,4,6,8,2,5,7\}$。

**【数据范围】**

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

所有数据满足 $1\le n\le 10^6$，$1\le m\le \min (10^6,\frac{n(n-1)}{2})$。详细数据范围如下：

- Subtask #1 (12 pts): $n,m\le 10$。
- Subtask #2 (17 pts): $n,m\le 100$。
- Subtask #3 (11 pts): $n,m\le 5\times 10^3$。
- Subtask #4 (18 pts): $m=n-1$，图连通，所有点度数不超过 $2$。
- Subtask #5 (16 pts): $m=\dfrac{n(n-1)}{2}$。
- Subtask #6 (15 pts): $n,m\le 10^5$。
- Subtask #7 (11 pts): 没有任何附加限制。


title: 「Wdoi-4」使用三个系统程度的能力

background:
**勘误**：事实上，自从 $2001$ 年发布的 $\text{MacOS X}$ 之后换行符都变成了 $\verb!\n!$。网上发布的很多文章都存在谬误，当时出题人也没实地考察就信了。为了防止谣言继续传播，就在这里放了这段话。数据仍然以目前的题目描述为准，未做更改。

---

赫卡提亚·拉碧斯拉祖利是拥有三副身体，司掌月球、地球、异界三界地狱的神明。由于与纯狐结盟的缘故，赫卡提亚接触到了幻想乡，以及其他的一些现代科技。

赫卡提亚发现，在人类社会中存在三个非常通用流行的操作系统，也就是 $\text{Windows}$、$\text{Linux}$ 和 $\text{Mac}$。这三者就像是赫卡提亚本人的三个身体般，分别占据了很大的市场。

但是赫卡提亚又发现，尽管这三个系统之间的文件可以通过一些方式进行信息流通，可是毕竟存在一些区别：例如换行方面采用的字符的不同。赫卡提亚对此非常感兴趣。

现在赫卡提亚不知道从哪里搞来了一个系统的文本文件，她想知道这个文件是在哪个系统里编辑而成的。你能写个程序帮帮她吗？

description:
在 $\text{Windows}$、$\text{Linux}$ 和 $\text{Mac}$ 系统下，分别采用了三种不同的换行符方式。表示为显式转义符，分别是 $\verb!\r\n!$、$\verb!\n!$ 和 $\verb!\r!$ 。现在有一份已经写好了的非空文本文件（里面仅由大小写英文字母、下划线、阿拉伯数字、空格，以及换行符组成）。这个文本文件是在单一系统中写成的，因此保证换行符只会出现上述三种情况**之一**。

比如，这是一个合法的文本文件：

```plain
SCP2021 J rp plus plus
chen zhe AK IOI

Welcome to Hell
```

现在将其中的换行变为对应的转义符。那么在上述三个系统中，分别会变为以下三种模样：

- $\text{Windows}$ 系统：

$$\colorbox{f5f5f5}{\verb!SCP2021 J rp plus plus\r\nchen zhe AK IOI\r\n\r\nWelcome to Hell!}$$

- $\text{Linux}$ 系统：

$$\colorbox{f5f5f5}{\verb!SCP2021 J rp plus plus\nchen zhe AK IOI\n\nWelcome to Hell!\kern{31.5pt}}$$

- $\text{Mac}$ 系统：

$$\colorbox{f5f5f5}{\verb!SCP2021 J rp plus plus\rchen zhe AK IOI\r\rWelcome to Hell!\kern{31.5pt}}$$

---

现在你被给定的任务是，根据转换后的文本文件，判断这是哪个系统下编写的文本文件。对于上述三种情况，分别输出 `windows`、`linux` 或 `mac`。

inputFormat: 输入共一行，为转换后的文本文件。保证文本文件非空，且转换前至少有一个换行符。**输入可能包含空格。**

outputFormat: 输出一行一个小写单词，输出此文本文件在哪个系统下编写。

samples:
chen_zhe AK IOI\r\nchen_zhe AK NOI\r\n
windows

samples: include iostream\rsigned main return 0\r

hint:
样例 $4$ 见下发的附件 $\textbf{\textit{system4.in}/\textit{system4.out}}$。

#### 数据范围

- 对于 $40\%$ 的数据，保证不存在空格。
- 对于 $100\%$ 的数据，保证输入字符串的长度 $\le 10^5$。输入中仅包含大写英文字母、小写英文字母、下划线、数字、空格和转义字符（`\r`、`\n`）。

#### 注意

本题中的 `\n` 及 `\r` 表示直接写在输入里的一个反斜杠符号跟着一个小写字母 `n` 或 `r`，而不是一个**真正的**转义字符。


title: 『JROI-3』Moke 的游戏

description:
Moke 是一个喜欢玩游戏的男孩子。

众所周知，游戏应当有血量。血量**永远是非负整数**，如果在某个时刻血量将要变为负数，那么游戏会崩溃，这就不算作一种游戏局面。这里允许血量是 $0$。
一般来说，友好的游戏都会具有一定的初始血量。但是 Moke 是一个喜欢在游戏里受虐的男孩子。所以他把自己的初始血量设成了 $0$。

不过，这个游戏的难度并不高。
它一共进行 $n+1$ 个时刻。初始是第 $0$ 个时刻，最终是第 $n$ 个时刻。每个时刻 Moke 会遇到以下三种事件，然后进入下一时刻：

 1. 空地。它使得 Moke 的血量不变。一共有 $a_0$ 种不同的空地。
 2. 怪兽。它使得 Moke 的血量减一。一共有 $a_{-1}$ 种不同的怪兽。
 3. 道具。它使得 Moke 的血量增加一个正整数。具体地，一共有 $a_p$ 种使 Moke 血量加 $p$ 的道具，其中 $p \in \mathbb Z^+$。

为了不让游戏太复杂，游戏的开发者保证 $\big|\{p \mid p \in \mathbb Z^+ \land a_p > 0\}\big|=k$。即，所有道具总共只造成恰好 $k$ 种不同的血量变化量。

当然，Moke 还是给自己进一步增加了难度。他要求结束时自己的血量为 $0$，且给出一个正整数 $m$，表示限制这 $n+1$ 个时刻中，他恰好有 $m$ 次血量为 $0$（包括初始时刻）。

请求出所有不同的，符合 Moke 限制的游戏局面个数。两个局面不同当且仅当每个时刻遇到的事件的种类不同（包括不同的空地、不同的怪兽和不同的道具）。

Moke 不希望你面对太困难的问题。所以他给出一个质数 $P=10^9+7$ 并只要求你给出取模 $P$ 后的答案。

inputFormat:
第一行，三个正整数 $n,m,k$。
第二行，两个正整数 $a_0,a_{-1}$。
以下 $k$ 行，其中第 $i$ 行两个正整数 $p_i,a_{p_i}$。表示存在道具造成的血量变化量为 $p_i$，且这样的道具有 $a_{p_i}$ 种。

outputFormat: 一行，一个非负整数。表示答案取模 $P$ 的结果。


title: 「LCOI2022」 Cow Insertion

background: Farmer John 迎来了新奶牛——Bessie。每个奶牛都会有一定的开心值，Farmer John 希望 Bessie 能更幸福的生活在这里。

description:
牛棚里原来有 $n$ 头奶牛，开心值的感染距离 $m$，并且 $a_i$ 表示原来牛棚中第 $i(1\le i\le n)$ 头牛的开心值。并且，Bessie 同样拥有一个开心值 $A$。

整个牛棚的开心值是 $\sum\limits_{i=1}^{n-m+1}\ \max\limits_{i\le j\le i+m-1}\ a_j$，Bessie 可以住在任意两头牛的中间或起始以及最后。Farmer John 想知道：Bessie 来这里之后，整个牛棚的开心值最大为多少。

inputFormat:
第一行包含三个整数 $n,m,A$。分别表示为奶牛个数，开心值的感染距离，以及 Bessie 的开心值。

接下来一行，包含 $n$ 个数 $a_i$，表示原来牛棚中第 $i(1\le i\le n)$ 头牛的开心值。

outputFormat: 仅一行，表示 Bessie 来这里之后，整个牛棚的开心值的最大值。


title: 「PMOI-0」假·儒略日

background:
（原 LZOI-1，改名已经 PMOI 成员同意）

Lanuxhem 听说 言琢დ 在 S-PSC 考场上就切穿了 **儒略の日**，想得到 言琢დ 手中的考场 AC 代码。

但是 言琢დ 不想给他，所以 言琢დ 就扔给了 Lanuxhem 下面这题，并说：“切了这道题就给你。”

lhm-02

description:
给定一个正整数 $n$ 和另一个正整数 $d$。

要求构造一个长度为 $2n$ 的数列 $\{a_{2n}\}$，满足：

1. $1\sim n$ 之中每个数字均出现 $2$ 次。
2. 对于数字 $i$，若 $i$ 为奇数，则数字 $i$ 两次出现位置之差 **必须** 超过 $d$。
3. 对于数字 $i$，若 $i$ 为偶数，则数字 $i$ 两次出现位置之差 **不能** 超过 $d$。

由于 Lanuxhem 想得到 言琢დ 的代码，但他并不会这道题，所以他只能请聪明的你帮他完成这题。

inputFormat: 第一行输入两个整数 $n$ 和 $d$。

outputFormat:
如果无解输出 `-1`，否则输出一个长度为 $2n$ 的数列表示你的答案。

**如果有多组解输出任意一组均给分。**


title: [ZYOI Round1] Truth/真心话大冒险

background:
**注意：请勿恶意提交代码，浪费评测资源。**

一群人参加了聚会，在玩“真心话大冒险”。

description:
Charlie 现在盯上了一个人 Percy，Ta 打算找出 Percy 对于 $n$ 个异性的好感度的排名。

具体地，Charlie 可以提出两种要求：

1. 【真心话】给定 $3$ 个正整数 $x,y,z$，要求 Percy 回答其中他第二喜欢的异性的编号。要求：$1 \leq x,y,z \leq n$。

2. 【大冒险】给定 $2$ 个正整数 $x,y$，要求 Percy 拥抱其中他更喜欢的那个异性。要求：$1 \leq x,y \leq n$ 且必须保证异性 $x,y$ 之中必有一个是 Percy 最喜欢的。

Charlie 希望通过至多 $2 \times 10^6$ 次询问达到他的目的。

**交互格式：**

一开始读入一个正整数 $n$ 开始交互。

你可以输出 $3$ 种信息：

1. `1 x y z`，表示“真心话”询问，并读入结果。
2. `2 x y`，表示“大冒险”询问，并读入结果。
3. `3 a1 a2 ... an`，表示你已经得出了答案，按顺序输出 Percy 最喜欢、第二喜欢、……的异性的编号。

inputFormat: （见题目描述）

outputFormat: （见题目描述）

hint:
**以上输入输出只是为了演示交互格式，可能并不符合逻辑**。

对于 $20\%$ 的数据，$1 \leq n \leq 10$。

对于 $40\%$ 的数据，$1 \leq n \leq 100$。

对于 $60\%$ 的数据，$1 \leq n \leq 10^3$。

对于 $80\%$ 的数据，$1 \leq n \leq 10^4$。

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^4$。

注意输出不合法可能导致 WA/RE/TLE/MLE 等玄学问题。


title: 『JROI-3』1÷0

background:
```
1÷0=梦恋
```
```
   在距离遥远的山丘上，看得见彼方宛如天地崩毁的光景。

    「——『设计体』传来报告——以功率《七二·八％》重现设计成功——开始同步。」

    一机机凯种的女性体这么告知里克，然后举起手。

    「【典开】——Org.0000——『真典·弑星者』——拜托您了。」

    ——出现在虚空中的是，外形有如小型的塔，刺在地上的一把枪。

    方才目睹的，有如让世界终结的暴力漩涡。

```

description:
空想用跳棋模拟「圣战」中机凯种的移动方式。

一条**无限长**的数轴上有 $n$ 个不能动的跳棋，空会询问把一颗可以动的跳棋放在一个位置可以**最多**进行几次跳跃。空会问很多次，每次询问**互相独立**。

设第 $i$ 颗不能动的棋子的坐标为 $x_i\left(\forall i\in\left[1,n\right]\right)$.

则跳棋移动的规则如下：

- 这颗跳棋必须是允许移动的。
- 若这颗棋子位于 $a$，目标位置为 $b$，则应**仅有一颗**棋子位于二个位置之间且中间棋子到 $a,b$ 的距离相等。

形式化的讲应有：

$$\sum_{k=1}^n \left[x_k\in\left[b,a\right]\right]=1$$

且 $\exists k\ x_k=\dfrac{a+b}{2}$.

- 出题人过于良心（，你只能向左边跳。

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

接下来一行 $n$ 个整数，第 $i$ 个表示 $x_i$。

接下来一行 $q$ 个数 $x_0$，表示放置可以动的棋子的位置。

outputFormat: $q$ 行，每行一个整数，第 $i$ 行表示第 $i$ 次询问的结果。

hint:
#### 样例解释 1

$$\Huge\Box\Box\blacksquare{\color{red}{\Box}}\blacksquare{\color{red}{\Box}}{\color{red}{\Box}}\blacksquare\Box\Box$$

从左到右的三个红色方块是询问的位置。

- 对于第一个询问，可以跳 $1$ 步，从 4 跳到 2。
- 对于第二个询问，可以跳 $2$ 步，从 6 跳到 4 跳到 2。
- 对于第三个询问，棋子不能向左移动，因为左边同距离位置有一颗不能动的棋子。

对于 $100\%$ 的数据满足 $1\le n\leq 3\times 10^6$，$1\le q\leq3\times 10^5$，$1\le x\le 10^{18}$，$x_i+1\lt x_{i+1}(\forall i \in [1,n-1])$。

| Subtask 编号 | $n\le$ | $q\le$ | 时限 | 空间限制 | 特殊限制 |
| :-----------: | :-----: | :---: | :--: | :------:| :------: |
| Subtask 0 (10 pts) | $10^3$ | $10^3$ |  $1000\ \rm\small ms$ | $\rm512.00\small\  MB$ |  |
| Subtask 1 (30 pts) |  |  | $1000\ \rm\small ms$ | $\rm512.00\small\  MB$ | $\rm A$|
| Subtask 2 (25 pts) |  |  | $1000\ \rm\small ms$ | $\rm512.00\small\  MB$ | $\rm B$ |
| Subtask 3 (25 pts) | $3 \times 10^5$ |  | $400\ \rm\small ms$ | $\rm512.00\small\  MB$ |
| Subtask 4 (10 pts) |  |  | $400\ \rm\small ms$ | $\rm512.00\small\  MB$ |

- 限制 $\text{A}$： $x_n\le2\times 10^5$。
- 限制 $\text{B}$：有不超过 $50$ 个 $i$ 不满足 $x_i-x_{i-1}\le 100$ ，其余 $i$ 满足 $\sum_{i}{x_i-x_{i-1}} \le 2\times 10^5$。


title: [Cnoi2021] 幻想乡程序设计大赛

background:
幻想乡，春。

新年的土地吐出稚嫩的幼芽，第一届幻想乡程序设计大赛(Inner-Gensokyo Programming Contest, IGPC)拉开帷幕。作为举办者， Cirno 却有些不得不考虑的事情。

那就是气球的分配问题。

description:
本场比赛共有 $n$ 道题，Cirno 已经精确预测了每道题目的 AC 队伍数 $a_1,a_2,a_3,\cdots,a_n$。但由于经费限制，主办方 $n$ 种颜色的气球分别只准备了 $b_1,b_2,b_3,\cdots,b_n$ 个。

而 Cirno 需要合理地安排每道题目对应的气球颜色，使得能派发的气球尽可能多。

显然地，每道题目只能对应一种颜色的气球，每种颜色的气球只能对应一道题目，如果一道题有队伍通过但该种颜色的气球已经发完了，则很遗憾，该队拿不到这种气球了。

由于这个问题过于 trival，于是 Cirno 决定将这个任务分配给你。

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

第二行，$n$ 个整数，用空格隔开，表示 $\{a_n\}$。

第三行，$n$ 个整数，用空格隔开，表示 $\{b_n\}$。

outputFormat: 一行，一个整数，表示最多能派发的气球数。

hint:
**数据范围与约定**

对于 $100\%$ 的数据保证 $1 \le n \le 10^5$，$0 \le a_i,b_i \le 10^4$，且 $\{a_n\},\{b_n\}$ 单调不降。

**子任务**

Subtask1（$60$ points）：$n \le 8$。

Subtask2（$40$ points）：无特殊限制。


title: 「Wdoi-4」觉姐姐和恋妹妹

background:
古明地觉和古明地恋是居住在地灵殿的觉妖怪。古明地觉拥有读心程度的能力，但她的妹妹古明地恋却不具备读心能力。

地灵殿是旧地狱上层的极为空旷的大型别墅建筑。正因如此，古明地恋经常在地灵殿里探索新奇好玩的东西。地灵殿可以被划分出好多好多的房间，每个房间里都有一个装饰物。在古明地恋眼里，每个装饰物都有一个新奇程度（特别地，新奇程度可能为负数，代表恋恋觉得这个物件非常枯燥无味）。

喜欢闲逛的古明地恋，有一天想要探索整个地灵殿。作为姐姐的古明地觉，自然不希望恋恋会失望。也就是说，古明地觉可以通过搬运房间内的物件，移动到新的房间里，来提升恋恋整个游览过程的愉悦程度（即恋恋看到的所有物件的新奇程度之和）。

然而，古明地觉向来是不擅长运动的，因此她不会走很长的路。你现在要做的，就是告诉古明地觉，经过她的清理后，恋恋最多可以获得的愉悦程度的最大值。

description:
地灵殿可以看作有一个有 $n\times m$ 间房间组成的矩阵，我们用 $(x,y)$ 描述一个房间的位置。其中，位于 $(i,j)$ 的房间里拥有的物件的新奇程度为 $w_{i,j}$，用一个整数表示（可能为负数）。古明地恋的愉悦度被定义为她看到的所有物件的新奇程度之和。

打扫房间的古明地觉，将会从 $(1,1)$ 走到 $(x_s,y_s)$ 。期间，古明地觉**只能走到下侧或者右侧的房间**（假设古明地觉当前在 $(i,j)$，那么她下一步只能走到 $(i+1,j)$ 或者 $(i,j+1)$，并且她不会走出地灵殿）。古明地觉走到一个房间时，可以**捡起房间内的物件**放入背包；她也可以**从背包里取出任意若干件物件**放在该房间（可以既捡起物品又放置物品）。当然，古明地觉不希望带出地灵殿里的物件，因此**结束打扫时，觉的背包里应该没有物件**。初始时，背包为空。

接下来，古明地恋将会从 $(1,1)$ 走到 $(x_k,y_k)$，进行自己的旅行。古明地恋将会看到一个房间里**所有的**物件，并且取得相应的新奇程度。和古明地觉相同，古明地恋**同样**只会向下侧或者右侧的房间行走。

古明地觉想知道，按照这样的规则，恋恋最终得到的愉悦程度最大是多少。

inputFormat:
第一行有两个正整数 $n,m$，描述地灵殿房间的规模。
接下来 $n$ 行，每行有 $m$ 个整数，其中第 $i$ 行第 $j$ 个整数 $w_{i,j}$ 描述房间 $(i,j)$ 内的物件的新奇程度。
接下来一行，输入四个正整数，依次为 $x_s,y_s,x_k,y_k$，意义同题目描述，代表觉与恋的终止位置。

outputFormat: 输出一行，表示该组数据下古明地恋可以取得的最大愉悦程度。


title: [Cnoi2021] 自我主义的平衡者

background:
「流浪月球 ~ The Wandering Moon」在幻想乡上映了。

正如一千个人心中有一千个哈姆雷特，关于它的争议也在悄然蔓延。

不知何时起，一个叫做「花瓣」的平台出现，慢慢取代了市井之中的讨论声，成为了争议的主战场——因为它具有评分功能。平台上旁征博引、各抒己见的评分帖成为了幻想乡的居民们日常，一切看起来岁月静好。

直到平衡者的出现。

起初没有人在意在意这缕杂音，这只不过是一种无心的叛逆，一点无奈的情感，一次无聊的宣泄。直到平衡的思想深入人心，自我主义的狂潮达到顶峰，评分系统的秩序几近崩溃。

Cirno 觉得自己该做些什么了。

description:
Cirno 决定通过计算来说服与拯救被自我主义裹挟的众人。

参与评分的共有 $n$ 位居民，平台限制的最高分为 $m$。

每个居民在评分前都有一个心理预期分数 $a_i(a_i\in[0,m]\cap\mathbb{Z})$。

但人们并不会按照心理预期分数直接评分，而是当当前平台上的平均分严格高于自己的心理预期分数时，便评分道「分数太高了，打个 $0$ 分平衡一下」，反之则说「分数太低了，打个满分（$m$分）平衡一下」。

初始时平台上的平均分为 $0$。

为了证明这种评分方式对公平的破坏性，Cirno 希望你计算出这 $n$ 位居民在不同的排列顺序下评分，平台上最终平均分可能的最大值与最小值。

inputFormat:
第一行，两个整数，用空格隔开，表示 $n$，$m$。

第二行，$n$ 个整数，用空格隔开，表示 $\{a_n\}$。

outputFormat: 一行，两个实数，保留两位小数，分别表示平均分最大值和最小值。

hint:
**数据范围与约定**

对于 $100\%$ 的数据保证，$1 < n,m\le 10^5$，$a_i \in [0,m]$。

**子任务**

Subtask1（10 points）：$n \le 8$。

Subtask2（10 points）：$n \le 20$。

Subtask3（30 points）：$n \le 10^3$。

Subtask4（50 points）：无特殊限制。


title: 「RdOI R3.5」RMSQ

description:
给出一个长度为 $m$ 的**排列** $b$ 和一个长度为 $n$ 的**序列** $a$。

如果一个序列 $S$，满足其按位置从左到右依次匹配 $b$ 的一个区间从左到右的位置，那么我们说 $S$ 是一个「优美序列」。

给出 $q$ 次询问。每次询问给出两个整数 $l$ 和 $r$。你需要找到一个 $a$ 的 $[l,r]$ 子区间中的一个最长的满足「优美序列」条件的子序列长度。注意子序列可以不连续。

inputFormat:
- 第一行输入四个整数 $m,n,q,T$，其中 $n,m,q$ 的含义见「题目描述」，$T$ 表示是否强制在线。
- 第二行输入 $m$ 个整数 $b_1,b_2,\cdots,b_m$。
- 第三行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$。
- 接下来 $q$ 行每行输入两个整数 $l',r'$。若 $T=1$，则你需要将 $l'$ 和 $r'$ 按位异或 $\mathit{lastans}$ 来得到真正的 $l,r$。其定义为上一次询问操作得到的答案，若之前没有询问操作，则为 $0$。否则若 $T=0$，则 $l=l',r=r'$。

outputFormat:
- 输出共 $q$ 行。
- 第 $i$ 行输出一个整数，表示第 $i$ 次询问的答案。

hint:
### 样例解释

$\mathit{lastans}$ 解密后的询问为：

```plain
1 3
1 4
2 4
2 5
2 6
1 6
```

### 数据范围

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|c|} \hline
\textbf{Subtask} & \textbf{分值} & \bm{{n,m\le}} &\bm{{q\le}} & \bm{{T=}} & \textbf{特殊性质} & \textbf{Subtask 依赖}\cr\hline
1 & 10 & 100 & 10^4 & 1 & \textbf{A} & -\cr\hline
2 & 15 & 10^5 & 10^5 & 1 & \textbf{A} & 1\cr\hline
3 & 30 & 3\times 10^5 & 10^6 & 0 & - & -\cr\hline
4 & 45 & 3\times 10^5 & 10^6 & 1 & - & 2,3\cr\hline
\end{array}
$$

- 特殊性质 $\textbf{A}$：保证 $a_i,b_i,l,r$ 在数据范围内均匀随机。

对于 $100\%$ 的数据，$1\le l\le r\le n\le 3\times 10^5$，$1\le a_i\le m\le 3\times 10^5$，$1\le q \le 1\times 10^6$，$T \in \{0,1\}$。


title: [JRKSJ R3] practiceZ

description:
琴琴给了你两个长为 $n$ 的序列 $a,b$，请你支持三种操作共 $m$ 次：

1. `1 l r x`，将 $a$ 序列的区间 $[l,r]$ 中的所有数修改为 $x$。
2. `2 l r y`，将 $b$ 序列的区间 $[l,r]$ 中的所有数修改为 $y$。
3. `3 l r`，求 $\sum_{i=l}^r \sum_{j=1}^{b_i} a_j$。答案对 $2^{32}$ 取模。

inputFormat:
输入均为整数。

第 $1$ 行 $2$ 个数 $n,m$。\
第 $2$ 行 $n$ 个数表示序列 $a$。\
第 $3$ 行 $n$ 个数表示序列 $b$。\
接下来 $m$ 行，每行一个操作，格式见题目描述。

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

tags: 珂朵莉树,颜色段均摊,ODT


title: [CoE R4 B/Stoi2041] 龙拳

description:
对于 $n \in \mathbb{Z_{\ge 2}}$，设 $g(n)$ 为 $n$ 的小于 $n$ 的最大约数，如 $g(7) = 1, g(12) = 6$。

定义 $f(n) = n + g(n)$。记 $f^{(0)}(n)=n$，且对 $m \in \mathbb{Z_{\ge 0}}$ 有 $f^{(m+1)}(n)=f(f^{(m)}(n))$。

多次询问，每次询问给定正整数 $n,k$，求最小的自然数 $m_0$，使得对于任意 $m \ge m_0$，均有 $f^{(m)}(n) \mid f^{(m+k)}(n)$。

若不存在这样的 $m_0$，则令 $m_0=-1$。

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

接下来 $T$ 行，每行两个正整数 $n,k$，表示一次询问。

outputFormat: 对于每组询问输出一个整数表示答案。


title: 「EZEC-11」雪的魔法

background:
Muxii 是一个雪魔法师。只要他挥起魔法棒，念出神秘的咒语，雪花就会从天而降，在地面上一点一点地积累起厚厚的雪层。正因 Muxii 魔力高超，上帝任命 Muxii 掌管整个世界的雪。

某天，上帝给 Muxii 下达了一个任务：他需要让一个长为 $n$ 的地面上下雪。其中，第 $i$ 个位置的积雪厚度需要达到 $a_i$（$a_i\ge0$，“达到 $a_i$” 指不能低于也不能超过 $a_i$）。然而，上帝不知道的是，Muxii 的能力有限，他每次施法只能让长度 $\le m$ 的区间内下雪 1s，使得这个区间内的积雪厚度增加 $1$。由于任务急迫，Muxii 想要知道，若要完成某些区间的任务，他至少要施法多少次。

description:
定义初始数列为每个数字都为 $0$ 的数列。

定义一次操作为将数列的一个区间中每一个数的值增加 $1$，规定该区间的长度不能超过 $m$。

给定一个长度为 $n$ 的数列 $a$，第 $i$ 个数为 $a_i$。

你需要回答 $q$ 次询问。每次询问给定 $l,r$，你需要回答将一个长度为 $r-l+1$ 的初始数列变为 $a$ 中的 $[l,r]$（即数列 $a_l$, $a_{l+1}$, $\cdots$, $a_r$）至少需要多少次操作。

inputFormat:
第一行三个整数 $n,m,q$。

第二行 $n$ 个整数，第 $i$ 个为 $a_i$。

接下来 $q$ 行，每行两个整数，表示 $l,r$。

outputFormat: $q$ 行，每行一个整数，表示至少需要的操作次数。

hint:
**「样例 1 说明」**

一个长度为 $5$ 的初始数列为 $0$ $0$ $0$ $0$ $0$。

第一次操作为，将区间 $[1,3]$ 中每一个数，即第 $1$、$2$、$3$ 个数的值分别增加 $1$。经过该操作后，数列变为  $1$ $1$ $1$ $0$ $0$。

第二次操作为，将区间 $[3,5]$ 中每一个数，即第 $3$、$4$、$5$ 个数的值分别增加 $1$。经过该操作后，数列变为  $1$ $1$ $2$ $1$ $1$。

**「数据范围与约定」**

- Subtask 1（1 point）：$m=1$。
- Subtask 2（4 points）：$m=n$。
- Subtask 3（10 points）：$n,q\le300$。
- Subtask 4（10 points）：$n,q\le5\times10^3$。
- Subtask 5（15 points）：$m\le5$。
- Subtask 6（15 points）：$m\le100$。
- Subtask 7（20 points）：$n,q\le5\times10^4$。
- Subtask 8（25 points）：无特殊限制。

对于 $100\%$ 的数据，保证 $1\le m\le n\le10^5$，$1\le q\le10^5$，$0\le a_i\le10^9$，$1\le l\le r\le n$。


title: [Kubic] Pyramid

background:
容易发现，F 题出题人不是 lxl。

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

description:
给定一个初始长度为 $n$ 的序列 $p$。

设当前 $p$ 的长度为 $L$，有以下两种操作：

- A 操作先构造长度为 $L-1$ 的序列 $p'$ 满足 $p_i'=\min\{p_i,p_{i+1}\},i\in [1,L)$。然后用 $p'$ 代替 $p$。

- B 操作先构造长度为 $L-1$ 的序列 $p'$ 满足 $p_i'=\max\{p_i,p_{i+1}\},i\in [1,L)$。然后用 $p'$ 代替 $p$。

再给定一个长度为 $m$ 的序列 $a$，表示一共进行 $m$ 组操作，第 $i$ 组中先进行 $a_i$ 次 A 操作，再进行 $a_i$ 次 B 操作。保证 $2\sum a_i=n-1$。

最后给定 $q$ 次询问，每次给出参数 $x,l,r$，你需要求出进行前 $x$ 个操作之后 $\sum\limits_{i=l}^r p_i$ 的值。

**注意：询问中的 $x$ 指的是前 $x$ 个操作而不是前 $x$ 组操作，即有可能在某一组操作进行一部分时询问。**

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

第二行，$n$ 个整数，第 $i$ 个整数表示 $p_i$。

第三行，$m$ 个整数，第 $i$ 个整数表示 $a_i$。

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

outputFormat: 共 $q$ 行，每行一个整数，第 $i$ 行的整数表示第 $i$ 次询问的答案。

hint:
对于 $100\%$ 的数据，$1\le n,m,q\le 1.5\times 10^5,1\le x<n,1\le l\le r\le n-x,1\le p_i\le 10^9,2\sum a_i=n-1$。

||分值|时限 $(\operatorname{s})$|$n$|$m$|$q$|特殊性质|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|$\operatorname{Subtask}1$|$5$|$1$|$\le 100$|$\le 100$|$\le 100$|无|
|$\operatorname{Subtask}2$|$10$|$1$|无特殊限制|无特殊限制|无特殊限制|AB|
|$\operatorname{Subtask}3$|$15$|$5$|无特殊限制|无特殊限制|无特殊限制|B|
|$\operatorname{Subtask}4$|$15$|$1$|无特殊限制|$=1$|无特殊限制|C|
|$\operatorname{Subtask}5$|$15$|$1$|无特殊限制|$=1$|无特殊限制|无|
|$\operatorname{Subtask}6$|$20$|$4$|无特殊限制|$\le 50$|无特殊限制|无|
|$\operatorname{Subtask}7$|$20$|$5$|无特殊限制|无特殊限制|无特殊限制|无|

特殊性质 A：$\forall i,a_i=1$

特殊性质 B：$l=r$。

特殊性质 C：$l=1,r=n-x$。

### 样例解释

给定的操作过程如下：

`6 2 4 1 3`

`2 2 1 1`

`2 2 1`

`2 1`

`2`

~~特殊性质单独拉出来写只是为了表格好看一点...~~

感谢 $\operatorname{A\color{red}lfalfa\_w}$ 对本题的贡献！


title: 兜心の顶

background:
Source：[八仙敬酒](/paste/78f1vlm0)，这是可以点的。

- 吕洞宾——醉酒提壶力千钧；
- 铁拐李——旋肘膝撞醉还真；
- **汉钟离——跌步抱坛兜心顶**；
- 蓝采和——单提敬酒拦腰破；
- 张果老——醉酒抛杯踢连环；
- 曹国舅——仙人敬酒锁喉扣；
- 韩湘子——擒腕击胸醉吹箫；
- 何仙姑——弹腰献酒醉荡步。

description:
给定正整数 $n$，要求构造一棵 $n$ 个结点的树，满足树的直径的重心 **不是** 树的重心。

同时这棵树需满足：直径$^1$、重心$^2$、直径的重心$^3$全部唯一。

---

注：

- 树的直径$^1$：[https://oi-wiki.org/graph/tree-diameter/](https://oi-wiki.org/graph/tree-diameter/)
- 树的重心$^2$：[https://oi-wiki.org/graph/tree-centroid/](https://oi-wiki.org/graph/tree-centroid/)
- 树的直径的重心$^3$：将树的直径（一条链）视作一棵树，求其中心（一个点）。

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

outputFormat:
第一行输出一个正整数 $n$。

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

无解输出 `-1`。

**本题采取 Special Judge，输出任意一组合法解均给分。**


title: 「Wdoi-5」樱点收集

background:
119 季 5 月，明明本应是樱花盛开的春天，幻想乡却依然下着大雪。异变的主谋**西行寺幽幽子**在古书上看到，只要使妖樱西行妖满开便会有什么人复活，便出于兴趣命令妖梦收集幻想乡中的春度，一手策划成了这场异变。在收集春度的过程中散落的能量在西行妖的影响下化为**樱点**，散落在幻想乡各处。

出发解决**春雪异变**的灵梦将前往冥界旅途划分为了若干段，每一段都可以收集到一定的樱点。收集齐一定程度的樱点，就会立即开出樱之结界。开出樱之结界后可以短暂地屏蔽一切攻击，并且获得相应的增益。

但是樱之结界何时开放仅由樱点的收集情况所决定，她不得不对樱点进行「规划」。通过某些途径规避某一段路上樱点的收集，借此使得在将来的某几段路程里，灵梦得以恰好在该段的末尾开放樱之结界。

但是现实往往不尽人意。也就是说，可能有某些要求无法达成。灵梦希望找出一个方案，使得她可以达成的要求最多。灵梦委托八云紫帮忙决策，于是这个重任就被一条懒紫交给了式神八云蓝。尽管八云蓝擅长计算，但是八云紫睡觉去了没有给她编程，因而现在这个任务就落到了你的手上。

description:
灵梦当前拥有的樱点可以使用一个**变量** $c$ 存储，初始时为 $0$。当樱点在某个瞬间**恰好**变为了 $k$，灵梦就会展开樱之结界，同时 $c$ 变为 $0$。

现在她把路程**依次**划分为了 $n$ 个关卡，其中第 $i$ 关上，灵梦一共可以获得 $a_i$ 点樱点。这些樱点是均匀分布在这关的路程上的。也就是说，随着这段路程的进行，灵梦的樱点个数会依次增加，每次增加 $1$ 个单位（$c\gets c+1$），恰好在这段路程结束的瞬间会收集到这关中第 $a_i$ 点樱点。

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

**【需要注意的是，这只是图示参考，不满足实际的数据限制。】**

在这个例子里，灵梦将路径划分为了四个关卡。这四个关卡的樱点个数分别为 $2,0,3,1$。

灵梦提出了 $m$ 个要求。第 $i$ 个要求 $b_i$ 表示灵梦希望在第 $b_i$ 段路程结束的瞬间，**恰好**展开樱之结界（如果在这段路程的中途展开但是结束的瞬间没有展开，那就不算达成了要求）。

灵梦可以选择在某个关卡开头放 bomb，**跳过**整个关卡的樱点收集。这样的机会**有且仅有**一次（当然，灵梦可以选择不使用 bomb）。

现在需要求出，在最优的选择下，灵梦**最多**可以达成多少个要求。

inputFormat:
- 第一行共有三个整数 $n,m,k$，分别表示关卡数、要求个数，以及常量 $k$。
- 第二行 $m$ 个整数 $b_1,b_2,\cdots b_m$，描述了灵梦的 $m$ 个要求。**保证 $\bm{b_i}$ 单调递增**。
- 第三行 $n$ 个整数 $a_1,a_2,\cdots a_n$，描述了第 $i$ 关可以获得的樱点个数。

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

hint:
样例 $2$ 见下发的附件 $\textbf{\textit{sukura2.in/sakura2.ans}}$。该样例约束与测试点 $1\sim 8$ 一致。
样例 $3$ 见下发的附件 $\textbf{\textit{sukura3.in/sakura3.ans}}$。该样例约束与测试点 $9\sim 14$ 一致。
样例 $4$ 见下发的附件 $\textbf{\textit{sukura4.in/sakura4.ans}}$。该样例约束与测试点 $15\sim 20$ 一致。

#### 样例 1 解释

- 在不使用 bomb 时，灵梦会在第 $2$、$3$ 关开出樱之结界，其中第 $3$ 关在统计序列中，满足要求数为 $1$。
- 在第 $1$ 关使用 bomb，灵梦会在第 $4$ 关开出樱之结界，且第 $4$ 关在统计序列中，满足要求数为 $1$。
- 在第 $2$ 关使用 bomb，灵梦会在第 $4$ 关开出樱之结界，且第 $4$ 关在统计序列中，满足要求数为 $1$。
- 在第 $3$ 关使用 bomb，灵梦会在第 $2$ 关开出樱之结界，且第 $2$ 关不在统计序列中，满足要求数为 $0$。
- 在第 $4$ 关使用 bomb，灵梦会在第 $2$、$3$ 关开出樱之结界，其中第 $3$ 关在序列中，满足要求数为 $1$。

#### 数据范围及约定

本题共有 $20$ 个测试点，每个测试点 $5$ 分。最终分数为所有测试点分数之和。

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{Task} & \bm{n\le } & \bm{k\le} \cr\hline
1\sim 8 & 200 & 10^3 \cr\hline
9\sim 14 & 2\times 10^3 & 10^5 \cr\hline
15\sim 20 & 3\times 10^5 & 10^6 \cr\hline
\end{array}
$$

对于 $100\%$ 的数据，保证 $1\le m\le n\le 3\times 10^5$，$1\le k\le 10^6$，$1\le a_i\le 10^9$，$1 \le b_i \le n$，$b$ 序列递增。


title: 「SvR-2」Let's Meet at a Higher Place

background: $$「有朝一日，让我们相逢在更高处！」$$

description:
构造一个长为 $m$ 的整数序列 $a$，使 $\forall 1 \leq i \leq m$，$a_i \in [1, n]$。

求出其前缀 $\gcd$，记为整数序列 $b$。

$f(n, m, k)$ 的值为可以通过如上方式构造出的 $b$ 序列中**相邻项相等的情况出现次数 $\leq k$** 的**不同**的 $b$ 序列的个数。

给定正整数 $n, m$，小 L 请你帮他求出 $\displaystyle\sum_{i = 1}^n \sum_{j = 1}^m \sum_{k = 0}^{j - 1} f(\lfloor \frac{n}{i} \rfloor, j, k)$ 的值。

由于结果可能很大，所以你只需要求出结果对 $2^{32}$ 取模的值。

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

outputFormat: 一行，一个整数，表示所求的值。


title: 「PMOI-0」一笔画

background: （原 LZOI-1，改名已经 PMOI 成员同意）

description:
言琢დ 在一个 $2n \times 2n$ 的矩阵中坐标为 $(x,y)$ 的一个点上。

现在 lhm 需要任意选择矩阵上的一个点作为起点，然后依次经过 $k$ 个点，移动规则如下：

- 每次移动只能选择与目前相邻（上下左右）的点作为本次移动的目标点。不能选择矩阵外的点。

- 每一轮移动必须正好经过矩阵上的所有点，不能重复经过同一个点。每经过所有点后，视为一轮移动结束。

- 注意依次经过 $k$ 个点后，最后一轮移动可能并没有完成。

现在 lhm 想知道，他最少会经过 言琢დ 多少次。

inputFormat: 第一行输入四个正整数 $n,k,x,y$。

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


title: 「Wdsr-3」蓬莱药局

background:
八意永琳是居住在永远亭的医生。她有着精湛的医术以及大量的医学知识，因而可以制造出各种的药物。

尽管如此，八意永琳常常为新的药物进行试验（包括但不限于对铃仙下手）。不过，八意永琳也开始使用被称为「培养基」一类的东西，培养被称为「细菌」的微小妖怪作为实验材料了。

细菌的分裂能力很强。每一次分裂，细菌的数目都能翻倍。更有意思的是，产生的细菌的子代不一定与亲代相同。换言之，子代细菌会发生变异，从而为永琳的药物实验提供了大量的材料。当然了，细菌太多也是一件苦恼的事情；如果培养基里长满了四处活跃的细菌，那么永琳将不得不采取措施，消灭它们。

在执行一次新的培养之前，永琳希望对细菌上的基因进行一些研究；由于永琳忙着去制药，因此这个任务就交给你了。

description:
为了更方便地描述题意，我们先给出以下定义：

- **子段**：我们定义数组 $B$ 是数组 $A$ 从 $P$ 位置开始的子段，当且仅当 $|A| + P - 1 \le |B|$ 且 $B_1=A_P,B_2=A_{P+1},\dots,B_{|B|}=A_{P+{|B|}-1}$．
- **作为子段的出现次数**：我们定义数组 $B$ 在数组 $A$ 中作为子段的出现次数为：初始设次数为 $0$．枚举每个不同的 $P$，若数组 $B$ 是数组 $A$ 从 $P$ 位置开始的子段，则将次数加一．最后得到的值即为数组 $B$ 在数组 $A$ 中作为子段的出现次数．
- **基因数组**：每个细菌都有一个「基因数组」．它是一个值域为 $[1,k]$ 的整数数组．
- **目标数组**：「目标数组」是一个值域为 $[1,k]$ 的整数数组．在本题中，我们会给定 $m$ 个不同的「目标数组」，第 $i$ 个数组为 $g_i$．
- **目标细菌**：对于一个细菌，记它的「基因数组」为 $X$．我们统计每个「目标数组」$g_1, g_2, \dots, g_m$ 分别在 $X$ 中「作为子段的出现次数」，并将它们求和．若得到的和为 **奇数**，则我们称这个细菌为一个「目标细菌」．
- **基因突变**：「基因突变」是作用于一个细菌的变换．给定一个 $k \times k$ 的突变概率矩阵 $p$．记这个细菌的「基因数组」为 $X$．对于 $x$ 中的每个元素 $X_i$，$X_i$ 会以 $p_{X_i,j}$ 的概率替换为 $j$（$1 \le j \le k$）．根据此定义，显然有 $\forall i \in [1,k], \sum_{i=j}^k p_{i,j}=1$．

一次实验的过程如下：

- 首先在一个空的培养皿中放入一个指定的细菌．
- 在接下来的每分钟，现有的每个细菌会分裂成两个细菌，每个细菌的「基因数组」与原细菌完全相同．分裂之后，每个基因都会进行一次「基因突变」．
- $t$ 分钟后，统计培养皿中「目标细菌」的数量，并结束实验．

现在给定一个长度为 $n$ 的「基因数组」$s$．对于 $s$ 的每个前缀数组 $s[1,1],s[1,2],\dots,s[1,n]$，假设该数组是实验开始时放入的细菌的「基因数组」，请你求出实验结束时得到的「目标细菌」的数量的期望，对 $10^9+7$ 取模．

inputFormat:
- 第一行输入四个整数，$n,m,k,t$．
- 第二行输入 $n$ 个整数，描述数组 $s$．
- 接下来输入 $m$ 行．每行第一个整数 $|g_i|$ 表示「目标数组」$g_i$ 的长度．接下来 $|g_i|$ 个整数描述「目标数组」$g_i$．
- 由于 $p$ 矩阵为实数矩阵，输入不方便，因此我们采用另一种方式输入 $p$ 矩阵．具体而言，接下来输入 $k$ 行，每行包含 $k$ 个整数，描述一个 $k \times k$ 的矩阵 $p'$．则有

$$
p_{i,j}=\frac{p'_{i,j}}{\sum_{l=1}^k p'_{i,l}}.
$$

outputFormat: - 输出 $n$ 行，每行一个整数．表示假设以 $s[1,i]$ 为初始细菌的「基因数组」，实验结束后能得到的「目标细菌」的数量的期望，对 $10^9+7$ 取模．

hint:
### 样例解释

#### 样例 \#1

- 当前缀长度为 $1$ 时，初始细菌的「基因数组」为 $\{1\}$．分裂一次后变为 $\{1\}$ 和 $\{2\}$ 的概率均为 $\frac 1 2$．若变为 $\{1\}$，则是「目标细菌」；若变为 $\{2\}$，则不是「目标细菌」．分裂一次后培养皿中有 $2$ 个细菌，故「目标细菌」总数的期望为 $\frac 1 2\times 2=1$．
![](https://cdn.luogu.com.cn/upload/image_hosting/ytz7qxkl.png)
- 当前缀长度为 $2$ 时，初始细菌的「基因数组」为 $\{1, 1\}$．分裂一次后的细菌变为 $\{1, 1\}, \{1, 2\}, \{2, 1\}, \{2, 2\}$ 的概率都为 $\frac 1 4$．其中 $\{2, 2\},\{1,2\},\{2,1\}$ 均为「目标细菌」，$\{1,1\}$ 不是「目标细菌」（因为出现了两次子串 $\{1\}$）．即分裂后的「目标细菌」的总数的期望为 $\frac 3 4$．分裂一次后培养皿中有 $2$ 个细菌．即最后「目标细菌」数量之和的期望为 $\frac 3 4\times 2=\frac 3 2$．
![](https://cdn.luogu.com.cn/upload/image_hosting/cjx85fuk.png)

### 数据范围

**本题采用捆绑测试，且不存在一个 Subtask 包含其他所有 Subtask 的数据范围和限制．**

$$
\def{\arraystretch}{1.5}
\begin{array}{|c|c|c|c|c|c|c|c|} \hline
\textbf{Subtask} & \textbf{分值} &\bm{n\le} & \bm{m\le} &\bm{k\le}&\bm{t\le} & \bm {|g_i|\le} &  \textbf{特殊性质} \cr \hline
1 & 1 & 10^5 & 10^5 & 100 & 0 & 10^5 \cr \hline
2 & 14 & 5 & 5 & 5 & 1 & 5 \cr \hline
3 & 15 & 10^3 & 1 & 10^3 & 1 & 100 & \text{A} \cr \hline
4 & 30 & 5\times 10^4 & 5 & 10 & 1 & 50 & \text{B} \cr \hline
5 & 20 & 5\times 10^4 & 5 & 10 & 10^3 & 50 \cr \hline
6 & 20 & 10^3 & 10^4 & 10 & 10^3 &  10^4 & \text{C}\cr \hline
\end{array}
$$

- **特殊性质** $\textbf{A}$：对于 $i=1,2,\dots,m$，保证 $g_{i}$ 中所有整数均为 $1$
- **特殊性质** $\textbf{B}$：对于 $i=1,2,\dots, k$，$j=1,2,\dots,k$，保证 $p'_{i,j}=1$
- **特殊性质** $\textbf{C}$：保证 $\sum_{i=1}^m |g_i|\le 10^4$

对于所有数据，保证 $1\le n,m,\sum|g_i| \le 10^5$．$0\le t\le 10^3$，$0\le p'_{i,j} \le 10^9$．且 $p'$ 矩阵不会出现某一行的和在模 $10^9+7$ 意义下为 $0$．


title: [Cnoi2021] 六边形战士

background:
在 Cirno 的精心照料下，六边形成长为一只可爱的平行六边形。

现在，Cirno 很想知道它的战斗力是多少。

description:
可爱的平行六边形所有边的夹角均为 $\frac{2\pi}{3}$，三组对边的长度分别为 $a$，$b$，$c$ 个单位。如图。

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

在战斗力鉴定时，鉴定师会以六边形的每一条边所在的直线，间隔 $\frac{\sqrt{3}}{2}$ 个单位建立平行直线系。这样六边形战士会被划分成若干个正三角形。如图。

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

鉴定师会将所有有公共边的正三角形连边。由于没有奇环，很容易知道这是一个二分图。然后鉴定师会试图构造该二分图的完美匹配。如图。

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

该六边形战士的战斗力为上述**二分图的完美匹配**可能的种类数。作为见习鉴定师，你需要帮 Cirno 求出该六边形的战斗力。

由于答案可能过大，仅需输出它对 $998244353$ 取模的结果即可。

inputFormat: 一行，三个整数，用空格隔开，表示 $a$，$b$，$c$。

outputFormat: 一行，一个整数，表示六边形战士的战斗力对 $998244353$ 取模后的结果。

hint:
**数据范围与约定**

对于 $100\%$ 的数据，保证 $1\le a,b,c\le 10^6$。

**子任务**

Subtask1（$10$ points）：$a,b,c\le 3$。

Subtask2（$10$ points）：$a,b,c\le 8$。

Subtask3（$70$ points）：$a,b,c\le 100$。

Subtask4（$10$ points）：无特殊限制。

**提示**

 - **Krattenthaler’s formula**
 $\displaystyle\det\left(\prod\limits_{k=2}^j(x_i+a_k)\prod\limits_{k=j+1}^n(x_i+b_k)\right)_{i,j=1}^{n}=\prod\limits_{1\le i<j\le n}{(x_i-x_j)}\prod\limits_{2<i\le j\le n}(a_i-b_j)$。


title: [Kubic] Addition

background: 建议先看 B 题题目背景。

description: 有一个初始长度为 $n$ 的序列 $a$。你需要进行 $n-1$ 次操作。每一次操作先在当前序列中选出两个相邻的数 $x,y$ 并删除（原序列中 $x$ 在 $y$ 左边），再往原位置插入一个 $x+y$ 或一个 $x-y$。$n-1$ 次操作之后最终只会剩下恰好一个数，求这个剩下的数的最大值。

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

第二行，共 $n$ 个整数 $i$ 个表示 $a_i$。

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

hint:
对于 $100\%$ 的数据，$1\le n\le 10^5,|a_i|\le 10^9$。

||分值|$n$|$\vert a_i\vert$|特殊性质|
|:-:|:-:|:-:|:-:|:-:|
|$\operatorname{Subtask}1$|$10$|$\le 2$|无特殊限制|无|
|$\operatorname{Subtask}2$|$20$|$\le 100$|无特殊限制|无|
|$\operatorname{Subtask}3$|$5$|无特殊限制|无特殊限制|$a_i\ge 0$|
|$\operatorname{Subtask}4$|$30$|无特殊限制|$\le 1$|无|
|$\operatorname{Subtask}5$|$35$|无特殊限制|无特殊限制|无|

### 样例解释

一种操作过程如下：

`-1 1 1 -1 1`

`-1 1 1 -2`

`-1 1 3`

`-1 4`

`3`

可以证明没有更优的方案。


title: 「EVOI-RD2」童年

background:
池塘边的榕树上 知了在声声地叫着夏天
操场边的秋千上 只有蝴蝶儿停在上面
黑板上老师的粉笔还在拼命叽叽喳喳写个不停
等待着下课 等待着放学
等待游戏的童年

description:
Charlie 童年时代很喜欢爬树。

有一天，Charlie 准备向一棵高大的苹果树发起挑战。这棵苹果树有 $n$ 个结点，其中结点 $1$ 为树根。

每个结点会有若干个苹果或一个鸟巢。若这个结点上是若干个苹果，则 Charlie 会摘下所有的苹果装入自己的口袋中；若这个结点是鸟巢**且 Charlie 是第一次访问它**，则 Charlie 会给这个鸟巢中的每只鸟儿一个苹果~~不要问鸟儿为什么喜欢苹果~~。

特别地，如果 Charlie 当前口袋中的苹果不足以给该结点的每只鸟儿一个，则他就不会走向这个结点。注意 Charlie 重复经过一个结点时，不会重复采摘苹果，也不会重复给出苹果。

一开始，Charlie 口袋中有 $s$ 个苹果。Charlie 将从树根开始爬树，每次经过一条边到达一个结点，并执行对应的操作（摘苹果或给苹果，根结点的操作也要执行）。Charlie 希望最终拥有的苹果数最多。由于 Charlie 还在忙着爬其他的树，他想请你写个程序帮帮他。

inputFormat:
第一行两个整数 $n,s$，含义如上所示。

接下来一行 $n-1$ 个整数，第 $i$ 个整数代表第 $i+1$ 号结点的父亲 $p_i$。

再接下来一行 $n$ 个整数，第 $i$ 个数为 $a_i$。若 $a_i>0$，则代表这个结点有 $a_i$ 个苹果；若 $a_i<0$，则代表这个结点有一个 $|a_i|$ 只鸟儿的鸟巢；若 $a_i=0$，则说明这个结点什么也没有。

outputFormat: 一行一个整数，代表 Charlie 最终拥有的最多苹果数。

hint:
**样例 1 解释：**

可以摘走所有苹果。

**样例 2 解释：**

只能摘走结点 $1,3$ 的苹果，结点 $2$ 因为鸟儿太多无法访问。

**样例 3 解释：**

![样例3解释](https://cdn.luogu.com.cn/upload/image_hosting/hj7eoes3.png)

结点 $1$ 给掉 $2$ 个苹果，先摘完结点 $3,6,7$ 的苹果，此时口袋中有 $6$ 个苹果。再闯过结点 $2$，然后拿走结点 $5$ 的苹果，结点 $4$ 由于鸟儿太多没必要走。

一种最优的具体路径：$1 \rightarrow 3 \rightarrow 6 \rightarrow 3 \rightarrow 7  \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1$。

**数据规模与约定**

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

+ Subtask 1 (10 pts)：$\, n \leq 10$。
+ Subtask 2 (20 pts)：$\, n \leq 100$ 。
+ Subtask 3 (10 pts)：$\, p_i=1$。
+ Subtask 4 (30 pts)：$\, p_i=i-1$。
+ Subtask 5 (30 pts)：无特殊限制。

对于 $100\%$ 的数据，$1 \leq n \leq 6000, 1 \leq p_i \lt i, |a_i| \leq 10^9,0 \leq s \leq 10^9$。

---

“记得门前，有两株树，一株是苹果树，还有一株……也是苹果树。”


title: [✗✓OI R1] 左方之地

background:
后记中将会详细描述帅神左方之地为何能成为「魔禁六帅」之首。

如果你很奇怪题目名称里面为什么没有前方之风，那你可能应该去看看 div.2。

但在此之前，你需要做一道构造题。

description:
给你一个自然数 $n$ 和一个自然数参数 $k$，你需要构造一个长度为 $2^n$ 的序列 $a$，满足 $[0,2^n)$ 间的所有整数恰好出现一次，并且 $\forall i\in[2,2^n]$，$\operatorname{popcount}(a_i \oplus a_{i-1})=k$。
其中 $\operatorname{popcount}(x)$ 表示 $x$ 在二进制下 $1$ 的个数，$\oplus$ 表示[按位异或](https://oi-wiki.org/math/bit/#_1)运算。

若有解则输出 `1` 并输出这个序列，否则输出 `0`。

inputFormat: 一行两个整数 $n,k$，意义同题目描述。

outputFormat:
第一行输出一个整数 `0` 或者 `1`，其中 `0` 代表不存在这样的序列，而 `1` 代表存在这样的序列。
如果第一行输出的是 `1`，接下来一行输出 $2^n$ 个整数，表示你构造的序列。如果有多个合法的序列，输出任意一个。


title: [✗✓OI R1] 右方之火

background:
> 「区区二十亿，区区两千年，根本就不够。」
> 「本大爷所拥有的力量可比你想象的还多哦。」

你打不过右方之火。
但是为了证明你的想象力很丰富，你要做一道构造题。

description:
你有一个 $n$ 个点 $m$ 条边的无向连通图，每个点有一个初始权值 $a_i$ 以及一个目标权值 $b_i$。现在你可以对这张图进行这样的操作：
- 选择一个整数 $c$，需要满足 $|c| \le 10^{18}$；
- 选一条点数为 $3$，边数为 $2$ 的链；
- 使得中间点的权值减去 $2c$，另外两个点的权值各加上 $c$。

问是否可以进行若干次操作使得最后每个点的权值都为 $b_i$。如果可以，你需要输出方案，操作次数不能超过 $4n$。

**注意 $c$ 可以为负数。**

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

第一行一个正整数 $T$ ，表示测试数据的数量。
对于每组数据，第一行两个正整数 $n,m$，分别表示点数和边数。
接下来两行，每行各 $n$ 个正整数，表示初始权值 $a_i$ 和目标权值 $b_i$。
接下来 $m$ 行，每行两个整数 $u,v$，表示 $u$ 号点和 $v$ 号点之间有一条边，保证图连通，没有自环和重边。

outputFormat:
对于每组数据，第一行输出一个字符串，若能够从初始权值变为目标权值，输出 `Yes` ，否则输出 `No`。**输出 `Yes` 和 `No` 的这一行不要有其他奇怪的字符，不然可能会被 checker 判成错误。**
第二行输出一个整数 $k(k\le4n)$，表示构造方案共有 $k$ 步。
接下来 $k$ 行，每行四个整数 $x,y,z,c$ 满足 $1 \le x,y,z \le n$，$|c| \le 10^{18}$，$(x,y),(y,z)\in E$，表示 $a_x \gets a_x+c,a_y \gets a_y-2c,a_z \gets a_z+c$。

**本题采用 Special Judge。如果有多种答案，输出任意一种即可。**


title: [Ynoi2006] rmpq

description:
你需要包含头文件`lib.h`；

在本地编译时，需要和 `lib.cpp` 一起编译；

交互库提供了以下数据类型和函数：

```cpp
struct Data{
	unsigned short a,b,c,d;
	void operator*=(const Data &x);
	void clr();
};
```

Data 类型是一个含幺半群 $(D,*,e)$，具体地：

$D$ 是类型为 Data 的元素构成的集合；

$*:D\times D\to D$

$e\in D$

$\forall x,y,z\in D, x*(y*z)=(x*y)*z$

$\forall x\in D, x*e=e*x=x$

使用 `x.clr()` 可以将 $x$ 修改为 $e$；

使用 `x=y` 可以将 $x$ 修改为 $y$；

使用 `x*=y` 可以将 $x$ 修改为 $x*y$，这个操作的调用次数有常数上限 $2\times 10^7$，不计 $x=e$ 或 $y=e$ 的情况。

初始条件下，平面上每个点 $(x,y)$ 都对应一个权值 $d(x,y)\in D$；

你需要实现以下函数：

```cpp
void update(int x,int dim,Data d1,Data d2);
```

对每个 $(x_0,y_0)$ 执行操作：

若 $dim=0$ 且 $x_0<x$，则将 $d(x_0,y_0)$ 修改为 $d(x_0,y_0)*d1$；

若 $dim=0$ 且 $x_0\ge x$，则将 $d(x_0,y_0)$ 修改为 $d(x_0,y_0)*d2$；

若 $dim=1$ 且 $y_0<x$，则将 $d(x_0,y_0)$ 修改为 $d(x_0,y_0)*d1$；

若 $dim=1$ 且 $y_0\ge x$，则将 $d(x_0,y_0)$ 修改为 $d(x_0,y_0)*d2$；

```cpp
Data query(int x,int y);
```

查询 $d(x,y)$，返回值为答案。

为了您的方便，这里提供模板。请完善以下代码：

```cpp
/* BEGIN HEADER: */
struct Data{
	unsigned short a,b,c,d;
	void operator*=(const Data &x);
	void clr();
};
void update(int x,int dim,Data d1,Data d2);
Data query(int x,int y);
/* END HEADER. */

#include <bits/stdc++.h>

void update(int x,int dim,Data d1,Data d2){
	// complete this
}
Data query(int x,int y){
	// complete this
}
```

由于洛谷的交互方法比较奇怪，所以提交的时候需要把本地的代码复制过来，放在 update, query 函数这里，和前面的 HEADER 一起提交。提交时不引用 "lib.h" 头文件。

inputFormat: 这是交互题，不需要这种东西。

outputFormat: 这是交互题，不需要这种东西。

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

对于前 8 组数据，操作个数分别为 $10,1000,10000,20000,40000,60000,80000,10^5$，且 $x,y,dim$ 均匀随机选取；

对于其余数据，操作个数为 $10^5$，且构成子任务。

对于所有数据：
对于 update 操作，满足 $1\le x\le 10^9$，$dim\in\{0,1\}$；
对于 query 操作，满足 $1\le x,y\le 10^9$。


title: 「Wdcfr-1」Magical Expression

description:
Nitori is learning postfix expressions. She has a incomplete postfix expression $E$ of length $n$. Being a Youkai, she wants to find its magical property.

Her postfix expression contains the Bitwise Or operator (denoted as `|`), the Bitwise And operator (denoted as `&`), and numbers `0` and `1`. Being incomplete, some operators have not been decided yet and are denoted as `?`. She promised that $E$ **will become a *vaild* postfix expression** after you complete it.

In this problem, the term *substring* is defined as a continuous segment of $E$. **Two substrings are considered different as long as their positions or length differ.**  So `1?0`, `01?0` are all substrings of `01?01?|`  , but `0101` is not.

Nitori found out that a substring of her expression is *magical* if and only if the following conditions are met:

- It is possible to transform it into a *valid* postfix expression after replacing `?` with either `&` or `|` .
- Among these transformations, it is possible to find at least one of them that after applying it, the expression yields $0$,  and at least one of them that after applying it, the expression yields $1$.

Your task is to find out the number of *magical* substrings.

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

For each test case, input one integer $n$ and an expression $E$ in a single line.

outputFormat: For each test case, print one integer which is the answer.

translation:
给定一个合法的含 `|&?01` 的后缀表达式（以字符串形式给出，其为“合法的”代表将所有 `?` 替换为运算符后其会成为一个合法的后缀表达式），试求出其有多少个子串满足：

- 将所有的 `?` 替换成 `|` 或 `&` 后，该串为合法的后缀表达式；
- 存在一种将所有的 `?` 替换成 `|` 或 `&` 的方法使得该式所得结果为 $0$，同时也存在替换方法使得结果为 $1$。

请输出这样的子串的数量。两个子串是不同的仅当它们长度不同或位置不同。

hint:
### Constraints

$1\le T,n\le 2\times 10^6$. The sum of $n$ of all test cases $\le 2\times 10^6$.


title: [✗✓OI R1] 逆转比特

background: myy 正在广东佛山游玩，所以他出了一道 [**高明**](https://baike.baidu.com/item/%E9%AB%98%E6%98%8E%E5%8C%BA/7747108?fr=aladdin) 的题目。

description:
一个点在长为 $n$ 的只含有 0/1 的序列上随机游走，点的初始坐标为 $p$，重复进行以下操作：
1. 当序列全为一种字符时，停止操作；
2. 记点当前位置 $p$，等概率随机选择一个点 $q$，把点移动到 $q$，将 $q$ 处的字符的取反，总代价加上 $f(|p-q|)$，这里 $f(x)=Ax^2+Bx$，其中 $A,B$ 是两个给定常数；
3. 回到第一条。

你需要进行 $q$ 次修改，具体而言，每次修改包括
1. 将序列第 $\mathit{idx}$ 位的 0/1 翻转；
2. 查询初始坐标为 $p$ 时，停止操作后的期望代价。

**注意，一旦修改一直有效**。

你需要输出 $q$ 次询问期望代价模 $998244353$ 的结果的异或和。

考虑到输入输出量比较大，数据采用如下随机生成方式
```cpp
struct Random {
  unsigned long long X;
  void init(unsigned long long seed) { X = seed; }
  unsigned long long Rand() {
    X ^= X << 13;
    X ^= X >> 7;
    X ^= X << 17;
    return X;
  }
} R;
```
初始 01 串生成，会提供 $\mathit{seed1}$。
```cpp
R.init(seed1);
for (int i = 1; i <= n; i++) seq[i] = R.Rand() & 1;
```
对于 $q$ 次询问，会提供 $\mathit{seed2}$。
```cpp
R.init(seed2);
for (int i = 1; i <= q; i++) {
  idx = R.Rand() % n + 1, p = R.Rand() % n + 1;
  ans ^= query(idx, p);
}
```

outputFormat: 一行一个整数 $\mathit{ans}$，表示 $q$ 次询问期望代价模 $998244353$ 的结果的异或和。


title: 「Wdcfr-1」Border of Gensokyo

description:
**This is an interactive problem.**

Ran is helping Yukari to maintain the border of Gensokyo.

The border of Gensokyo is a $n\times m$ matrix, where $n$ and $m$ are both even. Unfortunately, due to Moriya Shrine's moving in, there are now $4$ weakened points within the matrix.

To ease the maintenance work, Ran have already found a path from $(1,1)$ to $(n,m)$, going only down or right. The path separates the four weakened points so that exactly two of them are on either side. She will tell you this path in the input.

Now you need to help Ran maintain the border. You can use the operation `? x y` to ask whether the point $(x,y)$ is weakened. And after the query, Ran will mark the point with blue.

If, after a query, you have just found out the $k$-th weakened point, and $k$ is even, you will need to construct a simple path from the $(k-1)$-th weakened point to the $k$-th. The path you constructed must pass through and only pass through **all** the points that are marked blue.  Ran will then strengthen these points in the border and recolor them red.

Ran does not want to do repetitive work, so you can only ask for points that are white with the `?` query.

Now Ran hopes that you can ask all the "weakened points" and finish all the constructions.

### Interaction Protocol

First read two integers $n$ and $m$ from standard input.

Then read several points (including start and end points) from standard input, one per line, representing a simple path from $(1,1)$ to $(n,m)$.

Then you can make **unlimited** queries. Print your queries to standard output in the format of `? x y`. You will then receive an integer $p$ from standard input. If $p=1$, it means that the point you asked is indeed weakened; if $p=0$, it means that it is not weakened.

Remember to flush your output, you can use `fflush(stdout);` in C++. Please refer to your programming language's documentation.

On the $k$-th time ($k$ is even) of receiving the result $p=1$, please output several points (including the two weakened points) in order, one per line, ending with $-1,-1$, so that they represent the simple path from the $(k-1)$-th to the $k$-th weakened point.

You need to exit your program immediately after finding the fourth weakened point and finishing the construction.

inputFormat: Refer to "Interactive Method".

outputFormat: Refer to "Interactive Method".

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

有一个 $n\times m$ 的矩阵，保证 $n$ 和 $m$ **均为偶数**。初始所有格子都是白色。用 $(x,y)$ 表示矩阵第 $x$ 行第 $y$ 列的格子。

矩阵中有四个关键点（也就是特殊的格子），并且保证存在一条从 $(1,1)$ 到 $(n,m)$ 的只能向下或向右的路径，将四个关键点分隔成两侧每侧两个。**路径已被给出。**

你可以用操作 `? x y` 来询问格子 $(x,y)$ 是否为关键点（是的话交互器返回 $1$，否则返回 $0$），并且询问过后该格子会被染成蓝色。

在你第偶数次询问到关键点后，你需要输出一条从倒数第二次被询问到的关键点到最近一次询问到的关键点的简单路径，满足经过且仅经过**所有**被染成蓝色的格子。输出完成后，所有的蓝色格子都会变成红色。

需要注意，你**只能询问白色格子**。

hint:
### Explanation

The matrix in the sample is as follows:

```plain
..XX
X...
....
X...
```

Which `X` means a "weakened point".

### Constraints

$4\le n,m\le100$。


title: 「EVOI-RD2」旅行家

description:
小 A 是一个热衷于旅行的旅行家。有一天，他来到了一个城市，这个城市由 $n$ 个景点与 $m$ 条连接这些景点的道路组成。每个景点有一个**美观度** $a_i$。

定义一条**旅游路径**为两个景点之间的一条非严格简单路径，也就是点可以重复经过，而边不可以。

接下来有 $q$ 个旅游季，每个旅游季中，小 A 将指定两个顶点 $x$ 和 $y$，然后他将走遍 $x$ 到 $y$ 的**所有旅游路径**。

所有旅游季结束后，小 A 会统计他所经过的所有景点的美观度之和（重复经过一个景点只统计一次美观度）。他希望你告诉他这个美观度之和。

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

第二行 $n$ 个正整数 $a_i$，代表顶点 $i$ 的权值。

接下来 $m$ 行，每行 $2$ 个正整数，表示一条无向边的两个端点。

然后一个正整数 $q$，代表有 $q$ 个旅游季。

接下来 $q$ 行，每行 $2$ 个整数 $x,y$，表示指定的起点和终点。

outputFormat: 一行，一个整数表示最终的美观度总和。

hint:
**【数据规模与范围】**

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

+ Subtask 1 (30 pts)：$3 \leq n \leq 500,m \leq 2 \times 10^5,q=200$。
+ Subtask 2 (30 pts)：$3 \leq n \leq 3 \times 10^5,m \leq 2 \times 10^6,q=10^6$。
+ Subtask 3 (40 pts)：$3 \leq n \leq 5 \times 10^5,m \leq 2 \times 10^6,q=10^6$。

对于 $100\%$ 的数据，保证 $3 \leq n \leq 5 \times  10^5$，$m \leq 2 \times 10^6$，$q=10^6$，$1 \leq a_i \leq 100$，且该图联通，没有重边和自环。

---

**对于题面的解释：**

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

上图与样例无关。

如图，为城市的景点分布图，为无向图。
假设 $6$ 号顶点为 $x$ 景点，$5$ 号顶点为 $y$ 景点。
很显然，路径 $6 \rightarrow 2 \rightarrow 4 \rightarrow 5$ 和路径 $6 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 5$ 都是合法的，这两条路径满足了都是简单路径的条件，并且都是在一次旅游季中行走的。
虽然 $6 \rightarrow 2$ 这条边经过了 $2$ 次，但仍旧是合法的，因为它们不是在一条路径中经过的。

简单来说，一次旅游季会走不定条路径，每条路径必须是简单路径，但是每条简单路径之间可以有重边。


title: 「Wdcfr-1」CONsecutive and CONcat (easy version)

description:
**In easy version, It is guaranteed that any string in array $\mathbf a$ contains at least two different letters.**

Lily White is playing with strings. Being a yousei, she is not capable of complex speech. Thus, she likes strings that only contain one kind of letter, she calls such strings of length $x$ a "$x$-CON string". For example, `qqqq` is a "$4$-CON string", while `aaab` is not any type of "CON string".

Lily White composed an array $a$. It contains $n$ strings of length $m$ that she will use to herald spring. For each permutation of $1,2,\ldots, n$, let us denote current permutation as $p=\{p_1,p_2,\cdots,p_n\}$. Lily White concatenates all the string in array $a$ in the order of $a_{p_1},a_{p_2},\cdots,a_{p_n}$ into a string $s$ of length $nm$ .

As she likes $k$-CON strings, she wants to know the sum of the number of "$k$-CON string" in all non-empty substrings of $s$ composed by all $n!$ permutations. Since the answer may be enormous, just print the answer taken modulo $998,244,353$ (a large prime).

inputFormat:
The first line contains three integers $n,m,k$.

Then $n$ lines follow, each line contains a string of length $m$. The string in the$(i+1)$-th line represents $a_i$.

outputFormat: Print a single integer - the answer taken modulo $998,244,353$.

translation:
**在 easy version 中，保证所有 $\mathbf a$ 中的字符串至少包含两种不同的字母。**

给定若干长度为 $m$ 的字符串 $a_1,a_2,...,a_n$，给定常数 $k$，试求出对于所有的长度为 $n$ 的排列 $p$，将 $a_{p_1},a_{p_2},...,a_{p_n}$ 依次拼接形成的长字符串 $s$ 中，有多少个位置 $x$ 满足 $s_x,s_{x+1},...,s_{x+k-1}$ 为同一种字符。请输出位置数的和 $\bmod \space998244353$ 的值。

hint:
### Explanation

#### Sample \#1

- For permutation $1,2,3$, the formed $s$ is `aabbaabaa`, none on the non-empty substring in this string are "$4$-CON string".
- For permutation $1,3,2$, the formed $s$ is `aabbaabaa`, none on the non-empty substring in this string are "$4$-CON string".
- For permutation $2,1,3$, the formed $s$ is `baaaabbaa`, this string has one substring `aaaa` which is a "$4$-CON string".
- For permutation $2,3,1$, the formed $s$ is `baabaaaab`, this string has one substring `aaaa` which is a "$4$-CON string".
- For permutation $3,1,2$, the formed $s$ is `baaaabbaa`, this string has one substring `aaaa` which is a "$4$-CON string".
- For permutation $3,2,1$, the formed $s$ is `baabaaaab`, this string has one substring `aaaa` which is a "$4$-CON string".

In summary, the answer is $0+0+1+1+1+1=4$.

#### Sample \#2

In all of the full permutation of length $3$, there will be six different $s$: `xyzqaqaba`, `xyzabaqaq`, `qaqxyzaba`, `qaqabaxyz`, `abaqaqxyz`, and `abaxyzqaq`. None of these has a non-empty substrings which is a "$2$-CON string". So the answer is $0$.

### Constraints

$2\le k \le n\cdot m\le 10^6;\ 1\le m \le 100$. $a_i$ contains only lowercase English letters.

**In easy version, we ensure that any string in array $\mathbf a$ contains at least two different letters.**


title: Alice and Bob are playing a Normal Game

description:
给定一个长度为 $n$ 的序列，Alice 和 Bob 交替操作一共 $k$ 次，第 $i$ 次当前操作的人必须选一个 $-x_i \sim x_i$ 的整数把它插在序列开头或结尾，Alice 先手（也就是说 $i$ 为奇数时由 Alice 来插入一个 $-x_i\sim x_i$ 的整数，$i$ 为偶数时由 Bob 来插入一个 $-x_i\sim x_i$ 的整数）。

记最终的序列为 $a_1,a_2,\dots,a_{n+k}$，则得分为 $\sum_{i=1}^{n+k} (-1)^{i-1}a_i$。Alice 希望得分最大，Bob 希望得分最小。在两人都采取最优策略的情况下，求最终得分。

inputFormat:
第一行两个正整数 $n,k$ 表示初始序列长度以及操作次数。

接下来一行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示初始的序列。

接下来一行 $k$ 个非负整数，第 $i$ 个表示 $x_i$。

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


title: [Kubic] ABC

background: 建议先看 D 题题目背景。

description:
给定一个长度为 $n$ 的只包含 $\texttt{A,B,C}$ 的字符串 $S$，你可以进行若干次操作，每次操作为：

- 先选择一个区间 $[l,r]$，你需要保证 $1\le l\le r\le n$。

- 再选择三个字符 $pA,pB,pC\in\{\texttt{A,B,C}\}$，并将 $S_{l\dots r}$ 中所有 $\texttt{A}$ 变为 $pA$，所有 $\texttt{B}$ 变为 $pB$，所有 $\texttt{C}$ 变为 $pC$，**$pA,pB,pC$ 可以相等**。

求出**最少**需要进行多少次操作才能使得 $S$ 中**任意相邻两个字符不同**，并**输出构造方案**。

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

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

outputFormat:
第一行，一个整数 $m$，表示你所构造的方案的操作次数。

接下来 $m$ 行，每行两个整数 $l,r$ 和三个字符 $pA,pB,pC$。

你需要保证 $1\le l\le r\le n,pA,pB,pC\in\{\texttt{A,B,C}\}$。

**注意：$pA,pB,pC$ 之间不需要，也不应该加空格（参考样例输出）**。

hint:
对于 $100\%$ 的数据，$1\le n\le 5\times 10^3,S_i\in\{\texttt{A,B,C}\}$。

||分值|$n$|特殊性质|
|:-:|:-:|:-:|:-:|
|$\operatorname{Subtask}1$|$1$|无特殊限制|$\forall i\in[1,n),S_i\neq S_{i+1}$|
|$\operatorname{Subtask}2$|$19$|$\le 10$|无|
|$\operatorname{Subtask}3$|$10$|无特殊限制|$S_i=\texttt{A}$|
|$\operatorname{Subtask}4$|$20$|无特殊限制|$S_i\in\{\texttt{A,B}\}$|
|$\operatorname{Subtask}5$|$20$|$\le 100$|无|
|$\operatorname{Subtask}6$|$30$|无特殊限制|无|

### 评分方法

以下情况将会使你在该测试点获得 $0$ 分：

- 输出格式不满足要求。

- 输出多余信息（包括空格和换行符）

- 构造的方案操作次数与标准答案不同。

- 构造的方案不符合题目要求。

- 时间超限。

如果没有上述情况，你在该测试点获得满分。

**保证 SPJ 占用不超过 $100\operatorname{ms},10\operatorname{MB}$**。

### 样例解释 1

一种操作过程如下：

`ABBAA`

`ABABA`

可以证明没有更优的方案。

### 样例解释 2

初始序列已经符合题目要求，直接输出一行 $0$ 即可。


title: [Ynoi2006] rldcot

description:
给定一棵 $n$ 个节点的树，树根为 $1$，每个点有一个编号，每条边有一个边权。

定义 $dep(x)$ 表示一个点到根简单路径上边权的和，$lca(x,y)$ 表示 $x,y$ 节点在树上的最近公共祖先。

共 $m$ 组询问，每次询问给出 $l,r$，求对于所有点编号的二元组 $(i,j)$ 满足 $l \le i,j \le r$ ，有多少种不同的 $dep( lca(i,j))$。

inputFormat:
第一行两个用空格隔开的数 $n,m$。

之后 $n-1$ 行，每行三个用空格隔开的数 $u,v,d$ 表示一条 $u$ 到 $v$ 边权为 $d$ 的边。

之后 $m$ 行，每行两个用空格隔开的数 $l,r$ 表示一次询问。

outputFormat: 共 $m$ 行，一行一个整数，表示询问的答案。

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

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

对于另外 $20\%$ 的数据，满足 $1\le n,m \le 5000$。

对于另外 $20\%$ 的数据，满足 $1\le n,m \le 50000$。

对于另外 $20\%$ 的数据，满足 $d=1$。

对于 $100\%$ 的数据，满足 $1\le n \le 10^5$，$1\le m \le 5 \times 10^5$，所有数值为整数，$-10^9 \le d \le 10^9$。


title: 一曲新词酒一杯

background: 昨夜勾栏听曲，一壶浊酒，与明月凭栏相望，想起如今的处境，却没有怅然若失，仍然醉心于宴饮涵咏之乐，把酒临风之际，想起一种酒桌上的游戏，便和好友玩起来。

description:
酒桌上共有 $n$ 杯酒，标号为 $1\sim n$。桌旁有许多写有“酒”字的红色纸片。

接下来对这 $n$ 杯酒**依次**进行 $m$ 次操作。

操作共分为 $2$ 种：

- `1 x`：给 $x$ 号酒贴上 $1$ 张红纸。
- `2 x`：给除了 $x$ 号酒的其它 $n-1$ 杯酒分别贴上 $1$ 张红纸。

问在**至少**几次操作后，每杯酒上至少有一张红纸？

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

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

对于每组测试数据：

- 第一行两个整数 $n,m$。
- 后 $m$ 行每行两个整数 $o_i,x_i$，表示第 $i$ 次操作。

outputFormat:
对于每组测试数据：

- 若在 $m$ 次操作后至少有一杯酒没有红纸，输出一行 `-1`；
- 否则输出一行一个整数表示答案。

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

对于第一组数据：

- 第 $1$ 次操作后，$1$ 号酒有 $1$ 张红纸，$2$ 号酒有 $0$ 张红纸，$3$ 号酒有 $0$ 张红纸。
- 第 $2$ 次操作后，$1$ 号酒有 $1$ 张红纸，$2$ 号酒有 $1$ 张红纸，$3$ 号酒有 $0$ 张红纸。
- 第 $3$ 次操作后，$1$ 号酒有 $1$ 张红纸，$2$ 号酒有 $1$ 张红纸，$3$ 号酒有 $1$ 张红纸。

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

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

-  Subtask 1（20 points）：$o_i=1$。
-  Subtask 2（20 points）：$o_i=2$。
-  Subtask 3（20 points）：所有 $x_i$ 均相等。
-  Subtask 4（20 points）：$\sum n,\sum m\le 3\times 10^3$。
-  Subtask 5（20 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le T,n,m,\sum n,\sum m\le 2\times 10^5$，$o_i\in \{1,2\}$，$1\le x_i\le n$。


title: [COCI2007-2008#5] TRI

description:
Mirko 在他的数学笔记本上写下了一个包含三个正整数 $a,b,c$、一个等号和一个四则运算符（加号、减号、乘号、除号）的等式。但是在另一节课上，Mirko 的朋友 Slavko 将等式中的等号和运算符从他的笔记本上擦除了。

请您通过这三个整数还原这个等式以帮助 Mirko。

inputFormat: 一行，三个整数 $a,b,c$。

outputFormat:
一行，一个包含以上三个整数 $a,b,c$（顺序与输入相同），一个等号和一个四则运算符的字符串，表示一种可能的算式。

如果有多个可能解，输出其中任意一个即可。

hint:
对于 $100\%$ 的数据，$0< a,b,c< 100$。

输入数据保证有解，但不保证有唯一解。

本题分值按照原比赛设置，满分 $20$ 分。


title: [COCI2007-2008#5] PASCAL

description:
小 Frane 已经十年级了，但是在信息课上学习 Pascal 仍然很吃力。老师写下了如下的 Pascal 程序作为家庭作业，他需要根据输入的整数 $N$ 来判断程序的输出。

```pascal
readln(N);
counter := 0;
for i := N-1 downto 1 do begin
	counter := counter + 1;
	if N mod i = 0 then break;
end;
writeln(counter);
```

请您编写一个程序来解决这个问题。

inputFormat: 一行，一个整数 $N$。

outputFormat: 一行，表示以上程序的输出结果。

hint:
对于 $100\%$ 的数据，$1\le N\le10^9$。

本题分值按照原比赛设置，满分 $30$ 分。


title: [COCI2007-2008#5] JABUKE

description: 给出一个三角形三个顶点的坐标以及 $N$ 个点的坐标，请您计算出这个三角形的面积和在这 $N$ 个点中，有多少个点在这个三角形内部（包含边界）。

inputFormat:
前三行，每行两个整数，表示三角形一个顶点的坐标。

接下来一行，一个整数 $N$。

接下来 $N$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个点的坐标。

outputFormat:
第一行，一个实数，表示三角形的面积，保留一位小数。

第二行，一个整数，表示在三角形内部和边界上的点数。

hint:
对于 $100\%$ 的数据，$1\le N\le100$，所有坐标的 $x,y$ 均为小于 $10^3$ 的正整数。

**提示：以坐标 $(x_A,y_A)$，$(x_B,y_B)$ 与 $(x_C,y_C)$ 为顶点的三角形面积公式如下：**

$\dfrac{|x_A(y_B-y_C)+x_B(y_C-y_A)+x_C(y_A-y_B)|}{2}$

本题分值按照原比赛设置，满分 $30$ 分。


title: [COCI2007-2008#5] AVOGADRO

description:
Luka 画了一张 $3$ 行 $N$ 列的表格，然后将整数 $1$ 到 $N$ 写进表格。对于表格第一行，每个整数只出现一次。对于其余两行，每个数字可以出现任意次或者不出现。

Luka 现在可以删去任意一些列。完成后，他对这个表的每一行进行升序排序。

他希望得到一张表，使得表中的三行在升序排序后完全相同。请您求出他至少需要删去多少列。

inputFormat:
第一行，一个整数 $N$，表示表中数字的列数。

接下来三行，每行包含 $N$ 个整数。这些整数都在 $1$ 到 $N$ 之间，第一行每个数字有且仅出现一次。

outputFormat: 一行，一个整数，表示 Luka 至少需要删除的列数。

hint:
对于 $40\%$ 的测试点，$N\le 100$。

对于 $70\%$ 的测试点，$N\le 10000$。

对于 $100\%$ 的测试点，$1\le N\le 10^5$。

### 样例 1 解释：

对于样例 1，Luka 需要删除第二、第四、第六和第七列。删除并排序后，这三行都只包含 $1,3,5$ 三个整数。

本题分值按照原比赛设置，满分 $60$ 分。


title: [COCI2007-2008#5] BARICA

description:
Barica 是一只非同寻常的青蛙。她住在一个池塘里，有 $N$ 片漂浮在水面上的荷叶。这些荷叶的编号为 $1$ 到 $N$，位置可以用一对坐标表示。Barica 可以在这些荷叶上跳来跳去，但是她害怕斜着跳和朝负方向跳。

准确的说，她可以从坐标 $(x_1,y_1)$ 跳到另一个坐标 $(x_2,y_2)$ 仅当：

- $x_2>x_1$ 且 $y_2=y_1$ 或者

- $y_2>y_1$ 且 $x_2=x_1$。

对于每一片荷叶，我们知道其附近的苍蝇数量。Barika 可以吃掉所有在她荷叶附近的苍蝇。

Barica 每吃一只苍蝇会获得 $1$ 个单位的能量，每进行一次跳跃消耗 $K$ 个单位的能量。如果 Barica 没有足够的能量，她就不能进行跳跃。

Barica 想通过 $1$ 号植物到达 $N$ 号植物，并获得尽可能多的能量。Barica 开始时没有能量，必须通过吃掉 $1$ 号植物附近的苍蝇来获取能量。

找到使得 Barica 达到目标的一种可行路径。

inputFormat:
第一行，两个整数 $N$ 和 $K$。

接下来 $N$ 行，每行包含三个整数 $x_i$，$y_i$ 和 $z_i$，表示第 $i$ 号荷叶的坐标为 $(x_i,y_i)$，且其附近有 $z_i$ 只苍蝇。

outputFormat:
第一行，输出到达终点后能量单位数量。

第二行，输出一个整数 $L$，表示 Barica 需要经过的植物个数。必须包含 $1$ 号和 $N$ 号植物。

接下来 $L$ 行，依次输出 Barica 需要经过的植物坐标。

hint:
对于 $100\%$ 的数据，$2\le N\le 3\times 10^5$，$1\le K\le 1000$，$0\le x_i,y_i\le 10^5$，$0\le z_i\le 1000$。

输入数据保证有解，但不保证有唯一解。

本题分值按照原比赛设置，满分 $70$ 分。


title: [COCI2007-2008#5] BAZA

description:
定义两个字符串的公共前缀为这两个字符串从开头开始的公共子串。比如，字符串 `identity` 和字符串 `idealistic` 的公共前缀为 `ide`。

有一个数据库包含了 $N$ 个字符串。

在这个数据库中查询字符串 $W$ 使用的算法很原始，它将 $W$ 与数据库中的字符串一一比较。两个字符串的字符也一一比对，直到找到一个不匹配的字符或者其中一个字符串的结尾，然后进行最后一次比较确定两个字符串长度是否相等。当在数据库中找到 $W$ 时，算法结束。

分析这个算法，我们发现，在数据库中找到 $W$ 所用的步骤数等于与 $W$ 进行比较的字符串数量，加上 $W$ 与所有进行比较的字符串的公共前缀之和。

共有 $Q$ 个需查询的字符串。

写出一个程序，计算对于每一个字符串，程序需要多少步才能在数据库中找到这个词。

**请留意本题非同寻常的内存限制。**

inputFormat:
第一行，一个整数 $N$，表示数据库中字符串的个数。

接下来 $N$ 行，每行一个数据库中的字符串，这些字符串按照算法的查询顺序给出，互不相同。

接下来一行，一个整数 $Q$，表示需查询的字符串数。

接下来 $Q$ 行，每行一个需查询的字符串。

outputFormat: 对于每个查询字符串，输出一行，一个整数，表示程序在数据库中找到这个词所需的步数。

samples:
5
hobotnica
robot
hobi
hobit
robi
4
robi
hobi
hobit
rakija

samples:
8
majmunica
majmun
majka
malina
malinska
malo
maleni
malesnica
3
krampus
malnar
majmun

hint:
对于 $100\%$ 的数据，$1\le N,Q\le 3\times 10^4$，所有字符串长度 $<30$，且只包含小写字母。

### 样例 2 解释：

对于样例 2，搜索字符串 `krampus` 所用的步数为 $8$，我们只需要将数据库里每一个字符串的第一个字符与此字符串比较即可。

搜索字符串 `malnar` 时，前三个字符串每个字符串需要比较三次，剩下五个字符串每个字符串则需要比较四次，所以总共需要 $29$ 次比较。

为了找到 `majmun` 字符串，我们总共需要 $14$ 次比较。对于第一个单词，我们进行了六次成功的比较，但最后一次比较确定了字符串 `majmunica` 比 `majmun` 长。对于第二个字符串，我们也进行了六次成功的比较，在最后一次比较中我们发现两个字符串长度相等，算法结束。

本题分值按照原比赛设置，满分 $90$ 分。


title: [Ynoi2006] wcirq

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

你需要进行 $n$ 个原始操作，对一个序列进行维护。初始序列为空。

第 $i$ 个原始操作给出整数 $x_i,\;l_i,\;r_i$，表示在序列的第 $x_i$ 个位置前插入元素 $i$（若 $x_i=i$ 则表示在序列末尾插入），然后查询序列中第 $l_i,\;l_{i+1},\;\dots,\;r_i$ 个元素构成的集合。

为了回答这些查询，你可以操作若干个集合。这些集合初始为空，编号为 $1$ 到 $2\times 10^7$ 的整数。

你可以花费 $1$ 个单位的第一类代价进行插入操作：在编号为 $x$ 的集合中插入元素 $y$，在回答第 $i$ 个原始操作的查询前，需要保证 $1\le y\le i$。

你可以花费 $k$ 个单位的第二类代价回答查询：选取编号为 $a_1,\;a_2,\;\dots,\;a_k$ 的集合，要求这些集合互不相交，且并集是查询的答案。

每次原始操作后，插入操作和回答查询的第一类/第二类代价不能超过当前子任务的代价上限 $m_1,\;m_2$。每次原始操作的代价分别计算。

inputFormat:
你需要实现函数：

```cpp
void solve(int x,int l,int r);
```

对于每次原始操作，这个函数被调用一次，参数 `x l r` 对应 $x_i,\;l_i,\;r_i$。

outputFormat:
你可以调用函数：

```cpp
void op1(int x,int y);
void op2(int k);
```

调用 `op1` 表示执行一次插入操作；

对 $a_1,\dots,a_k$ 依次调用 `op2` 表示回答查询。

在提交的代码中，你需要声明这两个函数。

samples:
假设交互库调用了3次 `solve` 函数如下：

```cpp
solve(1,1,1);
solve(1,2,2);
solve(2,1,3);
```

samples:
以下给出了一种符合要求的对 `op1` 和 `op2` 的调用：

```cpp
op1(1,1);
op2(1);
```

此时序列为 $(1)$，编号1的集合为 $\{1\}$，第1次 `solve` 函数调用返回；

```cpp
op2(1);
```

此时序列为 $(2,1)$，编号1的集合为 $\{1\}$，第2次 `solve` 函数调用返回；

```cpp
op1(1,2);
op1(2,3);
op2(2);
op2(1);
```

此时序列为 $(2,3,1)$，编号1的集合为 $\{1,2\}$，编号2的集合为 $\{3\}$，第3次 `solve` 函数调用返回。

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

对于 $100\%$ 的数据，满足 $1\le n\le 10^6$；$1\le x_i\le i$；$1\le l_i\le r_i\le i$；

你输出的插入操作或回答查询中，集合编号在范围 $1$ 到 $2\times 10^7$ 内，插入操作的 $y$ 必须是序列中已有的元素。

子任务1（10分）：保证 $1\le n\le 10^3$；

子任务2（10分）：保证 $l_i=1,\;r_i=i$；

子任务3（10分）：保证 $x_i=i$；

子任务4（20分）：保证 $1\le n\le 10^4$；

子任务5（10分）：保证 $1\le n\le 10^5$；

子任务6（20分）：数据随机生成，其中 $n=10^6$， $(l_i,r_i)$ 和 $x_i$ 分别在所有可能的情况中随机选取。

子任务7（20分）：无特殊限制。

对子任务6，$(m_1,m_2)=(64,64)$；

对其余子任务，$(m_1,m_2)=(64,256)$。


title: [JRKSJ R3] a question

background: 这是一个问题。

description:
现在有一棵 $n$ 个结点的树 $\text{T}$，边带权，结点的编号为 $[1,n]$ 的排列。

设 $\text{G}$ 为 $\text{T}$ 的补图。对于 $\text{G}$ 上的每一条边 $(x,y)$，该边的权值为 $\text{T}$ 上 $x\rightarrow y$ 的路径上的边权和。

设 $dis(x,y)$ 为 $\text{G}$ 上 $x,y$ 两点之间的最短路径的长度。若 $x,y$ 两点不连通，则令 $dis(x,y)=0$。

求 $\displaystyle\sum_{i=1}^{n-1} \sum_{j=i+1}^n dis(i,j)$。

inputFormat:
输入的所有数都为整数。

第一行一个数 $n$。\
接下来 $n-1$ 行每行三个数 $u,v,w$ 表示 $\text{T}$ 中有一条连接 $u,v$ 且边权为 $w$ 的边。

outputFormat: 输出一个数表示答案，由于答案很大，请对 $10^9+7$ 取模。


title: 【模板】Meissel-Lehmer

description:
给定整数 $n$，求出 $\pi(n)$ 的值。

$\pi(n)$ 表示 $1 \sim n$ 的整数中质数的个数。

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

outputFormat: 一行，一个整数，表示所求的值。


title: [✗✓OI R1] 前方之风

background:
>「不错的恶意。」
> 女性呵呵笑道。
>「但是，如果向我发出恶意，你可是会死哦？」

你不知道什么动作会被算作发出恶意，所以你决定做一道题来分散自己的注意力。

description:
给出一个长度为 $n$ 的序列 $a$ 和 $q$ 个询问，第 $i$ 个询问给出 $k_i$。对于每次询问，你需要进行以下操作：
1. 求出剩下的数的平均数 $\mathit{avg}$。
2. 将剩下的数中 $<\mathit{avg}-k_i$ 的数删去。
3. 重复以上两个步骤直到所有数都不会被删去。
4. 输出最后会剩下几个数。

**注意：询问之间是独立的，也就是说，不会真的删去那些数。**

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

第一行一个整数 $T$，表示测试数据的数量。
对于每一组数据，第一行两个整数 $n,q$，表示数字个数和询问数量。
接下来一行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。
接下来一行 $q$ 个整数，第 $i$ 个整数表示 $k_i$。

outputFormat: 输出共 $T$ 行，每行输出 $q$ 个整数，第 $i$ 个数表示第 $i$ 次询问最终会剩下几个数。


title: 平面最近点对（加强加强版）

background:
[P1429 平面最近点对（加强版）](https://www.luogu.com.cn/problem/P1429)里最高赞题解写道：

> 我们充分发扬人类智慧：
> 将所有点全部绕原点旋转同一个角度，然后按 $x$ 坐标排序
> 根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太远
> 所以我们只取每个点向后的 $5$ 个点来计算答案
这样速度快得飞起，在 $n=1000000$ 时都可以在 1 s 内卡过

当然，这是错的。

description: 给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$，请输出距离最近的两个点的距离。

inputFormat:
输入第一行为一个正整数 $n$，表示点数。

接下来 $n$ 行，第 $i$ 行为用空格隔开的整数 $x_i, y_i$，表示 $p_i = (x_i, y_i)$。

输入保证：没有两个坐标完全相同的点。

outputFormat:
输出一行，包含一个整数 $D^2$，表示距离最近的两个点的距离的**平方**。

由于输入的点为整点，因此这个值一定是整数。

hint:
对于第二组样例，$(1, 9)$、$(0, 10)$ 两个点最近，距离为 $\sqrt 2$，因此你需要输出 $2$。

### 数据范围

对于 $100 \%$ 的数据，$2 \leq n \leq 4 \times 10^5$，$-10^7 \leq x_i, y_i \leq 10^7$。

本题目标复杂度是 $O(n \log ^2 n)$。设置 350ms 时限的原因是：
1. $O(n \log ^2 n)$ 参考代码使用 `cin` 不会 TLE。最快的 std 能 $<$ 100ms。
2. @wlzhouzhuan 的程序能恰好在 350ms 内跑 $1000n$ 次检查。
3. 150 组测试数据，为了防止卡评测。


title: 「MCOI-08」Fill In

description:
Dream 有一个长度为 $n$（$1\le n\le 10^5$）的正整数数组 $a_1,a_2,\dots,a_n$，其中对于 $i=1,2,\dots,n$，满足 $1\le a_i\le 1000$。

他计算了前缀和数组 $p_i=a_1+a_2+\dots+a_i$，保证对于 **原前缀和数组** 有任意 $1 \le i <n$ 都有 $p_i<p_{i+1}$。

现在 Tommy 偷走了这个数组以及将 $p$ 的若干个元素替代为 $-1$。给定当前的 $p$ 数组，请恢复任意一组合法 $a_1,a_2,\dots,a_n$，可证明一定存在一个数组 $a_i$ 满足要求。

inputFormat:
本题有多组数据，第一行一个正整数 $t$，为数据组数。接下来 $t$ 组数据，其中对于每一组数据：

第一行一个整数 $n$。

第二行 $n$ 个整数 $p_i$ 代表前缀和序列。

outputFormat:
对于每一组数据：

一行 $n$ 个整数代表一组满足要求的 $a_i$。

hint:
#### 样例 1 解释

输出的序列 $a_i$ 一定满足要求：

- $p_1=10=a_1$；
- $p_3=20=a_1+a_2+a_3$；
- $p_5=30=a_1+a_2+a_3+a_4+a_5$。

#### 数据规模与约定

对于 $100\%$ 的数据，$1\le n,\sum n\le 10^5$，并保证存在至少一个合法 $a$ 数组。

 - Subtask 1（50 pts）：对于 $i=1,2,\dots,n$，$p_i\neq -1$；
 - Subtask 2（30 pts）：保证不存在 $i$ 使得 $p_i=p_{i+1}=-1$；
 - Subtask 3（20 pts）：无特殊限制。


title: 「Wdcfr-1」Alice Wins!  (easy version)

description:
**The difference between the versions is the limit of operations.**

Alice is a cute girl who has a lot of dolls.

There are $4\cdot n$ dolls playing *rock-paper-scissors*. They are divided into two teams: Team A and Team B. Each team contains $2\cdot n$ dolls.

A total of $2\cdot n$ rounds of the game will be played. In the $i$-th round, the $i$-th doll in Team A will play against the $i$-th doll in Team B. If the doll in Team A wins, Team A will get $1$ point. If it loses, Team A will lose $1$ point. If it ties, Team A will not get points.

Alice knows all the dolls' choices in this game. To be precise, she uses two arrays $a$ and $b$ to represent the choices of the dolls in the two teams. $a_i$ means the choice of the $i$-th doll in Team A, and $b_i$ means the choice of the $i$-th doll in Team B. In this question, we use $1$ for rock, $2$ for scissors, and $3$ for paper.

Now for **each team**, Alice wants to change the choices of **at most** $n$ dolls to make the score of Team A as high as possible.

Find the maximum score of Team A and its construction method. If there are multiple answers print any of them (you still have to maximize the score of Team A).

inputFormat:
Each test contains multiple testcases. The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains one integer $n$.

Then two lines follow, containing an array $a$ of length $2\cdot n$ and an array $b$ of length $2\cdot n$, respectively.

outputFormat:
For each test case, print three lines.

The first line contains one integer, the maximum score of Team A.

The second line contains an array $a'$ of length $2\cdot n$, which represents the $a$ array after Alice's modification. For integers $1$ to $2\cdot n$, if $a_i \ne a'_i$, then it means you have modified the choice of one player in Team A.

The third line contains an array $b'$ of length $2\cdot n$, which represents the $b$ array after Alice's modification. For integers $1$ to $2\cdot n$, if $b_i \ne b'_i$, then it means you have modified the choice of one player in Team B.

translation:
AB 每队 $2n$ 人正在玩石头剪刀布。A 队第 $i$ 个人出 $a_i$，B 队第 $i$ 个人出 $b_i$。编号相同的人会对战。若 A 队赢则加一分，平不得分，输扣一分。你可以**至多**改变**每队** $n$ 个人的出拳方案，使得 A 队的得分最高。输出得分的最大值和任意一组构造方案。

本题中，我们用 $1$ 代表石头，$2$ 代表剪刀，$3$ 代表布。

hint:
### Explanation

For the first test case, we can change $a_2$ to $1$ and $b_1$ to $2$. Then Team A can get $2$ points. It can be proved that this is the maximum score that Team A can get.

For the second test case, we can change $a_1$ to $3$ and $a_2$ to $1$.

### Constraints

$1\le T,n \le 10^5;\ 1\le a_i,b_i \le 3$. The sum of $n$ over all test cases  $\le 10^5$.


title: 「MCOI-08」Dantalion

background: And thus it is Tairitsu's turn to gain  the upper hand.

description:
给定一个长为 $n$（$1\le n\le 6\times 10^5$）的非负整数序列 $a_0,a_1,\dots,a_{n-1}$（$0\le a_i<2^{30}$）。

有 $q$ 个问询（$1\le q\le 10^6$）。

每次问询两个整数 $l,r$（$0\le l\le r<n$），有多少对整数 $x,y$ 满足：

 - $l\le x\le y\le r$；
 - $\forall i,j\in S\ :i\oplus j\in S$，其中 $S:=\{a_k\}_{k=x}^y$。

Tip: 本题总时限较大，故请减少无意义提交量（如高复杂度暴力或是直接提交所给尚需完善的代码等）。

inputFormat:
由于本题数据较多，您不需要输入输出，请完善以下程序中的 `init(int, int, vector<int>)` 和 `solve(int, int)` 函数，并提交。正解不依赖于其模板。

```cpp
#include <bits/stdc++.h>
using namespace std;

void init(int n, int q, vector<int> a) {
  // implement...
}

long long solve(int l, int r) {
  // implement...
}

int main() {
  int n, q;
  uint64_t s;
  cin >> n >> q >> s;
  string r;
  cin >> r;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    for (int s = 5 * i; s < 5 * i + 5; s++)
      a[i] = (a[i] * 64 + (int)(r[s]) - (int)('0'));
  init(n, q, a);
  uint64_t state = 0;
  auto splitmix64 = [&](uint64_t v) {
    uint64_t z = (v + 0x9e3779b97f4a7c15);
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
    z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
    return z ^ (z >> 31);
  };
  mt19937_64 rng(s);
  for (int i = 0; i < q; i++) {
    int l = (rng() ^ state) % n;
    int r = (rng() ^ state) % n;
    long long ans = solve(min(l, r), max(l, r));
    state = splitmix64(state + ans);
    if ((i + 1) % (1 << 15) == 0)
      cout << state << endl;
  }
  cout << state << endl;
}
```

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

对于 $100\%$ 的数据，$1\leq n\le 6\times 10^5,1\le q\leq 10^6$，$0 \le a_i < 2^{30}$，$0 \le l \le r < n$。

对于 $100\%$ 的数据，输入合法。

- Subtask 1（5 pts,~~Tutorial~~）：$1\le n,q\le 10^2$。
- Subtask 2（7 pts,~~Tutorial~~）：$1\leq n,q\leq 10^3$
- Subtask 3（11 pts,~~PST 5.0~~）：$1\leq n,q\leq 10^4$。
- Subtask 4（17 pts,~~PRS 8.2~~）：$1\leq n,q\leq 10^5$。
- Subtask 5（61 pts,~~FTR 10.9~~）：$1\leq n\le 6\times 10^5,1\le q\leq 10^6$。

为什么要多个 $1$ 分呢，因为谱师打本曲时性了 $1$ Lost.

Idea: Powerless; Solution: ccz181078&noip&w33z; Code: w33z; Data: w33z

This problem was added on 2022.4.10. Thanks for their help.

The data was strengthened on 2022.4.27 by w33z.

2022.4.10 - 2022.5.4 : 25 days 1st kill (水军带你飞).

2022.4.10 - 2022.5.17 : 38 days 2nd kill (WhisperingSnowflakes).

2022.4.10 - 2022.6.9 : 61 days 3rd kill (Verdandi).