title: [eJOI2019] 异或橙子

description:
Janez 喜欢橙子！他制造了一个橙子扫描仪，但是这个扫描仪对于扫描的每个橙子的图像只能输出一个  $32$ 位整数。

他一共扫描了 $n$ 个橙子，但有时他也会重新扫描一个橙子，导致这个橙子的 $32$ 位整数发生更新。

Janez 想要分析这些橙子，他觉得异或操作非常有趣，他每次选取一个区间从 $l$  至 $u$，他想要得到这个区间内所有子区间的异或和的异或和。

例如 $l=2,u=4$ 的情况，记橙子序列 $A$ 中第 $i$ 个橙子的整数是 $a_i$，那么他要求的就是：

$$a_2 \oplus a_3 \oplus a_4 \oplus (a_2\oplus a_3)\oplus(a_3\oplus a_4)\oplus(a_2\oplus a_3 \oplus a_4)$$

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

注：式子中的 $\oplus$ 代表按位异或运算。异或的运算规则如下。

对于两个数的第 $i$ 位，记为 $x,y$，那么：

|$x$|$y$|$x\oplus y$|
| :-----------: | :-----------: | :-----------: |
|$0$|$1$|$1$|
|$1$|$0$|$1$|
|$0$|$0$|$0$|
|$1$|$1$|$0$|

例：$13\oplus 23=26$

|$13=$|$0\cdots 001101$|
| --------: | :------: |
|$23=$|$0\cdots 010111$|
|$13\oplus 23=$|$0\cdots 011010$|

inputFormat:
第一行输入两个正整数 $n,q$，表示橙子数量和操作次数。

接下来一行 $n$ 个非负整数，表示每个橙子扫描得到的数值 ，从 $1$ 开始编号。

接下来 $q$ 行，每行三个数：

- 如果第一个数是 $1$，接下来输入一个正整数 $i$ 与非负整数 $j$，表示将第 $i$ 个橙子的扫描值 $a_i$ 修改为 $j$。

- 如果第一个数是 $2$，接下来输入两个正整数 $u,l$ 表示询问这个区间的答案。

outputFormat: 对于每组询问，输出一行一个非负整数，表示所求的总异或和。

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

- 最初，$A=[1,2,3]$，询问结果为 $1\oplus 2\oplus 3\oplus(1\oplus 2)\oplus (2\oplus 3)\oplus(1\oplus 2\oplus 3)=2$

- 修改后，第一个位置被修改为 $3$ ，询问的结果是 $3\oplus 2\oplus 3\oplus(3\oplus 2)\oplus (2\oplus 3)\oplus(3\oplus 2\oplus 3)=0$。

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

#### 数据规模与约定：

**本题采用多测试点捆绑测试，共有 5 个子任务**。

- Subtask 1(12 points)：$1\le n,q\le 10^2$，无特殊限制
- Subtask 2(18 points)：$1\le n,q\le 5\times 10^2$，且没有修改操作。
- Subtask 3(25 points)：$1\le n,q\le 5\times 10^3$，无特殊限制
- Subtask 4(20 points)：$1\le n,q\le 2\times 10^5$，且没有修改操作。
- Subtask 5(25 points)：$1\le n,q\le 2\times 10^5$，无特殊限制

对于所有数据，$0\le a_i\le 10^9,1\le n,q\le 2\times 10^5$

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

#### 说明

