title: [NOI2012] 魔幻棋盘

description:
将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘，它是一个 $N$ 行 $M$ 列的网格棋盘，每个格子中均有一个正整数。棋盘守护者在棋盘的第 $X$ 行第 $Y$ 列（行与列均从 $1$ 开始编号）并且始终不会移动。棋盘守护者会进行两种操作：

* （a）询问：他会以自己所在位置为基础，向四周随机扩展出一块大小不定的矩形区域，向你询问这一区域内所有数的最大公约数是多少。
* （b）修改：他会随意挑选棋盘上的一块矩形区域，将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友，当你连续答对 $19930324$ 次询问后会得到一个惊喜噢！”。小 Q 十分想得到这个惊喜，于是每天都在玩这个玩具。但由于他粗心大意，经常算错数，难以达到这个目标。于是他来向你寻求帮助，希望你帮他写一个程序来回答棋盘守护者的询问，并保证 $100\%$ 的正确率。

为了简化问题，你的程序只需要完成棋盘守护者的 $T$ 次操作，并且问题保证任何时刻棋盘上的数字均为不超过 $2^{62} - 1$ 的正整数。

inputFormat:
第一行为两个正整数 $N,M$，表示棋盘的大小。

第二行为两个正整数 $X,Y$，表示棋盘守护者的位置。

第三行仅有一个正整数 $T$，表示棋盘守护者将进行 $T$ 次操作。

接下来 $N$ 行，每行有 $M$ 个正整数，用来描述初始时棋盘上每个位置的数。

接下来 $T$ 行，按操作的时间顺序给出 $T$ 次操作。每行描述一次操作，以一个数字 $0$ 或 $1$ 开头：

* 若以数字 $0$ 开头，表示此操作为询问，随后会有四个非负整数 $x_1,y_1,x_2,y_2$，表示询问的区域是以棋盘守护者的位置为基础向上扩展
 $x_1$ 行，向下扩展 $x_1$ 行，向左扩展 $y_1$ 列，向右扩展 $y_2$ 列得到的矩形区域（详见样例）。
* 若以数字 $1$ 开头，表示此操作为修改，随后会有四个正整数 $x_1,y_1,x_2,y_2$ 和一个整数 $c$，表示修改区域的上、下边界分别为第 $x_1,x_2$ 行，左、右边界分别为第 $y_1,y_2$ 列（详见样例），在此矩形区域内的所有数统一加上 $c$（注意 $c$ 可能为负数）。

outputFormat: 对于每次询问操作，每行输出一个数，表示该区域内所有数的最大公约数。

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

对于第一、第四次操作（查询操作）后，加粗部分表示查询区域。

对于第二、第三次操作（修改操作）后，加粗部分表示修改区域。

测试数据分为 A、B、C 三类：

A 类数据占 $20\%$，满足 $N \leq 100$，$M \leq 100$，$T \leq 2\times 10^4$。

B 类数据占 $40\%$，满足 $N = 1$，$M \leq 5\times 10^5$，$T \leq 10^5$。

C 类数据占 $40\%$，满足 $N \times M \leq 5\times 10^5$，$T \leq 10^5$。

在每类数据中，均有 $50\%$ 的数据满足每次修改操作仅含一个格子（即 $x_1 = x_2$，$y_1 = y_2$）。

输入数据保证满足题目描述中的所有性质。


title: GTY的人类基因组计划2

type: P

background: GTY 决心改变人类基因！！

description: GTY 召唤了 $n$ 个人来做实验，GTY 家的房子很大，有 $m$ 个房间一开始所有人都在 $1$ 号房间里，GTY 会命令某人去某个房间等待做实验，或者命令一段区间的房间开始实验，实验会获得一些实验信息点数，点数为房间里的人数，如果一个房间里的一群人已经做过实验了那么这些人将不会增加实验信息点数（不会增加是针对这一群人的，不是对这群人中的每个人，即 $1,2,3$ 做了实验，$1,2$ 再做实验还会增加 $2$ 点实验点数）。

inputFormat:
第一行两个整数 $n,m,q (n,m,q \leq 10^5)$ 表示人数，房间数和操作数

接下来 $q$ 行每行一个操作 `C i j` 表示让第 $i$ 个人去房间 $j$，`W l r` 表示让区间 $[l,r]$ 的房间做实验。

outputFormat: 对于每一个 $W$ 操作，输出一个数，表示此次操作所获得的实验点数。

hint: 善用 STL。


title: 果汁店的难题

description:
炎热的夏天，来上一杯现榨的冰爽果汁想想都是一件惬意的事情！话说小王就看准了这一商机，在学校附近开了这么一家果汁店，但是最近他碰到了一个不大不小的难题：小王的果汁店里准备了 $K$ 台榨汁机，当然每台榨汁机只能榨一种果汁，在某个时段内，一个客人点了某种果汁，如果恰好有某台果汁机榨过这种果汁，那么就直接给客人用这台果汁机接着榨就可以了，但是如果点的是一种新的果汁就需要找一台干净的果汁机来用，问题就出在这，如果这时候还有空的果汁机还好，如果没有的话小王就需要将某台刚才用过的拿去清洗，清洗的话呢就得浪费很多的时间和很多的水，小王是个很有经济头脑的人，他想知道在排队客人需求已知的情况下最少需要清洗多少次果汁机？假定开始时所有果汁机都是干净的，为了方便描述，我们将果汁编号为 $1$ （橙汁）, $2$（苹果汁）， $3$ （葡萄汁）......

[友情提示：本店不售卖混合果汁]

inputFormat: 每组测试数据第一行包括两个整数$K,N$，其中，$K$ 表示小王准备了 $K$ 台干净的榨汁机，$N$ 表示排队等待的有 $N$ 个客人，接下来 $N$ 行，每行一个整数表示一个客人点的果汁种类 $X_i$ 。

outputFormat: 输出在当前的请求序列下，小王最少需要清洗果汁机的次数。


title: 烤鸡

background: 猪猪 Hanke 得到了一只鸡。

description:
猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 $10$ 种配料（芥末、孜然等），每种配料可以放 $1$ 到 $3$ 克，任意烤鸡的美味程度为所有配料质量之和。

现在， Hanke 想要知道，如果给你一个美味程度 $n$ ，请输出这 $10$ 种配料的所有搭配方案。

inputFormat: 一个正整数 $n$，表示美味程度。

outputFormat:
第一行，方案总数。

第二行至结束，$10$ 个数，表示每种配料所放的质量，按字典序排列。

如果没有符合要求的方法，就只要在第一行输出一个 $0$。


title: 每日打卡心情好

background: 在洛谷中，打卡不只是一个简单的鼠标点击动作，通过每天在洛谷打卡，可以清晰地记录下自己在洛谷学习的足迹。通过每天打卡，来不断地暗示自己：我又在洛谷学习了一天，进而帮助自己培养恒心、耐心、细心。此外，通过打卡，还可以获取经验值奖励，经验值的多少在一定程度上反映了你在洛谷的资历和成就。通过打卡累积活跃值，渐渐升级，会让你感觉“离神犇越来越近了”。

description:
洛谷的打卡系统与其他网站的打卡系统一样，连续”打卡天数越多，每次打卡获得的奖励也就越多，同时连续天数加上一天。然而，于其他网站只要一天不打卡，连续天数就要清零。与其他网站不同的是，洛谷的打卡更具有人性化，如果多天不打卡，连续天数仅仅只是减少，当遗漏天数越少，减少的天数也就越少。规则是减少 $2^{n-1}$ 天，$n$ 为连续遗漏天数。连续天数在下一次打卡时清算，打卡连续天数不会小于 $0$。也就是说，如果每隔一天打卡，那么连续天数就不会变了。

当连续天数达到以下天数时，给予不同的活跃值奖励：

$1$ 天：奖励 $1$（千里之行，始于足下）

$3$ 天：奖励 $2$（坚持 $3$ 天了，加油！）

$7$ 天：奖励 $3$（曜日轮回）

$30$ 天：奖励 $4$（月圆月缺，习惯养成）

$120$ 天：奖励 $5$（坚持四个月了！）

$365$ 天：奖励 $6$（一年四季都坚持下来了！真不容易！）

小 a $N$ 天前在洛谷注册了一个账号，虽然当时立志每天都要打卡，但发现这不太容易做到。现在知道他 $N$ 天的的打卡记录，小 a 希望得知他通过打卡，在 $N$ 天能获得多少活跃值？

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

接下来 $N$ 行，每行一个整数 $1$ 或 $0$，代表当天是否打过卡。

outputFormat: 一个整数，表示获得的活跃值！

hint:
第 $1$ 天：$1$ // 开始打卡！获得 $1$ 点经验，共 $1$ 点，连续 $1$ 天。

第 $2$ 天：$1$ // 获得 $1$ 点经验，共 $2$ 点，连续 $2$ 天。

第 $3$ 天：$1$ // 获得 $2$ 点经验，共 $4$ 点，连续 $3$ 天。

第 $4$ 天：$1$ // 获得 $2$ 点经验，共 $6$ 点，连续 $4$ 天

第 $5$ 天：$1$ // 获得 $2$ 点经验，共 $8$ 点，连续 $5$ 天

第 $6$ 天：$0$ // 由于要去趟火星，没有网络不得已而断签

第 $7$ 天：$0$

第 $8$ 天：$0$

第 $9$ 天：$1$ // 我回来了，可惜连续天数变成 $5-4=1$ 天了 TQT…… 获得 $1$ 点经验，共 $9$ 点，连续 $2$ 天

第 $10$ 天：$0$ // 啊，事情太多给忘了

第 $11$ 天：$1$ // 连续天数变成 $2-1=1$ 天。获得 $1$ 点经验，共 $10$ 点，连续 $2$ 天。

第 $12$ 天：$1$ // 获得 $2$ 点经验，共 $12$ 点，连续 $3$ 天。

小 a：弄个自动打卡机，怎么样？

kkksc03：这不符合洛谷的规则的！

$1\leq N\leq 10^3$。


title: 万能的OIH搜索

background:
以下皆为真实的故事。

OIH（Oi in hand <http://www.oiinhand.info/> ）是洛谷的官方战略合作伙伴。

洛谷的题目搜索功能（请看看上面的搜索框）、在线 IDE 功能均使用 OIH 的服务。

OIH 的搜索功能很强大，其庞大的数据库拥有 $8000+$ 道中外主流 OJ 的题目。只需要只言片语（题目名称、描述、甚至是测试数据）就可以很快的搜出这道题的出处（“改编题”的杀手）。

以后，OIH 还将收录全网上的题解（数量是万级别的），只要通过题目名称，就可以搜到这个题目的题解。

OIH 的目标是制作出一个适合 OIers 的 app。虽然 OIH 不是 OJ，但是 OIH 的辅助功能能够给 OIers 带来很大的便利。如果您有任何的 idea，请 @soha（oih 的作者）。

description:
经过多次谈判，kkksc03 终于取得了 OIH 搜索的接口，现在向 OIH 服务器发送了一个查询请求，返回了一道题目。

查询关键词是一句话，由汉字（我们用它的拼音代替）、空格（每个汉字之间都有空格）、半角标点组成。返回的题目也是这样的。kkksc03 希望将题目中的某些词语加粗。所谓词语，就是连续两个或以上汉字。比如说 `tao tao`,`zhai ping guo` 都是词语，而 `hao`,`ni,hao` 不是词语。如果一个在题目中出现的词语也在关键词中出现的词语，那么加粗。加粗的方法是在词语前加上 `<b>`，在词语后面加上一个 `</b>`。至于标点符号么加不加粗无所谓。kkksc03 希望添加标记（`<b>` `</b>`对）的数量尽可能少，而且每个标记之间的的字符数最少。

inputFormat: 两行。第一行为一个字符串 $S_1$，关键词字符串。第二行 $S_2$，是 OIH 返回的题目字符串。

outputFormat: 一行，处理的结果。

samples:
Shang wang dou tmd bei ping ping an an he xie diao le.
Tian yao mie he xie, tui he xie bao ping an.  shang Wang sou suo jiu ping cha cha cha ,you       zhen       xiang!

hint:
每个汉字不超过 $7$ 个英文字符。

关键字不超过 $100$ 个汉字。

返回的题目不超过 $1000$ 个汉字。


title: 榨取kkksc03

description:
洛谷 2 的团队功能是其他任何 OJ 和工具难以达到的。借助洛谷强大的服务器资源，任何学校都可以在洛谷上零成本的搭建 OJ 并高效率的完成训练计划。

为什么说是搭建 OJ 呢？为什么高效呢？

