title: [蓝桥杯 2020 省 AB3] 画中漂流

description:
在梦境中，你踏上了一只木䇝，在江上漂流。

根据对当地的了解，你知道在你下游 $D$ 米处有一个峡谷，如果你向下游前进大于等于 $D$ 米则必死无疑。

现在你打响了急救电话，$T$ 秒后救援队会到达并将你救上岸。水流速度是 $1 \mathrm{~m} / \mathrm{s}$，你现在有 $M$ 点体力。每消耗一点体力，你可以划一秒桨使船向上游前 进 $1 \mathrm{~m}$，否则会向下游前进 $1 \mathrm{~m}$ (水流)。$M$ 点体力需在救援队赶来前花光。因为江面太宽了，凭借你自己的力量不可能上岸。

请问，有多少种划桨的方案可以让你得救。

两个划桨方案不同是指：存在某一秒钟，一个方案划桨，另一个方案不划。

inputFormat: 输入一行包含三个整数 $D$，$T$，$M$。

outputFormat: 输出一个整数，表示可以让你得救的总方案数，答案可能很大，请输出方案数除以 $1000000007$（即 $10^9+7$）的余数。

hint:
对于 $50 \%$ 的评测用例，$1 \leq T \leq 350$。

对于所有评测用例，$1 \leq T \leq 3000,1 \leq D \leq T，1 \leq M \leq 1500$。

蓝桥杯 2020 第三轮省赛 AB 组 I 题。


title: [蓝桥杯 2020 省 AB3] 旅行家

type: P

description:
从前，在海上有 $n$ 个岛屿，编号 $1$ 至 $n$。居民们深受洋流困扰，无法到达比自己当前所在岛屿编号更小的岛屿。经过数年以后，岛屿上的人数随着岛屿的编号递增（可能相等）。作为一名出色的旅行家（$\mathrm{RP}$ 学家），你想从 $1$ 号岛屿出发开启一次旅程，以获得更多的 $\mathrm{RP}$，因为受到海洋的洋流影响，你只能去到比当前岛屿编号更大的岛屿。因为你比较善良，你会在离开一个岛屿的时候将你的 $\mathrm{RP}$ 分散给岛民，具体地：你的 $\mathrm{RP}$ 会除以 $2$（用去尾法取整，或者说向零取整）（当你的 $\mathrm{RP}$ 小于零时，岛民也依旧要帮你分担，毕竟你们已经建立起了深厚的友谊)。

第 $i$ 号岛屿有 $T_{i}$ 人，但是你很挑剔，每次你从 $j$ 号岛屿到达 $i$ 号岛屿时，你只会在到达的岛屿上做 $T_{i} \times T_{j}$ 件好事（一件好事可以获得 $1$ 点 $\mathrm{RP}$ )。

唯一不足的是，由于你在岛上住宿，劳民伤财，你会扣除巨量 RP，第 $i$ 号岛屿的住宿扣除 $F_{i}$ 点 $\mathrm{RP}$。

注意: 将离开一个岛屿时，先将 $\mathrm{RP}$ 扣除一半，再扣除住宿的 $\mathrm{RP}$，最后在新到达的岛屿上做好事，增加 $\mathrm{RP}$。离开 $1$ 号岛屿时需要扣除在 $1$ 号岛屿住宿的 $\mathrm{RP}$，当到达这段旅程的最后一个岛屿上时，要做完好事，行程才能结束，也就是说不用扣除在最后到达的岛屿上住宿的 $\mathrm{RP}$ 。

你因为热爱旅行（RP），所以从 $1$ 号岛屿开始旅行，初始时你有 $0$ 点 $\mathrm{RP}$。你希望选择一些岛屿经过，最终选择一个岛屿停下来，求最大的 $\mathrm{RP}$ 值是多少?

inputFormat:
输入的第一行包含一个数 $n$，表示岛屿的总数。

第二行包含 $n$ 个整数 $T_{1},T_{2},\cdots,T_{n}$，表示每个岛屿的人口数。

第三行包含 $n$ 个整数 $F_{1},F_{2},\cdots,F_{n}$，表示每个岛屿旅馆损失的 $\mathrm{RP}$。

outputFormat: 输出一个数，表示最大获得的 $\mathrm{RP}$ 值。

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

从一号岛屿直接走到三号岛屿最优，初始 $0$ 点 $\mathrm{RP}$，扣除一半取整变成 $0$ 点。扣除在一号节点住宿的 $1 \mathrm{RP}$，在三号岛屿做好事产生 $4 \times 5=20$ 点 $\mathrm{RP}$。最终得到 $19$ 点 $R P$ 。

**【评测用例规模与约定】**

对于 $20 \%$ 的评测用例，$1 \leq n \leq 15$;

对于 $70 \%$ 的评测用例，$1 \leq n \leq 5000$;

对于所有评测用例，$1 \leq n \leq 5\times10^5,1 \leq T_{i} \leq 20000,1 \leq F_{i} \leq 2\times 10^8$。给定的 $T_{i}$ 已经按照升序排序。

建议使用 64 位有符号整数进行运算。

蓝桥杯 2020 第三轮省赛 AB 组 J 题。

Upd.2024.7.13 已添加hack数据


title: 求数列所有后缀最大值的位置

type: B

description:
给定一个数列 $a$，初始为空。有 $n$ 次操作，每次在 $a$ 的末尾添加一个正整数 $x$。

每次操作结束后，请你找到当前 $a$ 所有的后缀最大值的下标（下标从 1 开始）。一个下标 $i$ 是当前 $a$ 的后缀最大值下标当且仅当：对于所有的 $i < j \leq |a|$，都有 $a_i > a_j$，其中 $|a|$ 表示当前 $a$ 的元素个数。

为了避免输出过大，请你**每次操作结束后都输出一个整数**，表示**当前数列**所有后缀最大值的下标的按位异或和。

inputFormat:
第一行是一个整数，表示操作次数 $n$。
第二行有 $n$ 个整数，依次表示 $n$ 次操作所添加的整数 $x_i$。

outputFormat: 每次操作后请输出一行一个整数，表示当前数列所有后缀最大值下标的按位异或和。

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

对于全部的测试点，保证 $1 \leq n \leq 10^6$，$1 \leq x_i \lt 2^{64}$。


title: 「DTOI-2」星之影

background: >闻是白极影，见时方立竿。

description:
白极影化为立竿之人莅临人间，带来了星之函数 $f(x)$，它的值为最接近于 $\sqrt[4]x$ 的整数$\\$（即 $f(x)=\left\lfloor\sqrt[4]x+\dfrac12\right\rfloor$；$\lfloor u\rfloor$ 为对 $u$ 向下取整后的值）。

现有 $t$ 个数字 $n$，对于每个 $n$，立竿人想知道 $\sum\limits_{i=1}^n\dfrac1{f(i)}$ 的值是多少，请你告诉它吧。

---
~~因为立竿人很急，所以~~本题的 $t$ 组询问强制在线，后一个询问需通过前一个询问的答案生成。

可用以下 `C++` 代码生成（其他语言同理；需包含 `<stdio.h>`）：
```cpp
typedef long long ll;
char buf_ans[114];
ll next_n(double last_ans=0,ll get_n=0){
	//last_ans<n<=1e18
	sprintf(buf_ans,"%.6f",last_ans);
	for(ll i=0,x=0;;i++){
		if(buf_ans[i]=='.')return get_n^x;
		if(i&1)x*=10;
		else x=x*10+(buf_ans[i]^48);
	}
}
```
该函数第一个参数为上一次询问的答案（第一次询问时该值为 $0$，也就是说第一个数未经加密），第二个参数为这一次读入的被加密的数，函数返回解密后的 $n$。

inputFormat:
第一行一个整数 $t$，表示数据组数（询问次数）。

对于每组数据，仅一行一个整数表示加密后的 $n$（第一个 $n$ 未被加密）。

outputFormat: 每行输出一个六位小数，表示答案。

hint:
### 样例解释

样例#1 解密后各组询问分别是：
$$
\def{\r}{\cr\hline}
\def\arraystretch{1.5}\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{t}&1&2&3&4&5&6&7\r
\textbf{n}&1&4&8&89&2022&1145141919810&1\r
\end{array}
$$
### 数据范围

**本题采用捆绑测试。**
$$
\def\arraystretch{1.5}\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & t= & n\le&\bm{\textbf{Score}} \cr\hline
1 & 10&10^6 & 2 \cr\hline
2&1000&10^6&13\cr\hline
3&100&10^9&15\cr\hline
4 &1000&10^{18}&40\cr\hline
5 &%\text{No Special Constraints}
5\times10^5&10^{18}& 30 \cr\hline
\end{array}
$$

对于 $100\%$ 的数据，$10 \le t \le 5\times10^5$，$1 \le n \le 10^{18}$。

### 计分规则

本题采用 $\textbf{Special Judge}$，令你输出的答案为 $\text{pans}$，标答答案为 $\text{jans}$，如果 $\vert \text{pans}-\text{jans}\vert<\text{jans}\times10^{-5}$ 那么该组数据通过，在一个测试点内只有所有 $t$ 组数据通过该测试点才算通过。

注意后一个 $\text{Subtask}$ 对前一个 $\text{Subtask}$ 有依赖关系，即如果你没有在前一个 $\text{Subtask}$ 拿到分，那么你即使通过后一个 $\text{Subtask}$ 的所有测试点，你也无法拿到后面的分数。


title: 求区间所有后缀最大值的位置

description:
给定一个长度为 $n$ 的数列 $a$，对于其中每个长度为 $k$ 的子区间，请你求出这个这个子区间构成的数列的所有后缀最大值的位置个数。

一个下标 $i$ 是是数列 $b$ 的后缀最大值下标当且仅当：对于所有的 $i < j \leq |b|$，都有 $b_i > b_j$，其中 $|b|$ 表示 $b$ 的元素个数。

inputFormat:
第一行是两个整数，依次表示操作次数 $n$ 和子区间长度 $k$。
第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

outputFormat: 共输出 $n - k + 1$ 行每行一个整数，按左端点从小到大的顺序依次输出每个子区间构成的数列的后缀最大值位置个数。

hint:
### 样例 1 解释

第一个子数列：$2, 1, 3$。其中 $3$ 是后缀最大值。
第二个子数列：$1, 3, 5$，其中 $5$ 是后缀最大值。
第三个子数列：$3,5,4$，其中 $5$ 和 $4$ 是后缀最大值。

### 数据规模与约定

对于全部的测试点，保证 $1 \leq k \leq n \leq 10^6$，$1 \leq x_i \lt 2^{64}$。


title: 「DBOI」Round 1 DTTM

background: 张则雨和穆制程坐在天台上看着满天的星辰。在他们的世界，流行一种连接星星的活动。他们对此有一种浪漫的诠释：如果连不完，剩下的一颗星星就是身旁的人；如果连得完，那身边的人和自己都是星星。

description:
星空中有 $n$ 颗星星，第 $i$ 颗位于坐标 $(x_i,y_i)$。你需要把星星连接成满足张则雨的如下需求：

- 每一颗星星都是且仅是一条线段的端点，所有线段互不相交（包括端点）。
- 所有线段左右端点 $|x_l-x_r|$ 之和有最小值。

然而张则雨有点笨，并不知道应该怎么连。穆制程知道你是地球上最聪明的人，于是告诉你 $n$ 颗星星的坐标，你需要输出连接方案或者报告无解。

inputFormat:
第一行 $n$ 表示星星的数量。

从第二行开始，共 $n$ 行，每行两个整数。第 $i+1$ 行表示第 $i$ 颗星星的 $(x_i,y_i)$ 坐标。

outputFormat:
第一行输出所有线段左右端点 $|x_l-x_r|$ 的和的最小值。

接下来每一行输出两个编号，表示为了得到最小值，你每条线段连接的星星的编号。

如果有多种可能的连接方案，输出任意一种。如果无解在第一行输出 $-1$。


title: 「DBOI」Round 1 烟花

background:
回忆本身就是惩罚，惩罚那些不愿往前走的人，将他们困在那条小巷子里，怎么也走不出去。

每一年都有烟花，唯独那一年的烟花最好看。

“我要对烟花许愿，许我们永远在一起。”

“就算不许愿，我们也会永远在一起的。”

再后来，死了的人被葬在了那座山上，活着的人被记忆困在了那条巷中。今天的我们听到这个故事，只是想再放一次故事里的烟花，放给那些再没能陪身旁的人看到一次烟花的人。

description:
烟花在夜空中绽放连成一片，我们把这些连成一片的烟花看成一棵含有 $n$ 个点的有根树，根为最早点燃的烟花 $1$。

烟花有红蓝两种颜色，为了方便，我们对这棵树黑白染色。最初有 $p$ 个限制，一条限制形如 $(x_i,y_i)$，表示树中编号为 $x_i$ 的点的子树中黑点只能**恰好**有 $y_i$ 个。当年，他们认为满足其**子树内所有有限制点的限制**的子树是**均好的子树**。显然，要想使一个子树成为均好的子树，可能有**多种染色方法**。

你需要回答以下两种询问：

- `Z k c`，表示给点 $k$ 以均等概率在 $[0,c]$ 中选择一个数 $f$，然后给点 $k$ 直接加上 $f$ 个没有限制的儿子，其它儿子状态不变。问点 $k$ 为根的子树成为**均好的子树**的期望染色方法数量。
- `H k`，表示如果去掉 $k$ 的所有有限制儿子的限制，询问 $k$ 为根的子树成为**均好的子树**的染色方法数量。

我们并没有必要点燃更多的烟花，因此所有的询问都是相互独立的，没有询问会真的影响原树。

我们深知可能复现不了当时完整的情况，历史太过斑驳，可能的烟花组合成千上万，因此你只需要得到答案对 $998244353$ 这个大质数取模的值。

inputFormat:
第一行两个整数 $n,p$，表示树的节点个数与限制个数。

接下来 $n-1$ 行，每行两个数 $u,v$，表示 $u,v$ 之间有一条直连边。这 $n-1$ 行表示树的结构。

接下来 $p$ 行，每行两个数 $(x_i,y_i)$，表示限制以 $x_i$ 点为根的子树，需要恰好存在 $y_i$ 个黑点在其子树内。

接下来一行一个整数 $q$，表示询问个数。

接下来 $q$ 行，每行一个字符另加 $1$ 或 $2$ 个整数表示题目中说明的询问。

outputFormat:
为了减小输出量，我们假设第 $i$ 个询问（$i$ 从 $1$ 开始）的答案为 $ans_i$，你只需要输出一行，表示所有询问的 $i\times ans_i$ 的异或和。最终的异或和以及每一个 $i\times ans_i$ 都**无需**对 $998244353$ 取模，但每个询问的答案 $ans_i$ 是对其取模后的答案。

**注意：std 不依赖于输出方式。也就是说，std 可以独立获取每一个询问的答案。**

hint:
### 样例解释

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

如图为样例 #1 的烟花，构成一个有 $14$ 个点，其中 $5$ 个限制点的树。与题目中不同的是，我们用红色烟花表示限制点，蓝色烟花表示无限制点。红色烟花右上角的浅蓝色数字表示其限制的黑点数量。

初始情况下每一个点为根子树的合法烟花燃放方法数量如下（从左至右第 $i$ 项表示以第 $i$ 个点为根的子树的答案）：

$$
[320,10,4,4,2,8,1,2,2,1,2,2,1,1]
$$

下面我们给出询问的答案与部分解释：

- `Z 2 5`，为 $2$ 号点添加 $i$ 个儿子后的 $2$ 号点子树内合法烟花燃放数量表示为此数列的第 $i+1$ 项：$[10,20,35,56,84,120]$。总期望即为 $\frac{325}{6}$。对 $998244353$ 取模之后得到 $166374113$。
- `H 14`，由于 $14$ 号点没有儿子，因此答案仍然为 $1$。
- `Z 7 3`，共有 $10$ 种可能的合法烟花燃放方案，总期望即为 $\frac{5}{2}$，对 $998244353$ 取模之后得到 $499122179$。
- `Z 7 1` 的答案为 $499122178$。
- `H 6` 的答案为 $16$。
- `Z 1 9` 的答案为 $32736$。
- `H 1`，去除 $1$ 的所有有限制儿子（仅有节点 $2$）的限制后有 $1024$ 种可能的合法烟花燃放方案。
- `H 8` 的答案为 $8$。
- `H 12` 没有儿子，因此答案不变，此询问的答案仍然为 $2$。
- `Z 10 1` 的答案为 $1$。

最终，所有询问的 $i\times ans_i$ 的异或和即为 $665340330$。

### 数据范围

**请注意常数因子对程序效率的影响。**

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

下面定义 $S=3\times 10^5$。

| $\rm Subtask$ | $n$ | $q$ | $y_i$ | $c$ | 特殊性质 | 得分 | 子任务依赖 |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $\leqslant 10$ | $\leqslant 10$ | $\leqslant 5$ | $\leqslant 5$ | 无 | $10$ | 无 |
| $2$ | $\leqslant 200$  | $\leqslant 200$ | $\leqslant 200$ | $\leqslant 200$ | 无 | $15$ | $1$ |
| $3$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $\leqslant 10$ | 无 | $20$ | $1,2$ |
| $4$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $A$ | $15$ | 无 |
| $5$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $B$ | $20$ | 无 |
| $6$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | 无 | $20$ | $1,2,3,4,5$ |

特殊性质 $A$：$p=0$。

特殊性质 $B$：满足不存在 `Z` 询问。

对于 $100\%$ 的数据，存在输入的所有数均为 $\leqslant S$ 的整数。特别地，存在 $0\leqslant p\leqslant n$，输入的任何树的节点编号 $x$ 都满足 $1\leqslant x \leqslant n$。保证输入的询问字符都为 `Z` 或 `H`，输入的一定是一棵树。保证对于所有限制存在 $x_i\neq x_j(i\neq j)$。

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

冬天的最后一场雪如约而至，很快又要迎来一个新的春天。万物都在等待复苏，可峰城里的一个小巷子，再也不复往日繁荣。

八十多年过去，我们早已找不到当初的巷子，只留下这样一个故事。

感谢你放的烟花。


title: 「PEOI Rd1」异或（xor）

description:
给定两个正整数 $n,m$，求：

$$\sum_{i=1}^{n}\sum_{j=1}^{m}\left(i \oplus j\right) $$

其中，$\oplus$ 表示按位异或运算（即 C++ 中的 `^` 符号）。答案对 $998244353$ 取模。

inputFormat:
本题包含多组数据。

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

接下来 $T$ 行，每行输入两个整数 $n,m$。

outputFormat: 输出共 $T$ 行，每行一个整数，表示每组询问的答案。


title: 「TAOI-1」Pentiment

background:
近日（存疑），一款名为闊靛緥婧愮偣的游戏更新了它的 4.0 版本。在这个版本中某谱面中的大直角蛇给玩家们留下了深刻的印象……

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

description:
我们规定，在 $n$ 行 $m$ 列的网格中，“直角蛇”是这样一条路径：

- 从最下方（第一行）的某个格子的中心开始，在最上方（第 $n$ 行）的某个格子的中心结束。
- 每次可以向上、向右或向左移动一格，每次移动后都到达某个格子的中心（**不能向下移动**）。
- 不能重复经过同一个格子。

特别地，为了给你增加一些考验，我们规定有一些格子是“直角蛇”不能经过的。

请你统计在给定的网格中存在多少种这样的“直角蛇”。答案对 $998244353$ 取模。

inputFormat:
第一行三个整数 $n, m, q$，代表网格的行数和列数，以及限制的数量。

接下来的 $q$ 行，每行两个整数 $x_i, y_i$，代表第 $x_i$ 行第 $y_i$ 列的格子不能经过。保证同一个格子至多出现一次。保证所有格子按照 $x_i$ 为第一关键字，$y_i$ 为第二关键字，从小到大排序后给出。（我们规定最下方的格子的行数为 $1$，最左侧格子的列数为 $1$）

outputFormat: 共一行一个整数，代表符合条件的“直角蛇”数量对 $998244353$ 取模的结果。

hint:
### 数据范围

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

- Subtask 1（10 points）：$n \leq 10^6$，$m \leq 2$。
- Subtask 2（10 points）：$q=0$。
- Subtask 3（15 points）：$n,m \leq 10^4$。
- Subtask 4（20 points）：$n \leq 10^4$。
- Subtask 5（20 points）：$m \leq 10^4$。
- Subtask 6（25 points）：无特殊限制。

对于所有测试数据，$2 \leq n \leq 10^9$，$1 \leq m \leq 10^9$，$0 \leq q \leq 10^5$，$1 \leq x_i \leq n$，$1 \leq y_i \leq m$。

### 样例解释

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

如图，样例一中共有八种满足条件的“直角蛇”。

对于样例二，不存在满足条件的“直角蛇”。

---

在寂若死灰中屈服。

在飘忽不定中屈服。

在功亏一篑中屈服。

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


title: 「PEOI Rd1」k 叉堆（heap）

background:
**数据范围较赛时加强**。

- 2023.04.25：发现 1.50s 时限过于卡常，扩大到 2.00s。

description:
给定一个 $1 \sim n$ 的序列，每个位置 $i$ 有 $k$ 个参数 $a_{i,1},a_{i,2},\dots,a_{i,k}$。已知这个序列是一个按照大根堆的 bfs 序得到的序列。

bfs 序，即按照下图中**红色数字编号的顺序**：

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

一个大根堆满足条件，当且仅当所有子节点的**所有** $k$ 个权值都小于等于父节点，即 $\forall u\in[1,n],\forall v\in son(u),\forall j \in [1,k],a_{v,j} \leq a_{u,j}$。

假设这个大根堆是**完全 $m$ 叉树**，求所有 $m \in [1,n-1]$，使得这个 $m$ 叉堆**满足条件**的 $m$ 的取值。

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

接下来 $k$ 行，每行 $n$ 个整数，表示给定的序列。其中，第 $i+1$ 行第 $j$ 列表示的是 $a_{j,i}$。

可以理解为，分成 $k$ 行给出了所有位置的 $k$ 个参数。

outputFormat:
第一行一个整数 $A$，表示所有可能的 $m$ 的取值数量。

接下来一行 $A$ 个整数，表示所有的可能的 $m$ 的取值。


title: [语言月赛202211] String Problem

background: 扶苏很喜欢研究制糊串问题。

description:
扶苏给你了两个长度为 $n$ 的字符串 $s$ 和 $t$，请你判定这两个字符串是否相同。

扶苏觉得这个问题太简单了，所以她还给出了 $q$ 次操作，每次操作是修改其中一个字符串的某个位置的字符。每次操作过后，都请你回答一次 $s$ 和 $t$ 是否相同。

字符串下标从 1 开始编号。例如，若字符串 $s$ 为 $\texttt {abc}$，要将它的第二个位置修改为 $d$，则修改后的字符串为 $\texttt{adc}$。

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

输入的第一行是一个整数 $T$，表示数据组数。接下来按顺序给出每组数据的输入：

对每组数据，第一行是两个整数，依次表示字符串长度 $n$ 和操作的次数 $q$。
第二行是一个长度为 $n$ 的字符串，表示 $s$。
第三行是一个长度为 $n$ 的字符串，表示 $t$。
接下来 $q$ 行，每行两个整数 $o, p$ 和一个字符 $c$，其中 $o$ 是 $0$ 或 $1$。
- 若 $o = 0$，则表示将字符串 $s$ 的第 $p$ 个字符修改成 $c$。
- 若 $o = 1$，则表示将字符串 $t$ 的第 $p$ 个字符修改成 $c$。

outputFormat:
对每组数据，依次输出答案。

每组数据共需要输出 $q + 1$ 行。
首先对初始给定的字符串 $s$ 和 $t$，若他们相同，则输出一行 `Yes`，否则输出一行 `No`。
接下来，对每次操作，若操作后两字符串相同，输出一行 `Yes`，否则输出一行 `No`。

samples:
2
3 2
abc
abc
1 2 d
0 2 d
5 0
abdce
acdce

hint:
### 样例 1 解释

对第一组数据：
- 输入的字符串 $s = t$，故第一行输出为 `Yes`。
- 第一次操作，将 $t$ 的第 2 位改为 $\texttt d$，此时 $s = \texttt{abc}$，$t = \texttt{adc}$，$s \neq t$，故第二行输出为 `No`。
- 第二次操作，将 $s$ 的第 2 位改为 $\texttt d$，此时 $s = \texttt{adc}$，$t = \texttt{adc}$，$s = t$，故第三行输出为 `Yes`。

