title: [JOISC2022] 错误拼写

background: JOISC2022 D1T3

description:
从前，K 总统有着一个长度为 $N$ 的字符串 $S$，仅由小写字母组成。然而，他忘记了它。
他还有一个词典，其中包含了各式各样的错误拼写。而他曾看过那本词典，现在他确认到 $S$ 满足以下条件：

- 令 $T_i$ $(1\le i\le N)$ 为 $S$ 删去第 $i$ 个字符并将前后字符相接所得的字符串。对于每个 $j$ $(1\le j\le M)$ 满足 $T_{A_j} \le T_{B_j}$。

其中 $T_{A_j} \le T_{B_j}$ 表示 $T_{A_j}$ 等于 $T_{B_j}$ 或 $T_{A_j}$ 在字典序上小于 $T_{B_j}$。

请写一个程序，对于 K 总统给定的如上关于 $S$ 的信息，输出可能的 $S$ 的个数，对 $10^9+7$ 取模。

inputFormat:
第一行，两个正整数 $N,M$，表示 $S$ 的长度与限制的个数。

以下 $M$ 行，其中第 $j$ $(1 \le j \le M)$ 行包含两个正整数 $A_j, B_j$，表示一条限制。

outputFormat: 一行一个非负整数，表示可能的 $S$ 的个数对 $10^9+7$ 取模的结果。

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

举例说明，若 $S=\texttt{bab}$，则 $T_1 = \texttt{ab}, T_2 = \texttt{bb}, T_3 = \texttt{ba}$。其满足 $T_1 \le T_3$ 和 $T_3 \le T_2$。所以该 $S$ 是合法的。
可以证明，总共有 $5876$ 种合法的 $S$。因此，输出 $5876$。

另一方面，若 $S=\texttt{aab}$，则 $T_1 = \texttt{ab}, T_2 = \texttt{ab}, T_3 = \texttt{aa}$。其不满足 $T_1 \le T_3$。所以该 $S$ 不合法。

该样例满足所有子任务的限制。

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

该样例满足子任务 $1,2,4,5$ 的限制。

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

取模前的结果为 $824\,206\,295\,601$，所以输出 $206\,289\,833$。

该样例满足子任务 $1,2,4,5$ 的限制。

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

该样例满足所有子任务的限制。

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

该样例满足所有子任务的限制。

**【数据范围】**

对于所有数据，满足：

- $2 \le N \le 500\,000$。
- $1 \le M \le 500\,000$。
- $1 \le A_j,B_j \le N$ $(1 \le j \le M)$。
- $A_j\ne B_j$ $(1 \le j \le M)$。
- $(A_j,B_j)\ne(A_k,B_k)$ $(1 \le j < k \le M)$。

详细子任务附加限制及分值如下表所示：

|子任务编号|附加限制|分值|
|:-:|:-:|:-:|
|$1$|$N \le 10$|$8$|
|$2$|$N \le 200$|$20$|
|$3$|存在 $\{1,2,\dots,N\}$ 的排列 $P$ 满足 $A_j = P_j, B_j = P_{j+1}$ $(1 \le j \le M=N-1)$|$29$|
|$4$|$N \le 20\,000$|$32$|
|$5$|无附加限制|$11$|


title: [JOISC2022] 复制粘贴 3

type: P

background: JOISC2022 D2T1

description:
JOI 公司是一家以“没啥用发明”而闻名的公司。最近，JOI 公司开发了一款名为“没啥用编辑器”的编辑器。

在这个编辑器中，可以执行如下几种操作来输入某个字符串，设 $X$ 为屏幕上的字符串，$Y$ 为剪切板中的字符串，初始均为空串：

- 操作 A：输入字符 $c$，即将 $X$ 更新为 $X+c$。
- 操作 B：选择所有字符并剪切，即将 $Y$ 更新为 $X$，并将 $X$ 置为空串。
- 操作 C：将剪切板中的字符串粘贴到当前字符串末尾，即将 $X$ 更新为 $X+Y$。

对于字符串或字符 $x,y$，$x+y$ 表示将 $x$ 和 $y$ 顺次拼接得到的结果。使用一次操作 A,B,C 分别要花费 $A,B,C$ 单位时间。

你安装了“没啥用编辑器”，并想要尽可能快地输入一个长度为 $N$ 的字符串 $S$。

你需要计算出最少需要花费多少时间。

inputFormat:
第一行一个整数 $N$ 表示字符串长度。

第二行一个长度为 $N$ 的字符串 $S$ 表示要输入的字符串。

第三行一个整数 $A$ 表示操作 A 的代价。

第四行一个整数 $B$ 表示操作 B 的代价。

第五行一个整数 $C$ 表示操作 C 的代价。

outputFormat: 一行一个整数表示输入字符串 $S$ 最少要多少单位时间。


title: [JOISC2022] 团队竞技

background: JOISC2022 D2T3

description:
JOI 大学有 $N$ 只海狸，他们都参与竞技编程。每只海狸有三项能力值：思考值，行动值和运气值。如果一个能力值很大，意味着他这项能力比较强大。对于第 $i~(i\in[1,N])$ 只海狸，他的思考值为 $X_i$，行动值为 $Y_i$，运气值为 $Z_i$。

今年 JOI 大学的海狸们将参与一场团体竞技编程，一支队伍由三名队员组成。Bitaro 是 JOI 大学的教练，由于团队合作很重要，Bitaro 决定从 $N$ 只海狸中选出三只海狸组成队伍，这三只海狸要满足以下条件：

**条件**：每个成员都有自己的优势，这意味着每个成员都有一项能力值严格大于其他两人的对应能力值。

在所有符合条件的组队中，Bitaro 想要选一个总能力最强的队伍，一个队伍的总能力定义为：三人最大思考值，三人最大行动值和三人最大运气值之和。

请你求出，是否存在一个符合条件的组队，如果是，计算队伍总能力可能的最大值。

inputFormat:
第一行一个整数 $N$ 表示海狸数。

接下来 $N$ 行每行三个整数 $X_i,Y_i,Z_i$ 表示海狸的各项能力值。

outputFormat: 一行一个整数，如果不存在符合条件的组队，输出 `-1`，否则输出队伍总能力的最大值。

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

由海狸 $1,4,5$ 组成的队伍符合条件，因为：

1. 海狸 $1$ 的优势是运气。
2. 海狸 $4$ 的优势是行动。
3. 海狸 $5$ 的优势是思考。

总能力值为：$5+4+4=13$。

可以证明这是符合条件的组队中，总能力值最高的队伍。

注意如果选择海狸 $1,3,5$，总能力值将达到 $15$，但是这会导致海狸 $1$ 没有特长。

这组样例满足所有子任务的限制。

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

最优组队为：海狸 $2,3,4$。

这组样例满足所有子任务的限制。

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

任何组队方式都会导致队员没有特长，不存在符合条件的组队。

这组样例满足所有子任务的限制。

**【数据范围】**

对于所有数据，满足：

- $3\leq N\leq 150000$。
- $1\leq X_i,Y_i,Z_i\leq 10^8$ $(1\leq i\leq N)$。

详细子任务附加限制及分值如下表所示：

|子任务编号|附加限制|分值|
|:-:|:-:|:-:|
|$1$|$N\leq 300$|$8$|
|$2$|$N\leq 4000$|$29$|
|$3$|$X_i,Y_i,Z_i\leq 5$ $(i\in[1,N])$|$9$|
|$4$|$X_i,Y_i,Z_i\leq 20$ $(i\in[1,N])$|$9$|
|$5$|$X_i,Y_i,Z_i\leq 300$ $(i\in[1,N])$|$9$|
|$6$|$X_i,Y_i,Z_i\leq 4000$ $(i\in[1,N])$|$9$|
|$7$|无附加限制|$27$|


title: [JOISC2022] 洒水器

background: JOISC2022 D3T2

description:
JOI 君有多年在自家菜园种植蔬菜的经验，现在他计划管理 IOI 农场。

IOI 农场由 $N$ 块土地组成。土地间有 $N-1$ 条双向道路相连，编号从 $1$ 到 $N-1$，第 $i$ 条道路连接土地 $A_i$ 和 $B_i$，任意两块土地间都可以通过道路互达。农场的每块土地上都有一个洒水器，使用洒水器可以向附近的土地洒水。

JOI 君计划在 IOI 农场种植 JOI 谷。JOI 谷是一种奇特的作物，它在被浇水时高度会立刻发生变化。但是同时，JOI 谷是一种脆弱的植物，若它的高度大于等于 $L$，JOI 谷顶部长为 $L$ 的部分会立刻断裂并掉落。JOI 君会收获掉落的部分。

初始时，JOI 君在土地 $j$ 上种了一株高度为 $H_j$ 的 JOI 谷，之后的 $Q$ 天，JOI 君都会照料这些 JOI 谷，在第 $k$ 天，JOI 君会做如下两个操作之一：

- 操作 $1$：JOI 君使用土地 $X_k$ 上的洒水器，向与土地 $X_k$ 距离不超过 $D_k$ 的土地上浇水，使这些土地上的 JOI 谷高度乘以 $W_k$。由于 JOI 谷会不断断裂，因此若对一株原高度为 $h$ 的 JOI 谷洒水，它的高度会变为 $hW_k\bmod L$。
- 操作 $2$：JOI 君测量土地 $X_k$ 上 JOI 谷的高度。

土地 $x$ 和土地 $y$ 间距离的定义为：从土地 $x$ 前往土地 $y$ 经过道路数的最小值。

JOI 君希望 JOI 谷按照计划长大，因此，他希望提前算出每次操作 $2$ 应当测量出 JOI 谷的高度。

inputFormat:
第一行两个整数 $N,L$，表示土地块数和 JOI 谷的断裂阈值。

接下来 $N-1$ 行，每行两个整数 $A_i,B_i$ 表示一条道路。

接下来 $N$ 行，每行一个整数 $H_i$ 表示 JOI 谷的初始高度。

接下来一行一个整数 $Q$ 表示操作次数。

接下来 $Q$ 行，第 $k$ 行以 $T_k$ 开头，表示这次操作类型，接下来：

- 若 $T_k=1$，这是一次操作 $1$，接下来三个整数 $X_k,D_k,W_k$ 分别表示洒水器编号，洒水半径和生长参数。
- 若 $T_k=2$，这是一次操作 $2$，接下来一个整数 $X_k$ 表示需要测量的 JOI 谷的编号。

outputFormat: 对于每一次操作 $2$，输出一个整数表示 JOI 谷的预期高度。

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

初始时，JOI 君在所有土地上种植了高度为 $1$ 的 JOI 谷。

第一天，JOI 君使用土地 $2$ 的洒水器，土地 $1,2,3$ 的 JOI 谷被影响，高度乘以 $2$，四株 JOI 谷的高度变为 $2,2,2,1$。

第二天，JOI 君使用土地 $1$ 的洒水器，土地 $1$ 的 JOI 谷被影响，高度乘以 $2$，四株 JOI 谷的高度变为 $4,2,2,1$。

第七天，JOI 君使用土地 $4$ 的洒水器，土地 $1,2,3,4$ 的 JOI 谷被影响，高度乘以 $2$，第一株 JOI 谷的高度变为 $8$，发生断裂，因此四株 JOI 谷的高度变为 $1,4,4,2$。

这组样例满足子任务 $1,5,6$ 的限制。

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

第一天，JOI 君使用土地 $5$ 的洒水器，土地 $5,6$ 上的 JOI 谷高度乘以 $7$，高度分别变为 $63,7$，因此，土地 $5$ 上的 JOI 谷会不断断裂，高度变为 $3$。

这组样例满足子任务 $1,2,3,6$ 的限制。

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

这组样例满足子任务 $1,3,4,6$ 的限制。

**【数据范围】**

对于所有数据，满足：

- $2\leq N\leq 200000$。
- $2\leq L\leq 10^9$。
- $1\leq A_i\lt B_i\leq N$ $(i\in[1,N-1])$。
- 任意土地之间都可以通过若干条道路到达。
- $0\leq H_j\lt L$ $(1\leq j\leq N)$。
- $1\leq Q\leq 400000$。
- $T_k$ 均为 $1$ 或 $2$。
- 对于满足 $T_k=1$ $(k\in[1, Q])$ 的 $k$，保证 $1\leq X_k\leq N, 0\leq D_k\leq 40, 0\leq W_k\lt L$。
- 对于满足 $T_k=2$ $(k\in[1, Q])$ 的 $k$，保证 $1\leq X_k\leq N$。

详细子任务附加限制及分值如下表所示：

|子任务编号|附加限制|分值|
|:-:|:-:|:-:|
|$1$|$N,Q\le 1000$|$3$|
|$2$|对于满足 $T_k=1$ 的 $k$，保证 $D_k\leq 1$|$9$|
|$3$|对于满足 $T_k=1$ 的 $k$，保证 $D_k\leq 2$|$29$|
|$4$|对于满足 $T_k=1$ 的 $k$，保证 $W_k=0$|$12$|
|$5$|对于满足 $T_k=1$ 的 $k$，保证 $W_k=2$|$30$|
|$6$|无附加限制|$17$|


title: [JOISC2022] 蚂蚁与方糖

background: JOISC2022 D3T3

description:
JOI 君是一个生物学家。他准备对蚂蚁和方糖做一些实验。

JOI 君的实验在一个长度为 $10^9$ 的木条上进行。这根木条被从左往右放置。木条上距离左端点 $x$ 的点被称作坐标为 $x$ 的点。

现在，木条上什么都没有。JOI 君将会进行 $Q$ 次操作。第 $i$ 个操作 $(1 \le i \le Q)$ 由三个整数 $T_i,X_i,A_i$ 描述，表示：

- 若 $T_i=1$，JOI 君在坐标为 $X_i$ 的点处放了 $A_i$ 个蚂蚁。
- 若 $T_i=2$，JOI 君在坐标为 $X_i$ 的点处放了 $A_i$ 块方糖。

由于蚂蚁和方糖都很小，所以可能会有一些蚂蚁和方糖放在同一个点上。JOI 君也可能在同一个点执行多次操作。

这次实验中使用的蚂蚁具有「好奇心强」的萌点。具体地，当 JOI 君拍手时，每个蚂蚁会执行以下操作：

- 如果存在一块方糖与该蚂蚁距离不超过 $L$，它会选择任意一块并吃掉。

可能存在多个蚂蚁同时吃掉一块方糖的情况。

对于每个 $k$ $(1\le k \le Q)$，JOI 君想要知道以下问题的答案。

- 假设 JOI 君在第 $k$ 次操作后拍了一次手，最多有多少块方糖被至少一个蚂蚁吃掉了？

请写一个程序，对于给定的 JOI 君执行的操作和 $L$ 的值，对于所有 $k$ 回答 JOI 君的每个问题。

注意 JOI 君并不会真的拍手。因此蚂蚁的位置不会改变，方糖也不会被吃掉。

inputFormat:
第一行，两个正整数 $Q,L$，表示操作个数和蚂蚁可能吃到的方糖的范围。

接下来 $Q$ 行，其中第 $i$ $(1 \le i \le Q)$ 包含三个整数 $T_i,X_i,A_i$，表示一次操作。

outputFormat: 输出 $Q$ 行，第 $k$ $(1 \le k \le Q)$ 行包含一个整数，表示若 JOI 君在第 $k$ 次操作后拍了一次手，被至少一个蚂蚁吃掉的方糖的个数可能的最大值。

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

在这组样例中，所有操作和每个 $k$ 的答案如下：

 1. JOI 君在坐标为 $1$ 的点放了一个蚂蚁。
    由于没有方糖，对应的答案为 $0$。
 2. JOI 君在坐标为 $2$ 的点放了一块方糖。
    假设 JOI 君此时拍手，则坐标为 $1$ 的蚂蚁会吃掉坐标为 $2$ 的方糖，所以对应的答案为 $1$。
 3. JOI 君在坐标为 $3$ 的点放了一个蚂蚁。
    假设 JOI 君此时拍手，则坐标为 $1,3$ 的蚂蚁会同时吃掉坐标为 $2$ 的方糖，所以对应的答案为 $1$。
 4. JOI 君在坐标为 $0$ 的点放了一块方糖。
    假设 JOI 君此时拍手，则坐标为 $1,3$ 的蚂蚁可以分别吃掉坐标为 $0,2$ 的方糖，所以对应的答案为 $2$。

这组样例满足子任务 $1,2,4$ 的限制。

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

这组样例满足子任务 $1,2,4$ 的限制。

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

这组样例满足子任务 $1,4$ 的限制。

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

这组样例满足子任务 $1,3,4$ 的限制。

**【数据范围】**

对于所有数据，满足：

- $1 \le Q \le 500\,000$。
- $1 \le L \le 10^9$。
- $T_i \in \{1,2\}$。
- $0 \le X_i \le 10^9$ $(1 \le i \le Q)$。
- $1 \le A_i \le 10^9$ $(1 \le i \le Q)$。

详细子任务附加限制及分值如下表所示：

|子任务编号|附加限制|分值|
|:-:|:-:|:-:|
|$1$|$Q \le 3\,000$|$6$|
|$2$|$L=1$，$X_i \le Q-1$，$X_i+T_i$ 是偶数 $(1\le i\le Q)$|$16$|
|$3$|$Q$ 是偶数，$T_i = 1$ $(1 \le i \le Q/2)$，$T_i = 2$ $(Q/2+1 \le i \le Q)$|$26$|
|$4$|无附加限制|$52$|


title: [JOISC2022] 一流团子师傅

background:
JOISC2022 D4T1

**特别提醒，由于洛谷交互机制的特殊性，你不能在程序中引用 `dango3.h`，而需要把 `dango3.h` 中的内容加入文件的开头。即，在程序中 `void Solve(int N, int M)` 的前面加入以下几行语句：**

```cpp
#include <vector>

void Solve(int N, int M);

int Query(const std::vector<int> &x);
void Answer(const std::vector<int> &a);
```

description:
JOI 君是一位专业的团子师傅。在 JOI 君的店里，团子的颜色很有讲究。一共有 $N$ 种颜色，编号为 $1,2,\dots,N$。

**一流团子串**是 JOI 君的店里的招牌食品。制作一个一流团子串，需要将 $N$ 个**颜色不同**的团子串在一根竹签上。

