title: [HNOI2014] 米特运输

description:
米特是 D 星球上一种非常神秘的物质，蕴含着巨大的能量。在以米特为主要能源的 D 星上，这种米特能源的运输和储存一直是一个大问题。

D 星上有 $N$ 个城市，我们将其顺序编号为 $1$ 到 $N$，$1$ 号城市为首都。这 $N$ 个城市由 $N-1$ 条单向高速通道连接起来，构成一棵以 $1$ 号城市（首部）为根的树，高速通道的方向由树中的儿子指向父亲。树按深度分层：根结点深度为 $0$，属于第 $1$ 层；根结点的子节点深度为 $1$，属于第 $2$ 层；依此类推，深度为 $i$ 的结点属于第 $i+1$ 层。

建好高速通道之后，D 星人开始考虑如何具体地储存和传输米特资源。由于发展程度不同，每个城市储存米特的能力不尽相同，其中第 $i$ 个城市建有一个容量为 $A_i$ 的米特储存器。这个米特储存器除了具有储存的功能，还具有自动收集米特的能力。

如果到了晚上六点，有某个储存器处于未满的状态，它就会自动收集大气中蕴含的米特能源，在早上六点之前就能收集满；但是，只有在储存器完全空的状态下启动自动收集程序才是安全的，未满而又非空时启动可能有安全隐患。

早上六点到七点间，根节点城市（$1$ 号城市）会将其储存器里的米特消耗殆尽。根节点不会自动搜集米特，它只接受子节点传输来的米特。

早上七点，城市之间启动米特传输过程，传输过程逐层递进：先是第 $2$ 层节点城市向第 $1$ 层（根节点城市，即 $1$ 号城市）传输，直到第 $1$ 层的储存器满或第 $2$ 层的储存器全为空；然后是第 $3$ 层向第 $2$ 层传输，直到对于第 $2$ 层的每个节点，其储存器满或其子节点（位于第 $3$ 层）的储存器全为空；依此类推，直到最后一层传输完成。传输过程一定会在晚上六点前完成。

由于技术原因，运输方案需要满足以下条件：

1. 不能让某个储存器到了晚上六点传输结束时还处于非空但又未满的状态，这个时候储存器仍然会启动自动收集米特的程序，而给已经储存有米特的储存器启动收集程序可能导致危险，也就是说要让储存器到了晚上六点时要么空要么满；

2. 关于首都——即 $1$ 号城市的特殊情况，  每天早上六点到七点间 $1$ 号城市中的米特储存器里的米特会自动被消耗殆尽，即运输方案不需要考虑首都的米特怎么运走；

3. 除了 $1$ 号城市，每个节点必须在其子节点城市向它运输米特之前将这座城市的米特储存器中原本存有的米特全部运出去给父节点，不允许储存器中残存的米特与外来的米特发生混合；

4. 运向某一个城市的若干个来源的米特数量必须完全相同，不然，这些来源不同的米特按不同比例混合之后可能发生危险。

现在 D 星人已经建立好高速通道，每个城市也有了一定储存容量的米特储存器。为了满足上面的限制条件，可能需要重建一些城市中的米特储存器。你可以，也只能，将某一座城市（包括首都）中原来存在的米特储存器摧毁，再新建一座任意容量的新的米特储存器，其容量可以是小数（在输入数据中，储存器原始容量是正整数，但重建后可以是小数），不能是负数或零，使得需要被重建的米特储存器的数目尽量少。

inputFormat:
第一行是一个正整数 $N$，表示城市的数目。
接下来 $N$ 行，每行一个正整数，其中的第 $i$ 行表示第 $i$ 个城市原来存在的米特储存器的容量。
再接下来是 $N-I$ 行，每行两个正整数 $a，b$ 表示城市 $b$ 到城市 $a$ 有一条高速通道 $(a≠b)$。

outputFormat: 输出文件仅包含一行，一个整数，表示最少的被重建（即修改储存器容量）的米特储存器的数目。

hint:
【样例解释】

一个最优解是将 $A_1$ 改成 $8$，$A_3$ 改成 $4$，$A_5$ 改成 $2$。这样，$2$ 和 $3$ 运给 $1$ 的量相等，$4$ 和 $5$ 运给 $2$ 的量相等，且每天晚上六点的时候，$1$，$2$ 满，$3$，$4$，$5$ 空，满足所有限制条件。

对于 $100\%$ 的数据满足 $N<500000，A_j<10^8$


title: [HNOI2014] 道路堵塞

type: P

background: ### 本题可能不存在正确解法，题解均已被 hack。

description: A 国有 $N$ 座城市，依次标为 $1$ 到 $N$。同时，在这 $N$ 座城市间有 $M$ 条单向道路，每条道路的长度是一个正整数。现在，A 国交通部指定了一条从城市 $1$ 到城市 $N$ 的路径，并且保证这条路径的长度是所有从城市 $1$ 到城市 $N$ 的路径中最短的。不幸的是，因为从城市 $1$ 到城市 $N$ 旅行的人越来越多，这条由交通部指定的路径经常发生堵塞。现在 A 国想知道，这条路径中的任意一条道路无法通行时，由城市 $1$ 到 $N$ 的最短路径长度是多少。

inputFormat: 输入文件第一行是三个用空格分开的正整数 $N$、$M$ 和 $L$，分别表示城市数目、单向道路数目和交通部指定的最短路径包含多少条道路。按下来 $M$ 行，每行三个用空格分开的整数 $a$、$b$ 和 $c$，表示存在一条由城市 $a$ 到城市 $b$ 的长度为 $c$ 的单向道路。这 $M$ 行的行号也是对应道路的编号，即其中第 $1$ 行对应的道路编号为 $1$，第 $2$ 行对应的道路编号为 $2$，......，第 $M$ 行对应的道路编号为 $M$。最后一行为 $L$ 个用空格分开的整数 $\operatorname{sp}(1),\ldots,\operatorname{sp}(L)$，依次表示从城市 $1$ 到城市 $N$ 的由交通部指定的最短路径上的道路的编号。

outputFormat: 输出文件包含 $L$ 行，每行为一个整数，第 $i$ 行（$i = 1,2,\ldots,L$）的整数表示删去编号为 $\operatorname{sp}(i)$ 的道路后从城市 $1$ 到城市 $N$ 的最短路径长度。如果去掉后没有从城市 $1$ 到城市 $N$ 的路径，则输出 $-1$。


title: [HNOI2015] 亚瑟王

description:
小 K 不慎被 LL 邪教洗脑了，洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定，在脱坑之前，最后再来打一盘亚瑟王。既然是最后一战，就一定要打得漂亮。众所周知，亚瑟王是一个看脸的游戏，技能的发动都是看概率的。

作为一个非洲人，同时作为一个前 OIer，小 K 自然是希望最大化造成伤害的期望值。但他已经多年没写过代码，连 Spaly都敲不对了，因此，希望你能帮帮小 K，让他感受一下当欧洲人是怎样的体验。

本题中我们将考虑游戏的一个简化版模型。 玩家有一套卡牌，共 $n$ 张。游戏时，玩家将 $n$ 张卡牌排列成某种顺序，排列后将卡牌按从前往后依次编号为 $1 -  n$。本题中，顺序已经确定，即为输入的顺序。每张卡牌都有一个技能。第 $i$ 张卡牌的技能发动概率为 $p_i$，如果成功发动，则会对敌方造成 $d_i$ 点伤害。也只有通过发动技能，卡牌才能对敌方造成伤害。基于现实因素以及小 K 非洲血统的考虑，$p_i$ 不会为 $0$，也不会为 $1$，即 $0 < p_i < 1$。 一局游戏一共有 $r$ 轮。在每一轮中，系统将从第一张卡牌开始，按照顺序依次考虑每张卡牌。在一轮中，对于依次考虑的每一张卡牌：

1. 如果这张卡牌在这一局游戏中已经发动过技能，则

1.1. 如果这张卡牌不是最后一张，则跳过之（考虑下一张卡牌）； 否则（是最后一张），结束这一轮游戏。

2. 否则（这张卡牌在这一局游戏中没有发动过技能），设这张卡牌为第 $i$ 张

2.1. 将其以 $p_i$ 的概率发动技能。

2.2. 如果技能发动，则对敌方造成 $d_i$ 点伤害，并结束这一轮。

2.3. 如果这张卡牌已经是最后一张（即 $i$ 等于 $n$），则结束这一轮；否则，考虑下一张卡牌。

请帮助小 K 求出这一套卡牌在一局游戏中能造成的伤害的期望值。

inputFormat:
输入文件的第一行包含一个整数 $T$，代表测试数据组数。

接下来一共 $T$ 组数据。

每组数据的第一行包含两个用空格分开的整数 $n$ 和 $r$，分别代表卡牌的张数和游戏的轮数。

接下来 $n$ 行，每行包含一个实数和一个整数，由空格隔开，描述一张卡牌。第$i$ 行的两个数为 $p_i$ 和 $d_i$，分别代表第 $i$ 张卡牌技能发动的概率（实数）和技能发动造成的伤害（整数）。保证 $p_i$ 最多包含 $4$ 位小数，且为一个合法的概率。

outputFormat: 对于每组数据，输出一行，包含一个实数，为这套卡牌在这一局游戏中造成的伤害的期望值。对于每一行输出，只有当你的输出和标准答案的相对误差不超过 $10^{-8}$ 时——即 $\frac{|a-o|}{a} \leq 10^{-8}$ 时(其中 $a$ 是标准答案， $o$ 是输出)，你的输出才会被判为正确。建议输出 $10$ 位小数。

hint:
一共有 $13$ 种可能的情况：

1.  第一轮中，第 $1$ 张卡牌发动技能；第二轮中，第 $2$ 张卡牌发动技能；

概率为 $0.15$，伤害为 $5$。

2.  第一轮中，第 $1$ 张卡牌发动技能；第二轮中，第 $3$ 张卡牌发动技能；

概率为 $0.315$，伤害为 $3$。

3.  第一轮中，第 $1$ 张卡牌发动技能；第二轮不发动技能；

概率为 $0.035$，伤害为 $2$。

4.  第一轮中，第 $2$ 张卡牌发动技能；第二轮中，第 $1$ 张卡牌发动技能；

概率为 $0.075$，伤害为 $5$。

5.  第一轮中，第 $2$ 张卡牌发动技能；第二轮中，第 $3$ 张卡牌发动技能；

概率为 $0.0675$，伤害为 $4$。

6.  第一轮中，第 $2$ 张卡牌发动技能；第二轮不发动技能；

概率为 $0.0075$，伤害为 $3$。

7.  第一轮中，第 $3$ 张卡牌发动技能；第二轮中，第 $1$ 张卡牌发动技能；

概率为 $0.1575$，伤害为 $3$。

8.  第一轮中，第 $3$ 张卡牌发动技能；第二轮中，第 $2$ 张卡牌发动技能；

概率为 $0.04725$，伤害为 $4$。

9.  第一轮中，第 $3$ 张卡牌发动技能；第二轮不发动技能；

概率为 $0.11025$，伤害为 $1$。

10.  第一轮不发动技能；第二轮中，第 $1$ 张卡牌发动技能；

概率为 $0.0175$，伤害为 $2$。

11.  第一轮不发动技能；第二轮中，第 $2$ 张卡牌发动技能；

概率为 $0.00525$，伤害为 $3$。

12.  第一轮不发动技能；第二轮中，第 $3$ 张卡牌发动技能；

概率为 $0.011025$，伤害为 $1$。

13.  第一轮不发动技能；第二轮亦不发动技能；

概率为 $0.001225$，伤害为 $0$。

造成伤害的期望值为概率与对应伤害乘积之和，为 $3.266025$。

对于所有测试数据， $1 \leq T \leq 444， 1 \leq n \leq 220， 0 \leq r \leq 132， 0 < p_i < 1， 0 \leq d_i \leq 1000$。

除非备注中有特殊说明，数据中 $p_i$ 与 $d_i$ 均为随机生成。

请注意可能存在的实数精度问题，并采取适当措施。

本题使用 `special_judge`。


title: [HNOI2015] 实验比较

description:
小 D 被邀请到实验室，做一个跟图片质量评价相关的主观实验。

实验用到的图片集一共有 $N$ 张图片，编号为 $1$ 到 $N$。实验分若干轮进行，在每轮实验中，小 D 会被要求观看某两张随机选取的图片， 然后小 D 需要根据他自己主观上的判断确定这两张图片谁好谁坏，或者这两张图片质量差不多。

用符号 ”$<$”、“$>$” 和 “$=$” 表示图片 $x$ 和 $y$（$x$、$y$ 为图片编号）之间的比较：如果上下文中 $x$ 和 $y$ 是图片编号，则 $x<y$ 表示图片 $x$「质量优于」$y$，$x>y$ 表示图片 $x$「质量差于」$y$，$x=y$ 表示图片 $x$ 和 $y$ 「质量相同」；也就是说，这种上下文中，“$<$”、“$>$”、“$=$” 分别是质量优于、质量差于、质量相同的意思；在其他上下文中，这三个符号分别是小于、大于、等于的含义。

图片质量比较的推理规则（在 $x$ 和 $y$ 是图片编号的上下文中）：
1. $x < y$ 等价于 $y > x$。
2. 若 $x < y$ 且 $y = z$，则 $x < z$。
3. 若 $x < y$ 且 $x = z$，则 $z < y$。
4. $x=y$ 等价于 $y=x$。
5. 若 $x=y$ 且 $y=z$，则 $x=z$。

实验中，小 D 需要对一些图片对 $(x, y)$，给出 $x < y$ 或 $x = y$ 或 $x > y$ 的主观判断。小 D 在做完实验后， 忽然对这个基于局部比较的实验的一些全局性质产生了兴趣。

在主观实验数据给定的情形下，定义这 $N$ 张图片的一个合法质量序列为形如 “$x_1 R_1 x_2 R_2 x_3 R_3 …x_{N-1} R_{N-1} x_N$” 的串，也可看作是集合 $\{ x_i R_i x_{i+1}|1 \leq i \leq N-1 \}$，其中  $x_i$ 为图片编号，$x_1,x_2, \ldots ,x_N$ 两两互不相同（即不存在重复编号），$R_i$ 为 $<$ 或 $=$，「合法」是指这个图片质量序列与任何一对主观实验给出的判断不冲突。

例如： 质量序列 $3 < 1 = 2$ 与主观判断 “$3 > 1$，$3 = 2$” 冲突（因为质量序列中 $3<1$ 且 $1=2$，从而 $3<2$，这与主观判断中的 $3=2$ 冲突；同时质量序列中的 $3<1$ 与主观判断中的 $3>1$ 冲突） ，但与主观判断 “$2 = 1$，$3 < 2$”  不冲突；因此给定主观判断 “$3>1$，$3=2$” 时，$1<3=2$ 和 $1<2=3$ 都是合法的质量序列，$3<1=2$ 和 $1<2<3$ 都是非法的质量序列。

由于实验已经做完一段时间了，小 D 已经忘了一部分主观实验的数据。对每张图片 $X_i$，小 D 都**最多**只记住了某一张质量不比 $X_i$ 好的另一张图片 $K_{X_i}$。这些小 D 仍然记得的质量判断一共有 $M$ 条（$0 \leq M \leq N$），其中第 $i$ 条涉及的图片对为 $(K_{X_i}, X_i)$，判断要么是 $K_{X_i} < X_i$，要么是 $K_{X_i} = X_i$，而且所有的 $X_i$ 互不相同。小 D 打算就以这 M 条自己还记得的质量判断作为他的所有主观数据。

现在，基于这些主观数据，我们希望你帮小 D 求出这 $N$ 张图片一共有多少个不同的合法质量序列。我们规定：如果质量序列中出现 “$x = y$”，那么序列中交换 $x$ 和 $y$ 的位置后仍是同一个序列。因此： $1<2=3=4<5$ 和 $1<4=2=3<5$ 是同一个序列， $1 < 2 = 3$ 和 $1 < 3 = 2$ 是同一个序列，而 $1 < 2 < 3$ 与 $1 < 2 = 3$ 是不同的序列，$1<2<3$ 和 $2<1<3$ 是不同的序列。

由于合法的图片质量序列可能很多， 所以你需要输出答案对 $10^9 + 7$ 取模的结果。

inputFormat:
第一行两个正整数 $N,M$，分别代表图片总数和小 $D$ 仍然记得的判断的条数；

接下来 $M$ 行，每行一条判断，每条判断形如「$x < y$」或者「$x = y$」。

outputFormat: 输出仅一行，包含一个正整数，表示合法质量序列的数目对 $10^9+7$ 取模的结果。


title: [HNOI2015] 开店

description:
风见幽香有一个好朋友叫八云紫，她们经常一起看星星看月亮从诗词歌赋谈到人生哲学。最近她们灵机一动，打算在幻想乡开一家小店来做生意赚点钱。

这样的想法当然非常好啦，但是她们也发现她们面临着一个问题，那就是店开在哪里，面向什么样的人群。很神奇的是，幻想乡的地图是一个树形结构，幻想乡一共有 $n$ 个地方，编号为 $1$ 到 $n$，被 $n-1$ 条带权的边连接起来。每个地方都住着一个妖怪，其中第 $i$ 个地方的妖怪年龄是 $x_i$。

妖怪都是些比较喜欢安静的家伙，所以它们并不希望和很多妖怪相邻。所以这个树所有顶点的度数都小于或等于 $3$。妖怪和人一样，兴趣点随着年龄的变化自然就会变化，比如我们的 $18$ 岁少女幽香和八云紫就比较喜欢可爱的东西。幽香通过研究发现，基本上妖怪的兴趣只跟年龄有关，所以幽香打算选择一个地方 $u$（$u$ 为编号），然后在 $u$ 开一家面向年龄在 $L$ 到 $R$ 之间（即年龄大于等于 $L$ 小于等于 $R$）的妖怪的店。

也有可能 $u$ 这个地方离这些妖怪比较远，于是幽香就想要知道所有年龄在 $L$ 到 $R$ 之间的妖怪，到点 $u$ 的距离的和是多少（妖怪到 $u$ 的距离是该妖怪所在地方到 $u$ 的路径上的边的权之和），幽香把这个称为这个开店方案的方便值。

幽香她们还没有决定要把店开在哪里，八云紫倒是准备了很多方案，于是幽香想要知道，对于每个方案，方便值是多少呢。

inputFormat:
第一行三个用空格分开的数 $n,Q$ 和 $A$，表示树的大小、开店的方案个数和妖怪的年龄上限。

第二行 $n$ 个用空格分开的数 $x_1,x_2,\ldots,x_n$；$x_i$ 表示第 $i$ 个地点妖怪的年龄，满足 $0\le x_i\lt A$。(年龄是可以为 $0$ 的，例如刚出生的妖怪的年龄为 $0$。)

接下来 $n-1$  行，每行三个用空格分开的数 $a$、$b$、$c$，表示树上的顶点 $a$ 和 $b$ 之间有一条权为 $c(1\le c\le1000)$ 的边，$a$ 和 $b$ 是顶点编号。

接下来 $Q$ 行，每行三个用空格分开的数 $u,a,b$。

对于这 $Q$ 行的每一行，用 $a,b,A$ 计算出 $L$ 和 $R$，表示询问”在地方 $u$ 开店，面向妖怪的年龄区间为 $[L,R]$ 的方案的方便值是多少“。

对于其中第 $1$ 行，$L$ 和 $R$ 的计算方法为：$L=\min(a\bmod A,b\bmod A),R=\max(a\bmod A,b\bmod A)$ 。

对于第 $2$ 到第 $Q$ 行，假设前一行得到的方便值为 $ans$，那么当前行的 $L$ 和 $R$ 计算方法为： $L=\min((a+ans)\bmod A,(b+ans)\bmod A), R=\max((a+ans)\bmod A,(b+ans)\bmod A)$ 。

outputFormat: 对于每个方案，输出一行表示方便值。

hint: 满足 $n\le1.5 \times 10^5,Q\le2 \times 10^5$。对于所有数据，满足 $A\le 10^9$。


title: [HNOI2015] 接水果

description:
风见幽香非常喜欢玩一个叫做 osu! 的游戏，其中她最喜欢玩的模式就是接水果。由于她已经 DT FC 了 The big black，她觉得这个游戏太简单了，于是发明了一个更加难的版本。

首先有一个地图，是一棵由 $n$ 个顶点，$n-1$ 条边组成的树。

这颗树上有 $p$ 个盘子，每个盘子实际上是一条路径，并且每个盘子还有一个权值。第 $i$ 个盘子就是顶点 $a_i$ 到顶点 $b_i$ 的路径（由于是树，所以从 $a_i$ 到 $b_i$ 的路径是唯一的），权值为 $c_i$。

接下来依次会有 $q$ 个水果掉下来，每个水果本质上也是一条路径，第 $i$ 个水果是从顶点 $u_i$ 到顶点 $v_i$ 的路径。

幽香每次需要选择一个盘子去接当前的水果：一个盘子能接住一个水果，当且仅当盘子的路径是水果的路径的子路径。这里规定：从 $a$ 到 $b$ 的路径与从 $b$ 到 $a$ 的路径是同一条路径。

当然为了提高难度，对于第 $i$ 个水果，你需要选择能接住它的所有盘子中，权值第 $k_i$ 小的那个盘子，每个盘子可重复使用（没有使用次数的上限：一个盘子接完一个水果后，后面还可继续接其他水果，只要它是水果路径的子路径）。幽香认为这个游戏很难，你能轻松解决给她看吗？

inputFormat:
第一行三个数 $n$ 和 $p$ 和 $q$，表示树的大小和盘子的个数和水果的个数。

接下来 $n-1$ 行，每行两个数 $a,b$，表示树上的 $a$ 和 $b$ 之间有一条边。树中顶点按 $1$ 到 $n$ 标号。

接下来 $p$ 行，每行三个数 $a,b,c$，表示路径为 $a$ 到 $b$、权值为 $c$ 的盘子，其中 $a \neq b$。

接下来 $q$ 行，每行三个数 $u,v,k$，表示路径为 $u$ 到 $v$ 的水果，其中 $u \neq v$，你需要选择第 $k$ 小的盘子，第 $k$ 小一定存在。

outputFormat: 对于每个果子，输出一行表示选择的盘子的权值。


title: [HNOI2015] 菜肴制作

description:
知名美食家小 A 被邀请至 ATM 大酒店，为其品评菜肴。ATM 酒店为小 A 准备了 $n$ 道菜肴，酒店按照为菜肴预估的质量从高到低给予 $1$ 到 $n$ 的顺序编号，预估质量最高的菜肴编号为 $1$。

由于菜肴之间口味搭配的问题，某些菜肴必须在另一些菜肴之前制作，具体的，一共有 $m$ 条形如 $i$ 号菜肴必须先于 $j$ 号菜肴制作的限制，我们将这样的限制简写为 $(i,j)$。

现在，酒店希望能求出一个最优的菜肴的制作顺序，使得小 A 能尽量先吃到质量高的菜肴：

也就是说，

1. 在满足所有限制的前提下，$1$ 号菜肴尽量优先制作。

2. 在满足所有限制，$1$ 号菜肴尽量优先制作的前提下，$2$ 号菜肴尽量优先制作。

3. 在满足所有限制，$1$ 号和 $2$ 号菜肴尽量优先的前提下，$3$ 号菜肴尽量优先制作。

4. 在满足所有限制，$1$ 号和 $2$ 号和 $3$ 号菜肴尽量优先的前提下，$4$ 号菜肴尽量优先制作。

5. 以此类推。

例 1：共 $4$ 道菜肴，两条限制 $(3,1)$、$(4,1)$，那么制作顺序是 $3,4,1,2$。

例 2：共 $5$ 道菜肴，两条限制 $(5,2)$、$(4,3)$，那么制作顺序是 $1,5,2,4,3$。

例 1 里，首先考虑 $1$，因为有限制 $(3,1)$ 和 $(4,1)$，所以只有制作完 $3$ 和 $4$ 后才能制作 $1$，而根据 3，$3$ 号又应尽量比 $4$ 号优先，所以当前可确定前三道菜的制作顺序是 $3,4,1$；接下来考虑 $2$，确定最终的制作顺序是 $3,4,1,2$。

例 $2$ 里，首先制作 $1$ 是不违背限制的；接下来考虑 $2$ 时有 $(5,2)$ 的限制，所以接下来先制作 $5$ 再制作 $2$；接下来考虑 $3$ 时有 $(4,3)$ 的限制，所以接下来先制作 $4$ 再制作 $3$，从而最终的顺序是 $1,5,2,4,3$。现在你需要求出这个最优的菜肴制作顺序。无解输出 `Impossible!`（首字母大写，其余字母小写）

inputFormat: 第一行是一个正整数 $t$，表示数据组数。接下来是 $t$ 组数据。对于每组数据：第一行两个用空格分开的正整数 $n$ 和 $m$，分别表示菜肴数目和制作顺序限制的条目数。接下来 $m$ 行，每行两个正整数 $x,y$，表示 $x$ 号菜肴必须先于 $y$ 号菜肴制作的限制。

outputFormat: 输出文件仅包含 $t$ 行，每行 $n$ 个整数，表示最优的菜肴制作顺序，或者 `Impossible!` 表示无解。

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

第二组数据同时要求菜肴 $1$ 先于菜肴 $2$ 制作，菜肴 $2$ 先于菜肴 $3$ 制作，菜肴 $3$ 先于菜肴 $1$ 制作，而这是无论如何也不可能满足的，从而导致无解。

**【数据范围】**

$100\%$ 的数据满足 $n,m\le 10^5$，$1\le t\le 3$。

$m$ 条限制中可能存在完全相同的限制。


title: [HNOI2015] 落忆枫音

background:
「恒逸，你相信灵魂的存在吗？」 郭恒逸和姚枫茜漫步在枫音乡的街道上。望着漫天飞舞的红枫，枫茜突然问出这样一个问题。

「相信吧。不然我们是什么，一团肉吗？要不是有灵魂......我们也不可能再见到你姐姐吧。」 恒逸给出了一个略微无厘头的回答。枫茜听后笑了笑。 「那你仔细观察过枫叶吗？」 说罢，枫茜伸手，接住了一片飘落的枫叶。

「其实每一片枫叶都是有灵魂的。你看，枫叶上不是有这么多脉络吗？我听说，枫叶上有一些特殊的位置，就和人的穴位一样。脉络都是连接在这些穴位之间的。枫树的灵魂流过每片枫叶的根部，沿着这些脉络，慢慢漫进穴位，沁入整片枫叶。也是因为这个原因，脉络才都是单向的，灵魂可不能倒着溜回来呢。」 恒逸似懂非懂地点了点头。枫茜接着说了下去。

「正是因为有了灵魂，每片枫叶才会与众不同。也正是因为有了灵魂，每片枫叶也都神似其源本的枫树，就连脉络也形成了一棵树的样子。但如果仔细看的话，会发现，在脉络树之外，还存在其它的非常细的脉络。虽然这些脉络并不在树上，但他们的方向也同样顺着灵魂流淌的方向，绝不会出现可能使灵魂倒流的回路。」  恒逸好像突然想到了什么。 「那这些脉络岂不是可以取代已有的脉络，出现在脉络树上？」 枫茜闭上了眼睛。

「是啊，就是这样。脉络树并不是唯一的。只要有一些微小的偏差，脉络树就可能差之万里，哪怕是在这同一片枫叶上。就像我们的故事，结局也不是唯一的。只要改变一个小小的选项，故事流程可能就会被彻底扭转。」

「真是深奥啊......」 恒逸盯着这片红枫，若有所思地说。枫茜继续说道。

「还不止如此呢。所有的脉络都不会永恒存在，也不会永恒消失。不管是脉络树上的脉络，还是之外的细小脉络，都是如此。存在的脉络可能断开消失，消失的脉络也可能再次连接。万物皆处在永恒的变化之中，人与人之间的羁绊也是。或许有一天，我们与大家的羁绊也会如同脉络一样，被无情地斩断。或许我们也终将成为”枫音乡的过客“。或许这一切都会是必然，是枫树的灵魂所决定的......」