对第二组数据：
- 输入的字符串 $s \neq t$，故第四行输出为 `No`。

### 数据规模与约定

本题共 10 个测试点，各测试点的规模见下表

| 测试点编号 | $n = $ | $q =$ |
| :-: | :-: | :-:|
| 1 | $1$ | $0$ |
| 2 | $1000$ | $0$ |
| 3 | $1000$ | $0$ |
| 4 | $1000$ | $1000$|
| 5 | $1000$ | $1000$ |
| 6 | $1000$ | $1000$ |
| 7 | $10^6$ | $10^6$ |
| 8 | $10^6$ | $10^6$ |
| 9 | $10^6$ | $10^6$ |
| 10 | $10^6$ | $10^6$ |

对全部的测试点，保证 $T = 5$，$s,t$ 均只含小写英文字母，输入的换行符不含 `\r`，$o \in \{0, 1\}$，$1 \leq p \leq n$，$c$ 为小写英文字母。

### 提示

请注意大量的数据读入输出对程序效率造成的影响。

By 一扶苏一


title: 星环防御工事

background: 来自河外星系的小行星群即将有组织地打击地球。

description:
据观测，一共会有共 $n$ 波小行星群攻击太阳系。每一波攻击有两个属性：$d_i,m_i$，表示第 $i$ 波攻击会在第 $d_i$ 个太阳日发动，小行星群的总质量为 $m_i$。如果不进行精准防御，太阳系或将面临灭顶之灾。于是你的上司将星环防御工事的建设任务交给了你。

准确来讲，星环防御工事每个太阳日最多可以击毁总质量为 $k$ 的小行星。对于某一个在第 $d$ 个太阳日出现的小行星群，如果星环防御工事不能在第 $d$ 或 $d+1$ 个太阳日将其击毁(或者仅能部分击毁)，那么该小行星群(或其残余部分)将会被移交给地球和平联合组织 TPC 去处理——你当然不希望到手的美差被别人抢走！

因此你现在想知道，你领导的星环防御工事最多可以击毁多少质量的小行星呢？

inputFormat:
第 $1$ 行共两个整数 $n,k$ ，表示共有 $n$ 波小行星群，每个太阳日最多击毁 $k$ 质量的小行星。

第 $2\sim n+1$ 行每行两个非负整数 $d_i,m_i$，含义见题目描述。

outputFormat: 共一行一个整数 $ans$ ，表示最多可以击毁多少的小行星总质量。

hint:
对于 $10\%$ 的数据，$1\leq n,\max\{d_i\} \leq 20$。

对于 $20\%$ 的数据，$1\leq n,\max\{d_i\}\leq 600$。

对于 $40\%$ 的数据，$1\leq n,\max\{d_i\}\leq 5000$。

对于另外 $10\%$ 的数据，保证全部小行星群的 $m_i$ 总和不超过 $k$ 。

对于 $100\%$ 的数据，$1\leq n,\max\{d_i\}\leq 3\times 10^5$，$0\leq m_i,k\leq 10^4$。


title: 新的家乡

background: 2102 年，太阳系的生态终于不再支持人类的生存。人类打算沿着之前建好的星际长途路线去往金牛座蟹状星云中的某行星 $\beta$ 谋求发展。

description:
你作为第一批科研人员，提前来到了 $\beta$ 星建造基地。

$\beta$ 星盛产锰钛矿石。基地需要一些**高度相同**的柱子，而每根柱子都需要由**恰好**两根锰钛矿石顺次连接组成。例如，若你有两根高度分别为 $h_x,h_y$ 的锰钛矿石，那么你可以用两者合成为一根高度为 $h_x+h_y$ 的柱子。每根锰钛矿石**显然至多被使用一次**。

现在你来到了 $\beta$ 星的锰钛矿场，摆在你面前的是 $n$ 根高度分别为 $h_i$ 的锰钛矿石。经过严密思考后你发现，房屋的牢固程度应该取决于柱子的数目，而不是柱子的高度。所以你想知道，使用面前这 $n$ 根矿石最多可以建造出多少根高度相同的柱子？

但小花觉得这个问题太 easy 了，于是 ta 选择多问你一嘴：假设柱子高度均为 $h$，基地最多可以建出 $\mathrm{res}$ 根柱子，那么在柱子数目同为 $\mathrm{res}$ 时 $h$ 可以有几种不同的取值？

inputFormat:
输入共两行。

第一行共一个正整数 $n$，表示锰钛矿石的数量。

第二行共 $n$ 个正整数 $h_i$，含义见题目描述。

outputFormat: 输出共一行两个整数 $\mathrm{res}$ 和 $\mathrm{ans}$，分别表示最多的柱子数目以及最优答案下有多少种不同的高度方案。

hint:
额外样例见附加文件 `ex.in/out`。

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

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

对于 $70\%$ 的数据，$1\leq n\leq 10^5$。

对于 $100\%$ 的数据，$1\leq n\leq 10^6$，$1\leq h_i \leq 3\times 10^3$。


title: 球状精灵的传说

description:
你在人马座的三叶星云里，发现了一类新生物：球状精灵。

球状精灵是一类外形为标准椭球形的精灵。每只精灵有三个维度的**幅度** $\{r_1,r_2,r_3\}$，分别表示其三维世界中三个方向上的尺度。

而关于球状精灵有一个传说：族群中**声望值最高**的球状精灵会获得升入四维宇宙的机会。而某个幅度为 $\{r_1,r_2,r_3\}$ 的球状精灵的声望值 $\rho$ 定义为：

$$\rho=\left\lfloor{\frac{1}{4}\min\{r_1,r_2,r_3\}^3}\right\rfloor$$

其中 $\left\lfloor\right\rfloor$ 表示下取整。

同时，每只球状精灵可以选择与别的精灵**拥抱至多一次**，之后两者会合成为**一个新的球状精灵**。两只球状精灵能够拥抱，当且仅当它们**存在至少一个幅度面能够重合**。具体来讲，即需要两只精灵的幅度**存在至少两个值相同**。

例如，两只精灵三个方向上的幅度分别为 $\{a,x,y\}$ 和 $\{b,x,y\}$，那么他们可以选择拥抱并生成一只幅度为 $\{a+b,x,y\}$ 的新精灵。但是注意，精灵们都是漂浮在宇宙中的，所以他们可以任意旋转。比如幅度为 $\{x,y,z\}$ 的精灵可以任意旋转成为 $\{x,z,y\},\{z,x,y\},\{z,y,x\},\{y,z,x\},\{y,x,z\}$ 的精灵。**拥抱形成的新精灵不能再次参与拥抱。**

现在球状精灵们想知道，族群中能够升入四维宇宙的精灵，声望值最高能是多少？

请仔细阅读输入格式和输出格式以获取更详细的讯息。

inputFormat:
第 $1$ 行共一个正整数 $n$，表示族群中最初的球状精灵数目。最初全部的球状精灵都没有拥抱过。

第 $2\sim n+1$ 行，每行三个非负整数 $r_{i,1},r_{i,2},r_{i,3}$，分别表示编号为 $i$ 的球状精灵三个维度的幅度。

outputFormat:
第一行，输出一个整数 $opt$:

  - 当最优情况下，升入四维空间的球状精灵是最初未拥抱过的精灵之一时，$opt=0$。

  - 当最优情况下，升入四维空间的精灵是由原来的两只精灵拥抱生成时，$opt=1$。

第二行，有两种情况：

  - 当 $opt=0$ 时，输出一个整数 $i$，表示升入四维空间的精灵是编号为 $i$ 的精灵。

  - 当 $opt=1$ 时，输出两个整数 $i,j$，表示最终升入四维空间的精灵由编号为 $i,j$ 的精灵拥抱生成。

第三行，共一个整数，表示最优情况下升入四维空间精灵的声望值为多少。

如果最优解有多种方案，输出任意一种情况即可。


title: 探索未知

background:
下发文件：

<https://luogu-ipic.oss-cn-shanghai.aliyuncs.com/watujir2-jdi92.zip>

description:
2102 年，人类已经建立了从地球到室女座 $\alpha $ 星的星际通道。通道绵延数百光年。

而在通道上有许多路牌。第 $i$ 个路牌上写有一个分数 $\dfrac{a_i}{b_i}$ 和一个分数运算符 $+$ 或 $-$。

一开始，你的手上拿着一个数字 $0$。你沿着通道向后走。每走到一个路牌，**会用手上的数和路牌上的分数，用路牌上的运算符号进行计算，并把得到的新数拿在手中（丢弃掉手中原来的数）**。值得注意的是，如果你手中计算得到的数不是整数，则会保留既约分数的形式；否则直接保留整数形式。

现在你想知道，当你走到通道的末端时，手中拿着的数是多少？

inputFormat:
第 $1$ 行共一个正整数 $n$ 表示通道内共有 $n$ 个路牌。

第 $2\sim n+1$ 行每行三个正整数 $a_i,b_i,opt_i$ 表示第 $i$ 个路牌上写着的分数为 $\dfrac{a_i}{b_i}$，运算符为 $opt_i$。

其中，$+,-$ 两种运算分别用 $1,2$ 代替。

outputFormat:
共一行一个数。

若最终的结果可以保留为整数，则输出一个整数 $ans$ 表示结果。

否则，若最终的结果只能保留为分数，则需要以 $a/b$ 的形式输出一个分数 $\dfrac{a}{b}$。需要保证 $\dfrac{a}{b}$ 为既约分数，即 $\gcd(a,b)=1$ 。

需要注意，结果可能出现负数，此时需要保留负号。例如，若结果为 $-\dfrac{11451}{4}$，那么需要输出 `-11451/4`。

hint:
对于 $20\%$ 的数据，运算符只存在加法。

另有 $20\%$ 的数据，运算法只存在减法。

对于 $100\%$ 的数据，保证 $1\leq n\leq 10^3$，$0\leq a \leq 1000$，$0 < b \leq 1000$，保证答案以及过程中全部数值(整数部分/分子/分母)不超过 $2\times 10^9$。


title: [语言月赛202210] 标题修改

description:
某 E 写了一篇文章，标题为字符串 $S$，由小写英文字符和空格组成。

某 E 恪守规范，因此，字符串 $S$ 是由若干个单词组成的，单词之间由一个空格隔开。

编辑人员要求将单词中的字母的大小写做调整。具体的，对每个单词，编辑人员要求将**每个单词**中的第奇数个字母改成大写，第偶数个字母改成小写。

> 关于单词下标的定义：这里我们以 $1$ 为起始下标。也就是说，对一个长度为 $n$ 的单词，我们将字母从头到尾记作第一个、第二个、$\cdots$、第 $n$ 个。
>
> 举例：对单词 $\texttt{apple}$
> - 第一个字母为 $\texttt{a}$
> - 第二个字母为 $\texttt{p}$
> - 第三个字母为 $\texttt{p}$
> - 第四个字母为 $\texttt{l}$
> - 第五个字母为 $\texttt{e}$

某 E 要赶 ddl，请你帮她完成这个任务。

inputFormat: 输入一行一个字符串 $S$。

outputFormat: 输出一行一个字符串，代表修改后的标题。

samples:
i like eat apple
I LiKe EaT ApPlE

hint:
对于 $20\%$ 的数据，$|S|=1$；
对于另外 $30\%$ 的数据，标题仅由一个单词组成；
对于 $100\%$ 的数据，保证去除空格后的 $S$ 长度 $\le 10^6$。

如果想要使用 `char` 数组对整个 $S$ 进行存储，将数组大小调整至 $2 \times 10 ^ 6$ 以上即可。


title: 折线

description:
平面直角坐标系的第一象限内有一块左下角为 $(0,0)$ 右上角为 $(10^{100},10^{100})$ 的矩形区域，区域内有**正偶数**个整点，试求出这样一条从 $(0,0)$ 出发，到 $(10^{100},10^{100})$ 的在区域内部的折线：

- 折线的每一部分都平行于 $x$ 轴或 $y$ 轴。
- 折线不能经过给定的整点。
- 折线将整块区域分成包含给定整点个数相等的两块。
- 折线拥有尽可能少的折点。

可以证明一定存在一条满足限制的折线，你只需要输出满足限制的折线的折点数即可。

注意折点的坐标可以不是整数。

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

接下来的每组数据中，第一行一个**正偶数** $n$，表示给定的整点个数。

接下来 $n$ 行，第 $i$ 行两个正整数 $x_i,y_i$，表示给定的第 $i$ 个整点的坐标为 $(x_i,y_i)$。

outputFormat: 输出 $T$ 行，每行一个正整数，表示满足限制的折线的折点数。


title: 线段

description:
有一个初始为空的线段集，你需要处理 $q$ 组询问，每组询问的格式为如下三种之一：

1. 加入一条新线段 $[l_i,r_i]$。
2. 将线段集里所有与 $[l_i,r_i]$ 相交的线段修改为其与 $[l_i,r_i]$ 的交。
3. 求出线段集里所有与 $[l_i,r_i]$ 相交的线段与 $[l_i,r_i]$ 的交的长度和。

两条线段 $[a,b],[c,d]$ 相交，当且仅当 $\max\{a,c\} \leq \min\{b,d\}$，它们的交为 $[\max\{a,c\},\min\{b,d\}]$。

一条线段 $[a,b]$ 的长度为 $b-a$。

在部分测试点中，你需要**在线地**进行这些操作。

**注意：在本题中，线段可能退化为单点。**

inputFormat:
第一行两个正整数 $q$ 和 $type$，分别表示操作次数和强制在线参数。

接下来 $q$ 行，每行三个正整数 $opt,l_i',r_i'$，其中 $opt$ 表示操作类型。

我们记 $last$ 表示上一次 $3$ 询问的答案（$last$ 初始为 $0$），则真实的 $l_i = ( l_i' + type \times last ) \bmod ( 2 \times 10^5 + 1 ), r_i = ( r_i' + type \times last ) \bmod ( 2 \times 10^5 + 1 )$。

数据保证 $1 \leq l_i \leq r_i \leq 2 \times 10^5$。

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


title: [语言月赛202211] BAN-PICK

description:
在第五人格职业联赛的每一场对局中，需要进行 Ban-Pick 流程。Ban 即角色禁用，Pick 即角色选用。

如试题 Winner 所述，游戏分为 **求生者（$\texttt{Survivor}$）** 与 **监管者（$\texttt
{Hunter}$）** 两个阵营。**求生者阵营** 共有 $n$ 名角色，**监管者阵营** 共有 $m$ 名角色。

在某局比赛中，**监管者** 可以 ban(禁用) 掉 **求生者阵营** $5$ 名角色，**求生者** 可以 ban(禁用) 掉 **监管者阵营** $2$ 名角色。

每个角色，无论其属于求生者阵营还是监管者阵营，均可以使用 **熟练度** 来量化该阵营选手选择该角色的优先程度。选手一定会优先选择 **熟练度** 更高的角色进行游戏。

基于这样的考量，**监管者选手** 在进行 Ban 流程时，往往会选择 ban(禁用) 掉 **求生者阵营熟练度最高** 的若干名 **求生者角色**。同样，**求生者选手** 在进行 Ban 流程时，往往会选择 ban(禁用) 掉 **监管者阵营熟练度最高** 的若干名 **监管者角色**。

在 Ban 流程完成后，需要执行 Pick 流程。

如试题 Winner 所述，**求生者选手** 需要从 **求生者阵营** 中选择 $4$ 名不同的角色，**监管者选手** 需要从 **监管者阵营** 中选择 $1$ 名角色。

现在告诉你所有角色的名字、阵营与选手对其熟练度，请你给出双方阵营 Pick 的角色名字。

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

输入的第一行为两个整数 $n,m$，分别代表求生者阵营角色数和监管者阵营角色数。

接下来 $n+m$ 行，首先为一个仅由英文字母组成的字符串，代表该角色的姓名；接下来为一个大写字符 `H` 或 `S`，若为 `H`，则代表该角色为监管者阵营，若为 `S`，则代表该角色为求生者阵营；接下来一个正整数，代表该阵营选手对该角色的熟练度。上述字符串、大写字符、正整数之间由一个空格分隔。

outputFormat:
输出共 $5$ 行。

输出的第一行为监管者阵营选择角色的角色名。

输出的第二到五行为求生者阵营选择角色的角色名，按照熟练度从高到低排列。

samples:
9 3
Amily S 1
Lydia S 2
Lisa S 4
Beck H 1
Freddie S 5
Cliche S 6
Aesop S 7
Eli S 8
Norton S 9
Tiletower H 3
Yidhra H 2
Emma S 3

hint:
### 输入输出样例 1 解释

求生者阵营角色：$\texttt{Amily,Lydia,Lisa,Freddie,Cliche,Aesop,Eli,Norton,Emma}$。

监管者阵营角色：$\texttt{Beck,Tiletower,Yidhra}$。

监管者选手将 ban 掉求生者阵营中角色 $\texttt{Norton,Eli,Aesop,Cliche,Freddie}$。

求生者选手将 ban 掉监管者阵营中角色 $\texttt{Tiletower,Yidhra}$。

### 数据规模与约定

对于前 $20\%$ 的数据，$n = 9, m = 3$。

对于前 $50\%$ 的数据，保证 $n \leq 10 ^ 3, m \leq 10 ^3$。

对于前 $70\%$ 的数据，保证 $w _ i \leq 10 ^ 9$。

对于所有数据，保证 $9 \leq n \leq 10 ^ 5, 3 \leq m \leq 10 ^ 5$，所有名字长度 $\leq 10$。熟练度大小 $w _ i$ 满足 $1 \leq w _ i \leq 10 ^ {18}$。保证每个阵营中熟练度互不相同。保证名字仅有大写字母和小写字母构成。


title: [语言月赛202211] Winner

description:
在网易非对称对抗游戏《第五人格》中，玩家分为 **监管者** 与 **求生者** 两个阵营。

一局标准模式游戏由一名监管者玩家和四名求生者玩家组成。游戏的胜利判定与求生者逃脱人数 $K$ 有关：

- $K>2$，求生者获胜（$\texttt{Survivor Win}$）
- $K=2$，平局（$\texttt{Tie}$）
- $K<2$，监管者获胜（$\texttt{Hunter Win}$）

现在给出一局游戏的求生者逃脱人数，请问获胜阵营（或平局）。

inputFormat: 输入一行一个整数 $K$，代表求生者逃脱人数。

outputFormat:
输出一行一个字符串，代表游戏结果：

- 若求生者阵营获胜，输出 `Survivor`
- 若监管者阵营获胜，输出 `Hunter`
- 若平局，输出 `Tie`


title: [JRKSJ R7] 月下缭乱