对于每一种颜色，JOI 君都制作了 $M$ 个这种颜色的团子。因此，JOI 君总共有了 $NM$ 个团子。这些团子被编号为 $1,2,\dots,NM$。使用这些团子和 $M$ 根竹签，JOI 君希望串出 $M$ 个一流团子串。

为了避免在颜色上犯错误，JOI 君将会启用他的团子检测器。如果 JOI 君输入一些团子的编号，团子检测器会返回使用这些团子能制作的一流团子串的个数的最大值。当然，前提是充分使用竹签。

JOI 君希望能通过使用若干次团子检测器将 $NM$ 个团子分为 $M$ 组。其中，每一组包含 $N$ 个团子，且每种颜色的团子恰有一个。

JOI 君想在使用不超过 $50\,000$ 次团子检测器的前提下完成这件事。

请写一个程序，对于给定的团子的信息，实现 JOI 君使用不超过 $50\,000$ 次团子检测器来完成任务的策略。

---

**【实现细节】**

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

  - `void Solve(int N, int M)`。
    对于每组测试数据，该函数会被调用恰好一次。
      - 参数 $\texttt N$ 是团子的颜色数 $N$。
      - 参数 $\texttt M$ 是 JOI 君想制作的一流团子串的个数 $M$。

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

  - `int Query(const std::vector<int> &x)`。
    你的程序可以通过调用这个函数来使用团子检测器。
      - 参数 `x` 是输入给团子检测器的团子的编号列表。
      - 该函数返回使用 `x` 中的团子能制作的一流团子串的最大值。
      - `x` 中的每个元素都应当是 $[1,NM]$ 中的整数。否则你的程序会被判定为 **Wrong Answer [1]**。
      - `x` 中的元素应当互不相同。否则你的程序会被判定为 **Wrong Answer [2]**。
      - 你的程序不得调用该函数超过 $50\,000$ 次。否则你的程序会被判定为 **Wrong Answer [3]**。

  - `void Answer(const std::vector<int> &a)`。
    你的程序可以通过调用这个程序来报告分组方案。
      - 参数 `a` 是你分出的一组团子的编号列表。
      - `a` 的长度应当为 $N$。否则你的程序会被判定为 **Wrong Answer [4]**。
      - `a` 中的每个元素都应当是 $[1,NM]$ 中的整数。否则你的程序会被判定为 **Wrong Answer [5]**。
      - 在整个过程中，同一个团子不能出现在参数中多于一次。否则你的程序会被判定为 **Wrong Answer [6]**。
      - 如果用 `a` 中的团子并不能制作一个一流团子串，你的程序会被判定为 **Wrong Answer [7]**。
      - 该函数应当被调用恰好 $M$ 次。否则你的程序会被判定为 **Wrong Answer [8]**。

**【提示】**

  - 你的程序可以实现其他函数以供内部使用，或者使用全局变量。
  - 你的程序不得使用标准输入输出流，也不得以任何方式访问任何文件。然而，你可以输出调试信息到标准错误流。

**【编译与测试运行】**

你可以从「附加文件」中下载样例评分器来测试你的程序。「附加文件」中也提供了你应当提交的程序的一个样例。

样例评分器即 `grader.cpp`。为了测试你的程序，请将 `grader.cpp,dango3.cpp` 放置在同一个目录下，并执行如下命令来编译你的程序。

`g++ -std=gnu++17 -O2 -o grader grader.cpp dango3.cpp`

若编译成功，将会生成一个可执行文件 `grader`。

请注意，实际使用的评分器与下发的样例评分器不同。样例评分器仅会有单个进程，从标准输入中读取输入数据并将结果输出到标准输出。

**【样例评分器输入格式】**

第一行，两个正整数 $N,M$。表示团子的颜色数和 JOI 君想制作的一流团子串的个数。

第二行，$N\times M$ 个正整数 $C_1,C_2,\dots,C_{NM}$。其中 $C_i$ 是一个 $[1,N]$ 内的正整数，表示第 $i$ 个团子的颜色。

**【样例评分器输出格式】**

- 如果你的程序被判定为正确，样例评分器会输出调用 `Query` 的次数，如 “$\texttt{Accepted: 2022}$”。
- 如果你的程序被判定为任意一种 Wrong Answer，样例评分器会输出其类型，如 “$\texttt{Wrong Answer [4]}$”。

如果你的程序属于多种 Wrong Answer，样例评分器只会输出其中一种。


title: [JOISC2022] 鱼 2

background: JOISC2022 D4T2

description:
JOI 君有 $N$ 条鱼，编号为 $1,2,\dots,N$。第 $i$ $(1 \le i \le N)$ 条鱼的大小为 $A_i$。

当我们养鱼的时候，需要注意如下的一个事实：如果有两条鱼离得很近，那么随着时间的流逝，可能会有其中一条吃掉另一条。其中，两条鱼离得很近，当且仅当它们中间没有鱼。
更具体地，如果鱼 $x$ 的大小不小于鱼 $y$ 的大小，且鱼 $x,y$ 离得很近，那么 $x$ 可以吃掉 $y$，且 $x$ 的大小变为原来 $x,y$ 的大小之和。如果 $x,y$ 一样大，那么 $x$ 吃掉 $y$ 或 $y$ 吃掉 $x$ 都可能发生。

JOI 君会养 $Q$ 天鱼。为了消磨时光，他会进行如下的思想实验。在第 $j$ 天 $(1 \le j \le Q)$，JOI 君会进行如下行动中的一个：

- 第一类：JOI 君给鱼 $X_j$ 吃了某些秘制的食物。这会将鱼 $X_j$ 的大小变为 $Y_j$。

- 第二类：JOI 君将编号在区间 $[L_j,R_j]$ 内的鱼单独拿出来，并进行以下实验：
  JOI 君将鱼 $L_j,L_j+1,\dots,R_j$ 从左到右依次放在一个鱼缸中。由于鱼们具有如上所述的特点，最后只有一条鱼会存活。存活的这条鱼的编号取决于在哪些时刻哪些鱼吃掉了哪些鱼。JOI 君想知道可能成为最后存活者的鱼的条数。在实验中，鱼的编号不会改变，也不能有两条鱼同时吃掉同一条鱼。

请写一个程序，对于给定的 JOI 君的鱼和实验的信息，计算每个第二类行动的答案来让 JOI 君能够证明或证伪自己的观点。注意这只是思想实验，并没有任何鱼真的被吃掉。

inputFormat:
第一行，一个正整数 $N$，表示鱼的条数。

第二行，$N$ 个正整数 $A_1,A_2,\dots,A_N$，表示每条鱼的大小。

第三行，一个正整数 $Q$，表示养鱼的天数。
接下来 $Q$ 行，其中第 $j$ $(1 \le j \le Q)$ 行包含若干个由空格分隔的整数，其中第一个整数为 $T_j$，表示操作类型。
  - 若 $T_j=1$，则该行还包含两个正整数 $X_j,Y_j$，表示 JOI 君第 $j$ 天进行了第一类行动。鱼 $X_j$ 的大小变为 $Y_j$。
  - 若 $T_j=2$，则该行还包含两个正整数 $L_j,R_j$，表示 JOI 君第 $j$ 天进行了第二类行动。JOI 君对编号在 $[L_j,R_j]$ 内的鱼进行了一次实验。

outputFormat: 对于每次第二类行动（即，对于每个满足 $T_j=2$ 的 $j$ $(1 \le j \le Q)$），输出一行一个整数，表示可能成为最后存活者的鱼的条数。

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

在 $6$ 天中，JOI 君进行了以下行动：

- 第一天，他对鱼 $1,2,3,4,5$ 进行了一次实验。
- 第二天，他对鱼 $1,2,3$ 进行了一次实验。
- 第三天，他给鱼 $3$ 吃了秘制食物，使其大小变为 $1$。
- 第四天，他对鱼 $2,3,4,5$ 进行了一次实验。
- 第五天，他对鱼 $1,2,3,4,5$ 进行了一次实验。
- 第六天，他对鱼 $2,3,4$ 进行了一次实验。

第一天的实验的结果如下：

- 鱼缸中的鱼的大小依次为 $[6,4,2,2,6]$。
- 例如，经过如下过程，鱼 $2$ 会成为最后存活者。（其中粗体为鱼 $2$ 的大小。）
  $[6,\textbf 4,2,2,6]$（初始状态）$\longrightarrow$ $[6,\textbf 4,4,6]$（鱼 $4$ 吃掉鱼 $3$）$\longrightarrow$ $[6,\textbf 8,6]$（鱼 $2$ 吃掉鱼 $4$）$\longrightarrow$ $[\textbf{14},6]$（鱼 $2$ 吃掉鱼 $1$）$\longrightarrow$ $[\textbf{20}]$（鱼 $2$ 吃掉鱼 $5$）。
- 类似地，鱼 $1,2,3,4,5$ 都可能成为最后存活者。因此答案为 $5$。

该样例满足子任务 $1,3,6$ 的限制。

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

该样例满足所有子任务的限制。

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

该样例满足子任务 $1,3,4,6$ 的限制。

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

该样例满足子任务 $1,3,5,6$ 的限制。

**【数据范围】**

对于所有数据，满足：

- $1 \le N,Q \le 100\,000$。
- $1 \le A_i \le 10^9$ $(1\le i\le N)$。
- $T_j \in \{1,2\}$。
- $1 \le X_j \le N$ $(1\le j\le Q)$。
- $1 \le Y_j \le 10^9$。
- $1 \le L_j \le R_j \le N$ $(1 \le j \le Q)$。

详细子任务附加限制及分值如下表所示：

|子任务编号|附加限制|分值|
|:-:|:-:|:-:|
|$1$|$N \le 500$，$Q \le 500$|$5$|
|$2$|$Q=1$，$T_j=2$，$L_j=1$，$R_j=N$ $(1 \le j \le Q)$|$8$|
|$3$|$Q\le 1\,000$|$12$|
|$4$|$T_j=2$ $(1 \le j\le Q)$|$23$|
|$5$|对于每个满足 $T_j=2$ 的 $j$ $(1\le j\le Q)$，满足 $L_j=1$，$R_j=N$|$35$|
|$6$|无附加限制|$17$|


title: [JOISC2022] 复兴计划

background: JOISC2022 D4T3

description:
JOI 镇是一个曾经辉煌的工业区。为了运输产品，其中建起了许多铁轨与火车站。尽管 JOI 镇已经衰落，那里仍有许多不再被使用的铁轨与火车站。

JOI 镇中有 $N$ 个火车站，编号为 $1,2,\dots,N$。其中还剩下 $M$ 条铁轨。第 $i$ 条铁轨 $(1\le i \le M)$ 双向连接火车站 $A_i$ 和 $B_i$，且其宽度为 $W_i$。保证能够从任意火车站经过若干条铁轨到达任意其他火车站。

你是 JOI 镇的镇长。你计划吸引铁路公司来使用 JOI 镇中留下的铁轨与火车站，使得 JOI 镇复苏成为「铁路之镇」。

于是，共有 $Q$ 个铁路公司申请参与这个复兴计划。然而，不同公司的火车所需的铁轨宽度也有所不同。这意味着你需要重建这些铁轨，使得它们都匹配对应公司的火车。

第 $j$ $(1\le j\le Q)$ 家铁路公司的火车所需的铁轨宽度为 $X_j$。为了迎合公司 $j$，要求满足以下条件：
- **条件**：保证能够从任意火车站只经过宽度为 $X_j$ 的铁轨到达任意其他火车站。

为了满足上述条件，你可以按如下方式重建铁轨任意次：
- **重建**：选择一条铁轨，你可以重建其使得其宽度增加或减少 $1$ 并花费 $1$。然而，若其宽度为 $1$，则不能再减少其宽度。

为了确定你能满足哪些公司，你需要求出迎合公司 $j$ 所需要的最小花费。

请写一个程序，对于给定的火车站、铁轨与铁路公司的信息，计算迎合公司 $j$ 所需要的最小花费。

inputFormat:
第一行，两个正整数 $N,M$，表示火车站的个数和铁轨的条数。

接下来 $M$ 行，其中第 $i$ $(1 \le i \le M)$ 行包含三个正整数 $A_i, B_i, W_i$，表示第 $i$ 条铁轨连接的火车站和其宽度。

第 $M+2$ 行，一个正整数 $Q$，表示铁路公司的个数。

接下来 $Q$ 行，其中第 $j$ $(1 \le j \le Q)$ 行包含一个正整数 $X_j$，表示第 $j$ 个铁路公司的火车需要的铁路宽度。

outputFormat: 输出 $Q$ 行，第 $j$ $(1\le j\le Q)$ 包含一个整数，表示迎合公司 $j$ 所需要的最小花费。


title: 【MX-X3-T4】「RiOI-4」上课

background: 一天，小 M 在宿舍 $6:53$ 起床，而早自习 $7:00$ 开始。

description:
给定正整数 $n,q$ 和 $n$ 个区间 $[l_i,r_i]$。

有 $q$ 组询问，每次询问给定一个整数 $x$。在每个区间内选择一个整数 $a_i$（$l_i\leq a_i\leq r_i$），使得所选整数的总和等于 $x$，并使得选出的 $a$ 序列的方差最小。输出方差最小值，对 $998\,244\,353$ 取模。保证存在至少一种合法的选取方案。