枫茜的眼角泛起了几滴晶莹剔透的泪珠。恒逸看着这样的枫茜，将她抱入怀中。

「别这样想，枫茜。就算脉络断开，也有可能还会有新的脉络树，也还会与枫树的根相连。这样的话，我们的羁绊仍然存在，只是稍微绕了一些远路而已。无论如何，我都不会离开你的。因为你是我穷尽一生所寻找的，我的真恋啊！」

两人的目光对上了。枫茜幸福地笑了，把头埋进了恒逸的怀抱。从远方山上的枫林中，传来了枫的声音。

description:
不妨假设枫叶上有 n个穴位，穴位的编号为 1 ~  n。有若干条有向的脉络连接着这些穴位。穴位和脉络组成一个有向无环图——称之为脉络图（例如图 1），穴位的编号使得穴位 1 没有从其他穴位连向它的脉络，即穴位 1 只有连出去的脉络；由上面的故事可知，这个有向无环图存在一个树形子图，它是以穴位 1为根的包含全部n个穴位的一棵树——称之为脉络树（例如图 2和图 3给出的树都是图1给出的脉络图的子图）；值得注意的是，脉络图中的脉络树方案可能有多种可能性，例如图2和图 3就是图 1给出的脉络图的两个脉络树方案。

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

脉络树的形式化定义为：以穴位 r 为根的脉络树由枫叶上全部 n个穴位以及 n-  1 条脉络组成，脉络树里没有环，亦不存在从一个穴位连向自身的脉络，且对于枫叶上的每个穴位 s，都存在一条唯一的包含于脉络树内的脉络路径，使得从穴位r 出发沿着这条路径可以到达穴位 s。 现在向脉络图添加一条与已有脉络不同的脉络（注意：连接 2个穴位但方向不同的脉络是不同的脉络，例如从穴位3到4的脉络与从4到3的脉络是不同的脉络，因此，图 1 中不能添加从 3 到 4 的脉络，但可添加从 4 到 3 的脉络），这条新脉络可以是从一个穴位连向自身的（例如，图 1 中可添加从 4 到 4 的脉络）。原脉络图添加这条新脉络后得到的新脉络图可能会出现脉络构成的环。 请你求出添加了这一条脉络之后的新脉络图的以穴位 1 为根的脉络树方案数。

由于方案可能有太多太多，请输出方案数对 1,000,000,007 取模得到的结果。

inputFormat: 输入文件的第一行包含四个整数 n、m、x和y，依次代表枫叶上的穴位数、脉络数，以及要添加的脉络是从穴位 x连向穴位y的。 接下来 m行，每行两个整数，由空格隔开，代表一条脉络。第 i 行的两个整数为ui和vi，代表第 i 条脉络是从穴位 ui连向穴位vi的。

outputFormat: 输出一行，为添加了从穴位 x连向穴位 y的脉络后，枫叶上以穴位 1 为根的脉络树的方案数对 1,000,000,007取模得到的结果。

hint: 对于所有测试数据，$1 \leq n \leq 100000, n - 1 \leq m \leq min(200000, \frac {n(n -1)} {2}),1 \leq x, y, u_i, v_i \leq n$


title: [HNOI2016] 大数

description: 小 B 有一个很大的数 $S$，长度达到了 $n$ 位；这个数可以看成是一个数字串，它可能有前导 $0$，例如 `00009312345`。小 B 还有一个素数 $p$。现在，小 B 提出了 $m$ 个询问，每个询问求 $S$ 的一个子串中有多少子串是 $p$ 的倍数（$0$ 也是 $p$ 的倍数）。例如 $S$ 为 `0077` 时，其子串 `007` 有 $6$ 个子串：`0,0,7,00,07,007`；显然 `0077` 的子串 `007` 有 $6$ 个子串都是素数 $7$ 的倍数。

inputFormat:
第一行一个整数：$p$。

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

第三行一个整数：$m$。接下来 $m$ 行，每行两个整数 $fr,to$，表示对 $S$ 的子串 $S[fr\dots to]$ 的一次询问。注意：$S$ 的最左端的数字的位置序号为 $1$；例如 $S$ 为 `213567`，则 $S[1\dots 3]$ 为 `213`。

outputFormat: 输出 $m$ 行，每行一个整数，第 $i$ 行是第 $i$ 个询问的答案。

hint:
#### 样例 1 解释

第一个询问问的是整个串，满足条件的子串分别有：`121121,2112,11,121,121`。

#### 数据范围

对于 $100\%$ 的数据，$1\le n,m\le 2\times 10^5$，$2\le p\le 10^9$，$S$ 中只有数字字符，$p$ 为素数。


title: [HNOI2016] 序列

description:
给定长度为 $ n $ 的序列：$ a_1, a_2, \cdots , a_n $，记为 $ a[1 \colon n] $。类似地，$ a[l \colon r] $（$ 1 \leq l \leq r \leq N$）是指序列：$ a_{l}, a_{l+1}, \cdots ,a_{r-1}, a_r$。若 $1\leq l \leq s \leq t \leq r \leq n$，则称 $ a[s \colon t] $ 是 $ a[l \colon r] $ 的子序列。

现在有 $ q $ 个询问，每个询问给定两个数 $ l $ 和 $ r $，$ 1 \leq l \leq r \leq n $，求 $ a[l \colon r] $ 的不同子序列的最小值之和。例如，给定序列
 $ 5, 2, 4, 1, 3 $，询问给定的两个数为 $ 1 $ 和 $ 3 $，那么 $ a[1 \colon 3] $ 有 $ 6 $ 个子序列 $a[1 \colon 1], a[2 \colon 2], a[3 \colon 3], a[1 \colon 2],a[2 \colon 3], a[1 \colon 3] $，这 $6 $ 个子序列的最小值之和为 $5+2+4+2+2+2=17$。

inputFormat:
输入文件的第一行包含两个整数 $ n $ 和 $ q $，分别代表序列长度和询问数。

接下来一行，包含 $ n $ 个整数，以空格隔开，第 $ i $ 个整数为 $ a_i $，即序列第 $i$ 个元素的值。

接下来 $ q $ 行，每行包含两个整数 $ l $ 和 $ r $，代表一次询问。

outputFormat: 对于每次询问，输出一行，代表询问的答案。


title: [HNOI2016] 最小公倍数

description:
给定一张 $N$ 个顶点 $M$ 条边的无向图(顶点编号为 $1,2,\ldots,n$)，每条边上带有权值。所有权值都可以分解成 $2^a\times 3^b$ 的形式。

现在有 $q$ 个询问，每次询问给定四个参数 $u,v,a$ 和 $b$，请你求出是否存在一条顶点 $u$ 到 $v$ 之间的路径，使得路径依次经过的边上的权值的最小公倍数为 $2^a\times 3^b$。

注意：路径可以不是简单路径。

下面是一些可能有用的定义，如果与其它地方定义不同，在本题中以下面的定义为准：

最小公倍数： $ k $ 个数 $ a_1 , a_2, \ldots, a_k $ 的最小公倍数是能被每个 $a_i$ 整除的最小正整数。

路径：顶点序列 $ P \colon P_1,P_2,\ldots,P_k $ 是一条路径，当且仅当 $k \geq 2$，且对于任意 $ 1 \leq i < k $ ，节点 $ P_i $ 和 $ P_{i+1} $ 之间都有边相连。

简单路径：如果路径 $ P \colon P_1,P_2,\ldots,P_k $ 中，对于任意 $ 1 \leq s \neq t \leq k $ 都有 $ P_s \neq P_t $ ，那么称 $P$ 为简单路径。

inputFormat:
输入文件的第一行包含两个整数 $N$ 和 $M$，分别代表图的顶点数和边数。

接下来 $M$ 行，每行包含四个整数 $u,v,a,b$ 代表一条顶点 $u$ 和 $v$ 之间、权值为 $2^a\times 3^b$ 的边。

接下来一行包含一个整数 $q$，代表询问数。

接下来 $q$ 行，每行包含四个整数 $u,v,a$ 和 $b$，代表一次询问。询问内容请参见问题描述。

outputFormat: 对于每次询问，如果存在满足条件的路径，则输出一行 `Yes`，否则输出一行 `No`（注意：第一个字母大写，其余字母小写）。


title: [HNOI2016] 树

description:
小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为 $N$ 的树，结点的编号为 $1,2,...,N$，其中结点 $1$ 为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下：

1. 将模板树复制为初始的大树。

2. 以下(2.1)(2.2)(2.3)步循环执行 $M$ 次

（2.1）选择两个数字 $a,b$，其中 $1 \leq a \leq N, 1 \leq b \leq \text{当前大树的结点数}$。

（2.2）将模板树中以结点 $a$ 为根的子树复制一遍，挂到大树中结点 $b$ 的下方(也就是说，模板树中的结点 $a$ 为根的子树复制到大树中后，将成为大树中结点 $b$ 的子树)。