background:
![](https://cdn.luogu.com.cn/upload/image_hosting/xkd5zhgk.png?x-oss-process=image)

轻快的音乐声坚定了你做一道简单题的决心。

（题目背景图片来自 Phigros 曲绘，如有侵权，请告知出题人。）

description:
你有一个长度为 $n$，初值全为 $0$ 的序列 $a$。

你有长为 $m$ 的操作序列，其中第 $i$ 次有三个参数 $l_i,r_i,x_i$，表示令 $\forall j\in[l_i,r_i] ,a_j\gets\max(a_j,x_i)$。

令 $\text{sol}(l,r)$ 表示依次操作第 $l$ 至第 $r$ 个操作后的 $a$ 序列。

你需要回答有多少对 $(l,r)$ 满足 $1\le l\le r\le m$ 且 $\text{sol}(l,r)=\text{sol}(1,m)$。

记 $f_i$ 为有多少 $i\le k\le m$ 满足 $\text{sol}(i,k)=\text{sol}(1,m)$，你还需要输出 $\displaystyle\bigoplus_{i=1}^m f_i\times i$ 与 $\displaystyle\sum_{i=1}^m f_i\times i$ 的值。

所有答案都需要对 $2^{32}$ 取模后输出。

inputFormat:
第一行两个整数 $n,m$。\
接下来 $m$ 行，每行三个整数 $l_i,r_i,x_i$，表示第 $i$ 个操作。

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

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


title: 藤原「灭罪寺院伤」

background:
藤原氏，权倾一时的重臣。凭借着炙手可热的权势，杀害了政敌长屋王而触碰到了最高的权力。

是天谴吗？即使修缮寺庙积德行善，藤原四兄弟最终覆灭在了天花之下。

description:
环环相扣的因果报应可看成平面上的 $n$ 个小正方形，它们的边长分别为 $1,2,3,\cdots,n$。初始时，编号较小的正方形被编号较大的正方形完全包含：

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

为了方便记录正方形的位置，我们取正方形左上角的坐标 $(x_i,y_i)$ 为正方形的坐标。此时可以唯一确定该正方形。

现在需要将最小的正方形的位置移动到 $(x_{\rm end},y_{\rm end})$，移动过程满足：

- 每次**最多移动一个**正方形，可以往上下左右四个方向之一移动一个单位长度。
- 在移动过程中，需要保证**较小正方形会被较大的正方形包含**。

请求出最少次数。

inputFormat:
第一行有三个整数 $n, x_{\mathrm{end}},y_{\mathrm{end}}$，含义如题面所示。

接下来 $n$ 行，每行有两个整数 $x_i,y_i$，描述第 $i$ 小的正方形左上角的坐标。

outputFormat: 输出共一行一个整数，表示最小的操作步数。

hint:
### 样例 1 解释

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

### 数据范围及约定

对于全部数据，$1\le n\le 10^5$，$0\le x_i,y_i,x_{\mathrm{end}},y_{\mathrm{end}}\le 10^9$。


title: 「不死鸟附体」

background:
死而复生，生而复死。所谓的不死鸟就是这样的一种生物，在无尽的时间里无尽地循环往复。

果然最好还是别获得不老不死的能力吧。

description:
不死鸟的「一生」可以被看成一个长度不超过 $l_{\max}$ 的字符串 $S_0$。在无尽的轮回后形成了一个无限长的字符串 $S_{\mathrm{inf}}=S_0+S_0+S_0+\cdots$。现在截取 $S_{\infty}$ 前 $l$ 个字符，作为可观测时间里不死鸟的生命 $S_{\mathrm{fin}}$。

然而所谓的轮回并不是机械的循环往复。因此，$S_\mathrm{fin}$ 当中会有不超过 $n$ 个字符被修改成了别的字符，变成了 $S_{\mathrm{real}}$。

现在观测到了 $S_{\mathrm{real}}$，我们希望找到这轮回的最小片段 $S_0$。

当然，由于 $S_{\mathrm{real}}$ 从 $S_{\mathrm{fin}}$ 修改而来，可能不存在长度不超过 $l_{\max}$ 的字符串 $S_0$ 可以直接生成 $S_{\mathrm{real}}$。于是，现在只希望找到这样一个 $S_0'$，使得由它生成的 $S_\mathrm{fin}'$ 修改不超过 $m$ 个字符后可以变成 $S_{\mathrm{real}}$。

inputFormat:
第一行有四个正整数 $l,l_{\max},n,m$。

第二行描述观测到的长度为 $l$ 的字符串 $S_{\mathrm{real}}$。

outputFormat:
第一行输出一个正整数 $l_0$，表示你所找到的 $S_0$ 的长度。你应当保证 $1\le l_0\le l_{\max}$。

第二行输出一个长度为 $l_0$ 的字符串 $S_0$，表示你所找到的字符串。

hint:
### 样例解释

重要：样例仅供理解题意，不一定符合数据范围的约束。具体约束请参见「数据范围及约定」。

生成 $S_{\mathrm{real}}$ 所用的 $S_0=\verb!aabcd!$。

- 由此生成 $S_{\mathrm{inf}}=\verb!aabcdaabcdaabcdaabcdaabcd!\cdots$；
- 由此生成 $S_{\mathrm{fin}}=\verb!aabcdaabcdaabcdaabcdaabcd!$；
- 由此生成 $S_{\mathrm{real}\kern{-2.5pt}}=\verb!aaacdaabbbaabccaabcdaabcd!$。

样例输出给出了一个可能的 $S_0'=\verb!aaacd!$。由此计算出 $S_{\mathrm{fin}}'$ 与 $S_{\mathrm{real}}$ 的差距：

$$\begin{aligned}
S_{\mathrm{fin}}'=&\texttt{aaacdaa\textcolor{red}a\textcolor{red}c\textcolor{red}daa\textcolor{red}ac\textcolor{red}daa\textcolor{red}acdaa\textcolor{red}acd}\cr
S_{\mathrm{real}}=&\texttt{aaacdaabbbaabccaabcdaabcd}\cr
\end{aligned}$$

相差为 $7$，不超过 $m=10$，可以被接受。

### 数据范围及约定

对于全部数据，保证 $l=3\times 10^5$，$n=3\times 10^3$，$m=10^4$，$1\le l_{\max} \le 10^5$。


title: 灭罪「正直者之死」

background:
正直的人，坚强不屈的人，刚正不阿的人。

大约这样的人会处处吃亏吧，不过这样的观点大约是从欺骗者的眼光里看到的。正直的人，即使是在死后，也是最为人尊敬的吧。

description:
有一台计算器，使用 $k$ 位的带符号整型来对数字进行存储。也就是说，一个变量能够表示的范围是 $[-2^{k-1},2^{k-1})$。现在我们希望使用该计算器计算一系列数 $a_1,a_2,\cdots,a_n$ 的和。计算的伪代码如下：

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

由于奇怪的特性，如果两个变量在相加时得到的结果在 $[-2^{k-1},2^{k-1})$ 之外，即发生了溢出，那么这台计算器就会卡死，再也无法进行计算了。

为了防止这样的事情发生，一个变通的方法是**更改 $a_i$ 的排列顺序**。容易发现这样不会改变计算出的和的值。

不过，可能不存在一种方案，使得计算出这 $n$ 个数并且计算机不爆炸。但我们还是希望，计算出**尽量多**的数字的和。

inputFormat:
第一行有两个整数 $n,k$，分别表示元素个数和整型位数。

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

outputFormat: 共一行一个整数，表示最多能将多少个数字计算出和。

hint:
### 样例解释

- 对于样例 $1$，一种最优的方案是 $[a_1,a_2,a_3]$，这样可以在计算出前两个数的情况下不溢出。
- 对于样例 $2$，一种最优的方案是 $[a_{10},a_1,a_2,a_5,a_4,a_7,a_6,a_8,a_9,a_3]$，这样可以在计算前 $9$ 个数的情况下不溢出。

### 数据范围及约定

对于全部数据，保证 $1\le n\le 500$，$1< k\le 8$，$-2^{k-1}\le a_i<2^{k-1}$。


title: 「KDOI-02」一个截的拦

background:
「{!@@(*@@￥';l]dw@)%)%&^_^}（可恶的人类！我一定会回来的！）」

它将飞船拉到了最高速度，试图离开这个充满人类的地狱。

……

description:
过了那么多年，外星人的飞船速度早已比不过地球的飞船。因此，它决定使用折跃点逃离。

平面地图上有 $n$ 个折跃点，坐标分别为 $(x_i,y_i)$。某些折跃点之间有双向空间隧道连接，共 $m$ 条隧道，每条隧道分别连接折跃点 $u_i,v_i$，且激活该隧道需要消耗 $w_i$ 单位能量。**请注意，为了保证空间隧道之间互不干扰，对于任意两条空间隧道 $\bm{i,j}$，都保证连接点 $\bm{u_i,v_i}$ 与点 $\bm{u_j,v_j}$ 的线段没有交点。保证不存在起点和终点都相同的两条空间隧道。**

外星人的科技非常神奇，因此为了成功折跃离开，外星人必须经过地图上的所有折跃点 **至少一次**，它可以从任意一点开始折跃并从任意一点结束折跃，最终，外星人所花费的总能量为激活路径上所有隧道所消耗能量的 **按位或运算和**。经过两次或两次以上同一隧道只需激活一次该隧道。

外星人的飞船上拥有 $x$ 单位能量，因此，它所选择的折跃方案花费的总能量不能超过 $x$。为了拦截外星人，地方可以执行以下操作任意多次：

+ 选择一条连接 $u$ 和 $v$ 的双向隧道（你需要保证在点 $u$ 和 $v$ 之间存在双向隧道连接）；
+ 将激活它所需要的能量增加 $w$（$w\ge0$ 且操作后激活该通道所需要的能量不能超过 $2^{31}-1$）。

其中，$u,v,w$ 都可以自行指定。**每次操作所需要的代价为 $w$ 的二进制表示下 $1$ 的个数。**（即 `c++` 中的 `__builtin_popcount()` 函数）

为了赎罪，你需要设计一种操作方案，使得外星人无法通过折跃逃离，并最小化该方案所需要的代价。

inputFormat:
从标准输入读入数据。

输入的第一行包含 $1$ 个正整数 $W$，表示该测试点的评分参数。

输入的第二行包含 $3$ 个整数 $n,m,x$，分别表示折跃点个数，双向隧道条数以及外星人飞船上拥有的能量。

第 $3$ 至 $(n+2)$ 行，第 $(i+2)$ 行有 $2$ 个整数 $x_i,y_i$，表示第 $i$ 个折跃点的坐标。

接下来 $m$ 行，每行 $3$ 个整数 $u_i,v_i,w_i$，表示每条双向隧道连接的两个折跃点和激活所需能量。

outputFormat:
输出到标准输出。

**本题采用自定义校验器（special judge）评测。**

输出的第一行应包含一个非负整数 $k$，表示操作总次数。

接下来 $k$ 行，每行一次操作，形如 $u~v~w$，表示将激活连接 $u$ 和 $v$ 的双向隧道所需能量增加 $w$。

你需要保证 $0\le k\le 10000$，否则将被判定为不合法答案。

samples:
见附件中的 intercept2.in
见附件中的 intercept2.ans

samples:
见附件中的 intercept3.in
见附件中的 intercept3.ans

hint:
**【样例解释】**
+ **样例 1 解释：**
经过操作后的平面地图如下图所示（省略坐标轴）：
![](https://cdn.luogu.com.cn/upload/image_hosting/cbg7sir6.png)
由于与 $2$ 号折跃点相连的空间隧道所需要的激活能量全部为 $10$，所以成功折跃所需要的能量至少为 $10$，因此外星人无法通过折跃逃离，代价为 $1$，显然不存在代价更小的操作方案。

***

**【评分方式】**

对于每个测试点，如果你的操作方案不合法或使得外星人能够成功通过折跃逃离，你将在该测试点得到  $0$ 分。

否则，设该测试点的评分参数为 $W$，标准答案的代价为 $a$，你的操作方案的代价为 $b$，则你的分数 $s$ 将由下列公式给出：

$$
s=\max\left(1-\frac{b-a}{a}\times W,0\right)\times10
$$

***

**【数据范围】**

对于 $100\%$ 的数据，$12\le n\le 53280$，$n-1\le m\le 3n-6$，$0\le x<2^{31}-1$，$0\le|x_i|,|y_i|\le3\times10^4$，$0\le w_i<2^{31}$，$1\le W\le 1000$。

|测试点编号|$n=$|$m=$|$W=$|数据随机生成|
|:--:|:--:|:--:|:--:|:--:|
|$1$|$12$|$26$|$1000$|否|
|$2$|$12$|$26$|$1$|是|
|$3$|$200$|$579$|$2$|是|
|$4$|$500$|$1482$|$5$|是|
|$5$|$5000$|$14971$|$5$|否|
|$6$|$5000$|$14962$|$1$|是|
|$7$|$10656$|$30188$|$1000$|否|
|$8$|$10656$|$30188$|$5$|否|
|$9$|$53280$|$150960$|$1000$|否|
|$10$|$53280$|$150960$|$1000$|否|

***

**【校验器】**

为了方便测试，在 $\texttt{intercept}$ 目录下我们下发了 $\texttt{checker.cpp}$ 文件。你可以编译该文件，并使用它校验自己的输出文件。请注意它与最终评测时所用的校验器并不完全一致，你不需要也不应该关心其代码的具体内容。

编译命令为：

```plain
g++ checker.cpp -o checker -std=c++14
```

使用方式为：

```
./checker <inputfile> <outputfile> <answerfile>
```

校验器可能会返回以下状态中的其中一种：

+ $\texttt{accepted}$：表示你的输出完全正确。
+ $\texttt{points } x$：表示你的输出部分正确，可以在该测试点得到比例为 $x$ 的分数。
+ $\texttt{wrong answer}$：表示你在该测试点得到 $0$ 分。

对于所有非 $\texttt{accepted}$ 状态，校验器接下来会输出以下信息中的一种：

+ $\texttt{A}$：表示你的输出不合法。
+ $\texttt{B x y}$：表示你的输出方案的代价为 $x$，标准答案为 $y$。
+ $\texttt{C}$：表示你的输出方案使得外星人能够成功通过折跃逃离。

***

**【后记】**

他知道，他将永远离开家乡了。他仍记得，在倒转时空前，指挥官最后的那句叮嘱。他花了几乎半辈子，终于建立了新的基地，重整了军队。他的目的，就是为了防止这一切重蹈覆辙。现在，基地被毁了，他被困在这暗淡无光的星系里。他终于醒悟了，一切都是早已被决定好的。
「指挥官，对不起。」
「舱室将在十秒后自毁。十。九。八。七……」
举起手枪，对准自己太阳穴。
「六。五。四。三……」
随着砰的一声，他无力地倒下了，眼里黯淡无光。
「二。一。」
巨响过后，无人将被铭记。


title: [蓝桥杯 2016 省 A] 密码脱落

description:
X 星球的考古学家发现了一批古代留下来的密码。

这些密码是由 A、B、C、D 四种植物的种子串成的序列。

仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的回文串）。

由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。

你的任务是：

给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。

inputFormat: 输入一行，表示现在看到的密码串。（长度不大于 $1000$）

outputFormat: 要求输出一个正整数，表示至少脱落了多少个种子。

hint: 蓝桥杯 2016 年省赛 A 组 I 题。


title: [蓝桥杯 2016 国 B] 生成树计数

description:
给定一个 $n×m$ 的格点图，包含 $n$ 行 $m$ 列共 $n×m$ 个顶点，相邻的顶点之间有一条边。

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

给出了一个 $3×4$ 的格点图的例子。

如果在图中删除部分顶点和其相邻的边，如上图删除第 $2$ 行第 $3$ 列和第 $3$ 行第 $1$ 列的顶点后，如下图所示。

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

图的生成树指包含图中的所有顶点和其中的一部分边，使得任意两个顶点之间都有由边构成的唯一路径。如果两个生成树包含有不同的边即被认为不同，则上图中共有 $31$ 种不同的生成树，其中 a 边不选有 $10$ 种，a 边选有 $21$ 种。

给出格点图中保留的顶点的信息，请计算该图一共有多少种不同的生成树。

inputFormat:
输入的第一行包含两个整数 $n$，$m$，用空格分隔，表示格点图的行数和列数。

接下来 $n$ 行，每行 $m$ 个字母（中间没有分隔字符），每个字母必然是大写 `E` 或大写 `N`，`E` 表示对应的顶点存在，`N` 表示对应的顶点不存在。保证存在至少一个顶点。

outputFormat: 输出一行，包含一个整数，表示生成树的个数。答案可能很大，你只需要计算答案除以 $1000000007$（即 $10^9+7$） 的余数即可。

hint:
对于 $10\%$ 的数据，$1\le n\le2$。

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

对于 $40\%$ 的数据，$1\le n\le4$。

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

另有 $20\%$ 的数据，$1\le n\times m\le12$。

另有 $10\%$ 的数据，$1\le m\le15$。

对于 $100\%$ 的数据，$1\le n\le6，1\le m\le10^5$。


title: [蓝桥杯 2016 国 A] 圆圈舞

description:
春天温暖的阳光照耀着大地，正是草原上的小动物们最快乐的时候。小动物们在草原上开了一个舞会，欢度这美好的时光。

舞会上最重要的一个环节就是跳圆舞曲，$n$ 只小动物手拉手围成一大圈，随着音乐跳起来。在跳的过程中，小动物们可能会变换队形。它们的变换方式是动物 A 松开自己右手，动物 B 松开自己的左手，动物 A 和 B 手拉到一起，而它们对应的松开的手（如果有的话）也拉到一起。

例如，假设有 $10$ 只小动物，按顺序围成一圈，动物 $1$ 的右手拉着动物 $2$ 的左手，动物 $2$ 的右手拉着动物 $3$ 的左手，依次类推，最后动物 $10$ 的右手拉着动物 $1$ 的左手。如果通过动物 $2$ 和 $8$ 变换队形，则动物 $2$ 的右手拉着动物 $8$ 的左手，而对应的动物 $3$ 的左手拉着动物 $7$ 的右手，这样形成了 `1-2-8-9-10` 和 `3-4-5-6-7` 两个圈。如果此时通过动物 $2$ 和 $6$ 变换队形，则将形成 `1-2-6-7-3-4-5-8-9-10` 一个大圈。注意，如果此时通过动物 $1$ 和 $2$ 变换队形，那么队形不会改变，因为动物 $1$ 的右手和动物 $2$ 的左手松开后又拉到一起了。

在跳舞的过程中，每个动物 $i$ 都有一个欢乐值 $H_i$ 和一个感动值 $F_i$。

如果两个动物在一个圈中，欢乐值会彼此影响，产生欢乐能量。如果两个动物 $i, j(i\neq j)$ 在同一个大小为 $t$ 的圈中，而动物 $i$ 在动物 $j$ 右手的第 $p$ 个位置（动物 $j$ 右手的第 $1$ 个位置就是动物 $j$ 右手所拉着的动物，而第 $2$ 个位置就是右手第 $1$ 个位置的动物右手拉着的动物，依次类推），则产生的欢乐能量为 $(t-p)\times H_j\times F_i$。在跳舞的过程中，动物们的欢乐值和感动值有可能发生变化。

圆舞曲开始的时候，所有的动物按编号顺序围成一个圈，动物 $n$ 右手的第 $i$ 个位置正好是动物 $i$。现在已知小动物们变换队形的过程和欢乐值、感动值变化的过程，求每次变换后所有动物所产生的欢迎能量之和。

inputFormat:
输入的第一行包含一个整数 $n$，表示动物的数量。

接下来 $n$ 行，每行两个用空格分隔的整数 $H_i$，$F_i$，按编号顺序给出每只动物的欢乐值和感动值。
接下来一行包含一个整数 $m$，表示队形、欢乐值、感动值的变化次数。

接下来 $m$ 行，每行三个用空格分隔的整数 $k$，$p$，$q$，当 $k=1$ 时，表示小动物们通过动物 $p$ 和动物 $q$ 变换了队形，当 $k=2$ 时，表示动物 $p$ 的欢乐值变为 $q$，当 $k=3$ 时，表示动物 $p$ 的感动值变为了 $q$。

outputFormat:
输出 $m$ 行，每行一个整数，表示每次变化后所有动物产生的能量之和。

答案可能很大，你需要计算答案除以 $1000000007$（即 $10^9+7$） 的余数。


title: [蓝桥杯 2017 省 A] 正则问题

description:
考虑一种简单的正则表达式：

只由 `x` `(` `)` `|` 组成的正则表达式。

小明想求出这个正则表达式能接受的最长字符串的长度。

例如 `((xx|xxx)x|(x|xx))xx` 能接受的最长字符串是： `xxxxxx`，长度是 $6$。

inputFormat: 一个由 `x()|` 组成的正则表达式。输入长度不超过 $100$，保证合法。

outputFormat: 这个正则表达式能接受的最长字符串的长度。

hint: 蓝桥杯 2022 省赛 A 组 G 题。


title: [蓝桥杯 2017 省 B] 日期问题

description:
小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在 1960 年 1 月 1 日至 2059 年 12 月 31 日。令小明头疼的是，这些日期采用的格式非常不统一，有采用`年/月/日`的，有采用`月/日/年`的，还有采用`日/月/年`的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。

比如 `02/03/04`，可能是 2002 年 03 月 04 日、2004 年 02 月 03 日或 2004 年 03 月 02 日。

给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

inputFormat: 一个日期，格式是 `AA/BB/CC`。($0\le A, B, C\le 9$)

outputFormat: 输出若干个不相同的日期，每个日期一行，格式是 `yyyy-MM-dd`。多个日期按从早到晚排列。


title: [蓝桥杯 2014 国 B] 生物芯片

description:
X 博士正在研究一种生物芯片，其逻辑密集度、容量都远远高于普通的半导体芯片。

博士在芯片中设计了 $n$ 个微型光源，每个光源操作一次就会改变其状态，即：点亮转为关闭，或关闭转为点亮。

这些光源的编号从 $1$ 到 $n$，开始的时候所有光源都是关闭的。

博士计划在芯片上执行如下动作：

所有编号为 $2$ 的倍数的光源操作一次，也就是把 $2,4,6,8,\cdots$ 等序号光源打开

所有编号为 $3$ 的倍数的光源操作一次, 也就是对 $3,6,9,\cdots$ 等序号光源操作，注意此时 $6$ 号光源又关闭了。

所有编号为 $4$ 的倍数的光源操作一次。

…

直到编号为 $n$ 的倍数的光源操作一次。

X 博士想知道：经过这些操作后，某个区间中的哪些光源是点亮的。

inputFormat:
3 个用空格分开的整数：$N$，$L$，$R$。 ($L < R < N < 10^{15}$)

$N$ 表示光源数，$L$ 表示区间的左边界，$R$ 表示区间的右边界。

outputFormat: 输出 $1$ 个整数，表示经过所有操作后，$[L, R]$ 区间中有多少个光源是点亮的。


title: [蓝桥杯 2015 省 A] 饮料换购

description:
乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊 C 型饮料，凭 $3$ 个瓶盖可以再换一瓶 C 型饮料，并且可以一直循环下去(但不允许暂借或赊账)。

请你计算一下，如果小明不浪费瓶盖，尽量地参加活动，那么，对于他初始买入的 $n$ 瓶饮料，最后他一共能喝到多少瓶饮料。

inputFormat: 一个整数 $n$，表示开始购买的饮料数量。（$0<n<10000$）

outputFormat: 一个整数，表示实际得到的饮料数。

hint: 2015 年蓝桥杯省赛 A 组 H 题。


title: [蓝桥杯 2018 省 A] 航班时间

description:
小 h 前往美国参加了蓝桥杯国际赛。小 h 的女朋友发现小 h 上午十点出发，上午十二点到达美国，于是感叹到“现在飞机飞得真快，两小时就能到美国了”。

小 h 对超音速飞行感到十分恐惧。仔细观察后发现飞机的起降时间都是当地时间。由于北京和美国东部有 $12$ 小时时差，故飞机总共需要 $14$ 小时的飞行时间。

不久后小 h 的女朋友去中东交换。小 h 并不知道中东与北京的时差。但是小 h 得到了女朋友来回航班的起降时间。小 h 想知道女朋友的航班飞行时间是多少。

对于一个可能跨时区的航班，给定来回程的起降时间。假设飞机来回飞行时间相同，求飞机的飞行时间。

inputFormat:
从标准输入读入数据。

一个输入包含多组数据。

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

每组数据包含两行，第一行为去程的起降时间，第二行为回程的起降时间。

起降时间的格式如下

```h1:m1:s1 h2:m2:s2```

或

```h1:m1:s1 h3:m3:s3 (+1)```

或

```h1:m1:s1 h4:m4:s4 (+2)```

表示该航班在当地时间 `h1` 时 `m1` 分 `s1` 秒起飞，

第一种格式表示在当地时间 当日 `h2` 时 `m2` 分 `s2` 秒降落

第二种格式表示在当地时间 次日 `h3` 时 `m3` 分 `s3` 秒降落。

第三种格式表示在当地时间 第三天 `h4` 时 `m4` 分 `s4` 秒降落。

对于此题目中的所有以 `h:m:s` 形式给出的时间, 保证（$0\le h\le23$，$0\le m,s\le59$）.

outputFormat:
输出到标准输出。

对于每一组数据输出一行一个时间 `hh:mm:ss`，表示飞行时间为 `hh` 小时 `mm` 分 `ss` 秒。

注意，当时间为一位数时，要补齐前导零。如三小时四分五秒应写为 `03:04:05`。

hint: 保证输入时间合法，飞行时间不超过 $24$ 小时。


title: [蓝桥杯 2018 省 A] 三体攻击

description:
三体人将对地球发起攻击。为了抵御攻击，地球人派出了 $A\times B\times C$ 艘战舰，在太空中排成一个 $A$ 层 $B$ 行 $C$ 列的立方体。其中，第 $i$ 层第 $j$ 行第 $k$ 列的战舰（记为战舰 $(i, j, k)$）的生命值为 $d(i, j, k)$。

三体人将会对地球发起 $m$ 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地，第 $t$ 轮攻击用 $7$ 个参数 $la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t$ 描述；

所有满足 $i\in [la_t, ra_t],j\in [lb_t, rb_t],k\in [lc_t, rc_t]$ 的战舰 $(i, j, k)$ 会受到 $h_t$ 的伤害。如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。

地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。

inputFormat:
从标准输入读入数据。

第一行包括 $4$ 个正整数 $A$，$B$，$C$，$m$；

第二行包含 $A\times B\times C$ 个整数，其中第 $((i − 1)\times B + (j − 1)) \times C + (k − 1)+1$ 个数为 $d(i, j, k)$；

第 $3$ 到第 $m + 2$ 行中，第 $(t + 2)$ 行包含 $7$ 个正整数 $la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t$。

outputFormat:
输出到标准输出。

输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。

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

在第 $2$ 轮攻击后，战舰 $(1,1,1)$ 总共受到了 $2$ 点伤害，超出其防御力导致爆炸。

**【数据约定】**

对于 $10\%$ 的数据，$B = C = 1$；

对于 $20\%$ 的数据，$C = 1$；

对于 $40\%$ 的数据，$A\times B \times C, m\le10000$；

对于 $70\%$ 的数据，$A, B, C \le 200$；

对于所有数据，$1\le A\times B\times C \le 10^6$，$1\le m \le 10^6$，$0 \le  (i, j, k)$, $h_t\le 10^9$。


title: [蓝桥杯 2018 省 B] 递增三元组

description:
给定三个整数数组 $A = [A_1, A_2,\cdots, A_N]$，$B = [B_1, B_2,\cdots, B_N]$，$C = [C_1, C_2,\cdots,C_N]$。

请你统计有多少个三元组 $(i, j, k)$ 满足：
1. $1 \le i, j, k \le N$
2. $A_i < B_j < C_k$

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

第二行包含 $N$ 个整数 $ A_1, A_2,\cdots, A_N$。

第三行包含 $N$ 个整数 $ B_1, B_2,\cdots, B_N$。

第四行包含 $N$ 个整数 $ C_1, C_2,\cdots, C_N$。

outputFormat: 一个整数表示答案


title: [蓝桥杯 2018 省 B] 螺旋折线

description:
如图所示的螺旋折线经过平面上所有整点恰好一次。

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

对于整点 $(X, Y)$，我们定义它到原点的距离 $\text{dis}(X, Y)$ 是从原点到 $(X, Y)$ 的螺旋折线段的长度。

例如 $\text{dis}(0, 1)=3$，$\text{dis}(-2, -1)=9$。

给出整点坐标 $(X, Y)$，你能计算出 $\text{dis}(X, Y)$ 吗？

inputFormat: $X$ 和 $Y$。

outputFormat: 输出 $\text{dis}(X, Y)$


title: [蓝桥杯 2018 省 B] 乘积最大

description:
给定 $N$ 个整数 $A_1, A_2,\cdots, A_N$。请你从中选出 $K$ 个数，使其乘积最大。

请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 $1000000009$（即 $10^9+9$）的余数。

注意，如果 $X<0$， 我们定义 $X$ 除以 $1000000009$ 的余数是 $0-((0-x)\bmod 1000000009)$。

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

以下 $N$ 行每行一个整数 $A_i$。

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


title: [蓝桥杯 2018 国 B] 矩阵求和

description:
经过重重笔试面试的考验，小明成功进入 Macrohard 公司工作。

今天小明的任务是填满这么一张表：

表有 $n$ 行 $n$ 列，行和列的编号都从 $1$ 算起。

其中第 $i$ 行第 $j$ 个元素的值是 $\gcd(i, j)$ 的平方，$\gcd$ 表示最大公约数，以下是这个表的前四行的前四列：

```
1  1  1  1
1  4  1  4
1  1  9  1
1  4  1 16
```

小明突然冒出一个奇怪的想法，他想知道这张表中所有元素的和。
由于表过于庞大，他希望借助计算机的力量。

inputFormat: 一行一个正整数 $n$ 意义见题。

outputFormat: 一行一个数，表示所有元素的和。由于答案比较大，请输出模 $1000000007$（即$10^9+7$）后的结果。


title: 「DTOI-5」进行一个排的重 (Maximum Version)

background:
**本题与 Minimum Version 的区别是所求最值和数据范围不同。**

小 L 热衷于重排数列使之规整。

description:
小 L 有一个长为 $n$ 的序列 $a$，其中每一项 $a_i$ 都是一个 pair $(p_i, q_i)$。

为了让 $a$ 看起来规整一些，他钦定 $p, q$ 分别均为长为 $n$ 的排列。

为了对 $a$ 的规整程度进行量化计算，他给出了一个权值函数 $f(a) = \displaystyle\sum_{i = 1}^n ([p_i > \max_{j = 1}^{i - 1} p_j] + [q_i > \max_{j = 1}^{i - 1} q_j])$。**注意 $i = 1$ 时两个方括号都能取到值，因为我们认为 $\displaystyle\max_{j = 1}^0 p_j = \displaystyle\max_{j = 1}^0 q_j = -\infty$。**

为了让 $a$ 看起来更加规整，他决定分别以某种方式重排 $a$ 得到 $a'$ 使得 $f(a')$ 最大。**注意重排时必须将 $a'_i = (p'_i, q'_i)$ 视为整体。**

他希望你求出 $f(a')_{\max}$ 的值，以及分别有多少个 $a'$ 可以取到 $f(a')_{\max}$。

由于方案数可能很大，你只需要求出结果对 $998244353$ 取模的值。

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

第二行，$n$ 个整数 $p_1, p_2, \cdots, p_n$；

第三行，$n$ 个整数 $q_1, q_2, \cdots, q_n$。

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

hint:
**【数据范围】**

$$
\def\or{\operatorname{or}}
%\def\arrayscretch{1.5}
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{Subtask}&n\le &\textbf{Points}\cr\hline
\sf1&10&10 \operatorname{pts}\cr\hline
\sf2&50&20 \operatorname{pts}\cr\hline
\sf3&500&20 \operatorname{pts}\cr\hline
\sf4&2\times 10^3&20 \operatorname{pts}\cr\hline
\sf5&/&30 \operatorname{pts}\cr\hline
\end{array}
$$
对于 $100\%$ 的数据，$1 \leq n \leq 10^4$，$1 \leq p_i, q_i \leq n$，保证 $p, q$ 均为**排列**。


title: [POI2002] 火车线路

description:
某列火车从 $1$ 号城市出发，前往编号为 $C$ 的城市。该火车有 $S$ 个座位，现在有 $R$ 个车票订购需求。

一个订购由 $O,D,N$ 三个整数组成，表示从起点站 $O$ 到目标站 $D$ 需要订购 $N$ 个座位。

如果在该订购范围内有能满足的空座位，就称该订购可以被满足，否则就不可以。

请你按订购给出顺序处理，判断是否可以满足该订购需求。

inputFormat:
第一行为三个整数 $C,S,R$。

接下来 $R$ 行，每行为三个整数 $O,D,N$，分别表示每一个预定。

outputFormat: 对第 $i$ 个预定，如果能满足，输出 ```T```，否则输出 ```N```。

hint: 数据范围：$1 \le C,S,R \le 60000$。


title: [POI2002] 商务旅行

description:
某地首都的商人要经常到其他城镇去做生意，他们会按自己的路线去走。

有 $N$ 个城镇，首都编号为 $1$。商人从首都出发，其他各城镇之间都有道路连接。

任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。如果从首都出发，能到达任意一个城镇。

请你求出商人最短的旅行时间。

inputFormat:
第一行有一个整数 $N$，为城镇的数目。

接下来 $N-1$ 行，每行两个整数 $a$ 和 $b$，表示城镇 $a$ 和城镇 $b$ 有公路连接。

接下来一个整数 $M$，然后 $M$ 行，每行有该商人需要顺次经过的各城镇编号。

outputFormat: 一行，输出商人最短的旅行时间。

hint: 数据范围：$1 \le N \le 30000$。**保证公路网络不会存在环。**


title: [POI2002] 超级马

description:
在一个大小为无限的棋盘上有一个超级马，它可以完成各种动作。

每一种动作包含两个整数，第一个数说明上下移动的数，第二个数说明左右移动的数，移动马来完成这个动作。（数字均为正数向右，负数向左）

请你对每一个输入的超级马进行确认，看它是否可以到达棋盘上的每一个地方。

inputFormat:
第一行中存在一个整数 $K$，表示数据组数。

对于每一组数据，第一行一个数 $N$，表示超级马能完成的动作个数。

接下来 $N$ 行，每一个行中包含两个整数 $P$ 和 $Q$，表示这个动作。

outputFormat: 输出 $K$ 行，判断超级马是否可以到达棋盘所有地方，可以输出 ```TAK```，否则输出 ```NIE```。


title: [POI2002] 滑雪者

description:
在某山的斜坡上有一些滑雪轨道和一个滑雪电梯，所有的轨道都是从山顶到山底。

每天清晨都有一群工人检查轨道情况，他们一起乘电梯到到达山顶。接着他们沿每个人选择的轨道滑到底端，每个工人只能滑一次。

工人选择的轨道可能有部分相同，每个轨道可由任一个向下滑行的工人检查。向下滑雪从高到底选择一条轨道进行。

滑雪轨道由一个空地网络组成，每个空地有不同的高度。任意两个空地之间最多有一条道相连。

inputFormat:
第一行一个整数 $n$ 表示空地的数目。

接下来 $n-1$ 行，第 $i+1$ 行的整数表示空地 $i$ 有轨道滑向它们。第一个整数 $k$ 表示空地数目，接着 $k$ 个整数，表示它们的编号（从西往东排列）。特别的，山顶编号为 $1$，山脚编号为 $n$。

outputFormat: 一行，表示最少需要多少个工人检查所有的滑道。

hint: 数据范围：$2 \le n \le 5000$，给定的图是平面图。


title: [语言月赛202211] Gold-Purple-Blue-Green-White

background: 扶苏在玩一款名叫第五暖暖的游戏。

description:
扶苏在游戏中的角色有一个被称为「精神力」的属性，初始时，这一属性为 $x_0$。

扶苏的仓库里有 $n$ 件挂件，对于第 $i$ 件挂件，只有当人物的精神力**不低于** $a_i$ 时才能装备该挂件，装备该挂件后，人物的精神力会**增加** $b_i$。

现在，扶苏希望按照**从 $1$ 到 $n$** 的顺序**依次**尝试装备每件挂件。策略是：当尝试装备某件挂件时，如果满足装备该挂件的条件（也就是人物的精神力不低于 $a_i$），则装备该挂件（此时人物的精神力会增加 $b_i$）；否则不装备该挂件，以后也不再考虑该挂件。

请你求出，扶苏一共装备了几件挂件。

inputFormat:
第一行是两个整数，表示挂件数量 $n$ 和初始的精神力 $x_0$。
第二行有 $n$ 个整数，第 $i$ 个整数表示装备挂件 $i$ 最少需要的精神力值 $a_i$。
第三行有 $n$ 个整数，第 $i$ 个整数表示装备挂件 $i$ 后增加的精神力值 $b_i$。

outputFormat: 输出一行一个整数，表示扶苏装备的挂件数量。

hint:
### 样例 1 解释

初始扶苏的精神力为 $1$。
她开始考虑第一件挂件，装备第一件挂件需要的精神力不低于 $1$，符合要求，故她装备了第一件挂件，精神力增加 $1$，变成 $2$。
考虑第二件挂件，要求精神力不低于 $3$，不符合条件，于是不装备该挂件。
考虑第三件挂件，要求精神力不低于 $2$，此时精神力是 $2$，符合要求，故装备该挂件，精神力增加 $1$，变成 $3$。
需要注意的是，虽然此时已经可以装备第二件挂件，但是第二件挂件已经被考虑过了，所以我们不再尝试装备上它。
最终，扶苏装备了两件挂件。

### 数据规模与约定

- 对于 $10\%$ 的数据，保证 $x_0 < \min\limits_{i = 1}^n a_i$；
- 对于另外 $10\%$ 的数据，保证 $n = 1$；
- 对于另外 $20\%$ 的数据，保证 $b_i = 0$；
- 对于另外 $20\%$ 的数据，保证 $a_i < a_{i + 1}$（对 $1 \leq i < n$）；
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$0 \leq a_i, b_i,x_0 \leq 10^9$。

By 一扶苏一


title: [语言月赛202211] Zone Selection

description:
在第五人格巅峰七阶及以上的排位赛中，需要进行区域选择。我们将在本题中形式化、推广化的解决区域选择问题。

在地图中，共有 $n$ 台密码机，第 $i$ 台密码机的坐标为 $(x_i,y_i)$。在推广化的游戏中，有 $k$ 名求生者。每名求生者可以选择一台密码机作为其出生点，我们称被选择的密码机为 **出生密码机**。

监管者共有 $T$ 个出生点可供选择。第 $i$ 个可能的出生点坐标为 $(x_i,y_i)$。此时，由于“封禁”天赋的存在，离监管者最远的密码机将不能被破译。

**如果多台密码机与监管者的距离相同且最远，“封禁”天赋将会封禁这几台密码机中标号最小的那一台。**

请问在该 $T$ 个出生点中，有多少出生点，可以使某一台 **出生密码机** 被封禁。

请注意：坐标点 $(x_1,y_1)$ 与坐标点 $(x_2,y_2)$ 之间的距离为 $\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。

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

输入的第一行为三个整数 $n,k,T$。

接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示一台密码机的坐标。

接下来 $k$ 行，每行两个整数 $x_i,y_i$，表示一名求生者选择出生密码机的坐标，保证该坐标在上面出现过。

接下来 $T$ 行，每行两个整数 $x_i,y_i$，表示监管者的一个出生点。

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

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

显然，第一台密码机和第四台密码机为**出生密码机**。

第一位监管者与位置在 $(-1, 0)$ 的第一台密码机距离最远，为 $4$。因此，第一台密码机被封禁。

第二位监管者与位置在 $(2, 0), (0, 2)$ 的第三、四台密码机距离相同且最远，为 $2$。根据上面提到的规则，第三台密码机被封禁。

被封禁的出生密码机为 $1$ 台。

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

对前 $10\%$ 的数据，保证 $n = k = 1$。

对前 $20\%$ 的数据，保证 $n, k, t \leq 10$。

对另外 $20\%$ 的数据，保证密码机与出生点的坐标中的 $x$ 均为 $0$。

对另外 $10\%$ 的数据，保证 $n = k$。

对另外 $10\%$ 的数据，保证 $T = 1$。

对于 $100\%$ 的数据范围 $1 \le k \le n \le 10^3, 1 \le T \le 10^3, 1 \le |x_i|,|y_i| \le 10^3$。


title: [语言月赛202211] Jewellery

description:
第五人格抽奖宝箱被称为珍宝。某一赛季珍宝池中共有 $n$ 件道具。道具不可以重复获得。因此，第一次抽出某道具，可以将该道具放入仓库。之后抽出该道具，不会将该道具放入仓库，而是给予一定的碎片补偿。

道具共有五种品质，分别为金色、紫色、蓝色、绿色与白色，不同品质道具给予的碎片补偿数量不同，具体数量如下表所示。

| 品质 | 碎片补偿数量 | 品质代号 |
| :---: | :---: | :---: |
| 金色 | $2000$ | $1$ |
| 紫色 | $1000$ | $2$ |
| 蓝色 | $200$ | $3$ |
| 绿色 | $36$ | $4$ |
| 白色 | $6$ | $5$ |

某 E 一共抽了 $k$ 次珍宝。现在告诉你珍宝池和某 E 的抽出道具情况，请问某 E 一共得到了多少碎片。

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

输入的第一行为两个正整数 $n,k$，分别代表珍宝池中道具的数量和某 E 抽珍宝次数。

接下来 $n$ 行，每行一个字符串和一个整数，分别代表道具的名称和品质代号。

接下来 $k$ 行，每行一个字符串，代表某 E 抽到的道具的名称。数据保证对应名称的道具在上面的 $n$ 个道具中出现过。

outputFormat: 输出一行一个整数，代表可以获得的碎片数量。

samples:
5 10
Legendary 1
Epic 2
Rare 3
Uncommon 4
Common 5
Common
Uncommon
Common
Common
Uncommon
Legendary
Uncommon
Common
Uncommon
Rare

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

对于前 $20\%$ 的数据，保证 $n, k \leq 10$。

对于另外 $10\%$ 的数据，保证 $n = 1$。

对于另外 $10\%$ 的数据，保证 $k = 1$。

对于另外 $10\%$ 的数据，所有的 $n$ 件道具全部为金色品质。

对于 $100\%$ 的数据，保证 $1 \leq n \leq 1000, 1 \leq k \le 5000$。所有名字长度 $\leq 10$。名字仅由英文大小写字母构成。保证不同道具名字不同。


title: 似曾相识燕归来

background: 春雨将过，忽而燕鸣轻唤，唤起春波荡漾。春波荡漾，漾起去年的回忆。回忆生香，香满檐下。檐下燕巢残旧，不禁落泪，抬头望归来之燕，心中一动，却是旧时相识……

description:
$n$ 只燕在夕阳中飞过。按从前到后的顺序，第 $i$ 只燕的大小为 $p_i$，且 $p$ 是一个长度为 $n$ 的排列。

现在可以进行**至多 $L$ 次**如下操作：

- 选定三个整数 $i,j,k$ 满足 $1\le i<j<k\le n$，如果 $p_i>p_k$，交换第 $i,j$ 只燕；否则交换第 $j,k$ 只燕。

为了使队形整齐，我们希望燕是从前到后升序排列的，即 $\forall 1\le i\le n$ 都有 $p_i=i$。

问是否可以达成目标。若可以，请构造一组符合要求的操作。

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

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

对于每组测试数据：

- 第一行两个整数 $n,L$。
- 第二行 $n$ 个整数 $p_1,p_2,\ldots,p_n$。

outputFormat:
对于每组测试数据：

- 若无法用至多 $L$ 次操作使得 $p$ 升序排列，仅输出一行 `-1`；
- 否则第一行输出一个整数表示操作次数 $x$，后 $x$ 行每行输出三个整数 $i,j,k$ 表示进行的操作。你需要保证 $0\le x\le L$，$1\le i<j<k\le n$。

hint:
**【提示】**

一个长度为 $n$ 的排列是一个满足 $1$ 到 $n$ 中的所有正整数恰好出现 $1$ 次的数组。例如，$[3,1,2]$ 是一个长度为 $3$ 的排列，而 $[5,5,1,2,3]$ 不是一个排列。

**【样例 1 解释】**

- 第一次操作中，$i=1,j=3,k=4$，由于 $p_1>p_4$，我们交换 $p_1,p_3$，此时 $p=[1,2,4,3]$；
- 第二次操作中，$i=2,j=3,k=4$，由于 $p_2<p_4$，我们交换 $p_3,p_4$，此时 $p=[1,2,3,4]$。

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

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

-  Subtask 1（5 points）：$n\le 3$。
-  Subtask 2（5 points）：$n\le 4$。
-  Subtask 3（5 points）：$T\le 50$，$n\le 8$。
-  Subtask 4（10 points）：$n\le 8$。
-  Subtask 5（25 points）：$L=n+2$。
-  Subtask 6（25 points）：$L=n+1$。
-  Subtask 7（25 points）：无特殊限制。

对于 $100\%$ 的数据，$1\le T\le 10^5$，$1\le n,\sum n\le 2\times 10^6$，$n\le L\le n+2$，$p$ 为一个 $1\sim n$ 的排列。


title: 「yyOI R1」youyou 的异或

background: youyou 非常菜，但是他很喜欢构造奇奇怪怪的数列。

description:
本题评测方式为 **Special Judge**。

youyou 很喜欢数列，所以他想让你构造一个长度为 $n$ 的**正整数**序列 $\{a_i\}$。

youyou 很喜欢[异或](https://oi-wiki.org/math/bit/#%E4%B8%8E%E6%88%96%E5%BC%82%E6%88%96)，所以他要求构造出的序列满足 $a_1 \oplus a_2 \oplus a_3 \oplus \cdots \oplus a_{n-1} \oplus a_n = n$（记 $\oplus$ 表示异或）。

youyou 非常讨厌相同的数，所以他要求序列中所有数**互不相同**。

但 youyou 不想让这个序列的数太大，所以他要求序列中所有数的总和不超过 $n^2$，即 $\displaystyle\sum_{i=1}^n a_i \le n^2$。

现在你需要构造出一个序列从而满足 youyou 的所有要求。如果无解，输出 `-1` 。如果有多种答案，输出任意一个序列即可。

你需要回答 $T$ 组数据。

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

接下来 $T$ 行，每行一个整数 $n$，表示你需要构造出一个长度为 $n$ 的满足要求的序列。

outputFormat:
共 $T$ 行。

若第 $i$ 行需要构造长度为 $n$ 的序列，则第 $i$ 行输出恰好 $n$ 个数，表示你所构造出的序列，注意序列中每个数为**正整数**。若无法构造出这样的序列，请在这一行输出 `-1` 。


title: [语言月赛202211] Fear

description:
在平行宇宙的第五人格，游戏内有一个隐藏的数值，叫做**恐慌值**。

这个数值存在于**求生者**上，会随**监管者**追逐**求生者**的时间增长而变化。

具体的，在求生者未被监管者追逐前，求生者的**初始量**为 $y _ 0$。求生者被监管者追逐了 $t$ 秒。

第 $1$ 秒时，求生者的**恐慌值**为**初始量** $y _ 0$。接下来的每一秒，其**恐慌值**会被乘上它的**初始量**。

**特别的，如果 $t$ 为 $0$，那么求生者的恐慌值为 $1$。**

如果对于恐慌值的计算方式有疑惑，可以查看**样例解释 #1**帮助理解。

你需要计算，在追逐 $t$ 秒后，求生者的**恐慌值**的**奇偶性**以及**正负性**。

inputFormat:
输入一行两个整数，使用空格隔开。

第一个整数为 $y _ 0$，代表**初始量**。

第二个整数为 $t$，代表追逐时间。

outputFormat:
输出两行，每行为一个字符串，`NO` 或 `YES`。

第一行，如果恐慌值为负数，输出 `YES`，否则输出 `NO`。

第二行，如果恐慌值为奇数，输出 `YES`，否则输出 `NO`。


title: [传智杯 #5 初赛] C-莲子的排版设计学

background:
> 你现在不能休息，周围有 deadline 在游荡。

莲子正在赶自己的程序设计作业。除了完成程序代码的编写，对提交上去的作业进行排版以对助教留下良好印象同样重要。

而众所周知，文章里面的代码和一些特殊性质的文本是要附上行号的，然而它们的篇幅往往都很长，手动去加容易出现失误。因此，莲子决定自力更生造轮子，写一个行号生成器。

description:
莲子希望实现这样一个功能：输入一份文本文件，并给该文件加上行号。

以下是本题中三个基本概念的定义：

- **文本字符**由 $\textsf{ASCII}$ 中所有的可视字符，以及空格（$\textsf{ASCII}=32$）组成。
- **一行字符**由若干个（可以为 $0$ 个）文本字符，以及在末尾**恰好一个**换行符（$\textsf{ASCII}=10$）组成。
- **文本文件**由若干个（至少为 $1$ 个）一行字符组成。文本文件的行数就是组成它的行的数量。

以下是本题中添加行号的方法：

- 设该文本文件一共有 $m$ 行。设正整数 $m$ 的字宽为 $s$。那么，在每一行的开头会有 $s+1$ 的长度用来显示行号。
- 对于第 $i$ 行，假设 $i$ 的字宽为 $t$，那么这一行行号将会显示为 $\underbrace{\texttt{␣␣...␣}}_{s-t\text{ 个}}\ i\ \texttt{␣}$，其中 $\texttt{␣}$ 表示空格。

以下是一个例子：

$$\boxed{\begin{aligned}
&\verb!#include<iostream>!\\
&\verb!using namespace std;!\\
&\verb!int main(){!\\
&\verb!    int a, b;!\\
&\verb!    cin >> a >> b;!\\
&\verb!    cout << a + b << endl;!\\
&\verb!    cout << a - b << endl;!\\
&\verb!    cout << a * b << endl;!\\
&\verb!    cout << a / b << endl;!\\
&\verb!    return 0;!\\
&\verb!}!
\end{aligned}} \Rightarrow
\boxed{\begin{aligned}
&\verb! 1 #include<iostream>!\\
&\verb! 2 using namespace std;!\\
&\verb! 3 int main(){!\\
&\verb! 4     int a, b;!\\
&\verb! 5     cin >> a >> b;!\\
&\verb! 6     cout << a + b << endl;!\\
&\verb! 7     cout << a - b << endl;!\\
&\verb! 8     cout << a * b << endl;!\\
&\verb! 9     cout << a / b << endl;!\\
&\verb!10     return 0;!\\
&\verb!11 }!
\end{aligned}}
$$

为了便于读者观察，这里将所有的空格换成用来表示空格的 $\verb!␣!$ 字符。

$$\boxed{\begin{aligned}
&\verb!#include<iostream>!\\
&\verb!using␣namespace␣std;!\\
&\verb!int␣main(){!\\
&\verb!␣␣␣␣int␣a,␣b;!\\
&\verb!␣␣␣␣cin␣>>␣a␣>>␣b;!\\
&\verb!␣␣␣␣cout␣<<␣a␣+␣b␣<<␣endl;!\\
&\verb!␣␣␣␣cout␣<<␣a␣-␣b␣<<␣endl;!\\
&\verb!␣␣␣␣cout␣<<␣a␣*␣b␣<<␣endl;!\\
&\verb!␣␣␣␣cout␣<<␣a␣/␣b␣<<␣endl;!\\
&\verb!␣␣␣␣return␣0;!\\
&\verb!}!
\end{aligned}} \Rightarrow
\boxed{\begin{aligned}
&\verb!␣1␣#include<iostream>!\\
&\verb!␣2␣using␣namespace␣std;!\\
&\verb!␣3␣int␣main(){!\\
&\verb!␣4␣␣␣␣␣int␣a,␣b;!\\
&\verb!␣5␣␣␣␣␣cin␣>>␣a␣>>␣b;!\\
&\verb!␣6␣␣␣␣␣cout␣<<␣a␣+␣b␣<<␣endl;!\\
&\verb!␣7␣␣␣␣␣cout␣<<␣a␣-␣b␣<<␣endl;!\\
&\verb!␣8␣␣␣␣␣cout␣<<␣a␣*␣b␣<<␣endl;!\\
&\verb!␣9␣␣␣␣␣cout␣<<␣a␣/␣b␣<<␣endl;!\\
&\verb!10␣␣␣␣␣return␣0;!\\
&\verb!11␣}!
\end{aligned}}
$$

inputFormat: 输入包含若干行，为原始的文本文件。

outputFormat: 输出包含若干行，为加上行号后的文本文件。

samples:
#include<iostream>
using namespace std;
int main(){
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
    cout << a - b << endl;
    cout << a * b << endl;
    cout << a / b << endl;
    return 0;
}

samples:
 1 #include<iostream>
 2 using namespace std;
 3 int main(){
 4     int a, b;
 5     cin >> a >> b;
 6     cout << a + b << endl;
 7     cout << a - b << endl;
 8     cout << a * b << endl;
 9     cout << a / b << endl;
10     return 0;
11 }

samples:
public class Main {
    public static void main(String[] args) throws Exception {
        int b = 0, c = 0;
        for (int a = 123; a < 333; a++) {
            int[] array = new int[10];
            Boolean flag = true;
            b = a * 2;
            c = a * 3;
            array[a / 100] = 1;
            array[a / 10 % 10] = 1;
            array[a % 10] = 1;

            array[b / 100] = 1;
            array[b / 10 % 10] = 1;
            array[b % 10] = 1;

            array[c / 100] = 1;
            array[c / 10 % 10] = 1;
            array[c % 10] = 1;
            for (int i = 1; i < array.length; i++) {
                if (array[i] != 1) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                System.out.println(a + " " + b + " " + c);
        }
    }
}

samples:
 1 public class Main {
 2     public static void main(String[] args) throws Exception {
 3         int b = 0, c = 0;
 4         for (int a = 123; a < 333; a++) {
 5             int[] array = new int[10];
 6             Boolean flag = true;
 7             b = a * 2;
 8             c = a * 3;
 9             array[a / 100] = 1;
10             array[a / 10 % 10] = 1;
11             array[a % 10] = 1;
12
13             array[b / 100] = 1;
14             array[b / 10 % 10] = 1;
15             array[b % 10] = 1;
16
17             array[c / 100] = 1;
18             array[c / 10 % 10] = 1;
19             array[c % 10] = 1;
20             for (int i = 1; i < array.length; i++) {
21                 if (array[i] != 1) {
22                     flag = false;
23                     break;
24                 }
25             }
26             if (flag)
27                 System.out.println(a + " " + b + " " + c);
28         }
29     }
30 }

samples:
Tao hua kai yo li hua kai, jie jie mei mei dong qi lai;
Tao hua kai yo li hua kai, jie jie mei mei tiao qi lai.
    Gei ni zi ji, chun yi mai huai (yi ya yo);
    Gei xin shang ren, chun se man kai.
Tao hua kai yo li hua kai, jie jie mei mei dong qi lai;
Tao hua kai yo li hua kai, jie jie mei mei tiao qi lai.
    Gei tong bao men, chun yi man huai, hai hai yo;
    Gei zhe da di, chun se quan kai!!!
Cong na nu jiang nan, dao mo he bei,
    Dao chu dou you hua rong ming mei.
Lai hui hui shou, zai diao ge tou,
    Wu xian chun guang zai wo xiong.
Cong jing cheng, dao yuan ye,
    Dao chu dou you sheng de xi yue.
Lai hui hui shou, zai yan ran huang ge tou,
    Wu xian CHUN GUANG XIAN ZU GUO!!!
Tao hua kai yo li hua kai, Jiong xian mei mei dong qi lai;
Tao hua kai yo li hua kai, Jie jie mei mei tiao qi lai.
    Gei ni zi ji, chun yi mai huai chun yi man huai yi ya yo;
    Gei xin shang ren, chun se man kai chun se man kai.
Tao hua kai yo li hua kai, Jie jie mei mei dong qi lai;
Tao hua kai yo li hua kai, Jie jie mei mei tiao qi lai.
    Gei tong bao men, chun yi man huai, hai hai yo;
    Gei zhe da di, chun se quan kai!!!
Cong na nu jiang nan, dao mo he bei,
    Dao chu dou you hua rong ming mei.
Lai hui hui shou, zai diao ge tou,
    Wu xian chun guang zai wo xiong.
Cong jing cheng, dao yuan ye,
    Dao chu dou you sheng de xi yue.
Lai hui hui shou, zai yan ran huang ge tou,
    Wu xian CHUN GUANG XIAN ZU GUO!!!
Lai hui hui shou, zai yan ran huang ge tou,
    Wu xian CHUN GUANG XIAN ZU GUO!!!

samples:
 1 Tao hua kai yo li hua kai, jie jie mei mei dong qi lai;
 2 Tao hua kai yo li hua kai, jie jie mei mei tiao qi lai.
 3     Gei ni zi ji, chun yi mai huai (yi ya yo);
 4     Gei xin shang ren, chun se man kai.
 5 Tao hua kai yo li hua kai, jie jie mei mei dong qi lai;
 6 Tao hua kai yo li hua kai, jie jie mei mei tiao qi lai.
 7     Gei tong bao men, chun yi man huai, hai hai yo;
 8     Gei zhe da di, chun se quan kai!!!
 9 Cong na nu jiang nan, dao mo he bei,
10     Dao chu dou you hua rong ming mei.
11 Lai hui hui shou, zai diao ge tou,
12     Wu xian chun guang zai wo xiong.
13 Cong jing cheng, dao yuan ye,
14     Dao chu dou you sheng de xi yue.
15 Lai hui hui shou, zai yan ran huang ge tou,
16     Wu xian CHUN GUANG XIAN ZU GUO!!!
17 Tao hua kai yo li hua kai, Jiong xian mei mei dong qi lai;
18 Tao hua kai yo li hua kai, Jie jie mei mei tiao qi lai.
19     Gei ni zi ji, chun yi mai huai chun yi man huai yi ya yo;
20     Gei xin shang ren, chun se man kai chun se man kai.
21 Tao hua kai yo li hua kai, Jie jie mei mei dong qi lai;
22 Tao hua kai yo li hua kai, Jie jie mei mei tiao qi lai.
23     Gei tong bao men, chun yi man huai, hai hai yo;
24     Gei zhe da di, chun se quan kai!!!
25 Cong na nu jiang nan, dao mo he bei,
26     Dao chu dou you hua rong ming mei.
27 Lai hui hui shou, zai diao ge tou,
28     Wu xian chun guang zai wo xiong.
29 Cong jing cheng, dao yuan ye,
30     Dao chu dou you sheng de xi yue.
31 Lai hui hui shou, zai yan ran huang ge tou,
32     Wu xian CHUN GUANG XIAN ZU GUO!!!
33 Lai hui hui shou, zai yan ran huang ge tou,
34     Wu xian CHUN GUANG XIAN ZU GUO!!!

hint:
### 数据范围及约定

对于全部数据，保证输入的文本文件的字符总数（包括换行符在内），不超过 $2\times 10^4$。同时，保证输入数据合法。

评测时，会忽略选手输出文件的行末空格与文末换行。因此选手可以自行决定行尾是否要输出多余空格。请使用 Java 或 Python 语言作答的选手注意输入输出时的效率。


title: [传智杯 #5 初赛] E-梅莉的市场经济学

background:
梅莉这个学期选修了经济学。但是主修心理学的她实在不擅长经济领域的分析，为此她时常抱怨自己学不会，想退课。

但是如果现在退掉的话这学期的学分就不够啦，因此她根据“梦中”的经历，“胡诌”了一个简单到不现实的市场模型，并依据这个模型编起了 essay。为了方便地编出图表，她需要写一个程序来查询每个时刻的市场贸易差。

description:
市场每一天的贸易差可以视为一个有周期性规律的数列 $a$：$\color{red}[0],\color{blue}[0,\allowbreak 1,\allowbreak 0,\allowbreak -1,\allowbreak 0],\color{red}[0,\allowbreak 1,\allowbreak 2,\allowbreak 1,\allowbreak 0,\allowbreak -1,\allowbreak -2,\allowbreak -1,\allowbreak 0],\allowbreak \color{blue}[0,\allowbreak 1,\allowbreak 2,\allowbreak 3,\allowbreak 2,\allowbreak 1,\allowbreak 0,\allowbreak -1,\allowbreak -2,\allowbreak -3,\allowbreak -2,\allowbreak -1,\allowbreak 0]\dots$ 具体而言，$a$ 可以被分为无穷段，第 $i$ 段的内容为 $\{0,\allowbreak 1,\allowbreak \cdots,\allowbreak i,\allowbreak i-1,\allowbreak \cdots,0,\allowbreak -1,\allowbreak \cdots,\allowbreak -i,\allowbreak -i+1,\allowbreak \cdots 0\}$。如下图所示，是将 $a$ 数列内的前一些点绘制在坐标轴上的情况：

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

现在梅莉对市场发起了 $q$ 次询问，每次她会给定一个 $k$，希望求出 $a_k$ 是多少。

inputFormat:
- 第一行有一个正整数 $q$，表示询问次数。
- 接下来 $q$ 行，每行一个正整数 $k$，描述每次询问。

outputFormat: - 输出共 $q$ 行。对于每次询问，输出对应的结果。

hint: 对于所有数据，$1 \leq q \leq 10^5$，$1 \leq k \leq 4\times 10^{18}$。


title: [传智杯 #5 初赛] I-不散的宴会

background:
学校正在组织宴会。

莲子和梅莉发现，学校的结构十分复杂。学生之间存在着部门与上司的关系。每一个部门内部，都呈现出连成一条线的上司关系。一个部门内等级最高的学生，又可能受限于另外某个部门内的某个学生。

莲子和梅莉同样参加了宴会。但是她们对参加学生有自己的评判。例如，她对某些部门比较喜欢，对另一些部门则不感兴趣。同时对位居不同等级的学生同样有着不同的看法。

正如某个经典问题所描述的一样，每个学生都不希望与自己的直接上司共同参加宴会。

梅莉想要知道，最好情况下，有多少个参加宴会的学生是她喜欢的。

description:
学生社会可以被看作一个排列成等腰直角三角形的节点阵列。该节点阵列共有 $n$ 行，第 $i$ 行共有 $i$ 个节点。我们将第 $i$ 行第 $j$ 列的节点，标号为 $(i,j)$。

- 这些节点具有权值。具体而言，节点 $(i,j)$ 的权值为 $r_i\oplus c_j$，其中 $r$ 和 $c$ 是给定的 $01$ 序列，$\oplus$ 是**二进制异或**操作。
- 这些节点有边相连。具体而言，对于 $1\le i< n$，$1\le j\le i$，会有一条边连接 $(i,j)$ 和 $(i+1,j)$。此外，对于 $2\le i\le n$，还会有边连接 $(i,i)$ 和 $(i-1,a_i)$。其中 $a$ 是给定的序列。

现在你需要从这些节点中，选出一些节点，使得这些节点间**两两不存在边相连**，最大化选出来的节点的**权值之和**。

如下图所示，是 $n=8$ 的一个例子。黑色节点权值为 $1$，白色节点权值为 $0$。

**注**：图片中只象征性地给出了部分 $r_i$ 和 $c_i$ 的值。该图片上实际 $\def\t{,\allowbreak}r=\{1\t 1\t 0\t 1\t 0\t 0\t 0\t 1\}\t c=\{0\t 0\t 1\t 0\t 1\t 1\t 0\t 0\}$。

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

inputFormat:
- 第一行有一个正整数 $n$，描述节点阵列的大小。
- 第二行有 $n$ 个整数 $0$ 或者 $1$，描述 $r_i$ 的值。
- 第三行有 $n$ 个整数 $0$ 或者 $1$，描述 $c_i$ 的值。
- 第四行有 $n-1$ 个正整数，其中第 $i$ 个数描述 $a_{i+1}$ 的值。

outputFormat: - 输出共一行一个整数，描述选出的节点的权值之和的最大值。

hint:
### 样例解释

一种可能的选择方案如下图所示。橘红色方块表示选中的节点。

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

### 数据范围及约定

对于全部数据，保证 $1\le n\le 10^6$，$r_i\in\{0,1\}$，$c_i\in\{0,1\}$，$1\le a_i<i$。


title: [传智杯 #5 初赛] B-莲子的机械动力学

background:
**【题目背景和题目描述的两个题面是完全等价的，您可以选择阅读其中一部分。】**

专攻超统一物理学的莲子，对机械结构的运动颇有了解。如下图所示，是一个三进制加法计算器的（超简化）示意图。

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

一个四位的三进制整数，从低到高位，标为 $x_1,x_2,x_3,x_4$。换言之，这个数可以写成 $\overline{x_4x_3x_2x_1}_{(3)}$。把它放在这四个齿轮里，对应箭头指向的数字就是现在这位的数值。

在这种机械式计算机里，我们通过齿轮的啮合来实现数位间的连接。通过不同齿轮半径的比例来确定进制。图中所有浅灰色的小齿轮的半径，比上使用皮带相接的较大齿轮的半径，都是 $1:3$。那么小齿轮每转动一圈，大齿轮就转动 $\dfrac{1}{3}$ 圈，也就是刚好一个数码的角度。

于是，我们通过控制齿轮的半径实现了 $3$ 进制的进位。

如果需要实现三进制加法，则只需要在对应数位拨动对应的数码长度即可。

如下是个例子，实现 $\overline{1021}_{(3)}+\overline{0021}_{(3)}=\overline{1112}_{(3)}$

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

初始时齿轮的状态如上。

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

把第一个齿轮拨动一个单位长度，变为如上图所示。

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

把第二个齿轮拨动两个单位长度，变为如上图所示。读数，得到结果 $\overline{1112}_{(3)}$。

---

现在莲子设计了如下图所示的机械结构。对于从左往右数的第 $i$ 枚齿轮，它上面的浅色小齿轮与第 $i+1$ 枚齿轮上的深色小齿轮的半径之比为 $1:(i+2)$。也就是说，第 $i$ 枚齿轮每转动 $1$ 圈，第 $i+1$ 枚齿轮转过的角度恰好为它上面的一个数码。

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

莲子想要知道，在这样的特别的进制表示下，给定 $a,b$，那么计算出的 $a+b$ 的结果是多少。

description:
题目背景的问题可以转化为如下描述：

给定两个长度分别为 $n,m$ 的整数 $a,b$，计算它们的和。

但是要注意的是，这里的 $a,b$ 采用了某种特殊的进制表示法。最终的结果也会采用该种表示法。具体而言，从低位往高位数起，第 $i$ 位采用的是 $i+1$ 进制。换言之，相较于十进制下每一位的「逢 $10$ 进 $1$」，该种进制下第 $i$ 位是「逢 $i+1$ 进 $1$」。

下图所示，左边是十进制的竖式加法；右边是这种特殊进制的竖式加法。图中的红色加号表示上一位发生了进位。

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

inputFormat:
- 第一行有两个整数 $n,m$，分别表示 $a$ 和 $b$ 的位数。
- 第二行有 $n$ 个整数，中间用空格隔开，**从高到低位**描述 $a$ 的每个数码。
- 第三行有 $m$ 个整数，中间用空格隔开，**从高到低位**描述 $b$ 的每个数码。

outputFormat: - 输出有若干个整数，从高到低位输出 $a+b$ 在这种特殊表示法下的结果。

hint: 对于全部数据，保证 $1\le n,m\le 2\times 10^5$，从低位往高位数起有 $a_i\in[0,i]$，$b_i\in[0,i]$。请使用 Java 或 Python 语言作答的选手注意输入输出时的效率。


title: [传智杯 #5 初赛] D-莲子的物理热力学

background:
莲子正在研究分子的运动。

每个分子都有一个速度，约定正方向为正，负方向为负。分子的数量极多，速度又并不一致，看上去杂乱无章。于是莲子希望调整部分分子的速度，使得最终分子们看上去整齐。

description:
莲子给定了 $n$ 个整数 $a_1,a_2,\cdots a_n$，描述每个分子。现在她可以进行**至多** $m$ 次操作（也可以一次也不进行），每次操作可以执行以下两条之一：

- 选择 $i$，满足 $a_i=\min_j\{a_j\}$，然后将 $a_i$ 变为 $\max_j\{a_j\}$。
- 选择 $i$，满足 $a_i=\max_j\{a_j\}$，然后将 $a_i$ 变为 $\min_j\{a_j\}$。

现在莲子希望需要最小化最终序列的极差（最大值减去最小值的差）。请求出最小的极差。

---

例如，对于序列 $a=\{5,1,4\}$，可以进行如下几次操作：

- 选择 $i=1$，满足 $a_1=5$ 是当前的最大值 $5$，可以将 $a_1$ 修改成当前的最小值 $1$，此时序列变成 $\{1,1,4\}$；
- 再选 $i=2$，满足 $a_2=1$ 是当前的最小值 $1$，可以将 $a_2$ 修改成当前的最大值 $4$，此时序列变成 $\{1,4,4\}$。

这两次操作后得到的序列为 $\{1,4,4\}$。最大值减去最小值的差为 $|4-1|=3$。

当然，这种操作方式得到的极差并非最小。最优策略是，先将最大值 $a_1=5$ 变成目前的最小值 $1$，再把此时的最大值 $a_3=4$ 变成目前的最小值 $1$。此时序列为 $\{1,1,1\}$，得到的极差 $|1-1|=0$ 是所有策略中最小的。

inputFormat:
- 第一行有两个正整数 $n,m$，分别表示序列的长度和你最多可以进行的操作次数。
- 第二行有 $n$ 个整数 $a$，描述给定的序列。

outputFormat: - 输出共一行一个整数，表示最优策略下能得到的最小极差。


title: [传智杯 #5 初赛] G-二人的花纹纸游戏

background:
梅莉买到了一张特殊的带有花纹的纸。整张纸的图案可以视为，由一个较小的图案，沿着横向与纵向无限循环而成。同时，这个基本图案部分透明，部分不透明。

于是，如果将这张纸覆盖在书本上，那么一些字可以被看见，另一些字看不见。

莲子突发奇想：假使她制作一张很大很大的数表，将花纹纸覆盖在上面，那么就会有很多数字被遮挡。那些没有被遮挡的数字的和是多少呢？

description:
事实上，二人的问题可以转化成如下描述：给定一个 $n$ 行 $m$ 列的普通矩阵 $A$，以及一个 $r$ 行 $c$ 列的 $01$ 矩阵 $B$。$B$ 中为 $1$ 的格子是黑色，不透明；为 $0$ 的格子是透明的。

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

使用 $B$ 矩阵，循环生成一个**无穷大**的矩阵 $M$：

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

现在有 $q$ 次询问。每次将 $M$ 矩阵左上角和 $(x_1,y_1)$ 对齐，此时此时会有一些 $A$ 中的元素被遮挡，另一些元素可以被看见。

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

求出此时，$A$ 当中以 $(x_1,y_1)$ 作为左上角，$(x_2,y_2)$ 作为右下角的子矩阵中，可以被看见的元素之和。结果对 $998{,}244{,}353$ 取模。

在上面的例子里，$(x_1,y_1)=(2,3)$，$(x_2,y_2)=(4,7)$。可以被看见的元素之和为 $a_{2,3}+a_{2,5}+a_{2,6}+a_{3,5}+a_{4,3}+a_{4,5}+a_{4,6}$。

### 形式化题面

给定一个 $n$ 行 $m$ 列的普通矩阵 $A$，以及一个 $r$ 行 $c$ 列的 $01$ 矩阵 $B$。使用 $B$ 矩阵，生成一个**无穷大**的矩阵 $M$：

$$M=
\begin{pmatrix}
B & B & B  &\cdots \\
B & B & B  &\cdots \\
B & B & B  &\cdots \\
\vdots &\vdots &\vdots &
\end{pmatrix}
=\begin{pmatrix}
b_{1,1} & b_{1,2} & \cdots & b_{1,c} & b_{1,1} & b_{1,2} & \cdots & b_{1,c} & b_{1,1} & \cdots \\
b_{2,1} & b_{2,2} & \cdots & b_{2,c} & b_{2,1} & b_{2,2} & \cdots & b_{2,c} & b_{2,1} & \cdots \\
\vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots &  \\
b_{r,1} & b_{r,2} & \cdots & b_{r,c} & b_{r,1} & b_{r,2} & \cdots & b_{r,c} & b_{r,1} & \cdots \\
b_{1,1} & b_{1,2} & \cdots & b_{1,c} & b_{1,1} & b_{1,2} & \cdots & b_{1,c} & b_{1,1} & \cdots \\
b_{2,1} & b_{2,2} & \cdots & b_{2,c} & b_{2,1} & b_{2,2} & \cdots & b_{2,c} & b_{2,1} & \cdots \\
\vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots &  \\
b_{r,1} & b_{r,2} & \cdots & b_{r,c} & b_{r,1} & b_{r,2} & \cdots & b_{r,c} & b_{r,1} & \cdots \\
\vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots &  \\
\end{pmatrix}$$

现在有 $q$ 次询问，每次给出一个子矩阵的左上角坐标 $(x_1,y_1)$ 和右下角坐标 $(x_2,y_2)$，你需要求出：

$$S=\left(\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}a_{i,j}\times [M_{i-x_1+1,j-y_1+1}=0] \right)\bmod 998{,}244{,}353$$

其中 $[P]$ 表示艾弗森括号。若 $P$ 为真，则 $[P]=1$，否则 $[P]=0$。

inputFormat:
- 第一行有两个正整数 $n,m$，描述矩阵 $A$ 的大小。
- 接下来 $n$ 行 $m$ 列，每行一个非负整数，描述 $A$ 中的元素 $a_{i,j}$。
- 下一行有两个正整数 $r,c$，描述矩阵 $B$ 的大小。
- 接下来 $r$ 行 $c$ 列，每行一个非负整数，描述 $B$ 中的元素 $b_{i,j}$。
- 下一行有一个正整数 $q$，表示询问的次数。
- 接下来 $q$ 行，每行有四个正整数 $x_1,y_1,x_2,y_2$，描述一组询问。保证 $x_1\le x_2$，$y_1\le y_2$。

outputFormat: - 输出共 $q$ 行。每行输出该次询问的答案。

hint:
### 样例 1 解释

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

- 对于第一次询问，结果为 $2+4+5+7+10+12=40$；
- 对于第二次询问，结果为 $3+6+11=20$。

### 数据范围及约定

对于全部数据，保证 $1\le n,m\le 10^3$，$1\le q\le 10^4$，$1\le r,c\le 50$，$0\le a_{i,j}<998{,}244{,}353$，$b_{i,j}\in\{0,1\}$。


title: [传智杯 #5 初赛] H-二人的世界

background:
莲子设计了一个三维立体空间软件。这个软件可以模拟真实的物理引擎，包括实体方块和水流方块。然而，同时计算大量水流会对软件造成不小的负荷。

于是，莲子希望找到这样一种算法，快速计算这些水流模拟后的结果。

description:
莲子设计的水流模型是这样的：

考虑一个三维空间。这个空间内有 $n$ 个正方体。我们使用坐标 $(x_i,y_i,h_i)$ 描述每个正方体的位置。这些正方体，可以被称作**实体方块**。

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

现在将会在这张图中模拟一种水流机制。具体而言，我们会定义**水方块**。水方块会有一个强度 $s$，范围是 $[1,k]$。

### 运行逻辑

- 假定 $(x,y,h)$ 处有强度为 $s$ 的水方块，且 $(x,y,h-1)$ 位置没有实体方块，那么下一时刻 $(x,y,h-1)$ 位置会生成强度为 $k$ 的水方块。**注意**：无论此时 $s$ 的值是多少，在 $(x,y,h-1)$ 位置生成的水方块的强度都是 $k$。
- 假定 $(x,y,h)$ 处有强度为 $s$ 的水方块，且 $s>1$，且 $(x,y,h-1)$ 位置有实体方块，那么会进行**扩散操作**。
- 如果下一时刻，某个位置 $(x,y,h)$ 同时有多个水方块会生成，那么最终生成的水方块的强度，是这些可能生成的水方块里，最大的强度。

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

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

### 扩散操作

**考虑到扩散操作比较抽象，建议结合图示理解**。

对于水方块 $(x,y,h)$，它会在高度 $h$ 的平面上进行寻路。为了考虑这个过程，我们考虑这个高度为 $h$ 的平面：

- 如果空间里 $(x,y,h)$ 位置有实体方块存在，那么平面上 $(x,y)$ 处**不可经过**。否则，如果没有实体方块，那么 $(x,y)$ 处**可以经过**。
- 在 $(x,y)$ **可以经过**的情况下，如果空间里 $(x,y,h-1)$ 位置没有实体方块存在，那么平面上 $(x,y)$ 位置称为**目标位置**。目标位置可以不止一个。

根据扩散的前提条件，可知平面上 $(x,y)$ 位置可以经过，但不是目标位置。

从平面上 $(x,y)$ 处出发，进行路径的搜索。每次在 $(a,b)$ 位置会向 $(a+1,b),(a-1,b),(a,b+1),(a,b-1)$ 位置扩展。搜索过程会找到距离 $(x,y)$ 位置**最近**的，且距离不超过 $s-1$ 的**所有**目标位置，或者找不到这样的目标位置。

- 如果存在这样的目标位置，那么在到达目标位置的最短路的方向上，下一时刻会生成一个强度为 $s-1$ 的水方块。
- 如果不存在这样的目标位置，那么下一时刻，会向 $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$ 位置都生成强度为 $s-1$ 的水方块（如果这个位置可以到达的话）。

请结合图示理解扩散过程。

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

如图所示。$S$ 处是平面上该水方块所在的位置。白色的方块是目标位置，打 $\times$ 的方块是不可经过的位置。我们计算出 $S$ 到达最近的目标位置的最小值 $d_{\min}=5$，图中标出来的**红色路径**就是三条可能的最短路。

如果 $s>5$，那么下一时刻，在**蓝色箭头**处会有强度为 $s-1$ 的水方块生成。否则，若 $5\ge s>1$，那么下一时刻除了蓝色箭头外，灰色路径对应的方向**也会生成**强度为 $s-1$ 的水方块。

---

为了检验水流模型的合理性以及其运行效率，莲子提出了这个问题：在 $(x_0,y_0,10^9+1)$ 处，有一个强度为 $k$ 的水方块。询问：在经过充分长的时间后（比如经过了 $10^{9961^{9961}}$ 时刻），有多少个点对 $(a,b)$，满足在 $(a,b,-1)$ 位置，会有水方块生成过。

inputFormat:
- 第一行有两个正整数 $n,k$ 和两个整数 $x_0,y_0$，描述实体方块的个数、水方块最大强度，以及初始水方块的位置。
- 接下来 $n$ 行，每行三个整数 $x_i,y_i,h_i$，描述每个实体方块的位置。保证不存在两个位置完全相同的实体方块。

outputFormat: - 输出共一行一个整数，表示有多少个点对 $(a,b)$，使得充分长时间后 $(a,b,-1)$ 位置有水方块生成过。

hint:
### 样例 1 解释

（图片实在太难画啦，将就一下吧。）为了防止方块阻挡导致看不见，方块全部换成了透明的。

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

初始状态下一根水流柱从高空落下，落在了方块 $(3,4,2)$ 上，进行了扩散。水方块的坐标为 $(3,4,3)$，强度为 $3$。

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

- 如图 $3$，根据寻路机制，它会在 $(3,5,3)$ 和 $(4,4,3)$ 上生成强度为 $2$ 的水方块。
- 如图 $4$，生成的两个支流下方都没有方块，于是在 $(3,5,2)$ 和 $(4,4,2)$ 上生成强度为 $3$ 的水方块。
- 如图 $5$，水方块 $(3,5,2)$ 下方依旧没有实体方块，于是在 $(3,5,1)$ 生成了强度为 $3$ 的水方块，一直流到 $(3,5,-1)$；水方块 $(4,4,2)$ 下方有实体方块，于是在 $(4,3,2)$ 生成了强度为 $2$ 的水方块。

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

下面只关心水方块 $(4,3,2)$。它下面有实体方块 $(4,3,1)$，于是它向两边扩散，生成强度均为 $1$ 的两个水方块。这两个方块下面都不再有实体方块，于是**一直往下流**到 $(4,2,-1)$ 和 $(5,3,-1)$。

因此，最终一共会有三个位置 $(3,5,-1)$、$(4,2,-1)$、$(5,3,-1)$ 有水方块经过。

### 数据范围及约定

对于所有数据，$1\le n\le 10^5$，$1\le k\le 10^9$，$0\le |x_i|,|y_i|\le 10^9$，$0\le h_i\le 10^9$。


title: [语言月赛202211] Power Strip

description:
理塘大学举行了第五人格校内排位赛，很多同学带了自己的笔记本电脑用来比赛。笔记本需要供电，但是很快同学们发现了一个问题，赛场里只有一个插座！因此同学们将自己的插排带到了赛场里。

具体的，同学们一共带来了 $n$ 个插排，我们分别将其标号为 $1 \sim n$。

下一个问题是插排的安装问题。由于赛场里只有一个插座，因此同学们只能用如图的 “插排插插排” 的方式。

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

$$\begin{matrix} \color{red} \small \text{请注意，这种情况只是服务于题目背景，但是十分不符合用电安全！} \\\color{red} \small \text{在生活用电中，请保证安全至上！}\end{matrix}$$

具体的，你会得到一个长度为 $n - 1$ 的序列 $u _ 2, \cdots, u _ n$。 除编号为 $1$ 的插排连接在插座上外，$u _ i$ 代表编号为 $i$ 的插排连接在 $u _ i$ 编号的插排上，我们保证 $u _ i < i$。

插排安装好后，同学们将充电器插在了不同的插座上。最后，我们可以用一个序列 $a _ 1, a _ 2, \cdots, a _ n$ 表示充电器的使用情况。具体的，对于标号为 $i$ 的插座，其被插上了 $a _ i$ 个充电器。

我们定义插排 $i$ 向某个充电器**供电**，当且仅当电流从赛场中的唯一一个插座流向这个充电器的时候，经过了插排 $i$。

如果对供电的概念有疑问，可以参照**样例解释 #1**进一步理解。

现在同学们想要知道，对于每一个插排，这个插排在向几个充电器**供电**。然而这个问题对于他们来说太难，所以他们找到了你，希望你能够帮他们解决这个问题。

inputFormat:
输入共三行。

第一行为一个整数 $n$，代表插排数量。

第二行 $n - 1$ 个整数 $u _ \bold{2}, u _ 3, \cdots, u _ n$，代表第 $2 \sim n$ 号插排连接的插排序号。

第三行 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，代表 $1 \sim n$ 插排上插上的的充电器数量。

outputFormat:
输出一行。

第一行为 $n$ 个整数，以一个空格隔开，代表每个插排**供电**的充电器数量。

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

我们使用紫色矩形表示一个充电器，样例 #1 的插排排布如下图：

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

以 $4$ 号插排举例，显然 $4, 5, 6$ 号插排上的充电器供电都需要经过 $4$ 号插排。电流方向如下图蓝色箭头所示。

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

$4$ 号插排供电的充电器共有 $1 + 2 + 4 = 7$ 个。

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

对于前 $10\%$ 的数据，保证 $n = 2$。

对于前 $20\%$ 的数据，保证 $n \leq 10$。

对于前 $50\%$ 的数据，保证 $n \leq 5 \times 10 ^ 3$。

对于另外 $10\%$ 的数据，保证对任意的 $2 \leq i \leq n, u_i = i - 1$。

对于另外 $10\%$ 的数据，保证对任意的 $2 \leq i \leq n, u_i = 1$。

对于所有数据，保证 $2 \leq n \leq 1 \times 10 ^ 6, 0 \leq a _ i \leq 10 ^ 9, 1 \leq u _ i < i$。


title: 「KDOI-03」还原数据

description:
小 E 正在做一道经典题：

给定一个长度为 $n$ 的序列 $a$ 和 $q$ 个操作，操作共有 $2$ 种类型：

+ $\tt{1~l~r~x}$：对于所有 $l\le i\le r$，$a_i\leftarrow a_i+x$。
+ $\tt{2~l~r~x}$：对于所有 $l\le i\le r$，$a_i\leftarrow \max(a_i,x)$。

题目要求输出所有操作结束后的最终序列 $a'$。

小 E 迅速写了一份代码提交，但是发现，由于宇宙射线的影响，输入数据出现了一些小问题。具体地，对于所有 $2$ 操作，操作中给出的 $x$ 均被丢失了，也就是说，输入数据中的 $2$ 操作只剩下了 $\tt{2~l~r}$。输出数据则没有问题。小 E 现在想要通过剩余的数据恢复原来的输入数据，请你帮助他完成这个任务。

当然，可能会有多种合法的输入数据，你需要找到其中任意一种。数据保证有解。

inputFormat:
从标准输入读入数据。

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

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

对于每组测试数据，第一行两个非负整数 $n,q$。

第二行 $n$ 个整数，表示初始序列 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行一次操作，形如 $\tt{1~l~r~x}$ 或 $\tt{2~l~r}$。

接下来一行 $n$ 个整数，表示最终序列 $a_1',a_2',\ldots,a_n'$。

outputFormat:
输出到标准输出。

**本题开启自定义校验器（Special Judge）。**

对于每组测试数据，设共有 $q_2$ 个 $2$ 操作，输出一行 $q_2$ 个整数，第 $i$ 个整数表示第 $i$ 次 $2$ 操作中所给出的 $x$ 的值。

你需要保证 $-10^{15}\le x\le 10^{15}$。

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

所有合法输出需要满足：第 $1$ 个数 $\le3$，第 $2$ 个数恰好为 $20$。

**【样例 2】**

见选手文件中的 `restore/restore2.in` 与 `restore/restore2.ans`。

**【样例 3】**

见选手文件中的 `restore/restore3.in` 与 `restore/restore3.ans`。

***

**【数据范围】**

记 $q_2$ 为单组数据内 $2$ 操作的个数，$\sum n$ 为单个测试点内所有 $n$ 的和，$\sum q$ 为单个测试点内所有 $q$ 的和。

对于 $20\%$ 的数据，保证 $n,q\le50$，$\sum n,\sum q\le1~000$。

对于 $40\%$ 的数据，保证 $n,q\le1~000$，$\sum n,\sum q\le10^5$。

对于另外 $20\%$ 的数据，保证 $l=1,r=n$。

对于另外 $20\%$ 的数据，保证 $q_2\le100$。

对于 $100\%$ 的数据，保证 $1\le T\le 100$，$1\le n,q\le 10^5$，$1\le\sum n,\sum q\le 3\times10^5$，$-10^9\le a_i,x\le 10^9$，$-10^{15}\le a_i'\le10^{15}$， $q_2\ge1$。

***

**【校验器】**

本题样例文件较大，无法在附件中下载，请在选手文件中查看。

为了方便测试，在 $\texttt{restore}$ 目录下我们下发了 $\texttt{checker.cpp}$ 文件。你可以编译该文件，并使用它校验自己的输出文件。请注意它与最终评测时所用的校验器并不完全一致，你不需要也不应该关心其代码的具体内容。

编译命令为：

```plain
g++ checker.cpp -o checker -std=c++14
```

使用方式为：

```
./checker <inputfile> <outputfile> <answerfile>
```

校验器可能会返回以下状态中的其中一种：

+ $\tt{Accepted}$：表示你的输出完全正确。
+ $\tt{Wrong~answer~at~testcase~ x}$：表示你的输出在第 $x$ 个测试数据出错。

***

**【提示】**

本题输入输出量较大，推荐使用较快的输入输出方式。

KDOI 出题组温馨提示：**多测不清空，爆零两行泪。**


title: [传智杯 #5 初赛] A-莲子的软件工程学

background:
在宇宙射线的轰击下，莲子电脑里的一些她自己预定义的函数被损坏了。

对于一名理科生来说，各种软件在学习和研究中是非常重要的。为了尽快恢复她电脑上的软件的正常使用，她需要尽快地重新编写这么一些函数。

description:
具体而言，给定两个整数 $a,b$，保证 $b\neq 0$。莲子要实现这样一个函数 $\operatorname{fun}(a,b)$ 来将 $b$ 的符号转移到 $a$ 上。

具体而言，$\operatorname{fun}(a,b)=\operatorname{sgn}(b)\times |a|$。其中，$\operatorname{sgn}(b)=\begin{cases}1&b>0\\-1&b<0\end{cases}$

换而言之：

- 如果 $b$ 是正数，那么 $\operatorname{fun}(a,b)=+|a|=|a|$；
- 如果 $b$ 是负数，那么 $\operatorname{fun}(a,b)=-|a|$。

inputFormat: - 共一行两个整数 $a,b$。

outputFormat: - 共一行一个整数 $\operatorname{fun}(a,b)$ 的值。

hint: 对于全部数据，保证 $a,b$ 在 $32$ 位有符号整型范围内，并且 $b \neq 0$。


title: [传智杯 #5 初赛] F-二人的大富翁游戏

background:
作为大学生，莲子和梅莉有着比高中时更为闲暇的课余时光。在没有课的时候，她们喜欢玩大富翁这一游戏，在游玩过程中交流自己的喜怒哀乐。

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

如图所示，是一个 $n=10$ 的大富翁地图。玩家在圆格子上行动。而方格子则可以建造建筑物。每个圆格子唯一对应一个方格子。

**（友情提示：赌博是不对的）**

description:
莲子和梅莉在玩大富翁游戏。这个大富翁游戏是由传智播客定制的，**与一般的大富翁游戏在玩法上有略微区别**，因此也被称为传智大富翁。

大富翁游戏是由 $n$ 个格子组成，编号逆时针地从 $1,2,\dots,n$，构成了一个环。莲子和梅莉起始在编号为 $1$ 的格子。莲子和梅莉最开始都有 $m$ 元资金。每一个回合，莲子先投掷骰子，再是梅莉投掷骰子。每一方行动时，设骰子最上面的数字为 $k$，则行动方逆时针移动 $k$ 步。在移动的过程中，行动者所经过的每一个格子应当都分为两种情况：

- 如果当前格子（假设编号为 $i$）上有建筑物，而且建筑物是自己的，则行动方可以获得额外的 $a_i$ 元资金。
- 如果当前格子上有建筑物，但是建筑物是对方的，则行动方要将自己的 $a_i$ 元资金转移给对方。

在行动结束后亦有两种情况：

- 如果当前格子（设编号为 $i$）上没有建筑物，则行动方可以选择花费 $C_{i,0}$ 元资金（前提要求行动者当前的资金大于等于 $C_{i,0}$）搭建建筑物，此时 $a_i$ 被初始化为 $C_{i,0}$。
- 如果当前格子的建筑物是行动方的，假设当前是一座 $j$ 等级的建筑物，那么行动方可以选择用 $C_{i,j}$ 元为建筑物升级，功效是使得 $a_i \gets a_i+C_{i,j}$。这里，$C_{i,j}$ 表示将第 $i$ 个格子上的第 $j$ 等级的建筑物升级到第 $j+1$ 等级的建筑物所需花费的资金。同一回合内可以多次升级建筑。特别地，建筑物的等级上限为 $L$。如果当前建筑物等级已经到达上限则无法升级。
- 在所有建筑操作结束后，操作权转移给另一方。

两人都操作完一轮回合后，圆环上的每个建筑物都会提供给拥有者资金，具体来说，第 $i$ 格上的建筑物会给其拥有者提供 $d_i$ 的资金。游戏结束当且仅当存在一个人在它行动过程中或者结束时的资金为负数。此时这个人成为输家（换而言之，允许中途过程资金为 $0$）。

给定莲子和梅莉的 $q$ 个回合的每次操作，请问谁会是输家呢？

inputFormat:
第一行输入四个正整数 $n,m,q,L$，表示格子数、初始资金、回合次数和建筑物等级上限。

第二行开始，往下 $n$ 行，每行输入 $L$ 个正整数，表示 $C_{i,j}$，其中 $j$ 是从 $0$ 到 $L-1$。

第 $(n+2)$ 行输入 $n$ 个正整数表示 $d_i$。

第 $(n+3)$ 行开始，往下若干行，每行只会有两种可能的情况：

- $\texttt{1 k}$，表示当前行动方投掷了骰子，最上面的点数是 $k$。之后行动者会逆时针移动 $k$ 步。
- $\texttt{2 k}$，表示当前行动方在当前位置**建造或者升级**了建筑物共 $k$ 次。
  - 在此过程中，当前位置已经有了对方建筑物则忽略此操作；
  - 如果资金不够升级 $k$ 次，则只升级到资金允许范围内的最高等级；
  - 在此过程中，如果进行下一次升级，建筑物等级超过 $L$，则后续的所有升级忽略处理。

特别地，规定除了第一次外，每次 $\texttt{1 k}$ 操作出现时意味着行动者的切换。也就是说，第一次输入 $\texttt{1 k}$ 操作时，行动方是莲子，第二次是梅莉，第三次是莲子……以此类推。值得注意的是，$\texttt{2 k}$ 操作出现**并不会**切换行动者。

此外，**保证每个 $\bm 1$ 操作后面最多跟随 $\bm 1$ 个 $\bm 2$ 操作**。

outputFormat:
如果已经分出了输赢，则输出谁是输家（如果莲子输，则输出 $\texttt{Renko}$；如果梅莉输，则输出 $\texttt{Merry}$）；

如果没有分出输赢，则按照先莲子，后梅莉的顺序输出她们现在有的资金数。

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

第一回合，莲子首先走 $4$ 步，到达编号为 $5$ 的格子，同时尝试建造与升级 $3$ 次第五个格子的建筑物，但是 $C_{5,0}+C_{5,1}+C_{5,2}=48$，所以只能把建筑物造到 $2$ 级。此时莲子手上还有 $16$ 元。
接着梅莉走了两步，到达编号为 $3$ 的格子，同时尝试建造与升级 $5$ 次第三个格子的建筑物，$C_{3,0}+C_{3,1}+C_{3,2}=26$，而造五次会超过等级上限 $L$，因此只能升到 $3$ 次，此时梅莉手上还有 $14$ 元。
回合结束后每个建筑物都会提供给拥有者 $d_i$ 的资金，也就是说莲子此时手上有 $21$ 元，梅莉手上有 $17$ 元。
第二回合，莲子首先走 $3$ 步，到达编号为 $2$ 的格子。梅莉接着走 $2$ 步，到达编号为 $5$ 的格子，收取 $a_i$ 元。而 $a_i=24$，因此梅莉的资金被扣成了负数，从而输出 $\texttt{Merry}$。

**【样例解释 2】**

仅在初始资金与第一组样例有一定变化，因此在这些回合中无法决出胜负，因此输出两人手上现有的资金。

**【数据范围】**

对于所有数据，保证 $1 \leq n,L\leq 100$，$1 \leq q \leq 10^4$，$1 \leq m,C_{i,j},d_i \leq 10^6$，$1 \leq k \leq 10^3$（你可以不必在意怎么获得一个 $k$ 面的骰子）。数据保证 $1$ 操作次数恰好为 $2\times q$。


title: 「PFLOI R1」PFL 除法

background:
[有必要把所有比赛题的背景连在一起](https://www.luogu.com.cn/paste/enzfvjum)。

就这样，新世界的大门向它们敞开了……

“喵！”一只可爱的花猫向它们问好。

“你们刚来到这？”

“嗯。”

“我带你们去转转吧，谁叫我这么可爱呢！”

“……” 花猫突然止住，打量一番手中的序列，俶尔又微笑着说：

“但你们要先答出我的问题哦。”

description:
花猫有一个长度为 $n$ 的序列 $A$ 和另一个长度为 $m$ 的序列 $B$。你可以进行若干次以下操作：

+ 选择两个整数 $i$ 和 $j$，满足 $1\le i\le n$，$1\le j\le m$ 且 $B_j \mid A_i$，然后将 $A_i$ 变为 $\frac{A_i}{B_j}$。

**注意**：$A$ 和 $B$ 中的每个元素都可以选择并被**操作多次**。

最终要使得 $A$ 中的元素都相等，请求出最少的操作次数；若无解，输出 `-1`。

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

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

第三行 $m$ 个正整数表示序列 $B$。

outputFormat: 输出一个整数表示最少的操作次数；若无解，输出 `-1`。


title: 「KDOI-03」序列变换

description:
给定一个长度为 $n$ 的 $\tt01$ 序列 $a$ 和 $q$ 次询问，询问参数 $k$。

每次询问给定 $L,R$，其中 $1\leq L\leq R\leq n$，你可以进行如下操作：

+ 选择一个下标 $L<i\le R$；
+ 将 $a_{i-1}$ 赋值为 $a_{i-1}\oplus a_i$，$a_{i+1}$  赋值为 $a_{i+1}\oplus a_i$。如果 $i=n$，则不对 $a_{i+1}$ 作出改变。其中 $\oplus$ 表示按位异或运算。

求使得 $[L,R]$ 区间内**至多**有 $k$ 个 $\tt1$ 的最小操作次数。询问之间相互独立，也就是说，每次询问后重置为初始序列。

inputFormat:
从标准输入读入数据。

第一行包含三个正整数 $n,k,q$。

第二行包含 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$。

接下来 $q$ 行，每行包含两个正整数 $L,R$，表示一次询问。

outputFormat:
输出到标准输出。

输出共 $q$ 行，每行包含一个整数，表示答案。

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

如图，用绿色代表 $\tt0$，红色代表 $\tt1$，初始序列如下：

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

对于第 $1$ 次询问，选择 $i=3$，则序列变为下图：

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

对于第 $2$ 次询问，选择 $i=2$，则序列变为下图：

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

**【样例 2 解释】**

对于第 $1$ 次询问，由于 $a_{12},a_{13},a_{14},a_{15}$ 中只有 $2$ 个 $\tt1$，所以不需要进行任何操作。

对于第 $6$ 次询问，可以依次选择 $i=\{7,8,9,10,11,12\}$。

**【样例 3】**

见选手文件中的 `control/control3.in` 与 `control/control3.ans`。

此样例满足测试点 $7\sim10$ 的限制。

**【样例 4】**

见选手文件中的 `control/control4.in` 与 `control/control4.ans`。

此样例满足测试点 $15\sim17$ 的限制。

**【样例 5】**

见选手文件中的 `control/control5.in` 与 `control/control5.ans`。

此样例满足测试点 $18\sim21$ 的限制。

***

**【数据范围】**

对于 $100\%$ 的数据， $2\le n\le 3~000$，$1\le k\le
\min(n,1~000)$，$1\le q\le 5\times10^5$，$0\le a_i\le 1$。

|测试点编号|$n\le$|$k\le$|$q\le$|特殊性质|
|:--:|:--:|:--:|:--:|:--:|
|$1\sim3$|$80$|$50$|$2~000$|无|
|$4\sim6$|$400$|$300$|$1$|$k$ 是偶数|
|$7\sim10$|$400$|$2$|$10~000$|无|
|$11\sim14$|$400$|$300$|$10~000$|无|
|$15\sim17$|$3~000$|$10$|$5\times10^5$|无|
|$18\sim21$|$3~000$|$1~000$|$5\times10^5$|$k$ 是偶数|
|$22\sim25$|$3~000$|$1~000$|$5\times10^5$|无|


title: [集训队互测 2022] 树链剖分

background: 请注意：**本题不是树链剖分模板题**。

description:
给定一棵 $n$ 个节点的树 $T$ 以及树上的 $m$ 条 **不同的** 路径 $I_i = (u_i, v_i)(u_i\neq v_i)$。具体地，$I_i$ 表示树上 $u_i$ 和 $v_i$ 之间的简单路径上所有点形成的点集。

考虑 $T$ 上某条路径 $I = (u, v)$，定义 $f(I) = \sum\limits_{i = 1} ^ m\sum\limits_{j = 1} ^ m [I_i\cup I = I_j\cup I]$。

对于 $T$ 上所有不同路径 $I$，求 $f(I)$ 之和，并将答案对 $998244353$ 取模。也就是说，你需要求 $\left(\sum\limits_{u = 1} ^ n\sum\limits_{v = u} ^ n f((u, v))\right) \bmod 998244353$。

inputFormat:
第一行一个整数 $S$，表示子任务编号。样例的子任务编号为 $-1$。

第二行两个整数 $n, m$，分别表示树的大小和路径条数。

接下来 $n - 1$ 行，每行两个整数 $x_i, y_i$ 表示 $T$ 上的一条边。

接下来 $m$ 行，每行两个整数 $u_i, v_i$ 表示第 $i$ 条路径 $I_i$。

**保证给定路径两两不同**。

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


title: [语言月赛202212] 不可以，总司令

background:
> “同志，你只是一直在回答‘不可以’吗？你到底有没有好好判断形势？现在是关乎国家危亡的时刻……”
>
> “总司令，您知道我不太聪明，没找到快速而正确地计算出结果的办法，但是据某项统计，我一直回答 NO 的话，在一次战役中判断完全正确的概率是 $45\%$。”

（全文见 <https://www.luogu.com.cn/discuss/525529>）

description:
扶苏当上了星战地球舰队的参谋长，但是她不太聪明。

人工智能计算出，如果扶苏在一直回答“NO”的话，她在战役中判断完全正确的概率为 $x\%$；如果她一直在回答“YES”的话，她在战役中判断完全正确的概率是 $y\%$。

注意可能 $x + y \neq 100$，因为还存在她需要既回答“YES”也回答“NO”的情况，但是这一概率并不重要，因为她并不聪明，只能在全回答“YES”和全回答“NO”之中做一个选择。

扶苏自然希望做出的判断能尽可能准确，如果一直说“NO”的判断正确概率较高，她会一直回答“NO”；如果一直说“YES”的判断正确概率较高，她会一直回答“YES”。现在，给出这两者的概率，请你确定她应该回答 YES 还是 NO。

如果回答“YES”和“NO”的正确概率一样高，请你输出 “equal probability”。

inputFormat: 输入只有一行两个整数，依次表示「题目描述」中的 $x$ 和 $y$。

outputFormat:
输出一行一个字符串:
- 如果回答 “YES” 的判断正确概率较高则输出 `YES`；
- 如果回答 “NO” 的判断正确概率较高则输出 `NO`；
- 如果两者的概率一样高，请你输出 `equal probability`。

如果输出的字符串是 `YES` 或 `NO`，则字符串大小写不敏感，也就是说，`yes`, `yeS`, `yEs`, `yES`, `Yes`, `YeS`, `YEs`, `YES` 都被认为是 `YES`，`NO` 同理。

如果输出的字符串是 `equal probability`，你必须输出严格的由小写字母和空格组成的字符串，例如，`Equal probability` 将被认为是错误的输出。

samples:
0 45
yEs

samples:
50 50
equal probability

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

对全部的测试点，保证 $0 \leq x, y \leq 100$，$x + y\leq 100$。

$\textcolor{white}{\texttt{No,commander!}}$


title: [DMOI-R2] 梦境

background: 小 A 做噩梦了。

description:
小 A 的梦境可以看做有 $n$ 个点，$m$ 条边的无向图。小 A 在图上的点 $S$，有一个怪物在点 $B$，安全屋在点 $F$。

怪物正在追杀小 A，现在小 A 需要逃到安全屋。小 A 意识到这是在自己的梦境里，所以他在一定程度上操控了梦境。他把怪物的移动速度设置成了 $3$，但代价是自己的移动速度被设置成 $2$。

小 A 始终会沿着到 $F$ 的最短路走，如果有多条最短路，则小 A 会选择使得**经过点的编号所顺次构成序列的字典序最小**的那条最短路，因为他觉得这样走最不容易被怪物抓到。

而怪物在梦境中游荡，会随机向自身周围的点移动，且怪物已经访问过的点不会重复访问。

现在小 A 需要知道**在最坏情况下**他能否安全到达安全屋，或者何时被怪物抓住。

inputFormat:
第一行五个整数 $n,m,S,B,F$。

接下来 $m$ 行，第 $i$ 行三个整数 $u_i,v_i,w_i$，代表 $u_i,v_i$ 之间有一条长度为 $w_i$ 的无向边。

outputFormat:
两行。

如果小 A **在最坏情况下**能够安全到达安全屋，输出 `YES`，接下来一行输出小 A 到达安全屋后怪物到安全屋的距离。

如果小 A **在最坏情况下**不能安全到达安全屋，输出 `NO`，接下来一行输出小 A 在何时被怪物抓到。

若第二行的答案为整数则输出整数，**否则输出小数**。

hint:
**关于最坏情况的解释**：怪物的走法可能有多种。也就是说，你需要同时考虑怪物的每种走法，只要怪物的某种最短路走法可以抓到小 A 时答案即为 `NO`。而最坏情况是指怪物的走法在所有走法中能够最快抓到（或接近）小 A 的情况。

另外本题没有 special judge，也就是说如果答案是整数，你需要严格输出整数答案，不带小数点。同时数据保证不存在小数位数超过两位的答案。

### 数据范围

本题采用捆绑测试。

$$
\def{\arraystretch}{1.5}
\begin{array}{c|c|c|c|c}\hline
\textbf{~~Subtask~~}&\bm{~~n \le ~~}&\bm{~~~~m \le~~~~}& ~\textbf{~~特殊性质~~}~&\textbf{~~分值~~}\cr\hline
0	&10			&20			&		&10\cr\hline
1	&500		&1000		&		&10\cr\hline
2	&800 		&2000		&		&10\cr\hline
3	&2\times10^5&  			&\text{A+B}&15	\cr\hline
4	&2\times10^5& 			&\text{A}&15	\cr\hline
5	&10^5		&2\times10^5&		&20\cr\hline
6	&2\times10^5&2\times10^5&		&20
\end{array}
$$

特殊性质 $\text{A}$：$m=n-1$。

特殊性质 $\text{B}$：对于给定的每个 $v_i$，满足 $v_i=u_i+1$。

对于 $100\%$ 的数据，保证 $S \ne B \ne F$ 且 $1 \le S,B,F \le n$，$1 \le w_i \le 10^3$，图连通且不存在重边。

### 特殊评分方式
本题开启子任务依赖，具体如下：
- 对于子任务 $i\in\{0,3\}$，您只需答对子任务 $i$ 即可获得子任务 $i$ 的分数。
- 对于子任务 $4$，您需要答对子任务 $3$ 才能获得子任务 $4$ 的分数。
- 对于子任务 $i\in\{1,2,5,6\}$，您需要答对子任务 $0$ 才能获得子任务 $i$ 的分数。

### 附件说明
对于赛时许多选手卡在了 sub3，此处提供一组 sub3 内的数据用于检查并改正代码。


title: 「JEOI-R1」子序列

background:
| 出题 | 标程 | 数据 | 验题 | 题解 |
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
| [Pekemetier](/user/146070) | [Pekemetier](/user/146070) | [Pekemetier](/user/146070) | [cq_zry](https://www.luogu.com.cn/user/734533) & [lOlAKME](/user/768786) | [Pekemetier](/user/146070) |

description:
给定一个仅包含 `0`、`1` 和 `?` 的字符串，你需要将字符串中的每个 `?` 分别替换成 `0` 或 `1` 之一。也就是说替换成一个 $01$ 字符串。求有多少种替换方案，使得替换后的字符串满足：恰好拥有奇数个**不同的**子序列（包含空串）的非空子串的个数为奇数。特别地，如果字符串中不包含 `?`，应将其自身视为唯一的替换方案。

每个数据点会给定一个字符串 $s$ ，然后每次对 $s$ 的一个子串进行询问，答案对 $998244353$ 取模。

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

第二行一个长为 $n$ 的字符串 $s$，仅包含 `0`、`1` 和 `?`。

第三行一个整数 $m$ 表示询问次数。

接下来 $m$ 行，每行两个整数 $l,r$ 表示对子串 $s_{l,r}$ 进行一次询问。

outputFormat:
输出 $m$ 行，每行一个整数表示答案，对 $998244353$ 取模。

不存在合法方案则输出 `0`。


title: 幻想中成为原神

description: 其中一个问题是这样的：定义一个丘丘人是可以被击杀的，当且仅当存在一个大于 $1$ 的完全平方数能够整除它的编号。比如，$12$ 号丘丘人就是可以被击杀的，因为它能够被 $4$ 整除；$15$ 号丘丘人则不能被击杀。请计算编号为 $1\sim n$ 中的丘丘人中能够被击杀的个数。由于钟离秉承着“差不多得了”的做事理念，因此，他允许你的答案与真正的答案有着不超过 $2\times10^4$ 的绝对误差。

inputFormat:
**本题多组询问**。第一行输入一个数 $T$，表示询问组数。

每组询问输入一行，一个正整数 $n$。

outputFormat: 对于每组询问，输出一行一个整数，表示编号为 $1\sim n$ 中的丘丘人中能够被击杀的个数。

hint:
#### 样例解释

$1\sim 10$ 中，只有 $4,8,9$ 这 $3$ 个丘丘人可以被击杀，因此答案为 $3$。

需要注意的是，由于你的答案被允许与标准答案有 $2\times 10^4$ 的绝对误差，因此 $-2,3,20003$ 等输出都将被认为是正确的。

#### 数据范围

- $\text{Subtask 1(10 pts)}$：$n\le 10^5$。
- $\text{Subtask 2(20 pts)}$：$n\le 10^7$。
- $\text{Subtask 3(20 pts)}$：$n\le 10^9$。
- $\text{Subtask 4(20 pts)}$：$T=1$。
- $\text{Subtask 5(30 pts)}$：无特殊性质。

对于 $100\%$ 数据，满足 $1\le n\le 10^{18}$，$1\le T\le 10^4$，保证 $n$ 在范围内随机得到。


title: 无知时诋毁原神

background:
纳西妲很喜欢排列。

![](https://img2.huashi6.com/images/resource/thumbnail/2022/07/28/14225_32552389084.jpg?imageMogr2/quality/100/interlace/1/thumbnail/700x)

画师 pid：72405030

description: 纳西妲有一个 $0\sim n-1$ 的排列 $c$。她希望你构造两个同样为 $0\sim n-1$ 的排列的 $a,b$，满足 $\forall i\in[1,n],c_i=(a_i+b_i)\bmod n$。如果纳西妲的要求无法被满足，请输出 $-1$。

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

第二行，$n$ 个整数，表示排列 $c$。

outputFormat:
如果不存在满足要求的构造，输出一行 $-1$。

否则，输出两行，每行 $n$ 个整数，第一行为 $a_i$，第二行为 $b_i$。

hint:
### 数据范围

- $\text{Subtask 1(30 pts)}$：$n\le 10$。
- $\text{Subtask 2(20 pts)}$：保证有解。
- $\text{Subtask 3(50 pts)}$：无特殊性质。

对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，$c$ 构成一个排列。


title: 「JEOI-R1」棋

background:
| 出题 | 标程 | 数据 | 验题 | 题解 |
| -----------: | -----------: | -----------: | -----------: | -----------: |
 | [RedNebula](/user/478829) | [RedNebula](/user/478829) | [RedNebula](/user/478829) and [gyyyyx](/user/554574) | [gyyyyx](/user/554574) | [RedNebula](/user/478829) |

[RedNebula](/user/478829) 和 [_JF_](/user/361141) 在下一盘棋，然后……

description:
现在有一个 $n\times m$ 的棋盘，从上到下依次是 $1\sim n$ 行，从左到右依次是 $1\sim m$ 列，一个位于第 $x$ 行第 $y$ 列的位置被标记为 $(x,y)$。共有 $c$ 个棋子，**不重叠**地摆放在棋盘的某些位置上。一个位于 $(x,y)$ 的棋子可以走向 $(x-1,y-1),(x-1,y+1),(x+1,y-1),(x+1,y+1)$（如果这些位置**存在**且其上**没有棋子**）。

现有若干询问，每次询问给定 $x_1,y_1,x_2,y_2,p$，然后给定 $p$ 个位置，表示一个子矩阵的左上角位置为 $(x_1,y_1)$，右下角位置为 $(x_2,y_2)$，问是否可以移动棋子（无次数限制）使得矩阵内**有且仅有**给定的 $p$ 个位置上有棋子。**询问之间相互独立。**

为了减少程序时间复杂度的常数影响，**建议使用更快的读入方式。**

inputFormat:
第一行三个正整数 $n,m,c$，表示棋盘的列数、行数和已有的棋子数。

接下来 $c$ 行，一行两个整数 $a_i,b_i$，表示有一个棋子位于 $a_i$ 行 $b_i$ 列处。

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

接下来 $q$ 组询问。每一组询问第一行是五个正整数 $x_1,y_1,x_2,y_2,p$，接下来 $p$ 行每行两个正整数 $c_i,d_i$，表示只希望矩阵内有棋子的位置。

outputFormat: 对于每个询问，如果可以移动棋子（无次数限制）使得矩阵内有且仅有给定的位置上有棋子，输出 `YES`，否则输出 `NO`。

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

解释以 `0` 代表空位，`1` 代表放置了棋子的位置。

初始状态：

```plain
011
100
011
```

对于第一个询问，可以证明 $(1,2)$ 处的棋子无法移出 $(1,2)$ 到 $(2,3)$ 的矩阵。

对于第二个询问，考虑把 $(3,2)$ 处的棋子移到 $(2,3)$，得：

```plain
011
101
001
```

满足询问要求。移动方式不唯一。

对于第三个询问，可以证明 $(2,1)$ 处的棋子无法移出 $(1,1)$ 到 $(2,3)$ 的矩阵。

**【数据范围】**

对于 $25\%$ 的数据，$n,m,q\le 10$，$c\le 20$。

对于另外 $25\%$ 的数据，保证 $a_i+b_i\equiv 0 \pmod 2$，$c_i+d_i\equiv 0 \pmod 2$。

对于另外 $25\%$ 的数据，保证 $n\cdot m-c\le(x_2-x_1+1)\cdot (y_2-y_1+1)-p$。

对于 $100\%$ 的数据，$2\le n,m\le 10^5$，$1\le c,q\le 10^5$，$c\le n\cdot m$，$1\le a_i\le n$，$1\le b_i\le m$，$\sum p\le 2\times 10^5$。对于每个询问，$1\le p\le (x_2-x_1+1)\cdot (y_2-y_1+1)$，$x_1\le c_i\le x_2$，$y_1\le d_i\le y_2$。

**【提示与说明】**

提供一种较快的读入一个 `int` 类型非负整数的方式。调用下文中的 `read()`，其作用是返回输入中的一个非负整数，同时读取其后的一个字符。

```cpp
int read() {
  int x(0);
  char c(getchar());
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return x;
}
```


title: 懂事时理解原神

background:
胡桃喜欢用 dfs 求最短路，尽管这有可能会得到错误的答案。

![](https://img2.huashi6.com/images/resource/2021/03/01/8812956h7p1.jpg?imageMogr2/quality/100/interlace/1/thumbnail/700x)

画师 pid：6657532

description:
具体地，给定一个有 $n$ 个点和 $m$ 条边的无向无权图。则 dfs 求最短路的算法伪代码具体如下：

```
vis[], dis[]
dfs(u):
	vis[u] = 1
	记所有满足 u,v 之间有边且 !vis[v] 的点 v 构成的序列为 S
	以随机的顺序遍历 S:
		dis[v] = dis[u] + 1
		dfs(v)
solve():
	for i in [1, n]:
    	dis[i] = -1;
        vis[i] = 0
	dis[1] = 0
	dfs(1)
```

其中，```以随机的顺序遍历 S``` 可以被理解为随机打乱 $S$，得到每一种结果的概率均为 $\frac{1}{|S|!}$，并按照打乱后的顺序遍历。

现在，胡桃想要知道，如果她调用函数 ```solve()```，得到的最短路数组 ```dis[]``` 完全正确的概率有多大。```dis[]``` 被认为完全正确，当且仅当 $\forall i\in[1,n]$，```dis[i]``` 的值均等于从 $1$ 到 $i$ 的最短路长度（特别地，若 $1$ 无法走到 $i$，则认为 $1$ 到 $i$ 的最短路长度为 $-1$）。

inputFormat:
**本题多组询问。** 第一行输入一个数 $T$，表示询问组数。

对于每组询问：

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

第二行至第 $m+1$ 行，每行两个整数 $u,v$，表示 $u,v$ 之间有一条边。

outputFormat: 对于每组询问，输出一个实数，为 ```dis[]``` 数组完全正确的概率。**你需要输出答案保留三位小数（四舍五入）后的结果。**

hint:
- 对于 $20\%$ 的数据，$n,m\le 10$。
- 对于 $50\%$ 的数据，$n,m\le 1000$。
- 对于另外 $30\%$ 的数据，保证所给出的图为一仙人掌（任意一条边至多只出现在一条环上）。
- 对于 $100\%$ 的数据，$1\le n,m\le 50000，1\le T\le 10$，保证所输入的图无重边、自环。


title: 成熟时追随原神

background:
可莉喜欢生活在树上。

![](https://img2.huashi6.com/images/resource/2021/04/29/8945867h9p0.jpg?imageMogr2/quality/100/interlace/1/thumbnail/700x)

画师 pid：4787895

description:
可莉生活在一颗有根树上，初始节点从 $1$ 到 $n$ 编号。为了方便可莉的出行，蒙德人决定从每个非叶子节点出发，修建一条新道路。具体而言，对与每个非叶子节点 $u$，蒙德人会从其子节点中均匀随机选取一个点 $v$，并在 $u$ 和 $v$ 之间修建一条新道路。显然，这些新修建的道路连成了许多的连通块。为了帮助他们的修建，你需要告诉蒙德人，连通块个数的期望是多少。

可莉听说这个任务后，认为它对于你而言太简单了。因此，她决定添加一些对于树的修改操作：

- $\text{Add}\ u$：在节点 $u$ 下添加一子结点，编号为 $n+i$，其中 $i$ 为操作编号。保证操作前结点 $u$ 存在。
- $\text{Del}\ u$：删除结点 $u$。保证操作前结点 $u$ 存在且为叶子结点。
- $\text{Upd}\ u$：将树根变为 $u$。保证操作前结点 $u$ 存在。

同时，对于任意时刻，保证树不会被删空。

对于初始的树和每次修改之后所得的树，你都需要回答一遍上述的问题。注意，$m$ 次修改之间不独立，但是蒙德人每次修建的新道路不受上一次结果的影响。

inputFormat:
第一行，一个整数 $n$，表示初始树的大小。

第二行至第 $n$ 行，每行输入一个整数，第 $i$ 行将给出 $f_i$，即初始树中 $i$ 的父节点。初始时，节点 $1$ 为树根。

第 $n+1$ 行，一个整数 $m$，表示修改操作个数。

第 $n+2$ 行至第 $n+m+1$ 行，每行输入一个修改操作，形式见 **题目描述**。

outputFormat:
输出共 $m+1$ 行。

第 $1$ 行，为初始时的答案。

第 $2$ 行至第 $m+1$ 行，第 $i$ 行应输出第 $i-1$ 次修改操作后的答案。

所有输出均对 $998244353$ 取模。具体而言，如果答案为 $\frac{p}{q}$，你应当输出一个满足 $xq\equiv p\pmod {998244353}$ 的 $x$。

hint:
$$
\begin{array}{|c|c|c|c|}\hline
\textbf{测试点编号}& { n\le} & {m\le} & \textbf{特殊性质} \cr\hline
1\sim 3 & 5 & 5 & - \cr\hline
4\sim 7 & 1000 & 1000 &- \cr\hline
8\sim 10 & 10^5 & 0 & - \cr\hline
11\sim 13 & 10^5 & 2\times 10^5 & \textbf{AB}\cr\hline
14\sim 16 & 2\times 10^5 & 5\times 10^4 & \textbf{A} \cr\hline
17\sim 20 & 2\times 10^5 & 2\times 10^5 & - \cr\hline
\end{array}
$$

- 特殊性质 $\textbf{A}$：保证不存在 $\text{Upd}$ 操作。
- 特殊性质 $\textbf{B}$：保证不存在 $\text{Del}$ 操作。

对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5$。保证 $1\le f_i<i$。


title: 「CGOI-3」巫泡弹弹乐

background:
mc 正在挑战弹弹乐。

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

description:
弹弹乐由 $n$ 个弹力菇组成，每个弹力菇有 $a,b$ 两个属性。

对于弹力菇 $i$ 会向弹力菇 $j$ 连一条边权为 $\max(a_i,a_j)+\max(b_i,b_j)$ 的双向弹力通道。现在 mc 想知道弹力菇组成的图的最小生成树，以便他打破记录。

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

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

第三行 $n$ 个整数，第 $i$ 个数表示 $b_i$。

outputFormat:
第一行输出这个最小生成树的边权和。

接下来 $n-1$ 行，每行输出两个整数表示一条树边。你可以输出任意一种合法方案。

hint:
#### 数据范围

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

$$\def{\arraystretch}{1.5}\begin{array}{|c|c|c|c|}\hline
\textbf{Subtask} & \bm{n} & \textbf{特殊性质} & \textbf{分值}\cr\hline
1 & n\le 500 & \text{无} & 20 \cr\hline
2 & n\le 5\times 10^4 & \text{无} & 20\cr\hline
3 & \text{无特殊限制} & \text{数据随机} & 20\cr\hline
4 & \text{无特殊限制} & \text{无} & 40 \cr\hline
\end{array}$$

- 对于 $100\%$ 的数据，满足：$1\le n\le 10^6$，$1\le a_i,b_i\le 10^9$。


title: [DMOI-R1] 柯基棋

background: 小 A 和小 B 都是爱狗人士，且绝顶聪明，尤其喜爱柯基，于是他们发明了“柯基棋”。

description:
小 A 和小 B 在一个 $n \times n$ 的棋盘内轮流下棋。小 A 先手，小 B 后手。设当前有一只“柯基”被下在了棋盘的 $(x,y)$ 处，那么棋盘内的 $(x-1,y-1)$，$(x-1,y+1)$，$(x+1,y-1)$，$(x+1,y+1)$ 处都会变为这只“柯基”的地盘，也就不能再放一只“柯基”。当一个人不能再放下一只“柯基”时，他就输了。

可惜，小 C 却不怎么喜欢柯基，所以他很反对小 A 和小 B 玩“柯基”棋，于是他非常喜欢捣乱棋局。当小 A 和小 B 一共下了 $x_i$ 只“柯基”时，小 C 就会以当前 $w \times w$ 棋盘的中心为中心，扩大棋盘为 $(w+2) \times (w+2)$，他一共会捣乱 $q$ 次。

而你的任务是要判断这局棋是小 A 赢还是小 B 赢，如果小 A  赢，输出 `A won`，否则输出 `B won`。

由于他们两个人比较贪玩，所以他们一共会玩 $T$ 局。

**注意**：

1. 当小 A 和小 B 已经将原来的棋盘下到不能再下时，他们会直接跳转到小 C 下一次的捣乱（如果有）。

2. 小 A 和小 B 知道小 C 会捣乱，且会按照自己的最优策略走。

由于数据过大，$x_i$ 由数据随机生成器给出。

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

每组数据一行三个正整数 $n,q,seed$，其中 $seed$ 的作用见提示说明。

outputFormat: 共 $T$ 行，每一行输出一个字符串 `A won` 或 `B won`。

hint:
### 随机数据生成器

每一轮游戏的 $x_i$ 由下方的生成器给出：

```cpp
unsigned long long x[10000005];
unsigned long long xor_shift(unsigned long long &seed){
  return seed^=seed>>12, seed^=seed<<25, seed^=seed>>27, seed*0x2545F4914F6CDD1D;
}
int main(){
  //your code here
  int n,q;
  unsigned long long seed;
  cin>>n>>q>>seed;
  for(int i=1;i<=q;i++){
	x[i]=x[i-1]+((xor_shift(seed)%(unsigned long long)(2*2)+1))*2;
  }
  //your code here
  return 0;
}
```

### 样例解释

对于第一局游戏，$x_i$ 数组如下：`6 8 16 18 22`。

对于第二局游戏，$x_i$ 数组如下：`8 14 16 24 32 36 38 40`。

对于第三局游戏，$x_i$ 数组如下：`4 8 10 16`。

### 数据范围

对于 $20\%$ 的数据，$n,q\leq100$。

对于 $50\%$ 的数据，$n,q\leq10000$。

对于 $100\%$ 的数据，$1 \le T \le 10,2\leq n,q,\sum q \leq 10^7$，$x_i \equiv 0 \pmod 2\ (i\in[1,q]),0 \le seed \le 10^7$。


title: [NOI1997] 文件匹配

background:
**此为上古NOI原题，未证明有无靠谱的正解可以通过。**

在计算机的日常操作中，经常需要对当前回录下的所有文件中的一部分文件进行操作。例如，将当前目录下的所有文本文件复制至另一个目录下、将当前目录下所有以 `a` 打头的文件删除; 等等。

description:
很多操作系统都采用正则表达式来实现文件匹配功能。一种简单的正则表达式由英文字母（区分大小写）、数字及通配符 `*` 和 `?` 组成，`?` 代表任意一个字符，`*` 则可以代表零个或任意多个字符。

例如：
1. `a*b` 可以匹配 `acb` (`*` 代表 `c`)、`aabb` (`*` 代表 `ab`）、`asdsfdfdb` (`*` 代表 `sdsfdfd`)、`ab` (`*` 不代表任何字符)。
2. `a*b` 不可以匹配 `ac`（缺少最右边的字母 `b`)、`bb`（缺少最左边的字母 `a`)、  `abbc`（最右边的字母不是 `b`)。
3. `a?b` 可以匹配 `acb`（`?` 代表 `c`)。
4. `a?b` 不可以匹配 `ab`（缺少中间的一个字符）、`accb`（`?` 只能代表一个字符）。

现要对某目录下的部分文件进行操作。写一个程序,寻找一个正则表达式，使其能匹配的待操作文件最多，但不能匹配任何不进行操作的文件。注意你所找到的最优正则表达式的长度应当是**最短**的。

如果有多个长度最短的最优正则表达式，则其中任意一个都是允许的。

inputFormat:
由 $n$ 行组成，第一行一个整数 $n$ 表示字符串数量。

每行给出了一个字符串表示文件名（由英文字母和数字组成：英文字符区分大小写），其后是一个空格和一个字符（`+` 或 `-`）。

`+` 表示要对该行给出的文件进行操作，`-` 表示不进行操作。

outputFormat:
由两行组成。

第一行是一个整数，给出了你的程序所找到的最优正则表达式所能匹配的文件数目。

在第二行给出你的程序所找到的最优正则表达式。

samples:
5
EXCHANGE +
EXT +
HARDWARE +
MOUSE -
NETWORK -

samples:
5
EXCHANGE +
EXTRAS +
HARDWARE +
MOUSE -
NETWORK -

hint:
对于 $100\%$ 的数据：$1\le n\le 250，|S_i|\le8$。

为了便于调试和验证 Special Judge 的正确性，公布错误信息和对应的意思：

错误信息：
1. `The number of matching file name(s) is wrong!` 你输出的数量不是最多的。
2. `The expression is longer than jury's expression!` 你输出的表达式不是最短的。
3. `The expression matches an invalid file name!` 你输出的表达式匹配了不进行操作的文件。
4. `The answer is correct.` 你输出的表达式符合题目要求。
5. `The expression is shorter than jury's expression ???` 你输出的表达式符合题目要求，且比现有最优表达式短。
6. `The expression is better than jury's expression ???` 你输出的表达式符合题目要求，且匹配的文件数目比现有最优表达式多。
7. `The number of matching file name(s) is false!` 你输出的表达式匹配的数量比你输出的数量少。

如果你遇到了 5、6 的评测错误情况，请找搬题人或者管理员，我们将修正数据。

感谢Special Judge来源：[Sprague_Garundy](https://www.luogu.com.cn/user/764746)。

感谢 hack 数据提供：[oOoOoOOOooOO](https://www.luogu.com.cn/user/42324)，位于单独的Subtask，为0分，但是不通过视为不通过此题。


title: [JRKSJ R7] 魔改的第二分块

description:
给您一个长度为 $n$ 的序列 $a$，请您支持 $m$ 次操作：

1. 将 $[l,r]$ 区间中 $> x$ 的数减去 $x$。
2. 求 $[l,r]$ 区间中 $\le x$ 的数的个数。

inputFormat:
**本题强制在线。**

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

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

下面 $m$ 行，每行四个整数 $opt,l,r,x'$，$opt$ 表示操作编号，$x'$ 异或上次操作 $2$ 答案得到真实的 $x$。若此前没有操作 $2$，则不需要进行异或操作，真实的 $x$ 即为 $x'$。

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


title: 「DTOI-4」中位数

description:
给定一个长度为 $n$ 的整数序列 $a$，你可以进行以下操作不超过 $k$ 次：

- 选择一个区间 $[l, r]$ 满足 $1 \leq l \leq r \leq n$，并将 $[l, r]$ 中的所有数替换为这个区间的中位数。

你要使得操作后 $a$ 的**最小值最大**。

关于此处中位数的定义：对于一个长度为 $len$ 的序列，其中位数定义为该序列中第 $\lceil \frac{len}{2} \rceil$ 小的数。

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

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

outputFormat: 一行，表示经过不超过 $k$ 次操作后序列最小值的最大值。


title: [CCC2021 J3] Secret Instructions

description:
多组数据。

对于每组数据读入 $5$ 个数字字符。

- 如果前两个之和为奇数，输出 `left`；
- 如果前两个之和为非零偶数，输出 `right`；
- 如果前两个之和为零，输出 `left` 或 `right` 取决于上组数据。

然后输出一个空格与后三个数字字符。

inputFormat:
多组数据。

每行 $5$ 个数字字符。

读入直到 `99999`。

outputFormat: 每行一个字符串与 $3$ 个数字字符，空格隔开。

hint:
读入的第三个字符不会为 $0$。

第一组数据不会以 $00$ 开头。

译自 [CCC2021 J3](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/juniorEF.pdf)。


title: [CCC2021 J5/S2] Modern Art

description:
维护一个 $01$ 矩阵，初始矩阵全为 $0$。

每次操作会将一行或一列反转（$0$ 变成 $1$，$1$ 变成 $0$）。

输出最后有多少个 $1$。

inputFormat:
第一行 $M$，表示矩阵行数。

第二行 $N$，表示矩阵列数。

第三行 $K$，表示操作个数。

接下来 $K$ 行，每行一个字符与一个数字。字符为 `R` 则表示操作某一行，`C` 表示一列。数字表示哪一行或哪一列。

outputFormat: 一行一个数字，表示最终 $1$ 的个数。

hint:
样例解释：

```
011           01000
100           01000
100           10111
              10111
```

$$M\times N\leq 5000000,K\leq 1000000$$

译自 [CCC2021 J5/S2](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/juniorEF.pdf)。


title: [CCC2021 S1] Crazy Fencing

description:
栅栏由 $N$ 块木板组成。

因为是栅栏，所以第 $i$ 块的右边界与第 $i+1$ 块的左边界的高度一样。

告诉你这些木板的边界的高度与这些木板的宽度，输出这些木板的总面积。

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

第二行 $N+1$ 个整数，表示每个边界的高度。

第三行 $N$ 个整数，表示每块木板的宽度。

outputFormat: 一行一个保留一位小数的实数，总面积。

hint:
样例解释：

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

$N\leq 10000$，高度和宽度 $\leq 100$。

译自 [CCC2021 S2](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/seniorEF.pdf)。


title: [DMOI-R1] 实验基地

background: 小 A 和小 B 用实验基地全新的装备进行了一场世纪蒟蒻之战。

description:
众所周知，实验基地的武器都是一次性的。现在，小 A 选取了 $n$ 把不同的武器，小 B 也获取了 $m$ 把不同武器。每个人的武器都可以用编号 $1$ 到编号 $n$ 或 $m$ 依次表示，他们将会按此顺序逐个使用武器。

实验仓库记录了所有武器的火力。小 A 的第 $k$ 把武器能爆发出 $a_k$ 的能量，而小 B 的第 $k$ 把武器能爆发出 $b_k$ 的能量。特别的，当小 A 的第 $i$ 把武器与小 B 的第 $j$ 把武器同时使用，会释放 $d_{i,j}$ 的能量。由于某些不可描述的组合的奇效，$a,b,d$ **都可能小于** $0$。

当某人第一个使用了武器，战斗就正式开始，记为第 $1$ 秒，直至某人使用完武器后再无人使用武器,记此时为第 $t$ 秒（$t$ **不为输入数据**）。也就是说，**在第 $1$ 秒和第 $t$ 秒必须有人使用武器，而在 $1$ 至 $t$ 秒内在符合其他条件下，每一秒双方可以选择按顺序使用武器或不使用**。

为了避免打死对方，**双方都不一定使用完武器**。

由于实验基地有发电装置，如果小 A 没有连续使用武器释放能量，而是休息了 $x$ 秒，那么祂将会吸收掉  $Ax+B\ (A,B \in \mathbb{N})$ 的能量。同样，小 B 间隔 $y$ 秒将吸收 $Cy+D\ (C,D \in \mathbb{N})$ 的能量。连续两秒都释放武器间隔时间为 $0$ 秒，以此类推。

为了防止基地被核爆，你需要算出战斗结束后可能释放的最大总能量（可能为负数）。

**若对题目细节有疑惑请先读提示内的额外解释。**

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

第二行有 $n$ 个数，第 $k$ 个数字即 $a_k$。

第三行有 $m$ 个数，第 $k$ 个数字即 $b_k$。

接下来 $n$ 行，每行 $m$ 个数字，其中第 $i$ 行第 $j$ 列表示的是 $d_{i,j}$。

最后一行有四个非负整数 $A,B,C,D$。

outputFormat: 只有一行，输出一个数字，即最大可能能量。

hint:
1. 战斗的开始时间（第 $1$ 秒）为双方某人最先释放出第一个技能的时间，战斗结束时间为双方某人释放出最后一个技能的时间。**结束时间不定**。

2. 技能必须按顺序释放，但**不一定需要在战斗中释放完**。

3. $a,b,d$ 可以为负数，总计能量可能为负，“吸收能量”指总能量减少 $Ax+B$ 或 $Cy+D$，也就是**间隔时总能量一定减少**，而且时间越长减少越多。

4. 本题 IO 量较大，建议使用合适的读入方式。

### 样例解释：

样例 1：每个人在 $1$ 到 $6$ 秒依次使用自己的编号为 $1$ 到 $6$  的武器即可取到最大值。

样例 2：小 B 在 $1$ 到 $4$ 秒依次使用自己的编号为 $1$ 到 $4$ 的武器，小 A 在第 $4$ 秒使用自己的 $1$ 号武器可以取到最大值。其中单个武器释放的能量为 $(-2)+(2+3+4+9) = 16$，武器碰撞释放 $d_{1,4} = 4$ 单位的能量，小 A 在前 $3$ 秒吸收了 $A \times 3 + B = 5$ 单位的能量。

### 数据范围：

|Subtask|$n\leq$|$m\leq$|分值|
|-|-|-|-|
|$1$|$10$|$10$|$20$|
|$2$|$500$|$500$|$30$|
|$3$|$3000$|$3000$|$50$|

**本题采用捆绑测试**，您只有通过了一个 Subtask 中的所有测试点才能得到这个 Subtask 的分数。

对于 $100\%$ 的数据：$0 \le |a_k|,|b_k|,|d_{i,j}|,A,B,C,D \leq 1000$, $1\leq n, m\leq 3000$。


title: [CCC2021 S3] Lunch Concert

description:
有 $N$ 个人，第 $i$ 个人的速度为 $W_i$ **秒每米**，听力为 $D_i$，即能听见距离他不超过 $D_i$ 米处的音乐，初始在 $P_i$ 位置。

你要在 $c$ 位置处开音乐会，这个 $c$ 由你决定且为整数。这 $N$ 个人都会靠近你直到能听到你。你要最小化每个人移动的时间之和。

inputFormat:
第一行：$N$。

接下来的 $N$ 行，每行依次包含 $P_i,W_i,D_i$。

outputFormat: 一个整数：每个人移动的时间之和的最小值。（注意：答案可能超过 $2^{32}$）

hint:
$$1\leq N\leq 200000,0\leq P_i\leq 10^9,1\leq W_i\leq 1000,0\leq D_i\leq 10^9$$

译自 [CCC2021 S3](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/seniorEF.pdf)。

###### 2023.8.10 新增一组 hack 数据。


title: 「TAOI-1」椎名真昼

background: **请注意赛后题目添加了多测。因此请将您的赛时代码进行修改后再提交。**

description:
你正在看轻小说，突然你的家长走了进来，于是你假装在写 OI 题目。

Alice 和 Bob 正在玩一款游戏，给定一个有向图，每个点初始有一个颜色（黑或白）。

双方轮流进行操作，Alice 先手，每次操作选定一个节点，将所有从该点开始，能到达的点（包括自身）颜色翻转。如果某次操作后所有节点都变为白色，则进行该次操作的人胜利。

假如双方都采用最优策略使得自己胜利，或者如果自己无法胜利，使得对方无法胜利。

给你节点的初始状态，请你求出最终的胜者，亦或者，没有胜者。

---

定义点 $u$ 能到达点 $v$，当且仅当存在数列 $(a_1,a_2,a_3,\cdots,a_k)$，其中 $k \ge 1$，使得 $\forall i \in [1,k)$，存在有向边 $a_i \to a_{i+1}$，且 $a_1=u$，$a_k=v$。

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

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

对于每组测试数据：

第一行两个整数 $n, m$，代表图的点数，边数。

第二行 $n$ 个整数，代表每个点开始时的颜色。$1$ 代表黑色，$0$ 代表白色。

接下来 $m$ 行，每行两个整数 $u, v$ 代表一条从 $u \to v$ 的边。

outputFormat:
对于每组测试数据：

如果最后 Alice 胜利，输出 `A`。

如果最后 Bob 胜利，输出 `B`。

如果双方（在对方的阻止下）都无法胜利，输出 `N`。

您无需输出空格或换行符。

hint:
### 数据范围

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

- Subtask 1（5 points）：$n \leq 2$，$m \leq 1$，$T=1$。
- Subtask 2（15 points）：$n \leq 5$，$m \leq 8$，$T=1$。
- Subtask 3（25 points）：保证所有点的初始颜色相同。
- Subtask 4（55 points）：无特殊限制。

对于所有测试数据，$1 \leq n \leq 10^5$，$1 \leq m \leq 2 \times 10^5$，$1 \le T \le 15$。

### 样例解释

在第一组数据中，Alice 可以先手对节点 $1$ 进行操作。操作后所有节点变为白色。

在第二组数据中，双方都没有必胜的方法，因此双方会互相拖延对方阻止对方获胜。

---

「据说如果无论如何都输出 `N` 的话，有 $45\%$ 的几率能够得到正确答案？」

「怎么可能，不会真的有人造出这么蠢的数据吧……」


title: 「KDOI-04」Again Counting Set

description:
小 S 不喜欢集合，不喜欢自然数，不喜欢求和，不喜欢求积，不喜欢最小值，不喜欢最大值，不喜欢 $\operatorname{mex}$，所以有了这题。

给出 $n,k$，求有多少个可重**整数**集合 $S$ 满足：

* $|S|=k$；
* 对于任意 $x\in S$，$0\le x\le n$；
* $\displaystyle{\prod_{x\in S} x=\min_{x\in S} x}$；
* $\displaystyle{\sum_{x\in S} x=\min_{x\in S} x+\max_{x\in S}x+{\operatorname{mex}}(S)}$。

**注： $\bf{mex}$ 指集合中没有出现过的最小的自然数。**

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

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

对于每组测试数据，输入包含一行两个正整数 $n,k$。

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


title: [CCC2021 S4] Daily Commute

description:
已知有 $N$ 个地铁站，你家在 $1$，学校在 $N$。

有 $W$ 条单向人行道。经过需要一分钟。

此外还有一条环形地铁线路，依次经过 $S_1,S_2,\cdots,S_N$，且保证 $S_1=1$。每天**有且仅有**一辆地铁在 $0$ 时刻从 $S_1$ 出发，并且恰好在第 $i$ 分钟到达 $S_i$。

在接下来 $D$ 天中：

- 交换 $S_{X_i}$ 和 $S_{Y_i}$。注意修改是永久的。
- 查询从 $1$ 到 $N$ 的最短用时。你出发时地铁在 $1$。

inputFormat:
第一行：$N,W,D$。

接下来 $W$ 行：$A_i,B_i$ 表示单向人行道。

接下来一行 $N$ 个数：$S$。

接下来 $D$ 行：$X_i,Y_i$，保证 $2\leq X_i,Y_i\leq N,X_i\neq Y_i$。

outputFormat: $D$ 行，每天的答案。

hint:
$$3\leq N\leq 200000,0\leq W\leq 200000,1\leq D\leq 200000$$

译自 [CCC2021 S4](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/seniorEF.pdf)。

请注意常数。


title: [CCC2021 S5]  Math Homework

description:
构造一个长度为 $N$ 的整数序列 $A$，使得：

1. $\forall i,1\leq A_i\leq 10^9$；
2. $\forall i,\gcd(A_{X_i},A_{X_i+1},\cdots,A_{Y_i})=Z_i$。

或者报告无解。

inputFormat:
第一行，$N,M$。

接下来 $M$ 行，每行有 $X_i,Y_i,Z_i$，描述一个限制 2.

outputFormat: 一行，序列 $A$，或者 `Impossible`。

hint:
$$1\leq N\leq 150000,1\leq M\leq 150000,1\leq Z_i\leq 16$$

译自 [CCC2021 S5](https://cemc.math.uwaterloo.ca/contests/computing/past_ccc_contests/2021/ccc/seniorEF.pdf)。

spj 在附件里，发现锅了请联系[我](/user/90693)。


title: [DMOI-R1] Portal

background:
出题人正在玩一款叫 Portal 的游戏。但由于他太菜了，于是找来了你，让你帮他过几个他过不去的关卡。

什么？你说你不会玩？

玩家需要通过传送门枪到达出口。利用传送门枪射击可开出两种门，分别是橙色门和蓝色门，两面都可作入口及出口。在创造门的时候，另一道同样颜色的门会消失，即是说同时间不可能存在两道同色的门，最多只可同时存在一道蓝色及一道橙色的门。

两道传送门在三维空间之中的两个地点创造出视觉上及物理上的连系，传送门的立点只限于平面，玩家从门出来时会自动配合地心吸力调整身体水平。

出题人把所有希望都寄托于你身上了哟。哦，对了，因为出题人是个白嫖党，因此他拥有的是盗版 Portal。

description:
在一个 $n \times n$ 的二维平面图上，用 $(x,y)$ 表示地图第 $x$ 行第 $y$ 列。每个点都是墙、虚空和地面中的一种，分别用 `#`，`*`，`.` 表示。玩家只能站在地面上。**地图之外都是墙。**

你手里有一个传送门枪，可以发射蓝色和橙色的传送门，只能朝上下左右四个方向使用。

在选定一个方向和颜色后，将会在该方向上第一个碰到的墙的墙面上建造选定颜色的传送门，并摧毁之前建造的这种颜色的传送门。两种颜色的传送门不能被建立在同一墙面。

玩家可以朝上下左右四个方向的空地移动。玩家还可以在不同色传送门之间穿梭。假如玩家朝一堵墙移动并且墙面上有传送门，并且当前已经建立了两个传送门，那么会从另一个传送门出来（必须保证出来也站在陆地上）。

出来的时候，玩家会站在另一个门外的空地上，**四个方向都可以。**

一开始玩家站在 $(1,1)$，目的地是 $(n,n)$。求最少使用多少次传送门枪才能到达目的地。

**注意哦，这里的使用指的是穿过多少面传送门。**

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

每组数据第一行一个正整数 $n$ 表示平面图的行数和列数。

接下来 $n$ 行每行 $n$ 个字符只包含 `#`，`*`，`.` 三种字符表示地图。

outputFormat: 对于每组数据输出一个数表示最少需要使用传送门枪的次数。无法到达输出 `-1`。如果起点或终点不为陆地，那么直接结束程序。

hint:
### 样例1解释

我们用白色格子表示空地，黑色格子表示墙，蓝色格子表示蓝色传送门，橙色格子表示橙色传送门，可以画出第一局的如下地图：

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

走到橙色传送门处，从橙色传送门进入，蓝色传送门出即可。

而第二局地图如下：

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

走到蓝色传送门处，从蓝色传送门进入，橙色传送门出即可。

### 数据范围

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

对于 $60\%$ 的数据，$n \le 100$。

对于另外 $10\%$ 的数据，$T=1$ 且不存在虚空。

对于 $100\%$ 的数据，$2 \le n \le 500$，$1 \le T \le 10$。


title: 「TAOI-1」拼凑的断音

background:
> flick tap flick tap 面を滑って \
> swipe tap swipe tap 「A.R→T」\
> flick tap flick tap 開いて叩いて \
> swipe swipe swipe swipe …もう嫌だな \
> ズルズル 糸が呟く

description:
你的面前有 $n$ 个音符，它们的动听程度由数列 $\{a_n\}$ 描述。

现在有 $n$ 种魔法，第 $i$ 种魔法会让 $a_i$ 增加 $s(s \gt 0)$。每种魔法的成功几率都为 $\dfrac{p}{q}$，并且彼此独立。

求在施加魔法情况下，最终最动听的音符的动听程度（即，$\max\limits_{i=1}^n a_i$）的期望。

**本题目有 Special Judge，你可以用两种不同的方式输出答案，具体见【输出格式】处**。

inputFormat:
第一行为四个整数 $n, p, q, s$。

第二行为 $n$ 个整数 $a_i$，由空格隔开。

outputFormat:
**本题有两种不同的输出格式**。

- 第一种输出格式：

  请在第一行输出 `1`。

  接着，在第二行输出所求的期望，它应当是一个实数。

  如果您的答案与标准答案相差不超过 $10^{-4}$，则判定为正确。但由于众所周知的浮点数的误差，不保证评测结果百分百准确。如果您确信自己的程序正确但无法 AC，可以尝试使用第二种输出方式。

- 第二种输出格式：

  请在第一行输出 `2`。

  接下来，若你求出的期望是 $\dfrac{m}{n}$（显然期望为一个有理数），则请在第二行输出它对 $998244353$ 取模的结果，即一个 $[0, 998244353)$ 的整数 $x$，使得 $xn \equiv m \pmod {998244353}$。

hint:
### 数据范围

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

- Subtask 1（20 points）：$n \leq 15$。
- Subtask 2（15 points）：保证 $\forall i \in [1, n), a_i \leq a_{i+1}$，$a_n \geq a_{n-1}+s$。
- Subtask 3（15 points）：保证 $\forall i,j\in[1,n], a_i = a_j$。
- Subtask 4（50 points）：无特殊限制。

对于所有测试数据，$1 \leq n \leq 10^5$，$1 \leq p \lt q \leq 10^7$，$1 \leq a_i,s \leq 10^7$。

### 样例解释

注意到两个样例的输入相同，区别仅在于输出格式不同。

以下列举了所有可能的魔法施加情况和其对应的最大值以及出现概率：

| 魔法情况 | 动听度最大值 | 出现概率 | 对期望的贡献 |
| :------: | :----------: | :------: | :----------: |
|${\color{black}1},{\color{black}2},{\color{black}3}$|$3$|$\dfrac{8}{27}$|$\dfrac{8}{9}$|
|${\color{red}3},{\color{black}2},{\color{black}3}$|$3$|$\dfrac{4}{27}$|$\dfrac{4}{9}$|
|${\color{black}1},{\color{red}4},{\color{black}3}$|$4$|$\dfrac{4}{27}$|$\dfrac{16}{27}$|
|${\color{black}1},{\color{black}2},{\color{red}5}$|$5$|$\dfrac{4}{27}$|$\dfrac{20}{27}$|
|${\color{red}3},{\color{red}4},{\color{black}3}$|$4$|$\dfrac{2}{27}$|$\dfrac{8}{27}$|
|${\color{red}3},{\color{black}2},{\color{red}5}$|$5$|$\dfrac{2}{27}$|$\dfrac{10}{27}$|
|${\color{black}1},{\color{red}4},{\color{red}5}$|$5$|$\dfrac{2}{27}$|$\dfrac{10}{27}$|
|${\color{red}3},{\color{red}4},{\color{red}5}$|$5$|$\dfrac{1}{27}$|$\dfrac{5}{27}$|

可得，最终的答案为 $\dfrac{35}{9}$。

+ 若使用第一种输出方式，它的值约为 $3.888889$。
+ 若使用第二种输出方式，可以发现 $554580200 \times 9 \equiv 35 \pmod {998244353}$。


title: [COCI2022-2023#1] Desni klik

background: NFP 即未来！当谈到金融话题时，Noa 的朋友们都希望听到他说这句话。

description:
NFP 是一种加密货币。一枚 NFP 在 $s$ 天内的价值可以用一个仅包含字符``.``与``#``的 $r$ 行 $s$ 列字符矩阵表示。第 $i$ 列中自底向上第 $j$ 行的``#``表示第 $i$ 天该 NFP 的价值为 $j$。

NFP 的“不安全度”定义为在 $s$ 天之内其价值到达的最大值与最小值之差。

```
....##.
#..#...
.##....
......#
```
如上，这枚 NFP 在 $7$ 天内的价值依次为：$3,2,2,3,4,4,1$。它的“不安全度”是3。

现在 Noa 想让你帮他确定他手中 $n$ 枚 NFP 的不安全度。

inputFormat:
第一行包含三个整数 $n,r,s$，分别表示 NFP 的数量，矩阵的行数和列数。

接下来 $n$ 个 $r$ 行 $s$ 列的矩阵，描述每枚 NFP 的在 $s$ 天内的价值。

保证每枚 NFP 的价值矩阵的每一列都包含且仅包含一个字符``#``。

outputFormat: 输出 $n$ 行，表示每枚 NFP 的不安全度。


title: [COCI2022-2023#1]  Čokolade

background: Lana 和 Fran 正在参观一家巧克力工厂，现在他们想买些巧克力。

description:
巧克力工厂里有 $n$ 块不同的巧克力，其中第 $i$ 块的价格为 $c_i$。Lana 和 Fran 想买 $m$ 块巧克力。

Fran 有一个消费方案：

•如果巧克力价格低于 $k$ 元，这块巧克力的费用将全部由 Lana 支付。

•否则，Lana 将支付 $k$ 元，而 Fran 将支付其余的部分，即 $c_i−k$ 元。

Lana 对 Fran 的方案不满意，想要报复 Fran。设 $l$ 为 Lana 需要支付的金额，$f$ 为 Fran 需要支付的金额。Lana 将选择使 $l−f$ 的值最小的购买方案。

由于 Fran 还在犹豫，不知道要买多少巧克力，所以 Lana 想知道对于给出的 $q$ 种不同的购买方案 $k_i$ 和 $m_i$，每种方案 $l−f$ 的最小值。

inputFormat:
第一行包含两个整数 $n$ 和 $q$，分别表示巧克力的数量和询问数量。

第二行包含 $n$ 个整数 $c_i$，依次表示每块巧克力的价格。

接下来 $q$ 行，每行包含两个整数 $k_i$ 和 $m_i$，分别表示 Fran 的付款阈值和购买的巧克力总数量。

outputFormat: 输出 $q$ 行，每行一个整数表示 Lana 询问的答案。