关于方差的有关定义参照此[云剪切板](https://www.luogu.com.cn/paste/dpptrubn)，有理数取模参照[【模板】有理数取余](https://www.luogu.com.cn/problem/P2613)。

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

接下来的 $n$ 行，每行两个自然数 $l_i,r_i$。

最后 $q$ 行，每行一个整数 $x$，表示一次询问。保证存在至少一种合法的选取方案。

outputFormat: $q$ 行，每行一个整数，表示最小方差对 $998\,244\,353$ 取模的值。


title: [语言月赛 202309] 数组与内存 EV

type: B

description:
一维数组常常被想象为一个线性的数列，二维数组常常被想象为一个平面上的矩阵，三维数组常常被想象为空间中的一个立方体。由于我们生存在三维宇宙中，再高维度的数组的形态难以被想象，但是我们有理由认为，$n$ 维数组在 $n$ 维空间中可以被想象为一个几何体。

但是，无论数组的维数多高，计算机的内存空间总是线性的。
- C++ 在定义一维数组 $a[N]$ 时，会从 $a[0]$ 开始，在内存中连续申请 $N$ 个变量的**连续的**空间，依次分配给 $a[0],a[1],\cdots,a[N-1]$。

- 二维数组 $a[N][M]$ 可以看作 $N$ 个大小为 $M$ 的一维数组连续拼接在一起。C++ 在定义二维数组 $a[N][M]$ 时，会从 $a[0][0]$ 开始，在内存中申请 $N\times M$ 个变量的**连续的**空间，先排布 $a[0]$ 的一维数组，再依次排布 $a[1],a[2],\cdots,a[N-1]$ 的一维数组。排布规则与上面一维数组的情形相同。

- 更高维的数组以此类推。

众所周知，二维数组 $a[N][M]$ 可以使用的下标范围为 $a[0\sim N-1][0\sim M-1]$。但是，当定义了数组 $a[2][3]$，并使用了下标 $a[0][4]$，并不会访问非法内存，而是会访问到 $a[1][1]$。这是因为数组是依托于**连续线性**内存的，$a[0][4]$ 与 $a[1][1]$ 都是指向自 $a[0][0]$ 数起的（含 $a[0][0]$）第 $5$ 个变量，它们指向的内存地址是相同的。更高维度的数组亦有相同的机制。

现在，小 F 定义了一个二维数组 $a[N][M]$，并尝试访问 $a[p][q]$，请问小 F 是否会访问非法内存。

inputFormat: 输入一行四个非负整数，依次为 $N,M,p,q$。

outputFormat:
输出一行一个字符串：

- 若会访问非法内存，输出 `Segmentation fault.`。
- 若不会访问非法内存，输出 `Program ends with return value 0.`。

samples:
4 2 2 3
Program ends with return value 0.

samples:
4 2 2 100
Segmentation fault.


title: 「yyOI R1」youyou 的篡改（Hard Ver.）

background: **Easy Version 与 Hard Version 仅最后所求内容不同，其他描述均一致。**

description:
youyou 准备举办一场比赛，这场比赛有 $n$ 道题，每一道题都有一个难度值 $v_i$。

youyou 给出一个计数分量 $k(k\le n)$，他认为，第 $x(x \geq k)$ 道题的可做性 $a_x$ 应当是第 $1\sim x$ 题所有题目中将难度值从小到大排序后难度较大的 $k$ 道题目难度值之和。

由于第 $1 \sim k-1$ 题难度过于简单，youyou 不想考虑这些题目的可做性。

那么这场比赛的总可做性即为第 $k$ 道题至第 $n$ 道题可做性之和，即 $\sum^{n}_{i=k}a_i$
 的值。

他可以篡改题目 $m$ 的难度为任意正整数。

问：总可做性必须满足在区间 $[l,r]$ 的范围内，那么总可做性有几种取值？

inputFormat:
第一行输入五个正整数，分别为 $n,m,k,l,r$。

第二行输入 $n$ 个整数，第 $i$ 个数 $v_i$ 为第 $i$ 道题难度值。

outputFormat: 仅一行，输出一个数，表示在满足条件的前提下，总可做性的取值数。


title: Water

description:
有 $n$ 个杯子，每个杯子的容积是 $a$，且初始装有 $b$ 体积水。
你可以进行任意次操作，每次操作选择任意两个杯子，将其中一个杯子内的水**全部倒入**另一个杯子中，但是过程中**杯子里的水不能溢出（即不能超过其容积）**，如果不满足则无法进行该操作。

请通过合法的操作，最大化装有最多水的杯子里水的体积。

inputFormat: 一行三个整数，表示 $a,b,n$。

outputFormat: 一行一个整数 $x$，表示最多水的杯子内的水的体积。


title: Line

description:
在一个二维平面内，给定两条**分别与 $x$ 轴和 $y$ 轴平行**的线段 $AB$ 和 $CD$。

你可以选择一条线段，将其沿着平行于坐标轴（上下左右）的任意一个方向平移**任意单位长度**，称为一次操作。

问至少进行几次操作可以使两条线段相交？

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

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

对于每组测试数据：

- 一行八个正整数 $x_A,y_A,x_B,y_B,x_C,y_C,x_D,y_D$，表示 $A,B,C,D$ 的坐标。

outputFormat:
对于每组测试数据：

- 一行一个整数表示最少操作次数。


title: 「MXOI Round 1」宝箱

description:
小 C 喜欢在一款叫做渊深的游戏中收集宝箱。

现在，小 C 在一条数轴上，他在数轴的原点处。

同时，在这条数轴上还有两个宝箱，它们的坐标分别为 $a$ 和 $b$。

只要小 C 移动到某个宝箱的位置，就认为小 C 收集到了这个宝箱。特殊地，如果小 C 初始时就在某个宝箱的位置，那么他可以直接收集到这个宝箱；如果两个宝箱在同一个位置，那么他可以同时收集这两个宝箱。

小 C 每次可以沿着这条数轴的正方向或负方向移动一个单位长度。小 C 想知道，收集到这两个宝箱至少需要移动多少次？

inputFormat: 两个整数 $a,b$。

outputFormat: 一个整数，表示小 C 收集到这两个宝箱所至少需要的移动次数。

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

小 C 可以先沿着数轴的负方向移动 $1$ 次，再沿着数轴的正方向移动 $2$ 次。

可以证明小 C 至少需要移动 $3$ 次。

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

小 C 可以直接沿着数轴的负方向移动 $5$ 次。

可以证明小 C 至少需要移动 $5$ 次。

#### 【数据范围】

对于 $100\%$ 的数据，$\vert a\vert,\vert b\vert \le 200$。

|测试点编号|特殊性质|
|:---:|:---:|
|$1\sim3$|保证 $\vert a\vert,\vert b\vert \le 1$|
|$4\sim6$|保证 $ab=0$|
|$7\sim10$|无|


title: 「KDOI-06-J」ION 比赛

description:
在 ION 比赛中，总共有 $n$ 道题目。每道题目的满分均为 $100$ 分。

第 $i$ 道题有 $a_i$ 个测试点，且该题的所有测试点分值相等，因此 $a_i$ 一定是 $100$ 的因数。每通过一个测试点，你将会得到与该测试点分值相等的分数。

通过一些技术手段，你了解到 ION 比赛今年的 Au 分数线是 $t$ 分。

现在，你在第 $i$ 道题中已经通过了 $b_i$ 个测试点。作为一名策略选手，你想知道：对于任意 $1\le j\le n$，如果你在比赛剩下的时间内死磕第 $j$ 题（不做其他题目），需要至少再多通过几个测试点以获得 Au，也就是说，使你的总分 $\ge t$。

当然，你有可能无法通过死磕某一道题目翻盘（获得 Au），此时你需要输出 `NaN`。

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

输入的第一行包含一个正整数 $n$，表示题目总数。

接下来 $n$ 行，一行两个非负整数 $a_i,b_i$，表示第 $i$ 题的测试点个数和你已经通过的测试点个数。保证 $a_i$ 是 $100$ 的因数且 $b_i\le a_i$。

最后一行一个整数 $t$，表示 Au 分数线。

outputFormat:
输出到标准输出。

如果你的分数已经达到 Au 线，请输出一行一个字符串 `Already Au.`。

否则，输出 $n$ 行。在第 $i$ 行中你应该输出以下两种格式之一：

+ 一个正整数 $c_i$，表示在第 $i$ 道题目中你需要至少再通过多少个测试点才可以获得 Au。
+ 一个字符串 `NaN`，表示你无法通过这题翻盘（获得 Au）。


title: [湖北省选模拟 2023] 日记 / diary

description:
小 M 决定开始写日记，但她不愿意花费太多时间构思日记的内容。为此，她找来了一个长度为 $n$ 的字符串 $S$，决定任取 $S$ 的一个前缀 $P$，再任取 $S$ 的一个后缀 $Q$，将 $P$ 和 $Q$ 顺次连接起来得到的字符串 $P+Q$ 作为日记的内容。这里，空串也认为是 $S$ 的前缀和后缀，因此 $P$ 和 $Q$ 各有 $n+1$ 种取法。

当然了，这样形成的很多字符串是无意义的。具体而言，小 M 认为一个已知的长度为 $m$ 的字符串 $T$ 为重要信息，所有包含该重要信息作为子串的字符串都是有意义的，反之则是无意义的。

请你求出，小 M 一共能写出多少种本质不同的有意义的字符串。本质不同就是说，对于某个有意义的字符串 $A$ ，即使它可以被若干种取前缀和后缀的方式得到，也只应被计入一次。

inputFormat:
输入共两行。

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

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

outputFormat: 一行一个整数，所求答案。

samples: 见选手目录下的 diary/diary3.in 与 diary/diary3.ans。

samples: 见选手目录下的 diary/diary4.in 与 diary/diary4.ans。

samples: 见选手目录下的 diary/diary5.in 与 diary/diary5.ans。

hint:
### 样例 1 解释

对于第一组样例，所有能够形成的有意义字符串分别为  `ab`，`aab`，`aaab`，`aaaab`，`aabaab`，`aabab`，`aabb`，一共 $7$ 种。

### 子任务

对于所有测试数据，保证 $1 \leq |S| \leq 5 \times 10^6$，$1 \leq |T| \leq 2|S|$，输入的字符串 $S$ 和 $T$ 仅包含小写英文字母。其中 $|S|,|T|$ 分别表示串 $S$ 和 $T$ 的长度。

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

- 2023.8.21 添加一组 hack 数据。


title: [湖北省选模拟 2023] 调和 / conduct

description:
小 C 是一名药师，为了制作出某种药剂，她需要在 S 大陆上寻找一些药材。

S 大陆可以抽象为一棵 $n$ 个顶点的无根树，每个顶点上都有一种药材。每种药材的属性可以描述为一个三元组 $(x,y,z)$，其中 $x$，$y$，$z$ 均为正整数。

如果小 C 获得了 $n$ 种属性分别为 $(x_1,y_1,z_1), (x_2,y_2,z_2)  \ldots  (x_n,y_n,z_n)$ 的 $n$ 种药材，她可以任取 $n$ 个不全为 $0$ 的非负实数 $a_1,a_2 \ldots a_n$，将这些药材调和为一种属性为 $(\sum a_i x_i,\sum a_i y_i,\sum a_i z_i)$ 的药剂。

现在小 C 需要在 S 大陆上收集药材。具体而言，她需要选定树上的一个连通块，并获得连通块中所有顶点上的药材。现给定小 C 想制作的药剂的属性 $(a,b,c)$，请你求出，如果小 C 需要使用所获得的药材调和出属性为 $(a,b,c)$ 的药剂，她选定的连通块的大小至少是多少。

inputFormat:
输入共 $2n$ 行。

第一行四个正整数 $n,a,b,c$。

接下来 $n$ 行，每行三个正整数 $x_i,y_i,z_i$，表示 $i$ 号节点上的药材的属性。

接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$，表示树上存在一条连接 $u$ 和 $v$ 的边。

**保证输入的边描述的是一棵树。**

**保证不存在两个完全相同的药材，但是可以存在某一个药材的属性和所需药剂完全一致。**

**保证对于所有药材，都有 $x_i + y_i + z_i = a + b + c$。**

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

hint:
### 样例 1 解释

对于第一组样例，可以选择包含顶点 $1$，$2$ 和 $3$ 的连通块，取 $a_1,a_2,a_3$ 分别为 $\dfrac{1}{2},0,\dfrac{1}{2}$，即可得到属性为 $(\dfrac{1}{2} + \dfrac{3}{2},\dfrac{1}{2} + \dfrac{3}{2},\dfrac{5}{2} + \dfrac{1}{2}) = (2,2,3)$ 的药材。

### 子任务

对于所有测试数据，保证 $1 \leq n \leq 5 \times 10^4$，$1 \leq a,b,c,x_i,y_i,z_i \leq 2 \times 10^9$。

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

- 2023.8.25 添加一组 hack 数据。


title: [湖北省选模拟 2023] 环山危路 / road

description:
R 国有 $n$ 座城市，编号从 $1$ 到 $n$。这些城市两两之间都有道路连接，形成一个图的结构。不过，这些路修得很烂，每条路都有一个固定的方向，车只能按照这个方向行驶；路还是一次性的，也就是说最多只能过一辆车。

现在 R 国正在制定防灾减灾预案。你需要帮助 R 国计算，如果 $t_i$ 号城市发生了灾难，并且 $s_{i,1},s_{i,2},\dots,s_{i,k_i}$ 这些城市有充足的救灾物资（可以认为它们都拥有可以装无数辆车的物资），那么最多能从这些城市运送几车物资到达 $t_i$。车只能走城间的那些一次性道路，不过车在到达 $t_i$ 之前是可以经过多个城市和多条道路中转的。

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

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

第二行到第 $n+1$ 行，每行一个长为 $n$ 的 $01$ 字符串，第 $i+1$ 行第 $j$ 列表示是否有从 $i$ 通向 $j$ 的道路（$1$ 表示有，$0$ 表示无）。

接下来 $m$ 行，每行第一个正整数为 $t_i$，第二个正整数为 $k_i$，接着 $k_i$ 个正整数 $s_{i,1},s_{i,2},\dots,s_{i,k_i}$。保证 $s_{i,1},s_{i,2},\dots,s_{i,k_i}$ 中没有重复的数且没有 $t_i$。

outputFormat: 输出 $m$ 行，每行一个非负整数，表示第 $i$ 次询问的答案。

samples:
见选手目录下的 road/road2.in 与 road/road2.ans。
见选手目录下的 road/road2.in 与 road/road2.ans。

hint:
### 样例 1 解释

城市间的路如下图所示：

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

这是答案对应的一种可能的方案：

第一次询问中，一辆车走 $1 \rightarrow 2$，另一辆走 $4 \rightarrow 1 \rightarrow 5 \rightarrow 2$；

第二次询问中，一辆车走 $1 \rightarrow 5$，一辆走 $1 \rightarrow 2 \rightarrow 3 \rightarrow5$，还有一辆走 $4 \rightarrow 5$。

### 子任务

对于所有测试数据，保证 $1 \le n \le 3000$，$1 \le m,\sum\limits_{i=1}^mk_i \le 30000$。

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

特殊性质 A：保证所有询问的 $t_i$ 相等。

特殊性质 B：保证 $u$ 与 $v$ 之间的路从 $\min(u,v)$ 通向 $\max(u,v)$。


title: [湖北省选模拟 2023] 山路长环 / ring

description:
张三和李四在玩游戏。游戏规则是这样的：

在他们面前有一个棋盘，棋盘是一个由 $n$ 个节点和 $n$ 条边构成的环，边有边权。初始时，一枚棋子被放置在某个节点上。张三和李四轮流移动棋子，张三为先手，无法移动者败。每次移动时，必须选择棋子当前所在节点的某个相邻点（即有边相连的点），沿着边将棋子移动到这个相邻点去，并将边权减少任意正整数。需要注意的是，边权不允许被减小到负数。

张三想让你算算，对于给定的棋盘，有多少种初始棋子的摆放方式能使得他有必胜策略。

现在你有一个长为 $m$ 的序列 $a_1,a_2,\dots,a_m$，你需要完成 $q$ 次操作。每次操作形式为如下之一：

- `1 x y` 表示将 $a_x$ 赋值为 $y$；
- `2 l r` 表示查询如果棋盘上共 $(r-l+1)$ 个节点，且边权以顺时针方向分别为 $a_l,a_{l+1},\dots,a_r$，那么这样一盘游戏共有多少个不同的初始棋子位置可以让张三有必胜策略。

inputFormat:
输入共 $m+2$ 行。

第一行两个正整数 $m,q$。

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

接下来 $q$ 行，每行三个整数，格式如题面所述。

outputFormat: 输出若干行，每行一个非负整数，表示一次询问的答案。

samples:
见选手目录下的 ring/ring2.in 与 ring/ring2.ans。
见选手目录下的 ring/ring2.in 与 ring/ring2.ans。

hint:
### 子任务

对于所有测试数据，保证 $1 \le m,q \le 3 \times 10^5$，$1 \le l \le r \le m$，$1\le x \le m$，$0 \le y,a_i \le 10^6$。

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

特殊性质 A：保证 $0 \le y,a_i \le 1$。

特殊性质 B：保证所有询问满足 $l=1$，$r=m$。

特殊性质 C：保证没有修改操作。


title: [湖北省选模拟 2023] 路环群山 / mountain

description:
某二维世界中有一个山地，山体可以用一个函数 $f(x)$ 描述，其表示横坐标 $x$ 的位置海拔高度为 $h=f(x)$。这个世界里有 $n+m$ 只羊，其中有 $n$ 只山羊和 $m$ 只绵羊。我们知道第 $i$ 只山羊所在的横坐标是 $p_i$，第 $j$ 只绵羊所在的横坐标是 $q_j$，但不知道它们所在的高度。不过，我们知道山羊们所在的位置海拔集中在一个较高的范围，而绵羊们所在的位置海拔集中在一个较矮的范围。你需要根据山羊和绵羊的分布情况猜测山体形态 $f(x)$，使得山羊高度的方差和绵羊高度的方差都尽可能小，同时山羊高度尽可能高于绵羊高度。

形式化地，令

$$
\bar{u}=\frac{1}{n}\sum_{i=1}^n f(p_i)
$$

$$
\bar{v}=\frac{1}{m}\sum_{j=1}^m f(q_i)
$$

表示山羊、绵羊分别的平均高度，你的目标就是构造函数 $f$，最小化代价
$$
\operatorname{cost}(f)=\frac{1}{\bar{u}-\bar{v}}\sqrt{\left[\sum_{i=1}^n (f(p_i)-\bar{u})^2\right]+\left[\sum_{j=1}^m (f(q_j)-\bar{v})^2\right]}
$$
当然，**你还需要保证 $\bar u > \bar v + 10^{-9}$**。

方便起见，你需要使用傅里叶级数描述 $f$。即给定 $k$，你需要求出最优的形如 $f(x)=\sum_{i=1}^k a_i\cos(ix)+b_i\sin(ix)$ 的函数 $f$，并输出 $a_i,b_i$ 表示答案。**请你保证 $10^{-9}\le \max_{i=1}^k\{|a_i|,|b_i|\} \le 10^9$**。**数据保证存在满足上述限制的最优解。**

本题开启 Special Judge。给定容错度 $\epsilon=10^{-E}$。当你给出的函数 $f$ 与答案给出的函数 $f^*$ 满足 $\operatorname{cost}(f)<\max(\epsilon+\operatorname{cost}(f^*),(1+\epsilon)\operatorname{cost}(f^*))$ 时认为你的答案正确。

inputFormat:
输入共三行。

第一行三个整数 $n,m,k,E$；

第二行 $n$ 个整数，第 $i$ 个数为 $p_i$；

第三行 $m$ 个整数，第 $j$ 个数为 $q_j$。

outputFormat: 输出 $k$ 行，每行两个浮点数 $a_i,b_i$。

samples: 见选手目录下的 mountain/mountain3.in 与 mountain/mountain3.ans。

hint:
### 样例 1 解释

观察到 $\cos(10838702)=\cos(-10838702)\approx 1 =\cos(0)$，$\cos(1)=\cos(-1)\approx 0.5403023$。即当 $f(x)=\cos(x)$ 时，所有山羊几乎均位于同一海拔、所有绵羊均位于同一海拔、山羊所在位置均高于绵羊所在位置。此时 $\operatorname{cost}(f) \approx 0$ 取得最优解。

值得注意的是，对于任何非零数 $r$，函数 $f(x)=r\cos(x)$ 均可视为最优解。

### 样例 2 解释

最优函数（之一）约为 $f(x)=0.6648289523\cos(x)-0.1433645347\sin(x)+0.6172866488\cos(2x)+1.3647253547\sin(2x)$，其代价约为 $3.908439063011$。

### 子任务

对于所有测试数据，保证 $1 \le n,m \le 600$，$1 \le k \le \min\{\dfrac{n+m}{4},300\}$，$0 \le E \le 9$，$0\le |p_i|,|q_i| \le 10^9$。

**保证每个测试数据中，$p_i$ 和 $q_j$ 均在该测试点数据范围内以及问题有解的条件下均匀随机生成。**

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


title: 「PFLOI R1」PFL 团主的 PFL 操作

background:
比赛结束后，智力、旸麦、花猫邀来碓瑘，四人从此结交为友。

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

实际上，不光碓瑘，智力、旸麦、花猫都曾是 OI 界中最强的存在。一次又一次 AK 一场又一场 Trash Round 后，它们厌倦了，从此销声匿迹，退出江湖。

今天看到碓瑘才气不减当年，它们又念想起那些和 OI 作伴的时光……兴意，顿生心头。

于是它们找到了 PFLOI 团长珺珺，请求珺珺给它们再次辉煌的机会——出一场属于自己的比赛。

听完它们的事迹后，珺珺颇为感动，欣然同意。5 人就此相聚在 PFLOI。

但是旸麦进入 PFLOI 后~~乱出题~~太调皮了，珺珺可不乐意了，于是：

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

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

description:
有 $n$ 次操作，每次操作会等概率地进行以下事件中的一个：

1. 将 $a_i$ 加入团队，操作后 $a_i$ 为成员。
2. 将 $a_i$ 踢出团队。
3. 将 $a_i$ 设置为管理员。
4. 将 $a_i$ 设置为成员。

**注意：**

+ 开始时没有人在团队里。
+ 如果 $a_i$ 不在团队中，则 2、3、4 操作无效果。
+ 如果 $a_i$ 为成员，则 1、4 操作无效果。
+ 如果 $a_i$ 是管理员，则 1、2、3 操作无效果。

最后输出团队中管理员个数的期望，答案对 $998244353$ 取模。

inputFormat:
第一行一个整数 $\text{type}$。
如果 $\text{type}$ 为 $1$，则采用**第一种输入方式**，否则采用**第二种输入方式**。

### 第一种输入方式：

第一行一个正整数 $n$。
第二行共 $n$ 个整数表示数组 $a$。

### 第二种输入方式：

共一行四个整数分别是 $n,a_0,p,q$。

**注意：第二种输入方式中，数组 $a$ 需要你计算得出，满足 $a_i=(a_{i-1}\times p+p)\bmod q+ 1$ $ (i \geq 1)$。**

outputFormat: 输出一个整数表示团队中管理员个数的期望，对 $998244353$ 取模。


title: [NICA #3] 彩灯装饰

description:
Aya 在研究彩灯装饰图案。一个 $n$ 阶的彩灯装饰图案由 $n$ 行组成，第 $i$ 行一共有 $2\times i-1$ 个 `#` 构成一个等腰三角形。如下图是一个 $3$ 阶的彩灯装饰图案：

```
  #
 ###
#####
```

为了让彩灯的图案更为有趣，Aya 决定将每一行中第 **完全平方数** 个 `#` 改为 `!`，例如说 $3$ 阶的彩灯装饰图案最后会变成这样：

```
  !
 !##
!##!#
```

现在给定一个正整数 $n$，问 $n$ 阶的彩灯装饰图案会变成什么样。

inputFormat: 输入一个正整数 $n$，表示要求的是 $n$ 阶的彩灯装饰图案。

outputFormat: 输出该图案，注意每一行末尾不应出现多余的空格。

hint: 数据保证，$1 \leq n \leq 100$。


title: [SDCPC2023] Building Company

description:
You're the boss of a building company. At the beginning, there are $g$ types of employees in the company, and different types of employees have different occupations. For the $i$-th type of employees, their occupation can be numbered as $t_i$ and there are $u_i$ employees in total.

There are $n$ building projects in the market waiting to be undertaken. To undertake the $i$-th project, your company must meet $m_i$ requirements. The $j$-th requirement requires that your company has at least $b_{i, j}$ employees whose occupation is $a_{i, j}$. After undertaking the project, your company will become more famous and will attract $k_i$ types of employees to join your company. The occupation of the $j$-th type of employees is $c_{i, j}$ and there are $d_{i, j}$ employees in total.

You can undertake any number of projects in any order. Each project can be undertaken at most once. Calculate the maximum number of projects you can undertake.

Note that employees are not consumables. After undertaking a project the number of employees in your company won't decrease.

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

The first line of the input first contains an integer $g$ ($1 \le g \le 10^5$) indicating the number of types of employees in the company at the beginning. Then $g$ pairs of integers $t_1, u_1, t_2, u_2, \cdots t_g, u_g$ follow ($1 \le t_i, u_i \le 10^9$), where $t_i$ and $u_i$ indicate that there are $u_i$ employees whose occupation is $t_i$. It's guaranteed that for all $1 \le i < j \le g$ we have $t_i \ne t_j$.

The second line contains an integer $n$ ($1 \le n \le 10^5$) indicating the number of projects waiting to be undertaken.

For the following $2n$ lines, each two lines describe a project.

The $(2i - 1)$-th line first contains an integer $m_i$ ($0 \le m_i \le 10^5$) indicating the number of requirements to undertake the $i$-th project. Then $m_i$ pairs of integers $a_{i, 1}, b_{i, 1}, a_{i, 2}, b_{i, 2}, \cdots, a_{i, m_i}, b_{i, m_i}$ follow ($1 \le a_{i, j}, b_{i, j} \le 10^9$) where $a_{i, j}$ and $b_{i, j}$ indicate that the company is required to have at least $b_{i, j}$ employees whose occupation is $a_{i, j}$. It's guaranteed that for all $1 \le x < y \le m_i$ we have $a_{i, x} \ne a_{i, y}$.

The $2i$-th line first contains an integer $k_i$ ($0 \le k_i \le 10^5$) indicating the number of types of employees to join the company after undertaking the $i$-th project. Then $k_i$ pairs of integers $c_{i, 1}, d_{i, 1}, c_{i, 2}, d_{i, 2}, \cdots, c_{i, k_i}, d_{i, k_i}$ follow ($1 \le c_{i, j}, d_{i, j} \le 10^9$) where $c_{i, j}$ and $d_{i, j}$ indicate that there are $d_{i, j}$ employees whose occupation is $c_{i, j}$ joining the company. It's guaranteed that for all $1 \le x < y \le k_i$ we have $c_{i, x} \ne c_{i, y}$.

It's guaranteed that neither the sum of $m_i$ nor the sum of $k_i$ will exceed $10^5$.

outputFormat: Output one line containing one integer indicating the maximum number of projects you can undertake.

translation:
**【题目描述】**

您是一家建筑公司的老板。一开始，公司共有 $g$ 类员工，每一类员工都属于一个工种。第 $i$ 类员工的工种编号为 $t_i$，共有 $u_i$ 人。

市场上共有 $n$ 项工程等待承接。想要承接第 $i$ 项工程，您的公司需要满足 $m_i$ 项要求，其中第 $j$ 项要求您的公司至少有工种编号为 $a_{i, j}$ 的员工 $b_{i, j}$ 人。承接该工程后，您的公司将会更加有名，并吸引 $k_i$ 类员工加入公司，其中第 $j$ 类员工的工种编号为 $c_{i, j}$，共有 $d_{i, j}$ 人。

您可以按任意顺序承接任意数量的工程，每项工程最多只能被承接一次。求最多能承接多少工程。

请注意：员工不是消耗品。承接一项工程后，员工的数量不会减少。

**【输入格式】**

每个测试文件仅有一组测试数据。

第一行首先输入一个整数 $g$（$1 \le g \le 10^5$）表示一开始公司内员工的种类数。接下来输入 $g$ 对整数 $t_1, u_1, t_2, u_2, \cdots t_g, u_g$（$1 \le t_i, u_i \le 10^9$），其中 $t_i$ 和 $u_i$ 表示一开始工种编号为 $t_i$ 的员工共有 $u_i$ 人。保证对于所有 $1 \le i < j \le g$ 有 $t_i \ne t_j$。

第二行输入一个整数 $n$（$1 \le n \le 10^5$）表示等待承接的工程数量。

对于接下来 $2n$ 行，每两行描述一项工程。

第 $(2i - 1)$ 行首先输入一个整数 $m_i$（$0 \le m_i \le 10^5$）表示承接第 $i$ 项工程有几项要求。接下来输入 $m_i$ 对整数 $a_{i, 1}, b_{i, 1}, a_{i, 2}, b_{i, 2}, \cdots, a_{i, m_i}, b_{i, m_i}$（$1 \le a_{i, j}, b_{i, j} \le 10^9$），其中 $a_{i, j}$ 和 $b_{i, j}$ 表示公司至少要有工种编号为 $a_{i, j}$ 的员工 $b_{i, j}$ 人。保证对于所有 $1 \le x < y \le m_i$ 有 $a_{i, x} \ne a_{i, y}$。

第 $2i$ 行首先输入一个整数 $k_i$（$0 \le k_i \le 10^5$）表示承接第 $i$ 项工程之后有几类员工加入公司。接下来输入 $k_i$ 对整数  $c_{i, 1}, d_{i, 1}, c_{i, 2}, d_{i, 2}, \cdots, c_{i, k_i}, d_{i, k_i}$（$1 \le c_{i, j}, d_{i, j} \le 10^9$），其中 $c_{i, j}$ 和 $d_{i, j}$ 表示工种编号为 $c_{i, j}$ 的员工共 $d_{i, j}$ 人加入公司。保证对于所有 $1 \le x < y \le k_i$ 有 $c_{i, x} \ne c_{i, y}$。

保证 $m_i$ 与 $k_i$ 之和均不超过 $10^5$。

**【输出格式】**

输出一行一个整数表示最多能承接几项工程。

**【样例解释】**

样例解释如下，用 $(t, u)$ 表示工种为 $t$ 的员工有 $u$ 名。

首先承接没有任何要求的第 $5$ 项工程，承接后工种为 $3$ 的 $2$ 名员工加入公司。公司内现有员工为 $\{(1, 2), (2, 1), (3, 2)\}$。

接下来承接第 $1$ 项工程，承接后没有员工加入公司。公司内现有员工仍为 $\{(1, 2), (2, 1), (3, 2)\}$。

接下来承接第 $2$ 项工程，承接后工种为 $3$ 的 $2$ 名员工，以及工种为 $2$ 的 $1$ 名员工加入公司。公司内现有员工为 $\{(1, 2), (2, 2), (3, 4)\}$。

接下来承接第 $4$ 项工程，承接后工种为 $1$ 的 $3$ 名员工加入公司。公司内现有员工为 $\{(1, 5), (2, 2), (3, 4)\}$。

由于工种为 $2$ 的员工不足 $3$ 名，因此无法承接仅剩的第 $3$ 项工程。

hint:
We explain the sample test case as follows. Let $(t, u)$ indicate $u$ employees whose occupation is $t$.

First, undertake the $5$-th project with no requirements. After undertaking the project, there are $2$ employees, whose occupation is $3$, joining the company. The company now have these employees: $\{(1, 2), (2, 1), (3, 2)\}$.

Next, undertake the $1$-st project. After undertaking the project, no employee joins the company. The company now still have these employees: $\{(1, 2), (2, 1), (3, 2)\}$.

Next, undertake the $2$-nd project. After undertaking the project, there are $2$ employees, whose occupation is $3$, and $1$ employee, whose occupation is $2$, joining the company. The company now have these employees: $\{(1, 2), (2, 2), (3, 4)\}$.

Next, undertake the $4$-th project. After undertaking the project, there are $3$ employees, whose occupation is $1$, joining the company. The company now have these employees: $\{(1, 5), (2, 2), (3, 4)\}$.

As the company does not have $3$ employees whose occupation is $2$, we cannot undertake the $3$-rd project.


title: [SDCPC2023] Orders

description:
A factory receives $n$ orders at the beginning of day $1$. The $i$-th order can be described as two integers $a_i$ and $b_i$, indicating that at the end of day $a_i$, the factory needs to deliver $b_i$ products to the customer.

Given that the factory can produce $k$ products each day, and at the beginning of day $1$ the factory has no product in stock, can the factory complete all orders?

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

The first line contains two integers $n$ and $k$ ($1 \le n \le 100$, $1 \le k \le 10^9$) indicating the number of orders and the number of products the factory can produce each day.

For the following $n$ lines, the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$) indicating that the $i$-th order require the factory to deliver $b_i$ products at the end of day $a_i$.

outputFormat: For each test case output one line. If the factory can complete all orders output $\texttt{Yes}$, otherwise output $\texttt{No}$.

translation:
**【题目描述】**

某工厂在第 $1$ 天开工之前收到了 $n$ 笔订单，第 $i$ 笔订单可以用两个整数 $a_i$ 和 $b_i$ 描述，表示工厂需要在第 $a_i$ 天结束时交付 $b_i$ 件货物。

已知工厂每天能生产 $k$ 件货物，且第 $1$ 天开工之前没有任何存货，问该工厂能否完成所有订单。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 100$）表示测试数据组数，对于每组测试数据：

第一行输入两个整数 $n$ 和 $k$（$1 \le n \le 100$，$1 \le k \le 10^9$）表示订单数量以及工厂每日能生产的货物数量。

对于接下来 $n$ 行，第 $i$ 行输入两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^9$）表示第 $i$ 笔订单要求在第 $a_i$ 天结束时交付 $b_i$ 件货物。

**【输出格式】**

每组数据输出一行。若工厂能完成所有订单输出 $\texttt{Yes}$，否则输出 $\texttt{No}$。

**【样例解释】**

对于第一组样例数据，工厂每天能生产 $5$ 件货物。
-  在第 $1$ 天结束时，工厂共有 $5$ 件货物，可以完成第 $2$ 笔订单。交付后，工厂剩余 $2$ 件货物。
-  在第 $6$ 天结束时，工厂又多生产了 $25$ 件货物，共有 $27$ 件货物，可以完成第 $1$ 和第 $3$ 笔订单。交付后，工厂剩余 $0$ 件货物。
- 在第 $8$ 天结束时，工厂又多生产了 $10$ 件货物，共有 $10$ 件货物，可以完成第 $4$ 笔订单。交付后，工厂剩余 $9$ 件货物。

对于第二组样例数据，工厂每天能生产 $100$ 件货物。
- 在第 $3$ 天结束时，工厂共有 $300$ 件货物，可以完成第 $1$ 笔订单。交付后，工厂剩余 $100$ 件货物。
- 在第 $4$ 天结束时，工厂又多生产了 $100$ 件货物，共有 $200$ 件货物，无法完成第 $2$ 笔订单。

hint:
For the first sample test case, the factory can produce $5$ products each day.

- At the end of day $1$, there are $5$ products in stock so the factory can complete the $2$-nd order. After delivery, there are $2$ products left in stock.
- At the end of day $6$, the factory produces $25$ more products. There are $27$ products in stock so the factory can complete the $1$-st and the $3$-rd order. After delivery, there are $0$ products left in stock.
- At the end of day $8$, the factory produces $10$ more products. There are $10$ products in stock so the factory can complete the $4$-th order. After delivery, there are $9$ products left in stock.

For the second sample test case, the factory can produce $100$ products each day.

- At the end of day $3$, there are $300$ products in stock and the factory can complete the $1$-st order. After delivery, there are $100$ products left in stock.
- At the end of day $4$, the factory produces $100$ more products. There are only $200$ products in stock so the factory cannot complete the $2$-nd order.


title: [SDCPC2023] Trie

description:
Recall the definition of a trie:

- A trie of size $n$ is a rooted tree with $n$ vertices and $(n - 1)$ edges, where each edge is marked with a character.
- Each vertex in a trie represents a string. Let $s(x)$ be the string vertex $x$ represents.
- The root of the trie represents an empty string. Let vertex $u$ be the parent of vertex $v$, and let $c$ be the character marked on the edge connecting vertex $u$ and $v$, we have $s(v) = s(u) + c$. Here $+$ indicates string concatenation, not the normal addition operation.
- The string each vertex represents is distinct.

We now present you a rooted tree with $(n + 1)$ vertices. The vertices are numbered $0, 1, \cdots, n$ and vertex $0$ is the root. There are $m$ key vertices in the tree where vertex $k_i$ is the $i$-th key vertex. It's guaranteed that all leaves are key vertices.

Please mark a lower-cased English letter on each edge so that the rooted tree changes into a trie of size $(n + 1)$. Let's consider the sequence $A = \{s(k_1), s(k_2), \cdots, s(k_m)\}$ consisting of all strings represented by the key vertices. Let $B = \{w_1, w_2, \cdots, w_m\}$ be the string sequence formed by sorting all strings in sequence $A$ from smallest to largest in lexicographic order. Please find a way to mark the edges so that sequence $B$ is minimized.

We say a string $P = p_1p_2\cdots p_x$ of length $x$ is lexicographically smaller than a string $Q = q_1q_2\cdots q_y$ of length $y$, if

- $x < y$ and for all $1 \le i \le x$ we have $p_i = q_i$, or
- there exists an integer $1 \le t \le \min(x, y)$ such that for all $1 \le i < t$ we have $p_i = q_i$, and $p_t < q_t$.

We say a string sequence $F = \{f_1, f_2, \cdots, f_m\}$ of length $m$ is smaller than a string sequence $G = \{g_1, g_2, \cdots, g_m\}$ of length $m$, if there exists an integer $1 \le t \le m$ such that for all $1 \le i < t$ we have $f_i = g_i$, and $f_t$ is lexicographically smaller than $g_t$.

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

The first line contains two integers $n$ and $m$ ($1 \le m \le n \le 2 \times 10^5$) indicating the number of vertices other than the root and the number of key vertices.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($0 \le a_i < i$) where $a_i$ is the parent of vertex $i$. It's guaranteed that each vertex has at most $26$ children.

The third line contains $m$ integers $k_1, k_2, \cdots, k_m$ ($1 \le k_i \le n$) where $k_i$ is the $i$-th key vertex. It's guaranteed that all leaves are key vertices, and all key vertices are distinct.

It's guaranteed that the sum of $n$ of all test cases will not exceed $2 \times 10^5$.

outputFormat: For each test case output one line containing one answer string $c_1c_2\cdots c_n$ consisting of lower-cased English letters, where $c_i$ is the letter marked on the edge between $a_i$ and $i$. If there are multiple answers strings so that sequence $B$ is minimized, output the answer string with the smallest lexicographic order.

translation:
**【题目描述】**

请回忆字典树的定义：

- 一棵大小为 $n$ 的字典树是一棵有 $n$ 个节点和 $(n - 1)$ 条边的有根树，每一条边都标有一个字符。
- 字典树中的每个节点都代表一个字符串，令 $s(x)$ 表示节点 $x$ 代表的字符串。
- 字典树的根代表的是空字符串。设节点 $u$ 为节点 $v$ 的父节点，设 $c$ 表示节点 $u$ 和 $v$ 之间的边上标有的字符，则 $s(v) = s(u) + c$。这里的 $+$ 代表字符串连接，而不是普通的加法。
- 所有节点代表的字符串互不相同。

给定一棵有 $(n + 1)$ 个节点的有根树，节点编号为 $0, 1, \cdots, n$，其中节点 $0$ 是根节点。树上共有 $m$ 个关键节点，其中第 $i$ 个关键节点的编号为 $k_i$。保证所有叶子节点都是关键节点。

请为每一条边标上一个小写字母，使得这棵有根树变为一棵大小为 $(n + 1)$ 的字典树。考虑所有关键节点代表的字符串构成的序列 $A = \{s(k_1), s(k_2), \cdots, s(k_m)\}$，设 $B = \{w_1, w_2, \cdots, w_m\}$ 是由序列 $A$ 中所有字符串按字典序从小到大排序后得到的字符串序列，您需要找到一个标记字母的方案，使得序列 $B$ 最小。

称长度为 $x$ 的字符串 $P = p_1p_2\cdots p_x$ 的字典序小于长度为 $y$ 的字符串 $Q = q_1q_2\cdots q_y$，若

- $x < y$ 且对于所有 $1 \le i \le x$ 有 $p_i = q_i$，或者
- 存在一个整数 $1 \le t \le \min(x, y)$，对于所有 $1 \le i < t$ 有 $p_i = q_i$，且 $p_t < q_t$。

称长度为 $m$ 的字符串序列 $F = \{f_1, f_2, \cdots, f_m\}$ 小于长度为 $m$ 的字符串序列 $G = \{g_1, g_2, \cdots, g_m\}$，若存在一个整数 $1 \le t \le m$，对于所有 $1 \le i < t$ 有 $f_i = g_i$，且 $f_t$ 的字典序小于 $g_t$ 的字典序。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入两个正整数 $n$ 和 $m$（$1 \le m \le n \le 2 \times 10^5$）表示除了根节点以外的节点数量和关键节点的数量。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$0 \le a_i < i$），其中 $a_i$ 代表节点 $i$ 的父节点。保证每个节点至多有 $26$ 个子节点。

第三行输入 $m$ 个整数 $k_1, k_2, \cdots, k_m$（$1 \le k_i \le n$），其中 $k_i$ 代表第 $i$ 个关键节点的编号。保证所有叶子节点都是关键节点，且没有重复的关键节点。

保证所有测试数据 $n$ 之和不超过 $2 \times 10^5$。

**【输出格式】**

每组数据输出一行一个由小写字母组成的答案字符串 $c_1c_2\cdots c_n$，其中 $c_i$ 表示节点 $a_i$ 到 $i$ 的边上标有的小写字母。若有多种答案字符串使得字符串序列 $B$ 最小，请输出字典序最小的答案字符串。

**【样例解释】**

第一组样例数据的答案如下图所示。

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

其中，节点 $1$ 代表的字符串为 ``a``，节点 $4$ 代表的字符串为 ``aba``，节点 $3$ 代表的字符串为 ``aa``，节点 $5$ 代表的字符串为 ``abb``。因此 $B = \{$``a``, ``aa``, ``aba``, ``abb``$\}$。

hint:
The answer of the first sample test case is shown as follows.

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

The string represented by vertex $1$ is ``a``. The string represented by vertex $4$ is ``aba``. The string represented by vertex $3$ is ``aa``. The string represented by vertex $5$ is ``abb``. So $B = \{$``a``, ``aa``, ``aba``, ``abb``$\}$.


title: [SDCPC2023] Fast and Fat

description:
You're participating in a team competition of trail running. There are $n$ members in your team where $v_i$ is the speed of the $i$-th member and $w_i$ is his/her weight.

The competition allows each team member to move alone or carry another team member on their back. When member $i$ carries member $j$, if member $i$'s weight is greater than or equal to member $j$'s weight, member $i$'s speed remains unchanged at $v_i$. However, if member $i$'s weight is less than member $j$'s weight, member $i$'s speed will decrease by the difference of their weight and becomes $v_i - (w_j - w_i)$. If member $i$'s speed will become negative, then member $i$ is not able to carry member $j$. Each member can only carry at most one other member. If a member is being carried, he/she cannot carry another member at the same time.

For all members not being carried, the speed of the slowest member is the speed of the whole team. Find the maximum possible speed of the whole team.

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

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

For the following $n$ lines, the $i$-th line contains two integers $v_i$ and $w_i$ ($1 \le v_i, w_i \le 10^9$) indicating the speed and weight of the $i$-th member.

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

outputFormat: For each test case output one line containing one integer indicating the maximum speed of the whole team.

translation:
**【题目描述】**

您正在参加一场团体越野比赛。您的队伍共有 $n$ 名队员，其中第 $i$ 名队员的速度为 $v_i$，体重为 $w_i$。

比赛允许每名队员独立行动，也允许一名队员背着另一名队员一起行动。当队员 $i$ 背着队员 $j$ 时，如果队员 $i$ 的体重大于等于队员 $j$，则队员 $i$ 的移动速度不会变化，仍然为 $v_i$；如果队员 $i$ 的体重小于队员 $j$，则队员 $i$ 的移动速度会减去两者的体重差值，即变为 $v_i - (w_j - w_i)$。如果队员 $i$ 的移动速度将变为负数，则队员 $i$ 无法背起队员 $j$。每名队员最多只能背负另一名队员，被背负的队员无法同时背负其他队员。

所有未被背负的队员中，最慢的队员的速度，即为整个队伍的速度。求整个队伍能达到的最大速度。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 10^5$）表示队员人数。

对于接下来 $n$ 行，第 $i$ 行输入两个整数 $v_i$ 和 $w_i$（$1 \le v_i, w_i \le 10^9$）表示第 $i$ 名队员的速度和体重。

保证所有数据中 $n$ 之和不超过 $10^5$。

**【输出格式】**

每组数据输出一个整数，表示整个队伍可以达到的最大速度。

**【样例解释】**

样例数据的最优策略如下：

- 队员 $1$ 背起队员 $4$。因为 $w_1 > w_4$，因此队员 $1$ 速度不变，仍然为 $10$。
- 队员 $3$ 背起队员 $2$。因为 $w_3 < w_2$，因此队员 $3$ 的速度减少 $w_2 - w_3 = 2$，即速度变为 $10 - 2 = 8$。
- 队员 $5$ 独立行动，速度为 $9$。

因此答案为 $8$。

hint:
The optimal strategy for the sample test case is shown as follows:

- Let member $1$ carry member $4$. As $w_1 > w_4$, member $1$'s speed remains unchanged, which is still $10$.
- Let member $3$ carry member $2$. As $w_3 < w_2$, member $3$'s speed will decrease by $w_2 - w_3 = 2$ and becomes $10 - 2 = 8$.
- Member $5$ shall move alone. His/Her speed is $9$.

So the answer is $8$.


title: [SDCPC2023] Math Problem

description:
Given two positive integers $n$ and $k$, you can perform the following two types of operations any number of times (including zero times):

- Choose an integer $x$ which satisfies $0 \leq x < k$, and change $n$ into $k\cdot n+x$. It will cost you $a$ coins to perform this operation once. The integer $x$ you choose each time can be different.
- Change $n$ into $\lfloor \frac{n}{k} \rfloor$. It will cost you $b$ coins to perform this operation once. Note that $\lfloor \frac{n}{k} \rfloor$ is the largest integer which is less than or equal to $\frac{n}{k}$.

Given a positive integer $m$, calculate the minimum number of coins needed to change $n$ into a multiple of $m$. Please note that $0$ is a multiple of any positive integer.

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

The first line contains five integers $n$, $k$, $m$, $a$, $b$ ($1\leq n\leq 10^{18}$, $1\leq k, m, a, b\leq 10^9$).

outputFormat: For each test case output one line containing one integer, indicating the minimum number of coins needed to change $n$ into a multiple of $m$. If this goal cannot be achieved, output $-1$ instead.

translation:
**【题目描述】**

给定两个正整数 $n$ 和 $k$，您可以进行以下两种操作任意次（包括零次）：

- 选择一个整数 $x$ 满足 $0 \leq x < k$，将 $n$ 变为 $k\cdot n+x$。该操作每次花费 $a$ 枚金币。每次选择的整数 $x$ 可以不同。
- 将 $n$ 变为 $\lfloor \frac{n}{k} \rfloor$。该操作每次花费 $b$ 枚金币。其中 $\lfloor \frac{n}{k} \rfloor$ 表示小于等于 $\frac{n}{k}$ 的最大整数。

给定正整数 $m$，求将 $n$ 变为 $m$ 的倍数最少需要花费几枚金币。请注意：$0$ 是任何正整数的倍数。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$（$1\leq T\leq 10^5$）表示测试数据组数。对于每组测试数据：

第一行输入五个正整数 $n$，$k$，$m$，$a$，$b$（$1\leq n\leq 10^{18}$，$1\leq k, m, a, b\leq 10^9$）。

**【输出格式】**

每组数据输出一行一个整数，代表将 $n$ 变为 $m$ 的倍数最少需要花费几枚金币。如果无法完成该目标，输出 $-1$。

**【样例解释】**

对于第一组样例数据，一开始 $n=101$，最优操作如下：

- 首先进行一次第二种操作，将 $n$ 变为 $\lfloor \frac{n}{4} \rfloor=25$，花费 $5$ 枚金币。
- 接下来进行一次第一种操作，选择 $x = 3$，将 $n$ 变为 $4\cdot n+3=103$，花费 $3$ 枚金币。
- 接下来进行一次第一种操作，选择 $x = 2$，将 $n$ 变为 $4\cdot n+2=414$，花费 $3$ 枚金币。
- 此时 $414=2 \times 207$，满足 $n$ 是 $m$ 的倍数。共花费 $5+3+3=11$ 枚金币。

对于第二组样例数据，进行两次第二种操作将 $n$ 变为 $0$。共花费 $1 + 1 = 2$ 枚金币。

对于第三组样例数据，因为 $n = 114 = 6 \times 19$ 已经是 $m$ 的倍数，因此无需进行任何操作。共花费 $0$ 枚金币。

hint:
For the first sample test case, initially $n=101$. The optimal steps are shown as follows:

- Firstly, perform the second type of operation once. Change $n$ into $\lfloor \frac{n}{4} \rfloor=25$. This step costs $5$ coins.
- Then, perform the first type of operation once. Choose $x = 3$ and change $n$ into $4\cdot n+3=103$. This step costs $3$ coins.
- Then, perform the first type of operation once. Choose $x = 2$ and change $n$ into $4\cdot n+2=414$. This step costs $3$ coins.
- As $414=2 \times 207$, $n$ is a multiple of $m$. The total cost is $5+3+3=11$ coins.

For the second sample test case, perform the second type of operation twice will change $n$ into $0$. The total cost is $1 + 1 = 2$ coins.

For the third sample test case, as $n = 114 = 6 \times 19$ is already a multiple of $m$, no operation is needed. The total cost is $0$ coins.


title: [SDCPC2023] Colorful Segments

description:
Consider $n$ segments on the number axis, where the left endpoint of the $i$-th segment is $l_i$ and the right endpoint is $r_i$. Each segment has a color where the color of the $i$-th segment is $c_i$ ($0 \le c_i \le 1$). There are two types of colors, where $c_i = 0$ indicates a red segment and $c_i = 1$ indicates a blue segment.

You need to choose some segments (you can also choose no segments at all). If any two chosen segments overlap, then they must have the same color.

Calculate the number of ways to choose segments.

We say segment $i$ overlaps with segment $j$, if there exists a real number $x$ satisfying both $l_i \le x \le r_i$ and $l_j \le x \le r_j$.

We say two ways of choosing segments are different, if there exists an integer $1 \le k \le n$ such that the $k$-th segment is chosen in one of the ways and is not chosen in the other.

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

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

For the following $n$ lines, the $i$-th line contains three integers $l_i$, $r_i$ and $c_i$ ($1 \le l_i \le r_i \le 10^9$, $0 \le c_i \le 1$) indicating the left and right endpoints and the color of the $i$-th segment.

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

outputFormat: For each test case output one line containing one integer indicating the number of ways to choose segments. As the answer may be large, please output the answer modulo $998244353$.

translation:
**【题目描述】**

考虑数轴上的 $n$ 条线段，其中第 $i$ 条线段的左端点为 $l_i$，右端点为 $r_i$。每一条线段都被涂上了颜色，其中第 $i$ 条线段的颜色为 $c_i$（$0 \le c_i \le 1$）。颜色共有两种，$c_i = 0$ 代表一条红色的线段，而 $c_i = 1$ 代表一条蓝色的线段。

您需要选择若干条线段（可以不选择任何线段）。如果您选择的任意两条线段有重合，则这两条线段的颜色必须相同。

求选择线段的不同方案数。

称第 $i$ 条线段和第 $j$ 条线段有重合，若存在一个实数 $x$ 同时满足 $l_i \le x \le r_i$ 且 $l_j \le x \le r_j$。

称两种选择线段的方案是不同的，若存在一个整数 $1 \le k \le n$，满足第 $k$ 条线段在其中一个方案中被选择，而在另一个方案中没有被选择。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 10^5$）表示线段的数量。

对于接下来 $n$ 行，第 $i$ 行输入三个整数 $l_i$，$r_i$ 和 $c_i$（$1 \le l_i \le r_i \le 10^9$，$0 \le c_i \le 1$）表示第 $i$ 条线段的左右端点以及颜色。

保证所有数据 $n$ 之和不超过 $5 \times 10^5$。

**【输出格式】**

每组数据输出一行一个整数表示选择线段的不同方案数。由于答案可能很大，请将答案对 $998244353$ 取模后输出。

**【样例解释】**

对于第一组样例数据，您不能同时选择第 $1$ 和第 $2$ 条线段，也不能同时选择第 $2$ 和第 $3$ 条线段，因为它们有重合且颜色不同。

对于第二组样例数据，因为第 $2$ 条线段与第 $1$ 和第 $3$ 条线段都不重合，因此您可以任意选择线段。

hint:
For the first sample test case, you cannot choose the $1$-st and the $2$-nd segment, or the $2$-nd and the $3$-rd segment at the same time, because they overlap with each other and have different colors.

For the second sample test case, as the $2$-nd segment does not overlap with the $1$-st and the $3$-rd segment, you can choose them arbitrary.


title: [GDCPC2023] Programming Contest

description:
Guangdong Province is one of the earliest province in China which holds its own provincial collegiate programming contest. Sun Yat-sen University hosted the first Guangdong Collegiate Programming Contest in year $2003$. After that, other universities in Guangdong, such as South China Agricultural University, South China University of Technology and South China Normal University, also hosted the contest. The contest is held once a year except for year $2020$ due to the epidemic. In year $2023$, Shenzhen Technology University will host the twentieth Guangdong Collegiate Programming Contest. We are looking forward to seeing participants' outstanding performance!

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

In another world, a programming contest has been held once a year since year $y_1$, except for the $n$ years $s_1, s_2, \cdots, s_n$ when it was not held due to special reasons.

Calculate the number of times the competition has been held up to year $y_2$ (inclusive).

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

The first line contains an integer $y_1$ ($1970 \le y_1 \le 9999$) indicating the first year when the contest was held.

The second line first contains an integer $n$ ($0 \le n \le 100$) indicating the number of years the contest was not held. Then $n$ integers $s_1, s_2, \cdots, s_n$ ($y_1 < s_i \le 9999$) follow, indicating the years when the contest was not held. These years are given in increasing order and have no duplicates.

The third line contains an integer $y_2$ ($y_1 \le y_2 \le 9999$). It's guaranteed that $y_2$ is not a year when the contest was not held.

outputFormat: For each test case output one line containing one integer, indicating the number of times the competition has been held up to year $y_2$ (inclusive).

translation:
**【题目描述】**

广东省是全国较早一批将程序设计竞赛引入省内大学生竞赛体系的省份之一。$2003$ 年，中山大学承办了第一届广东省大学生程序设计竞赛。此后，华南农业大学、华南理工大学、华南师范大学等省内高校也先后承办了此赛事，除 $2020$ 年因疫情停办外，每年一届。$2023$ 年，深圳技术大学将承办第二十届广东省大学生程序设计竞赛，让我们期待选手们出色的表现！

在另一个世界中，某程序设计竞赛自 $y_1$ 年起开始举办。除了 $s_1, s_2, \cdots, s_n$ 这 $n$ 年由于特殊原因无法举办之外，其他年份每年举办一次。

求 $y_2$ 年是该竞赛的第几次举办。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 20$）表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $y_1$（$1970 \le y_1 \le 9999$），表示该竞赛第一次举办的年份。

第二行首先输入一个整数 $n$（$0 \le n \le 100$）表示该竞赛停办的年份数，之后输入 $n$ 个整数 $s_1, s_2, \cdots, s_n$（$y_1 < s_i \le 9999$）表示该竞赛的停办年份。停办年份按递增顺序给出，且没有重复的年份。

第三行输入一个整数 $y_2$（$y_1 \le y_2 \le 9999$）。保证 $y_2$ 不是停办年份之一。

**【输出格式】**

每组数据输出一行一个整数，表示 $y_2$ 年是该竞赛的第几次举办。

**【样例解释】**

对于第一组样例数据，如题目描述中所述，答案为 $20$。

对于第二组样例数据，由于 $2003$ 就是该竞赛第 $1$ 次举办的年份，因此答案为 $1$。

对于第三组样例数据，由于竞赛从未停办，因此答案为 $3456 - 2345 + 1 = 1112$。

对于第四组样例数据，该竞赛前 $5$ 次举办的年份为 $3000$，$3002$，$3005$，$3006$ 与 $3007$。因此答案为 $5$。

hint:
For the first sample test case, as described in the problem description, the answer is $20$.

For the second sample test case, because year $2003$ is the $1$-st year when the contest was held, the answer is $1$.

For the third sample test case, because the contest was held every year, the answer is $3456 - 2345 + 1 = 1112$.

For the fourth sample test case, the first $5$ years when the contest was held is $3000$, $3002$, $3005$, $3006$ and $3007$. So the answer is $5$.


title: [GDCPC2023] Base Station Construction

description:
China Mobile Shenzhen Branch was registered in $1999$. Four years later, Guangdong Collegiate Programming Contest was held for the first time. China Mobile Shenzhen Branch, along with Guangdong Collegiate Programming Contest, witnesses the prosperity and development of the computer industry in Guangdong.

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

During the construction of a communication line, it is critical to carefully choose the locations for base stations. The distance from west to east of a city is $n$ kilometers. The engineers have investigated the cost to build a base station at $1, 2, \cdots, n$ kilometers from west to east, which are $a_1, a_2, \cdots, a_n$ respectively.

To ensure communication quality for the residents, the locations of base stations also need to meet $m$ requirements. The $i$-th requirement can be represented as a pair of integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$), indicating that there must be at least $1$ base station between $l_i$ kilometers and $r_i$ kilometers (both inclusive) from west to east.