（2.3）将新加入大树的结点按照在模板树中编号的顺序重新编号。例如，假设在进行2.2步之前大树有 $L$ 个结点，模板树中以 $a$ 为根的子树共有 $C$ 个结点，那么新加入模板树的 $C$ 个结点在大树中的编号将是 $L+1,L+2,...,L+C$ ；大树中这C个结点编号的大小顺序和模板树中对应的 $C$ 个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图：![](https://cdn.luogu.com.cn/upload/image_hosting/mchs3i55.png)

根据第(1)步，初始的大树与模板树是相同的。

在(2.1)步，假设选择了 $a=4, b=3$。运行(2.2)和(2.3)后，得到新的大树如下图所示

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

现在他想问你，树中一些结点对的距离是多少。

inputFormat:
第一行三个整数：$N,M,Q$，以空格隔开，$N$ 表示模板树结点数，$M$ 表示第(2)中的循环操作的次数，$Q$ 表示询问数量。

接下来 $N-1$ 行，每行两个整数 $fr,to$，表示模板树中的一条树边。

再接下来$M$行，每行两个整数$x,to$，表示将模板树中 $x$ 为根的子树复制到大树中成为结点 $to$ 的子树的一次操作。

再接下来 $Q$ 行，每行两个整数 $fr,to$，表示询问大树中结点 $fr$ 和 $to$ 之间的距离是多少。

$N,M,Q \leq 100000$

outputFormat: 输出 $Q$ 行，每行一个整数，第 $i$ 行是第 $i$ 个询问的答案。

hint:
经过两次操作后，大树变成了下图所示的形状：

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

结点6到9之间经过了6条边，所以距离为6；类似地，结点1到8之间经过了3条边；结点5到3之间也经过了3条边。


title: [HNOI2016] 矿区

description:
平面上的矿区划分成了若干个开发区域。

简单地说，你可以将矿区看成一张连通的平面图，平面图划分为了若干平面块，每个平面块即为一个开发区域，平面块之间的边界必定由若干整点(坐标值为整数的点)和连接这些整点的线段组成。每个开发区域的矿量与该开发区域的面积有关：具体而言，面积为 $ s $ 的开发区域的矿量为 $ s^2 $。

现在有 $ m $ 个开采计划。每个开采计划都指定了一个由若干开发区域组成的多边形，一个开采计划的优先度被规定为矿量的总和÷开发区域的面积和；例如，若某开采计划指定两个开发区域，面积分别为 $ a $ 和 $ b $，则优先度为 $ (a^2+b^2)/(a+b) $。由于平面图是按照划分开发区域边界的点和边给出的，因此每个开采计划也只说明了其指定多边形的边界，并未详细指明是哪些开发区域（但很明显，只要给出了多边形的边界就可以求出是些开发区域）。

你的任务是求出每个开采计划的优先度。为了避免精度问题，你的答案必须按照分数的格式输出，即求出分子和分母，且必须是最简形式（分子和分母都为整数，而且都消除了最大公约数；例如，若矿量总和是 $ 1.5 $，面积和是 $ 2 $，那么分子应为 $ 3 $，分母应为 $ 4 $；又如，若矿量和是 $ 2 $，面积和是 $ 4 $，那么分子应为
 $ 1 $，分母应为 $ 2 $）。

由于某些原因，你必须依次对每个开采计划求解（即下一个开采计划会按一定格式加密，加密的方式与上一个开采计划的答案有关）。具体的加密方式见输入格式。

inputFormat:
第一行三个正整数 $ n, m, k $，分别描述平面图中的点和边，以及开采计划的个数。

接下来 $ n $ 行，第 $ i $ 行 ( $ i = 1, 2, \cdots , n $)有两个整数 $x_i, y_i$,  表示点 $ i $ 的坐标为 $(x_i, y_i)$。

接下来 $ m $ 行，第 $ i $ 行有两个正整数 $a, b$，表示点 $ a $ 和 $ b $ 之间有一条边。

接下来一行若干个整数，依次描述每个开采计划。每个开采计划的第一个数 $ c $ 指出该开采计划由开发区域组成的多边形边界上的点的个数为 $ d=(c+P) \bmod n \mathrel{+} 1 $；接下来 $ d $ 个整数，按逆时针方向描述边界上的每一个点：设其中第 $ i $ 个数为 $ z_i $，则第 $ i $ 个点的编号为 $(z_i+P)\bmod n \mathrel{+} 1$。其中 $ P $ 是上一个开采计划的答案中分子的值；对于第 $ 1 $ 个开采计划，$ P = 0 $。

outputFormat: 对于每个开采计划，输出一行两个正整数，分别描述分子和分母。

hint:
### 样例解释

输入文件给出的 $9$ 个点和 $14$ 条边描述的平面图如下所示：

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

第一个开采计划，输入的第 $1$ 个值为 $3$，所以该开采计划对应的多边形有 $(3+0)\bmod 8+1=4$ 个点，将接下的 $4$ 个数 $3,0,4,7$，分别代入 $(z_i+0)\bmod n+1$ 得到 $4$ 个点的编号为 $4,1,5,8$。计算出第一个开采计划的分子为 $1$，分母为 $1$。

类似地，可计算出余下开采计划的多边形的点数和点的编号：第二个开采计划对应的多边形有 $3$ 个点，编号分别为 $5,6,8$。第三个开采计划对应的多边形有 $6$ 个点，编号分别为 $1,2,6,5,8,4$。第四个开采计划对应的多边形有 $5$ 个点，编号分别为 $1,2,6,8,4$。第五个开采计划对应的多边形有 $6$ 个点，编号分别为 $1,5,6,8,7,4$。

### 数据范围及约定

对于 $ 100 \% $ 的数据，$ n, k \leq 2 \times 10^5, \  m \leq 3n-6, \  |x_i|, |y_i| \leq 3×10^4$。

所有开采计划的 $ d $ 之和不超过 $2 \times 10^6$。保证任何开采计划都包含至少一个开发区域，且这些开发区域构成一个连通块。

保证所有开发区域的矿量和不超过 $ 2^{63}-1 $。

保证平面图中没有多余的点和边。

保证数据合法。由于输入数据量较大，建议使用读入优化。


title: [HNOI2016] 网络

description:
一个简单的网络系统可以被描述成一棵无根树。每个节点为一个服务器。连接服务器与服务器的数据线则看做一条树边。两个服务器进行数据的交互时，数据会经过连接这两个服务器的路径上的所有服务器（包括这两个服务器自身）。

由于这条路径是唯一的，当路径上的某个服务器出现故障，无法正常运行时，数据便无法交互。此外，每个数据交互请求都有一个重要度，越重要的请求显然需要得到越高的优先处理权。现在，你作为一个网络系统的管理员，要监控整个系统的运行状态。系统的运行也是很简单的，在每一个时刻，只有可能出现下列三种事件中的一种：

1. 在某两个服务器之间出现一条新的数据交互请求；
2. 某个数据交互结束请求；
3. 某个服务器出现故障。系统会在任何故障发生后立即修复。也就是在出现故障的时刻之后，这个服务器依然是正常的。但在服务器产生故障时依然会对需要经过该服务器的数据交互请求造成影响。

你的任务是在每次出现故障时，维护未被影响的请求中重要度的最大值。注意，如果一个数据交互请求已经结束，则不将其纳入未被影响的请求范围。

inputFormat:
第一行两个正整数 $n,m$，分别描述服务器和事件个数。服务器编号是从 $1$ 开始的，因此 $n$ 个服务器的编号依次是 $1,2,3,\cdots,n$。

接下来 $n-1$ 行，每行两个正整数 $u,v$，描述一条树边。$u$ 和 $v$ 是服务器的编号。

接下来 $m$ 行，按发生时刻依次描述每一个事件；即第 $i$ 行（$i=1,2,3,...,m$）描述时刻 $i$ 发生的事件。每行的第一个数 $\mathrm{type}$ 描述事件类型，共 $3$ 种类型：

1. 若 $\mathrm{type}=0$，之后有三个正整数 $a,b,v$，表示服务器 $a,b$ 之间出现一条重要度为 $v$ 的数据交互请求；
2. 若 $\mathrm{type}=1$，之后有一个正整数 $t$，表示时刻 $t$（也就是第 $t$ 个发生的事件）出现的数据交互请求结束；
3. 若 $\mathrm{type}=2$，之后有一个正整数 $x$，表示服务器 $x$ 在这一时刻出现了故障。

对于每个 $\mathrm{type}$ 为 $2$ 的事件，就是一次询问，即询问“当服务器 $x$ 发生故障时，未被影响的请求中重要度的最大值是多少？”注意可能有某个服务器自身与自身进行数据交互的情况。$2 \le n \le 10^5$，$1 \le m \le 2\times 10^5$，其他的所有输入值不超过 $10^9$。

outputFormat: 对于每个 $\mathrm{type}=2$ 的事件，即服务器出现故障的事件，输出一行一个整数，描述未被影响的请求中重要度的最大值。如果此时没有任何请求，或者所有请求均被影响，则输出 $-1$。

hint:
样例给出的树如下所示：

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

解释其中的部分询问；下面的解释中用 $(a,b;t,v)$ 表示在 $t$ 时刻出现的服务器 $a$ 和 $b$ 之间的重要度为 $v$ 的请求：

对于第一个询问（在时刻 $1$），此时没有任何请求，输出 $-1$。

对于第四个询问（在时刻 $6$），此时有两条交互$(8,13;2,3),(9,12;3,5)$，所有询问均经过 $2$ 号服务器，输出 $-1$。

对于第五个询问（在时刻 $8$），此时有三条交互 $(8,13;2,3),(9,12;3,5),(10,12;7,1)$，只有交互 $(10,12;7,1)$ 没有经过 $2$ 号服务器，因此输出其重要度 $1$。

对于最后一个询问（在时刻 $23$），此时有三条交互 $(9,5;12,6),(9,12;16,4),(10,5;17,7)$。当 $3$ 号服务器出现故障时，只有交互 $(9,5;12,6)$ 没有经过 $3$ 号服务器，因此输出 $6$。

$\text{upd 2016.5.20}$：新加一组 $\text{Hack}$ 数据。


title: [JLOI2012] 时间流逝

description:
生活可以很简单。可以探索水底世界的神秘，也可以去发现奇特新生物，亦或踏上一段新生的旅程。在必须要迎接挑战或跟周围的生物进行生存争夺之前，享受自由的飞翔。此时你会觉得生活是如此美好。

像蛇喜欢吃浮游生物一样（哦，我好像忘记告诉你这个常识），每天，你可以吃一些你周围的基础生物，然后会在你的尾巴上得到一个能量圈。你将会有好多种不同的能量圈，每一个都会被赋予一个能量。你可以拥有多个同种的能量圈，但是对于新得到的相同的能量圈，它的能量不能大于你已拥有的任何一个能量圈。除了前面的规则，获得新的能量圈的种类的概率是一样的。一天天过去，你得到越来越多的能量，开始了进化演变。

但是你也有自己的问题，有时你会面对邪恶的果冻鱼。它会追着你咬你，你不得不扔出最小能量值的能量圈然后赶忙逃跑。在这种情况下，你不会有任何的胃口了，因此这天你将不再得到任何能量圈。幸好，当你没有任何能量圈的时候，果冻鱼就算看见你也不会追着你，此时你可以好好地享用美食。

你听说当你的总的能量值超过了某个阈值之后，可以进化成强大模式并能够吃掉果冻鱼。是时候反击了！下面是本题的问题：预计要过多少天你才能进化成强大模式？（第一天默认你没有任何能量圈）

inputFormat: 输入包含多个测例。对每个测例会有两行。第一行是一个浮点数P，一个整数T和一个整数N。P是每天遇到果冻鱼的概率，T是阈值。第二行是N个不同的正整数，表示每一种能量圈的能量值。

outputFormat: 对于每个测例，输出一行表示预计要过多少天你的能量值能够超过阈值，四舍五入到三位小数。


title: [JLOI2012] 树

description: 在这个问题中，给定一个值 $s$ 和一棵树。在树的每个节点有一个权值，第 $i$ 个点的权值为 $a_i$，问有多少条路径的节点权值总和为 $s$。路径中节点的深度必须是升序的。假设节点 $1$ 是根节点，根的深度是 $0$，它的儿子节点的深度为 $1$。路径不必一定从根节点开始。

inputFormat:
第一行有两个整数 $n$ 和 $s$，其中 $n$ 是树的节点数。

第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示节点 $i$ 的权值。

接下来的 $(n-1)$ 行，每行有两个个整数 $x$ 和 $y$，表示 $y$ 是 $x$ 的儿子。

outputFormat: 输出路径节点总和为 $s$ 的路径数量。

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

- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq a_i, s \leq 10^3$。


title: [JLOI2013] 删除物品

description:
箱子再分配问题需要解决如下问题：

1. 一共有 $N$ 个物品，堆成 $M$ 堆。

2. 所有物品都是一样的，但是它们有不同的优先级。

3. 你只能够移动某堆中位于顶端的物品。

4. 你可以把任意一堆中位于顶端的物品移动到其它某堆的顶端。若此物品是当前所有物品中优先级最高的，可以直接将之删除而不用移动。

5. 求出将所有物品删除所需的最小步数。删除操作不计入步数之中。

6. 这是一个比较难解决的问题，这里你只需要解决一个比较简单的版本：不会有两个物品有着相同的优先级，且 $M=2$。

inputFormat: 第一行是包含两个整数 $N_1$, $N_2$ 分别表示两堆物品的个数。接下来有 $N_1$ 行整数按照从顶到底的顺序分别给出了第一堆物品中的优先级，数字越大，优先级越高。再接下来的 $N_2$ 行按照同样的格式给出了第二堆物品的优先级。

outputFormat: 对于每个数据，请输出一个整数，即最小移动步数。


title: 圆桌问题

description:
有来自 $m$ 个不同单位的代表参加一次国际会议。第 $i$ 个单位派出了 $r_i$ 个代表。

会议的餐厅共有 $n$ 张餐桌，第 $i$ 张餐桌可容纳 $c_i$ 个代表就餐。

为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。

inputFormat:
输入的第一行是用空格隔开的两个整数，分别代表单位的个数 $m$ 和餐桌的个数 $n$。
第二行有 $m$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 个单位的代表人数 $r_i$。
第三行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 张餐桌能容纳的人数 $c_i$。

outputFormat:
**本题存在 Special Judge**。
请输出是否存在满足要求的就餐方案，若存在，请给出任意一种可行的方案。
输出的第一行是一个非 $0$ 即 $1$ 的整数，若存在方案则输出 $1$，否则输出 $0$。
若存在方案，则对于第 $2$ 到第 $(m + 1)$ 行，在第 $(i + 1)$ 行输出 $r_i$ 个整数，代表第 $i$ 个单位的代表就餐的餐桌编号。

hint:
**【数据规模与约定】**

- 对于 $100\%$ 的数据，保证 $1 \leq m \leq 150$，$1 \leq n \leq 270$，$1 \leq r_i, c_i \leq 10^3$。

**【提示】**

- 请注意输入的第一行先读入 $m$ 再读入 $n$。

tags: 网络流与线性规划 24 题


title: [JLOI2013] 地形生成

description:
最近IK正在做关于地形建模的工作。其中一个工作阶段就是把一些山排列成一行。每座山都有各不相同的标号和高度。为了遵从一些设计上的要求，每座山都设置了一个关键数字，要求对于每座山，比它高且排列在它前面的其它山的数目必须少于它的关键数字。 显然满足要求的排列会有很多个。

对于每一个可能的排列，IK生成一个对应的标号序列和等高线序列。标号序列就是按顺序写下每座山的标号。

等高线序列就是按顺序写下它们的高度。例如有两座山，这两座山的一个合法排列的第一座山的标号和高度为1和3，而第二座山的标号和高度分别为2和4，那么这个排列的标号序列就是1 2，而等高线序列就是3 4.

现在问题就是，给出所有山的信息，IK希望知道一共有多少种不同的符合条件的标号序列和等高线序列。

inputFormat: 输入第一行给出山的个数N。接下来N行每行有两个整数，按照标号从1到N的顺序分别给出一座山的高度和关键数。

outputFormat: 输出两个用空格分隔开的数，第一个数是不同的标号序列的个数，第二个数是不同的等高线序列的个数。这两个答案都应该对2011取模，即输出两个答案除以2011取余数的结果

hint: 对于所有的数据，有1<=N<=1000，所有的数字都是不大于109的正整数。


title: [JLOI2013] 赛车

description: 这里有一辆赛车比赛正在进行，赛场上一共有 $n$ 辆车，分别称为个 $g_1,g_2,...,g_n$。赛道是一条无限长的直线。最初，$g_i$ 位于距离起跑线前进 $k_i$ 的位置。比赛开始后，车辆 $g_i$ 将会以 $v_i$ 单位每秒的恒定速度行驶。在这个比赛过程中，如果一辆赛车曾经处于领跑位置的话（即没有其他的赛车跑在他的前面），这辆赛车最后就可以得奖，而且比赛过程中不用担心相撞的问题。现在给出所有赛车的起始位置和速度，你的任务就是算出那些赛车将会得奖。

inputFormat:
第一行有一个正整数 $n$，表示赛车的个数。

接下来一行，包含 $n$ 个整数，按顺序给出 $n$ 辆赛车的起始位置。再接下来一行给出 $n$ 个整数，按顺序给出 $n$ 辆赛车的恒定速度。

outputFormat: 输出包括两行，第一行为获奖的赛车个数。第二行按从小到大的顺序输出获奖赛车的编号，编号之间用空格隔开，注意最后一个编号后面不要加空格。


title: [JLOI2014] 天天酷跑

description:
在游戏天天酷跑中，最爽的应该是超级奖励模式了吧，没有一切障碍，可以尽情的吃金币，现在请你控制游戏角色来获得尽可能多的分数。游戏界面离散为一个长度为 $1 \sim n$，高度为 $1 \sim m$（初始点为 $(0,1)$）的矩阵图。每个格子上都有收益 $(-1 \sim 1000)$，$-1$ 表示该点不能通过。游戏角色从起点一路奔跑向终点，中途可以跳跃来获得更高的分数，在空中还能进行连跳。

游戏开始前你可以设定跳跃的高度，以及能连跳的次数，初始跳跃高度为 $1$，连跳数为 $1$（最多为 $5$），升级跳跃高度和连跳都需要一定的花费。跳跃高度设定完后游戏角色每次跳跃高度都将固定，连跳必须在下落过程中可以使用。所有操作都将在整点上完成，需要保证设定完的跳跃高度及连跳数，无法跳出游戏高度上限。

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

从 $(1,1)$ 点用一次跳跃，一次经过 $(2,2),(3,3),(4,2),(5,1)$。

以下是连跳数为 $2$ 连跳，跳跃高度为 $2$ 的跳跃方案：

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

从 $(1,1)$ 起跳，依次经过 $(2,2),(3,3),(4,2)$ 再使用连跳，经过 $(5,3),(6,4),(7,3),(8,2),(9,1)$。

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

inputFormat:
第一行四个整数 $n,m,cost_1,cost_2$。$n,m$ 如题意所示，$cost_1,cost_2$ 分别表示每升一级跳跃高度，连跳数所需的花费。

接下来 $m$ 行，每行 $n$ 个数。第 $i$ 行第 $j$ 个数表示地图中高度为 $i$，长度在第 $j$ 列处的收益。

outputFormat: 如果无法跑出终点线，就输出 `mission failed`，否则输出一行三个数，分别表示最大收益；及最大收益时，最小的连跳数；最大收益，最小连跳数时，最小的跳跃高度。


title: [JLOI2014] 松鼠的新家

description:
松鼠的新家是一棵树，前几天刚刚装修了新家，新家有$n$ 个房间，并且有 $n-1$ 根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。

松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去 $a_1$，再去 $a_2$，……，最后到 $a_n$，去参观新家。可是这样会导致重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。

维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。

因为松鼠参观指南上的最后一个房间 $a_n$ 是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

inputFormat:
第一行一个正整数 $n$，表示房间个数第二行 $n$ 个正整数，依次描述 $a_1, a_2,\cdots,a_n$。

接下来 $n-1$ 行，每行两个正整数 $x,y$，表示标号 $x$ 和 $y$ 的两个房间之间有树枝相连。

outputFormat: 一共 $n$ 行，第 $i$ 行输出标号为 $i$ 的房间至少需要放多少个糖果，才能让维尼有糖果吃。

hint: 对于全部的数据，$2 \le n \le 3 \times 10^5$，$1 \le a_i \le n$。


title: [JLOI2014] 路径规划

description:
相信大家都用过地图上的路径规划功能，只要输入起点终点就能找出一条最优路线。现在告诉你一张地图的信息，请你找出最优路径（即最短路径）。考虑到实际情况，一辆车加满油能开的时间有限，**为 $limit$**，所以在地图上增加了几个加油站。

地图由点和双向边构成，每个点代表一个路口，也有可能是加油站或起点终点。有些路口还装有红绿灯。由于经过太多的红绿灯会让人感到不爽，所以请求在经过不超过 $k$ 个红绿灯的情况下，最少平均花费多少时间能从起点到终点。保证起点终点和加油站没有红绿灯。（题目不考虑最坏情况下能否加到油，只考虑平均花费时间的前提下，车能否到达加油站加油）。

注意：

1. $limit$ 指的是车最多能走多长时间，可以看作车的油箱，是不能叠加的（比如不能连续经过多个加油站后剩余能走的时间 $>limit$）。
2. 与上面类似，一个加油站最多只能加到 $limit$，不能累加。
3. 不管在加油站加多少油，反正加一次耗费的时间都是 $cost$。
4. 经过加油站可以不加油。

inputFormat:
第一行输入 $5$ 个整数 $n,m,k,limit,cost$，表示有 $n$ 个点 $m$ 条边，车能开 $limit$ 长的时间，及加油所花时间 $cost$。

接下来 $n$ 行输入每个点信息，包括点的名称（带 `gas` 的为加油站，`start` 为起点，`end` 为终点），及该点是否有红绿灯，用 $a,b$ 表示。（若为 $a=0$ 则表示没有，$a$ 表示红灯长，$b$ 表示绿灯长）。

接下来 $m$ 行输入每条边信息，包括边的起点，终点，边的名称，通过该边所花时长。

保证点和边名的长度不大于 $20$，只有大小写字母，数字及 `_` 组成。

outputFormat: 一行输出最少平均花费时长。

samples:
5 8 1 100 10
start 0 0
azhan 10 10
xxgasxx 0 5
bpoint 20 5
end 0 100
start azhan sdf 30
azhan xxgasxx ewfg 20
start end r3tg 200
end azhan 1xq2 70
azhan bpoint gg 10
xxgasxx bpoint kk 30
bpoint end dsg 40
xxgasxx end t_s 100

hint:
共 $14$ 组数据。

- 其中 $3$ 组数据，满足 $1 \le n<10$，$1 \le m<20$，$1 \le k<5$。
- 另有 $3$ 组没有红绿灯。

所有数据满足 $1 \le n \le 10000$，$1 \le m \le 20000$，$1 \le k \le 10$，加油站 $\le 50$。


title: [JLOI2014] 镜面通道

description:
在一个二维平面上，有一个镜面通道，由镜面 $AC, BD$ 组成，$AC, BD$ 长度相等，且都平行于 $x$ 轴，$B$ 位于 $(0,0)$。

通道中有 $n$ 个外表面为镜面的光学元件，光学元件 $\alpha$ 为圆形，光学元件 $\beta$ 为矩形（这些元件可以与其他元件和通道有交集，具体看下图）。光线可以在 $AB$ 上任一点以任意角度射入通道，光线不会发生削弱。当出现元件与元件，元件和通道刚好接触的情况视为光线无法透过（比如两圆相切）。

现在给出通道中所有元件的信息（$\alpha$ 元件包括圆心坐标和半径 $x_i, y_i, r_i$，$\beta$ 元件包括左下角和右上角坐标 $x_1, y_1, x_2, y_2$）

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

如上图，$S$ 到 $T$ 便是一条合法线路。

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

当然，显然存在光线无法透过的情况，现在交给你一个艰巨的任务，请求出至少拿走多少个光学元件后，存在一条光线线路可以从 $CD$ 射出。

下面举例说明：

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

现在假设，取走中间那个矩形，那么就可以构造出一条穿过通道的光路，如图中的 $S$ 到 $T$。

inputFormat:
第一行包含两个整数，$x, y$，表示 $C$ 点坐标。

第二行包含一个数字 $n$，表示有 $n$ 个光学元件。

接下来 $n$ 行第一个数字如果是 $1$，表示元件 $\alpha$，后面会有三个整数 $x_i, y_i, r_i$ 分别表示圆心坐标和半径。第一个数字如果是 $2$，表示元件 $\beta$，后面会有四个整数 $x_1, y_1, x_2, y_2$ 分别表示左下角和右上角坐标。（矩形都平行，垂直于坐标轴）

outputFormat: 输出包含一行，至少需要拿走的光学元件个数 $m$。


title: [JLOI2015] 城池攻占

description:
小铭铭最近获得了一副新的桌游，游戏中需要用 $m$ 个骑士攻占 $n$ 个城池。

这 $n$ 个城池用 $1$ 到 $n$ 的整数表示。除 $1$ 号城池外，城池 $i$ 会受到另一座城池 $f_i$ 的管辖，其中 $f_i<i$。也就是说，所有城池构成了一棵有根树。

这 $m$ 个骑士用 $1$ 到 $m$ 的整数表示，其中第 $i$ 个骑士的初始战斗力为 $s_i$，第一个攻击的城池为 $c_i$。

每个城池有一个防御值 $h_i$，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可以占领这座城池；否则占领失败，骑士将在这座城池牺牲。占领一个城池以后，骑士的战斗力将发生变化，然后继续攻击管辖这座城池的城池，直到占领 $1$ 号城池，或牺牲为止。

除 $1$ 号城池外，每个城池 $i$ 会给出一个战斗力变化参数 $(a_i,v_i)$。若 $a_i=0$，攻占城池 $i$ 以后骑士战斗力会增加 $v_i$；若 $a_i=1$，攻占城池 $i$ 以后，战斗力会乘以 $v_i$。

注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。

现在的问题是，对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。

inputFormat:
第 $1$ 行包含两个正整数 $n,m$，表示城池的数量和骑士的数量。

第 $2$ 行包含 $n$ 个整数，其中第 $i$ 个数为 $h_i$，表示城池 $i$ 的防御值。

第 $3\sim n+1$ 行，每行包含三个整数。其中第 $i+1$ 行的三个数为 $f_i,a_i,v_i$，分别表示管辖这座城池的城池编号和两个战斗力变化参数。

第 $n+2\sim n+m+1$ 行，每行包含两个整数。其中第 $n+i$ 行的两个数为 $s_i,c_i$，分别表示初始战斗力和第一个攻击的城池。

outputFormat: 输出 $n+m$ 行，每行包含一个非负整数。其中前 $n$ 行分别表示在城池 $1$ 到 $n$ 牺牲的骑士数量，后 $m$ 行分别表示骑士 $1$ 到 $m$ 攻占的城池数量。


title: [JLOI2015] 战争调度

description:
脸哥最近来到了一个神奇的王国，王国里的公民每个公民有两个下属或者没有下属，这种关系刚好组成一个 $n$ 层的完全二叉树。公民 $i$ 的下属是 $2i$ 和 $2i +1$。最下层的公民即叶子节点的公民是平民，平民没有下属，最上层的是国王，中间是各级贵族。

现在这个王国爆发了战争，国王需要决定每一个平民是去种地以供应粮食还是参加战争，每一个贵族（包括国王自己）是去管理后勤还是领兵打仗。一个平民会对他的所有直系上司有贡献度，若一个平民 $i$ 参加战争，他的某个直系上司 $j$ 领兵打仗，那么这个平民对上司的作战贡献度为 $w_{ij}$。若一个平民 $i$ 种地，他的某个直系上司 $j$ 管理后勤，那么这个平民对上司的后勤贡献度为 $f_{ij}$，若 $i$ 和 $j$ 所参加的事务不同，则没有贡献度。为了战争需要保障后勤，国王还要求不多于 $m$ 个平民参加战争。

国王想要使整个王国所有贵族得到的贡献度最大，并把这件事交给了脸哥。但不幸的是，脸哥还有很多 deadline 没有完成，他只能把这件事又转交给你。你能帮他安排吗？

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

接下来 $2^{n-1}$ 行，每行 $n-1$ 个数，第 $i$ 行表示编号为 $2^{n-1}-1+ i$ 的平民对其 $n-1$ 个直系上司的作战贡献度，其中第一个数表示对第一级直系上司，即编号为 $\frac{2^{n-1}-1+ i}{2}$ 的贵族的作战贡献度 $w_{ij}$，依次往上。

接下来 $2^{n-1}$ 行，每行 $n-1$ 个数，第 $i$ 行表示编号为 $2^{n-1}-1+ i$ 的平民对其 $n-1$ 个直系上司的后勤贡献度，其中第一个数表示对第一级直系上司，即编号为 $\frac{2^{n-1}-1+ i}{2}$ 的贵族的后勤贡献度 $f_{ij}$ ，依次往上。

outputFormat: 一行一个数表示满足条件的最大贡献值。


title: [JLOI2015] 有意义的字符串

description:
B 君有两个好朋友，他们叫宁宁和冉冉。有一天，冉冉遇到了一个有趣的题目：输入三个非负整数 $b,d,n$，求

$$\left\lfloor \left ( \frac{b+\sqrt{d}}{2} \right ) ^n \right\rfloor \bmod p$$

其中 $p=7,528,443,412,579,576,937$

inputFormat: 一行三个非负整数 $b$，$d$，$n$。


title: [JLOI2015] 管道连接

description:
小铭铭最近进入了某情报部门，该部门正在被如何建立安全的通道连接困扰。该部门有 $n$ 个情报站，用 $1$ 到 $n$ 的整数编号。给出 $m$ 对情报站 $(u_i,v_i)$ 和费用 $w_i$，表示情报站 $u_i$ 和 $v_i$ 之间可以花费 $w_i$ 单位资源建立通道。

如果一个情报站经过若干个建立好的通道可以到达另外一个情报站，那么这两个情报站就建立了通道连接。形式化地，若 $u_i$ 和 $v_i$ 建立了通道，那么它们建立了通道连接；若 $u_i$ 和 $v_i$ 均与 $t_i$ 建立了通道连接，那么 $u_i$ 和 $v_i$ 也建立了通道连接。

现在在所有的情报站中，有 $p$ 个重要情报站，其中每个情报站有一个特定的频道。小铭铭面临的问题是，需要花费最少的资源，使得任意相同频道的情报站之间都建立通道连接。

inputFormat:
第一行包含三个整数 $n,m,p$，表示情报站的数量，可以建立的通道数量和重要情报站的数量。

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,w_i$，表示可以建立的通道。

最后有 $p$ 行，每行包含两个整数 $c_i,d_i$，表示重要情报站的频道和情报站的编号。

outputFormat: 输出一行一个整数，表示任意相同频道的情报站之间都建立通道连接所花费的最少资源总量。


title: [JLOI2015] 装备购买

description:
脸哥最近在玩一款神奇的游戏，这个游戏里有 $n$ 件装备，每件装备有 $m$ 个属性，用向量 $\mathbf{z_i}=(a_1, \ldots ,a_j, \ldots , a_m)$ 表示 ($1 \leq i \leq n, \ 1 \leq j \leq m$)，每个装备需要花费 $c_i$，现在脸哥想买一些装备，但是脸哥很穷，所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。对于脸哥来说，如果一件装备的属性能用购买的其他装备组合出（也就是说脸哥可以利用手上的这些装备组合出这件装备的效果），那么这件装备就没有买的必要了。

严格的定义是，如果脸哥买了 $\mathbf{z_{i_1}}, \ldots , \mathbf{z_{i_p}}$这 $p$ 件装备，那么对于任意待决定的 $\mathbf{z_h}$，不存在 $b_1, \ldots ,b_p$使得 $b_1\mathbf{z_{i_1}} + \ldots + b_p\mathbf{z_{i_p}} = \mathbf{z_h}$
 （$b_i$均是实数），那么脸哥就会买 $\mathbf{z_h}$，否则 $\mathbf{z_h}$ 对脸哥就是无用的了，自然不必购买。

举个例子，$\mathbf{z_1}=(1, 2, 3), \ \mathbf{z_2}=(3, 4, 5), \ \mathbf{z_h}=(2, 3, 4), \ b_1 =\frac{1}{2}, \ b_2 =\frac{1}{2}$，就有 $b_1\mathbf{z_1} + b_2\mathbf{z_2} = \mathbf{z_h}$ ，那么如果脸哥买了 $\mathbf{z_1}$和 $\mathbf{z_2}$ 就不会再买 $\mathbf{z_h}$了。

脸哥想要在买下最多数量的装备的情况下花最少的钱，你能帮他算一下吗？

inputFormat: 第一行两个数 $n,m$。接下来 $n$ 行，每行 $m$ 个数，其中第 $i$ 行描述装备 $i$ 的各项属性值。接下来一行 $n$ 个数，其中 $c_i$ 表示购买第 $i$ 件装备的花费。

outputFormat: 一行两个数，第一个数表示能够购买的最多装备数量，第二个数表示在购买最多数量的装备的情况下的最小花费。

hint:
如题目中描述，选择装备 $1$ 装备 $2$，装备 $1$ 装备 $3$，装备 $2$ 装备 $3$ 均可，但选择装备 $1$ 和装备 $2$ 的花费最小，为 $2$。

对于 $100\%$ 的数据 $,1 \le n,m \le 500$，$0 \le a_j \le 1000$。


title: [JLOI2015] 骗我呢

description:
说起来，毕业之后 B 君也就见过 R 君两面而已。
R 君有一个 $n \times m$ 的数组 $x_{i,j}(1 \le i \le n; 1 \le j \le m)$。
对于 $1 \le i \le n; 1 \le j \le m$，满足$0 \le x_{i,j} \le m$。求 可能的数组$x_{i,j}$ 的解数。
B 君觉得限制太宽松，还要求对于 $1 \le i \le n; 1 \le j<m$，满足 $x_{i,j} <x_{i,j+1}$，对于$1 <i \le n; 1 \le j<m$，满足 $x_{i,j} <x_{i-1,j+1}$。
B 君认为 R 君可以直接 pwn 掉这个题。
R 君说：「黑的实在逼真 =.=，你起码把解数模 $10^9+7$ 吧。」B 君觉得 R 君说的有道理，于是想让你求解数模 $10^9+7$ 的结果。

inputFormat: 一行两个整数表示 $n, m$，含义如题目中所述。

outputFormat: 一行一个数表示同时满足 B 君和 R 君的条件 $x_{i,j}$ 的解数，模 $10^9+7$ 的结果。


title: [JLOI2016/SHOI2016] 侦察守卫

description:
小 R 和 B 神正在玩一款游戏。这款游戏的地图由 $N$ 个点和 $N-1$ 条无向边组成，每条无向边连接两个点，且地图是连通的。换句话说，游戏的地图是一棵有 $N$ 个节点的树。

游戏中有一种道具叫做侦查守卫，当一名玩家在一个点上放置侦查守卫后，它可以监视这个点以及与这个点的距离在 $D$ 以内的所有点。这里两个点之间的距离定义为它们在树上的距离，也就是两个点之间唯一的简单路径上所经过边的条数。在一个点上放置侦查守卫需要付出一定的代价，在不同点放置守卫的代价可能不同。

现在小 R 知道了所有 B 神可能会出现的位置，请你计算监视所有这些位置的最小代价。

inputFormat:
第一行包含两个正整数 $N$ 和 $D$，分别表示地图上的点数和侦查守卫的视野范围。约定地图上的点用 $1$ 到 $N$ 的整数编号。

第二行 $N$ 个正整数，第 $i$ 个正整数表示在编号为 $i$ 的点放置侦查守卫的代价 $W _ i$。保证 $W _ i \le 1000$。

第三行一个正整数 $M$，表示 B 神可能出现的点的数量。保证 $M \le N$。

第四行 $M$ 个正整数，分别表示每个 B 神可能出现的点的编号，从小到大不重复地给出。

接下来 $N-1$ 行，每行包含两个正整数 $U,V$，表示在编号为 $U$ 的点和编号为 $V$ 的点之间有一条无向边。

outputFormat: 仅一行一个整数，表示监视所有 B 神可能出现的点所需要的最小代价。

hint: 对于所有的数据，$N \le 5 \times 10 ^ 5,D \le 20$。


title: [JLOI2016] 圆的异或并

description:
在平面直角坐标系中给定 $N$ 个圆。已知这些圆**两两没有交点**，即两圆的关系只存在相离和包含。求这些圆的异或面积并。

异或面积并定义为：当一片区域在奇数个圆内，则计入其面积，否则，当一片区域在偶数个圆内则不计入其面积。

inputFormat:
第一行包含一个正整数 $N$，代表圆的个数。

接下来 $N$ 行，每行 $3$ 个非负整数 $x,y,r$，表示一个圆心在 $(x,y)$，半径为 $r$ 的圆。

数据保证 $|x_i|,|y_i|\le 10^8$，$0<r\leq 10^6$，$1\le N\le 2\times 10^5$。

outputFormat: 仅一行一个整数，表示所有圆的异或面积并除以圆周率 $\pi$ 的结果。


title: [JLOI2016] 字符串覆盖

description: 字符串A有N个子串B1,B2,...,Bn。如果将这n个子串分别放在恰好一个它在A中出现的位置上（子串之间可以重叠）这样A中的若干字符就被这N个子串覆盖了。问A中能被覆盖字符个数的最小值和最大值。

inputFormat:
第一行包含一个正整数T，表示数据组数。保证T<=10。

接下来依次描述T组数据，每组数据中：

第一行包含一个由小写字母组成的字符串，表示母串A。

第二行包含一个整数N，表示子串的个数。

接下来N行，每行包含一个由小写字母组成的字符串，描述子串。数据保证所有子串均在母串中出现。

outputFormat: 输出为T行，对应每组数据的答案。每行包含两个整数Minans和Maxans，分别表示对应数据中能被覆盖字符数量的最小值和最大值。


title: [JLOI2016] 成绩比较

description:
G 系共有 $N$ 位同学，$M$ 门必修课。这 $N$ 位同学的编号为 $0$ 到 $N-1$ 的整数，其中 B 神的编号为 $0$ 号。这 $M$ 门必修课编号为 $0$ 到 $M-1$ 的整数。一位同学在必修课上可以获得的分数是 $1$ 到 $U_i$ 中的一个整数。

如果在每门课上 A 获得的成绩均小于等于 B 获得的成绩，则称 A 被 B 碾压。在 B 神的说法中，G 系共有 $K$ 位同学被他碾压（不包括他自己），而其他 $N-K-1$ 位同学则没有被他碾压。D 神查到了 B 神每门必修课的排名。

这里的排名是指：如果 B 神某门课的排名为 $R$，则表示有且仅有 $R-1$ 位同学这门课的分数大于 B 神的分数，有且仅有 $N-R$ 位同学这门课的分数小于等于 B 神（不包括他自己）。

我们需要求出全系所有同学每门必修课得分的情况数，使其既能满足 B 神的说法，也能符合 D 神查到的排名。这里两种情况不同当且仅当有任意一位同学在任意一门课上获得的分数不同。

你不需要像 D 神那么厉害，你只需要计算出情况数模 $10^9+7$ 的余数就可以了。

inputFormat:
第一行包含三个正整数 $N,M,K$，分别表示 G 系的同学数量（包括 B 神），必修课的数量和被 B 神碾压的同学数量。

第二行包含 $M$ 个正整数，依次表示每门课的最高分 $U_i$。

第三行包含 $M$ 个正整数，依次表示 B 神在每门课上的排名 $R_i$。

数据保证至少有 $1$ 种情况使得 B 神说的话成立。

outputFormat: 仅一行一个正整数，表示满足条件的情况数模 $10^9+7$ 的余数。

hint: $1\leq N\leq 100$，$1\leq M\leq 100$，$1\leq U_i\leq 10^9$，$1\leq R_i\leq N$。


title: [JLOI2016] 方

description:
上帝说，不要圆，要方，于是便有了这道题。

由于我们应该方，而且最好能够尽量方，所以上帝派我们来找正方形上帝把我们派到了一个有 $N$ 行 $M$ 列的方格图上，图上一共有 $(N+1)\times(M+1)$ 个格点，我们需要做的就是找出这些格点形成了多少个正方形（换句话说，正方形的四个顶点都是格点）。

但是这个问题对于我们来说太难了，因为点数太多了，所以上帝删掉了这 $(N+1)\times(M+1)$ 中的 $K$ 个点。既然点变少了，问题也就变简单了，那么这个时候这些格点组成了多少个正方形呢？

inputFormat:
第一行三个整数 $N, M, K$，代表棋盘的行数、 列数和不能选取的顶点个数。保证 $N, M \ge 1$， $K \le (N + 1) \times(M + 1)$。

约定每行的格点从上到下依次用整数 $0$ 到 $N$ 编号，每列的格点依次用 $0$ 到 $M$ 编号。

接下来 $K$ 行，每行两个整数 $x,y$ 代表第 $x$ 行第 $y$ 列的格点被删掉了。

保证 $0 \le x \le N \le 10^6$，$0 \le y \le M \le 10^6$，$K \le 2000$ 且不会出现重复的格点。

outputFormat: 仅一行一个正整数，代表正方形个数对 $100000007 ( 10^8 + 7)$ 取模之后的值。


title: [SCOI2011] 地板

description:
lxhgww 的小名叫“小 L”，这是因为他总是很喜欢 L 型的东西。

小 L 家的客厅是一个 $r\times c$ 的矩形，现在他想用 L 型的地板来铺满整个客厅，客厅里有些位置有柱子，不能铺地板。

现在小 L 想知道，用 L 型的地板铺满整个客厅有多少种不同的方案？

需要注意的是，如下图所示，L 型地板的两端长度可以任意变化，但不能长度为 $0$。

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

铺设完成后，客厅里面所有没有柱子的地方都必须铺上地板，但同一个地方不能被铺多次。

inputFormat:
输入的第一行包含两个整数，$r$ 和 $c$，表示客厅的大小。

接着是 $r$ 行，每行 $c$ 个字符，字符要么是 `_`，要么是 `*`，`_` 表示对应的位置是空的，必须铺地板；`*` 表示对应的位置有柱子，不能铺地板。

outputFormat: 输出一行，包含一个整数，表示铺满整个客厅的方案数。由于这个数可能很大，只需输出它除以 $20110520$ 的余数。


title: [SCOI2011] 棘手的操作

description:
有 $N$ 个节点，标号从 $1$ 到 $N$，这 $N$ 个节点一开始相互不连通。第i个节点的初始权值为 $a_i$，接下来有如下一些操作：
- `U x y`: 加一条边，连接第 $x$ 个节点和第 $y$ 个节点；
- `A1 x v`: 将第 $x$ 个节点的权值增加 $v$；
- `A2 x v`: 将第 $x$ 个节点所在的连通块的所有节点的权值都增加 $v$；
- `A3 v`: 将所有节点的权值都增加 $v$；
- `F1 x`: 输出第 $x$ 个节点当前的权值；
- `F2 x`: 输出第 $x$ 个节点所在的连通块中，权值最大的节点的权值；
- `F3`: 输出所有节点中，权值最大的节点的权值。

inputFormat:
输入的第一行是一个整数 $N$，代表节点个数。接下来一行输入 $N$ 个整数，$a_1,a_2,\dots,a_N$，代表 $N$ 个节点的初始权值。

再下一行输入一个整数 $Q$，代表接下来的操作数。

最后输入 $Q$ 行，每行的格式如题目描述所示。

outputFormat: 对于操作 `F1 x`,`F2 x`,`F3`，输出对应的结果，每个结果占一行。


title: [SCOI2011] 植物大战僵尸

description:
坚果保龄球是植物大战僵尸中的一个小游戏。现在疯狂戴夫只给了 lxhgww 一些最普通的坚果，让 lxhgww 像保龄球一样把坚果扔出去，砸死院子里的僵尸。

院子一共由 $N$ 条轨道组成，从上到下依次编号从 $1$ 到 $N$，每条轨道又被分成若干格。院子里一共有 $M$ 只僵尸，每只僵尸站在某个格子内，并且可以认为它的位置不会变化。

游戏可以分成 $K$ 个回合，在每个回合中，你可以选择一条轨道，把一个坚果扔出去。被扔出去的坚果首先会沿着轨道直线的从左往右滚动，直到撞到第一只僵尸之后，它开始沿着 $45$ 度的斜线滚动，并且向中心的一侧滚动（即前 $N/2$ 行的向右下滚动，后 $N/2$ 行的向右上滚动，题目保证 $N$ 是偶数）。院子的两边是围墙。斜着走的坚果撞到围墙或者僵尸会反弹，即从往右上走变成往右下走，或者反过来。直到坚果不再能打到任何僵尸之后，该回合结束。

注意：多只僵尸可能站在同一格，这个时候坚果每次只会撞死该格子的其中一只僵尸。为了砸死尽量多的僵尸，现在 lxhgww 决定在每回合的开始，选择在当前情况下可以砸死最多僵尸的一条路线扔出坚果。在出现相同的情况时，他会选择编号最小的轨道扔出。

为了了解这个做法的效果，现在 lxhgww 需要你帮助他计算这个方法可以砸死的僵尸数目。

inputFormat: 输入的第一行有 3 个整数，$N$，$M$，$K$。接下来 $M$ 行，每行两个整数 $X_i$, $Y_i$，表示第 $i$ 个僵尸位于第 $Y_i$ 条轨道，从左数第 $X_i$ 个格子中。

outputFormat: 输出数据包括 $K+1$ 行。前 $K$ 行，每行2个数据 $A_i, B_i$，表示在第 $i$ 个回合，从第 $A_i$ 条轨道扔出坚果，这个坚果在运行过程中打到了 $B_i$ 个僵尸。最后一行是一个数字，表示被打到的僵尸总数。

hint:
【数据范围】

对于 $20\%$ 的数据，保证： $N\le200$，$M\le500$，$K\le200$，$X_i\le200$；

对于 $50\%$ 的数据，保证： $N\le200$，$M\le2\times 10^5$，$K\le200$，$X_i\le10^6$；

对于 $100\%$ 的数据，保证： $N\le20000$，$M\le2\times 10^5$，$K\le10^5$，$Xi\le10^6$。

对于所有的数据，保证：$1\le Y_i\le N$。


title: [SCOI2011] 糖果

description: 幼儿园里有 $N$ 个小朋友，$\text{lxhgww}$ 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，$\text{lxhgww}$ 需要满足小朋友们的 $K$ 个要求。幼儿园的糖果总是有限的，$\text{lxhgww}$ 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

inputFormat:
输入的第一行是两个整数 $N$，$K$。接下来 $K$ 行，表示这些点需要满足的关系，每行 $3$ 个数字，$X$，$A$，$B$。

+ 如果 $X=1$， 表示第 $A$ 个小朋友分到的糖果必须和第 $B$ 个小朋友分到的糖果一样多；
+ 如果 $X=2$， 表示第 $A$ 个小朋友分到的糖果必须少于第 $B$ 个小朋友分到的糖果；
+ 如果 $X=3$， 表示第 $A$ 个小朋友分到的糖果必须不少于第 $B$ 个小朋友分到的糖果；
+ 如果 $X=4$， 表示第 $A$ 个小朋友分到的糖果必须多于第 $B$ 个小朋友分到的糖果；
+ 如果 $X=5$， 表示第 $A$ 个小朋友分到的糖果必须不多于第 $B$ 个小朋友分到的糖果；

outputFormat: 输出一行，表示 $\text{lxhgww}$ 老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 $-1$。

hint:
对于 $30\%$ 的数据，保证 $N\leq100$

对于 $100\%$ 的数据，保证 $N\leq100000$

对于所有的数据，保证 $K\leq100000, 1\leq X\leq5, 1\leq A, B\leq N$

---

$\text{upd 2022.7.6}$：新添加 $21$ 组 [Hack 数据](https://www.luogu.com.cn/discuss/454051)。


title: [SCOI2011] 镜像拆分

description: lxhgww 非常喜欢数字游戏，他发现，很多数都可以表示成两个相互反转的数之和，他把这个现象称为数的“镜像拆分”。比如 $66$ 共有五种镜像拆分方法：$66=15+51=24+42=33+33=42+24=51+15$。注意，前导 0 是不允许的，所以 $66=60+06$ 不算做合法的镜像拆分。现在 lxhgww 想知道，在 K 进制下，对于在 $[A,B]$ 区间内的数，其镜像拆分的方案数之和是多少？

inputFormat: 输入的第一行是一个数 $K$。输入的第二行是一个数 $n$，表示数字 $A$ 的长度。接下来 $n$ 行，表示 $A$ 从低位开始的每一位数字。然后是一个数 $m$，表示数字 $B$ 的长度。接下来 $m$ 行，表示 $B$ 从低位开始的每一位数字。

outputFormat: 输出一行，包含一个整数，表示镜像拆分的方案数之和。由于这个答案非常大，只需要输出这个答案除以 $20110521$ 的余数。

hint:
对于 $20\%$ 的数据，保证：$2\le K\le100$，$1\le n,m\le100$。

对于 $50\%$ 的数据，保证：$2\le K\le1000$，$1\le n,m\le1000$。

对于 $100\%$ 的数据，保证：$2\le K\le10^5$，$1\le n,m\le10 ^ 5$。

对于所有的数据，保证：$0\lt A\le B$。$A,B$ 的每一位数字都在 $[0, K-1]$ 的范围内，没有前导零。


title: [SCOI2011] 飞镖

description:
飞镖是在欧洲颇为流行的一项运动。它的镖盘上分为20个扇形区域，分别标有1到20的分值，每个区域中有单倍、双倍和三倍的区域，打中对应的区域会得到分值乘以倍数所对应的分数。

例如打中18分里面的三倍区域，就会得到54分。

另外，在镖盘的中央，还有”小红心“和”大红心“，分别是25分和50分。

通常的飞镖规则还有一条，那就是在最后一镖的时候，必须以双倍结束战斗，才算获胜。也就是说，当还剩12分的时候，必须打中双倍的6才算赢，而打中单倍的12或者三倍的4则不算。

特别的，”大红心“也算双倍(双倍的25)。在这样的规则下，3镖能解决的最多分数是170分(两个三倍的20，最后用大红心结束)。

现在，lxhgww把原来的1到20分的分值变为了1到K分，同时把小红心的分数变为了M分(大红心是其双倍)，现在lxhgww想知道能否在3镖内（可以不一定用满3镖）解决X分。同样的，最后一镖必须是双倍（包括大红心）。

inputFormat:
输入的第一行是一个整数T，包括了T组数据。

第二行是5个整数，$A_1,B_1,C_1,D_1,K_1$，表示第一组数据的镖盘是从1到$K_1$分的，随后数据的镖盘由公式$K_i=(A_1K^2_{i-1}+B_1K_{i-1}+C_1)mod D_1 + 20$决定，其中第$i(1<i\le T)$组数据的镖盘是从1到$K_i$分的。

第三行是5个整数，$A_2,B_2,C_2,D_2,M_1$，表示第一组数据的小红心$M_1$分的，随后数据的镖盘由公式$M_i=(A_2M^2_{i-1}+B_2M_{i-1}+C_2)mod D_2 + 20$决定，其中第$i(1<i\le T)$组数据的小红心是$M_i$分。

第四行是5个整数，$A_3,B_3,C_3,D_3,X_1$，表示第一组数据需要解决的分数是$X_1$分的，随后数据的镖盘由公式$X_i=(A_3X^2_{i-1}+B_3X_{i-1}+C_3)mod D_3 + 20$决定，其中第$i(1<i\le T)$组数据需要解决的分数是$X_i$分。

outputFormat: 一行，包括一个数字，表示这T组数据中，能够被解决的数据数目。


title: [SCOI2013] 多项式的运算

description:
某天，mzry1992 一边思考着一个项目问题一边在高速公路上骑着摩托车。一个光头踢了他一脚，摩托车损坏，而他也被送进校医院打吊针。现在该项目的截止日期将近，他不得不请你来帮助他完成这个项目。

该项目的目的是维护一个动态的关于x 的无穷多项式 ，这个多项式初始时对于所有i有$a_i = 0$。

$f(x)=a_0x^0+a_1x^1+a_2x^2...$

操作者可以进行四种操作：

将$x^L$ 到$x^R$ 这些项的系数乘上某个定值v

将$x^L$ 到$x^R$ 这些项的系数加上某个定值v

将$x^L 到x^R $这些项乘上x变量

将某个定值v代入多项式F(x)，并输出代入后多项式的值，之后多项式还原为代入前的状况

经过观察，项目组发现使用者的操作集中在前三种，第四种操作不会出现超过10次。mzry1992 负责这个项目的核心代码，你能帮他实现么？

inputFormat:
输入的第一行有一个整数n 代表操作的个数。

接下来n 行，每行一个操作，格式如下：

mul L R v 代表第一种操作

add L R v 代表第二种操作

mulx L R 代表第三种操作

query v 代表第四种操作

outputFormat: 对于每个query 操作，输出对应的答案，结果可能较大，需要模上20130426。

samples:
6
add 0 1 7
query 1
mul 0 1 7
query 2
mulx 0 1
query 3

hint:
【样例解释】

操作一之后，多项式为F(x) = 7x + 7。

操作三之后，多项式为F(x) = 49x + 49。

操作五之后，多项式为F(x) = 49x^2 + 49x。

【数据范围与约定】

对于30% 的数据：N ≤ 5000，0 ≤ L ≤ R ≤ 5000，0 ≤ v ≤ 10^9

另有20% 的数据：N ≤ 10^5，0 ≤ L ≤ R ≤ 10^5，0 ≤ v ≤ 10^9，没有mulx 操作

剩下的50% 的数据：N ≤ 10^5，0 ≤ L ≤ R ≤ 10^5，0 ≤v ≤ 10^9


title: [SCOI2013] 密码

description:
Fish是一条生活在海里的鱼。有一天他很无聊，就到处去寻宝。他找到了位于海底深处的宫殿，但是一扇带有密码锁的大门却阻止了他的前进。

通过翻阅古籍，Fish 得知了这个密码的相关信息：

1. 该密码的长度为N。

2. 密码仅含小写字母。

3. 以每一个字符为中心的最长回文串长度。

4. 以每两个相邻字符的间隙为中心的最长回文串长度。

很快Fish 发现可能有无数种满足条件的密码。经过分析，他觉得这些密码中字典序最小的一个最有可能是答案，你能帮他找到这个密码么？

注意：对于两个串A和B，如果它们的前i个字符都相同，而A的第i+1个字符比B的第i+1个字符小，那么认为是则称密码A 的字典序小于密码B 的字典序，例如字符串abc 字典序小于字符串acb。如果密码A的字典序比其他所有满足条件的密码的字典序都小，则密码A是这些密码中字典序最小的一个。

inputFormat: 输入由三行组成。第一行仅含一个整数N，表示密码的长度。第二行包含N 个整数，表示以每个字符为中心的最长回文串长度。第三行包含N - 1 个整数，表示每两个相邻字符的间隙为中心的最长回文串长度。

outputFormat: 输出仅一行。输出满足条件的最小字典序密码。古籍中的信息是一定正确的，故一定存在满足条件的密码。


title: [SCOI2013] 摩托车交易

description:
mzry1992 在打完吊针出院之后，买了辆新摩托车，开始了在周边城市的黄金运送生意。在 mzry1992 生活的地方，城市之间是用双向高速公路连接的。另外，每条高速公路有一个载重上限，即在不考虑驾驶员和摩托车重量的情况下，如果所载货物的量超过某个值，则不能驶上该条高速公路。

今年，mzry1992 一共收到了来自 $n$ 个不同城市的 $n$ 份定订单，每个订单要求卖出上限为一定量的黄金，或是要求买入上限为一定量的黄金。由于订单并不是同时发来的，为了维护生意上的名声，mzry1992 不得不按照订单发来的顺序与客户进行交易。他与第i 个客户进行交易的具体步骤是：

1. 前往第 $i$ 个客户所在城市。当然，中途是完全允许经过其他城市的。
2. 与第 $i$ 个客户进行交易，在此过程中他希望有限制的让交易额尽量大。具体的限制有两个：
(a) 他希望与最后一个客户完成交易后，手上没有剩余黄金。
(b) 由于黄金是很贵重的物品，不能出现因为买入过多黄金而造成在以后的运送过程中不得不丢弃黄金的情况。

一开始，mzry1992 位于第一个订单客户所在的城市。现在有一个好消息，有人提供了 mzry1992 免费试用周边城市的列车系统的资格。具体来讲，如果mzry1992希望从 $A$ 城市到达 $B$ 城市，且 $A$、$B$ 城市均有列车站的话，他可以携带着黄金与摩托车从 $A$ 城市乘坐列车到 $B$ 城市，这里假定乘坐列车没有载重限制。

现在已知城市间的交通系统情况和订单情况，请帮助 mzry1992 计算每个向 mzry1992 购买黄金的客户的购买量。

inputFormat:
输入的第一行有三个整数 $n,m,q$，分别表示城市数，连通城市的高速公路数和有列车站的城市数。

接下来的一行有 $n$ 个数，每个数均不相同，且值介于 $1$ 到 $n$ 之间，代表订单的顺序。

第三行有 $n$ 个数，第 $i$ 个数表示 $i$ 号城市的订单的上限额 $b_i$，$b_i$ 为正值表示该订单为买入交易（针对mzry1992 而言），上限为 $b_i$，$b_i$ 为负值表示该订单为卖出交易（同样针对mzry1992 而言）上限为 $-b_i$。

接下来的 $m$ 行每行有三个数，$u, v, w$，表示城市 $u$ 和城市 $v$ 之间有一条载重上限为 $w$ 的高速公路，这里假定所有高速公路都是双向的，城市的序号是从 $1$ 到 $n$ 的。

输入的最后一行有 $q$ 个数，代表有列车站城市的序号。

outputFormat: 按照订单顺序对于每个卖出交易，输出一行，该行只有一个整数 $x$，表示卖出黄金的量。

hint:
### 样例解释

第一组样例：其中一种合法的方案是最初从 $2$ 号城市买入 $5$ 单位的黄金，先走第三条高速公路到 $1$ 号城市，然后再坐列车到 $3$ 号城市，在 $3$ 号城市卖出 $3$ 单位的黄金，然后乘坐列车到 $1$ 城市，在 $1$ 号城市卖出 $2$ 单位的黄金。

第二组样例：其中一种合法的方案是最初从 $1$ 号城市买入 $4$ 单位的黄金，走第一条高速公路，在 $2$ 号城市买入 $3$ 单位的黄金，走第二条高速公路，在三城市点卖出 $6$ 单位的黄金，走第三条高速公路，在 $4$ 号城市卖出 $1$ 单位的黄金。

### 数据范围与约定

- 对于 $20\%$ 数据，$n \le 100$，$m \le 200$。
- 对于 $50\%$ 数据，$n \le 3000$，$m \le 6000$。
- 对于 $100\%$ 数据，$1 \le n \le 10^5$，$n - 1 \le m \le 2\times 10^5$，$0 \le q \le n$，$0 < |b_i| < 10^9$，$0 < w < 10^9$，保证任意两个城市之间是通过高速公路连通的。


title: [SCOI2013] 数数

description:
Fish 是一条生活在海里的鱼，有一天他很无聊，就开始数数玩。他数数玩的具体规则是：

1. 确定数数的进制B

2. 确定一个数数的区间[L, R]

3. 对于[L, R] 间的每一个数，把该数视为一个字符串，列出该字符串的每一个（连续的）子串对应的B进制数的值。

4. 对所有列出的数求和。现在Fish 数了一遍数，但是不确定自己的结果是否正确了。由于[L, R] 较大，他没有多余精力去验证是否正确，你能写一个程序来帮他验证吗？

inputFormat:
输入包含三行。

第一行仅有一个数B，表示数数的进制。

第二行有N +1 个数，第一个数为N，表示数L 在B 进制下的长度为N，接下里的N个数从高位到低位的表示数L 的具体每一位。

第三行有M+ 1 个数，第一个数为M，表示数R 在B 进制下的长度为M，接下里的M个数从高位到低位的表示数R 的具体每一位。

outputFormat:
输出仅一行，即按照Fish 数数规则的结果，结果用10 进制表示，由于该数可能很大，输出该数模上20130427的模数。

数据中有 $r<l$ 的情况，输出的是 $-ans[r+1,l-1]\bmod 20130427$


title: [SCOI2013] 泡泡鱼

description:
Fish 是一条生活在海里的鱼，有一天他很无聊，想起了一个人类玩的游戏泡泡龙，于是他打算玩一把泡泡鱼。Fish 并不是特别清楚泡泡龙的规则（我们也是），于是他采用自己定的近似规则。

这里我们把海底想象成一个平面区域，它的上边界离发射点距离为H，左右边界离发射点的距离均为W。

起初时在这个区域的某些位置上有一些各种颜色的泡泡，且每个泡泡的直径为2（这里视泡泡为圆形）。

如果两个相同颜色的泡泡相切，我们就说这两个泡泡相邻。

如果两个相同颜色的泡泡相邻或者可以通过第三个相同颜色的泡泡相连，我们就说这两个泡泡相连。

为了方便描述，我们定义发射点的坐标为(0, 0)，每次Fish 会在发射点以某个给定角度发射某种颜色的泡泡。

如果泡泡撞到墙壁或者其他泡泡（即在某个时间第一次与墙壁或者其他泡泡相切），这个泡泡就会停住。如果这个泡泡与超过一个泡泡相连，那么这些泡泡就会消失，而Fish 就会得到消失泡泡数量的平方的分数值。

请注意，初始时如果有超过两个泡泡相连，这些泡泡并不会消失。现在已知初始泡泡的情况和每次发射泡泡的颜色和角度（相对于+x 轴逆时针方向），请你给出最终的总得分。注意，在上一次发射出去的泡泡停止之前，Fish 不能够继续发射泡泡。

inputFormat:
输入的第一行有两个实数W，H，表示游戏区域的边界坐标，精确到小数点后六位。

接下来一行有一个整数n，表示初始泡泡的个数。

接下来n 行，第i 行首先是两个浮点数xi 和yi，表示第i 个泡泡的圆心坐标，精确到小数点后八位，然后是一个整数ci，表示第i 个泡泡的颜色。

接下来一行有一个整数q，表示发射的泡泡的个数。最后q 行，第i 行首先是一个浮点数ai，精确到小数点后两位，表示第i 次发射的泡泡的角度，然后是一个整数ci，表示第i 次发射的泡泡的颜色。

数据保证刚开始所有的泡泡均在区域内！数据保证泡泡刚发射的位置永远不会停放有泡泡！

由于泡泡会在海水中浮动（以及计算机浮点的精度误差），我们认为当(xa-xb)^2 + (ya-yb)^2  <= (2 [1]\* 1)^2 + 10^-6成立时，泡泡a 和泡泡b 相切！数据保证初始时不存在相交的泡泡

outputFormat: 输出只有一行，这一行只有一个整数，代表Fish 最后的总得分。


title: [SCOI2013] 火柴棍数字

description:
Fish是一条生活在海里的鱼，有一天他很无聊，于是他去捡了人类扔进海里的垃圾，打算用这些来玩些什么。

他从捡回来的垃圾堆里找到了不少火柴棍，便把这些火柴棍拼成了一个长度为n 的十进制数，每个数字的拼法如下图所示

注意：每个数字占据的宽度和摆放方式是固定的，故以下情况均不合法。 ![](https://cdn.luogu.com.cn/upload/pic/4633.png)

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

拼完之后他好累，感觉再也不会拼了。他对拼出来的数大小不满意，希望通过移动一些火柴棍的位置来把这个数变得尽量大。

由于太累，他只能最多移动k 根火柴棍。而且由于数字的最低位放在墙边，他不能在该数的低位后面添加数字，但他可以在该数的前面添加数字。

你能帮他算出他移动火柴棍之后的数最大能是多大吗？

注意：火柴棍对于Fish 来说是很贵重的物品，所以不允许折断或丢弃火柴棍。

注意：火柴头的方向不影响数字的辨识，例如下面几种情况都是数字1

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

inputFormat: 输入仅含一行，分别是长度为n 的十进制数x 和最多移动火柴棍的数量k。x 没有前导零。

outputFormat: 输出仅一行，表示移动火柴棍之后的最大数。


title: [SCOI2014] 方伯伯打扑克

description:
方伯伯有一些空白的扑克牌。方伯伯想要用这些牌来玩一个数学游戏。

方伯伯首先决定好他要用这些空白的扑克牌组成 $m$ 个牌堆，每一堆牌的张数都是 $2$ 的整数次幂。确切地说，第 $i$ 堆（**注意**：从 $0$ 开始计数）牌将会有 $2^{n_i}$ 张牌。方伯伯首先决定好第 $0$ 堆牌要有 $2^{n_0}$ 张牌，然后将这堆牌从上到下按次序标记 $1 \sim 2^{n_0}$ 的十进制数字。

方伯伯开始游戏前决定要先洗牌，他决定好要洗 $x_0$ 次牌。他洗牌有一个固定的模式，每次洗牌操作等同于以下两个步骤的操作：

1. 将所有奇数位上的牌依次取出组成新的一堆牌。
2. 将新的一堆牌放在旧有的牌前面。

如当 $n_0=3$ 时，第 $0$ 堆牌从上到下一开始为 ``12345678``，洗一次牌得到 ``13572468``，洗两次牌得到 ``15263748``。

洗完牌后，方伯伯在心中决定好把其中从上往下数第 $l_0$ 到第 $r_0$ 张牌上的数字均加上一个数字 $t_0$，并依次（转换成二进制）异或之后得到一个异或值；方伯伯把第 $0$ 堆牌的这个异或值取模 $\bmod  \ 2^{n_0-1}$ 的值记作 $\mathrm{ans}_0$。

类似地，方伯伯将按同样的方式用剩下的 $m-1$ 个牌堆。具体地说，他决定按照如下几个公式来对每一堆牌组进行游戏：
1. 对于第 $i$ 堆牌，牌堆中将会有 $2^{n_i-1}$ 张牌，并从上到下标有 $1\sim 2^{n_i-1}$ 的十进制整数。其中，$n_i=(\mathrm{ans}_{i-1}+i-1) \bmod 5 \mathrel{+} \mathrm{base}$， $\mathrm{base}$ 是一个方伯伯事先决定好的正整数。
2. 方伯伯将会先决定好自己用来游戏的牌处于牌堆中的什么位置。方伯伯首先决定好他要看的第一张牌应该是第 $l_i$ 张，其中 $l_i=(2\mathrm{ans}_{i-1}+l_{i-1}+i-1)\bmod 2^{n_i} \mathrel{+} 1$。
3. 方伯伯接着决定他要看的最后一张牌应该是第 $r_i$ 张，其中 $r_i=(\mathrm{ans}_{i-1}+1+l_1\bmod 2^{\lfloor n_i/2 \rfloor} \cdot 2^{\lfloor n_i/2 \rfloor})\bmod 2^{n_i} \mathrel{+}1$。
4. 因为上面两个式子并不简单，有可能会产生 $l_i>r_i$ 的结果，此时将它们的值互换。
5. 想好自己要看什么牌后，方伯伯就会以此决定自己要洗 $x_i$ 次牌，其中 $x_i=(r_i-l_i+t_{i-1}+i-1)\bmod 2^{n_i}$。
6. 方伯伯同时还会想好他要给每张牌要加上数字的是 $t_i$，其中 $t_i=(l_i+r_i)\bmod 2^{n_i}$。
7. 方伯伯洗完牌后，把其中从上往下数第 $l_i$ 到第 $r_i$ 张牌上的数字均加上数字 $t_i$，并依次（转换成二进制）异或之后得到一个异或值；方伯伯把第 $i$ 堆牌的这个异或值取模 $\bmod 2^{n_i-1}$ 的值记作 $\mathrm{ans}_i$，接着回到第一步玩下一个牌堆。

方伯伯听说你有高超的信息学能力，他想知道你能否在他完成游戏前就算出最后一个牌堆，即第 $m-1$ 个牌堆，得到的游戏结果 $\mathrm{ans}_{m-1}$。你能做到吗？

inputFormat:
第一行包含一个整数 $m$，表示牌组的个数。

接下来一行包含六个整数，分别为 $n_0, x_0 ,l_0 ,r_0, t_0 , \mathrm{Base}$。

outputFormat: 输出为一个数，表示最后的答案。


title: [SCOI2014] 方伯伯的OJ

description:
方伯伯正在做他的 OJ。现在他在处理 OJ 上的用户排名问题。OJ 上注册了 $n$ 个用户，编号为 $1\sim n$，一开始他们按照编号排名。

方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号：

1. 操作格式为 $1\ \ x\ \ y$，意味着将编号为 $x$ 的用户编号改为 $y$，而排名不变，执行完该操作后需要输出该用户在队列中的位置，数据保证 $x$ 必然出现在队列中，同时，$y$ 是一个当前不在排名中的编号。
2. 操作格式为 $2\ \ x$，意味着将编号为 $x$ 的用户的排名提升到第一位，执行完该操作后需要输出执行该操作前编号为 $x$ 用户的排名。
3. 操作格式为 $3\ \ x$，意味着将编号为 $x$ 的用户的排名降到最后一位，执行完该操作后需要输出执行该操作前编号为 $x$ 用户的排名。
4. 操作格式为 $4\ \ k$，意味着查询当前排名为 $k$ 的用户编号，执行完该操作后需要输出当前操作用户的编号。

但同时为了防止别人监听自己的工作，方伯伯对他的操作进行了加密，即将四种操作的格式分别改为了：

- $1\ \ x+a\ \ y+a$；
- $2\ \ x+a$；
- $3\ \ x+a$；
- $4\ \ k+a$；
- 其中 $a$ 为上一次操作得到的输出，一开始 $a=0$。

例如：上一次操作得到的输出是 $5$，这一次操作的输入为：$1\ \ 13\ \ 15$ 因为这个输入是经过加密后的，所以你应该处理的操作是 $1\ \ 8\ \ 10$。

现在你截获了方伯伯的所有操作，希望你能给出结果。

inputFormat: 输入的第 $1$ 行包含 $2$ 个用空格分隔的整数 $n$ 和 $m$，表示初始用户数和操作数。此后有 $m$ 行，每行是一个询问，询问格式如上所示。

outputFormat: 输出包含 $m$ 行。每行包含一个整数，其中第 $i$ 行的整数表示第 $i$ 个操作的输出。

hint:
对于 $100\%$ 的数据，$1 \le n \le 10^8$，$1 \le m \le 10^5$。

输入保证对于所有的操作 $1,2,3$，$x$ 必然已经出现在队列中，同时对于所有操作 $1$，$1 \le y \le 2\times 10^8$，并且 $y$ 没有出现在队列中。

对于所有操作 $4$，保证 $1 \le k \le n$。


title: [SCOI2014] 方伯伯的商场之旅

description:
方伯伯有一天去参加一个商场举办的游戏。商场派了一些工作人员排成一行。每个人面前有几堆石子。

说来也巧，位置在 $i$ 的人面前的第 $j$ 堆的石子的数量，刚好是 $i$ 写成 $K$ 进制后的第 $j$ 位。现在方伯伯要玩一个游戏，商场会给方伯伯两个整数 $L,R$。

方伯伯要把位置在 $[L, R]$ 中的每个人的石子都合并成一堆石子。每次操作，他可以选择一个人面前的两堆石子，将其中的一堆中的某些石子移动到另一堆，代价是移动的石子数量 $\times$ 移动的距离。

商场承诺，方伯伯只要完成任务，就给他一些椰子，代价越小，给他的椰子越多。所以方伯伯很着急，想请你告诉他最少的代价是多少。例如：$10$ 进制下的位置在 $12312$ 的人，合并石子的最少代价为：$1 \times 2 + 2 \times 1 + 3 \times 0 + 1 \times1 + 2 \times 2 = 9$即把所有的石子都合并在第三堆。

inputFormat: 输入仅有 $1$ 行，包含 $3$ 个用空格分隔的整数 $L,R,K$，表示商场给方伯伯的 $2$ 个整数，以及进制数。

outputFormat: 输出仅有 $1$ 行，包含 $1$ 个整数，表示最少的代价。


title: [SCOI2014] 方伯伯的玉米田

description: 方伯伯在自己的农田边散步，他突然发现田里的一排玉米非常的不美。这排玉米一共有 $N$ 株，它们的高度参差不齐。方伯伯认为单调不下降序列很美，所以他决定先把一些玉米拔高，再把破坏美感的玉米拔除掉，使得剩下的玉米的高度构成一个单调不下降序列。方伯伯可以选择一个区间，把这个区间的玉米全部拔高 $1$ 单位高度，他可以进行最多 $K$ 次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。问能最多剩多少株玉米，来构成一排美丽的玉米。

inputFormat: 第一行包含两个整数 $n, K$，分别表示这排玉米的数目以及最多可进行多少次操作。第二行包含 $n$ 个整数，第 $i$ 个数表示这排玉米，从左到右第 $i$ 株玉米的高度 $a_i$。

outputFormat: 输出一个整数，最多剩下的玉米数。


title: [SCOI2014] 方伯伯运椰子

description:
四川的方伯伯为了致富，决定引进海南的椰子树。方伯伯的椰子园十分现代化，椰子园中有一套独特的交通系统。

现在用点来表示交通节点，边来表示道路。这样，方伯伯的椰子园就可以看作一个有  $N+2$ 个交通节点， $M$ 条边的有向无环图。 $N +1$ 号点为入口， $N +2$ 号点为出口。每条道路都有  $6$ 个参数， $u_i,v_i,a_i,b_i,c_i,d_i$。分别表示，该道路从  $u_i$ 号点通向  $v_i$ 号点，将它的容量压缩一次要  $a_i$ 的花费，容量扩大一次要  $b_i$ 的花费，该条道路当前的运输容量上限为  $c_i$，并且每单位运输量通过该道路要  $d_i$ 的费用。

在这个交通网络中，只有一条道路与起点相连。因为弄坏了这条道路就会导致整个交通网络瘫痪，聪明的方伯伯决定绝不对这条道路进行调整，也就是说，现在除了这条道路之外，对其余道路都可以进行调整。

有两种调整方式：

- 选择一条道路，将其进行一次压缩，这条道路的容量会下降  $1$ 单位。

- 选择一条道路，将其进行一次扩容，这条道路的容量会上升  $1$ 单位。

一条道路可以被多次调整。

由于很久以前，方伯伯就请过一个工程师，对这个交通网络进行过一次大的优化调整。所以现在所有的道路都被完全的利用起来了，即每条道路的负荷都是满的（每条道路的流量等于其容量）。

但方伯伯一想到自己的海南椰子会大丰收，就十分担心巨大的运输量下，会导致过多的花费。因此，方伯伯决定至少进行一次调整，调整之后，必须要保持每条道路满负荷，且总交通量不会减少。

设调整后的总费用是  $Y$，调整之前的总费用是  $X$。现在方伯伯想知道，最优调整比率是多少，即假设他进行了  $k$ 次调整， $\dfrac{X-Y}{k}$最大能是多少？

注：总费用 = 交通网络的运输花费 + 调整的花费

inputFormat: 第一行包含二个整数 $N$， $M$接下来 $M$行代表 $M$条边，表示这个交通网络每行六个整数，表示 $u_i,v_i,a_i,b_i,c_i,d_i$ 。

outputFormat: 一个浮点数，保留二位小数。表示答案，数据保证答案大于 $0$。


title: [SCOI2014] 舌尖上的方伯伯

description:
方伯伯为了吃到最传统最纯净的美食，决定亲自开垦一片菜园。现有一片空地，方伯伯已经规划n个地点准备种上蔬菜。

最新鲜的蔬菜需有最甘甜井水的灌溉，因此方伯伯将要打出两口井，分别记为井A、井B。现在问题来了，在何处打井？每颗蔬菜分别由哪口井来灌溉？方伯伯不善于计算，于是提出以下几个原则，再根据这些原则找方案。原则如下：

1.井必须打在它负责灌溉的蔬菜的正中心，即设它的坐标为(X,Y)，X(Y)为它负责灌溉的所有蔬菜的横(纵)坐标之和的平均值。

2.所有蔬菜都需要被灌溉。3.两口井都必须要灌溉至少一颗蔬菜。4.到A井更近的蔬菜，必须由A井灌溉，到B井更近的蔬菜，必须由B井灌溉。距离相等相等时则可任意一口井灌溉。

当然两口井不能打到同一个位置，多株蔬菜当然也不会种在同一个位置。

方伯伯把他的开垦原则告诉了你，请你告诉他有多少种满足这些原则方案。我们把灌溉1号蔬菜的井记为A号井，那么，只要A灌溉的蔬菜的集合不同，就是一种不同的方案。

inputFormat: 输入1行包含1个整数n，代表方师傅的蔬菜的数目接下来n行，每行包含2个整数，xi，yi，代表第i棵蔬菜的坐标。

outputFormat: 输出包含1个整数，代表方师傅可行的方案数


title: [SCOI2016] 围棋

description:
近日，谷歌研发的围棋 AI——AlphaGo 以 $4:1$ 的比分战胜了曾经的世界冠军李世石，这是人工智能领域的又一里程碑。

与传统的搜索式 AI 不同，AlphaGo 使用了最近十分流行的卷积神经网络模型。在卷积神经网络模型中，棋盘上每一块特定大小的区域都被当做一个窗口。例如棋盘的大小为 $5\times 6$，窗口大小为 $2\times 4$，那么棋盘中共有 $12$ 个窗口。此外，模型中预先设定了一些模板，模板的大小与窗口的大小是一样的。

下图展现了一个 $5\times 6$ 的棋盘和两个 $2\times 4$ 的模板：

![](https://i.loli.net/2020/03/05/24yfVvrmNScWF5g.jpg)

对于一个模板，只要棋盘中有某个窗口与其完全匹配，我们称这个模板是被激活的，否则称这个模板没有被激活。

例如图中第一个模板就是被激活的，而第二个模板就是没有被激活的。我们要研究的问题是：对于给定的模板，有多少个棋盘可以激活它。

为了简化问题，我们抛开所有围棋的基本规则，只考虑一个 $n\times m$ 的棋盘，每个位置只能是黑子、白子或无子三种情况，换句话说，这样的棋盘共有 $3^{n\times m}$ 种。此外，我们会给出 $q$ 个 $2\times c$ 的模板。

我们希望知道，对于每个模板，有多少种棋盘可以激活它。强调：模板一定是两行的。

inputFormat:
输入数据的第一行包含四个正整数 $n,m,c$ 和 $q$，分别表示棋盘的行数、列数、模板的列数和模板的数量。

随后 $2\times q$ 行，每连续两行描述一个模板。其中，每行包含 $c$ 个字符，字符一定是 ```W```，```B``` 或 ```X``` 中的一个，表示白子、黑子或无子三种情况的一种。

outputFormat: 输出应包含 $q$ 行，每行一个整数，表示符合要求的棋盘数量。由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模后的结果即可。


title: [SCOI2016] 妖怪

description:
邱老师是妖怪爱好者，他有 $n$ 只妖怪，每只妖怪有攻击力 $\mathrm{atk}$ 和防御力 $\mathrm{dnf}$ 两种属性。邱老师立志成为妖怪大师，于是他从真新镇出发，踏上未知的旅途，见识不同的风景。

环境对妖怪的战斗力有很大影响，环境 $(a,b)$ 由 $a,b$ 两个参数定义，其中 $a,b$ 为**正实数**。在环境 $(a,b)$ 中，妖怪可以降低自己 $k\times a$ 点攻击力，提升 $k\times b$ 点防御力或者提升自己 $k\times a$ 点攻击力，降低 $k\times b$ 点防御力。其中 $k$ 为**任意实数**，但是 **$\mathrm{atk}$ 和 $\mathrm{dnf}$ 必须始终非负**。

妖怪在环境 $(a,b)$ 中的**战斗力** $\mathrm{strength}$ 定义为妖怪在该种环境中能达到的最大攻击力和最大防御力之和，即 $\mathrm{strength}(a,b)=\max(\mathrm{atk}(a,b))+\max(\mathrm{dnf}(a,b))$。

比如当前环境 $a=3,b=2$，那么攻击力为 $6$，防御力为 $2$ 的妖怪，能达到的最大攻击力为 $9$，最大防御力为 $6$。所以该妖怪在 $a=3,b=2$ 的环境下战斗力为 $15$。

因此，在不同的环境，战斗力最强的妖怪可能发生变化。

作为一名优秀的妖怪训练师，邱老师想发掘每一只妖怪的最大潜力，他想知道在**最为不利的情况下**，他的 $n$ 只妖怪能够达到的最强战斗力值。换言之，存在一组正实数 $(a,b)$ 使得 $n$ 只妖怪在该环境下最强战斗力最低，你需要输出这个最低的战斗力。

inputFormat:
第一行一个n，表示有 $n$ 只妖怪。

接下来 $n$ 行，每行两个整数 $\mathrm{atk}_i$ 和 $\mathrm{dnf}_i$，表示第 $i$ 只妖怪的攻击力和防御力。

outputFormat: 输出在最不利情况下最强妖怪的战斗力值，保留 $4$ 位小数。

hint:
对于 $100\%$ 的数据，$1\le n\le 10^6$，$0\lt \mathrm{atk},\mathrm{dnf}\le 10^8$。

Statement fixed by Starrykiller.


title: [SCOI2016] 幸运数字

description:
A 国共有 $n$ 座城市，这些城市由 $n - 1$ 条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个幸运数字，以纪念碑的形式矗立在这座城市的正中心，作为城市的象征。

一些旅行者希望游览 A 国。旅行者计划乘飞机降落在 $x$ 号城市，沿着 $x$ 号城市到 $y$ 号城市之间那条唯一的路径游览，最终从 $y$ 城市起飞离开 A 国。在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸运是不能简单叠加的，这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。

例如，游览者拍了 $3$ 张照片，幸运值分别是 $5, 7, 11$，那么最终保留在自己身上的幸运值就是 $5 \operatorname{xor} 7 \operatorname{xor} 11 = 9$。

有些聪明的游览者发现，只要选择性地进行拍照，便能获得更大的幸运值。例如在上述三个幸运值中，只选择 $5$ 和 $11$ ，可以保留的幸运值为 $14$ 。现在，一些游览者找到了聪明的你，希望你帮他们计算出在他们的行程安排中可以保留的最大幸运值是多少。

inputFormat:
第一行包含 $2$ 个正整数 $n, q$，分别表示城市的数量和旅行者数量。

第二行包含 $n$ 个非负整数，其中第 $i$ 个整数 $G_i$ 表示 $i$ 号城市的幸运值。

随后 $n - 1$ 行，每行包含两个正整数 $x, y$，表示 $x$ 号城市和 $y$ 号城市之间有一条道路相连。

随后 $q$ 行，每行包含两个正整数 $x, y$，表示这名旅行者的旅行计划是从 $x$ 号城市到 $y$ 号城市。

outputFormat: 输出需要包含 $q$ 行，每行包含 $1$ 个非负整数，表示这名旅行者可以保留的最大幸运值。


title: [SCOI2016] 美味

description:
一家餐厅有 $n$ 道菜，编号 $1, 2, \ldots, n$，大家对第 $i$ 道菜的评价值为 $a_i$。有 $m$ 位顾客，第 $i$ 位顾客的期望值为 $b_i$，而他的偏好值为 $x_i$。因此，第 $i$ 位顾客认为第 $j$ 道菜的美味度为 $b_i\oplus (a_j + x_i)$，$\oplus$ 表示异或运算。

第 $i$ 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第 $l_i$ 道到第 $r_i$ 道中选择。请你帮助他们找出最美味的菜。

inputFormat:
第 $1$ 行两个整数 $n, m$，表示菜品数和顾客数。

第 $2$ 行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示每道菜的评价值。

第 $3$ 至 $m + 2$ 行，每行四个整数 $b,x,l,r$，表示该位顾客的期望值，偏好值，和可以选择菜品区间。

outputFormat: 输出 $m$ 行，每行一个整数表示该位顾客选择的最美味的菜的美味值。

hint: 对于 $100\%$ 的数据，满足 $1 \le n \le 2 \times 10^5$，$0 \le a_i,b_i,x_i < 10^5$，$1 \le l_i \le r_i \le n$（$1 \le i \le m$），$1 \le m \le 10^5$。


title: [SCOI2016] 背单词

description:
Lweb 面对如山的英语单词，陷入了深深的沉思：我怎么样才能快点学完，然后去玩三国杀呢？这时候睿智的凤老师从远处飘来，他送给了 Lweb 一本计划册和一大缸泡椒，他的计划册是长这样的：

| 序号    | 单词 |
| ------- | ---- |
| $1$     |      |
| $2$     |      |
| $\dots$ |      |
| $n-1$    |      |
| $n$     |      |

然后凤老师告诉 Lweb ，我知道你要学习的单词总共有 $n$ 个，现在我们从上往下完成计划表，对于一个序号为 $x$ 的单词（序号 $1,\dots ,x-1$ 都已经被填入）：

1. 如果存在一个单词是它的后缀，并且当前没有被填入表内，那他需要吃 $n \times n$ 颗泡椒才能学会；
2. 当它的所有后缀都被填入表内的情况下，如果在 $1,\dots,x-1$ 的位置上的单词都不是它的后缀，那么你吃 $x$ 颗泡椒就能记住它；
3. 当它的所有后缀都被填入表内的情况下，如果 $1,\dots,x-1$ 的位置上存在是它后缀的单词，所有是它后缀的单词中，序号最大为 $y$，那么你只要吃 $x-y$ 颗泡椒就能把它记住。

Lweb 是一个吃到辣辣的东西会暴走的奇怪小朋友，所以请你帮助 Lweb ，寻找一种最优的填写单词方案，使得他记住这 $n$ 个单词的情况下，吃最少的泡椒。

inputFormat:
输入一个整数 $n$ ，表示 Lweb 要学习的单词数。

接下来 $n$ 行，每行有一个单词（由小写字母构成，且保证任意单词两两互不相同）。

outputFormat: Lweb 吃的最少泡椒数


title: [SCOI2016] 萌萌哒

description:
一个长度为 $n$ 的大数，用 $S_1S_2S_3 \cdots S_n$表示，其中 $S_i$ 表示数的第 $i$ 位, $S_1$ 是数的最高位。告诉你一些限制条件，每个条件表示为四个数，$l_1,r_1,l_2,r_2$，即两个长度相同的区间，表示子串 $S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1}$ 与 $S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2}$ 完全相同。

比如 $n=6$ 时，某限制条件 $l_1=1,r_1=3,l_2=4,r_2=6$ ，那么 $123123$，$351351$ 均满足条件，但是 $12012$，$131141$ 不满足条件，前者数的长度不为 $6$ ，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

outputFormat: 一个数，表示满足所有条件且长度为 $n$ 的大数的个数，答案可能很大，因此输出答案模 $ 10^9+7 $ 的结果即可。


title: [SDOI2013] 刺客信条

description:
故事发生在1486 年的意大利，Ezio 原本只是一个文艺复兴时期的贵族，后来因为家族成员受到圣殿骑士的杀害，决心成为一名刺客。最终，凭借着他的努力和出众的天赋，成为了杰出的刺客大师，他不仅是个身手敏捷的武林高手，飞檐走壁擅长各种暗杀术。刺客组织在他的带领下，为被剥削的平民声张正义，赶跑了原本统治意大利的圣殿骑士首领-教皇亚历山大六世。在他的一生中，经历了无数次惊心动魄、扣人心弦的探险和刺杀。

曾经有一次，为了寻找Altair 留下的线索和装备，Ezio 在佛罗伦萨中的刺客墓穴进行探索。这个刺客墓穴中有许多密室，且任何两个密室之间只存在一条唯一的路径。这些密室里都有一个刺客标记，他可以启动或者关闭该刺客标记。为了打开储存着线索和装备的储藏室，Ezio 必须操作刺客标记来揭开古老的封印。要想解开这个封印，他需要通过改变某些刺客标记的启动情况，使得所有刺客标记与封印密码“看起来一样”。

在这里，“看起来一样”的定义是：存在一种“标记”密室与“密码”密室之间一一对应的关系，使得密室间的连接情况和启动情况相同（提示中有更详细解释）。幸运的是，在Ezio 来到刺客墓穴之前，在Da Vinci 的帮助下，Ezio 已经得知了打开储藏室所需要的密码。

而你的任务则是帮助Ezio 找出达成目标所需要最少的改动标记次数。

inputFormat:
第一行给出一个整数n, 表示密室的个数,

第二行至第 n 行, 每行绐出两个整数 a 和 b, 表示第 a 个密室和第 b 个密室之间存在一条通道.

第 n+1行1 绐出 n 个整数1 分别表示当时每个密室的启动情况 {0表示关闭, 1表示启动).

第 n+2 行7 给出 n 个整数, 分别表示密码中每个密室的启动情况.

outputFormat: 输出只有一行，即输出最少改动标记次数

hint:
密室的编号是可以变的！将第三个密室关闭后，在当前标记和密码之间，存在1->4,2->3,3->2,4->1 的对应关系，重新编号后连接情况没有改变，且标记与密码对应。对于更一般的情况，存在一个1 到n 的置换P，使得对于任意密室之间的道路u-v，都一定有密码密室中的道路P(u)-P(v)；如果不存在密室之间的道路u-v，则一定没有密码密室中的道路P(u)-P(v)。

对于100%的数据，n<=700，且每个密室至多与11个密室相通


title: [SDOI2013] 逃考

description:
髙考又来了，对于不认真读书的来讲真不是个好消息为了小杨能在家里认真读书，他的亲戚决定驻扎在他的家里监督他学习，有爷爷奶奶、外公外婆、大舅、大嫂、阿姨 ......。

小杨实在是忍无可忍了，这种生活跟监狱有什么区别！为了他亲爱的小红，为了他的 dota， 他决定越狱！

假设小杨的家是个 $n\times m$ 的矩阵，左下角坐标为（$0,0)$，右上角坐标为（$x_1,y_1)$。小杨有 $n$ 个亲戚，驻扎在矩阵里（位置不同，且不在矩阵的边上）。小杨家里的每个地方都被亲戚监控着，而且只被距离最近的亲戚监控：

