title: [PA2020] Programowanie współbieżne

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Programowanie współbieżne](https://sio2.mimuw.edu.pl/c/pa-2020-1/pro/)**

为了准备算法竞赛，Bytie 决定学习一些并发编程的知识。毕竟，即使是 PA，也曾经出过分布式题（参考 PA 2018 Runda 4）。

Bytie 从编写 $n$ 个非常简单的程序开始。所有程序共享一个全局整数型变量 $x$，此外，每个程序都有一个私有的计数器 $y$。每个程序都由一连串的指令组成，每个指令都属于以下四种类型之一：

- $\texttt W$：将全局变量的值 $x$ 载入私有计数器 $y$。
- $\texttt Z$：将私有计数器 $y$ 的值写入全局变量 $x$。
- $\texttt{+ }c$：将 $y$ 的值加一正常数 $c$。
- $\texttt{- }c$：将 $y$ 的值减一正常数 $c$。

Bytie 并行运行所有的程序。所有计数器 $y$ 和变量 $x$ 的初始值都是 $0$。这些程序的指令**交错**执行，即所有程序的所有指令都是一个接一个地执行，对于每个时刻，每个程序满足它的指令的一个前缀以一定顺序被执行。

这种交错执行的方式结果是相当不幸的，变量 $x$ 的最终值是如此之小，以至于让 Bytie 非常惊讶。他甚至怀疑这是不可能的，是他的电脑骗了他。帮助 Bytie 验证他的疑惑，写一个验证器，对于给定的程序，计算所有程序并行执行后变量 $x$ 的最小可能值是多少。

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

对于每个测试点，第一行一个整数 $n$，表示 Bytie 写的程序个数。

接下来 $2n$ 行描述每个程序。对于每个程序的描述有两行，第一行一个整数 $l$，表示程序中指令个数。第二行包含对这 $l$ 个指令的描述，指令是如下四种类型之一：

- 一个字符 $\texttt W$：表示载入指令；
- 一个字符 $\texttt Z$：表示写入指令；
- 一个字符 $\texttt{+}$ 和一个数字 $c$：表示给私有计数器加 $c$；
- 一个字符 $\texttt{-}$ 和一个数字 $c$：表示给私有计数器减 $c$。

对于一组数据中的所有测试点，$l$ 的总和不超过 $10^6$。

outputFormat: 输出 $t$ 行，第 $i$ 行是对第 $i$ 个测试点的回答，表示在并行执行这些程序后 $x$ 可能的最小值。

hint:
#### 样例 1 解释

对于第一个测试点，得到最小的 $x$ 程序指令执行顺序如下表。

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

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

#### 数据范围

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

对于 $100\%$ 的数据，保证 $1\le t\le 10^5$，$1\le n\le 10^5$，$1\le l\le 10^5$，$\sum{l}\leq 10^6$。


title: [PA2020] Trzy drogi

type: P

background: 本题仅评测部分测试点。

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Trzy drogi](https://sio2.mimuw.edu.pl/c/pa-2020-1/trz/)**

Byteur 国王，Byteotia 的统治者，梦想着征服 Bitotia。梦见打败敌人是件令人愉快的事，然而生活不是一场梦，醒来后情况就有些不同。

Byteotia 由 $n$ 个城市（编号从 $1$ 到 $n$）组成，由 $m$ 条双向道路连接。每条路都连接着两个不同的城市，但也可能有多条道路连接着同一对城市的情况。从任何城市出发，经过一条或多条道路可以到达其他任意城市。

国王想知道，如果 Bitotia 进攻 Byteotia，从现有的 $m$ 条道路中毁掉三条，会发生什么，将严重损害该国的通信的可能性有多大？你的任务是找出答案！数一数有多少条这样的三条路，在这些路被毁之后，至少有一对城市不可以通过剩余的道路互相到达对方。

inputFormat:
第一行包含两个整数 $n,m$，分别表示 Byteotia 的城市个数和道路条数。

接下来 $m$ 行，每行两个整数 $a_i,b_i$，表示城市 $a_i$ 和 $b_i$ 之间被一条道路连接。

你可以假设从任何城市出发，经过一条或多条道路可以到达其他任意城市。

outputFormat: 输出一行一个整数，表示移除这三条路，至少存在两个城市彼此不可达的无序三元组的个数。

hint:
#### 样例 1 解释

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

请注意，例如移除第 $3,5,7$ 条路后，Byteotia 会被分为多于两部分，但这样的三元组只能被计算一次。

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

#### 数据范围

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

对于 $100\%$ 的数据，保证 $2\le n\le 2\times 10^5$，$3\le m\le 5\times 10^5$，$1\le a_i,b_i\le n$，$a_i\neq b_i$。


title: [PA2020] Królewski bal

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Królewski bal](https://sio2.mimuw.edu.pl/c/pa-2020-1/bal/)**

自古以来，Byteotia 的所有统治者都会举行奢华的舞会，Byteur 国王也不例外。然而，每当他组织一次，他就觉得少了点什么。因此，他决定在下一次舞会中加入一些艺术元素。

为此，Byteur 国王委托他的首席顾问编排演出，不久之后，首席顾问向他提出了自己的设想。

根据顾问的计划，$n^2$ 名马戏团演员将参加演出，其中 $n$ 是一个正整数。在演出的压轴部分，他们将排成 $n$ 行，每行恰好有 $n$ 个马戏团演员，从而形成一个 $n\times n$ 大小的正方形。在压轴部分开始时，每个演员将带或不带燃烧的呼拉圈跳舞。在午夜时分，一些带着呼啦圈跳舞的马戏团演员可能会把呼啦圈扔给其他没有带呼啦圈跳舞的马戏团演员。每个演员最多允许扔给一个其他的演员。

他们都会在同一时间进行投掷。他们是专业人士，所以他们的呼啦圈肯定不会在空中相撞，但这里有一个问题。**每次投掷必须在位于同一行或同一列的演员之间进行**。

值得一提的是，Byteur 国王喜欢大规模的行动，所以马戏团演员的数量可能非常庞大。在制定计划时，他的顾问首先确定了数字 $n$，并假设所有马戏团的演员都会在没有燃烧呼拉圈的情况下开始最后的表演。然后，他会选择 $m$ 次一些特定的行列范围，画出一个矩形，并使得这个区域中的每个演员应该以不同的方式开始压轴表演。即，如果在之前的方案中他们拿着呼啦圈开始，则这版方案中他们就不拿呼啦圈开始，反之亦然。

Byteur 国王在得知顾问的计划后，立即明白，为了使演出尽可能地壮观，呼啦圈的抛掷次数应该尽可能地多。Byteur 国王想知道这个数字，但这并不容易，因为他不断修改计划。他的每项修改（他总共已经做了 $q$ 次修改）都涉及到挑选一个马戏团演员并改变他开始压轴表演的方式（即如果他之前拿着呼啦圈开始，那么他现在就不拿着呼啦圈开始，反之亦然）。国王的修改在方案上永久保留，也就是说，如果有任何适用于某个马戏团演员的修改，这个修改的效果一直保留到最后，除非国王再次修改他。

因此，顾问的任务并不简单。帮助他，对于区间 $[0, q]$ 中的每个整数 $i$，在考虑国王的前 $i$ 次修改后，确定可能发生的最大投掷次数。

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

接下来 $m$ 行描述顾问的方案，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示对行编号 $x_1$ 到 $x_2$（包含两端），列编号 $y_1$ 到 $y_2$（包含两端）的艺术家进行一次操作。行列编号均从 $1$ 到 $n$。

接下来 $q$ 行描述国王的修改，第 $i$ 行包含两个数 $a_i,b_i$，表示国王修改第 $a_i$ 行第 $b_i$ 列的演员状态。

outputFormat: 输出 $q+1$ 行，第 $i$ 行输出如果考虑国王的前 $i-1$ 次修改，可能发生的最大投掷次数。

hint:
#### 样例 1 解释

下图展示了国王进行了第一次修改后的情况。演出开始有呼啦圈的演员用加粗圆圈标出，箭头标明了可能发生的投掷。

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

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

#### 数据范围

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

- 对于一些子任务，满足 $n\le 50$，$m\le 10^4$，$q=0$。
- 对于一些其他的子任务，满足 $n\le 200$，$m\le 10^5$，$q\le 10$。
- 对于一些其他的子任务，满足 $n\le 2\times 10^3$，$m\le 10^5$，$q\le 5\times 10^3$。
- 对于一些其他的子任务，满足 $q=0$。

对于上述情况，至少有一个子任务满足。

对于 $100\%$ 的数据，保证 $1\le n\le 3\times 10^5$，$0\le m,q\le 3\times 10^5$，$1\le x_1\le x_2\le n$，$1\le y_1\le y_2\le n$，$1\le a_i,b_i\le n$。

此外，对于每个子任务，至少满足以下条件中的一个：

- $n\le 2\times 10^3$
- 时间限制为 $12$ 秒

由于未给出具体子任务时间限制，因此在洛谷上所有子任务的时间限制均为 $3$ 秒。


title: [PA2020] Bardzo skomplikowany test

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Bardzo skomplikowany test](https://sio2.mimuw.edu.pl/c/pa-2020-1/bst/)**

Bytie 刚刚参加了算法和数据结构这门课的面试。他没有为之学习太长时间，所以他做得不是太好。经过几分钟的交谈，这位心碎的主讲老师决定给这个男孩最后一次机会。

- 「孩儿，你知道啥是 BST 不？」教授问

Bytie 听到这句话后内心狂喜，因为在他上课睡觉的时候记住了一些理论。

- 「知道。大小为 $n$ 的 BST 是一棵有根树，其顶点用 $1$ 到 $n$ 的整数来编号。每个节点最多可以有两个子节点；它可以有一个最多一个左子节点和一个最多一个右子节点。此外，每个节点的编号必须大于其左子树中所有节点的编号，并小于其右子树中所有顶点的编号。」Bytie 回答说，他达到了他潜意识的深处。
- 「很好。让我们看看你是否记住了如何对 BST 进行旋转。」一直坐在那里的教授回答说。他站起来，向黑板走去。

Bytie 被冷汗浸透了。他一时失去了信心，因为他记不起旋转的具体原理（可能在上这节课的时候，他正在另一边摸鱼，没听课）。考官在黑板上画了两棵同样大小的 BST 树，并让 Bytie 用正确的旋转将第一棵树转化为第二棵树。

Bytie 想了一会儿，认为左旋就是选择某个节点 $v$ 和它的右子节点 $w$，并让 $w$ 成为 $v$ 的父节点。Bytie 的直觉用以下伪代码描述。

```
if v.Parent != null then
    if v.Parent.RightSon == v then
        v.Parent.RightSon := w
    else
        v.Parent.LeftSon := w
w.Parent := v.Parent
v.Parent := w
w.LeftSon := v
v.RightSon := null
```

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

以此类推，Bytie 理解了右旋，其中 $w$ 是 $v$ 的左子节点。

```
if v.Parent != null then
    if v.Parent.RightSon == v then
        v.Parent.RightSon := w
    else
        v.Parent.LeftSon := w
w.Parent := v.Parent
v.Parent := w
w.RightSon := v
v.LeftSon := null
```

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

然而，Bytie 很快就注意到有些不对劲。如果节点 $w$ 在左旋时有左子树，它就会丢失！同样在右转过程中，节点 $w$ 的右子树也会丢失。

- 「快点孩儿，你不是唯一一个想通过这次考试的人。」教授不耐烦地催促道。

在没有太多时间考虑的情况下，Bytie 假设只有在这个有问题的子树是空的情况下才能执行旋转，也就是说，如果没有顶点丢失并且树保持一致的话才进行旋转。

为了尽快结束他的煎熬，他决定进行最少次数的旋转，使他能够将第一棵树变成第二棵。请告诉他这是否可行，如果可行，他需要进行多少次轮换？由于这个数字可能相当大，请告诉他这个值对 $10^9+7$ 取模后的值。

inputFormat:
第一行包含一个整数 $n$，表示这个 BST 的大小。

接下来两行描述这两棵树。对于一棵树用一行 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 描述。如果 $a_i\ge 1$，表示 $i$ 节点的父节点；如果 $a_i=-1$，则表示这是树的根节点。

你可以假设这两棵树都是合法的 BST，即树中没有环，恰好有一个根节点，每个节点最多只有一个比自己小的子节点和一个比自己大的子节点。

outputFormat: 输出应该包含一个整数，表示用 Bytie 的方式把第一棵树转化为第二棵树所需最少旋转次数对 $10^9+7$ 取模后的值，如果不可能转化，输出 $-1$。

hint:
#### 样例 1 解释

下图展示了旋转最小次数所采取的旋转方式。

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

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

#### 数据范围

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

对于 $100\%$ 的数据，保证 $1\le n\le 5\times 10^5$，$-1\le a_i\le n$，$a_i\neq 0$。


title: [PA2020] Cukierki

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Cukierki](https://sio2.mimuw.edu.pl/c/pa-2020-1/cuk/)**

Bytie 要去参加 Bitek 的生日聚会。他知道 Bitek 喜欢吃甜食，所以他想送他一些糖果作为礼物。他买了 $n$ 袋糖，其中第 $i$ 袋包含 $a_i$ 个糖果。

然而，这些糖相当重，Bytie 想知道他是否需要把它们全都给 Bitek。他决定，他将选择一个非空的袋装糖果子集，把它们拿给 Bitek，并对他说：「我这里总共有 $x$ 颗糖果，你想要多少？」，其中 $x$ 将是带到派对上的包装里的糖果总数。Bitek 听到这个问题后，可能会选择区间 $[1, x]$ 中的任何整数 $y$。无论 Bitek 的回答如何，他都希望能够从带到派对上的糖中选择一部分（其余的留给自己），这样这些袋糖中的糖果总数正好等于 $y$。当然，不可以撕毁包装纸——给散装的糖果是不礼貌的。

因此，Bytie 在想，他能给 Bitek 带去多少种非空的袋装糖果子集，以便在不考虑 Bitek 的选择的情况下，能够送给他所需数量的糖果。请帮助他计算一下吧！由于这种子集的数量可能非常大，请输出它对 $10^9+7$ 取模后的结果。

inputFormat:
第一行一个整数 $n$，表示 Bytie 有的袋装糖果数量。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每袋糖果中糖果的数量。

outputFormat: 输出可能的袋装糖果子集种类数对 $10^9+7$ 取模后的值。


title: [PA2020] Skierowany graf acykliczny

description:
**题目译自 [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Runda 5 [Skierowany graf acykliczny](https://sio2.mimuw.edu.pl/c/pa-2020-1/dag/)**

正如名字所示，有向无环图（*Directed Acyclic Graph*，简称 DAG）是一个无环的有向图。

如果我们在这样一个图中选择两个节点，我们可以计算出这些节点之间存在多少条不同的有向路径。如果其中一条路径包含一条边而另一条不包含这条边，我们就认为这两条路径是不同的。

你的任务是构造一个 $n$ 个节点（编号从 $1$ 到 $n$）的有向无环图，其中从节点 $1$ 到节点 $n$ 正好有 $k$ 条路径。你的图最多可以有 $100$ 个节点，每个节点最多可以有两条出边，而且不能包含重边（即如果一个节点有两条出边，它们必须通向不同的节点）。可以证明，对于每一个满足输入中约束条件的 $k$，都可以构造一个满足条件的图。

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

outputFormat:
第一行输出一个整数 $n$，表示你构造的图中节点的个数。

接下来 $n$ 行，每行两个整数。第 $i$ 行表示以编号为 $i$ 的节点为起点的出边到达的节点编号。这两个数中任何一个都可以是 $-1$，表示不存在这条边。如果两个数都不是 $-1$，那这两个数不应该相等。

如果有许多满足条件的图，你可以输出任何一个。注意你不需要最小化节点个数，且在限制之下图节点个数是足够的。

hint:
#### 样例 1 解释

下图展示了输出中 $6$ 个节点的有向无环图，从 $1$ 到 $6$ 有三条路径：$1\to 3\to 2\to 6,1\to 3\to 6$ 和 $1\to 5\to 6$。

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

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

#### 数据范围

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

对于 $100\%$ 的数据，保证 $1\le k\le 10^9$，$2\le n\le 100$。


title: 「TAOI-1」Antipathy World

background:
> 簡単なことも解らないわ \
> あたしって何だっけ \
> それすら夜の手に絆されて \
> 愛のように 消える 消える \
> さようならも言えぬ儘泣いた フォニイ フォニイ フォニイ \
> 嘘に絡まっているあたしはフォニイ \
> **ANTIPATHY WORLD**

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

可不有 $n$ 朵花，每朵花有一个正整数美丽度。

她发现，有一朵花的美丽度不小于其它任何一朵花的美丽度的两倍。

你想知道这朵花是哪一朵，于是你可以进行至多 $k$ 次询问，每次询问你给出两个正整数 $i,j \in [1, n]$，可不会告诉你第 $i$ 朵和第 $j$ 朵花的美丽度之差的绝对值。

你想运用这些询问的答案，得到最美丽的花是第几朵。

### 交互格式

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

第一行交互库给出一个整数 $T$，表示数据组数。

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

对于你的每组询问，你输出 `? i j`，交互库会返回一个非负整数，表示第 $i$ 朵和第 $j$ 朵花的美丽度之差。

如果你已经得到答案，输出 `! i` 代表你得到第 $i$ 朵花为最美丽的花。在此之后你应该开始对下一组数据的处理。

每次你输出之后，请**刷新缓冲区**。

你可以使用如下语句来清空缓冲区：

- 对于 C/C++：`fflush(stdout)`；
- 对于 C++：`std::cout << std::flush`；
- 对于 Java：`System.out.flush()`；
- 对于 Python：`stdout.flush()`；
- 对于 Pascal：`flush(output)`；
- 对于其他语言，请自行查阅对应语言的帮助文档。

特别的，对于 C++ 语言，在输出换行时如果你使用 `std::endl` 而不是 `'\n'`，也可以自动刷新缓冲区。

inputFormat: 见「交互格式」。

outputFormat: 见「交互格式」。

hint:
样例中给出了一种可能的交互方式，其中花的美丽度为 $\{4,1,2\}$。

---

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

- Subtask 1（20 points）：$k=\dfrac{n(n-1)}{2}$，$n \le 200$。
- Subtask 2（30 points）：$k=n$。
- Subtask 3（50 points）：$k=\left\lfloor\dfrac{n}{2}\right\rfloor+2$。

对于所有测试数据，设所有花的美丽度为 $a_i$，$1 \le T \le 25$，$3 \le n \le 5 \times 10^4$，$1 \le a_i \le 10^8$。


title: [语言月赛202303] M Function G

type: B

description:
对于一个长度为 $n$ 的正整数数列 $a$，Farmer John 定义 M 函数 $M(l, r)$ 如下：

$$
M(l, r) = \begin{cases}
\left(M(l, \left \lfloor \dfrac{l + r}{2} \right \rfloor) \bmod \max(M(\left \lfloor \dfrac{l + r}{2} \right \rfloor + 1, r), 7)\right ) + \left(a _ {\left \lfloor \frac{l + r}{2} \right \rfloor} - 1 \right ) & |r - l| > 5 \\
\max \limits _ {l \leq i \leq r}{a _ i} & |r - l| \leq 5
\end{cases}
$$

$\max \limits _ {l \leq i \leq r}{a _ i}$ 代表 $a _ l, a _ {l + 1}, \cdots, a _ {r - 1}, a _ r$ 中的最大值。

$\left \lfloor x \right \rfloor$ 代表 $\leq x$ 的最大整数。比如 $\left \lfloor 4.2 \right \rfloor = 4$，$\left \lfloor 5 \right \rfloor = 5$。

$\max(x, y)$ 代表 $x, y$ 中的最大值。

现在给定 $n$ 和 $a$，请你求出 $M(1, n)$。

inputFormat:
输入共两行。

第一行为一个整数 $n$。

第二行为 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，对应题目中的正整数数列 $a$。

outputFormat: 输出共一行一个整数，代表 $M(1, n)$ 的值。


title: [Ynoi2079] 2stmo

description:
给定一棵 $n$ 个顶点的有根树，顶点编号为 $1,\dots,n$ ，$1$ 为根，$f_2,\dots,f_n$ 依次表示 $2,\dots,n$ 的父亲。

给定 $m$ 对整数 $a_1,b_1,\dots,a_m,n_m$ ，你需要构造一个 $1,\dots,m$ 的排列 $p_1,\dots,p_m$ ，满足这个排列的代价不超过 $4\times 10^9$。

排列的代价定义为：

$|S(a_{p_1})|+|S(b_{p_1})|+\sum\limits_{i=2}^m |S(a_{p_{i-1}})\oplus S(a_{p_i})|+|S(b_{p_{i-1}})\oplus S(b_{p_i})|$

其中 $S(x)$ 是以 $x$ 为根的子树中的顶点构成的集合，$|A|$ 是集合 $A$ 的元素个数，$A\oplus B$ 是集合 $A,B$ 的对称差（即在 $A,B$ 中恰好出现一次的元素构成的集合）。

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

第二行 $n-1$ 个整数 $f_2,\dots,f_n$ ；

接下来 $m$ 行，每行两个整数表示 $a_i,b_i$ ，$i=1,\dots,m$ 。

outputFormat: 输出 $m$ 行，每行一个整数，依次表示 $p_1,\dots,p_m$ 。

hint:
Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $25\%$ 的数据，满足 $n,m\le 10^4$。

对于 $50\%$ 的数据，$n,m\le 2\times 10^5$。

对于 $75\%$ 的数据，$n,m\le 5\times 10^5$。

对于 $100\%$ 的数据，满足 $1\le n,m\le 10^6$，$1\le f_i\le i-1$，$1\le a_i,b_i\le n$。


title: 除法题

description:
给定大小为 $n$ 的集合 $a$，保证其中元素互不相同且均为正整数。

如果我们从中**按顺序**取出三个元素 $a, b, c$，则共有 $n \cdot (n-1) \cdot (n-2)$ 种不同的选择方案。

现在对于一种选择方案 $(a,b,c)$，定义其权值为 $\Bigl\lfloor\dfrac{a}{b}\Bigr\rfloor\Bigl\lfloor\dfrac{a}{c}\Bigr\rfloor\Bigl\lfloor\dfrac{b}{c}\Bigr\rfloor$。

你需要对所有的选择方案计算权值的总和，你只需输出这个总和对 $2^{32}$ 取模的结果。

注：$\lfloor a\rfloor$ 表示不大于 $a$ 的最大整数。如 $\lfloor 2.4\rfloor=2$、$\lfloor 5\rfloor=5$。

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

第二行，$n$ 个正整数 $a_1, a_2, \ldots, a_n$，每个数描述了集合 $a$ 的一个元素，这些数互不相同。

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


title: 「CMOI R1」First Town of This Journey／Grid Covering

background:
![Link:First Town of This Journey](bilibili:BV1ka411G78Y)$\small\color{white}/10^{\text{th}}\text{Problem by AtC}.$

本题中认为两个点间的连线为以这两个点作为端点的线段。

description:
$\text{BiOI}$ 有一个 $n$ 行 $m$ 列的网格。你需要选出最少的格点，使得任意两个**不同的**格点的连线至少经过一个被选中的点（这里我们认为一条线段**经过了**它的两个端点）。

$\text{CmOI}$ 觉得这个问题太简单了，所以他会另外给定 $a,b,x$，表示第 $a$ 行第 $b$ 列的格点必须被或不被选中：

* $x=0$ 时该格点不可选中；
* $x=1$ 时该格点必须选中。

你只需要求出最少选出几个格点，$\text{BiOI}$ 和 $\text{CmOI}$ 会把网格和你的答案一起丢给 $\text{ArCu}$ 让他构造方案。

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

第二行三个整数 $a,b,x$。

outputFormat: 一行一个整数，最少选出的格点数。

hint:
$\text{Details about Subtasks}:$

所有数据满足 $1\leq n,m<2^{32},1\leq a\leq n,1\leq b\leq m,0\leq x\leq 1$。

* $\text{Subtask 1}:1\leq n,m\leq 10,\text{5 points.}$
* $\text{Subtask 2}:x=0,\text{25 points}.$
* $\text{Subtask 3}:x=1,\text{30 points.}$
* $\text{Subtask 4}:\text{40 points.}$

$\text{Sample Explanation}:$

* $\text{Sample 1}:$

此时网格有 $3$ 行 $3$ 列，要求第 $2$ 行第 $2$ 列的格点必须被选中。

最优方案如下（黑色是被选中的格点）：

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

注意以下方案并不合法：

* 图中给出了两种方法使得两个不同的格点间连线不经过黑点；
* 第二行第二列的格点没有被选中，输入中要求这个格点必须被选中。

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

以及我们认为端点在黑点上算是经过黑点。也就是说下面的这种连线经过了一个黑色格点。

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


title: [语言月赛202303] Milk Sales S

description:
Farmer John 正在售卖两款牛奶，分别为 A 型牛奶和 B 型牛奶。

Farmer John 已经售卖了 $n$ 个月这两种牛奶，得到了一份数据 $a _ 1, a _ 2, \cdots a _ n$ 和 $b _ 1, b _ 2, \cdots, b _ n$，分别代表 A、B 型牛奶每个月的销量。

其中，$a _ i$ 代表 A 型牛奶第 $i$ 个月的销量，$b _ i$ 代表 B 型牛奶分别的销量，二者单位均为盒。

现在，Farmer John 想要知道，在这 $n$ 个月中，在**最少**经过几个月后，B 型牛奶的累计售出的盒数超过 A 型牛奶累计售出的盒数。

形式化的讲，请你求出最小的 $x$，使 $\sum \limits _{i=1}^x a_i<\sum \limits _{i=1}^x b_i$。

inputFormat:
输入共三行。

第一行为一个整数 $n$，代表 Farmer John 售卖牛奶的月份数。

第二行为 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，分别代表这 $n$ 个月中 A 型牛奶每个月的销量（单位为盒）。

第三行为 $n$ 个整数 $b _ 1, b _ 2, \cdots, b _ n$，分别代表这 $n$ 个月中 B 型牛奶每个月的销量（单位为盒）。

outputFormat: 输出共一行一个整数 $x$，代表在**最少**经过 $x$ 个月后，B 型牛奶的累计售出的盒数超过 A 型牛奶累计售出的盒数。


title: Trees

background: ZHY 有很多树，每个树上都有很多点，每个点上都有一个数，但他忘记了每个点上写的数是什么了。

description:
ZHY 拥有 $m$ 棵树，每棵树形态相同，且均有 $n$ 个点。定义 $(i,j)$ 是第 $i$ 棵树上的第 $j$ 个点，你需要为每个点 $(i,j)$ 赋一个值 $a_{(i,j)}$，且满足以下条件：

- 对于 $\forall i \in [1,m],\forall j \in [1,n]$，有 $a_{(i,j)}\in\{0,1\}$。

- 对于 $\forall i \in [1,n]$，有 $\sum_{j=1}^m a_{(j,i)}\le 1$。

- 对于任意的一条边 $(u,v)$ 和 $i \in [1,m]$，有 $a_{(i,u)}+a_{(i,v)}\le 1$。

请你计算有多少种赋值方式，对 $10^9+7$ 取模。注意这 $m$ 棵树是有序的。

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

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示这 $m$ 棵树中每棵树都有一条从 $u$ 到 $v$ 的无向边。保证数据可以构成一棵树。

outputFormat: 输出一行表示答案。

hint:
**本题使用捆绑数据。**

对于所有的数据，$1 \le n \le 10^6$，$1 \le m \le 10^9$。

- Subtask 0（10 pts）：$n,m \le 4$。
- Subtask 1（30 pts）：$n,m \le 10^3$。
- Subtask 2（15 pts）：$n \le 10^3$。
- Subtask 3（25 pts）：$m=1$。
- Subtask 4（20 pts）：无特殊限制。


title: 「TAOI-2」喵了个喵 Ⅳ

background:
小 S 共有 $n$ 只可爱的喵喵，第 $i$ 只喵喵有可爱度 $a_i$。小 S 想要把他的喵喵分成两组。考虑到小 S 的喵喵不像某些喵喵有九条命，他的喵喵只有一条，于是一只喵喵不能被同时分到两组内（请不要试图想象这个画面）。同时，如果一只喵喵没有被分到任意一组，他就会十分生气，很有可能导致小 S 失眠。

当然，小 S 也希望两组的**组可爱度**相等。即存在一个正整数 $x$，使得其中一组的 $\gcd(x, a_i)$ 之和等于另一组的 $\gcd(x, a_i)$ 之和。请你判断是否可以使得小 S 可以将喵喵分成两组，并可以找出一个 $x$ 使得两组的**组可爱度**相等。

description:
给定正整数 $n$ 及长度为 $n$ 的正整数序列 $a$，请你将 $a$ 划分为两个集合 $B, C$ 并给出正整数 $x$，使得 $\sum_{y\in B}\gcd(x,y) = \sum_{y\in C}\gcd(x,y)$。如果无解，输出 $-1$。

你需要保证 $1 \leq x \leq 10^9$，保证在本题的数据约束下若有解则总有 $x \leq 10^9$ 的解。

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

接下来一行为 $n$ 个正整数，其中第 $i$ 个表示 $a_i$。

outputFormat:
如无解，仅输出一行一个整数 $-1$。否则：

第一行输出一个正整数 $x$。

第二行输出一个长度为 $n$ 的 $\tt 01$ 串，第 $i$ 个数为 $\tt 0$ 代表 $a_i$ 被划分到集合 $B$ 中，为 $\tt 1$ 代表 $a_i$ 被划分到集合 $C$ 中。

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

+ Subtask 0（2 pts）：$n$ 为偶数。
+ Subtask 1（8 pts）：$a_i$ 均为奇数。
+ Subtask 2（15 pts）：$n \leq 50$，$a_i \leq 50$。
+ Subtask 3（25 pts）：$n \leq 10^3$，$a_i \leq 10^3$。
+ Subtask 4（50 pts）：无特殊限制。

对于所有数据，$1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^6$。


title: 「SiR-1」Checkmate

background:
这里本来有一串很长的背景，但是出题人觉得它实在太长了，所以就把它删掉了。

「来吧，游戏开始了。」

description:
有一个 $n$ 行 $m$ 列的棋盘。你要在这个棋盘上的所有格子**依次**放置一个棋子。

每当你放置一个棋子，你将会获得一定的分数，获得的分数为**放置时**你放置的这个棋子旁边的格子中没有放置棋子的格子的个数。这里「旁边」指的是上、下、左、右的相邻格子。

你想知道，在**按照最优策略决策放置棋子的顺序的情况下**，你最终得分总和的最大值。

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

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

对于每组测试数据，包含由空格隔开的两个正整数 $n,m$。

outputFormat: 对于每组测试数据，输出一行，代表最大的分数。

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

- Subtask 1（20 points）：$n, m \leq 3$，$T \leq 5$。
- Subtask 2（20 points）：$n, m \leq 4$，$T \leq 10$。
- Subtask 3（20 points）：$n=1$。
- Subtask 4（20 points）：$n=m$。
- Subtask 5（20 points）：无特殊限制。

对于所有测试数据，$1 \leq n, m \leq 10^8$，$1 \leq T \leq 10^5$。


title: [IOI2009] Archery

background: IOI2009 D1T1

description:
一场箭术比赛正在举行。一条直线上排着 $N$ 个靶子，靶子从左到右依次标号为从 $1$ 到 $N$。有 $2N$ 个选手，在比赛的任何时刻，同一个靶位上都有两个选手。比赛的每一轮按照如下规则进行：

- 在同一个靶位的两位选手比赛一场决出胜者，然后所有选手按照如下规则移动：

  - 在 $2$ 到 $N$ 号靶位上的胜者移动到他们的左侧的靶位（即分别移动到 $1\sim N - 1$ 号靶位）。
  - 在 $2$ 到 $N$ 号靶位上的负者，以及 $1$ 号靶位上的胜者，停留在同一个靶位。
  - $1$ 号靶位上的负者移动到 $N$ 号靶位。

比赛一共持续 $R$ 轮，轮数至少为参赛选手的数量，即 $R\geq 2N$。

你是唯一一个准时到达的选手。其它 $2N - 1$ 个选手已经提前到达并站成了一排，你现在要做的就是插入这个队伍。在你进入队伍后，队列中前两个选手（最左侧的两个选手）将对应一号靶位，接下来两个选手将对应二号靶位，以此类推，最右侧的两个选手对应 $N$ 号靶位。

所有 $2N$ 个选手（包括你）都用一个数值衡量技术水平，没有两个选手的技术水平相同。在同一个靶位上，数值较小的选手会成为胜者。

在了解了所有选手的技术水平之后，你需要找到一个位置插入使得你最终对应的靶位序号尽量小，在此前提下，你希望你初始时对应的靶位序号尽量大。

**任务**：编写一个程序，给定所有选手的技术水平（包括你自己）和你的对手们的排列顺序，计算出你的初始靶位编号，以满足你的上述目标。

inputFormat:
第一行包含两个由空格隔开的整数 $N, R$，分别表示靶位数和比赛轮数。

接下来 $2N$ 行给出选手的排列 $S_1, S_2, \cdots,  S_{2N}$。$S_1$ 表示你的排名，$S_2, S_3, \cdots, S_{2N}$ 表示其他选手的排名，依照他们已经排列好的顺序（由左至右）。$S_k$ 是 $1\sim 2N$ 的整数，排名 $1$ 表示最好，排名 $2N$ 表示最差。没有两位选手的排名相同。

outputFormat: 输出一个 $1\sim N$ 的整数，表示开始的箭靶编号。

hint:
### 样例解释

- 样例 1：你是排名倒数第二的选手。如果你从靶 $1$ 开始比赛，接下来你将移动到靶 $4$ 而且一直留在靶 $4$ 直到最后。如果你从靶 $2$ 或靶 $4$ 开始，你将会一直留到最后。如果你从靶 $3$ 开始，你将会击败最差的选手，然后移到靶 $2$ 并留在那里。

- 样例 2：你是排名第二的选手。排名第一的选手在靶 $1$ 并一直留在那里。因此，无论你从哪里出发，你永远会按 $4\to 3\to 2\to 1\to 4$ 的顺序循环移动。为了最终留在靶 $1$，你应该从靶 $2$ 开始。

### 数据范围与约定

- 对于 $20\%$ 的数据，$N\leq 200$。
- 对于 $60\%$ 的数据，$N\leq 5000$。
- 对于 $100\%$ 的数据，$1\leq N\leq 2\times 10 ^ 5$，$2N\leq R\leq 10 ^ 9$，$1\leq S_k\leq 2N$ 且 $S_k$ 互不相同。

另有三组 @[asmend](https://www.luogu.com.cn/user/21658) 提供的 hack 数据，不计分。


title: [语言月赛202303] Factorial B

description:
Farmer John 的孩子做数学题时遇到了一个难题，想要请你解答一下。

这道数学题是，$n!$ 是否是 $12$ 的倍数。

$n!$ 是 $n$ 的阶乘。一般来讲，对于一个正整数 $n$，$n! = 1 \times 2 \times 3 \times \cdots \times n$。特别的，$0 ! = 1$。

Farmer John 也觉得这个问题太难了，因此他想要把这道题交给你来完成，请你帮助他完成这个问题。

inputFormat: 输入共一行一个整数 $n$。

outputFormat:
输出共一行一个字符串。

对第一行，如果 $n!$ 是 $12$ 的倍数，输出 `Yes`，否则输出 `No`。


title: [IOI2009] Hiring

background: IOI2009 D1T2

description:
你需要为一个建设项目雇佣一些工人。现在有 $N$ 位候选工人，标号为 $1\sim N$。第 $k$ 个工人要求如果自己被雇佣，则必须得到至少 $S_k$ 美元的工资。每个工人有能力值 $Q_k$。建筑业监管局规定，你必须按工人们的能力值的比例分配他们的工资。例如，如果 $Q_A = 3Q_B$，则你付给 $A$ 的工资必须恰为 $B$ 的三倍。你可以付给你的工人们任意非负实数金额的工资。

你的手上有 $W$ 美元，你想用这些钱雇佣最大数量的工人。你可以决定选用哪些工人以及付给他们的工资，但必须满足每个工人的最低工资要求以及监管局的分配规定，并保证工资总额不超过 $W$。

工人们的能力值和你的项目无关，因此你只想最大化雇佣工人的数量，而不关心他们的能力值。尽管如此，你仍希望最小化你的支出，即如果存在多种方案，则你需要选择支付给工人们的工资总额最小的那一个。如果仍存在多种方案，任意一个都是满足要求的。

**任务**：编写一个程序，给定每个工人的工资要求和能力值，以及你拥有的资金，计算出具体雇佣哪些工人。你必须在最大化工人的数量的前提下最小化支出，并满足上文提到的监管局的要求。

inputFormat:
第一行包含两个由空格隔开的整数 $N, W$，分别表示候选工人数和你拥有的资金。

接下来 $N$ 行，每行描述一个候选工人。其中第 $k$ 行描述第 $k$ 个候选工人，包含两个由空格隔开的整数 $S_k, Q_k$。

outputFormat:
第一行一个整数 $H$，表示你雇佣的工人数量。

接下来 $H$ 行，每行一个整数，表示你雇佣的所有工人的编号（互不相同），以任意顺序排列。

hint:
### 样例解释

- 样例 1：选择工人 $2$ 和 $3$ 是唯一符合所有要求且雇佣了两个工人的方案。你可以分别付给他们 $80$ 美元和 $8$ 美元，满足 $100$ 美元的预算。

- 样例 2：你可以雇佣三个工人。你可以分别付给他们 $1$ 美元，$1.5$ 美元和 $1.5$ 美元。

### 数据范围与约定

对于任意测试点，如果你的方案满足了所有要求和你的目标，你将获得该测试点的满分。**否则**，如果你的第一行是正确的，即你输出了正确的工人数量 $H$，无论你接下来的输出是否符合格式，你都将获得该测试点 $50\%$ 的分数。

注意，在实际评测中，只有你的输出符合格式，才能获得测试点 $50\%$ 或 $100\%$ 的分数。

- 对于 $50\%$ 的数据，$N\leq 5000$。
- 对于 $100\%$ 的数据，$1\leq N\leq 5\times 10 ^ 5$，$1\leq S_k, Q_k\leq 2\times 10 ^ 4$，$1\leq W\leq 10 ^ {10}$。

注意，$W$ 超出了 $32$ 位整形变量的存储范围。你需要使用 $64$ 位整型变量存储 $W$，例如 C/C++ 中的 `long long` 或 Pascal 中的 `int64`。


title: [语言月赛202303] Out for Dinner B

description:
Bessie 一家今晚要外出就餐。饭馆中只有三种菜，这三种菜的名称分别为 `A`、`B`、`C`。

饭店在进行折扣活动。如果我们称消费打 $Y$ 折，则意味着**支付金额**是**菜品金额**的 $\dfrac{Y}{10}$ 倍。具体的，如果购买了 `B` 菜且未购买 `C` 菜，则消费打**八折**；如果购买了 `C` 菜且未购买 `B` 菜，则消费打**七折**；如果 `B`、`C` 两道菜都购买了，则消费打**六折**。

这一次 Bessie 一家人只点了两道菜。这两道菜**可能是相同的**。最终结账时，**菜品金额**是 $x$ 元。给定两道菜的名字和 $x$，请你求出 Bessie 的**支付金额**。

inputFormat:
输入共两行。

第一行为一个整数 $x$，代表 Bessie 一家的**消费金额**。

第二行为两个大写英文字母 $a, b$，代表 Bessie 一家点的两道菜的名称。

outputFormat: 输出共一行一个整数，代表 Bessie 一家这一次在打折后需要支付多少钱。

hint:
### 样例 1 解释

Bessie 一家如果购买了 `B` 菜且未购买 `C` 菜，整次消费会打八折。他们本次未打折前需要支付 $100$ 元，因此打折后需要支付 $100 \times 80\% = 80$ 元。

### 数据规模与约定

对于 $100\%$ 的数据，保证 $10 \leq x \leq 10 ^ {18}$ 且 $x$ 是 $10$ 的倍数，$a, b$ 分别是大写英文字母 `A`、`B`、`C` 中的一个。

请注意，我们不保证 $a, b$ 一定不相同，这意味着可能出现 $a, b$ 相同的情况。


title: [IOI2009] POI

background: IOI2009 D1T3

description:
普罗夫迪夫信息学奥林匹克竞赛（Plovdiv Olympiad in Informatics, POI）正在举行。有 $N$ 个选手和 $T$ 道题目。每道题目只有一组测试数据，因此对于每个选手和每道题目，要么这个选手解决了这道题目，要么没有解决。没有部分分。

比赛结束后，每道题目的分数为没有解决这道题目的选手数量。每个选手的得分为他解决的每道题目的得分之和。

Philip 参加了这场比赛，但他被复杂的计分规则搞糊涂了。他看着比赛结果，无法计算出他的最终排名。写一个程序帮助 Philip 计算他的分数和排名。

在比赛开始之前，每个选手从 $1$ 到 $N$ 编号。Philip 的编号为 $P$。最终的排行榜将所有选手按分数降序列出。为避免平局，在得分相同的选手中，按解决题目数量降序排序（解决题目数量多的选手排在解决数量题目少的选手之前）。如果仍存在平局，则按编号升序排序。

**任务**：编写一个程序，给定每个选手的解题情况，计算出 Philip 的分数和他在最终排行榜上的排名。

inputFormat:
第一行包含三个整数 $N, T, P$，分别由一个空格隔开，分别表示选手数，题目数和 Philip 的编号。

接下来 $N$ 行描述了每名选手的解题情况。其中第 $k$ 行描述了编号为 $k$ 的选手的解题情况，包含 $T$ 个由空格隔开的 $0$ 或 $1$。第 $i$ 个数字描述了编号为 $k$ 的选手是（对应 $1$）否（对应 $0$）解决了第 $i$ 道题。

outputFormat: 输出一行两个由空格隔开的整数，分别表示 Philip 在 POI 竞赛中的得分和他在最终排行榜上的排名。排名用 $1\sim N$ 的整数描述，其中 $1$ 表示选手排在排行榜顶部，$N$ 表示选手排在排行榜底部。

hint:
### 样例解释

第一道题目只有一个选手没有解决，所以它值 $1$ 分。第二道题目有两个选手没有解决，所以它值 $2$ 分。第三道题目有四个选手没有解决，所以它值 $4$ 分。因此编号为 $1$ 的选手得 $4$ 分，编号为 $2, 4, 5$ 的选手得 $3$ 分，编号为 $3$ 的选手得 $1$ 分。根据平局规则，编号为 $2$ 的选手（Philip）排在编号为 $4, 5$ 的选手之前，因此 Philip 的最终排名为 $2$，仅在编号为 $1$ 的选手下面。

### 数据范围与约定

- 对于 $35\%$ 的数据，没有选手得分和 Philip 相同。
- 对于 $100\%$ 的数据，$1\leq N, T\leq 2000$，$1\leq P\leq N$。


title: [福建省队集训2019] 最大权独立集问题

description:
E.Space 喜欢出最大权独立集问题。

接下来，他还想出 $n$ 道最大权独立集问题。

E.Space 有 $n$ 个 AI，编号为 $1\sim n$。

开始第 $i$ 个 AI 里面存有一道 E.Space 事先出好的一道难度为 $d_i$ 的最大权独立集问题。

有些 AI 之间可以互相通信，对于所有的 $2 \le i \le n$，第 $i$ 个 AI 可以和第 $c_i$ 个 AI 互相通信。此外，其他对 AI 不可以互相通信。

E.Space 每次可以选择一个存有一道最大权独立集问题的 AI，把存在里面的题出出来，然后清除存在这个 AI 里的题。

在 E.Space 出题之后清除题目之前，AI 会把这道题发给能和它通信的所有 AI。

如果一个收到这道题的 AI 中已经存有一道最大权独立集问题，那么这个 AI 会把这个收到的题和原本存有的题结合起来，变成一道新的最大权独立集问题存起来。形式化地，如果这个 AI 原来存了一道难度为 $x$ 的最大权独立集问题，接着收到了一道难度为 $y$ 的最大权独立集问题，那么结合之后是一道难度为 $x+y$ 的最大权独立集问题。

如果一个收到题的 AI 中未存有题，那么这个 AI 会销毁收到的这个信息。

由于出题人的丧病心理，E.Space 想要出出来的 $n$ 道最大权独立集问题的难度之和尽量大。

他想叫你帮他解决这个问题，还说如果你成功在这场训练中解决了这个问题，那么在出那 $n$ 道最大权独立集问题的时候，他会在训练结束前 10 分钟切换至你的账号然后提交一份标程代码。

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

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

第三行 $n-1$ 个整数，第 $i$ 个表示 $c_{i+1}$。

outputFormat: 一行一个整数，表示最大的难度之和。

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

一种最优的出题方案如下：

1. 出第 $2$ 个 AI 中的最大权独立集问题，此时该题难度为 $10$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $11,*,13,5$ ($*$ 表示该 AI 中没有最大权独立集问题，下同)。

2. 出第 $3$ 个 AI 中的最大权独立集问题，此时该题难度为 $13$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $11,*,*,18$。

3. 出第 $1$ 个 AI 中的最大权独立集问题，此时该题难度为 $11$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $*,*,*,18$。

4. 出第 $4$ 个 AI 中的最大权独立集问题，此时该题难度为 $18$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $*,*,*,*$。

所以 $4$ 道题的难度之和为 $10+13+11+18=52$。

### 【样例解释 2】

一种最优的出题方案如下：

1. 出第 $3$ 个 AI 中的最大权独立集问题，此时该题难度为 $5$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $1,3,*,5$。

2. 出第 $4$ 个 AI 中的最大权独立集问题，此时该题难度为 $5$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $1,8,*,*$。

3. 出第 $2$ 个 AI 中的最大权独立集问题，此时该题难度为 $8$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $9,*,*,*$。

4. 出第 $1$ 个 AI 中的最大权独立集问题，此时该题难度为 $9$，出题后 $4$ 个 AI 中的最大权独立集问题的难度分别为 $*,*,*,*$。

所以 $4$ 道题的难度之和为 $5+5+8+9=27$。

### 【数据范围】

保证 $\left|d_i\right| \le 10^9$，$1 \le c_i \lt i$，$1\le n \le 400$。

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

对于编号为奇数的子任务，保证 $d_i \ge 0$。

子任务 $1,2$（$11 \times 2 = 22$ 分）：
$n \le 9$。

子任务 $3,4$（$10 \times 2 = 20$ 分）：
$n \le 19$。

子任务 $5,6$（$7 \times 2 = 14$ 分）：
$n \le 50$，$c_i = i-1$。

子任务 $7,8$（$10 \times 2 = 20$ 分）：
$c_i=i-1$。

子任务 $9,10$（$5 \times 2 = 10$ 分）：
$n \le 50$。

子任务 $11,12$（$7 \times 2 = 14$ 分）：
无特殊限制。

### 后记

听说 E.Space 的最大权独立集问题的难度是取了对数的？

听说 E.Space 要把这 $n$ 道题结合成一道题出出来？

听说 E.Space 不会把这些题出在训练里面？


title: [IOI2009] Garage

background: IOI2009 D2T1

description:
一个停车场有 $N$ 个停车位，依次编号为 $1$ 到 $N$。每天早上，停车场的所有停车位都是空的。当一辆车到达停车场时，服务员检查是否有空的停车位。如果没有，则这辆车将在入口处等待，直到有新的停车位。如果有，则这辆车将停在编号最小的空的停车位上。如果多辆车在入口处等待，则它们会按照到达的顺序排成队列，当出现空的停车位时，队列中的第一辆车（最早到达的车辆）将停在该停车位上。

每辆车的停车费是它的重量乘以对应停车位的特定比率，和它在停车场停了多久无关。

停车场管理员得知今天将有 $M$ 辆车前来停车，以及它们到达和离开的顺序。帮他计算今天的收入。

**任务**：编写一个程序，给定每个停车位的特定比率，每辆车的重量和所有车辆到达和离开的顺序，求出车库的总收入。

inputFormat:
第一行包含两个由空格隔开的整数 $N, M$，分别表示停车位数和车辆数。

接下来 $N$ 行描述了停车位的收费率。其中第 $s$ 行包含一个整数 $R_s$，表示编号为 $s$ 的停车位每千克收费的价格。

接下来 $M$ 行描述了车辆的重量。车辆从 $1$ 到 $M$ 编号，其中第 $k$ 行包含一个整数 $W_k$，表示编号为 $k$ 的车辆的重量，单位千克。

接下来 $2M$ 行描述了所有车辆到达和离开的时间顺序。一个正数 $i$ 表示编号为 $i$ 的车辆到达停车场。一个负数 $-i$ 表示编号为 $i$ 的车离开停车场。没有车辆会在到达之前离开停车场，且 $1\sim M$ 每辆车会在序列中出现恰好两次，一次到达，一次离开。此外，没有车辆会在停入停车场之前离开，也就是说，不会有队列中的车辆离开。

outputFormat: 一行一个整数，表示停车场管理员今天的收入。

hint:
### 样例解释

- 样例 1：
  - 车辆 $3$ 停在车位 $1$，支付 $300\times 2 = 600$ 美元。
  - 车辆 $2$ 停在车位 $2$，支付 $100\times 3 = 300$ 美元。
  - 车辆 $1$ 停在车位 $1$（车辆 $3$ 空出的停车位），支付 $200\times 2 = 400$ 美元。
  - 车辆 $4$ 停在车位 $3$，支付 $800\times 5 = 4000$ 美元。

- 样例 2：
  - 车辆 $3$ 停在车位 $1$，支付 $1000\times 5 = 5000$ 美元。
  - 车辆 $1$ 停在车位 $2$，支付 $100\times 2 = 200$ 美元。
  - 车辆 $2$ 到达并在入口处等待。
  - 车辆 $4$ 到达并在入口处等待，排在车辆 $2$ 之后。
  - 当车辆 $1$ 离开时，车辆 $2$ 停在空出的车位 $2$，支付 $500\times 2 = 1000$ 美元。
  - 当车辆 $3$ 离开时，车辆 $4$ 停在空出的车位 $1$，支付 $2000\times 5 = 10000$ 美元。

### 数据范围与约定

- 对于 $40\%$ 的数据，没有车辆会在停车场等待。
- 对于 $100\%$ 的数据，$1\leq N\leq 100$，$1\leq M\leq 2000$，$1\leq R_s\leq 100$，$1\leq W_k\leq 10 ^ 4$。


title: [IOI2009] Mecho

background: IOI2009 D2T2

description:
小熊 Mecho 发现了一个宝藏 —— 蜜蜂的秘密蜜罐，里面装满了蜂蜜！他高兴地吃着他的新发现的宝藏，直到突然有一只蜜蜂看到了他，并发出了警报。他知道就在这个时刻，成群的蜜蜂会从蜂巢里出来，开始四处蔓延，试图抓住他。他知道他必须离开蜜罐，尽快回家，但蜂蜜太甜了， Mecho 不想太早离开。帮 Mecho 确定他最晚什么时候可以离开。

Mecho 所在的森林是 $N\times N$ 的正方形网格，其两侧平行于南北和东西方向。每个格子由一棵树、一小块草、一个蜂巢或 Mecho 的家占据。如果两个格子中的一个与另一个的北、南、东或西相邻（但不在对角线上），则认为这两个格子相邻。Mecho 是一只笨拙的熊，所以每次它走一步，都只能移动至相邻的格子。Mecho 只能在草地上行走，不能穿过树木或蜂巢，而且他每分钟最多能走 $S$ 步。

当蜜蜂警报响起的那一刻， Mecho 在装有蜜罐的草格子里，而蜜蜂则在每个包含蜂巢的格子里（森林里可能有不止一个蜂巢）。接下来的每一分钟内，以下事件按顺序发生:

1. 如果 Mecho 还在吃蜂蜜，他会决定是继续吃还是离开。如果它继续吃东西，就会一动不动。否则，他会立即离开，并像上面描述的那样移动至多 $S$ 步。 Mecho 不能带任何蜂蜜，所以一旦他移动了，他就不能再吃蜂蜜了。

2. 当 Mecho 吃完或移动了整整一分钟后，蜜蜂在网格中进一步扩散了一个单位，只移动到草格子中。具体地，蜂群扩散到每一个与任何已经有蜜蜂的格子相邻的草格子。此外，一旦一个格子有蜜蜂，它将永远有蜜蜂（也就是说，蜂群不移动，但它生长）。

换句话说，蜜蜂的分布如下：当蜜蜂警报响起时，蜜蜂只占据蜂巢所在的格子。在第一分钟结束时，它们占据了蜂巢附近所有长满草的格子（以及原本的所有蜂巢）。在第二分钟结束时，它们又占据了和 “与蜂巢相邻的草格子” 相邻的草格子，以此类推。只要有足够的时间，这些蜜蜂就会同时占据森林中它们能到达的所有草格子。

Mecho 和蜜蜂都不能走出森林。另外，根据上面的规则，Mecho 总是吃整数分钟的蜂蜜。

如果 Mecho 发现自己在一个被蜜蜂占据的格子里，蜜蜂就会抓住 Mecho。

**任务**：编写一个程序，给定一张森林地图，计算出  Mecho 可以在最初的位置继续吃蜂蜜的最长时间，同时还能在任何蜜蜂抓到他之前回到他的家。

inputFormat:
第一行包含两个由空格隔开的整数 $N, S$，分别表示地图大小和 Mecho 每分钟最多移动的步数。

接下来 $N$ 行描述了森林地图。其中每一行包含 $N$ 个字符，每个字符表示一个格子。可能的字符及其含义如下:

- `T` 表示树。
- `G` 表示草格子。
- `M` 表示 Mecho 的初始位置，也是蜜罐的位置。这是一个草格子，蜜蜂可以进入。
- `D` 表示 Mecho 的家。Mecho 可以进入这个格子，但蜜蜂不可以。
- `H` 表示蜂巢。

**注意**：保证地图恰好包含一个字母 `M`，恰好一个字母 `D` 和至少一个字母 `H`。保证存在相邻的字母 `G` 形成的路径连接 Mecho 和它的家，以及相邻的字母 `G` 形成的路径连接蜜罐（即 Mecho 最初的位置）和至少一个蜂巢。这些序列可能长度为零，如 Mecho 的家或蜂巢和 Mecho 的初始位置相邻。另外，蜜蜂不能通过或飞过 Mecho 的家。对它们来说，Mecho 的家就像一棵树。

outputFormat:
输出一行一个整数，表示 Mecho 最多还能在初始位置吃多少分钟蜂蜜，并安全地回家。

如果 Mecho 不可能在蜜蜂抓住它之前回家，输出 $-1$。

samples:
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT

samples:
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
TGHHGGT

hint:
### 样例解释

- 样例 1：吃了一分钟蜂蜜后，Mecho 可以沿着最短的路径直接往右走，再过两分钟他就可以安全到家了。

- 样例 2：吃了两分钟蜂蜜后，Mecho 可以在第三分钟向右，向上，向右走；在第四分钟向右走三步；在第五分钟向下，向右走。

### 数据范围与约定

- 对于 $40\%$ 的数据，$N\leq 60$。
- 对于 $100\%$ 的数据，$1\leq N\leq 800$，$1\leq S\leq 1000$。

注意在实际评测中，部分分和以上描述有出入。


title: [春季测试 2023] 涂色游戏

description:
有一天，小 D 在刷朋友圈时看到了一段游戏视频。

这个游戏的名字叫涂色游戏，视频中的游戏界面是一个 $n$ 行 $m$ 列的网格，初始时每一个格子都是白色（用数字 $0$ 表示）。其中每一行的左侧、每一列的上方都有一把带颜色的刷子。玩家点击某个刷子后，这个刷子会将其右侧（或下方）的一整行（或一整列）涂上同一种颜色，**该行（或该列）格子原有的颜色都会被覆盖成新涂上的颜色。**

下图展示的情况可以通过先将第一列涂成红色，然后将第一行涂成蓝色得到，若此时选择将第三列涂成绿色，则图中绿色方框中的格子都会变成绿色。

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

小 D 想用他自己编写的程序来进行视频中的游戏。在编程的过程中，小 D 在涂色逻辑的实现上却遇到了一些困难，于是他向你求助，希望你能帮他完成实现涂色逻辑部分的代码。

首先，小 D 会给你网格的行数和列数 $n, m$，然后给出 $q$ 次操作，每次操作用三个整数 $opt_i, x_i, c_i$ 表示：

- 如果 $opt_i=0$，那么这次操作会将第 $x_i$ **行**涂成颜色 $c_i$。
- 如果 $opt_i=1$，那么这次操作会将第 $x_i$ **列**涂成颜色 $c_i$。

在所有涂色操作结束以后，你需要输出网格中每个位置的颜色是什么。

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

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

接下来一共 $T$ 组数据，每组数据格式如下：

第一行包含三个整数 $n, m, q$，分别表示涂色板的行数、列数，以及小 D 进行涂色操作的次数。

接下来 $q$ 行，每行包含三个整数 $opt_i, x_i, c_i$，表示一次操作。

outputFormat:
对于每组数据，输出 $n$ 行，每行 $m$ 个由单个空格隔开的整数。

其中第 $i$ 行第 $j$ 个整数表示涂色完成后网格中第 $i$ 行第 $j$ 列的方格是什么颜色。


title: [春季测试 2023] 幂次

description:
小 Ω 在小学数学课上学到了“幂次”的概念：$\forall a, b \in \N^+$，定义 $a^b$ 为 $b$ 个 $a$ 相乘。

她很好奇有多少正整数可以被表示为上述 $a^b$ 的形式？由于所有正整数 $m \in N^+$ 总是可以被表示为 $m^1$ 的形式，因此她要求上述的表示中，必须有 $b \geq k$，其中 $k$ 是她事先选取好的一个正整数。

因此她想知道在 $1$ 到 $n$ 中，有多少正整数 $x$ 可以被表示为 $x = a^b$ 的形式，其中 $a, b$ 都是正整数，且 $b \geq k$？

inputFormat: 第一行包含两个正整数 $n, k$，意义如上所述。

outputFormat: 输出一行包含一个非负整数表示对应的答案。


title: [春季测试 2023] 圣诞树

description:
众所周知，3202 年的圣诞节快要到了，因此小 Ω 买了一棵圣诞树和一根挂满了彩灯的电线，并打算把这根电线缠绕在圣诞树上。

圣诞树可以视作一个二维平面上有 $n$ 个顶点的**凸多边形**。这 $n$ 个顶点可以用于固定电线，且按**逆时针顺序**依次编号为 $1, \ldots, n$。其中第 $i$ 个顶点的坐标为 $(x_i, y_i)$，记其中 **$y$ 坐标最大**的顶点的编号为 $k$（若有多个满足条件的顶点，则取**编号最小**的）。不保证编号为 $1$ 的顶点的 $x$ 坐标最小。

下图左侧展示了一棵圣诞树的轮廓，其中 **$y$ 坐标最大**的顶点的编号为 $k = 5$。

![图 2：一棵圣诞树及一种可能的挂电线的方案](https://cdn.luogu.com.cn/upload/image_hosting/ayjegrhj.png)

小 Ω 希望用挂满了彩灯的电线装饰这棵圣诞树。出于美观性考虑，她希望这根电线**经过所有顶点恰好一次**；为了连接电源，这根电线需要**从 $(x_k, y_k)$ 出发**。形式化地，她需要决定一个 $1, \cdots, n$ 的**排列** $p_1, \cdots, p_n$，满足 $p_1 = k$，随后这根电线从 $(x_{p_1}, y_{p_1})$ 出发，依次经过 $(x_{p_2}, y_{p_2}), \cdots, (x_{p_n}, y_{p_n})$。此时，电线长度为 $\sum_{i=1}^{n-1}{\operatorname{d}((x_{p_i}, y_{p_i}), (x_{p_{i+1}}, y_{p_{i+1}}))}$。

- 其中 $\operatorname{d}$ 为平面上的**欧几里得距离**，即 $\operatorname{d}((x, y), (x', y')) = \sqrt{(x - x')^2 + (y - y')^2}$。

上图右侧展示了一种可能的方案，此时对应的排列为 $5, 4, 8, 6, 3, 9, 1, 7, 2$。

为了节省成本，她希望你能在所有可能的方案中，给出一种使电线长度**最短**的方案。如果使电线长度最短的方案不唯一，你只需要求出其中**任意**一种。

**考虑到浮点数产生的误差，你输出的方案与最优方案的线段长度的相对误差或绝对误差不超过 $10^{-10}$ 时即认为答案正确**。

inputFormat:
第一行包含一个正整数 $n$，表示圣诞树的顶点数。

接下来 $n$ 行，其中第 $i$ 行包含两个精确到小数点后 $9$ 位的实数 $x_i, y_i$ 表示编号为 $i$ 的顶点的坐标。

数据保证这 $n$ 个点**两两不同**，并且依次连接 $(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)$ 将形成一个**凸多边形**。

outputFormat: 输出一行包含 $n$ 个由单个空格隔开的正整数 $p_1, p_2, \cdots, p_n$，表示一个 $1, \cdots, n$ 的排列，满足 $p_1 = k$，且电线的长度 $\sum_{i=1}^{n-1}{\operatorname{d}((x_{p_i}, y_{p_i}), (x_{p_{i+1}}, y_{p_{i+1}}))}$ 在所有可能的方案中**最短**。如果这样的方案不唯一，请输出其中任意一种方案。


title: [春季测试 2023] 密码锁

description:
寒假过后，小 I 回到学校，发现自己忘记了自行车锁的密码，于是请你帮忙。

小 I 自行车上的密码锁有 $n$ 个拨圈，每个拨圈有 $k$（$k \leq 4$）格。密码锁上的每一格都包含一个正整数，其中第 $j$ 个拨圈的第 $i$ 格上的正整数为 $a _ {i, j}$。

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

（一个锁的例子，其中 $k = n = 3$，每列表示一个拨圈，拨圈的格子从上往下编号。）

你可以对每个拨圈拨若干次（也可以不拨），每拨一次拨圈，它的格子就会进行一次轮换。形式化地，拨第 $j$ 个拨圈一次，则会让第 $j$ 个拨圈上第 $i$ 格的数字移动到第 $((i \bmod k) + 1)$ 格，其他拨圈不动。

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

（一个拨动拨圈的例子，对左侧的锁拨一次第二个拨圈得到右侧的锁。）

为了方便记忆，小 I 设定密码时要求同一行上的数字尽可能靠近。
形式化地，对于 $1 \leq i \leq k$，定义密码锁第 $i$ 行的松散度为

$$
c(i) = \max \limits _ {j = 1} ^ n a _ {i, j} - \min \limits _ {j = 1} ^ n a _ {i, j}
$$

同时定义整个密码锁的松散度为

$$
C = \max \limits _ {1 \leq i \leq k} c(i)
$$

因为能开锁的状态满足 $C$ 尽可能小，因此小 I 希望你找出最小的 $C$ 值。

inputFormat:
**本题有多组测试数据，题目保证一个测试点中所有测试数据的 $k$ 相同。**

第一行包含两个正整数 $T, k$，分别表示测试数据组数和密码锁拨圈上的格数。

接下来一共 $T$ 组数据，每组数据格式如下：

第一行包含一个正整数 $n$，表示拨圈数。

接下来 $k$ 行，每行包含 $n$ 个正整数，其中第 $i$ 行第 $j$ 个整数 $a _ {i,j}$ 表示密码锁第 $j$ 个拨圈上第 $i$ 格对应的数字。

**注意输入的矩阵中每一列对应一个拨圈，而非每一行对应一个拨圈。**

outputFormat: 对于每组数据，输出一行包含一个整数，表示所有方案中 $C$ 的最小值。

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

samples:
见选手目录下的 lock/lock3.in。
见选手目录下的 lock/lock3.ans。

samples:
见选手目录下的 lock/lock4.in。
见选手目录下的 lock/lock4.ans。

samples:
见选手目录下的 lock/lock5.in。
见选手目录下的 lock/lock5.ans。


title: [USACO23FEB] Hungry Cow B

description:
Bessie is a hungry cow. Each day, for dinner, if there is a haybale in the barn, she will eat one haybale. Farmer John does not want Bessie to starve, so some days he sends a delivery of haybales, which arrive in the morning (before dinner). In particular, on day $d_i$, Farmer John sends a delivery of $b_i$ haybales $(1 \le d_i \le 10^{14}, 1 \le b_i \le 10^9)$.

Compute the total number of haybales Bessie will eat during the first $T$ days.

inputFormat:
The first line contains $N$ and $T$ $(1 \le N \le 10^5, 1 \le T \le 10^{14})$.

The next $N$ lines each contain $d_i$ and $b_i$. It is additionally guaranteed that $1 \le d_1<d_2<\cdots <d_N \le T$.

outputFormat:
Output the number of haybales that Bessie will eat during the first $T$ days.

Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

translation:
Bessie 喜欢吃干草。每一天晚上，如果她所在的谷仓里面还有至少一堆干草，Bessie 都会吃一堆当作晚饭。

一开始谷仓里面并没有任何干草，为了不让 Bessie 饿着，FJ 会时不时地给 Bessie 送干草。具体来说，他会在第 $d_i$ 天给 Bessie 送来 $b_i$ 堆干草，并总共送 $N$ 次。$(1 \leq N \leq 10^5,1 \leq d_i \leq 10^{14}, 1 \leq b_i \leq 10^9)$。

Bessie 想要知道在前 $T$ 天她一共能吃多少堆干草，请你帮助她算出这个数值。$(1 \leq T \leq 10^{14})$

请注意数据范围，可能需要使用 `long long` 来存储部分数据。

Translation by @南阳刘子骥

hint:
### Explanation for Sample 1

Two haybales arrive on the morning of day $1$. Bessie eats one haybale for dinner on day $1$ and another haybale on day $2$. On days $3 \cdots 5$, there are no more haybales for Bessie to eat. In total, Bessie eats $2$ haybales during the first $5$ days.

### Explanation for Sample 2

Two haybales arrive on the morning of day $1$. Bessie eats one haybale on days $1$ and $2$. There are no haybales for Bessie to eat on days $3$ and $4$. On the morning of day $5$, $10$ haybales arrive. Bessie eats one haybale for dinner on day $5$. In total, Bessie eats $3$ haybales during the first $5$ days.

### Explanation for Sample 3

10 haybales arrive on the morning of day $1$. Bessie eats one haybale on days $1 \cdots 4$. On the morning of day $5$, another $10$ haybales arrive, meaning there are $16$ haybales in the barn. For dinner on day $5$, Bessie eats another haybale. In total, Bessie eats $5$ haybales during the first $5$ days.

### SCORING

 - Inputs $4-7$: $T \le 10^5$
 - Inputs $8-13$: No additional constraints.


title: [USACO23FEB] Stamp Grid B

description:
A **stamp painting** is a black and white painting on an $N \times N$ canvas, where certain cells are inked while others are blank. It can be described by an $N \times N$ array of characters $(1 \le N \le 20)$. The $i$-th entry of the $j$-th column of the array is equal to `*` if the canvas contains ink at that square and `.` otherwise.

Bessie has a stamp painting that she would like to create, so Farmer John has lent her a single $K \times K(1 \le K \le N)$ stamp to do this and an empty $N \times N$ canvas. Bessie can repeatedly rotate the stamp clockwise by $90^{\circ}$ and stamp anywhere on the grid as long as the stamp is entirely inside the grid. Formally, to stamp, Bessie chooses integers $i,j$ such that $i \in [1,N−K+1]$ and $j \in [1,N−K+1]$; for each $(i^{\prime},j^{\prime})$ such that $1 \le i^{\prime},j^{\prime} \le K$, canvas cell $(i+i^{\prime}−1,j+j^{\prime}−1)$ is painted black if the stamp has ink at $(i^{\prime},j^{\prime})$. Bessie can rotate the stamp at any time between stampings. Once a canvas cell is painted black, it remains black.

Farmer John is wondering whether it's possible for Bessie to create her desired stamp painting with his stamp. For each of $T(1 \le T \le 100)$ test cases, help Farmer John answer this question.

inputFormat:
The first line of input contains $T$, the number of test cases.

Each test case starts with an integer $N$ followed by $N$ lines, each containing a string of `*`s and `.`s, representing Bessie's desired stamp painting. The next line contains $K$ and is followed by $K$ lines, each containing a string of `*`s and `.`s, representing Farmer John's stamp.

Consecutive test cases are separated by newlines.

outputFormat: For each test case, output `YES` or `NO` on separate lines.

translation:
邮票画是在 $N \times N$ 画布上的黑白画，其中某些单元被涂上墨水，而其他单元则是空白。它可以用一个 $N \times N$ 的字符数组来描述 $(1 \le N \le 20)$。如果画布在该方格含有墨水，则数组中第$i$行的第$j$列为 `*`，否则等于 `.`。

Bessie有一幅邮票画，她想创作，所以农夫John借给她一张 $K \times K(1 \le K \le N)$ 的邮票来做，还有一张空的 $N \times N$ 的帆布。Bessie可以重复地将邮票顺时针旋转$90^{\circ}$ 。并在网格上的任何地方涂墨，只要涂墨的地方完全在网格内。为了涂墨，Bessie选择整数 $i,j$ ，使 $i \in [1,N−K+1]$ and $j \in [1,N−K+1]$；对于每一个 $(i^{\prime},j^{\prime})$ 使 $1 \le i^{\prime},j^{\prime} \le K$。

Bessie可以在两次盖章之间的任何时候旋转印章。一旦邮票画被涂成黑色，它就一直是黑色的。

农民John想知道Bessie是否有可能用他的邮票创造出她想要的邮票画。对于 $T(1 \le T \le 100)$ 的每一个测试案例，帮助农夫John回答这个问题。

hint:
### Explanation for Sample 1

In the first test case, Bessie can perform the following sequence of stampings:

1. Stamp at $(1,1)$
2. Stamp at $(1,2)$
3. Stamp at $(2,1)$

In the second test case, Bessie can perform the following sequence of stampings:

1. Stamp at $(2,2)$
2. Stamp at $(2,1)$
3. Rotate $90^{\circ}$
4. Rotate $90^{\circ}$
5. Stamp at $(1,2)$

In the third test case, it is impossible to paint the middle cell.

In the fourth test case, Bessie can perform the following sequence of stampings:

1. Rotate $90^{\circ}$
2. Stamp at $(1,1)$
3. Stamp at $(1,2)$
4. Stamp at $(2,2)$


title: [USACO23FEB] Watching Mooloo B

description:
Bessie likes to watch shows on Mooloo. Because Bessie is a busy cow, she has planned a schedule for the next $N (1 \le N \le 10^5)$ days that she will watch Mooloo. Because Mooloo is a paid subscription service, she now needs to decide how to minimize the amount of money she needs to pay.

Mooloo has an interesting subscription system: it costs $d+K(1 \le K \le 10^9)$ moonies to subscribe to Mooloo for d consecutive days. You can start a subscription at any time, and you can start a new subscription as many times as you desire if your current subscription expires. Given this, figure out the minimum amount of moonies Bessie needs to pay to fulfill her schedule.

inputFormat:
The first line contains integers $N$ and $K$.

The second line contains $N$ integers describing the days Bessie will watch Mooloo: $1 \le d_1<d_2< \cdots <d_N \le 10^{14}$.

outputFormat: **Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).**

translation:
### 题目描述

贝茜喜欢看 Mooloo 的演出。因为她是一只忙碌的奶牛，她计划在接下来的 $N (1 \le N \le 10^5)$ 天去看演出。因为 Mooloo 提供了订阅服务，她想要使她花费的钱最少。

Mooloo 有一个有趣的订阅服务系统：若要在此之后的连续 $d$ 天看演出，则在订阅时需要花费 $d+K(1 \le K \le 10^9)$ 个单位价格。你可以随时订阅；若本次订阅已经过期，你可以根据需要订阅多次。基于以上条件，请计算出贝茜最少要花费多少个单位价格，才能完成她的计划。

### 输入格式

第一行输入两个正整数 $N$ 和 $K$。

第二行输入 $N$ 个正整数，表示在这些天里，贝茜会看 Mooloo 的演出：$1 \le d_1<d_2<\cdots<d_N \le 10^{14}$。

### 输出格式

**请注意，此问题中可能需要使用 64 位整数数据类型（如 C 或 C++ 中的 long long）。**

### 样例 #1 解释

贝茜在第 $7$ 天时，购买了 $3$ 天的订阅，共花费 $d+K=3+4=7$ 个单位价格。

### 样例 #2 解释

贝茜在第 $1$ 天时，购买了 $1$ 天的订阅，花费 $d+K=1+3=4$ 个单位价格；在第 $10$ 天时，也购买了 $1$ 天的订阅，花费 $d+K=1+3=4$ 个单位价格。贝茜一共花费了 $8$ 个单位价格。

translated by [liyuanchen2021](https://www.luogu.com.cn/user/557680)

hint:
### Explanation for Sample 1

Bessie buys a three-day subscription on day $7$, spending $d+K=3+4=7$ moonies.

### Explanation for Sample 2

Bessie first buys a one-day subscription on day $1$, spending $d+K=1+3=4$ moonies. Bessie also buys a one-day subscription on day $10$, spending $d+K=1+3=4$ moonies. In total, Bessie spends $8$ moonies.

### SCORING

 - Inputs $3-5$: $N \le 10$
 - Inputs $6-12$: No additional constraints.


title: [USACO23FEB] Bakery S

description:
Bessie has opened a bakery!

In her bakery, Bessie has an oven that can produce a cookie in $t_C$
 units of time or a muffin in $t_M$
 units of time $(1\le t_C,t_M\le 10^9)$. Due to space constraints, Bessie can only produce one pastry at a time, so to produce $A$ cookies and $B$ muffins, it takes $A \cdot t_C+B \cdot t_M$ units of time.

Bessie's $N (1\le N\le 100)$ friends would each like to visit the bakery one by one. The $i$-th friend will order $a_i(1 \le a_i \le 10^9)$ cookies and $b_i(1 \le b_i \le 10^9)$ muffins immediately upon entering. Bessie doesn't have space to store pastries, so she only starts making pastries upon receiving an order. Furthermore, Bessie's friends are very busy, so the $i$-th friend is only willing to wait $c_i(a_i+b_i \le c_i \le 2 \cdot 10^{18})$ units of time before getting sad and leaving.

Bessie really does not want her friends to be sad. With one mooney, she can upgrade her oven so that it takes one less unit of time to produce a cookie or one less unit of time to produce a muffin. She can't upgrade her oven a fractional amount of times, but she can choose to upgrade her oven as many times as she needs before her friends arrive, as long as the time needed to produce a cookie and to produce a muffin both remain strictly positive.

For each of $T(1 \le T \le 100)$ test cases, please help Bessie find out the minimum amount of moonies that Bessie must spend so that her bakery can satisfy all of her friends.

inputFormat:
The first line contains $T$, the number of test cases.

Each test case starts with one line containing $N$
, $t_C$, $t_M$. Then, the next $N$ lines each contain three integers $a_i,b_i,c_i$.

Consecutive test cases are separated by newlines.

outputFormat: The minimum amount of moonies that Bessie needs to spend for each test case, on separate lines.

translation:
## 题目描述

Bessie 开了一家面包店!

在她的面包店里，Bessie 有一个烤箱，可以在 $t_C$ 的时间内生产一块饼干或在 $t_M$ 单位时间内生产一块松糕。
$(1 \le t_C,t_M \le 10^9)$。由于空间限制，Bessie 一次只能生产一种糕点，所以要生产 $A$ 块饼干和 $B$ 块松饼，需要 $A\cdot t_C+B\cdot t_M$ 单位的时间。

Bessie的 $N (1\le N\le 100)$ 朋友都想一个一个地去面包店。第 $i$ 个朋友一进门就会点 $a_i(1 \le a_i \le 10^9)$ 块饼干和 $b_i(1 \le b_i \le 10^9)$ 块松饼。Bessie 没有空间来储存糕点，所以她只有在接到订单后才开始制作糕点。此外，Bessie 的朋友都很忙，所以第 $i$ 个朋友只愿意等 $c_i(a_i+b_i \le c_i \le 2 \cdot 10^{18})$ 个单位的时间，然后就伤心地离开。

Bessie 真的不希望她的朋友们伤心，她可以用一块钱升级她的烤箱，让它少花一个单位的时间来生产一块饼干或少花一个单位的时间来生产一个松饼。她不能将她的烤箱升级到花费小于等于 $0$ 的时间，但她可以选择在她的朋友到来之前将她的烤箱升级多少次，只要生产一块饼干和生产一个松饼所需的时间都严格保持为正数。

对于每一个 $T(1\le T\le 100)$ 的测试案例，请帮助 Bessie 找出她必须花费的最小的钱数量，以便她的面包店能够满足所有的朋友。

## 输入格式

第一行包含 $T$，测试案例的数量。

每个测试用例都以一行开始，包含 $N$
,$t_C$,$t_M$。然后，接下来的 $N$ 行各包含三个整数 $a_i,b_i,c_i$。

测试案例用换行符隔开。

## 输出格式

Bessie 需要为每个测试案例花费的最少钱数，每行一个。

## 样例 #1

### 样例输入 #1

```
2

3 7 9
4 3 18
2 4 19
1 1 6

5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22
```

### 样例输出 #1

```
11
6
```

## 提示

### 样例解释 1

在第一个测试案例中，贝西可以支付 $11$ 元来减少 $4$ 单位生产一块饼干所需的 时间和 $7$ 单位生产一块松饼所需的时间，从而使她的烤箱在 $3$ 单位的时间内生产饼干，在 $2$ 单位的时间内生产松饼。那么她可以在 $18$ 单位的时间内满足第一个朋友，在 $14$ 单位的时间内满足第二个朋友，在 $5$ 单位的时间内满足第三个朋友，所以他们都不会伤心而离开。

在第二个测试案例中，贝西应该把生产一块饼干的时间减少 $6$ 单位，把生产一块松饼的时间减少 $0$ 单位。

### 数据规模与约定

 - 输入 $2-4$：$N\le 10,t_C,t_M \le 1000$
 - 输入 $5-11$，没有额外的约束。

翻译 @ \_\_11jiang08\_\_

hint:
### Explanation for Sample 1

In the first test case, Bessie can pay $11$ moonies to decrease the time required to produce a cookie by $4$ and a muffin by $7$, so that her oven produces cookies in $3$ units of time and muffins in $2$ units of time. Then she can satisfy the first friend in $18$ units of time, the second friend in $14$ units of time, and the third friend in $5$ units of time, so none of them will get sad and leave.

In the second test case, Bessie should decrease the time required to produce a cookie by $6$ and a muffin by $0$.

### SCORING

 - Inputs $2-4$: $N \le 10,t_C,t_M \le 1000$
 - Inputs $5-11$: No additional constraints.


title: [USACO23FEB] Cow-libi S

description:
**Note: The time limit for this problem is 4s, two times the default.**

Somebody has been grazing in Farmer John's $G(1 \le G \le 10^5)$ private gardens! Using his expert forensic knowledge, FJ has been able to determine the precise time each garden was grazed. He has also determined that there was a single cow that was responsible for every grazing incident.

In response to these crimes each of FJ's $N(1 \le N \le 10^5)$ cows have provided an alibi that proves the cow was in a specific location at a specific time. Help FJ test whether each of these alibis demonstrates the cow's innocence.

A cow can be determined to be innocent if it is impossible for her to have travelled between all of the grazings and her alibi. Cows travel at a rate of $1$ unit distance per unit time.

inputFormat:
The first line of input will contain $G$ and $N$ separated by a space.

The next $G$ lines contain the integers $x, y$, and $t (−10^9 \le x,y \le 10^9;0 \le t \le 10^9)$

separated by a space describing the location and time of the grazing. It will always be possible for a single cow to travel between all grazings.

The next $N$ lines contain $x$, $y$, and $t(−10^9 \le x,y \le 10^9;0 \le t \le 10^9)$ separated by a space describing the location and time of each cow's alibi.

outputFormat: Output a single integer: the number of cows with alibis that prove their innocence.

translation:
有人在农夫约翰的 $G(1 \le G \le 10^5)$ 个私人花园里放牧！约翰利用他的专业法医知识，已经能够确定每个花园被放牧的确切时间。他还确定有一头牛负责了每一次放牧事件。

作为对这些犯罪行为的回应，约翰的 $N(1 \le N \le 10^5)$ 头奶牛都提供了一个证明牛在特定时间处于特定位置的不在场证明。帮助约翰测试每个不在场证明是否证明了牛的清白。

如果一头牛不可能在所有放牧地点和她的不在场证明之间旅行，那么她就可以被确定为清白。牛的行进速度为每单位时间 $1$ 个单位距离。

**输入格式（输入从终端/标准输入中获取）：**

输入的第一行将包含用空格分隔的 $G$ 和 $N$。

接下来的 $G$ 行包含用空格分隔的整数 $x$，$y$ 和 $t\ (-10^9 \le x, y \le 10^9;\ 0 \le t \le  10^9)$，描述放牧的位置和时间。一头牛始终可以在所有放牧地点之间旅行。

接下来的 $N$ 行包含用空格分隔的整数 $x$，$y$ 和 $t\ (-10^9 \le x, y \le 10^9;\ 0 \le t \le  10^9)$，描述每头牛的不在场证明的位置和时间。

**输出格式（将输出打印到终端/标准输出）：**

输出一个整数：证明了其清白的具有不在场证明的牛的数量。

**说明提示：**

有两次放牧；第一次在 $(0,0)$ 的时间是 $100$，第二次在 $(50,0)$ 的时间是 $200$。

第一头牛的不在场证明不能证明她的清白。她只有足够的时间到达第一次放牧地点。

第二头牛的不在场证明证明了她的清白。她离任何放牧地点都很远。

不幸的是，对于第三头牛，身处犯罪现场并不能证明清白。

最后，第四头牛是清白的，因为从她的不在场证明到最后的放牧地点是不可能的。

**数据范围**

- 输入 $2 \sim 4$：$1 ≤ G, N ≤ 10^3$。此外，对于农场和不在场证明，$-10^6 ≤ x,y ≤ 10^6$ 和 $0 ≤ t ≤ 10^6$。

- 输入 $5 \sim 11$：没有额外的约束条件。

hint:
### Explanation for Sample 1

There were two grazings; the first at $(0,0)$ at time 100 and the second at $(50,0)$ at time $200$.

The first cow's alibi does not prove her innocence. She has just enough time to arrive at the first grazing.

The second cow's alibi does prove her innocence. She is nowhere near any of the grazings.

Unfortunately for the third cow, being at the scene of the crime does not prove innocence.

Finally, the fourth cow is innocent because it's impossible to make it from her alibi to the final grazing in time.

### SCORING

 - Inputs $2-4$: $1 \le G,N \le 10^3$. Also, for both the fields and alibis, $−10^6 \le x,y \le 10^6$ and $0 \le t \le 10^6$.
 - Inputs $5-11$: No additional constraints.


title: [USACO23FEB] Moo Route II S

description:
**Note: The time limit for this problem is 4s, twice the default.**

Bessie is on vacation! Due to some recent technological advances, Bessie will travel via technologically sophisticated flights, which can even time travel. Furthermore, there are no issues if two "parallel" versions of Bessie ever meet.

In the country there are $N$ airports numbered $1,2,\cdots ,N$ and $M$ time-traveling flights $(1 \le N,M \le 200000)$. Flight $j$ leaves airport $c_j$ at time $r_j$, and arrives in airport $d_j$ at time $s_j (0 \le rj,sj \le 10^9$, $s_j<r_j$ is possible$)$. In addition, she must leave $a_i$ time for a layover at airport $i (1 \le a_i \le 10^9)$. (That is to say, if Bessie takes a flight arriving in airport $i$ at time $s$, she can then transfer to a flight leaving the airport at time $r$ if $r \ge s+a_i$. The layovers do not affect when Bessie arrives at an airport.)

Bessie starts at city $1$ at time $0$. For each airport from $1$ to $N$, what is the earliest time when Bessie can get to at it?

inputFormat:
The first line of input contains $N$ and $M$.

The next $M$ lines describe flights. The $j$-th of these lines contains $c_j, r_j, d_j, s_j$ in that order. $(1 \le c_j,d_j \le N, 0 \le r_j,s_j \le 10^9)$

The next line describes airports. It contains $N$
space separated integers, $a_1, \cdots ,a_N$.

outputFormat: There are $N$ lines of output. Line $i$ contains the earliest time when Bessie can get to airport $i$, or $-1$ if it is not possible for Bessie to get to that airport.

translation:
### 题意

Bessie 正在旅游！有 $n$ 个城市和 $m$ 条航线，第 $i$ 条航线有 $(c_i,r_i,d_i,s_i)(1\leq c_i, d_i\leq n,0\leq r_i,s_i\leq 10^9)$ 的限制，表示从 $c_i$ 到 $d_i$，最迟 $r_i$ 时进入，$s_i$ 时到达，注意 $r_i$ 可能大于 $s_i$。第 $i$ 个城市有 $a_i$ 的停泊时间，表示 **乘坐航班到达** $i$ 后，需要等待 $a_i$ 的时间后才能继续飞行。问到达每个城市的最早时间？如果不能到达，输出 `-1`。

Bessie $0$ 时刻在 $1$ 城市。

### 输入格式

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

接下来 $m$ 行每行四个整数 $c_i,r_i,d_i,s_i$。

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

### 输出格式

$n$ 行，第 $i$ 行一个整数表示到达 $i$ 的最早时间，不能到达输出 `-1`。

hint:
### Explanation for Sample 1

Bessie can take the $3$ flights in the listed order, which allows her to arrive at airports $1$ and $2$ at time $0$, and airport $3$ at time $20$.

Note that this route passes through airport $2$ twice, first from time $10-11$ and then from time $0-1$.

### Explanation for Sample 2

In this case, Bessie can take flight $1$, arriving at airport $2$ at time $10$. However, she does not arrive in time to also take flight $2$, since the departure time is $10$ and she cannot make a $1$ time-unit layover.

### SCORING

 - Inputs $3-5$: $r_j<s_j$ for all $j$
, i.e. all flights arrive after they depart.
 - Inputs $6-10$: $N,M \le 5000$
 - Inputs $11-20$: No additional constraints.


title: [USACO23FEB] Equal Sum Subarrays G

description:
**Note: The time limit for this problem is 3s, 1.5x the default.**

FJ gave Bessie an array $a$ of length $N(2 \le N \le 500,−10^{15} \le a_i \le 10^{15})$ with all $\dfrac{N(N+1)}{2}$ contiguous subarray sums distinct. For each index $i \in [1,N]$, help Bessie compute the minimum amount it suffices to change ai by so that there are two different contiguous subarrays of a with equal sum.

inputFormat:
The first line contains $N$.

The next line contains $a_1, \cdots ,a_N$
(the elements of $a$, in order).

outputFormat: One line for each index $i \in [1,N]$.

translation:
### 题目描述

**提示：本题的时间限制是3s，为默认值的1.5倍。**

FJ给了Bessie一个长度为 $N(2\leq N\leq 500, -10^{15}\leq a_i \leq 10^{15})$ 的数组，且数组所有的 $\frac{N(N+1)}{2}$ 个区间和互不相同。对于每个 $i\in[1,N]$，帮助Bessie把 $a_i$ 改成一个值，使得数组有两个区间和相等，且改值与 $a_i$ 的差值最小。

### 输入格式

第一行输入 $N$。

第二行输入数组 $a$。

### 输出格式
对于每个 $i\in[1,N]$，每行输出满足题意的最小差值。

### 说明/提示

样例1：把 $a_1$减 $2$ 使得 $a_1+a_2=a_2$。类似的，把 $a_2$加 $3$ 使得 $a_1+a_2=a_1$。

样例2：把 $a_1$ 加 $1$ 或把 $a_3$ 减 $1$ 使得 $a_1=a_3$。把 $a_2$ 加 $6$ 使得 $a_1=a_1+a_2+a_3$。

数据范围

输入 $3$：$N\leq 40$

输入 $4$：$N\leq 80$

输入 $5-7$：$N\leq 200$

输入 $8-16$：没有额外限制。

hint:
### Explanation for Sample 1

Decreasing $a_1$ by $2$ would result in $a_1+a_2=a_2$. Similarly, increasing $a_2$ by $3$ would result in $a_1+a_2=a_1$.

### Explanation for Sample 2

Increasing a1 or decreasing $a_3$ by $1$ would result in $a_1=a_3$. Increasing $a_2$ by $6$ would result in $a_1=a_1+a_2+a_3$.

### SCORING

 - Input $3$: $N \le 40$
 - Input $4$: $N \le 80$
 - Inputs $5-7$: $N \le 200$
 - Inputs 8-16: No additional constraints.


title: [USACO23FEB] Fertilizing Pastures G

description:
There are $N$ pastures $(2 \le N \le 2 \cdot 10^5)$, connected by $N−1$ roads, such that they form a tree. Every road takes $1$ second to cross. Each pasture starts out with $0$ grass, and the ith pasture's grass grows at a rate of $a_i (1 \le a_i \le 10^8)$ units per second. Farmer John is in pasture $1$ at the start, and needs to drive around and fertilize the grass in every pasture. If he visits a pasture with $x$ units of grass, it will need $x$ amount of fertilizer. A pasture only needs to be fertilized the first time it is visited, and fertilizing a pasture takes $0$ time.

The input contains an additional parameter $T \in \{0,1\}$.

 - If $T=0$, Farmer John must end at pasture $1$.
 - If $T=1$, Farmer John may end at any pasture.

Compute the minimum amount of time it will take to fertilize every pasture and the minimum amount of fertilizer needed to finish in that amount of time.

inputFormat:
The first line contains $N$ and $T$.

Then for each $i$ from $2$ to $N$, there is a line containing $p_i$ and $a_i$, meaning that there is a road connecting pastures $p_i$ and $i$. It is guaranteed that $1 \le p_i<i$.

outputFormat: The minimum amount of time and the minimum amount of fertilizer, separated by spaces.

translation:
### 题目描述

有 $N$ 个顶点的树，经过节点之间的每一条边都需要 $1s$。每个顶点一开始的权值均为 $0$，第 $i$ 个点的权值的增长速率为 $a_i/s$。FJ 从 $1$ 号顶点出发遍历整棵树。当 FJ 走到某个节点时，若该节点的权值为 $x$，则需要支出大小为 $x$ 的费用。（当然，只需在第一次经过该节点时需要支出。）

给出一个参数 $T$:

+ **若 $T=0$，FJ 必须回到 $1$ 号节点**。

+ **若 $T=1$，FJ 可以在任意节点结束他的遍历**。

求遍历所有节点的最小时间和此时需要付出的最小的费用。

### 输入格式

第一行包括 $N$ 和 $T$。

第 $2$ 行到第 $N$ 行，包含两个整数 $p_i$ 和 $a_i$,$a_i$ 的含义见上文。$p_i$ 则表示节点 $i$ 和 $p_i$ 之间有一条边相连。

### 输出格式
两个整数：遍历所有节点的最小时间和此时需要付出的最小的费用。

$2 \le N \le 2 \times 10^5,T \in \{0,1\},1 \le a_i \le 10^8, 1 \le p_i < i$。

hint:
### Explanation for Sample 1

The optimal route for Farmer John is as follows:

 - At time $1$, move to node $3$, which now has $1 \cdot 2=2$ grass and so needs $2$ fertilizer.
 - At time $2$, move to node $5$, which now has $2 \cdot 4=8$ grass and so needs $8$ fertilizer.
 - At time $3$, move back to node $3$, which we already fertilized and so don't need to fertilize again.
 - At time $4$, move to node $4$, which now has $4 \cdot 1=4$ grass and so needs $4$ fertilizer.
 - At time $5$, move back to node $3$, which we already fertilized.
 - At time $6$, move back to node $1$.
 - At time $7$, move to node $2$, which now has $7 \cdot 1=7$ grass and so needs $7$ fertilizer.
 - At time $8$, return to node $1$.

This route takes $8$ time and uses $2+8+4+7=21$ fertilizer. It can be shown that $8$ is the least possible amount of time for any route that returns to node $1$ at the end and $21$ is the least possible fertilizer used for any route that returns to node $1$ and takes $8$ time.

### Explanation for Sample 2

The optimal route for Farmer John is as follows:

 - At time $1$, move to node $2$, which now has $1 \cdot 1=1$ grass and so needs $1$ fertilizer.
 - At time $2$, move back to node $1$.
 - At time $3$, move to node $3$, which now has $3 \cdot 2=6$ grass and so needs $6$ fertilizer.
 - At time $4$, move to node $5$, which now has $4 \cdot 4=16$ grass and so needs $16$ fertilizer.
 - At time $5$, move back to node $3$, which we already fertilized and so don't need to fertilize again.
 - At time $6$, move to node $4$, which now has $6 \cdot 1=6$ grass and so needs $6$ fertilizer.

This route takes $6$ time and uses $1+6+16+6=29$ fertilizer. It can be shown that $6$ is the least possible amount of time for any route and $29$ is the least possible fertilizer used for any route that takes $6$ time.

### SCORING

 - Inputs $3-10$: $T=0$
 - Inputs $11-22$: $T=1$
 - Inputs $3-6$ and $11-14$: No pasture is adjacent to more than three roads.


title: [USACO23FEB] Piling Papers G

description:
Farmer John wrote down $N (1 \le N \le 300)$ digits on pieces of paper. For each $i \in [1,N]$, the ith piece of paper contains digit $a_i (1 \le a_i \le 9)$.

The cows have two favorite integers $A$ and $B(1 \le A \le B<10^{18})$, and would like you to answer $Q (1 \le Q \le 5⋅10^4)$ queries. For the $i$-th query, the cows will move left to right across papers $l_i \cdots r_i (1 \le l_i \le r_i \le N)$, maintaining an initially empty pile of papers. For each paper, they will either add it to the top of the pile, to the bottom of the pile, or neither. In the end, they will read the papers in the pile from top to bottom, forming an integer. Over all $3 ^ {r_i−l_i+1}$ ways for the cows to make choices during this process, count the number of ways that result in the cows reading an integer in $[A,B]$ inclusive, and output this number modulo $10^9+7$.

inputFormat:
The first line contains three space-separated integers $N, A$, and $B$.

The second line contains $N$ space-separated digits $a_1,a_2, \cdots ,a_N$.

The third line contains an integer $Q$, the number of queries.

The next $Q$ lines each contain two space-separated integers $l_i$ and $r_i$.

outputFormat: For each query, a single line containing the answer.

translation: 给定长度为 $n(1\leq n\leq 300)$ 的整数序列 $a(1\leq a_i\leq 9)$，和整数区间 $[A,B](1\leq A\leq B\leq 10^{18})$，有 $q$ 次询问，每次询问给出 $l,r$。每次询问开始，你有一个空串 $x$，你可以正序对 $a_{l\sim r}$ 进行操作，操作有三种：$x\rightarrow\overline{x+a_i}$，$x\rightarrow\overline{a_i+x}$，或者什么也不做，求 $\overline{x}$ 的取值在 $[A,B]$ 的不同的操作方案数，对 $10^9+7$ 取模。

hint:
### Explanation for Sample 1

For the first query, there are nine ways Bessie can stack papers when reading the interval $[1,2]$:

 - Bessie can ignore $1$ then ignore $2$, getting $0$.
 - Bessie can ignore $1$ then add $2$ to the top of the stack, getting $2$.
 - Bessie can ignore $1$ then add $2$ to the bottom of the stack, getting $2$.
 - Bessie can add $1$ to the top of the stack then ignore $2$, getting $1$.
 - Bessie can add $1$ to the top of the stack then add $2$ to the top of the stack, getting $21$.
 - Bessie can add $1$ to the top of the stack then add $2$ to the bottom of the stack, getting $12$.
 - Bessie can add $1$ to the bottom of the stack then ignore $2$, getting $1$.
 - Bessie can add $1$ to the bottom of the stack then add $2$ to the top of the stack, getting $21$.
 - Bessie can add $1$ to the bottom of the stack then add $2$ to the bottom of the stack, getting $12$.

Only the $2$ ways that give $21$ yield a number between $13$ and $327$, so the answer is $2$.

### SCORING

 - Inputs $2-3$: $B<100$
 - Inputs $4-5$: $A=B$
 - Inputs $6-13$: No additional constraints.


title: [USACO23FEB] Hungry Cow P

description:
**Note: The time limit for this problem is 6s, three times the default. The memory limit for this problem is 512MB, twice the default.**

Bessie is a hungry cow. Each day, for dinner, if there is a haybale in the barn, she will eat one haybale. Farmer John does not want Bessie to starve, so some days he sends a delivery of haybales, which arrive in the morning (before dinner). In particular, on day $d_i$, Farmer John sends a delivery of $b_i$ haybales $(1 \le d_i \le 10^{14}, 0 \le b_i \le 10^9)$.

Process $U(1 \le U \le 10^5)$ updates as follows: Given a pair $(d,b)$, update the number of haybales arriving on day $d$ to $b$. After each update, output the sum of all days on which Bessie eats haybales modulo $10^9+7$.

inputFormat: $U$, followed by $U$ lines containing the updates.

outputFormat: The sum after each update modulo $10^9+7$.

translation:
Bessie 很饿，每天晚饭如果有干草就会吃 $1$ 份，没有就不吃，初始没有干草。

每天早上 Farmer John 会给它送若干干草，设第 $k$ 天送 $a_k$ 份干草，初始时 $a_k=0$，表示该天不送干草。

$q$ 次操作，每次给出 $x,y$，表示将 $a_x$ 改成 $y$，请将在此时 Bessie 有干草吃的**日期编号**求和并输出。对 $10^9+7$ 取模。

操作间互不独立。

$1\le q\le10^5$，$1\le x\le10^{14}$，$0\le y\le10^9$。

hint:
### Explanation for Sample 1

Answers after each update:

$4+5+6=15$
$1+2+3+4+5+6+7+8=36$
$1+2+4+5+6=18$

### SCORING

 - Input $3$: $U \le 5000$
 - Inputs $4-10$: Updates only increase the number of haybales arriving on day $d$.
 - Inputs 11-22: No additional constraints.


title: [USACO23FEB] Problem Setting P

description:
**Note: The memory limit for this problem is 512MB, twice the default.**

Farmer John created $N(1 \le N \le 10^5)$ problems. He then recruited $M (1 \le M \le 20)$ test-solvers, each of which rated every problem as "easy" or "hard."

His goal is now to create a problemset arranged in increasing order of difficulty, consisting of some subset of his $N$ problems arranged in some order. There must exist no pair of problems such that some test-solver thinks the problem later in the order is easy but the problem earlier in the order is hard.

Count the number of distinct nonempty problemsets he can form, modulo $10^9+7$.

inputFormat:
The first line contains $N$ and $M$.

The next $M$ lines each contain a string of length $N$. The $i$-th character of this string is `E` if the test-solver thinks the ith problem is easy, or `H` otherwise.

outputFormat: The number of distinct problemsets FJ can form, modulo $10^9+7$.

translation:
Farmer John 出了 $n$ 道题，聘了 $m$ 个验题人来品鉴难度。

难度只有简单（`E`）和困难（`H`）两种。

Farmer John 将从中选出若干道（**至少一道**），并以一定顺序排列，使得前一道题目中任意一个觉得此题困难的验题人也觉得后面一道题目困难。

回答有多少种选出来并排列的方案，对 $10^9+7$ 取模。

$1\le n\le10^5$，$1\le m\le20$。

samples:
10 6
EHEEEHHEEH
EHHHEEHHHE
EHEHEHEEHH
HEHEEEHEEE
HHEEHEEEHE
EHHEEEEEHE

hint:
### Explanation for Sample 1

The nine possible problemsets are as follows:

$[1]$
$[1,2]$
$[1,3]$
$[1,3,2]$
$[2]$
$[3]$
$[3,1]$
$[3,2]$
$[3,1,2]$

Note that the order of the problems within the problemset matters.

### SCORING

 - Inputs $3-4$: $M=1$
 - Inputs $5-14$: $M \le 16$
 - Inputs $15-22$: No additional constraints.


title: [USACO23FEB] Watching Cowflix P

description:
**Note: The time limit for this problem is 3s, 1.5x the default.**

Bessie likes to watch shows on Cowflix, and she watches them in different places. Farmer John's farm can be represented as a tree with $N(2 \le N \le 2 \cdot 10^5)$ nodes, and for each node, either Bessie watches Cowflix there or she doesn't. It is guaranteed that Bessie watches Cowflix in at least one node.

Unfortunately, Cowflix is introducing a new subscription model to combat password sharing. In their new model, you can choose a connected component of size $d$ in the farm, and then you need to pay $d+k$ moonies for an account that you can use in that connected component. Formally, you need to choose a set of disjoint connected components $c_1,c_2, \cdots ,c_C$ so that every node where Bessie watches Cowflix must be contained within some $c_i$. The cost of the set of components is $\sum\limits^{C}_{i=1}(|c_i|+k)$, where $|c_i|$ is the number of nodes in component $c_i$. Nodes where Bessie does not watch Cowflix do not have to be in any $c_i$.

Bessie is worried that the new subscription model may be too expensive for her given all the places she visits and is thinking of switching to Mooloo. To aid her decision-making, calculate the minimum amount she would need to pay to Cowflix to maintain her viewing habits. Because Cowflix has not announced the value of $k$, calculate it for all integer values of $k$ from $1$ to $N$.

inputFormat:
The first line contains $N$.

The second line contains a bit string $s_1s_2s_3\cdots s_N$ where $s_i=1$ if Bessie watches Cowflix at node $i$.

Then $N - 1$ lines follow, each containing two integers $a$ and $b (1 \le a,b \le N)$, which denotes an edge between $a$ and $b$ in the tree.

outputFormat: The answers for each $k$ from $1$ to $N$ on separate lines.

translation:
Bessie 喜欢在 Cowflix 上看节目，并且喜欢在农场里的不同地方看。

Farmer John 的农场可以被描述成一颗 $n$ 个节点的树，并且 Bessie 只可能在树上的一些指定的节点处看节目。每个节点是否要看节目将在初始时给定；保证至少在一个节点处会看节目。

不幸的是，Cowflix 为了避免奶牛们使用公用账号，采取了一个新的会员策略：
* Bessie 将多次付款，每次选择树上任意一个大小为 $d$ 的**连通块**，为其支付 $d+k$ 的代价，才能够在这些位置看节目。

换言之，Bessie 将选取若干**连通块** $c_1,c_2,\dots,c_C$，支付 $\sum_{i=1}^C(|c_i|+k)$ 的代价，才可以在这些连通块的各个节点处看节目；即，**被指定的节点必须被某个连通块包含，不被指定的节点不必被包含**。

Bessie 觉得这个策略的代价太昂贵了，考虑是否要改在 Mooloo 上看节目。为了帮助其决策，你应当告诉之 $k$ 取遍 $1\sim n$ 时看节目的最小总代价。

$1\le n\le2\times10^5$。

hint:
### Explanation for Sample 1

For $k \le 3$, it's optimal to have two accounts: $c_1=\{1\},c_2=\{5\}$. For $k \ge 3$, it's optimal to have one account: $c_1=\{1,2,3,4,5\}$.

### SCORING

 - Inputs $3-5$: $N \le 5000$
 - Inputs $6-8$: $i$ is connected to $i+1$ for all $i \in [1,N)$.
 - Inputs $9-19$: $N \le 10^5$
 - Inputs $20-24$: No additional constraints.


title: [语言月赛202303] String Problem P

description:
Farmer John 有 $n$ 个字符串，第 $i$ 个字符串为 $s_i$。

现在，你需要支持如下 $q$ 次操作：

- `1 x y i`：把字符串 $s_x$ 整体插入到字符串 $s_y$ 的第 $i$ 个字符后，更新 $s_y$。
- `2 y`：求 $s_y$。

例如，设 $s_1 = \texttt{abc}$，$s_2 = \texttt{xyz}$，则执行完 `1 2 1 2` 后（把 $s_2$ 整体插入到 $s_1$ 的第 $2$ 个字符后，更新 $s_1$），$s_1 = \texttt{abxyzc}$，$s_2 = \texttt{xyz}$。

inputFormat:
第一行是两个整数，表示字符串数量 $n$ 和操作的数量 $q$。
接下来 $n$ 行，每行一个字符串，第 $i$ 行的字符串为 $s_i$。
接下来 $q$ 行，每行四个或二个整数，依次表示每次操作。具体格式见『题目描述』。

outputFormat: 对每次操作 $2$，输出一行一个字符串，表示被询问的串。

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

- 对 $60\%$ 的数据，保证 $i = |s_y|$。
- 对 $100\%$ 的数据，$1 \leq n,q \leq 10$，$1 \leq |s_i| \leq 10$。$1 \leq x, y \leq n$，$1 \leq i \leq |s_y|$。

其中 $|s_y|$ 表示进行对应操作时 $s_y$ 的长度，$|s_i|$ 表示输入时字符串的长度。

provider：一扶苏一


title: 「PEOI Rd1」Morning or Afternoon

description:
有一个可用转盘显示日期的指针闹钟，我从一个时刻观测到了另一个时刻（闭区间），现在我想知道我是否一定可以通过判断这期间日期的变化情况来推断出现在是上午还是下午。

闹钟在上午 $12:00$ 准时更新日期。

上午/下午 $11:59$ 后的时刻为 下午/上午 $12:00$，上午/下午 $12:59$ 后的时刻为 上午/下午 $1:00$。

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

接下来 $T$ 行每行两个时刻以空格隔开，表示起始观测和终止观测的时刻。注意观测时间区间是闭区间。

时刻以 $\texttt{(a)b:cd}$ 的形式给出，其中 $\overline\texttt{ab}$ 表示小时数，$\overline\texttt{cd}$ 表示分钟数。如果 $\tt a$ 位不省略，那么 ${\tt a}\not=0$。保证 $\overline\texttt{ab}\in[1,12]$，$\overline\texttt{cd}\in[0,59]$。

outputFormat: 对于每组数据输出一行，如果一定可以判断，输出 `Yes`，否则输出 `No`。

hint:
### 样例解释#1
因为我从 $11:30$ 看到了 $12:20$（假设 $12:20$ 是第一次观测到；后面的 $12:20$ 的上下午情况可以根据现在的情况推出，因为我知道右端点的 $12:20$ 是第几次观测到），我可以通过判断这期间日期有没有变化来判断这个时刻是上午还是下午。比如，我看到这段时间里闹钟更新了日期，那么 $12:20$ 一定是上午；反之 $12:20$ 一定是下午。

样例#3 同理。
### 样例解释#2
有可能是上午 $12:20$ 到上午 $5:00$，也有可能是下午 $12:20$ 到下午 $5:00$，这两种情况日期都不可能发生改变，所以我无法判断。

### 数据范围
对于 $18\%$ 分数的数据，所有时刻保证不会出现 小时数 $=12$ 的情况（即不会出现 `12:25` 类型的时刻）。

对于另外 $9\%$ 分数的数据有 $T=1$。$\color{#fff}\sout\text{不可以，总司令！}$

对于 $100\%$ 的数据 $T\leqslant 100$，$\overline\texttt{ab}\in[1,12]$，$\overline\texttt{cd}\in[0,59]$。


title: 「FAOI-R2」Program of atom(x) 2027 (D)

background:
这是来自 $2027$ 年的 FAOI 的一道题目，是一道带有 SPJ 的传统题。

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

自从 [krjt](https://www.luogu.com.cn/user/691537) 上次被 $160$ 人 [JC](https://www.luogu.com.cn/problem/T269289) 后，他换了一个「量子密码锁」，并用它锁上了自己的电脑包——打不开密码锁，就取不出包里的电脑。理论上，一旦 krjt 忘了密码，就连造这把锁的人也打不开。

然而，这把锁并非固若金汤。~~有一天，krjt 突然对化学产生了浓厚的兴趣。他拿起那把锁，放在酒精灯上加热，结果发现：~~ 在高温环境下，这把锁内的原子（严格来说是「离子」，下同）排布变得不稳定，这将导致它瘫痪。

description:
krjt 找来了密码锁的说明书：

> 在密码锁中，有一条长度为 $n$（不能更改，$n$ 的具体取值见密码锁铭牌）的链，链上共有 $n$ 个结点。每个结点上可以存放至多一个原子。初始时，$1,2,\ldots,n$ 号原子以某个顺序（可以由用户自行调整）被存放在其中，每个结点存放一个原子。
>
> 定义 $i$ 号原子的电荷量为 $i!=1 \times 2\times 3 \times \ldots \times i$。
>
> 现有一个计时器 $b$（单位为秒），其初值为 $0$。
>
> 密码锁被加热后，以下事件**依次循环发生**，直至达成终止条件：
>
> 1. 位于链两端的原子被移除（**这不会使链变短**），**不再对后续事件产生影响**；
> 2. 判定终止条件：
>    - 若此时链中剩下**不多于 $1$ 个**原子（**也可以是 $0$ 个**），则**达成终止条件**，密码锁瘫痪（**此时计时器 $b$ 的值不会增加 $1$**）；
>    - 否则，将计时器 $b$ 的值增加 $1$。
> 3. 给每个原子标定运动方向（**标定的运动方向是临时的，只生效一次，在下一次标定前会被重置**）：
>    - 计算它左边所有原子的电荷量之和，设计算结果为 $x$；
>    - 计算它右边所有原子的电荷量之和，设计算结果为 $y$；
>    - 如果 $x<y$，则标定方向为「向左」；
>    - 如果 $x>y$，则标定方向为「向右」；
>    - 可以证明，$x \ne y$。
> 4. 所有原子按照所标定的运动方向，移动一条边的距离，来到相邻的结点。

此外，krjt 从铭牌上读取到了 $n$ 的值。

krjt 定义，密码锁的瘫痪用时，为它瘫痪时 $b$ 的值。当然，krjt 希望密码锁尽量安全，因此他想**最大化密码锁的瘫痪用时**。

~~为了不让更多人再次 JC krjt~~，请问：他该如何排列密码锁中 $n$ 个原子的初始顺序？

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

outputFormat:
一行 $n$ 个正整数，一个 $1 \sim n$ 的排列，表示你给 krjt 规划的排列方案：从左到右（或者从右到左，可以证明它们的瘫痪用时相等）依次输出 $n$ 个原子的编号。

**答案可能有多个，输出一个即可。**

hint:
**样例解释：**

$6$ 个样例的瘫痪用时分别为 $0,0,0,1,1,2$ 秒。

实际上，枚举可知：当 $n \le 6$ 时，输出任何一个 $1 \sim n$ 的排列都能 AC。

下面对样例 $6$ 进行模拟。在链的描述中：

- $0$ 表示该结点为空；
- $i$ 表示该结点上存放着 $i$ 号原子；
- $(x,y)$ 为计算结果。

1. **初始的链**为 $\color{blue}2-4-5-1-6-3$；
2. $b$ 初始为 $0$；
3. **位于两端的原子被移除**，链变为 $\color{blue}0-4-5-1-6-0$；
4. $b$ 增加至 $1$；
5. **计算**，$4$ 个原子（从左向右）的结果分别为 $(\color{red}0\color{black},841),(\color{red}24\color{black},721),(\color{red}144\color{black},720),(145,\color{red}0\color{black})$；
6. 根据结果，左边 $3$ 个原子（$4,5,1$）**向左运动**，最右边的原子（$6$）**向右运动**，链变为 $\color{blue}4-5-1-0-0-6$；
7. **位于两端的原子被移除**，链变为 $\color{blue}0-5-1-0-0-0$；
8. $b$ 增加至 $2$；
9. **计算**，$2$ 个原子（从左向右）的结果分别为 $(\color{red}0\color{black},1),(120,\color{red}0\color{black})$；
10. 根据结果，左边的原子（$5$）**向左运动**，右边的原子（$1$）**向右运动**，链变为 $\color{blue}5-0-0-1-0-0$；
11. **位于两端的原子被移除**，链变为 $\color{blue}0-0-0-1-0-0$；
11. 此时链中只剩下 $1$ 个原子（$1$），**反应结束，密码锁瘫痪**。

综上，样例 $6$ 的瘫痪用时为 $2$ 秒。

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

本题共 $100$ 个测试点，分别有 $n=1,2,\ldots,100$，每个 $1$ 分。

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


title: [THUPC 2023 初赛] 大富翁

background: 有一天，小 W 和小 H 在玩大富翁。

description:
这版大富翁的游戏规则比较独特。它的地图是一棵 $n$ 个节点的有根树，其中 $1$ 号节点为根。树上每个节点都有一个价格，第 $x$ 号节点的价格记为 $w_x$。

对于树上两个不同的节点 $x,y$，若 $x$ 是 $y$ 的祖先节点（即，$x$ 在 $1$ 号点到 $y$ 号点的简单路径上），则称 $x$ **支配** $y$。

游戏过程中，小 W 和小 H 轮流**购买**树上的一个未被人购买过的节点，直到树上的 $n$ 个节点都被小 W 或小 H 购买。（游戏开始前，树上的所有节点都没有被购买。）

对于一次购买，假设买方购买了 $x$ 号节点，那么他首先要向系统支付 $w_x$ 个游戏币。假设此时 $x$ 支配着 $n_1$ 个已被买方的对手购买了的节点，同时又被 $n_2$ 个已被对手购买了的节点支配。若 $n_1>n_2$，那么对手要向买方支付 $n_1-n_2$ 个游戏币，若 $n_1<n_2$，那么买方要向对手支付 $n_2-n_1$ 个游戏币。

小 W 和小 H 都是绝顶聪明的人，他们都会在游戏中采用最优策略，来使自己赚到尽量多的游戏币。现在，小 W 想考考你：如果他先手，他最终能赚到多少个游戏币？（即，在整个游戏过程中，小 W 从小 H 手中获得的游戏币个数减去他支付给系统和小 H 的游戏币个数。你可以认为，游戏开始前，小 H 和小 W 手中都有足够数量的游戏币。注意：答案可能为负数。）

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

第二行 $n$ 个非负整数，第 $i$ 个整数为 $i$ 号节点的价格 $w_i$。

第三行 $n-1$ 个正整数，第 $i$ 个正整数表示第 $i+1$ 号节点的父亲编号。

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

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

hint:
#### 样例解释 1

一个可能的游戏过程是：

- 第一次购买：小 W 购买 $1$ 号节点，向系统支付 $0$ 个游戏币。
- 第二次购买：小 H 购买 $2$ 号节点，向系统支付 $0$ 个游戏币，并向小 W 支付 $1$ 个游戏币。
- 第三次购买：小 W 购买 $3$ 号节点，向系统支付 $1$ 个游戏币。
- 第四次购买：小 H 购买 $4$ 号节点，向系统支付 $0$ 个游戏币，并向小 W 支付 $1$ 个游戏币。
- 第五次购买：小 W 购买 $6$ 号节点，向系统支付 $0$ 个游戏币。
- 第六次购买：小 H 购买 $5$ 号节点，向系统支付 $0$ 个游戏币，并向小 W 支付 $1$ 个游戏币。
- 第七次购买：小 W 购买 $7$ 号节点，向系统支付 $0$ 个游戏币。

#### 子任务

对于所有测试数据，$1\leq n\leq 2\times 10^5$，$0\leq w_x\leq 2\times 10^5$。保证输入的图为一棵以 $1$ 号节点为根的有根树。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。


title: [THUPC 2023 初赛] 拧螺丝

background:
张华考上了北京大学；李萍进了中等技术学校；~~小 E 在工地搬砖~~：他们都有光明的前途。

由于搬砖太累，小 E 决定进厂拧螺丝。但是小 E 遇到了一个各种刁难人的老板。

description:
加工一个模块需要拧 $n$ 个螺丝。但是，每隔 $10$ 分钟，小 E 的老板就会到小 E 的工位上收走一个未完工的模块。在这期间，只够小 E 拧 $k$ 个螺丝。

小 E 的老板刚刚离开。问老板接下来第几次来的时候小 E 才可能有一个完工的模块？假设小 E 的老板极力不想让小 E 达成这件事。

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

outputFormat:
如果小 E 无论如何也不能有一个完工的模块，那么输出一行 `Poor E.S.!`。

否则输出一行一个正整数，表示答案。

hint:
#### 样例解释 1

小 E 先选择两个模块各拧上一个螺丝，然后老板来了拿走一个。接下来小 E 只需要在剩下的那个零件上面拧两个螺丝就可以完工了。所以老板第二次来的时候小 E 就有了一个完工的模块。注意小 E 在老板来的时候不能有只拧上了一半的螺丝，不然老板看到了会说小 E 加工不合格。

#### 子任务

保证 $1\le k \le n \le 10^5$。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。


title: [THUPC 2023 初赛] 快速 LCM 变换

description:
小 I 今天学习了快速最小公倍数变换（Fast Least-Common-Multiple Transform, FLT），于是他想考考你。

给定一个长度为 $n$ 的正整数序列 $r_1,r_2,\cdots,r_n$。你需要做以下操作恰好一次：

- 选择整数 $i,j$ 使得 $1 \le i < j \le n$。在序列末尾加入 $(r_i+r_j)$，并将 $r_i$ 和 $r_j$ 从序列中删除。

可以注意到总共有 $\frac{n(n-1)}{2}$ 种可能的操作，每种操作会得到一个长度为 $n-1$ 的序列。

你需要对所有的这 $\frac{n(n-1)}{2}$ 个序列，求出序列中所有元素的最小公倍数，并给出它们的和模 $998244353$ 的值。

inputFormat: 输入的第一行包含一个正整数 $n$，表示序列的长度。接下来一行 $n$ 个正整数 $r_1,r_2,\cdots,r_n$，描述初始序列。

outputFormat: 输出一行一个整数，表示所有序列的最小公倍数的和模 $998244353$ 的值。

hint:
#### 样例解释 1

- $i=1,j=2$ 时，得到的序列为 $\{4,5\}$，最小公倍数为 $20$；
- $i=1,j=3$ 时，得到的序列为 $\{3,6\}$，最小公倍数为 $6$；
- $i=2,j=3$ 时，得到的序列为 $\{2,7\}$，最小公倍数为 $14$。

因此输出为 $20+6+14=40$。

#### 子任务

对于所有测试数据，$2 \le n \le 5 \times 10^5, 1 \le r_1,r_2,\cdots,r_n \le 10^6$。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。


title: [THUPC 2023 初赛] 种苹果

description:
农夫种了一棵苹果树，树上结满了大大小小的苹果。夏天正是果树生长发育的大好时节，树上不断抽出新的枝条、结出新的苹果，已有的苹果也在不断长大。

为了观察和记录苹果的生长状况，以便对未来收获的行情有大致的估计，农夫进行了长时间仔细的观察和研究。在整个记录周期的最开始，树上一共结有 $n$ 个苹果，农夫将其编号为 $1\sim n$ ，有 $n-1$ 条树枝连接这些苹果，每条树枝的两端都恰好挂有一个苹果，使得整个苹果树成为一个名副其实的树形结构。农夫对每个苹果进行了一番价值估计，第 $i$ 个苹果的初始价值为 $a_i$ ，表示农夫此时摘下它并卖出的净收益，考虑到成本因素， $a_i$ 可能为负。

在整个记录周期中，共发生了 $m$ 件值得记录的事件，所有的事件共分为以下几种类型：

$1\ u\ v\ w$：树上原本连接苹果 $u$ 和苹果 $v$ 的树枝中间结出了一个新的苹果。设原先树上共有 $k$ 个苹果，则此时变为 $k+1$ 个，农夫将新长出的苹果编号为 $k+1$ ，其价值为 $w$ 。原先连接苹果 $u$ 和 $v$ 的树枝也因此分裂成两条，一条连接苹果 $u$ 和 $k+1$ ，另一条连接苹果 $k+1$ 和 $v$；

$2\ u\ w$：树上长出了一条新树枝和一个新苹果。设原先树上共有 $k$ 个苹果，则此时变为 $k+1$ 个，农夫将新长出的苹果编号为 $k+1$，其价值为 $w$。新树枝连接苹果 $u$ 和 $k+1$。

$3\ u\ v\ w$：树上一部分苹果的价值发生了变化。树上连接苹果 $u$ 和 $v$ 的一整段枝条（即树形结构上连接 $u$ 和 $v$ 的最短路径，包括 $u$ 和 $v$ 本身）上的所有苹果的价值均增加了 $w$ 。考虑到价值的变化也可能是由于营养不足或病虫害引起的，因此 $w$ 可能为负。

$4\ u\ v\ w$：农夫想在树上进行一次抽样调查来研究自己的可能收益。他定义价值不小于 $w$ 的苹果为“优质苹果”，并选择了树上连接苹果 $u$ 和 $v$ 的一整段枝条（含义同上），想统计一下这段枝条上的苹果中有多少个“优质苹果”。

但由于苹果的数量是在太多了，农夫数不过来，便只好请你来帮忙。注意：由于农夫不能预测未来，因此你帮农夫时必须**强制在线**地回答问题。

inputFormat:
第 $1$ 行： $2$ 个正整数 $n,m$。

第 $2$ 行： $n$ 个整数 $a_i$。

接下来 $n-1$ 行：每行两个正整数 $u_i,v_i$，依次描述初始时树上的所有树枝。

接下来 $m$ 行，每行 $3$ 或 $4$ 个整数，按照时间顺序描述所有的事件，格式如题目描述中所述。

为了体现强制在线性，设上一次 $4$ 事件的答案是 $lastans$ （最开始时 $lastans=0$），则所有事件中输入的 $u,v,w$ 都需要异或上 $lastans$ 才是真正的 $u,v,w$。

outputFormat: 对于每个 $4$ 事件输出一行，一个非负整数，表示农夫此次调查的“优质苹果”数量。

hint:
#### 样例解释 1

对于这组样例，去除强制在线后的数据如下：

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

#### 数据范围

对于所有数据， $n,m \leq 2 \times 10^5$，$|a_i|, |w|\leq 10^9$，保证任意时刻涉及到的苹果编号均有意义，保证初始的 $n-1$ 条树枝构成树形结构，所有 $1$ 事件保证连接苹果 $u$ 和 $v$ 的树枝在事件发生时存在。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。


title: [THUPC 2023 初赛] 速战速决

description:
小 I 与小 J 正在玩一个叫做“开火车”，又称作“拖板车”和“小猫钓鱼”的扑克游戏。游戏规则如下，注意其与一般玩法可能有不同：

- 有 $2n$ 张牌，其中对于整数 $1 \le i \le n$，牌面为 $i$ 的牌恰好有 $2$ 张。
- 游戏开始时，小 I 和小 J 各拿其中 $n$ 张牌组成双方的初始手牌。
- 维护一个公共牌堆（可以将其看作一个栈），初始没有牌。小 I 与小 J 依次行动，小 I 先手。一次行动时，行动方依次进行以下操作：
  1. 将手牌中的一张牌放在公共牌堆顶；
  2. 若此时公共牌堆中有两张相同的牌，则这两张相同的牌以及在这两张牌之间的所有牌从公共牌堆移到当前行动方手牌中；
  3. 若此时当前行动方没有手牌，则当前行动方失败，另一方胜利。

小 J 是扑克萌新，所以会按照以下策略行动：

- 维护一个队列，初始将 $n$ 张手牌按照一定顺序放入队列中；
- 每次行动时，将队列开头的牌放在公共牌堆顶；
- 若小 J 放入某张牌后公共牌堆中有两张相同的牌，则按照在公共牌堆中自顶到底的顺序将获得的牌放入队列尾。

小 I 通过偷看得到了小 J 的策略以及队列中牌的顺序。现在小 I 不仅想获胜，还想速战速决，用**最少**的行动次数获胜，但他也是扑克萌新。所以给定小 J 队列中的 $n$ 张牌以及它们的顺序，你需要给出小 I 的策略，使得小 I 能够获胜，同时行动次数最少，或者告诉他这是不可能的。

inputFormat:
每组数据的第一行一个整数 $n$ 表示牌面的种数。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，从队头到队尾的顺序依次描述小 J 队列中的牌。

得到小 J 的 $n$ 张手牌也就得到了小 I 的 $n$ 张手牌，因此不会输入小 I 的手牌。

outputFormat: 如果小 I 不可能获胜，只需要输出一个整数 `-1`；否则第一行输出一个整数 $s$，表示你给出的策略中小 I 的行动次数。接下来一行 $s$ 个整数，依次描述每次行动时小 I 从手牌中放入公共牌堆的牌的牌面，两个数之间以一个空格分隔。**注意你给出的策略要满足 $s$ 最小。**

hint:
#### 样例解释 1

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

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

#### 子任务

对于所有测试数据，$1 \le n \le 3 \times 10^5$，$1 \le a_1,a_2,\cdots, a_n \le n$，且每个整数在序列 $a$ 中至多出现两次。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。


title: [THUPC 2023 初赛] 乱西星上的空战

background:
众所周知，在乱西星的现代战争中，制空权是很重要的。为此，人们发展出了无人机技术——遗憾的是，由于乱西星的算法水平和各种意义上的通讯水平实在太落后了，所以这些无人机只能采用各自独立的傻瓜式战斗模式，这些模式不含任何随机因素，因此一场傻瓜式无人机空战总是几乎能在开始前就被预测到结果。

总而言之，乱西星上正在相互战争的 |\\| 国和 () 国的傻瓜式无人机战斗机编队在其边境交界处的空域遭遇了，现在两国军方希望你能预测这一空战的结果。

description:
### 空域与时刻

由于乱西星的神秘物理法则，乱西星的时间和空间并不是连续的；若认为遭遇战开始的时刻是第 $1$ 时刻，那么对于任意的第 $k\in \N$ 个时刻，在这一时刻开始和结束时，一个物体（无人机或导弹）只能在形如 $(x,y,z)\in\mathbb Z^3$ 的位置（即空域内的整点）上。

### 无人机

由于空域相比无人机要大得多，因此我们可以将无人机视为一个质点（尽管他们实际上长得和地球上的一般意义上的飞机十分相似）。

#### 飞行状态

在每个时刻，一架无人机的飞行状态可以用以下三组参数描述：

1. 当前时刻所在的坐标 $\vec p=(x,y,z)\in\mathbb Z^3$；
2. 当前时刻的飞行方向向量 $\vec{d},\|\vec d\|=1$；
   - 其中， $\|\vec{v}\|$ 表示向量 $\vec v$ 的长度：设 $\vec{v}=(v_x,v_y,v_z)$，则 $\|\vec{v}\|=\sqrt{v_x^2+v_y^2+v_z^2}$。
   - 你可以简单地将 $\vec d$ 理解为机头指向的方向。
3. 当前时刻的无人机升力线方向 $\vec u,\|\vec u\|=1,\vec u\bot \vec d$；
   - 你可以简单的将 $\vec u$ 理解为飞机所在平面的、从机腹指向机背的单位法向量。
   - 此时，$\vec d$ 和 $\vec u$ 可以唯一确定一个“左手向” $\vec l=\vec u\times \vec d$。

#### 飞行性能

不严格地讲，一般而言，一架飞机通常有三个操作轴，即俯仰、滚转和偏航：俯(负杆)和仰(正杆)分别对应飞机机头向下和向上（即保持 $\vec l$ 不变）；滚转即飞机以飞行方向为中轴线旋转（即保持 $\vec d$ 不变）；偏航则为飞机机头向左或者向右（即保持 $\vec u$ 不变）。由于无人机的特殊设计，其**没有偏航**轴，只能进行俯仰和滚转——容易看出，即使仅进行俯仰和滚转，一架无人机也能随意地改变 $\vec d$ 和 $\vec u$ （在保持 $\|\vec u\|=\|\vec d\|=1,\vec u\bot \vec d$ 的前提下）。

以上的俯仰(正杆或负杆)、滚转操作，以及直线飞行，及其复合统称“机动”。

由于无人机型号差异，一架无人机的飞行性能可以用以下三组参数描述（为方便起见，在本节中，对进行一次机动前的飞行状态对应参数为 $\vec p=(x,y,z),\vec d,\vec u,\vec l$，进行一次机动后的飞行状态对应的参数为 $\vec p'=(x',y',z'),\vec d',\vec u',\vec l'$）：

1. 正杆率 $\theta_u\in(\dfrac\pi4,\dfrac\pi2)$ 和负杆率 $\theta_d\in(\dfrac\pi4,\dfrac \pi2)$；
   - 若无人机**仅进行正杆**机动，则必须有 $\vec p=\vec p',\vec l=\vec l',\vec u\cdot \vec d'\ge 0$；此时，进行一次这样的机动花费的时间是 $\dfrac{\angle(\vec d,\vec d')}{\theta_u}$。
   - 若无人机**仅进行负杆**机动，则必须有 $\vec p=\vec p',\vec l=\vec l',\vec u\cdot \vec d'\le 0$；此时，进行一次这样的机动花费的时间是 $\dfrac{\angle(\vec d,\vec d')}{\theta_d}$。
2. 滚转率 $\gamma\in(\dfrac\pi4,\dfrac \pi 2)$；
   - 若无人机**仅进行滚转**机动，则必须有 $\vec p=\vec p',\vec d=\vec d'$；此时，进行一次这样的机动花费的时间是 $\dfrac{\angle(\vec u,\vec u')}{\gamma}$。
3. 飞行极速 $v_{m}>0$；
   - 若无人机**仅进行直线飞行**，则必须有 $\vec d=\vec d',\vec u=\vec u'$；此时，花费的时间是 $\dfrac{\|\vec p'-\vec p\|}{v_m}$。

#### 合法位移

在每个时刻，若一架无人机可以从 $\vec p=(x,y,z),\vec d,\vec u,\vec l$ 这一飞行状态，严格按照**滚转**、**俯仰**(正杆或负杆)和**直线飞行**的顺序进行机动，使飞行状态变为 $\vec p'=(x',y',z')\not=\vec p,\vec d',\vec u',\vec l'$，满足 $\vec d'//(\vec p'-\vec p)$，并且各机动花费的时间之和不超过 $1$，则称这是一次(无人机的)合法的综合机动。

如果一架无人机可以从 $\vec p=(x,y,z),\vec d,\vec u,\vec l$ 通过一次合法的综合机动，使飞行状态变为 $\vec p'=(x',y',z')\not=\vec p,\vec d',\vec u',\vec l'$，并且在所有使飞行状态变为 $\vec p''=\vec p',\vec d'',\vec u'',\vec l''$ 的合法综合机动中，总用时是最短的，则称之为一次（无人机的）合法位移（或称该位移合法）。此时，无人机会沿直线从 $\vec p$ 移动到 $\vec p'$。如无特殊指明，下文中“位移”均默认(应当为)合法位移。

#### 眼镜蛇机动

在每个时刻，无论无人机飞行性能如何，无人机总是可以通过眼镜蛇机动，从 $\vec p=(x,y,z),\vec d,\vec u,\vec l$ 这一飞行状态，变为 $\vec p'=\vec p,\vec d'=\vec u,\vec u'=-\vec d,\vec l'=\vec l$ 这一飞行状态。注意，这种机动不被视为合法机动。

#### 其它参数

除此之外，一架无人机还具有以下参数：

1. 无人机编号（简称“编号”）；
   - 保证任意两架无人机编号不同。
2. 所在阵营（简称“阵营”）；
   - 所在阵营必须是|\\| 国或者是 () 国中之一，并且双方互称敌方阵营。

#### 坠毁

一架无人机坠毁，当且仅当其符合下列条件之一：

1. 在某激活的导弹位移过程中，与该导弹的距离不大于导弹的空爆距离（详见下文）。
2. 在某导弹位移结束后，与该导弹位置重合（从而导弹直接命中无人机导致坠毁，下同）。
3. 在无人机位移过程中，存在至少一枚激活的导弹，与其距离不大于该导弹的空爆距离。
4. 在无人机位移结束后，存在至少一枚导弹所在位置与其位置重合。
5. 在无人机位移结束后，存在另一架无人机与其坐标相同（从而发生碰撞导致双双坠毁）。

无人机坠毁后将立即消失，此后不会发射导弹，也不会导致其它无人机坠毁。但无人机已经发射的导弹不会立刻消失或爆炸。

此时也称无人机被摧毁。

### 空空红外制导导弹

类似的，一枚空空红外制导导弹（下文简称“导弹”）也可视为一质点，并且同样可以描述其飞行状态和飞行性能。

#### 飞行状态

由于导弹无所谓上下左右，因此仅需要以下两组参数以描述一个导弹的飞行状态：

1. 当前时刻所在的坐标 $\vec p=(x,y,z)\in\Z^3$；
2. 当前时刻的飞行方向向量 $\vec{d},\|\vec d\|=1$；
   - 你可以简单地将 $\vec d$ 理解为导弹弹头指向的方向。

#### 飞行性能

同样由于一枚导弹无所谓上下左右，因此其不存在俯仰、滚转和偏航轴，其向各个方向改变 $\vec d$ 的性能是相同的，此时统称仅改变 $\vec d$ 的操作为 "偏航"。其与直线飞行及复合统称“机动”。

因此一枚导弹的飞行性能可以用以下两组参数描述（为方便起见，在本节中，对进行一次机动前的飞行状态对应参数为 $\vec p=(x,y,z),\vec d$，进行一次机动后的飞行状态对应的参数为 $\vec p'=(x',y',z'),\vec d'$）：

1. 偏航率 $\theta_r\in(\dfrac\pi4,\dfrac\pi2)$；
   - 若导弹**仅进行偏航**机动，则必须有 $\vec p=\vec p'$；此时，进行一次这样的机动花费的时间是 $\dfrac{\angle(\vec d,\vec d')}{\theta_r}$；
