title: 异界之门

background:
跟随着线索，莲子来到了七夕坂。无暇欣赏此处的风景，高速运转着大脑的莲子，不断寻找异界的线索。翻转的地藏、奇异的裂缝、被隐匿的第五个季节……这个禁忌之中的世界，正向她揭晓着自己的秘密。

但莲子第一时间看到的只有梅莉，来不及思考，她一把抓住了梅莉的手——

description:
嗅觉敏锐的莲子察觉到，进入异界的方法一定和这些特别的地藏有所联系。她发现它们恰好构成了一棵形状特殊的树。

给定一棵 $n$ 个点的带点权的**有根**树，其根为 $1$，且点 $i$ 的点权为 $w_i$。**其满足对于任意两个深度相同的结点，它们的儿子数也相同**。

为了进入异界，莲子进行了一些操作来改变这棵树的点权：

1. 选择一条边，假设它连接了两点 $(u,v)$，设其中深度更高者为 $u$（即 $u$ 是 $v$ 的儿子），将 $w_u$ 加上 $w_v$。
2. 上述操作可以被执行任意多次，但是**不能重复选择同一条边**。

经过操作后，莲子求出了树的某个 [DFS 序列](https://oi-wiki.org/graph/dfs/)，并记录下了这个 DFS 序列所对应的点权序列 $c$（具体来说，$c_i$ 为 DFS 序过程中遍历到的第 $i$ 个点的点权）。

不幸的是，她突然忘记了她进行过哪些操作，也忘记了如何 DFS 这棵树，她希望你能还原出任意一组合法的操作方案与 DFS 序列。

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

对于接下来 $n$ 行：第 $i$ 行两个整数 $f_i,w_i$，其中 $f_i$ 代表点 $i$ 的父节点（特别的，$f_1=0$，对于其余节点有 $1\le f_i<i$），$w_i$ 代表点 $i$ 的权值。

接下来一行 $n$ 个整数描述序列 $c$，代表莲子的 DFS 序列所对应的点权序列 $c$。保证一定存在一种合法的操作方式和操作后的 DFS 方式得到序列 $c$。

outputFormat:
第一行一个整数 $m$，表示你进行的操作数。

接下来一行 $m$ 个数，第 $i$ 个数 $x_i$ 代表你在第 $i$ 次操作选择连接节点 $x_i$ 和其父节点 $f_{x_i}$ 的边进行操作。

接下来一行 $n$ 个数描述一个排列 $p$，其中 $p_i$ 代表你构造的 DFS 序列中遍历到的第 $i$ 个节点为点 $p_i$。

hint:
### 样例解释

#### 样例 \#1

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

其中一种可行的方案是依次操作边 $(2,3),(3,4),(1,2)$，操作后的树的点权序列为 $\{1,3,5,9\}$，选出的 DFS 序列为 $\{1,2,3,4\}$。

注意到该样例符合特殊性质 $\mathbf{A}$。

#### 样例 \#2

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

其中一种可行的方案是依次操作边 $(1,2),(3,5),(1,3)$，操作后的树的点权序列为 $\{1,0,0,3,3\}$，选出的 DFS 序列为 $\{1,2,4,3,5\}$。
#### 样例 \#3

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

其中一种可行的方案是依次操作边 $(1,2)$，操作后的树的点权序列为 $\{1,3,3,4\}$，选出的 DFS 序列为 $\{1,4,2,3\}$。

注意到该样例符合特殊性质 $\mathbf{B}$。
#### 样例 \#4

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

其中一种可行的方案是依次操作边 $(1,2),(2,4),(3,5),(1,3)$，操作后的树的点权序列为 $\{1,2,3,2,2\}$，选出的 DFS 序列为 $\{1,3,5,2,4\}$。

注意到该样例符合特殊性质 $\mathbf{C}$。

### 数据范围

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

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|}\hline
\textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n\le } & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\cr\hline
1 & 10 & 6 & - &-\cr\hline
2 & 10 & 100 & \mathbf{A}&- \cr\hline
3 & 10 & 100 & \mathbf{B}&- \cr\hline
4 & 15 & 2\times 10^3 & \mathbf{C}&-  \cr\hline
5 & 15 & 2\times 10^3 & \mathbf{D}&-  \cr\hline
6 & 15 & 100 & -&1,2,3  \cr\hline
7 & 25 & 2\times 10^3 & -&1,2,3,4,5,6  \cr\hline
\end{array}
$$

特殊性质 $\mathbf{A}$：保证给出的树满足 $f_i=i-1$ ($i\ne 1$)。\
特殊性质 $\mathbf{B}$：保证给出的树满足 $f_i=1$ ($i\ne 1$)。\
特殊性质 $\mathbf{C}$：保证给出的树满足 $w_i=1$。\
特殊性质 $\mathbf{D}$：保证给出的树满足所有非叶节点儿子数不超过 $2$。

对于所有数据满足：$1\le n\le 2000$，$-10^8\le w_i\le 10^8$，$-10^{14}\le c_i\le 10^{14}$。


title: 排除干扰

type: P

background:
其实，莲子有所不知的是，梅莉早在几周前就瞒着她一个人去探险，至今未归。得知了此事的莲子后悔万分。

为了找到失踪的梅莉，莲子独自前去梅莉家寻找线索，但她翻箱倒柜却仍一无所获。

“该怎么办啊！要是能排除干扰，找到有用的线索就好了。对了，那就以梅莉的视角想想吧！”

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

为了同时从两者的角度思考，莲子在内心构想了一场博弈，而主角则仍是小 R 与小 M，规则如下：

小 R 和小 M 初始均有 $m$ 张牌，牌共有 $n$ 类，编号为 $1$ 到 $n$。**保证她们初始拥有每类牌至少一张**。她们可以互相看见手牌。

小 R 和小 M 轮流弃牌，**其中小 R 为先手**。每回合她们都要丢弃恰好一张牌。当她们均把牌弃到只剩一张时，假设小 R 的牌为 $u$，小 M 的牌为 $v$，那么小 R 获得的分数为 $a_{u,v}$，小 M 获得的分数为 $-a_{u,v}$。她们都希望自己的得分尽可能高。

现在，你需要和交互库模拟一局游戏，若 $c=0$，你将扮演小 R；若 $c=1$，你将扮演小 M。你取得的分数至少需要达到双方均以最优策略决策时所得到的分数。

inputFormat:
第一行三个整数 $n,m,c$，它们的含义都与题目描述相同。

接下来的 $n$ 行，每行 $n$ 个整数，描述矩阵 $a$。第 $i$ 行第 $j$ 列的元素为 $a_{i,j}$。

接下来共两行，每行 $n$ 个整数。对于第一行，其中第 $i$ 个整数 $R_i$ 代表小 R 初始拥有多少张第 $i$ 类的牌。对于第二行，第 $i$ 个整数 $M_i$ 代表小 M 初始拥有多少张第 $i$ 类的牌。保证有 $\sum R_i=\sum M_i=m$。

接下来进入交互过程：

1. 如果轮到对手（交互库）操作，你可以读入一个正整数 $x$，代表对手该回合丢弃了一张第 $x$ 类的牌。
2. 如果轮到你操作，你需要输出一个正整数 $y$，代表你该回合丢弃了一张第 $y$ 类的牌。
3. 如果游戏结束（两人均只剩一张牌）且你取得的分数不是最优/你进行了不合法的操作，你需要读入一个 `-1` 后退出程序。
4. 如果游戏结束且你取得的分数是最优，你需要读入一个 `0` 后退出程序。

**注意：在交互过程中，你需要在输出后刷新缓存区，下面是一些常见语言的刷新缓存区方式：**

- C++：`fflush(stdout)` 或 `cout.flush()`。
- C: `fflush(stdout)`。
- Java: `System.out.flush()`。
- Python: `stdout.flush()`。
- Pascal: `flush(output)`。
- 其他语言：请参考对应语言的帮助文档。

outputFormat: 见「输入格式」。

hint:
### 样例解释

#### 样例 \#1

你将扮演小 R（先手）游玩。假设你丢弃一张 $1$ 类牌，对手丢弃一张 $2$ 类牌，最终你的得分即为 $1$。可以证明，得分 $1$ 即为最优得分。

注意到该样例同时符合特殊性质 $\mathbf{B}$ 和 $\mathbf{C}$。
#### 样例 \#2

你将扮演小 R（先手）游玩。可以证明，最终小 R 的得分 $3$ 即为最优得分。

注意到该样例符合特殊性质 $\mathbf{A}$。
#### 样例 \#3

你将扮演小 M（后手）游玩。可以证明，最终小 M 的得分 $1$ 即为最优得分。

### 数据范围

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

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|}\hline
\textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n\le} & \bm{m\le} & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\cr\hline
1 & 20 & 5 & 5 & - &-\cr\hline
2 & 15 & 10^3 & 10^4 & \mathbf{A}&- \cr\hline
3 & 20 & 10^3 & 10^4 & \mathbf{B}&- \cr\hline
4 & 20 & 10^3 & 10^3 & \mathbf C&-  \cr\hline
5 & 25 & 10^3 & 10^4 & -&1,2,3,4  \cr\hline
\end{array}
$$

特殊性质 $\mathbf{A}$：保证 $a_{i,j}=i+j$。\
特殊性质 $\mathbf{B}$：保证 $a$ 中只出现 $0$ 和 $1$。\
特殊性质 $\mathbf{C}$：保证每人初始拥有每类牌恰好一张。

对于所有数据满足：$1\le n\le 10^3$，$1\le m\le 10^4$，$0\le |a_{i,j}|\le 10^8$，$1\le R_i,M_i \le m$ 且 $\sum R_i = \sum M_i = m$。保证交互库进行的操作均合法。


title: [JRKSJ R8] 网球

background: ~~垒球是橙色的~~ 网球是绿色的。网球是上升的，网球是下落的。

description:
你有两个啮合在一起的齿轮，你希望齿轮 A 每转 $a$ 圈齿轮 B 都能转恰好 $b$ 圈。

由于精细度要求，每个齿轮都必须有**不少于** $c$ 个齿，求齿轮 A 和齿轮 B 的总齿数和的最小值。

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

第一行一个整数 $T$ 描述数据组数。对于每组数据：

- 仅一行，三个整数 $a, b, c$。

outputFormat: 对于每组数据，一行一个整数表示答案。

hint:
### 样例解释

- 对于第一组数据，最优方案为齿轮 A 有 $6$ 个齿，齿轮 B 有 $4$ 个齿，答案为 $4 + 6 = 10$；
- 对于第二组数据，最优方案为齿轮 A 有 $10$ 个齿，齿轮 B 有 $5$ 个齿，答案为 $10 + 5 = 15$；
- 对于第三组数据，最优方案为齿轮 A 有 $8$ 个齿，齿轮 B 有 $20$ 个齿，答案为 $8 + 20 = 28$。

### 数据规模与约定

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

令 $v = \max(a, b, c)$。

- Subtask 0（13 pts）：$v \leq 20$；
- Subtask 1（13 pts）：$v \leq 5000$；
- Subtask 2（20 pts）：$v \leq 10^6$；
- Subtask 3（54 pts）：无特殊限制。

对于所有数据，保证 $1 \leq T \leq 8\times 10^3$，$1 \leq a, b, c \leq 10^9$。


title: Monochrome Tree

description:
给定你一棵根节点为 $1$ 的树，对于任意的节点 $u$ 都只能有两种颜色：黑或白。每个节点 $u$ 的起始颜色都是已知的，记为 $\mathrm{color}_u$。

现在你有两种操作：
- 操作 $1$：把任意一个节点 $u$ 到根节点的路径上节点的颜色全部翻转（路径包括 $u$ 和根节点）。
- 操作 $2$：把任意一个以 $u$ 为根节点的子树上的节点颜色全部翻转（$u$ 的子树包括 $u$）。

现在问你，最少需要几次操作才能把整棵树变成黑色。

inputFormat:
第一行一个整数 $n$ 表示节点个数。

第二行 $n$ 个整数表示 $\mathrm{color}_i$，$\mathrm{color}_i=0$ 代表 $i$ 节点初始为白色，$\mathrm{color}_i=1$ 代表 $i$ 节点初始为黑色。

接下来 $n-1$ 行，每行两个整数，表示一条边连接的两个节点。

outputFormat: 一个整数，表示最少的操作次数。