也就是说假设小杨所在的位置是（$3,3)$, 亲戚 $A$ 在（$3,0)$，A 距离小杨距离是 $3$；亲戚 $B$ 在（$6,7),$ 则 $B$ 距离小杨距离是 $5$。距离 $A<$ 距离 $B$，所以（$3,3)$ 位置由 $A$ 监控。

如果“最近距离”出现同时有几个亲戚，那么那个位置同时被那几个亲戚监控。

给出小杨的坐标（$x_0,y_0)$。因为被发现的人数越少，越狱成功的机会越大，所以小杨需要你设计一条越狱路线到达矩形的边上，且被发现的人数最少。

小杨做的方向是任意的，也就是说路线上的任意位置 $H$ 需要是实数。

保证一开始小杨只被一个亲戚监控着。

inputFormat:
第一行一个正整数 $t \le 3$ 表示数据个数。

接下来 $t$ 个数据：

第一行 $n$ 表示亲戚个数。

第二行 $4$ 个正整数表示举行右上角坐标 $(x_1,y_1)$ 和小杨的坐标 $(x_0,y_0)$。

接下来 $n$ 行，每行 $2$ 个正整数表示一个亲戚的位置。

outputFormat: 每个数据一个正整数表示越狱被发现人数的最小值

hint:
数据解释 :。