As the chief engineer, you need to decide the number of base stations to build and their locations, and finally calculate the minimum total cost to satisfy all requirements.

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

The first line contains an integer $n$ ($1 \le n \le 5 \times 10^5$) indicating the distance from west to east of the city.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$) where $a_i$ indicates the cost to build a base station at $i$ kilometers from west to east.

The third line contains an integer $m$ ($1 \le m \le 5 \times 10^5$) indicating the number of requirements.

For the following $m$ lines, the $i$-th line contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) indicating that there must be at least $1$ base station between $l_i$ kilometers and $r_i$ kilometers (both inclusive) from west to east.

It's guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $5 \times 10^5$.

outputFormat: For each test case output one line containing one integer indicating the minimum total cost to satisfy all requirements.

translation:
**【题目描述】**

中国移动通信集团广东有限公司深圳分公司（以下简称``深圳移动``）于 $1999$ 年正式注册。四年后，广东省大学生程序设计竞赛第一次举办。深圳移动与广东省大学生程序设计竞赛一起见证了广东省计算机行业的兴旺与发展。

在建设通信线路的过程中，信号基站的选址是一个非常关键的问题。某城市从西到东的距离为 $n$ 千米，工程师们已经考察了在从西往东 $1, 2, \cdots, n$ 千米的位置建设基站的成本，分别是 $a_1, a_2, \cdots, a_n$。