2. 飞行极速 $v_m>0$；
   - 若导弹**仅进行直线飞行**，则必须有 $\vec d=\vec d'$；此时，花费的时间是 $\dfrac{\|\vec p'-\vec p\|}{v_m}$。

#### 合法位移

在每个时刻，若一枚导弹可以从 $\vec p=(x,y,z),\vec d$ 这一飞行状态，严格按照**偏航**和**直线飞行**的顺序进行机动，使飞行状态变为 $\vec p'=(x',y',z')\not=\vec p,\vec d'$，满足 $\vec d//(\vec p'-\vec p)$，并且各机动花费的时间之和不超过 $1$，则称这是一次(导弹的)合法位移（或称该位移合法）。此时，导弹会沿直线从 $\vec p$ 移动到 $\vec p'$。如无特殊指明，下文中“位移”均（应当）默认为合法位移。

#### 其它参数

除此之外，一枚导弹还具有以下参数：

1. 保险距离 $d_s>0$ 和激活状态；
   - 导弹被发射后立即处于未激活状态。
   - 每个时刻结束时，若导弹处于未激活状态，并且发射该导弹的无人机已坠毁，或者与发射该导弹的无人机的距离大于保险距离 $d_s$ 时，进入激活状态。此后将保持激活状态，并称该导弹被激活，或称其为一枚激活的导弹。