第一个数据，小杨直接往上走，只被 $(5,6)$ 监控过。

第二个数据，小杨被 $(7,7)$ 监控 - 走到 $(9,9)$ 被 $(7,11)$ 监控，然后直接往上走。

数据规模 :

前 $50\%$ 数据, $n \le 200$。

其余数据 $n \le 600$。


title: [SDOI2013] 泉

description:
作为光荣的济南泉历史研究小组中的一员，铭铭收集了历史上x个不同年份时不同泉区的水流指数，这个指数是一个小于. 2^30的非负整数。第i个年份时六个泉区的泉水流量指数分别为 A(i,l)，A(i,2)，A(i,3)，A(i,4)， A(i,5)与 A(i,6)。

现在铭铭希望知道有多少对不同的年份：i和j,满足这两年恰好有K个泉区的泉水流S指数对应相同。

inputFormat:
第一行有2个整数，分别是N和K

之后N行，每行有6个整数。第i行的第j个数字A(i，j)表示第i个年份中第j个泉区的泉水流量指数。

outputFormat: 一个整数表示有多少对不同的年份满足恰有K个区的泉水流量指数对应相同。

hint:
对于 100%的数据, 0<=K <=6, 且所有数据中K是等概率出现的, 即对于任意的 0<=x都有大约 1/7 的数据中 K=x.
N<=100000


title: [SDOI2013] 保护出题人

description:
出题人铭铭认为给SDOI2012出题太可怕了，因为总要被骂，于是他又给SDOI2013出题了。

参加SDOI2012的小朋友们释放出大量的僵尸，企图攻击铭铭的家。而你作为SDOI2013的参赛者，你需要保护出题人铭铭。

僵尸从唯一一条笔直道路接近，你们需要在铭铭的房门前放置植物攻击僵尸，避免僵尸碰到房子。

第一关，一只血量为$a_1$点的墦尸从距离房子$x_1$米处速接近，你们放置了攻击力为$y_1$点/秒的植物进行防御；第二关，在上一关基础上，僵尸队列排头增加一只血量为$a_2$点的僵尸，与后一只僵尸距离$d$米，从距离房$x_2$米处匀速接近，你们重新放置攻击力为$y_2$点/秒的植物；……；第$n$关，僵尸队列共有$n$只僵尸，相邻两只僵尸距离$d$米，排头僵尸血量为$a_n$点，排第二的 僵尸血量$a_{n-1}$，以此类推，排头僵尸从距离房子$x_n$米处匀速接近，其余僵尸跟随排头同时接近，你们重新放置攻击力为$y_n$点/秒的植物。

每只僵尸直线移动速度均为$1$米/秒，由于植物射击速度远大于僵尸移动速度，可忽略植物子弹在空中的时间。所有僵尸同时出现并接近，因此当一只僵尸死亡后，下一只僵尸立刻开始受到植物子弹的伤害。

游戏得分取决于你们放置的植物攻击力的总和$\sum \limits _{i=1} ^{n} y_i$，和越小分数越高，为了追求分数上界，你们每关都要放置攻击力尽量小的植物。

作为SDOI2013的参赛选手，你们能保护出题人么？

inputFormat:
第一行两个空格隔开的正整数n和d，分别表示关数和相邻僵尸间的距离。

接下来n行每行两个空格隔开的正整数，第i + 1行为Ai和 Xi，分别表示相比上一关在僵尸队列排头增加血量为Ai 点的僵尸，排头僵尸从距离房子Xi米处开始接近。

outputFormat: 一个数，n关植物攻击力的最小总和 ，保留到整数。

hint:
第一关：距离房子3米处有一只血量3点的僵尸，植物最小攻击力为1.00000；
第二关：距离房子1米处有一只血量1点的僵尸、3米处有血量3点的僵尸，植物最小攻击力为1.33333；
第三关：距离房子8米处有一只血量10点的僵尸、10米处有血量1点的僵尸、12米处有血量3点的僵尸，植物最小攻击力为1.25000；
第四关：距离房子8米处有一只血量4点的僵尸、10米处有血量10点的僵尸、12米处有血量1点的僵尸、14米处有血量3点的僵尸，植物最小攻击力为1.40000；
第五关：距离房子3米处有一只血量2点的僵尸、5米处有血量4点的僵尸、7米处有 血量10点的僵尸、9米处有血量1点的僵尸、11米处有血量3点的僵尸，植物最小攻击力 为2.28571。
植物攻击力的最小总和为7.26905。

对于100%的数据， $ 1\le n \le 10^5  ,1 \le d,x,a \le 10^{12} $ 。


title: [SDOI2013] 城市规划

description:
A 市的市长打算在海边开发一段地带。这个地带看成是一个 $N \times M $ 的方格阵。每个格子可以是建筑、道路或者草地。这片地带是要出租给某些公司，但是这些公司的要求很奇怪。他们要求租给他们的建筑要通过道路形成一个连通块。同一个连通块只能租给一家公司。这个 $N\times M$ 的方格阵是用字符组成的：`O`，`.`，`+`，`|`，`-`，其中 `O` 表示建筑，'.' 表示草地。`|`，`-`，`+` 表示道路，分别表示把上下，左右、上下左右的格子连起来。相邻的 `O` 表示这是一个建筑物。

由于规划可能不太好，可能某些连通块里面只有道路，这里道路是不能出租的！由于最后这块地的选取可能有部分会与其他市共冋开发，所以最后会在这个 $N\times M$ 中选取一段出来，最后选取出来的是一个 $N_i\times M$（$0<N_1\le N$）的地段。A 市的市长想弄要一个规划软件，支持以下功能：

1. 改变一个格子。
2. 询问某块地带有多少个带建筑的连通块。

inputFormat:
第一行两个整数 $N, M$，如题意所示

接下来的 $N$ 行，每行 $M$ 个字符表示这片地带的初始情况。

接下来的一行一个整数 $Q$，表示操作次数。接下来的 $Q$ 行，每行有两种格式：
- `C i j k` :  把第 $i$ 行第 $j$ 个格子修改成k；
- `Q l r`:  询问 $(l, 1) (r, M)$ 这块地带连通块个数。

outputFormat: 对于每个询问中的 $Q$，输出一行，一个数字，表示当前的连通块个数。


title: [SDOI2013] 方程

description:
给定方程
$x_1+x_2+\dots +x_{n}=m$。

我们对第 $1 \sim n_1$ 个变量进行一些限制： $x_{1} \le a_{1},x_{2} \le a_{2},\dots, x_{n_1} \le a_{n_1}$。

我们对第 $n_1+1\sim n_1+n_2$ 个变量进行一些限制： $x_{n_1+1} \ge a_{n_1+1},x_{n_1+2} \ge a_{n_1+2},\dots,x_{n1+n2} \ge a_{n_1+n_2}$。

求：在满足这些限制的前提下，该方程正整数解的个数。答案可能很大，请输出对 $p$ 取模后的答案。

inputFormat:
输入含有多组数据。

第一行两个正整数 $T,p$。$T$  表示这个测试点内的数据组数，$p$ 的含义见题目描述。

对于每组数据，第一行四个非负整数 $n,n_1,n_2,m$。

第二行 $n_1+n_2$ 个正整数，表示 $a_{1},a_2,\dots, a_{n_1+n_2}$。请注意，如果 $n_1+n_2$ 等于 $0$，那么这一行会成为一个空行。

outputFormat: 共 $T$ 行，每行一个正整数表示取模后的答案。


title: [SDOI2013] 森林

description:
小 Z 有一片森林，含有 $N$ 个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有 $M$ 条边。

小Z希望执行 $T$ 个操作，操作有两类：

 - `Q x y k` 查询点 $x$ 到点 $y$ 路径上所有的权值中，第 $k$ 小的权值是多少。此操作保证点 $x$ 和点 $y$ 连通，同时这两个节点的路径上至少有 $k$ 个点。
 - `L x y` 在点 $x$ 和点 $y$ 之间连接一条边。保证完成此操作后，仍然是一片森林。

为了体现程序的在线性，我们把输入数据进行了加密。设 $lastans$ 为程序上一次输出的结果，初始的时候 $lastans$ 为 $0$。

对于一个输入的操作 `Q x y k`，其真实操作为 `Q x^lastans y^lastans k^lastans`。

对于一个输入的操作 `L x y`，其真实操作为 `L x^lastans y^lastans`。其中 `^` 运算符表示异或，等价于 Pascal 中的 `xor` 运算符。

请写一个程序来帮助小 Z 完成这些操作。

inputFormat:
第一行包含一个正整数 $\mathrm{testcase}$，表示当前测试数据的测试点编号。

第二行包含三个整数 $N,M,T$，分别表示节点数、初始边数、操作数。

第三行包含 $N$ 个非负整数表示 $N$ 个节点上的权值。

接下来 $M$ 行，每行包含两个整数 $x$ 和 $y$，表示初始的时候，点 $x$ 和点 $y$ 之间有一条无向边。

接下来 $T$ 行，每行描述一个操作，格式为 `Q x y k` 或者 `L x y`，其含义见题目描述部分。

outputFormat: 对于每一个第一类操作，输出一个非负整数表示答案。


title: [SDOI2013] 淘金

description:
小 Z 在玩一个叫做《淘金者》的游戏。游戏的世界是一个二维坐标。$X$ 轴、$Y$ 轴坐标范围均为$1\ldots N$。初始的时候，所有的整数坐标点上均有一块金子，共 $N^2$ 块。

一阵风吹过，金子的位置发生了一些变化。细心的小 Z 发现，初始在 $(i,j)$ 坐标处的金子会变到 $(f(i),f(j))$ 坐标处。其中 $f(x)$ 表示 $x$ 各位数字的乘积，例如 $f(99)=81,~f(12)=2,~f(10)=0$。

如果金子变化后的坐标不在 $1\ldots N$ 的范围内，我们认为这块金子已经被移出游戏。同时可以发现，对于变化之后的游戏局面，某些坐标上的金子数量可能不止一块，而另外一些坐标上可能已经没有金子。这次变化之后，游戏将不会再对金子的位置和数量进行改变，玩家可以开始进行采集工作。

小 Z 很懒，打算只进行 $K$ 次采集。每次采集可以得到某一个坐标上的所有金子，采集之后，该坐标上的金子数变为 $0$。

现在小 Z 希望知道，对于变化之后的游戏局面，在采集次数为 $K$ 的前提下，最多可以采集到多少块金子？ 答案可能很大，小 Z 希望得到对 $10^9+7$ 取模之后的答案。

inputFormat: 共一行，包含两个正整数 $N, K$。

outputFormat: 一个整数，表示最多可以采集到的金子数量。


title: [SDOI2013] 直径

description:
小 Q 最近学习了一些图论知识。根据课本，有如下定义。树：无回路且连通的无向图，每条边都有正整数的权值来表示其长度。如果一棵树有 $N$ 个节点，可以证明其有且仅有 $N-1$ 条边。

路径：一棵树上，任意两个节点之间最多有一条简单路径。我们用 $\text{dis}(a,b)$ 表示点 $a$ 和点 $b$ 的路径上各边长度之和。称 $\text{dis}(a,b)$ 为 $a,b$ 两个节点间的距离。

直径：一棵树上，最长的路径为树的直径。树的直径可能不是唯一的。

现在小 Q 想知道，对于给定的一棵树，其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。

inputFormat:
第一行包含一个整数 $N$，表示节点数。

接下来 $N-1$ 行，每行三个整数 $a,b,c$，表示点 $a$ 和点 $b$ 之间有一条长度为 $c$ 的无向边。

outputFormat: 共两行。第一行一个整数，表示直径的长度。第二行一个整数，表示被所有直径经过的边的数量。

hint:
【样例说明】