为了保证居民的通信质量，基站的选址还需要满足 $m$ 条需求。第 $i$ 条需求可以用一对整数 $l_i$ 和 $r_i$ 表示（$1 \le l_i \le r_i \le n$），代表从西往东 $l_i$ 千米到 $r_i$ 千米的位置之间（含两端）至少需要建设 $1$ 座基站。

作为总工程师，您需要决定基站的数量与位置，并计算满足所有需求的最小总成本。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 5 \times 10^5$）表示城市从西到东的距离。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le 10^9$），其中 $a_i$ 表示在从西往东 $i$ 千米的位置建设基站的成本。

第三行输入一个整数 $m$（$1 \le m \le 5 \times 10^5$）表示需求的数量。

对于接下来 $m$ 行，第 $i$ 行输入两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）表示从西往东 $l_i$ 千米到 $r_i$ 千米的位置之间（含两端）至少需要建设 $1$ 座基站。

保证所有数据 $n$ 之和与 $m$ 之和均不超过 $5 \times 10^5$。

**【输出格式】**

每组数据输出一行一个整数，表示满足所有需求的最小总成本。

**【样例解释】**

对于第一组样例数据，最优方案是在从西往东 $2$ 千米和 $5$ 千米的位置建设基站。总成本为 $2 + 100 = 102$。