2. 空爆距离 $d_p>0$；
   - 每次导弹位移过程中，当一枚激活的导弹与任一无人机（包括发射该导弹的无人机）距离不大于 $d_p$ 时，该导弹会进入可空爆状态（详见下文“可空爆”）。
   - 每次无人机位移过程中，若存在一无人机与一枚激活的导弹距离不大于 $d_p$ 时，该导弹也会进入可空爆状态。
3. 最大锁定角 $\beta_s\in(\dfrac\pi4,\dfrac\pi2)$；
   - 任意时刻，一枚飞行状态为 $\vec p=(x,y,z),\vec d$、最大锁定角的导弹能锁定到 $\vec p'$ 处的无人机，当且仅当 $\vec d\cdot(\vec p'-\vec p)>0$，并且 $\angle(\vec d,\vec p'-\vec p)\le \beta_s$。
   - 此时称该无人机能被该导弹锁定，或称其在导弹的锁定范围内。
   - 称 $\angle(\vec d,\vec p'-\vec p)$ 为锁定角。
4. 制导时长 $t_z>0$；
   - 若导弹在第 $k$ 个时刻被发射，则到第 $k+t_z$ 个时刻结束时，若导弹仍未爆炸，则导弹会立刻消失（见“爆炸、消失与可空爆”）。此时称导弹超过制导时长。

#### 爆炸、消失与可空爆

一枚导弹在符合下列全部条件时，会立刻爆炸并消失：

1. 在导弹位移开始前，导弹处于激活状态；

2. 符合以下条件之一：

   1. 在该导弹位移过程中，存在一架位于 $\vec q$ 的无人机，使 $\min_{\lambda\in[0,1]}\|\lambda \vec p+(1-\lambda)\vec p'-\vec q\|\le d_p$，其中  $\vec p,\vec p'$ 为导弹本次位移的起点和终点。

      - 此时，所有这样的无人机都会被该导弹摧毁。同时，一架无人机可能同时被若干枚导弹摧毁。

   2. 在无人机位移过程中，存在一架无人机，记其从位置 $\vec q$ 位移到 $\vec q'$ ，满足 $\min_{\lambda\in[0,1]}\|\lambda \vec q+(1-\lambda)\vec q'-\vec p\|\le d_p$，其中 $\vec p$ 为导弹此时的位置。

      - 此时，所有这样的无人机都会被该导弹摧毁。同时，该导弹也可能同时摧毁若干这样的无人机。

此时，称该导弹可空爆，或该导弹进入可空爆状态。

一枚导弹在符合下列条件之一时，不会发生爆炸，但是会在当前时刻结束时消失：

1. 导弹脱锁（见下文“导弹脱锁”），并且在当前时刻开始时已被激活；

2. 导弹超过制导时长；

3. 导弹未激活，并且导弹位移结束后与一无人机位置重合；

   - 此时，该无人机会被这枚导弹摧毁。同时，一架无人机可能同时被若干枚导弹摧毁。

4. 导弹未激活，无人机位移结束后，该导弹与一无人机位置重合。

   - 此时，该无人机会被这枚导弹摧毁。同时，一枚导弹可能同时摧毁若干这样的无人机。

### 无人机视野、雷达搜索与导弹锁定

#### 无人机视野

任意时刻，一架飞行状态为 $\vec p=(x,y,z),\vec d,\vec u,\vec l$ 的无人机能够发现一架位于 $\vec p'=(x',y',z')$ 的无人机，当且仅当 $\vec d\cdot(\vec p'-\vec p)> 0$；此时称 $\vec p'$ 处的无人机在 $\vec p$ 处无人机的视野内。

#### 无人机机载雷达搜索范围

一架无人机的机载雷达（下文简称“雷达”）的扫描范围可以用以下两个参数描述：

1. 水平扫描范围 $L_x\in\N^+$ 和垂直扫描范围 $H_y\in\N^+$；
   - 任意时刻，一架飞行状态为 $\vec p=(x,y,z),\vec d,\vec u,\vec l$ 、雷达扫描范围为 $L_x,H_y$ 的无人机的能够扫描到一架位于 $\vec p'$ 的无人机，当且仅当，$\vec d\cdot(\vec p'-\vec p)>0$ 并且 $\exist x,y,s.t.\ |x|\le L_x,|y|\le H_y$ 且 $[\vec p'-(\vec p+x\vec l+y\vec u)]//\vec d$。
   - 即若以 $\vec p$ 为原点、以 $\vec l$ 和 $\vec u$ 为 $X,Y$ 轴建一平面 $\alpha=\alpha(\vec p;\vec l,\vec u)$，则  $\vec p'$ 在这一平面上的投影 $\vec r=P(\vec p';\alpha)$ 应当落在 $[-L_x,L_x]\times [-H_y,H_y]$ 中。
   - 此时称 $\vec p'$ 处的无人机在 $\vec p$ 处无人机雷达扫描范围内。

#### 导弹脱锁

当无人机位移结束后，若一枚导弹选定的目标已坠毁，或其不能被该导弹锁定，则称该导弹脱锁，或处于脱锁状态。

此后将一直保持脱锁状态，无论是否此前选定的无人机是否重新可以被导弹锁定。

### 无人机选定目标策略

任意时刻，无人机（简称"本机"，下同）按下述策略选择目标无人机。

1. 若本机视野内无敌方阵营无人机（简称“敌机”，下同），则本机无选定目标；
2. 否则，若上一时刻本机选择的无人机仍位于本机视野内，则本机仍选定该目标；
3. 否则，若存在至少一架敌机处于本机雷达扫描范围内，则选取其中与本机距离最近的；若与本机距离最近的敌机不唯一，则选取编号最小的。
4. 否则，对视野内的处于 $\vec p'$ 的敌机，记 $\alpha=\alpha(\vec p;\vec l,\vec u),\vec r=P(\vec p';\alpha)=(r_x,r_y)$，则选取 $\min\{|r_x-L_x|,|r_x+L_x|\}+\min\{|r_y-H_y|,|r_y+H_y|\}$ 最小的。若有多个最小值，则同样选择编号最小的。