直径共有两条，$3$ 到 $2$ 的路径和 $3$ 到 $6$ 的路径。这两条直径都经过边 $(3,1)$ 和边$(1, 4)$。

对于 $100\%$ 的测试数据：$2\le N\le 200000$，所有点的编号都在 $1\sim N$ 的范围内，边的权值 $\le10^9$。


title: [SDOI2013] 费用流

description:
Alice 和 Bob 在图论课程上学习了最大流和最小费用最大流的相关知识。

> 最大流问题：给定一张有向图表示运输网络，一个源点 $S$ 和一个汇点 $T$ ，每条边都有最大流量。
>
> 一个合法的网络流方案必须满足：
>
> 1. 每条边的实际流量都不超过其最大流量且非负；
> 2. 除了源点 $S$ 和汇点 $T$ 之外，对于其余所有点，都满足该点总流入流量等于该点总流出流量；而 $S$ 点的净流出流量等于 $T$ 点的净流入流量，这个值也即该网络流方案的总运输量。
>
> 最大流问题就是对于给定的运输网络，求总运输量最大的网络流方案。

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

上图表示了一个最大流问题。对于每条边，右边的数代表该边的最大流量，左边的数代表在最优解中，该边的实际流量。需要注意到，一个最大流问题的解可能不是唯一的。

对于一张给定的运输网络，Alice 先确定一个最大流，如果有多种解，Alice 可以任选一种；之后 Bob 在每条边上分配单位花费（单位花费必须是非负实数），要求所有边的单位花费之和等于 $P$。

总费用等于每一条边的实际流量乘以该边的单位花费。需要注意到，Bob 在分配单位花费之前，已经知道 Alice 所给出的最大流方案。现在 Alice 希望总费用尽量小，而 Bob 希望总费用尽量大。我们想知道，如果两个人都执行最优策略，最大流的值和总费用分别为多少。

inputFormat:
第一行三个整数 $N,M,P$。$N$ 表示给定运输网络中节点的数量，$M$ 表示有向边的数量，$P$ 的含义见问题描述部分。为了简化问题，我们假设源点 $S$ 是点 $1$，汇点 $T$ 是点 $N$。

接下来 $M$ 行，每行三个整数 $A,B,C$，表示有一条从点 $A$ 到点 $B$ 的有向边，其最大流量是 $C$。

outputFormat: 第一行一个整数，表示最大流的值。第二行一个实数，表示总费用。建议选手输出四位以上小数。

hint:
**【样例说明】**

对于 Alice，最大流的方案是固定的。两条边的实际流量都为 $10$。

对于 Bob，给第一条边分配 $0.5$ 的费用，第二条边分配 $0.5$ 的费用。总费用为：$10\times 0.5+10\times 0.5=10$。可以证明不存在总费用更大的分配方案。

**【数据规模和约定】**

对于 $20\%$ 的测试数据，所有有向边的最大流量都是 $1$。

对于 $100\%$ 的测试数据，$N\le 100$，$M\le 1000$。

对于 $100\%$ 的测试数据：所有点的编号在 $1\sim N$ 范围内，$1 \le \text{每条边的最大流量} \le 50000$，$1\le P\le 10$，给定运输网络中不会有起点和终点相同的边。


title: [SDOI2013] 随机数生成器

background: 小 W 喜欢读书，尤其喜欢读《约翰克里斯朵夫》。

description:
最近小 W 准备读一本新书，这本书一共有 $p$ 页，页码范围为 $0 \sim p-1$。

小 W 很忙，所以每天只能读一页书。为了使事情有趣一些，他打算使用 NOI2012 上学习的线性同余法生成一个序列，来决定每天具体读哪一页。

我们用 $x_i$ 来表示通过这种方法生成出来的第 $i$ 个数，也即小 W 第 $i$ 天会读哪一页。这个方法需要设置 $3$ 个参数 $a,b,x_1$，满足 $0\leq a,b,x_1\lt p$，且 $a,b,x_1$ 都是整数。按照下面的公式生成出来一系列的整数：
$$x_{i+1} \equiv a \times x_i+b \pmod p$$
其中 $\bmod$ 表示取余操作。

但是这种方法可能导致某两天读的页码一样。

小 W 要读这本书的第 $t$ 页，所以他想知道最早在哪一天能读到第 $t$ 页，或者指出他永远不会读到第 $t$ 页。

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

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

接下来 $T$ 行，每行有五个整数 $p, a, b, x_1, t$，表示一组数据。

outputFormat: 对于每组数据，输出一行一个整数表示他最早读到第 $t$ 页是哪一天。如果他永远不会读到第 $t$ 页，输出$-1$。

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

对于全部的测试点，保证：

- $1 \leq T \leq 50$。
- $0 \leq a, b, x_1, t \lt p$，$2 \leq p \leq 10^9$。
- $p$ 为质数。


title: [SDOI2013] 项链

background:
项链作为人体的装饰品之一，是最早出现的首饰。项链除了具有装饰功能之外，有些项链还具有特殊的显示作用，如天主教徒的十字架链和佛教徒的念珠。

从古至今人们为了美化人体本身，也美化环境，制造了各种不同风格、不同特点、不同样式的项链，满足了不同肤色、不同民族、不同审美观的人的审美需要。就材料而论，首饰市场上的项链有黄金、白银、珠宝等几种。

珍珠项链为珍珠制成的饰品，即将珍珠钻孔后用线串在一起，佩戴于项间，天然珍珠项链具有一定的护养作用。

description:
最近，铭铭迷恋上了一种项链。与其他珍珠项链基本上相同，不过这种项链的珠子却与众不同，是正三菱柱的泰山石雕刻而成的。

三菱柱的侧面是由正方形构成的，每个侧面都刻有数字。能够让铭铭满意的项链必须满足以下条件：

1. 这串项链由 $n$ 颗珠子构成。

2. 每一个珠子上面的每个数字 $x$，必须满足 $0<x\le a$，且珠子上面三个数字的最大公约数要恰好为 $1$。

3. 相邻的两个珠子必须不同。两个珠子被认为是相同的，当且仅当它们经过旋转，或者翻转后能够变成一样的。

4. 两串项链如果能够经过旋转变成一样的，那么这两串项链被认为是相同的。

铭铭很好奇如果给定 $n$ 和 $a$，能够找到多少串不同的项链。由于答案可能很大，所以输出答案模上 $10^{9}+7$ 的值。

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

第一行给定一个整数 $T$，表示数据组数。
接下来 $T$ 行，每行两个整数 $n$ 和 $a$。

outputFormat: 对于每组数据输出一个整数，表示有多少串不同的项链。


title: [SDOI2014] LIS

description:
给定序列 $A$，序列中的每一项 $A_i$ 有删除代价 $B_i$ 和附加属性 $C_i$。请删除若干项，使得 $A$ 的最长上升子序列长度减少至少 $1$，且付出的代价之和最小，并输出方案。

如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。

inputFormat:
输入包含多组数据。

输入的第一行包含整数 $T$，表示数据组数。接下来 $4T$ 行描述每组数据。

每组数据的第一行包含一个整数 $N$，表示 $A$ 的项数。

接下来三行，每行 $N$ 个整数 $A_1\sim A_n$，$B_1\sim B_n$，$C_1\sim C_n$，满足 $1\le A_i,B_i,C_i \le 10^9$，且 $C_i$ 两两不同。

outputFormat: 对每组数据，输出两行。第一行包含两个整数 $S,M$，依次表示删去项的代价和与数量；接下来一行 $M$ 个整数，表示删去项在 $A$ 中的的位置，按升序输出。


title: [SDOI2014] 向量集

description:
维护一个向量集合，在线支持以下操作：

- `A x y`（$|x|,|y| \le 10^8$）：加入向量 $(x,y)$；
- `Q x y l r`（$|x|,|y| \le 10^8$，$1 \le l \le r \le t$，其中 $t$ 为已经加入的向量个数）：询问第 $l$ 个到第 $r$ 个加入的向量与向量 $(x,y)$ 的点积的最大值。

集合初始时为空。

inputFormat:
输入的第一行包含整数 $N(1 \le N \le 4 \times 10^5)$ 和字符 $s$，分别表示操作数和数据类别；

接下来 $N$ 行，每行一个操作，格式如上所述。

请注意 $s$ 不为 `E` 时，输入中的所有整数都经过了加密。你可以使用以下程序得到原始输入：

```
inline int decode(int x, long long lastans) {
    return x ^ (lastans & 0x7fffffff);
}
```

其中 `x` 为程序读入的数，`lastans` 为之前最后一次询问的答案。在第一次询问之前，`lastans` 为 $0$。注：向量 $(x, y)$ 和 $(z, w)$ 的点积定义为 $xz+yw$。

outputFormat: 对每个 `Q` 操作，输出一个整数表示答案。


title: [SDOI2014] 括号序列计数

description:
Alice 和 Bob 知道，一个由空格、左括号、右括号组成的序列被称为括号序列。有一类特殊的括号序列被称为"合法括号序列"。已知：

- 空串是合法括号序列；
- 如果 $S_1$ 和 $S_2$ 均是合法括号序列，则 $S_1+S_2$ 是合法括号序列；
- 如果 $S$是合法括号序列，则 $(+S+)$ 是合法括号序列；
- 如果 $S$ 是合法括号序列，在 $S$ 的任何位置（包括头尾位置）插入一个空格得到的序列是合法括号序列。

现在 Alice 希望知道：对于某个已知的有限状态自动机中的状态 $s$ 与 $t$ ，存在多少以 $s$ 为起点、$t$ 为终点、长度为 $k$ 的合法括号序列。

有限状态自动机是一个有向图 $G$，由 $n$ 个结点组成，每一个结点表示一个状态，且存在三类以此为起点的有向边。对于每一个状态，其向外的同一类有向边指向同样的状态。三类有向边分别代表三种符号：左括号、右括号和空格。

我们将状态从 $0$ 开始编号。对于第 $i$ 个状态，用 $dfa_{i,0/1/2}$ 分别表示从 $i$ 出发，代表了左括号、右括号和空格的那一类边指向的状态，再用 $dfa2_{i,0/1/2}$ 表示每一类边的个数。对于一条从 $s$ 出发到 $t$ 结束的路径，满足长度为 $k$ 且路径经过的边对应的符号构成的序列组成了一组合法的括号匹配，则称作"满足 $[G,s,t,k]$ 的合法括号序列"。

现在，Alice 为 Bob 提供了自动机 $G$，并提出 $Q$ 组询问。对于每一组询问，Alice 会给出 $s,t,k$，她希望 Bob 可以告诉她满足 $[G,s,t,k]$ 的合法括号序列有多少组。她只需要知道答案除以 $47$ 后的余数。

inputFormat:
第一行一个整数 $n$ 表示状态数，第二到 $n+1$ 行，第 $i$ 行六个整数 $dfa_{i-1,0},dfa2_{i-1,0},dfa_{i-1,1},dfa2_{i-1,1},dfa_{i-1,2},dfa2_{i-1,2}$，描述第 $i-1$ 个状态的出边。

接下来一行一个整数 $q$ 表示询问数，接下来 $q$ 行每行三个整数 $s,t,k$ 描述一组询问。

outputFormat: 输出 $q$ 行，每行一个整数表示对应询问的答案 $\bmod\ 47$ 的结果。

hint:
在样例解释中使用符号 `_` 代表空格。

对于第一组询问长度为 $3$ 的合法括号序列有：

- `___`，合法方案数为 $3^3 = 27$；
- `_()`、`(_)`、`()_`，合法方案数均为 $1\times2\times3=6$。

所以总方案数为 $27+6\times3=45$。

对于 $100 \%$ 的数据，$1 \leq n \leq 2$，$0 \leq dfa_{i,j} , s , t < n$，$0 \leq dfa2_{i,j} < 2^{31}$，$1 \leq k \leq 10^5$。


title: [SDOI2014] 数数

description:
我们称一个正整数 $x$ 是幸运数，当且仅当它的十进制表示中不包含数字串集合 $s$ 中任意一个元素作为其子串。例如当 $s = \{22, 333, 0233\}$ 时，$233$ 是幸运数，$2333$、$20233$、$3223$ 不是幸运数。给定 $n$ 和 $s$，计算不大于 $n$ 的幸运数个数。

答案对 $10^9 + 7$ 取模。

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

第二行有一个整数，表示 $s$ 中的元素个数 $m$。

接下来 $m$ 行，每行一个数字串 $s_i$，表示 $s$ 中的一个元素。

outputFormat: 输出一行一个整数，表示答案对 $10^9 + 7$ 取模的结果。

hint:
#### 样例 1 解释

除了 $3, 13, 2, 12, 20, 14$ 以外，不大于 $20$ 的整数都是幸运数字。

#### 数据规模与约定

对于全部的测试点，保证：

$1 \leq n < 10^{1201}$，$1 \leq m \leq 100$，$1 \leq \sum_{i = 1}^m |s_i| \leq 1500$，$\min_{i = 1}^m |s_i| \geq 1$，其中 $|s_i|$ 表示字符串 $s_i$ 的长度。$n$ 没有前导 $0$，但是 $s_i$ 可能有前导 $0$。


title: [SDOI2014] 数表

description: 有一张 $n\times m$ 的数表，其第 $i$ 行第 $j$ 列（$1\le i\le n$，$1\le j\le m$）的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$，计算数表中不大于 $a$ 的数之和。

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

输入的第一行一个整数 $Q$ 表示测试点内的数据组数。

接下来 $Q$ 行，每行三个整数 $n$，$m$，$a$（$|a|\le 10^9$）描述一组数据。

outputFormat: 对每组数据，输出一行一个整数，表示答案模 $2^{31}$ 的值。

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

对于全部数据，$1\le n,m\le 10^5$，$1\le Q\le 2\times 10^4$。


title: [SDOI2014] 旅行

description:
S 国有 $N$ 个城市，编号从 $1$ 到 $N$。城市间用 $N-1$ 条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。

为了方便，我们用不同的正整数代表各种宗教，S 国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S 国为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。

在 S 国的历史上常会发生以下几种事件：

- `CC x c`：城市 $x$ 的居民全体改信了 $c$ 教；
- `CW x w`：城市 $x$ 的评级调整为 $w$；
- `QS x y`：一位旅行者从城市 $x$ 出发，到城市 $y$，并记下了途中留宿过的城市的评级总和；
- `QM x y`：一位旅行者从城市 $x$ 出发，到城市 $y$，并记下了途中留宿过的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

inputFormat:
输入的第一行包含整数 $N,Q$ 依次表示城市数和事件数。

接下来 $N$ 行，第 $i+1$ 行两个整数 $W_i,C_i$ 依次表示记录开始之前，城市 $i$ 的评级和信仰。

接下来 $N-1$ 行每行两个整数 $x,y$ 表示一条双向道路。

接下来 $Q$ 行，每行一个操作，格式如上所述。

outputFormat: 对每个 `QS` 和 `QM` 事件，输出一行，表示旅行者记下的数字。

hint:
对于 $100\%$ 的数据，$N,Q \leq10^5,C \leq10^5$

数据保证对所有 `QS` 和 `QM` 事件，起点和终点城市的信仰相同；在任意时刻，城市的评级总是不大于 $10^4$ 的正整数，且宗教值不大于 $C$。


title: [SDOI2014] 电路板

description:
对于用户给出的电路图和指定大小的电路板，Alice和Bob需要将电路在电路板上实现出来。

所谓电路板，可以看作是一个n\*m的格子图。 用户给定的电路由若干电路原件组成，每一个电路原件可能会占用一个或多个格子。这里，我们将被电路原件占据的格子分为两类。

第一类只是纯粹占据了这个格子，之后这个格子不会再被使用，也不会从被占据的位置连出去任何的电路线。这样的格子被我们视作是电路板上的障碍物。

还有一类格子，我们称为是电路原件的接口，上面虽然被电路原件占用，但是仍有可能从其中连出去一些电路线到其它的电路原件上，从而形成电路。

对于电路图中一些链接某两个原件的电路线，我们可以指定为电路板上的k个格子对，要求每对格子对之间连一条电路线。 同一个格子可能属于多个格子对（比如一些并联电路）。 任意两条电路线不能相交（但可以连接到同一个有着电路原件的格子中），且电路板上的每一个格子的每一条边都只能经过一条电路线。（所以每一个电路原件的接口上只能接出去最多4条不同的电路线）。然而，每一个不被电路原件占用的格子内却可以经过多条电路 线。

具体来说：为了保证电路线不相交，可以一条电路线从上边界进入当前格子，从左边界离开这个格子，另外一条电路线可以从下边界进入格子，从右边界出去。（需要注意的是：电路线本身是没有方向感念的，即格子对描述的边关系是无向边。所以这样的方案也可以描述为从左边界进入后从上边界出去，从右边界进入后从下边界出去）相似的方案还有好几种。

现在，Alice希望找到一个可行方案，使得路径的总长度最短。而Bob则希望知道满足最短长度的方案有多少种。

inputFormat:
第一行三个整数，n,m,k，表示电路板的大小，以及需要连接电路线的格子对个数。

接下来m行，每行n个整数，为0或1。0代表当前格子可以用，否则表示有障碍，不能使用。

接下来k行，每行4个整数x1,y1,x2,y2，给出一组格子对，表示对应的电路要连接 的两个格子。格子的行列都从0开始编号，所以0<=x1,x2<n，0<=y1,y2<m。

本题有多组数据（最多30组），输入文件最后以0 0 0 结束。

outputFormat:
对于每组数据，输出两个整数，最短电线长度和最短电线长度的方案数。 方案数只需要输出对25619849取余数后的结果。

如果无解，输出-1 0。

hint:
样例解释：

第一组数据：(1,2)与(2,1)之间有4条路径，立刻可以发现，最短路径长度和为16。对于每一种可行方案，任意一条(1,2)与(2,1)之间的路径都可以对应要求的4条路径中的任何一条。而若就形态来说，完全不同的方案有4种，考虑到排列数4!＝24，所以总的方案为96种。

第二组数据：因为有3个障碍点，所以可行路径只有一条。


title: [SDOI2014] 酗酒者

description:
$\text{Alice}$ 发现：人在心情不好的时候，便会选择酗酒。这往往与 $\text{OI}$ 选手比赛胜利后的欢腾庆祝不同，酗酒者喝醉后便会忘记回家的路，然后在大街上无规律地乱走乱逛，同时喊着一些谁也听不懂的话。

这几天， $\text{Bob}$  因为考试的原因心情很不好，每天晚上都会在城里面找一处酒吧。喝醉后离开酒吧开始在城市街道中无规律乱走，直到某一时刻，若他碰巧遇到了在夜晚出来看星星的 $\text{Alice}$ ，便会被她带回家。

已知 $\text{Alice}$ 和 $\text{Bob}$  所在的城市街道可以被描绘为一个 $N$ 行 $M$ 列的格点地图， $N$ 行依次编号为 $0$ 到 $N-1$ ， $M$ 列依次编号为 $0$ 到 $M-1$ 。城市中共有 $N \times M$ 处路口，每一个路口可以用坐标 $(i,j)$ 表示。若 $i<N$ ，则 $(i,j)$ 与 $(i+1,j)$ 有无向的连边，边权长度 ， $p_{(i,j)}$ 表示走过这一条路所需的时间。若 $j<M$ ，则 $(i,j)$ 与 $(i,j+1)$ 有连无向边，边权长度 $q_{(i,j)}$ 。

对于给定的两个点 $(u,v)$ 和 $(s,t)$ 分别为 $\text{Bob}$ 今晚去的酒吧的位置，和 $\text{Alice}$ 今晚看星星的位置。 $\text{Bob}$ 离开酒吧后，对于每一个路口，他会等概率选择其中之一，然后走向下一个路口。在走到下一个路口之前， $\text{Bob}$ 不会回头。同时 $\text{Bob}$ 并不会因为之前走过什么道路而影响之后的行走路线。

具体来说：如果 $\text{Bob}$ 从 $(3,4)$ 走到 $(3,5)$ ，他有可能在抵达 $(3,5)$ 后立刻折回 $(3,4)$。对于四叉路口， $\text{Bob}$ 向每一个方向行走的概率都是 $1/4$ ，对于三叉路口（这只存在于城市的边界上）则是 $1/3$ ，对于二叉路口（这只存在于城市的 $4$ 个角落）就是 $1/2$。

$\text{Alice}$ 希望知道，从 $\text{Bob}$ 离开酒吧， $\text{Alice}$ 期望情况下还需要等多久才能等到 $\text{Bob}$ ，即对于给定的两个点 $(u,v)$ 与 $(s,t)$，$\text{Bob}$ 从 $(u,v)$ 走到 $(s,t)$ 的期望用时是多少？

inputFormat:
第一行 $N$ ， $M$ 。 之后 $N-1$ 行，每行 $M$ 个正整数，其中第 $i$ 行第 $j$ 个为 $p_{(i,j)}$ 。

之后 $N$ 行，每行 $M-1$ 个正整数，其中第 $i$ 行第 $j$ 个为 $q_{(i,j)}$ 。 单独一行给出一个整数 $Q$ ，表示总询问次数。

之后 $Q$ 行，每行有 $4$ 个整数 $u$ ，$v$ ，$s$ ，$t$ 。

outputFormat: 一共 $Q$ 行，每一行对应一次询问：从 $(u,v)$ 走到 $(s,t)$ 的期望时间是多少？你的答案可以保留任意多位小数，但只有与正确答案的错误率在 $0.1\%$ 内才算正确。

hint:
对于 $10\%$ 的数据， $N \times M \le 25$ 。

对于 $30\%$ 的数据， $N \times M \le 625$ 。

对于 $50\%$的数据， $N \times M \le 2500$。

对于 $100\%$ 的数据， $1\leq N \times M \le 10^4$ ， $1\leq Q\leq 100$ 。 $\forall i,j$ , $1\leq p_{(i,j)},q_{(i,j)} \le 200$，$N,M\geq 1$。

此外存在 $10\%$ 的数据，$\min(N,M) \le 10$。


title: [SDOI2014] 里面还是外面

background:
upd：

- 数据更新：现在选取了原题的总共 10 个测试点，并删除了其中两个不符合题意的。

description:
Alice给出了平面上的一个简单N-多边形。所谓简单N-多边形，包括N个给定的端点，和连接相邻点的直线段，特别的，我们认为1号点与N号是相邻的。

对于边界上不同的直线段，保证它们只会在公共端点处相交。有的时候Alice会指着平面上一个点，然后问Bob：”这个点是在多边形的里面呢，还是外面呢，还是在边界上呢？“

这个时候，如果她所指的点是多边形的一个顶点或者在多边形某条边的边界上，都将被认为是在多边形的边界上。还有的时候，Alice为了加大难度，会删除连接a和b的边，并插入新的点c（新插入的点保证不与任何已有的端点重合，也不在任何边界上），然后新增a到c的边与b到c的边，从而得到一个新的简单多边形。

Alice保证这样的操作得到的新图形总是简单多边形。Bob要做的，就是准确回答出Alice的提问。而实际上，Alice的每一次提问都将由Bob上一次的回答决定，虽然这个回答是唯一的，但却意味着如果Bob不能回答出前一个问题，就不能拿到Alice的下一个问题。

不过，Alice对多边形的修改确实事先准备好的。详细来说：Alice的每一次修改命令可以看作是一个六元组：〈x\_a，y\_a，x\_b，y\_b，x\_c，y\_c〉表示删除了坐标位置（x\_a，y\_a），与坐标位置（x\_b，y\_b）的点之间的连边，并插入新的点（x\_c，y\_c）。

这里我们保证坐标为（x\_a，y\_a）的点与坐标为（x\_b，y\_b）的点总是存在的。因为Alice保证了所有出现的点（这包括了询问点）的坐标都是非负整数，且都小于1000000000，且多边形中（这不包括询问点）任意两个点的x坐标不同，y坐标也不同。所以每一次询问Alice将给出7个非负整数：r，x\_{in}，y\_{in}，x\_{out}，y\_{out}，x\_{bd}，y\_{bd}而Alice这一次询问真正要询问的点（X，Y）的坐标将由上一次询问的点（x\_0，y\_0）与上一次询问的回答而决定。例如，若上一次询问的点在多边形外，则：X = (r \* x\_0 + x\_{out}) mod 1000000000Y = (r \* y\_0 + y\_{out}) mod 1000000000对于第一次讯问，我们假设x\_0 = y\_0 = 0，也就是说将(0,0)考虑为前一次的询问。

inputFormat:
输入文件的第一行有一个整数N，表示初始时多边形的点数。

之后N行，每行一对非负整数x和y（0<=x,y<1000000000）。按照某一顺序依次描述了多边形的所有顶点的坐标，并编号为1到N。这里我们只认为，对于平面上的一点(10^100,10^100)一定是处在多边形以外的。之后一行有一个整数Q，表示总的操作次数。

之后Q行，每行第一个数字p，如果p=0，则表示询问；如果p=1，则表示修改。
- 对于询问，之后给出了7个非负整数，它们是：r，x\_{in}，y\_{in}，x\_{out}，y\_{out}，x\_{bd}，y\_{bd}
- 对于修改，之后给出了6个整数，它们是：x\_a，y\_a，x\_b，y\_b，x\_c，y\_c

outputFormat: 对于每一次询问操作，单独输出一行且只包含一个字符串，它或者是in、或者是out、或者是bd（均为小写字符），分别表示询问点在多边形的内、外或边界。

hint: 对于100%的数据：N<=50000，Q<=50000，所有坐标非负且均小于1000000000，而r或者为1或者为0。


title: [SDOI2014] 重建

description:
T 国有 $N$ 个城市，用若干双向道路连接。一对城市之间至多存在一条道路。

在一次洪水之后，一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况，但直到现在几乎没有消息传回。

幸运的是，此前 T 国政府调查过每条道路的强度，现在他们希望只利用这些信息估计灾情。具体地，给定每条道路在洪水后仍能通行的概率，请计算仍能通行的道路恰有 $N-1$ 条，且能联通所有城市的概率。

inputFormat:
输入的第一行包含整数 $N$。

接下来 $N$ 行，每行 $N$ 个实数，第 $i+1$ 行，列的数 $G_{i,j}$ 表示城市 $i$ 与 $j$ 之间仍有道路联通的概率。

输入保证 $G_{i,j}=G_{j,i}$，且 $G_{i,i}=0$。$G_{i, j}$ 至多包含两位小数。

outputFormat:
输出一个任意位数的实数表示答案。

你的答案与标准答案相对误差不超过 $10^{-4}$ 即视为正确。

hint:
$1<N\leq 50$。

数据保证答案非零时，答案不小于 $10^{-4}$。


title: [SDOI2015] 双旋转字符串

description:
给定两个字符串集合 S 和 T 。其中 S 中的所有字符串长度都恰好为 N ，而 T 中所有字符串长度都恰好为 M 。且 N+M 恰好为偶数。如果记 S 中字符串全体为 S1，S2，...，STotalS ,而 T 中字符串全体为 T1，T2，...，TTotalT 。现在希望知道有多少对 <i,j> ，满足将 Si 和 Tj 拼接后得到的字符串 Si+Tj 满足双旋转性。

一个长度为偶数字符串 W 可以表示成两段长度相同的字符串的拼接，即 W=U+V。如果 V 可以通过 U 旋转得到，则称 W 是满足双旋转性的。比如说字符串 U=”vijos“可以通过旋转得到”ijosv“，”josvi“，”osvij“ 或”svijo“。那么”vijosjosvi“就是满足双旋转性的字符串。

inputFormat: 第一行输入四个正整数，分别为 TotalS，TotalT，N 和 M，依次表示集合 S 的大小，集合 T 的大小，集合 S 中字符串的长度和集合 T 中字符串的长度。之后 TotalS 行，依次给出 S 中所有的字符串 Si，1<=i<=TotalS。保证每一个字符串长度都恰为 N ，且字符串只由 26 个小写字母组成。之后 TotalT 行，依次给出 T 中所有的字符串 Ti，1<=i<=TotalT。保证每一个字符串长度都恰为 M ，且字符串只由 26 个小写字母组成。1<=N<=100；1<=M<=100；1<=TotalS<=100；1<=Total^T<=100,2<=N\*TotalS+M\*TotalT<=4×10^6