对于第二组样例数据，最优方案是在从西往东 $2$ 千米和 $4$ 千米的位置建设基站。总成本为 $3 + 2 = 5$。

hint:
For the first sample test case the optimal solution is to build base stations at $2$ kilometers and $5$ kilometers from west to east. The total cost is $2 + 100 = 102$.

For the second sample test case the optimal solution is to build base stations at $2$ kilometers and $4$ kilometers from west to east. The total cost is $3 + 2 = 5$.


title: [GDCPC2023] Trading

description:
Twenty years ago, the northern section of Beijing Road Pedestrian Street in Guangzhou unearthed eleven layers of pavement from the Tang Dynasty to the Republic of China, and the southern section excavated the foundation of Gongbei Building with five layers from the Song Dynasty to the Ming and Qing Dynasties. This proves that Beijing Road has a long history as a commercial pedestrian street since the Song Dynasty. At the same time, the first Guangdong Province Collegiate Programming Contest was also held at Sun Yat-sen University in Guangzhou. Today, twenty years later, Beijing Road Pedestrian Street has become one of Guangzhou's most famous tourist attractions and shopping destinations, and the Guangdong Province Collegiate Programming Contest is also celebrating its twentieth birthday.

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

There are $n$ stores in the pedestrian street which buy and sell the same type of product. The buying and selling price of one such product in the $i$-th store are both $a_i$. To avoid over-trading, the pedestrian street has a regulation, that one can only trade $b_i$ times in the $i$-th store (each buy or each sell both count as a trade) and can only trade one product each time.

You're going to earn money by buying and selling the products in the pedestrian street. If you have infinite amount of money at the beginning (that is to say, you can't be short of money when buying a product), what's the maximum total profit you can make? More precisely, \textit{profit} means the total amount of money earned by selling the products, minus the total amount of money spent for buying the products.

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

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

For the following $n$ lines, the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^6$) indicating the price and the maximum number of trades in the $i$-th store.

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

outputFormat: For each test case output one line containing one integer indicating the maximum total profit.

translation:
**【题目描述】**

二十年前，广州的北京路步行街北段出土了自唐代直到民国时期的十一层路面，南段则发掘出宋代至明清时期共五层的拱北楼建筑基址，佐证了北京路自宋代以来作为商业步行街的悠久历史；同时第一届广东省大学生程序设计竞赛也在位处广州的中山大学举办。二十年后的今天，北京路步行街已成为广州最负盛名的景点和购物胜地之一，而广东省大学生程序设计竞赛也迎来了自己的二十岁生日。

在步行街中，有 $n$ 间商店买卖同一种商品，第 $i$ 间商店一件商品的收购价和出售价均为 $a_i$ 元。为了防止过度交易，步行街有一个规定：您在第 $i$ 间商店最多进行 $b_i$ 次交易（一次买或一次卖均计为一次交易），且每次只能交易一件商品。

您准备通过在步行街中买卖这种商品来赚钱。假如初始时有无限的金钱（也就是说，不会因为钱不够而买不了一件商品），您最多能在步行街中赚到多少总利润？具体来说，``利润``指的是卖出商品获得的金钱总额，减去购买商品花费的金钱总额。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$1 \le n \le 10^5$），表示商店的数量。

对于接下来 $n$ 行，第 $i$ 行输入两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^6$），分别表示第 $i$ 间商店的商品价格，以及该商店可以交易的最大次数。

保证所有数据 $n$ 之和不超过 $10^6$。

**【输出格式】**

每组数据输出一行一个整数，表示在步行街中赚到的最大总利润。

**【样例解释】**

对于第一组样例数据，最优方案是在第 $1$ 间商店买入 $2$ 件商品，在第 $3$ 间商店买入 $4$ 件商品，在第 $2$ 间商店卖出 $5$ 件商品，在第 $4$ 间商店卖出 $1$ 件商品。总利润为 $30 \times 5 + 50 \times 1 - 10 \times 2 - 20 \times 4 = 100$。

对于第二组样例数据，由于所有商店的商品价格都相同，因此无法获得利润。

hint:
For the first sample test case, the optimal strategy is to buy $2$ products from the $1$-st store, buy $4$ products from the $3$-rd store, sell $5$ products to the $2$-nd store and sell $1$ product to the $4$-th store. The total profit is $30 \times 5 + 50 \times 1 - 10 \times 2 - 20 \times 4 = 100$.

For the second sample test case, because all stores have the same price, there is no profit.


title: [GDCPC2023] New Houses

description:
With the construction and development of Guangdong, more and more people choose to come to Guangdong to start a new life. In a recently built community, there will be $n$ people moving into $m$ houses which are arranged in a row. The houses are numbered from $1$ to $m$ (both inclusive). House $u$ and $v$ are neighboring houses, if and only if $|u-v|=1$. We need to assign each person to a house so that no two people will move into the same house. If two people move into a pair of neighboring houses, they will become neighbors of each other.

Some people like to have neighbors while some don't. For the $i$-th person, if he has at least one neighbor, his happiness will be $a_i$; Otherwise if he does not have any neighbor, his happiness will be $b_i$.

As the planner of this community, you need to maximize the total happiness.

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

The first line contains two integers $n$ and $m$ ($1 \le n \le 5 \times 10^5$, $1 \le m \le 10^9$, $n \le m$) indicating the number of people and the number of houses.

For the following $n$ lines, the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$) indicating the happiness of the $i$-th person with and without neighbors.

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

outputFormat: For each test case output one line containing one integer indicating the maximum total happiness.

translation:
**【题目描述】**

随着广东的建设与发展，越来越多人选择来到广东开始新生活。在一片新建的小区，有 $n$ 个人要搬进 $m$ 栋排成一行的房子，房子的编号从 $1$ 到 $m$（含两端）。房子 $u$ 和 $v$ 相邻，当且仅当 $|u-v|=1$。我们需要为每一个人安排一栋房子，要求所有人入住的房子互不相同。若两个人住进了一对相邻的房子，则这两个人互为邻居。

有的人喜欢自己有邻居，而有的人不喜欢。对于第 $i$ 个人，如果他有至少一位邻居，则他的满意度为 $a_i$；否则如果他没有邻居，则他的满意度为 $b_i$。

您作为小区的规划者，需要最大化所有人的总满意度。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入两个整数 $n$ 和 $m$（$1 \le n \le 5 \times 10^5$，$1 \le m \le 10^9$，$n \le m$），表示人数和房子数。

对于接下来的 $n$ 行，第 $i$ 行输入两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^9$），表示第 $i$ 个人在有邻居和没有邻居时的满意度。

保证所有数据 $n$ 之和不超过 $10^6$。

**【输出格式】**

每组数据输出一行一个整数表示最大总满意度。

**【样例解释】**

对于第一组样例数据，最优方案是让第 $1$ 个人入住房子 $1$，第 $2$ 到 $4$ 个人入住房子 $3$ 到 $5$。这样，第 $1$ 个人没有邻居，而第 $2$ 到 $4$ 个人都有邻居。答案为 $100 + 100 + 100 + 100 = 400$。当然，也可以让第 $2$ 到 $4$ 个人入住房子 $1$ 到 $3$，第 $1$ 个人入住房子 $5$，也能得到 $400$ 的总满意度。

对于第二组样例数据，由于只有 $2$ 栋房子，因此第 $1$ 和第 $2$ 个人必须成为邻居。答案为 $1 + 1 = 2$。

对于第三组样例数据，最优方案是让第 $1$ 个人入住房子 $1$，第 $2$ 个人入住房子 $3$。这样，两个人都没有邻居。答案为 $50 + 1000 = 1050$。

hint:
For the first sample test case, the optimal strategy is to let person $1$ move into house $1$ and let person $2$ to $4$ move into house $3$ to $5$. Thus, person $1$ have no neighbors while person $2$ to $4$ have neighbors. The answer is $100 + 100 + 100 + 100 = 400$. Of course, we can also let person $2$ to $4$ move into house $1$ to $3$ and let person $1$ move into house $5$. This will also give us $400$ total happiness.

For the second sample test case, as there are only $2$ houses, person $1$ and $2$ have to be neighbors. The answer is $1 + 1 = 2$.

For the third sample test case, the optimal strategy is to let person $1$ move into house $1$ and let person $2$ move into house $3$. Thus, both of them have no neighbors. The answer is $50 + 1000 = 1050$.


title: [GDCPC2023] New but Nostalgic Problem

description:
Given $n$ strings $w_1, w_2, \cdots, w_n$, please select $k$ strings among them, so that the lexicographic order of string $v$ is minimized, and output the optimal string $v$. String $v$ satisfies the following constraint: $v$ is the longest common prefix of two selected strings with different indices. Also, $v$ is the lexicographically largest string among all strings satisfying the constraint.

More formally, let $\mathbb{S}$ be a set of size $k$, where all the elements in the set are integers between $1$ and $n$ (both inclusive) and there are no duplicated elements. Let $\text{lcp}(w_i, w_j)$ be the longest common prefix of string $w_i$ and $w_j$, please find a set $\mathbb{S}$ to minimize the lexicographic order of the following string $v$ and output the optimal string $v$.

$$
v = \max\limits_{i \in \mathbb{S}, j \in \mathbb{S}, i \ne j} \text{lcp}(w_i, w_j)
$$

In the above expression, $\max$ is calculated by comparing the lexicographic order of strings.

Recall that:
- String $p$ is a prefix of string $s$, if we can append some number of characters (including zero characters) at the end of $p$ so that it changes to $s$. Specifically, empty string is a prefix of any string.
- The longest common prefix of string $s$ and string $t$ is the longest string $p$ such that $p$ is a prefix of both $s$ and $t$. For example, the longest common prefix of ``abcde`` and ``abcef`` is ``abc``, while the longest common prefix of ``abcde`` and ``bcdef`` is an empty string.
- String $s$ is lexicographically smaller than string $t$ ($s \ne t$), if
  - $s$ is a prefix of $t$, or
  - $s_{|p| + 1} < t_{|p| + 1}$, where $p$ is the longest common prefix of $s$ and $t$, $|p|$ is the length of $p$, $s_i$ is the $i$-th character of string $s$, and $t_i$ is the $i$-th character of string $t$.
- Specifically, empty string is the string with the smallest lexicographic order.

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

The first line contains two integers $n$ and $k$ ($2\leq n\leq 10^6$, $2\leq k\leq n$) indicating the total number of strings and the number of strings to be selected.

For the following $n$ lines, the $i$-th line contains a string $w_i$ ($1\leq |w_i|\leq 10^6$) consisting of lower-cased English letters.

It's guaranteed that the total length of all strings of all test cases will not exceed $10^6$.

outputFormat: For each test case output one line containing one string indicating the answer. Specifically, if the answer is an empty string, print $\texttt{EMPTY}$.

translation:
**【题目描述】**

给定 $n$ 个字符串 $w_1, w_2, \cdots, w_n$，请选出恰好 $k$ 个字符串，最小化字符串 $v$ 的字典序，并输出这个最优的字符串 $v$。其中 $v$ 满足以下条件：$v$ 是被选出的字符串中，某两个编号不同的字符串的最长公共前缀。而且，$v$ 是所有满足条件的字符串中，字典序最大的字符串。

更正式地，令 $\mathbb{S}$ 表示一个大小为 $k$ 的集合，集合中的元素均为从 $1$ 到 $n$ 的整数（含两端），且没有重复的元素。令 $\text{lcp}(w_i, w_j)$ 表示字符串 $w_i$ 和 $w_j$ 的最长公共前缀，您需要找到一个集合 $\mathbb{S}$ 以最小化下述字符串 $v$ 的字典序，并输出这个最优的字符串 $v$。

$$
v = \max\limits_{i \in \mathbb{S}, j \in \mathbb{S}, i \ne j} \text{lcp}(w_i, w_j)
$$

上式中的 $\max$ 通过字典序比较两个字符串。

请回忆：
- 称字符串 $p$ 是字符串 $s$ 的前缀，若可以在 $p$ 的末尾添加若干个字符（包括零个字符）将它变成 $s$。特别地，空字符串是任意字符串的前缀。
- 字符串 $s$ 和 $t$ 的最长公共前缀是一个最长的字符串 $p$，满足 $p$ 既是 $s$ 的前缀，又是 $t$ 的前缀。例如，``abcde`` 与``abcef`` 的最长公共前缀为 ``abc``，而 ``abcde`` 与 ``bcdef`` 的最长公共前缀为空字符串。
- 称字符串 $s$ 的字典序小于字符串 $t$（$s \ne t$），若
  - $s$ 是 $t$ 的前缀，或
  - $s_{|p| + 1} < t_{|p| + 1}$，其中 $p$ 为 $s$ 和 $t$ 的最长公共前缀，$|p|$ 为 $p$ 的长度，$s_i$ 表示字符串 $s$ 的第 $i$ 个字符，$t_i$ 表示字符串 $t$ 的第 $i$ 个字符。
- 特别地，空字符串是字典序最小的字符串。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入两个整数 $n$ 和 $k$（$2\leq n\leq 10^6$，$2\leq k\leq n$），表示字符串的总数和需要选择的字符串的数量。

对于接下来 $n$ 行，第 $i$ 行输入一个由小写字母构成的字符串 $w_i$（$1\leq |w_i|\leq 10^6$）。

保证所有数据中字符串长度之和不超过 $10^6$。

**【输出格式】**

每组数据输出一行一个字符串表示答案。特别地，若答案为空字符串，输出 $\texttt{EMPTY}$。

samples:
2
5 3
gdcpc
gdcpcpcp
suasua
suas
sususua
3 3
a
b
c


title: [GDCPC2023] Traveling in Cells

description:
There are $n$ cells arranged in a row. The $i$-th cell has a color $c_i$ and contains a ball with value $v_i$.

You're going to travel several times in the cells. For each travel, you'll be given an integer $x$ and a set of colors $\mathbb{A} = \{a_1, a_2, \cdots, a_k\}$ where $c_x \in \mathbb{A}$. The travel starts from cell $x$. During the travel, if you're located in cell $i$ you can next move to cell $(i - 1)$ or $(i + 1)$. Note that you can't move out of these $n$ cells. Also at any time, the color of cell you're located in must belong to set $\mathbb{A}$.

When you're in cell $i$, you can choose to remove the ball in the cell and gain its value $v_i$. As there is only one ball in each cell, you can only remove the ball from each cell once.

Your task is to process $q$ operations in order. Each operation is one of the following three types:

- $1\; p \; x$: Change $c_p$ to $x$.
- $2\; p \; x$: Change $v_p$ to $x$.
- $3\; x\; k\; a_1\; a_2 \; \ldots\; a_k$: Given the starting cell $x$ and the color set $\mathbb{A} = \{a_1, a_2, \cdots, a_k\}$ of a travel, imagine that you're going on this travel, calculate the maximum total value you can gain. Note that this travel is only an imagination, thus the balls won't be truely removed. That is, all queries are independent.

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

The first line contains two integers $n$ and $q$ ($1 \leq n \leq 10^5$, $1 \leq q \leq 10^5$) indicating the number of cells and the number of operations.

The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq n$) where $c_i$ is the initial color of the $i$-th cell.

The third line contains $n$ integers $v_1, v_2, \ldots, v_n$ ($1 \leq v_i \leq 10^9$) where $v_i$ is the initial value of ball in the $i$-th cell.

For the following $q$ lines, the $i$-th line describes the $i$-th operation. The input format is listed as follows:

- $1\; p\; x$: $1 \leq p \leq n$ and $1 \leq x \leq n$.
- $2\; p\; x$: $1 \leq p \leq n$ and $1 \leq x \leq 10^9$.
- $3\; x\; k\; a_1\; a_2\; \ldots \; a_k$: $1 \leq x \leq n$, $1 \leq a_1 < a_2 < \ldots < a_k \leq n$ and $c_x \in \{a_1, a_2, \cdots, a_k\}$.

It's guaranteed that neither the sum of $n$ nor the sum of $q$ of all test cases will exceed $3 \times 10^5$. Also the sum of $k$ of all test cases will not exceed $10^6$.

outputFormat: For each operation of type $3$ output one line containing one integer, indicating the maximum total value you can gain.

translation:
**【题目描述】**

有 $n$ 个格子排成一行，第 $i$ 个格子的颜色为 $c_i$，上面放置着一个权值为 $v_i$ 的球。