![](https://cdn.luogu.com.cn/upload/pic/1236.png)

因为，你可以上传私有题目，团队外别人是无法看到的。我们还能帮你们评测！

你可以创建作业，给组员布置任务，查看组员的完成情况，还可以点评任意一份代码！

你可以创建比赛！既可以是 OI 赛制还可以是 ICPC 赛制！既可以是团队内部的私有比赛，也可以公开赛，甚至可以指定谁可以参加比赛。这样，搞“x 校联赛”最合适不过了。洛谷凭借这个功能，希望能够提供公开及私有比赛的另外一个平台。

![](https://cdn.luogu.com.cn/upload/pic/1237.png)

值得说明的是，本次比赛就是采用团队私有题目+邀请比赛的机制。

洛谷的运营组决定，如果一名 OIer 向他的教练推荐洛谷，并能够成功的使用（成功使用的定义是：该团队有 $20$ 个或以上的成员，上传 $10$ 道以上的私有题目，布置过一次作业并成功举办过一次公开比赛），那么他可以浪费掉 kkksc03 的一些时间的同时消耗掉 kkksc03 的一些金钱以满足自己的一个愿望。

kkksc03 的时间和金钱是有限的，所以他很难满足所有同学的愿望。所以他想知道在自己的能力范围内，最多可以完成多少同学的愿望？

inputFormat:
第一行三个整数 $n,M,T$，表示一共有 $n$（$1 \le n \le 100$）个愿望， kkksc03 的手上还剩 $M$（$0 \le M \le 200$）元，他的暑假有 $T$（$0 \le T \le 200$）分钟时间。

第 $2$~$n+1$ 行 $m_{i}$ , $t_{i}$ 表示第 $i$ 个愿望所需要的金钱和时间。

outputFormat: 一行，一个数，表示 kkksc03 最多可以实现愿望的个数。


title: 资料分发1

description: 有一些电脑，一部分电脑有双向数据线连接。如果一个电脑得到数据，它可以传送到的电脑都可以得到数据。现在，你有这个数据，问你至少将其输入几台电脑，才能使所有电脑得到数据。

inputFormat:
第一行两个数n，m。n是点数，m是边数。

接下来m行，每行2个整数p，q表示p到q有一条双向数据线。

outputFormat: 一个整数，表示至少输入的电脑数量。


title: [USACO16DEC] Team Building P

description:
Every year, Farmer John brings his $N$ cows to compete for "best in show" at the state fair. His arch-rival, Farmer Paul, brings his $M$ cows to compete as well ($1 \leq N \leq 1000, 1 \leq M \leq 1000$).

Each of the $N + M$ cows at the event receive an individual integer score. However, the final competition this year will be determined based on teams of $K$ cows ($1 \leq K \leq 10$), as follows: Farmer John and Farmer Paul both select teams of $K$ of their respective cows to compete. The cows on these two teams are then paired off: the highest-scoring cow on FJ's team is paired with the highest-scoring cow on FP's team, the second-highest-scoring cow on FJ's team is paired with the second-highest-scoring cow on FP's team, and so on. FJ wins if in each of these pairs, his cow has the higher score.

Please help FJ count the number of different ways he and FP can choose their teams such that FJ will win the contest. That is, each distinct pair (set of $K$ cows for FJ, set of $K$ cows for FP) where FJ wins should be counted. Print your answer modulo 1,000,000,009.

inputFormat:
The first line of input contains $N$, $M$, and $K$. The value of $K$ will be no larger than $N$ or $M$.

The next line contains the $N$ scores of FJ's cows.

The final line contains the $M$ scores of FP's cows.

outputFormat: Print the number of ways FJ and FP can pick teams such that FJ wins, modulo 1,000,000,009.

translation:
每年，Farmer John 都要带领他的 $N$ 头奶牛参加才艺比赛，他的对手 Farmer Paul，会带着 $M$ 头奶牛参加比赛。

所有 $N+M$ 头奶牛都会得到评委给出的一个分数。而比赛的最终结果将取决于 $K$ 头奶牛组成的队伍。更具体地来说，FJ 和 FP 各自从自己的奶牛中挑选 $K$ 头奶牛组队，FJ 队伍中分数最高的奶牛将和 FP 队伍中分数最高的奶牛进行比较，FJ 队伍中分数次高的奶牛将和 FP 队伍中分数次高的奶牛进行比较，以此类推。如果 FJ 队伍中的每头奶牛的分数都比相对应的对手的分数高的话，FJ 就获得了胜利。

现在请你求出，在所有的组队情况中，有多少种情况 FJ 能取得胜利，输出方案数对 $1\,000\,000\,009$ 取模的结果。

数据范围：$1\leq N,M \leq 1000$,$1 \leq K \leq 10$。


title: [ZJOI2007] 最大半连通子图

description:
一个有向图 $G=\left(V,E\right)$ 称为半连通的 (Semi-Connected)，如果满足：$\forall u,v\in V$，满足 $u\to v$ 或 $v\to u$，即对于图中任意两点 $u,v$，存在一条 $u$ 到 $v$ 的有向路径或者从 $v$ 到 $u$ 的有向路径。

若 $G'=\left(V',E'\right)$ 满足 $V'\subseteq V$，$E'$ 是 $E$ 中所有跟 $V'$ 有关的边，则称 $G'$ 是 $G$ 的一个导出子图。若 $G'$ 是 $G$ 的导出子图，且 $G'$ 半连通，则称 $G'$ 为 $G$ 的半连通子图。若 $G'$ 是 $G$ 所有半连通子图中包含节点数最多的，则称 $G'$ 是 $G$ 的最大半连通子图。

给定一个有向图 $G$，请求出 $G$ 的最大半连通子图拥有的节点数 $K$，以及不同的最大半连通子图的数目 $C$。由于 $C$ 可能比较大，仅要求输出 $C$ 对 $X$ 的余数。

inputFormat:
第一行包含两个整数 $N,M,X$。$N,M$分别表示图 $G$ 的点数与边数，$X$ 的意义如上文所述。

接下来 $M$ 行，每行两个正整数 $a,b$，表示一条有向边 $\left(a,b\right)$。图中的每个点将编号为 $1,2,3\dots N$，保证输入中同一个$\left(a,b\right)$不会出现两次。

outputFormat: 应包含两行，第一行包含一个整数 $K$，第二行包含整数 $C\bmod X$。


title: [NOIP2016 普及组] 魔法阵

background: NOIP2016 普及组 T4

description:
六十年一次的魔法战争就要开始了，大魔法师准备从附近的魔法场中汲取魔法能量。

大魔法师有 $m$ 个魔法物品，编号分别为 $1,2,\ldots,m$。每个物品具有一个魔法值，我们用 $X_i$ 表示编号为 $i$ 的物品的魔法值。每个魔法值 $X_i$ 是不超过 $n$ 的正整数，可能有多个物品的魔法值相同。

大魔法师认为，当且仅当四个编号为 $a,b,c,d$ 的魔法物品满足 $X_a<X_b<X_c<X_d,X_b-X_a=2(X_d-X_c)$，并且 $X_b-X_a<(X_c-X_b)/3$ 时，这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这个魔法阵的 $A$ 物品，$B$ 物品，$C$ 物品，$D$ 物品。

现在，大魔法师想要知道，对于每个魔法物品，作为某个魔法阵的 $A$ 物品出现的次数，作为 $B$ 物品的次数，作为 $C$ 物品的次数，和作为 $D$ 物品的次数。

inputFormat:
第一行包含两个空格隔开的正整数 $n,m$。

接下来 $m$ 行，每行一个正整数，第 $i+1$ 行的正整数表示 $X_i$，即编号为 $i$ 的物品的魔法值。

保证 $1 \le n \le 15000$，$1 \le m \le 40000$，$1 \le X_i \le n$。每个 $X_i$ 是分别在合法范围内等概率随机生成的。

outputFormat:
共 $m$ 行，每行 $4$ 个整数。第 $i$ 行的 $4$ 个整数依次表示编号为 $i$ 的物品作 为 $A,B,C,D$ 物品分别出现的次数。

保证标准输出中的每个数都不会超过 $10^9$。每行相邻的两个数之间用恰好一个空格隔开。

hint:
【样例解释 $1$】

共有 $5$ 个魔法阵，分别为：

- 物品 $1,3,7,6$，其魔法值分别为 $1,7,26,29$；
- 物品 $1,5,2,7$，其魔法值分别为 $1,5,24,26$；
- 物品 $1,5,7,4$，其魔法值分别为 $1,5,26,28$；
- 物品 $1,5,8,7$，其魔法值分别为 $1,5,24,26$；
- 物品 $5,3,4,6$，其魔法值分别为 $5,7,28,29$。

以物品 $5$ 为例，它作为 $A$ 物品出现了 $1$ 次，作为 $B$ 物品出现了 $3$ 次，没有作为 $C$ 物品或者 $D$ 物品出现，所以这一行输出的四个数依次为 $1,3,0,0$。

此外，如果我们将输出看作一个 $m$ 行 $4$ 列的矩阵，那么每一列上的 $m$ 个数之和都应等于魔法阵的总数。所以，如果你的输出不满足这个性质，那么这个输出一定不正确。你可以通过这个性质在一定程度上检查你的输出的正确性。

【数据规模】

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


title: MICE

description:
S 国的动物园是一个 $N \times M$ 的网格图，左上角的坐标是 $(1,1)$，右下角的坐标是 $(N,M)$。

小象在动物园的左上角，它想回到右下角的家里去睡觉，但是动物园中有一些老鼠，而小象又很害怕老鼠。动物园里的老鼠是彼此互不相同的。小象的害怕值定义为他回家的路径上可以看见的不同的老鼠的数量。若小象当前的位置为 $(x_1,y_1)$，小象可以看见老鼠，当且仅当老鼠的位置 $(x_2,y_2)$ 满足 $|x_1-x_2| + |y_1-y_2| \leq 1$。由于小象很困了，所以小象只会走一条最近的路回家，即小象只会向下或者向右走。现在你需要帮小象确定一条回家的路线，使得小象的害怕值最小。

inputFormat:
第一行包含两个用空格隔开的整数，$N$ 和 $M$。

接下来一个 $N \times M$ 的矩阵表示动物园的地图。其中 $A_{i,j}$ 表示第 $i$ 行第 $j$ 列上老鼠的数量。若 $A_{i,j} = 0$ 则表示当前位置上没有老鼠(小象的家里也可能存在老鼠)。

outputFormat: 输出一个整数，表示路线最小的害怕值是多少。


title: YY的GCD

description:
神犇 YY 虐完数论后给傻× kAc 出了一题

给定 $N, M$，求 $1 \leq x \leq N$，$1 \leq y \leq M$ 且 $\gcd(x, y)$ 为质数的 $(x, y)$ 有多少对。

inputFormat:
第一行一个整数 $T$ 表述数据组数。

接下来 $T$ 行，每行两个正整数，$N, M$。

outputFormat: $T$ 行，每行一个整数表示第 $i$ 组数据的结果。


title: [NOIP2014 提高组] 寻找道路

background: NOIP2014 提高组 D2T2

description:
在有向图 $G$ 中，每条边的长度均为 $1$，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：

1. 路径上的所有点的出边所指向的点都直接或间接与终点连通。
2. 在满足条件 $1$ 的情况下使路径最短。

注意：图 $G$ 中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度。

inputFormat:
第一行有两个用一个空格隔开的整数 $n$ 和 $m$，表示图有 $n$ 个点和 $m$ 条边。

接下来的 $m$ 行每行 $2$ 个整数 $x,y$，之间用一个空格隔开，表示有一条边从点 $x$ 指向点 $y$。

最后一行有两个用一个空格隔开的整数 $s,t$，表示起点为 $s$，终点为 $t$。

outputFormat: 输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出 $-1$。

hint:
**样例 1 解释**

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

如上图所示，箭头表示有向道路，圆点表示城市。起点 $1$ 与终点 $3$ 不连通，所以满足题目描述的路径不存在，故输出 $-1$。

**样例 2 解释**

![](https://cdn.luogu.com.cn/upload/image_hosting/tm2e1lqq.png)
如上图所示，满足条件的路径为 $1\to 3\to 4\to 5$。注意点 $2$ 不能在答案路径中，因为点 $2$ 连了一条边到点 $6$，而点 $6$ 不与终点 $5$ 连通。

**数据范围及约定**

- 对于 $30\%$ 的数据，$0<n\le10$，$0<m\le 20$。
- 对于 $60\%$ 的数据，$0<n\le100$，$0<m\le 2000$。
- 对于 $100\%$ 的数据，$0<n\le 10^4$，$0<m\le 2\times 10^5$，$0<x,y,s,t\le n,x,s\ne t$。


title: [AHOI2009] 飞行棋

description: 给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。

inputFormat: 第一行为正整数 $N$，表示点的个数，接下来 $N$ 行分别为这 $N$ 个点所分割的各个圆弧长度。

outputFormat: 所构成不重复矩形的个数。

hint:
$N \le 20$。

![](https://cdn.luogu.com.cn/upload/pic/13233.png)


title: [国家集训队] 部落战争

background: lanzerb 的部落在 A 国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。

description:
A 国是一个 $M\times N$ 的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb 把自己的部落分成若干支军队，他们约定：

每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。途中只能经过城镇，不能经过高山深涧。

如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。
每支军队都可以在任意一个城镇停止征战。

所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走 $1\times2$ 的路线，而他们只能走 $R\times C$ 的路线。

lanzerb 的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮 lanzerb 算算至少要多少支军队才能完成统一全国的大业。

inputFormat: 第一行包含 $4$ 个整数 $M,N,R,C$，意义见问题描述。接下来 $M$ 行每行一个长度为 $N$ 的字符串。如果某个字符是 `.` 表示这个地方是城镇；如果这个字符是 `x` 则表示这个地方是高山深涧。

outputFormat: 输出一个整数，表示最少的军队个数。

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

对于 $100\%$ 的数据，$1\le M,N\le 50,1\le R,C\le 10$。


title: 【模板】Nim 游戏

description:
甲，乙两个人玩 nim 取石子游戏。

nim 游戏的规则是这样的：地上有 $n$ 堆石子（每堆石子数量小于 $10^4$），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 $n$ 堆石子的数量，他想知道是否存在先手必胜的策略。

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

第一行一个整数 $T$ （$T\le10$），表示有 $T$ 组数据

接下来每两行是一组数据，第一行一个整数 $n$，表示有 $n$ 堆石子，$n\le10^4$。

第二行有 $n$ 个数，表示每一堆石子的数量.

outputFormat: 共 $T$ 行，每行表示如果对于这组数据存在先手必胜策略则输出 `Yes`，否则输出 `No`。


title: 数字对

description:
对于一个数字对(a, b)，我们可以通过一次操作将其变为新数字对(a+b, b)或(a, a+b)。

给定一正整数n，问最少需要多少次操作可将数字对(1, 1)变为一个数字对，该数字对至少有一个数字为n。

inputFormat: 第一行一个正整数 n

outputFormat: 一个整数表示答案。


title: 排序

description:
小 A 有 $n$ 个物件排成一排，每个物件有它的体积 $V$ 和质量 $M$。$n$ 个物件的体积在 $1 \sim n$ 内，且各不相同，但质量可能相同。

现在，小 A 需要把 $n$ 个物件按体积从小到大重新排列。他的排序方式是：每次交换两个物件。这样会他会消耗的体力值为两个物件的质量和。

小 A 想知道，为了将物件排序，他消耗的最少体力值是多少？

inputFormat:
第一行，一个正整数 $n$，表示物件的数量。

第二行 $n$ 个正整数，第 $i$ 个数表示从左到右第 $i$ 个物品的体积。

第三行 $n$ 个正整数，第 $i$ 个数表示从左到右第 $i$ 个物品的质量。

outputFormat: 一个数，表示小 A 消耗的最小体力值。


title: 数字游戏

description: KC 邀请他的两个小弟 K 和 C 玩起了数字游戏。游戏是 K 和 C 轮流操作进行的，K 为先手。KC 会先给定一个数字 $Q$，每次操作玩家必须写出当前数字的一个因数来代替当前数字，但是这个因数不能是 $1$ 和它本身。例如当前数字为 $6$，那么可以用 $2, 3$ 来代替，但是 $1$ 和 $6$ 就不行。现在规定第一个没有数字可以写出的玩家为胜者。K 在已知 $Q$ 的情况，想知道自己作为先手能不能胜利，若能胜利，那么第一次写出的可以制胜的最小数字是多少呢？整个游戏过程我们认为 K 和C用的都是最优策略。

inputFormat: 仅一行，一个正整数 $Q$。

outputFormat:
第一行是 $1$ 或 $2$，$1$ 表示 K 能胜利，$2$ 表示 C 能胜利。

若 K 能胜利，则在第二行输出第一次写出的可以制胜的最小数字。

若是第一次就无法写出数字，则认为第一次写出的可以制胜的最小数字为 $0$。


title: [国家集训队] JZPFAR

background: 原《零件分组》见 P1233。

description: 平面上有 $n$ 个点。现在有 $m$ 次询问，每次给定一个点 $(px, py)$ 和一个整数 $k$，输出 $n$ 个点中离 $(px, py)$ 的距离第 $k$ 大的点的标号。如果有两个(或多个)点距离 $(px, py)$ 相同，那么认为标号较小的点距离较大。

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

下面 $n$ 行，每行两个整数 $x_i,y_i$，表示 $n$ 个点的坐标。点的标号按照输入顺序，分别为 $1\ldots n$。

下面一行，一个整数 $m$，表示询问个数。

下面 $m$ 行，每行三个整数 $px_i,py_i,k_i$，表示一个询问。

outputFormat: $m$ 行，每行一个整数，表示相应的询问的答案。

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

- $50\%$ 的数据中，$n$ 个点的坐标在某范围内随机分布。
- $100\%$ 的数据中，$1\le n\le 10^5$，$1\le m\le 10^4$，$1\le k\le 20$，$-10^9\le x_i,y_i,px_i,py_i\le 10^9$，$n$ 个点中任意两点坐标不同，$m$ 个询问的点的坐标在某范围内随机分布。


title: 运输

description: 现在已知 $N$ 件商品，和搬运它们其中每一件的费用。现在搬家公司老板 Mr.sb 决定让我们每次任意选取 $2$ 件商品。然后这 $2$ 件商品只算一件商品的费用。但是这个商品的搬运费用是将选出的 $2$ 个商品的费用之和除以 $k$ 的运算结果。如此反复。直到只收一件商品的钱。这个就是商店要付的费用。掌柜的想尽可能的少付钱，以便将更多的钱捐给希望工程。所以请你帮他计算一下最少只用付多少钱。

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

第二行 $n$ 个整数 $w_1,w_2,\ldots,w_n$，表示每一件物品搬运费。

outputFormat: 一行一个整数表示最少付多少钱。

hint:
$n,k,w_i$ 均为非负数。

$n,k\le 10^4$。

---

$\text{upd 2022.7.24}$：新增加一组 Hack 数据。题目是否存在该数据范围下的正确解法有争议。


title: 营养膳食

description:
Mr.L 正在完成自己的增肥计划。

为了增肥，Mr.L 希望吃到更多的脂肪。然而也不能只吃高脂肪食品，那样的话就会导致缺少其他营养。

Mr.L 通过研究发现：真正的营养膳食规定某类食品不宜一次性吃超过若干份。比如就一顿饭来说，肉类不宜吃超过 $1$ 份，鱼类不宜吃超过 $1$ 份，蛋类不宜吃超过 $1$ 份，蔬菜类不宜吃超过 $2$ 份。

Mr.L 想要在营养膳食的情况下吃到更多的脂肪，当然 Mr.L 的食量也是有限的。

inputFormat:
第一行包含三个正整数 $n,m$ 和 $k$。表示 Mr.L 每顿饭最多可以吃 $m$ 份食品，同时有 $n$ 种食品供 Mr.L 选择，而这 $n$ 种食品分为 $k$ 类。

第二行包含 $k$ 个不超过 $10$ 的正整数，表示可以吃 $1$ 到 $k$ 类食品的最大份数。

接下来 $n$ 行每行包括 $2$ 个正整数，分别表示该食品的脂肪指数 $a_i$ 和所属的类别 $b_i$。

outputFormat: 包括一个数字即 Mr.L 可以吃到的最大脂肪指数和。

hint: 对于 $100\%$ 的数据，$1\leq n\leq 200$，$1\leq m\leq 100$，$1\leq k\leq 100$，$1\leq a_i\leq 100$，$1\leq b_i\leq k$。


title: 最佳旅游线路

description:
某旅游区的街道成网格状。其中东西向的街道都是旅游街，南北向的街道都是林阴道。由于游客众多，旅游街被规定为单行道，游客在旅游街上只能从西向东走，在林阴道上则既可从南向北走，也可以从北向南走。

阿龙想到这个旅游街游玩，他的好友阿福给了他一些建议，用分值表示所有旅游街相邻两个路口之见的街道值得游览的程度，分值是从-100到100的整数，所有林阴道不打分。所有分值不可能全是负分。如图：

 ![](https://cdn.luogu.com.cn/upload/pic/1235.png)

inputFormat: 输入文件的第一行是两个整数m和n,之间用一个空格隔开，m表示有m条旅游街（1≤m≤100 ），n 表示有(n+1)条林阴道（1≤n≤20001 ）。接下来的m行依次给出了由北向南每条旅游街的分值信息。每行有n个整数，依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。

outputFormat: 输出文件只有一行，是一个整数，表示你的程序找到的最佳游览线路的总分值。


title: [USACO17FEB] Why Did the Cow Cross the Road I P

description:
Why did the cow cross the road? We may never know the full reason, but it is certain that Farmer John's cows do end up crossing the road quite frequently. In fact, they end up crossing the road so often that they often bump into each-other when their paths cross, a situation Farmer John would like to remedy.

Farmer John raises $N$ breeds of cows ($1 \leq N \leq 100,000$), and each of his fields is dedicated to grazing for one specific breed; for example, a field dedicated to breed 12 can only be used for cows of breed 12 and not of any other breed. A long road runs through his farm. There is a sequence of $N$ fields on one side of the road (one for each breed), and a sequence of $N$ fields on the other side of the road (also one for each breed). When a cow crosses the road, she therefore crosses between the two fields designated for her specific breed.

Had Farmer John planned more carefully, he would have ordered the fields by breed the same way on both sides of the road, so the two fields for each breed would be directly across the road from each-other. This would have allowed cows to cross the road without any cows from different breeds bumping into one-another. Alas, the orderings on both sides of the road might be different, so Farmer John observes that there might be pairs of breeds that cross. A pair of different breeds $(a,b)$ is "crossing" if any path across the road for breed $a$ must intersect any path across the road for breed $b$.

Farmer John would like to minimize the number of crossing pairs of breeds. For logistical reasons, he figures he can move cows around on one side of the road so the fields on that side undergo a "cyclic shift". That is, for some $0 \leq k < N$, every cow re-locates to the field $k$ fields ahead of it, with the cows in the last $k$ fields moving so they now populate the first $k$ fields. For example, if the fields on one side of the road start out ordered by breed as 3, 7, 1, 2, 5, 4, 6 and undergo a cyclic shift by $k=2$, the new order will be 4, 6, 3, 7, 1, 2, 5. Please determine the minimum possible number of crossing pairs of breeds that can exist after an appropriate cyclic shift of the fields on one side of the road.

inputFormat: The first line of input contains $N$. The next $N$ lines describe the order, by breed ID, of fields on one side of the road; each breed ID is an integer in the range $1 \ldots N$. The last $N$ lines describe the order, by breed ID, of the fields on the other side of the road.

outputFormat: Please output the minimum number of crossing pairs of breeds after a cyclic shift of the fields on one side of the road (either side can be shifted).

translation:
# 题目描述

为什么牛要过马路？我们可能永远都不知道全部原因，但肯定的是，农民约翰的牛经常穿过马路。事实上，他们经常过马路，当他们的路径交叉时，他们经常碰到对方，这是约翰希望改进的情况。

农夫约翰将奶牛分成了$N$个不同的品种（$1\le N\le 100000$），他的每一个田地都是专门为一种特定的品种放牧; 例如，专门用于品种$12$奶牛的田地只能用于品种$12$的奶牛，而不能用于任何其他品种的奶牛。一条长长的路穿过他的农场。道路一侧有$N$个田地（每个品种一个），道路另一侧也有$N$个田地（每个品种也有一个）。所以，当一头牛穿过马路，它会穿过特定品种的两个田地。

如果农民约翰更仔细的研究他的计划，他会在道路两旁订购同品种田地，所以每个品种的两个田野将直接穿过彼此的道路。这样就可以让奶牛随意过马路，而不会有不同品种的牛碰撞在一起。唉，但现在道路两边的田地可能不一样，所以农民约翰明白，可能会有一对品种$(a,b)$是交叉的当且仅当是一对不同的品种，且道路上一边田地品种a上的任何路线都与道路另一边田地品种b的任何路线相交 。

农民约翰希望尽量减少品种的交叉对数。由于物流方面的原因，他表示，他可以在道路的一边移动牛，所以那边的田地可以“循环转移”。也就是说，对于一个给定的常值k来说，循环转移是指每头牧场里的牛都会向前移动k个田野，而最前面的k只奶牛会移动到最后，因为向前移动的奶牛已经填补了前k个田地。比如，如果道路一侧的田地移动前的排列为3,7,1,2,5,4,6，假设k为2，新排列将为4,6,3,7 ,1,2,5.请编程确定在道路一侧的田野适当循环移动后存在的品种交叉对的最小值。

# 输入格式

一行包含$N$ ($1 \leq N \leq 100,000$),接下来$N$行按顺序描述了小路一旁田地的品种的ID号，每一个ID号是一个在$1...N$之间的整数。倒数$N$行描述了小路另一旁田地的品种的ID号。

# 输出格式

循环移动道路侧的田野后，请输出可能的品种交叉对的最小数量（两边均可移动）

感谢@Adscn提供翻译@mydiplomacy修正


title: 凌乱的地下室

description:
小Z家的地下室里并排放n个小方块（小Z是一位MC狂热爱好者，喜欢用小方块装饰他家的地下室），并且每个方块都不一样（小Z喜欢各不相同的东西），比如有草方块、大理石、黑曜石等。

小Z喜欢以一种特殊的顺序摆放这些小方块，比如：草方块、大理石、黑曜石。一天，小D帮助小Z整理地下室，可是智商捉急的小D将所有小方块搬出来后忘记了它们原来的具体位置，凭着模糊的印象，他可能把原来放在第i个位置上的小方块放到第（i-1）、i、（i+1）个位置中的任意一个上（当然，第1个不可能放到第0个位置上，第n个不可能放到第（n+1）个位置上），比如（对应上面那个例子）：大理石、草方块、黑曜石。

小Z是一个心胸宽广的人，他希望计算一下小D一共会有几种可能的摆放结果，并不追究小D的责任（追究了只会更乱……）。由于他自己的智商也比较捉急，所以如果答案很大的话他只想看到最后的8位（前导零就不要给他看了）。

inputFormat: 一行，一个正整数n，代表小Z家的地下室一共有n个小方块。

outputFormat: 一行，一个正整数，表示小D一共有几种可能的摆放结果，只输出后8位，前导零不输出。

hint:
【样例解释1】

接着题目中的例子，一共有3种：（草方块，大理石，黑曜石）、（大理石，草方块，黑曜石）、（草方块，黑曜石，大理石）。

【样例解释2】

一共有……00223731种摆放结果，由于前导零不输出，因此输出223731。

【数据规模】

一共有50个测试点。

其中第1~15个：1<n<=10^6

其中第16~25个：10^6<n<=10^16

其中第26~50个：10^16<n<=10^1000

【时空限制】

0.2s/64MB


title: 小Z的矩阵

description:
小 Z 最近迷上了矩阵，他定义了一个对于一种特殊矩阵的特征函数 $G$。对于 $N\times N$ 的矩阵 $A$，$A$ 的所有元素均为 $0$ 或 $1$，则 $\displaystyle G(A) = \left(\sum_{i = 1}^n\sum_{j = 1}^n A_{i, j}\cdot A_{j, i}\right) \bmod 2$。举一个例子：

$$
\begin{pmatrix}
1 & 1 & 1\\
0 & 1 & 1\\
1 & 0 & 0\\
\end{pmatrix}
$$

对于上面这个 $3\times 3$ 矩阵 $A$，$G(A)=(1\times 1+1\times 0+1\times 1+0\times 1+1\times 1+1\times 0+1\times 1+ 0\times 1+0\times 0) \bmod 2 = 0$。

当然询问一个矩阵的 $G$ 值实在是太简单了。小Z在给出一个 $N\times N$ 矩阵的同时将给你 $Q$ 个操作，操作描述如下：

- 操作 1：形如 `1 x`，表示将第 $x$ 行的元素全部“翻转”。
- 操作 2：形如 `2 x`，表示将第 $x$ 列的元素全部“翻转”。
- 操作 3：形如一个整数`3`，表示询问当前矩阵的特征值 $G$。

“翻转”的定义为将 $1$ 变成 $0$，将 $0$ 变成 $1$。

inputFormat:
第一行：两个正整数 $N,Q$。$N$ 表示矩阵的行数（列数），$Q$ 表示询问的次数。

接下来 $N$ 行：一个 $N\times N$ 的矩阵 $A$，$0\le A_{i, j}\le 1$。

接下来 $Q$ 行：$Q$ 个操作。

outputFormat: 一行若干个数，中间没有空格，分别表示每个操作的结果（操作 1 和操作 2 不需要输出）。


title: 命运石之门的选择

description:
在某一条不知名世界线的冈伦今天突然接到了一条dmail，上面说世界线将会发生巨大变动，未来的他无论如何都无法扭转这种变动回到原来的世界线。而世界线变动的原因是现在的他不久后错过了与助手的约会。他约好要和助手去约会，但是在去约会之前，由于一直拖欠房租，房东大叔要求他帮忙完成一幅画的上色，然而他没有以最快的速度完成这个任务，导致他错过了与助手的约会，从而导致世界线的剧变。现在到了拯救世界的时候，由于冈伦并不擅长画画，于是他找到了同样不擅长画画的你来帮他解决这个问题（这是命运石之门的选择）。不管怎样现在拯救世界的重任交到了你的手上，而你虽然不擅长画画，但是你可以使用编程来帮助你解决这个问题。

一幅画由 $N$ 个宽度为 $1$ 高度为 $H_i$ 的矩形组成，矩形并排排列，相邻的矩形间没有空隙，初始情况下每个矩形都是没有颜色的。你有一个宽度为 $1$ 的刷子，可以竖直或水平的刷，每次使用刷子，刷子都必须保证一直全部处于矩形中，即不能刷到矩形以外的地方去，当然每次刷的时候也不能拐弯。每刷一次，要花费 $1$ 的时间，这和刷的长度无关，比如你可以从最左边刷到最右边（当然是不经过矩形以外的部分），这也只花费 $1$ 的时间。你的目的是将全部的矩形都涂满颜色。请你计算并输出这个最短的时间。

inputFormat:
第 $1$ 行：一个正整数 $N$，表示矩形的个数。

接下来 $N$ 个正整数 $H_i$，表示第 $i$ 个矩形的高度。

outputFormat: 一个整数，表示最少花费的时间。


title: 地砖铺设

description:
在游戏厅大赚了一笔的小 Z 终于赢到了他想要的家具。乘此机会，他想把自己的房间好好整理一下。

在百货公司，可以买到各种各样正方形的地砖，为了美观起见，小 Z 不希望同样颜色的正方形地砖相邻。所以他找到了小 C 来帮忙解决这件事情。

小 C 很快解决了这个任务。然而，出于某种强迫症，她希望在地上按照长宽划分成网格后，逐行逐列每一块的颜色组成的序列的字典序最小。她希望你帮忙验证一下她的方案。

inputFormat: 第一行，包含两个整数 $N$ 和 $M$，表示房间的长和宽。

outputFormat: $N$ 行，每行 $M$ 列，表示地砖铺设的方案，需要这个方案是字典序最小的合法方案。（可以认为，输出的方案去掉回车后形成的字符串字典序最小）

hint:
对于 $50\%$ 的数据，保证 $N,M \leq 5$。

对于 $100\%$ 的数据，保证 $1 \leq N,M \leq 100$。


title: 道路值守

description:
Z-Kingdom 有着四通八达的现代化交通。时值独立庆典之际，随着来自周边国家旅客的日益增多，犯罪行为也悄无声息开始滋长起来。

特别任务支援科的警察们从总部收到了关于调查伪装在游客中的犯罪分子的请求。通过调查，他们得到了一张地图，记载了 Z-Kingdom 内每一条道路的长度。

显然，为了减少犯罪行为被发现的可能性，犯罪分子总是会选择最短的路径来行动。为了方便安排人手和推测犯罪分子采取的路线，他们希望得知任意两个地点之间，有多少条犯罪分子可能会选择的道路。

inputFormat:
第一行，包含两个整数 $N,M$，表示 Z-Kingdom 内的地点数和道路数。

接下来 $N$ 行，每行包含三个整数 $x,y,z$，表示道路连接的两个不同地点的标号，以及道路的长度。道路是双向的。

两个不同地点之间不会有超过一条道路。

outputFormat:
输出一行，包含 $\dfrac{N(N-1)}{2}$ 个整数  $C_{1,2},C_{1,3},\cdots,C_{1,N},C_{2,3},C_{2,4},\cdots,C_{2,N},\cdots,C_{N-1,N}$。

其中 $C_{x, y}$ 表示 x 号地点到 y 号地点之间有多少条犯罪分子可能会选择的道路。

hint:
【数据规模】

- 对于 $30\%$ 的数据，保证 $N \le 50$；
- 对于 $60\%$ 的数据，保证 $N \le 100$；
- 对于 $100\%$ 的数据，保证 $N \le 500$。


title: 开心派对小火车

description:
Aqours铁路公司旗下有N个站，编号1,2,..,N。

有各停（各站停车）电车特急电车两种。特急车会在$S_1,S_2,...,S_M (1=S_1<S_2 <...<S_M=N)$，一共M个车站停车。

相邻的两站(即编号为i的车站和编号为$i+1$的车站，而不是特急电车停车的相邻的两站)之间，各停电车要运行A分钟，特急需要B分钟。我们认为列车一直匀速运行，不考虑停车和加减速。

现在要加一种快速电车，要求其停站覆盖所有的特急电车的停站，而相邻的两站要运行C分钟。为了要快，决定刚好停K个站（$K>M$，包括特急的所有车站）。如果一个站可以停多种电车，那么旅客可以在这一站换乘。不过只能向前坐车，不能往回坐。

你需要设计一种快速列车的设站方案，要求旅客在T分钟**乘车时间（等车和换乘时间不计）**内，可以从1号站到尽可能多数量的站。你只需要告知能有几站可以达到。

inputFormat:
第一行3个整数，N，M，K，其意义已经在描述中给出。

第二行3个整数，A，B，C，其意义也已经在描述中给出。

第三行1个整数T，表示乘车时间。

接下来M行，每行一个整数。其中第i个整数为$S_i$

outputFormat: 一个整数，表示限定时间内能够达到的最多站的数量。

hint:
【样例解释】

可以设快速列车站为1/5/6/8/10。

2,3,4可以直接乘坐各停慢车，5可以乘坐快速列车，6,10可以乘坐特急列车，7可以到6转慢车，8可以到6传快速列车。9没办法在30分钟的乘车时间内到达

【数据范围】

对于20%的数据，$N \le 300, K-M=2, A \le 10^6 , T \le 10^9$

对于50%的数据，$N \le 1000$

对于100%的数据，$2 \le N \le 10^9, 2 \le M \le K \le 3000, 1 \le B < C < A \le 10^9, i \le T \le 10^{18}$


title: First Step (ファーストステップ)

background:
> **知らないことばかりなにもかもが（どうしたらいいの？）**
**一切的一切 尽是充满了未知数（该如何是好）**
**それでも期待で足が軽いよ（ジャンプだ！）**
**但我仍因满怀期待而步伐轻盈（起跳吧！）**
**温度差なんていつか消しちゃえってね**
**冷若冰霜的态度 有朝一日将会消失得无影无踪**
**元気だよ元気をだしていくよ**
**拿出活力 打起精神向前迈进吧**

 ![](https://cdn.luogu.com.cn/upload/pic/4471.png)

我们 Aqours，要第一次举办演唱会啦！

虽然学生会长看上去不怎么支持我们的样子，可是有了理事长的支持，我们还是被允许在校内的篮球场里歌唱！

歌曲也好好地准备过了，名字叫“[最喜欢的话就没问题！ (ダイスキだったらダイジョウブ！)](https://zh.moegirl.org/%E6%9C%80%E5%96%9C%E6%AC%A2%E7%9A%84%E8%AF%9D%E5%B0%B1%E6%B2%A1%E9%97%AE%E9%A2%98)“，大家一定会喜欢的吧！

演唱会一定会顺利进行的！

希望不要发生**停电**什么的事故哦……！

description:
可是……这个篮球场，好像很久没有使用过的样子啊……

里面堆满了学校的各种杂物呢……

我们 Aqours 的成员要怎么在里面列队站下呢？

我们浦之星女子学院的篮球场是一个 $R$ 行 $C$ 列的矩阵，其中堆满了各种学校的杂物 (用 `#` 表示)，空地 (用 `.` 表示) 好像并不多的样子呢……

我们 Aqours 现在已经一共有 $K$ 个队员了，要歌唱舞蹈起来的话，我们得排成一条 $1\times K$ 的直线，一个接一个地站在篮球场的空地上呢 (横竖均可)。

我们想知道一共有多少种可行的站位方式呢。

Aqours 的真正的粉丝的你，能帮我们算算吗？

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

接下来的 $R$ 行 $C$ 列，表示浦之星女子学院篮球场。

outputFormat: 总共的站位方式数量。


title: 不成熟的梦想家 (未熟 DREAMER)

background:
**どんな未来かは 誰もまだ知らない**

**那是个任谁也不会知晓的未来**

**でも楽しくなるはずだよ**

**但应该会充满乐趣吧**

**みんなとなら乗りこえられる**

**只要大伙儿同在 就能跨越难关**

**これからなんだねお互いがんばろうよ**

**现在才正要开始 彼此互相加油吧**

**どんな未来かは 誰もまだ知らない**

**那是个任谁也不会知晓的未来**

**でも楽しくしたホントに**

**不过真心期望能够充满着乐趣**

**みんなとなら無理したくなる**

**只要大伙儿同在 就会想将顾虑抛诸脑后**

**成長したいなまだまだ未熟DREAMER**

**愿能有所成长 如今还只是尚未成熟的梦想家**

 ![](https://cdn.luogu.com.cn/upload/pic/4493.png)

Aqours的成员终于到齐了。

今天，是我们全员在一起的第一场演唱会。

大家都好好练习过了，相信一定会表现得很出色的。

不过，每个人的唱功也要尽量地接近才可以呢，如果太突出或者太落后，也是会影响表现的样子。

所以我们从隔壁的学园都市借来了一个发明，可以改变我们成员的唱功呢。

description:
我们Aqours的成员共有N+1人，他们会列成一队。

他们的唱功以A[0]到A[N]表示，A[i]$(0\le i \le N)$均给出。

学园都市的机器可以改变队列中连续多个成员的唱功值，并将其加上一个数Z，当然当Z是负数的时候就变成减去了。

我打算一共使用这个机器Q次，每次把第X到第Y号（$1\le X,Y\le10^6$）的成员都加上Z点唱功值。

而我们队伍的魅力值B，是这么算的：

一开始B=0，然后从第1号到第N号成员，

- 当$A_{i-1}<A_i$：$B = B-S\cdot|A_{i-1} - A_i|$
- 当$A_{i-1}>A_i$：$B = B+T\cdot|A_{i-1} - A_i|$
其中S和T是LoveLive组委会给我们的常数。

果然，我是バカチカ（笨蛋千歌）呢，所以作为领导我永远排在队伍的开头，唱功永远是0，机器也不会改到我头上呢。

你能帮我们算算，我**每次**使用完这个机器之后，成员的魅力B是多少吗？

inputFormat:
第一行4个整数，N，Q，S，T，各个变量在描述中已经解释

接下来N+1行，每行一个数整数Ai，其中A0=0

接下来Q行，每行3个整数，X，Y，Z各个变量在描述中已经解释

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

hint:
30% 的数据 $N,Q\le 2000$,

另外20% 的数据 $S=T$

100%的数据 $N,Q\le 200000$；$1\le S,T,A_i\le10^6$；$|Z|\le 10^6$
请注意可能需要使用int64，cin/cout可能超时。

样例解释：

第一次变化后，

A 0 6 3 4 6

B -12 -3 -5 -9

#### 以下是彩蛋

没有。

哪来的那么多彩蛋？


title: [USACO17FEB] Why Did the Cow Cross the Road II P

background: *本题与 [金组同名题目](/problem/P6119) 在题意上一致，唯一的差别是数据范围。*

description:
Farmer John 饲养了 $N$ 种奶牛，编号从 $1$ 到 $N$。一些品种的奶牛和其他奶牛间相处良好，事实证明，如果两个品种的奶牛编号分别为 $a,b$，当 $|a-b| \leq 4$ 时，这两个品种的奶牛能友好相处，否则不能友好相处。

一条长长的道路贯穿整个农场，道路的左侧有 $N$ 个牧场（每个品种的奶牛恰好占据一个牧场），道路的右侧也有 $N$ 个牧场（每个品种的奶牛恰好占据一个牧场）。为了让奶牛们安全穿过马路，Farmer John 希望能在马路上画出一些人行道（牛行道？），要求这些人行道满足如下条件：

1. 人行道从左侧的某个牧场出发，连接到右侧的某个牧场；
2. 人行道连接的两个牧场的奶牛要能友好相处；
3. 人行道不能在道路中间相交；
4. 每个牧场只能与一条人行道相连。

你需要帮 FJ 求出最多能有多少条人行道。

inputFormat:
输入第一行一个整数 $N$（$1 \leq N \leq 10^5$）。

接下来 $N$ 行，每行一个整数 $a_i$，代表道路左侧第 $i$ 个牧场的奶牛品种编号。

接下来 $N$ 行，每行一个整数 $b_i$，代表道路右侧第 $i$ 个牧场的奶牛品种编号。

outputFormat: 输出最多能画多少条人行道。


title: [USACO17FEB] Why Did the Cow Cross the Road III P

description:
Farmer John is continuing to ponder the issue of cows crossing the road through his farm, introduced in the preceding two problems. He realizes now that the threshold for friendliness is a bit more subtle than he previously considered -- breeds $a$ and $b$ are now friendly if $|a - b| \leq K$, and unfriendly otherwise.
Given the orderings of fields on either side of the road through FJ's farm, please count the number of unfriendly crossing pairs of breeds, where a crossing pair of breeds is defined as in the preceding problems.

inputFormat: The first line of input contains $N$ ($1 \leq N \leq 100,000$) and $K$ ($0 \leq K < N$). The next $N$ lines describe the order, by breed ID, of fields on one side of the road; each breed ID is an integer in the range $1 \ldots N$. The last $N$ lines describe the order, by breed ID, of the fields on the other side of the road. Each breed ID appears exactly once in each ordering.

outputFormat: Please output the number of unfriendly crossing pairs of breeds.

translation: 给出两个排列 $A,B$ ，相等的数之间连线，求数对 $(i,j)$ 的个数。其中 $(i,j)$ 满足：它们所在两个排列间对应的线交叉且 $|i-j|>k$ 。

hint: In this example, breeds 1 and 4 are unfriendly and crossing, as are breeds 1 and 3.


title: [USACO17FEB] Why Did the Cow Cross the Road I G

description:
Why did the cow cross the road? Well, one reason is that Farmer John's farm simply has a lot of roads, making it impossible for his cows to travel around without crossing many of them.

奶牛们为什么要穿马路？一个原因只是因为FJ的牧场的路实在是太多了，使得奶牛们每天不得不穿梭在许许多多的马路中央

FJ's farm is arranged as an $N \times N$ square grid of fields ($3 \leq N \leq 100$), with a set of $N-1$ north-south roads and $N-1$ east-west roads running through the interior of the farm serving as dividers between the fields. A tall fence runs around the external perimeter, preventing cows from leaving the farm. Bessie the cow can move freely from any field to any other adjacent field (north, east, south, or west), as long as she carefully looks both ways before crossing the road separating the two fields. It takes her $T$ units of time to cross a road ($0 \leq T \leq 1,000,000$).

FJ的牧场可以看作是一块 $N\times N$ 的田地（$3\le N\le 100$），$N-1$ 条南北向的道路和 $N-1$ 条东西向的道路贯穿整个牧场，同时是每块田野的分界线。牧场的最外面是一圈高大的栅栏以防止奶牛离开牧场。Bessie只要穿过分离两块田野的道路，就可以从任何田野移动到与其相邻的田野里去（北，东，南或西）。当然，Bessie穿过每一条马路都是需要$T$ 时间的。（$0\le T\le 1,000,000$）

One day, FJ invites Bessie to visit his house for a friendly game of chess. Bessie starts out in the north-west corner field and FJ's house is in the south-east corner field, so Bessie has quite a walk ahead of her. Since she gets hungry along the way, she stops at every third field she visits to eat grass (not including her starting field, but including possibly the final field in which FJ's house resides). Some fields are grassier than others, so the amount of time required for stopping to eat depends on the field in which she stops.

有一天，FJ邀请Bessie来他家下棋，Bessie从牧场的西北角出发，FJ的家在牧场的东南角。因为Bessie在中途可能会饿，所以她每走过三块田野就要停下来，享用她所在田野上的新鲜的牧草（不包括Bessie的出发点，但是可能会包括终点FJ的家），牧场上有些田野的牧草长得比其他地方茂盛，所以Bessie对应的停留时间也会变长。

Please help Bessie determine the minimum amount of time it will take to reach FJ's house.

请帮帮Bessie计算出她走到FJ家的最短时间。

inputFormat:
The first line of input contains $N$ and $T$. The next $N$ lines each contain $N$ positive integers (each at most 100,000) describing the amount of time required to eat grass in each field. The first number of the first line is the north-west corner.

接下来 $N$ 行，每行 $N$ 个数表示每块田野Bessie需要停留的时间（每块最多不超过$100,000$），第一行的第一块田野是牧场的西北角

outputFormat:
Print the minimum amount of time required for Bessie to travel to FJ's house.

一行一个整数表示Bessie走到FJ家的最短时间

hint:
The optimal solution for this example involves moving east 3 squares (eating the "10"), then moving south twice and west once (eating the "5"), and finally moving south and east to the goal.

对于样例，Bessie先向东走过了三块田野（在“10”停留），再向南走两步，又向西走了一步（在“5”停留），最后向南走一步，再向东走一步到达FJ的家（不用停留），总共时间是15（停留时间）+16（穿马路时间）=31

感谢@jzqjzq 提供翻译


title: 二进制

description:
小 Z 最近学会了二进制数，他觉得太小的二进制数太没意思，于是他想对一个巨大二进制数做以下 $4$ 种基础运算：

运算 $1$：将整个二进制数加 $1$。

运算 $2$：将整个二进制数减 $1$。

运算 $3$：将整个二进制数乘 $2$。

运算 $4$：将整个二进制数整除 $2$。

小 Z 很想知道运算后的结果，他只好向你求助。

（Ps：为了简化问题，数据保证 `+`，`-` 操作不会导致最高位的进位与退位）

inputFormat:
第一行两个正整数 $n,m$，表示原二进制数的长度以及运算数。

接下来一行 $n$ 个字符，分别为 `0` 或 `1` 表示这个二进制数。

第三行 $m$ 个字符，分别为 `+`，`-`，`*`，`/`，对应运算 $1,2,3,4$。

outputFormat: 一行若干个字符，表示经过运算后的二进制数。


title: K皇后

description:
小 Z 最近捡到了一个 $n$ 行 $m$ 列的棋盘，棋盘上的格子的横纵坐标从 $1$ 开始编号，他想在棋盘上摆放 $K$ 个皇后。他想知道在他摆完这 $K$ 个皇后之后，棋盘上还有多少个格子是不会被攻击到的。

**注意：一个皇后会攻击到这个皇后所在的那一行，那一列，以及两条对角线。**

inputFormat:
第一行三个正整数 $n,m,K$，表示棋盘的行列，以及小 Z 摆放的皇后的个数。

接下来 $K$ 行，每行两个正整数 $x,y$，表示这个皇后被摆在了第 $x$ 行，第 $y$ 列，数据保证任何两个皇后都不会被摆在同一个格子里。

outputFormat: 仅一个整数，表示棋盘上还有多少个格子是不会被攻击到的。


title: Sam数

description: 小 Z 最近发现了一种非常有趣的数，他将这种数称之为 Sam 数。Sam 数具有以下特征：相邻两位的数字之差不超过 $2$。小 Z 还将 Sam 数按位数进行了分类，他将一个 $k$ 位 Sam 数称之为 $k$ 阶 Sam 数。但不幸的是小 Z 发现他数不清第 $k$ 阶的 Sam 数一共有多少个，这个时候机智的他想到了向你求助。

inputFormat: 输入共一行一个整数 $k$，含义见题面。

outputFormat:
一行一个整数 $ans$，表示 $k$ 阶的 Sam 数的个数。

由于第 $k$ 阶 Sam 数非常多，你只需要输出 $ans\bmod 1000000007$。


title: 小Z的AK计划

description:
在小 Z 的家乡，有机房一条街，街上有很多机房。每个机房里都有一万个人在切题。小 Z 刚刷完 CodeChef，准备出来逛逛。

机房一条街有 $n$ 个机房，第 $i$ 个机房的坐标为 $x_i$ ，小 Z 的家坐标为 $0$。小 Z 在街上移动的速度为 $1$，即从 $x_1$ 到 $x_2$ 所耗费的时间为 $|x_1 - x_2|$。

每个机房的学生数量不同，ACM 题目水平也良莠不齐。小 Z 到达第 $i$ 个机房后，可以花 $t_i$ 的时间想题，然后瞬间 AK；当然，也可以过机房而不入。

小 Z 现在只有 $m$ 个单位时间，之后他就该赶着去打 Codeforces 了。现在他想知道自己最多能在多少个机房 AK，希望你帮帮他。

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

接下来 $n$ 行，每行包含两个整数 $x_i,t_i$。

outputFormat: 第一行包含一个整数，表示小 Z 最多能 AK 的机房数量。


title: [USACO17FEB] Why Did the Cow Cross the Road III G

background: 给定长度为2N的序列，1~N各处现过2次，i第一次出现位置记为ai，第二次记为bi，求满足ai<aj<bi<bj的对数

description:
The layout of Farmer John's farm is quite peculiar, with a large circular road running around the perimeter of the main field on which his cows graze during the day. Every morning, the cows cross this road on their way towards the field, and every evening they all cross again as they leave the field and return to the barn.

As we know, cows are creatures of habit, and they each cross the road the same way every day. Each cow crosses into the field at a different point from where she crosses out of the field, and all of these crossing points are distinct from each-other. Farmer John owns $N$ cows, conveniently identified with the integer IDs $1 \ldots N$, so there are precisely $2N$ crossing points around the road. Farmer John records these crossing points concisely by scanning around the circle clockwise, writing down the ID of the cow for each crossing point, ultimately forming a sequence with $2N$ numbers in which each number appears exactly twice. He does not record which crossing points are entry points and which are exit points.

Looking at his map of crossing points, Farmer John is curious how many times various pairs of cows might cross paths during the day. He calls a pair of cows $(a,b)$ a "crossing" pair if cow $a$'s path from entry to exit must cross cow $b$'s path from entry to exit. Please help Farmer John count the total number of crossing pairs.

inputFormat: The first line of input contains $N$ ($1 \leq N \leq 50,000$), and the next $2N$ lines describe the cow IDs for the sequence of entry and exit points around the field.

outputFormat: Please print the total number of crossing pairs.


title: 学英语

description:
为了适应紧张的大学学习生活，小 Z 发愤图强开始复习巩固英语。

由于小 Z 对数学比较有好感，他首先复习了数词。小 Z 花了一整天的时间，终于把关于基数词的知识都搞懂了。于是小 Z 非常兴奋，决定出一些题目考考已经过了英语四级、人称英语帝的小 G。考法很简单：小 Z 给出某个整数 $x$ 的英文写法，要求小 D 用阿拉伯数字写出 $x$。

小 Z 会保证以下几点：

1. $-999,999,999 \leq  x \leq 999,999,999$

2. 题目中只会用到以下这些英文单词：

`negative, zero, one, two, three, four, five, six, seven, eight, nine, ten`

`eleven, twelve, thirteen, fourteen, fifteen, sixteen, seventeen, eighteen, nineteen, twenty`

`thirty, forty, fifty, sixty, seventy, eighty, ninety, hundred, thousand, million`

3. 若 $x$ 为负数，题目中第一个单词是 `negative`，否则任何时候都不会出现 `negative` 这个词。

4. 由于小 Z 很牛 B，他不知道像 $103$ 这样的数字要写成 `one hundred and three` 而是直接写成了 `one hundred three`，就是说小 Z 的所有题目中都没有写 `and` 这个词（尽管本应该是要写的），请你谅解。

5. 除了第 4 点， 其他还是基本符合英语的语法规则的， 比如 $1500$ 他会写成 `one thousand five hundred` 而不会写成 `fifteen hundred`。

小 D 拿到题目后不屑地说了一句：水题！写个程序么好了……

但是小 D 要出去玩（此时应该已经在千里之外爽玩了） ，这个任务就交给你了。

inputFormat: 一行，题目描述中所说的 $x$ 的英文写法。

outputFormat: 一行， $x$ 的阿拉伯数字写法。

samples: eight hundred fourteen thousand twenty two


title: 欢总喊楼记

description:
诗经有云：

关关雎鸠，在河之洲。窈窕淑女，君子好逑。

又是一个被风吹过的夏天……一日欢总在图书馆中自习，抬起头来，只见一翩跹女子从面前飘过，真是回眸一笑百媚生，六宫粉黛无颜色！一阵诗情涌上欢总心头，他顺手写下那诗句：

啊，你是爱，是暖，是希望，你是人间四月天！

任时光匆匆而过，欢总一直没能忘记那女子。人言单思苦，欢总偏单思。夜夜难入梦，此心淑可知。偶然一次机会，欢总得知了那女孩的信息。一日，欢总终于鼓起了勇气，他向她表白！

那晚的夜色格外美丽，欢总在楼下慷慨激昂，气氛浪漫而感人。女孩有点心动了，但是直接答应是不是有点太不矜持了呢？于是，她想难难欢总，看看他到底有多少诚意。

女孩给出了两个整数 L 和 R，她要欢总数出到底有多少个这样的 X：L <= X <= R，且 X 的最高位与最低位相等（十进制下）。比如，2、101、329873可以是这样的 X，而23、4567就不是。

孩子们，欢总下辈子的幸福生活就靠你们帮忙了！

inputFormat: 一行，这一行包括两个整数 L 和 R。

outputFormat: 一行，这一行包括一个整数，即满足所述性质的 X 的个数。


title: 考场奇遇

background: 本市的某神校里有一个学霸，他的名字叫小明（为了保护主人公的隐私，他的名字都用“小明”代替）。在这次的期中考试中，小明同学走桃花运，在考场上认识了一位女生，她的名字叫小红（同样是为了保护隐私）。

description:
英语考试结束了，打完铃，她就主动来找小明说话，一来就要借英语卷子对答案。小明是公认的英语大神，二话不说就把卷子借给了她。小红对了一遍答案，简直是千差万别，她不禁冒出了冷汗。这时，小明走过来，安慰她：“没事，我又不是标准答案，不一定全对。”

已知小明答案的准确率是 $A\%$，一共有 $N$ 道题，给出小红对答案的结果 $S$（一个长为 $N$ 的 01 串，其中 `1` 表示两人答案一样，`0` 表示不一样）。为了简化问题，所有题目都是判断题。

请你帮小红写一个程序，计算出她对 $Q$ 题及以上的概率。

（P.S. 小明后来把那张卷子送给了小红，别想多了，不是定情信物）

inputFormat:
第 $1$ 行，三个正整数 $N,A,Q$。

第 $2$ 行，一个 01 字符串 $S$。

outputFormat: 一行，一个实数，表示她对 $Q$ 题及以上的概率。（保留 $3$ 位小数）

hint:
对于 $90\%$ 数据，$N \leq 50, N-5 \leq Q \leq N$。

对于剩下的 $10\%$ 数据，$N \leq 10000, Q = 0$。


title: 鸿雁传书

background: 小明给小红写了一封情书，他想把文章变得更完美，所以要进行排版。

description:
他一共写了 $N$ 个单词，为了美观，要把 $N$ 个单词分成 $K$ 行。单词的相对顺序不能变化。为了简化问题，无需考虑单词间的空格。

小红会喜欢整齐的情书，小明想赢得小红的芳心，所以，他找到你，想让你帮他写一个程序，帮他排版，使得每行字母数的方差最小。请你求出最小的方差。

inputFormat:
第 $1$ 行，两个正整数 $N,K$。

第 $2$ 行，$N$ 个空格隔开的单词。

outputFormat: 一行，一个 $1$ 位小数表示每行字母数的最小方差。

samples:
4 2
xxx xxxxx xxxx xx
（输入的本来是一封情书，被和谐了……）

hint:
【样例说明】

```plain
xxx xxxxx
xxxx xx
```

$1 \div 2 \times ((8-7)^2+(6-7)^2) = 1$。

【数据范围】

对于 $30\%$ 数据，$N \leq 100$，$K \leq 3$。

对于全部数据，$N \leq 1000$，$K \leq 100$，单词长度 $\leq 20$。


title: 看球泡妹子

background: 2014 年巴西世界杯开幕了，现在满城皆是世界杯，商家们利用它大赚一笔，小明和小红也借此机会增进感情。

description:
本届世界杯共有 $n$ 支球队，$m$ 场比赛。男球迷小明喜欢看比赛，女球迷小红喜欢看帅哥。每支球队在小明眼里的实力值为 $a_i$，在小红眼里的帅哥数量为 $b_i$。

每场比赛有两个球队对抗，它们的编号分别是 $p_i$ 和 $q_i$。小明认为一场比赛的精彩度等于两队实力的乘积，小红则认为是两队帅哥数量之和。

由于体力的限制，他们最多只能看 $k$ 场比赛。当然，只要看比赛，两个人一定会一起看。小明作为男生，理应迁就一下女生，所以，请你写一个程序，求出小红看到比赛的精彩度总和不小于 $c$ 的情况下，小明看到比赛的精彩度的最大总和。

inputFormat:
第一行包含四个正整数 $n,m,k,c$。

第二行有 $n$ 个用空格隔开的正整数 $a_i$。

第三行有 $n$ 个用空格隔开的正整数 $b_i$。

接下来 $m$ 行，每行两个正整数 $p_i,q_i$。

outputFormat: 一行，一个正整数表示小明看到比赛的精彩度的最大总和。如果无论如何都无法满足小红的要求，输出 `-1`。


title: [NOI2014] 起床困难综合症

description:
$21$ 世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。作为一名青春阳光好少年，atm 一直坚持与起床困难综合症作斗争。通过研究相关文献，他找到了该病的发病原因：在深邃的太平洋海底中，出现了一条名为 drd 的巨龙，它掌握着睡眠之精髓，能随意延长大家的睡眠时间。正是由于 drd 的活动，起床困难综合症愈演愈烈，以惊人的速度在世界上传播。为了彻底消灭这种病，atm 决定前往海底，消灭这条恶龙。历经千辛万苦，atm 终于来到了 drd 所在的地方，准备与其展开艰苦卓绝的战斗。drd 有着十分特殊的技能，他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来，drd 的防御战线由 $n$ 扇防御门组成。每扇防御门包括一个运算 $op$ 和一个参数 $t$，其中运算一定是 $\text{OR},\text{XOR},\text{AND}$ 中的一种，参数则一定为非负整数。如果还未通过防御门时攻击力为 $x$，则其通过这扇防御门后攻击力将变为 $x~op~t$。最终 drd 受到的伤害为对方初始攻击力 $x$ 依次经过所有 $n$ 扇防御门后转变得到的攻击力。

由于 atm 水平有限，他的初始攻击力只能为 $0$ 到 $m$ 之间的一个整数（即他的初始攻击力只能在 $0,1,\ldots,m$ 中任选，但在通过防御门之后的攻击力不受 $m$ 的限制）。为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 drd 受到多少伤害。

inputFormat:
输入文件的第 $1$ 行包含 $2$ 个整数，依次为 $n, m$，表示 drd 有 $n$ 扇防御门，atm 的初始攻击力为 $0$ 到 $m$ 之间的整数。

接下来 $n$ 行，依次表示每一扇防御门。每行包括一个字符串 $op$ 和一个非负整数 $t$，两者由一个空格隔开，且 $op$ 在前，$t$ 在后，$op$ 表示该防御门所对应的操作，$t$ 表示对应的参数。

outputFormat: 输出一行一个整数，表示 atm 的一次攻击最多使 drd 受到多少伤害。

hint:
【样例说明】

atm 可以选择的初始攻击力为 $0,1,\ldots ,10$。

假设初始攻击力为 $4$，最终攻击力经过了如下计算

- $4 \text{ AND } 5 = 4$；
- $4 \text{ OR } 6 = 6$；
- $6 \text{ XOR } 7 = 1$。

类似的，我们可以计算出初始攻击力为 $1,3,5,7,9$ 时最终攻击力为 $0$，初始攻击力为 $0,2,4,6,8,10$ 时最终攻击力为 $1$，因此atm的一次攻击最多使drd受到的伤害值为 $1$。

【数据规模与约定】

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

- 特殊性质 $\mathrm A$：存在一扇防御门为 $\texttt{AND 0}$；
- 特殊性质 $\mathrm B$：所有防御门的操作均相同。

对于所有数据，保证 $2\le n\le 10^5$，$0\le m\le 10^9$，$0\le t\le 10^9$，且 $\mathrm{op}$ 一定为 $\verb!AND!,\verb!OR!,\verb!XOR!$ 中的一种。


title: [USACO14MAR] Sabotage G

description:
Farmer John's arch-nemesis, Farmer Paul, has decided to sabotage Farmer John's milking equipment!

The milking equipment consists of a row of N (3 <= N <= 100,000) milking machines, where the ith machine produces M\_i units of milk (1 <= M\_i <= 10,000).  Farmer Paul plans to disconnect a contiguous block of these machines -- from the ith machine up to the jth machine (2 <= i <= j <= N-1); note that Farmer Paul does not want to disconnect either the first or the last machine, since this will make his plot too easy to discover.  Farmer Paul's goal is to minimize the average milk production of the remaining machines.  Farmer Paul plans to remove at least 1 cow, even if it would be better for him to avoid sabotage entirely.

Fortunately, Farmer John has learned of Farmer Paul's evil plot, and he is wondering how bad his milk production will suffer if the plot succeeds.  Please help Farmer John figure out the minimum average milk production of the remaining machines if Farmer Paul does succeed.

农夫约翰的头号敌人保罗决定破坏农民约翰的挤奶设备。挤奶设备排成一行，共N（3<= N <=100000）台挤奶机，其中第i个台挤奶机生产M\_i单位（1 <= M\_i<=10,000）的牛奶。

保罗计划切断一段连续的挤奶机，从第i台挤奶机到第j台挤奶机（2<= i<= j<= N-1）。注意，他不希望断开第一台或最后一台挤奶机，因为这将会使他的计划太容易被发现。保罗的目标是让其余机器的平均产奶量最小。保罗计划除去至少1台挤奶机。

请计算剩余机器的最小平均产奶量。

inputFormat:
第 1 行：一个整数 N。

第 2 到 N+1 行：第 i+1 行包含一个整数 M\_i。

outputFormat: 第 1 行： 一个实数， 表示平均牛奶产量的最小值， 保留三位小数 （四舍五入）。


title: [NOIP2014 普及组] 比例简化

background: NOIP2014 普及组 T2

description:
在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 $1498$ 人，反对的有 $902$ 人，那么赞同与反对的比例可以简单的记为 $1498:902$。

不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 $5:3$，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。

现给出支持人数 $A$，反对人数 $B$，以及一个上限 $L$，请你将 $A$ 比 $B$ 化简为 $A'$ 比 $B'$，要求在 $A'$ 和 $B'$ 均不大于 $L$ 且 $A'$ 和 $B'$ 互质（两个整数的最大公约数是 $1$）的前提下，$\dfrac{A'}{B'} \ge  \dfrac{A}{B}$ 且 $\dfrac{A'}{B'} - \dfrac{A}{B}$ 的值尽可能小。

inputFormat: 共一行，包含三个整数 $A,B,L$，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。

outputFormat: 共一行，包含两个整数 $A',B'$，中间用一个空格隔开，表示化简后的比例。


title: 城墙

description:
有一次，一个贪婪的国王命令他的骑士在他的城堡外修建一堵围墙，要求围墙离城堡的最近距离不能少于 $L$。

城堡是一个 $n$ 边形，国王非常吝啬，不愿意多花建一米的围墙，多建的话他会杀掉负责修建的骑士。

请你帮助这个倒霉的骑士，帮他求出最少需要修建多长的围墙。

inputFormat:
第一行两个整数 $n$，$L$ 表示多边形的边数和最小距离。

接下里 $n$ 行，每行两个整数，表示多边形上的点的坐标。

outputFormat: 一行一个整数，即最小的围墙长度，四舍五入到整数。


title: [USACO17FEB] Why Did the Cow Cross the Road I S

background: 征求翻译。如果你能提供翻译（不接受百度翻译等机器翻译）或者题意简述，请直接发讨论，感谢你的贡献。

description:
Farmer John's cows are trying to learn to cross the road effectively. Remembering the old "why did the chicken cross the road?" joke, they figure the chickens must be experts on crossing the road, and go off in search of chickens to help them.

农夫约翰的牛们正在尝试去学会高效地穿越马路。熟知经典的笑话“为什么鸡要过马路？”，他们想到鸡一定是过马路的专家，便动身寻找能够帮助它们的鸡。

As it turns out, chickens are very busy creatures and have limited time to help the cows. There are $C$ chickens on the farm ($1 \leq C \leq 20,000$), conveniently numbered $1 \ldots C$, and each chicken $i$ is only willing to help a cow at precisely time $T_i$. The cows, never in a hurry, have more flexibility in their schedules. There are $N$ cows on the farm ($1 \leq N \leq 20,000$), conveniently numbered $1 \ldots N$, where cow $j$ is able to cross the road between time $A_j$ and time $B_j$. Figuring the "buddy system" is the best way to proceed, each cow $j$ would ideally like to find a chicken $i$ to help her cross the road; in order for their schedules to be compatible, $i$ and $j$ must satisfy $A_j \leq T_i \leq B_j$.

牛们发现，鸡是一种特别繁忙的动物，并且只有一定的时间来帮助它们。农场上共有$C$ 只鸡（$1\le C\le 20000$），十分便利地被编号为$1...C$, 而且，每只鸡$i$ 只有恰好在时间$T_{i}$ 时才会愿意帮助牛们。而从不慌张的牛们，有更加灵活的时间安排。农场上共有$N$ 只牛（$1\le N\le 20000$），也十分便利地被编号为$1...N$，牛$j$ 在时间$A_{j}$ 到$B_{j}$ 之间可以穿过马路。想到“小伙伴系统”是最好的行进方式，每只牛$j$ 会理想地愿意找到一只鸡$i$ 来帮助她穿过马路；为了是它们的时间表不冲突，$i$ 和$j$ 必须满足$A_{j}\le T_{i}\le B_{j}$

If each cow can be paired with at most one chicken and each chicken with at most one cow, please help compute the maximum number of cow-chicken pairs that can be constructed.

如果每头奶牛最多只能配一只鸡，而每只鸡最多只配上一头牛，请帮忙计算出可以构造的牛鸡对的最大数量。

inputFormat:
The first line of input contains $C$ and $N$. The next $C$ lines contain $T_1 \ldots T_C$, and the next $N$ lines contain $A_j$ and $B_j$ ($A_j \leq B_j$) for $j = 1 \ldots N$. The $A$'s, $B$'s, and $T$'s are all non-negative integers (not necessarily distinct) of size at most 1,000,000,000

第一行的输入包括$C$ 和$N$。下面的$C$ 行包括$T1...TC$，再接下来的$N$ 行包括$A_{j}$ 和$B_{j}$($A_{j}\le B_{j}$)，$j=1...N$。所有$A,B$ 与$T$ 都是非负整数（可能相等），并皆小于等于$1,000,000,000$。

outputFormat:
Please compute the maximum possible number of cow-chicken pairs.

请计算最大的可行牛-鸡配对数。

hint: 感谢@Darkins 提供翻译


title: 拆地毯

background: 还记得 NOIP 2011 提高组 Day1 中的铺地毯吗？时光飞逝，光阴荏苒，三年过去了。组织者精心准备的颁奖典礼早已结束，留下的则是被人们踩过的地毯。请你来解决类似于铺地毯的另一个问题。

description:
会场上有 $n$ 个关键区域，不同的关键区域由 $m$ 条无向地毯彼此连接。每条地毯可由三个整数 $u$、$v$、$w$ 表示，其中 $u$ 和 $v$ 为地毯连接的两个关键区域编号，$w$ 为这条地毯的美丽度。

由于颁奖典礼已经结束，铺过的地毯不得不拆除。为了贯彻勤俭节约的原则，组织者被要求只能保留至多 $K$ 条地毯，且保留的地毯构成的图中，任意可互相到达的两点间只能有一种方式互相到达。换言之，组织者要求新图中不能有环。现在组织者求助你，想请你帮忙算出这至多 $K$ 条地毯的美丽度之和最大为多少。

inputFormat:
第一行包含三个正整数 $n$、$m$、$K$。

接下来 $m$ 行中每行包含三个正整数 $u$、$v$、$w$。

outputFormat: 只包含一个正整数，表示这 $K$ 条地毯的美丽度之和的最大值。

hint:
选择第 $1$、$2$、$4$ 条地毯，美丽度之和为 $10 + 9 + 3 = 22$。

若选择第 $1$、$2$、$3$ 条地毯，虽然美丽度之和可以达到 $10 + 9 + 7 = 26$，但这将导致关键区域 $1$、$2$、$3$ 构成一个环，这是题目中不允许的。

$1\le n,m,k \le 10^5$。


title: 还教室

background: 还记得 NOIP 2012 提高组 Day2 中的借教室吗？时光飞逝，光阴荏苒，两年过去了，曾经借教室的同学们纷纷归还自己当初租借的教室。请你来解决类似于借教室的另一个问题。

description:
在接受借教室请求的 $n$ 天中，第 $i$ 天剩余的教室为 $a_i$ 个。作为大学借教室服务的负责人，你需要完成如下三种操作共 $m$ 次：

1. 第 $l$ 天到第 $r$ 天，每天被归还 $d$ 个教室；
1. 询问第 $l$ 天到第 $r$ 天教室个数的平均数；
1. 询问第 $l$ 天到第 $r$ 天教室个数的方差。

inputFormat:
第一行包括两个正整数 $n$ 和 $m$，其中 $n$ 为借教室的天数，$m$ 为操作次数。

接下来一行，共包含 $n$ 个整数，第$i$个整数表示第 $i$ 天剩余教室数目为 $a_i$个。

接下来 $m$ 行，每行的第一个整数为操作编号（只能为 $1$ 或 $2$ 或 $3$），接下来：

包含两个正整数 $l$ 和 $r$，若操作编号为 $1$，则接下来再包含一个正整数 $d$。

outputFormat: 对于每个操作 2 和操作 3，输出一个既约分数（分子与分母互质）表示询问的答案（详见样例）。特别地，若答案为 $0$，请输出 $\verb!0/1!$。

hint:
对于全部测试数据满足：$1 \leq l \leq r \leq n \leq 10^5, m\leq 10^5$，$0 \leq a_i \leq 10$，$1 \leq d \leq 3$，操作 $1$ 的数量不超过 $10\%$。

注意：$a_i$和 $d$ 的范围很小及操作 $1$ 数量很少的原因是为了保证答案的分子不会很大，以防止答案的分子溢出 $64$ 位整数的范围，这与题目做法无关。


title: 皇后游戏

background: 还记得 NOIP 2012 提高组 Day1 的国王游戏吗？时光飞逝，光阴荏苒，两年过去了。国王游戏早已过时，如今已被皇后游戏取代，请你来解决类似于国王游戏的另一个问题。

description:
皇后有 $n$ 位大臣，每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临，皇后决定为 $n$ 位大臣颁发奖金，其中第 $i$ 位大臣所获得的奖金数目为第 $i - 1$ 位大臣所获得奖金数目与前 $i$ 位大臣左手上的数的和的较大值再加上第 $i$ 位大臣右手上的数。

形式化地讲：我们设第 $i$ 位大臣左手上的正整数为 $a_i$，右手上的正整数为 $b_i$，则第 $i$ 位大臣获得的奖金数目为 $c_i$ 可以表达为：

$$ c_{i} = \begin{cases} a_{1}+b_{1}  & ,i=1 \\ \displaystyle \max \left \{ c_{i-1},\sum_{j=1}^{i}a_{j} \right \} +b_{i} & ,2\leq i \leq n \end{cases} % ![](https://cdn.luogu.com.cn/upload/pic/1257.png) $$

当然，吝啬的皇后并不希望太多的奖金被发给大臣，所以她想请你来重新安排一下队伍的顺序，使得获得奖金最多的大臣，所获奖金数目尽可能的少。

注意：重新安排队伍并不意味着一定要打乱顺序，我们允许不改变任何一位大臣的位置。

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

接下来 $T$ 个部分，每个部分的第一行包含一个正整数 $n$，表示大臣的数目。

每个部分接下来 $n$ 行中，每行两个正整数，分别为 $a_i$ 和 $b_i$，含义如上文所述。

outputFormat: 共 $T$ 行，每行包含一个整数，表示获得奖金最多的大臣所获得的奖金数目。

hint:
按照 $1,2,3$ 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 $10$；

按照 $1,3,2$ 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 $9$；

按照 $2,1,3$ 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 $9$；

按照 $2,3,1$ 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 $8$；

按照 $3,1,2$ 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 $9$；

按照 $3,2,1$ 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 $8$。

当按照 $3,2,1$ 这样排列队伍时，三位大臣左右手的数分别为：

$(1,2),(2,2),(4,1)$。

- 第 $1$ 位大臣获得的奖金为 $1+2=3$；
- 第 $2$ 位大臣获得的奖金为 $\max{3,3}+2=5$；
- 第 $3$ 为大臣获得的奖金为 $\max{5,7}+1=8$。

对于全部测试数据满足：$T\le10$，$1\le n\le 2\times 10^4$，$1\le a_i,b_i\le 10^9$。


title: [USACO17FEB] Why Did the Cow Cross the Road II S

description:
The long road through Farmer John's farm has $N$ crosswalks across it, conveniently numbered $1 \ldots N$ ($1 \leq N \leq 100,000$). To allow cows to cross at these crosswalks, FJ installs electric crossing signals, which light up with a green cow icon when it is ok for the cow to cross, and red otherwise. Unfortunately, a large electrical storm has damaged some of his signals. Given a list of the damaged signals, please compute the minimum number of signals that FJ needs to repair in order for there to exist some contiguous block of at least $K$ working signals.

共有N个信号灯，编号为1~N，有B个信号灯损坏，给你它们的编号。

问，最少修好几个信号灯，可以有K个编号连续的信号灯。

inputFormat: The first line of input contains $N$, $K$, and $B$ ($1 \leq B, K \leq N$). The next $B$ lines each describe the ID number of a broken signal

outputFormat: Please compute the minimum number of signals that need to be repaired in order for there to be a contiguous block of $K$ working signals somewhere along the road.

hint: 感谢@ jlyzxxm1 提供题意简述


title: 图书馆书架上的书

background:
NOIP2014 即将来临，JC 书院信息学兴趣小组也在积极准备着，于是乎 usqwedf 、梁大大、畜牧办专场、YH 大神和 LHT 大神也要推出“蓝翔杯”。

在图书馆、 MC 等大神们相继举办了 JC 书院联合竞赛“弃疗杯”“UID#3”，据说 YH 大神还要苦苦钻研网络流的 JC 书院 $13$ 届 $13$ 班的 WZF 神牛和 MZC 神牛听到这个消息后决定联袂打造“十三点杯”。但是出一套题目是一项繁重的工作，于是他们决定再拉上和他们同届并且同班还同为 JC 书院信息学兴趣小组成员同时也在图书馆正在找“Hello World”标程的蒟蒻 SY。

可怜的蒟蒻 SY 因为还要写一大堆的作业，怎么也不肯答应，终于 WZF 神牛妥协说：“我来出一道题，你要是做出来了我们就不让你出题，否则……你懂的。”蒟蒻 SY 才刚看完 WZF 神牛即兴出的题目，便带着哭腔对 WZF 神牛说：“你们赢了。”。

可是蒟蒻 SY 实在是太弱了，根本不会出题，他绞尽脑汁，终于想到了一个办法——将 WZF 神牛出的题目 copy 一下。

description: 图书馆有 $n$ 个书架，第 $1$ 个书架后面是第 $2$ 个书架，第 $2$ 个书架后面是第 $3$ 个书架……第 $n-1$ 个书架后面是第 $n$ 个书架，第 $n$ 个书架后面是第 $1$ 个书架，第 $i$ 个书架上有 $b_i$ 本书。现在，为了让图书馆更美观，WZF 神牛让蒟蒻 SY 搬动书架上的书，使每个书架上的书一样多。由于搬动的书可能会很多，所以蒟蒻 SY 只能将一个书架上的书搬到与其相邻的两个书架上。那么蒟蒻 SY 最少搬动几本书呢？

inputFormat: 共 $2$ 行，第 $1$ 行 $1$ 个正整数 $n$，第 $2$ 行 $n$ 个非负整数，第 $i$ 个为 $b_i$。

outputFormat:
输出共 $n+1$ 行。

第一行 $1$ 个正整数 $m$，表示蒟蒻 SY 最少搬动 $m$ 本书；

之后 $n$ 行，每行 $2$ 个整数，第 $i$ 行有两个整数 $af_i$ 和 $ab_i$，分别表示蒟蒻 SY 要将第 $i$ 个书架上的 $af_i$ 本书和 $ab_i$ 本书分别搬到它前面的一个书架上和它后面的一个书架上。

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

对于全部数据，$1\le n\le 10^5+1$，且 $n$ 必为奇数；$b_i\le 10^7$。

若 $af_i$ 为负数，则说明蒟蒻 SY 要把第 $i$ 个书架前面的那个书架上的 $-af_i$ 本书搬到第 $i$ 个书架上。

同理，若 $ab_i$ 为负数，则说明蒟蒻 SY 要把第 $i$ 个书架后面的那个书架上的 $-ab_i$ 本书搬到第 $i$ 个书架上。


title: 狂奔的Wzf

background: 众所周知，Wzf一直想写作业。可是今天，它的作业被WSD抢了！！！Wzf很愤怒？！他决定以最快的速度，冲向作业。在他面前是一个迷宫，作业就在其中！

description: Wzf从（1,1）开始，每秒可以向上下左右某一方向走2的次方步，问至少多久可以到达作业？

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

接下来n行，每行m个字符，`$`或者`.`代表可走的空地，`X`表示障碍，`#`表示作业，（保证只有一个作业）

outputFormat: Wzf到达作业最短耗时。如果没有解输出 `-1`。


title: L 国的战斗续之多路出击

background: 广而告之：背景见其他L国的战斗！！大家一起刷

description: 这一次，L 国决定军队分成 $n$ 组，分布在各地，若以 L 国为原点，可以看作在一个直角坐标系内。但是他们都受统一的指挥，指令部共发出 $m$ 个命令。命令有移动、上下转移和左右转移，但是由于某些奇奇怪怪的原因，军队收到命令总是有延迟，为了方便，军方已经写好一个栈，所以你要处理的顺序，应该是从后往前。

inputFormat:
输入包括 $n+m+1$ 行。

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

接下来 $n$ 行，第 $i+1$ 行两个整数 $x_i,y_i$ 表示第 $i$ 支军队的位置。

接下来 $m$ 行，每行首先是一个字符 $c$。
- 若 $c$ 为 `m`，则后面再输入两个整数 $p,q$，表示把每支军队的位置从 $(x_i,y_i)$ 移到 $(x_i+p,y_i+q)$。
- 若 $c$ 为 `x`，则表示把每支军队的位置从 $(x_i,y_i)$ 移到 $(-x_i,y_i)$。
- 若 $c$ 为 `y`，则表示把每支军队的位置从 $(x_i,y_i)$ 移到 $(x_i,-y_i)$。

outputFormat: 输出包含 $n$ 行，第 $i$ 行有两个整数 $x_i',y_i'$，表示第 $i$ 支军队移动后的位置。

hint:
对于 $30\%$ 的数据，$1\leqslant n,m\leqslant 1000$。

对于 $100\%$ 的数据，$1\leqslant n,m\leqslant 5\times 10^5$，$x_i,y_i$ 在 `int` 范围内。


title: Mzc家中的男家丁

background: mzc 与 djn 的…还没有众人皆知，所以我们要来宣传一下。

description: mzc 家很有钱（开玩笑），他家有 $n$ 个男家丁，现在 mzc 要将她们全都聚集起来（干什么就不知道了）。现在知道 mzc 与男家丁们互相之间通信的时间，请算出把他们每个人叫到需要的总时间（要重复的哦）。保证能把他们每个人叫到。

inputFormat: 第一行有一个数 $n$，表示有 $n$ 个男家丁。第二行一个数 $m$ 表示有 $m$ 条通信路线。之后 $m$ 行，每行三个数 $a_i,b_i,c_i$，表示第 $a_i$个男家丁（或 mzx）和第 $b_i$ 个男家丁（或 mzc）通信需要时间（双向）。$a_i\left(\text{或}b_i\right)=0$ 表示 mzc。

outputFormat: 一行，一个数 $sum$，表示把他们每个人叫到需要的总时间。


title: [USACO17FEB] Why Did the Cow Cross the Road III S

description:
Why did the cow cross the road? Well, one reason is that Farmer John's farm simply has a lot of roads, making it impossible for his cows to travel around without crossing many of them.

为什么牛过马路？ 其中一个简单的原因就是农民约翰的农场有很多道路，使得他的母牛不得不穿越许多道路。

FJ's farm is arranged as an $N \times N$ square grid of fields ($2 \leq N \leq 100$), Certain pairs of adjacent fields (e.g., north-south or east-west) are separated by roads, and a tall fence runs around the external perimeter of the entire grid, preventing cows from leaving the farm. Cows can move freely from any field to any other adjacent field (north, east, south, or west), although they prefer not to cross roads unless absolutely necessary.

FJ的农场在 $N\times N$的网格中（ $2\le N\le 100$），某些相邻的区域（例如，南北或东西）由道路分隔，高大的围栏围绕着整个格栅的外围，防止牛离开农场。 牛可以从任何场地自由移动到任何其他相邻的区域（北，东，南或西），不过除非不得已，她们并不愿意穿越道路。

There are $K$ cows ($1 \leq K \leq 100, K \leq N^2$) on FJ's farm, each located in a different field. A pair of cows is said to be "distant" if, in order for one cow to visit the other, it is necessary to cross at least one road. Please help FJ count the number of distant pairs of cows.

在FJ的农场有 $K$ 头牛（$1\le K\le 100,K\le N^{2}$)，每个位于不同的区域。 定义一对牛是“遥远的”，是指让一头牛访问另一头牛时，必须至少穿过一条路。 请帮助FJ计算有多少对牛是“遥远的”。

inputFormat:
The first line of input contains $N$, $K$, and $R$. The next $R$ lines describe $R$ roads that exist between pairs of adjacent fields. Each line is of the form $r$ $c$ $r'$ $c'$ (integers in the range $1 \ldots N$), indicating a road between the field in (row $r$, column $c$) and the adjacent field in (row $r'$, column $c'$). The final $K$ lines indicate the locations of the $K$ cows, each specified in terms of a row and column.

第一行输入包含 $N$， $K$和 $R$。 接下来的 $R$ 行描述存在于相邻区域对之间的 $R$ 条路。 每行的格式为 $r$ ; $c$ ; $r'$ ; $c'$（都是在 $1...N$中的整数），表示在两个相邻的区域（第$r$行第$c$列，和第$r'$  行第$c'$  列）之间的路。 最终的$K$行表示 $K$ 头牛的位置，也用行列来表示。

outputFormat:
Print the number of pairs of cows that are distant.

输出遥远的牛数量对。

hint: 感谢@太阳之神2015 提供翻译


title: [USACO17OPEN] Modern Art P

description:
Art critics worldwide have only recently begun to recognize the creative genius behind the great bovine painter, Picowso.

Picowso paints in a very particular way. She starts with an $N \times N$ blank canvas, represented by an $N \times N$ grid of zeros, where a zero indicates an empty cell of the canvas. She then draws $N^2$ rectangles on the canvas, one in each of $N^2$ colors (conveniently numbered $1 \ldots N^2$). For example, she might start by painting a rectangle in color 2, giving this intermediate canvas:

2 2 2 0

2 2 2 0

2 2 2 0

0 0 0 0

She might then paint a rectangle in color 7:

2 2 2 0

2 7 7 7

2 7 7 7

0 0 0 0

And then she might paint a small rectangle in color 3:

2 2 3 0

2 7 3 7

2 7 7 7

0 0 0 0

Each rectangle has sides parallel to the edges of the canvas, and a rectangle could be as large as the entire canvas or as small as a single cell. Each color from $1 \ldots N^2$ is used exactly once, although later colors might completely cover up some of the earlier colors.

Given the final state of the canvas, please count how many of the $N^2$ colors could have possibly been the first to be painted.

小TY突然想画画，他有独特的艺术风格，他从N×N空白画布开始，其中0表示画布的空单元格。然后他会在画布上绘制恰好矩形，每个颜色是1到N×N中的一个。他每次可以选择任意一种未使用过的颜色进行绘画。例如，他可以从颜色2的矩形开始，画出这样的画布：

2 2 2 0

2 2 2 0

2 2 2 0

0 0 0 0

然后他可以用颜色7绘制一个矩形：

2 2 2 0

2 7 7 7

2 7 7 7

0 0 0 0

然后他可以在颜色3上绘制一个小矩形：

2 2 3 0

2 7 3 7

2 7 7 7

0 0 0 0

每个矩形都平行于画布边缘，而且矩形可以与整个画布一样大或者像一个单元一样小。每个颜色从1到正好使用一次，后来的颜色可能完全覆盖一些较早画上的颜色。

现在已知画布的最终状态，请计算有多少种颜色可能被第一个被画。

inputFormat:
The first line of input contains $N$, the size of the canvas ($1 \leq N \leq 1000$).

The next $N$ lines describe the final picture of the canvas, each containing $N$ integers that are in the range $0 \ldots N^2$. The input is guaranteed to have been drawn as described above, by painting successive rectangles in different colors.

outputFormat: Please output a count of the number of colors that could have been drawn first.

hint:
In this example, color 2 could have been the first to be painted. Color 3 clearly had to have been painted after color 7, and color 7 clearly had to have been painted after color 2. Since we don't see the other colors, we deduce that they also could have been painted first.

感谢@ yhf\_2015 的翻译


title: [USACO17OPEN] Switch Grass P

description:
Farmer John has recently been experimenting with cultivating different types of grass on his farm, realizing that different types of cows like different types of grass. However, he must be careful to ensure that different types of grass are planted sufficiently far away from each-other, in order to prevent them from being inextricably mixed.

FJ's farm consists of $N$ fields ($1 \leq N \leq 200,000$), where $M$ pairs of  fields are connected by bi-directional pathways ($1 \leq M \leq 200,000$).  Using these pathways, it is possible to walk from any field to any other field. Each pathway has an integer length in the range $1 \ldots 1,000,000$. Any pair of fields will be linked by at most one direct pathway.

In each field, FJ initially plants one of $K$ types of grass ($1 \leq K \leq N$). Over time, however, he might decide to switch the grass in some field to a different type. He calls this an "update"  peration. He might perform several updates over the course of time, which are all cumulative in nature.

After each update, FJ would like to know the length of the shortest path between two fields having different grass types. That is, among all pairs of fields having different grass types, he wants to know which two are closest. Ideally,

this number is large, so he can prevent grass of one type from mixing with grass of another type. It is guaranteed that the farm will always have at least two fields with different grass types.

In 30 percent of the input cases, each field will be directly connected to at most 10 pathways.

inputFormat:
The first line of input contains four integers, $N$, $M$, $K$, and $Q$, where $Q$ is the number of updates ($1 \leq Q \leq 200,000$).

The next $M$ lines describe the paths; each one contains three integers $A$, $B$, and $L$, indicating a path from field $A$ to field $B$ (both integers in the range $1 \ldots N$) of length $L$.

The next line indicates the initial type of grass growing in each field ($N$ integers in the range $1 \ldots K$).

Finally, the last $Q$ lines each describe an update, specified by two integers $A$ and $B$, where the grass in field $A$ is to be updated to type $B$.

outputFormat: For each update, print the length of the shortest path between two fields with different types of grass, after the update is applied.

translation:
农夫约翰最近一直在在他的农场试种各种类型的草，他发现不同类型的牛，喜欢不同类型的草。然而，他必须注意，在种草时，不同类型的草，要保持足够远的距离，以防止它们混合。他的农场由总共 $N(1\le N\le 2\times 10^5)$ 块田地组成，其中有 $M(1\le M\le 2\times 10^5)$ 对田地中用小路连接。通过这些小路，这些田地**联通**。每条路的长度在 $[1,10^6]$ 范围内。**没有重边**。
对于每个田地，草的品种是 $K$ 种草 $(1\le K\le N)$ 中的一种。然而，随着时间的推移，他可能决定在某些田地将草转变为不同品种，称之为“更新”。他可能会在一段时间内执行多次更新，这些更新都是**累积**的。
在每次更新之后，他想知道具有**不同**草品种的两个田地之间的**最短路径**的长度。也就是说，在具有不同草品种的所有田地中，他想知道哪两个是最接近的。保证农场将**总是具有至少两个**具有不同草品种的田地。

## 输入格式

第一行输入四个整数 $N,M,K,Q$，$Q$ 代表“更新”的次数。

接下来 $M$ 行，输入三个整数 $A,B,L$，代表一条从 $A$ 到 $B$ 的长度为 $L$ 的双向边。

下一行输入 $N$ 个数，每个数代表这块田地一开始种的哪种草（在 $1\cdots K$）范围内。

最后输入 $Q$ 行，每行两个整数 $A,B$ 表示第 $A$ 块田地的草被换成了第 $B$ 品种。

## 输出格式

总共有 $Q$ 行，每行一个整数。

每个更新后，输出不同种类草之间的最短距离。

## 数据范围

$1\le N,M,Q\le 2\times 10^5,1\le K\le N$。

对于所有边，有 $1\le A,B\le N,1\le L\le 10^6$。

对于 30% 的数据，保证每个田地衍生出来的道路条数 $\le 10$。

hint:
感谢 @∑∵∴∷  的翻译。

简洁翻译 by cc123321 :

给定一张带权无向图，每个点有一个颜色，每次改变一个点的颜色，要求你在操作后输出这个图中最近异色点对之间的距离。最近异色点对定义为：一对点颜色不同，且距离最小。


title: 序列排序

description: 小C有一个N个数的整数序列，这个序列的中的数两两不同。小C每次可以交换序列中的任意两个数，代价为这两个数之和。小C希望将整个序列升序排序，问小C需要的最小代价是多少？

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

第二行，N个整数，表示小C的序列。

outputFormat: 一行，一个整数，表示小C需要的最小代价。

hint:
数据范围：

对于30%的数据，1<=N<=10；

对于全部的数据，1<=N<=100000，输入数据中的其他整数均为正整数且不超过 $10^9$。


title: 赤壁之战

description:
赤壁之战，黄盖率舰满载薪草膏油诈降曹军。

受庞统所授的连环计，曹军战船之间由铁索相连，没有两艘战船在同一位置，也没有铁索两两相交或穿过战船。每艘船都有其一定的战略价值。

为了保证达到破坏效果，黄盖需要保证被点燃的曹军船只两两之间都有铁索连接。他希望找到一种方案点燃总价值尽可能大的战船。

inputFormat:
第一行包含数字 $N$，$M$ ，表示战船的数量和铁索的数量。

接下来包含 $N$ 行，每 $i$ 行包含 $1$ 个数字 $V_i$，表示第 $i$ 艘战船的战略价值。

接下来包含 $M$ 行，每 $i$ 行包含 $2$ 个数字 $S_i$，$T_i$ ，表示铁索连接的两艘船只。

数据保证这是一个可行的舰队安排。

outputFormat: 输出一个数字，表示最多摧毁总价值多少的战船。

hint:
#### 【数据规模】

对于 $50\%$ 的数据，保证 $N$，$M \le 10$。

对于 $100\%$ 数据，保证 $N \le 450$，$M \le 900$，$V_i \le 6000$。

#### 【注意】

题目中的每句话（除了第一段）都有作用。


title: 彩球树

description:
小Z是一个聪明的小学生，他用塑料管和橡皮泥搭成了一棵树，每个橡皮泥上都连接着一个向下的塑料管，有的连接着两根向上的塑料管，有的则连接着一些彩球。

然而，这个工艺品很快因为不平衡倒了下来。于是，小Z请教了和他在同一个班上的妹子小C。在百科全书上看到天平平衡原理的小C知道，如果任何一块橡皮泥向上连接的两根管子的载重量之差超过一个彩球的重量，工艺品就会不平衡倒下来。由于彩球比较重，橡皮泥和塑料管的重量可以忽略不计。

由于移动彩球需要花时间拆卸和固定，小C希望移动最少次数彩球让这个工艺品平衡起来。你能帮助她吗？

inputFormat: 一行，以中序遍历的方式描述了这棵树，B 表示彩球。

outputFormat: 输出一个数字，表示最少移动多少个彩球就能使它平衡，或输出”impossible”，表示如何移动多少个都无法平衡。

hint:
【图解】

[PIC=1259]

【数据规模】

对于 15% 的数据，保证输入文件不超过 25 字节。

对于 50% 的数据，保证输入文件不超过 250 字节。

对于 100% 的数据，保证输入文件不超过 5000 字节。

（PS：1字节≈1字符）

【时空限制】

0.1s/128M


title: 小Z的队伍排列

description:
小 Z 想给班里的同学拍一张合影，为此需要先让大家排好队伍。他希望大家站成 $k$ 排，并规定了每排的人数，保证每一排的人数都不多于后面一排的人数。

这时小 Z 发现队伍看起来还是乱糟糟的，原因是大家的身高互不相同。于是，他希望排头对齐，每位同学都比自己正后方的同学以及排头方向的同学矮。

排完以后，善于思考的小 Z 还想知道一共有多少种排法。

例如，大家排成 $3$ 排，且从后往前每排分别是 $3$ 、 $2$ 、 $1$ 人，就有以下 $16$ 种排法（每个数代表将所有同学身高从高到低排序后该同学的排名）：

$$\begin{matrix}
123 & 123 & 124 & 124 & 125 & 125 & 126 & 126 & 134 & 134 & 135 & 135 & 136 & 136 & 145 & 146 \\
45 & 46 & 35 & 36 & 34 & 36 & 34 & 35 & 25 & 26 & 24 & 26 & 24 & 25 & 26 & 25 \\
6 & 5 & 6 & 5 & 6 & 4 & 5 & 4 & 6 & 5 & 6 & 4 & 5 & 4 & 3 & 3
\end{matrix}$$

可是班里一共有 $n$ 个人，小 Z 算不出来了，希望你帮帮他。

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

第二行包含 $k$ 个整数，表示从后往前每排的人数。

outputFormat: 一行，包含一个整数，表示队伍排列的方案数。

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

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

对于另外 $30\%$ 的数据，只有最后一排超过 $1$ 个人。

对于 $100\%$ 的数据，$1 \le k \le 5$，$1 \le n \le 30$，方案数小于 $2^{32}$。


title: 拉近距离

background: 我是源点，你是终点。我们之间有负权环。 ——小明

description:
在小明和小红的生活中，有 $N$ 个关键的节点。有 $M$ 个事件，记为一个三元组 $(S_i,T_i,W_i)$，表示从节点 $S_i$ 有一个事件可以转移到 $T_i$，事件的效果就是使他们之间的距离减少 $W_i$。

这些节点构成了一个网络，其中节点 $1$ 和 $N$ 是特殊的，节点 $1$ 代表小明，节点 $N$ 代表小红，其他代表进展的阶段。所有事件可以自由选择是否进行，但每次只能进行当前节点邻接的。请你帮他们写一个程序，计算出他们之间可能的最短距离。

inputFormat:
第一行，两个正整数 $N,M$。

之后 $M$ 行，每行 $3$ 个空格隔开的整数 $S_i,T_i,W_i$。

outputFormat: 一行，一个整数表示他们之间可能的最短距离。如果这个距离可以无限缩小，输出``Forever love``。


title: 天作之合

background: 生活就是一次A\*，你是我的第一个目标状态。——小明

description:
在小明的学校中，一共有若干个女生。小明认为每个女生的特征可以抽象为一个6位的数字串其中不重复地包含1~6这6个数码。

在小明心中，有一个理想的女生，她的特征数字串为A。如果串Y是串X交换两个连续的数码所得，那么我们认为特征数字串X和Y相似。首先，小明找到了他的同桌，她的特征数字串为S。每次，小明会寻找一个特征数字串和当前串相似的女生，直到寻找到适合他的（即特征数字串和A相同或相似的）。定义每个女生的合适程度为找到此人至少需要找女生的数量（包括他的同桌和此人自己）。显然，合适程度数值越小的女生越适合小明。

然而，小明觉得老天不会轻易地让他找到，所以他认为合适程度第二小的才是他最合适的伴侣（也就是小红）。那么，请你帮他写一个程序，求出对于小明，小红的合适程度是多少。

inputFormat:
第1行，一个特征数字串A。

第2行，一个特征数字串S。

outputFormat: 一行，一个正整数表示小红的合适程度。

hint:
对于全部数据，保证串A和S合法，且保证能找到。

数据比较弱。


title: 百日旅行

background:
> 重要的不是去哪里，而是和你在一起。——小红

对小明和小红来说，$2014$ 年 $7$ 月 $29$ 日是一个美好的日子。这一天是他们相识 $100$ 天的纪念日。

（小明：小红，感谢你 $2$ 场大考时默默的支持，$100$ 个日夜的陪伴；感谢你照亮我 $100$ 个美好的日子，给我留下无数美好的回忆……在这个美好的日子里，我准备带你去旅行。）

description:
小明和小红还剩下 $n$ 天的假期，小明可以安排旅行的计划。如果连续 $x$ 天旅游，小明需要花旅行费用  $p \times x \times x$ 元；如果连续 $x$ 天不旅游，小明需要请小红吃饭，花费为 $q \times x$ 元（ $p,q$ 都是输入的常数）。

请你帮小明写一个程序，计算出假期里他至少需要花费多少元。

inputFormat: 输入只有一行，包含三个空格隔开的正整数 $n,p,q$。

outputFormat: 一行，一个正整数表示小明至少需要花费多少元。


title: 方块消除

description:
Jimmy 最近迷上了一款叫做方块消除的游戏。游戏规则如下：$n$ 个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻方块颜色相同，则这两个方块属于同一区域）。为简化题目，将连起来的同一颜色方块的数目用一个数表示。

例如，`9 122233331` 表示为

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

游戏时，你可以任选一个区域消去。设这个区域包含的方块数为 $x$，则将得到 $x^2$ 个分值。方块消去之后，其余的方块就会竖直落到底部或其他方块上。而且当有一列方块被完全消去时，其右边的所有方块就会向左移一格。Jimmy 希望你能找出得最高分的最佳方案，你能帮助他吗？

inputFormat:
第一行包含一个整数 $m$（$1 \le m \le 50$），表示同颜色方块区域的数目。
第二行包含 $m$ 个数，表示每个区域的颜色（$1$ 到 $m$ 之间的整数）。
第三行包含 $m$ 个数，表示每个区域包含的方块数（$1$ 到 $20$ 之间的整数）。

outputFormat: 仅一个整数，即最高可能得分。


title: Gty的妹子树

background:
我曾在弦歌之中听过你，

檀板声碎，半出折子戏。

舞榭歌台被风吹去，

岁月深处尚有余音一缕……

Gty 神(xian)犇(chong)从来不缺妹子……

他来到了一棵妹子树下，发现每个妹子有一个美丽度……

由于Gty很哲♂学，他只对美丽度大于某个值的妹子感兴趣。

他想知道某个子树中美丽度大于 $k$ 的妹子个数。

某个妹子的美丽度可能发生变化……

树上可能会出现一只新的妹子……

description:
维护一棵初始有 $n$ 个节点的有根树（根节点为 $1$），树上节点编号为 $1 \sim n$，每个点有一个权值 $w_i$。

支持以下操作：

- `0 u x` 询问以 $u$ 为根的子树中，严格大于 $x$ 的值的个数。

- `1 u x`  把 $u$ 节点的权值改成 $x$。

- `2 u x`  添加一个编号为“当前树中节点数+1”的节点，其父节点为 $u$，其权值为 $x$。

**本题强制在线。**
所有输入的 $u,x$ 都需要异或 $\text{last}$ 才是真正的输入。
其中 $\text{last}$ 为上一次询问的答案，定义初始 $\text{last} = 0$。

inputFormat:
第一行一个正整数 $n$，表示初始节点数。

接下来 $n-1$ 行，每行两个整数 $u,v$，为树上的一条无向边。

接下来一行 $n$ 个整数 $w_i$，表示初始时每个节点的权值。

接着一行一个正整数 $m$，表示操作个数。

接下来 $m$ 行，每行三个整数 $\text{op},u,x$，表示一次操作。

outputFormat: 对每个 $\text{op}=0$ 的操作，输出一行，包括一个整数，意义见题目描述。


title: HXY玩卡片

description: HXY得到了一些卡片，这些卡片上标有数字 $0$ 或 $5$ 。现在她可以选择其中一些卡片排成一列，使得排出的一列数字组成的数最大，且满足被 $90$ 整除这个条件。同时，这个数必须为合法的某个非负整数，即不能含有前导 $0$ ，即 $0$ 不能作为这串数的首位。但是特殊地，整数 $0$ 满足条件。如果不能排出这样的数，输出“$-1$”。

inputFormat:
第一行，卡片的个数 $n$ 。

第二行，分别给出了这 $n$ 个数（只能为数字 $5$ 或 $0$ ）。

outputFormat: 仅一行，如果可以排出，则输出这个数。否则输出`-1`。

hint:
数据范围：

对于 $30\%$ 的数据，$n\le 10$ ；

对于 $20\%$ 的数据，仅含数字 $5$ ；

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


title: 小Z的关系距离

description:
小 Z 学习了辩证唯物主义，知道了联系具有普遍性。他看着草稿纸上的字符串，就想挖掘它们之间的关系。

小 Z 认为，对于两个字符串 $a,b$，如果它们各自删除不超过其自身长度一半的字符能够相等，则称 $a,b$ 有距离为 $1$ 的关系。而如果存在另一个字符串 $c$，它和 $a$ 有距离为 $1$ 的关系，和 $b$ 有距离为 $n$ 的关系，则称 $a,b$ 有距离为 $n + 1$ 的关系。

现在小 Z 随机挑选出了两个小写字母字符串 $a,b$，想知道它们之间关系的最小距离，希望你帮帮他。

inputFormat:
第一行包含一个字符串 $a$。

第二行包含一个字符串 $b$。

outputFormat: 第一行包含一个整数，表示 $a,b$ 之间关系的最小距离。

hint:
对于 $30\%$ 的数据，$a,b$ 由同一字母构成。

对于 $100\%$ 的数据，$1 \leq |a|,|b| \leq 100$。


title: HXY和序列

description: HXY 突发奇想，她想要找到一个正整数序列，满足序列中所有的数不超过 $n$，序列长度为 $p$，且除了第一个数外，所有的数都能被前一个数整除（即是前一个数的倍数）。很快她找到了一个这样的序列。可是她觉得还不够，想要知道这样的序列有多少个，可她被惊人的数据范围吓怕了。现在她找到了你，请你来帮助她解决这个问题。（因为结果可能会很大，请输出对 $10^9+7$ 取模后的值）

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

outputFormat: 仅一行，一个正整数，表示满足条件序列的个数对 $10^9+7$ 取模后的值。

hint:
数据范围：

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

对于 $30\%$ 的数据，$1 \leq n,p \leq 10$；

对于 $60\%$ 的数据，$1 \leq n,p \leq 5 \times 10^2$；

对于 $100\%$ 的数据，$1 \leq n,p \leq 2 \times 10^3$。


title: 小Z的掷骰游戏

description:
小 Z 得到了一种奇特的骰子（如下图所示），想要用它进行掷骰游戏。

![](https://cdn.luogu.com.cn/upload/pic/1263.png)

游戏很简单，小 Z 每次都从同样的位置将一个骰子竖直抛下，当骰子落到平面或另一个骰子上时停下来。然而，由于这是一种奇特的骰子，它还会继续翻滚和下落。这种骰子有以下特性：

- 普通骰子可能往四个方向翻滚，而这种骰子只能往 $4,5,6$ 这三个面的方向翻滚。在下图所示的情况中，这种骰子只能往两个方向翻滚；

![](https://cdn.luogu.com.cn/upload/pic/1264.png)

- 这种骰子只有在翻滚后会导致其下落时才会翻滚（如下图所示），当有多个方向可以翻滚时，它会往数字最大的面的方向翻滚；

![](https://cdn.luogu.com.cn/upload/pic/1265.png)

- 这种骰子翻滚恰好 $90^\circ$ 后会竖直下落，当落到平面或另一个骰子上时停下来（如下图中的 $B$ 和 $C$ 所示），然后继续翻滚和下落的过程。

![](https://cdn.luogu.com.cn/upload/pic/1266.png)

上图就是将 $4$ 个骰子均以上面是 $6$ 前面是 $4$ 的状态依次抛下的过程。

现在小 Z 抛了 $n$ 个骰子，他想知道游戏结束后从上面看每个数字分别出现了多少次（如下图所示），希望你帮帮他。

![](https://cdn.luogu.com.cn/upload/pic/1267.png)

inputFormat:
每次多组数据，每组数据格式如下：

第 $1$ 行，一个整数 $n$，表示抛了 $n$ 个骰子；

第 $2\sim n+1$ 行，每行包含两个整数 $t,f$，表示一个骰子以上面是 $t$ 前面是 $f$ 的状态抛下。

outputFormat: 对于每组数据，输出一行，每行包含六个整数，表示游戏结束后从上面看每个数字分别出现的次数。

hint:
本题有 $4$ 个点，每个点 $25$ 分。

对于 $25\%$ 的数据，$n=1$。

对于另外 $25\%$ 的数据，$n=2$。

对于 $100\%$ 的数据，$1 \leq n \leq 100$，不超过 $30$ 组数据。


title: 小Z的电力管制

description:
小 Z 在供电公司找到了一份工作，刚上班就遇到了一个棘手的任务。

小 Z 所在的城市可以看成一个 $n \times m$ 的网格，第 $i$ 行第 $j$ 列的格子有电力需求 $a_{i,j}$ 。然而，供电公司能够供应的电力 $u$ 小于每格的电力需求之和。为此，供电公司不得不将城市划分成若干个区域，每个区域轮流断电，使得断电后剩余区域的电力需求之和不超过供电公司能够供应的电力。

为了方便起见，划分区域的方式很简单，每次将大区域横向或纵向划分成两个小区域，递归进行。

供电公司想尽可能减少市民的不满，因此需要小 Z 计算出最多能划分成多少个区域以及在此前提下能够剩余的最多电力（一种划分的剩余电力为每次断电后剩余电力的最小值），希望你帮帮他。

inputFormat:
第一行包含三个整数 $n ,m ,u$ 。

接下来 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个整数为 $a_{i,j}$，含义见题目描述。

outputFormat: 共一行，包含两个整数，分别表示最多能划分成的区域数和在此前提下能够剩余的最多电力。


title: HXY烧情侣

description:
众所周知，HXY 已经加入了 FFF 团。现在她要开始喜（sang）闻（xin）乐（bing）见（kuang）地烧情侣了。

这里有 $n$ 座电影院，$n$ 对情侣分别在每座电影院里，然后电影院里都有汽油，但是要使用它需要一定的费用。$m$ 条单向通道连接相邻的两对情侣所在电影院。

HXY 有个绝技，如果她能从一个点开始烧，最后回到这个点，那么烧这条回路上的情侣的费用只需要该点的汽油费即可。并且每对情侣只需烧一遍，电影院可以重复去。然后她想花尽可能少的费用烧掉所有的情侣。

问：最少需要多少费用，并且当费用最少时的方案数是多少？由于方案数可能过大，所以请输出方案数对 $10^9+7$ 取模的结果。

（注：这里 HXY 每次可以从任何一个点开始走回路。就是说一个回路走完了，下一个开始位置可以任选。所以说不存在烧不了所有情侣的情况，即使图不连通，HXY 自行选择顶点进行烧情侣行动。且走过的道路可以重复走。）

inputFormat:
第一行一个正整数 $n$。
第二行 $n$ 个正整数，表示每个点的汽油费 $w_i$。
第三行一个正整数 $m$。
接下来 $m$ 行，每行两个正整数 $x_i,y_i$，表示一条 $x_i \to y_i$ 的单向道路。

outputFormat: 输出一行两个整数，分别表示最小花费，和花费最小时的方案数。

hint:
对于 $30\%$ 的数据，$1\le n,m \le 20$；
对于另外 $10\%$ 的数据，保证不存在回路；
对于 $100\%$ 的数据，$1\le n \le 10^5$，$1\le m \le 3\times 10^5$，$0\le w_i \le 10^9$。


title: Gty的超级妹子树【数据疑似有误】

background:
我曾在青山之中遇过你，
新竹做杖，鬓插紫茱萸。
跣足踏过无边丝雨，
又拾起燕川雪片片落如席……

Gty神(xian)犇(chong)从来不缺妹子……

他又来到了一棵妹子树下，发现每个妹子有一个美丽度……

由于Gty很 哲♂学 也很 机♂智，他只对美丽度大于某个值的妹子感兴趣。
他想知道某个子树中美丽度大于 $x$ 的妹子个数。

某个妹子的美丽度可能发生变化……

树上可能会出现一只新的妹子……

但是……树枝可能会断裂，于是，Gty 惊讶地发现，他的面前变成了一片妹子树组成的森林……

description:
维护一棵初始有 $n$ 个节点的有根树（根节点为 $1$），树上节点编号为 $1 \sim n$，每个点有一个权值 $w_i$，它可能会变成森林。

支持以下操作：

- `0 u x` 询问以 $u$ 为根的子树中，严格大于 $x$ 的值的个数。
- `1 u x`  把 $u$ 节点的权值改成 $x$。
- `2 u x`  添加一个编号为“当前树中节点数+1”的节点，其父节点为 $u$，其权值为 $x$。
- `3 u` 删除 $u$ 与其父亲的边，并使 $u$ 变为其所在连通块的根。

**本题强制在线。**

所有输入的 $u,x$ 都需要异或 $\text{last}$ 才是真正的输入。其中 $\text{last}$ 为上一次询问的答案，定义初始 $\text{last} = 0$。

inputFormat:
第一行一个正整数 $n$，表示初始节点数。

接下来 $n-1$ 行，每行两个整数 $u,v$，为树上的一条无向边。

接下来一行 $n$ 个整数 $w_i$，表示初始时每个节点的权值。

接着一行一个正整数 $m$，表示操作个数。

接下来 $m$ 行，每行若干个整数，表示一次操作。


title: [USACO17OPEN] COWBASIC P

description:
Bessie has invented a new programming language, but since there is no compiler yet, she needs your help to actually run her programs.

COWBASIC is a simple, elegant language. It has two key features: addition and MOO loops. Bessie has devised a clever solution to overflow: all addition is done modulo $10^9+7$. But Bessie's real achievement is the MOO loop, which runs a block of code a fixed number of times. MOO loops and addition can, of course, be nested.

Given a COWBASIC program, please help Bessie determine what number it returns.

Bessie研制出了一种新的编程语言，但是因为还没有设计编译器的缘故，她需要你的帮助来运行她编的程序。

COWBASIC语言是一种简单的、优美的语言。它有两个关键功能：变量相加和MOO循环。对于可能的溢出问题，Bessie想出了一个很好的方法，**所有的变量加法都要以10^9+7为模**。但是Bessie设计的COWBASIC语言中真正成功之处是可以运行一段固定数量的代码的MOO循环。**MOO循环和加法是可以嵌套的**。

给你一段COWBASIC程序，请你帮助Bessie确定这个程序段将会返回什么数值。

inputFormat:
You are given a COWBASIC program at most 100 lines long, with each line being at most 350 characters long. A COWBASIC program is a list of statements.

```cpp
<variable> = <expression>

<literal> MOO {
<list of statements>
}

RETURN <variable>
```

```cpp
<literal>

<variable>

( <expression> ) + ( <expression> )
```

There are three types of statements:

There are three types of expressions:

A literal is a positive integer at most 100,000.

A variable is a string of at most 10 lowercase English letters.

It is guaranteed that no variable will be used or RETURNed before it is defined. It is guaranteed that RETURN will happen exactly once, on the last line of the program.

你将会得到一段**最长为100行的COWBASIC程序，每行的长度最长为350个字符**。COWBASIC语言的结构和类型如下所述：

这是COWBASIC语言的三种主要结构：

<变量>=<表达式>          //赋值结构

<数字（循环次数）>MOO{          //循环结构

<一系列的表达式（也就是循环部分）>

}
RETURN <变量>           //输出结构 把return的变量输出就行了

这是COWBASIC语言的三种类型（我是这么理解的）

<数字> 这些数字是**小于100,000正整数**

<变量> 这些变量名字是**一串10个以内的小写英文字母**

(<表达式>)+(<表达式>) //**注意：这是COWBASIC中变量加法的表达方法，详见样例**

我们保证返回的变量是已定义的，**RETURN（输出结构）将只会出现一次且在程序的最后一行**。

outputFormat:
Output a single positive integer, giving the value of the RETURNed variable.

输出返回的变量值（有符号的整形数字）

说明：

samples:
x = 1
10 MOO {
x = ( x ) + ( x )
}
RETURN x

hint:
Scoring

In 20 percent of all test cases - MOO loops are not nested.

In another 20 percent of all test cases - The program only has 1 variable. MOO loops can be nested.

In the remaining test cases, there are no further restrictions.

评分标准

20%数据：MOO循环不嵌套

另外20%数据：程序只有一个变量，MOO循环可嵌套

其他数据没有多余限制（即最长100行，每行最长350字符）

感谢@psk2016  提供的翻译


title: [USACO17OPEN] Bovine Genomics G

description:
Farmer John owns $N$ cows with spots and $N$ cows without spots. Having just completed a course in bovine genetics, he is convinced that the spots on his cows are caused by mutations in the bovine genome.

At great expense, Farmer John sequences the genomes of his cows. Each genome is a string of length $M$ built from the four characters A, C, G, and T. When he lines up the genomes of his cows, he gets a table like the following, shown here

for $N=3$ and $M=8$:

```cpp
Positions: 1 2 3 4 5 6 7 8

Spotty Cow 1: A A T C C C A T
Spotty Cow 2: A C T T G C A A
Spotty Cow 3: G G T C G C A A

Plain Cow 1: A C T C C C A G
Plain Cow 2: A C T C G C A T
Plain Cow 3: A C T T C C A T
```

Looking carefully at this table, he surmises that the sequence from position 2 through position 5 is sufficient to explain spottiness. That is, by looking at the characters in just these these positions (that is, positions $2 \ldots 5$), Farmer John can predict which of his cows are spotty and which are not. For example, if he sees the characters GTCG in these locations, he knows the cow must be spotty.

Please help FJ find the length of the shortest sequence of positions that can explain spottiness.

农夫约翰拥有N头带斑点的奶牛和N头没有斑点的奶牛。他刚刚完成了牛遗传学课程，他确信奶牛上的斑点是由牛基因组突变引起的。

农夫约翰花了大钱对他奶牛的基因组进行测序。每个基因组都是一串长度为M的字符串，由四个字符A，C，G和T构成。当他排列奶牛的基因组时，他得到一张如下表，如下所示

对于N = 3和M = 8：

Positions：1 2 3 4 5 6 7 8

Positions: 1 2 3 4 5 6 7 8

Spotty Cow 1: A A T C C C A T
Spotty Cow 2: A C T T G C A A
Spotty Cow 3: G G T C G C A A

Plain Cow 1: A C T C C C A G
Plain Cow 2: A C T C G C A T
Plain Cow 3: A C T T C C A T
他仔细查看该表，认为从位置2到位置5的顺序足以解释斑点。也就是说，仅通过查看这些位置（即位置2 ……5）中的字符，农夫约翰就可以预测出他的哪些母牛斑点，哪些不是斑点。例如，如果他在这些位置看到字符GTCG，他就知道那头母牛一定是斑点的。

请帮助FJ找到可以解释斑点的最短位置序列的长度。

FJ有一些有斑点和一些没有斑点的牛，他想搞清楚到底什么基因控制这个牛有没有斑点。

于是他找了n有斑点的牛和n头没有斑点的牛

这些牛的基因长度为m（基因中之包含ATCG四个字母）

求这个序列中的一个子串，可以确定是否有斑点。

子串需要符合要求：有斑点的牛这部分的子串，不能和无斑点的牛的这部分子串相同

求最短子串长度

inputFormat:
The first line of input contains $N$ ($1 \leq N \leq 500$) and $M$ ($3 \leq M \leq 500$). The next $N$ lines each contain a string of $M$ characters; these describe the genomes of the spotty cows.

The final $N$ lines describe the genomes of the plain cows. No spotty cow has the same exact  genome as a plain cow.

outputFormat: Please print the length of the shortest sequence of positions that is sufficient to explain spottiness. A sequence of positions explains spottiness if the spottiness trait can be predicted with perfect accuracy among Farmer John's population of cows by looking at just those locations in the genome.

samples:
3 8
AATCCCAT
ACTTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

hint: 感谢@ dzysc 提供题目简述


title: [USACO17OPEN] Modern Art 2 G

background:
小TY的同学HF也想创作艺术

HF只有一块长条状的画布(画条)，所以每一次涂色只能涂上连续几个单位的颜料，同样新的颜料可以完全覆盖旧的颜料

由于他的颜料同样非常傲娇，每次涂完要等上1day才能完全干，只有旧颜料干了以后才能用新颜料覆盖

现在小HF用了2017个年头终于画出了一个大作品，自己非常满意

现在他想复制这份作品

description:
Having become bored with standard 2-dimensional artwork (and also frustrated at others copying her work), the great bovine artist Picowso has decided to switch to a more minimalist, 1-dimensional style.

Although, her paintings can now be described by a 1-dimensional array of colors of length $N$ ($1 \leq N \leq 100,000$), her painting style remains unchanged: she starts with a blank canvas and layers upon it a sequence of "rectangles" of paint, which in this 1-dimensional case are simply intervals. She uses each of the colors $1 \ldots N$ exactly once, although just as before, some colors might end up being completely covered up by the end.

To Picowso's great dismay, her competitor Moonet seems to have figured out how to copy even these 1-dimensional paintings, using a similar strategy to the preceding problem: Moonet will paint a set of disjoint intervals, wait for them to dry, then paint another set of disjoint intervals, and so on. Moonet can only paint at most one interval of each color over the entire process. Please compute

the number of such rounds needed for Moonet to copy a given 1-dimensional Picowso painting.

现在给你一个长度为N(N≤1e5)的画条

上面有若干种颜色，每位的数字表示一种颜色，0表示没有涂色

为了快捷，每次涂色可以用一种颜色填充一个区间，同一种颜色只能使用一次

每次可以涂色好几次，但是这些区间必须分别连续切两两不能相交

然后等待1day油漆干了后再同样操作，输出创作完成并全干了后的最少时间

inputFormat:
The first line of input contains $N$, and the next $N$ lines contain an integer in the range $0 \ldots N$ indicating the color of each cell in the 1-dimensional painting (0 for a blank cell).

第一行为N，画条长度

一下N行每行一个数表示颜色

outputFormat:
Please output the minimum number of rounds needed to copy this painting, or -1 if this could not have possibly been an authentic work of Picowso (i.e., if she could not have painted it using a layered sequence of intervals, one of each color).

输出一个整数表示最少天数。数据若不合法则输出-1

hint:
In this example, the interval of color 1 must be painted in an earlier round than the intervals of colors 4 and 5, so at least two rounds are needed.

样例解释：

第一次可以把1颜色和3颜色填充，变成

0 1 1 1 1 3 3

等待1Day后再填充颜色4和颜色5，变成

0 1 4 5 1 3 3

在等待一Day油漆干了后创作完成

所以答案是2

感谢 @ Night\_Aurora 贡献翻译


title: 高精度减法

description: 高精度减法。

inputFormat: 两个整数 $a,b$（第二个可能比第一个大）。

outputFormat: 结果（是负数要输出负号）。


title: [USACO11DEC] RoadBlock S / [USACO14FEB]Roadblock G/S

description:
每天早晨，FJ 从家中穿过农场走到牛棚。农场由 $N$ 块农田组成，农田通过 $M$ 条双向道路连接，每条路有一定长度。FJ 的房子在 $1$ 号田，牛棚在 $N$ 号田。没有两块田被多条道路连接，以适当的路径顺序总是能在农场任意一对田间行走。当 FJ 从一块田走到另一块时，总是以总路长最短的道路顺序来走。

FJ 的牛呢，总是不安好心，决定干扰他每天早晨的计划。它们在 $M$ 条路的某一条上安放一叠稻草堆，使这条路的长度加倍。牛希望选择一条路干扰使得 FJ 从家到牛棚的路长增加最多。它们请你设计并告诉它们最大增量是多少。

inputFormat:
第 $1$ 行：两个整数 $N, M$。

第 $2$ 到 $M+1$ 行：第 $i+1$ 行包含三个整数 $A_i, B_i, L_i$，$A_i$ 和 $B_i$ 表示道路 $i$ 连接的田的编号，$L_i$ 表示路长。

outputFormat: 一个整数，表示通过使某条路加倍而得到的最大增量。

hint:
【样例说明】

若使 $3$ 和 $4$ 之间的道路长加倍，最短路将由 $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ 变为 $1 \rightarrow 3 \rightarrow 5$。

【数据规模和约定】

对于 $30\%$ 的数据，$N \le 70，M \le 1500$。

对于 $100\%$ 的数据，$1 \le N \le 100，1 \le M \le 5,000，1 \le L_i \le 1,000,000$。


title: 小Z的游戏分队

description:
小 Z 受不了寂寞，准备举办一次 DOTA 比赛，为了能让 ACM 班全部都参加比赛，他还特制了一张 DOTA 地图能够支持任意多人打任意多人。

现在问题来了，怎么把这么多人分成两队？小 Z 的想法是，每个人报上自己愿意同队的同学，接着小 Z 会按如下要求将所有人分为两队：

对任意同学甲，和同学甲同队的人，必须都是同学甲愿意同队的同学。

小 Z 希望两队的人数差尽量小，如果这种分组不存在，那么输出 `No solution`。

inputFormat:
第 $1$ 行为 $N$，表示一共有多少个学生。

之后 $2$ 到 $N+1$ 行，每行表示这个学生信任的同学的名单，以 $0$ 结束。

outputFormat: $1$ 行，如果解存在，输出两队的人数，将人数比较小的那队放在前面；如果解不存在，输出 `No solution`。


title: 小Z的神奇数列

background: 小Z最近在研究数列，他需要知道在他所研究的数列中，最大的数是多少（Max），最小的数是多少（Min），最大的数的最小的数次幂是多少（Max^Min），所有数的乘积是多少。要知道，这样的问题是肯定难不倒小Z的。但是，最近小Z突发奇想，想要研究下这个数列的更深层的性质，所以他决定不断的从这个数列中删去一些数，每次删除后都研究下当前数列。由于数列项数很大，这给小Z带来了很大的麻烦，于是小Z请你帮他写一个程序，来完成下列操作。

description:
你需要维护一个可重集，支持五种操作：

- `D x` 表示删除 $x$，保证 $x$ 一定存在。若有多个只用删除一个。

- `B` 询问集合中最大值。

- `S` 询问集合中最小值。

- `M` 设集合中最大值为 $a$，最小值为 $b$，询问 $a^b \bmod 317847191$。

- `T` 询问数列中所有数的乘积，对 $317847191$ 取模。

对于所有询问保证集合非空。

inputFormat:
第一行两个正整数 $n,m$，表示初始集合大小和操作数。
第二行 $n$ 个正整数 $a_i$，表示初始集合。
接下来 $m$ 行，每行表示一个操作。

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


title: [ZJOI2012] 网络

description:
有一个无向图 $G$，每个点有个权值，每条边有一个颜色。这个无向图满足以下两个条件：

1、 对于任意节点连出去的边中，相同颜色的边不超过两条。

2、图中不存在同色的环，同色的环指相同颜色的边构成的环。

在这个图上，你要支持以下三种操作：

- `0 x y` 表示把节点 $x$ 的权值改为 $y$

- `1 u v w` 表示将边 $(u,v)$ 的颜色改为 $w$。

- `2 c u v` 表示查询由颜色 $c$ 的边构成的图中，所有可能在 $u \to v$ 之间的简单路径上的节点的权值的最大值。

inputFormat:
第一行四个正整数 $n,m,C,k$，分别表示节点数、边数、颜色数和操作数。

接下来 $n$ 行，每行一个正整数 $v_i$，为节点 $i$ 的权值。

之后 $m$ 行，每行三个正整数 $u,v,w$，为一条连接 $u,v$ 节点的边，颜色为$w$。

最后 $k$ 行，每行若干个正整数，表示一次操作。

outputFormat:
输出若干行，每行输出一个对应的信息。

1、 对于修改节点权值操作，不需要输出信息。

2、对于修改边的颜色操作，按以下几类输出：

- 若不存在连接节点 $u$ 和节点 $v$ 的边，输出 `No such edge.`。

- 若修改后不满足条件 $1$，不修改边的颜色，并输出 `Error 1.`。

- 若修改后不满足条件 $2$，不修改边的颜色，并输出 `Error 2.`。

- 其他情况，成功修改边的颜色，并输出 `Success.`。

输出满足条件的第一条信息即可，即若同时不满足条件 $1,2$ ，则只需要输出`Error 1.`。

3、 对于查询操作，输出一个整数表示答案。若 $u,v$ 之间没有颜色 $c$ 构成的路径，则输出 $-1$。

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

颜色 $0$ 为实线的边，颜色 $1$ 为虚线的边，

由颜色 $0$ 构成的从节点 $1$ 到节点 $4$ 的路径有 $1 \to 2 \to 4$，故$\max\{v_1, v_2, v_4\} = \max\{ 1, 2, 4 \} = 4$。

将连接节点 $1$ 和节点 $2$ 的边修改为颜色 $1$，修改成功，输出 `Success.`

将连接节点 $4$ 和节点 $3$ 的边修改为颜色 $1$，由于修改后会使得存在由颜色 $1$ 构成的环( $1 – 2 – 4 – 3 – 1$ )，不满足条件 $2$，故不修改，并输`Error 2`。

不存在颜色 $0$ 构成的从节点 $1$ 到节点 $4$ 的边，输出 `-1`。

将连接节点 $2$ 和节点 $3$ 的边修改为颜色 $1$，由于修改后节点 $2$ 的连出去的颜色为 $1$ 的边有 $3$ 条，故不满足条件 $1$，故不修改，并输出`Error 1.` 。

将节点 $2$ 的权值修改为 $5$。

由颜色 $1$ 构成的从节点 $1$ 到节点 $4$ 的路径有 $1 \to 2 \to 4$，故$\max\{v_1, v_2, v_4\} = \max\{ 1, 5, 4 \} = 5$。

【数据范围】

对于 $30\%$ 的数据：$n ≤ 1000$，$m ≤ 10^4$，$k ≤ 1000$；
另有 $20\%$ 的数据：$n ≤ 10^4$，$m ≤ 10^5$，$C = 1$，$k ≤ 10^5$；
对于 $100\%$ 的数据：$n ≤ 10^4$，$m ≤ 10^5$，$C ≤ 10$，$k ≤ 10^5$。

$1\le u,v,x \le n$，$0 \le c < C$，保证图中没有重边和自环。


title: [USACO17OPEN] Paired Up S

description:
Farmer John finds that his cows are each easier to milk when they have another cow nearby for moral support. He therefore wants to take his $M$ cows ($M \leq 1,000,000,000$, $M$ even) and partition them into $M/2$ pairs. Each pair of cows will then be ushered off to a separate stall in the barn for milking. The milking in each of these $M/2$ stalls will take place simultaneously.

To make matters a bit complicated, each of Farmer John's cows has a different milk output. If cows of milk outputs $A$ and $B$ are paired up, then it takes a total of $A+B$ units of time to milk them both.

Please help Farmer John determine the minimum possible amount of time the entire milking process will take to complete, assuming he pairs the cows up in the best possible way.

有M(M为偶数)头奶牛，每头奶牛有一个产奶量，将这些奶牛两两配对，每对奶牛的产奶的时间为两头奶牛产奶量的总和。现在这M/2对奶牛同时产奶，问所需的最短时间是多少 M保证为偶数

inputFormat:
The first line of input contains $N$ ($1 \leq N \leq 100,000$).

Each of the next $N$ lines contains two integers $x$ and $y$, indicating that FJ has $x$ cows each with milk output $y$ ($1 \leq y \leq 1,000,000,000$). The sum of the $x$'s is $M$, the total number of cows.

第一行为一个正整数N

接下来有N行，每行两个正整数x和y，表示有x头奶牛的产奶量为y。保证所有x的总和等于M

outputFormat:
Print out the minimum amount of time it takes FJ's cows to be milked, assuming they are optimally paired up.

输出产奶时间的最小值

hint:
Here, if the cows with outputs 8+2 are paired up, and those with outputs 5+5 are

paired up, the both stalls take 10 units of time for milking. Since milking

takes place simultaneously, the entire process would therefore complete after 10

units of time. Any other pairing would be sub-optimal, resulting in a stall taking more than 10

units of time to milk.

奶牛的产奶量分别为8,5,5,2。

让8和2配对，5和5配对，则产奶时间分别为10,10，所以这两对奶牛同时产奶的时间为10.

感谢 @ x咫尺天涯x 的翻译


title: [NOI2012] 骑行川藏

description:
蛋蛋非常热衷于挑战自我，今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。

川藏线的沿途有着非常美丽的风景，但在这一路上也有着很多的艰难险阻，路况变化多端，而蛋蛋的体力十分有限,因此在每天的骑行前设定好目的地，同时合理分配好自己的体力是一件非常重要的事情。

由于蛋蛋装备了一辆非常好的自行车，因此在骑行过程中可以认为他仅在克服风阻做功（不受自行车本身摩擦力以及自行车与地面的摩擦力影响）。

某一天他打算骑 $n$ 段路，每一段内的路况可视为相同：对于第 $i$ 段路,我们给出有关这段路况的 $3$ 个参数 $s_i,k_i,v_i'$，其中 $s_i$ 表示这段路的长度，$k_i$ 表示这段路的风阻系数，$v_i'$ 表示这段路上的风速（$v_i'\gt 0$ 表示在这段路上他遇到了顺风，反之则意味着他将受逆风影响）。

若某一时刻在这段路上骑车速度为 $v$，则他受到的风阻
大小为 $F=k_i(v-v_i')^2$（这样若在长度为 $s$ 的路程内保持骑行速度 $v$ 不变,则他消耗能量（做功）$E=k_i(v-v_i')^2s$ ）。

设蛋蛋在这天开始时的体能值是 $E_U$，请帮助他设计一种行车方案,使他在有限的体力内用最短的时间到达目的地。请告诉他最短的时间 $T$ 是多少。

inputFormat:
第一行包含一个正整数 $n$ 和一个实数 $E_U$，分别表示路段的数量以及蛋蛋的体能值。

接下来 $n$ 行分别描述 $n$ 个路段，每行有 $3$ 个实数 $s_i,k_i,v_i'$ 分别表示第 $i$ 段路的长度，风阻系数以及风速。

outputFormat: 输出一个实数 $T$，表示蛋蛋到达目的地消耗的最短时间，要求至少保留到小数点后 $6$ 位。

hint:
### 样例说明

一种可能的方案是：蛋蛋在三段路上都采用匀速骑行的方式,其速度依次为 $5.12939919,8.03515481,6.17837967$。

### 评分方法

本题没有部分分,你程序的输出只有和标准答案的差距不超过 $10^{-6}$ 时，才能获得该测试点的满分，否则不得分。

### 数据规模与约定

对于 $10\%$  的数据，$n=1$。

对于 $40\%$  的数据，$n\le2$。

对于 $60\%$  的数据，$n\le100$。

对于 $80\%$  的数据，$n\le 1000$。

对于 $100\%$  的数据，$n\le 10^4$，$E_U\le 10^8$，$s_i\in[0,10^5]$，$k_i\in(0,15]$，$v_i'\in(-100,100)$。

数据保证最终的答案不会超过 $10^5$。

### 提示

必然存在一种最优的体力方案满足：蛋蛋在每段路上都采用匀速骑行的方式。


title: 摆石子

background: 我们伟大的KK突然想到了一个很高（Shā）明（bī）的问题。

description: 我们伟大的KK在N条水平线与M条竖直线构成的网格中（KK的自创坐标系），放K枚石子，每个石子都只能放在网格的交叉点上。现在KK想知道在最优的摆放方式下，最多可以找到多少四边平行于坐标轴的长方形，而且KK要求它的四个角上都恰好放着一枚石子。

inputFormat: 一行输入三个正整数 N，M，K。

outputFormat: 一行输出一个正整数，表示最多的满足条件的长方形数量。

hint:
50%的数据    0<N，M≤30；

100%的数据   0<N，M≤30000  K≤N\*M。


title: [USACO17OPEN] Bovine Genomics S

description:
Farmer John owns $N$ cows with spots and $N$ cows without spots. Having just completed a course in bovine genetics, he is convinced that the spots on his cows are caused by mutations in the bovine genome.

At great expense, Farmer John sequences the genomes of his cows. Each genome is a string of length $M$ built from the four characters A, C, G, and T. When he lines up the genomes of his cows, he gets a table like the following, shown here

for $N=3$:

```cpp
Positions: 1 2 3 4 5 6 7 ... M

Spotty Cow 1: A A T C C C A ... T
Spotty Cow 2: G A T T G C A ... A
Spotty Cow 3: G G T C G C A ... A

Plain Cow 1: A C T C C C A ... G
Plain Cow 2: A G T T G C A ... T
Plain Cow 3: A G T T C C A ... T
```

Looking carefully at this table, he surmises that positions 2 and 4 are sufficient to explain spottiness. That is, by looking at the characters in just these two positions, Farmer John can predict which of his cows are spotty and which are not (for example, if he sees G and C, the cow must be spotty).

Farmer John is convinced that spottiness can be explained not by just one or two positions in the genome, but by looking at a set of three distinct positions.  Please help him count the number of sets of three distinct positions that can each explain spottiness.

FJ 有 $n$ 头有斑点的牛和 $n$ 头没有斑点的牛。由于他刚刚学完牛的基因学的课程，他想知道牛有没有斑点是否与牛的基因有关。

FJ花了巨大的代价测出了每个牛的基因，每头牛的基因用一个长度为 $M$ 的由 `A,C,G,T` 的串构成。FJ将这

些串写成一个表/矩阵，就像图中这样。

$N=3$ 的例子：

```cpp
Positions: 1 2 3 4 5 6 7 ... M

Spotty Cow 1: A A T C C C A ... T
Spotty Cow 2: G A T T G C A ... A
Spotty Cow 3: G G T C G C A ... A

Plain Cow 1: A C T C C C A ... G
Plain Cow 2: A G T T G C A ... T
Plain Cow 3: A G T T C C A ... T
``````cpp
Positions: 1 2 3 4 5 6 7 ... M

Spotty Cow 1: A A T C C C A ... T
Spotty Cow 2: G A T T G C A ... A
Spotty Cow 3: G G T C G C A ... A

Plain Cow 1: A C T C C C A ... G
Plain Cow 2: A G T T G C A ... T
Plain Cow 3: A G T T C C A ... T
```

FJ 仔细的观察这个表，他发现通过观测 $2,4$ 位置的字符串可以预测牛是否有斑点。

（在这个例子中，假如他看到 24 位置是 GC、AT 或者 AC 就可以断定其有斑点，因为1号有斑点的牛 24 位置基因为 AC，2 号为 AT，3 号为 GC，而且没有任何一头无斑点的牛的 24 位置出现过这三个串）

 FJ 认为，1 个或者两个位点是不能够区分品种的，必须是刚好 3 个位点。他想知道能用多少组三个本质不同的位置判断牛的斑点，$\{1,2,3\}$ 和 $\{1,3,2\}$是本质相同的

inputFormat: The first line of input contains $N$ ($1 \leq N \leq 500$) and $M$ ($3 \leq M \leq 50$). The next $N$ lines each contain a string of $M$ characters; these describe the genomes of the spotty cows. The final $N$ lines describe the genomes of the plain cows.

outputFormat: Please count the number of sets of three distinct positions that can explain spottiness. A set of three positions explains spottiness if the spottiness trait can be predicted with perfect accuracy among Farmer John's population of cows by looking at just those three locations in the genome.

samples:
3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

hint: 感谢@ 秘密观测者 的提供翻译


title: [NOI2015] 品酒大会

description:
一年一度的“幻影阁夏日品酒大会”隆重开幕了。大会包含品尝和趣味挑战 两个环节，分别向优胜者颁发“首席品酒家”和“首席猎手”两个奖项，吸引了众多品酒师参加。

在大会的晚餐上，调酒师 Rainbow 调制了 $n$ 杯鸡尾酒。这 $n$ 杯鸡尾酒排成一行，其中第 $n$ 杯酒 ($1 ≤ i ≤ n$) 被贴上了一个标签 $s_i$ ，每个标签都是 $26$ 个小写 英文字母之一。设 $str(l, r)$ 表示第 $l$ 杯酒到第 $r$ 杯酒的 $r - l + 1$ 个标签顺次连接构成的字符串。若 $str(p, p_0) = str(q, q_0)$，其中 $1 ≤ p ≤ p_0 ≤ n$, $1 ≤ q ≤ q_0 ≤ n$, $p ≠ q$，$p_0-p+1 = q_0 - q + 1 = r$ ，则称第 $p$ 杯酒与第 $q$ 杯酒是“ $r$ 相似” 的。当然两杯“ $r$ 相似”($r > 1$)的酒同时也是“ $1$ 相似”、“ $2$ 相似”、……、“ $(r - 1)$ 相似”的。特别地，对于任意的 $1 ≤ p ,q ≤ n,p  ≠  q$，第 $p$ 杯酒和第 $q$ 杯酒都 是“ $0$ 相似”的。

在品尝环节上，品酒师 Freda 轻松地评定了每一杯酒的美味度，凭借其专业的水准和经验成功夺取了“首席品酒家”的称号，其中第 $i$ 杯酒 ($1 ≤ i ≤ n$) 的 美味度为 $a_i$ 。现在 Rainbow 公布了挑战环节的问题：本次大会调制的鸡尾酒有一个特点，如果把第 $p$ 杯酒与第 $q$ 杯酒调兑在一起，将得到一杯美味度为 $a_p\times a_q$ 的 酒。现在请各位品酒师分别对于 $r = 0,1,2,⋯,n-1$ ，统计出有多少种方法可以 选出 $2$ 杯“ $r$ 相似”的酒，并回答选择 $2$ 杯“$r$ 相似”的酒调兑可以得到的美味度的最大值。

inputFormat:
第 $1$ 行包含 $1$ 个正整数 $n$ ，表示鸡尾酒的杯数。

第 $2$ 行包含一个长度为 $n$ 的字符串 $S$，其中第 $i$ 个字符表示第 $i$ 杯酒的标签。

第 $3$ 行包含 $n$ 个整数，相邻整数之间用单个空格隔开，其中第 $i$ 个整数表示第 $i$ 杯酒的美味度 $a_i$ 。

outputFormat:
包括 $n$ 行。

第 $i$ 行输出 $2$ 个整数，中间用单个空格隔开。第 $1$ 个整 数表示选出两杯“ $(i - 1)$ 相似”的酒的方案数，第 2 个整数表示选出两杯 “ $(i - 1)$ 相似”的酒调兑可以得到的最大美味度。若不存在两杯“ $(i - 1)$ 相似” 的酒，这两个数均为 $0$ 。


title: 内存杀手

background: 我们伟大的KK突然想到了一个很高（Shā）明（bī）的问题。

description:
我们伟大的 KK 最近一段时间突然迷上了电影，但是他从来不去电影院，因为他口袋里没有一分钱，更因为没人陪他去！但是 KK 不是这么容易就会屈服于命远的，他从爸爸那里“偷”来了电脑，没日没夜的进入了疯狂刷电影状态。

显然我们的 KK 在任何情况下都会出现问题的：KK 习惯于用“百度影音”这个神奇的软件。众所周知，这个软件具备一个牛犇的功能，他可以一边看一边下载，然后，KK 每次都不会在线观看，而是连着 wifi（哇\~\~还说没钱！）看，然后的然后KK发现电脑开始变得卡起来了，为了在爸爸突击检查时能够准确准时的将电脑关闭归位，KK 不得不干起了电脑修理师的工作。

KK 翻查了注册表（这都懂？！牛~），发现罪魁祸首竟是存在于一个内存区域中的一个正方形方阵。现在我们的 KK 简单的称呼这种方阵为“内存杀手”，他对于这个“内存杀手”的定义是边长大于 $1$，且在旋转了 $180\degree$ 之后方阵仍与原来保持不变，如：

$$
\begin{bmatrix}
0 & 0 \\
0 & 0
\end{bmatrix},
\begin{bmatrix}
1 & 0 \\
0 & 1
\end{bmatrix},
\begin{bmatrix}
1 & 0 & 1 \\
1 & 1 & 1 \\
1 & 0 & 1
\end{bmatrix}
$$

当然，一个内存区域中“内存杀手”可能不止一个的，现在我们的 KK 想找出这个方阵中最大的“内存杀手”的边长。

inputFormat: 共 $N+1$ 行，第一行两个整数 $N,M$，表示内存矩阵的大小。第 $2 \sim N+1$ 行，每行 $M$ 个字符表示内存矩阵。

outputFormat: 共一行，即最大的内存杀手边长；若不存在，则输出 $-1$。


title: HXY造公园

description:
现在有一个现成的公园，有 $n$ 个休息点和 $m$ 条双向边连接两个休息点。众所周知，HXY 是一个 SXBK 的强迫症患者，所以她打算施展魔法来改造公园并即时了解改造情况。她可以进行以下两种操作：

1. 对某个休息点 $x$，查询公园中可以与该点互相到达的休息点组成的路径中的最长路径。
2. 对于两个休息点 $x,y$，如果 $x,y$ 已经可以互相到达则忽略此次操作。否则，在 $x$ 可到达的所有休息点和 $y$ 可到达的所有休息点（包括 $x,y$ 自身）分别选择一个休息点，然后在这两个休息点之间连一条边，并且这个选择应该满足对于连接后的公园，$x$ 和 $y$ 所在的区域（即 $x,y$ 可达到的所有休息点和边组成的集合）中的最长路径的长度最小。

HXY打算进行 $q$ 个操作，请你回答她的对于公园情况的询问（操作 1）或者执行她的操作（操作 2）。

注：所有边的长度皆为 $1$。保证不存在环。最长路径定义为：对于点 $v_1,v_2\cdots v_k$，如果对于其中任意的 $v_i$ 和 $v_{i+1}\quad (1\le i\le k-1)$，都有边相连接，那么 $v_j\quad(1\le j\le k)$ 所在区域的最长路径就是 $k-1$。

inputFormat:
- 第一行，三个正整数，分别为 $n,m,q$。
- 接下来的 $m$ 行，每一行有两个正整数 $x_i,y_i$，表示 $x_i$ 和 $y_i$ 有一条双向边相连。
- 再接下来的 $q$ 行，每一行表示一个操作。
  - 若该行第一个数为 $1$，则表示操作 1，之后还有一个正整数 $x_i$，表示要查询的休息点。
  - 若该行第一个数为 $2$，则表示操作 2，之后还有两个正整数 $x_i,y_i$，表示需要执行操作的两个休息点。

outputFormat:
输出行数为操作 1 的个数。

每行输出对于操作 1 询问的回答。


title: 对角线

description:
对于一个 $n$ 个顶点的凸多边形，它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。

例如，$6$ 边形：

![](https://cdn.luogu.com.cn/upload/pic/6023.png)

inputFormat: 输入只有一行一个整数 $n$，代表边数。

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

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

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


title: [USACO17OPEN] Where's Bessie? S

background:
农夫John正在测试一个他新发明的全自动寻找奶牛无人机，它能够照一张农场的图片然后自动找出奶牛的位置。

不幸的是，这个相机并不包含一个优秀的寻找奶牛函数，所以农夫John需要你来写一个。

农场的俯瞰图被定义为一个n \* n的字符矩阵。矩阵由大写字母A到Z组成，每个字母表示一种可行

的颜色。农夫John发现一个可能是奶牛的位置（以下简称PCL）的最好定义如下：

一个PCL是一个矩阵（可能是整张图），矩阵的边与图像的边缘平行，且不能被其他PCL所包含（因此PCL内部不可能有PCL）

更多的，一个PCL必须满足以下特性：

1、矩阵有且只能有2种颜色构成。

2、这两种颜色一种构成一个连通块，另一种形成两个或两个以上的连通块。

举个例子：

AAAAA ABABA AAABB 这个矩阵就是一个PCL，其中颜色A构成一个连通块，B构成两个连通块，描述了一只可能以A为底色，B为花纹的奶牛。

在这里连通块被定义为：从其中的任何一个点，你能仅通过上下左右移动，到达另外任何一个点

（即上下左右相邻）

给定农场的照片，请你计算图中有几个PCL。

输入格式：

第一行包含一个正整数N，表示矩阵的边长。

接下来的N行每行N个字符，描述了这个矩阵的颜色。

输出格式：

输出PCL的个数

说明：

在这个样例里，两个PCL分别是：

(如下)

description:
Always known for being quite tech-savy, Farmer John is testing out his new automated drone-mounted cow locator camera, which supposedly can take a picture of his field and automatically figure out the location of cows. Unfortunately, the camera does not include a very good algorithm for finding cows, so FJ needs your help developing a better one.

The overhead image of his farm taken by the camera is described by an $N \times N$ grid of characters, each in the range $A \ldots Z$, representing one of 26 possible colors. Farmer John figures the best way to define a potential cow location (PCL) is as follows: A PCL is a rectangular sub-grid (possibly the entire image) with sides parallel to the image sides, not contained within any other PCL (so no smaller subset of a PCL is also a PCL).  Furthermore, a PCL must satisfy the following property: focusing on just the contents of the rectangle and ignoring the rest of the image, exactly two colors must be present, one forming a contiguous region and one forming two or more contiguous regions.

```cpp
AAAAA
ABABA
AAABB
```

For example, a rectangle with contents

would constitute a PCL, since the A's form a single contiguous region and the B's form more than one contiguous region. The interpretation is a cow of color A with spots of color B.

A region is "contiguous" if you can traverse the entire region by moving repeatedly from one cell in the region to another cell in the region taking steps up, down, left, or right.

Given the image returned by FJ's camera, please count the number of PCLs.

inputFormat:
The first line of input contains $N$, the size of the grid ($1 \leq N \leq 20$).

The next $N$ lines describe the image, each consisting of $N$ characters.

outputFormat: Print a count of the number of PCLs in the image.

hint:
In this example, the two PCLs are the rectangles with contents

```cpp
ABB
BBB
AAB
ABB

and

BC
BC
BB
BC
``


title: [JSOI2010] 巨额奖金

description:
 NJ 市的快速发展得益于其便捷的交通。可是，随着经济的发展，大量的人进入 NJ 市， NJ 市的交通也承受着巨大的压力。现在， NJ 市正在筹划建设一个新型的交通枢纽，从而减轻交通的压力。

 NJ 市包含 $n$ 个区，有些区之间有双向的干道存在。新型交通枢纽建设在这些干道的基础上，将其中的部分干道改进为新型干道。改进后，干道能承受的压力可以比原来增加几十倍。为了和谐发展，在新型的交通枢纽建成后，要求任何两个区之间都可以只通过新型干道（直接或间接地）连接。政府已经预测出每条干道改进为新型干道的费用。政府希望建设新型交通枢纽的总费用最小，并以巨额奖金向市民征集方案。政府很快发现费用最小的方案不一定唯一，所以决定将奖金平分给每一种方案的第一个设计者，即如果一个人设计的费用是最小的而且前面没人和他设计出一模一样的方案，则他可获奖。

 Js08 被奖金深深的吸引，准备设计一种方案。可是，他发现方案可能会很多，如果最后获奖者太多，巨额的资金分到每个人头上的也不会太多。所以他决定先算一下可行的方案数是多少。

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

输入的第一行包含两个数 $n, m$，分别表示该市有多少个区和有多少条干道。

接下来 $m$ 行，每行三个数 $a_i$、$b_i$、$c_i$，表示 $a_i$ 区和 $b_i$ 区之间有一条干道，如果改进需要 $c_i$ 的费用。

outputFormat: 输出费用最小的方案有多少种。由于答案可能很大，你只要输出方案数除以 $31011$ 的模即可。

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

对于 $100\%$ 的数据，保证 $1 \leq n \leq 100$，$1 \leq m \leq 1000$，$1 \leq a _ i, b _ i \leq n$，$1 \leq c _ i \leq 10 ^ 9$。


title: [FJOI2007] 轮状病毒

description:
轮状病毒有很多变种。许多轮状病毒都是由一个轮状基产生。一个 $n$ 轮状基由圆环上 $n$ 个不同的基原子和圆心的一个核原子构成。$2$ 个原子之间的边表示这 $2$ 个原子之间的信息通道，如图 1 所示。

$n$ 轮状病毒的产生规律是在 $n$ 轮状基中删除若干边，使各原子之间有唯一一条信息通道。例如，共有 $16$ 个不同的 $3$ 轮状病毒，如图 2 所示。

给定 $n\ (n\le100)$，编程计算有多少个不同的 $n$ 轮状病毒。

![](https://cdn.luogu.com.cn/upload/pic/1408.png)

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

outputFormat: 共 $1$ 行，表示不同的 $n$ 轮状病毒数。


title: [JSOI2007] 祖玛

background: 管理员备注：本题可能是错题。

description:
这是一个流行在 Jsoi 的游戏，名称为祖玛。

精致细腻的背景，外加神秘的印加音乐衬托，彷佛置身在古老的国度里面，进行一个神秘的游戏——这就是著名的祖玛游戏。祖玛游戏的主角是一只石青蛙，石青蛙会吐出各种颜色的珠子，珠子造型美丽，并且有着神秘的色彩。

环绕着石青蛙的是载着珠子的轨道，各种颜色的珠子会沿着轨道往前滑动，石青蛙必需遏止珠子们滚进去轨道终点的洞里头，如何减少珠子呢？就得要靠石青蛙吐出的珠子与轨道上的珠子相结合，颜色相同者即可以消失得分！直到轨道上的珠子通通都被清干净为止。 或许你并不了解祖玛游戏。没关系。这里我们介绍一个简单版本的祖玛游戏规则。一条通道中有一些玻璃珠，每个珠子有各自的颜色，如图 1 所示。玩家可以做的是选择一种颜色的珠子（注意：颜色可以任选，这与真实游戏是不同的）射入某个位置。

 ![](https://cdn.luogu.com.cn/upload/pic/1446.png)

图 2 中玩家选择一颗蓝色珠子，射入图示的位置，于是得到一个图 3 的局面。

当玩家射入一颗珠子后，如果射入的珠子与其他珠子组成了三颗以上连续相同颜色的珠子，这些珠子就会消失。例如，将一颗白色珠子射入图 4 中的位置，就会产生三颗颜色相同的白色珠子。这三颗珠子就会消失，于是得到图 5 的局面。

需要注意的一点是，图 4 中的三颗连续的黄色珠子不会消失，因为并没有珠子射入其中。 珠子的消失还会产生连锁反应。当一串连续相同颜色的珠子消失后，如果消失位置左右的珠子颜色相同，并且长度大于 2，则可以继续消失。例如，图 6 中，射入一颗红色珠子后，产生了三颗连续的红色珠子。当红色珠子消失后，它左右都是白色的珠子，并且一共有四颗，于是白色珠子也消失了。之后，消失位置的左右都是蓝色珠子，共有三颗，于是蓝色珠子也消失。最终得到图 7 的状态。注意，图 7 中的三颗黄色珠子不会消失，因为蓝色珠子消失的位置一边是紫色珠子，另一边是黄色珠子，颜色不同。

除了上述的情况，没有其他的方法可以消去珠子。现在，我们有一排珠子，需要你去消除。对于每一轮，你可以自由选择不同颜色的珠子，射入任意的位置。你的任务是射出最少的珠子，将全部珠子消去。

inputFormat: 第一行一个整数 $n(n \le 500)$，表示珠子的个数 第二行 $n$ 个整数（32 位整数范围内），用空格分割，每个整数表示一种颜色的珠子。

outputFormat: 一个整数，表示最少需要射出的珠子个数。


title: [NOI2015] 软件包管理器

background: Linux 用户和 OSX 用户一定对软件包管理器不会陌生。通过软件包管理器，你可以通过一行命令安装某一个软件包，然后软件包管理器会帮助你从软件源下载软件包，同时自动解决所有的依赖（即下载安装这个软件包的安装所依赖的其它软件包），完成所有的配置。Debian/Ubuntu 使用的 apt-get，Fedora/CentOS 使用的 yum，以及 OSX 下可用的 homebrew 都是优秀的软件包管理器。

description:
你决定设计你自己的软件包管理器。不可避免地，你要解决软件包之间的依赖问题。如果软件包 $a$ 依赖软件包 $b$，那么安装软件包 $a$ 以前，必须先安装软件包 $b$。同时，如果想要卸载软件包 $b$，则必须卸载软件包 $a$。

现在你已经获得了所有的软件包之间的依赖关系。而且，由于你之前的工作，除 $0$ 号软件包以外，在你的管理器当中的软件包都会依赖一个且仅一个软件包，而 $0$ 号软件包不依赖任何一个软件包。且依赖关系不存在环（即不会存在 $m$ 个软件包 $a_1,a_2, \dots , a_m$，对于 $i<m$，$a_i$ 依赖 $a_{i+1}$，而 $a_m$ 依赖 $a_1$ 的情况）。

现在你要为你的软件包管理器写一个依赖解决程序。根据反馈，用户希望在安装和卸载某个软件包时，快速地知道这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包），你的任务就是实现这个部分。

注意，安装一个已安装的软件包，或卸载一个未安装的软件包，都不会改变任何软件包的安装状态，即在此情况下，改变安装状态的软件包数为 $0$。

inputFormat:
第一行一个正整数 $n$，表示软件包个数，从 $0$ 开始编号。
第二行有 $n-1$ 个整数，第 $i$ 个表示 $i$ 号软件包依赖的软件包编号。
然后一行一个正整数 $q$，表示操作个数，格式如下：

- `install x` 表示安装 $x$ 号软件包
- `uninstall x` 表示卸载 $x$ 号软件包

一开始所有软件包都是未安装的。

对于每个操作，你需要输出这步操作会改变多少个软件包的安装状态，随后应用这个操作（即改变你维护的安装状态）。

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

samples:
7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

samples:
10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

hint:
![](https://cdn.luogu.com.cn/upload/pic/1504.png)
一开始所有软件包都处于未安装状态。

安装 $5$ 号软件包，需要安装 $0,1,5$ 三个软件包。

之后安装 $6$ 号软件包，只需要安装 $6$ 号软件包。此时安装了 $0,1,5,6$ 四个软件包。

卸载 $1$ 号软件包需要卸载 $1,5,6$ 三个软件包。此时只有 $0$ 号软件包还处于安装状态。

之后安装 $4$ 号软件包，需要安装 $1,4$ 两个软件包。此时 $0,1,4$ 处在安装状态。最后，卸载 $0$ 号软件包会卸载所有的软件包。

【数据范围】
![](https://cdn.luogu.com.cn/upload/pic/1505.png)


title: [SDOI2008] 洞穴勘测

description:
辉辉热衷于洞穴勘测。

某天，他按照地图来到了一片被标记为JSZX的洞穴群地区。经过初步勘测，辉辉发现这片区域由n个洞穴（分别编号为1到n）以及若干通道组成，并且每条通道连接了恰好两个洞穴。假如两个洞穴可以通过一条或者多条通道按一定顺序连接起来，那么这两个洞穴就是连通的，按顺序连接在一起的这些通道则被称之为这两个洞穴之间的一条路径。 洞穴都十分坚固无法破坏，然而通道不太稳定，时常因为外界影响而发生改变，比如，根据有关仪器的监测结果，123号洞穴和127号洞穴之间有时会出现一条通道，有时这条通道又会因为某种稀奇古怪的原因被毁。

辉辉有一台监测仪器可以实时将通道的每一次改变状况在辉辉手边的终端机上显示：

如果监测到洞穴u和洞穴v之间出现了一条通道，终端机上会显示一条指令 `Connect u v`

如果监测到洞穴u和洞穴v之间的通道被毁，终端机上会显示一条指令 `Destroy u v`

经过长期的艰苦卓绝的手工推算，辉辉发现一个奇怪的现象：无论通道怎么改变，任意时刻任意两个洞穴之间至多只有一条路径。

因而，辉辉坚信这是由于某种本质规律的支配导致的。因而，辉辉更加夜以继日地坚守在终端机之前，试图通过通道的改变情况来研究这条本质规律。 然而，终于有一天，辉辉在堆积成山的演算纸中崩溃了……他把终端机往地面一砸（终端机也足够坚固无法破坏），转而求助于你，说道：“你老兄把这程序写写吧”。

辉辉希望能随时通过终端机发出指令 `Query u v`，向监测仪询问此时洞穴u和洞穴v是否连通。现在你要为他编写程序回答每一次询问。 已知在第一条指令显示之前，JSZX洞穴群中没有任何通道存在。

inputFormat: 第一行为两个正整数n和m，分别表示洞穴的个数和终端机上出现过的指令的个数。 以下m行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s（"Connect”、”Destroy”或者”Query”，区分大小写），之后有两个整数u和v (1≤u, v≤n) 分别表示两个洞穴的编号。

outputFormat: 对每个Query指令，输出洞穴u和洞穴v是否互相连通：是输出”Yes”，否则输出”No”。（不含双引号）

samples:
3 5
Connect 1 2
Connect 3 1
Query 2 3
Destroy 1 3
Query 2 3

hint:
数据说明

10%的数据满足n≤1000, m≤20000

20%的数据满足n≤2000, m≤40000

30%的数据满足n≤3000, m≤60000

40%的数据满足n≤4000, m≤80000

50%的数据满足n≤5000, m≤100000

60%的数据满足n≤6000, m≤120000

70%的数据满足n≤7000, m≤140000

80%的数据满足n≤8000, m≤160000

90%的数据满足n≤9000, m≤180000

100%的数据满足n≤10000, m≤200000

保证所有Destroy指令将摧毁的是一条存在的通道

本题输入、输出规模比较大，建议c\c++选手使用scanf和printf进行I\O操作以免超时

---

@namespace_std 于 2019.12.1 添加一组 Hack 数据


title: [SDOI2009] E&D

description:
小 E 与小 W 进行一项名为 `E&D` 游戏。

游戏的规则如下：桌子上有 $2n$ 堆石子，编号为 $1 \sim 2n$。其中，为了方便起见，我们将第 $2k-1$ 堆与第 $2k$ 堆（$1 \le k \le n$）视为同一组。第 $i$ 堆的石子个数用一个正整数 $S_i$ 表示。

一次分割操作指的是，从桌子上任取一堆石子，将其移走。然后分割它同一组的另一堆石子，从中取出若干个石子放在被移走的位置，组成新的一堆。操作完成后，所有堆的石子数必须保证大于 $0$。显然，被分割的一堆的石子数至少要为 $2$。两个人轮流进行分割操作。如果轮到某人进行操作时，所有堆的石子数均为 $1$，则此时没有石子可以操作，判此人输掉比赛。

小 E 进行第一次分割。他想知道，是否存在某种策略使得他一定能战胜小 W。因此，他求助于小 F，也就是你，请你告诉他是否存在必胜策略。例如，假设初始时桌子上有 $4$ 堆石子，数量分别为 $1,2,3,1$。小 E 可以选择移走第 $1$ 堆，然后将第 $2$ 堆分割（只能分出 $1$ 个石子）。接下来，小 W 只能选择移走第 $4$ 堆，然后将第 $3$ 堆分割为 $1$ 和 $2$。最后轮到小 E，他只能移走后两堆中数量为 $1$ 的一堆，将另一堆分割为 $1$ 和 $1$。这样，轮到小 W 时，所有堆的数量均为 $1$，则他输掉了比赛。故小 E 存在必胜策略。

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

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

对于每组数据：

第一行一个整数 $N$，表示桌子上共有 $N$ 堆石子，这里的 $N$ 即为题目描述中的 $2n$。

第二行 $N$ 个整数 $S_{1 \dots N}$。

outputFormat: 对于每组数据，如果小 E 必胜，则一行一个字符串 `YES`，否则一行一个字符串 `NO`。

hint:
对于 $20\%$ 的数据，$N=2$。

对于另外 $20\%$ 的数据，$N \le 4$，$S_i \le 50$。

对于 $100\%$ 的数据，$1 \le T \le 20$，$1 \le N \le 2 \times 10^4$ 且 $N$ 为偶数，$1 \le S_i \le 2 \times 10^9$。


title: [SDOI2009] Elaxia的路线

description:
最近，Elaxia 和 w** 的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们必须合理地安排两个人在一起的时间。

Elaxia 和 w** 每天都要奔波于宿舍和实验室之间，他们 希望在节约时间的前提下，一起走的时间尽可能的长。

现在已知的是 Elaxia 和 w** 所在的宿舍和实验室的编号以及学校的地图：
地图上有 $n$ 个路口，$m$ 条路，经过每条路都需要一定的时间。 具体地说，就是要求无向图中，两对点间最短路的最长公共路径。

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

第二行四个正整数 $x_1,y_1,x_2,y_2$，分别表示 Elaxia 的宿舍和实验室及 w** 的宿舍和实验室的标号。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示 $u,v$之间有一条边，需要 $w$ 的时间经过。

outputFormat: 一行一个整数表示答案。（即最长公共路径的长度）

hint:
【数据范围】
对于 $30\%$ 的数据，$1\le n \le 100$；
对于 $60\%$ 的数据，$1\le n \le 1000$；
对于 $100\%$ 的数据，$1\le n \le 1500$，$1 \leq m \leq 3 \times 10^5$，$1\le w \le 10^4$，输入数据保证没有重边和自环。


title: [NOI2015] 寿司晚宴

description:
为了庆祝 NOI 的成功开幕，主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手，也被邀请参加了寿司晚宴。

在晚宴上，主办方为大家提供了 $n−1$ 种不同的寿司，编号 $1,2,3,\ldots,n-1$，其中第 $i$ 种寿司的美味度为 $i+1$。（即寿司的美味度为从 $2$ 到 $n$）

现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为 $x$ 的寿司，小 W 品尝的寿司中存在一种美味度为 $y$ 的寿司，而 $x$ 与 $y$ 不互质。

现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 $p$ 取模）。注意一个人可以不吃任何寿司。

inputFormat: 输入文件的第 $1$ 行包含 $2$ 个正整数 $n, p$ 中间用单个空格隔开，表示共有 $n$ 种寿司，最终和谐的方案数要对 $p$ 取模。

outputFormat: 输出一行包含 $1$ 个整数，表示所求的方案模 $p$ 的结果。

hint:
【数据范围】

 ![](https://cdn.luogu.com.cn/upload/pic/1506.png)

**勘误：$0 < p \le 10^9 $**


title: [SDOI2009] HH去散步

description:
HH 有个一成不变的习惯，喜欢饭后百步走。所谓百步走，就是散步，就是在一定的时间内，走过一定的距离。但是同时 HH 又是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。又因为 HH 是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。

现在给你学校的地图（假设每条路的长度都是一样的都是 $1$），问长度为 $t$，从给定地点 $A$ 走到给定地点 $B$ 共有多少条符合条件的路径。

inputFormat:
第一行：五个整数 $N,M,t,A,B$。其中 $N$ 表示学校里的路口的个数，$M$ 表示学校里的路的条数，$t$ 表示 HH 想要散步的距离，$A$ 表示散步的出发点，而 $B$ 则表示散步的终点。

接下来 $M$ 行，每行一组 $A_i,B_i$，表示从路口 $A_i$ 到路口 $B_i$ 有一条路。数据保证 $A_i \neq B_i$，但不保证任意两个路口之间至多只有一条路相连接。路口编号从 $0$ 到 $N-1$。同一行内所有数据均由一个空格隔开，行首行尾没有多余空格。没有多余空行。答案模 $45989$。

outputFormat: 一行，表示答案。


title: [SDOI2009] SuperGCD

description: Sheng bill 有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的最大公约数！因此他经常和别人比赛计算最大公约数。有一天Sheng bill很嚣张地找到了你，并要求和你比赛，但是输给 Sheng bill 岂不是很丢脸！所以你决定写一个程序来教训他。

inputFormat: 共两行，第一行一个整数 $a$，第二行一个整数 $b$。

outputFormat: 一行，表示 $a$ 和 $b$ 的最大公约数。