outputFormat: 输出一个整数，表示满足要求的数字对 <i,j> 有多少个。

samples:
4 4 7 3
vijosvi
josvivi
vijosos
ijosvsv
jos
vij
ijo
jos


title: [SDOI2015] 嫁接树

description:
Alice 设计了一个树结构，有 $N$ 个结点（包括根）被依次编号为 $1$ 到 $N$，由 $N-1$ 条边连接。后来，Bob 在上面增加了 $K$ 条原来没有的边（也就是说既不是自环，也不会因此产生重边）并称这样得到的图为” $K$-嫁接树“。

现在 Alice 希望对嫁接树的每一个结点进行染色，允许使用的颜色恰有 $N$ 种，分别编号为 $1$ 到 $N$。Alice 要求相邻两个结点要涂上不同的颜色。假设颜色为 $i$ 的结点有 $t_i$ 个，则 Bob 给出了如下的评价分数：

$$\mathit{score}=\dfrac{t_1+\dfrac{1}{2}t_2+\dfrac{1}{3}t_3+\cdots+\dfrac{1}{N}t_N}{1+P\times (t_1+2t_2+3t_3+\cdots+Nt_N)}$$

其中 $P$ 为非负系数。现在，Alice 希望可以找到一种染色方案，使得 Bob 给出来的评分最大。你能帮助他吗？

inputFormat:
第一行有 $2$ 个整数，依次为 $N$ 和 $K$，如题所述。第二行到第 $N+K$ 行，每行有两个整数 $u$ 和 $v$，依次给出了 $N+K-1$ 条边。**其中，首先给出 $N - 1$ 条树边，其次给出新增加的边**。保证不存在自环，也不存在重边。最后一行给定非负浮点数 $P$。

$K \le 2$，$1 \le N \le 2 \times 10^5$，$0 \le P<10$。

outputFormat: 输出最大的可能评分，四舍五入保留到小数点后第三位。

hint: 2024-10-11 update: 更新了数据精度问题


title: [SDOI2015] 寻宝游戏

description:
小 B 最近正在玩一个寻宝游戏，这个游戏的地图中有 $N$ 个村庄和 $N-1$ 条道路，并且任何两个村庄之间有且仅有一条路径可达。游戏开始时，玩家可以任意选择一个村庄，瞬间转移到这个村庄，然后可以任意在地图的道路上行走，若走到某个村庄中有宝物，则视为找到该村庄内的宝物，直到找到所有宝物并返回到最初转移到的村庄为止。

小 B 希望评测一下这个游戏的难度，因此他需要知道玩家找到所有宝物需要行走的最短路程。但是这个游戏中宝物经常变化，有时某个村庄中会突然出现宝物，有时某个村庄内的宝物会突然消失，因此小 B 需要不断地更新数据，但是小 B 太懒了，不愿意自己计算，因此他向你求助。为了简化问题，我们认为最开始时所有村庄内均没有宝物。

inputFormat:
第一行，两个整数 $N,M$，其中 $M$ 为宝物的变动次数。

接下来的 $N-1$ 行，每行三个整数 $x,y,z$，表示村庄 $x,y$ 之间有一条长度为 $z$ 的道路。

接下来的 $M$ 行，每行一个整数 $t$，表示一个宝物变动的操作。若该操作前村庄 $t$ 内没有宝物，则操作后村庄内有宝物；若该操作前村庄 $t$ 内有宝物，则操作后村庄内没有宝物。

outputFormat: $M$ 行，每行一个整数，其中第 $i$ 行的整数表示第 $i$ 次操作之后玩家找到所有宝物需要行走的最短路程。若只有一个村庄内有宝物，或者所有村庄内都没有宝物，则输出 `0`。

hint:
- 对于 $10\%$ 的数据，$1 \leq N \leq 100, 1 \leq M \leq 100$；
- 对于 $20\%$ 的数据，$1 \leq N \leq 1000, 1 \leq M \leq 1000$；
- 对于另外 $15\%$ 的数据，每个村庄最多成为两条道路的端点；
- 对于 $100\%$ 的数据，$1 \leq N \leq 100000,\ 1 \leq M \leq 100000,\ 1 \leq z \leq 10^9$。


title: [SDOI2015] 序列统计

description:
小C有一个集合 $S$，里面的元素都是小于 $m$ 的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为 $n$ 的数列，数列中的每个数都属于集合 $S$。

小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数 $x$，求所有可以生成出的，且满足数列中所有数的乘积 $\bmod \ m$ 的值等于 $x$ 的不同的数列的有多少个。

小C认为，两个数列 $A$ 和 $B$ 不同，当且仅当 $\exists i \text{ s.t. } A_i \neq B_i$。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案对 $1004535809$ 取模的值就可以了。

inputFormat:
一行，四个整数，$n,m,x,|S|$，其中 $|S|$ 为集合 $S$ 中元素个数。
第二行，$|S|$ 个整数，表示集合 $S$ 中的所有元素。

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


title: [SDOI2015] 排序

description:
小 A 有一个 $1\sim 2^N$ 的排列 $A_1\sim A_{2^N}$，他希望将 $A$ 数组从小到大排序,小 $A$ 可以执行的操作有 $N$ 种，每种操作最多可以执行一次，对于所有的 $i(1\le i\le N)$，第 $i$ 种操作为将序列从左到右划分为 $2^{N-i+1}$ 段，每段恰好包括 $2^{i-1}$ 个数,然后整体交换其中两段。

小 A 想知道可以将数组 $A$ 从小到大排序的不同的操作序列有多少个。小 A 认为两个操作序列不同，当且仅当操作个数不同，或者至少一个操作不同（种类不同或者操作位置不同）。

下面是一个操作事例: $N=3,A=[3,6,1,2,7,8,5,4]$。
- 第一次操作，执行第 $3$ 种操作，交换 $A[1..4]$ 和 $A[5..8]$，交换后的 $A$ 为$[7,8,5,4,3,6,1,2]$。
- 第二次操作，执行第 $1$ 种操作，交换 $A[3]$ 和 $A[5]$，交换后的 $A$ 为$[7,8,3,4,5,6,1,2]$。
- 第三次操作，执行第 $2$ 种操作，交换 $A[1..2]$ 和 $A[7..8]$，交换后的 $A[1..8]$ 为$[1,2,3,4,5,6,7,8]$。

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

第二行，$2^N$ 个整数，$A_1\sim A_{2^N}$。

outputFormat: 一个整数表示答案。


title: [SDOI2015] 旅行计划

description:
在有 $N$ 座城市的国度，Alice 希望可以开始一场充满传奇的旅行。TA 希望可以从一个城市出发开始旅行，每次前往一个相邻的城市，途中不重复得经过恰好 $K$ 座城市，最后抵达另外一个城市并结束旅行。

需要注意的是，起点与终点也被考虑为经过的城市，也就是说包括起点和终点在内经过的所有城市都是不能重复的。现在，Alice 希望知道哪些城市对 $(u,v)$ 可以作为合法的旅行起点与终点。

inputFormat:
本题每一个测试点有多组测试数据。

第一行给定正整数 $T$ ，表示数据组数。

对于每一组数据来说，第一行给定三个整数 $N$，$M$ 和 $K$，表示城市个数，城市之间的相邻关系个数，还有旅途应该经过的城市个数。

接下来 $M$ 行．每一行给定两个整数 $u$ 和 $v$ ，表示标号为 $u$ 的城市与标号为 $v$ 的城市之间是相邻的，即可以从其中一个城市出发前往另外一个。

$N\le 1000$，$M\le 5000$，$2\le K\le 7$ 且 $T\times \left\lfloor \frac k 2 \right\rfloor^{\left\lfloor \frac k 2 \right\rfloor}\le 60$

outputFormat: 对于每一组数据，输出 $N$ 行，每行 $N$ 个字符，其中第 $i$ 行第 $j$ 个字符，或者为 `Y` 或者为 `N`，分别表示是否存在从城市 $i$ 出发到城市 $j$ 结束的合法旅行方案。


title: [SDOI2015] 星际战争

description:
$3333$ 年，在银河系的某星球上，X 军团和 Y 军团正在激烈地作战。

在战斗的某一阶段，Y 军团一共派遣了 $N$ 个巨型机器人进攻 X 军团的阵地，其中第 $i$ 个巨型机器人的装甲值为 $A_i$。当一个巨型机器人的装甲值减少到 $0$ 或者以下时，这个巨型机器人就被摧毁了。

X 军团有 $M$ 个激光武器，其中第 $i$ 个激光武器每秒可以削减一个巨型机器人 $B_i$ 的装甲值。激光武器的攻击是连续的。

这种激光武器非常奇怪，一个激光武器只能攻击一些特定的敌人。Y 军团看到自己的巨型机器人被 X 军团一个一个消灭，他们急需下达更多的指令。

为了这个目标，Y 军团需要知道 X 军团最少需要用多长时间才能将 Y 军团的所有巨型机器人摧毁。但是他们不会计算这个问题，因此向你求助。

inputFormat:
题面修理器
第一行，两个整数，N,M。

第二行，N个整数，A1,A2...AN。

第三行，M个整数，B1,B2...BM。

接下来的M行，每行N个整数，这些整数均为0或者1。这部分中的第i行的第j个整数为0表示第i个激光武器不可以攻击第j个巨型机器人，为1表示第i个激光武器可以攻击第j个巨型机器人。

专有名词（用,隔开）

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

第二行，$N$ 个整数，$A_1,A_2 \cdots A_N$。

第三行，$M$ 个整数，$B_1,B_2 \cdots B_M$。

接下来的 $M$ 行，每行 $N$ 个整数，这些整数均为 $0$ 或者 $1$。这部分中的第 $i$ 行的第 $j$ 个整数为 $0$ 表示第 $i$ 个激光武器不可以攻击第 $j$ 个巨型机器人，为 $1$ 表示第 $i$ 个激光武器可以攻击第 $j$ 个巨型机器人。

outputFormat: 一行，一个实数，表示 X 军团要摧毁 Y 军团的所有巨型机器人最少需要的时间。输出结果与标准答案的绝对误差不超过 $10^{-3}$ 即视为正确。

hint:
**【样例说明1】**

战斗开始后的前 $0.5$ 秒，激光武器 $1$ 攻击 $2$ 号巨型机器人，激光武器 $2$ 攻击 $1$ 号巨型机器人。$1$ 号巨型机器人被完全摧毁，$2$ 号巨型机器人还剩余 $8$ 的装甲值；

接下来的 $0.8$ 秒，激光武器 $1$ 、 $2$ 同时攻击 $2$ 号巨型机器人。$2$ 号巨型机器人被完全摧毁。

**【数据范围】**

对于全部的数据，$1 \le N,M \le 50$，$1 \le A_i \le 10^5$，$1 \le B_i \le 1000$，输入数据保证 X 军团一定能摧毁 Y 军团的所有巨型机器人。

[spj]


title: [SDOI2015] 模拟电路

description:
一家著名的芯片公司希望您能帮他们在一些最新的产品上安装可以稳定电压的组件。每块芯片都被设计成 $N\times M$ 的带插槽的正方形，一个插槽可以安装一块单独的组件，你的任务是尽可能多地插入这些组件。

现代处理器的设计是很复杂的。为了可以稳定电压，你要面对下面几个限制：一些插槽是不可用的。一些插槽已经被其它的组件占据了，因而无法被新的组件使用。内存总线要连接到芯片的水平和垂直的边界上，它们的负载电压需要是安全的。

具体来说，芯片公司提供了 $N$ 组限制条件，分别对应了 $N$ 行。其中对于第 $i$ 行以及第 $i$ 组限制条件，给定非负整数 $T_i$ 与 $T_i$ 个列编号，记为 $r_{i,j}$（$1\le j\le T_i$），要求满足：第 $i$ 行的组件数目不能超过指定的 $T_i$ 个列方向上组件数目的和（也就是不超过“第 $r_{i,1}$ 列的组件数目 $+$ 第 $r_{i,2}$ 列的组件数目 $+$ $\cdots$”）。为了避免插槽过热，给定浮点数 $s_i$（$1\le i\le N$） 且 $0\le s_i\le 1$，要求第 $i$ 行的组件数不超过总组件数的 $s_i$。同样给定浮点数 $t_i$（$1\le i\le N$）且 $0\le T_i\le 1$，要求第 $i$ 列的组件数不超过总组件数的 $t_i$。

需要注意的是，已经占据了位置的组件，在统计一行或一列组件总数时，也是要被考虑在内的。而在计算芯片总组件数时．也要将已经占据了位置的组件考虑进去。芯片被描述为一个 $N$ 行，每行 $N$ 个字符的矩阵，其中 `.` 表示开放插槽，`/` 表示不可用插槽，`C` 表示插槽已被一个组件占据。

inputFormat:
第一行给定 $1$ 个正整数，表示芯片的规模 $N$（$1\le N\le 40$）。

然后给出 $N$ 行，每行 $N$ 个字符描述插槽，字符为 `.` ， `/` 或 `C` 之一，含义如上所述。

之后 $N$ 行，描述了限制条件。其中第 $i$ 行首先给出非负整数 $T_i$，表示第 $i$ 行的限制条件涉及到的列的个数。之后再给出 $T_i$ 个不重复的整数（都在 $1$ 到 $N$ 的范围中），描述了相关的列。

再下一行，给出了 $N$ 个浮点数依次对应 $s_i$。每一个数字小数点后不超过三位。

再下一行，给出了 $N$ 个浮点数依次对应 $t_i$。每一个数字小数点后不超过三位。

outputFormat: 如果存在合法的策略，输出最多可以再在芯片上安装多少个组件。否则输出 `impossible`。


title: [SDOI2015] 立体图

description:
小渊是个聪明的孩子，他经常会给周围的小朋友们讲些自己认为有趣的内容。最近，他准备给小朋友们讲解彩色水平光源照射下的立体图，并请你帮他在平面上画出来。

小渊有一块面积为m\*n的矩形区域，上面有m\*n个边长为1的格子，每个格子上堆了一些同样大小的积木（积木的长宽高都是1）。

为了方便阐述，我们假设这块区域是坐北朝南的，下面我们给出一个例子。

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

小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式，并且不会做任何翻转旋转，只会严格以这一种形式摆放（左侧是应该打印出来的图样，右侧为对应每一个位置符号的十进制ASCII，其中ASCII为32的符号为空

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

在良好的光学环境下，小渊将T束平行光同时照射在这些积木上。这些平行光首先满足一定是红绿蓝三基色之一，其次入射角度满足：与x轴y轴的夹角度数均为45的倍数；且与z轴正方向的夹角或为45度，或为0度，或为315度。

具体来说，我们最多会考虑9个方向的不同平行光，它们的入射方向可以被描述为：   西北方45度仰角  正北方45度仰角  东北方45度仰角   正西方45度仰角  垂直从上入射光  正东方45度仰角   西南方45度仰角  正南方45度仰角  东南方45度仰角对于每一个单位积木来说，可以打印出来的三个表面被分为12个小三角形，如下图所示（下图中用符号0,1,2,。。

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

红绿蓝三基色分别用字母RGB来表示。而二次叠加后的三种颜色青黄紫，分别用CYP来表示。对于三次叠加后的颜色，也就是白色，用W来表示。

inputFormat: 第一行有两个正整数m和n，表示区域有m行n列。之后m行，依次由远及近描述了每一行的情况。每一行给出n个正整数，表示第i行第j列中有堆放了多少积木。之后3行，每行三个字符，描述了9个对应方向（与地图描述方向相同）的光照颜色。其中每一个字符或者为RGB中之一，表示对应的颜色。或者为\*，表示没有照射光。这九个方向依次是：   西北方45度仰角  正北方45度仰角  东北方45度仰角   正西方45度仰角  垂直从上入射光  正东方45度仰角   西南方45度仰角  正南方45度仰角  东南方45度仰角

outputFormat: 输出给出了打印后的效果。其中要求输出结果不含前导空行，结尾也没有额外空行。输出的第一列不能全是空格，且每一行末尾也没有额外空格。

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

对于15%的数据，1<=n,m<=100,没有入射光。

对于40%的数据，1<=n,m<=100,入射光只有一束，且入射方向一定是东南方。

对于100%的数据，1<=n,m<=100，每一个位置堆放的积木总数不超过100,入射光颜色可能是RGB中的任何一种颜色，最多可以有9束入射光。


title: [SDOI2015] 约数个数和

description:
设 $d(x)$ 为 $x$ 的约数个数，给定 $n,m$，求
$$\sum_{i=1}^n\sum_{j=1}^md(ij)$$

inputFormat:
输入文件包含多组测试数据。
第一行，一个整数 $T$，表示测试数据的组数。
接下来的 $T$ 行，每行两个整数 $n,m$。

outputFormat: $T$ 行，每行一个整数，表示你所求的答案。

hint:
【数据范围】
对于 $100\%$ 的数据，$1\le T,n,m \le 50000$。


title: [SDOI2015] 音质检测

description:
万老板希望在新的智能音乐播放设备 $\operatorname{IPOOD}$ 中，实现对波文件音质性能的评定。离散的波文件被考虑为长度为 $N$ 的整数序列：$A_1,A_2,\cdots,A_N$。所谓的音质性能检测，可以评定任何的一个区间范围 $[L,R]$ ，音质性能取决于下述评分：

$$\sum_{L<i<R}F[A_{i-1}+1]F[A_{i+1}-1] \operatorname{mod}\;(10^9+7)$$

其中 $F$ 是可归纳定义的数列，满足 $F_1=1$，$F_2=2$ 且 $F_{k+2}=F_{k+1}+aF_{k}+b$ 对于任何 $k>0$ 成立。

其中 $a$ 和 $b$ 为正整系数。为了可以为用户提供更好的服务体验，并希望对给定的波文件进行修正优化。这一款设备中，还应该支持对波文件的修改。对于给定的区间范围 $[L,R]$ ，允许用户将 $A_L$ 至 $A_R$ 同时增加一，或同时减少一。

inputFormat:
输入的第一行有两个正整数，波文件的总长度 $N$ ，和总的修改与询问次数 $Q$ 。

第二行有两个整数，分别表示系数 $a$ 和 $b$ 。

之后若干行，一共给出 $N$ 个正整数 $A_1$ 到 $A_N$ ，满足 $1\leq A_i\leq 2\times 10^9$ 。

之后 $Q$ 行，每行是下述三种形式之一：
- $\text{plus}\;L\;R:$将波文件数列中下标在区间 $[L,R]$ 内的元素每一个都加一。
- $\text{minus}\;L\;R:$将波文件数列中下标在区间 $[L,R]$ 内的元素每一个都减一。
- $\text{query}\;L\;R:$询问区间 $[L,R]$ 的音质性能评分。修改和询问中，均保证 $L\leq R$ ，且保证 $A_i$ 严格大于总的修改次数加一(修改操作包括 $\text{plus}$ 和 $\text{minus}$ 两种)。

outputFormat: 输出若干行，每一行对应一次询问，输出一个整数。

samples:
7 7
1 0
3 4 5 6 7 8 9
query 2 4
query 3 7
plus 3 5
query 2 4
plus 4 7
query 3 7
query 1 7


title: [ZJOI2011] 最小割

description:
小白在图论课上学到了一个新的概念——最小割，下课后小白在笔记本上写下了如下这段话：

对于一个图，某个对图中结点的划分将图中所有结点分成两个部分，如果结点 $s$ 和 $t$ 不在同一个部分中，则称这个划分是关于 $s,t$ 的割。对于带权图来说，将所有顶点处在不同部分的边的权值相加所得到的值定义为这个割的容量，而 $s,t$ 的最小割指的是在关于 $s,t$ 的割中容量最小的割。

现给定一张无向图，小白有若干个形如“图中有多少个无序点对的最小割的容量不超过 $x$ ”的疑问，小蓝虽然很想回答这些问题，但小蓝最近忙着挖木块，于是作为小蓝的好友，你又有任务了。

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

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

对于每组测试数据，第一行两个整数 $n,m$，表示图的点数和边数。

接下来 $m$ 行，每行三个整数 $u,v,c$ 表示有一条权为 $c$ 的无向边 $(u,v)$。不保证图中无重边。

接下来一行一个整数 $q$ 表示询问的个数，下面 $q$ 行每行一个整数 $x$ 描述一组询问。

outputFormat:
对于每一组测试数据输出 $q$ 行，每行一个整数表示对应询问的答案。对于满足条件的点对 $(p,q)$ 和点对 $(q,p)$ 只应该在答案中统计一次。

**在两组测试数据之间需要输出一行空行。**


title: [ZJOI2011] 看电影

description:
到了难得的假期，小白班上组织大家去看电影。但由于假期里看电影的人太多，很难做到让全班看上同一场电影。最后大家在一个偏僻的小胡同里找到了一家电影院，但这家电影院分配座位的方式很特殊，具体方式如下：

电影院的座位共有 $K$ 个，并被标号为 $1 \sim K$。每个人买完票后会被随机指定一个座位，具体来说是从 $1 \sim K$ 中等概率随机选取一个正整数，设其为 $L$。

如果编号 $L$ 的座位是空位，则这个座位就分配给此人，否则将 $L$ 加一，继续前面的步骤；如果不存在编号 $L$ 的座位，则该人只能站着看电影，即所谓的站票。

小白班上共有 $N$ 人（包括小白自己），作为数学爱好者，小白想知道全班都能够有座位的概率是多少。

inputFormat: 本题有多组数据。第一行一个整数 $T$ 表示数据组数，接下来 $T$ 行每行两个整数 $N,K$ 表示人数和电影院座位数。

outputFormat: 对于每一组数据数据输出一行两个整数 $A,B$，表示答案为 $\frac{A}{B}$。你需要保证 $\gcd(A,B) = 1$。

hint: 对于 $100 \%$ 的数据，$1 \leq T \leq 50$，$1 \leq N,K \leq 200$。


title: [ZJOI2011] 礼物

description:
小白的生日就要到了，小蓝决定送一件自己亲手做的手工艺品使自己的礼物与众不同。具体来说，小蓝已经通过某种方式制作出了一个 $p\times q\times r$ 的木块（由 $pqr$ 个单位小木块组成）。

但由于小蓝手艺不精，现在这个木块中的有些单位小木块是有问题的（有裂缝、里面是空心等等），这样的礼物小蓝是不可能直接送出去的。于是小蓝决定在这个木块中再挖出一个 $a\times a\times b$ 的子木块（即要求挖出的长方体木块存在两条长度相等的相邻边），当然这个子木块中是不能包含有问题的单位小木块的。

为了使这个木块上能包含更多的图案，小蓝希望从所有可行的方案中挑取 $4ab$ 的值最大的方案。但小蓝光检测木块中哪些地方有问题就已经耗尽了体力，作为小蓝的好友，你能帮帮小蓝吗？

inputFormat:
每个输入文件中仅包含一个测试数据。

第一行包含三个由空格隔开的正整数，$p,q,r$。

接下来有 $pq$ 行，每行包含 $r$ 个字符，每个字符只可能是 `P`（Poor）或者 `N`（Nice），分别表示该单位小木块有问题或者没问题。具体的说，第 $1+(yp+x-p)$ 行的第 $z$ 个字符描述的是坐标为 $(x,y,z)$ 的小木块情况。

outputFormat: 输出文件仅包含一个整数，表示最佳方案的 $4ab$ 的值。

samples:
3 2 5
PNNNN
PNNNN
NPPNP
PNNNP
NNNNP
PPNNP

hint: 对于 $100\%$ 的数据，$0<p,q,r\le 150$，输入中至少包含一个 `N`。


title: [ZJOI2013] K大数查询

description:
你需要维护 $n$ 个可重整数集，集合的编号从 $1$ 到 $n$。
这些集合初始都是空集，有 $m$ 个操作：

- `1 l r c`：表示将 $c$ 加入到编号在 $[l,r]$ 内的集合中
- `2 l r c`：表示查询编号在 $[l,r]$ 内的集合的并集中，第 $c$ 大的数是多少。

注意可重集的并是不去除重复元素的，如 $\{1,1,4\}\cup\{5,1,4\}=\{1,1,4,5,1,4\}$。

inputFormat:
第一行两个正整数 $n,m$，表示集合个数和操作个数。
接下来 $m$ 行，每行四个整数表示一次操作。

outputFormat: 对于每个 $2$ 操作，输出一行一个整数表示答案。

hint:
【样例说明】
第 $1$ 次操作在 $1,2$ 号集合中分别加入了一个  $1$。
第 $2$ 次操作在 $1,2$ 号集合中分别加入了一个 $2$。
第 $3$ 次操作查询 $1$ 号集合中第 $2$ 大的数，答案为 $1$。
第 $4$ 次操作查询 $1$ 号集合中第 $1$ 大的数，答案为 $2$。
第 $5$ 次操作查询 $1,2$ 号集合的并集 $\{1,2,1,2\}$ 中第 $3$ 大的数，答案为 $1$。

【数据范围】
$1 \le n,m \le 5\times 10^4$
$1\le l,r \le n$
$1$ 操作中 $|c|\le n$
$2$ 操作中 $1\le c < 2^{63}$

---

$\text{upd 2023.8.23}$：新增加一组 Hack 数据。


title: [ZJOI2013] 丽洁体

description:
平时的练习和考试中，我们经常会碰上这样的题：命题人给出一个例句，要我们类比着写句子。这种往往被称为仿写的题，不单单出现在小学生的考试中，也有时会出现在中考中。许多同学都喜欢做这种题，因为较其它题显得有趣。仿写的句子往往具有“A\_\_B\_\_C”的形式，其中A，B，C是给定的由一个或多个单词组成的短句，空的部分需要学生填写。当然，考试的时候空在那里也是可以的。例如，“其实天不暗阴云终要散，其实 ，其实 ，其实路不远一切会如愿，艰难困苦的日子里我为你祈祷，请你保重每一天”。再比如，“见了大海的汹涌，没见过大山的巍峨，真是遗憾；见了大山的巍峨，没见过 ，还是遗憾。出发吧，永远出发。 ，人有不老的心情。”

由于现在是网络时代，我们不再只能仿写命题人命的题，我们可以仿写网上各种句子和段落。2011年3月26日，某人在博客上发布了的消息就惹来了很多人的仿写。

很难过吧。。。考得完爆了。。。

。。。。。。其实也没什么可以说的。。。都是蒟蒻的借口罢了。。。

。。。自己果然还只是半吊子水平呢。。。。

。。。祝大家都能进省队。。。其实只要不要有遗憾就好了呢。。。

虽然我很遗憾或许不能走下去了。。。。。

886

在网络上广泛流传的仿写，因为在某些地方有独到之处，大都被命名为“某某体”。打开人人，刷新微博，你也能发现这样和那样的体，比如，对不起体，**说明他爱你体等等。金先生注意到了这一现象，他敏锐地认为这是一个很有价值的研究课题，于是就其展开研究，打算发一篇paper。由于在网上发消息，人们有了更大的灵活度，人们有时因为表达的需要，还往原本固定的A, B, C中添加一些修饰的词语。这就给辨别一个句子或段落是否是另一个句子或段落的仿写增加了困难。

金先生现在研究一种形如“A\*B\*C”的体作品，其中A, B, C分别是某个由若干单词组成的短句，\*代表0个或多个单词。他在网上找了大量的体作品，不过很多体作品不太合乎原作者的格式，也就是相当于在正规的体作品中插入了0个或多个单词。

由于数据量太大，金先生无法一个一个看过去，于是想请你帮忙，去掉尽量少的单词，使它成为指定的体。

inputFormat:
包含4行。

第一行是某个也许不规范的体作品T，

接下来三行分别代表A, B, C。

outputFormat: 仅一行，包含一个数，即最少的去除单词数。

samples:
xiang yao yi zhi ai zhe mou wu de hua yi yao guai zhi si lai shuo tai chang le xiang yao shi xian yi qie meng xiang de hua yi ren lei zhi sheng lai shuo tai duan le
yao
tai chang le yao
tai duan le

hint:
【样例说明】

在上述样例中，不规范的体作品为：“想要一直爱着某物的话，以妖怪之死来说太长了；想要实现一切梦想的话，以人类之生来说太短了”。