您将要在格子中进行若干次旅行。每次旅行时，您会得到旅行的起点 $x$ 与一个颜色集合 $\mathbb{A} = \{a_1, a_2, \cdots, a_k\}$，且保证 $c_x \in \mathbb{A}$。旅行将从第 $x$ 个格子上开始。在旅行期间，如果您在格子 $i$ 处，那么您可以向格子 $(i - 1)$ 或 $(i + 1)$ 处移动，但不能移动到这 $n$ 个格子之外。且在任意时刻，您所处的格子的颜色必须在集合 $\mathbb{A}$ 中。

当您位于格子 $i$ 时，您可以选择将格子上的球取走，并获得 $v_i$ 的权值。由于每个格子上只有一个球，因此一个格子上的球只能被取走一次。

您的任务是依次处理 $q$ 次操作，每次操作形如以下三种操作之一：

- $1\; p \; x$：将 $c_p$ 修改为 $x$。
- $2\; p \; x$：将 $v_p$ 修改为 $x$。
- $3\; x\; k\; a_1\; a_2 \; \ldots\; a_k$：给定旅行的起点 $x$ 与一个颜色集合 $\mathbb{A} = \{a_1, a_2, \cdots, a_k\}$。假设如果进行这样的一次旅行，求出取走的球的权值之和最大是多少。注意，由于我们仅仅假设进行一次旅行，因此并不会真的取走任何球。即，所有询问之间是独立的。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入两个整数 $n$ 和 $q$（$1 \leq n \leq 10^5$，$1 \leq q \leq 10^5$）表示格子的数量和操作的数量。

第二行输入 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \leq c_i \leq n$），其中 $c_i$ 表示第 $i$ 个格子的初始颜色。

第三行输入 $n$ 个整数 $v_1, v_2, \ldots, v_n$（$1 \leq v_i \leq 10^9$），其中 $v_i$ 表示第 $i$ 个格子里的球的初始权值。

对于接下来 $q$ 行，第 $i$ 行描述第 $i$ 次操作，格式如下：

- $1\; p\; x$：保证 $1 \leq p \leq n$ 且 $1 \leq x \leq n$。
- $2\; p\; x$：保证 $1 \leq p \leq n$ 且 $1 \leq x \leq 10^9$。
- $3\; x\; k\; a_1\; a_2\; \ldots \; a_k$：保证 $1 \leq x \leq n$ 且 $1 \leq a_1 < a_2 < \ldots < a_k \leq n$ 且 $c_x \in \{a_1, a_2, \cdots, a_k\}$。

保证所有数据 $n$ 之和与 $q$ 之和均不超过 $3 \times 10^5$，且所有数据 $k$ 之和不超过 $10^6$。

**【输出格式】**

对于每次操作 $3$ 输出一行一个整数，表示取走的球的权值之和的最大值。


title: [SDCPC2023] Matching

description:
Given an integer sequence $a_1, a_2, \cdots, a_n$ of length $n$, we construct an undirected graph $G$ from the sequence. More precisely, for all $1 \le i < j \le n$, if $i - j = a_i - a_j$, there will be an undirected edge in $G$ connecting vertices $i$ and $j$. The weight of the edge is $(a_i + a_j)$.

Find a matching of $G$ so that the sum of weight of all edges in the matching is maximized, and output this maximized sum.

Recall that a matching of an undirected graph means that we choose some edges from the graph such that any two edges have no common vertices. Specifically, not choosing any edge is also a matching.

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

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

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

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

outputFormat: For each test case output one line containing one integer indicating the maximum sum of weight of all edges in a matching.

translation:
**【题目描述】**

给定长度为 $n$ 的整数序列 $a_1, a_2, \cdots, a_n$，我们将从该序列中构造出一张无向图 $G$。具体来说，对于所有 $1 \le i < j \le n$，若 $i - j = a_i - a_j$，则 $G$ 中将存在一条连接节点 $i$ 与 $j$ 的无向边，其边权为 $(a_i + a_j)$。

求 $G$ 的一个匹配，使得该匹配中所有边的边权之和最大，并输出最大边权之和。

请回忆：无向图的匹配，指的是从该无向图中选出一些边，使得任意两条边都没有公共的节点。特别地，不选任何边也是一个匹配。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$2 \le n \le 10^5$）表示序列的长度。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$-10^9 \le a_i \le 10^9$）表示序列。

保证所有数据中 $n$ 之和不超过 $5 \times 10^5$。

**【输出格式】**

每组数据输出一行一个整数，表示匹配的最大边权之和。

**【样例解释】**

对于第一组样例数据，最优方案是选择连接节点 $3$ 和 $5$，节点 $4$ 和 $7$，以及节点 $8$ 和 $9$ 的三条边，边权之和为 $(5 + 7) + (6 + 9) + (1 + 2) = 30$。

对于第二组样例数据，由于每条边的边权都是负数，因此最优匹配不应该选择任何边，答案为 $0$。

对于第三组样例数据，由于图中不存在任何边，因此答案为 $0$。

hint:
For the first sample test case, the optimal choice is to choose the three edges connecting vertex $3$ and $5$, vertex $4$ and $7$, and finally vertex $8$ and $9$. The sum of weight is $(5 + 7) + (6 + 9) + (1 + 2) = 30$.

For the second sample test case, as all edges have negative weights, the optimal matching should not choose any edge. The answer is $0$.

For the third sample test case, as there is no edge in the graph, the answer is $0$.


title: [GDCPC2023] Swapping Operation

description:
Given a non-negative integer sequence $A = a_1, a_2, \dots, a_n$ of length $n$, define

$$
F(A)=\max\limits_{1\leq k<n} ((a_1 \,\&\, a_2 \,\&\, \cdots \,\&\, a_k)+(a_{k+1} \,\&\, a_{k+2} \,\&\, \cdots \,\&\, a_n))
$$

where $\&$ is the bitwise-and operator.

You can perform the swapping operation at most once: choose two indices $i$ and $j$ such that $1\leq i < j\leq n$ and then swap the values of $a_i$ and $a_j$.

Calculate the maximum possible value of $F(A)$ after performing at most one swapping operation.

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

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

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($0\leq a_i\leq 10^9$) indicating the given sequence $A$.

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

outputFormat: For each test case output one line containing one integer indicating the maximum possible value of $F(A)$ after performing at most one swapping operation.

translation:
**【题目描述】**

给定长度为 $n$ 的非负整数序列 $A = a_1, a_2, \dots, a_n$，定义

$$
F(A)=\max\limits_{1\leq k<n} ((a_1 \,\&\, a_2 \,\&\, \cdots \,\&\, a_k)+(a_{k+1} \,\&\, a_{k+2} \,\&\, \cdots \,\&\, a_n))
$$

其中 $\&$ 表示按位与操作。

您可以进行至多一次交换操作：选择两个下标 $i$ 和 $j$ 满足 $1\leq i < j\leq n$，交换 $a_i$ 与 $a_j$ 的值。

求经过至多一次交换后，$F(A)$ 的最大值。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$2\leq n\leq 10^5$)，表示序列 $A$ 的长度。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$0\leq a_i\leq 10^9$)，表示给定的序列 $A$。

保证所有数据 $n$ 之和不超过 $10^5$。

**【输出格式】**

每组数据输出一行一个整数，表示经过至多一次交换后 $F(A)$ 的最大值。

**【样例解释】**

对于第一组样例数据，可以交换 $a_4$ 和 $a_6$ 将序列变为 $\{6, 5, 4, 6, 5, 3\}$，然后选择 $k = 5$，就得到了 $F(A) = (6 \,\&\, 5 \,\&\, 4 \,\&\, 6 \,\&\, 5) + (3) = 7$。

对于第二组样例数据，可以交换 $a_2$ 和 $a_4$ 将序列变为 $\{1, 1, 1, 2, 2, 2\}$，然后选择 $k = 3$，就得到了 $F(A) = (1 \,\&\, 1 \,\&\, 1) + (2 \,\&\, 2 \,\&\, 2) = 3$。

对于第三组样例数据，不进行交换操作，然后选择 $k = 2$，就得到了 $F(A) = (1 \,\&\, 1) + (2 \,\&\, 2 \,\&\, 2) = 3$。

hint:
For the first sample test case, we can swap $a_4$ and $a_6$ so the sequence becomes $\{6, 5, 4, 6, 5, 3\}$. We can then choose $k = 5$ so that $F(A) = (6 \,\&\, 5 \,\&\, 4 \,\&\, 6 \,\&\, 5) + (3) = 7$.

For the second sample test case, we can swap $a_2$ and $a_4$ so the sequence becomes $\{1, 1, 1, 2, 2, 2\}$. We can then choose $k = 3$ so that $F(A) = (1 \,\&\, 1 \,\&\, 1) + (2 \,\&\, 2 \,\&\, 2) = 3$.

For the third sample test case we do not perform the swapping operation. We can then choose $k = 2$ so that $F(A) = (1 \,\&\, 1) + (2 \,\&\, 2 \,\&\, 2) = 3$.


title: [GDCPC2023] Canvas

description:
There is a sequence of length $n$. At the beginning, all elements in the sequence equal to $0$. There are also $m$ operations, where the $i$-th operation will change the value of the $l_i$-th element in the sequence to $x_i$, and also change the value of the $r_i$-th element in the sequence to $y_i$. Each operation must be performed exactly once.

Find the optimal order to perform the operations, so that after all operations, the sum of all elements in the sequence is maximized.

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

The first line contains two integers $n$ and $m$ ($2 \leq n, m \leq 5 \times 10^5$) indicating the length of the sequence and the number of operations.

For the following $m$ lines, the $i$-th line contains four integers $l_i$, $x_i$, $r_i$ and $y_i$ ($1 \leq l_i<r_i \leq n$, $1 \leq x_i,y_i \leq 2$) indicating the $i$-th operation.

It's guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $5 \times 10^5$.

outputFormat: For each test case, first output one line containing one integer, indicating the maximum sum of all elements in the sequence after all operations. Then output another line containing $m$ integers $a_1, a_2, \cdots, a_m$ separated by a space, indicating the optimal order to perform the operations, where $a_i$ is the index of the $i$-th operation to be performed. Each integer from $1$ to $m$ (both inclusive) must appear exactly once. If there are multiple valid answers, you can output any of them.

translation:
**【题目描述】**

有一个长度为 $n$ 的序列，一开始序列中的所有元素均为 $0$。另外还有 $m$ 个操作，其中第 $i$ 个操作会将序列中第 $l_i$ 个元素的值改为 $x_i$，以及将序列中第 $r_i$ 个元素的值改为 $y_i$。每个操作必须恰好执行一次。

求执行操作的最优顺序，使得所有操作执行完成后，序列中所有元素之和最大。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入两个整数 $n$ 和 $m$（$2 \leq n, m \leq 5 \times 10^5$）表示序列的长度和操作的个数。

对于接下来 $m$ 行，第 $i$ 行输入四个整数 $l_i$，$x_i$，$r_i$ 和 $y_i$（$1 \leq l_i<r_i \leq n$，$1 \leq x_i,y_i \leq 2$）表示第 $i$ 个操作。

保证所有数据 $n$ 之和与 $m$ 之和均不超过 $5 \times 10^5$。

**【输出格式】**

每组数据首先输出一行一个整数，表示执行操作后，所有元素的最大和。接下来输出一行 $m$ 个由单个空格分隔的整数 $a_1, a_2, \cdots, a_m$ 表示执行操作的最优顺序，其中 $a_i$ 表示第 $i$ 次执行的操作的编号。从 $1$ 到 $m$ 的每个整数（含两端）必须恰好出现一次。若有多种合法答案，您可以输出任意一种。

**【样例解释】**

对于第一组样例数据，按 $4, 1, 3, 2$ 的顺序执行操作后，序列变为 $\{2, 2, 2, 1\}$，元素之和为 $7$。

对于第二组样例数据，按 $2, 1$ 的顺序执行操作后，序列变为 $\{2, 0, 2, 1\}$，元素之和为 $5$。

hint:
For the first sample test case, after performing operations $4, 1, 3, 2$ in order, the sequence becomes $\{2, 2, 2, 1\}$. The sum of all elements is $7$.

For the second sample test case, after performing operations $2, 1$ in order, the sequence becomes $\{2, 0, 2, 1\}$. The sum of all elements is $5$.


title: [GDCPC2023] Path Planning

description:
There is a grid with $n$ rows and $m$ columns. Each cell of the grid has an integer in it, where $a_{i, j}$ indicates the integer in the cell located at the $i$-th row and the $j$-th column. Each integer from $0$ to $(n \times m - 1)$ (both inclusive) appears exactly once in the grid.

Let $(i, j)$ be the cell located at the $i$-th row and the $j$-th column. You now start from $(1, 1)$ and need to reach $(n, m)$. When you are in cell $(i, j)$, you can either move to its right cell $(i, j + 1)$ if $j < m$ or move to its bottom cell $(i + 1, j)$ if $i < n$.

Let $\mathbb{S}$ be the set consisting of integers in each cell on your path, including $a_{1, 1}$ and $a_{n, m}$. Let $\text{mex}(\mathbb{S})$ be the smallest non-negative integer which does not belong to $\mathbb{S}$. Find a path to maximize $\text{mex}(\mathbb{S})$ and calculate this maximum possible value.

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

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^6$, $1 \le n \times m \le 10^6$) indicating the number of rows and columns of the grid.

For the following $n$ lines, the $i$-th line contains $m$ integers $a_{i, 1}, a_{i, 2}, \cdots, a_{i, m}$ ($0 \le a_{i, j} < n \times m$) where $a_{i, j}$ indicates the integer in cell $(i, j)$. Each integer from $0$ to $(n \times m - 1)$ (both inclusive) appears exactly once in the grid.

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

outputFormat: For each test case output one line containing one integer indicating the maximum possible value of $\text{mex}(\mathbb{S})$.

translation:
**【题目描述】**

有一个 $n$ 行 $m$ 列的网格。网格里的每个格子都写着一个整数，其中第 $i$ 行第 $j$ 列的格子里写着整数 $a_{i, j}$。从 $0$ 到 $(n \times m - 1)$ 的每个整数（含两端）在网格里都恰好出现一次。

令 $(i, j)$ 表示位于第 $i$ 行第 $j$ 列的格子。您现在需要从 $(1, 1)$ 出发并前往 $(n, m)$。当您位于格子 $(i, j)$ 时，您可以选择走到右方的格子 $(i, j + 1)$（若 $j < m$），也可以选择走到下方的格子 $(i + 1, j)$（若 $i < n$）。

令 $\mathbb{S}$ 表示路径上每个格子里的整数形成的集合，包括 $a_{1, 1}$ 和 $a_{n, m}$。令 $\text{mex}(\mathbb{S})$ 表示不属于 $\mathbb{S}$ 的最小非负整数。请找出一条路径以最大化 $\text{mex}(\mathbb{S})$，并求出这个最大的值。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入两个整数 $n$ 和 $m$（$1 \le n, m \le 10^6$，$1 \le n \times m \le 10^6$）表示网格的行数和列数。

对于接下来 $n$ 行，第 $i$ 行输入 $m$ 个整数 $a_{i, 1}, a_{i, 2}, \cdots, a_{i, m}$（$0 \le a_{i, j} < n \times m$），其中 $a_{i, j}$ 表示格子 $(i, j)$ 里的整数。从 $0$ 到 $(n \times m - 1)$ 的每个整数（含两端）在网格里都恰好出现一次。

保证所有数据 $n \times m$ 之和不超过 $10^6$。

**【输出格式】**

每组数据输出一行一个整数，表示最大的 $\text{mex}(\mathbb{S})$。

**【样例解释】**

对于第一组样例数据，共有 $3$ 条可能的路径。

- 第一条路径为 $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3)$。$\mathbb{S} = \{1, 2, 4, 5\}$ 因此 $\text{mex}(\mathbb{S}) = 0$。
- 第二条路径为 $(1, 1) \to (1, 2) \to (2, 2) \to (2, 3)$。$\mathbb{S} = \{1, 2, 0, 5\}$ 因此 $\text{mex}(\mathbb{S}) = 3$。
- 第三条路径为 $(1, 1) \to (2, 1) \to (2, 2) \to (2, 3)$。$\mathbb{S} = \{1, 3, 0, 5\}$ 因此 $\text{mex}(\mathbb{S}) = 2$。

因此答案为 $3$。

对于第二组样例数据，只有 $1$ 条可能的路径，即 $(1, 1) \to (1, 2) \to (1, 3) \to (1, 4) \to (1, 5)$。$\mathbb{S} = \{1, 3, 0, 4, 2\}$ 因此 $\text{mex}(\mathbb{S}) = 5$。

hint:
For the first sample test case there are $3$ possible paths.

- The first path is $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3)$. $\mathbb{S} = \{1, 2, 4, 5\}$ so $\text{mex}(\mathbb{S}) = 0$.
- The second path is $(1, 1) \to (1, 2) \to (2, 2) \to (2, 3)$. $\mathbb{S} = \{1, 2, 0, 5\}$ so $\text{mex}(\mathbb{S}) = 3$.
- The third path is $(1, 1) \to (2, 1) \to (2, 2) \to (2, 3)$. $\mathbb{S} = \{1, 3, 0, 5\}$ so $\text{mex}(\mathbb{S}) = 2$.

So the answer is $3$.

For the second sample test case there is only $1$ possible path, which is $(1, 1) \to (1, 2) \to (1, 3) \to (1, 4) \to (1, 5)$. $\mathbb{S} = \{1, 3, 0, 4, 2\}$ so $\text{mex}(\mathbb{S}) = 5$.


title: [GDCPC2023] X Equals Y

description:
For positive integers $X$ and $b \geq 2$, define $f(X,b)$ as a sequence which describes the base-$b$ representation of $X$, where the $i$-th element in the sequence is the $i$-th least significant digit in the base-$b$ representation of $X$. For example, $f(6, 2) = \{0, 1, 1\}$, while $f(233, 17) = \{12, 13\}$.

Given four positive integers $x$, $y$, $A$ and $B$, please find two positive integers $a$ and $b$ satisfying:

- $2 \leq a \leq A$
- $2 \leq b \leq B$
- $f(x, a) = f(y, b)$

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