title: [ICPC2024 Xi'an I] Guess The Tree

description:
There is a full binary tree with $n$ levels(so it has exactly $2^n-1$ nodes). Each node has an integer ID from $1$ to $2^n-1$, and the $2^n-1$ IDs form an arrangement from $1$ to $2^n-1$, but you don't know.

You need to find the IDs of the $2^n-1$ nodes using at most $4800$ queries.

inputFormat:
The first line contains one integer $n(1\leq n\leq 10)$, the levels of the full binary tree.

To ask a query, you need to pick two nodes with IDs $u,v(1\leq u,v\leq 2^n-1)$, and print the line of the following form:

> "? u v"

After that, you will receive:

> "t"

The lowest common ancestor's ID of $u$ and $v$.

You can ask at most $4800$ queries.

If you have found the structure of the tree, print a line of the following form:

"! $f_1\ f_2\ f_3\ f_4$ ... $f_{2^n-1}$"

$f_i$ means the i-th node's father's ID. If it has no father, then $f_i=-1$.

After printing a query or the answer for a test case, do not forget to output the end of line and flush the output. Otherwise, you will get the verdict 'Idleness Limit Exceeded'. To do this, use:

`fflush(stdout)` or `cout.flush()` in C++;

`System.out.flush()` in Java;

`stdout.flush()` in Python.

The interactor in this task is not adaptive.

hint:
In this case, the tree's root is $3$, it's two sons are $1$ and $2$.

For any query "? a b",if $a\neq b$, the jury will return answer $3$.

So we found the tree's root is $3$ .


title: [ICPC2024 Xi'an I] Turn Off The Lights

description:
Kitty has $n^2$ lights, which form an $n\times n$ matrix.

One day, Kitty found that some of these lights were on, and some were off. Kitty wants to turn them all off.

To achieve her goal, Kitty can perform three types of operations:

- (1) Choose a row, reverse the state of this row. It means if a light of this row is on, after this operation, it is now off. If a light of this row is off, after this operation, it is now on.

- (2) Choose a column, reverse the state of this column. It means if a light of this column is on, after this operation, it is now off. If a light of this column is off, after this operation, it is now on.

- (3) Choose exactly one light, reverse the state of this light. **This operation can only be performed not more than $k$ times.**

For the current state, help Kitty achieve her goal within $3n$ operations.

inputFormat:
The first line contains two integers $n(1\leq n\leq 1000),k(0\leq k < n)$, indicating as described above.

Then $n$ lines follow, each line has exactly $n$ numbers, $0$ represents that the light is turned off at this time, while $1$ represents the opposite.

The $y$-th number of the $(x+1)$-th line in input means the light at coordinate $(x,y)$.

outputFormat:
If Kitty can not achieve her goal,print $-1$ in a single line.

Otherwise, print $M(0\leq M\leq 3n)$ in the first line, indicating the number of operations she needs to perform.

The next $M$ lines, each line contains $2$ integers $x,y$, separated by white space.

If $1\leq x\leq n,1\leq y\leq n$, it means Kitty will reverse the light at coordinate $(x,y)$.

If $x=0,1\leq y\leq n$, it means Kitty will reverse all lights at coordinates $(z,y)1\leq z\leq n$.

If $1\leq x\leq n,y=0$, it means Kitty will reverse all lights at coordinates $(x,z)1\leq z\leq n$.

If there are multiple answers, print any of them.


title: [ICPC2024 Xi'an I] Fix the Tree

description:
You are given a tree consisting of $n$ vertices. Each vertex $i$ of this tree has a value $w_i$ assigned to it.

Now the vertex $u$ will be broken. Once it's broken, vertex $u$ and all edges with one end at vertex $u$ will be removed from the tree.

To make the tree connected, you can do the following operation any number of times(possibly zero) in any order:

- First choose two vertices $u$ and $v$ from the tree;
- Then pay $w_u+w_v$ coins, and add an edge between vertices $u$ and $v$;
- At last, replace $w_u+1$ with $w_u$, replace $w_v+1$ with $w_v$.

Your task is to calculate the minimum number of coins to be paid.

But you don't know which vertex $u$ is, so you need to find the answer for each $1\le u\le n$. Please answer all the queries independently.

inputFormat:
The first line contains a single integer $n(2\le n\le 10^6)$ --- the number of vertices in this tree.

The next line contains $n$ numbers, the $i$ -th number is $w_i(1\le w_i\le n)$.

The next $n-1$ lines contain a description of the tree's edges. The $i$ -th of these lines contains two integers $u_i$ and $v_i(1\le u_i,v_i\le n) $ --- the numbers of vertices connected by the $i$ -th edge.

It is guaranteed that the given edges form a tree.

outputFormat: Print $n$ integers, the $i$ -th integer is the answer when $u=i$.


title: [ICPC2024 Xi'an I] Make Them Straight

description:
There is a sequence $a$ of non-negative integers of length $n$, the $i$-th element of it is $a_i(1\leq i\leq n)$.

A sequence is defined as 'good' if and only if there exists a non negative integer $k(0\leq k\leq 10^6)$ that satisfies the following condition:

$a_{i}=a_{1}+(i-1)k$ for all $1\leq i\leq n$.

To make this sequence 'good', for each $i(1\leq i\leq n)$, you can do nothing, or pay $b_i$ coin to replace $a_i$ with any non-negative integer.

The question is, what is the minimum cost to make this sequence 'good'.

inputFormat:
The first line contains an integer $n(1\leq n\leq 2\times 10^5)$, described in the statement.

The second line contains $n$ integers $a_1,...,a_n(0\leq a_i\leq 10^6)$.

The third line contains $n$ integers $b_1,...,b_n(0\leq b_i\leq 10^6)$.

outputFormat: One integer, the answer.


title: [ICPC2024 Xi'an I] Dumb Robot

description:
You have a dumb robot, and you are going to let it play games with $n$ robots.

There is a matrix $A$ with three rows and three columns in the game. We call the number of row $i$ and column $j$ of this matrix $A_{i,j}$. The game goes like this:

Two players each choose an integer from $[1,3]$ at the same time. We call the number your robot chooses $i$, and the number the other robot chooses $j$.
The score is $A_{i,j}$.
In game $i$, your robot will play this game with the $i$ -th robot. The $i$ -th robot has a probability of choosing $1$ as $p_{i,1}$, a probability of choosing $2$ as $p_{i,2}$, and a probability of choosing $3$ as $p_{i,3}$.

Your goal is to make the expected value of the score not negative in each game. But your robot is very dumb, so it will choose $1$ with probability $q_1$, $2$ with probability $q_2$, and $3$ with probability $q_3$, and you don't know the value of $q_1,q_2,q_3$.

We all know that $q_1+q_2+q_3=1$. If $q_1,q_2,q_3$ are chosen uniformly at random from a set of all possible cases, please calculate the probability that you will reach your goal.

inputFormat:
The first line contains one integer $n$($1\le n\le10^4$).

Each of the next $3$ lines contains $3$ integers, the $j$ -th integer in the $i$ -th of these lines is $A_{i,j}$($-20\le A_{i,j}\le20$).

Each of the next $n$ lines contains $3$ real numbers, the $j$ -th number in the $i$ -th of these lines is $p_{i,j}$. It is guaranteed that $p_{i,1}+p_{i,2}+p_{i,3}=1$ and $0\le p_{i,j}$.

outputFormat:
Output the answer to the problem. It is guaranteed that the answer will never be $0$.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-2}$. Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\frac{|a-b|}{max(1,|b|)} \leq 10^{-2}$.

hint: In example $1$, for example, $(q_1=1,q_2=0,q_3=0)$ is ok. In this case, Your robot will always choose $1$, so no matter what number will robot $1$ choose, the score will always be $1$, which is enough to reach your goal.


title: [ICPC2024 Xi'an I] XOR Game

background:
# statement updated:
$z$ is the number of numbers whose values are $0$.

description:
Alice and Bob are playing a game against each other.

In front of them are a multiset $\{a_i\}$ of non-negative integers and a single integer $x$. Each number in $a$ is $0$ or $2^i(0\le i<k)$ before the game.

This game will be a turn-based game, and Alice will go first. In one person's turn, he or she will choose an integer from $a$. Let this number be $p$. Then this person will choose whether or not to make $x\gets x\oplus p$, then remove $p$ from $a$. Here, operation $\oplus$ means bitwise xor.

Alice wants to make $x$ as big as possible, and Bob wants to make $x$ as small as possible.

You are a bystander who wants to know the final value of $x$. However, the size of $a$ is a huge number. Formally, there are $b_i$ numbers whose values are $2^i$ in $a$ for all $0\le i<k$, and $z$ numbers whose values are $0$. But you still want to challenge this impossible problem.

If Alice and Bob are smart enough, please output the final value of $x$.

inputFormat:
The first line contains two integers $k,z(1\le k\le10^5,0\le z\le 10^9)$.

The next line contains $k$ integers, the $i$ -th integer is $b_{i-1}(0\le b_{i-1}\le10^9)$.

outputFormat: Output the answer in binary format. Note that you should output exactly $k$ digit from high to low even though this number has leading $0$s.


title: [ICPC2024 Xi'an I] The Last Cumulonimbus Cloud

description:
Every April, the city is always shrouded under cumulonimbus clouds.

This city is connected by $n$ buildings and $m$ two-way streets. In order to facilitate people's travel, any two buildings can directly or indirectly reach each other through the streets. At the same time, no street connects the same building, and there is at most one street that connects each pair of buildings.

The pace of life in this city is very slow because the city layout is not very bulky.

Specifically,if we consider this city as an undirected graph $G$ ,it is guaranteed that for any non empty subgraph in this graph,there is at least one building inside it that connects up to 10 streets within the subgraph.

The rain is not stopping, and the number of cumulonimbus clouds is constantly increasing. At the beginning, there are $a_i$ cumulonimbus clouds above the $i$ -th building, but in the following $q$ days, one of the following two events will occur every day:

- $\text{1 x v}$ $v$ cumulonimbus clouds have been added over the $x$ -th building.
- $\text{2 x}$ you need to report how many cumulonimbus clouds are in total over all buildings directly connected to building $x$.

inputFormat:
The first line contains three integers $n,m,q(1\le n\le 3\times 10^5,1\leq m\leq 3\times 10^6, 1\leq q\leq 2\times 10^6)$.

Each of the next $m$ lines contains two integers $x,y(1\leq x,y\leq n,x\neq y)$, which represents a street connecting the $x$ -th and $y$ -th buildings.

Each of the next $n$ lines contains an integer $a_i(0\leq a_i\leq 100)$.

Each of the next $q$ lines contains two or three integers, if the first integer is $1$, it represents a first type of event, and the next two integers represent $x,v(0\leq v\leq 100)$. If the first integer is $2$, it represents a second type of event, the next integer represents $x$.

outputFormat: Several rows, each representing a query result for a second type of event.

translation:
你有一个 $n(1\le n\le 3\times 10^5)$ 个点，$m(1\le m\le 3\times 10^6)$ 条边的无向图。

保证这个图的任意一个非空子图都至少有一个点的度数小于 $10$。

每个点初时有一个权值 $a_i$。

现在要执行 $q(1\le q\le 2\times 10^6)$ 次操作：

- $\text{1 x v}$ 给第 $x$ 个点的权值加 $v$。
- $\text{2 x}$ 询问第 $x$ 个点所有相邻的点的权值之和（不包括自己）。


title: [APIO2024] 九月

background:
## 请勿使用 C++14(GCC9) 提交

杭州市的中心广场有一棵著名的古树。这棵古树可以看作一棵 $N$ 个节点的有根树，节点编号从 $0$ 到 $N - 1$，其中 $0$ 号节点是根节点。

称没有孩子的节点为叶子节点。古树每次落叶时，会选择一个当前的叶子节点删去。每一天中，古树可能会多次落叶。

有 $M$ 位志愿者（编号从 $0$ 到 $M - 1$）负责看护古树。每一位志愿者将各自按照如下方式独立记录今年的落叶的情况：

每一天，收集所有新的落叶的编号（即当天删除的节点的编号），然后将它们按任意顺序写在先前的落叶编号之后。

例如：第一天，叶子 $3$ 和 $4$ 落下，于是他们写下 $3, 4$ 或 $4, 3$。第二天，叶子 $1$ 和 $2$ 落下，于是他们继续写下 $1, 2$ 或 $2, 1$。最终的记录可能为 $(3, 4, 1, 2)$，$(4, 3, 1, 2)$，$(3, 4, 2, 1)$ 或 $(4, 3, 2, 1)$ 中的任意一个。

这个过程持续了 $K$ 天，每天都有新的叶子掉落，直到只剩根节点为止。

你在旅途过程中经过了杭州。此刻已是寒冬，仰望古树光秃秃的枝干，你不禁想起落叶纷飞的美丽景象。

你很想知道今年有几天能看见落叶，但你只能找到 $M$ 位志愿者的记录。尝试根据这些记录推断出 $K$ 可能的最大值。

description:
你无需在程序开头引入库 `september.h`。

你只需要实现以下函数：

```cpp
int solve(int N, int M, std::vector<int> F,
            std::vector<std::vector<int>> S);
```

+   $N$：古树的节点数量。
+   $M$：志愿者的数量。
+   $F$：一个长度为 $N$ 的数组。对于 $1 \le i \le N - 1$，$F[i]$ 表示节点 $i$ 的父亲节点的编号。$F[0]$ 始终为 $-1$。
+   $S$：一个长度为 $M$ 的数组。$S$ 中的每个元素是一个长度为 $N - 1$ 的数组。$S[i][j]$ 表示志愿者 $i$ 记录的第 $j$ 个节点编号（从 $0$ 开始）。
+   该函数必须返回一个整数，表示根据如上规则的 $K$ 可能的最大值（即，最大可能的落叶天数）。
+   对于每个测试点，交互库可能调用该函数多于一次。每次调用都应该作为新的情况分别处理。

注意：由于函数调用可能会发生多次，选手需要注意之前调用的残余数据对于后续调用的影响，尤其是全局变量的状态。

inputFormat:
评测程序示例读取如下格式的输入：

+   第 1 行：$T$

对于接下来 $T$ 组数据中的每一组：

+   第 $1$ 行：$N\ M$
+   第 $2$ 行：$F[1]\ F[2]\ \ldots\  F[N - 1]$
+   第 $3 + i\ (0 \le i \le M - 1)$ 行：$S[i][0]\ S[i][1]\ S[i][2]\ \ldots\ S[i][N - 2]$

outputFormat:
评测程序示例按照如下格式打印你的答案：

对于每组测试数据：

+   第 1 行：函数 `solve` 的返回值


title: [APIO2024] 星际列车

background:
## 请勿使用 C++14(GCC9) 提交

在 2992 年，机器人已经取代了人类的大部分工作，大家都有着大量的空闲时间。因此你和家人决定利用这些时间来一场星际旅行。

有 $N$ 个人类已经可以到达的行星，编号为 $0$ 到 $N - 1$，以及 $M$ 种不同的星际列车路线。第 $i$ 种列车路线 ($0 \le i < M$) 在时间 $A[i]$ 从行星 $X[i]$ 出发，在时间 $B[i]$ 到达行星 $Y[i]$，票价为 $C[i]$。在行星之间，这些星际列车是仅有的交通方式。对于你搭乘的一列星际列车，你只能在它的终点站下车，并且你搭乘的下一趟列车的起点站必须和这趟列车的终点站相同（这里认为换乘不耗时）。形式化地，你可以依次乘坐第 $q[0], q[1], \ldots, q[P]$ 次列车，当且仅当对任意 $1 \le k \le P$ 都有 $Y[q[k - 1]] = X[q[k]]$，$B[q[k - 1]] \le A[q[k]]$。

在不同行星之间移动是非常耗时的，所以除了车票钱，餐费支出也不可忽视。列车上免费提供不限量的食物，也就是在列车上吃饭不花钱：如果你决定乘坐第 i 种星际列车，则在任何 $A[i]$ 到 $B[i]$ 之间的时刻（包括端点）你都可以免费吃任意多顿饭。但如果你决定在行星 $i$ 吃饭，每顿饭都需要 $T[i]$ 元。

你和家人在旅途中总共需要吃 $W$ 顿饭，第 $i\ (0 \le i < W)$ 顿饭可以在 $L[i]$ 到 $R[i]$（包括端点）的任何时刻吃，吃饭不耗费时间。吃饭没有顺序要求，例如允许在吃完第 $1$ 顿饭后再吃第 $0$ 顿饭（见样例 $2$）。

现在是 $0$ 时刻，你和家人正在 $0$ 号行星上。你需要求出到达 $N - 1$ 号行星的最小花费，花费定义为车票价格和餐费之和。如果无法到达 $N - 1$ 号行星，最小花费定义为 $-1$。

description:
你无需在程序开头引入库 `train.h`。

你只需要实现以下函数：

```cpp
long long solve(int N, int M, int W, std::vector<int> T,
                std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C,
                std::vector<int> L, std::vector<int> R);
```

+   $N$：行星数量。
+  $ M$：星际列车路线数量。
+   $W$：需要用餐的次数。
+   $T$：一个长度为 $N$ 的数组。$T[i]$ 表示在行星 $i$ 每次用餐的花费。
+   $X, Y, A, B, C$：五个长为 $M$ 的数组。$(X[i], Y[i], A[i], B[i], C[i])$ 描述了第 $i$ 条列车路线。
+   $L, R$：两个长为 $W$ 的数组。$(L[i], R[i])$ 描述了第 $i$ 顿饭的用餐时间。
+   你需要返回从行星 $0$ 到达行星 $N - 1$ 的最小花费。如果行星 $N - 1$ 不可达，返回 $-1$。
+   每个测试点中，该函数恰好被调用一次。

outputFormat:
评测程序示例按照如下格式打印你的答案：

+   第 $1$ 行：函数 `solve` 的返回值


title: 【MX-X4-T4】「Jason-1」一步最优

description:
对于如下问题：

- 给定长度为 $n$ 的数列 $a_1, \ldots, a_n$（其中 $a_i$ 可能为负数）以及一个正整数 $m$。
- 你需要选择不超过 $m$ 个数列 $a$ 的下标区间 $[l_j, r_j]$，且确保它们互不相交。
- 你需要最大化选择的区间中的元素之和的总和，即最大化 $\sum_j \sum_{i = l_j}^{r_j} a_i$。

考虑该贪心算法（并不正确）：

- 重复如下过程 $m$ 次：
- 在所有与当前已选择的区间不相交的区间（包括空区间）中，选择一个元素之和最大的区间。
  - **如果有多个元素之和最大的区间，从中任意选择一个。**
  - 注：若选择了空区间，等价于中止过程，即选择的区间数量不超过 $m$ 个。
- 将如上过程中选择的所有非空区间中的元素之和作为答案。

现给定 $n$ 和数列 $a_1, \ldots, a_n$，对于每个 $m \in [1, n]$，请求出该算法可能得到的答案（即区间和的总和）的最大值和最小值。

inputFormat:
**本题输入包含多组数据。**

第一行，一个正整数 $T$，表示数据组数。对于每组数据：

- 第一行，一个正整数 $n$。
- 第二行，$n$ 个整数 $a_1, \ldots, a_n$。

outputFormat:
对于每组数据：

- 第一行，$n$ 个整数，第 $i$ 个整数表示当 $m = i$ 时，该算法能够得到的答案的**最大值**；
- 第二行，$n$ 个整数，第 $i$ 个整数表示当 $m = i$ 时，该算法能够得到的答案的**最小值**。

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

对于第一组数据，

- 一种取到最大值的方案为，依次选择区间 $[1,1],[3,3],[5,5],\varnothing, \varnothing$；
- 一种取到最小值的方案为，依次选择区间 $[1,5],\varnothing,\varnothing,\varnothing,\varnothing$。

对于第二组数据，

- 一种取到最大值的方案为，依次选择区间 $[3,5],[1,1],\varnothing,\varnothing,\varnothing$；
- 一种取到最小值的方案为，依次选择区间 $[1,5],\varnothing,\varnothing,\varnothing,\varnothing$。

需要注意：在第一次更新时，无法选择区间 $[1,1],[1,3],[3,3]$ 等，因为它们不满足区间和在所有 $S$ 中的区间内最大（即 $= 3$）。在任意一次更新时，都无法选择区间 $[2,2]$，因为其区间和为 $-2$，而 $-2 < 0$（即空区间的区间和）。

对于第三组数据，只有唯一的选择方案，即依次选择区间 $[6,6],[1,2],[4,4],\varnothing,\varnothing,\varnothing$。

**【数据范围】**

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

| 子任务 | $n \le$ | $\sum n \le$ | 分值 |
| :----------: | :----------: | :----------: | :----------: |
| 1 | $10$ | $50$ | $17$ |
| 2 | $100$ | $500$ | $24$ |
| 3 | $2000$ | $10^4$ | $13$ |
| 4 | $10^4$ | $5 \times 10^4$ | $9$ |
| 5 | $10^5$ | $5 \times 10^5$ | $37$ |

对于 $100 \%$ 的数据，$1 \le T \le 10^4$，$1 \le n \le 10^5$，$\sum n \le 5 \times 10^{5}$，$|a_i| \le 10^9$。


title: [THUPC 2024 决赛] 古明地枣的袜子

description:
你需要维护一个序列 $a_1,\dots,a_n$ 。

给定一个操作序列 $(x_1,y_1),\dots,(x_n,y_n)$ ，操作 $(x,y)$ 表示将 $a_1,\dots,a_x$ 的值加上 $y$ 。

共 $m$ 次查询，每次查询给出 $l,r$ ，问对初始值为 $0$ 的序列 $a$ 依次执行操作 $(x_l,y_l),\dots,(x_r,y_r)$ ，最后 $\max\limits_{i=1}^n a_i$ 的值。

inputFormat:
第一行两个整数 $n,m$ （$1\le n,m\le 5\times 10^5$）；

接下来 $n$ 行每行两个整数 $x_i,y_i$（$1\le x_i\le n, |y_i|\le n$）；

接下来 $m$ 行，每行两个整数 $l,r$（$1\le l\le r\le n$）。

outputFormat: 输出 $m$ 行，每行一个整数，表示每次查询的答案。

hint:
**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: [THUPC 2024 决赛] 研发计划

description:
看到近期若干家大模型创业公司获得高额融资，作为炼丹大师的你心痒难耐，决定入局，亲自下场搞产品。

经过一段时间的梳理，你发现当前共有 $m$ 种产品推出后将会大卖，其中第 $i$ 个产品推出之后预期获得 $g_i$ 的收益。这 $m$ 种产品涉及 $n$ 种技术：共有 $p$ 条技术-产品依赖关系 $(u,v)$ ，表示第 $u$ 个技术是第 $v$ 个产品的前置技术。对于每个产品，你必须获得它的全部前置技术之后才能推出。

对于第 $j$ 个技术，你可以选择花费 $f_j$ 的代价直接从其他公司购买获得，或者花费 $h_j$ 的代价通过研发获得。研发需要一定的条件：给出 $q$ 条技术-技术依赖关系 $(a,b)$ ，表示第 $a$ 个技术是第 $b$ 个技术的前置技术，那么必须在获得了技术 $j$ 的所有前置技术后才能通过研发获得技术 $j$ 。若某个技术没有前置技术，那么你可以直接通过研发获得。保证技术-技术依赖关系构成一个有向无环图，即不会发生循环依赖（自然不会有自环）。

一个方案的收益为推出的产品的收益总和减去获得的技术的代价总和。现在，作为一个商人，你希望研究一些技术、推出一些产品，最大化你获得的收益。为简单起见，你只要输出最大的收益值。

inputFormat:
输入的第一行包含四个正整数 $n,m,p,q$，保证 $2 \le n \le 100, 1 \le m \le 100, 1 \le p\leq nm, 1 \le q\leq \frac{n(n-1)}{2}$ ，分别表示技术总数、产品总数、技术-产品依赖关系总数以及技术-技术依赖关系总数。

接下来一行 $n$ 个整数 $f_i$ ，表示直接购买第 $i$ 个技术的代价。

接下来一行 $n$ 个整数 $h_i$ ，表示在前置技术基础上研究第 $i$ 个技术的代价。

接下来一行 $m$ 个整数 $g_i$，表示第 $i$ 个产品推出之后获得的收益。

接下来 $p$ 行，第 $i$ 行两个整数 $u_i,v_i$ ，表示技术-产品依赖关系 $(u_i,v_i)$，保证 $1 \le u_i \le n$，$1 \le v_i \le m$，输入的所有 $(u_i,v_i)$ 两两不同。

接下来 $q$ 行，第 $i$ 行两个整数 $a_i,b_i$ ，表示技术-技术依赖关系 $(a_i,b_i)$，保证 $1 \le a_i \ne b_i \le n$，输入的所有 $(a_i,b_i)$ 两两不同，且不构成循环依赖。

保证所有输入数字均为不超过 $10^9$ 的非负整数。

outputFormat: 输出一个整数表示收益最大方案的收益。

hint:
最优方案是依次研究技术 1，购买技术 3，研究技术 4，这时我们就能推出产品 1、4、5 了。此时收益为 $(2+8+8)-(1+6+3)=8$。

**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: [THUPC 2024 决赛] RPG

description:
小 I 正在打一款回合制 RPG 的最终 boss 战。这一战中，主角和 TA 的 $(n-1)$ 个队友（也就是总共 $n$ 个人）会按照固定的顺序依次行动，目标是对 boss 产生尽可能高的总伤害。

游戏设定中共有 $x$ 种攻击模式，第 $i (1 \le i \le x)$ 种攻击模式会对 boss 产生 $d_i$ 的基础伤害。

在行动过程中可以对 boss 附着异常状态。异常状态共 $y$ 种，同一时刻 boss 不会陷入两种异常状态。当 boss 陷入特定的异常状态时，使用特定的攻击模式会触发暴击，产生更大的伤害。暴击的规则由 $m$ 个三元组 $(p_j, q_j, c_j)$ 给出，表示在附着第 $p_j (1 \le p_j \le y)$ 种异常状态时使用第 $q_j (1 \le q_j \le x)$ 种攻击模式会**额外**产生 $c_j$ 的伤害。

对战开始时，boss 没有陷入任何的异常状态。按照行动顺序，第 $i (1 \le i \le n)$ 个人可以进行以下三种行动：

- 使用法术使 boss 陷入第 $a_i$ 种异常状态，若 boss 之前陷入了其他异常状态，则之前的异常状态被移除。
- 使用第 $b_i$ 种攻击模式对 boss 进行攻击，无论是否触发暴击，在产生伤害之后 **boss 的异常状态被移除**。
- 摸鱼，即什么都不做，此时 boss 的异常状态被保留。

作为剧情党，小 I 自然是不想自己算最优策略，于是他把问题丢给了你。于是你需要求出 $n$ 次行动内总共能产生最多多少伤害。

inputFormat:
输入的第一行四个整数 $n, m, x, y (1 \le n, m, x, y \le 2 \times 10^5)$，分别表示行动次数、暴击规则数、攻击模式种类数和异常状态种类数。

第二行 $x$ 个整数 $d_1,d_2,\cdots,d_x (1 \le d_i \le 10^9)$，依次描述每种攻击模式对 boss 产生的基础伤害量。

接下来 $n$ 行第 $i$ 行两个整数 $a_i, b_i (1 \le a_i \le y, 1 \le b_i \le x)$，按照行动次序描述第 $i$ 个人的行动。

接下来 $m$ 行第 $j$ 行三个整数 $p_j, q_j, c_j (1 \le p_j \le y, 1 \le q_j \le x, 1 \le c_j \le 10^9)$，描述第 $j$ 条暴击规则。保证 $(p_j, q_j)$ 两两不同。

outputFormat: 输出一行一个整数，表示 $n$ 次行动对 boss 产生的伤害量总和的最大值。

hint:
样例中共有两种攻击模式和两种异常状态，其中第一种攻击模式会造成 $10$ 的基础伤害，第二种攻击模式会造成 $1$ 的基础伤害。暴击规则仅有一条：在第二种异常状态下进行第二种攻击会额外造成 $10^9$ 的伤害。

最优的行动策略如下：

- 第一个人使用法术使 boss 陷入第二种异常状态；
- 第二个人摸鱼，boss 仍然陷入第二种异常状态；
- 第三个人使用第二种攻击模式，产生 $1$ 的基础伤害和 $10^9$ 的暴击伤害，boss 的异常状态被清除；
- 第四个人使用第二种攻击模式，产生 $1$ 的基础伤害。

总伤害量为 $1 + 10^9 + 1 = 10^9+2$。

**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: [THUPC 2024 决赛] 黑白

description:
小 I 和小 J 又在玩游戏。

游戏在一个 $n \times m$ 的网格上进行，我们用二元组 $(x,y)$ 描述第 $x$ 行第 $y$ 列的格子，其中 $1 \le x \le n, 1 \le y \le m$。初始时，网格上有至少一个格子是白色的，其他格子是黑色的。

小 I 和小 J 轮流操作，小 I 先手。每次操作时，操作方必须选择恰好一个白色的格子并将其染黑。

称两个格子相邻当且仅当它们共用一条边。若某次操作后，格子 $(1,1)$ 不是白的，或者格子 $(n,m)$ 不是白的，或者无法从 $(1,1)$ 出发，每次经过相邻的白色格子，最终到达 $(n,m)$（即 $(1,1)$ 和 $(n,m)$ 不在同一个白色格子构成的四连通块内），则当前操作方输，另一方胜利。

你作为游戏的观众，想知道在小 I 和小 J 绝顶聪明的情况下，谁会获胜。

inputFormat:
**本题有多组测试数据。** 输入的第一行一个整数 $T (1 \le T \le 100)$ 表示测试数据组数，接下来依次输入每组测试数据。对于每组测试数据，

- 第一行两个整数 $n, m (2 \le n, m \le 1000)$，表示网格的大小。
- 接下来 $n$ 行每行一个长度为 $m$、字符集为 `BW` 的字符串，描述网格初始时的染色情况。其中第 $i$ 行第 $j$ 个字符为 `B` 表示 $(i,j)$ 初始为黑色，否则为 `W` 表示 $(i,j)$ 初始为白色。保证初始棋盘上至少有一个白色格子。

保证单个测试点中所有测试数据的 $n \times m$ 的和不超过 $5 \times 10^6$。

outputFormat: 对于每组测试数据输出一行一个字符，若小 I 必胜输出 `I`，否则若小 J 必胜输出 `J`。

hint:
对于第一组测试数据，小 I 只能染黑 $(2,1)$，但染黑 $(2,1)$ 会导致无法仅通过每次移动到相邻的白色格子从 $(1,1)$ 移动到 $(2,2)$，因此无论小 I 如何操作都将失败，故输出 `J`。

对于第二组测试数据，小 I 可以染黑 $(1,2)$，然后无论小 J 如何操作都将失败，故输出 `I`。

**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: [THUPC 2024 决赛] 转化

description:
有 $n$ 种物品和 $m$ 种转化方式。第 $i$ 种转化方式可以将一个第 $a_i$ 种物品转化成 $k_i$ 个互不相同的物品，其中第 $j$ 个的种类是 $b_{i,j}$。同一种转化方式可以使用任意多次。

你有一些物品。你想知道，对于每一种特定的物品 $d$，你用这些你所拥有的物品可以分别转化出最多多少个该种物品。

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

第二行 $n$ 个非负整数，其中第 $i$ 个为 $c_i$，表示你拥有的第 $i$ 种物品的数量。

接下来 $m$ 行，其中第 $i$ 行表示第 $i$ 种转化方式。

转化方式的格式为：一行 $k_i+2$ 个正整数，其中第一个为 $a_i$，第二个为 $k_i$，之后为 $k_i$ 个互不相同的正整数 $b_{i,1},b_{i,2},\cdots,b_{i,k_i}$。

保证 $1\le n \le 100$，$1\le m \le 1000$。

保证 $1\le a_i,k_i,b_{i,j} \le n$。

保证 $0\le c_i \le 1000$。

outputFormat: 输出 $n$ 行，其中第 $d$ 行表示第 $d$ 种物品最多能有多少个。如果可以任意多，即对于任意的 $N$ 都存在一种方案使得有超过 $N$ 个第 $d$ 种物品，输出 `infinity`。

hint:
不使用任何转化方式，可以得到一个物品 $1$。

使用一次第一种转化方式，可以把物品 $1$ 变成物品 $2$ 和物品 $4$。这样可以得到一个物品 $2$。

使用一次第二种转化方式，可以把物品 $1$ 变成物品 $3$。这样可以得到一个物品 $3$。

使用一次第一种转化方式，可以把物品 $1$ 变成物品 $2$ 和物品 $4$。然后再使用一次第三种转化方式，可以把物品 $2$ 变成物品 $4$。这样可以得到两个物品 $4$。

可以证明这四种方案分别是当 $d=1,2,3,4$ 时的最优方案。

**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: [THUPC 2024 决赛] 机器人

background: 注意本题的指令含义与初赛的略有不同。

description:
有 $n$ 个机器人围成一圈，编号按照逆时针顺序分别为 $0\sim n-1$。

每个机器人有两只手。编号为 $i$ 的机器人初始「左手」指向编号 $l_i$ 的机器人，「右手」指向编号 $r_i$ 的机器人。

所有的机器人内部都写有一条「指令」，「指令」有以下这些形式：

### 指令

下面介绍这些「指令」的格式以及它们被「执行」时的效果。文中的“自己”一词均指拥有这条「指令」的机器人。

- `SLACKOFF`：**「摸鱼」**，即什么也不做。
- `MOVE h z`：将第 $h$ 只手向逆时针方向 **「移动」** $z$ 个机器人的位置。当 $h=0$ 时表示「左手」，当 $h=1$ 时表示「右手」，下同。
- `SWAP`：**「交换」** 双手指向的机器人的「指令」。
- `TRIGGER <COMMANDNAME>: <COMMAND>`：其中 `<COMMANDNAME>` 为 `SLACKOFF`、`MOVE`、`SWAP`、`TRIGGER`、`TOGGLETRIGGERREPLACE` 之一；`<COMMAND>` 表示一条完整的非 `TRIGGER` 「指令」。`TRIGGER` 指令本身不会被「执行」，但是，当一个**其他**机器人「执行」完一条「指令」之后，且「右手」指向自己的时候，自己满足如下条件的 `TRIGGER` 指令（如果有）就会被 **「触发」**——「执行」一次对应的 `<COMMAND>`：
  - `<COMMANDNAME>` 不为 `TRIGGER` 时，刚刚「执行」完毕的「指令」为 `<COMMANDNAME>` 指令；
  - `<COMMANDNAME>` 为 `TRIGGER` 时，刚刚「执行」完毕的「指令」是一条 `TRIGGER` 指令被「触发」时，「执行」的 `<COMMAND>` 部分。
- `TOGGLETRIGGERREPLACE h <COMMANDNAME> <NEWCOMMAND>`：如果第 $h$ 只手指向的机器人的「指令」是 `TRIGGER` 指令，则将其 **「切换」** 为该「指令」的 `<COMMAND>` 部分，即删去前面的 `TRIGGER` 及条件部分；如果这条「指令」不是 `TRIGGER` 指令，假设是 `<COMMAND>`，则将其「切换」为 `TRIGGER <COMMANDNAME>: <COMMAND>`。其中 `<COMMANDNAME>` 为 `SLACKOFF`、`MOVE`、`SWAP`、`TRIGGER`、`TOGGLETRIGGERREPLACE` 之一。然后将自己的「指令」（注意这可能不仅仅包含正在「执行」的那部分「指令」）修改为 `<NEWCOMMAND>`。其中，`<NEWCOMMAND>` 是一条完整的「指令」。

机器人「执行」各「指令」时的输出格式如下：

- 「摸鱼」时输出 `Robot <id> slacks off.`。其中 `<id>` 为一个整数，表示「执行」当前「指令」的机器人编号，下同。
- 「移动」时输出 `Robot <id> moves its <side> hand towards Robot <id2>.`。其中 `<side>` 为 `left` 或 `right`，表示移动了哪只手（`left` 表示「左手」，`right` 表示「右手」）；`<id2>` 为一个整数，表示移动之后这只手指向的机器人的编号。
- 「交换」时输出 `Robot <id> swaps the commands of Robot <id2> and Robot <id3>.`。其中 `<id2>` 和 `<id3>` 为整数，表示被「交换」「指令」的机器人编号，这两个数可以按任意顺序输出。
- 「切换」时输出 `Robot <id> toggles the trigger property of the command of Robot <id2>`。
- `TRIGGER` 指令不会被「执行」，但当它们被「触发」时，会按照上面的格式输出对应的「指令」被「执行」的信息。

你按照一定顺序选择了一些机器人（可能重复选择）并「执行」了对应机器人的「指令」，得到了「执行」的**完整**输出，也就是说，在「执行」完输出中最后一条「指令」之后，没有其他「指令」被「触发」。但是，你忘记了你选择机器人的顺序，也忘了每个机器人开始时有什么「指令」。你只记得机器人的总数以及开始时每个机器人的手指向什么位置。

你想通过已知的所有信息还原出最初所有机器人的「指令」都是什么。

inputFormat:
第一行两个正整数 $n,k$，其中 $k$ 表示输出的总行数。

接下来 $n$ 行，每行两个整数 $l_i,r_i$，按编号从小到大的顺序输入。

接下来 $k$ 行，每行一条「执行」「指令」的输出信息。

为了减轻处理输入的负担，输出信息被简化如下（没有特殊声明的参数信息含义同上）：

- 「摸鱼」时输出 `SLACKOFF <id>`。
- 「移动」时输出 `MOVE <id> <side> <id2>`。其中 `<side>` 为 `0` 或 `1`，表示移动了哪只手（`0` 表示「左手」，`1` 表示「右手」）。
- 「交换」时输出 `SWAP <id> <id2> <id3>`。
- 「切换」时输出 `TOGGLETRIGGERREPLACE <id> <id2>`。
- `TRIGGER` 指令不会被「执行」，但当它们被「触发」时，会按照上面的格式输出对应的「指令」被「执行」的信息。

输入保证存在一组初始的「指令」，使得存在一种选择机器人的方式，能够得到对应的输出。

保证 $1\le n,k \le 500000$。

保证 $0\le l_i,r_i<n$。

outputFormat:
输出 $n$ 行，按编号从小到大输出机器人最初的「指令」，每条一行。

你需要保证「指令」格式正确，且 $0\le z < n$。

你需要保证你的输出文件不能过大。若你的输出文件大小不超过 $100\texttt{MB}$，则一定能保证 Special Judge 能够正确返回结果。

此外任何能够得到输入中 $k$ 行输出的答案均算作正确。

samples:
4 7
1 2
2 3
3 1
0 2
TOGGLETRIGGERREPLACE 0 1
SLACKOFF 3
MOVE 0 1 3
SWAP 1 2 3
TOGGLETRIGGERREPLACE 3 2
SLACKOFF 2
SLACKOFF 3

samples:
TOGGLETRIGGERREPLACE 0 MOVE MOVE 1 1
TRIGGER SLACKOFF: SWAP
TRIGGER SWAP: TOGGLETRIGGERREPLACE 1 TOGGLETRIGGERREPLACE SLACKOFF
SLACKOFF

samples:
4 4
2 1
1 2
0 3
1 3
SLACKOFF 0
SLACKOFF 1
SLACKOFF 2
SLACKOFF 3

samples:
SLACKOFF
TRIGGER SLACKOFF: SLACKOFF
TRIGGER SLACKOFF: SLACKOFF
TRIGGER TRIGGER: SLACKOFF

hint:
**样例解释 1**

选择机器人的顺序为 $1,1,0,1,3$，其中第二、六条被「执行」的「指令」是「触发」`TRIGGER` 指令之后被「执行」的。

注意 `TRIGGER` 指令「触发」的时机是在「执行」上一条「指令」之后，所以第一次「交换」之后由于 $1$ 号机器人的「右手」指向了写有 `TRIGGER SWAP: SWAP` 的 $0$ 号机器人，所以这条 `TRIGGER` 指令能被「触发」。

**样例解释 2**

选择机器人的顺序为 $0,3,0,1,3$，其中第五、六条被「执行」的「指令」是「触发」`TRIGGER` 指令之后被「执行」的。

第一次「执行」会使 $1$ 号机器人的「指令」变为 `SWAP`，$0$ 号机器人的「指令」变为 `MOVE 1 1`。

第五次「执行」会使 $2$ 号机器人的「指令」由 `SLACKOFF` 变为
```
TRIGGER TOGGLETRIGGERREPLACE: SLACKOFF
```
，$3$ 号机器人的「指令」由
```
TRIGGER SWAP: TOGGLETRIGGERREPLACE 1 TOGGLETRIGGERREPLACE SLACKOFF
```
会变为 `SLACKOFF` 而不是 `TRIGGER SWAP: SLACKOFF`。

**样例解释 3**

选择机器人的顺序为 $0$，其中第二、三、四条被「执行」的「指令」是「触发」`TRIGGER` 指令之后被「执行」的。

注意 $3$ 号机器人「执行」完「指令」后不会接着「触发」自己的 `TRIGGER` 「指令」，即使它的「右手」指向了自己。

另外，选择一个写有 `TRIGGER` 指令的机器人不会产生任何输出，所以这么做没有意义。

**样例解释 4**

见题目目录下的 *4.in*。该样例不提供样例输出。

**样例解释 5**

见题目目录下的 *5.in*。该样例不提供样例输出。

**提示**

我们会下发一个可执行文件 `checker` 来帮助你检查你的输出是否正确。使用方式为在该文件所在目录下使用如下指令：

```
./checker <输入文件路径> <你的输出文件路径>
```

若你的输出正确，程序会输出 `Accepted.`；否则会提示「执行」结果与输入文件最早一次不匹配的地方。

注意，若你使用的输入文件不是样例输入，该程序不会检查是否存在一组初始的「指令」，使得存在一种选择机器人的方式，能够得到对应的「执行」结果。

**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: [THUPC 2024 决赛] 采矿

background:
在精心地规划完工人的移动路线，执行完所有计划之后，你终于有钱了。你承包下了一个更大的矿坑，并购买了更先进的设备。

但是开始运行了你才发现，一部分运输矿物的通道居然装反了！还好它们本来就是可以反向的，并且中控的系统可以让你轻易地操作。

然而，现在最大的问题是，你刚刚接手这个矿坑，你甚至连它长什么样都不知道，也就更不知道每个开关是对应哪一条运输通道的。

时间就是金钱，你想要尽快摸清整个矿坑的结构以及所有开关与通道的对应关系。

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

已知你的矿坑有 $n$ 个节点，编号为 $1\sim n$。它们通过 $n-1$ 条运输通道连成一个树形结构。

运输通道都是单向的。对于一条从节点 $u$ 到节点 $v$ 的运输通道，可以将所有由节点 $u$ 产出的矿或运送到节点 $u$ 的矿以较快的速度运送到节点 $v$。如果一个节点有多条以其为起点的运输通道，那么会把这些矿平均分配给这些运输通道。

中控的系统包含 $n-1$ 个开关和一个监视器。开关的编号为 $1\sim n-1$，每个开关可以拨到 $0$ 或 $1$ 的位置。$n-1$ 个开关和 $n-1$ 条运输通道一一对应，但你并不知道它们的对应关系。你只知道，假设编号为 $i$ 的开关对应的运输通道在被装上去时是从 $u_i$ 到 $v_i$ 的，那么当开关拨到 $0$ 的时候，它的运输方向和它被装上去时相同；当开关拨到 $1$ 的时候，它的运输方向会变成从 $v_i$ 到 $u_i$。你的监视器可以监控到达每个节点的矿分别来自多少个不同的节点，也就是说，有多少个节点（包括其本身）能够通过运输通道把矿运输到这个节点。

当你调整完开关的位置后，需要等一段时间，监视器的结果才会趋于稳定，这时你的读数才是有意义的。所以为了避免浪费太多时间，你希望在 $50$ 次读数之内确定你想知道的所有信息。

inputFormat:
开始时你需要输入一个正整数 $n$。保证 $2\le n \le 10000$。

之后的输入会基于你的输出生成读数。你的读数结果是一行 $n$ 个正整数，其中第 $i$ 个表示到达节点 $i$ 的矿来自多少个不同的节点。

每个测试点中，矿坑的连接方式和所有运输通道刚装上去时的方向都是固定的，也就是说，这些不会因为你的输出而动态修改为另外一种符合之前所有回答的方案。

outputFormat:
当你需要调整开关并等待读数时，输出一行 `? s`，其中 `s` 为一个长为 $n-1$ 的 `01` 串，其中第 $i$ 位表示编号为 $i$ 的开关拨到的位置。然后交互库会在你的标准输入中给出监视器趋于稳定之后的读数结果。你最多只能读数 $50$ 次。

当你已经知道了所有通道的信息时，输出一行 `! u1 v1 ... un-1 vn-1`，其中 $u_i,v_i$ 表示编号为 $i$ 的开关对应的运输通道被装上去时的方向是从节点 $u_i$ 到节点 $v_i$ 的。

在输出一行之后，你需要刷新输出缓冲区，否则评测结果可能会变成 `TLE`。刷新输出缓冲区的方式为：

- C：`fflush(stdout);`

- C++：`fflush(stdout);` 或 `std::cout.flush();` 或使用 `std::endl` 换行

- Java：`System.out.flush();`

- Python：`sys.stdout.flush()`

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

通道的初始方向如上图所示。通道上的数字代表和通道对应的开关的编号。

样例只是用来说明输入输出格式和读数结果，并不意味着这次读数能够推出答案。

交互库的运行时间和内存不计入时间和内存限制。

若超出读数次数限制、最后的回答错误或输出格式错误，评测结果均为 `WA`。

**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: [THUPC 2024 决赛] 排列游戏

description:
有 $n$ 个格子排成一行，从左到右依次编号为 $1,2,\cdots,n$，每个格子上有一个数字卡片，初始状态下，格子 $i$ 上的卡片数字为 $i$。

打乱者会进行 $n$ 次交换操作来排列这些卡片：每次选择两个格子 $i,j$（$i\ne j$），然后交换格子 $i$ 和格子 $j$ 上的卡片。$n$ 次交换操作结束后，就完成了对卡片的排列。

然后轮到玩家行动，玩家同样需要用交换操作，每次交换两张卡片，目标是将这些卡片的顺序还原到初始状态。

交换格子 $i$ 和格子 $j$ 上的卡片所需的时间为 $|i-j|$，玩家打算用最短的时间还原该排列。问：有多少种可能的排列，玩家可以用不超过 $m$ 的总时间完成还原？两种排列不同，当且仅当至少有一张数字卡片在两种排列中所在的格子不同。

inputFormat:
每个测试点由多组数据组成。

第一行包含一个正整数 $T$，表示数据组数。保证 $T\le1,000$。

之后 $T$ 行，每行一组数据，包含两个正整数 $n$，$m$。保证 $2\le n\le500$，$m\le5,000$。

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

由于答案可能很大，请输出答案对 $1,000,000,007$ 取模的结果。

hint:
在第 $1$ 组数据中，打乱者的 $2$ 次操作均只可能是交换格子 $1$ 和格子 $2$ 上的卡片，只有 $1$ 种可能的排列，也就是初始状态 $[1,2]$。

在第 $2$ 组数据中，有 $2$ 种可能的排列：$[1,3,2]$ 和 $[2,1,3]$。注意初始状态 $[1,2,3]$ 不是一种可能的排列，因为打乱者进行前 $2$ 次交换之后，所有卡片要么仍在初始状态（前 $2$ 次交换的是同一对卡片），要么均不在初始位置上（前 $2$ 次交换的不是同一对卡片），第 $3$ 次交换后不可能回到初始状态。

在第 $3$ 组数据中，有 $7$ 种可能的排列：$[1,2,3,5,4]$，$[1,2,4,3,5]$，$[1,2,5,4,3]$，$[1,3,2,4,5]$，$[1,4,3,2,5]$，$[2,1,3,4,5]$，$[3,2,1,4,5]$。

**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: [THUPC 2024 决赛] 朔望

background: Syzygy，中文译作朔望，表示三个或三个以上的天体大致位于同一直线上。本题中主要探讨母恒星与至少两颗行星位于同一直线上的情况。

description:
在一个理想的行星系中，所有行星在同一平面内围绕共同的单一母恒星作匀速圆周的公转运动，且公转方向相同（如同为逆时针）。我们定义这样的行星系的 Syzygy 指数为平均每年发生的所有（含母恒星的）朔望的稀有程度之和，其中单次朔望的稀有程度是与产生连线的**行星**数量 $x$ 有关的常数 $w_x$；如果在行星系中同时发生多个朔望但不位于同一直线上，则对每条直线上的行星分别统计稀有程度。

现有一理想的包含 $n$ 颗行星的行星系，其中从内到外第 $i$ 颗行星绕母恒星公转周期为 $t_i$ 年（根据开普勒第三定律可知 $t_i$ 单调递增）。假设存在某一时刻，所有 $n$ 颗行星位于同一条以母恒星为端点的射线上。请求出该系统的 Syzygy  指数。

inputFormat:
第一行输入一个正整数 $n$（$2\le n\le 20$），表示该单星系统中行星的数量。

第二行输入 $n$ 个正整数 $t_1, t_2, \cdots, t_n$，分别表示公转轨道从内到外各行星的公转周期。保证 $1\le t_1 < t_2 < \cdots < t_n\le 10^9$。

第三行输入 $(n-1)$ 个正整数 $w_2, w_3, \cdots, w_n$（$1\le w_i\le 10^9$），分别表示发生不同数量的行星参与的朔望的稀有程度。

outputFormat: 输出该行星系的 Syzygy 指数。显然 Syzygy 指数是一个有理数；不妨假设其化为最简分式后的形式为 $p/q$（即其中 $p, q$ 互质），请输出 $x$ 使得 $qx\equiv p \pmod{10^9 + 7}$ 且 $0\le x<10^9 + 7$。可以证明，在本题数据范围下，$x$ 存在且唯一。

hint:
**样例解释 1**

不妨假设 $T=0$ 时刻两颗行星位于同一以母恒星为端点的射线上。由于两颗行星的公转周期的最小公倍数为 $12$ 年，且两颗行星的会合周期也恰为 $\displaystyle\frac{1}{\displaystyle\left|\frac{1}{3}-\frac{1}{4}\right|}=12$ 年，故可取 $T\in[0, 12)$ 年的行星系的运行情况作为研究对象。$T$ 取 $[0, 12)$ 中整数值时，行星系的运行情况分别如下各图所示：

{{ img('1.png', size = 0.5, align = 'middle', inline = False) }}

可以证明，在 $12$ 年的周期内，两颗行星仅发生如上图所示的 $2$ 次朔望（分别为 $T=0$ 时的内行星凌/外行星冲及 $T=6$ 年的合）。因此，该行星系的 Syzygy 指数为

$$
\frac{2\times 5}{12} = \frac{5}{6} \equiv 833333340 \pmod{10^9 +7}.
$$

**样例解释 2**

同理设 $T=0$ 时刻三颗行星位于同一以母恒星为端点的射线上。由 $\mathrm{lcm}(4, 5, 6)=60$，可取 $T\in[0,60)$ 年的行星系的运行情况作为研究对象。在这段时间内，发生的所有含母恒星的朔望如下图所示：

{{ img('2.png', size = 0.5, align = 'middle', inline = False) }}

因此，该行星系的 Syzygy 指数为

$$
\frac{14\times 7+2\times 8}{60}=\frac{19}{10}\equiv300000004 \pmod{10^9+7}.
$$

**样例解释 3**

同理设 $T=0$ 时刻四颗行星位于同一以母恒星为端点的射线上。由 $\mathrm{lcm}(4, 6, 8, 24)=24$，可取 $T\in[0,24)$ 年的行星系的运行情况作为研究对象。在这段时间内，发生的所有含母恒星的朔望如下图所示：

{{ img('3.png', size = 0.5, align = 'middle', inline = False) }}

因此，该行星系的 Syzygy 指数为

$$
\frac{20\times 20+0\times22+2\times 1207}{24}=\frac{1407}{12}\equiv250000119 \pmod{10^9+7}.
$$

**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: [THUPC 2024 决赛] 简单博弈

description:
有 $k$ 个棋盘。每个棋盘大小为 $n\times m$ ，上面有 $3$ 个位置是 $0$，其他是 $1$。

现在 A 和 B 轮流操作，每次操作需要指定一个棋盘，在该棋盘上选定一行或者选定一列或者选定一行一列，将其全部变成 $0$。但是要保证操作前后棋盘至少一个格子数字变了。

不能操作就输了。问是否先手必胜。

inputFormat:
输入的第一行包含一个正整数 $k$ 表示棋盘总数，保证 $1 \le k \le 10^5$。

接下来 $k$ 组数据，第 $i$ 组数据共 4 行，描述第 $i$ 张棋盘的样子：

* 第 1 行用空格隔开的两个正整数 $n,m$ 分别表示棋盘的行数和列数，保证 $1\le n,m \le 500$。
* 第 2-4 行，每行用空格隔开的两个正整数 $x,y$ 表示该棋盘上为 $0$ 的位置，保证互不相同且 $1\leq x\leq n, 1\leq y\leq m$ 。

outputFormat: 如果先手必胜，输出一个字符串 `OvO`，否则输出一个字符串 `QAQ`。

hint:
一开始棋盘为：

```
011
001
```

先手只需要选中第 1 行第 2 列即可全部清零，从而后手无法操作，先手获胜。

**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: [THUPC 2024 决赛] 贸易

description:
小 Z 生活的学校就像是一条链，直径很长，宽度很窄。

具体来说，这里有一个长度为 $n$ 的序列，每个位置有一个属性 $a_i\in \{0/1\}$ 和一个类型 $c_i$，在这里有一些贸易事件会发生。

小 Z 从左往右通过这个序列，若当前遇到一个 $0$ 属性的节点，则小 Z 可以购入至多一个 $c_i$ 类型的物品，若当前遇到一个 $1$ 属性的节点，则小 Z 可以卖出至多一个 $c_i$ 类型的物品，显然，在小 Z 没有这种类型的物品时是不能卖出的。

一次合法的交易定义为从某个节点买入，并在某个节点卖出，注意，你需要保证在最后小 Z 手里不存在任何东西。

给出 $q$ 次询问，每次小 Z 从 $l_i$ 顺序走到 $r_i$，问：最大合法交易次数是多少。

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

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

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

接下来 $q$ 行，每行两个数表示 $l_i,r_i$。

outputFormat: 输出共 $q$ 行，每行一个数表示当前这个询问中的最大合法交易次数。

hint:
对于所有数据，满足 $1\le n,q\le5\times 10^5,1\le c_i\le n,1\le l_i\le r_i\le n,a_i\in\{0,1\}$。

请注意输入输出效率。

**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: [THUPC 2024 决赛] 连向未来

background:
1 是烟消云散的过去。

2 是转瞬即逝的现在。

3 是遥不可及的未来。

过去的迷惘和烦恼连向了现在。如果梦想的热度至今不曾改变，那么不妨将迷惘和烦恼作为宝贵的经验。

现在也终将连向未来。通往未来的大门必定藏在世界上的某个角落。虽然可能无法简单寻得，但若不向前伸出双手，就无从触及。

想要创造从现在开始的崭新的时间，就需要将大家相连。1、2 和 3，缺一不可。只身一人所无法实现的目标，集齐众人的力量就必能跨过。就算形单影只时已足够努力奋斗，如果连在一起时都能各自加倍拼搏，那么不妨同舟共济，同音共律。

description:
给定一个 $N\times M$ 的网格。求在每个格子中分别填入 $1$，$2$ 或 $3$ 的方案数，使得填入后存在至少一种将具有公共边的格子分别相连的方案，满足：

- 每个填有 $1$ 或 $3$ 的格子**恰好**与相邻的任意一个填有 $2$ 的格子相连；

- 每个填有 $2$ 的格子**恰好**与相邻的任意一个填有 $1$ 的格子及任意一个填有 $3$ 的格子分别相连。

inputFormat:
输入第一行包括一个正整数 $T$，表示该测试点中的数据组数。保证 $1\le T\le 100$。

接下来 $T$ 行，每行包含两个由空格隔开的正整数 $N$ 和 $M$，表示网格的大小。保证 $1\le N\le 3$，$1\le M\le 10^9$。

outputFormat: 对每组数据输出一行，每行包括一个非负整数，表示填数方案数对 $998,244,353$ 取模之后的结果。

hint:
不是相遇会带来离别，而是离别会指引新的相遇。

**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: [THUPC 2024 决赛] 警钟长鸣

description:
一年两度的 THUPC 又到来了，小 Z 也掏出了他的传统艺能——压轴的整活签到题。对于往年来说，签到题总是能被选手们在刚开场便迅速通过，而这次，小 Z 决定整点不一样的——”如果我把签到题刻意搞得很谜语人，让选手刚开场抓耳挠腮哪怕一小会，岂不是很爽？“

说干就干，小 Z 精心设计了一套花里胡哨的障眼大法，望着最终的成品题目，小 Z 内心充满了得意。他甚至都开始想象起来，开场不久后选手们望着这道题毫无头绪，现场鸦雀无声，排行榜上一片沉寂的样子……

带着这种丰收的喜悦，小 Z 来到了比赛当日的赛场上。然而，随着开考声音的响起，赛场上却呈现出此起彼伏的窃窃私语声，小 Z 走上前去，只听得大家讨论的语气和情绪决不是正常讨论题目应当有的，许多人甚至忍不住笑出了声。

“奇怪，难道我的题目出了什么问题？”小 Z 疑惑地打开排行榜，只见此题的通过人数正在飞速上升，比以往的签到题还要快得多！“不，这不可能！”小 Z 双手颤抖地点开题目，在各个页面之间来回切换。突然，映入眼帘的内容使他瞬间呆住了。

是的你没猜错，小 Z 在这道题的命题环节中出现了严重的失误，使得选手可以轻而易举地通过此题！小 Z 从发现自己命题失误的震惊中稍稍缓和了过来，决定立即着手修复失误。然而，冷静思考后的小 Z 突然意识到了一个五雷轰顶的事实：他已经犯下了无法弥补的错误！

坦率而言，题目出现失误在比赛中并不罕见。大部分常见失误，如涉及到题面、评测数据、评测配置等环节，都可以通过赛时及时的修复来弥补，将损失降低至最小化。然而，小 Z 的失误恰恰是戳中了最致命的要害：选手已经获取到了本不应当获取到的、足以使他们轻松通过此题的信息，此时一切晚矣，一切努力都无法掩盖小 Z 已经捅了大篓子的事实。

“啊~”小 Z 感到一阵天旋地转，几近昏厥。

后续发生的一切，怎么处理的这一套烂摊子，在小 Z 的记忆中已变得模糊不清。时至今日，这一段传奇故事的细节早已散佚。而小 Z 在这过后沉寂了很久，终于决定痛定思痛，将这段往事进行艺术加工后向世人讲述，以示警钟长鸣。

inputFormat: 无输入。

outputFormat: 输出本题应当输出的内容。请注意，本题的输出是唯一且确定性的。

hint:
因为本题是直接输出答案，输出样例可以直接通过此题，所以并未在题面里渲染样例。

请工作人员在赛前仔细检查，不要把样例错发给选手。

**来源与致谢**

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>


title: 物理实验 (hard)

background: 莲子为了完善她的论文，决定研究一些物体的物理性质。由于工作实在是太多，她邀请你帮忙完成其中的一个小实验。不过，这次的略微困难一些。

description:
**这是该题的困难版本，两个版本之间的区别在于小球需要满足的条件不同。该题的满分为 50 分。**

莲子有一个初始在数轴 $0$ 点并向数轴正方向移动的小球。莲子在数轴的 $1$ 到 $n$ 这 $n$ 个点上设置了装置，当小球经过点 $i$ 时，她可以花费 $a_i$ 的代价让其改变移动方向（从数轴正方向切换为负方向，或者相反）。

莲子有 $m$ 个需要满足的条件，第 $i$ 个条件形如“小球需要从点 $x_i$ 移动到点 $y_i$ 至少 $k_i$ 次”，**其中** $x_i$ **大于** $y_i$。更详细的说，该条件即要求小球的移动路径形如 $\ldots\to x_i\to\ldots\to y_i\to\ldots\to x_i\to\ldots\to y_i\to\ldots$，其中从 $x_i$ 移动到 $y_i$ 的过程重复至少 $k_i$ 次。

莲子想要知道她至少要花费多少代价才能满足所有条件。

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

第二行 $n$ 个正整数描述序列 $a$。

接下来 $m$ 行中，第 $i$ 行依次给出三个正整数表示 $x_i$, $y_i$ 和 $k_i$。

outputFormat: 一行一个整数，表示莲子至少要花费多少代价才能满足所有条件。

hint:
### 样例解释

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

上图画出了样例 1 和样例 2 的具体构造方案，可供参考。

#### 样例 \#1

莲子让小球在经过点 $2$ 时反转方向，然后让其经过点 $1$ 时再反转方向。重复上述操作两次，最后再在点 $2$ 反转方向恰好能满足所有条件。总花费代价为 $8$。

注意到该样例符合特殊性质 $\mathbf{A}$。
#### 样例 \#2

莲子让小球依次在经过点 $3$、点 $2$、点 $3$ 时反转方向。总花费代价为 $8$。

### 数据范围

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

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n,m\le } & \bm{a_i\le} & \bm{x_i,y_i\le} & \bm{k_i\le} & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\cr\hline
1 & 10 & 10 & 100 & 10 & 10 & - &-\cr\hline
2 & 5 & 2\times 10^5 & 10^8 & 2\times 10^5 & 10^8 & \mathbf{A}&- \cr\hline
3 & 15 & 10^3 & 10^8 & 10^3 & 10^5 & -&1 \cr\hline
4 & 20 & 2\times 10^5 & 10^8 & 2\times 10^5 & 10^8 & -&1,2,3  \cr\hline
\end{array}
$$

特殊性质 $\mathbf{A}$：所有的 $k_i$ 均相等。

对于所有数据满足：$1\le n,m\le 2\times 10^5$，$1\le a_i\le 10^8$，$1\le y_i< x_i \le n\le 2\times 10^5$，$1\le k_i\le 10^8$。


title: [ICPC2024 Xi'an I] Holes and Balls

description:
You are given $n$ balls, the $i$ -th ball's value is $p_i$. It's guaranteed that $p_1,p_2,\dots,p_n$ is a permutation of $1,2,3\dots,n$.

There is also a rooted tree of $n$ vertices, each of the vertices is a hole, and each hole can only hold one ball.

The tree's root is the first vertex.

Now you need to fill the holes with the balls.

You need to throw each ball in order of $1$ to $n$ in the following steps:

1. Throw the ball into vertex $1$.
2. Let the vertex where the ball is be $p$.
3. If the $p$ -th vertex has already been filled with other balls, you need to choose a vertex $x$ and throw the ball into the $x$ -th vertex, then return to step $2$. You need to guarantee that the $x$ -th vertex is the $p$ -th vertex's son and at least one vertex in the subtree of the $x$ -th vertex is not filled.
4. Otherwise, the ball will fill the $p$ -th vertex.

After throwing all the balls, let $a_i$ express the value of the ball in the $i$ -th vertex.

You need to find the minimum lexicographical order of $\{a_n\}$.

We define $dep_i$ as the number of vertices on the path from the $i$ -th vertex to the tree's root(the first vertex).

Specially, for any two vertices $x<y$, it's guaranteed that $dep_x\le dep_y$.

inputFormat:
The first line contains a single integer $n(1\le n\le 5\times 10^5)$ - the number of vertices in this tree.

The next line contains $n$ numbers, the $i$ -th number is $p_i(1\le p_i\le n)$. It's guaranteed that $p_1,p_2,\dots,p_n$ is a permutation of $1,2,3\dots,n$.

The next $n-1$ lines contain a description of the tree's edges. The $i$ -th of these lines contains two integers $u_i$ and $v_i(1\le u_i,v_i\le n) $ - the numbers of vertices connected by the $i$ -th edge.

It is guaranteed that the given edges form a tree.

And for any vertices $x<y$, it's guaranteed that $dep_x\le dep_y$.

outputFormat: Output $n$ integers, the minimum lexicographical order of $\{a_n\}$.


title: [ICPC2024 Xi'an I] Smart Quality Inspector

description:
Ella has a factory. One day, her factory is facing a product quality inspection.

Her factory has $N$ production lines. Among the $N$ production lines, $N-K$ of them are qualified, and the other $K$ lines are unqualified. The fine of the $i$ -th$(1\leq i\leq K)$ unqualified line is $i$ Yuan.

There are $M$ quality inspectors here. For the $j$ -th$(1\leq j\leq M)$ quality inspector, he will inspect from the $l_i$ -th line to the $r_i$ -th line and find the unqualified production line with the largest fine among them, then impose this fine on Ella.

Ella does not want to receive so many fines, so she decides to renumber the $N$ production lines to receive the least amount of fines. Please help her.

In simple terms:

You have a sequence $A$ of length $N$, $A=[1,2,3,...,K,0,0,0,...,0]$. Here $N,K$ are given.

There are $M$ pairs of integers, each pair consists of two numbers $l_i,r_i$.

You need to rearrange sequence $A$ to minimize the following:

$$\sum_{i=1}^M \max_{j=l_i}^{r_i} (A_{j})$$

inputFormat:
The first line contains three integers $N,K,M(1\leq K\leq N\leq 20,1\leq M\leq 10^5)$, described in the statement.

Then $M$ lines, the $i$ -th line of them contains two integers $l_i,r_i(1\leq l_i\leq r_i\leq N)$.

outputFormat: An integer indicates the answer.


title: [ICPC2024 Xi'an I] Triangle

description:
There are three points $A(a, 0)$, $B(0, b)$, $C(0, 0)$ in the plane rectangular coordinate system. Define the size of triangle $ABC$ as the number of squares that belong to it.

For integers $x,y$, one square is defined by four points $(x, y)$, $(x + 1, y)$, $(x, y + 1)$, $(x + 1, y + 1)$. We consider a square to belong to a triangle if half or more of it is inside the triangle.

For example, when $a = 8, b = 6$, the size of triangle $ABC$ will be $24$. The image below shows which squares are counted in the triangle.

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

inputFormat: The first and only line contains two integers $a\ (1\le a\le 10^6)$ and $b\ (1\le b\le 10^6)$.

outputFormat: Print an integer: the size of triangle $ABC$.


title: [ICPC2024 Xi'an I] Yet Another Maximum Matching Counting Problem

description:
There is a two-dimensional plane.

You have a set of points $\{(x_i,y_i)\}$ that satisfies $1\le x_i\le n, 1\le y_i\le m$ (Both $x_i$ and $y_i$ are integers), and there are no two points with the same coordinates.

If two points have the same horizontal or vertical coordinates, we will connect an edge between these two points. This forms a graph.

You need to find the sum of the maximum number of matches in the graphs formed by all possible $2^{nm}-1$ non empty sets, and output the result modulo $998244353$.

Here, the maximum number of matches in a graph is defined as: selecting the most edges so that there are no common vertices between any two edges.

inputFormat:
There are multiple testcases in this problem.

The first line contains an integer $T(1\le T\le 100)$, which represents the number of testcases.

Each of the testcases contains two integers $n,m(1\leq n,m\leq 500)$.

outputFormat: For each of the testcases, print an integer representing the result modulo $998244353$.


title: [ICPC2024 Xi'an I] Rubbish Sorting

description:
Bob has many pieces of rubbish. One day, he wants to sort them.

For every piece of rubbish, its type is expressed as a positive integer.

He has $q$ operations. For each operation, it is one of the following two operations.

- `1 s x` He tells you that the piece of rubbish named $s$ has a type of $x$.
- `2 s` He wants to ask you the type of rubbish $s$.

But his memories are not always accurate.

For each operation $2$, $s$ may not have appeared in the previous operation $1$s.

We define the similarity of two strings $s_1$ and $s_2$ as $\sum_{i=1}^{\min\{|s_1|,|s_2|\}} [s_{1,i}=s_{2,i}]$.

Here all the strings' indexes start at $1$.

For a string $s$, its type is the type of string which has the maximum similarity to $s$ among all the strings that have appeared in the previous operations $1$s. Note that if there are multiple strings that all have the maximum similarity to $s$, the type of $s$ is the minimum type of these strings' type.

Now, he wants you to solve this problem.

inputFormat:
The first line contains an integer $q(1\le q\le 3\times 10^5)$, which is the number of operations.

Next $q$ lines contain operations, one per line. They correspond to the description given in the statement.

It is guaranteed that for every operation $2$ there is at least one operation $1$ before it.

But some pieces of rubbish will have more than one type, you can consider it as the minimum type you have read.

The rubbish's names only consist of lowercase Latin letters.

$1 \le |s| \le 5, 1 \le x \le 10^9$

outputFormat: For every operation $2$, you should print an integer in a single line that is the rubbish $s$'s type.


title: [ICPC2024 Xi'an I] Chained Lights

description:
You have $n$ lights in a row. Initially, they are all off.

You are going to press these $n$ lights one by one. When you press light $i$, light $i$ will switch its state, which means it will turn on if it's off and turn off if it's on, and then for every $j$ satisfied $i|j,i< j\le n$, press light $j$ once.

For example, if $n=4$, when you press light $1$, light $1$ will turn on, and then you will press light $2,3,4$. Since you pressed light $2$, light $2$ will turn on and you will press light $4$, which will cause light 4 to turn on. After all the operations, lights $1,2,3$ will be turned on and light $4$ is still off.

You will press these $n$ lights and do the operations as mentioned above one by one. After all the operations, you want to know whether light $k$ is on or off.

You can also use the following code to understand the meaning of the problem:

```cpp
void press(int x)
{
    light[x]^=1;
    for (int y=x+x;y<=n;y+=x) press(y);
}
for (int i=1;i<=n;i++) press(i);
```

inputFormat:
There are multiple testcases.

The first line contains an integer $T(1\le T\le10^5)$, which represents the number of testcases.

Each of the testcases contains two integers $n,k(1\le k\le n\le10^6)$ in a single line.

outputFormat: For each testcase, if light $k$ is turned on in the end, output $\text{YES}$, otherwise output $\text{NO}$.


title: 「CMOI R1」We Want To Run / Nilpotent

background:
![](bilibili:BV1qW4y1Q7Ce)

$\small\color{white}54^{\text{th}}\text{Problem by ArCu}.$

description:
对于 $n\times n$ 矩阵 $A$，定义 $f(A)$ 为最小的满足 $A^b=O$ 的正整数 $b$，若不存在这样的数则 $f(A)=0$。其中 $O$ 是零矩阵，即所有元素都是 $0$ 的矩阵。

给定 $n,a$，每个元素都是 $[0,a)$ 中整数的 $n\times n$ 矩阵有 $a^{n^2}$ 种。对所有 $a^{n^2}$ 种可能的矩阵 $A$ 求 $f(A)$ 之和。

答案对 $202407031$ 取模。

outputFormat: 一行一个整数，表示你求得的答案。

hint:
$\text{Sample 1 Explanation}:$

注意到对于任意正整数 $b$，$\begin{bmatrix}1&0\\1&1\end{bmatrix}^b\neq O$，所以 $f\left(\begin{bmatrix}1&0\\1&1\end{bmatrix}\right)=0$。而 $\begin{bmatrix}0&0\\1&0\end{bmatrix}^2=O$，所以 $f\left(\begin{bmatrix}0&0\\1&0\end{bmatrix}\right)=2$。

一共有 $2^4=16$ 种可能的矩阵。其中 $f(A)$ 不为 $0$ 的只有

$$f\left(\begin{bmatrix}0&0\\0&0\end{bmatrix}\right)=1,f\left(\begin{bmatrix}0&0\\1&0\end{bmatrix}\right)=f\left(\begin{bmatrix}0&1\\0&0\end{bmatrix}\right)=2$$

答案即为 $1+2+2=5$。

$\text{Details of Subtasks}:$

所有数据满足 $1\leq n\leq 600,0<a<2^{64}$。

| $\text{Subtask}$ | $\text{Special Constraints}$ | $\text{Score}$ |
| :----------: | :----------: | :----------: |
| $1$ | $n\leq 5,a\leq 2$ | $3$ |
| $2$ | $n\leq 5$ | $7$ |
| $3$ | $n\leq 10$ | $10$ |
| $4$ | $n\leq 40$ | $20$ |
| $5$ | $n\leq 200$ | $30$ |
| $6$ |  | $30$ |

$\text{Hint}:202407031=13009\times 15559.$


title: 「FSLOI Round I」石子

background:
**[English statement.](https://www.luogu.com.cn/problem/T500971) You must submit your code at the Chinese version of the statement.**

小 F 和小 L 正在玩一种古老的博弈游戏的改版。

description:
给定 $n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子。设序列 $a_1,a_2,\cdots,a_n$ 的平均数为 $x$。此外，还会给定一个不大于 $x$ 的数字 $k$。小 F 和小 L 将轮流进行以下操作直至一方胜出，小 F 先手：

- 选定两堆石子 $i,j$，满足 $a_i < x < a_j$。若无法选出这样的两堆石子，则对方获胜。

- 从第 $j$ 堆石子中拿出 $k$ 个石子放到第 $i$ 堆中。

小 F 和小 L 都将用最优策略进行操作。

若游戏会无限进行下去，输出 `Draw`。若小 F 将获胜，输出 `F`。否则，输出 `L`。

小 F 一共会进行 $T$ 场游戏，你需要告诉他每场游戏的结果。

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

每组数据共两行。

第一行输入两个整数 $n,k$。

第二行输入 $n$ 个整数 $a_i$。

outputFormat:
共 $T$ 行。

每行应为 `Draw`，`F`，`L` 中的一种。


title: [信息与未来 2024] 幸运数字

type: B

description:
如果一个正整数的二进制表示中，每个比特（$0$ 或 $1$）的左边或右边都至少有一个相同的比特，Dr. X 就认为它是一个“幸运数字”。例如:

- $(1)_2=(1)_{10}$ 有落单的 $1$，它不是幸运数字。

- $(110111)_2=(55)_{10}$ 有落单的 $0$，它不是幸运数字。

- $(111110011)_2=(499)_{10}$ 是幸运数字。

- $(110011001100)_2=(3276)_{10}$ 是幸运数字。

对于给定的 $a$ 和 $b$，Dr. X 希望你求出 $a, a + 1, a + 2, \dots, b$ 中幸运数字的数量。

inputFormat: 输入空格分隔的整数 $a$ 和 $b$。

outputFormat: 输出一行一个整数，代表 $a$ 和 $b$ 之间幸运数字的数量。

hint:
对于 $100\%$ 的数据,满足 $1 \leq a \leq b \leq 10^6$。

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2024] 红绿灯

description:
七段数码管是一种用来显示数字的电子元件，由七个可以发光的小段组成，这些小段排列成一个数字 $8$ 的形状。通过点亮不同的段,数码管可以显示出从 $0$ 到 $9$ 的数字。每个小段都有一个名字，从 $\tt A$ 到 $\tt G$，按下图方式排列和命名：

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

数码管通过点亮不同的段显示不同的数字。例如：

- 数字 $0$ 需要点亮 $\tt{A,B,C,D,E,F}$ 段。

- 数字 $1$ 需要点亮 $\tt{B,C}$ 段。

- 数字 $2$ 需要点亮 $\tt{A,B,D,E,G}$ 段。

Dr. X 发现，红绿灯上的数码管经常发生故障，故障分为两类：**常亮**和**不亮**：

- 如果数码管的某段发生了**常亮**故障，这一段都会始终保持点亮的状态。

- 如果数码管的某段发生了**不亮**故障，这一段都会始终保持不亮的状态。

今天，Dr. X 感觉红绿灯的一个数字显示异常,因此记录了数码管显示数字的日志。Dr. X 希望
你根据日志推测数码管的每一段分别可能发生了怎样的故障?

inputFormat:
输入数据第一行一个整数 $n$，代表 Dr. X 日志的数量。接下来 $n$ 行，每行一条日志 (一个字符
串)：

- 日志从一个数字 $k(0 \leq k \leq 9)$ 开始,代表本次观察的数字。

- 紧跟着数字的是若干的字母（$\tt{A\sim G}$，且每个字母至多出现一次），代表观察到数字 $k$ 显示时，处于“亮”状态的数码管段。日志准确、没有遗漏地记录了数码管亮着的段，且记录日志的过程中，红绿灯的状态保持不变：常亮的段一直常亮、不亮的段一直不亮、正常的段一直正常。日志中可能有同一个数字的多次记录，但不会自相矛盾。

outputFormat: 输出一行 $7$ 个字符，分别代表数码管 $\tt{A\sim G}$ 段的状态。对于每一段，如果有证据表明它常亮，输出大写字母 `X`。如果有证据表明它不亮，输出小写字母 `x`，否则输出半角减号 `-`。

hint:
对于 $100\%$ 的数据，满足 $0 \leq n \leq 100$。

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2024] 间谍卫星

description:
Dr. X 研制的间谍卫星拍摄到了许多 U 国建筑的照片。为了找出其中的军事设施，Dr. X 需要估算建筑的大小。Dr. X 发现，所有间谍卫星拍摄的照片都恰好包含一个完整的正方形，其中建筑边界上的像素被标记为了白色（用 $1$ 表示），其余像素被标记为了黑色（用 $0$ 表示）。一些照片的案例如下：

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

你的任务是根据拍摄的照片估算被摄正方形的**边长** (米)。照片中的每个像素都代表一个一米乘一米的正方形。

inputFormat: 输入数据第一行包含一个整数 $n$，代表间谍卫星拍摄照片的数量，随后是 $n$ 张照片，其中每张照片 $128$ 行，每行 $128$ 个字符，$1$ 表示白色，$0$ 表示黑色。两张照片之间有一个空行。

outputFormat: 为每张照片输出一个整数或小数，代表估计的正方形边长。输入数据保证每张照片中都恰好只包含一个正方形，且正方形的边界完全在照片内。

hint:
本题仅有一个 $n\leq 100$ 的测试数据，且测试数据和样例数据的生成方式相同。

当你对一幅照片估计的边长和实际建筑边长差距不超过 $2$ 时，则认为估计正确。若估计正确的照片比例 $A > 0.5$，本题得分为 $(A − 0.5) \times 30$ 向下取整，否则得零分。

我们在生成每张照片时，都先在平面上生成一个随机的、边长为整数、边界宽度为 $1$ 像素的正方形，然后“拍摄”得到它的照片。

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2024] 图灵完备

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

（你不需要看懂这张图片；但如果你看懂了，会觉得它很有趣。）

JavaScript 是一种功能强大且灵活的编程语言，也是现代 Web 开发的三大支柱之一 (另外两个是 HTML 和 CSS)。灵活的 JavaScript 包含“自动类型转换”的语言特性。例如，JavaScript 认为`[]`（空数组）和 `0` 是可以比较且相等的。自动类型转换带来的一个后果是我们可以只用 `()+[]!` 这 $6$ 个字符编写任意功能的 JavaScript 程序，包括游戏和交互网页。

Dr. X 请你帮他为整数 $n$ 生成一段仅包含 `()+[]!` 字符的 JavaScript 代码,且代码的运行结果恰好为整数 $n$。解决这个题目不需要任何 JavaScript 语言知识。~~压缩包中提供了人工智能实现的 jsexplorer.html 小工具，双击打开可以运行 JavaScript 代码并检查运行结果。~~

~~搬题者注：我没有收到下发的压缩包。~~

搬题者注：感谢 @[Jorisy](/user/400269) 在机房电脑中找到了遗留的 jsexplorer.html。

inputFormat: 输入一个非负整数 $n$，为你需要构造的目标数字。

outputFormat: 输出一行一个 JavaScript 程序，且仅由 `()+[]!` 六个字符构成。在 jsexplorer.html 中执行它可以得到整数 $n$。本题答案不唯一，输出任意不超过 $5000$ 个字符的解即可。

hint:
对于 $60\%$ 的数据，有 $n \leq 1000$。

对于 $100\%$ 的数据，有 $0 \leq n \leq 10^9$。

输出超过 $5000$ 个字符将被判定为错误。~~注意源代码有  $100\text{KB}$ 的大小限制。~~

搬题者注：这里是洛谷。源代码有 $50\text{KB}$ 的限制。

>本题原始满分为 $15\text{pts}$。


title: [信息与未来 2024] 数据排序

description:
在计算机世界中，“表格”是一种简单、基础而且十分通用的数据结构，在数据库、人工智能等领域中都有广泛的应用。表格由若干行、若干列的单元格组成：

| Name     | p1   | p2   | p3   | Score |
| :------- | :--- | ---- | ---- | ----- |
| ZhangSan | 40   | 30   | 28   | 98    |
| LiSi     | 40   | 28   | 30   | 98    |
| WangWu   | 40   | 25   | 20   | 85    |

CSV (Comma-Separated Values) 是一种常用的表格格式。Dr. X 需要你编程处理简化的 CSV 文
件，格式规定如下：

- CSV 文件包含 $n$ 行数据，其中第一行是标题行。
- CSV 文件每行一个字符串，对应了表格的一行。行中的单元格由**半角逗号**分隔。
- 每个单元格至少包含一个字符。单元格有两种类型：
  - **数值单元格**：由至少一个数字字符 $(0\sim 9)$ 组成。
  - **字符串单元格**：由数字字符 $(0\sim 9)$ 和大小写字母 $(\tt{a\sim z},\tt{A\sim Z})$ 组成,且至少包含一个字母。

- 标题行的所有单元格都是字符串单元格，且互不相同。标题行中包含了列的名称。

以下是一个 CSV 文件的示例：

```
Name,p1,p2,p3,Score
ZhangSan,40,30,28,98
LiSi,40,28,30,98
WangWu,40,25,20,85
```

你的任务是**根据指定的列为表格中的行排序**。例如根据 `Score- , Name+ , p3-` 排序意味着：

- 优先按 Score 列从大到小排序。Score 列都是数值单元格，因此按数值排序。

- 如果 Score 列相同，按 Name 列从小到大排序。Name 列都是字符串单元格，因此按照字典排序。

- 如果 Score 和 Name 列都相同，按 p3 列从大到小排序。p3 列都是数值单元格，因此按数
  值排序。

我们保证 CSV 文件每一行的单元格数量相同，且除标题行外，**每一列要么全是数值单元格，要么全是字符串单元格**。

inputFormat:
输入数据分为两部分。第一部分描述了 CSV 表格：
- 第一行一个整数 $n$，表示 CSV 文件的行数（**包含标题行**）。
- 接下来 $n$ 行,每行一个字符串，描述 CSV 表格中的行。

第二部分描述了排序要求:

- 第一行一个整数 $m$，表示排序依据列的数量。

- 接下来 $m$ 行，每行一个字符串，按顺序给出了排序依据的列名及排序方式（加号或减号）。加号代表升序排列、减号代表降序排列。

outputFormat: 输出 $n$ 行，为排序后的 CSV 表格（**包含标题行**）。对于所有排序依据列的值都相同的行，保持它们在输入文件中的相对顺序。

hint:
对于 $100\%$ 的数据，满足 $1 \leq n \leq 100$，表格不超过 $10$ 列，字符串单元格不超过 $16$ 个字符，且数值单元格中的数值是 $0$ 到 $10^4$ 之间的整数。

>本题原始满分为 $20\text{pts}$。


title: [信息与未来 2024] AI 机器人

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

在 $n$ 行 $m$ 列的矩形空间中有一个机器人。矩形空间的每一个格子要么是平地（用半角点号 `.` 表示），要么是障碍物 （用井号表示 `#`）。以下是一个 $n = 3, m = 7$ 的例子：

```
...#...
...#...
.......
```

初始时,机器人位于矩形的左上角 （第一行、第一列）。每一时刻，机器人可以遵照程序执行 `U`（Up，向上）、`L` （Left，向左）、 `D` （Down，向下）、`R` （Right，向右） 四种指令中的一个，尝试向某个方向移动一格；如果移动的目标格子超出了边界或是障碍物，则保持原地不动，例如执行程序：

`LLLRRRRRRRRRDDDDRRRRRRRRR`

后，机器人会从空间的左上角移动到右下角。Dr. X 扩展了机器人程序的表达能力,引入了循环。给定程序 `P`，`(P)n` 相当于把程序 `P`“复制粘贴”$n$ 次。循环可以嵌套。例如，在足够大且无阻挡的空间中执行程序：

`(R(DRUL)7)5`

会重复 $5$ 次执行“向右移动一格、转圈 $7$ 次”，而如果机器人在 $n = 1, m = 2$ 的空间中执行上述程序，就会表现为“左右横跳”。

Dr. X 还给机器人装备了人工智能，对于某些指定的循环，机器人可以由深度神经网络自主决定循环的次数（$0$ 次或任意多次），用星号 `*` 表示，例如

`(DR(R)*)3`

外层循环会执行 $3$ 次，由于循环“复制粘贴”的特性，每次向下向右移动一格后，机器人可以根据自己的想法向右移动 $0$ 格或任意多格。人工智能循环也可以嵌套，根据循环“先外层后里层”的执行顺序，总是先确定外层人工智能循环的执行次数，再按照“复制粘贴”的规则执行内层循环代码。

人工智能模块使机器人的行为变得难以预测。给定一个机器人程序，Dr. X 想知道，哪些格子是机器人在执行程序过程中绝无可能经过的（即无论机器人如何选择循环执行的次数，都不会经过）？这样他可以在这些格子上安装监控，并在观察到机器人行为失控的时候及时制止。

inputFormat:
输入第一行两个空格分隔的整数 $n$ 和 $m$，代表矩形空间的大小为 $n$ 行、$m$ 列。

接下来 $n$ 行，每行 $m$ 个字符，描述了矩形空间。其中半角点号为平地、井号为障碍物。

输入最后一行是一个字符串，为机器人执行的程序。程序由 $\tt{U/L/D/R}$、圆括号、正整数、星号组成。输入程序保证合法：圆括号总是正确配对，且之后紧跟一个正整数或一个星号。除此之外，程序中所有的字符都是 $\tt{U,L,D}$ 或 $\tt{R}$。机器人初始时位于左上角，输入保证左上角不是障碍物。**固定次数循环的次数总是在 $1$ 到 $9$ 之间。**

outputFormat: 输出 $n$ 行，每行 $m$ 个字符，按顺序输出矩形空间中每个格子的计算结果。如果是障碍物格子，输出井号 `#`。如果是机器人选择适当的循环次数可以到达的平地格子，输出加号 `+`。否则输出半角点号 `.`。

samples:
3 7
...#...
...#...
.......
LLLRRRRRRRRRDDDDRRRRRRRRR

hint:
对于 $30\%$ 的数据，输入程序不含星号 `*` 且在 $10^5$ 步内终止。

对于另外 $30\%$ 的数据，输入程序中不含星号 `*`。

对于 $100\%$ 的数据，$1 \leq n, m \leq 10$，且输入程序的长度不超过 $1000$。

>本题原始满分为 $20\text{pts}$。


title: 「CZOI-R1」卡牌

background: Alice 和 Bob 正在玩卡牌游戏。

description:
每张卡牌有四个属性：攻击、防御、速度、血量。

我们称一张卡牌能胜过另一张卡牌，当且仅当其至少有三个属性都大于另一张卡牌。

Bob 拥有 $m$ 张卡牌，而 Alice 拥有每个属性值在 $[1, n]$ 的所有 $n^4$ 张卡牌。

现在 Alice 想知道：她有多少张卡牌可以胜过所有 Bob 的卡牌？

inputFormat:
第一行包含两个整数 $n, m$，分别表示属性值上限和 Bob 的卡牌数量。

接下来 $m$ 行，每行四个整数 $a_i, b_i, c_i, d_i$，表示 Bob 一张卡牌的属性。

outputFormat: 输出一行一个整数，表示答案对 $2^{32}$ 取模后的结果。

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

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

- Subtask #1（$10\text{ pts}$）：$n, m \le 50$。
- Subtask #2（$10\text{ pts}$）：$n, m \le 5 \times 10^3$。
- Subtask #3（$20\text{ pts}$）：$d_i = 1$。
- Subtask #4（$20\text{ pts}$）：$n, m \le 10^5$。
- Subtask #5（$40\text{ pts}$）：无特殊限制。

对于所有测试数据，$1 \le n, m \le 5 \times 10^5$，$1 \le a_i, b_i, c_i, d_i \le n$。


title: Happybob's Numbers (UBC001B)

description:
happybob 在地上有 $n$ 个数，第 $i$ 个记为 $a_i$。happybob 正在研究如何将这些数全部删除。在他开始进行所有操作以前，他有一次按任意顺序摆放这些数的机会。他接下来要按照如下方式进行删数：

- happybob 有一个删数下标 $h$（初始时 $h=1$），他会设立一个新变量 $H$，其值为 $a_h$ ，然后对于每一个满足 $h\le i<k$ 的正整数 $i$ 都执行 $a_i\gets a_{i+1}$（这里 $k$ 是当前地上剩余的数的个数）并删除数 $a_k$，在这之后他会把 $h$ 赋值为 $H$。

- **如果在任何一次操作过后，$h$ 严格大于当前地上剩余的数的个数，那么他将不能再删除任何数。**

当然以他的这种删数方式不一定可以删完所有数，所以他现在想问你：他最多能删除多少个数？

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

对于每组数据：

第一行，一个正整数 $n$，表示 $a$ 的大小；

第二行，$n$ 个正整数表示 $a$ 中的元素。

outputFormat: $t$ 行，每行一个正整数，表示该组测试数据对应的答案。

hint:
#### 样例解释

对于第一个数据点，happybob 可以把 $a$ 数组排序为 $[2, 3, 1]$。以下是删数过程：

| 操作次数 | $h$（操作完成后） | 地上的数（操作完成后） |
| -- | -- | -- |
| 初始 | $1$ | $[2, 3, 1]$ |
| $1$ | $2$ | $[3, 1]$ |
| $2$ | $1$ | $[3]$ |
| $3$ | $3$ | $[]$ |

地上没有数了，也就是一共删除了 $3$ 个数。

对于第二个数据点，可以证明，无论怎么排序 $a$，都只能删除一个数。

#### 数据范围

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

对于 $100\%$ 的数据，保证 $1 \le t,n,\sum n\le 5 \times 10^5$，$1\le a_i\le 10^9$。其中 $\sum n$ 表示所有测试数据中 $n$ 的和。


title: Happybob's Puzzle (UBC001A)

description:
给定一棵有 $n$ 个点的树，每条边的长度都是 $1$，你需要构造一个 $1\sim n$ 的排列 $p$，满足以下条件：

- 对于每个满足 $1\le i<n$ 的整数 $i$，点 $p_i$ 到点 $p_{i+1}$ 的简单路径长度为奇数。

如果有解，请输出字典序最小的排列 $p$；否则，输出 $-1$。

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

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

对于每组测试数据：

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

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

outputFormat: $t$ 行，每行 $n$ 个正整数或一个整数 $-1$，表示该组测试数据的答案。

hint:
**数据范围**

对于所有数据，都有 $1\le t,n,\sum n\le 10^5$，保证有 $1 \leq u, v \leq n$ 且 $u \neq v$。保证输入构成一棵树。其中 $\sum n$ 表示所有测试数据的 $n$ 的总和。


title: [语言月赛 202407] true

background: 从前有个荣光的王国，小 A 是里面的国王，他认为他的王国现在还是不真实的，所以他打算现在赐以其真实。

description:
小 A 知道他的王国有三个属性，它们的和理应正好为  $10000$。但现在他所能看到的属性却不是这样：小 A 看到的依次是被放大了 $10$ 倍的第一个属性和被缩小了 $10$ 倍的第二个属性，无法看到第三个属性。

现在小 A 想知道这三个属性的真实值是多少，以方便小 A 将他的王国变为真实的。

inputFormat: 一行两个整数 $a,b$，表示小 A 看到的第一个属性和第二个属性的值。

outputFormat: 输出一行，三个整数，表示小 A 的王国的真实的三个属性分别是多少。

hint:
### 样例 1 解释

第一个属性被放大了 $10$ 倍，其真实值应该除以 $10$，为 $4000$，第二个属性被缩小了 $10$ 倍，其真实值为 $3000$，最后一个值应该为 $10000$ 减去 $4000$ 和 $3000$，为 $3000$。

### 样例 2 解释

第一个属性被放大了 $10$ 倍，其真实值应该除以 $10$，为 $5000$，第二个属性被缩小了 $10$ 倍，其真实值为 $1000$，最后一个值应该为 $10000$ 减去 $5000$ 和 $1000$，为 $4000$。

### 样例 3 解释

第一个属性被放大了 $10$ 倍，其真实值应该除以 $10$，为 $451$，第二个属性被缩小了 $10$ 倍，其真实值为 $2320$，最后一个值应该为 $10000$ 减去 $451$ 和 $2320$，为 $7229$。

### 数据范围

对于 $100\%$ 的数据，$1 \le a \le 100000$，$1 \le b \le 1000$，且 $a$ 为 $10$ 的倍数。保证结果没有负数。


title: [语言月赛 202407] rules

background: 从前有个荣光的王国，小 A 是其中的国王，他认为一个国家除了法律外还要有一些约定俗成的规则，所以今天他要赐以其规则。

description:
小 A 制定了一些规则，每条规则有一个代号，代号为不超过 $10^9$ 的非负整数。

小 A 的国家有 $n$ 位居民，每位居民每天会且仅会遵守 $1$ 条规则。小 A 记录了 $m$ 天里每天每位居民遵守的规则代号。

现在小 A 想要考察代号为 $k$ 的规则是否符合民意，具体考察方法如下：
- 如果在某一天里，有大于等于一半的人遵守了规则 $k$，那么小 A 认为在这一天规则 $k$ 是符合民意的。
- 如果在大于等于一半的天数里，规则 $k$ 符合民意，那么他会认为规则 $k$ 是正确的。否则，他会认为规则 $k$ 是错误的。

如果小 A 的规则 $k$ 是正确的，请你输出 `YES`，否则请你输出 `NO`。

inputFormat:
第一行三个整数 $n,m,k$，分别表示居民总数、记录的天数和小 A 想要考察的规则的代号。

接下来 $m$ 行，每行 $n$ 个整数分别表示每个人分别遵守的规则代号。

outputFormat: 一行一个字符串 `YES` 或 `NO` 表示小 A 的规则 $k$ 是否是被视作正确的。

hint:
### 样例 1 解释

- 第一天有 $2$ 人遵守 $1$ 号规则，大于总人数的一半，所以第一天小 A 的规则是符合民意的。
- 第二天只有 $1$ 人遵守，小于总人数的一半，不符合民意。

总共有 $1$ 天符合民意，等于天数的一半，所以小 A 认为他的规则是正确的。

### 样例 2 解释

第一天、第二天分别有 $1$ 个人遵守规则 $1$，都等于人数的一半，因此这两天小 A 的规则都符合民意，所以小 A 认为他的规则是正确的。

### 样例 3 解释

- 第一天没有人遵守 $1$ 号规则，所以第一天小 A 的规则是不符合民意的。
- 第二天只有 $1$ 个人遵守 $1$ 号规则，小于总人数的一半，不符合需求。

可见，没有一天 $1$ 号规则是符合需求的，所以小 A 认为他的规则是错误的。

### 数据范围

- 对于 $20\%$ 的数据，$m = 1$。
- 对于另外 $20\%$ 的数据，$n = 1$。
- 对于 $100\%$ 的数据，$1 \le n,m \le 1000$，$0 \leq k \leq 10^9$，输入的所有数据 $x$ 满足 $0 \leq x \leq 10^9$。


title: 「CZOI-R1」三角形与树

background:
CaiZi 讨厌三角形，但是他喜欢树。

2024.8.15 Update：增加了一组 hack 数据。

description:
给定一颗有 $n$ 个点的树，节点编号为 $1\sim n$，每个点有点权，开始时点 $i$ 的点权为 $a_i$。共有 $q$ 次操作。
1. 将点 $x$ 到点 $y$ 的简单路径上的点的点权**异或** $k$。
1. 判断能否在点 $x$ 到点 $y$ 的简单路径上选 $3$ 个**不同点**，并以这 $3$ 个点的点权为边长构成**三角形**。特别的，如果无法选出 $3$ 个点，也视为不能构成**三角形**。

点 $x$ 到点 $y$ 的简单路径：点 $x$ 到点 $y$ 不重复走过任何一条边的路径。其上的所有点为这条路径上所有的点，**包括**点 $x$ 和点 $y$。

**保证任何时刻不会有任何一个点的点权为 $0$。**

inputFormat:
第一行输入 $2$ 个整数 $n,q$，分别表示这棵树点的个数、操作的个数。

第二行输入 $n$ 个整数 $a_i$，表示开始时点 $i$ 的点权。

接下来 $n-1$ 行，每行输入 $2$ 个整数 $u,v$，表示这棵树的一条边。

接下来 $q$ 行，每行先输入 $1$ 个整数 $s$，表示操作类型。
- 若 $s=1$，则再输入 $3$ 个整数 $u,v,w$，表示一次修改操作。
- 若 $s=2$，则再输入 $2$ 个整数 $u,v$，表示一次询问操作。

outputFormat: 对于每次询问操作，若能满足条件输出 $1$，否则输出 $0$，无需空格或换行。

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

第 $1$ 次操作时简单路径上的点权少于 $3$ 个。
第 $2$ 次操作时简单路径上的点权分别为 $1,2,3,4$。
第 $3$ 次操作后点 $1\sim n$ 的点权分别为 $5,6,7,4,1$。
第 $4$ 次操作时简单路径上的点权分别为 $5,6,7$。
第 $5$ 次操作时简单路径上的点权分别为 $1,5,6$。

**【数据范围】**

**本题采用捆绑测试**。
- Subtask #1（$8\text{ pts}$）：$n,q\le3\times10^3$。
- Subtask #2（$8\text{ pts}$）：保证这棵树是一朵菊花。
- Subtask #3（$20\text{ pts}$）：每次修改操作时 $x=y$。
- Subtask #4（$24\text{ pts}$）：保证这棵树是一条链。
- Subtask #5（$40\text{ pts}$）：无特殊性质。**依赖 Subtask #1 到 Subtask #4。**

对于 $100\%$ 的数据，$1\le u,v\le n\le10^5$，$1\le q\le10^5$，$s\in\{1,2\}$，$1\le a_i,w\le 2^{31}-1$。


title: [洛谷 202406GESP 模拟 二级] 周长与面积计算

description:
小洛有 $n$ 个正方形，第 $1$ 个正方形的边长为 $1$，第 $2$ 个正方形的边长为 $2$，以此类推，第 $n$ 个正方形的边长为 $n$。它们被紧密地排列成一行。小洛想要知道这个图案的周长和面积分别是多少。

例如当 $n=5$ 时的图案如下图所示。红色的边框代表整个图案的周长，绿色区域代表整个图案的面积：

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

inputFormat: 输入一个正整数 $n$。

outputFormat:
输出两行。

第一行一个正整数代表图案的周长；

第二行一个正整数代表图案的面积；

hint:
对于 $70\%$ 的数据，$1 \leq n \leq 100$；

对于所有数据，$1 \leq n \leq 100000$。


title: 宇宙射线

background:
感谢 @[jason_sun](https://www.luogu.com.cn/user/399762) 加强数据。

宇宙射线天天乱改东西/fn。

description:
有一个长度为 $n$ 的二进制串 $s$，你需要找到一个最长的长度为偶数的子串，使得它的前半部分和后半部分完全相同。

但是因为宇宙射线攻击了这个串，有一些位置的值变得未知了。

你可以把未知的值视为 $0$ 和 $1$ 的任意一个数，求出在这种情况下这个最长子串的长度。

本题有多组测试。

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

接下来 $2t$ 行，每两行表示一组测试数据，每组测试数据第一行一个正整数 $n$，表示字符串的长度，接下来一行一个长度为 $n$ 的字符串 $s$。

outputFormat: $t$ 行，每行一个非负整数，表示第 $i$ 组测试的答案，由于这个串长一定是偶数，所以你只用输出它的长度除以 $2$ 的结果。


title: 椰子

background: 众所周知，椰子是一种椰子，但这和题目好像没什么关系。

description:
给出一个长度为 $n$ 的序列 $a$，我们保证 $1\sim n$ 中的每一个数都恰好在 $a$ 中出现了一次，对于每一个 $1\le i\le n$，求出在序列中将值为 $i$ 的数的值修改成 $1$ 后，序列有多少种不同的区间 $\gcd$ 的值。

严格来说，记将值为 $x$ 的数修改为 $1$ 后的序列为 $A^x$。集合 $S_x=\{\gcd\limits_{i=l}^r(A^x_i)|1\le l\le r\le n\}$，求出所有 $|S_i|$ 的值。

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

接下来一行 $n$ 个正整数，表示序列 $a$。

outputFormat: 一行一共 $n$ 个整数，第 $i$ 个数表示在把值为 $i$ 的数改成 $1$ 后，序列有多少种不同的区间 $\gcd$ 的值。


title: 【MX-J1-T2】『FLA - III』Ilumina

description:
定义 $\lfloor X \rfloor$ 为最大的小于等于 $X$ 的整数，例如 $\lfloor 1.99 \rfloor = 1,\lfloor 7 \rfloor = 7$。

有五个正整数 $n,m,a,b,c$，已知 $b=\left\lfloor \frac{a}{n} \right\rfloor , c=\left\lfloor \frac{b}{m} \right\rfloor$。

给定 $a$ 和 $c$ 的值，求出一个合法的 $b$ 的值，或者报告不存在合法的 $b$ 的值。

**本题使用自定义校验器，如果存在多个合法的 $b$ 的值，输出其中一个即可。**

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

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

对于每组测试数据，输入一行两个正整数 $a,c$。

outputFormat:
对于每组数据，输出一行一个整数。如果不存在合法的 $b$ 的值，输出 `-1`；否则输出一个合法的 $b$ 的值。

**本题使用自定义校验器，如果存在多个合法的 $b$ 的值，输出其中一个即可。**

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

对于第一组测试数据，取 $n=1,m=1$ 时可以得到 $b=1$。

对于第二组测试数据，取 $n=2,m=1$ 时可以得到 $b=3$。

对于第三、第四组测试数据，可以证明不存在合法的 $b$ 的值。

**「数据范围」**

|测试点编号|$a,c \leq$|特殊性质|
|:-:|:-:|:-:|
|$1 \sim 3$|$10$|无|
|$4 \sim 6$|$10^3$|无|
|$7 \sim 8$|$10^{18}$|有|
|$9 \sim 10$|$10^{18}$|无|

特殊性质：保证对于每组给定的 $a,c$ 一定存在合法的 $b$ 的值。

对于 $100\%$ 的数据，$1 \leq T \leq 10^5$，$1 \leq a,c \leq 10^{18}$。

2024 年 7 月 15 日：添加了 7 组 hack 数据置于 Subtask #1。


title: 【MX-J1-T1】『FLA - III』Spectral

background: > 没有看到昂星团。

description:
有一团火，最开始它的温度是 $0$，火焰旁边有 $n$ 个炭块，每块炭都有 $k$ 点能量。

使用 $T_i$ 表示烧掉 $i$ 块炭后火焰的温度，有：

$$T_i = \begin{cases} 0 & i = 0 \\ k+ \dfrac{T_{i-1}}{i} & i \neq 0 \end{cases}$$

火焰能够达到的最高温度是多少？

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

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

对于每组测试数据，输入一行两个正整数 $n,k$。

outputFormat: 对于每组测试数据，输出一行一个实数表示火焰能达到的最高温度，四舍五入到小数点后 $1$ 位。


title: 「ALFR Round 2」C 小 Y 的数

description:
小 Y 非常喜欢 $42$ 这个数，于是他也喜欢以 $42$ 为初始数，然后往后面依次拼接 $4,2$ 的数，如 $42,424,4242,\cdots$。小 Y 给了你一个大小为 $n$ 的整数序列 $a$，小 Y 有 $m$ 次操作，操作有四种：

- `1 l r x` 将 $l\sim r$ 中的数加上 $x$。

- `2 l r x` 将 $l\sim r$ 中的数乘上 $x$。

- `3 l r x` 将 $l\sim r$ 中的数修改为 $x$。

- `4 l r` 询问 $l\sim r$ 中有多少个小 Y 喜欢的数。

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

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

接下来 $m$ 行，每行 $3$ 或 $4$ 个整数描述一次操作。

outputFormat: 每行一个操作 $4$ 的答案。


title: [语言月赛 202406] 气球

description:
小 Z 参加了一个比赛。这个比赛一共有 $3$ 个题，在比赛过程中，正确完成第 $1$ 题后，可以获得一个蓝色的气球（用 `B` 表示）；正确完成第 $2$ 题后，可以获得一个黄色的气球（用 `Y` 表示）；正确完成第 $3$ 题后，可以获得一个红色的气球（用 `R` 表示）。正确完成一道后，会马上拿到这个气球。

小 Z 三道题都会做，但并不一定按照第 $1,2,3$ 题的顺序完成。现在给出小 Z 正确完成题目的顺序，请输出小 Z 获得气球的顺序。

inputFormat:
共一行，包含 $3$ 个整数，整数之间用一个空格隔开，表示正确完成题目的顺序。

保证输入的数字只有 $1,2,3$ 且不会重复。

outputFormat: 共一行，包含三个字母，表示小 Z 获得气球的顺序。其中 `B` 表示蓝色气球，`Y` 表示黄色气球，`R` 表示红色气球。

samples:
1 2 3
BYR

samples:
3 1 2
RBY

hint:
### 样例 1 解释

小 Z 正确完成第 $1$ 题后，获得了蓝色气球（用 `B` 表示）。\
小 Z 正确完成第 $2$ 题后，获得了黄色气球（用 `Y` 表示）。\
小 Z 正确完成第 $3$ 题后，获得了红色气球（用 `R` 表示）。

### 数据范围

保证输入的数字只有 $1,2,3$ 且不会重复。


title: [语言月赛 202406] 天然气计价

description:
天然气计费采用**阶梯计费**。

第一档收费标准：**年用气量**在 $0\sim 310(含)$ 立方米，价格为 $3$ 元/立方米；\
第二档收费标准：**年用气量**在 $310\sim 520(含)$ 立方米，价格为 $3.3$ 元/立方米；\
第三档收费标准：**年用气量**在 $520$ 立方米以上，价格为 $4.2$ 元/立方米。

例如，小 Z 家今年用气量为 $600$ 立方米，费用为 $310\times 3 + (520-310)\times 3.3 + (600-520)\times 4.2=930+693+336=1959$ 元。

现在给出小 Z 家 $1$ 至 $12$ 月的用气量，请输出小 Z 家每个月的天然气费用。

inputFormat: 共 $12$ 行，其中第 $i$ 行包含一个整数，表示 $i$ 月的用气量，单位为立方米。

outputFormat: 共 $12$ 行，第 $i$ 行包含一个小数，表示这个月的天然气费用，结果保留至小数点后 $1$ 位。

hint:
### 样例 1解释

前 $3$ 个月天然气费用为 $3\times 100=300$ 元。\
在 $4$ 月，有 $10$ 立方米的天然气使用第一档收费标准， $90$ 立方米的天然气使用第二档收费标准。因此费用为 $10\times 3+ 90 \times 3.3=327$ 元。此时，一年的总用气量为 $400$ 立方米。\
在 $5$ 月，有 $100$ 立方米的天然气使用第二档收费标准。因此费用为 $100 \times 3.3=330$ 元。此时，一年的总用气量为 $500$ 立方米。\
在 $6$ 月，有 $20$ 立方米的天然气使用第二档收费标准，$80$ 立方米的天然气使用第三档收费标准。因此费用为 $20 \times 3.3 + 80 \times 4.2=402$ 元。此时，一年的总用气量为 $600$ 立方米。\
后面 $6$ 个月全部使用第三档收费标准，因此每个月天然气的费用为 $100\times 4.2=420$ 元。

### 数据范围

对于 $20\%$ 的数据，满足一年的总用气量不超过 $310$。
对于 $50\%$ 的数据，满足一年的总用气量不超过 $520$。
对于 $100\%$ 的数据，满足一年的总用气量不超过 $10^9$。


title: 【MX-J1-T4】『FLA - III』Wrestle

background:
在 2022 年末，疫情将西北某不知名知名学校的大多数学生关在家中上网课，安同学还不知道，他和语文老师的对决已然悄无声息地开始了——他每天早读和语文课都直接睡过去了。

安同学习惯起来穿好衣服、面对摄像头睡觉，摄像头只能拍到他的半个肩膀，就算被强制打开也不会暴露他在睡觉的事实，而且从来没有老师强制打开他的摄像头。而这个不凡的早晨，语文老师打开了他的摄像头，现在是早读时间，他在朦胧中被老师的关爱声叫醒，可惜为时已晚，老师已经愤怒。安同学决定假装网络卡顿，平复老师愤怒的心情。

老师，愤怒了！在安同学醒来后的某些时间段，她要呼叫他的真名，其余时间等他应答。与此同时安同学要打造网卡的假象，他可以在某些时间段内检查设备或者呼叫老师，其余时间静止或随机在画面中闪现，他在这些时间段内的行为称为表演。你的任务是帮助安同学在不激怒老师的情况下最大化表演时间。

因为安同学实在是太抽象了，原始题面受他影响变得也很抽象，这里只有形式化题面给你看。

description:
给定三个正整数 $n,m,k$ 和两组线段。第一组线段有权值，共 $n$ 条，是**红色**的；第二组线段没有权值，共 $m$ 条，是**蓝色**的。这些线段位于同一个数轴。

- 使用 $l,r,w$ 三个正整数表示一条从数轴上第 $l$ 个整点覆盖到第 $r$ 个整点，权值为 $w$ 的红色线段。**保证数轴上任意一个整点至多被红色线段覆盖一次。**

- 使用 $L,R$ 两个正整数表示一条从数轴上第 $L$ 个整点覆盖到第 $R$ 个整点，没有权值的蓝色线段。**保证数轴上任意一个整点至多被蓝色线段覆盖一次。**

如果一条红色线段从第 $l_0$ 个整点覆盖到第 $r_0$ 个整点，一条蓝色线段从第 $L_0$ 个整点覆盖到第 $R_0$ 个整点且 $\max(l_0,L_0) \leq \min(r_0,R_0)$，就认为这两条线段有交集，交集包含从第 $\max(l_0,L_0)$ 个整点到第 $\min(r_0,R_0)$ 个整点的全部 $\min(r_0,R_0)-\max(l_0,L_0)+1$ 个整点。你可以选择一些蓝色线段，一种合法的选择方案必须符合以下条件：

- 题目给定的每条红色线段至多与你选择的 $1$ 条蓝色线段有交集。

- 所有和**你选择的蓝色线段**有交集的红色线段权值之和不超过 $k$。

选择方案合法时，**你选择的蓝色线段**和**所有红色线段**的交集至多能包含多少个整点？

inputFormat:
第一行输入三个正整数 $n,m,k$。

接下来 $n$ 行，第 $i$ 行输入三个正整数 $l_i,r_i,w_i$ 表示一条红色线段。

接下来 $m$ 行，第 $i$ 行输入两个正整数 $L_i,R_i$ 表示一条蓝色线段。

**保证数轴上任意一个整点至多被红色线段覆盖一次。保证数轴上任意一个整点至多被蓝色线段覆盖一次。**

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

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

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

如图，选择输入的第 $2$ 条蓝色线段和第 $3$ 条蓝色线段。

第 $2$ 条蓝色线段与第 $1$ 条红色线段有交，交集包含从第 $13$ 个整点到第 $18$ 个整点的所有整点；第 $3$ 条蓝色线段与第 $2$ 条红色线段有交，交集包含从第 $63$ 个整点到第 $71$ 个整点的所有整点。

第 $1$ 条红色线段仅与第 $2$ 条蓝色线段有交，第 $2$ 条红色线段仅与第 $3$ 条蓝色线段有交；和被选择的蓝色线段有交的红色线段权值和为 $9$，方案合法。故答案为 $15$。

**「数据范围」**

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

|Subtask|$n \leq$|$m \leq$|$k \leq$|$l_i,r_i,L_i,R_i \leq$|分值|
|:-:|:-:|:-:|:-:|:-:|:-:|
|**#1**|$10$|$10$|$50$|$100$|$20$|
|**#2**|$200$|$200$|$200$|$10^5$|$30$|
|**#3**|$5000$|$5000$|$5000$|$10^9$|$30$|
|**#4**|$2 \times 10^5$|$5000$|$5000$|$10^9$|$20$|

对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10^5$，$1 \leq m,k \leq 5000$，$1 \leq l_i,r_i,L_i,R_i \leq 10^9$，$1 \leq w_i \leq k$，$l_i < r_i$，$L_i < R_i$。**保证数轴上任意一个整点至多被红色线段覆盖一次。保证数轴上任意一个整点至多被蓝色线段覆盖一次。**


title: [语言月赛 202406] 朋友数列

description:
小 K 喜欢数列。设数列 $a,b$ 的长度均为 $n$，$a_i$ 表示数列 $a$ 中第 $i(1 \le i \le n)$ 个数字，$b_i$ 表示数列 $b$ 中第 $i(1 \le i\le n)$ 个数字。

如果对于所有的 $1 \le i \le n$，$a_i+b_i$ 的值均相同，并且满足 $-10^9 \le a_i,b_i \le 10^9$，则小 K 称它们是一对朋友数列。

现在，小 K 随手写下了 $n$ 和数列 $a$，小 K 希望你能帮助小 K 找到数列 $a$ 的一个朋友数列。

inputFormat:
输入共两行。

输入的第一行为一个整数 $n$。
输入的第二行为 $n$ 个整数，第 $i$ 个数为 $a_i$。

outputFormat:
输出一行 $n$ 个整数，表示数列 $a$ 的一个朋友数列。

**可能有多种符合题意的答案，你只需要输出任意一种即可。**


title: [语言月赛 202406] 优惠券

description:
某奶茶店推出优惠活动：

- 如果按照原价购买了一杯奶茶，可获赠一张优惠券；
- 如果使用优惠券购买了一杯奶茶，这杯奶茶不会再获赠优惠券；
- 每张优惠券可折抵 $1$ 元；
- 购买一杯奶茶使用的优惠券数量不限，但不找零。

现在，小 F 计划购买 $n$ 杯奶茶，其价格为 $a_1,a_2,\cdots,a_n$。**他可以以任意顺序购买这 $n$ 杯奶茶。**

请问，小 F 最少花费多少钱，才能买下全部 $n$ 杯奶茶？

inputFormat:
输入共两行。

输入的第一行为一个整数 $n$。
输入的第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n$。
**保证 $a_1\le a_2 \le \cdots \le a_n$。**

outputFormat: 输出一行一个整数，表示最少花费的钱数。

hint:
### 样例解释

按照 $3,3,2,1,4$ 的顺序购买，前四杯获得四张优惠券，最后一杯全部使用优惠券。

### 数据规模与约定

- 对于 $30\%$ 的测试数据，$n=2$；
- 对于 $100\%$ 的测试数据，$1 \le n \le 1000$，$1 \le a_i \le 50$，$a_1 \le a_2 \le \cdots \le a_n$。


title: [语言月赛 202406] 小 Z 的 Z 矩阵

description:
小 Z 想要一个 $n\times n$  的 Z 矩阵。具体来说，这个矩阵共有 $n$ 行，每行 $n$ 个字符。第一行，最后一行，以及反对角线为字符 `Z`，其余部分均为字符 `-`。

例如，一个 $n = 6$ 的 Z 矩阵如下:

```plain
ZZZZZZ
----Z-
---Z--
--Z---
-Z----
ZZZZZZ
```

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

outputFormat: 共 $n$ 行，每行包含 $n$ 个字符。该图形为 Z 矩阵。

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

对于 $60\%$ 的数据，满足 $3\le n\le 10$。\
对于 $100\%$ 的数据，满足 $3 \le n\le 100$。


title: [语言月赛 202406] 通配符匹配

background:
我们称两个字符 $a,b$ 是**匹配**的，当且仅当 $a =b$ 或 $a,b$ 中至少一个是字符 $\texttt ?$（ASCII 值 $63$）。例如：
- $\texttt x$ 和 $\texttt x$ 是匹配的；
- $\texttt x$ 和 $\texttt ?$ 是匹配的；
- $\texttt ?$ 和 $\texttt x$ 是匹配的；
- $\texttt ?$ 和 $\texttt ?$ 是匹配的；
- 但 $\texttt x$ 和 $\texttt y$ **不是**匹配的。

我们称两个字符串 $s$ 和 $t$ 是匹配的，当且仅当 $s$ 和 $t$ 长度相同，且对应位置上的字符是匹配的。例如，$\texttt{abc??z}$ 和 $\texttt{a?cx??}$ 是匹配的。

description:
给定两个字符串 $s, t$，规定 $s(l, r)$ 表示 $s$ 的第 $l$ 个字符到第 $r$ 个字符组成的字符串（$1 \leq l \leq r \leq |s|$）。例如：若 $s = \texttt{luogu}$，则 $s(2,4) = \texttt{uog}$。

现在，请你求出所有的 $l, r$，使得 $t$ 和 $s(l, r)$ 匹配。

inputFormat:
第一行是一个字符串 $s$。
第二行是一个字符串 $t$。

outputFormat:
输出若干行，每行两个整数，表示一组 $l,r$。

按 $l$ 从小到大的顺序输出。可以证明，按这个顺序进行输出的方案是唯一的。


title: 「CROI · R2」夏风与树

background:
刺眼的阳光把大地烤得炽热，小 B 走在街上，迎面吹来一阵清风，路旁郁郁葱葱的树叶沙沙地摇晃着。

“夏风扫过树叶的声音就像下雨一样呢。”

description:
Alice 和 Bob 在种树，同时，他们决定玩一个游戏。

Alice 拥有 $1\sim n$ 号结点，Bob 拥有 $(n+1)\sim 2n$ 号结点，这 $2n$ 个结点的权值恰好构成一个**排列** $a$，其中 $a_i$ 为 $i$ 号点上的权值。

首先，他们约定 $1$ 号点为树根。

然后，由 Alice 为 $2\sim n$ 号点决定父亲，其中 $i$ 号点的父亲只能在 $1\sim(i-1)$ 中选择。

接下来，由 Bob 为 $(n+1)\sim 2n$ 号点决定父亲，其中 $i$ 号点的父亲只能在 $0\sim(i-1)$ 中选择。$0$ 号点不在他们的树上，也就是说，Bob 的结点不一定要与这颗树连通。

最后，Alice 会从 $1$ 号点开始，对这棵树进行深度优先搜索，同时她会维护一个序列，搜索过程中，每遇到一个没访问过的点就将它上面的**权值**加入序列末尾。

Alice 希望最终序列的字典序尽可能小，Bob 希望最终序列的字典序尽可能大，并且他们二人都会采取最优策略。现在 Bob 请求你告诉他，最终序列会是什么样。

以下是关于字典序的定义：

- 对于一个长度为 $n$ 的序列 $a$，若 $i>n$，约定 $a_i=-\infty$。
- 对于两个序列 $a, b$，我们定义 $a$ 的字典序小于 $b$ 当且仅当存在 $i\ge 1$，使得 $\forall 1 \leq j < i$，$a_j = b_j$，且 $a_i < b_i$。

inputFormat:
**在本题的部分测试点中，Bob 会把 Alice 在第一步中决定好的 $2\sim n$ 号结点的父亲告诉你。**

第一行一个整数 $t$，表示子任务编号。特别地，样例的子任务编号为 $0$。

第二行一个正整数 $n$。

第三行 $2n$ 个正整数，表示排列 $a$。

第四行 $(n-1)$ 个整数，若该子任务拥有特殊性质 A，则表示 $2\sim n$ 号结点的父亲，否则这 $(n-1)$ 个整数都为 $0$。

outputFormat: 一行，表示最终序列。


title: [语言月赛 202407] significance

background: 从前有个荣光的王国，小 A 是里面的国王，他认为人活着需要有意义，所以今天他要赐予他的子民以意义。

description:
细心的小 A 发现，每个人的存在对于其他人来说都有着不可取代的意义。一个人的意义值定义为他的**朋友**和**朋友的朋友**的个数。

小 A 的王国共有 $n$ 位居民，以 $1, 2, \cdots, n$ 编号。每位居民分别有 $x_i$ 个朋友，现在小 A 想知道每位居民的意义值。

注意，朋友关系可能是单向的。即：有可能 $a$ 把 $b$ 当朋友，但 $b$ 不一定把 $a$ 当作朋友。同时，如果一个人的朋友的朋友中有自己，则这一部分的个数不统计。

时光荏苒，朋友的联系也会散去。而我们和一个人保持连接的方式就是记住，仅此而已。

inputFormat:
第一行一个整数 $n$ 表示小 A 王国的居民数。

接下来 $n$ 行每行 $x_i + 1$ 个整数。第一个整数 $x_i$ 表示 $i$ 号居民有几个朋友，接下来 $x_i$ 个整数分别表示他的朋友的编号。

outputFormat: 一行 $n$ 个整数分别表示每位居民的意义值。

hint:
 ### 样例 1 解释

- $1$ 号居民认为他的朋友是 $2$ 和 $3$，$3$ 认为自己没有朋友，但 $2$ 认为自己有一个朋友 $4$, 所以 $1$ 号居民的意义值是 $3$。
- $2$ 号居民认为他的朋友是 $4$，$4$ 没有朋友，所以 $2$ 号居民的意义值是 $1$。
- $3$ 号和 $4$ 号居民都认为自己没有朋友，所以他们的意义值是 $0$。

### 样例 2 解释

- $1$ 号和 $3$ 号居民认为他们没有朋友，所以他们的意义值是 $0$。
- $2$ 号居民的朋友是 $1$ 和 $3$，$1,3$ 都认为自己没有朋友，所以 $2$ 号居民的意义值是 $2$。

### 样例 3 解释

- $1$ 号居民认为他的朋友是 $2$, $2$ 认为他的朋友是 $3$，所以 $1$ 号居民的意义值是 $2$。
- $2$ 号居民的朋友是 $3$，$3$ 认为自己的朋友是 $1$，所以 $2$ 号居民的意义值是 $2$。
- $3$ 号居民的朋友是 $1$，$1$ 认为自己的朋友是 $2$，所以 $3$ 号居民的意义值是 $2$。

### 数据范围

- 对于 $20\%$ 的数据，$x_i \le 1$ 。
- 对于另外 $20\%$ 的数据，除 $x_1 = n - 1$ 外， $x_i = 0$ 。
- 对于 $100\%$ 的数据，$1 \le n \le 100$，$0 \le x_i \le n$。保证每一行除第一个数外的其他整数 $c$ 均有 $1 \leq c \leq n$ 且两两不同。
- 数据保证不会出现「一个人是自己的朋友」，或者「一个人既是另一个人的朋友，又是他朋友的朋友」的情况。


title: 『SpOI - R1』笑起来最帅的小孩

description:
**本题包含多组数据。**

有一个数字序列 $a$，长度为 $n$。序列中每一项均为 $0$ 到 $9$ 的数字。

另有一个空数字序列 $b$，$b$ 中会出现一个**光标**（你可以理解为能够出现在数字之间，或整个数字序列之前，或整个数字序列之后的细线），此时**光标**前后均没有数字。

现在向 $b$ 中依次输入数字序列 $a$。每输入一个数字，数字立即出现在**光标**之后。

接下来**光标**立即随机地移动到任意一个数字之前或所有数字之后。随机是均匀的。换句话说，**光标**移动到所有可移动到的位置的概率是均等的。

现在告诉你数字序列 $a$。你需要输出的是，最终得到的 $b$ 直接转为十进制后的大小（无视前导零）的期望，对质数 $2007072007$ 取模。

由于 $a$ 可能很长，所以本题采用压缩输入。

具体来说，最开始 $a$ 是空的数字序列，输入会给你一个 $k$ 长的二元组数组，其中第 $i$ 项为 $(x_i,l_i)$，表示数字 $x_i$ 连续出现 $l_i$ 次接在之前的 $a$ 之后。你可以用此方法解压缩真正的 $a$，再解决问题。

----------

**在本题，你可以对期望的理解**：对于一个变量可能的结果 $X$，若其权值为 $v_X$，得到该结果的概率为 $p_X$，则对于结果集 $S$，变量的期望 $E=\sum\limits_{X\in S}p_Xv_X$。

**如果你不知道如何对有理数取模**：请查看[此题](https://www.luogu.com.cn/problem/P2613)。

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

对于每组数据：

一行一个整数 $k$，表示 $a$ 压缩后得到的二元组数组包含多少项。

接下来共 $k$ 行，每行两个整数 $x_i,l_i$，表示在上一项所得 $a$ 序列的基础上，在末尾增加 $l_i$ 个数字 $x_i$ 得到新的 $a$ 序列。你可以用这种方式解压缩真正的 $a$ 序列。

outputFormat: 对于每组数据，输出一行一个整数，表示在光标每次都随机移动的情况下，可能得到的 $b$ 转化为十进制后的大小（无视前导零）的期望，对质数 $2007072007$ 取模的值。


title: 「FSLOI Round I」单挑

background:
**[English statement](https://www.luogu.com.cn/problem/T491159). You must submit your code at the Chinese version of the statement.**

小 F 和小 S 经常进行篮球单挑，但小 S 总是被盖帽。

description:
每次单挑的结果一定是小 F 获胜或者小 S 获胜，不存在平局的情况。

由于小 F 和小 S 实力不均衡，于是他们制定规则如下：

给定两个整数 $x,y$，若小 F 先赢 $x$ 场，则小 F 获胜。若小 S 先赢 $y$ 场，则小 S 获胜。

现在已经进行了 $n$ 场单挑，这 $n$ 场单挑的结果由一个字符串 $s$ 给出。若 $s$ 的第 $i$ 位为 `F`，则小 F 赢了第 $i$ 场。若 $s$ 的第 $i$ 位为 `S`，则小 S 赢了第 $i$ 场。

小 F 想知道，为了取得胜利，后续的比赛中他**最多连续胜利的场数最少是多少**。

你总共需要回答 $T$ 组询问。

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

每组数据共两行。

第一行三个整数 $n,x,y$，含义与题目描述一致。

第二行一个长度为 $n$ 的字符串 $s$，含义与题目描述一致。

outputFormat:
共 $T$ 行。

每行一个整数，表示小 F 在后续的比赛中最多连续胜利的场数的最小值。

samples:
1
29 1000 20
FFFSFFFFSFFFFFSFFFSFFFFFFSFFF

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

为了让小 F 获胜，后续的比赛结果只能为 $ \texttt {FFFF}$，此时最多连续胜利场数为 $4$。

**【样例 2 解释】**

为了让小 F 获胜，一种可能的后续的比赛结果为 $ \texttt {FFSFSF}$，此时最多连续胜利场数为 $2$。

请注意，您只需考虑**后续**的比赛中的最多连续胜场数，而不需要考虑前 $n$ 场。

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

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

对于 $100 \%$ 的数据，保证：
- $1 \leq T \leq 20$
- $1 \leq n \leq 2\times10^5$
- $1 \leq x,y \leq 10^9$
- $\forall i \leq n$，保证第 $i$ 场比赛结束后小 S 没有获胜。
- $\forall i < n$，保证第 $i$ 场比赛结束后小 F 没有获胜。

|子任务|分值|特殊性质|
|:-----:|:-----:|:-----:|
|$1$|$10$|$n=1$|
|$2$|$15$|$x,y\leq n$|
|$3$|$15$|$A$|
|$4$|$30$|$T=1$|
|$5$|$30$|无|

- 特殊性质 $A$：第 $n$ 场比赛结束后，小 S 总共获胜 $y-1$ 场。


title: [蓝桥杯 2024 国 A] 下一次相遇

description:
2024 年 6 月 1 日，这一天显得格外特别，因为欢乐的儿童节与星期六巧合地相遇了，这无疑为孩子们增添了诸多喜悦，让孩子们可以尽情地沉浸在这愉快的周末与浓厚的节日氛围当中。

不过，这也不禁引人思索，下一次的 6 月 1 日儿童节再度与星期六相遇，将会是在哪一年呢？请你以四位整数的格式给出答案。

inputFormat: 这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。


title: [蓝桥杯 2024 国 A] 兔子集结

description:
在森林幽静的一隅，有一村落居住着 $n$ 只兔子。

某个月光皎洁的夜晚，这些兔子列成一队，准备开始一场集结跳跃活动。村落中的每只兔子都占据一个位置，对于第 $i$ 只兔子，其位置为 $p_i$。我们称位置较小的为左边，位置较大的为右边。

按照兔子村落的习俗，每只兔子都会选择距离自己最近的兔子作为同伴，并向同伴所在的方向进行跳跃。如果一只兔子左边和右边的兔子距离它一样近，那么它会选择左边的兔子作为同伴。

兔子的每次跳跃，只能向左或向右移动一个单位距离。也就是说，如果一只兔子当前位于 $x$ 的位置，那么它下一次跳跃后会到达 $x-1$ 或者 $x+1$ 的位置。

当两只相互靠近的兔子之间的距离为 $1$ 时，左边的兔子会停在原地，而右边的兔子会跳到左边兔子的位置上，完成集结。

兔子们会一直跳跃，直到与自己最初选择的同伴完成集结后停下。

请问，当所有兔子都完成集结后，每只兔子都分别位于哪个位置上？

inputFormat:
输入的第一行包含一个整数 $n$，表示兔子的数量。
第二行包含 $n$ 个整数 $p_1,p_2,\cdots, p_n$，相邻整数之间使用一个空格分隔，表示每只兔子的初始位置。

outputFormat: 输出一行包含 $n$ 个整数，表示每只兔子完成集结后的位置。

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

兔子 $1$ 选择的同伴为兔子 $5$，兔子 $5$ 选择的同伴为兔子 $1$。由于它们彼此间的距离为 $1$，因此兔子 $5$ 会停在原地，而兔子 $1$ 会跳到位置 $1$ 上，与兔子 $5$完成集结。

兔子 $2$ 选择的同伴为兔子 $3$，兔子 $4$ 选择的同伴也为兔子3。对于兔子 $3$ 来说，兔子 $2$ 和兔子 $4$ 与它的距离相同，所以它会选择左边的兔子 $2$ 作为同伴。兔子 $2$ 会向右跳一个位置，兔子 $3$ 会向左跳一个位置，兔子 $4$ 会向左跳一个位置。此时，兔子 $2$ 和兔子 $3$ 均位于位置 $6$，完成集结（停止跳跃）。兔子 $4$ 会继续向左跳跃，直到跳到位置 $6$ 后与兔子 $3$ 完成集结。

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

对于 $40\%$ 的评测用例，$2\le n\le 500$，$1\le p_i\le 10^5$，$p_1,p_2,\cdots,p_n$ 各不相同。
对于所有评测用例，$2\le n \le 10^5$，$1 \le p_i \le 10^9$，$p_1,p_2,\cdots,p_n$ 各不相同。


title: [蓝桥杯 2024 国 A] 旋转九宫格

description:
给定一个 $3\times 3$ 的九宫格，每个格子内分别含有一个数字，每个格子里的数字互不相同。每步我们可以选择任意一个 $2\times 2$ 的区域将其顺时针旋转，例如：

例如

```plain
1 2 3
4 5 6
7 8 9
```

将其旋转右上角，可得：

```plain
1 5 2
4 6 3
7 8 9
```

问最少需要几步才能将给定的状态旋转为

```plain
1 2 3
4 5 6
7 8 9
```

inputFormat:
输入的第一行包含一个整数 $T$ 表示询问的组数。

接下来依次输入每组询问。

每组询问包含三行，每行包含三个数，表示询问的九宫格的状态。

outputFormat: 输出 $T$ 行，每行包含一个整数表示本次询问的答案。

hint:
对于 $60\%$ 的评测用例，$T=1$;
对于所有评测用例，$T\le 10^5$。


title: 小分图最大匹配

description:
给你一个二分图，有一些个左部点。还有 $m$ 个右部点，编号为 $0$ 到 $m-1$。

对于每个左部点 $i$，有一个连边参数 $a_i$，表示其向所有满足 $\exist x\in \mathbb{N}, a_ix\equiv j \pmod m$ 的 $j$ 连接了一条边。

现在给出两个长度为 $n$ 的数组 $a_i,c_i$，表示存在 $c_i$ 个左部点的连边参数为 $a_i$，换句话说，这个图总共有 $\sum\limits_{i=1}^n c_i$ 个左部点，使用这样的方式来快速读入左部点的连边参数。

保证 $a_i$ 两两不同。

求这张二分图的最大匹配。

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

接下来 $n$ 行，每行两个正整数，第 $i$ 行的两个数分别表示 $a_i$ 和 $c_i$ 的值。

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


title: 电王的传送迷宫

background: 电王天天玩传送门。

description:
给出一个大小为 $n\times m$ 的二维网格图。

网格上的 `.` 是可以通行的路径，`#` 是不能通行的障碍。

你每次可以走到一个与当前位置四连通的且不超过边界的点。

严格来说，若你当前在点 $(x,y)$，你可以走到 $(x-1,y),(x+1,y),(x,y-1),(x,y+1)$ 中的一个，并且保证在任意时刻你的坐标 $(x,y)$ 应该满足 $1\le x\le n,1\le y\le m$。

我们从起点 $(sx,sy)$ 出发，你希望知道到达任意一个位置至少要走几步。

但这太简单了，于是精通传送门的电王在这个网格图上建造了 $p$ 个传送门，它们的坐标分别为 $(a_1,b_1),(a_2,b_2),...,(a_p,b_p)$。

而电王也设计了 $q$ 个终点，它们的坐标分别为 $(c_1,d_1),(c_2,d_2),...,(c_q,d_q)$。

假如你使用了 $i$ 次传送门，当你到达任意一个传送门，你可以选择直接传送到点 $(c_{i+1},d_{i+1})$。而第 $q$ 次传送后，所有的传送门都会失效。

**所以，传送到的位置只与你传送的次数有关，而与你到达了哪个传送门没有任何关系，我们可以认为所有传送门都是等价的。**

**保证 $p$ 个传送门和 $q$ 个终点的位置都不是障碍。**

保证对于任意输入给出的坐标对应的位置上都是可以通行的路径，且这些坐标一定两两不同。

但电王有的时候并不想知道到去往任意点最少要移动几步，可能他只想知道到一个终点 $(tx,ty)$ 的最少移动步数，我们会在输入格式中了解这个测试点电王的喜好（保证 $tx,ty$ 不是一个障碍）。

inputFormat:
第一行输入一个正整数 $opt$。

第二行两个正整数 $n,m$，表示网格图的大小。

然后的 $n$ 行，每行 $m$ 个字符，用来描述这个网格的形态。

下一行若干个正整数，前四个数分别表示 $sx,sy,p,q$，若 $opt=1$，我们还会额外输入两个数 $tx,ty$，表示电王只想知道从起点到 $(tx,ty)$ 的最少移动步数。

接下来 $p$ 行，每行两个正整数，分别表示 $a_i,b_i$ 的值。

最后 $q$ 行，每行两个正整数，分别表示 $c_i,d_i$ 的值。

outputFormat:
若 $opt=0$，输出一个 $n\times m$ 的数组矩阵。第 $i$ 行 $j$ 列的数表示从起点 $(sx,sy)$ 到达 $(i,j)$ 最少移动几步，如果不可能到达或者这个地方是一个障碍，输出 `-1`。

否则输出一个数，表示从起点 $(sx,sy)$ 到达 $tx,ty$ 最少移动几步，如果不可能到达输出 `-1`。

**注意：使用传送门改变位置的操作，不算入移动的步数。**


title: 「CROI · R2」在相思树下 II

background:
真的要继续吗？

真的不想放弃吗？

真的有用吗？

description:
狐妖们在涂山上举办了一场淘汰制比赛，现在已知第 $i$ 名参赛者实力为 $i$，每场比赛都会有两名选手决出胜负，胜者进入下一轮，为了尽量让实力较强和较弱的参赛选手均有获胜的可能，涂山雅雅设计了一种特殊的比赛规则。

具体而言，一共有 $2^n$ 位选手报名参加淘汰赛，每场比赛一定按照两种规则之一进行。

- 规则一：参加比赛的两名选手实力较强者胜出。
- 规则二：参加比赛的两名选手实力较弱者胜出。

现在涂山雅雅会对你进行 $m$ 次询问，对于一个每场比赛规则确定但选手分布未知的签表，每次询问第 $a$ 名选手能否闯入第 $b$ 轮比赛，若能则输出 `Yes`，否则输出 `No`。特殊地，若某位选手夺得了冠军，则我们称其闯入了第 $n+1$ 轮比赛。

下图展示了一张每场比赛规则确定，但选手分布未知的签表示例。其中，每场比赛下标注 $\max$ 表示该场比赛按照规则一进行，实力较强者胜出；标注 $\min$ 表示该场比赛按照规则二进行，实力较弱者胜出。

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

inputFormat:
第一行两个整数 $n,m$，含义如题面所示。

接下来 $n$ 行描述签表，其中第 $i$ 行有 $2^{i-1}$ 个整数，代表第 $n-i+1$ 轮中从左往右的每场比赛的比赛规则，其中 $1$ 代表该场比赛按照规则一进行，$2$ 代表该场比赛按照规则二进行。

接下来 $m$ 行每行两个整数 $a,b$，代表一次询问。

outputFormat: 共 $m$ 行，每行一个字符串 `Yes` 或 `No` 代表每次询问的答案。

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

样例中的签表与题目描述中的图示一致。

若要使第六位选手进入第二轮，或使第七位选手进入第三轮，均可按照如下顺序安排选手位置：$\{1,2,3,4,7,8,5,6\}$。具体比赛情况如下图所示。

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

显然不存在一种可能的情况使得第八位选手进入第四轮（即夺得冠军）。

**【数据范围】**

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

- Subtask 0（20 points）：$n \leq 3$，$m \leq 20$。
- Subtask 1（10 points）：对于所有询问，$b \leq 2$。
- Subtask 2（10 points）：保证每场比赛的规则均为规则一。
- Subtask 3（20 points）：保证第 $i$ 轮中的所有比赛比赛规则均相同。
- Subtask 4（40 points）：无特殊限制。

对于所有数据，$1\leq a\leq 2^n$，$1\leq b\leq n+1$，$1 \leq 2^n,m \leq 10^6$。


title: [蓝桥杯 2024 国 A] 最长子段

description:
给定一个长度为 $n$ 的序列 $(s_1,s_2,\cdots,s_n)$ 和三个数 $a,b,c$，你需要找出一对 $L,R$ 满足如下式子：

$$
\sum\limits_{i=L}^Rs_i>a(bR-cL),1 \le L \le R \le n
$$

即，序列中的第 $L$ 至 $R$ 项之和大于 $a\cdot (b\cdot R - c \cdot L)$，求出满足条件的 $L,R$ 中 $R - L + 1$ 的最大值。

测试数据保证存在这样的一对 $L$ 和 $R$。

inputFormat:
输入的第一行包含四个整数 $n,a,b,c$，相邻整数之间使用一个空格分隔。

第二行包含 $n$ 个整数 $s_1,s_2,\cdots,s_n$，相邻整数之间使用一个空格分隔。

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

hint:
对于 $60\%$ 的评测用例，$n\le 5000$；
对于所有评测用例，$1\le n\le 3 \times 10^5$，$1\le a,b,c\le 1000$，$|s_i| \le 10^9$。


title: [蓝桥杯 2024 国 A] gcd 与 lcm

description:
给定两个数 $x,y$，求有多少种不同的长度为 $n$ 的序列 $(a_1,a_2,\cdots,a_n)$，其所有元素的最大公约数为 $x$ 且最小公倍数为 $y$。

两个序列 $(a_1,a_2,\cdots,a_n)$ 与 $(b_1,b_2,\cdots,b_n)$ 不同，是指存在至少一个位置 $i$ 满足 $a_i\neq b_i$。

由于答案可能很大，请输出答案对 $998\ 244\ 353$ 取模后的结果。

inputFormat:
输入的第一行包含一个整数 $Q$ 表示询问次数。

接下来 $Q$ 行，每行包含三个整数 $x,y,n$ 表示一组询问，相邻整数之间使用一个空格分隔。对于每个询问，保证至少存在一个满足条件的序列。

outputFormat: 输出 $Q$ 行，每行包含一个整数，依次表示每个询问的答案。

hint:
对于 $40\%$ 的评测用例，$n\le 30$；
对于 $70\%$ 的评测用例，$n\le 5000$；
对于所有评测用例，$1\le Q\le 100$，$2\le n\le 10^5$，$1\le x,y\le 10^9$。


title: [蓝桥杯 2024 国 A] 重复的串

description: 给定一个仅含小写字母的字符串 $S$，问有多少个长度为 $n$ 的仅含小写字母的字符串中恰好出现了两次 $S$。答案对 $998\ 244\ 353$ 取模。

inputFormat: 输入一行包含一个字符串 $S$ 和一个整数 $n$，用一个空格分隔。

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


title: [蓝桥杯 2024 国 A] 最强策略家

description:
在一场智力对弈的游戏中，两位玩家小蓝和小乔需要对一个初始值均为 $0$、大小为 $n \times n$ 的矩阵进行操作，以展现他们的智慧和谋略，并确定谁才是最强的策略家。

操作规则如下：

- 小蓝拥有先手操作权，完成操作后轮到小乔，然后再轮到小蓝，依此规律交替进行。
- 在小蓝的每个回合中，他可以选择矩阵中的 $2$ 个元素，并将这些元素的值变更为 $1$。
- 在小乔的第 $1$ 个回合中，他可以选择一个大小为 $1\times 1$ 的子矩阵，并将该子矩阵内的所有元素的值重置为 $0$。在小乔的第 $2$ 个回合中，他可以选择一个 $2\times 2$ 的子矩阵，并将该子矩阵内的所有元素的值重置为 $0$。以此类推，在小乔的第 $i$ 个回合中，他可以选择一个大小为 $i\times i$ 的子矩阵，并将该子矩阵内所有元素的值重置为 $0$。
- 在双方各进行了 $n$ 次操作后，游戏结束。

设在整个游戏过程中，矩阵中值为 $1$ 的元素的数量最多时为 $X$。

小蓝致力于最大化 $X$ 的值，小乔致力于最小化 $X$ 的值。

假设两位玩家都具有完美的逻辑推理能力，并总是采取最佳策略。请问，$X$ 的值会是多少（即在整个游戏过程中，矩阵中值为 $1$ 的元素的数量最多时是多少）？

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

接下来 $T$ 行，每行包含一个整数 $n$，表示矩阵的大小。

outputFormat: 对于每组数据，输出一行包含一个整数，表示答案。

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

在第一个样例中，小蓝和小乔需要轮流操作一个 $2\times 2$ 的矩阵。

**初始矩阵状态：**

$$
\begin{bmatrix}
0 & 0 \\
0 & 0
\end{bmatrix}
$$

**小蓝的第 $1$ 个回合：** 将两个值为 $0$ 的元素变更为 $1$。可能的状态为：

$$
\begin{bmatrix}
1 & 1 \\
0 & 0
\end{bmatrix}
$$

**小乔的第 $1$ 个回合：** 小乔只能选择一个 $1\times 1$ 的子矩阵将元素重置为 $0$。为了最小化值为 $1$ 的元素数量，小乔需要将已经是 $1$ 的一个元素重置为 $0$。可能的状态为：

$$
\begin{bmatrix}
0 & 1 \\
0 & 0
\end{bmatrix}
$$

**小蓝的第 $2$ 个回合：** 小蓝再次将两个元素值为 $0$ 的元素变更 $1$。可能的状态为：

$$
\begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
$$

**小乔的第 $2$ 个回合：** 小乔可以选择一个 $2\times 2$ 的子矩阵（即整个矩阵），并且把所有值重置为 $0$。

$$
\begin{bmatrix}
0 & 0 \\
0 & 0
\end{bmatrix}
$$

因此，在双方都采取最佳策略下，矩阵中值为 $1$ 的元素最多时能达到 $3$ 个。

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

对于 $30\%$ 的评测用例，$1 \le T \le 10^3$，$1 \le n \le 10^3$。
对于所有评测用例，$1 \le T \le 10^5$，$1 \le n \le 10^9$。


title: [蓝桥杯 2024 国 A] 异或路径

description:
给定一棵有 $n$ 个结点的树，结点 $1$ 至 $n$ 编号。编号为 $x > 1$ 的结点与编号为 $\lfloor \sqrt x \rfloor$
 的结点有一条权值为 $x-\lfloor \sqrt x \rfloor ^ 2$ 的边。

定义一条路径的价值为这条路径上的所有边的权值的异或和。如果两条路径包含不同的边，则认为这两条路径不同。求这棵树的所有本质不同的简单路的价值的乘积（价值为 $0$ 的除外），答案对 $998\ 244\ 353$ 取模。

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

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

hint:
对于 $40\%$ 的评测用例，$n\le 10^3$；
对于 $70\%$ 的评测用例，$n\le 10^6$；
对于所有评测用例，$1\le n\le 10^9$。


title: [蓝桥杯 2024 国 A] 数学题

description: 求 $\sum\limits_{i=1}^n{\sum\limits_{j=1}^m{|f(ij)|}}$，其中 $|f(x)|$ 当 $x$ 是完全平方数时为 $1$，否则为 $0$。

inputFormat: 输入一行包含两个正整数，用一个空格分隔，表示题目描述中的 $n$ 和 $m$。

outputFormat:
输出一行包含一个正整数表示答案。

提示：数据保证答案不会超出 `unsigned long long` 表示范围。

hint:
对于 $15\%$ 的评测用例，$n,m \le 10^5$；
对于 $30\%$ 的评测用例，$n \le 10^7$，$m \le 10^9$；
对于 $50\%$ 的评测用例，$n,m \le 10^{11}$；
对于 $70\%$ 的评测用例，$n,m \le 10^{15}$；
对于所有评测用例，$1 \le n,m \le 1.5 \times 10^{16}$。

感谢 @[ACaCaca_](https://www.luogu.com.cn/user/320423) 提供数据。


title: 「CROI · R2」落月摇情

background:
>昨夜闲潭梦落花，\
可怜春半不还家。\
>江水流春去欲尽，\
江潭落月复西斜。
>
>斜月沉沉藏海雾，\
碣石潇湘无限路。\
>不知乘月几人归，\
落月摇情满江树。

description:
小烟是住在月亮上的仙女。为了和人间保持联系，小烟在江边种了一棵树。每当月光透过枝叶洒在江面上，形成特定的图案时，小烟就能与那个人产生心灵感应。为了让形成的图案更加美观，小烟用魔法让树的枝条互相交错成他喜欢的样子。你可以认为这棵树是一个**有 $n$ 个节点、$m$ 条边且无重边、无自环的无向连通图**。

某次小烟出差回到月亮上，发现这棵树上所有的枝条都被破坏了。为了快速恢复和人间的联系，小烟需要施加魔法将 $n$ 个节点重新连接起来。施加魔法生成一条边的代价与这条边对月光投影的影响程度有关。由于小烟忘记了原本树的形态，所以她希望花费最小的代价将这棵树恢复到任意一个可能的原先形态。也就是说，她需要这 $n$ 个节点之间形成一张有 $m$ 条边且无重边、无自环的无向连通图。

考虑到你不是仙女，很难计算每条边对投影的影响程度，善良的小烟给出了一个简单的计算方法：给你每个点的影响程度 $a_i$，则用魔法生成一条边 $(u,v)$ 的代价为 $a_u\times a_v$。请你帮小烟找到一组花费代价最小的施加魔法的方案。

**形式化地**，给出 $n$ 个点，每个点有点权 $a_i$，你需要构造一张有 $m$ 条边，且无重边、无自环的无向图，使得这 $n$ 个点连通。设边 $(u,v)$ 的权值为 $a_u\times a_v$，你需要最小化图中所有边的权值和。

inputFormat:
输入共两行。

第一行两个非负整数 $n,m$。

第二行 $n$ 个由空格隔开的整数 $a_i$。

outputFormat:
输出 $m+1$ 行。

第一行一个整数 $ans$，表示你构造的图中，所有边的权值和。

接下来的 $m$ 行每行两个正整数 $u,v$，表示你构造的图中存在一条边 $u,v$。你需要保证 $u\neq v$，且不存在两个无序二元组 $(u,v)$ 相同，且所有输出能表示一张 $n$ 个点的连通图。**如有多解，输出任意一组合法解即可**。

hint:
**【Special Judge】**

本题采用 Special Judge。只要你输出的图满足无重边、无自环且连通，同时其边权和与你输出的答案一致且输出的答案与标准答案一致，你就可以通过对应的测试点。

需要注意的是，请确保你的输出符合输出格式中的要求，否则你得到的结果可能不确定。

本题开启子任务依赖。你可以得到一个子任务对应的分数，当且仅当你通过了当前子任务，同时你也通过了当前子任务依赖的所有子任务。具体的依赖情况见“数据范围”部分的表格。

**【数据范围】**

对于所有数据，满足 $1\leq n\leq 10^6$，$n-1\leq m\leq \min(10^6,\frac{n(n-1)}{2})$，$0\leq |a_i|\leq 10^6$。

本题开启捆绑测试、开启子任务依赖。

|  子任务编号  | $n \le$ | $m \le$ | 特殊性质 | 分值 |子任务依赖|
| :----------: | :-----: | :--------------: | :------------: | :-----: | :-----: |
|$1$ |$7$ | $21$ | 无 |$10$| 无 |
| $2$ | $16$ |  $120$ | 无 |$15$| $1$ |
|  $3$  | $1000$ | $3\times 10^5$| 无 |$15$|$1,2$|
| $4$ | $2\times 10^5$ | $3\times 10^5$ | 保证 $a_i$ 为非负整数 |$15$|无|
| $5$ | $2\times 10^5$ | $3\times 10^5$ | 保证 $m=n-1$ |$10$|无|
| $6$ | $2\times 10^5$ | $3\times 10^5$ |  无  | $15$|$1,2,3$|
| $7$ | $10^6$ | $10^6$ |  无  | $20$|$1,2,3,6$|

**【样例解释】**

- 对于样例一，构造出的图如下图所示。边权和为 $2+-2+-4+-3+-6=-13$。该样例的构图方式是唯一的。

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

- 对于样例二，构造出的图如下图所示。边权和为 $-3+-6+-12+-15+0=-36$。该样例还存在其它正确的构图方式，比如你可以把边 $(5,6)$ 改为边 $(5,3)$。

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


title: 【MX-X4-T5】「Jason-1」占领高地

description:
有一张 $n$ 行 $m$ 列的地图，其第 $i$ 行 $j$ 列的位置的**高度**为 $h_{i,j}$ 且**军事化程度**为 $p_{i,j}$，且满足**任意两个四连通相邻的位置高度差的绝对值不超过 $\bm 1$**。
（两个位置 $(a, b)$、$(c, d)$ 四连通相邻，当且仅当 $\lvert a - c\rvert + \lvert b - d\rvert = 1$。）

你可以选择若干个位置建立补给站。若在位置 $(i,j)$ 建立了补给站，定义其**运输范围**为所有满足 $h_{i,j} - h_{x,y} + p_{i,j} \geq \lvert i - x\rvert + \lvert j - y\rvert$ 的位置 $(x, y)$。每个补给站都可以在其运输范围中任意移动物资的位置。

定义若干个补给站 $(x, y)$ 的安全程度为其中 $h_{x,y}$ 的最小值。

有 $q$ 次询问，每次给出四个整数 $a, b, c, d$，询问：若要建立若干个补给站，以将物资从位置 $(a, b)$ 运输至位置 $(c, d)$，则建立补给站的安全程度最大值是多少？或报告不可能完成运输任务。

**注意：物资可以通过多个补给站间接运输。不一定必须在 $(a, b)$ 和 $(c, d)$ 两点建立补给站。**

**本题数据保证 $\bm{p_{i, j} \le 9}$。**

inputFormat:
第一行，三个正整数 $n,m,q$，表示地图的行数、列数，和询问个数。

接下来 $n$ 行，每行 $m$ 个非负整数，其中第 $i$ 行第 $j$ 列的整数表示高度 $h_{i,j}$。**保证任意两个四连通相邻的位置高度差的绝对值不超过 $\bm 1$**。

接下来 $n$ 行，每行 $m$ 个非负整数，其中第 $i$ 行第 $j$ 列的整数表示军事化程度 $p_{i,j}$。**保证 $\bm{p_{i, j} \le 9}$**。

接下来 $q$ 行，每行四个正整数 $a, b, c, d$，表示询问。

outputFormat: $q$ 行，第 $i$ 行一个整数，表示第 $i$ 次询问的答案，即能让物资从 $(a,b)$ 运输至 $(c,d)$ 时，最大的安全程度。如果无论建立多少补给站都无法实现运输任务，则认为答案是 $-1$。


title: BZOJ4671 异或图

background: 题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。

description:
定义两个结点数相同的图 $G_1$ 与图 $G_2$ 的异或为一个新的图 $G$，其中如果 $(u,v)$ 在 $G_1$ 与 $G_2$ 中的出现之和为 $1$，那么边 $(u,v)$ 在 $G$ 中，否则这条边不在 $G$ 中。

现在给定 $s$ 个结点数相同的图 $G_{1\sim s}$，$S=\{G_1,G_2,\dots,G_s\}$，请问 $S$ 有多少个子集的异或为一个连通图？

inputFormat:
第一行为一个整数 $s$，表示图的个数。

接下来每一行一个二进制串，第 $i$ 行的二进制串为 $g_i$，其中 $g_i$ 是原图通过以下伪代码转化得到的。图的结点从 $1$ 开始编号，下面设结点数为 $n$。

```
Algorithm 1 Print a graph G = (V, E)

for i = 1 to n do
    for j = i + 1 to n do
        if G contains edge (i, j) then
            print 1
        else
            print 0
        end if
    end for
end for
```

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

hint: 对于 $100\%$ 的数据，$2\leq n\leq 10$，$1\leq s\leq 60$。


title: BZOJ4361 isn

description:
给出一个长度为 $n$ 的序列 $a_1,a_2,\dots a_n$。如果序列 $a$ 不是非降的，你必须从中删去一个数。

这一操作将被不断执行，直到 $A$ 非降为止。求有多少种不同的操作方案。操作方案不同当且仅当删除的顺序或次数不同。答案对 $10^9+7$ 取模。

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

第二行输入 $n$ 个正整数 $a_i$，表示序列。

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


title: BZOJ2958 序列染色

description:
给出一个长度为 $n$，由 $\tt B,W,X$ 三种字符组成的字符串 $S$，你需要把每一个 $\tt X$ 染成 $\tt B$ 或 $\tt W$ 中的一个。

对于给出的 $k$，问由多少种染色方式，使得存在整数 $a,b,c,d$ 满足：
- $1\leq a\leq b<c\leq d\leq n$；
- $b=a+k-1$，$d=c+k-1$;
- $S_a=S_{a+1}=\dots=S_b=\tt B$；
- $S_c=S_{c+1}=\dots=S_d=\tt W$；

由于方法可能很多，你只需输出最后的答案对 $10^9+7$ 取模的结果。

inputFormat:
第一行输入两个正整数 $n,k$；

第二行输出一个长度为 $n$ 的字符串 $S$。

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


title: BZOJ2445 最大团

description:
一个 $n$ 个点的无向图被叫做是一个 symmetric labeled cliquer，当且仅当该图的任意一个连通子图拥有相同的点数，并且任意一个连通子图都是完全图。

现在用 $m$ 种颜色给所有的 $n$ 个点的 symmetric labeled cliquer 染色，结点有标号，可以染相同的颜色。问方案数对 $10^{9}-401$ 取模的结果。

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

接下来每行包含两个正整数 $n,m$，含义如题所述。

outputFormat: 输出包含 $T$ 行，每行输出答案。

hint: 数据保证，$1\leq T\leq 2$，$1\leq n,m\leq 2\times 10^9$。


title: Xavier is Learning to Count

description:
Xavier, a 9-year-old student, loves playing many kinds of puzzles. One of his favourites is the following:

Xerier, his classmate, has made many cards. She writes down a single positive number on each of them. No numbers written on different cards are the same. After that she writes down an equation, whose right side is a single positive number chosen by her, and the left side is the sum of $p$ integers:

Then she asks Xavier put $p$ cards on the corresponding $X_i$’s position to make this equation correct, with an additional condition that $X_i$ should be ordered from smaller to bigger, i.e.

Every time Xavier immediately comes up with many solutions. Now he wants to know how many solutions in total are there for any $n$ given by Xerier.

inputFormat:
There are multiple test cases. The number of them is given in the beginning of the input. Then a series of input block comes one by one.

For each test case:

The first line contains two space-separated integers $m$ and $p (1\leq p\leq 5)$. The second line contains $m$ distinct positive integers - the numbers written on each of the cards. None of these integers exceeds $13000$.

There are about $120$ test cases in total, but $90\%$ of them are relatively small. More precisely, all numbers are less than or equal to $100$ in $90\%$ of the test cases.

outputFormat:
For each test case:

For each positive integer, output the number of ways in a single line. To keep the output finite, only numbers with positive ways should be outputted.

Output a blank line after each test case. See sample for more format details.

translation:
集合 $S$ 内有 $m$ 个互异整数。请对于任意整数 $i$ 求出 $S$ 内满足大小为 $p$ 且元素和为 $i$ 的子集数量。

输入格式：$T$ 组测试数据。对于每组数据，第一行输入整数 $m,p$，第二行输入 $m$ 个整数，表示 $S$ 内的元素。

输出格式：只需输出答案不为 $0$ 的 $i$ 及其对应的答案。每组测试数据之间以换行隔开。


title: BZOJ2839 集合计数

description: 一个有 $N$ 个元素的集合有 $2^N$ 个不同子集（包含空集），现在要在这 $2^N$ 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 $K$，求取法的方案数，答案模 $10^9+7$。

inputFormat: 一行两个整数 $N,K$。

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

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

假设原集合为 $\{A,B,C\}$，则满足条件的方案为：$\{AB,ABC\}$，$\{AC,ABC\}$，$\{BC,ABC\}$，$\{AB\}$，$\{AC\}$，$\{BC\}$

**【数据范围】**

对于 $100\%$ 的数据，$1\leq N\leq 1000000$，$0\leq K\leq N$。


title: BZOJ4665 小 w 的喜糖

background:
题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。

---

废话不多说，反正小 w 要发喜糖啦！！

description:
小 w 一共买了 $n$ 块喜糖，发给了 $n$ 个人，每个喜糖有一个种类。这时，小 w 突发奇想，如果这 $n$ 个人相互交换手中的糖，那会有多少种方案使得每个人手中的糖的种类都与原来不同。

两个方案不同当且仅当，存在一个人，他手中的糖的种类在两个方案中不一样。

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

接下来 $n$ 行，每行一个正整数，第 $i$ 个整数 $A_i$ 表示开始时第 $i$ 个人手中的糖的种类。

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

hint: 对于所有数据，$1\leq A_i \leq n \leq 2000$。


title: BZOJ2162 男生女生

background:
题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。

---

雨荨的班主任安远老师是一个非常严厉的老师。到了大学，男生和女生之间难免会出现一些暧昧关系，但这样显然是影响学习的。所以作为艾利斯顿的一块招牌，安远老师当然要拒绝这种现象的出现以及繁衍。

所以每当安远老师发现一个男生和一个女生放学走在一起或者男女生之间互相传纸条等，他就会立马制止并且通知家长。他也要求所有男女生晚上八点之后必须关手机，并且不定期打电话检查。于是安远老师的学生都感慨：这货不是大学，不是大学。

description:
安远老师的学生里，一共有 $n$ 个男生和 $n$ 个女生，编号都以 $1\sim n$ 编号。有 $m$ 对男女生之间有暧昧关系。现在安远老师想找出这样一个男女生群体，每个男生都和每个女生之间有暧昧关系，并且男女生总数最大。注意，男生数目或者女生数目可以为 $0$。

如果有多个这样的群体，安远老师会选择男生最多的那个群体，因为他觉得男生会很不安分。如果这样的群体依然不唯一，他会选择任意一个。

接下来，安远老师从选出的这个群体的所有暧昧关系中，选出 $k$ 个进行调查，使得这个群体的所有男生和女生，都至少和其中的一对暧昧关系有关系（即是这个暧昧关系的男/女主人公）。安远老师想让你告诉他总方案数除以 $19921228$ 的余数是多少。

inputFormat:
输入的第一行包含两个正整数 $n$ 和 $k$，分别代表男生女生的个数，以及安远老师要选择的暧昧关系个数。

第二行为一个正整数 $m$，代表暧昧关系总个数。接下来 $m$ 行，每行两个整数，代表一对有暧昧关系的男女生编号。

outputFormat: 第一行有两个空格隔开的整数，代表选择的团体内男生和女生的个数。第二行有一个整数，代表选法除以 $19921228$ 的余数。

hint: 对于所有数据，$1\leq n \leq 50$，$1\leq m,k \leq 2500$。同一对暧昧关系不会在输入中出现多次。


title: [BalticOI 2022 Day1] Art Collection

description:
有一个值域 $[1,n]$ 的未知排列 $P$。你每次可以询问一个排列 $R$。交互库会返回满足在排列 $P$ 中 $i$ 出现在 $j$ 前面，在排列 $R$ 中 $i$ 出现在 $j$ 后面的有序对 $(i,j)$ 的数量。你需要猜出排列 $P$。

### 实现细节

你无需在程序开头引用头文件 `art.h`，你只需要在代码开头加入以下代码。

```cpp
#include <vector>
void answer(std::vector<int>);
int publish(std::vector<int>);
```

你需要实现一个函数 `void solve(int N)`，这个函数可以调用如下函数：

- `int publish(std::vector<int> R)`
    - 该函数可以向交互库询问排列 $R$，$R$ 应当是一个值域 $[1,n]$ 的排列。
    - 该函数至多能被调用 $4000$ 次。
- `void answer(std::vector<int> R)`
    - 该函数向交互库提交答案，表示你猜测的排列。
    - 你必须恰好调用该函数一次。

inputFormat:
样例交互库从标准输入流读入以下数据：

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

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

如果输入不符格式，则直接判为 `Invalid input!`。

outputFormat:
样例交互库向标准输入流输出以下数据：

在你每一次调用 `public` 函数后，交互库都会输出一行，表示你的交互内容。

在你调用 `answer` 函数，交互库会输出两行。

第一行，$n$ 个整数，表示你回答的排列。

第二行会输出交互库的判决。若回答正确会返回 `Correct: x published ranking(s).`，其中 $x$ 是你的交互次数。否则返回 `Wrong answer!`。


title: BZOJ2164 采矿

description:
浩浩荡荡的 cg 大军发现了一座矿产资源极其丰富的城市，他们打算在这座城市实施新的采矿战略。

这个城市可以看成一棵有 $n$ 个节点的有根树，我们把每个节点用 $1$ 到 $n$ 的整数编号。为了方便起见，对于任何一个非根节点 $v$，它任何一个祖先的编号都严格小于 $v$。树上的每个节点表示一个矿点，每条边表示一条街道。

作为 cg 大军的一个小队长，你拥有 $m$ 个部下。你有一张二维的动态信息表，用 $T_{i,j}$ 表示第 $i$ 行第 $j$ 列的数据。当你被允许开采某个区域时，你可以将你的部下分配至各个矿点。在第 $i$ 个矿点安排 $j$ 个人可以获得 $T_{i,j}$ 单位的矿产。

允许开采的区域是这样描述的：给你一对矿点 $(u,v)$，保证 $v$ 是 $u$ 的祖先（这里定义祖先包括 $u$ 本身）；$u$ 为你控制的区域，可以在以 $u$ 为根的子树上任意分配部下；$u$ 到 $v$ 的简单路径（不包括 $u$ 但包括 $v$，若 $u=v$ 则包括 $u$）为探险路径，在该路径上你可以选择至多一个矿点安排部下。你这次开采的收益为安排有部下的矿点的收益之和。

inputFormat:
输入的第一行包含 $5$ 个正整数 $n,m,A,B,Q$。其中 $n$ 为矿点的个数，$m$ 为部下的数量。$A,B,Q$ 是与动态信息表有关的数据。

第二行包含 $n-1$ 个正整数，第 $i$ 个数为 $F_{i+1}$，表示节点 $i+1$ 的父亲。

接下来需要你用下文的方法依次生成 $n$ 组数据，每组数据共 $m$ 个。其中第 $i$ 组的 $m$ 个数据为信息表中第 $i$ 行的 $m$ 个数据。紧接着一行包含一个正整数 $C$，表示事件的数量。

最后给出 $C$ 行，每行描述一个事件。每个事件会先给出一个 $0$ 或 $1$ 的整数。如果该数为 $0$，则后面有一个正整数 $p$，表示动态信息表有更新，你需要生成一组 $m$ 个数据，来替换信息表中第 $p$ 行的 $m$ 个数据。如果该数为$1$，则后面有两个正整数 $u,v$，表示出现了一个你可以开采的区域，你需要回答这次开采的收益。同一行的各个数之间均用一个空格隔开，没有多余的空格和换行。

数据的生成方法如下：每次生成一组 $m$ 个从小到大排列的数据，替换动态信息表的一行。其中，从小到大第 $j$ 个数替换信息表中第 $j$ 列的数。调用以下代码 $m$ 次并排序得到一组数据。（注意可能会出现重复的数）

```
Function GetInt

A←((A xor B)+(B div X)+(B * X))and Y
B←((A xor B)+(A div X)+(A * X))and Y

return (A xor B)mod Q
```

其中 $A,B,Q$ 均用 $32$ 位有符号整数保存（C/C++ 的 signed long int 类型，pascal 的 longint 类型），$X=2^{16}$，$Y=2^{31}-1$，xor 为位异或运算，div 为整除运算，and 为位且运算，mod 为取余运算。由于只保留了低 $31$ 位，易得我们不用考虑数据的溢出问题。注意每次 $A$ 和 $B$ 都会被改变）

outputFormat: 对于每个开采事件（开头为 $1$ 的事件），输出一行一个整数，为每次的收益。


title: BZOJ4350 括号序列再战猪猪侠

description:
括号序列是一个仅由 `()` 构成的序列。以下的括号序列是合法的：
1. `()` 是一个合法序列。
2. 如果 `A` 是一个合法序列，则 `(A)`  也是一个合法序列。
3. 如果 `A` 和 `B` 都是合法序列，则 `AB` 也是一个合法序列。

定义 $match_i$ 表示从左往右数第 $i$ 个左括号所对应的是第几个右括号。

现在得到了一个长度为 $2n$ 的括号序列，提供 $m$ 个信息，第 $i$ 个信息形如 $a_i,b_i$，表示 $match_{a_i}<match_{b_i}$。

现问，若根据这些信息还原出合法括号序列的方案数一共有多少？答案对 $998244353$ 取模。

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

对于每组数据，第一行两个正整数 $n,m$。其中 $n$ 表示有几个左括号，$m$ 表示信息数。

接下来 $m$ 行，每行两个正整数 $a_i,b_i$。

outputFormat: 对于每组数据，输出一个数表示答案。

hint: 对于所有数据，保证 $1\leq T\leq 5$，$1\leq n\leq 300$，$1\leq a_i,b_i\leq n$。


title: [NWERC 2006] Ticket to Ride

description: 给一张地图，地图上有一些城市，城市之间可能有线路连通，我们用一个无向图来表示以简化概念，每条边有个权值，表示选择这条边需要花费的费用。给定 $4$ 对顶点（可能重复），求一个权值最小的边集，使得任意一对顶点可以由选出的边集中的边相连。

inputFormat:
第一行输入 $2$ 个整数，$n$ 和 $m$，分别表示城市的个数和边的个数。

接下来 $n$ 行，每行一个字符串，表示每个城市的名字。城市的名字为一个不超过 $20$ 个字符，由小写字母构成的字符串。

再接下来 $m$ 行，每行给出 $s_1,s_2,w$，其中 $s_1,s_2$ 为城市的名字，$w$ 为他们之间边的权值。

最后，给出 $4$ 行，每行给出两个字符串，分别为要求的一对城市的名字。

outputFormat: 输出一行，输出最小的花费。

samples:
10 15
stockholm
amsterdam
london
berlin
copenhagen
oslo
helsinki
dublin
reykjavik
brussels
oslo stockholm 415
stockholm helsinki 396
oslo london 1153
oslo copenhagen 485
stockholm copenhagen 522
copenhagen berlin 354
copenhagen amsterdam 622
helsinki berlin 1107
london amsterdam 356
berlin amsterdam 575
london dublin 463
reykjavik dublin 1498
reykjavik oslo 1748
london brussels 318
brussels amsterdam 173
stockholm amsterdam
oslo london
reykjavik dublin
brussels helsinki

samples:
2 1
first
second
first second 10
first first
first first
second first
first first

hint: 数据保证，$1\leq n\leq 30$，$0\leq m\leq 1000$，$1\leq w\leq 10000$。