规范的体形如：“要\*太长了要\*太短了”。

修改后的规范的体为：“要一直爱着某物的话，以妖怪之死来说太长了；要实现一切梦想的话，以人类之生来说太短了”。

【数据规模与约定】

对于20%的数据，1≤|T|, |A|, |B|, |C|≤10。
对于40%的数据，1≤|T|, |A|, |B|, |C|≤100。
对于70%的数据，1≤|T|, |A|, |B|, |C|≤1000。
对于100%的数据，1≤|T|, |A|, |B|, |C|≤50000；所有单词长度不超过5，出现次数不超过500；数据保证答案总存在。


title: [ZJOI2013] 抛硬币

description:
有一枚硬币，抛出正面H的概率为a/b，抛出反面T的概率为1-a/b。现在TT小朋友开始玩丢硬币的游戏，并且把每次抛出的结果记录下来，正面记为H，反面记为T，于是她得到了一个抛硬币序列HTHHT…。她突然想到一个问题：在抛出正面和反面概率都是1/2的情况下，要使得抛出的序列出现目标序列HT，期望要抛多少次。然而经过1秒的思考以后她发现，若第一次抛出的是T，那么还需要期望抛出HT的次数，如果第一次抛出的是H，则期望只需要抛出T的次数，而期望抛出T的次数显然是2。她设抛出HT的期望次数是x，则得到了方程：

$x=1+(1/2*x+1/2*2) $

解得x=4，所以抛出HT的期望次数是4次。

她在解决了这个弱化很多的问题以后，开始思考对于一般情况下，抛出正反面的概率不一定相同，且抛出的目标序列不一定为HT时需要的期望步数。然而经过很长一段时间的苦思冥想仍然无果，于是她开始求助于你。

inputFormat:
第一行两个数a,b。意义如题目描述。

接下来1行一个只包含’H’和’T’的字符串S。表示要抛出的目标序列。

outputFormat:
输出仅一行p/q，其中p和q均为正整数且互质，表示抛出目标序列S所需要的期望步数。

注意，若q为1时，不省略/1。


title: [ZJOI2013] 蚂蚁寻路

description:
在一个 $n \times m$ 的棋盘上，每个格子有一个权值，初始时，在某个格子的顶点处一只面朝北的蚂蚁，我们只知道它的行走路线是如何转弯，却不知道每次转弯前走了多长。

蚂蚁转弯是有一定特点的，即它的转弯序列一定是如下的形式：右转，右转，左转，左转，右转，右转…左转，左转，右转，右转，右转。即两次右转和两次左转交替出现的形式，最后两次右转（最后两次一定是右转）后再多加一次右转。我们还知道，蚂蚁不会在同一个位置连续旋转两次，并且蚂蚁行走的路径除了起点以外，不会到达同一个点多次，它最后一定是回到起点然后结束自己的行程，而且蚂蚁只会在棋盘格子的顶点处转弯。

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

现在已知棋盘大小、每个格子的权值以及左转次数除以 $2$ 的值，问蚂蚁走出的路径围出的封闭图形，权值之和最大可能是多少。

inputFormat:
第一行三个数 $n,m,k$。意义如题目描述。

接下来一个 $n$ 行 $m$ 列的整数矩阵，表示棋盘。

outputFormat: 一个数，表示蚂蚁所走路径围出的图形可能的最大权值和。

hint:
### 样例说明

除了第一行的第二个和第一行的第四个都要围起来才至少合法。

### 数据规模与约定

- $10\%$ 的数据所有格子中权值均非负。
- 另 $20\%$ 的数据 $n=2$。
- 另 $30\%$ 的数据 $k=0$。
- $100\%$ 的数据 $1 \le n\le 100$，$1 \le m \le 100$，$0 \le k \le 10$，保证存在合法路径，数据有梯度，格子中每个元素的值绝对值不超过 $10000$。


title: [ZJOI2013] 话旧

description:
小林跟着银河队选手去了一趟宇宙比赛，耳濡目染，变得学术起来。回来后，他发现世界大变样了。比丘兽究级进化，成了凤凰兽；金先生因为发了一篇 paper，一跃成为教授，也成为了银河队选拔委员会成员。

一日，小林与金教授聊天。金教授回忆起过去的岁月，那些年他学过的电路原理。他曾经对一种三角波很感兴趣，并且进行了一些探究。小林感到很好奇，于是金教授就将课题形式化地说了一遍。

有一定义在 $[0,N]$ 的连续函数 $f(x)$，其中 $N$ 是整数，满足 $f(0)=f(N)=0$，它的所有极值点在整数处取到，且 $f(x)$ 的**极小值**均是 $0$。对于任意的 $0$ 到 $N-1$ 间的整数 $I$，$f(x)$ 在 $(I, I+1)$ 上是斜率为 $1$ 或 $-1$ 的一次函数。

金先生研究的是，若他知道其中 $K$ 个整点的函数值，那么：

1. 有多少个函数满足条件？
2. 满足条件的函数中，$f(x)$ 的最大值，最大能是多少？

小林思考了一下，便想出了很好的算法。那么作为经过多年训练的你呢？

inputFormat: 第一行包含两个用空格隔开的整数 $N,K$。接下来 $K$ 行，每行两个整数，表示 $x_i$ 和 $f(x_i)$。

outputFormat: 一行两个整数，分别对应两个问题的答案。考虑到第一问答案可能很大，你只要输出它除以 $19940417$ 的余数。


title: [ZJOI2013] 防守战线

description: 战线可以看作一个长度为 $n$ 的序列，现在需要在这个序列上建塔来防守敌兵，在序列第 $i$ 号位置上建一座塔有 $C_i$ 的花费，且一个位置可以建任意多的塔，费用累加计算。有 $m$ 个区间 $[L_1, R_1], [L_2, R_2], \cdots, [L_m, R_m]$，在第 $i$ 个区间的范围内要建至少 $D_i$ 座塔。求最少花费。

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

接下来一行，有 $n$ 个数，描述 $C$ 数组。

接下来 $m$ 行，每行三个数 $L_i,R_i,D_i$，描述一个区间。

outputFormat: 仅包含一行，一个数，为最少花费。

hint:
【样例说明】

位置 $1$ 建 $2$ 个塔，位置 $3$ 建一个塔，位置 $4$ 建一个塔。花费 $1\times 2+6+3=11$。

【数据规模】

对于 $20\%$ 的数据，$n\le 20$，$m\le 20$。

对于 $50\%$ 的数据（包括上部分的数据），$D_i$ 全部为 $1$。

对于 $70\%$ 的数据（包括上部分的数据），$n\le 100$，$m\le 1000$。

对于 $100\%$ 的数据，$n\le 1000$，$m\le 10000$，$1\le L_i\le R_i\le n$，其余数据均 $\le 10000$。


title: [ZJOI2014] 力

description:
给出 $n$ 个数 $q_1,q_2, \dots q_n$，定义

$$F_j~=~\sum_{i = 1}^{j - 1} \frac{q_i \times q_j}{(i - j)^2}~-~\sum_{i = j + 1}^{n} \frac{q_i \times q_j}{(i - j)^2}$$

$$E_i~=~\frac{F_i}{q_i}$$

对 $1 \leq i \leq n$，求 $E_i$ 的值。

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

以下 $n$ 行，每行有一个实数。第 $i+1$ 行的数代表 $q_i$。

outputFormat:
输出 $n$ 行每行一个实数，第 $i$ 行的数字代表 $E_i$。

当你的输出与标准答案相差不超过 $10^{-2}$ 时即被认为正确。


title: [ZJOI2014] 取石子游戏

description:
Roland. p Sprague 和 Patrick M. Grundy 都是组合游戏的狂热爱好者，但他们素未谋面。

一天，Sprague 在写给 Grundy 的信中向他介绍了一个据称是来自东方的古老游戏一一取石子。

取石子是一个双人博弈游戏。在游戏的一开始，桌面上有几堆石子堆。接下 来，游戏双方轮流进行操作：从桌面上选取一堆石子堆，然后从这一堆里面取走任意多个石子（但不能不取）。当某个人无法操作时则失败，另一方获得胜利。由于条件所限, Sprague 建议在纸上写一排自然数来代表各个石子堆的石子数目，然后两人轮流划数与数；Grundy 欣然应允。

一个月过去了，在 Grundy 连续输了 $5$ 盘游戏之后，他怀疑 Sprague 要诈。经过几天的研究，Grundy 在某天下午发现假设游戏双方都足够聪明，那么给定一个初始状态（一排自然数），可以有很简单的方法来判定先手必胜还是后手必胜，并且可以给出必胜策略！于是 Grundy 决定要进行反击。

翌日，Grundy 在写给 Sprague 的信中建议把游戏的规则改得更复杂一点：首先确定一个常数 $K$。然后，游戏双方的操作改为：每次选择一个数划掉。假设该数为 $x$，操作者可以任选一个正整数a，在划掉之后需要再写上 $x-a$，$x-2a $，$\cdots$，$x-K \times a$ 共 $K$ 个数，且 $a$ 需满足 $x-K\times a \geq 0$。若这样的 $a$ 不存在，那么操作者就不能划掉这个无。某一方失败的条件依然是他无法操作。

碍于面子，Sprague 当然无法拒绝。不过他也不会坐以待毙，现在他已经得到了和写在纸上的个数。他把这些数据和这个游戏的规则都告诉了你一一一个正在研究如何使用一个尚不存在的机械（你将其命名为计算机）解决实际的数学、物理、经济学）的计算机科学家。

inputFormat:
输入文件，第一行是一个正整数，表示数据组数 $T$（Sprague 向你询问的次数）。接下来依次输入 $T$ 组数据，每组数据占 $N + 2$ 行，格式如下：

- 第 $1$ 行是一个空行。
- 第 $2$ 行，两个正整数，按顺序表示 $N$ 和 $K$。
- 接下来 $N$ 行，每行一个正整数，表示写在纸上的 $N$ 个数。

outputFormat: 输出文件共有 $T$ 行。对每组数据，如果先手必胜（先进行操作的玩家拥有必胜策略），则输出 `Preempt.`。若后手必胜，则输出 `Leapfrog.`。若两者皆非，则输出 `Je suis un imbecile.`


title: [ZJOI2014] 星系调查

description:
银河历 $59451$ 年，在银河系有许许多多已被人类殖民的星系。如果想要在行星系间往来，大家一般使用连接两个行星系的跳跃星门。一个跳跃星门可以把物质在它所连接的两个行星系中互相传送。露露、花花和萱萱被银河系星际联盟调查局任命调查商业巨擘 ZeusLeague+ 的不正当商业行为。

在银河系有 $N$ 个已被 ZeusLeague+ 成功打入市场的行星系，不妨标号为 $1,2,...,N$。而 ZeusLeague+ 在这 $N$ 个行星系之间还拥有自己的 $M$ 个跳跃星门。使用这些跳跃星门，ZeusLeague+ 的物资就可以在这 $N$ 个行星系中两两任意互相传输。由于经费问题，跳跃星门的个数不会超过行星系的个数。

露露在颇费周折之后得到了 ZeusLeague+ 在这 $N$ 个行星系中的各自的贸易总额 $C_i$。

萱萱设计了一个经济学特征指标 $D_i$ 来度量这 $N$ 个行星系的经济学特征。于是，我们可以用二元组 $(C_i,D_i)$ 来表示第 $i$ 个行星系的 XP (Xuan's Position)。现在假设我们有 $k$ 个行星系的 XPs，把它们放置在二维平面上，然后我们用一条直线去拟合这些 XPs。定义一条直线与 XPs的相斥度为这条直线到各个 XP 的 Euclid 距离的平方之和。再令 XPs 的线性假设相斥度为所有直线与 XPs 的相斥度中的最小者。那么，这个值越小，ZeusLeague+ 在这 $k$ 个行星系中的相互贸易活动就越可疑，从而值得进一步调查。花花负责计算许多行星系对 $(u,v)$ 的非可疑度。一条跳跃星门航线的非可疑度被定义为它经过的所有行星系（包括起点和终点）的 XPs 的线性假设相斥度。而一个行星系对 $(u,v)$ 的非可疑度则被定义为所有以 $u$ 为起点，$v$ 为终点的跳跃星门航线的非可疑度中的最小值。一条跳跃星门航线是指从某个行星系开始，通过跳跃星门依次到达某些行星系，然后终止，并且中途不重复经过行星系，这样的一个过程。

花花负责计算许多行星系对 $(u,v)$ 的非可疑度。一条跳跃星门航线的非可疑度被定义为它经过的所有行星系（包括起点和终点）的 XPs 的线性假设相斥度。而一个行星系对 $(u,v)$的非可疑度则被定义为所有以 $u$ 为起点，$v$ 为终点的跳跃星门航线的非可疑度中的最小值。一条跳跃星门航线是指从某个行星系开始，通过跳跃星门依次到达某些行星系，然后终止，并且中途不重复经过行星系，这样的一个过程。

在花花数天夜以继日的工作之后，平行调查组的你——大名鼎鼎的计算机科学家 Hcceleration.Gerk.Gounce 不忍心看到她这样不眠不休，于是你在完成了手头的工作之后决定帮一帮她。

inputFormat: 第一行是 $N,M$，分别表示这个银河系内的行星系的个数以及跳跃星门的个数。接下来 $N$ 行，每行2个正整数 $C_i,D_i$，表示第 $i$ 个行星系的 XP (Xuan's Position)。接下来的 $M$ 行来描述跳跃星门，每行两个正整数 $u_i,v_i$，表示有一个连接着行星系 $u_i$ 和 $v_i$ 的跳跃星门。注意这个连接是无向的。不会存在自己连向自己的情况。也不会存在重复连接的情况。接下来的一行，有一个正整数 $Q$，表示花花需要计算的非可疑度的行星对数。接下来的 $Q$ 行，每行两个正整数 $s_i,t_i$，表示花花需要计算从 $s_i$ 到 $t_i$ 的非可疑度。

outputFormat: 总共 $Q$ 行，每一行一个实数，表示花花第 $i$ 次需要计算的答案。你的答案需要和标准答案的差不超过 $0.01$ 才能得分。

hint:
#### 简要题意（by yummy）

在边数不超过结点数的简单无权无向连通图内，每个结点在平面直角坐标系内对应一个坐标。有 $Q$ 组询问，每次给一对结点，找出一条路径，并找出一条直线，使得该路径上结点对应的坐标到直线距离平方和最小，并输出最小值。

[spj 0.01]


title: [ZJOI2014] 消棋子

description:
消棋子是一个有趣的游戏。游戏在一个 $r \times c$ 的棋盘上进行。棋盘的每个格子，要么是空，要么是一种颜色的棋子。同一种颜色的棋子恰好有两个。

每一轮，玩家可以选择一个空格子 $(x, y)$，并选择上下左右四个方向中的两个方向，如果在这两个方向上均存在有棋子的格子，而且沿着这两个方向上第一个遇到的棋子颜色相同，那么，我们将这两个棋子拿走，并称之为合法的操作。否则称这个操作不合法，游戏不会处理这个操作。游戏的目的是消除尽量多的棋子。

给出这样一个游戏和一个人的玩法。你需要：
1. 指出此人能消去多少棋子。
1. 输出能消去最多棋子数量。

inputFormat:
第一行给出了整数 $r$，$c$。

第二行给出了整数 $n$，表示不同颜色数。接下来 $n$ 行，第 $i$ 行含 $4$ 个整数 $a_i$，$b_i$，$c_i$，$d_i$，表示颜色为 $i$ 的两个格子分别是 $(a_i, b_i)$，$(c_i, d_i)$。然后是一个整数 $m$，表示此人的操作数。接下来 $m$ 行，每行有 $2$ 个整数和 $2$ 个字母，代表了他选择的格子，以及两个方向。我们用 `UDLR` 分别表示上下左右。

outputFormat: 输出用空格分隔的两个数字：此人能消去多少棋子和一个整数 $k$，表示能消去最多棋子数量。

hint: 对于所有数据，$1\leq r,c,n \leq 10^5$，数据保证答案的操作数 $0\leq k \leq 10^6$。


title: [ZJOI2014] 璀灿光华

description:
金先生有一个女朋友没名字。她勤劳勇敢、智慧善良。金先生很喜欢她。为此，金先生用 $a^3$ 块 $1\times 1 \times 1$ 的独特的水晶制作了一个边长为 $a$ 的水晶立方体，他要将这个水晶立方体送给他见过最单纯善良的她。

由于水晶立方体太太，不好运送，金先生还是将它拆开来送出。他相信拼好这个水晶立方难不倒聪明的她。

没名字收到了礼物后果然不一会儿就根据说明将水晶立方体拼好了。没名字发现，有 $n$ 块水晶在漆黑安静的夜晚会随机以等概率向上下左右前后六个方向的一个发出穿透光。被光照到的水晶显得格外好看。没名字给每一块不会发光的水晶定义了一个好看程度。水晶立方体在夜晚中的好看程度就是每块被光照到的水晶的好看程度之和。没名字想知道，水晶立方体在夜晚中的好看程度的最小值和最大值。

inputFormat:
第一行是 $a$，表示水晶立方体的边长。
接下来 $a^3$ 行，每行若干整数。
第一个数 $g_i$ 表示第 $i$ 块水晶的好看程度。如果 $g_i=0$，代表这块水晶会发光。接下来 $3\sim 6$ 个整数，代表与这块水晶有共同面的水晶编号。

outputFormat: 两个整数，代表水晶立方体在夜晚好看程度的最小值与最大值。

hint: 对于所有数据，$1<a\leq 70$，$g_i<10^6$，$n\leq 8$。


title: [ZJOI2015] 地震后的幻想乡

description:
傲娇少女幽香是一个很萌很萌的妹子，而且她非常非常地有爱心，很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。

这不，幻想乡突然发生了地震，所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。幻想乡一共有 $n$ 个地方，那么最快的方法当然是修复 $n-1$ 条道路将这 $n$ 个地方都连接起来。 幻想乡这 $n$ 个地方本来是连通的，一共有 $m$ 条边。现在这 $m$ 条边由于地震的关系，全部都毁坏掉了。每条边都有一个修复它需要花费的时间，第 $i$ 条边所需要的时间为 $e_i$。地震发生以后，由于幽香是一位人生经验丰富，见得多了的长者，她根据以前的经验，知道每次地震以后，每个 $e_i$ 会是一个 $0$ 到 $1$ 之间均匀分布的随机实数。并且所有 $e_i$ 都是完全独立的。

现在幽香要出发去帮忙修复道路了，她可以使用一个神奇的大魔法，能够选择需要的那 $n-1$ 条边，同时开始修复，那么修复完成的时间就是这 $n-1$ 条边的 $e_i$ 的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边 $e_i$ 的值，然后再选择完成时间最小的方案。 幽香在走之前，她想知道修复完成的时间的期望是多少呢？

inputFormat:
第一行两个数 $n,m$，表示地方的数量和边的数量。其中点从 $1$ 到 $n$ 标号。

接下来 $m$ 行，每行两个数 $a,b$，表示点 $a$ 和点 $b$ 之间原来有一条边。这个图不会有重边和自环。

outputFormat: 一行输出答案，四舍五入保留 $6$ 位小数。

hint:
### 样例解释

对于第一个样例，由于只有四条边，幽香显然只能选择这四条，那么答案就是四条边的 $e_i$ 中最大的数的期望，由提示中的内容，可知答案为 $0.8$。

### 提示

（以下内容与题意无关，对于解题也不是必要的。）

对于 $n$ 个 $[0,1]$ 之间的随机变量 $x_1,x_2,...,x_n$，第 $k$ 小的那个的期望值是 $k/(n+1)$。

数据范围：

对于所有数据：$n \leq 10, \ m \leq n(n-1)/2, \ n,m \geq 1$。

对于 $15 \%$ 的数据：$n \leq 3$。

另有 $15 \%$ 的数据：$n \leq 10, m=n$。

另有 $10 \%$ 的数据：$n \leq 10, m=n(n-1)/2$。

另有 $20 \%$ 的数据：$n \leq 5$。

另有 $20 \%$ 的数据：$n \leq 8$。


title: [ZJOI2015] 幻想乡 Wi-Fi 搭建计划

description:
傲娇少女幽香是一个很萌很萌的妹子。随着科技的进步，幻想乡的大家也开始使用手机了。这时幽香发现没人来她的太阳花田玩了，她感到很伤心，于是向别人打听了一下，才知道原来大家都嫌弃这里没有 Wi-Fi，手机上网还需要流量。

怎么办呢？幽香决定赶快搭建几个 Wi-Fi 点，让所有人都能在太阳花田里畅快地上网。

我们可以近似地把太阳花田看成一个 $y$ 轴在 $[0,R]$ 之间，$x$ 坐标在 $(-\infty,+\infty)$（也就是在 $x$ 轴上无限延伸）的无限长方形。

太阳花田里面有 $n$ 个景点，是游客们经常光顾的，幽香认为只要让这些景点尽量被 Wi-Fi 覆盖，那么游客们就肯定心满意足了。

八云紫表示她可以帮幽香架设 Wi-Fi 路由器。现在通用的路由器，每个的覆盖半径正好也是 $R$。八云紫扫视了一遍地图，发现在太阳花田外面，只有 $m$ 个有网络的地点，她只可以在那里架设路由器。如果你在点 $p$ 搭建了路由器，那么位于 $q$ 的地点，只要 $p$ 和 $q$ 的欧几里得距离小于等于 $R$，$q$ 点就会被 Wi-Fi 覆盖。

同时八云紫表示，架设难度随着地点的不同而不同，所以收费也不一样，在第 $i$ 个位置架设需要 $c_i$ 的钱。

现在幽香想要覆盖尽量多的景点，在这个前提下，幽香也想要尽量节省钱。你能帮助她吗？

inputFormat:
输入第一行三个整数 $n,m,R$，分别表示景点的数量，网络架设地点的数量和太阳花田的宽度。

接下来 $n$ 行，每行两个整数 $x,y$，满足 $|x|\le 10^8,0\le y\le R$，表示一个景点。两个景点的位置不会重合。

接下来 $m$ 行，每行三个整数 $x,y,c$，满足 $|x|\le 10^9$，$-10^8\lt y\lt 0$ 或者 $R\lt y\lt 10^8$，表示一个网络架设点的位置和花费。两个网络架设点不会重合。

outputFormat:
输出第一行表示最多覆盖的景点数。

第二行表示在覆盖景点数最多的前提下，最少的花费。

hint:
- 对于 $10\%$ 的数据，$n,m\le 20$；
- 对于另 $30\%$ 的数据，$n,m\le 100$，所有网络架设点的 $y$ 坐标都大于 $R$；
- 对于另 $60\%$ 的数据，$n,m\le 100$。

对于全部数据，$1\le R\le 10^8,0\le c\le 10^4$。


title: [ZJOI2015] 幻想乡战略游戏

background: ## 警告，滥用本题者将被封号。

description:
傲娇少女幽香正在玩一个非常有趣的战略类游戏，本来这个游戏的地图其实还不算太大，幽香还能管得过来，但是不知道为什么现在的网游厂商把游戏的地图越做越大，以至于幽香一眼根本看不过来，更别说和别人打仗了。

在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。

整个地图是一个树结构，一共有 $n$ 块空地，这些空地被 $n-1$ 条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起来。

在游戏中，幽香可能在空地上增加或者减少一些军队。同时，幽香可以在一个空地上放置一个补给站。如果补给站在点 $u$ 上，并且空地 $v$ 上有 $d_v$ 个单位的军队，那么幽香每天就要花费 $d_v \times \text{dist}(u,v)$ 的金钱来补给这些军队。由于幽香需要补给所有的军队，因此幽香总共就要花费为 $\sum (d_v \times \text{dist}(u,v))$（其中 $1 \leq v \leq N$）的代价，$\text{dist}(u,v)$ 表示 $u$ 和 $v$ 在树上的距离（唯一路径的权和）。

因为游戏的规定，幽香只能选择一个空地作为补给站。在游戏的过程中，幽香可能会在某些空地上制造一些军队，也可能会减少某些空地上的军队，进行了这样的操作以后，出于经济上的考虑，幽香往往可以移动他的补给站从而省一些钱。但是由于这个游戏的地图是在太大了，幽香无法轻易的进行最优的安排，你能帮帮她吗？

你可以假定一开始所有空地上都没有军队。

inputFormat:
第一行两个数 $n$ 和 $Q$ 分别表示树的点数和幽香操作的个数，其中点从 $1$ 到 $n$ 标号。

接下来 $n-1$ 行，每行三个正整数 $a,b,c$，表示 $a$ 和 $b$ 之间有一条边权为 $c$ 的边。

接下来 $Q$ 行，每行两个数 $u,e$，表示幽香在点 $u$ 上放了 $e$ 单位个军队（如果 $e<0$，就相当于是幽香在 $u$ 上减少了 $|e|$ 单位个军队，说白了就是 $d_u←d_u+e$）。

数据保证任何时刻每个点上的军队数量都是非负的。

outputFormat: 对于幽香的每个操作，输出操作完成以后，每天的最小花费，也即如果幽香选择最优的补给点进行补给时的花费。

hint:
对于所有数据，$1\le c\le 10^3$，$0\le |e| \le 10^3$，$1\le n\le10^5$，$ 1\le Q\le10^5$ 。

非常神奇的是，对于所有数据，这棵树上的点的度数都不超过 $20$。


title: [ZJOI2015] 诸神眷顾的幻想乡

description:
幽香是全幻想乡里最受人欢迎的萌妹子，这天，是幽香的 $2600$ 岁生日，无数幽香的粉丝到了幽香家门前的太阳花田上来为幽香庆祝生日。

粉丝们非常热情，自发组织表演了一系列节目给幽香看。幽香当然也非常高兴啦。

这时幽香发现了一件非常有趣的事情，太阳花田有 $n$ 块空地。

在过去，幽香为了方便，在这 $n$ 块空地之间修建了 $n-1$ 条边将它们连通起来。

也就是说，这 $n$ 块空地形成了一个树的结构。

有 $n$ 个粉丝来到了太阳花田上。

为了表达对幽香生日的祝贺，他们选择了 $c$ 种颜色的衣服，每种颜色恰好可以用一个 $0$ 到 $c-1$ 之间的整数来表示。

并且每个人都站在一个空地上，每个空地上也只有一个人。

这样，整个太阳花田就花花绿绿了。幽香看到了，感觉也非常开心。

粉丝们策划的一个节目是这样的，选中两个粉丝 $A$ 和 $B$（$A$ 和 $B$ 可以相同），然后A所在的空地到B所在的空地的路径上的粉丝依次跳起来（包括端点）。

这样幽香就能看到一个长度为 $A$ 到 $B$ 之间路径上的所有粉丝的数目（包括 $A$ 和 $B$）的颜色序列。

一开始大家打算让任意两个粉丝（注意：$A,B$ 和 $B,A$ 是不同的，他们形成的序列刚好相反）都来一次。

但是有人指出这样可能会出现一些一模一样的颜色序列，会导致审美疲劳。

于是他们想问，在这个树上，一共有多少可能的不同的颜色序列幽香可以看到呢？

由于太阳花田的结构比较特殊，只与一个空地相邻的空地数量不超过 $20$ 个。

inputFormat:
第一行两个正整数 $n,c$，表示空地数量和颜色数量。

第二行有 $n$ 个 $0$ 到 $c-1$ 之间，由空格隔开的整数，依次表示第 $i$ 块空地上的粉丝的衣服颜色。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示有一条连接空地 $u$ 和空地 $v$ 的边。

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

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

- 对于 $15\%$ 的数据，$n\le2\times 10^3$。
- 另有 $5\%$ 的数据，所有空地都至多与两个空地相邻。
- 另有 $5\%$ 的数据，除一块空地与三个空地相邻外，其他空地都分别至多与两个空地相邻。
- 另有 $5\%$ 的数据，除某两块空地与三个空地相邻外，其他空地都分别至多与两个空地相邻。
- 对于 $100\%$ 的数据，$1\le n\le10^5$，$1\le c\le10$，$1 \leq u, v \leq n$。