### 飞行策略

#### 无人机飞行策略

设无人机飞行状态是 $\vec p=(x,y,z),\vec d,\vec u,\vec l$，其飞行极速为 $v_m$，机载雷达扫描范围为 $L_x,H_y$。

1. 若无人机有位于 $\vec p'$ 的选定目标：
   1. 若无人机能够合法地位移到某个位置，使敌机现在的位置 $\vec p'$ 仍处于本机的视野内，则无人机会合法地移动到飞行状态 $\vec q=(x_q,y_q,z_q),\vec d_q,\vec u_q,\vec l_q$，使敌机现在的位置 $\vec p'$ 仍处于本机视野内，且 $\|\vec p'-\vec q\|$ 最小。
      1. 若有多个这样的位置，记 $\alpha_q=\alpha(\vec q;\vec l_q,\vec u_q),\vec r_q=P(\vec p';\alpha_q)=(r_{qx},r_{qy})$，则优先选取使 $\vec r_q=(r_{qx},r_{qy})\in[-L_x,L_x]\times [-H_y,H_y]$ 的位置；
         1. 若仍有多个这样的位置，则选取使 $\|\vec r_q\|=\sqrt{r_{qx}^2+r_{qy}^2}$ 最小的；
         2. 若仍有多个这样的位置，则选取 $\vec q$ 字典序最小的。
      2. 若不存在这样的 $\vec r_q$，则选取使 $\min\{|r_{qx}-L_x|,|r_{qx}+L_x|\}+\min\{|r_{qy}-H_y|,|r_{qy}+H_y|\}$ 最小的；
         1. 若仍有多个这样的位置，则选取 $\vec q$ 字典序最小的。
   2. 否则，无人机会合法地移动到某个位置 $\vec q$，使 $\|\vec q-\vec p-v_m\vec d\|$ 最小；
      1. 若有多个这样的位置，则选取 $\vec q$ 字典序最小的。
2. 否则，无人机通过眼镜蛇机动，将飞行状态变为 $\vec p=(x,y,z),\vec u,-\vec d,\vec l$。

保证在上述1.的情况下，无人机总能合法地移动到某个位置。

#### 导弹飞行策略

设导弹当前时刻飞行状态 $\vec p,\vec d$，其选定的敌机飞行状态为 $\vec p',\vec d',\vec u',\vec l'$；

若上一时刻结束时，导弹未脱锁，则记 $\vec q'$ 为敌机根据其飞行策略，下一时刻会移动到的位置。

若导弹能合法位移到 $\vec q'$，则导弹会直接位移到 $\vec q'$。

否则，导弹会合法地位移到能使敌机位移后的位置 $\vec q'$ 处于锁定范围内的位置 $\vec q$ ，且 $\|\vec q-\vec q'\|$ 最小。

1. 若有多个这样的 $\vec q$，则选取位移后锁定角最小的；
2. 若仍有多种可能，则选取 $\vec q$ 字典序最小的。

若不存在这样的位置，或者上个时刻结束时，导弹已经脱锁，则导弹会合法地位移到某个位置 $\vec q$，使 $\|\vec q-\vec p-v_m\vec d\|$ 最小。

保证导弹总能合法地移动到某个位置。

### 无人机发射导弹规则

一飞行状态为 $\vec p=(x,y,z),\vec d,\vec u,\vec l$ 的无人机（简称"本机"）向**被本机选定**的、处于 $\vec p'$ 的目标无人机（简称“敌机”）发射导弹的规则为：

在每个时刻开始时，若选定的敌机已处于本机雷达扫描范围内，且当前不存在由本机发射且未爆炸（或消失）的导弹，则向敌机发射一初始飞行状态为 $\vec p,\vec d=\dfrac{\vec p'-\vec p}{\|\vec p'-\vec p\|}$ 的未激活的导弹，该导弹选定敌机。

### 同一时刻内各事件发生顺序

1. 所有无人机选定目标，并确定当前时刻内的飞行策略；
2. 所有能发射导弹的无人机发射导弹；
3. 所有导弹确定飞行策略并位移，该过程中部分无人机可能被摧毁；
4. 所有可空爆的导弹爆炸并消失；
5. 所有无人机按 1. 中确定的飞行策略位移，该过程中部分无人机可能被摧毁；
6. 所有可空爆的导弹爆炸并消失；
7. 所有位置相同的无人机发生碰撞并坠毁。
8. 所有超过制导时长和脱锁且已激活的导弹消失。
9. 所有可激活的导弹被激活。

### 任务

给定空域开始时（即第 $1$ 时刻开始时），各无人机的飞行性能与状态、导弹的飞行性能，假定这场空战会持续 $T$ 个时刻，双方指挥官希望你能按时间顺序依次给出每个时刻发生的所有重要事件。

inputFormat:
第一行两个正整数 $n,T$ ，表示共有 $2n$ 架无人机，模拟前 $T$ 个时刻。其中，前 $n$ 架阵营是 |\\| 国，后 $n$ 架阵营是 () 国。

接下来有 $2n$ 组数据，每一组包含若干行，其中第 $i$ 组描述了编号为 $i$ 的无人机。

在每组数据中：

第一行三个整数表示 $\vec p\in\mathbb Z^3$；保证所有的 $\vec p$ 两两不同，且坐标的绝对值不超过 $100$。

第二行六个整数依次表示无人机的 $\vec d,\vec u$，保证 $\vec d,\vec u\in S_v$；

- 其中， $S_v=\{(1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1)\}$；

第三行六个实数依次表示无人机的 $\theta_u,\theta_d,\gamma,v_m,L_x,H_y$；

第四行五个实数和一个正整数依次表示导弹的 $\theta_r,v_m,d_s,d_p,\beta_s,t_z$。

outputFormat:
输出 $T$ 组数据，第 $i$ 组数据表示第 $i$ 个时刻发生的重要事件。

在每组数据中：

第一行三个非负整数 $p_1,p_2,p_3$ ，表示在这个时刻的导弹位移过程中被摧毁的无人机数量、在这个时刻的无人机位移过程中被摧毁的无人机数量、这个时刻结束时，有多少组无人机因位置相同而两两碰撞坠毁。

接下来 $p_1$ 行，每行形如 $id_0\ k\ id_1\ id_2\ \cdots\ id_k$，表示编号为 $id_0$ 的无人机在这个时刻的导弹位移过程中被摧毁，并且在该过程中摧毁该无人机的导弹共有 $k$ 枚，分别来自编号为 $id_1,id_2,\cdots,id_k$ 的无人机。

为保证输出唯一，这 $p_1$ 行中的每一行内，$id_1,\dots,id_k$ 应当从小到大输出，行之间按 $id_0$ 从小到大输出。

接下来 $p_2$ 行，每行形如 $id_0\ k\ id_1\ id_2\ \cdots\ id_k$，表示编号为 $id_0$ 的无人机在这个时刻的无人机位移过程中被摧毁，并且在该过程中摧毁该无人机的导弹共有 $k$ 枚，分别来自编号为 $id_1,id_2,\cdots,id_k$ 的无人机。

为保证输出唯一，这 $p_2$ 行中的每一行内，$id_1,\dots,id_k$ 应当从小到大输出，行之间按 $id_0$ 从小到大输出。

接下来 $p_3$ 行，每行形如 $k\ id_1\ id_2\ \dots id_k$，表示该时刻结束时，有 $k$ 架无人机位置相同 ，它们的编号是 $id_1,...,id_n$。

为保证输出唯一，这 $p_3$ 行中的每一行内，$id_1,\dots,id_k$ 应当从小到大输出，行之间按 $id_1$ 从小到大输出，并且每个编号出现至多一次。

hint:
#### 样例解释 1

在第 $1$ 时刻，两架飞机于 $(4,0,0)$ 处相撞。

#### 样例解释 2

在第 $4$ 时刻，两枚导弹分别摧毁了敌机。

#### 数据范围

$T,n\le 100,3\le v_m\le 20$；

$v_m>10$ 的无人机和导弹总数不超过 $10$；

$\theta_u,\theta_d,\gamma,\theta_r,\beta_s\in(\dfrac\pi4,\dfrac\pi2)$；

$1\le d_s,d_p\le 20,1\le t_z\le 100$；

$|x|,|y|,|z|\le 100$；

$1\le L_x,H_y\le 100$。

所有输入的实数精确到小数点后不超过 $6$ 位。

最初时，$\vec p$ 两两不同。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。


title: [THUPC 2023 初赛] 公平合作

description:
在大地的尽头，一座灰白的灯塔矗立在漫长的海岸线上。这一片海域海流复杂、礁石嶙峋，却又是不少航线的必经之路。若没有如此高耸而明亮的灯塔为过路的船只照亮航路，或许会有更多不幸的生命葬身海底。为了看管好这一座海上明灯，一批训练有素的守望人轮流值守于此。日复一日的工作枯燥乏味却又不能有丝毫闪失，紧绷的神经直到下一班守望人到来才得以放松。

在电力普及之前，灯塔通常使用煤油灯为过往的水手指引前行的方向。每次为这座灯塔添加燃油时，需要两位守望人各自搬运一个容积为 $L$ 的油桶；而每次轮到 Y 和 S 所在的班组照料这座灯塔时，总是由 Y 和 S 负责为灯塔加油。将煤油搬运至灯室时，如果不装满油桶，对灯塔的正常运转也没有太大影响，无非是需要多来回搬运几趟。但是，如果两位守望人都想着偷懒，问题恐怕就不只是多几趟那么简单。Y 和 S 想到了一个好办法：互相为对方的油桶装油。

灯塔里有 $N$ 个用于将储存的煤油转移到油桶中的容器，其中第 $i$ 个容器的容积为 $a_i$。Y 和 S 先想办法决定由谁先装油。两人先后装油；轮到其中一位守望人装油时，这位守望人每次从所有容器中等概率地随机选出一个容器，将其装满油，并全部倒入对方的油桶中。两位守望人都可以在操作任意多次（可以是 0 次）后结束装油，但后手必须等先手结束后才能开始装油。Y 和 S 先后装完煤油后，两人会比一下谁把对方的油桶装得更满，再各自把自己的油桶搬运到灯室。但是，如果有谁某次选出一个容器后，把对方的油桶装满了，但容器里还有没倒出的煤油，那么这位倒霉的守望人就必须把两个油桶都独自搬到灯室——这也算是为单调的生活平添了几分乐趣。显然，如果先手某次随机选中的容器会使得油桶溢出，那么后手可以往先手的油桶里面装任意量的煤油，然后幸灾乐祸；因此我们约定：当先手溢出时，必定由先手搬两个油桶。

现在只剩下了一个问题：当 Y 和 S 都采取最优策略，使得对方搬的煤油尽可能地比自己多的时候，先手搬的煤油不多于后手的概率是多大？

inputFormat:
输入的第一行包括两个正整数 $N$ 和 $L$，分别表示转移用的容器数量和油桶的容积。

输入的第二行包括 $N$ 个正整数 $a_1, \cdots, a_N$，分别表示每个转移用的容器的容积。

outputFormat: 输出一个实数，表示先手搬的煤油不多于后手的概率。当你的输出与标准输出的绝对误差不超过 $10^{-6}$ 时，我们认为你的输出是正确的。

samples:
见附件中的 2.in
见附件中的 2.out

samples:
见附件中的 3.in
见附件中的 3.out

hint:
#### 样例解释 1

可以证明，此时先手的策略一定是装满对方的油桶，且装满时必胜。经过若干次随机抽取后，能恰好将对方的油桶装满的概率为：

$$
\left(\frac{1}{2}\right)^2 + \binom{3}{1}\left(\frac{1}{2}\right)^3 + \left(\frac{1}{2}\right)^4 = \frac{11}{16}=0.6875
$$

#### 数据范围

对于 $100\%$ 的数据，保证 $1\le N\le 2\times 10^3$，$1\le L\le 10^9$，$1\le a_i\le 2\times 10^3$。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。


title: [THUPC 2023 初赛] 欺诈游戏

background: 在《LIAR GAME》中，小 E 看到了一个有趣的游戏。

description:
这个游戏名叫《走私游戏》。游戏规则大概是这样的：一名玩家扮演走私者，一名玩家扮演检察官。走私者可以将 $x$ 日元（$x$ 为 $[0,n]$ 内的整数，由走私者决定）秘密放入箱子中，而检查官需要猜测箱子中的金额。假设检察官猜了 $y$（$y$ 也必须是整数）。如果 $x=y$，则走私失败，走私者一分钱也拿不到。如果 $x>y$，则走私成功，走私者可以从检查官那里拿走 $x$ 日元。如果 $x<y$，则走私失败，但是由于冤枉检察官需要赔付给走私者 $y/2$ 日元。游戏分有限回合进行。双方轮流做走私者和检察官。

可以证明，最优情况下每个回合走私者会采用同一种策略，检察官也会采用同一种策略。小 E 想知道在一个回合中，双方的最优策略分别是什么。

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

outputFormat:
输出两行，每行 $n+1$ 个数，其中第 $i$ 个表示放/猜 $i-1$ 日元的概率。

第一行输出走私者的策略，第二行输出检察官的策略。

你需要保证，在一方的策略不变的情况下，另一方无论如何改变自己的策略，都不能使自己的期望收益比原来多。

可以证明，这样的策略是唯一的。

答案对 $998244353$ 取模。

hint:
#### 样例解释 1

这 $4$ 个数分别为 $2/3,1/3,1/3,2/3$。

#### 子任务

保证 $1\le n \le 400000$。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。


title: [THUPC 2023 初赛] 众数

description:
你有若干个 $[1,n]$ 内的正整数：对于 $1 \le i \le n$，你有 $a_i$ 个整数 $i$。设 $S = \sum_{i=1}^n a_i$。

对于一个序列 $p_1,p_2,\cdots,p_l$，定义其众数 $\text{maj}(p_1,p_2,\cdots,p_l)$ 为出现次数最多的数。若有多个数出现次数最多，则其中最大的数为其众数。

现在你需要把这 $S$ 个数排成一个序列 $b_1,b_2,\cdots,b_S$，使得 $\sum_{i=1}^S \text{maj}(b_1,b_2,\cdots,b_i)$ 最大。输出该最大值。

inputFormat:
第一行一个整数 $n$，表示值域。

接下来一行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示每种数的个数。

outputFormat: 输出一行一个正整数表示 $\sum_{i=1}^S \text{maj}(b_1,b_2,\cdots,b_i)$ 的最大值。

hint:
#### 样例解释 1

一个达到最大值的序列为 $(3,2,3,1,2,2)$。

#### 数据范围

对于所有测试数据，$1 \le n \leq 10^5$，$1 \le a_1,a_2,\cdots,a_n \le 10^5$。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。


title: 「RiOI-03」匀速相遇

background:
当大家都在加速时，我与你，在人生中的十字路口，匀速地相遇了。

确是惊动我心的一瞥，却是无法逗留的遗憾，我们再次，朝着自己的方向匀速奔跑。下次再见，又会是什么时候呢……

description:
平面直角坐标系上有 $n + m$ 个点，其中：

- 有 $n$ 个 $\rm A$ 类点，它们在初始时依次位于位置 $(1, 0), (2, 0), (3, 0), \dots, (n, 0)$。
- 有 $m$ 个 $\rm B$ 类点，它们在初始时依次位于位置 $(0, 1), (0, 2), (0, 3), \dots, (0, m)$。

在某一个时刻，$\rm A, B$ 类点同时开始运动。具体地：

- 对于第 $i$ 个 $\rm A$ 类点，其以 $a_i$ 个单位长度每秒的速度向上（即 $y$ 轴正方向）匀速运动。特别地，若 $a_i = 0$，则该点始终保持静止。
- 对于第 $i$ 个 $\rm B$ 类点，其以 $b_i$ 个单位长度每秒的速度向右（即 $x$ 轴正方向）匀速运动。特别地，若 $b_i = 0$，则该点始终保持静止。

相遇与分离实在是再平凡不过的了。作为匆匆时光里的一名过客，在这个你暂留的驿站里，你能否帮小 T 解决这个简单的问题：求出有多少点对会在某个时刻相遇，即它们在某一刻共点。

由于你无法使时间静止，所以所有点无论相遇与否，都会永无止境地运动下去。祝愿在这道路上奔跑的你，能有一天与理想匀速相遇，永不停息。

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

第二行 $n$ 个整数 $a_1\dots a_n$，依次表示第 $1\dots n$ 个 $\rm A$ 类点的运动速度。

第三行 $m$ 个整数 $b_1\dots b_m$，依次表示第 $1\dots m$ 个 $\rm B$ 类点的运动速度。

outputFormat: 一行一个整数，表示有多少点对会在某个时刻相遇。

hint:
### 样例解释 1

当 $t = 1$ 时，第 $2$ 个 $\rm A$ 类点和第 $2$ 个 $\rm B$ 类点同时到达点 $(2, 2)$。这也是在本组样例中的唯一一次相遇，故输出 $1$。

### 数据规模与约定

**本题开启捆绑测试。**

+ Subtask 0（10 pts）：$n \leq 10$，$m \leq 10$。
+ Subtask 1（20 pts）：$n \leq 5\times 10^3$，$m \leq 5\times 10^3$。
+ Subtask 2（30 pts）：保证 $\forall a_i \geq 1$，$\forall b_i \geq 1$。
+ Subtask 3（40 pts）：无特殊限制。

对于所有数据，$1 \leq n, m \leq 10^6$，$0 \leq a_i, b_i \leq 10^9$。


title: [THUPC 2023 初赛] 最后的活动

background:
各位亲爱的《La Lumière: Scarlet Intense Flame》玩家：

感谢您一直给予《La Lumière: Scarlet Intense Flame》的支持与厚爱。我们非常遗憾地宣布，《La Lumière: Scarlet Intense Flame》将于 2023 年 3 月 5 日 16:00 停止运营服务。

停止运营相关时间表如下：

……

description:
元老级二次元手游《La Lumière: Scarlet Intense Flame》将于今年 3 月停止运营服务。作为这款游戏的忠实玩家，小 S 希望能在游戏的最后一次活动中刷到一个特殊的分数，以此为近十年来与这款游戏共度的难忘时光画上一个圆满的句号。

《La Lumière: Scarlet Intense Flame》中的每种活动都有其独特的规则，而最后一次活动是 Chase Festival。在 Chase Festival 中，玩家需要多次攻略每次随机生成的多层迷宫，每次退出迷宫时根据在迷宫中各层击杀怪物的评价独立结算本次随机迷宫的分数。每次挑战迷宫时的流程简化如下：

1. 选择挑战的随机迷宫的难度。小 S 是这款游戏的资深玩家，因此在本题中假定小 S 总是挑战最高难度的迷宫。最高难度的迷宫最深为 $N$ 层。确定难度后，从随机生成的迷宫的第 1 层开始挑战。

2. 进行第 $i$ 层的挑战。挑战第 $i$ 层时，小 S 有可能挑战失败，挑战成功并获得普通评价，或者挑战成功并获得高评价。如果小 S 选择保守的挑战策略，则有 $p_{i,0}$ 的概率挑战失败，有 $p_{i,1}$ 的概率挑战成功并获得普通评价，有 $p_{i,2}$ 的概率挑战成功并获得高评价；如果小 S 选择激进的挑战策略，则有 $q_{i,0}$ 的概率挑战失败，有 $q_{i,1}$  的概率挑战成功并获得普通评价，有 $q_{i, 2}$ 的概率挑战成功并获得高评价。

   - 获得普通评价时，在当前层获得 $s_{i,1}$ 的分数；获得高评价时，在当前层获得 $s_{i,2}$ 的分数。这部分获得的分数**不会直接加算**到玩家的总分数中，而是**在退出迷宫时结算**。如果挑战成功，且当前不是最后一层（$i<N$），则跳转到第 3 步，选择是否继续挑战；否则（$i=N$），退出迷宫并跳转到第 4 步进行结算。

   - 如果挑战失败，则强制退出迷宫，跳转到第 4 步。

3. 如果当前不是最后一层，玩家可以选择是否继续挑战下一层。如果选择继续，则返回第 2 步；否则退出当前迷宫，跳转到第 4 步进行结算。

4. 本次迷宫的分数结算：如果因为失败而强制退出，则当前层不获得任何奖励，且**本次迷宫中之前各层**累积的分数需要乘上惩罚系数 $c$（为了使最终分数为整数，游戏会对惩罚后的分数先求和再下取整）；除了强制退出之外，玩家主动退出或者通关迷宫后退出都可以获得全部尚未结算的分数。

小 S 想得到的目标分数是一个比较大的分数，因此小 S 需要先大量刷最高难度的迷宫，再在接近目标分数时根据当前剩余的分数选择相对稳定的策略，以确保活动结束时能恰好获得目标分数。小 S 不会编程，因此小 S 找到了你，希望你能帮忙计算当剩余分数在 $1$ 至 $M$ 分之间，仅按照上述的流程挑战迷宫，并采用最佳策略时，最终能够恰好达到目标分数的最大概率。

outputFormat: 输出一行 $M$ 个实数，其中第 $i$ （$1\le i\le M$）个实数表示当距离目标分数恰好还剩 $i$ 分时，在最优策略下能够恰好获得 $i$ 分的最大概率。 当你输出中的每个实数与相应标准输出的绝对误差不超过 $10^{-6}$ 时，我们认为你的输出是正确的。

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

hint:
#### 子任务

对于 $100\%$ 的数据，保证 $1\le N\le 6$，$1\le M\le 10000$，$0\le c'\le 100$，$1\le s_{i,1}\le s_{i, 2}\le 10000$，$0\le u_{i, 0}, u_{i, 1}, u_{i, 2}, v_{i, 0}, v_{i, 1}, v_{i, 2}\le 10000$，$u_{i,1}+u_{i,2}\ge 1$，$v_{i,1}+v_{i,2}\ge 1$。

#### 提示

《La Lumière: Scarlet Intense Flame 2》将于 2023 年春暖花开的时节与大家相见！

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。


title: [语言月赛202303] Stone Gambling S

description:
Farmer John 和 Bessie 正在玩一个石头游戏。

初始时，Farmer 手中有 $x$ 块石头，Bessie 有 $y$ 块。他们的眼前有一个石头堆，可以认为里面有无限块石头。

从 Farmer John 开始，双方轮流操作。每次操作中，如果自己的石头数量**小于**对方的石头数，就从石头堆中拿 $1$ 块石头；否则，就要向石头堆里扔石头直到手中的石头数不超过本次操作开始时自身石头数的一半（这就是说，如果本次操作开始时自己有 $w$ 块石头，则需要扔石头直到手里还剩 $\left\lfloor\frac w 2 \right\rfloor$ 块石头）。当有一方在操作完成后**手头没有石头**（即石头数量为 $0$）了，那么游戏结束。

请你求出游戏结束时双方手中的石头数量。

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

第一行是一个整数，表示数据组数 $T$。接下来 $T$ 行，每行表示一组数据的输入信息。

对每组数据，输入只有一行两个整数，依次表示 Farmer John 初始的石头数 $x$ 和 Bessie 初始的石头数 $y$。

outputFormat: 对每组数据，输出一行两个整数，依次表示 Farmer John 最终的石头数 $x$ 和 Bessie 最终的石头数 $y$。

hint:
### 样例 1 解释

下表中，用 $s$ 和 $t$ 分别代表 Farmer John 和 Bessie 在对应轮次**开始前**手中的石头数，每行代表一次操作。

| 操作者 | $s$ | $t$ | 操作 |
| :-: | :-: | :-: | :-: |
| Farmer John | $2$ | $5$ | $s = s + 1$ |
| Bessie | $3$ | $5$ | $t = \left\lfloor\frac{t}{2}\right\rfloor$ |
| Farmer John | $3$ | $2$ | $s = \left\lfloor\frac{s}{2}\right\rfloor$ |
| Bessie | $1$ | $2$ | $t = \left\lfloor\frac{t}{2}\right\rfloor$ |
| Farmer John | $1$ | $1$ | $s = \left\lfloor\frac{s}{2}\right\rfloor$ |
| 结束 | $0$ | $1$ | |

### 数据规模与约定

- 对 $20\%$ 的数据，保证 $x, y \leq 5$。
- 另有 $20\%$ 的数据，保证 $x = y$。
- 对 $60\%$ 的数据，保证 $x, y \leq 10^9$，$T = 1$。
- 对 $100\%$ 的数据，保证 $1\leq T \leq 100$，$1 \leq x, y \leq 10^{18}$。

provider：一扶苏一


title: [语言月赛202303] Coin Selection G

description:
Farmer John 和 Bessie 正在一起玩硬币选择游戏。

初始时桌面上有 $n$ 枚硬币，每枚硬币有一个面额，我们使用 $a _ 1, a _ 2, \cdots, a _ n$ 分别代表第 $1, 2, \cdots, n$ 枚硬币的面额。

他们还各有一个属于自己的钱包，初始时，钱包都是空的。

从 **Farmer John** 开始，双方轮流操作。每次操作中，当前的操作者会从桌面上剩余的硬币中选择**面值不超过当前自己钱包中硬币的总面额**的硬币中**面额最大的**一枚硬币，把它从桌子上拿走，放到自己的钱包里。如果桌面上剩余的**所有**硬币面值都**超过了自己钱包里已有硬币的总面额**，那么选择剩余的所有硬币中面额**最小**的一个。

当桌面上没有硬币时，游戏结束。

请你分别求出，	游戏结束后，Farmer John 和 Bessie 钱包里硬币的总面额。

inputFormat:
第一行为一个整数，代表初始时桌面上的硬币的数量 $n$。
第二行为 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，分别代表第 $1, 2, \cdots, n$ 枚硬币的面额。

outputFormat: 输出共一行两个整数，第一个整数表示 Farmer John 最终钱包里的总面额，第二个整数表示 Bessie 最终钱包里硬币的总面额，两个整数之间使用一个空格隔开。

hint:
### 样例 1 解释

Farmer John 开始时「自己钱包中硬币的总面额」为 $0$，小于桌面上的任何一枚硬币，因此他只能选择剩下的所有硬币中面值最小的一个，为 $2$。

接下来 Bessie「自己钱包中硬币的总面额」为 $0$，小于桌面上的任何一枚硬币，因此只能选择剩下的所有硬币中面值最小的一个，为 $3$。

### 数据规模与约定

- 对 $20\%$ 的数据，保证 $n \leq 2$。
- 另有 $20\%$ 的数据，保证 $a_i = 1$。
- 对 $60\%$ 的数据，保证 $n \leq 100$。
- 对 $100\%$ 的数据，保证 $1 \leq n \leq 10^3$，$1 \leq a_i \leq 10^{16}$。

provider：一扶苏一


title: [THUPC 2023 初赛] 喵了个喵 II

background: 本来这题的题面和《喵了个喵》有关的。但是听说有人嫌题面长，就少说点好了。

description: 给定一个长为 $4n$ 的序列，其中 $1\sim n$ 各出现 $4$ 次。问是否能够将其划分为两个相等的子序列。

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

第二行 $4n$ 个正整数，表示序列。保证 $1\sim n$ 各出现 $4$ 次。

outputFormat:
如果不能划分为两个相等的子序列，输出一行 `No`。

否则第一行输出 `Yes`。第二行输出一个长为 $4n$ 的 `01` 串。其中第 $i$ 位表示原序列的第 $i$ 个数被划分到第几个子序列。你需要保证你划分出来的两个子序列完全相等。

hint:
#### 样例解释 1

两个子序列均为 $(1,2,1,2)$。

#### 子任务

保证 $1\le n \le 5\times10^4$。

保证序列中 $1\sim n$ 各出现 $4$ 次。

#### 评分方式

你的输出的第一行需要与标准答案一致。若为 `Yes`，输出任意一种合法的划分均算正确。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。

By E.Space：由于考场上数据太弱，我于 3.12 和 3.19 两度加强了数据。


title: [THUPC 2023 初赛] 背包

description:
本题中，你需要解决完全背包问题。

有 $n$ 种物品，第 $i$ 种物品单个体积为 $v_i$、价值为 $c_i$。

$q$ 次询问，每次给出背包的容积 $V$，你需要选择若干个物品，每种物品可以选择任意多个（也可以不选），在选出物品的体积的和**恰好**为 $V$ 的前提下最大化选出物品的价值的和。你需要给出这个最大的价值和，或报告不存在体积和恰好为 $V$ 的方案。

为了体现你解决 NP-Hard 问题的能力，$V$ 会远大于 $v_i$，详见数据范围部分。

inputFormat:
第一行两个整数 $n,q$，表示物品种数和询问次数。

接下来 $n$ 行每行两个整数 $v_i,c_i$ 描述一种物品。

接下来 $q$ 行每行一个整数 $V$ 描述一次询问中背包的体积。

outputFormat: 对于每组询问输出一行一个整数。若不存在体积和恰好为 $V$ 的方案，输出 `-1`；否则输出最大的选出物品的价值和。

hint:
#### 样例解释 1

第二组询问的最优方案为：选择 $3$ 个物品 $1$ 和 $12499999998$ 个物品 $2$。

#### 子任务

对于所有测试数据，$1 \le n \le 50, 1 \le v_i \le 10^5, 1 \le c_i \le 10^6, 1 \le q \le 10^5, 10^{11} \le V \le 10^{12}$。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。


title: [THUPC 2023 初赛] 世界杯

description:
2022 年卡塔尔世界杯已于 12 月 18 日落下帷幕，作为一项始于 1930 年的悠久赛事，迄今已走过 22 届，四年一度的足球盛宴，是陪伴全世界无数足球运动员和爱好者成长的荣耀时光和青春记忆。

作为一个新球迷，小 M 在这届世界杯前对足球几乎一无所知，但受到身边小伙伴的带动，他也决定加入到球迷的大家庭中。赛前，小 M 对世界杯进行了一定的了解，得知世界杯正赛共分为小组赛和淘汰赛，其中淘汰赛尤为刺激，16 强、8 强、半决赛、决赛，只要输一场便立刻淘汰出局，唯有全胜者方能捧得桂冠。因此，小 M 心想，夺得世界杯冠军当然是无可争议的世界巅峰，而能否从小组赛出线杀入淘汰赛、以及在淘汰赛阶段走得多远，也同样是衡量一支队伍强弱的重要指标。

世界杯正赛共有 32 支球队参加，而遗憾落选的队伍则更多。全世界这么多支球队，对于萌新小 M 来说，逐一去了解难免是一个浩大的工作。因此，小 M 决定先从联合国五常来入手，对应的 5 支球队分别为：中国队（`China`）、英格兰队（`England`）、法国队（`France`）、俄罗斯队（`Russia`）和美国队（`United States`）。值得一提的是，苏格兰队和威尔士队也曾打进过世界杯正赛，但以小 M 的知识水平来说，显然忽略了它们。

随后，小 M 仔细调查了这 5 支球队的历届世界杯战绩：英格兰队、法国队和美国队在近 30 年来均有至少 4 次杀入世界杯淘汰赛的经历，其中法国队收获了 1998、2018 世界杯的冠军，虽也有过小组赛 2 败出局的经历，但已足够向世界展示其强大；英格兰队唯一的世界杯冠军在 1966 年，近年来最好战绩为四强，而美国队近年来最好战绩为八强，这两支队伍的实力也都不容小觑；俄罗斯队近 30 年来的前 3 次世界杯之旅都不顺利，在小组赛阶段便早早接连失利并被淘汰，但 2018 年以东道主的身份打入淘汰赛并杀入八强；而中国队则实力稍逊，唯一一次打入世界杯正赛是在 2002 年，但小组赛三战全败，只得遗憾出局。

正像无数球迷心中都有一支“主队”，小 M 也希望从这 5 支球队中选出一支“最强球队”，作为他今后支持的对象。在他进一步了解后，也知道了评价一支球队有各项指标，这几支球队也似乎各有所长。到底该怎样衡量“最强”呢？小 M 思来想去，决定以“世界杯正赛中输球总场数最少”作为衡量依据。又经过了细致的查找资料和分析，他心中的“最强球队”已经呼之欲出。

此时，他想考考屏幕前的你：能猜出他心中的“最强球队”是哪一支吗？

inputFormat: 无输入。

outputFormat: 输出一个字符串，一定是 `China`，`England`，`France`，`Russia`，`United States` 中的一个，表示小 M 心中的“最强球队”。

hint:
#### 提示

题面所述信息已经足以推断出问题的答案，无需任何额外的足球知识。

#### 题目来源

来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。

题解等资源可在 <https://github.com/THUSAAC/THUPC2023-Pre> 查看。


title: [入门赛 #10] Coin Selection G（hard version）

description:
Farmer John 和 Bessie 正在一起玩硬币选择游戏。

初始时桌面上有 $n$ 枚硬币，每枚硬币有一个面额，我们使用 $a _ 1, a _ 2, \cdots, a _ n$ 分别代表第 $1, 2, \cdots, n$ 枚硬币的面额。

他们还各有一个属于自己的钱包，初始时，钱包都是空的。

从 **Bessie** 开始，双方轮流操作。每次操作中，当前的操作者会从桌面上剩余的硬币中选择**面值不超过当前自己钱包中硬币的总面额**的硬币中**面额最大的**一枚硬币，把它从桌子上拿走，放到自己的钱包里。如果桌面上剩余的**所有**硬币面值都**超过了自己钱包里已有硬币的总面额**，那么选择剩余的所有硬币中面额**最小**的一个。

当桌面上没有硬币时，游戏结束。

请你分别求出，	游戏结束后，Farmer John 和 Bessie 钱包里硬币的总面额。

outputFormat: 输出一行两个整数，第一个整数表示 Bessie 最终钱包里硬币的总面额，第二个整数表示 Farmer John 最终钱包里的总面额。

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

- 对 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq a_i \leq 10^{9}$。

Provider：一扶苏一