原题来自：[eJOI2019](http://ejoi2019.si/) Problem A. [XORanges](https://www.ejoi2019.si/static/media/uploads/tasks/xoranges-isc(1).pdf)

题面&数据来自：[LibreOJ](https://loj.ac/problem/3195)


title: 「StOI-1」树上询问

type: P

description:
给定一棵 $n$ 个点的无根树，有 $q$ 次询问。

每次询问给一个参数三元组 $(a,b,c)$ ，求有多少个 $i$ 满足这棵树在以 $i$ 为根的情况下 $a$ 和 $b$ 的 [LCA](https://www.luogu.com.cn/problem/P3379) 为 $c$ 。

inputFormat:
第一行2个数，为 $n$ 和 $q$ 。

接下来 $n-1$ 行，每行 $2$ 个数，表示树的一条边。

接下来 $q$ 行，每行 $3$ 个数，为 $(a,b,c)$。

outputFormat: 共 $q$ 行，每行一个数，为对于每个三元组的 $i$ 的个数。

hint:
---

#### 样例2解释

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

第一个查询的 $i$ 为 3 和 4。

第二个查询的 $i$ 为 1。

---

#### 数据范围

#### 本题按子任务测试：

$subtask1 (20pts)$：$1 \leq n \leq$ $1000$ ，$1 \leq q \leq$ $500$ 。

$subtask2 (15pts)$：$1 \leq n \leq$ $10^{5}$，$1 \leq q \leq$ $10^{5}$，树退化成链 。

$subtask3 (25pts)$：$1 \leq n \leq$ $5$ $\times$ $10^{5}$，$1 \leq q \leq $ $10^{5}$，数据**不随机** 。

$subtask4 (40pts)$：$1 \leq n \leq$ $5$ $\times$ $10^{5}$，$1 \leq q \leq $ $2$ $\times$ $10^{5}$ 。

对于所有数据：$1 \leq n \leq$ $5$ $\times$ $10^{5}$，$1 \leq q \leq $ $2$ $\times$ $10^{5}$ 。

注：数据强度不高，不必卡常与快读快输。


title: 「StOI-1」小Z的旅行

description:
一块空地，有$n$座山，每座山有一个高度值$h$。小Z在最高的山上，要去最低的山。

他有如下移动方案：

$1.$ 移动到一座比当前山低的山；

$2.$ 移动到和当前山一样高的山（不可停留在当前山），对于每一高度只能执行一次该方案（即不可以连续 $3$ 次或以上到达同一高度的山）。

每次移动都会耗费体力值，耗费的体力值为两座山的水平距离（若从第 $i$ 座山移动到第 $j$ 座山，则耗费 |$i-j$| 点体力值）。

小Z**每次**若有多种方案移动，则会**等概率**选择任意一种，求耗费体力值的期望对 $998,244,353$ 取余后的结果。

inputFormat:
第一行一个正整数 $n$ ，表示山的个数。
接下来一行 $n$ 个正整数，表示每座山的高度。

outputFormat: 一个整数，表示最终答案对 $998,244,353$ 取余后的结果。


title: 神帖

background: zrl 的生日在 3.14。出生在神帖迭起的日子，他的快乐自然很多。这不，他又要收取来着神帖的馈赠了。

description:
神帖分布在讨论区的一些页面上，每个页面最多有一个神帖。假设他正在浏览的页面设为 $0$ 号页面。向左一页为 $-1$ 号页面，向右一页为 $1$ 号页面，以此类推。第 $i$ 个神帖在 $x_i$ 号页面上，并且有特定的封禁的时间 $t_i$ 和快乐值 $v_i$，超过了这个时间 $t_i$ 浏览就不能得到他的快乐值了。zrl 向左或向右翻一页需要 $1$ 单位时间，浏览神帖不需要时间。问：zrl 最多能得到多少快乐值。

注：在 $t_i$ 个单位时间浏览第 $i$ 个神贴仍能得到 $v_i$ 的快乐值。

**另注：每个神帖的快乐值最多只能得到一次。**

inputFormat:
第一行一个整数 $n$，表示神帖数量。

接下来 $n$ 行，每行三个整数，分别表示第 $i$ 个神帖的 $x_i$，$v_i$，$t_i$。

outputFormat: 一个整数，为 zrl 能得到的最多的快乐值。

hint:
#### 样例解释：

样例 1：$0 \rightarrow -1 \rightarrow 0 \rightarrow 1 \rightarrow 2 \rightarrow 3$
样例 2：$0 \rightarrow -1 \rightarrow 0 \rightarrow 1 \rightarrow 2 \rightarrow 3$
样例 3：$0 \rightarrow -1 \rightarrow -2 \rightarrow -3 \rightarrow -4 \rightarrow -5$

---

#### 数据范围：

| 测试点 | 特殊性质 |
| :-----------: | :-----------: |
| $1-2$ | $x_i \ge 0$ |
| $3-4$ | $0 \le t_i \le 20$ |
| $5-6$ | $n \le 20$ |
| $7$ | $-10 \le x_i \le 10$ |
| $8-9$ | $t_i=$\|$x_i$\| |
| $10-13$ | 所有 $t_i$ 均相等 |
| $14-17$ | $n \le 60$ |
| $17-22$ | 无 |

对于 $100\%$ 的数据，$n \le 200$，$-500 \le x_i \le 500$，$0 \le v_i \le 10^9$，$0\le t_i \le 500$。

Hint：新增两组 Hack 数据，贪心/模拟已经过不去了。


title: 齿轮

description:
Daniel13265 从不知哪里找来了 $n$ 个齿轮，第 $i$ 个齿轮的齿数为不超过 $m$ 的正整数 $a_i$。他现在想把其中 $k$ 个齿轮按照一定的方式拼接在一起。

当齿轮使用一段时间后，就会产生损耗。一个齿轮组的损耗速率是由这个齿轮组的所有齿轮齿数的最大公约数决定的：最大公约数越大，相同的齿之间啮合的频率就会增高，从而损耗的速率就会变快。这个最大公约数又被称为损耗因子。

算出一个齿轮组的损耗因子是很容易的。可是现在 Daniel13265 想要知道，对于可能拼接出的所有齿轮组的损耗因子。

Daniel13265 知道拼接出损耗因子大于 $m$ 的齿轮组是不可能的，而且由于可能拼出的齿轮组的个数很多，你只需要反过来告诉他对于所有的 $t\in[1, m]$，能够拼接出的损耗因子为 $t$ 的齿轮组的个数对 $10^9+7$ 取模后的结果即可。

inputFormat:
输入共 $2$ 行。

第一行包含三个正整数 $n,m,k$，分别表示 Daniel13265 拥有的齿轮个数，齿轮齿数的最大可能值与 Daniel13265 期望的齿轮组的齿轮个数。
第二行共 $n$ 个用单个空格隔开的正整数，第 $i$ 个数 $a_i$ 表示第 $i$ 个齿轮的齿数。

outputFormat: 输出一行 $m$ 个整数，第 $t$ 个数表示能够拼接出的损耗因子为 $t$ 的齿轮组的个数对 $10^9+7$ 取模后的结果。


title: [BalticOI 2019 Day2] 项链

background: **译自 [BalticOI 2019](http://boi2019.eio.ee/tasks/) Day2 T2.** ***[Necklace](http://boi2019.eio.ee/wp-content/uploads/2019/05/necklace.en_.pdf)***

description:
Jill 和 Jane 是姐妹，去年圣诞节他们每个人都得到了一串彩色珠子。我们可以将每种颜色描述为小写英文字母（$\texttt{a}\ldots \texttt{z}$），并将每串珠子描述为一个单词。

女孩们想从他们的珠子中创造项链。他们可以从自己的那串珠子的两端移除一些珠子（可能为零），然后连接剩余部分的两端，将其变成项链。生成的项链可以旋转和翻转。

姐妹们希望他们的项链看起来完全一样，并且尽可能长。她们项链可以达到的最大长度是多少？

inputFormat: 输入包含两行，每行一个字符串，分别描述了 Jill 和 Jane 的一串彩珠。

outputFormat:
输出第一行应该包含一个正整数，代表项链的长度。测试数据保证存在长度为正整数的项链。

第二行包含两个正整数，分别代表 Jill 和 Jane 得到的项链在原来彩珠串中的起始位置，如果有多种合法方案，任意输出一种即可。每一串彩珠从左到右从 $ 0 $ 开始编号。

hint:
### 样例解释

我们对两串彩珠进行如下处理：

`zxyabcd` $ \to $ `---abcd`
`yxbadctz` $ \to $ `--badc--`

最终得到的两串项链 `abcd` 和 `badc` 经过翻转和旋转后是等价的。

### 评分标准

如果你的程序得到的项链合法（即两条项链等价），且长度与可能的最长项链长度相等，你将得到该测试点全部的分数。

如果你的程序得到的项链合法，且长度达到了最长项链长度的一半，你将得到该测试点 $ 20\% $ 的分数。

**请注意，你在一个子任务上的得分，等于你在该子任务所有测试点的最低得分。**

### 子任务

设输入中每个字符串的长度上限为 $ N $ 。

- 子任务 1（25 分）：$ N = 100 $；
- 子任务 2（20 分）：$ N = 400 $；
- 子任务 3（40 分）：$ N = 3000 $；
- 子任务 4（15 分）：$ N = 3000 $，**内存限制为 3 MB**。

前三个子任务内存限制均为 1GB。


title: [BalticOI 2019 Day2] 奥运会

background: **译自 [BalticOI 2019](http://boi2019.eio.ee/tasks/) Day2 T3.** ***[Olympiads](http://boi2019.eio.ee/wp-content/uploads/2019/05/olymp.en_.pdf)***

description:
两个相邻的城市每年都会派出一个 $ K $ 人的代表队参加 $ K $ 场比赛。每一位参赛者都参加所有 $ K $ 场比赛，单场比赛中代表队的得分是该比赛中代表队单名参赛者的最高分，而代表队的总得分是各场比赛代表队的得分之和。

举个 $ K = 3 $ 的例子：

|              | 比赛 1 | 比赛 2 | 比赛 3 |
| :----------: | :---: | :---: | :---: |
|   参赛者 1    |   4   |   5   |   3   |
|   参赛者 2    |   7   |   3   |   6   |
|   参赛者 3    |   3   |   4   |   5   |
| **团队得分** |   7   |   5   |   6   |

该队在这三场比赛的总得分为 $ 7+5+6=18 $。

两个城市之间已经不仅仅开始争论哪个城市有最好的代表队，而且争论哪个城市有第 $ C $ 好的代表队。其中 $ C=1 $ 代表最好（即团队总分最高）的代表队，$ C=2 $ 代表第二好的代表队，以此类推。

你的任务是为其中一个城市找到他们城市中第 $ C $ 好的代表队。两个代表队是不同的，当且仅当两个代表队中至少有一名成员不同。

inputFormat:
输入第一行包含三个整数 $ N,K,C $，其中 $ N $ 代表该城市的候选队员人数，$ K $ 代表一个代表队的人数，$ C $ 代表你要求出的是第 $ C $ 好的代表队。

接下来 $ N $ 行，每行包含 $ K $ 个整数，其中第 $ i $ 行第 $ j $ 个数代表队员 $ i $ 在第 $ j $ 场比赛上的得分。

数据保证：$ K \leq N $ ，可能的代表队组成方案数不少于 $ C $，每名队员的得分不超过 $ 10^6 $。

outputFormat: 输出包含一个整数，即该城市第 $ C $ 好的代表队的得分。

hint:
各子任务的数据规模如下：

- 子任务 1（13 分）：$ 1 \leq N \leq 500, 1 \leq K \leq 2, 1 \leq C \leq 2000 $；
- 子任务 2（31 分）：$ 1 \leq N \leq 40, 1 \leq K \leq 6, 1 \leq C \leq 2000 $；
- 子任务 3（24 分）：$ 1 \leq N \leq 500, 1 \leq K \leq 6, 1 \leq C \leq 2000 $ ，且所有得分均不超过 $ 10 $；
- 子任务 4（32 分）：$ 1 \leq N \leq 500, 1 \leq K \leq 6, 1 \leq C \leq 2000 $；


title: 差别

description:
定义整数 $p,q,r,s$ 与给定的整数 $a,b,c,d$ 的差别度

$$M=\Big|\left(a^2+b^2\right)\left(p^2+q^2\right)+\left(c^2+d^2\right)\left(r^2+s^2\right)+2\big(ac+bd\big)\big(pr-qs\big)+2\big(bc-ad\big)\big(ps+qr\big)\Big|$$

你的任务是求出差别度 $M$ 的非零最小值与取到非零最小值时的一组 $p,q,r,s$。保证差别度 $M$ 的非零最小值存在且小于 $2^{63}$，保证存在一组绝对值都小于 $2^{63}$ 的 $p,q,r,s$ 使得 $M$ 取到非零最小值。

inputFormat: 输入一行四个整数 $a,b,c,d$，意义如题面所述。

outputFormat: 输出一行五个整数 $p,q,r,s,M$，表示使差别度 $M$ 取到非零最小值时的一组 $p,q,r,s$ 与此时 $M$ 的值。

hint:
### 样例解释 #1

显然当 $a=1,b=9,c=2,d=6$ 时，差别度 $M$ 一定为偶数，因此 $M$ 不可能取到小与 $2$ 的非零值。

### 数据范围

| 测试点编号 | 特殊性质 |
|:-:|:-:|
| $1$ | $c=d=0$ |
| $2$ | $a=c=0$ |
| $3$ | $b=d=0$ |
| $4$ | $ad=bc$ |
| $5$ | $\vert a\vert,\vert b\vert,\vert c\vert,\vert d\vert\le10$ |
| $6\sim10$ | 无 |

对于 $100\%$ 的数据，满足 $\vert a\vert,\vert b\vert,\vert c\vert,\vert d\vert\le10^9$。

### 评分方式

**你需要保证每个测试点输出的数的个数为** $5$ **个且** $\vert p\vert,\vert q\vert,\vert r\vert,\vert s\vert,\vert M\vert<2^{63}$**，以避免出现无法预期的错误。**

对于每个测试点，如果你的 $M$ 与标准输出一致，就能得到 $4$ 分；如果你输出的 $p,q,r,s$ 能使计算结果等于 $M$，就能再获得 $6$ 分。

tags: 扩展欧几里德算法,exgcd


title: 替换

description:
Daniel13265 有一串由各种漂亮的贝壳组成的项链，但由于各种原因，这个项链不是环形的，而仅仅是用一根普通的丝线串起来的。项链上的每个贝壳都有一个好看程度 $a_i$，相同种类的贝壳有着相同的好看程度，而不同种类的贝壳有着不同的好看程度。

Danie13265 定义， 第 $l$ 个至第 $r$ 个这一段贝壳是对称的，当且仅当

$$\sum_{i=l}^r\left(a_i-a_{l+r-i}\right)^2=0$$

Daniel13265 经常从中取出一段贝壳。如果这一段贝壳是对称的，他就会非常高兴；如果这一段贝壳不是对称的，那么他会将其中的某些贝壳替换成新的，以使得这一段贝壳成为对称的。一次替换可以任意地改变任何一个位置上贝壳的好看程度，但是过多的替换会使这一段贝壳脱离原本的模样，所以 Daniel13265 至多会进行 $k$ 次替换。如果一段贝壳在进行至多 $k$ 次替换后能够成为对称的，那么 Daniel13265 就称这一段贝壳是「可观赏的」。

Daniel13265 简单地将第 $l$ 个至第 $r$ 个这一「可观赏的」的贝壳段的「观赏指数」定义为

$$\prod_{i=l}^ra_i$$

其中 $a_i$ 表示第 $i$ 个贝壳**原本的好看程度**。

他现在很好奇，在这个贝壳组成的项链中，「可观赏的」贝壳段中「观赏指数」的最大值。但是由于这个值可能很大，所以你只需要求出它对 $10^9+7$ 取模后的结果即可。

inputFormat:
输入共 $2$ 行。

第一行两个正整数 $n,k$，表示这个贝壳组成的项链中贝壳的数目与 Daniel13265 对一段贝壳最多进行替换的次数。
第二行 $n$ 个用单个空格隔开的正整数，第 $i$ 个数 $a_i$ 表示项链上第 $i$ 个贝壳的好看程度。

outputFormat: 输出一行一个非负整数，表示「可观赏的」贝壳段中「观赏指数」的最大值对 $10^9+7$ 取模后的结果。


title: 悔改

description:
Daniel13265 有一些同样长的小木棍，他把这些木棍随意砍成两段，使得每段的长都不超过 $m$。

现在他想把小木棍拼接成原来的样子，但是却遗失了部分小木棍，而且忘记了自己开始时有多少根木棍和它们的长度。所以他打算把剩下的小木棍拼接出尽可能多的相同长度的木棍。

给出每段小木棍的长度，求出从剩下的木棍中最多能够拼接出的相同长度的木棍的个数与能拼接出来相同长度的木棍个数最多时木棍的最小可能长度。

inputFormat:
输入共 $2$ 行。

第一行包含两个正整数 $n,m$，分别表示剩余木棍个数与剩余木棍的最大可能长度。
第二行共 $n$ 个用单个空格隔开的正整数，第 $i$ 个数 $a_i$ 表示第 $i$ 个木棍的长度。

outputFormat: 输出一行两个整数，分别表示从剩下的木棍中最多能够拼接出的相同长度的木棍的个数与能拼接出来相同长度的木棍个数最多时木棍的最小可能长度。


title: 集合

description:
你需要**在线**维护一个自然数的排序集 $S$ 并支持以下操作：

1. 给一个数 $x$，若 $x$ 不在集合 $S$ 中则将 $x$ 添加到集合 $S$ 中；
2. 给一个数 $x$，若 $x$ 已在集合 $S$ 中则将 $x$ 从集合 $S$ 中删除。

为了证明你维护了 $S$，你需要在操作过程中回答以下询问：

3. 求集合 $S$ 中最小元素的值，若 $S=\varnothing$ 则返回 `-1`；
4. 求集合 $S$ 中最大元素的值，若 $S=\varnothing$ 则返回 `-1`；
5. 求集合 $S$ 中元素的数量；
6. 给一个数 $x$，判断 $x$ 是否在集合内，若在则返回 `1` ，若不在则返回 `0` ；
7. 给一个数 $x$，求集合 $T=S\cap[0^-,x)$ 中最大元素的值，若 $T=\varnothing$ 则返回 `-1`；
8. 给一个数 $x$，求集合 $T=S\cap[x,n)$ 中最小元素的值，若 $T=\varnothing$ 则返回 `-1`。

为了证明你**在线地**维护了 $S$，对于所有在第一次询问后的操作 $1,2$ 与询问 $6,7,8$，实际操作和询问的参数 $x$ 为输入中给出的操作和询问的参数 $x'$ 与上一次询问的返回结果 $\text{last}$ 之和。即 $x=x'+\text{last}$。

保证 $0\le x<n$ 。

初始时 $S=\varnothing$。

inputFormat:
输入共 $(m+1)$ 行，其中 $m$ 的意义见下。

第一行两个正整数 $n,m$，其中 $n$ 表示操作与询问的参数 $x$ 的上界，$m$ 表示操作与询问个数的总和。
接下来 $m$ 行，每行一个或两个自然数，表示一次操作或者询问。保证每一行为如下八种形式之一：
1. `1 x'`，表示执行操作 $1$；
2. `2 x'`，表示执行操作 $2$；
3. `3`，表示回答询问 $3$；
4. `4`，表示回答询问 $4$；
5. `5`，表示回答询问 $5$；
6. `6 x'`，表示回答询问 $6$；
7. `7 x'`，表示回答询问 $7$；
8. `8 x'`，表示回答询问 $8$。

outputFormat: 为避免输出过多，你只需要输出一行一个整数，表示所有询问的返回结果之和。


title: [eJOI2019] Awesome Arrowland Adventure

description:
你现在在一个大小为 $m$ 行（行编号从 $0$ 开始，从上往下一直到 $m-1$） $n$ （列编号从 $0$ 开始，从左往右一直到 $n-1$）列的矩阵中。你的初始位置为 $(0,0)$。（$(r,c)$ 表示矩阵中第 $r$ 行，第 $c$ 列的位置）

你需要走到位置 $(m-1,n-1)$ 处。这个矩阵非常神奇——在矩阵的某些格子上有一个箭头。 箭头只可能有四种方向：北（向上），东（向右），南（向下），西（向左）。箭头分布在整个矩阵之上，形成了箭头矩阵。

当你在某一个位置时，假如这个位置不在矩形（左上角 $(0,0)$，右下角 $(m-1,n-1)$）范围内或这个位置没有箭头，那么你会一直停留于此，永远无法到达终点。如果此处有箭头，那么你将会向这个箭头的方向走一格。

但显然，你不一定能够在初始的箭头矩阵上找到一条从 $(0,0)$ 到 $(m-1,n-1)$ 的路径。为了找到这样一条路径，你可以一次将箭头矩阵中某一个箭头 ***顺时针*** 旋转 $90$ 度。通过几次的旋转，你可能会找到一条路径。

请你判断是否可以通过旋转来得到一条从 $(0,0)$ 到 $(m-1,n-1)$ 的路径，如果有，求出最小需要的旋转次数。

inputFormat:
第一行：两个整数 $m,n$ ，表示矩阵的大小；

接下来 $m$ 行，每行一个长度为 $n$ 的字符串，表示箭头矩阵中这一行的箭头的信息。字符串只可能包含 $5$ 种字符：`W`，`E`，`N`，`S`，`X`。它们分别表示：西，东，北，南，没有箭头。

outputFormat:
如果没有可以找到路径的旋转方案，输出 ```-1```；

如果有，输出一个整数表示需要旋转的最少次数。

hint:
#### 样例解释

【样例 1 解释】
- 一个可行的解是，将位置 $(1,2)$ 的 ```W``` 旋转 $3$ 次变成 ```S```。

【样例 2 解释】
- 不需要任何旋转就可以。

【样例 3 解释】
- 在 $(0,0)$ 处旋转 $1$ 次，在 $(1,0)$ 处旋转 $2$ 次，在 $(2,1)$ 处旋转 $1$ 次。

---
#### 数据规模与约定

**本题采用多测试点捆绑测试，共有 $5$ 个子任务**。

- Subtask 1（10 points）：$m=1$，且输入的字符矩阵只包含 ```E``` 或 ```X```。
- Subtask 2（12 points）：$m=1$。
- Subtask 3（12 points）：$n=m=3$。
- Subtask 4（16 points）：$m=2$。
- Subtask 5（50 points）：无特殊限制。

对于 全部的测试点，保证 $1\le m,n\le 500$。

---

#### 说明

原题来自：[eJOI2019](https://www.ejoi2019.si) Problem F [Awesome Arrowland Adventure](https://www.ejoi2019.si/static/media/uploads/tasks/adventure-isc(1).pdf)

题面翻译：@[```_Wallace_```](https://www.luogu.com.cn/user/61430)（如果觉得这个翻译令人谔谔，欢迎提供新翻译）


title: [PA2018] Palindrom

description:
**译自 [PA 2018](https://sio2.mimuw.edu.pl/c/pa-2018-1/dashboard/)  Runda 3 [Palindrom](https://sio2.mimuw.edu.pl/c/pa-2018-1/p/pal/)**

**请特别注意本题的内存限制。**

给出一个字符串，请你判断其是否为回文串。

回文串是指从左往右读与从右往左读完全相同。

inputFormat:
第一行一个整数 $n$。在有些数据中它代表了字符串的长度，有些数据中 $n=0$ （即不告诉你长度）。

第二行一个字符串，即需要判断的串。

outputFormat: 如果是回文串，则输出 `TAK`，否则输出 `NIE`。

hint:
#### 数据范围

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

对于 $100\%$ 的数据，保证字符串长度不超过 $2\times 10^7$。

您可以假设在任何测试数据中都有 $n>0$ 或者 $n=0$。

感谢 @[Infinite_Eternity](/user/897776) 提供的测试数据！


title: [eJOI2019] 挂架

description:
一个挂架由 $n$ 层的连接杆组成。第 $i$ 层（$i\in [0,n-1]$）有 $2^i$ 根连接杆。第 $0$ 层的连接杆的中点被固定在墙上。在其他层，第 $j$ 个（$j\in[1,2^i]$）连接杆的中点被上一层的第 $\left\lceil{\dfrac{j}{2}}\right\rceil$ 个连接杆所固定。如果 $j$ 是奇数，那就是被上一个连接杆所的左端点固定的，如果是偶数，那就是右端点。在最底层，每一个连接杆的左右端点都有一个用来挂衣服的挂钩。一个挂钩可以挂至多一件衣服。

举个例子，当 $n=3$ 时，这个挂架长这样：

![e.g.](https://cdn.luogu.com.cn/upload/image_hosting/1gjqwegx.png)

Mojca 想要把她的所有衣服挂到这个挂架上。每一件衣服恰好重一个单位。以免破坏挂架脆弱的结构，她必须按照某种特定的规则（或顺序）依次挂衣服：

- 当挂好一件衣服后，对于每一个连接杆，假设它左端点下方的总重为 $w_l$，右端点为 $w_r$，那么必须确保 $w_l-w_r \in {0,1}$。 **注意，不可以为** $-1$ 。

连接杆和挂钩很轻，重量可忽略不计。

Mojca 听说你很强，所以来寻求你的帮助。给定两个整数 $n,k$ ，请确定第 $k$ 个衣服应该挂在哪个挂钩上。

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

outputFormat: 输出包含一行，共一个整数，表示第 $k$ 个衣服应该挂的挂钩的编号，**并对** $(10^9+7)$ **取模，挂钩的编号不等同于连接杆的编号。**

hint:
#### 【样例输入输出解释】

**样例 1 解释**

- 挂钩的使用顺序应为：$1,5,3,7,2,6,4,8$，那么第二件衣服就应该挂在第 $5$ 个挂钩上。

**样例 2 解释**

- 这里，挂钩是使用顺序为：$1,	17,9,	25,5,	21,13,29,3,19,\text{etc.}$

---

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

**本题采用多测试点捆绑测试，共有 3 个子任务**。

- Subtask 1（20 points）：$n \leq 10$。
- Subtask 2（20 points）：$n \leq 20$。
- Subtask 3（60 points）：无特殊限制。

对于全部的测试点，保证 $1 \leq n \leq 10^6$，$1 \leq k \leq \min(2^n, 10^{18})$。

---

#### 【说明】

原题来自：[eJOI2019](https://www.ejoi2019.si) Problem B. [Hanging Rack](https://www.ejoi2019.si/static/media/uploads/tasks/rack-isc(1).pdf)

翻译提供：@[```_Wallace_```](https://www.luogu.com.cn/user/61430)（感觉 [LOJ 的翻译](https://loj.ac/problem/3196) 被过于简化容易导致歧义，所以供题者自行翻译了一遍）


title: [ICPC2019 WF] Azulejos

background:
### Warning: If you submit a malicious program, you will be banned.
### 警告：恶意提交本题将被封号。

description:
Ceramic artists Maria and João are opening a small azulejo store in Porto. Azulejos are the beautiful ceramic tiles for which Portugal is famous. Maria and João want to create an attractive window display, but, due to limited space in their shop, they must arrange their tile samples in two rows on a single shelf. Each of João's tiles has exactly one of Maria's tiles in front of it and each of Maria's tiles has exactly one of João's tiles behind it. These hand-crafted tiles are of many different sizes, and it is important that each tile in the back row is taller than the tile in front of it so that both are visible to passers-by. For the convenience of shoppers, tiles in each row are arranged in non-decreasing order of price from left to right. Tiles of the same price may be arranged in any order subject to the visibility condition stated above.

Your task is to find an ordering of the tiles in each row that satisfies these constraints, or determine that no such ordering exists.

inputFormat: The first line of input contains an integer $n$ ($1 \leq n \leq 5 \times 10^5$), the number of tiles in each row. The next four lines contain $n$ integers each; the first pair of lines represents the back row of tiles and the second pair of lines represents the front row. Tiles in each row are numbered from $1$ to $n$ according to their ordering in the input. The first line in each pair contains $n$ integers $p_1, \dots , p_n$ ($1 \leq p_i \leq 10^9$ for each $i$), where $p_i$ is the price of tile number $i$ in that row. The second line in each pair contains $n$ integers $h_1, \dots , h_n$ ($1 \leq h_i \leq 10^9$ for each $i$), where $h_i$ is the height of tile number $i$ in that row.

outputFormat:
If there is a valid ordering, output it as two lines of $n$ integers, each consisting of a permutation of the tile numbers from $1$ to $n$. The first line represents the ordering of the tiles in the back row and the second
represents the ordering of the tiles in the front row. If more than one pair of permutations satisfies the constraints, any such pair will be accepted. If no ordering exists, output `impossible`.

translation:
给你两种瓷砖 $a,b$，每种瓷砖有 $n$ 块，每块瓷砖有两个属性：高度 $h$ 和价值 $p$。

现在要求你把这些瓷砖重新排成两行（$2\times n$）。前一行放瓷砖 $b$，后一行放瓷砖 $a$。

要求从左到右 $p$ 递增（单调不减），对于任意一个位置 $i$，后面的瓷砖要比前面的瓷砖高。

求一种方案或输出无解。

$n\le 5\times 10^5$

hint: Source: ICPC 2019 World Finals.


title: [eJOI2019] T形覆盖

description:
如果你玩过俄罗斯方块，应该见过如下图形：

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

我们称它为一个 ***T 形四格拼板*** 。其 **中心** 被标记为 $\times$。

Manca 画了一个 $n$ 行 $m$ 列的长方形网格。行从 $0$ 至 $m-1$ 编号，列从 $0$ 至 $n-1$ 编号。她将网格中的一些格子标记为 ***特殊格子*** 。然后，她想要她的朋友 Nika 帮助她将 T 形四格拼板按找如下规则摆放：

- 特殊格子的数量与 T 形四格拼板的数量相同，每个 T 形四格拼板的中心在网格上的位置必须是特殊格子。
- T 形四格拼板之间不能有重叠部分。
- 所有拼板的部分均在网格内。

注意，T 形四格拼板有四种摆放方式：$\bot \top \vdash \dashv$。

如果方案不存在，输出 ```No```，否则请找出一种方案使得被拼板覆盖的数总和最大，求出这个最大值。

inputFormat:
第一行两个整数 $m,n$ 分别表示行数和列数。

接下来 $m$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个数（从 $0$ 开始编号）表示方格中第 $i$ 行第 $j$ 列的数 $a_{i,j}$。

接下来一行，一个整数 $k$ ，表示特殊格子的数量。

接下来 $k$ 行，每行两个整数 $r_i,c_i$，表示第 $i$ 个被标记的特殊格子的位置。

outputFormat: 如果有方案，输出可能的被覆盖的格子内数总和的最大值，否则输出 ```No```。

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

其中一种最优的方案如下：

- $(1,1)$ 位置的摆放方式为 $\dashv$。
- $(2,2)$ 位置的摆放方式为 $\vdash$。
- $(3,4)$ 位置的摆放方式为 $\bot$。

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

#### 数据规模与约定

**本题采用多测试点捆绑测试，共有 7 个子任务。**

- Subtask 1（5 points）：$k\le 10^3$，保证对于所有 $i\ne j$，$\max(|r_i-r_j|,|c_i-c_j|)>2$。
- Subtask 2（10 points）：$k\le 10^3$，保证对于所有 $i\ne j$，若 $\max(|r_i-r_j|,|c_i-c_j|)\le 2$，则 $(r_i,c_i)$ 与 $(r_j,c_j)$ 有邻边。
- Subtask 3（10 points）：$k\le 10^3$，保证对于所有 $i\ne j$，$\max(|r_i-r_j|,|c_i-c_j|)\ne 2$。
- Subtask 4（10 points）：所有特殊格子在同一行。
- Subtask 5（15 points）：$k\le 10$。
- Subtask 6（20 points）：$k\le 10^3$
- Subtask 7（30 points）：无其他限制。

对于所有数据，满足：$1\le k\le nm\le 10^6,a_{ij}\in[0,10^3],r_i\in[0,m),c_i\in[0,n)$。

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

#### 说明

原题来自：[eJOI2019](https://www.ejoi2019.si) Problem C. [T - Covering](https://www.ejoi2019.si/static/media/uploads/tasks/covering-isc(1).pdf)。

翻译来自：[LibreOJ](https://loj.ac/problem/3197)。


title: 好吃的题目

background: 这是一道好吃的题目。

description:
有一条小吃街，从左到右依次排列着 $n$ 个商店，从 $1$ 开始标号。

第 $i$ 个商店会只出售一种小吃，热量为 $h_i$，美味度为 $w_i$。

现在有 $m$ 个吃货要来逛街，第 $i$ 个吃货会在 $[l_i,r_i]$ 的商店内寻找小吃，而且为了防止太胖，最多能摄入 $t_i$ 的热量。

小吃吃多了会腻，所以同一个商店的小吃只能吃一次。

现在每个吃货想知道自己最多能得到多少美味度。

inputFormat:
第一行为两个整数，分别表示 $n,m$。

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

第三行为 $n$ 个整数，第 $i$ 个整数表示 $w_i$。

第 $4$ 到第 $(m + 3)$ 行，每行三个整数，第 $(i + 3)$ 行的整数 $l_i, r_i, t_i$ 分别表示第 $i$ 个吃货的参数。

outputFormat: 对于每个吃货，输出一行一个整数，表示最大的美味度和。

hint:
#### 【样例输入输出解释】

**样例 1 解释**

对于第一组数据的第一个吃货，可以选择第 $3$ 个商店和第 $5$ 个商店。

摄入的热量为 $36+36=72\leq 81$，获得美味度为 $284+282=566$。

**样例 2 解释**

对于第二组数据的第一个吃货，可以选择第 $10$，第 $13$，第 $15$ 个商店。

摄入的热量为 $15+9+6=30\leq 31$，获得美味度为 $34+21+11=66$。

---

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

- 对于 $30\%$ 的数据，满足 $n,m\leq 500$。
- 对于 $60\%$ 的数据，满足 $n\leq 4\times 10^4$，$m\leq 5000$。
- 对于 $100\%$ 的数据，满足 $1 \leq n\leq 4\times 10^4$，$1 \leq m\leq 2\times 10^5$，$1\leq l_i\leq r_i\leq n$，$1\leq h_i,t_i\leq 200$，$1\leq w_i\leq 10^7$。


title: [eJOI2019] 矩形染色

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

description:
Srečko 想给一个 $m$ 行（从 $0$ 至 $m-1$ 编号） $n$ 列（从 $0$ 至 $n-1$ 编号）的的矩形网格的每一个格子染上色。一开始，整个矩形都是白色的。每一步，他都会选择一条对角线，并给这条对角线上的所有格子染上色。每个对角线染色都需要一定的费用（忽略长度），这就导致某些对角线的染色费用有高于其他某些对角线。

你需要写一个程序，读入各个对角线的染色费用，求出将所有格子染上色的最小总费用。

**注意，同一个格子被重复多次地染色是被允许的。**

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

一个 $m$ 行 $n$ 列的矩形网格共有 $2n+2m-2$。

例：当 $m=4,n=3$ 时，共有 $12$ 条对角线：

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

inputFormat:
输入共 $3$ 行。

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

第二行：共 $m+n-1$ 个整数，描述所有 $\searrow$ 方向的对角线。第 $1$ 个整数表示 $(0,n-1)$ 这个单个的格子，第 $2$ 个整数表示 $(0,n-2),(1,n-1)$ 两个格子，以此类推。

第三行：共 $m+n-1$ 个整数，描述所有 $\nearrow$ 方向的对角线。第 $1$ 个整数表示 $(0,0)$ 这个单个的格子，第 $2$ 个整数表示 $(0,1),(1,0)$ 两个格子，以此类推。

outputFormat: 一个整数表示答案。

hint:
#### 【输入输出样例解释】

**样例 1 解释**

- 在这个情况中，如下的方案可以得到最小花费：

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

总花费 $=1+1+1+1=4$。

**样例 2 解释**

- 对于这个情况，如下的方案可以使花费最小化：

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

总花费 $=3+2+3+3+1+2=14$。

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

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

**本题采用多测试点捆绑测试，共有 7 个子任务**。

- Subtask 1（10 points）：$n,m\le 4$
- Subtask 2（10 points）：$m,n\le 10$
- Subtask 3（10 points）：$m,n\le 20$
- Subtask 4（20 points）：$m,n\le 2\times 10^3$
- Subtask 5（10 points）：$m=1,n\le 2\times 10^5$
- Subtask 6（20 points）：$m=n\le 2\times 10^5$
- Subtask 7（20 points）：无其他限制。

对于所有数据，保证 $1\le m,n\le 2\times 10^5$，每条对角线的染色费用 $\in [1,10^9]$

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

#### 【说明】

原题来自：[eJOI2019](https://www.ejoi2019.si) Problem E. [Colouring	a	rectangle](https://www.ejoi2019.si/static/media/uploads/tasks/colouring-isc.pdf)。

翻译提供：@[```_Wallace_```](https://www.luogu.com.cn/user/61430)。


title: 「SWTR-5」String

description: 小 A 有一个字符串 $t$。他可以进行以下操作：切掉 $t$ 的一个前/后缀，满足切掉的前/后缀为**切割后** $t$ 的子串。小 A 想得到字符串 $s$，请问他最少需要进行多少次操作。无解输出 $-1$。

inputFormat: 两行字符串分别表示 $t,s$。

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

hint:
「样例说明」

样例 $1$：$\texttt{abbabb}\to \texttt{abba}\to \texttt{bba}\to \texttt{ba}$。方案不唯一。

样例 $2$：$\texttt{fxofoxxooffoxooo}\to\texttt{xofoxxooffoxooo}\to\texttt{foxxooffoxooo}\to\texttt{xooffoxooo}\to\texttt{ffoxooo}\to\texttt{ffoxoo}\to\texttt{ffoxo}\to\texttt{ffox}\to\texttt{fox}$。方案不唯一。

「数据范围与约定」

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

- Subtask 1（1 points）：$s=t$。
- Subtask 2（9 points）：$s$ 仅包含字母 $\texttt{a}$。
- Subtask 3（15 points）：$|t|\leq 100$。
- Subtask 4（17 points）：$|t|\leq 500$。
- Subtask 5（18 points）：$|t|\leq 1.5\times 10^3$。
- Subtask 6（15 points）：$|s|=4$，*数据随机。
- Subtask 7（25 points）：无特殊限制。

对于 $100\%$ 的数据：$1 \leq |s| \leq |t| \leq 5\times 10^3$，字符集 $\in[\texttt{a,z}]$。

*数据随机：$s,t$ 字符均随机，字符集 $\in[\texttt{a,c}]$。

**请注意常数优化。**

---

「题目来源」

[Sweet Round 05](https://www.luogu.com.cn/contest/28195) E。
idea & solution：[Isaunoya](https://www.luogu.com.cn/user/96580) & [Alex_Wei](https://www.luogu.com.cn/user/123294)。


title: 【模板】线段树 3（区间最值操作、区间历史最值）

background: 本题是线段树维护区间最值操作与区间历史最值的模板。

description:
给出一个长度为 $n$ 的数列 $A$，同时定义一个辅助数组 $B$，$B$ 开始与 $A$ 完全相同。接下来进行了 $m$ 次操作，操作有五种类型，按以下格式给出：

- `1 l r k`：对于所有的 $i\in[l,r]$，将 $A_i$ 加上 $k$（$k$ 可以为负数）。
- `2 l r v`：对于所有的 $i\in[l,r]$，将 $A_i$ 变成 $\min(A_i,v)$。
- `3 l r`：求 $\sum_{i=l}^{r}A_i$。
- `4 l r`：对于所有的 $i\in[l,r]$，求 $A_i$ 的最大值。
- `5 l r`：对于所有的 $i\in[l,r]$，求 $B_i$ 的最大值。

在每一次操作后，我们都进行一次更新，让 $B_i\gets\max(B_i,A_i)$。

inputFormat:
第一行包含两个正整数 $n,m$，分别表示数列 $A$ 的长度和操作次数。

第二行包含 $n$ 个整数 $A_1,A_2,\cdots,A_n$，表示数列 $A$。

接下来 $m$ 行，每行行首有一个整数 $op$，表示操作类型；接下来两个或三个整数表示操作参数，格式见【题目描述】。

outputFormat: 对于 $op\in\{3,4,5\}$ 的操作，输出一行包含一个整数，表示这个询问的答案。


title: [eJOI2019] 塔

description:
Jernej 在晚上感到很无聊，于是他发明了一个游戏。他想要用数字卡片生成一个塔。一开始，他在一张卡片上写下了一个数字 $1$。

Jernej 可以再另一张写下一个新的数字并放在塔顶。 **这个新的数字必须等于之前塔中某一连续段的数字之和** 。也就是说，假设现在塔中已有 $n$ 个数字，你可以任意选取塔中的一段 $[l,u]$ ，并对这一段求和，将得到的新数字添加至塔顶，其中 $1\le l\le u\le n$。

Jernej 想要生成 $T$ 个塔（相当于多组询问），每个塔顶都是 $T$ 个可能不同的他想要的数字。你需要帮助他求出生成这些塔的最小步数及其方案。

inputFormat:
第一行：一个整数 $T$，表示塔的个数；

接下来 $T$ 行，一行一个整数 $q$，表示现在 Jernej 想生成一个塔顶数字为 $q$ 的塔。

保证有解。

outputFormat:
对于每个询问 $q$：

- 输出一行，包含一个整数 $s$ （$0\le s\le 10^3$），表示最小步数。
- 接下来 $s$ 行，每行两个由空格隔开的整数 $l,u$，表示建生成塔的方案（操作时间早的先输出）。

hint:
#### 【Special Judge 计分标准】

本题共 $10$ 个测试点。对于每个测试点，计分规则如下：

- 对于测试点中的任意一个塔，如果你的程序输出的 **最小步数** 与标准答案 **均一致** ，那么这个测试点你会得到 $10$ 分。
- 对于测试点中的任意一个塔，如果你的程序输出的答案是错误的，那么得 $0$ 分（评测时如果发现输出不完全可能会得到 UKE）。
- 如果你的答案并 **不是最优解但不是错误的** ，那么对于该测试点中的第 $i$ 个塔，你得到的分数为 $\text{score}_i =1+\dfrac{\text{minimum steps}}{\text{solution steps}}\times 7$，其中 $\text{minimum steps}$ 表示正确答案的最小步数，$\text{solution steps}$ 表示你的程序输出的答案。最终这个测试点的得分为 $\min\limits_{i\in [1,T]} \{\text{score}_i\}$。向上取两位小数。

#### 【输入输出样例解释】

**询问 1 解释**：

- Jernej 想要生成造一个塔顶数为 $2$ 的塔。起初塔为 $\{1\}$（左边表示塔底，右边表示塔顶）；
- 第一步，选取子段 $[1,1]$，对 $\{1\}$ 中的所有元素求和，得到 $1$，现在塔为 $\{1,1\}$；
- 第二步，选取子段 $[1,2]$，对 $\{1,1\}$ 中的所有元素求和，得到 $2$，现在塔为 $\{1,1,2\}$。此时已经达到了询问的要求。

**询问 2 解释**：

- 要生成塔顶为 $3$ 的塔不止一种方法。除了样例输出的一种之外，下面的也是正确答案：

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

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

**本题采用多测试点捆绑测试，共有 7 个子任务**。

- Subtask 1（1 test case - 10 points）：$T\le 10,q\le 10$。
- Subtask 2（1 test case - 10 points）：$T\le 20,q\le 20$。
- Subtask 3（1 test case - 10 points）：$T= 100,q\le 100$。
- Subtask 4（1 test case - 10 points）：$T= 10^3,q\le 10^4$。
- Subtask 5（1 test case - 10 points）：$T= 10^3,q\le 10^5$。
- Subtask 6（1 test case - 10 points）：$T= 10^3,q\le 10^6$。
- Subtask 7（1 test case - 10 points）：$T= 10^3,q\le 10^9$。
- Subtask 8（1 test case - 10 points）：$T= 10^3,q\le 10^{12}$。
- Subtask 9（2 test case - 20 points）：无其他限制。

对于所有数据，保证 $1\le T\le 10^3,1\le q\le 10^{18}$

#### 【说明】

原题来自：[eJOI2019](https://www.ejoi2019.si) Problem D. [Tower](https://www.ejoi2019.si/static/media/uploads/tasks/tower-isc.pdf)。

翻译提供：@[```_Wallace_```](https://www.luogu.com.cn/user/61430)


title: [JXOI2012] 奇怪的道路

description:
小宇从历史书上了解到一个古老的文明。这个文明在各个方面高度发达，交通方面也不例外。考古学家已经知道，这个文明在全盛时期有 $n$ 座城市，编号为 $1,2,...,n$。$m$ 条道路连接在这些城市之间，每条道路将两个城市连接起来，使得两地的居民可以方便地来往。一对城市之间可能存在多条道路。

据史料记载，这个文明的交通网络满足两个奇怪的特征。

1. 这个文明崇拜数字 $k$，对于任何一条道路，设它连接的两个城市分别为 $u$ 和 $v$，则必定满足 $1 \le \left\vert {u-v}\right\vert \le k$。
2. 任何一个城市都与恰好偶数条道路相连（ $0$ 也被认为是偶数）。

不过，由于时间过于久远，具体的交通网络我们已经无法得知了。小宇很好奇这 $n$ 个城市之间究竟有多少种可能的连接方法，于是她向你求助。

两种可能的连接方法不同当且仅当存在一对城市，它们间的道路数在两种方法中不同。

在交通网络中，有可能存在两个城市无法互相到达。

方法数可能很大，你只需要输出方法数模 $10^9 + 7$ 后的结果。

inputFormat: 输入共一行，有三个整数 $n,m,k$。

outputFormat: 输出一个整数，表示方案数模 $10^9 + 7$ 后的结果。

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

- 对于 $100\%$ 的数据，满足 $1 \le n,m \le 30$，$1 \le k \le 8$。


title: [集训队互测 2019] 神树大人挥动魔杖

background:
### 警告：恶意提交本题将被封号。

神树大人想要做一根魔杖，这样他就可以使用「鸽子固定咒」把神 J 固定住了。

第一天，神树大人在自己身上找了一根木头。神树大人使用了树顶上连神 J 都够不到的树枝。由于这根木头不能被凡人所理解，所以神树大人称它为「迷之木」。

第二天，神树大人需要为施法创造环境。于是神树大人花了数小时造了一个完整的魔法世界，由于这个世界不能被凡人所理解，所以神树大人称它为「大象世界」。

第三天，神树大人需要对迷之木附魔。于是神树大人写了一段咒语并让它在大象世界里运行，由于这段咒语不能被凡人所理解，所以神树大人称它为「花之语」。

神树大人邀请神 J 来到大象世界游玩，神 J 迟了若干天才到。神 J 见神树大人嘴里念念有词，便问道：「你在干什么？」神树大人立即掏出迷之木，对准神 J 大喊道：

「system call Joker remove pigeon protection！system call Joker Δεσμευτική！system call Joker ログアウト禁止！...」

神 J 立刻被固定住了。神树大人很满意，于是离开了大象世界，并命令神 J 留在里面做题。由于这些题不能被凡人所理解，所以神 J 只把简化版给了你。

description:
有一排 $n$ 个格子，有 $m$ 个人，初始都在 $1$ 号格。

每个人可以选择往前跳一格或者跳两格，跳一格的方法数为 $p$，跳两格的方法数为 $q$，跳出 $n$ 个格子则停止，注意在第 $n$ 个格子仍然能选择跳一或两格。

你需要计算有多少种方法使得每个格子都至少被一个人踩过。

inputFormat: 第一行输入四个整数，$n,m,p,q$。


title: [COCI2014-2015#3] DOM

description:
在一个养老院里，$n$ 位老人正在看电视。这个电视节目由 $m$ 个频道组成，数字从 $1$ 到 $m$ 不等。每个老人都有自己喜欢和讨厌的电视频道。

如果电视正在播放某个老人讨厌的频道，他会站起来，慢慢走向电视机，把频道换成他最喜欢的，然后回到舒适的椅子上。如果有多个老人讨厌现在的频道，他们中最年轻的会站起来，把频道换成他最喜欢的，其余的人都会坐着。

当然，在一次更换频道后，另一位老人可能会觉得新频道无法忍受，所以他会更换该频道。鉴于老人们很顽固，这种情况可能会无限期地持续下去。

对于老人们最喜欢和讨厌的频道以及电视上的初始频道，确定老人们保持快乐所需的频道更改次数。

inputFormat:
输入的第一行包含三个整数 $n,m$ 和 $p$，分别表示养老院里老人的数量，  电视频道的数量和在电视上显示的初始频道。

以下 $n$ 行中的每一行都包含两个整数 $a_i$ 和 $b_i$，分别表示每个老人最喜欢和最讨厌的频道。

老人的输入顺序是按年龄从小到大排列的。

outputFormat: 仅一行，输出必须包含所需的频道更改数。如果更改无限期地继续，则输出 `-1`。

hint:
#### 样例输入输出 1 解释
最初，电视上是 $2$ 频道。这个频道惹恼了最年轻和最年长的老人，所以最年轻的人站起来，把频道他最喜欢的改成 $1$ 频道，这样每个人都可以一起看 $1$ 频道。
#### 数据规模与约定

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


title: 「SWTR-5」Chain

description:
给定 $n$ 个点，$m$ 条边的有向无环图。不保证图连通。

$q$ 次询问，每次给出 $k$ 和 $k$ 个互不相同的数 $c_i$，求出如果去掉这 $k$ 个点，整个有向无环图将剩余多少条链。答案对 $10^9+7$ 取模。**每次询问独立。**

- “链”的定义是：我们设一条长度为 $p$ 的链的路径为 $w_0\to w_1\to\cdots\to w_{p-1}\to w_p$，则应满足 $w_0$ 入度为 $0$，$w_p$ 出度为 $0$。你可以将其理解为一条食物链。

- 两条链是“不同的”，当且仅当它们的长度不同，或者经过的点集不同。

- **需要特别注意的是，删去某些点后新产生的链不计入答案。** 例如 $1\to 2\to 3\to 4$ 一图中，有 $1$ 条链 $1\to 2\to 3\to 4$。如果去掉 $2$ 号点，则剩余 $0$ 条链。

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

接下来 $m$ 行，每行两个整数 $u,v(u\neq v)$，表示 $u\to v$ 有一条有向边。

第 $m+2$ 行一个整数 $q$，表示询问个数。

接下来 $q$ 行：
- 每行先是一个整数 $k$，表示去掉的点的个数。
- 接下来 $k$ 个整数 $c_i$，表示去掉的点的编号。

outputFormat: 共 $q$ 行，每行表示该次询问答案对 $10^9+7$ 取模后的值。

hint:
「样例 $1$ 说明」

DAG 如图：

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

询问 $1$：如果去掉 $2,4,6$，则剩余 $1$ 条链：$3\to 5$。

询问 $2$：如果去掉 $4,6$，则剩余 $3$ 条链：$3\to 5$，$3\to 2\to 5$，$3\to 7\to 2\to 5$。

询问 $7$：如果去掉 $6$，则剩余 $5$ 条链：$3\to 5$，$3\to 2\to 5$，$3\to 7\to 2\to 5$，$3\to 1\to 4\to 5$，$3\to 7\to 4\to 5$。

「数据范围与约定」

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

- Subtask 1（1 point）：给定的图是一条链。
- Subtask 2（14 points）：$n,q\leq 10$。
- Subtask 3（20 points）：$q\leq 10^3$。
- Subtask 4（17 points）：$k=1$。
- Subtask 5（18 points）：$k=2$。
- Subtask 6（30 points）：无特殊限制。

对于 $100\%$ 的数据：$2\leq n\leq 2\times 10^3$，$1\leq m\leq \min(\frac{n\times(n-1)}{2},2\times 10^4)$，$1\leq q\leq 5\times 10^5$。
所有询问满足：$1\leq \sum k\leq 2\times 10^6$，$0\leq k\leq \min(n,15)$，$1\leq c_i\leq n$。保证 $c_i$ 互不相同。

**本题轻微卡常，请注意 IO 优化。**

---

「题目来源」

[Sweet Round 05](https://www.luogu.com.cn/contest/28195) D。
idea & solution：[Alex_Wei](https://www.luogu.com.cn/user/123294)。


title: [USACO06OPEN] County Fair Events S

background: 题目是经过简写保证不改变原有题意的题目。

description:
FJ 参加活动。

他想参加尽可能多的 $N$ 个活动，参加完某个之后可以立刻参加下一个。

给定 FJ 可参加的活动列表、其开始时间 $T$ 和持续时间 $L$ ，求 FJ 可以参加的最大活动数。

FJ 每个活动都不会提早离开。

inputFormat:
第一行有一个整数 $N$。

第二到 $N+1$ 行：每行包含两个用空格分隔的整数 $T$ 和 $L$ ，意义如上述。

outputFormat: 输出仅一行，FJ 最多能参加几个活动。


title: [USACO06OPEN] The Milk Queue G

background: 题目是经过简写保证不改变原有题意的题目。

description:
每早，FJ 的 $N$ 头奶牛都排成一列挤奶．一个个进到仓库，为提高速率，FJ 把整个挤奶过程划分成两道工序，FJ负责实行第一道，第二道由 Rob 完成。

如果某头牛先于另一头牛开始进行第一道工序，那么她同样先开始第二道工序。

FJ 发现，如果奶牛们按某种顺序排队进行挤奶，那么可能会在排队等待上多花很多的时间。比如，如果 FJ 要花很长时间才能完成某头奶牛的第一道工序，那么 Rob 就会浪费一段时间。反之如果 FJ 的工作完成得太快，Rob 面前会有很多奶牛排起长队。

请你计算按最优方式排队后最少需要多少时间才能挤完奶。对于每头奶牛，数据提供第一道工序的时间 $A_i$ 和第二道工序的时间 $B_i$。

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

接下来 $N$ 行，每行两个整数表示第 $i$ 头牛的 $A_i$，$B_i$ 值。

outputFormat: 输出按最优方案排队后挤奶所需的最短时间。

hint:
#### 样例说明

把奶牛们按照 3，1，2  的顺序排队，这样挤奶总共花费 16 个单位时间．

$1\le N\le 25000$

$1\le A_i,B_i\le 2\times 10^4$


title: [USACO06OPEN] The Climbing Wall S

background: 题目是经过简写保证不改变原有题意的题目。

description:
Bessie 要爬墙，墙宽 $30000$ ，高 $H$，墙上有 $F$ 个不同的落脚点 $(X,Y)$。

$(0,0)$ 在左下角的地面。任意落脚点至少相距 $300$。至少有一条路可以上去，Bessie 每次最多爬 $1000$ 个单位距离，且可以向任意方向爬行。

一旦她到达了一个高度距离 $H$ 不到 $1000$ 的落脚点，可以直接到墙顶。Bessie 的起点可以在任一高度不超过 $1000$ 的落脚点上。问Bessi爬到顶端的最少次数。

本题距离指**欧几里得距离**。

inputFormat:
第一行有两个以空格分隔的整数 $H$ 和 $F$ 。

第二到 $F+1$ 行，每行是落脚点的坐标 $(X,Y)$，$X$ 是距攀岩墙左边的距离，$Y$ 是离地面的距离。

outputFormat: 输出仅一个整数，Bessie 到达攀岩墙顶部所需的最少步数。


title: 「EZEC-1」出题

background: 你是一个毒瘤出题人。

description: 已知你有 $n$ 道毒瘤题，已经出好了题面，但数据还没出好。你还剩下 $m$ 的时间，每道题的毒瘤程度为 $a_{i}$，出数据的时间是 $x_{i}$，你有 $k$ 个老师，每个老师可以把一道题的毒瘤程度翻倍（每道题目最多被翻倍一次）。你的父母由于坚决反对你出公开赛，抢走了你的一道题，现在老师和父母的行动你都可以控制，但每位老师和父母的行为必须执行，请问你要怎么做，才能使出的题毒瘤程度之和最大？

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

接下来 $n$ 行，每行 $2$ 个整数，分别是 $a_{i},x_{i}$。

outputFormat: 一个整数，最大的毒瘤程度之和。

hint:
【样例解释】

样例 $1$ ：

你控制你的父母拿走 $T1$ ，然后配 $T2$ 和 $T3$ 的数据，同时将 $T2$ 的毒瘤值翻倍，所以毒瘤值最大是 $15$

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

【数据范围】

对于 $30\%$ 的数据，$ 0 \le x_{i} \le m $，$0 \le m \le 100 $，$2 \le n \le 10$，$ k<n$。

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

对于 $100\%$ 的数据，$0 \le a_{i} \le 1000$，$ 0 \le x_{i} \le m $，$0 \le m \le 1000 $，$0 \le n \le 100$，$ k<n$。

upd in 2020.7.6：添加一组 hack 数据。


title: [SBCOI2020] 一直在你身旁

background:
转眼间，又到春天...
站在这里，我才发现，
原来，我的心，
已与那座被光玉守护的小镇相连。
......
“又到了一年春天啊...”
“看来，你已经准备留在这里了呢。”
“其实，我也没有什么远大的理想，只是努力地维持着现状...”
“不过，只要能实现自己的梦想，这又有什么关系啊...”
“但是现在，我真的是非常的开心。就像你说的那样，找到了很多快乐的事情...”
“我也和你一样，处在同一个世界。世界上没有一成不变的事物。
所以只要以其他方式找到自己的快乐就行了...”
“对啊，是时候开始新的生活了呢......”

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

“你对这个小镇真是执着呢...”
“因为，这里满是我不想忘记的回忆啊...”

description:
回到这座小镇后，她的新工作是维修电线。
现在，有一根电线坏了。已知电线长度可能为 $1,2,\cdots,n$ 中的一个数。现在，她需要知道电线的长度。
她可以花费 $a_i$ 块钱购买长度为 $i$ 的电线。购买这根电线后，她能知道所需要的电线长度是否 **大于** $i$。
保证 $a_1 \le a_2 \le \cdots \le a_n \le 10^9$。
问她至少要花多少钱才能保证知道需要电线的长度。

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

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

接下来，每组数据，一行一个整数 $n$，接下来一行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

outputFormat: $T$ 行，每行输出一个答案。

hint:
【样例解释】

买一根长度为 $1$ 的电线，就能知道需要的长度是否大于 $1$，也就能确定是 $1$ 还是 $2$，所以答案就是 $1$。

大样例[链接](https://www.luogu.com.cn/paste/csusv11e)。

【数据范围】

本题捆绑测试，共有 $4$ 个子任务。

$(Subtask 1)(10\%)$，$n \le 15$。

$(Subtask 2)(10\%)$，$n \le 500$。

$(Subtask 3)(30\%)$，$n \le 2000$。

$(Subtask 4)(50\%)$，没有任何额外限制。

对于100%的数据点, $ 1 \le n,\sum n \leq 7100,T \leq 500 $。$\sum n$ 表示所有数据中 $n$ 的和。


title: 「Wdoi-1」加密通信

background:
自月战之后，八云紫在槐安通道中设立了一重结界，使得从地面传向月都的信息全部会被拦截和破译。

为了维持正常的通讯，八意永琳同月兔们研究出了一种全新的加密方式。

description:
首先，八意永琳会写出需要被加密的明文 $A$ ，此段明文由 $n-1$ 个正整数构成。

之后，她会构造出一个由 $n$ 个**质数**构成的密文 $B$，满足对  $\forall  i \in [1,n),B_i \times B_{i + 1} = A_i$。

为了提高信息的利用率，八意永琳规定 $B$ 中出现的所有质数的值必须在 $[1,M]$ 范围内。

inputFormat:
第一行一个整数 $T$ , 表示需要被加密的明文的组数。

对于每组明文：

第一行两个整数 $n,M$ ，代表明文的长度$+1$，也即所求密文的长度和可出现质数的最大值。

接下来一行 $n - 1$ 个由空格隔开的正整数，代表明文 $A$。

outputFormat:
对于每组明文，均输出一行：

- 若有解，输出**任意一组**合法密文 $B$ 即可，密文中的 $n$ 个质数以空格隔开。

- 若无解，输出 `-1`。

hint:
#### 数据规模

- 对于 $20\%$ 的数据，$n \le 5,M \le 10$。

- 对于 $40\%$ 的数据，$A_i \le 10 ^ {12}$。

- 对于 $70\%$ 的数据， $A_i \neq A_{i + 1}$。

- 对于$100\%$的数据，$3 \le n \le 10 ^ 5$，$1 \le A_i,M \le 10 ^ {18}$，$1 \le T \le 5$。

- 以上几档部分分呈**包含关系**，$100\%$ 包含 $70\%$，$70\%$ 包含 $40\%\ \ldots\ldots$以此类推。

#### 数据保证：

- 若不考虑 $b_i$ 在 $[1,M]$ 范围内的条件，必然有至少一组合法解。

- 有至少一对 $(i,j)$，使得 $A_i \neq A_j$。

#### 后置资料

**本段资料与答题相关性不大**。

[百度百科 - 质数](https://baike.baidu.com/item/%E8%B4%A8%E6%95%B0/263515?fr=aladdin)


title: 「Wdoi-1」幻能采集

background:
幻能是一种全新的能源。

**注：点击"展开"阅读体验更佳**

description:
在图 $G=\{V,E\}$ 中，对于大小为 $C$ 的点集 $S\subset V$，若有一点编号为 $v$，且以 $S$ 中的每一个点为起点，$v$ 为终点能够选择出 $C$ 条不经过重边的路径，则称 $v$ 为点集 $S$  的"聚焦点"。

幻想乡的地图可以抽象为一棵含有 $n$ 个结点的有边权无根树(一条路径的长度定义为路径中所有边的边权之和)，而贤者们在树上 $c$ 个结点设置了幻能采集器。

为了幻能的充分利用，贤者们规定对于这 $c$ 个结点的 **大小至少为 $2$ 且不超过给定常数 $k$** 任意子集 $S$ ，在树上所有 $S$ 的"聚焦点"上都应设立一个只用于接受 $S$ 传递幻能的能量中枢。记其中的某个"聚焦点"为 $v$，则建立此能量中枢的代价按如下方式计算：

$$W_{S,v}=\prod_{u \in S}d(u,v)$$

其中，$d(u,v)$ 表示编号为 $u,v$ 的两点间的最短距离。

由于计划可能存在变化，贤者们设计了 **多组** 设置 $c$ 个幻能采集器的方案，而每个方案对应的常数 $k$ 也 **不一定** 相同。

现在，对于每个方案 $i$，贤者们想进行 $q_i$ 次询问，每次查询 若只建立 $x_{ij}$ 点应建的所有能量中枢，需要花费的总代价是多少(总代价等于建立每个能量中枢的代价之和)。由于幻想乡没有计算机，所以她们到外界找到了精通 $\text{OI}$ 的你来帮忙。

当然，由于答案可能很大，你只需要输出总代价 $\bmod\ 998244353$ 后的结果即可。

inputFormat:
第一行两个整数 $n,D$，表示结点数和某参数

之后 $n-1$ 行每行三个整数 $u,v,w$，表示一条 $u,v$ 间长度为 $w$ 的无向边

下一行一个整数 $T$，表示设置幻能采集器的方案个数

对于每组方案：

第一行两个整数 $c,k$，表示幻能采集器的个数和子集的大小上限

第二行 $c$ 个整数，表示幻能采集器所处的 $c$ 个结点，保证这 $c$ 个整数互不相同

第三行一个整数 $q$，表示对于该方案的询问的个数

之后 $q$ 行每行一个整数 $x$，表示查询只建立 $x$ 处所有中枢的代价和。

**因为某些原因，实际查询的 $x'=(x-1+D\times lastans)\bmod n+1$**，其中 $lastans$ 表示上一次查询的答案，第一次查询时 $lastans=0$，在改变方案后 $lastans$ **不清零**

outputFormat: 若干行，每行一个整数表示查询的答案对 $\text{998244353}$ 取模后的结果


title: [SDOI2012] 最近最远点对

description: 给定平面直角坐标系上的 $n$ 个点，分别求出距离最近的两个点的距离和距离最远的两个点的距离。注意，距离为直线距离。

inputFormat:
第一行一个整数，$n$。
接下来 $n$ 行每行两个非负浮点数，$x_i$,$y_i$，表示第 $i$ 个点的 X 坐标与 Y 坐标。

outputFormat: 总共一行，两个浮点数，为最短距离与最长距离。误差不超过 $0.01$ 视为正确。

hint:
- 对于 $30\%$ 的数据，$n\leq 2000$；
- 对于 $70\%$ 的数据，$n\leq 20000$；
- 对于 $100\%$ 的数据，$0 \lt n\leq 10^5$，输入数据中所有数均为不超过 $10^9$ 的非负数。


title: [COCI2014-2015#3] STROJOPIS

description:
正确的打字正成为文化的重要组成部分。如果你仍然没有使用所有的十根手指来打字，你必须重新学习打字——然后你会打字更快，感觉更舒适和愉快。

有很多网站教你正确打字。下图描述了基本原理：用同一个指针按所需的键是同一颜色的。黄色键需要用小指按下，蓝色键需要用无名指，绿色键需要用中指，红色键需要用食指。自然，左手按键盘的左侧（从 `5`、`T`、`G`、`B` 开始向左的键），右手按右侧（从 `6`、`Y`、`H`、`N` 开始向右的键），拇指负责空格。

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

您的任务是输出每根手指（拇指除外）正确输入给定字符串的分别按下的次数。

inputFormat: 仅一行一个字符串 $s$。字符串不包含空格，只包含上面图像中包含的字符。

outputFormat: 输出必须由八行组成，每行一个整数，表示**从左到右**观察到的每个手指的按键次数（拇指除外）。

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

令 $|s|$ 表示输入字符串的长度，则对于 $100\%$ 的数据，有 $1\le |s|\le 50$。


title: 「EZEC-1」甜品

background:
小 X 最喜欢甜品了！

马上就要开学了，但是小 X 并没有写完作业，他十分悲伤地走在街上。忽然，他发现了一家新开的甜品店，悲伤的心情一消而散，随即信步走进甜品店。

description:
小 X 发现，店里总共有 $n$ 种甜品，而他想挑选其中的 $k$ 种，并按照一定的顺序来品尝。

每种甜品都有一个美味值 $a_i$，小 X 吃甜品的顺序是有讲究的，他不想使连续两种甜品之间的美味值相差太小，不然他将无法品味出两种甜品之间的差别；但他也不想使连续两种甜品之间的美味值相差太大，否则他将受不了这巨大的味觉冲击。他十分纠结，不知道该如何选择，于是他向你求助。

你要从 $n$ 种甜品中选择 $k$ 种甜品，并且第 $i$  种甜品（ $i \in [ 2 , k ] $）需要满足如下两个条件：

- 第 $i$ 种甜品的美味值必须**大于等于**第 $i-1$ 种甜品的 $l$ 倍。

- 第 $i$ 种甜品的美味值必须**小于等于**第 $i-1$ 种甜品的 $r$ 倍。

问现在你有多少种方案？$k$ 种甜品的美味值之和最大为多少？

因为答案太大，所以两个问题你都需要对 $1000000007$($10^9+7$)  取模。

#### 注：方案总数只考虑 $k$ 种甜品的搭配，不考虑排列顺序。即若存在某 $k$ 种甜品，按照不同顺序品尝都满足条件，仍然只算一种方案。

inputFormat:
第一行：四个正整数：$n,k,l,r $。

第二行：$n$ 个正整数：$a_i$。

outputFormat:
第一行一个整数，表示总方案数。

第二行一个整数，表示美味值之和的最大值。

若没有答案，均直接输出 $0$ 。


title: [IOI2000] 邮局 加强版 加强版

background:
> 看到你时总是感觉清风徐徐,
>
> 本以为和你相识不会是偶遇,
>
> 奈何你犹如过客、化作秋雨,
>
> 只是经过我生命的一瓢柳絮,
>
> 从不会真正有童话似的结局.
>
> 我静静地写尽这些躁言丑句,
>
> 本以为可以稍稍地缓解抑郁.
>
> 却是徒增一场悲伤的脑补剧.
>
> 你问我为什么说这么多?
>
> 因为这题是加强版的 [IOI2000]邮局.

description:
高速公路旁边有 $n$ 个村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。两个位置之间的距离是其整数坐标差的绝对值。

现在要建立  $m$ 个邮局，邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

inputFormat:
第一行包含两个整数，分别表示村庄的数量 $n$ 和邮局的数量 $m$。

第二行共 $n$ 个整数，表示每个村庄的坐标，第 $i$ 个整数表示第 $i$ 个村庄的坐标 $a_i$。

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

tags: 凸完全单调性, wqs 二分


title: [USACO3.1] 形成的区域 Shaping Regions

description:
$n$ 个不同颜色且不透明的长方形被放在一张宽为 $a$ 长为 $b$ 的白纸上。它们的边于白纸的边缘平行，且所有的长方形都放置在白纸内。

现在将他们重叠，重叠后会出现不同形状的各种颜色，你需要求出每种颜色的面积。

白纸的左下角的坐标为原点 $(0,0)$，且坐标轴平行于白纸边缘。

inputFormat:
输入数据共 $n+1$ 行。

第一行三个整数，$a,b,n$。

第二到 $n+1$ 行，每行五个整数，$llx,lly,urx,ury,color$，表示一个长方形的左下角和右上角的坐标以及颜色编号。**注：颜色 1 和底部白纸的颜色相同**。

outputFormat: 一个所有能被看到颜色和该颜色的总面积的汇总，一行内格式为编号和面积，即使颜色的区域不是连续的，仍可以输出，并且按 $color$ 的增序排序输出，不要输出没有区域的颜色。

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

白纸经过各层覆盖后，各种颜色的面积分别为 $91,84,187,38$。

---

**数据规模与约定**

对于 $100\%$ 的数据，$1 \leq n \leq 10^3$，$1 \leq a,b \leq 10^4$，$1 \leq llx,lly,urx,ury \leq a,b$，$1 \leq color \leq n+1$。


title: [ICPC2019 WF] Dead-End Detector

description:
The council of your home town has decided to improve road sign placement,especially for dead ends. They have given you a road map, and you must determine where to put up signs to mark the dead ends. They want you to use as few signs as possible.

The road map is a collection of locations connected by two-way streets. The following rule describes how to obtain a complete placement of dead-end signs. Consider a street $S$ connecting a location $x$ with another location. The $x$-entrance of $S$ gets a dead-end sign if, after entering $S$ from $x$, it is not possible to come back to $x$ without making a U-turn. A U-turn is a 180-degree turn immediately reversing the direction.

To save costs, you have decided not to install redundant dead-end signs, as specified by the following rule. Consider a street $S$ with a dead-end sign at its $x$-entrance and another street $T$ with a dead-end sign at its $y$-entrance. If, after entering $S$ from $x$, it is possible to go to $y$ and enter $T$ without making a U-turn, the dead-end sign at the $y$-entrance of $T$ is redundant. See Figure E.1 for examples.

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

Figure E.1: Illustration of sample inputs, indicating where non-redundant dead-end signs are placed.

inputFormat: The first line of input contains two integers $n$ and $m$, where $n$ $(1 \leq n \leq 5\times10^5)$ is the number of locations and $m$ $(0 \leq m \leq 5 \times 10^5)$ is the number of streets. Each of the following $m$ lines contains two integers $v$ and $w$ $(1 \leq v \lt w \leq n)$ indicating that there is a two-way street connecting locations $v$ and $w$. All location pairs in the input are distinct.

outputFormat: On the first line, output $k$, the number of dead-end signs installed. On each of the next $k$ lines, output two integers $v$ and $w$ marking that a dead-end sign should be installed at the $v$-entrance of a street connecting locations $v$ and $w$. The lines describing dead-end signs must be sorted in ascending order of $v$-locations,breaking ties in ascending order of $w$-locations.

translation:
有一张 $n$ 个点 $m$ 条边的简单无向图。

如果走过一条边 $u→v$ 后，不掉头无法返回到 u，这条边就是对 $u$ 来说的“死路”。

你需要对每个死路标记路标，但是有的路标是多余的。

如果从一个死路 $u→v$ 开始可以不掉头地走到另一个死路 $u' → v'$，那么后者 $u' → v'$ 就是多余的。

最后问要标记多少路标，输出每对 $u→v$，按照 $u$ 为第一关键字，$v$ 为第二关键字排序。

第一行输入 $n$ , $m$ ，后 $m$ 行每行两个整数 $u$ , $v$ 。

输出的第一行是要标记的路标数 $k$ ，然后 $k$ 行每行一对题目所说的死路 ： $u→v$ （不要输出“$→$”）。

hint: Source: ICPC World Finals 2019 Problem E.


title: [ICPC2019 WF] Directing Rainfall

description:
Porto and the nearby Douro Valley are famous for producing port wine. Wine lovers from all over the world come here to enjoy this sweet wine where it is made. The International Consortium of Port Connoisseurs (ICPC) is organizing tours to the vineyards that are upstream on the Douro River. To make visits more pleasurable for tourists, the ICPC has recently installed sun tarps above the vineyards. The tarps protect tourists from sunburn when strolling among the vines and sipping on a vintage port.

Unfortunately, there is a small problem with the tarps. Grapes need sunlight and water to grow. While the tarps let through enough sunlight, they are entirely waterproof. This means that rainwater might not
reach the vineyards below. If nothing is done, this year's wine harvest is in peril!

The ICPC wants to solve their problem by puncturing the tarps so that they let rainwater through to the vineyards below. Since there is little time to waste before the rainy season starts, the ICPC wants to make the minimum number of punctures that achieve this goal. We will consider a two-dimensional version of this problem. The vineyard to be watered is an interval on the $x$-axis, and the tarps are modeled as line segments above the $x$-axis. The tarps are slanted, that is, not parallel to the $x-$ or $y-$ axes (see Figure F.1 for an example). Rain falls straight down from infinitely high. When any rain falls on a tarp, it flows toward the tarp's lower end and falls off from there, unless there is a puncture between the place where the rain falls and the tarp's lower end—in which case the rain will fall through the puncture instead. After the rain falls off a tarp, it continues to fall vertically.

This repeats until the rain hits the ground (the $x$-axis).

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

For legal reasons you have to ensure that at least some of the rain that reaches the vineyard originated from directly above the vineyard. This is to prevent any vineyard from stealing all their rain from neighboring vineyards (see the second sample input for an example).

inputFormat:
The first line of input contains three integers $l$ , $r$ and $n$, where $(l,r)$ $(0 \leq l \lt r \leq 10^9)$ is the interval representing the vineyard and $n$ $(0 \leq n \leq 5 \times 10^5)$ is the number of tarps. Each of the following $n$ linesdescribes a tarp and contains four integers $x_1, y_1, x_2, y_2$ , where $(x_1, y_1)$ is the position of the tarp's lowerend and $(x_2, y_2)$ is the position of the higher end $(0 \leq x_1, x_2 \leq 10^9 , x_1≠x_2, $ and $ 0 \lt y_1 \lt y_2 \leq 10^9)$.
The $x$-coordinates given in the input ($l$, $r$, and the values of $x_1$ and $x_2$ for all tarps) are all distinct. Thetarps described in the input will not intersect, and no endpoint of a tarp will lie on another tarp.

outputFormat: Output the smallest number of punctures that need to be made to get some rain falling from above the vineyard to the vineyard.

translation:
波尔图和附近的杜罗河谷以生产波尔图葡萄酒而闻名。来自世界各地的葡萄酒爱好者来到这里，在这里品尝酿制的甜酒。国际港口鉴赏家协会（ICPC）正在组织参观杜罗河上游的葡萄园。为了让游客更愉快地参观，ICPC最近在葡萄园上方安装了防晒布。当游客漫步在藤蔓间，在一个古老的港口啜饮时，防水布可以保护他们免受晒伤。

不幸的是，防水布有一个小问题。葡萄生长需要阳光和水。虽然防水油布能让足够的阳光透过，但它们是完全防水的。这意味着雨水可能无法到达下面的葡萄园。如果不采取任何行动，今年的葡萄酒收成将岌岌可危！

ICPC希望通过刺穿防水布来解决他们的问题，这样他们可以让雨水通过下面的葡萄园。由于雨季开始前几乎没有时间可以浪费，ICPC希望实现这一目标的穿刺次数最少。我们将考虑这个问题的二维版本。要浇水的葡萄园是xx轴上的一个间隔，防水布被建模为xx轴上方的线段。防水布是倾斜的，也就是说，与x-x不平行−还是y-y−轴（示例见图F.1）。雨从无限高的地方直下。当任何雨水落在防水油布上时，雨水会流向防水油布的下端并从那里落下，除非雨水落下的地方和防水油布的下端之间有一个小孔，在这种情况下，雨水会通过小孔落下。雨水从防水布上落下后，继续垂直下落。

这将重复进行，直到雨水落在地面上（xx轴）。

hint: Source: ICPC World Finals 2019 Problem F: Directing Rainfall.


title: 「EZEC-1」越狱

background:
由于监狱长 PF 的疏忽，罪犯小 E 找到了机会越狱。

然而，不学无术的小 E 不懂得保密。PF 很快发现了他的计划，并对他展开了追捕。

因为小 E 自己造船，而狱长 PF 坐的是官方的船，所以在每条航道上的表现不一样，通过时间可能不同。具体见输入格式。

为了不饿肚子，小 E 准备买一个包来装食物。

description:
小 E 的逃跑路线可以被看作是在 $n$ 个岛屿上，这些岛屿由 $n-1$ 条航线两两相连。

每个岛上都有足够的补给。**假设他每在海上航行一天，就要花费一个单位的食物**。黑心老板规定，**能装 $k$ 单位的食物的背包将会卖 $k$ 万元**。

PF 可以命令在任意两个**通过时间不超过 $d$**，**并且岛 $v$ 到岛 $u$ 的航线上至少有 $q$ 个岛屿**（**不包括 $u$ 和 $v$**）的岛屿 $u$ 与 $v$ 之间建立一条双向航线，通过这条航线的时间为 $\left\lfloor \dfrac{time(u \to v)}{2}\right\rfloor$。由于经济问题，**他只能建造一条额外的航线**。

小 E 可以根据官方给出的航线（**包括新增的航线**）确认 PF 到每个岛上的**最短时间**。

PF 将会在 $t$ 时发现小 E 逃走并开始追击。

为了节省钱，同时逃脱 PF 的追捕，小 E 想请你帮他编一个程序，计算最小的 $k$，使得他能够顺利逃脱到至少 $l$ 个岛屿。

**补给不需要时间，中途抓住也算抓住，同时到达则不算。**

**在岛屿上进行补给不需要时间，可以无限进行补给，只要背包装得下。**

题意概括：

有两个人 $a$，$b$ 和一颗 $n$ 个节点组成的树，$a$ 比 $b$早出发 $t$ 秒。如果两个节点之间通过时间不超过 $d$ 则 $b$ 可以在这两点之间建一条通过时间为 $\left\lfloor \dfrac{time(u \to v)}{2}\right\rfloor$ 的线路，求一个方案使 $a$ 至少到 $l$ 个点的最短时间不比 $b$ 长，并在此基础下要求岛屿之间距离最大值尽量小。

inputFormat:
第一行五个整数，$n,t,d,l,q$，表示岛屿的数量，PF 发现的时间，建立航线要求的通过时间范围，至少要到达的岛屿数量，以及建立航线所要求的中间岛屿的数量。他们的出发点均为点 $1$ 。

接下来 $n-1$ 行，每行四个整数 $u,v,p_i,e_i$，表示岛屿 $u$ 和岛屿 $v$ 之间有一条道路。$p_i$ 表示小 E 走这条航线的时间，$e_i$ 表示 PF 走这条航线的时间。**航线为双向** 。

outputFormat:
若有解，输出共两行。

第一行一个整数 $k$，表示最小能够逃脱所需要的钱数（单位：万元）。

第二行一个整数 $r$，表示用 $k$ 万元买背包时的能跑到的岛屿数量（ $1$ 号岛也算在内）。

若无解，只需输出 "no solution" (引号不需要输出)。


title: [USACO20OPEN] Social Distancing S

description:
由于高传染性的牛传染病 COWVID-19 的爆发，Farmer John 非常担忧他的奶牛们的健康。

为了限制疾病的传播，Farmer John 的 $N$ 头奶牛（$2\le N\le 10^5$）决定践行“社交距离”，分散到农场的各处。农场的形状如一维数轴，上有 $M$ 个互不相交的区间（$1\le M\le 10^5$），其中有可用来放牧的青草。奶牛们想要使她们位于不同的整数位置，每个位置上均有草，并且最大化 $D$ 的值，其中 $D$ 为最近的两头奶牛之间的距离。请帮助奶牛们求出 $D$ 的最大可能值。

inputFormat: 输入的第一行包含 $N$ 和 $M$。以下 $M$ 行每行用两个整数 $a$ 和 $b$ 描述一个区间，其中 $0\le a\le b\le 10^{18}$。没有两个区间有重合部分或在端点处相交。位于一个区间的端点上的奶牛视为在草上。

outputFormat: 输出 $D$ 的最大可能值，使得所有奶牛之间的距离均不小于 $D$ 单位。保证存在 $D>0$ 的解。


title: [USACO20OPEN] Cereal S

description:
Farmer John 的奶牛们的早餐最爱当然是麦片了！事实上，奶牛们的胃口是如此之大，每头奶牛一顿饭可以吃掉整整一箱麦片。

最近农场收到了一份快递，内有 $M$ 种不同种类的麦片（$1\le M\le 10^5$）。不幸的是，每种麦片只有一箱！$N$ 头奶牛（$1\le N\le 10^5$）中的每头都有她最爱的麦片和第二喜爱的麦片。给定一些可选的麦片，奶牛会执行如下的过程：

- 如果她最爱的麦片还在，取走并离开。
- 否则，如果她第二喜爱的麦片还在，取走并离开。
- 否则，她会失望地哞叫一声然后不带走一片麦片地离开。

奶牛们排队领取麦片。对于每一个 $0\le i\le N-1$，求如果 Farmer John 从队伍中移除前 $i$ 头奶牛，有多少奶牛会取走一箱麦片。

inputFormat:
输入的第一行包含两个空格分隔的整数 $N$ 和 $M$。

对于每一个 $1\le i\le N$，第 $i$ 行包含两个空格分隔的整数 $f_i$ 和
 $s_i$（$1\le f_i,s_i\le M$，且 $f_i\neq s_i$），为队伍中第 $i$ 头奶牛最喜爱和第二喜爱的麦片。

outputFormat: 对于每一个 $0\le i\le N-1$，输出一行，包含对于 $i$ 的答案。

hint:
### 样例解释
如果至少两头奶牛留下，那么恰有两头奶牛取走了一箱麦片。

### 子任务
- 测试点 $2$-$3$ 满足 $N,M\le 10^3$。
- 测试点 $4$-$10$ 没有额外限制。


title: [USACO20OPEN] The Moo Particle S

description:
FJ 的奶牛们最近很无聊，她们想到了一种全新的方式缓解无聊：研究高等物理！事实上，她们甚至成功发现了一种新的亚原子粒子，她们将其命名为“哞粒子”。

奶牛们正在进行一项有关 $N$ 个哞粒子的实验（$1\le N\le 10^5$）。粒子 $i$ 的“自旋”可以用范围在 $−10^9\ldots 10^9$ 之间的两个整数 $x_i$ 和 $y_i$ 来描述。有时两个哞粒子会发生相互作用。自旋为 ($x_i,y_i$) 和 ($x_j,y_j$) 的两个粒子之间仅当 $x_i\le x_j$ 并且 $y_i\le y_j$ 时会发生相互作用。在这些条件下，有可能这两个粒子中的一个会消失（另一个粒子不会发生任何变化）。在任意给定的时刻，至多只有一次相互作用会发生。

奶牛们想要知道在经过一些任意的相互作用之后剩余的哞粒子的最小数量。

inputFormat: 输入的第一行包含一个整数 $N$，为哞粒子的初始数量。以下 $N$ 行每行包含两个空格分隔的整数，为一个粒子的自旋。每个粒子的自旋各不相同。

outputFormat: 输出一个整数，为经过一些任意的相互作用之后剩余的哞粒子的最小数量。

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

一个可能的相互作用顺序：

- 粒子 $1$ 和 $4$ 相互作用，粒子 $1$ 消失。
- 粒子 $2$ 和 $4$ 相互作用，粒子 $4$ 消失。
- 粒子 $2$ 和 $3$ 相互作用，粒子 $3$ 消失。
仅留下粒子 $2$。

### 样例输入输出 2 解释

粒子 $3$ 不能与任何其他两个粒子相互作用，所以它必然会留下。粒子 $1$ 和 $2$ 中必然留下至少一个。

### 子任务
- 测试点 $3$-$6$ 满足 $N\le 10^3$。
- 测试点 $7$-$12$ 没有额外限制。


title: [eJOI2017] 魔法

description:
给定一个长度为 $n$ 的字符串 $S$。设 $S$ 中不同的字符数为 $k$ 。

定义字符串的子串为该字符串某一连续段。

而 ***有魔法的子串*** 被定义为 $S$ **的某一非空子串，满足该子串中不同的字符数为** $k$ **，且每个字符的出现的次数都相同**。

你需要求出给定字符串 $S$ 的不同的 有魔法的子串 的个数。

若两个子串的左右端点不同，则这两个子串不同。

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

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

outputFormat: 一个整数表示答案 $\bmod (10^9+7)$ 的值。

hint:
#### 【输入输出样例解释】

**样例 1 解释**

- 满足条件的子串有： $\texttt{abc},\texttt{cba},\texttt{abc},\texttt{abccba}$

**样例 2 解释**

- 仅子串 $\texttt{abcABC}$ 为 有魔法的子串（区分大小写，即 $\texttt{a}\ne \texttt{A}$）。

**样例 3 解释**

- 其中一个是 $\texttt{SwSwwS}$。

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

**本题采用多测试点捆绑测试，共有 4 个子任务**。

- Subtask 1（10 points）：$2\le n\le 100$。
- Subtask 2（20 points）：$2\le n\le 2\times 10^3$。
- Subtask 3（30 points）：$2\le n\le 10^5,k=2$ （即 $S$ 中只有两种字符）。
- Subtask 4（40 points）：无其他限制。

对于所有数据，保证 $2\le n\le 10^5$，字符集为 $ [\texttt{a},\texttt{z}] \cup [\texttt{A},\texttt{Z}]$

#### 【说明】

原题来自：[eJOI 2017](www.ejoi.org) Problem A [Magic](http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_1/EN/magic_statement-en.pdf)

翻译提供：@[```_Wallace_```](https://www.luogu.com.cn/user/61430)


title: 「Wdsr-1」贤者之石

background: 帕秋莉·诺蕾姬是一位擅长魔法的魔女，而炼制贤者之石便是她的日常任务。

description:
帕秋莉摆出了一个边长为 $k-1$（$k$ 个点）的正三角形点阵，每个点上**可以且只能**放一颗元素石。

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

在魔界中，正三角形被认为是最美丽而稳定的图形，因此当且仅当放在点阵中的**三颗元素石构成一个正三角形**时，元素石能够被合成为一颗贤者之石。

帕秋莉规定，假设她在边长为 $k-1$ 的点阵中**随机**选取三个点放置元素石，那么三颗元素石能够合成贤者之石的概率称为 $P_k$ 。（$P_1=0, P_2=1$）

现在，为了能够难倒智慧的你，帕秋莉想要你求出
$$\sum_{k=m}^{+\infty}P_k$$
的值，其中 $m$ 是给定的整数。

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

outputFormat:
一行一个小数，表示所求的答案。

**你需要保留 $5$ 位有效数字，并且使用科学记数法。**

举例说明：

假设答案为 ``0.0123``，则你需要输出 ``1.2300x10^-2``。

假设答案为 ``1.2345``，则你需要输出 ``1.2345x10^0``。


title: [eJOI2017] 六

description:
Elly 正在研究关于 正整数 $N$ 的一些性质，发现 $N$ 有不多于 $6$ 个不同的质因数。

接下来，她以一种特定的方式来生成的一个列表，一开始列表为空。她先写下了 $N$ 的一个大于一的因数 $x$ ，加入列表前，她先要确保 在所有已经在列表中的数中， 不能有 **超过** $1$ **个** 数与 $x$ **不互质**。

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

举个例子，当 $N=12156144$ 时：

合法的列表有： $ (42), (616, 6, 91, 23),(91, 616, 6, 23), (66, 7), (66, 7, 7, 23, 299, 66), \\(143, 13, 66),(42,12156144),\text{etc.} $

而不合法的有：之一是 $(5,11)$，原因是 $5$ 不是 $N$ 的因子；还有一个是 $ (66, 13, 143)$ ，原因是 $143$ 与其他两个数都不互质。

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

现在 Elly 希望你计算出给定的 $N$，可以生成几个不同的合法的列表。

**若两个列表长度不同，或存在一个位置使得两个列表的该位置的值不同，那么我们说这两个列表不同的**。

inputFormat: 一个整数：$N$。

outputFormat: 一个整数，表示列表的个数 $\bmod (10^9+7)$ 的值。


title: 「Wdoi-1」托卡马克

background: 今天的旧地狱依然核平，没有丝毫的波澜。

description:
阿空在一次实验中意外失控，导致炽热的托卡马克上出现了 $n$ 处破损，为了防止八咫乌的力量彻底释放影响地面世界，觉决定修复托卡马克。

阿空的托卡马克可抽象地理解为一条直线，以阿空为原点，这些破损位置的坐标分别为 $x_1,x_2,\ldots ,x_n$。

- 觉不希望消耗太多力量，所以她只会在这 $n$ 处破损中选择 $m$ 处进行修复。

- 为了防止破损处发生泄漏，觉会在选择的 $m$ 处破损间**两两连接**一条通道。

- 一条连接 $x_i$ 与 $x_j$ 处的通道的费用为 $\left\vert x_i - x_j \right\vert$，即两点间的直线距离，而一个方案的总花费被定义为所有通道的费用之和。

觉当然知道有很多修复 $m$ 处破损的方案，但她现在只想知道：在所有合法方案中，总花费为**严格**第 $k$ 大的方案是什么。

严格第 $k$ 大即不存在并列情况的第 $k$ 大方案。

由于觉拥有读心的能力，你只需要输出该方案的总花费即可。

若不存在符合要求的方案，输出 `-1`。

inputFormat:
第一行三个整数，$n,m,k$，含义与题目描述一致。

第二行 $n$ 个整数，为破损位置的坐标 $x_i$。

outputFormat: 一行一个整数，表示所求方案的总花费。


title: Strings of Monody

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

LGD 是一只喜欢 Monody 的小恐龙。

根据 Monody 的音乐，他建立了一个模型，叫做 赞歌字符串。简称， SoM (String of Monody)。

description:
赞歌字符串是一个由 $1,4,5$ 组成的字符串。每次操作 LsWn 会拿出左端点为 $l$，右端点为 $r$ 的子串，（注意，第一个字符的下标为 $1$，最后一个字符的下标为 $n$）并把它替换为新的给出的子串。替换之后，你需要回答 $3$ 个对于完整串的问询，分别是：
1. $1$ 的个数。
2. 整个字符串每个数位的总和。
3. 整个字符串每个数位的乘积。

所有输出都要对 $\color{black}998\color{red}24\color{black}353$ 取模。

inputFormat:
第一行一个字符串。
第二行一个数字 $m$ 代表有 $m$ 次操作
后面 $m$ 行每行两个数字 $l,r$，然后一个长 $r-l+1$ 的字符串代表把 $(l,r)$ 子串改为这个字符串。

outputFormat: $m$ 行，每行 $3$ 个数，代表每次修改后的 $3$ 个问询。

hint:
样例一的解释：

第一次操作，字符串变为 ```111514``` ，其中 $1$ 的个数为 $4$，和为 $1+1+1+5+1+4=13$，乘积为 $1\times 1\times 1\times 1\times 5\times 1\times 4=20$。
第二次操作，字符串变为 ```114414```。
第三次操作，字符串变为 ```114514```。

---

我们设初始字符串长度为 $n$。

对于 $10\%$ 的数据，$n\le 10$。
对于 $40\%$ 的数据，$n\le 1000$。
对于全部数据，$n\le 10^6, m\le 10^3, 1\le r-l+1\le 10^3$。


title: [COCI2010-2011#1] TIMSKO

description: 有一所大学每年都会举办一场信息学竞赛，竞赛中，每支队伍由 $1$ 名男生和  $2$ 名女生组成。一所学院的院长为了减少对手，把其他对手安排在一个遥远的国家进行实习，被派去实习的对手将无法参加比赛。所有选手中，女性选手的数量为 $m$，男性选手的数量为 $n$，可以派去实习的对手数量为 $k$。院长必须创建能参加比赛的队伍。你的任务是输出可以创建的最大团队数。

inputFormat:
输入数据共一行。

一行三个整数，$m,n,k$，含义如题所示。

outputFormat:
输出数据共一行。

一行一个整数，$ans$，表示可以组成的最大团队数。

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

院长就可以派一男一女去实习，这样就变成了：$m=5$，$n=2$，分成两队（一个女生没有队伍），所以答案为 $2$。

---

**数据规模与约定**

对于 $100\%$ 的数据，$0 \leq n,m \leq 100$，$0 \leq k \leq m+n$。

---

**说明**

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #1](https://hsin.hr/coci/archive/2010_2011/contest1_tasks.pdf) *T1 TIMSKO*。**


title: [COCI2010-2011#1] SRETAN

description: 已知 $4$ 和 $7$ 是幸运数字，而其他数字不是幸运数字。如果一个整数中只包含十进制表示法中的幸运数字，则这个整数是幸运的。你需要求出第 $k$ 个幸运的正整数。

inputFormat:
输入数据共一行。

一行一个整数 $k$，含义如题所示。

outputFormat:
输出数据共一行。

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

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

因为是正整数，所以第一个一定是数字 $4$。

---

**数据规模与约定**

对于 $100\%$ 的数据，$1 \leq k \leq 10^9$。

---

**说明**

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #1](https://hsin.hr/coci/archive/2010_2011/contest1_tasks.pdf) *T3 SRETAN*。**


title: [COCI2010-2011#1] ŽABE

description:
国王有 $n$ 个仆人。他把仆人排成一圈，每个仆人面向下一个仆人的后面。

每个仆人都有一个编号，序列总是从编号为 $1$ 的仆人开始。如果一个仆人插到前面的那位仆人前，这个操作就被视为一次插队。例如：仆人编号为 `1 5 4 3 2 6`，编号为 $2$ 的仆人插队了 $2$ 个位置，则得到：`1 5 2 4 3 6`。

当国王宣布数字 $b$ 时，编号为 $b$ 的仆人就要向前插队 $b$ 格。国王希望宣布一些指令以便将原始序列变为他希望的序列。

给你原始序列以及国王希望的序列，你需要求出国王依次下发的指令。数据保证原始序列和国王希望的序列不相等。

inputFormat:
输入数据共三行。

第一行一个整数 $n$，含义如题所示。

第二行 $n$ 个整数 $a_i$，表示原始序列。

第三行 $n$ 个整数 $k_i$，表示国王希望的序列。

outputFormat:
输出数据共 $m$ 行。

每行一个整数 $b$，含义如题所示。

注：$m$ 表示国王操作的次数。

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

仆人编号为 `1 5 4 3 2 6`，编号为 $2$ 的仆人插队了 $2$ 个位置，则得到：`1 5 2 4 3 6`。

---

**数据规模与约定**

对于 $100\%$ 的数据，$3 \leq n \leq 100$，$1 \leq m \leq 10^5$，$1 \leq a_i,k_i \leq 100$，$1 \leq b \leq n$。

---

**说明**

**题目译自 [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #1](https://hsin.hr/coci/archive/2010_2011/contest1_tasks.pdf) *T6 ŽABE*。**

感谢 [我谔谔](/user/127284) 提供的 Special Judge。


title: [COCI2014-2015#3] SILUETA

background:
画家文森特有一次发现自己身处一个摩天大楼林立的大都市，于是他立刻下来画画，陶醉于这一美妙的景象。由于一些普通程序员无法理解的原因，文森特决定只画眼前摩天大楼的轮廓。不幸的是，在他完成这幅杰作一周后，这幅画被烧了。

为了重建这幅画，文森特向各个方向寻求帮助，现在轮到你了！

description: 从你的角度来看，文森特的摩天大楼是长方形的，它的边平行于坐标轴，一边位于横坐标上。图片的横坐标应该用字符 `*` 表示，摩天大楼的轮廓用 `#` 表示，其余部分用 `.` 表示。图像的左边缘必须以摩天大楼开始，而图像的右边缘必须以摩天大楼结束。此外，为了验证数学家得到的结果，输出给定轮廓的周长，而不是计算横坐标上的边。

inputFormat:
第一行输入包含一个整数 $n$，即摩天大楼的数量。

以下 $n$ 行中的每一行都包含三个整数 $l_i,r_i$ 和 $h_i$，分别表示第 $i$ 座摩天大楼的位置。在笛卡尔坐标系中，这座摩天大楼被认为是一个矩形，左下角在 $(l_i,0)$ 中，右上角在 $(r_i,h_i)$ 中。

outputFormat:
第一行输出一个整数，表示摩天大楼轮廓的周长。

接下来的 $h+1$ 行，其中 $h+1$ 是最高摩天大楼的高度，必须包含题目描述中描述的文森特的绘图。

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

如下图，蓝色表示摩天大楼的轮廓（字符 `#`），而黄色是文森特绘画中横坐标的一部分（字符 `*`）。

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

#### 数据规模与约定

- 对于 $50\%$ 的数据，保证 $1\le n\le 100$，$1\le l_i,r_i,h_i\le 100$。
- 对于 $100\%$ 的数据，保证 $1\le n\le 10^4$，$1\le l_i,r_i,h_i\le 10^3$，$3 \leq r_i - l_i \leq 10^3$。


title: [湖北省队互测2014] 一个人的数论

background:
题目来源：$2014$ 年湖北省队互测Week1

资源来源：[链接](https://tieba.baidu.com/p/3050650090?red_tag=3002680446)

description:
有一天 hjy96 想到了一个数论问题:

对于一个非负整数 $d$ 和一个正整数 $n$，定义 $f_d(n)$ 为所有小于 $n$ 且与 $n$ 互质的正整数的 $d$ 次方之和。如 $f_3(10) = 1^3 +3^3 +7^3 +9^3$。

现给定 $d, n$，求 $f_d(n)$ 的值。输出答案对 $10^9 + 7$ 取模后的结果。

hjy96 当然知道怎么做啦! 但是他想考考你......

inputFormat:
由于 $n$ 可能很大，我们给出 $n$ 的质因数分解式。

$$
n=\prod_{i=1}^{w} p_{i}^{\alpha_{i}}
$$

第一行有用空格隔开的一个非负整数 $d$, 一个正整数 $w$。
接下来 $w$ 行，每行有两个用空格隔开的正整数 $p_i$, $α_i$。(保证 $p_i$ 为素数且互不相同)

outputFormat: 一行，一个非负整数表示 $f_d(n)$ 对 $10^9 + 7$ 取模后的结果。


title: [SHOI2002] N的连续数拆分

description:
所有的正整数均可以表示为一个、两个或者多个连续正整数的和。

给定一个不超过 $9\times 10^{14}$ 的正整数，求出它可以用几种不同的方法表示成连续正整数之和。例如给出 $9$，则有三种方式：$9,4+5,2+3+4$。

inputFormat: 输入一个正整数 $n$，表示要被拆分的正整数。

outputFormat: 输出方法个数。


title: [SHOI2002] 舞会

description: 某学校要召开一个舞会。已知学校所有 $n$ 名学生中，有些学生曾经互相跳过舞。当然跳过舞的学生一定是一个男生和一个女生。在这个舞会上，要求被邀请的学生中的任何一对男生和女生互相都不能跳过舞。求这个舞会最多能邀请多少个学生参加。

inputFormat:
输入的第一行是 $n$ 和 $m$ 。其中 $n$ 是可选的学生的总数， $m$ 是已知跳过舞的学生的对数 ( $n \leq 1000$ ， $m \leq 2000$ ）。

然后有 $m$ 行，每行包括两个非负整数，表示这两个编号的学生曾经跳过舞。学生的编号从 $0$ 号到 $n - 1$ 号。

outputFormat: 输出文件仅一行，为一个数字，即能够邀请的最多的学生数。


title: [SHOI2002] 空中都市

description:
在未来的空中都市中，有很多个小岛（城区）。现在要求在这些小岛之间架一座桥梁，每座桥是指在两个岛之间的通道。

有个约定，如果 $A$ 与 $B$ 之间有桥，$B$ 与 $C$ 之间有桥，则 $A$ 与 $C$ 之间就不能再架桥了，即对于城市中的任意三个岛，不能在其中的两两之间都架上桥。在这样的约定下，要求架的桥的数量最多。当然不必考虑具体的空间结构问题。

inputFormat: 输入文件只包含一行，其中仅包含一个非负整数 $n (0 \leq n \leq 1000)$，表示小岛的数量。

outputFormat: 输出文件也只包含一行，即表示最多能架设的桥梁数量。


title: 「Wdsr-1」仓库建设

background: 有一天，人间之里出现了饥荒。

description:
因为幻想乡倡导“幻想乡命运共同体”意识，河童们决定帮助人类修建一些粮仓防止饥荒再次发生。

人间之里有 $n$ 座城市和 $m$ 条双向道路，第 $i$ 条道路连接 $u_i，v_i$ 两座城市，长度为 $w_i$ 个单位。

由于每座城市的科技水平不同，从不同城市出发的运粮车的储油量不同。第 $i$ 座城市的运粮车的储油量只能支持运粮车行驶 $x_i$ 个单位。当然，城市与城市之间是友好的，无论到达哪个城市，热心的当地民众都会给运粮车**加满油**。

河童科技高度发达，所以仓库容纳的粮食可以视作无限。只有粮仓能发出运粮车。

现在要选择一些城市建设仓库，使得每一个城市都可以从粮仓中得到粮食。为了节约资源，河童希望仓库的数量最小。

但妖怪有时会占据一个城市，所以需要算出在任意一个城市不能建设粮仓时需要的最小粮仓数。

inputFormat:
第一行两个整数 $n，m$，意义如题面所述。

接下来 $m$ 行每行 3 个整数 $u_i，v_i，w_i$，意义如题面所述。

接下来一行 $n$ 个整数 $x_i$，意义如题面所述。

outputFormat:
输出一行 $n+1$ 个整数。

第一个整数表示最少需要多少粮仓；接下来 $n$ 个整数，第 $i$ 个整数表示 $i$ 号城市不能建粮仓所需的最小的粮仓数。

**如果第 $i$ 个城市不能建粮仓时，其他城市建粮仓不能到达这个城市，则输出**` -1`。

hint:
#### 样例解释
![](https://cdn.luogu.com.cn/upload/image_hosting/jg6fg91l.png)

这是样例画出来的图，显然在 3 号城市建立粮仓就可以解决问题，当 3 号城市不能建粮仓时，其他的城市无论怎么建粮仓，粮食也运不到 3 号城市，输出 ```-1```。

---

#### 数据范围

对于 $25\%$ 的数据，保证 $1\le n，m\le 10 ^ 3$。

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

对于 $100\%$ 的数据，保证 $1\le n，m \le 3\times 10^5，1\le u_i，v_i\le n，1\le w_i，x_i\le 10^6$，保证图联通。


title: [eJOI2017] 粒子

description:
两台相距 $L$ 的直线粒子加速器相对放置着。加速器 $A$ 发射 $x$ 粒子，加速器 $B$ 发射 $y$ 粒子。这两种粒子相遇时会碰撞并湮灭。注意，一个 $x$ 粒子可以超越另一个 $x$ 粒子，不会发生任何事。对于 $y$ 粒子也是同理。

在这样的条件下，从 $0$ 时刻开始，$A,B$ 加速器 分别开始发射 $N$ 个 $x,y$ 粒子。每一个粒子都以一个固定的速度移动。$x,y$ 粒子分别被编号为 $1,2,\cdots N$。

注：在时间 $t$ 内，速度为 $v$ 的粒子移动的路程为 $s = vt$。

$x$ 粒子的发射时刻从编号 $1$ 到 $N$ 分别为：$0 = tx_1 <  tx_2 < tx_3 < \cdots < tx_N$，速度分别为：$vx_1, vx_2, vx_3, \cdots, vx_N$。

相应的， $y$ 粒子的发射时刻分别为：$0 = ty_1 <  ty_2 < ty_3 < \cdots < ty_N$，速度分别为：$vy_1, vy_2, vy_3, \cdots, vy_N$。

发射粒子的过程中满足：

- 每个粒子会碰撞一个相反类型（$x,y$ 粒子互为相反粒子）的粒子。
- 当两个粒子碰撞时，所有其他粒子到碰撞点的距离将 $\ge 1$。在前 $K$ 次碰撞中，这个条件被满足。

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

你的任务是，编写一个程序，确定前 $K$ 次碰撞的粒子对。

inputFormat:
第一行，三个正整数，由空格隔开：$N,L,K$。

接下来 $N$ 行，每行两个整数：$tx_i,vx_i$。

再接下来 $N$ 行，每行两个整数：$ty_i,vy_i$。

outputFormat:
输出共 $K$ 行。

每行两个正整数 $i,j$，表示第 $i$ 个 $x$ 粒子和第 $j$ 个 $y$ 粒子。

第 $l$ 行表示第 $i$ 个 $x$ 粒子和第 $j$ 个 $y$ 粒子是第 $l$ 个发生碰撞的，即输出顺序代表碰撞的先后顺序。

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

对于所有数据，保证：

- $1 \le N \le 5\times 10^4$。
- $1 \le L \le 10^9$。
- $1\le K \le \min(10^2,N)$。
- $tx_i,ty_i \in [0,10^9]$。
- $vx_i,vy_i \in (0,10^9]$。

其中，对于 $30 \%$ 的数据，有 $1 \le N \le 10^3$。

#### 说明

原题来自：[eJOI2017](www.ejoi.org) Problem C [Particles](http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_1/EN/particles_statement-en.pdf)

翻译提供：@[```_Wallace_```](https://www.luogu.com.cn/user/61430)


title: [湖北省队互测2014] 没有人的算术

description:
万物初始之前，宇宙是无边无际混沌的黑暗，只有上帝之灵穿行其间。

上帝对这无边的黑暗十分不满，就一挥手说:“要有光”，于是世间就有了光。从此，世间 就有了昼与夜的交替。这是上帝创世的第一天。

第二天，上帝仍不满意眼前空洞的景象，就一挥手说：“要有零”。于是世间出现了第一个数：$0$。

第三天，上帝对只有 $0$ 很不满意，就一挥手说：“要有非零数”。于是上帝开始创造新数，每个新数用一个已经创造出来的数的有序对表示，即：

$$
x = (x_L, x_R)
$$

于是世间出现了 $(0, 0), (0, (0, 0)), ((0, 0), 0), ((0, 0), (0, 0)), ...$。到了晚上，各种各样千奇百怪的数在大地上奔腾。
（注：上帝造的这个 “数” 与普通的自然数、有理数之类的不同，这种数是以如上所述的方式递归定义的，总是数对里面是数对，拆分到最后会得到不可再拆的 $0$）

第四天，上帝看到各个数不分彼此，就一挥手说：“要有区别”。于是为了区分每个数，上帝定义等于：

1.  $0 = 0$ 。

2.  对于任意 $x_L, x_R, y_L, y_R$，若 $x_L = y_L$ 且 $x_R = y_R$，则 $(x_L, x_R) = (y_L, y_R)$。

3.  对于任意 $x, y$，$x = y$ 当且仅当满足以上条件之一。反之记作 $x \not = y$。

第五天，上帝看到各个数乱成一团，就一挥手说：“要有序”。于是为了比较每个数，上帝定义小于：

1. 对于任意 $x$，若 $x\not = 0$，则 $0 < x$。
2. 对于任意 $x_L, x_R, y_L, y_R$，若 $x_L < y_L$，则 $(x_L, x_R) < (y_L, y_R)$ 。
3. 对于任意 $x_L, x_R, y_L, y_R$，若 $x_L = y_L$ 且 $x_R < y_R$，则 $(x_L, x_R) < (y_L, y_R)$。
4. 对于任意 $x, y$，$x < y$ 当且仅当满足以上条件之一。反之记作 $x\not < y$。

在此基础上定义小于等于：$x ≤ y \iff x < y$ 或 $x = y$ 。容易发现：

1. $x ≤ y, y ≤ x ⇒ x = y$ 。
2. $x ≤ y, y ≤ z ⇒ x ≤ z$ 。
3. $x ≤ y$ 或 $y ≤ x$ 。

进而定义：

1. $x > y \Longleftrightarrow  y < x$ 。
2. $x ≥ y \Longleftrightarrow   x\not < y$。

至此万物欣欣向荣，和睦一堂。

第六天，由于之前沉迷与算术而忘记去造核酸和蛋白质，所以上帝没办法造人。但是上帝不甘心，就一挥手说：“要有跳蚤”，于是用泥巴捏出了神奇生物跳蚤。

上帝用五天的时间造出天地万物，又在第六天造出了唯一的生命——跳蚤。上帝看到天地万物井然有序、生生不息，自己造的跳蚤正在开心地和数学玩耍，很高兴，便决定把第七天作为休息的日子。

跳蚤每天的生活很简单。一天开始时，他会取一个长度为 $n$ 的数组 $a[1,2,\cdots,n]$，初始时均为 $0$。

接着他会不断地做下列两件事之一：

1. 在头脑中产生三个正整数 $l, r, k$，然后把 $a[k]$ 重新赋值为 $(a[l], a[r])$ 。特别地，如果 $l = k$ 或 $r = k$ 也是合法的，这不会导致错误，因为跳蚤总是先默默算出 $(a[l], a[r])$ 再给 $a[k]$ 赋值。

    保证 $1 ≤ l, r, k ≤ n$。

2. 在头脑中产生两个正整数 $l, r$，然后计算 $a[l], a[l + 1], \cdots, a[r − 1], a[r]$ 中的最大值。

     保证 $1 ≤ l ≤ r ≤ n$。

跳蚤当然知道怎么做啦！但是他想考考你……

inputFormat:
第一行两个正整数 $n, m$，表示长度为 $n$ 的数组，共 $m$ 个操作。接下来 $m$ 行每行表示一个操作:

1. `C l r k` : 赋值操作，执行 $ a[k] = (a[l], a[r])$ 。

2. `Q l r`: 询问操作，计算 $a[l], a[l + 1], ..., a[r − 1], a[r]$ 中的最大值。输出最大值对应的下标。 如果有多个最大值那么取下标最小的那一个。

outputFormat: 对于每个询问操作输出一行表示相应的结果。

hint:
$$
\def\arraystretch{1.5}
\begin{array}{c|l|l}
\hline\hline \rm Task~Id & n & m \\
\hline\hline 1 & =10 & =50 \\
\hline 2 & =5\times 10^4 & \leq 2\times 10^5 \\
\hline 3 & =5\times 10^4 & \leq 2\times 10^5 \\
\hline 4 & =6\times 10^4 & \leq 5\times 10^5 \\
\hline 5 & =6\times 10^4 & \leq 5\times 10^5 \\
\hline 6 & =8\times 10^4 & \leq 2\times 10^5 \\
\hline 7 & =8\times 10^4 & \leq 2\times 10^5 \\
\hline 8 & =10^5 & \leq 5\times 10^5 \\
\hline 9 & =10^5 & \leq 5\times 10^5 \\
\hline 10 & =10^5 & \leq 5\times 10^5 \\
\hline\hline
\end{array}
$$


title: [COCI2016-2017#1] Tarifa

description:
为了能够在网上冲浪，Pero 购买了一个数据套餐：

- 每月他将获得 $x \rm{MB}$ 流量。
- 每月未用完的流量，可以在次月继续使用。

现在，我们知道了 Pero 在使用这个套餐的前 $n$ 个月中，每月使用了多少 $\rm{MB}$ 流量。请你帮忙计算，第 $n+1$ 月他能使用多少 $\rm{MB}$ 流量。

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

第二行一个整数 $n$。

接下来 $n$ 行，每行一个整数 $p_i$，表示第 $i$ 月 Pero 使用了多少 $\rm{MB}$ 流量。

outputFormat: 一行，一个整数，表示第 $n+1$ 月 Pero 能使用多少 $\rm{MB}$ 流量。

hint:
#### 样例 1 解释

第一月，Pero 能使用 $10\rm{MB}$ 流量，实际使用 $4\rm{MB}$ 流量，剩余 $6\rm{MB}$ 流量。

第二月，Pero 能使用 $6+10=16(\rm{MB})$ 流量，实际使用 $6\rm{MB}$ 流量，剩余 $10\rm{MB}$ 流量。

第三月，Pero 能使用 $10+10=20(\rm{MB})$ 流量，实际使用 $2\rm{MB}$ 流量，剩余 $18\rm{MB}$ 流量。

第四月，Pero 能使用 $18+10=28(\rm{MB)}$ 流量。

---

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $1\le x\le 100$，$1\le n\le 100$，$0\le p_i\le 10^4$。

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

#### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #1](https://hsin.hr/coci/archive/2016_2017/contest1_tasks.pdf) _T1 Tarifa_**。


title: [COCI2016-2017#1] Jetpack

description:
Mirko 正在玩一款小游戏。在一个 $10$ 行 $n$ 列的矩阵中，他需要从左下角出发，避免在障碍物处停留，最终到达第 $n$ 列的任意位置。每秒，他都会向右移动一个单位。

在游戏中，Mirko 拥有一个喷气背包（游戏开始时关闭）：

- 打开喷气背包时，每秒他将额外向上移动一个单位（即向右上方移动），直到他处于矩阵顶端的一行。
- 关闭喷气背包时，每秒他将额外向下移动一个单位（即向右下方移动），直到他处于矩阵底端的一行。

他可以在任意一秒打开喷气背包，并在任意秒后关闭。将此记为一次操作。

现在，Mirko 想让你设计一系列操作，使他能够顺利结束游戏。

inputFormat:
第一行一个整数 $n$，表示矩阵的列数。

接下来 $10$ 行，每行 $n$ 个字符。表示相应位置是否存在障碍物。字符只可能是 `.` 或 `X`。

- `.` 表示该区域不存在障碍物。
- `X` 表示该区域存在障碍物。

outputFormat:
**本题使用 Special Judge**。

第一行一个非负整数 $p$，表示 Mirko 应进行操作的次数。

接下来 $p$ 行，每行两个正整数 $t_i$ 和 $x_i$，表示 Mirko 需要在第 $t_i$ 秒打开喷气背包，并在 $x_i$ 秒后关闭。

若存在多种答案，请输出任意一种。

另外：

- 操作应按时间顺序给出，且在一次操作完成前无法进行其他操作。即 $t_i+x_i\le t_{i+1}$。
- 游戏结束后 Mirko 无法进行任何操作。即 $t_i<n$。
- Mirko 不希望操作次数过多。即 $0\le p\le 5\times 10^4$。


title: 「Wdsr-1」小铃的书

background:
本居小铃在人间之里经营着一家名为“铃奈庵”的书店。店里井井有条地堆放着很多很多书。

一天，魔理沙来铃奈庵借书，搞得店里十分混乱，魔理沙随身携带的魔导书与铃奈庵的书籍全都混在了一起。

description:
小铃一共有 $n-1$ 本书，每本书有一个编号 $a_i$，两本书属于同一种类当且仅当两本书的编号相同。

由于小铃平时将这些书整理得井井有条，因此在小铃的 $n-1$ 本书中，每个种类的书的数量都恰好是 $k$ 的倍数，其中 $k$ 是一给出的常数。

现在，魔理沙的一本编号未知的魔导书与小铃的 $n-1$ 本书混在了一起，而魔理沙只有知道魔导书的编号才能将其找回。

由于书的数量实在太多，魔理沙找到了你来帮忙，希望聪明的你能帮她求出混入的魔导书的编号。

**注意：魔理沙的魔导书可能与小铃的某本书有着相同的编号。**

inputFormat:
第一行是两个整数 $n,k$，含义与题目描述一致。

保证 $n\equiv 1 \pmod k$ 。

第二行共 $n$ 个整数，表示混在一起的 $n$ 本书的编号 $a_i$ 。

outputFormat: 共一行一个整数，表示魔理沙的魔导书的编号。

hint:
#### 样例说明

样例 $1$ 中，小铃的书的编号为 $1,2,3$，分别有 $3$ 本。因此魔导书的编号为 $5$。

样例 $2$ 中，小铃的书的编号为 $1,4,5$，分别有 $4$ 本。因此魔导书的编号为 $1$。

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

#### 数据范围及约定

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

$$
\def{\arraystretch}{1.5}
\def\cuteran{https://www.luogu.com.cn/paste/iyzwht7l}
\begin{array}{|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le} & \textbf{分值} \cr\hline
1 & 10^5 & 50 \cr\hline
2 & 10^6 & 25 \cr\hline
3 & 10^7 & 25 \cr\hline
\end{array}
$$

对于全部数据，保证 $1 \le n \le 10^7$  ，$2 \le k \le 10^3$  ，$1 \le a_i \le 10^{18}$。保证数据合法，即有且只有一本混入的魔导书。

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

#### 提示

**请注意时空限制。**

**使用 $\texttt{cin}$ / $\texttt{cout}$ 可能超时，这里给出一个快速读入模板：**

```cpp
long long qread(){
    long long w=1,c,ret;
    while((c=getchar())> '9'||c< '0')
    w=(c=='-'?-1:1); ret=c-'0';
    while((c=getchar())>='0'&&c<='9')
    ret=ret*10+c-'0';
    return ret*w;
}
```

**或者使用这份模板：**

```cpp
typedef long long LL;
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++
static char buf[100000],*pa(buf),*pb(buf);
inline LL readint() {
	LL x=0;char c=gc;
	while(c<'0'||c>'9')c=gc;
	for(;c>='0'&&c<='9';c=gc)x=x*10+(c&15);
	return x;
}
```

**其中，在开启 O2 开关的前提下，前者在极限数据下的读入要 $500\texttt{ms}$，而后者需要 $300\texttt{ms}$。也就是说，你的程序至少有 $500\sim 700\texttt{ms}$ 的时间执行主要算法。**


title: [eJOI2017] 骆驼

description:
我们在棋盘上引入一个新的棋子，称之为“骆驼棋”。棋子跳跃规则：你可以将它移动到水平或垂直方向上的一个位置，使得新位置与旧位置之间隔着 $2$ 格；或者像四个斜对角线的方向之一移动，使得新位置与旧位置之间恰好相隔一个格子。如图，棋盘的中心就是棋子的位置，$8$ 个打上 ”$\times$“标记的就是可以移动到的位置。显然，棋子不可以跳出棋盘。

![GUzZDO.png](https://s1.ax1x.com/2020/04/03/GUzZDO.png)

整个棋盘是 $N$ 行 $N$  列的，其中保证 $5 | N$ 。

一开始，棋子在棋盘的左上角。经过一系列移动，使得整个棋盘每一个格子都被走过恰好一次，并且最后的位置与开始位置之间恰好可以以骆驼棋一步互相到达，这就是所谓的”骆驼循环“。

你需要写一个程序，找到给定棋盘的”骆驼循环”。或者判断是否存在“骆驼循环”。

inputFormat: 输入仅一行，一个正整数 $N$。

outputFormat:
首先，如果不存在输出 ```NO```。

输出包含一个 $N \times N$ 的方阵。

方阵包含 $N^2$ 个不同的正整数，大小在 $[1,N^2]$ 范围内，表示每一个格子的访问顺序。那么第一个数字就是 $1$ 。

例如，第 $i$ 行第 $j$ 列的数为 $k$ 说明这一个位置的格子是第 $k$ 个被走到的。详见样例。

hint:
#### Special Judge 计分标准

如果可行解有多个，输出任意一个就可以拿到这个测试点的分数。

如果输出不完全或发现不正确的情况你可能会得到一个 UKE。

如果在不该输出 ```NO``` 的地方输出了 ```NO``` ，你们你会得到 ```WA```，以及一句 ```wrong output format Expected integer, but "NO" found```

#### 输入输出样例解释

棋子移动的方式为：$(1,1)$（表示第一行第一列） $\rightarrow (4,1) \rightarrow (7,1) \rightarrow \text{etc.}$

最后棋子在 $(3,3)$ 处停止，恰好可以一步走到起点。

附图：

![GUxL3q.png](https://s1.ax1x.com/2020/04/03/GUxL3q.png)

#### 数据规模与约定

对于所有数据，保证 $1\le N\le 10^3$，且 $n$ 是 $5$ 的倍数。

本题共 $17$ 个测试点。

- 对于其中一个测试点，有 $N=5$ ，单点分值比例为 $20 \%$。
- 对于其他 $16$ 个测试点，无其他限制，单点分值比例为 $5\%$。

#### 说明

原题来自：[eJOI2017](www.ejoi.org) Problem D [Camel](http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_2/EN/camel_statement-en.pdf)

翻译提供：@[```_Wallace_```](https://www.luogu.com.cn/user/61430)


title: [COCI2016-2017#1] Cezar

description:
Mirko 想对 $n$ 个单词进行加密。加密过程是这样的：

1.  选择一个英文字母表的排列作为密钥。
2.  将单词中的 `a` 替换为密钥中的第一个字母，`b` 替换为密钥中的第二个字母……以此类推。

例如，以 `qwertyuiopasdfghjklzxcvbnm` 作为密钥对 `cezar` 加密后，将得到 `etmqk`。

他希望，将所有单词加密并按字典序升序排列后，最初的第 $a_i$ 个单词位于第 $i$ 位。请你判断，这能否实现。如果能，请给出任意一种可行的密钥。

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

接下来 $n$ 行，每行一个字符串，表示待加密的单词。

最后一行 $n$ 个整数，表示 $a_i$。

outputFormat:
**本题使用 Special Judge**。

如果 Mirko 的要求不能实现，输出 `NE`。

否则，输出 `DA`。接下来一行输出任意一种可行的密钥。

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

**样例 1 解释**

以 `bacdefghijklmnopqrstuvwxyz` 为密钥加密后，得到：

- `ba`
- `ac`

字典序升序排列后，得到：

- `ac`
- `ba`

原先的第一个单词在第二位，第二个单词在第一位。符合要求。

**样例 3 解释**

以 `adbcefghijklmnopqrstuvwxyz`  为密钥加密后，得到：

- `ddd`
- `bbb`
- `ccc`

字典序升序排列后，得到：

- `bbb`
- `ddd`
- `ccc`

原先的第一个单词在第二位，第二个单词在第三位，第三个单词在第一位。符合要求。

---

#### 数据规模与约定

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

所有单词的长度不超过 $100$，且只包含小写字母。

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

#### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #1](https://hsin.hr/coci/archive/2016_2017/contest1_tasks.pdf) _T3 Cezar_**。


title: 「Wdoi-1」蓬莱玉枝

background: 辉夜的游戏机没电了。

description:
由于游戏机在妖怪之山充电，辉夜玩起了蓬莱玉枝。

具体来说，辉夜面前有 $n$ 条蓬莱玉枝，第 $i$ 条蓬莱玉枝的长度为 $a_i$ 。

辉夜会从这 $n$ 条玉枝中选出若干条来，称作一次选择方案。一个方案被辉夜认为是"不无聊的"，当且仅当在选出的玉枝中，存在某三条玉枝能够 **构成一个三角形**。

当一个方案被认为是"无聊的"时，辉夜认为它的有趣程度为 $0$；当一个方案被辉夜认为是"不无聊的"时，若选出的玉枝数量为 $k$，选出的玉枝中最长的玉枝长度为 $m$ ，则这个方案的有趣程度为 $km$ 。

现在，辉夜想要知道，所有选择方案的有趣程度之和是多少。然而，辉夜的玉枝太多了，所以她找到了聪明的你来帮她算出答案，作为回报，你可以得到参加月都万象展的邀请。

辉夜认为一个巨大的数字也是很无趣的，因此你只需要输出答案对 $20060723$ 取模后的结果即可。

inputFormat:
输入数据共包括两行。

第一行，一个整数 $n$，表示玉枝的数量。

第二行，$n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 条玉枝的长度。

outputFormat: 一行一个整数，表示有趣程度之和对 $20060723$ 取模后的结果。


title: [COCI2016-2017#1] Mag

description:
你将获得一棵由无向边连接的树。树上每个节点都有一个魔力值。

我们定义，一条路径的魔力值为路径上所有节点魔力值的乘积除以路径上的节点数。

例如，若一条路径包含两个魔力值分别为 $3,5$ 的节点，则这条路径的魔力值为 $3\times 5/2=7.5$。

请你计算，这棵树上魔力值最小的路径的魔力值。

inputFormat:
第一行一个整数 $n$，表示树共有 $n$ 个节点，编号为 $1\dots n$。

接下来 $n-1$ 行，每行两个整数 $a_i,b_i$，表示编号为 $a_i,b_i$ 的两个节点由一条无向边连接。

接下来 $n$ 行，每行一个整数 $x_i$，表示编号为 $i$ 的节点的魔力值。

outputFormat: 一行，一个既约分数 $p/q$。

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

**样例 1 解释**

注意，路径可以只包含一个节点。

这棵树上魔力值最小的路径的包含节点 $1$，其魔力值为 $3/1$。

**样例 2 解释**

这棵树上魔力值最小的路径的包含节点 $2,4$，其魔力值为 $1\times 1/2=1/2$。

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

#### 数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le a_i,b_i\le n$，$1\le x_i\le 10^9$。

数据保证，$p,q$ 不会超过 $10^{18}$。

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

#### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #1](https://hsin.hr/coci/archive/2016_2017/contest1_tasks.pdf) _T4 Mag_**。


title: [COCI2016-2017#1] Kralj

description:
矮人国和精灵国即将爆发战争！精灵王 Slavko 将 $n$ 个精灵编号为 $1\dots n$。矮人王 Mirko 则让 $n$ 个矮人围成一个圆环，从某个矮人开始顺时针编号为 $1\dots n$。

接下来，Mirko 将为每个精灵分配一个数字 $a_i$，表示将与它们决斗的矮人的编号。然而，由于他的粗心，不同精灵分配到的数字可能是相同的。

为了决斗的公平，双方决定：

1.  Slavko 选出一位尚未确定对手的精灵，设其编号为 $i$。
2.  若编号为 $a_i$ 的矮人尚未确定对手，则将其作为这位精灵的对手。否则，从编号为 $a_i$ 的矮人开始，选择沿圆环顺时针方向第一个尚未确定对手的矮人作为这位精灵的对手。
3.  重复以上步骤，直到所有矮人及精灵都确定了对手。

Slavko 收集了所有矮人及精灵的力量值。决斗时，力量值大的一方总是获胜。他想知道，通过规划选择精灵的顺序，最多能有多少精灵在决斗中获胜。

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

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

第三行 $n$ 个整数 $p_i$，表示编号为 $i$ 的矮人的力量值。

第四行 $n$ 个整数 $v_i$，表示编号为 $i$ 的精灵的力量值。

outputFormat: 一行，一个整数，表示最多能有多少精灵在决斗中获胜。

hint:
#### 样例 1 解释

Slavko 以 $3,2,1$ 的顺序选择精灵。

这样，编号为 $1,2,3$ 的精灵的对手编号分别为 $2,1,3$。

编号为 $1,2$ 的精灵将在决斗中获胜。

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

#### 数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 5\times 10^5$，$1\le a_i\le n$，$1\le p_i,v_i\le 10^9$。

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

#### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #1](https://hsin.hr/coci/archive/2016_2017/contest1_tasks.pdf) _T5 Kralj_**。


title: [COCI2016-2017#1] Vještica

description:
Matej 面临着一个难题。在此之前，我们必须熟悉一种称作前缀树（`trie`）的数据结构。前缀树以前缀的方式，储存单词：

- 前缀树的每一条边都用英文字母表中的字母表示。
- 前缀树的根节点表示空前缀。
- 前缀树的每个其他节点都表示一个非空前缀。依次连接根节点至该节点路径上所标有的字母，即可得到该前缀。
- 不存在从一个节点出发的、标有相同字母的两条边。

例如，这棵前缀树储存了 `A,to,tea,ted,ten,i,in,inn`：

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

现在，Matej 获得了 $n$ 个单词，并可以将其中的一些单词重组。例如 `abc` 可以重组为 `acb,bac,bca,cab,cba`。请你计算，将一些单词重组后，储存这些单词的前缀树节点数的最小值。

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

接下来 $n$ 行，每行一个字符串，表示 Matej 获得的单词。

outputFormat: 一行，一个整数，表示将一些单词重组后，储存这些单词的前缀树节点数的最小值。

hint:
#### 样例 3 解释

所有单词均可以重组为 `aabb`。显然，前缀树最少的节点数应为 $5$（包含了表示空前缀的根节点）。

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

#### 数据规模与约定

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

所有单词的长度和不超过 $10^6$，且只包含小写字母。

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

#### 说明

**题目译自 [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #1](https://hsin.hr/coci/archive/2016_2017/contest1_tasks.pdf) _T6 Vještica_**。


title: [USACO20OPEN] Sprinklers 2: Return of the Alfalfa P

description:
Farmer John 有一块小的田地，形状为一个 $N$ 行 $N$ 列的一个方阵，对于所有的 $1 \le i,j \le N$，从上往下的第 $i$ 行的从左往右第 $j$ 个方格记为 $(i,j)$。他有兴趣在他的田地里种植甜玉米和苜蓿。为此，他需要安装一些特殊的洒水器。
在方格 $(I,J)$ 中的甜玉米洒水器可以喷洒到所有左下方的方格：即满足 $I \le i$ 以及 $j \le J$ 的 $(i,j)$。

在方格 $(I,J)$ 中的苜蓿洒水器可以喷洒到所有右上方的方格：即满足 $i \le I$ 以及 $J \le j$ 的 $(i,j)$。

被一个或多个甜玉米洒水器喷洒到的方格可以长出甜玉米；被一个或多个苜蓿洒水器喷洒到的方格可以长出苜蓿。但是被两种洒水器均喷洒到（或均喷洒不到）的方格什么也长不出来。

帮助 Farmer John 求出在他的田地里安装洒水器的方案数（ $\bmod \ 10^9 + 7$），每个方格至多安装一个洒水器，使得每个方格均能生长作物（即被恰好一种洒水器喷洒到）。

某些方格正被长毛奶牛占据；这不会阻止这些方格生长作物，但是这些方格里不能安装洒水器。

inputFormat:
输入的第一行包含一个整数 $N$。
对于每一个 $1\le i\le N$，第 $i+1$ 行包含一个长为 $N$ 的字符串，表示方阵的第 $i$ 行。字符串中的每个字符为 `W`（表示被一头长毛奶牛占据的方格）或 `.`（未被占据）。

outputFormat: 输出安装洒水器的方案数 $\bmod \ 10^9+7$ 的结果。

hint:
#### 样例 $1$ 解释：
以下是所有十四种可以使得 $(1,1)$ 生长甜玉米的方式。（译注：`C` 表示 sweet corn，即甜玉米；`A` 表示 alfalfa，即苜蓿）

```plain
CC  .C  CA  CC  .C  CA  CA  C.  CA  C.  CC  .C  CC  .C
CC, CC, CC, .C, .C, .C, CA, CA, .A, .A, C., C., .., ..
```

#### 样例 $2$ 提示：

这个样例满足第一个子任务的限制。

-----

对于 $100\%$ 的数据，满足 $1 \le N \le 2000$。

共 $16$ 个测试点，其中 $1\sim 2$ 为样例，其余性质如下：

对于测试点 $3 \sim 4$，满足 $N \le 10$ 且最多有 $10$ 个未被占据的格子。
对于测试点 $5 \sim 9$，满足 $N \le 200$。
对于测试点 $10 \sim 16$，无特殊限制。

---

出题人：Benjamin Qi


title: [USACO20OPEN] Exercise P

description:
Farmer John（又）想到了一个新的奶牛晨练方案！
如同之前，Farmer John 的 $N$ 头奶牛站成一排。对于 $1\le i\le N$ 的每一个 $i$，从左往右第 $i$ 头奶牛的编号为 $i$。他告诉她们重复以下步骤，直到奶牛们与她们开始时的顺序相同。

给定长为 $N$ 的一个排列 $A$，奶牛们改变她们的顺序，使得在改变之前从左往右第 $i$ 头奶牛在改变之后为从左往右第 $A_i$ 头。
例如，如果 $A=(1,2,3,4,5)$，那么奶牛们总共进行一步就回到了同样的顺序。如果 $A=(2,3,1,5,4)$，那么奶牛们总共进行六步之后回到起始的顺序。每步之后奶牛们从左往右的顺序如下：

0 步：$(1,2,3,4,5)$
1 步：$(3,1,2,5,4)$
2 步：$(2,3,1,4,5)$
3 步：$(1,2,3,5,4)$
4 步：$(3,1,2,4,5)$
5 步：$(2,3,1,5,4)$
6 步：$(1,2,3,4,5)$
**请你计算出所有可能的 $N!$ 种长为 $N$ 的排列 $A$ 回到起始顺序需要的步数的乘积。**

由于这个数字可能非常大，输出答案模 $M$ 的余数（$10^8\le M\le 10^9+7$，$M$ 是质数）。

-----

使用 C++ 的选手可以使用 [KACTL](https://github.com/kth-competitive-programming/kactl/blob/master/content/various/FastMod.h) 中的这一代码。这一名为 [Barrett 模乘](https://en.wikipedia.org/wiki/Barrett_reduction) 的算法可以以比通常计算快上数倍的速度计算 $a \% b$，其中 $b>1$ 为一个编译时未知的常数。（不幸的是，我们没有找到对于 Java 的这样的优化）。（译注：中文选手可以参考 几种取模优化方法[（译自 min-25 的博客）](https://loj.ac/article/327)）
```cpp
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
};
FastMod F(2);

int main() {
    int M = 1000000007; F = FastMod(M);
    ull x = 10ULL*M+3;
    cout << x << " " << F.reduce(x) << "\n"; // 10000000073 3
}
```

inputFormat: 输入一行包含 $N$ 和 $M$。

outputFormat: 输出一个整数。

hint:
#### 样例解释：
对于每一个 $1\le i\le N$，以下序列的第 $i$ 个元素等于奶牛需要使用 $i$ 步的排列数量：$[1,25,20,30,24,20]$。所以答案等于 $1^1\cdot 2^{25}\cdot 3^{20}\cdot 4^{30}\cdot 5^{24}\cdot 6^{20}\equiv 369329541\pmod{10^9+7}$。

**注意：这个问题的内存限制增加为 512 MB。**

---
对于 $100\%$ 的数据，满足 $1\le N\le 7500$。

共 $16$ 个测试点，其中 $1$ 为样例，其余性质如下：

测试点  $2$ 满足 $N=8$。
测试点 $3\sim 5$ 满足 $N\le 50$。
测试点 $6\sim 8$ 满足 $N\le 500$。
测试点 $9\sim 12$ 满足 $N\le 3000$。
测试点 $13\sim 16$ 没有额外限制。

----

出题人：Benjamin Qi


title: [USACO20OPEN] Circus P

description:
Farmer John 马戏团中的 $N$ 头奶牛正在为即将到来的演出做准备。演出全部在一棵节点编号为 $1\ldots N$ 的树上举行。演出的“初始状态”被定义为一个整数 $K$（$1\leq K\leq N$）使得奶牛 $1\ldots K$ 分布在树上的节点上，并且没有任何两头牛位于相同的节点。

在一场演出中，奶牛们可以“移动”任意次数。在一次“移动”中，一头奶牛可以从自己当前所处的节点移动到一个未被占据的相邻节点。如果一个状态可以通过一系列移动到达另一个状态，我们就称这两个初始状态是等价的。

对于每一个 $1\leq K\leq N$，你需要帮助奶牛确定有多少类等价的初始状态。即选出最多的起始状态数目，使得它们两两不等价。由于数字可能很大，所以只需输出答案 $\bmod \ 10^9+7$ 的结果。

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

接下来的 $N-1$ 行，每行两个整数 $a_i,b_i$，表示树中有一条连接 $a_i$ 和 $b_i$ 的边。

outputFormat: 输出共 $N$ 行，对于每一个 $1\leq i\leq N$，在第 $i$ 行输出 $K=i$ 时的答案 $\bmod \ 10^9+7$ 的结果。

hint:
#### 样例 $1$ 解释：
对于 $K=1$ 和 $K=2$，任何两个状态都可以互相到达。

然后考虑 $K=3$，令 $c_i$ 表示奶牛 $i$ 的位置，则状态 $(c_1,c_2,c_3)=(1,2,3)$ 等价于状态 $(1,2,5)$ 和 $(1,3,2)$，但不等价于状态 $(2,1,3)$。

-----

对于 $100\%$ 的数据，保证 $1 \le N \le 10^5$。

共 $20$ 个测试点，其中 $1\sim 2$ 为样例，其余性质如下：

对于测试点 $3 \sim 4$，满足 $N \leq 8$。
对于测试点 $5 \sim 7$，满足 $N \leq 16$。
对于测试点 $8 \sim 10$，满足 $N \leq 100$，且这个树为“星形”，最多有一个度数大于 $2$ 的节点。
对于测试点 $11 \sim 15$，满足 $N \leq 100$。
对于测试点 $16 \sim 20$，无特殊限制。

------

出题人：Dhruv Rohatgi


title: 烯烃计数

background:
你可能需要：

+ [烷基计数](https://loj.ac/problem/6538)

+ [烷烃计数](https://loj.ac/problem/6512)

由于洛谷没有上面两个题，所以就弄了这个题。

description:
求化学式为 $\text{C}_n \text{H}_{2n}$ 的 **烯烃（乙烯的同系物）** 的同分异构体个数。

本题中不考虑空间异构和顺反异构。

答案对 $998244353$ 取模。

inputFormat: 一个正整数 $n$。

outputFormat: 共 $n-1$ 行分别碳原子数目为 $2\sim n$ 的答案。


title: [USACO20OPEN] Haircut G

description:
Farmer John 由于对整理他难以整平的头发感到疲惫，于是决定去理发。他有一排 $N$ 缕头发，第 $i$ 缕头发初始时长度为 $A_i$ 微米（$0\le A_i\le N$）。理想情况下，他想要他的头发在长度上单调递增，所以他定义他的头发的“不良度”为逆序对的数量：满足 $i < j$ 及 $A_i > A_j$ 的二元对 $(i,j)$。
对于每一个 $j=0,1,\ldots,N-1$，Farmer John 想要知道他所有长度大于 $j$ 的头发的长度均减少到 $j$ 时他的头发的不良度。

-----

（有趣的事实：人类平均确实有大约 $10^5$ 根头发！）

inputFormat:
输入的第一行包含 $N$。
第二行包含 $A_1,A_2,\ldots,A_N$。

outputFormat:
对于每一个 $j=0,1,\ldots,N-1$，用一行输出 Farmer John 头发的不良度。

-----

**注意这个问题涉及到的整数大小可能需要使用 $64$ 位整数型存储（例如，C/C++ 中的“long long”）。**

hint:
#### 样例解释：

输出的第四行描述了 Farmer John 的头发长度减少到 $3$ 时的逆序对数量。
$A=[3,2,3,3,0]$ 有五个逆序对：$A_1>A_2,\,A_1>A_5,\,A_2>A_5,\,A_3>A_5,$ 和 $A_4>A_5$。

----

对于 $100\%$ 的数据，$1\le N\le 10^5$。

共 $13$ 个测试点，其中 $1$ 为样例，其余性质如下：

测试点 $2$ 满足 $N\le 100$。
测试点 $3\sim 5$ 满足 $N\le 5000$。
测试点 $6\sim 13$ 没有额外限制。

-----

出题人：Dhruv Rohatgi


title: [USACO20OPEN] Favorite Colors G

description:
Farmer John 的 $N$ 头奶牛每头都有一种最喜欢的颜色。奶牛们的编号为 $1\ldots N$，每种颜色也可以用 $1\ldots N$ 中的一个整数表示。
存在 $M$ 对奶牛 $(a,b)$，奶牛 $b$ 仰慕奶牛 $a$。有可能 $a=b$，此时一头奶牛仰慕她自己。对于任意颜色 $c$，如果奶牛 $x$ 和 $y$ 都仰慕一头喜欢颜色 $c$ 的奶牛，那么 $x$ 和 $y$ 喜欢的颜色相同。

给定这些信息，求一种奶牛喜欢颜色的分配方案，使得每头奶牛最喜欢的颜色中不同颜色的数量最大。由于存在多种符合这一性质的分配方案，输出字典序最小的（这意味着你应当依次最小化分配给奶牛 $1 \ldots N$ 的颜色）。

inputFormat:
输入的第一行包含 $N$ 和 $M$。
以下 $M$ 行每行包含两个空格分隔的整数 $a$ 和 $b$（$1\le a,b\le N$），表示奶牛 $b$ 仰慕奶牛 $a$。同一对奶牛可能会在输入中多次出现。

outputFormat: 对于 $1\ldots N$ 中的每一个 $i$，用一行输出分配给奶牛 $i$ 的颜色。

hint:
#### 样例解释：

在下图中，用粗边框圆表示的是最喜欢颜色 $1$ 的奶牛。

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

-----

对于 $100\%$ 的数据，$1\le N,M\le 2\times 10^5$。

共 $10$ 个测试点，其中 $1$ 为样例，其余性质如下：

测试点 $2\sim 3$ 满足 $N,M\le 10^3$。
测试点 $4\sim 10$ 没有额外限制。

-----

出题人：William Lin，Benjamin Qi


title: [USACO20OPEN] Exercise G

description:
Farmer John（又）想到了一个新的奶牛晨练方案！
如同之前，Farmer John 的 $N$ 头奶牛站成一排。对于 $1\le i\le N$ 的每一个 $i$，从左往右第 $i$ 头奶牛的编号为 $i$。他告诉她们重复以下步骤，直到奶牛们与她们开始时的顺序相同。

给定长为 $N$ 的一个排列 $A$，奶牛们改变她们的顺序，使得在改变之前从左往右第 $i$ 头奶牛在改变之后为从左往右第 $A_i$ 头。
例如，如果 $A=(1,2,3,4,5)$，那么奶牛们总共进行一步。如果 $A=(2,3,1,5,4)$，那么奶牛们总共进行六步。每步之后奶牛们从左往右的顺序如下：

0 步：$(1,2,3,4,5)$
1 步：$(3,1,2,5,4)$
2 步：$(2,3,1,4,5)$
3 步：$(1,2,3,5,4)$
4 步：$(3,1,2,4,5)$
5 步：$(2,3,1,5,4)$
6 步：$(1,2,3,4,5)$
**求所有正整数 $K$ 的和，使得存在一个长为 $N$ 的排列，奶牛们需要进行恰好 $K$ 步。**

由于这个数字可能非常大，输出答案模 $M$ 的余数（$10^8\le M\le 10^9+7$，$M$ 是质数）。

inputFormat: 输入的第一行包含 $N$ 和 $M$。

hint:
#### 样例解释：

存在排列使得奶牛需要进行 $1$、$2$、$3$、$4$、$5$ 以及 $6$ 步。因此，答案为 $1+2+3+4+5+6=21$。

-----

对于 $100\%$ 的数据，$1\le N\le 10^4$。

共 $10$ 个测试点，其中 $1$ 为样例，其余性质如下：

测试点 $2\sim 5$ 满足 $N\le 10^2$。
测试点 $6\sim 10$ 没有额外限制。

-----

出题人：Benjamin Qi


title: 轮换式 加强版

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

本题与原题的区别，只有模数和数据范围不同。

description:
小奔发现，对于任意的 $n$ 个字母，他们构成的轮换式，都表示成 $n$ 个基本轮换式的线性和。

一元的基本轮换式：$a$；

二元：$a+b$，$ab$；

三元：$a+b+c$，$ab+ac+bc$，$abc$；

四元：$a+b+c+d$，$ab+ac+ad+bc+bd+cd$，$abc+abd+bcd$，$abcd$；

......

已知 $n$ 个数的各个基本轮换式的值，求它们的 $m$ 次方和，答案对 $899678209$（$899678209 = 429 \times 2^{21} + 1$）取模。

inputFormat:
第一行两个正整数 $n,m$，意义如题目描述。
接下来一行 $n$ 个正整数，第 $i$ 个为 $a_i$，表示 $n$ 元 $i$ 次基本轮换式的值。

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


title: [NOI2019] 回家路线 加强版

background: 本题是 NOI 2019 回家路线的加强版，除数据范围外均与原题相同。

description:
猫国的铁路系统中有 $n$ 个站点，从 $1 - n$ 编号。小猫准备从 $1$ 号站点出发，乘坐列车回到猫窝所在的 $n$ 号站点。它查询了能够乘坐的列车，这些列车共 $m$ 班，从 $1 - m$ 编号。小猫将在 $0$ 时刻到达 $1$ 号站点。对于 $i$ 号列车，它将在时刻 $p_i$ 从站点 $x_i$ 出发，在时刻 $q_i$ 直达站点 $y_i$，小猫只能在时刻 $p_i$ 上 $i$ 号列车，也只能在时刻 $q_i$ 下 $i$ 号列车。小猫可以通过多次换乘到达 $n$ 号站点。一次换乘是指对于两班列车，假设分别为 $u$ 号与 $v$ 号列车，若 $y_u = x_v$ 并且 $q_u \leq p_v$，那么小猫可以乘坐完 $u$ 号列车后在 $y_u$ 号站点等待 $p_v - q_u$ 个时刻，并在时刻 $p_v$ 乘坐 $v$ 号列车。

小猫只想回到猫窝并且减少途中的麻烦，对此它用烦躁值来衡量。

 - 小猫在站点等待时将增加烦躁值，对于一次 $t (t \geq 0)$ 个时刻的等待，烦躁值将增加 $At^2 + Bt + C$，其中 $A, B,C$ 是给定的常数。注意：小猫登上第一班列车前，即从 $0$ 时刻起停留在 $1$ 号站点的那些时刻也算作一次等待。

 - 若小猫最终在时刻 $z$ 到达 $n$ 号站点，则烦躁值将再增加 $z$。

形式化地说，若小猫共乘坐了 $k$ 班列车，依次乘坐的列车编号可用序列 $s_1, s_2, \cdots , s_k$ 表示。该方案被称作一条可行的回家路线，当且仅当它满足下列两个条件：

 - $x_{s1} = 1,y_{sk} = n$

 - 对于所有 $j (1 \leq j < k)$，满足 $y_{sj} = x_{s_{j+1}}$ 且 $q_{sj}\leq p_{s_{j+1}}$

对于该回家路线，小猫得到的烦躁值将为：

$$q_{s_k}+(A\times p_{s_1}^2+B\times p_{s_1}+C)+\sum_{j=1}^{k-1}(A(p_{s_{j+1}}-q_{s_j})^2+B(p_{s_{j+1}}-q_{s_j})+C)$$

小猫想让自己的烦躁值尽量小，请你帮它求出所有可行的回家路线中，能得到的最 小的烦躁值。题目保证至少存在一条可行的回家路线。

inputFormat:
第一行五个整数 $n, m, A, B,C$，变量意义见题目描述。

接下来 $m$ 行，第 $i$ 行四个整数 $x_i, y_i, p_i, q_i$，分别表示 $i$ 号列车的出发站、到达站、出发时刻与到达时刻。

outputFormat: 输出仅一行一个整数，表示所求的答案。

hint:
对于所有的测试点，保证 $2\le n\le 10^5$，$1\le m\le  10^6$，$0\le
A\le 10$，$0\le B,C\le 10^7$，$1\le x_i,y_i\le n$，$x_i\neq y_i$，$0\le p_i<q_i\le 4\times 10^4$。


title: [eJOI2017] 经验

description:
X 公司有 $n$ 个员工。这个公司的员工之间的关系构成了一个树形结构。CEO 位于结构的顶端（树的根），他有一些下属（树根的子结点），下属又有下属……最后是一些底层员工（叶结点），没有下属。

这些员工被从 $1$ 到 $n$ 标号，且 CEO 的标号为 1。每个员工有一个 ***经验值***，第 $i$ 个员工的经验值为 $W_i$ 。

这个公司有一个大工程需要完成，所以公司的管理者想要将这个树形结构分裂重组为更小的团队。分裂的方式应遵循以下的规则：

- 任何一个团队至少由一个人组成，每个员工必须属于恰好一个团队。
- 对于任何一个团队，假设团队的成员 **按原来的层次等级由低到高排序之后**  为 $\{j_1,j_2,j_3,...,j_k\}$ ，那么须满足：对于$\forall i \in [1,k-1]$ 满足 $j_i$ 为 $j_{i+1}$ 的上司。

定义一个团队的总经验值为这个团队的所有成员的经验值的极差，换句话说，就是这个团队里所有成员经验值的最大值减去最小值。整个公司得到的总经验值就是所有团队的经验值之和。

你的任务是求出整个公司可以得到的经验值的最大值。

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

第二行，$n$ 个整数：$W_1,W_2,...,W_n$。

接下来 $n-1$ 行，每行两个整数 $u,v$ ，表示 $v$ 是 $u$ 的下属。

outputFormat: 一个整数表示答案。

hint:
#### 样例 1 解释

![GBNNDJ.png](https://s1.ax1x.com/2020/04/05/GBNNDJ.png)

一种方案是 $\{1,5,3\},\{6,2,4\},\{7\}$。

或者是 $\{1, 5\}, \{3\}, \{6, 2, 4\}, \{7\}$。

#### 数据规模与约定

- 对于大约 $20\%$ 的数据，保证：$n\le 20$。
- 对于大约 $50\%$ 的数据，保证：$n\le 5\times 10^3$。
- 对于另外大约 $10\%$ 的数据，保证：每个员工至多有一个下属。
- 对于所有数据，保证：$1\le n\le 10^5,0\le W_i\le 10^9$。

#### 说明

原题来自：[eJOI2017](www.ejoi.org) Problem E [Experience](http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_2/EN/experience_statement-en.pdf)

翻译提供： @[```_Wallace_```](https://www.luogu.com.cn/user/61430)


title: [eJOI2017] 游戏

description:
Alice 和 Bob ~~又双叒叕~~ 在玩游戏。

他们有一个由 $n$ 个 $\le n$ 的正整数组成的序列。序列中的元素被从 $1$ 到 $n$ 标号。序列中可能存在相同的数字。游戏开始时有一个可重集 $S$ ，包含了序列的前 $p$ 个元素。两人现在开始了游戏，Alice 先手。每一步游戏：

1. 玩家选择一个 $S$ 中的数并将其从 $S$ 中取出，然后将自己的分数加上这个取出的数的值（一开始两人的分数都为零）。
2. 序列中的下一个数字（如果还有剩余）将会被添加到集合 $S$ 中（如果序列已经为空，则跳过此操作）。也就是说，从 $S$ 中取出第一个后，将序列的第 $p+1$ 个数字添加到集合中，在第二个之后，将序列的第 $p+2$ 个数字添加到集合中，以此类推。

游戏进行直到 $S$ 为空为止。我们假设两个玩家都非常聪明（即总是使自己利益最大化）。游戏的结果为 Alice 的分数减去 Bob 的分数。

现在，你的任务是写一个程序，计算 $k$ 个（给定序列相同的）游戏的结果。

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

第二行，$n$ 个正整数 $a_1,a_2,...,a_n$，描述游戏开始的序列。

第三行，$k$ 个正整数 $p_1,p_2,...,p_k$，$p_i$ 表示第 $i$ 次游戏，有 $p=p_i$ 。

outputFormat:
输出包含 $k$ 个正整数，一行一个。

第 $i$ 个正整数表示第 $i$ 次游戏的结果。

hint:
#### 样例 1 解释

输入确定了你需要处理 $2$ 个游戏。这两个游戏中的序列是相同的，至是开始时的可重集 $S$ 不同。第一个游戏为 $\{2, 4, 2, 3\}$ ，第二个为 $\{2,4,2\}$ 。

#### 数据规模与约定

- 对于前 $10\%$ 的数据，保证 $1\le n\le 10$。
- 对于前 $30\%$ 的数据，保证 $1\le n\le 600$。
- 对于前 $50\%$ 的数据，保证 $1\le n\le 10^4,1\le k\le 10^3$。
- 对于所有数据，保证 $1\le n\le 10^5,1\le k\le 2\times 10^3,k\le n,a_i\in[1,n],p_i\in[1,n]$。

#### 说明

原题来自： [eJOI2017](www.ejoi.org) Problem F. [Game](http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_2/EN/game_statement-en.pdf)


title: [eJOI2018] 山

description:
Innopolis 城里有 $n$ 座山，第 $i$ 座的高度为 $a_i$。

美观起见，当一座山比它两边的山（如果存在）**严格** 地高时，才能在这座山上建房子。

有一台挖掘机，每小时可以将任意一座山的高度降低 $1$，同一时间挖掘机只能在一座山上工作。山的高度可以被降为 $0$ 或负数。

请求出当 $1\leq k\leq \lceil\frac{n}{2}\rceil$ 时，建造 $k$ 座房子（即至少使得 $k$ 座山满足上面的要求）时，挖掘机至少需要工作几小时。

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

第二行，$n$ 个整数 $a_{1\cdots n}$，表示数列 $\{a_i\}$。

outputFormat: 一行，$\lceil\frac{n}{2}\rceil$ 个整数，第 $i$ 个整数表示 $k=i$ 时的答案。


title: [eJOI2018] 循环排序

description:
给定一个长为 $n$ 的数列 $\{a_i\}$ ，你可以多次进行如下操作：

选定 $k$ 个不同的下标 $i_1,i_2\cdots,i_k$（其中 $1\leq i_j\leq n$），然后将 $a_{i_1}$ 移动到下标 $i_2$ 处，将 $a_{i_2}$ 移动到下标 $i_3$ 处，……，将 $a_{i_{k-1}}$ 移动到下标 $i_k$ 处，将 $a_{i_k}$ 移动到下标 $i_1$ 处。

换言之，你可以按照如下的顺序轮换元素：$i_1\rightarrow i_2\rightarrow\cdots\rightarrow i_{k}\rightarrow i_1$。

例如：$n=4,\{a_i\}=\{10,20,30,40\},i_1=2,i_2=3,i_3=4$ ，则操作完成后的 $a$ 数列变为 $\{10,40,20,30\}$。

你的任务是用操作次数最少的方法将整个数列排序成不降的。注意，所有操作中选定下标的个数总和不得超过 $s$ 。如果不存在这样的方法（无解），输出 `-1`。

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

第二行，$n$ 个整数 $a_{1\cdots n}$，表示数列 $\{a_i\}$。

outputFormat:
如果无解，仅输出 `-1`。

否则，第一行输出一个整数  $q$（可以为 $0$ ，参见样例 3 ），表示最少需要进行的操作次数。

接下来 $2\times q$ 行描述每次操作。

对于每次操作，先输出一个整数 $k$ 表示此操作选定的下标数量，然后在下一行中输出 $k$ 个整数 $i_{1\cdots k}$。

在操作次数 $q$ 最少的情况下，你可以输出任意一种可行方案。

hint:
【样例一解释】

你可以用两次操作 $1\rightarrow 4\rightarrow 1$ 和 $2\rightarrow 3\rightarrow 5\rightarrow 2$ 排序数组，但这样会 WA，因为你的任务是最小化 $q$ ，而最优解的 $q=1$。

一种可行的方法是 $1\rightarrow 4\rightarrow 2\rightarrow 3\rightarrow 5\rightarrow 1$，即样例输出。

【样例二解释】

所有操作中选定下标的个数总和的最小值为 $4$（一种可行的方法是 $1\rightarrow 2\rightarrow 1$ 和 $3\rightarrow 4\rightarrow 3$），因此无解。

【样例三解释】

数组已经有序，因此不需要进行操作。

补充说明：样例 4 和 5 满足子任务 6 和 7 的限制。

---

【数据范围】

对于 $100\%$ 的数据：$1\leq n\leq 2\times 10^5$，$0\leq s\leq 2\times 10^5$，$1\leq a_i\leq 10^9$。

| 子任务编号 | 分数 | 限制 |
| :-----------: | :-----------: | :-----------: |
| $1$ | $0$ | 样例 |
| $2$ | $5$ | $n,s\leq 2 且 1\leq a_i\leq 2$ |
| $3$ | $5$ | $n\leq 5$ |
| $4$ | $5$ | $1\leq a_i\leq 2$ |
| $5$ | $10$ | $a 是个排列，s=2\times n$ |
| $6$ | $10$ | $a 是个排列，n\leq 10^3$ |
| $7$ | $15$ | $a 是个排列$ |
| $8$ | $15$ | $s=2\times n$ |
| $9$ | $15$ | $n\leq 10^3$ |
| $10$ | $20$ | 无特殊限制 |

---

来源：[eJOI2018](http://ejoi2018.org/) Problem F「Cycle Sort」

说明：翻译来自 [LOJ](https://loj.ac/problem/2818)


title: [eJOI2018] AB 串

background: **题目译自 [eJOI2018](http://ejoi2018.org/) Problem C.** ***AB-Strings***

description:
你有两个字符串 $s,t$，它们其中仅包含字母 `a` 和 `b`。你可以多次进行如下操作：选出一个 $s$ 的前缀和一个 $t$ 的前缀并交换它们。（注意，这个前缀既**可以为空**也可以为整个串）

你的任务是找出一个操作序列使得进行这些操作后，一个字符串只包含字符 `a`，而另一个只包含字符 `b`。

你应该尽可能的进行最少的操作次数，但非最优解仍可能得到一部分分数，详情见“数据范围与提示”一栏。

inputFormat: 输入两行为两个字符串 $s,t$。

outputFormat:
输出第一行为一个整数 $n$（$0\leq n\leq 5\times 10^5$），表示操作总数。

接下来的 $n$ 行，每行包含两个整数 $a_i,b_i$，分别为 $s,t$ 在这次交换中的前缀长度。

如果有多种可能的方案，则可以输出任意一种。

hint:
#### 样例 $1$ 解释：
在这个样例中，首先把第一个串 $1$ 个长度的前缀与第二个串 $0$ 个长度的前缀交换，即将 `b` 插入第二个串开头。这时两个串变成了 `ab` 和 `bbb`。接下来把第一个串 $1$ 个长度的前缀与第二个串 $3$ 个长度的前缀交换，即交换 `a` 和 `bbb`，此时两个串变成了 `bbbb` 和 `a` ，达成目标。

#### 样例 $2$ 解释：

已经是最终要求的状态了。

------

#### 计分策略

设 $n$ 为你给出的操作数量，$m$ 为标准答案，**本题使用 SPJ**。

- 如果所有任务中 $n=m$，那么将得到 $100\%$ 的分数。

- 如果所有任务中 $n\leq m+2$，那么将得到 $70\%$ 的分数。（四舍五入到最接近的整数）

- 如果所有任务中 $n\leq 2m+2$，那么将得到 $50\%$ 的分数。（四舍五入到最接近的整数）

- 如果所有任务中 $n\leq 5\times 10^5$，那么将得到 $30\%$ 的分数。（四舍五入到最接近的整数）

- 如果至少一个任务中 $n > 5\times 10^5$，那么将得到 $0\%$ 的分数。

----

对于 $100\%$ 的数据，保证 $1\leq \lvert s\rvert,\lvert t\rvert \leq 2\times 10^5$，$\lvert s\rvert,\lvert t\rvert$ 分别代表 $s,t$ 的长度，且保证至少有一个串中包含至少一个字符 `a`，至少一个串中包含至少一个字符 `b`。

#### 数据限制

|子任务编号|分数|限制|
|:-:|:-:|:-:|
|$1$|$5$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 6$，这两个字符串中共含有一个字符 `a`|
|$2$|$10$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 6$ |
|$3$|$20$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 50$ |
|$4$|$20$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 250$ |
|$5$|$20$| $1\leq \lvert s\rvert,\lvert t\rvert \leq 2\times 10^3$ |
|$6$|$25$|无特殊限制|


title: [eJOI2018] 护照

description:
Gleb 是来自 Innopolis 的著名编程老师，他计划接下来参加 $n$ 场编程训练营。每场训练营会在不同的国家举办。他要申请每个国家的签证。

对于第 $i$ 场训练营，Gleb 知道出发日期 $s_i$，持续时长 $len_i$，和在该国申请签证需要的时间 $t_i$。Gleb 有 $P$ 本有效的护照并且他需要决定用哪本护照来申请签证。

第 $i$ 场训练营 Gleb 将在第 $s_i$ 天早上出发，在第 $s_i+len_i-1$ 天傍晚返回。

如果要在第 $d$ 天申请签证，Gleb 当天中午必须在 Innopolis。这意味着 Gleb 在参加训练营期间不能申请签证，包括第一天和最后一天。如果一场训练营结束后紧接着 Gleb 要去参加第二场训练营，他也无法在此期间申请签证。Gleb 最早可以申请签证的时间是第 $1$ 天。

在第 $d$ 天申请完第 $i$ 个国家的签证后，Gleb 会在第 $d+t_i$ 天中午获得该国的护照（即使当天 Gleb 不在 Innopolis）。

如果第 $s_i$ 天早上 Gleb 没有相应国家的护照，他就无法参加第 $i$ 场训练营。**注意，当时护照不能在办理签证的使馆里面。**

请你帮助 Gleb 找到一种申请签证的方案，使他可以顺利参加所有的训练营。

inputFormat:
输入第一行两个整数 $n,P$，分别表示训练营的个数和 Gleb 拥有的护照的个数。

接下来 $n$ 行，每行三个整数 $s_i,len_i,t_i$，表示第 $i$ 场训练营的开始时间，持续时长和对应国家办理签证所需时间。

保证每场都不相交。

outputFormat:
**本题存在 Special Judge**。

如果没有方案使得 Gleb 参加所有训练营，只用输出 `NO`。

否则，第一行输出 `YES`。

接下来输出 $n$ 行，每行两个整数分别表示对于每个训练营 Gleb 申请该国签证所用的护照的编号和他申请签证的日期。

输出顺序需要与输入顺序一致。日期从 $1$ 开始编号，护照编号 $1\cdots P$。

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

#### 样例一解释

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

每个单元格代表一天。矩形代表某一次训练营，从某一天早上开始，在某一天晚上结束。带角的矩形某一次申请签证的过程，从某一天中午开始，在某一天中午结束。一场训练营与他对应的申请签证的过程颜色相同。

#### 样例二解释

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

#### 样例三解释

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

上面代表第一个护照，下面代表第二个护照。

---

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

**本题采用多测试点捆绑测试，共 9 个子任务**。

- Subtask 1（5 pts）：$n\leq 2$，$s_i,len_i,t_i\leq 100$，所有 $t_i$ 均相等，$P=1$；
- Subtask 2（8 pts）：$n\leq 10$，$s_i,len_i,t_i\leq 100$，所有 $t_i$ 均相等，$P=1$；
- Subtask 3（7 pts）：$n\leq 10$，$s_i,len_i,t_i\leq 100$，所有 $t_i$ 均相等；
- Subtask 4（12 pts）：$n\leq 16$，$s_i,len_i,t_i\leq 100$，$P=1$；
- Subtask 5（13 pts）：$n\leq 16$，$s_i,len_i,t_i\leq 100$；
- Subtask 6（15 pts）：$n\leq 16$，$s_i,len_i,t_i\leq 10^7$，$P=1$；
- Subtask 7（15 pts）：$n\leq 16$，$s_i,len_i,t_i\leq 10^7$；
- Subtask 8（15 pts）：$n\leq 20$；
- Subtask 9（10 pts）：无特殊限制。

对于全部的测试点，保证 $1\leq n\leq 22$，$1\leq P\leq 2$，$1\leq s_i,len_i,t_i\leq 10^9$。

---

来源：[eJOI2018](http://ejoi2018.org/) Problem B「Passports」。

说明：翻译自翻。


title: [传智杯 #2 决赛] 补刀

description:
UIM 在写程序的空闲玩一款 MOBA 游戏。

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

当敌方的小兵进入到我方防御塔的范围内，就会持续受到防御塔造成的伤害；当然我方英雄也可以对它造成伤害。当小兵的血量降到了 0 或者更低，就会被击杀。为了获得经验，UIM 希望在防御塔将这个小兵杀死之前，亲自补刀将其击杀。

为了简化问题，我们假设这个小兵有 $h$ 点的生命值。每次防御塔的攻击可以给小兵造成 $x$ 点伤害，而你的英雄每次攻击可以给小兵造成 $y$ 点伤害。你的攻击速度和防御塔攻击速度相同，所以你可以在防御塔第一次攻击小兵之前，或者每次防御塔攻击之后，选择是否对小兵进行一次攻击，当然你也可以选择不攻击。

现在想知道，给出这些信息，判断英雄是否有办法将这个小兵击杀？

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

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

接下来 $T$ 行，每行三个非负整数 $h,x,y$，其意义已经在题目描述中给出。

outputFormat: 输出 $T$ 行。对于每组数据，如果可以最后将小兵击杀，输出 `Yes`，否则输出 `No`。


title: [传智杯 #2 决赛] 建设岛屿

description:
“动物森友会”是一款自由度很高的游戏，可以在自己的无人岛上建房子、种花种树，还能钓鲈鱼。

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

如果一个 $(2k-1)\times(2k-1)$ 的正方形土地满足最外圈的高度是 1，第二圈的高度是 2……以此类推，它就是一个高度为 k 的金字塔。下图是高度为 1 到 4 的金字塔的示例：

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

小 A 的岛大小是 $n\times m$ 的矩形，每个位置的高度都是已知的。他想要建造一个大大的金字塔。他拥有最多 $k$ 次改造地形机会，每次可以选择一个坐标，将这个点的高度增加 1，但是不能减少高度。请问，他能完成的金字塔的最高高度是多少？

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

第一行为一个整数 $T$，代表数据的组数。

对于每组数据，第一行是三个整数 $n,m,k$，表示岛的大小和操作次数上限。接下来是个 $n$ 行 $m$ 列的矩阵，表示最开始的高度，每个数字之间用空格分隔。

outputFormat: 输出 $T$ 行，对于每行，都输出一个整数，表示每组数据下可以完成金字塔的最大高度。

hint: 对于所有测试数据，$1\le T \le 5$，$1 \le n,m \le 350$，$1\le k \le 10^8$，初始高度 0 到 50 的非负整数。


title: [传智杯 #2 决赛] 传送门

description:
传智专修学院里有 $n$ 栋教学楼，有 $m$ 条双向通行道路连接这些教学楼，不存在重边和自环。每条道路都有一定的长度，而且所有教学楼之间都可以直接或者间接的通过道路到达。我们可以很容易的求出这些教学楼之间的最短路。

为了使交通更为顺畅，校方决定在两个教学楼里增设一对传送门。传送门可以将这对教学楼的距离直接缩短为 0。利用传送门，某些教学楼之间的最短路的距离就变短了。

由于预算有限，学校里只能安装一对传送门。但是校长希望尽可能方便学生，使任意两点之间的最短路长度的总和最小。当然啦，从 $x$ 教学楼到 $y$ 教学楼的长度和从 $y$ 教学楼到 $x$ 教学楼的长度只需要统计一次就可以了。

inputFormat:
输入第 1 行两个正整数 $n,m(n\le 100,m\le\frac{1}{2}n(n-1))$，代表教学楼和道路数量。

接下来 $m$ 行，每行三个正整数 $x_i,y_i,w_i(0 <w_i \le 10^4)$，表示在教学楼 $x_i$  和 $y_i$  之间，有一条长度为 $w_i$  的道路。

outputFormat: 输出一行，在最优方案下的任意点对的最短道路之和。

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

样例如图。当在 1 和 4 号教学楼架设一对传送门时，1 → 2 的最短路是 3，1 → 3 的最短路是 0+2，1 → 4 的最短路是 0，2 → 3 的最短路是 4，2 → 4 的最短路是 3+0，3 → 4 的最短路是 2，最短路之和是 14，是最佳方案。


title: [传智杯 #2 决赛] 课程安排

description:
传智播客的课表上按顺序提供 $n$ 节课程，课程可能是 Java、Python 或者前端开发等等，我们用不超过 $n$ 的正数代表每一节课程的种类。学员可以从这个课程序列选取连续的一小段的课程序列，作为一周的学习任务。

为了使学习任务不那么枯燥，学员不想连续上两节相同的课。特殊的，这一周学习任务的开头和结尾也不能是相同的课。为了保证学习效果，一周内至少要学完 $l$ 节课程。

请问，我们有多少种合法的选课方案？

两种选课方案，只要选取的课程序列在原序列的开头和结尾有至少一个位置不一致，那么就可以认为是不同的选课方案。注意，即使 $l$ 是 1，一周只安排一次课也是不合法的，至少需要安排 2 次课。

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

第一行为一个整数 $T$，代表数据的组数。

对于每组数据，第一行输入两个正整数 $n$ 和 $l$。接下来一行输入 $n$ 个非负整数 $c_i$ 表示课程种类编号。

outputFormat: 对于每组数据，输出一行一个数，表示方案数。

hint:
**样例解释**

对于第一组数据，有 [1,2] 和 [2,3] 和 [1,2,3] 三种方法。

对于第二组数据，由于至少要选 3 门课，只有 [1,2,3] 和 [2,3,1] 两种方法。

**数据范围**

测试数据不超过 5 组，$1\le N \le 5 \times 10^5$，$1\le l,c_i \le N$


title: 「Wdsr-2」间歇泉

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

description:
有一个间歇泉，冒出了 $n$ 杯水，由于一些原因，每杯水的温度、体积不同。第 $i$ 杯水的温度为 $c_i$，体积为 $a_i$。

现在混合任意**两**杯水，每混合两杯水都会得到一个新的温度值，求可能得到的第 $k$ 高的温度值（不计热量损失）。

**你的答案建议至少保留小数点后 $\bm3$ 位（与标准答案之差在 $\bm{10^{-2}}$ 以内即视为通过）。**

inputFormat:
第一行一个数 $n,k$，意义如题述。

接下来 $n$ 行，每行两个数 $a_i,c_i$。

outputFormat: 一行一个实数，表示混合后的水的第 $k$ 高温度。

hint:
#### 样例 1 说明

第 $1$ 和第 $5$ 杯水混合，得到 $4.5$ 的温度值。可以发现，这是可能得到的最高水温。

#### 样例 2

见题目附件中 $\textbf{\textit{pour2.in/pour2.ans}}$。

#### 数据规模与约定

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

- $\textbf{Subtask 1}\text{ (10 pts)}$：$1\le n\le 10$。
- $\textbf{Subtask 2}\text{ (40 pts)}$：保证 $k=1$。
- $\textbf{Subtask 3}\text{ (50 pts)}$：无特殊限制。
- $\textbf{Subtask 4}\text{ (0 pts)}$：Hack 数据。

对于 $100\%$ 的数据，有 $1\le n\le 10^5$，$1\le k\le \dfrac{n \times (n - 1)}{2}$，$1\le a_i,c_i\le 10^9$。

子任务 2/3/4 时限 $\text{2 s}$，子任务 1 时限 $\text{1 s}$。

#### 前置知识

对于两杯体积、温度分别为 $(a_i,c_i),(a_j,c_j)$ 的水，混合后温度为：

$$
T=\dfrac{a_ic_i+a_jc_j}{a_i+a_j}
$$

#### 说明

本题数据采用 [SvRan](https://github.com/Sept0913/SvRan) 生成，仅用时 $3\min$。


title: [CCO2017] Vera 与道路建设

description:
Vera 喜欢远足，因此她要建立自己的公路网。公路网包含 $v$ 个地点，这些地点分别编号为 $1,2,...,v$。公路网由 $e$ 条连接 $a_i$ 和 $b_i$ 的双向道路组成。保证图联通，允许有重边。

Vera 认为满足先从 $a$ 走到 $b$ 然后再回到 $a$，使得每条道路被通过不超过一次且满足 $a < b$ 的两个地点 $a,b$ 是一对 **完美点对**。她认为如果公路网恰好包含 $k$ 个完美点对，那么她的公路网就是美丽的。

给定 $k$，帮 Vera 找到美丽公路网。

inputFormat: 输入只有一行，为一个整数 $k$。

outputFormat:
按照以下格式输出一个美丽公路网：

- 第一行为顶点的数量 $v$ 与边数 $e$；

- 下面的 $e$ 行每行应包含代表从 $a_i$ 至 $b_i$ 有一条边的两个整数 $a_i$ 与 $b_i$（$1 \le i \le e$）。

道路的输出顺序无关紧要。如果有多个美丽公路网，你可以输出它们中的任意一个。

hint:
#### 样例解释

对于样例 $1$，完美点对为 `1,2` 和 `3,4`。

对于样例 $2$，每个点对都是完美点对。

#### 数据范围及约定

**本题采用多测试点捆绑测试，共有 $3$ 个子任务。**

- Subtask 1（12 points）：$0 \le k \le 10^3$；
- Subtask 2（24 points）：$0 \le k \le 10^5$；
- Subtask 3（64 points）：$0 \le k \le 10^7$。

对于全部的测试点，保证 $0 \le k \le 10^7$，$1 \le v,e \le 5 \times 10^3$。

来源：[CCO 2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/index.html) Day1「[Vera and Trail Building](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%202/day1.pdf)」。

说明：翻译来自 [LOJ](https://loj.ac/problem/2750)。


title: [CCO2017] 矩形帝国的霸业

description:
很久很久以前，矩形帝国统治了笛卡尔大陆。帝国繁荣昌盛，在无尽的战争与征服之中，帝国的土地一天天扩大。

矩形帝国实行 **矩形区域制**。这些地区都满足三个特殊标准。

1. 帝国的领土被划分为各个地区，且每一片土地属于且只属于一个地区；

2. 在地图上观察时，每个区域的形状必须是矩形且长边的长度是短边长度的两倍；

3. 区域各边的长度必须是整数，以 $Ξ$ 为单位（$Ξ$ 是矩形帝国的计量单位）。

帝国最初建立的时候，它由一个单一的区域组成。从那时起，为了扩充疆域，帝国会不断征服邻近区域。每当帝国控制一个新的区域时，他们总是建立一个独立的新区域，新区占用刚获得的全部土地。这意味的帝国只在乎他们想要征服的土地的几何属性。你可以假设没有两次征服出现在同一个地方。

帝国只能通过增加新区来扩充疆域。此外，每个地区一旦添加，就不会被修改或和另外一个合并。

矩形帝国的最后一个标准，是确保帝国的整体形状是一个矩形。不过，大矩形的长宽比可以不满足 $2:1$。

帝国的长度是 $n$，宽度是 $m$（以 $Ξ$ 为单位）。你的任务是估计在 $n \times m$ 的大小下帝国的区域数。在所有可能的情况下，帝国的最小区域数和最大区域数分别是什么？

inputFormat: 输入只有一行两个整数，分别为 $n,m$。

outputFormat: 输出只有一行两个整数，第一个是最小的区域数，第二个是最大的区域数。

hint:
#### 样例解释

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

#### 数据范围及约定

**本题采用多测试点捆绑测试，共有 $3$ 个子任务。**

- Subtask 1（20 points）：$1 \le n,m \le 10^3$；
- Subtask 2（32 points）：$1 \le n,m \le 10^6$；
- Subtask 3（48 points）：$1 \le n,m \le 10^8$。

对于全部的测试点，保证 $1 \le n,m \le 10^8$。

来源：[CCO 2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/index.html) Day1「[Cartesian Conquest](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%202/day1.pdf)」。

说明：翻译来自 [LOJ](https://loj.ac/problem/2751)。


title: [CCO2017] Vera 与现代艺术

description:
在受到大画家毕加索的启发后，Vera 决定创造她的杰作。她有一张可以被简化成无限大的二维平面的画布。Vera 喜欢 $2$ 的整数次幂 $(1,2,4,8,16,...)$，并且将以 $2$ 的整数幂为步长给一些点染色。

Vera 将会染 $n$ 次，第 $i$ 次染色可以用三个整数 $x_i,y_i,v_i$ 描述。令 $a_i$ 为最大的不大于 $x_i$ 的 $2$ 的整数次幂，$b_i$ 为最大的不大于 $y_i$ 的 $2$ 的整数次幂，Vera 会用第 $v_i$ 种颜色在所有坐标满足 $(x_i+a_ip,y_i+b_iq)$ 的点上染色（ $p,q$ 为非负整数）。一个点可以被不同的颜色分别染多次，也可以被同种颜色重复染多次，一个点的颜色为所有染过这个点的颜色之和。

接下来 Vera 将提出 $Q$ 个问题。对于第 $j$ 个问题，她希望知道坐标为 $(r_j,c_j)$ 的点是什么颜色。如果一个点没有被染过色，这个点的颜色就为 $0$。

因为你被迫做 Vera 的助手，你不得不回答 Vera 的问题。

inputFormat:
第一行包括两个整数 $n,Q$，用一个空格分隔。

接下来 $n$ 行，每行三个空格隔开的整数 $x_i,y_i,v_i$，表示用第 $v_i$ 种颜色进行题目中的染色操作，参数为 $x_i$ 和 $y_i$。

再接下来 $Q$ 行，每行两个空格隔开的整数 $r_j,c_j$，表示询问点 $(r_j,c_j)$ 的颜色。

outputFormat: 输出共有 $Q$ 行，每行一个整数，第 $j$ 行的整数表示点 $(r_j,c_j)$ 的颜色。

hint:
#### 样例解释

令颜色 $1,2,3,4,5$ 分别为红色、蓝色、绿色、橙色和紫色。

令 $p,q$ 为非负整数，则：

- 坐标为 $(1+p,2+2q)$ 的点被染成了红色；
- 坐标为 $(3+2p,4+4q)$ 的点被染成了蓝色；
- 坐标为 $(4+4p,5+4q)$ 的点被染成了绿色；
- 坐标为 $(6+4p,3+2q)$ 的点被染成了橙色；
- 坐标为 $(7+4p,1+q)$ 的点被染成了紫色；

从 $(0,0)$ 到 $(11,11)$ 的坐标纸如图所示：

我们可以发现：

- $(2,6)$ 被染成了红色，所以它的颜色为 $1$；
- $(7,8)$ 被染成了红色、蓝色和紫色，所以它的颜色为 $1+2+5=8$；
- $(5,9)$ 没有被染色，所以它的颜色为 $0$；
- $(11,2)$ 被染成了红色和紫色，所以它的颜色为 $1+5=6$；
- $(10,7)$ 被染成了橙色，所以它的颜色为 $4$；
- $(4,5)$ 被染成了绿色，所以它的颜色为 $3$。

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

#### 数据范围及约定

- 对于 $20\%$ 的数据，$1 \le n,Q \le 2 \times 10^3$ ；
- 对于另外 $20\%$ 的数据，$y_i = 1(1 \le i \le n)$；
- 对于另外 $20\%$ 的数据，$1 \le n,Q \le 10^5$ 且 $1 \le r_j,c_j \le 10^9(1 \le j \le Q)$。
- 对于 $100\%$ 的数据，$1 \le n,Q \le 2 \times 10^5$，$i \le i \le n$，$1 \le v_i \le 10^4$，$1 \le x_i,y_i,r_j,c_j  \le 10^{18}$，$1 \le j \le Q$。

由于评测机原因，改题只保留最后 $10$ 个数据。

来源：[CCO 2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/index.html) Day1「[Vera and Modern Art](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%202/day1.pdf)」。

说明：翻译来自 [LOJ](https://loj.ac/problem/2752)。


title: [COCI2006-2007#3] PATULJCI

description:
白雪公主原本有 $7$ 个小矮人，但某天她遇到了 $9$ 个小矮人。

这九个小矮人都自称是白雪公主 $7$ 个小矮人中的一个。他们每人戴着一顶帽子，每个帽子上面写着 $[1,99]$ 这个区间内的一个数字。

白雪公主知道，她的 $7$ 个小矮人的帽子数字之和是 $100$。

她想请你确定，哪 $7$ 个小矮人是她自己的。

inputFormat: 输入共 $9$ 行，每行一个数描述这个小矮人的帽子上的数字。

outputFormat: 输出共 $7$ 行，每行为一个符合要求的小矮人的帽子的数字。按照输入的顺序给出答案。

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

输入数据均为小于 $100$ 的正整数，且保证有且仅有一组解。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #3](https://hsin.hr/coci/archive/2006_2007/contest3_tasks.pdf) *T1 PATULJCI***


title: [COCI2006-2007#3] NPUZZLE

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

给定一个 $4\times 4$ 的方格棋盘，里面有 $A\sim O$ 这 $15$ 个字母，还有一个 `.` （表示空位），字母的标准位置如图所示。

现在有一个被打乱的棋盘，你需要计算出所有字母从当前位置到自己的标准位置的[曼哈顿距离](https://baike.baidu.com/item/%E6%9B%BC%E5%93%88%E9%A1%BF%E8%B7%9D%E7%A6%BB/743092?fr=aladdin)之和。

inputFormat: 输入共 $4$ 行，每行 $4$ 个字符描述了这个棋盘。

hint:
#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #3](https://hsin.hr/coci/archive/2006_2007/contest3_tasks.pdf) *T2 NPUZZLE***


title: [COCI2006-2007#3] TROJKE

description:
给定一个 $n\times n$ 的方格纸，每个格子可能有一个大写字母，也可能为空。不会有同一个字母在方格纸中出现两次。

你在一条线上找到三个字母，使得这条线穿过三个字母所在的格子的中心。

请你求出方格纸上还有多少条这样的线。

inputFormat:
输入第一行为一个整数 $n$，表示方格纸的边长。

接下来的 $n$ 行，每行 $n$ 个字符，每个字符可能为一个大写字母或 `.`（空）。

outputFormat: 输出一行一个整数，表示方格纸上这种线的数量。

hint:
#### 样例 1 解释

注意在第一个样例中，任意三个字母都处在同一条线上，这时的答案相当于 $C^{3}_{4}=4$。

----

#### 数据规模与约定

对于 $100\%$ 的数据，保证 $3\le n\le 100$，不会有同一个字母在方格纸中出现两次。

---

#### 说明
**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #3](https://hsin.hr/coci/archive/2006_2007/contest3_tasks.pdf) *T3 TROJKE***。


title: 【模板】点分树 | 震波

background: 模板题，没有 $rap$ 。

description:
在一片土地上有 $n$ 个城市，通过 $n-1$ 条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为 $1$，其中第 $i$ 个城市的价值为 $value_i$。

不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。

接下来你需要在线处理 $m$ 次操作：

`0 x k` 表示发生了一次地震，震中城市为 $x$，影响范围为 $k$，所有与 $x$ 距离不超过 $k$ 的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。

`1 x y` 表示第 $x$ 个城市的价值变成了 $y$ 。

为了体现程序的在线性，操作中的 $x$、$y$、$k$ 都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为 $0$ 。

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

第二行包含 $n$ 个正整数，第 $i$ 个数表示 $value_i$ 。

接下来 $n-1$ 行，每行包含两个正整数 $u$、$v$，表示 $u$ 和 $v$ 之间有一条无向边。

接下来 $m$ 行，每行包含三个数，表示 $m$ 次操作。

outputFormat: 包含若干行，对于每个询问输出一行一个正整数表示答案。

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

对于 $100 \%$ 的数据，有 $1\leq n,m\leq 10^5, 1\leq u,v,x\leq n, 1\leq value_i,y\leq 10^4,0\leq k\leq n-1$ 。

upd：样例范围与题目真实数据范围不同，以提示中给出的数据范围为准。

#### 说明
题目来源：BZOJ3730。


title: [COCI2006-2007#3]  TENKICI

description:
在一个 $n\times n$ 的棋盘上，有 $n$ 辆坦克，每辆坦克可以攻击到自己所在的行和列上的所有格子。

刚开始一个孩子正在畅快淋漓地玩着这局自己心目中的“二战”，但是他的母亲突然就叫他吃饭了。

他十分不舍，并打算对这些坦克进行若干次移动，每次向上、下、左、右任意方向移动一辆坦克一个格子的距离。

他现在想请你解决，最少需要多少次才能使得这 $n$ 个坦克互相无法攻击到？当然，为了不动脑子并快点去吃饭，你还需给出对应的方案之一。

inputFormat:
输入第一行一个整数 $n$，表示棋盘的边长以及坦克的数量。

接下来的 $n$ 行，每行两个整数 $r,c$，表示母亲叫他吃饭时这辆坦克所处的位置为第 $r$ 行第 $c$ 列。

行和列分别从上到下，从左到右，用 $1\sim n$ 标号，保证不存在任何两辆坦克处于相同的位置。

outputFormat:
输出第一行为一个整数 $k$，表示最少的移动次数。

接下来的 $k$ 行，每行先输出一个整数，表示此次将要移动的坦克；再输出一个字符，为`L`（左），`R`（右），`U`（上），`D`（下）之一，表示移动的方向。

**正确的移动序列可能不唯一，输出任意一种即可，本题使用 SPJ。**

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

对于 $100\%$ 的数据，保证 $5\le n\le 500$，$1\le r,c\le n$。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #3](https://hsin.hr/coci/archive/2006_2007/contest3_tasks.pdf) *T4 TENKICI***


title: [PA2011] Journeys

description:
一个星球上有 $n$ 个国家和许多双向道路，国家用 $1\sim n$ 编号。

但是道路实在太多了，不能用通常的方法表示。于是我们以如下方式表示道路：$(a,b),(c,d)$ 表示，对于任意两个国家 $x,y$，如果 $a\le x\le b,c\le y\le d$，那么在 $x,y$ 之间有一条道路。

首都位于 $P$ 号国家。你想知道 $P$ 号国家到任意一个国家最少需要经过几条道路。保证 $P$ 号国家能到任意一个国家。

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

之后 $m$ 行，每行 $4$ 个整数 $a,b,c,d$。

outputFormat: $n$ 行，第 $i$ 行表示 $P$ 号国家到第 $i$ 个国家最少需要经过几条路。

hint: 对于所有测试点，保证 $1\le n\le 5\times 10^5$，$1\le m\le 10^5$，$1\le a\le b\le n$，$1\le c\le d\le n$。


title: [COCI2006-2007#3] LISTA

background: Mirko 收到了一份礼物——一个崭新的双向链表！

description:
这个长度为 $n$ 的链表包含 $1\sim n$ 这 $n$ 个节点，从左到右排列。

可以对这个链表执行两种操作：

- `A x y`：把 $x$ 节点放到 $y$ 节点前。

- `B x y`：把 $x$ 节点放到 $y$ 节点后。

#### 例如：

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

这是一个有 $6$ 个节点的链表的初始状态。

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

这是进行操作 `A 1 4` 后的链表状态。

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

这是再进行操作 `B 3 5` 后的链表状态。

Mirko 把这个链表玩了几个小时。每进行一次操作，他都会在纸上记录下来。

当他兴致已尽，打算把链表恢复时，他惊讶地发现自己不知道最快的恢复方法，因为他只知道这些节点的结束位置。

请你运用 `A` `B` 两个操作，找出操作数最少的恢复方案并输出每一次的操作。

inputFormat:
输入第一行为两个整数 $n,k$，表示链表的节点个数和 Mirko 的操作次数。

接下来的 $k$ 行，每行描述一个 Mirko 在纸上记录下来的操作，格式如题目描述所示。

outputFormat:
输出第一行为一个整数 $K$，表示最少的恢复方案。

接下来的 $K$ 行，每行描述一个恢复时的操作，格式与输入相同。

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

对于 $100\%$ 的数据，$2\le n\le 5\times 10^5$，$0\le m\le 1\times 10^5$。

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #3](https://hsin.hr/coci/archive/2006_2007/contest3_tasks.pdf) *T6 BICIKLI***

感谢 @[andyli](https://www.luogu.com.cn/user/84282) 提供SPJ。