The first line contains four integers $x$, $y$, $A$ and $B$ ($1 \leq x,y \leq 10^9$, $2 \leq A,B \leq 10^9$).

It's guaranteed that there are at most $50$ test cases satisfying $\max(x, y) > 10^6$.

outputFormat:
For each test case, if valid positive integers $a$ and $b$ do not exist, output $\texttt{NO}$ in one line.

Otherwise, first output $\texttt{YES}$ in one line. Then in the next line, output two integers $a$ and $b$ separated by a space. If there are multiple valid answers, you can output any of them.

translation:
**【题目描述】**

对于正整数 $X$ 与 $b \geq 2$，定义 $f(X,b)$ 为一个描述了 $X$ 在 $b$ 进制表示下的序列，其中序列的第 $i$ 个元素表示 $X$ 在 $b$ 进制表示下从低到高第 $i$ 位的值。例如，$f(6, 2) = \{0, 1, 1\}$，而 $f(233, 17) = \{12, 13\}$。

给定的四个正整数 $x$，$y$，$A$ 和 $B$，请找到两个正整数 $a$ 和 $b$，同时满足：

- $2 \leq a \leq A$
- $2 \leq b \leq B$
- $f(x, a) = f(y, b)$

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$（$1 \leq T \leq 10^3$）表示测试数据组数。对于每组测试数据：

第一行输入四个整数 $x$，$y$，$A$ 和 $B$（$1 \leq x,y \leq 10^9$，$2 \leq A,B \leq 10^9$）。

保证至多只有 $50$ 组测试数据满足 $\max(x, y) > 10^6$。

**【输出格式】**

对于每组测试数据，如果不存在合法的正整数 $a$ 和 $b$，则输出一行一个字符串 $\texttt{NO}$。

否则，首先输出一行一个字符串 $\texttt{YES}$。下一行输出两个由单个空格分隔的整数 $a$ 和 $b$。如果有多种合法答案，您可以输出任意一种。

samples:
YES
2 2
NO
YES
2 10
YES
4 5
NO
YES
779 9478


title: [GDCPC2023] Peg Solitaire

description:
$\textit{Peg Solitaire}$ is a single-player boardgame on a chessboard with $n$ rows and $m$ columns. Each cell of the chessboard either is empty, or contains a chesspiece. Initially, there are $k$ chesspieces on the chessboard.

During the game, the player can choose a chesspiece, jump it over an adjacent chesspiece into an empty cell, and finally remove the chesspiece which is jumped over. More precisely, let $(i, j)$ be the cell on the $i$-th row and the $j$-th column, the player can perform operations of the following four types.

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

Given the initial state of the chessboard, the player can perform the operations any number of times (including zero times). Calculate the minimum possible number of chesspieces remaining on the chessboard.

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

The first line contains three integers $n$, $m$ and $k$ ($1 \le n, m \le 6$, $1 \le k \le \min(6, n \times m)$) indicating the number of rows and columns of the chessboard and the initial number of chesspieces.

For the following $k$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \le x_i \le n$, $1 \le y_i \le m$) indicating that there is a chesspiece in the cell on the $x_i$-th row and the $y_i$-th column at the beginning. Except from these $k$ cells, all other cells are empty at the beginning. The positions of these $k$ cells contain no duplicate.

outputFormat: For each test case output one line containing one integer indicating the minimum possible number of chesspieces remaining on the chessboard.

translation:
**【题目描述】**

``独立钻石``是一种单人桌游。游戏在 $n$ 行 $m$ 列的棋盘上进行，棋盘上的每一格要么是空格，要么有一枚棋子。一开始，棋盘上共有 $k$ 枚棋子。

在游戏中，玩家可以选择一枚棋子，将它跳过相邻棋子到空格上，并移除被跳过的棋子。具体来说，令 $(i, j)$ 表示位于第 $i$ 行第 $j$ 列的格子，玩家可以执行以下四种操作。

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

给定一个初始的棋盘，求经过任意次操作（包括零次）之后，棋盘上最少能剩余几枚棋子。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 20$）表示测试数据组数。对于每组测试数据：

第一行输入三个整数 $n$，$m$ 和 $k$（$1 \le n, m \le 6$，$1 \le k \le \min(6, n \times m)$）表示棋盘的行数，列数和初始棋子的数量。

对于接下来 $k$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le n$，$1 \le y_i \le m$）表示一开始第 $x_i$ 行第 $y_i$ 列的格子里有一枚棋子。除了这 $k$ 个格子之外，其它格子一开始都是空格。这 $k$ 个格子的位置不会重复。

**【输出格式】**

每组数据输出一行一个整数，表示经过任意次操作（包括零次）之后，棋盘上最少能剩余几枚棋子。

**【样例解释】**

第一组样例数据解释如下。

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

对于第二组样例数据，由于初始棋盘不存在空格，因此无法进行任何操作。

对于第三组样例数据，由于棋盘不足三格，因此无法进行任何操作。

hint:
The first sample test case is explained as follows.

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

For the second sample test case, as the chessboard does not contain empty cell at the beginning, the player cannot perform any operation.

For the third sample test case, as the chessboard has less than three cells, the player cannot perform any operation.


title: [GDCPC2023] Classic Problem

description:
Given an undirected complete graph with $n$ vertices and $m$ triples $P_1, P_2, \cdots, P_m$ where $P_i = (u_i, v_i, w_i)$, it's guaranteed that $1 \leq u_i < v_i \leq n$, and for any two triples $P_i$ and $P_j$ with different indices we have $(u_i, v_i) \ne (u_j, v_j)$.

For any two vertices $x$ and $y$ in the graph ($1 \leq x < y \leq n$), define the weight of the edge connecting them as follows:

- If there exists a triple $P_i$ satisfying $u_i = x$ and $v_i = y$, the weight of edge will be $w_i$.
- Otherwise, the weight of edge will be $|x - y|$.

Calculate the total weight of edges in the minimum spanning tree of the graph.

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

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 10^9$, $0 \leq m \leq 10^5$) indicating the number of vertices in the graph and the number of triples.

For the following $m$ lines, the $i$-th line contains three integers $u_i$, $v_i$ and $w_i$ ($1 \leq u_i < v_i \leq n$, $0 \leq w_i \leq 10^9$) indicating the $i$-th triple. It's guaranteed that for all $1 \leq i < j \leq m$ we have $(u_i, v_i) \ne (u_j, v_j)$.

It's guaranteed that the sum of $m$ of all test cases will not exceed $5 \times 10^5$.

outputFormat: For each test case output one line containing one integer indicating the total weight of edges in the minimum spanning tree of the graph.

translation:
**【题目描述】**

给定一张 $n$ 个点的无向完全图与 $m$ 个三元组 $P_1, P_2, \cdots, P_m$，其中 $P_i = (u_i, v_i, w_i)$。保证 $1 \leq u_i < v_i \leq n$，且对于任意两个编号不同的三元组 $P_i$ 和 $P_j$，有 $(u_i, v_i) \ne (u_j, v_j)$。

对于图中的任意两个节点 $x$ 与 $y$（$1 \leq x < y \leq n$），定义它们之间的无向边的边权如下：

- 如果存在一个三元组 $P_i$ 满足 $u_i = x$ 且 $v_i = y$，那么边权为 $w_i$。
- 否则，边权为 $|x - y|$。

求这张图的最小生成树的边权之和。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 10^5$）表示测试数据组数。对于每组测试数据：

第一行输入两个整数 $n$ 和 $m$（$1 \leq n \leq 10^9$，$0 \leq m \leq 10^5$）表示图的点数与三元组的数量。

对于接下来 $m$ 行，第 $i$ 行输入三个整数 $u_i$，$v_i$ 和 $w_i$（$1 \leq u_i < v_i \leq n$，$0 \leq w_i \leq 10^9$）表示第 $i$ 个三元组。保证对于所有 $1 \leq i < j \leq m$ 都有 $(u_i, v_i) \ne (u_j, v_j)$。

保证所有数据 $m$ 之和不超过 $5 \times 10^5$。

**【输出格式】**

每组数据输出一行一个整数，表示这张图的最小生成树的边权之和。

**【样例解释】**

第一组样例数据如下图所示，最小生成树用红色线段标出。

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

第二组样例数据如下图所示，最小生成树用红色线段标出。

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

第三组样例数据如下图所示，最小生成树用红色线段标出。

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

hint:
The first sample test case is illustrated as follows. The minimum spanning tree is marked by red segments.

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

The second sample test case is illustrated as follows. The minimum spanning tree is marked by red segments.

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

The third sample test case is illustrated as follows. The minimum spanning tree is marked by red segments.

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


title: [SDCPC2023] Be Careful 2

background: # 警告：滥用本题评测将被封禁。

description:
Little Cyan Fish has an $n \times m$ rectangle located in a plane. The top-right corner of the rectangle is at $(n, m)$, while the bottom-left corner is at $(0, 0)$. There are $k$ banned points inside the rectangle. The $i$-th banned point is located at $(x_i, y_i)$.

Little Cyan Fish would like to draw a square inside the rectangle. However, he dislikes all the banned points, so there cannot be any banned points inside his square. Formally, Little Cyan Fish can draw a square with the bottom-left corner at $(x, y)$ and a side length $d$ if and only if:

- Both $x$ and $y$ are non-negative integers while $d$ is a positive integer.
- $0 \leq x < x+d \leq n$.
- $0 \leq y < y+d \leq m$.
- For each $1 \leq i \leq k$, the following condition must **NOT** be met:
  - $x < x_i < x+d$ and $y < y_i < y+d$.

Please calculate the sum of the areas of all the squares that Little Cyan Fish can possibly draw. Since the answer could be huge, you need to output it modulo $998244353$.

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

The first line of the input contains three integers $n$, $m$ and $k$ ($2 \leq n,m \leq 10^9$, $1 \leq k \leq 5 \times 10^3$) indicating the size of the rectangle and the number of banned points.

For the following $k$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($0 < x_i < n$, $0 < y_i < m$) indicating the position of the $i$-th banned point. It is guaranteed that all the banned points are distinct.

outputFormat: Output one line containing one integer indicating the answer modulo $998244353$.

translation:
**【题目描述】**

小青鱼有一个位于二维平面上的，大小为 $n \times m$ 的矩形。矩形的右上角位于 $(n, m)$，而左下角位于 $(0, 0)$。矩形内部有 $k$ 个禁止点，第 $i$ 个禁止点位于 $(x_i, y_i)$。

小青鱼想在矩形里画一个正方形。但由于小青鱼不喜欢禁止点，因此正方形的内部不能有任何禁止点。更正式地，小青鱼可以画一个左下角位于 $(x, y)$ 且边长为 $d$ 的正方形，当且仅当：

- $x$ 和 $y$ 都是非负整数，$d$ 是一个正整数。
- $0 \leq x < x+d \leq n$。
- $0 \leq y < y+d \leq m$。
- 每个 $1 \leq i \leq k$ 都 **不能** 满足以下条件：
  - $x < x_i < x+d$ 且 $y < y_i < y+d$。

请计算小青鱼可以画的正方形的总面积。由于答案可能很大，请将答案对 $998244353$ 取模后输出。

**【输入格式】**

每个测试文件仅有一组测试数据。

第一行输入三个整数 $n$，$m$ 和 $k$（$2 \leq n,m \leq 10^9$，$1 \leq k \leq 5 \times 10^3$），表示矩形的大小和禁止点的数量。

对于接下来 $k$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$0 < x_i < n$，$0 < y_i < m$）表示第 $i$ 个禁止点的位置。保证所有禁止点互不相同。

**【输出格式】**

输出一行一个整数，代表对 $998244353$ 取模后的答案。

**【样例解释】**

对于第一组样例数据，小青鱼有 $12$ 种方式画一个正方形，如下图所示。

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

共有 $9$ 个边长为 $1$ 的正方形和 $3$ 个边长为 $2$ 的正方形。因此答案为 $9 \times 1^2 + 3 \times 2^2 = 21$。

以下画正方形的方式是不合法的，因为正方形内有一个禁止点。

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

hint:
For the first sample test case, Little Cyan Fish has $12$ ways to draw a square, illustrated as follows.

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

There are $9$ squares of side length $1$ and $3$ squares of side length $2$. So the answer is $9 \times 1^2 + 3 \times 2^2 = 21$.

Note that the following plans are invalid since there's a banned point in the square.

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


title: [SDCPC2023] Three Dice

description:
Dice are small, throwable objects with marked sides capable of landing in multiple positions. They are typically used to generate random values, especially in the context of tabletop games.

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

The most common dice are small cubes, with faces numbered from $1$ to $6$. Number $n$ ($1 \le n \le 6$) is usually represented by a pattern of $n$ round dots, known as pips. Moreover, the pips on the $1$ and $4$ faces are colored red, while those on the $2$, $3$, $5$ and $6$ faces are black.

Little Cyan Fish has three dice. One day, he threw them onto a table, and then observed the uppermost faces. He claimed that the total number of the red pips facing up was exactly $A$, and the total number of the black pips facing up was exactly $B$.

However, you find his claim doubtful. You want to verify whether it is possible to throw three dice such that the total number of red pips facing up is $A$, and the total number of black pips facing up is $B$.

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

The first line of the input contains two integers $A$ and $B$ ($0 \leq A,B \leq 100$), indicating the total number of red pips facing up and the number of black pips facing up.

outputFormat: Output one line. If it is possible for Little Cyan Fish to throw three dice such that the total number of red pips facing up is $A$, and the total number of black pips facing up is $B$ output `Yes`. Otherwise output `No`.

translation:
**【题目描述】**

骰子，是一种各面带有标记，以生成随机数的小型可投掷道具，通常用于桌上游戏。

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

最常见的骰子是一种小正方体，每个面上被标记了从 $1$ 到 $6$ 的数字。数字 $n$（$1 \le n \le 6$）通常由 $n$ 个小圆点组成的图案来表示，其中 $1$ 号与 $4$ 号面的小圆点是红色的，而 $2$, $3$, $5$ 与 $6$ 号面的小圆点是黑色的。

小青鱼手中有三只骰子。有一天，他将这三只骰子投掷在桌子上，并观察了朝上的那一个面。他发现所有朝上的面中，红色的点数之和恰好为 $A$，而黑色的点数之和恰好为 $B$。

然而，您对小青鱼的发现感到怀疑。您想要确认是否有可能投掷出三只骰子，使得所有朝上的面中，红色的点数之和恰好为 $A$，而黑色的点数之和恰好为 $B$。

**【输入格式】**

每个测试文件仅有一组测试数据。

第一行输入两个整数 $A$ 和 $B$（$0 \leq A,B \leq 100$），表示朝上的红色点数之和与黑色点数之和。

**【输出格式】**

输出一行。如果小青鱼有可能投掷出三只骰子使得所有朝上的面中，红色的点数之和恰好为 $A$，而黑色的点数之和恰好为 $B$，则输出 `Yes`。否则输出 `No`。

**【样例解释】**

在第一组样例中，其中一种合法的方案为 $4, 2, 3$。

在第二组样例中，其中一种合法的方案为 $1, 1, 1$。

samples:
4 5
Yes

samples:
3 0
Yes

samples:
1 2
No

hint:
In the first example, one possible solution is $4, 2, 3$.

In the second example, one possible solution is $1, 1, 1$.


title: [SDCPC2023] Difficult Constructive Problem

description:
Given a string $s_1s_2\cdots s_n$ of length $n$ where $s_i \in \{\text{0}, \text{1}, \text{?}\}$ and an integer $k$, please fill out all the $\text{?}$ with $\text{0}$ or $\text{1}$ such that the number of indices $i$ satisfying $1 \le i < n$ and $s_i \ne s_{i+1}$ equals to $k$. Different $\text{?}$ can be replaced with different characters.

To make this problem even more difficult, we ask you to find the answer with the smallest possible lexicographic order if it exists.

Recall that a string $a_1a_2\cdots a_n$ of length $n$ is lexicographically smaller than another string $b_1b_2\cdots b_n$ of length $n$ if there exists an integer $k$ ($1 \le k \le n$) such that $a_i = b_i$ for all $1 \le i < k$ and $a_k < b_k$.

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

The first line contains two integers $n$ and $k$ ($1 \le n \le 10^5$, $0 \le k < n$) indicating the length of the string and the required number of indices satisfying the condition.

The second line contains a string $s_1s_2,\cdots s_n$ ($s_i \in \{\text{0}, \text{1}, \text{?}\}$).

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

outputFormat: For each test case output one line. If the answer exists output the lexicographically smallest one (you need to output the whole given string after filling out all the $\text{?}$ and make this string the lexicographically smallest); Otherwise output `Impossible`.

translation:
**【题目描述】**

给定一个长度为 $n$ 的字符串 $s_1s_2\cdots s_n$，其中 $s_i \in \{\text{0}, \text{1}, \text{?}\}$，另外给定一个整数 $k$，请将字符串中所有的 $\text{?}$ 换成 $\text{0}$ 或 $\text{1}$，使得满足 $1 \le i < n$ 且 $s_i \ne s_{i+1}$ 的下标 $i$ 恰有 $k$ 个。不同的 $\text{?}$ 可以用不同字符替换。

为了让这题变得更加困难，我们要求您在答案存在的情况下，输出字典序最小的答案。

请回忆：称长度为 $n$ 的字符串 $a_1a_2\cdots a_n$ 的字典序小于长度为 $n$ 的字符串 $b_1b_2\cdots b_n$，若存在一个整数 $k$（$1 \le k \le n$）使得对于所有 $1 \le i < k$ 有 $a_i = b_i$，且 $a_k < b_k$。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数，对于每组测试数据：

第一行输入两个整数 $n$ 和 $k$（$1 \le n \le 10^5$，$0 \le k < n$）表示字符串的长度以及满足要求的下标数量。

第二行输入一个字符串 $s_1s_2,\cdots s_n$（$s_i \in \{\text{0}, \text{1}, \text{?}\}$）。

保证所有数据 $n$ 之和不超过 $10^6$。

**【输出格式】**

每组数据输出一行。若答案存在则输出字典序最小的答案（您需要输出将 $\text{?}$ 替换之后的整个字符串，并让这个字符串的字典序最小），否则输出 `Impossible`。