title: 评分系统

background:
答疑请到：https://www.luogu.org/discuss/show?postid=79498

由于时限等问题，请大家重交一遍这道题

本题时限开至2s

样例：https://files.cnblogs.com/files/ztz11/yl.rar

---

众所周知，luogu 有题目难度的评分系统，用户在通过题目后可以选择题目难度以及算法标签，来完善 luogu 的题库。

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

（原注：以下内容非真实评分数据，纯属作者编造，仅供娱乐使用。）

description:
Menteur-Hxy 同学很不老实，为了实现 NOIp 前 AC $100$ 道黑题的目标，他决定雇佣一些水军，最少雇佣 $1$ 个水军。

每个水军都有一个能力值 $x_i$，表示该水军可以解决难度最高为 $x_i$ 的题目。这些水军十分尽职尽责，在通过这道题目后都会给题目评最高难度。当然，luogu 的正常用户也会做题，他们会正常地评分。现在，我们给你所有水军的能力值以及每道题正常用户的评分记录，请你求出有多少种选择水军的方案，可以使这道题的评分变为黑题。因为答案可能过大，最终请输出答案数 $\bmod p$ 的值。

评分计算公式：去掉一个最高分，去掉一个最低分后求平均分。

**【表一：投票信息】**

| 投票编号 | 对应难度 | 分数贡献 |
| :------: | :------: | :------: |
| $1$ | 入门 | $1$ |
| $2$ | 普及- | $10$ |
| $3$ | 普及/提高- | $15$ |
| $4$ | 普及+/提高 | $25$ |
| $5$ | 提高+/省选- | $40$ |
| $6$ | 省选/NOI- | $55$ |
| $7$ | NOI | $75$ |
| $8$ | NOI+/CTSC | $100$ |

**【表二：难度规则】**

| 难度等级 | 对应颜色 | 对应分数 |
| :------: | :------: | :------: |
| 入门 | 红 | $1\sim 5$ |
| 普及- | 橙 | $6\sim 12$ |
| 普及/提高- | 黄 | $13\sim 20$ |
| 普及+/提高 | 绿 | $21\sim 35$ |
| 提高+/省选- | 蓝 | $36\sim 45$ |
| 省选/NOI- | 紫 | $46\sim 70$ |
| NOI+/CTSC | 黑 | $71\sim 100$ |

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

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

对于每组数据：

+ 第一行三个整数 $n, m, p$，分别表示 Menteur-Hxy 找的水军数量，luogu 用户评分数量，和输出时的模数。
+ 第二行，$n$ 个整数 $s_1 \dots s_n$ 分别表示水军的能力值。
+ 第三行，$m$ 个整数 $t_1 \dots t_n$，表示每个 luogu 用户的投票编号。
+ 第四行，一个整数 $k$ ，表示题目的难度系数。

outputFormat: 对于每组数据，输出一行一个整数，表示总选择方案数对 $p$ 取模后的结果，如无解，则输出 $0$。

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

luogu 用户评分和为 $25+40+55+75+100=295$，弃掉一个最低分后为 $270$，这时 Menteur-Hxy 雇佣两个及以上水军就可以达到目的。

因为可以通过本题的水军共有 $4$ 个，所以选择方案共有：

$$\{1,2\}\{1,2,3\}\{1,2,3,4\}\{1,2,4\}\{1,3\}\{1,3,4\}\{1,4\}\{2,3\}\{2,3,4\}\{2,4\}\{3,4\}$$

共 $11$ 种，对 $9$ 取余后结果为 $2$。

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

对于 $30\%$ 的数据，$n, m \leq 50$。

对于另外 $20\%$ 的数据，$p$ 为质数。

对于 $100\%$ 的数据，$1 \leq n, m, k,s_i \leq 10^5, 1 \leq t \leq 5, 2 \leq p \leq 3 \times 10^3, 1 \leq t_i \leq 8$。

保证合格水军的数量与需要的最少水军数量之差不超过 $5000$。

（原注：本题可能轻微卡常。感谢 @Ghostcai ，@Swhsz 帮忙验题。）


title: [yLOI2018] 锦鲤抄

type: P

background:
> 你在尘世中辗转了千百年，
> 却只让我看你最后一眼。
> 火光描摹容颜燃尽了时间，
> 别留我一人，孑然一身，凋零在梦境里面。

—— 银临 & 云の泣《锦鲤抄》

本题原名《逛庭院》。

这首歌的文案如下：（注：不阅读文案不影响下面的阅读）

> 宁武皇仁光九年锦文轩刻本《异闻录》载：扶桑画师浅溪，居泰安，喜绘鲤。院前一方荷塘，锦鲤游曳，溪常与嬉戏。
> 其时正武德之乱，藩镇割据，战事频仍，魑魅魍魉，肆逆于道。兵戈逼泰安，街邻皆逃亡，独溪不舍锦鲤，未去。
> 是夜，院室倏火。有人入火护溪，言其本鲤中妖，欲取溪命，却生情愫，遂不忍为之。翌日天明，火势渐歇，人已不见。
> 溪始觉如梦，奔塘边，但见池水干涸，莲叶皆枯，塘中鲤亦不知所踪。
> 自始至终，未辨眉目，只记襟上层迭莲花，其色魅惑，似血着泪。
> 后有青岩居士闻之，叹曰：魑祟动情，必作灰飞。犹蛾之投火耳，非愚，乃命数也。

description:
扶苏被画师和锦鲤的故事深深地打动了。为了能让锦鲤和画师继续生活在一起，他决定回到着火的庭院中灭掉大火。

画师的庭院可以抽象成一个有向图，每个点代表着一个着火的位置。为了量化火势的大小，扶苏给每个点一个火力值，火力值越大，代表这个点的火势越强。

风助火势，火借风力，对于每一个着火点，都有可能因为大风使得火扩散到其他点。有向图的每条边 $<u,v>$ 代表大火是从点 $u$ 扩散到点 $v$ 的。需要注意的是一个点可能会扩散到很多点，也可能是由很多点的大火一起扩散成的。

为了不因为灭掉火源让画师发现有人在帮他灭火，在任意时刻，扶苏不能灭掉任何一个不被任何点所扩散的点的火。一个点的火被灭掉后，所代表该点的火扩散的所有边将消失。需要说明的是，虽然边消失了，但是该点扩散到的所有点属性除入度以外都不会改变，更不会消失。

因为穿越的时间有限，扶苏只能灭掉最多 $k$ 个点的火。他想问问你他最多能扑灭多少火力值。

#### 简化版题意：

给你一张有向图，每个点有一个点权。任意时刻你可以任意选择一个**有入度**的点，获得它的点权并把它和它的出边从图上删去。最多能选择 $k$ 个点，求最多能获得多少点权。

inputFormat:
输入的第一行是三个用空格隔开的整数，代表图的点数 $n$ 和边数 $m$ 以及点数的限制 $k$。

输入的第二行是 $n$ 个用空格隔开的整数，第 $i$ 个数 $w_i$ 代表点 $i$ 的火力值（点权）。

第 $3$ 到第 $(m + 2)$ 行，每行两个用空格隔开的整数 $u, v$，代表一条 $u$ 指向 $v$ 的有向边。

outputFormat: 输出一行一个整数，代表最大的火力值。

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

选择 $3, 5, 7$ 三个节点。

---

### 数据规模与约定

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

- Subtask 1（30 points）：$n = 10$，$m = 50$。
- Subtask 2（30 points）：$n = 100001$，$m = 500001$。**保证给出的图是一个有向无环图**。
- Subtask 3（20 points）：$n = 100002$，$m = 500002$。保证给出的图中，没有入度的点有且仅有一个。
- Subtask 4（17 points）：$n = 100003$，$m = 500003$。
- Subtask 5（3 points）：$n = 500004$，$m = 2000004$。

对于全部的测试点，保证 $1 \leq n \leq 5 \times 10^5 + 4$，$1 \leq m \leq 2 \times 10^6 + 4$，$0 \leq w_i \leq 10^3$，$0 \leq k \leq n$。

**不保证**给出的图没有自环。

---

### 提示

- 请注意数据读入对程序效率造成的影响。
- $n$ 的末位数字可以帮助你快速的判断测试点所在的子任务。


title: 长脖子鹿放置

background: 众周所知，在西洋棋中，我们有城堡、骑士、皇后、主教和长脖子鹿。

description:
如图所示，西洋棋的“长脖子鹿”，类似于中国象棋的马，但按照“目”字攻击，且没有中国象棋“别马腿”的规则。（因为长脖子鹿没有马腿）

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

给定一个$N * M$,的棋盘，有一些格子禁止放棋子。问棋盘上最多能放多少个不能互相攻击的长脖子鹿。

inputFormat:
输入的第一行为两个正整数$N$，$M$，$K$。其中$K$表示禁止放置长脖子鹿的格子数。

第$2$~第$K+1$行每一行为两个整数$X_i, Y_i$,表示禁止放置的格子。

不保证禁止放置的格子互不相同。

outputFormat: 一行一个正整数，表示最多能放置的长脖子鹿个数。

hint:
**重要提示：请务必思考对图的遍历顺序对运行速度的影响**

对于$10$%的数据，  $1 ≤ N,M ≤ 5$

对于$30$%的数据，  $1 ≤ N,M ≤ 10$

对于$60$%的数据，  $1 ≤ N,M ≤ 50$

对于$80$%的数据，  $1 ≤ N,M ≤ 100$

对于$100$%的数据，$1 ≤ N,M ≤ 200$

数据已修正，有一些错误的算法（包括部分题解）将不能通过本题。

感谢@Alpha 指出问题


title: [yLOI2018] 不老梦

background:
> 于万人中万幸得以相逢，刹那间澈净明通。
> 成为我所向披靡的勇气和惶恐，裂山海，堕苍穹。

——银临《不老梦》。

本题原名《毒瘤分块题》。

description:
扶苏非常喜欢一边听古风歌一边写毒瘤分块题。所以这个题的题面恶意卡了分块。

给你一个序列，这个序列中的每个数字有三个参数 $v_i,a_i,b_i$。这个序列中的数有一个非常神奇的有关时间的性质：每过一个时刻，序列中第 $i$ 个数字的值 $v_i$ 会增加 $a_i \times b_i$。

现在扶苏会对你做出一些询问和对序列进行一些修改。每次操作形如：

- 查询第 $t$ 时刻区间 $[l,r]$ 的 $v$ 之和是多少。
- 在第 $t$ 时刻修改区间 $[l,r]$ 内的 $a$，将之整体加上一个整数 $x$。
- 在第 $t$ 时刻修改区间 $[l,r]$ 内的 $b$，将之整体加上一个整数 $y$。
- 在第 $t$ 时刻修改区间 $[l,r]$ 内的 $v$，将之整体加上一个整数 $z$。

规定初始时刻为时刻 $0$。

inputFormat:
每个测试点有且仅有一组测试数据。

输入的第一行是两个用空格隔开的整数，分别代表序列的长度 $n$ 以及操作的个数 $m$。

下面 $n$ 行，每行 $3$ 个用空格隔开的整数，第 $i$ 行的整数 $v_i,a_i,b_i$ 分别代表第 $i$ 个位置的三个参数。

下面 $m$ 行，每行第一个数是 $opt$，代表操作的种类。

- 对于 $opt = 1$ 的情况，代表对序列进行一次查询。 $opt$ 后有三个用空格隔开的整数 $t, x, y$，代表查询时刻 $t$ 区间 $[x,y]$ 中 $v$ 的和。
- 对于 $opt = 2$ 的情况，代表对序列的 $a$ 值进行一次修改。$opt$ 后有四个用空格隔开的整数 $t, x, y, z$，代表在第 $t$ 时刻将区间 $[x,y]$ 中 $a$ 的值加上 $z$。
- 对于 $opt = 3$ 的情况，代表对序列的 $b$ 值进行一次修改。$opt$ 后有四个用空格隔开的整数 $t, x, y, z$，代表在第 $t$ 时刻将区间 $[x,y]$ 中 $b$ 的值加上 $z$。
- 对于 $opt = 4$ 的情况，代表对序列的 $v$ 值进行一次修改。$opt$ 后有四个用空格隔开的整数 $t, x, y, z$，代表在第 $t$ 时刻将区间 $[x,y]$ 中 $v$ 的值加上 $z$。

数据保证参数 $t$ 是单调递增的，不存在同一时刻有超过一种查询或询问。

outputFormat: 对于每次查询操作，输出一个一行一个整数，代表查询的答案对 $10^8 + 7$ 取模的答案。

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

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

---

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

**本题共有 $17$ 个测试点，各测试点不等分。每个测试点的 $n$ 的规模如下表**。

| 测试点编号 |         $n=$          | 测试点编号 | $n=$|
| :--------: | :-------------------: | :--------: | :-------------------: |
|    $1$     |          $6$          |    $10$    |      $10^5 + 2$       |
|    $2$     |         $10$          |   $11$    | $1.5 \times 10^5 + 2$ |
|    $3$     |         $100$         |  $12$    |      $10^5 + 3$       |
|    $4$     |        $10^3$         |  $13$    | $1.5 \times 10^5 + 3$ |
|    $5$     |    $3 \times 10^3$    | $14$    |  $2 \times 10^5 + 4$  |
|    $6$     |    $3 \times 10^3$    |   $15$    |  $5 \times 10^4 + 5$  |
|    $7$     |      $10^4 + 1$       |   $16$    |      $10^5 + 5$       |
|    $8$     |      $10^5 + 1$       |  $17$    |  $2 \times 10^5 + 5$  |
|    $9$     | $1.5 \times 10^5 + 1$ |

**各测试点分值**：

- 对于第 $1$ 到第 $14$ 个测试点，每个测试点 $5$ 分。
- 对于第 $15$ 到第 $17$ 个测试点，每个测试点 $10$ 分。

**各测试点 $m$ 的取值**：

- 对于测试点 $1$，$m = 10$。
- 对于测试点 $2$，$m = 50$。
- 对于第 $3$ 到第 $17$ 个测试点，$m = n$。

**各测试点特殊性质**：

- 对于所有 $n$ 末位数字为 $6$ 的测试点，满足性质：操作所用到的时刻从 $1$ 开始，每次增加 $1$。
- 对于所有 $n$ 末位数字为 $1$ 的测试点，满足性质：所有修改操作只涉及对 $a$ 的修改，且修改区间 $x = y$。
- 对于所有 $n$ 末位数字为 $2$ 的测试点，满足性质：所有修改操作只涉及对 $a$ 的修改。
- 对于所有 $n$ 末位数字为 $3$ 的测试点，满足性质：所有修改操作不涉及对 $v$ 的修改，且对于 $b$ 的修改满足 $x= y$。
- 对于所有 $n$ 末位数字为 $4$ 的测试点，满足性质：不存在修改操作。

对于全部的测试点，保证 $1 \leq x \leq y \leq n$，$1 \leq op \leq 4$，给出的所有数字都在 32 位带符号整形的范围内，$t$ 为正数，且按照严格的升序给出。

---

#### 【提示】

- 请注意数据读入对程序效率造成的影响。
- 请注意常数因子对程序效率造成的影响。
- $n$ 的末位数字可以帮助你快速判断测试点的特殊性质。
- 当你的答案为负时，请将其取模成非负数后再进行输出。


title: 随机生成树

background: @葛军 改编的水题

description:
rainheavy在纸上画了N个点（从1到N编号），每个点的颜色用一个整数描述。rainheavy决定用这N个点随机生成一棵树，生成的规则如下：

对于2号点到N号点，每个点随机指定连接一个点。i号点(2 <= i <= N)的连的点在i的约数中和i的倍数中不超过N的中随机挑选一个。（例如N=30时10号点的可以连接1号，2号，5号，20号，30号）

生成的树中不能有重边（不然就不叫树了）

树生成完之后，rainheavy可以计算出这个树有多少个联通块，一个联通块是一些点的集合，需要满足以下两个条件：

1、从集合中任取两个点都满足：两个点颜色相同，且这两个点之间存在一条树边组成的路径，路径上的所有点都和这两个点颜色相同

2、对于集合中的任意一个点和集合外的任意一个点：两点要么不同色，要么不存在一条树边组成的路径使得路径上所有点都和这两个点同色。

rainheavy希望计算出生成的树中联通块个数最多时，需要连接哪些边，但是rainheavy太强了，不屑于做这种辣鸡题目，~~更重要的是他要去AK IOI~~，于是就把题目扔给了你

注：边的顺序

1.首先，满足连通块个数最多的优先（即对于生成连通块有贡献的优先）

2.同样满足条件1时，连接的两个点编号之和较小的边优先（如满足条件1时，连接3号点和5号点的边比连接4号点和5号点的边优先）

3.同时满足条件2时，连接的两个点编号的之中较小的一个较小的边优先（如满足条件2时，连接2号点和6号点的边比连接3号点和5号点的边优先）

inputFormat:
第一行一个整数N代表点数

第二行N个整数，第i个整数$c_i$代表第i个点的颜色

outputFormat:
输出共n-1行，每行两个整数x,y表示需要一条边连接点x和点y（要求x<y，且输出的顺序满足题目描述中边的顺序）

Tip：由于输出较多，建议用快速输出（不会就算了顶多T掉嘛对不对）

hint:
对于样例的解释：因为2号、4号点会对生成联通块有贡献（3号你连了也没用），又因为1+2<1+4，所以1 2比1 4优先输出，最后再输出1 3

对于30%的数据, 2 <= N <= 10

对于60%的数据, 2 <= N <= 5000

对于80%的数据, 2 <= N <= 200000

对于100%的数据, 2 <= N <= 500000，1<=颜色<=1e9（反正多了也没用）


title: [USACO09OPEN] Tower of Hay G

background: 为了调整电灯亮度，贝西要用干草包堆出一座塔，然后爬到牛棚顶去把灯泡换掉。干草包会从传送带上运来，共会出现 $n$ 包干草，第 $i$ 包干草的宽度是 $W_i$，高度和长度统一为 $1$。干草塔要从底层开始铺建。贝西会选择最先送来的若干包干草，堆在地上作为第一层，然后再把紧接着送来的几包干草包放在第二层， 再铺建第三层……重复这个过程，一直到所有的干草全部用完。每层的干草包必须紧靠在一起，不出现缝隙，而且为了建筑稳定，上层干草的宽度不能超过下层的宽度。 按顺序运来的干草包一定要都用上，不能将其中几个干草包弃置不用。贝西的目标是建一座最高的塔，请你来帮助她完成这个任务吧。

outputFormat: 第一行：单个整数，表示可以建立的最高高度。

hint:
### 样例解释

将 $1$ 和 $2$ 放在第一层，将 $3$ 放在第二层。


title: 列队

background:
本题是数据加强版，弱化版请参考$NOIP2017$   $DAY2$   $T3$

~~好了吓吓你们~~

description:
前段时间，$k$小$l$参加了$CTYZ$高一的的军训。众所周知，军训的时候需要站方阵。

$k$小$l$ 所在的队伍中有原本有蒟蒻（巨佬）$2*N$个，然而现在的只剩$k$小$l$等少数巨佬和一些蒟蒻了。

巨佬 $dwq$ ：教官我还有今年$IOI$的最后一题没调完，我先回去把题切了。

教官：行，准假，过十分钟调完了就先回去休息吧。

蒟蒻 $yz$ ：教官我今天任务计划里的红题还没做完，我要回去做。

教官：你现在回去也调不出来，乖乖站♂好，不要老是想偷懒。

$k$小$l$是一个热爱学习的男♀孩子，现在他发现，操场上只剩两列队了，原本两列的长度都为$N$，并且这两列队还残缺不全，蒟蒻在第一列，巨佬在第二列，并且如果一行中有巨佬，其气场会导致旁边不敢站蒟蒻。

#### 就算是这样，仅存巨佬们的战斗力还是比蒟蒻们的战斗力大（废话）

在$CTYZ$里面，一列队战斗力值是这样定义的

 $Fight=\sum_{i=0}^{n-1} p_{i}*2^{i}$

其中$i$为行标号，从$0$开始，$p_{i}=1/0$表示这一行是否有人，

现在$k$小$l$已经知道目前巨佬队伍的站队情况，现在他想问你，蒟蒻们有多少种可能的站队方式。

然而$k$小$l$觉得这样的太简单了，$k$小$l$现在有$M$个询问，每次会给你一个蒟蒻战斗力值范围$[a,b]$和一个$k$，表示他希望知道蒟蒻们的战斗力值在$[a,b]$之间，战斗力值第$k$大的蒟蒻站队方式的战斗力值，如果站队方式总数小于$k$，那么输出$POOR$ $AFO!$。

inputFormat:
第一行两个个整数$N,M$表示队列有$N$行，$k$小$l$的询问有$M$次。

第二行为一串$01$串，表示巨佬们的站队方式。

接下来$M$行，每行三个数$a_{i},b_{i},k_{i}$，表示$k$小$l$的询问。

outputFormat: 输出$M$行表示答案，$k$小$l$特别良心，允许你对于这个战斗力取模$20031102$输出。


title: 终于结束的起点

background:
> 终于结束的起点
> 终于写下句点
> 终于我们告别
> 终于我们又回到原点
> ……

一个个 OIer 的竞赛生涯总是从一场 NOIp 开始，大多也在一场 NOIp 中结束，好似一次次轮回在不断上演。
如果这次 NOIp 是你的起点，那么祝你的 OI 生涯如同夏花般绚烂。
如果这次 NOIp 是你的终点，那么祝你的 OI 回忆宛若繁星般璀璨。
也许这是你最后一次在洛谷上打比赛，也许不是。
不过，无论如何，祝你在一周后的比赛里，好运。

当然，这道题也和轮回有关系。

description:
广为人知的斐波拉契数列 $\mathrm{fib}(n)$ 是这么计算的

$$
\mathrm{fib}(n)=\begin{cases}
0,& n=0 \\
1,& n=1 \\
\mathrm{fib}(n-1) + \mathrm{fib}(n-2),& n>1
\end{cases}
$$

也就是 $0, 1, 1, 2, 3, 5, 8, 13 \cdots$，每一项都是前两项之和。

小 F 发现，如果把斐波拉契数列的每一项对任意大于 $1$ 的正整数 $M$ 取模的时候，数列都会产生循环。

当然，小 F 很快就明白了，因为 ($\mathrm{fib}(n - 1) \bmod M$) 和 ($\mathrm{fib}(n - 2) \bmod M)$ 最多只有 $M ^ 2$ 种取值，所以在 $M  ^ 2$ 次计算后一定出现过循环。

甚至更一般地，我们可以证明，无论取什么模数 $M$，最终模 $M$ 下的斐波拉契数列都会是 $0, 1, \cdots, 0, 1, \cdots$。

现在，给你一个模数 $M$，请你求出最小的 $n > 0$，使得 $\mathrm{fib}(n) \bmod M = 0, \mathrm{fib}(n + 1) \bmod M = 1$。

inputFormat: 输入一行一个正整数 $M$。

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

hint:
#### 样例 1 解释

斐波拉契数列为 $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \cdots$，在对 $2$ 取模后结果为 $0, 1, 1, 0, 1, 1, 0, 1, 1, 0, \cdots$。

我们可以发现，当 $n = 3$ 时，$f(n) \bmod 2= 0, f(n + 1) \bmod 2 = 1$，也就是我们要求的 $n$ 的最小值。

#### 数据范围

对于 $30\%$ 的数据，$M \leq 18$；

对于 $70\%$ 的数据，$M \leq 2018$；

对于 $100\%$ 的数据，$2 \leq M \leq 706150=\verb!0xAC666!$。

#### 提示

如果你还不知道什么是取模 $(\bmod)$，那我也很乐意告诉你，模运算是求整数除法得到的余数，也就是竖式除法最终「除不尽」的部分，也即
$$a \bmod M =k \iff a = bM + k\ (M > 0, 0 \leq k < M)$$
其中 $a, b, k$ 都是非负整数。

如果你使用 `C` / `C++`，你可以使用 `%` 来进行模运算。

如果你使用 `Pascal`，你可以使用 `mod` 来进行模运算。


title: 跳跳！

description:
你是一只小跳蛙，你特别擅长在各种地方跳来跳去。

这一天，你和朋友小 F 一起出去玩耍的时候，遇到了一堆高矮不同的石头，其中第 $i$ 块的石头高度为 $h_i$，地面的高度是 $h_0 = 0$。你估计着，从第 $i$ 块石头跳到第 $j$ 块石头上耗费的体力值为 $(h_i - h_j) ^ 2$，从地面跳到第 $i$ 块石头耗费的体力值是 $(h_i) ^ 2$。

为了给小 F 展现你超级跳的本领，你决定跳到每个石头上各一次，并最终停在任意一块石头上，并且小跳蛙想耗费**尽可能多**的体力值。

当然，你只是一只小跳蛙，你只会跳，不知道怎么跳才能让本领更充分地展现。

不过你有救啦！小 F 给你递来了一个写着 AK 的电脑，你可以使用计算机程序帮你解决这个问题，万能的计算机会告诉你怎么跳。

那就请你——会写代码的小跳蛙——写下这个程序，为你 NOIp AK 踏出坚实的一步吧！

inputFormat:
输入一行一个正整数 $n$，表示石头个数。

输入第二行 $n$ 个正整数，表示第 $i$ 块石头的高度 $h_i$。

outputFormat: 输出一行一个正整数，表示你可以耗费的体力值的最大值。

hint:
#### 样例解释

两个样例按照输入给定的顺序依次跳上去就可以得到最优方案之一。

#### 数据范围
对于 $1 \leq i \leq n$，有 $0 < h_i \leq 10 ^ 4$，且保证 $h_i$ 互不相同。

对于 $10\%$ 的数据，$n \leq 3$；

对于 $20\%$ 的数据，$n \leq 10$；

对于 $50\%$ 的数据，$n \leq 20$；

对于 $80\%$ 的数据，$n \leq 50$；

对于 $100\%$ 的数据，$n \leq 300$。


title: 咕咕咕

description:
小 F 是一个能鸽善鹉的同学，他经常把事情拖到最后一天才去做，导致他的某些日子总是非常匆忙。

比如，时间回溯到了 2018 年 11 月 3 日。小 F 望着自己的任务清单：

1. 看 iG 夺冠；
2. 补月赛题的锅。

小 F 虽然经常咕咕咕，但他完成任务也是很厉害的，他一次性可以完成剩余任务的任一**非空子集**。比如，他现在可以选择以下几种中的一种：

1. 看 iG 夺冠；
2. 补月赛题的锅；
3. 一边看 iG 夺冠的直播，一边补锅。

当然，比赛实在是太精彩了，所以小 F 就去看比赛了。

不过，当金雨从天而降、IG 举起奖杯之时，小 F 突然心生愧疚——锅还没补呢！于是，小 F 的内心产生了一点歉意。

这时小 F 注意到，自己总是在某些情况下会产生歉意。每当他要检查自己的任务表来决定下一项任务的时候，如果当前他干了某些事情，但是没干另一些事情，那么他就会产生一定量的歉意——比如，无论他今天看没看比赛，只要没有补完月赛的锅，他都会在选择任务的时候产生 $1$ 点歉意。小 F 完成所有任务后，他这一天的歉意值等于他每次选择任务时的歉意之和。

过高的歉意值让小 F 感到不安。现在，小 F 告诉你他还有 $n$ 项任务，并告诉你在 $m$ 种情况中的一种 $\mathrm{state}_i$ 的情况下，小 F 会产生 $a_i$ 点歉意。请你帮忙计算一下，小 F 在那一天所有可能的完成所有任务方式的歉意值之和是多少。

由于答案可能很大，你只需要输出答案对 $998244353$ 取模即可。

inputFormat:
输入一行两个整数 $n, m$，表示有 $n$ 项任务，在 $m$ 种情况中下小 F 会产生歉意值。

输入接下来 $m$ 行，每行有一个长度为 $n$ 的 $0-1$ 串 $\mathrm{state}_i$ 和一个歉意值 $a_i$，$\mathrm{state}_{i, j}$ 为 $0/1$  表示第 $j$ 项任务此时没做 / 已经做了。

详情请参考样例和样例解释。

outputFormat: 输出一行一个整数，表示小 F 在那一天所有可能的完成任务方式的歉意值之和对 $998244353$ 取模的结果。

hint:
#### 样例 1 解释：

$0-1$ 串中第一个数字表示小 F 看没看比赛，第二个数字表示小 F 补没补锅。

我们用 $\varnothing$ 表示小 F 什么都没干，$A$ 表示小 F 看了比赛，$B$ 表示小 F 补了锅，那么所有会产生愧疚的方式如下：

$\varnothing: 1$
$\{A\}:1$

那么所有可能的选择如下：

$\varnothing\rightarrow\{A\}\rightarrow\{A,B\}:2$
$\varnothing\rightarrow\{B\}\rightarrow\{A,B\}:1$
$\varnothing\rightarrow\{A,B\}:1$

所以答案是 $2 + 1 + 1 = 4$。

#### 数据范围

保证出现的 $\mathrm{state}_i$ 互不相同。

对于所有数据，有 $1 \leq n \leq 20$, $1 \leq m \leq \min(2 ^ n, 10 ^ 5), 1 \leq a_i \leq 10 ^ 5$。

| Case | $n$ |
| :------:|:------: |
|1|$1$|
|2|$2$|
|3|$3$|
|4|$10$|
|5|$12$|
|6|$14$|
|7|$16$|
|8|$18$|
|9|$19$|
|10|$20$|


title: 不围棋

background:
「不围棋」是一种非常有趣的棋类游戏。

大家都知道，围棋的「气」是指一个棋子所在的联通块相邻的空格。两粒棋如果在棋盘上线段的两端就认为是相邻的，也就是在同一个连通块里。比如在图中，白子为四个独立的连通块，黑子构成一个连通块，绿色点是黑子连通块唯一的「气」：

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

「提子」是指将没有「气」的棋子提出棋盘，在上图中，如果白方走绿点，那么就可以将黑子全部提走。

在围棋中，我们想尽量多地占领地盘、提走对方棋子。然而，不围棋恰恰相反——不围棋是一种非常和平的游戏，双方的走子不能产生任何提子，也就是说，**任何一次走子不能让棋盘上任何一个棋子所在的连通块没有气**。比如，白方在上图中不能走绿点。

在你的某一步棋后，对方无棋可走，那么你就赢了。

description:
小 F 对不围棋特别感兴趣，不过他经常输，所以他想做出一个 AI 来替他完成这局游戏。

不过造 AI 实在是太困难啦，小 F 千辛万苦写出来的 AI 被同学们的 AI 锤爆啦！

现在，他想请你帮他实现一个 AI 中一部分的功能——随机模拟，因为他相信你写的程序非常优秀，一定能优化他的 AI。

给你一个 $n \times n$ 的棋盘，上面或许已经有一些棋子了，但此时局面一定是合法的，即**不存在没有气的连通块**；此时轮到黑棋下棋，因此棋盘上**黑白棋子的数量一定是相等的**。

你的任务是，**依次**为黑棋和白棋**随意**指定一个可行的走子位置，直到某一步游戏无法进行，决出胜负为止。

在正式的不围棋比赛还存在一些禁手规则。不过由于小 F 玩的是一种棋盘大小可变的新型不围棋，我们只用考虑上面提到的气的规则就好。

inputFormat:
输入一行一个整数 $n$，表示棋盘大小。
输入接下来 $n$ 行，每行有一个长度为 $n$ 的字符串，表示第 $i$ 行的情况。

* `.` 表示空
* `X` 表示黑棋
* `O` 表示白棋

详细请参考样例。

输入保证，棋盘初始局面合法，`X` 与 `O` 数量相等。

outputFormat:
你需要输出至少一行，假设你输出了 $L$ 行，那么对于前 $L - 1$ 行，你应该输出两个用空格分隔的正整数表示下棋坐标 $x_i, y_i$，其中奇数行表示黑棋的行动，偶数行表示白棋的行动。$x$ 坐标为从上到下从 $1$ 到 $n$，$y$ 坐标为从左到右从 $1$ 到 $n$。

请在第 $L$ 行输出 `-1 -1`，表示此时第 $L$ 手执棋人已经无棋可走。

你的输出可能会很大，即使本题时限为 $3s$，也请你不要使用太慢的方法输出大量内容。

#### 评分方式：

本题启用 Special Judge，并且有部分分。我们将通过以下方式进行计分：

* 如果你输出格式错误，那么该测试点不得分。格式错误包括但不限于：输出了非数字内容；一行输出了超过或者少于两个正整数；输出的坐标在棋盘外；最后一行的输出不是 `-1 -1`。
* 如果你的输出格式正确，但是你的输出的第一行的答案就是不可接受的，那么该测试点不得分。例如：输出的坐标是黑棋不可以下的位置；黑棋有棋可走却输出了 `-1 -1`。
* 如果你的输出格式正确，并且你的前 $k(1 \leq k <L)$ 行输出是可以接受的，那么该测试点将至少得到 $s$ 分，其中 $s = \lfloor \lg k \rfloor + 1$，含义是 $k$ 在十进制表示下是一个 $s$ 位数。
* 如果你的输出完全正确，无论你输出了多少行，你都将得到 $10$ 分。

详情请参考样例解释。

hint:
#### 样例 1 解释：

注意到将棋盘下满会让棋盘上所有连通块都没有气，所以黑棋是无棋可走的。

#### 样例 2 解释：

样例 2 还有两个正确的输出是这样的：
```
3 2
2 3
-1 -1
```
```
3 3
2 3
-1 -1
```
我们将棋盘表示出来：

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

其中，黑棋是三个空格都可以走的。

* 如果黑棋走 $(2, 3)$，如图，此时白棋走任何位置都会提走相邻的黑棋，白棋无棋可走；
 ![](https://cdn.luogu.com.cn/upload/pic/41219.png)

* 如果黑棋走 $(3, 2)$，如图，此时白棋唯一可走的点是 $(2, 3)$，之后黑棋无棋可走；
 ![](https://cdn.luogu.com.cn/upload/pic/41218.png)

* 如果黑棋走 $(3, 3)$，如图，此时白棋唯一可走的点是 $(2, 3)$，之后黑棋无棋可走；
 ![](https://cdn.luogu.com.cn/upload/pic/41217.png)

这三种情况依次对应三个输出，输出任意一种可得到满分。

#### 评分规则解释：

为了解释评分规则，我们以样例 2 为例，对于以下几种输出：
```
I AK IOI
```
很不幸，因为您太强了，所以为了按住躁动的您，我们会给您 $0$ 分。

```
-1 -1
```
```
1 1
-1 -1
```
很不幸，你的第一行没有输出正确，得 $0$ 分。

```
3 3
-1 -1
```
你输出的前 $1$ 行是正确方案的一部分。由于 $1$ 是 $1$ 位数，恭喜你得到了整整 $1$ 分！

#### 数据范围：

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


title: 金坷垃

background:
@rainheavy 原创

这是一道巨（du）水（liu）题

第一届中国国际博览会于2018年11.5--11.10在上海举行，特朗普统治的国家——美国带来了金坷垃。这是一种神奇的产品，~~肥料用了金坷垃，能吸收20米以下的氮磷钾~~（这是他们的广告）

可是，在经过富土（tu）康的质检员 DevZhu质检的时候发现出了点问题，金坷垃的效果并不像广告所说的那样。毕竟植物的根只能到深度为$1$的位置，金坷垃的效果有限

description:
它的效果只能如下：（以20为例）

20的约数（除本身）有10、5、4、2、1

从地下20米深处可以往上跳一个约数的长度（比如10）

现在它在10米处，10的约数（除本身）有5、2、1

再跳一个5，为5，5的约数（除本身）有1

再跳1个1，为4，4的约数（除本身）有2、1。

**1已用过，不能再用**

再跳一个2，为2。2的约数（除本身）有1。

**1已用过。**
此时没法再跳了。此时的深度为2。

按上述要求跳，把所有符合要求的能跳的所有情况全试一遍，只要有一种情况最后结果为$1$，这个肥料就合格，否则不合格。

DevZhu面对一大堆待检验的金坷垃，并不想检验那么多，他想问问你有哪些金坷垃是合格的，在这些合格的金坷垃中，初始深度排在第k个的是哪一个

把合格的金坷垃按初始深度从小到大排，请输出第k个金坷垃的初始深度，对$123456789$取模（富土康从不用1e9+7和998244353）

inputFormat: 一个数$k$

outputFormat: 合格的第$k$个金坷垃的初始深度对$123456789$取模后的结果

hint:
（简单死了。。。）

（给不会的人一点福利：数据里有一个是1）

对于30%的数据，$k$<=$10^5$;

对于70%的数据，$k$<=$10^9$;

对于100%的数据，$k$<=$10^{18}$；


title: HMR的LIS Ⅲ

background:
[HMR的LIS Ⅰ](https://www.luogu.org/problemnew/show/T51390)

[HMR的LIS Ⅱ](https://www.luogu.org/problemnew/show/T51391)

在你帮助HMR切掉AKIOI的神仙LSK的两道题后，LSK很不满，决定好好刁难一下你（而不是HMR）

description:
LSK又给出了一个长度为n的序列，要求你求出它的IBvl序列

IBvl序列满足以下要求：

1.一个IBvl序列满足$ \forall ~ i \in (1,len] , L < a_i - a_{i-1} < R $，其中$len$为IBvl序列的长度

2.IBvl序列中的元素相对顺序应满足在原序列中的相对顺序

3.在所有满足条件的序列中长度最长

我们视位置不同的元素为不同元素，有任一组成元素不同的IBvl序列为不同IBvl序列

现在要求你输出原序列的IBvl序列的长度，并输出字典序第k小（以元素在原序列中的位置为关键字排序）的序列的每个元素在原序列中的位置

inputFormat:
第一行输入4个整数，n，k，L，R

第二行输入n个整数，表示神仙LSK给出的序列

outputFormat:
第一行输出IBvl序列的长度

第二行输出IBvl序列的每个元素的位置


title: 中国象棋 - 摆上马

background:
~~相信自己的做法 大喊一声 I won't MLE！您就会过这道题~~

Imakf 玩腻了国际象棋，决定玩一玩中国象棋。

他发现中国象棋的马和国际象棋的马有所不同，他意识到这又可以出一道简单的问题，于是他又准备摆一摆马了

description:
Imakf 有一个 $X$ 行 $Y$ 列的棋盘，还有很多**完全相同**的马（你可以认为有无数个）。现在在棋盘上摆上马（或者不摆），求任何马无法攻击另一匹马的方案总数。

中国象棋的马和国际象棋的马不同。

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

注意：实际问题中是没有兵的。

当然由于方案可能过多，请输出对 $(10^9+7)$ 取模的值

inputFormat: 第一行两个正整数 $X,Y$。

hint:
对于 100% 的数据，有 $1\le X\leq100$，$1\le Y\leq6$。

对于 20% 的数据，有 $X,Y\leq6$。

对于另外 20% 的数据，有 $X\leq20$。

对于样例 1，可以选择不摆或者摆。

对于样例 2，我有一个绝妙的解释可惜我写不下。


title: 庞氏骗局

background: 众所周知，庞氏骗局就是借新债还就债的骗术，隐瞒企业已经大开倒车的真相，保持虚假的增长。

description:
庞氏骗局源自于一个名叫查尔斯•庞兹的人。1919年，他故弄玄虚，设计了一份假金融企划向大众兜售。借此，坑骗了成千上万的波士顿的长脖子鹿，套走了近1500万美金。

查尔斯•庞兹的骗局计划分为两部分，第一次他向$K1$名长脖子鹿展示了自己的创业计划，向每一头长脖子鹿要来了$1$万元的投资。第二次他向$K2$名长脖子鹿展示了自己的创业计划，由于第二次需要填补第一次的亏空，所以向每一头长脖子鹿要来了$2$万元的投资。

现在，查尔斯•庞兹拥有了$K1$份1万元和$K2$份2万元，他希望通过一种特定的方式消费从而躲避美国税务局（IRS）的追查。每一天，他都会选择两份钱，各消费1万元。为了进一步减轻自己的嫌疑，他每天选择的两份钱不会与之前重复。他想知道，花光所有的钱，共有多少不同的方案集合。**即方案内没有先后顺序，每一天不分先后**

例如：第一天选择了从$(1,2)$两只长脖子鹿那里拿钱，第二天不能花$(1,2)$两只的钱，但可以从$(2,3)$或$(1,3)$这样的长脖子鹿组中拿钱。

方案数对$1e9+7$取模。

inputFormat: 一行，两个整数，$K1$，$K2$

outputFormat: 一行，一个整数，方案数

hint:
##### 样例解释

我们设1,2号长颈鹿给了1万元，3,4号长颈鹿给了2万元。

方案一为这样的方案集合${(1,3),(3,4),(2,4)}$

方案二位这样的方案集合${(1,4),(3,4),(2,3)}$

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


title: 抓捕

background:
@葛军  原创

古桥文乃作为一名OIer，每天勤奋地在洛谷上刷题，然而她的父母却认为他有网瘾，就将她送到了杨叫兽的网戒中心。

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

一年之后，凭借不懈地努力古桥文乃终于逃了出来，并且立刻向警察蜀黍举报杨叫兽的所作所为，了解情况后警察请她带路去网戒中心抓捕杨叫兽。

description:
啊~~~~！

他们刚到达网戒中心就听到惨叫声从里面传来。古桥文乃在网戒中心呆了一年，对里面的情况很熟悉，立马就知道杨叔又在13号治疗室“点现钱”。同时，她知道网戒中心有$n$个房间，任意房间都有走廊相连，每个走廊和房间之间都有门，门是向外锁上的，且在开启后会自动锁上（即每次从房间$i$进入任意一个与其相连的走廊需要花费$c_i$的体力开锁，而从走廊进入房间不用耗费体力）。

杨叔为了防止“盟友”逃跑，在每个房间安装了摄像头，安排了$n$个手下在监控中心看着监控。

**特别的，1号房间为监控中心，1号手下负责防止任何人（除了杨叔）进入监控中心（否则立刻报告给杨叔）**，

其余的2号到$n$号手下每人负责监控编号是自己整数倍的房间（例如$n=10$时2号手下监控2号，4号，6号，8号，10号房间），13号治疗室也按照此规则被监控，如果他们其中一个人看到同一个人两次，就会向杨叔报告（但是每一个手下不会互相交流信息），好在这些手下都四肢发达头脑简单，只能记得上一秒的事情。

为了保证抓捕的顺利，古桥文乃和警察不能被发现，现在他们在$x$号房间，13号治疗室在$y$号房间，已知他们通过每一条走廊要1秒，开锁和通过房间不用花费时间（但会被监控室的手下看到），古桥文乃和警察想知道他们在不被发现的情况下最少要花费多少体力才能进入13号治疗室。

inputFormat:
本题多组询问QAQ

第一行一个数$T$，表示有$T$组询问

第二行一个数$n$，表示有$n$个房间和手下（每组数据$n$相同且只在一开始读入一次，意思就是整个输入中只读入一次n！）

对于每一个询问：

第一行两个数：$x$，$y$，其中$x$表示古桥文乃和警察所在房间的编号，$y$表示13号治疗室所在房间的编号

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

提示：

本题读入可能较多，建议使用快读（不会快读的自己搜！）

还有，记得开$O_2$，不然你会T飞掉~~（虽然开了$O_2$也会T飞掉）~~（雾）

outputFormat:
输出共$T$行

每个询问输出一行，仅一个数，表示在不被发现的情况下最少要花费多少体力才能进入13号治疗室，若不能到达输出“-1”（不含引号）


title: 水の数列

background: ${\rm CYJian}$想到了一个很好玩的游戏呢...

description:
${\rm CYJian}$现在给你一个长度为$N$的数列，你可以选择一个数$x$，然后获得一个得分，得分越大越好。

得分是这样计算的:

首先把小于等于$x$的数标记，然后你的得分就是每一个连续标记的区间的长度的平方和。

${\rm CYJian}$觉得这样太简单了，~~答案显然就是最大值嘛~~所以他就把得分改成了原来的得分除以你选择的数。

${\rm CYJian}$还是觉得这样太简单了，所以他需要你选择的数得到的区间的个数在$l$~$r$的范围内。

${\rm CYJian}$还是觉得这样太简单了，所以他加上了$T$组询问。

${\rm CYJian}$还是觉得这样太简单了，所以他决定强制在线。

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

第二行$n$个正整数$Num_i$表示${\rm CYJian}$给出的数列。

接下来$T$行，每行四个正整数$a$，$b$，$x$，$y$，你需要这样得到真正的$l$和$r$:

```
l = (a * lastans + x - 1) % n + 1;
r = (b * lastans + y - 1) % n + 1;
if (l > r) swap(l, r);
```

其中${\rm lastans}$表示上一次询问的最大分数(原始得分)和得到这个最大的分数的$x$的乘积。特别的，我们令第一次询问时${\rm lastans}=0$。

outputFormat:
$T$行，每行两个正整数表示每一次询问能得到的最大的分数(原始的得分)和得到这个最大的分数的$x$。特别的，如果无解输出"$-1\ -1$"（此时 $lastans$ 为 $1$）。如果有多解则输出选择的数最大的一组。

$CYJian$想知道你是不是蒙的，所以你还需要告诉他**这一次询问的**$L$，$R$，$lastans \bmod n$。

具体参见样例。

hint:
${\rm Subtask\ 1(30\ pts)}:\qquad 1 \leq N,T \leq 10^2$

${\rm Subtask\ 2(30\ pts)}:\qquad 1 \leq N,T \leq 10^3$

${\rm Subtask\ 3(40\ pts)}:\qquad 1 \leq N \leq 10^6 \qquad 1 \leq T \leq 10^3$

$1 \leq Num_i \leq 10^6$

其余输入的数字均在${\rm int}$范围内。


title: z小f的函数

background: $z$小$f$热爱数学。

description:
由于$z$小$f$要复习$NOIp$，而且他认为觉得数学作业太简单了，于是把数学作业交给了你。

题目如下：

给定二次函数$y=ax^{2}+bx+c (a \neq 0)$，求函数的最大（小）值；

$z$小$f$当然不喜欢看见做这么简单的题目啦，于是他决定给函数进行如下操作：

操作 $1$：给定系数$k$，将函数向上平移$k$位，（$k$<$0$则向下平移$-k$位）

操作$2$：给定系数$k$，将函数向右平移$k$位，（$k$<$0$则向左平移$-k$位）

操作$3$：给定系数$k_1,k_2$，将函数关于点$(k_1,k_2)$进行对称变换

操作$4$：给定系数$k_1,k_2$，求函数在闭区间$[k_1,k_2]$上的最小值和最大值

操作$5$：给定系数$u,v,w$，求出二次函数$y$与二次函数$y_2=ux^{2}+vx+w$是否有交点。

由于$z$小$f$需要，你还要输出最终的二次函数$y$此时的最大值（最小值）。

inputFormat:
第一行一个正整数$T$，表示数学作业的题目数（即数据组数）

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

第一行三个数$a,b,c$，表示二次函数的系数$a,b,c$；

第二行一个正整数$n$，表示操作的数量。

接下来$n$行，每一行都有一个整数$p$，表示操作的编号，接下来的数即操作的内容（见题目描述 ）

由于$z$小$f$太可爱了，所以数据保证合法。

outputFormat:
对于每一个操作$4$，输出两个小数，分别表示区间的最小值与最大值（保留两位小数）；

对于每一个操作$5$，输出一个整数，其中0表示没有交点，2表示有交点；

每组数据操作完成后，输出最终的二次函数$y$此时的最大值（最小值）（保留两位小数）。


title: 树枝修剪

background: $Daleva$ $Geoge$是一个热爱生活的园艺工。

description:
$Daleva$ $Geoge$的花园里有一颗常年没有修剪的树，这一天，$Daleva$ $Geoge$家里来了客人，为了给客人一个好印象，他需要整理这个花园，但是那一颗树显得太碍眼了，他必须要给他好好地修剪一下。

这是一颗以$root$为根的有根树，有$n$个节点。$Daleva$ $Geoge$在根节点，$Daleva$ $Geoge$对某些叶子的形态感到不满，需要剪去多余的枝条。

有$S$个需要修剪的叶子节点,这些叶子节点有一些多余的枝条，这些叶子节点有着自己的权值$a_{i}$,表示这个节点上有多少个$Daleva$ $Geoge$不需要的枝条。同时，因为花园里没法容下这些枝条（否则就变得不和谐了），$Daleva$ $Geoge$需要把这些枝条安装到某些节点上。

$Daleva$ $Geoge$有一个神奇的胶水和一把神奇的剪刀，因此你不需考虑每个树枝的固定形态，根据$Daleva$ $Geoge$的推测，一共有$T$个叶子节点需要安装这些枝条，这些节点有各自的权值$b_{i}$，表示需要$b_{i}$个枝条才能把这棵树变得很好看。

为了修剪好这棵树，$Daleva$ $Geoge$不得不在树上跑边，把每个叶子节点中多余的枝条剪下，并用胶水粘在其他的有需要的叶子节点上。每条边都有不同的长度，现在，由于树太过庞大，$Daleva$ $Geoge$需要知道，他最少需要跑多远的路才能使这棵树被修剪好，$Daleva$ $Geoge$也要回到树根上下来。

虽然$Daleva$ $Geoge$有这些神奇的工具，但他的口袋是有限的，容量为$G$,$Daleva$ $Geoge$不能一次带太多枝条，即不能超过$G$,这更使他懒于考虑这些繁琐的问题。$Daleva$ $Geoge$当然会算啦，他那么巨，但他为了养足精力去剪枝条，这一艰巨的任务就落在你身上了。

$Daleva$ $Geoge$已经把心中树的形状告诉你了，他要躺在椅子上看你怎么算这些问题。

inputFormat:
输入的第一行$3$个整数：$n,G,root$.

接下来$n-1$行描述每个树边，每行$3$个整数：$u,v,w$表示$u$与$v$有一条长度为$w$的边。

接下来一行$2$个整数：$S,T$;

接下来$S$行，每行两个整数：$x,a_{i}$,表示在第$x$个节点有$a_{i}$个多余枝条，数据保证$x$为叶子节点。

接下来$T$行，每行两个整数：$x,b_{i}$,表示在第$x$个节点需要$b_{i}$个枝条，数据保证$x$为叶子节点。

数据保证$\sum_{i=1}^{S}a_{i}=\sum_{i=1}^{T}b_{i}$

outputFormat: 一行，一个整数，表示$Daleva$ $Geoge$最少需要跑多长的路才能把树修剪好并回到树根爬下树。

hint:
样例1解释：

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

蓝色数字表示有多少多余枝条，黄色数字表示需要的枝条数。

则最优方案为：$1→2→1→3→1→2→1→3→1→4→1→2→1→4→1$，答案为$40$;

对于$5\%$的数据，为样例1。

对于$40\%$的数据，$n\leq 10,G\leq 10;w \leq 1000$

对于$100\%$的数据，$n\leq 40,0000,G\leq 1000;S+T\leq n;a_{i},b_{i}\leq 10^{9};w\leq 10^{9}$

数据保证不会有任意一个叶子节点既需要枝条又有多余枝条。


title: Ryoku 与最初之人笔记

background:
Ryoku 在阅读「最初之人」的笔记的时候，发现了一个有趣的运算：$\rm xor$，这个运算的输入是两个数，输出是一个数，对应的运算时将输入的两个数化为二进制，再把每一位进行比较，若相同则输出的二进制中的这一位为 $0$，否则为 $1$。

在关于运算 $\text{xor}$ 笔记的下面有一道习题。Ryoku 很快就得出了答案，她想要考考你。

description:
Ryoku 向你复述了题目：求：

$$\sum_{a = 0}^n \sum_{b = a + 1}^n [a\equiv b\pmod {a \text{ xor } b}]$$

即：求满足 $a\equiv b\pmod {a \text{ xor } b}$，且 $a,b$ 均为小于等于 $n$ 的非负整数，$a<b$，的有序二元组 $(a,b)$ 个数。

inputFormat: 输入包含一个整数 $n$。

outputFormat: 输出包含一个整数，为上式的值，答案对 $10^9 + 7$ 取模。


title: [国家集训队] 阿狸和桃子的游戏

description:
阿狸和桃子正在玩一个游戏，游戏是在一个带权图G=(V, E)上进行的，设节点权值为w(v)，边权为c(e)。游戏规则是这样的：

1. 阿狸和桃子轮流将图中的顶点染色，阿狸会将顶点染成红色，桃子会将顶点染成粉色。已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。

2. 为了保证公平性，节点的个数N为偶数。

3. 经过N/2轮游戏之后，两人都得到了一个顶点集合。对于顶点集合S，得分计算方式为

$$\sum_{v \in S}w(v) + \sum_{e=(u,v)\in E \land u,v\in S}c(e)$$

由于阿狸石头剪子布输给了桃子，所以桃子先染色。两人都想要使自己的分数比对方多，且多得越多越好。如果两人都是采用最优策略的，求最终桃子的分数减去阿狸的分数。

inputFormat:
　输入第一行包含两个正整数N和M，分别表示图G的节点数和边数，保证N一定是偶数。

　　接下来N+M行。

　　前N行，每行一个整数w，其中第k行为节点k的权值。

　　后M行，每行三个用空格隔开的整数a b c，表示一条连接节点a和节点b的边，权值为c。

outputFormat: 输出仅包含一个整数，为桃子的得分减去阿狸的得分。

hint:
数据规模和约定

对于40%的数据，1 ≤ N ≤ 16。

对于100%的数据，1 ≤ N ≤ 10000，1 ≤ M ≤ 100000，-10000 ≤ w , c ≤ 10000。


title: [DBOI2019] 捡币

background:
> 众所周知，以津真天世界第一可爱。
> ——1jia1

你正在打不氪金手游 yys，这时家长进来了，于是你装作在打数据结构题。

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

description:
由于你在 $n$ 次十连抽后没钱了，于是你应以津真天的邀请去参加一个活动。

这个活动是在一个 $n\times n$ 的矩形区域中进行的，进行若干秒。第 $i$ 秒，主办方会在这个矩形中选择一块小的区域，在每格上面分别撒币。

捡币的规则是这样的：从左上角 $(1,1)$ 出发，走一条抵达  $(n,n)$ 的路径，每次只能从当前格子下面或右边的格子走，并捡起这个区域的金币。

你需要知道，在某一秒某个矩形区域中拥有最多金币的格子有多少金币，某个矩形区域中的金币总数，以及第 $m$ 秒后（如果有撒币操作则先撒币）开始最多能捡多少币。捡币过程中，场上金币数量不会变化，你可以认为这是在 1s 内完成的。

inputFormat:
第一行，输入整数 $n,m,Q\ (m\leq\text{撒币操作数量})$。

接下来 $Q$ 行，输入五个整数 $u,x1,y1,x2,y2$。（$0<x1\leq x2\leq n$，$0<y1\leq y2\leq n$，$-1\leq u\leq10$）。

- 若 $u>0$，则代表撒币操作，指左上、右下端点分别为 $(x1,y1),(x2,y2)$ 的矩形撒了 $u$ 元的币，撒币的时间依次增加（也就是说第一次撒币操作在第一秒，第二次撒币操作在第二秒，……）。
- 若 $u=0$，则为查大操作，指询问直到上一次撒币操作后，两端点为 $(x1,y1),(x2,y2)$ 的矩形中最大的金币值为多少。（具体意思见题目描述）
- 若 $u=-1$，则为查和操作，指询问直到上一次撒币操作后，两端点为 $(x1,y1),(x2,y2)$ 的矩形中金币值的总和。

outputFormat:
输出若干行。

前面几行输出一个整数，即每次查询的结果。

最后一行输出你在第$m$秒时，撒完币后捡币能获得的最多的金币。

hint:
【样例 #1 说明】

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

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

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

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

### 数据范围及约定

- Subtask #1（$20$分）：$1\leq n\leq 10$, $1\leq Q\leq 1000$。
- Subtask #2（$20$分）：$1\leq n\leq 1000$, $1\leq Q\leq 10$。
- Subtask #3（$20$分）：$1\leq n\leq 100$, $1\leq Q\leq 1000$。
- Subtask #4（$40$分）：$1\leq n\leq 1000$, $1\leq Q\leq 10000$。


title: 荷取融合

background:
作为一款Rougelike类游戏，TODR具有丰富的装备系统。每一款装备独特的外观和华丽的特效，上百种各有效果的印记，复杂的炼成调和分解融合系统都塑造了这款游戏极高的游戏性。

现在你的装备刷到了满级，需要和其他装备融合来继续成长，当然，你需要让河城荷取将你原装备中的印记抽取出来以便和新装备合成。

description:
已知原装备有 $n$ 个印记槽，每个印记槽中有无限多的一种印记，第 $i$ 个印记槽中的这种印记价值为 $a_{i}$。

河城荷取会用机械臂抽取印记槽内的印记，每一次抽取时，机械臂会向下抓取，从正下方的印记槽中抽取出一个印记，之后机械臂会向右移动或停留在原地(如果移动，那么可以移动任意格)，开始时机械臂的位置任意，但是任意时刻机械臂都必须在某个印记槽上。

河城荷取会进行 $k$ 次抓取，抓取结束后，你获得的总收益等于抓上来的 $k$ 个印记价值的乘积。

假设河城荷取进行的一切操作都是随机的，那么你能获得的收益的平均值是多少呢?

由于答案可能不是整数，你只需输出答案对 $\text{19260817}$ 取模后的结果。

inputFormat:
第一行两个整数 $n,k$ ，表示印记槽的个数和抓取的次数。

第二行 $n$ 个正整数 $a_{i}$ ，表示每个印记槽内印记的价值 。

outputFormat: 一个整数，表示 $k$ 次抓取结束后的收益的平均值。


title: [ICPC2019 WF] Hobson's Trains

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

description:
Mr. Hobson has retired from running a stable and has invested in a more modern form of transport,trains. He has built a rail network with n stations. However, he has retained his commitment to free the passenger from the burden of too many choices: from each station, a passenger can catch a train to exactly one other station. Such a journey is referred to as a **$leg$**. Note that this is a one-way journey, and it might not be possible to get back again.

Hobson also offers exactly one choice of ticket, which allows a passenger to travel up to $k$ legs in one trip. At the exit from each station is an automated ticket reader (only one, so that passengers do not need
to decide which to use). The reader checks that the distance from the initial station to the final station does not exceed $k$ legs.

Each ticket reader must be programmed with a list of valid starting stations, but the more memory this list needs, the more expensive the machine will be. Help Hobson by determining, for each station $A$, the
number of stations (including $A$) from which a customer can reach $A$ in at most $k$ legs.

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

inputFormat: The first line of input contains two integers $n$ and $k$, where $n$ $(2 \leq n \leq 5\times10^5)$ is the number of stations and $k$ $(1 \leq k \leq n − 1)$ is the maximum number of legs that may be traveled on a ticket. Then follow $n$ lines, the $i^{th}$ of which contains an integer $d_i$ $(1 \leq d_i \leq n$ and $d_i ≠ i)$, the station which may be reached from station $i$ in one leg.

outputFormat: Output $n$ lines, with the $i^{th}$ line containing the number of stations from which station $i$ can be reached in at most $k$ legs.

translation:
**【题目描述】**

Hobson 先生从管理马厩的工作中退休后，投资于一种更加现代的交通方式：火车。

他已经修建了一个包含 $n$ 个火车站的铁路网。然而，他兑现了让乘客摆脱选择困难症的承诺：对于每个站点，乘客只能乘坐火车前往一个站点，别无其它选择。

这样的一段旅程被称作一趟。要注意这是单向的旅程，可能无法再回到出发点。

Hobson 同样也只提供一种车票，允许乘客一次旅行的距离不超过 $k$ 趟。在每个站点的出口会有一个自动读票机（只有一个，所以乘客就不用纠结于要用哪个）。机器会检查从始发站到到达站的距离是否不超过 $k$ 趟。

每个读票机必须编入一个合法始发站列表，但是列表消耗的存储空间越多，机器就越贵。

请帮助 Hobson 先生确定：对于每个站点 $A$，能够在最多 $k$ 趟的旅程中到达 $A$ 的站点个数（包含 $A$ 本身）。

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

上图为样例输入 1 对应的示意图。每个圆圈代表了一个站点，圆圈旁边的数字为当 $k=2$ 时需要编入读票机的站点编号。

**【输入格式】**

第一行包含两个整数 $n, k$，$n$ 为站点个数，$k$ 为一张票允许旅行的最多趟数。
接下来 $n$ 行，第 $i$ 行包含一个整数 $d_i$，表示第 $i$ 个站点经过一趟到达的站点。

**【输出格式】**

输出 $n$ 行，第 $i$ 行输出能在 $k$ 趟内到达站点 $i$ 的站点数目。

**【译者注】**

在不侵犯原题版权的情况下，本题面中文翻译基于[知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议](http://creativecommons.org/licenses/by-nc-sa/4.0/)发布，注明出处时需指向本题链接。

Translate By @小粉兔

hint: Source: ICPC World Finals 2019.


title: [THUSC2015] 平方运算

description:
小 H 是一位勤奋的中学生，他的理想是进入自己心仪的大学学习计算机专业。为了实现这一目标。他从小就开始认真学习信息学竞赛的基础知识。

今天，小 H 学习了平方运算。为了检验自己是否熟练掌握了平方运算，小 H 决定给自己出一道题。小 H 有一个长度为 $N$ 的序列 ${X_1,X_2,\cdots,X_N}$。小 H 会时不时地取出 列中的一段连续区间 $[l,r]$，并将其中的每一个数改为原数值的平方对 $P$ 取模的结果，其中 $P$ 为某个给定的数。为了检验自己的运算是否正确，小 $H$ 还会时不时地想要知道序列中某一段连续区间 $[l,r]$ 内所有数的和是多少。

但是，小 H 现在并没有标准答案。所以，他向你求助，希望你编写一个程序，帮他计算出每次想要知道的区间内的数的和。

inputFormat:
输入第一行包含三个整数 $N,M,P$，$M$ 表示操作组数，$N,P$ 含义见题目描述；

接下来一行，包含 $N$ 个正整数，为 $X_1,X_2,X_3,\cdots,X_N$，$X_i<P$；

接下来共 $M$ 行输入，每行格式形如 $1\;l\;r$ 或 $2\;l\;r$，$1$ 表示修改每个元素的值，$2$ 表示询问区间和。

outputFormat: 对于每一个询问，输出答案。


title: 不可思议的迷宫

background: 融合了强力的装备,当然要去探索迷宫了

description:
然而，在你用一套神装愉快的切瓜切菜时，慧音大小姐对你发动了忘却技能，于是，没有融合"记"印记的你忘记了迷宫的构造。

由于在忘却前你对这个迷宫的构造已经了如指掌，所以你知道这个迷宫的 $ n $ 个房间都是互相连通的，并且有 $ n $ 条道路连接这些房间(当然，道路从两个方向都可以经过)

即使在不可思议的幻想乡，基本的常识也是存在的，也就是说不会有连接两个相同房间的道路，也不会有两端是同一个房间的道路。

忘记了迷宫的构造后，你无从得知你在哪里，以及前往下一层的通道在哪里.幸运的是，你保存了一份这个迷宫大致的地图，知道了这 $ n $ 条道路分别连接哪两个房间以及每条道路的长度。

为了通关，你会从你所在的位置(某个随机的位置)不重复经过道路地走向前往下一层的通道(某个随机的位置)，显然，这种路径可能不止 $1$ 条，那么这时你会随机选取其中一条。

现在，你想知道自己走过的路径的期望长度，为了避免精度误差，只要对 $19260817$ 取模就好了。

inputFormat:
第一行一个整数 $n$，表示房间以及道路的个数。

下面 $n$ 行每行三个整数 $u,v,w$，表示从房间 $u$ 到房间 $v$ 有一条长度为 $w$ 的道路。

outputFormat: 一行一个整数，表示期望路径长度。

hint:
#### 样例解释:

迷宫的结构如下:
![](https://cdn.luogu.com.cn/upload/pic/42707.png)
起始点和结束点都是随机的，用二元组$(x,y)$表示

以几个有代表性的二元组为例:

$(1,1)$，只有一条长度为$0$的路径

$(1,2)$，有两条路径$1-4-2,1-4-3-2$，期望路径长度为 $\frac{4+6}{2}=5$
$(3,3)$，有两条路径$3-2-4,3$，期望路径长度为 $\frac{6+0}{2}=3$

不难算出，将所有可能的二元组的期望路径长度加在一起为$57$，所以答案为 $\frac{57}{16}$ ,在模意义下等于 $8426611$。

#### 数据范围:

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


title: 纯粹的弹幕地狱

background:
除了丰富的迷宫系统之外,TODR的弹幕系统也富有趣味,不仅有多种华丽的特效,还有如咲夜的连发小刀,` The World `等特殊的攻击.

不仅自机如此,敌人也有自己独特的攻击方式,比如下图就是绵月丰姬的"净化之风"攻击模式

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

description:
通过了不可思议的迷宫后,你一路顺利地过关斩将来到了最后一层,却遭遇了前所未有的强敌——纯狐

所幸的是,纯狐的弹幕不像绀珠转的强度一样大,房间的地形也比较特殊,可以为你所用.

形式化的来说,每一回合你和纯狐的行动模式如下:

1. 你可以将房间当成一张正方形网格图,左下角坐标为$(0,0)$,右上角的坐标为$(n,n)$,房间的有效位置为这$(n+1)*(n+1)$个格点,在一回合开始的时候,你会被随机传送到房间的任意一个有效位置

2. 之后,纯狐会随机出现在房间中的某个有效位置,当然,她不会和你出现在同一位置

3. 纯狐会发射纯粹的自机狙,也就是向你的方向发射一片弹幕,如果这片弹幕在飞行过程中经过了某个不是纯狐和自机所在的格点,则格点上的弹幕结界会被触发,将其传送到亚空间,如果这片弹幕顺利到达你所在的格点,那么你会受到一些伤害

4. 由于时间狂暴,纯狐在第$t$回合的弹幕伤害可以计算为$at^{2}+bt+c$

5. 回合结束,开始下一回合

经过粗略估计,你认为和纯狐的弹幕战会持续$k$回合,那么,为了稳妥起见,你想要算出自机受到的总期望伤害

答案可能很大也可能丢精度,所以对$19260817$取模就可以了

inputFormat: 一行五个整数$n,a,b,c,k$,意义与题目描述保持一致

outputFormat: 一行一个整数,表示期望受到总伤害的值

hint:
样例$1$解释:

手画一个网格图,不难发现纯狐能打到你的情况有$12$种(先放自机再放纯狐即可得到)

所以第一发弹幕的伤害为$1*1*1+2*1+1=4$,期望伤害为$4*\frac{12}{16}=3$

只有一回合,所以答案为$3$

数据范围:

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


title: 水の三角(修改版)

background:
这个三角图真好看。。

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

这个是 ${\rm 4}$ 阶三角图。。

description:
现在我们定义一个三角图是像上面一样的图。。

请求出一个无限大的三角图从 $1$ 号点走到 $u$ 号点的方案数。

有 $T$ 组询问。

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

第二行 $T$ 个正整数 $u_i$。

outputFormat: $T$ 行，共 $T$ 个正整数，表示答案模 $998244353$ 的结果。


title: [Ynoi2019 模拟赛] Yuno loves sqrt technology II

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

给你一个长为 $n$ 的序列 $a$，$m$ 次询问，每次查询一个区间的逆序对数。

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

第二行 $n$ 个整数表示这个序列。

之后 $m$ 行，每行两个整数表示查询的区间。

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

hint:
$1\leq n,m \leq 10^5$，$0 \leq a_i \leq 10^9$。

我们已经有了低于 $n^{1.5}$ 的算法。

Source
By nzhtl1477


title: [Ynoi2019 模拟赛] Yuno loves sqrt technology I

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

给你一个长为 $n$ 的**排列**，$m$ 次询问，每次查询一个区间的逆序对数，强制在线。

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

第二行 $n$ 个正整数表示这个**排列**。

之后 $m$ 行，每行两个整数表示查询的区间。

本题强制在线，每次查询输入的数要 xor 上 $lastans$，第一次询问默认 $lastans=0$。

outputFormat: 输出m行，每行一个数表示这次询问的答案

hint:
$1\leq n,m\leq 10^5$。

我们已经有了低于 $n^{1.5}$ 的在线算法。

Source
By nzhtl1477


title: [Ynoi2019 模拟赛] Yuno loves sqrt technology III

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

给你一个长为 $n$ 的序列 $a$，$m$ 次询问，每次查询一个区间的众数的出现次数，强制在线。

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

第二行 $n$ 个整数表示这个序列。

之后 $m$ 行，每行两个数表示查询的区间。

本题强制在线，每次查询输入的数要 xor 上 $lastans$，第一次询问默认 $lastans=0$。

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

hint:
$1\leq n,m,a_i \leq 5\times 10^5$。

存在 $O( n^{1.48541} )$ 的算法

Source
By nzhtl1477


title: [NOIP2018 提高组] 铺设道路

background: NOIP2018 提高组 D1T1

description:
春春是一名道路工程师，负责铺设一条长度为 $n$ 的道路。

铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 $n$ 块首尾相连的区域，一开始，第 $i$ 块区域下陷的深度为 $d_i$ 。

春春每天可以选择一段连续区间 $[L,R]$ ，填充这段区间中的每块区域，让其下陷深度减少 $1$。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 $0$ 。

春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 $0$ 。

inputFormat: 输入文件包含两行，第一行包含一个整数 $n$，表示道路的长度。 第二行包含 $n$ 个整数，相邻两数间用一个空格隔开，第 $i$ 个整数为 $d_i$ 。

outputFormat: 输出文件仅包含一个整数，即最少需要多少天才能完成任务。


title: [NOIP2018 提高组] 货币系统

background: NOIP2018 提高组 D1T2

description:
在网友的国度中共有 $n$ 种不同面额的货币，第 $i$ 种货币的面额为 $a[i]$，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 $n$、面额数组为 $a[1..n]$ 的货币系统记作 $(n,a)$。

在一个完善的货币系统中，每一个非负整数的金额 $x$ 都应该可以被表示出，即对每一个非负整数 $x$，都存在 $n$ 个非负整数 $t[i]$ 满足 $a[i] \times t[i]$ 的和为 $x$。然而， 在网友的国度中，货币系统可能是不完善的，即可能存在金额 $x$ 不能被该货币系统表示出。例如在货币系统 $n=3$, $a=[2,5,9]$ 中，金额 $1,3$ 就无法被表示出来。

两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的，当且仅当对于任意非负整数 $x$，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。他们希望找到一个货币系统 $(m,b)$，满足 $(m,b)$ 与原来的货币系统 $(n,a)$ 等价，且 $m$ 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 $m$。

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

接下来按照如下格式分别给出 $T$ 组数据。 每组数据的第一行包含一个正整数 $n$。接下来一行包含 $n$ 个由空格隔开的正整数 $a[i]$。

outputFormat: 输出文件共有 $T$ 行，对于每组数据，输出一行一个正整数，表示所有与 $(n,a)$ 等价的货币系统 $(m,b)$ 中，最小的 $m$。

hint:
在第一组数据中，货币系统 $(2, [3,10])$ 和给出的货币系统 $(n, a)$ 等价，并可以验证不存在 $m < 2$ 的等价的货币系统，因此答案为 $2$。 在第二组数据中，可以验证不存在 $m < n$ 的等价的货币系统，因此答案为 $5$。

【数据范围与约定】

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

对于 $100\%$ 的数据，满足 $1 ≤ T ≤ 20, n,a[i] ≥ 1$。


title: [NOIP2018 提高组] 赛道修建

description:
C 城将要举办一系列的赛车比赛。在比赛前，需要在城内修建 $m$ 条赛道。

C 城一共有 $n$ 个路口，这些路口编号为 $1,2,…,n$，有 $n-1$ 条适合于修建赛道的双向通行的道路，每条道路连接着两个路口。其中，第 $i$ 条道路连接的两个路口编号为 $a_i$ 和 $b_i$，该道路的长度为 $l_i$。借助这 $n-1$ 条道路，从任何一个路口出发都能到达其他所有的路口。

一条赛道是一组互不相同的道路 $e_1,e_2,…,e_k$，满足可以从某个路口出发，依次经过 道路 $e_1,e_2,…,e_k$（每条道路经过一次，不允许调头）到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全，要求每条道路至多被一条赛道经过。

目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案，使得修建的 $m$ 条赛道中长度最小的赛道长度最大（即 $m$ 条赛道中最短赛道的长度尽可能大）

inputFormat:
输入文件第一行包含两个由空格分隔的正整数 $n,m$，分别表示路口数及需要修建的 赛道数。

接下来 $n-1$ 行，第 $i$ 行包含三个正整数 $a_i,b_i,l_i$，表示第 $i$ 条适合于修建赛道的道 路连接的两个路口编号及道路长度。保证任意两个路口均可通过这 $n-1$ 条道路相互到达。每行中相邻两数之间均由一个空格分隔。

outputFormat: 输出共一行，包含一个整数，表示长度最小的赛道长度的最大值。


title: [NOIP2018 普及组] 标题统计

background: NOIP2018 普及组 T1

description: 凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？ 注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字符数时，空格和换行符不计算在内。

inputFormat: 输入文件只有一行，一个字符串 $s$。

outputFormat: 输出文件只有一行，包含一个整数，即作文标题的字符数（不含空格和换行符）。

hint:
**样例 1 说明**

标题中共有 3 个字符，这 3 个字符都是数字字符。

**样例 2 说明**

标题中共有 $ 5$ 个字符，包括 $1$ 个大写英文字母， $1$ 个小写英文字母和 $2$ 个数字字符， 还有 $1$ 个空格。由于空格不计入结果中，故标题的有效字符数为 $4$ 个。

**数据规模与约定**

规定 $|s|$ 表示字符串 $s$ 的长度（即字符串中的字符和空格数）。
对于 $40\%$ 的数据，$1 ≤ |s| ≤ 5$，保证输入为数字字符及行末换行符。
对于 $80\%$ 的数据，$1 ≤ |s| ≤ 5$，输入只可能包含大、小写英文字母、数字字符及行末换行符。
对于 $100\%$ 的数据，$1 ≤ |s| ≤ 5$，输入可能包含大、小写英文字母、数字字符、空格和行末换行符。


title: [NOIP2018 普及组] 龙虎斗

background: NOIP2018 普及组 T2

description:
轩轩和凯凯正在玩一款叫《龙虎斗》的游戏，游戏的棋盘是一条线段，线段上有 $n$ 个兵营（自左至右编号 $1 \sim n$），相邻编号的兵营之间相隔 $1$ 厘米，即棋盘为长度为 $n-1$ 厘米的线段。$i$ 号兵营里有 $c_i$ 位工兵。下面图 1 为 $n=6$ 的示例：

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

轩轩在左侧，代表“龙”；凯凯在右侧，代表“虎”。 他们以 $m$ 号兵营作为分界， 靠左的工兵属于龙势力，靠右的工兵属于虎势力，而第 $m$ 号兵营中的工兵很纠结，他们不属于任何一方。

一个兵营的气势为：该兵营中的工兵数$ \times $ 该兵营到 $m$ 号兵营的距离；参与游戏 一方的势力定义为：属于这一方所有兵营的气势之和。
下面图 2 为 $n = 6,m = 4$ 的示例，其中红色为龙方，黄色为虎方：

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

游戏过程中，某一刻天降神兵，共有 $s_1$ 位工兵突然出现在了 $p_1$ 号兵营。作为轩轩和凯凯的朋友，你知道如果龙虎双方气势差距太悬殊，轩轩和凯凯就不愿意继续玩下去了。为了让游戏继续，你需要选择一个兵营 $p_2$，并将你手里的 $s_2$ 位工兵全部派往 兵营 $p_2$，使得双方气势差距尽可能小。

 注意：你手中的工兵落在哪个兵营，就和该兵营中其他工兵有相同的势力归属（如果落在 $m$ 号兵营，则不属于任何势力）。

inputFormat:
输入文件的第一行包含一个正整数$n$，代表兵营的数量。

接下来的一行包含 $n$ 个正整数，相邻两数之间以一个空格分隔，第 $i$ 个正整数代 表编号为 $i$ 的兵营中起始时的工兵数量 $c_i$。

接下来的一行包含四个正整数，相邻两数间以一个空格分隔，分别代表 $m,p_1,s_1,s_2$。

outputFormat: 输出文件有一行，包含一个正整数，即 $p_2$，表示你选择的兵营编号。如果存在多个编号同时满足最优，取最小的编号。


title: [NOIP2018 普及组] 摆渡车

background: NOIP2018 普及组 T3

description:
有 $n$ 名同学要乘坐摆渡车从人大附中前往人民大学，第 $i$ 位同学在第 $t_i$ 分钟去 等车。只有一辆摆渡车在工作，但摆渡车容量可以视为无限大。摆渡车从人大附中出发、 把车上的同学送到人民大学、再回到人大附中（去接其他同学），这样往返一趟总共花费 $m$ 分钟（同学上下车时间忽略不计）。摆渡车要将所有同学都送到人民大学。

凯凯很好奇，如果他能任意安排摆渡车出发的时间，那么这些同学的等车时间之和最小为多少呢？

注意：摆渡车回到人大附中后可以即刻出发。

inputFormat:
第一行包含两个正整数 $n, m$，以一个空格分开，分别代表等车人数和摆渡车往返一趟的时间。
第二行包含 $n$ 个正整数，相邻两数之间以一个空格分隔，第 $i$ 个非负整数 $t_i$ 代表第 $i$ 个同学到达车站的时刻。

outputFormat: 输出一行，一个整数，表示所有同学等车时间之和的最小值（单位：分钟）。

hint:
**样例 1 说明**

同学 $1$ 和同学 $4$ 在第 $3$ 分钟开始等车，等待 $0$ 分钟，在第 $3$ 分钟乘坐摆渡车出发。摆渡车在第 $4$ 分钟回到人大附中。
同学 $2$ 和同学 $3$ 在第 $4$ 分钟开始等车，等待 $0$ 分钟，在第 $4$ 分钟乘坐摆渡车 出发。摆渡车在第 $5$ 分钟回到人大附中。
同学 $5$ 在第 $5$ 分钟开始等车，等待 $0$ 分钟，在第 $5$ 分钟乘坐摆渡车出发。自此 所有同学都被送到人民大学。总等待时间为 $0$。

**样例 2 说明**

同学 $3$ 在第 $1$ 分钟开始等车，等待 $0$ 分钟，在第 $1$ 分钟乘坐摆渡车出发。摆渡 车在第 $6$ 分钟回到人大附中。
同学 $4$ 和同学 $5$ 在第 $5$ 分钟开始等车，等待 $1$ 分钟，在第 $6$ 分钟乘坐摆渡车 出发。摆渡车在第 $11$ 分钟回到人大附中。
同学 $1$ 在第 $11$ 分钟开始等车，等待 $2$ 分钟；同学 $2$ 在第 $13$ 分钟开始等车， 等待 $0$ 分钟。他/她们在第 $13$ 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。 总等待时间为 $4$。
可以证明，没有总等待时间小于 $4$ 的方案。

**数据规模与约定**

对于 $10\%$ 的数据，$n ≤ 10$，$m = 1$，$0 ≤ t_i ≤ 100$。
对于 $30\%$ 的数据，$n ≤ 20$，$m ≤ 2$，$0 ≤ t_i ≤ 100$。
对于 $50\%$ 的数据，$n ≤ 500$，$m ≤ 100$，$0 ≤ t_i ≤ 10^4$。
另有 $20\%$ 的数据，$n ≤ 500$，$m ≤ 10$，$0 ≤ t_i ≤ 4 \times  10^6$。
对于 $100\%$ 的数据，$n ≤ 500$，$m ≤ 100$，$0 ≤ t_i ≤ 4 \times 10^6$。


title: [NOIP2018 普及组] 对称二叉树

background: NOIP2018 普及组 T4

description:
一棵有点权的有根树如果满足以下条件，则被轩轩称为对称二叉树：

1.  二叉树；
2.  将这棵树所有节点的左右子树交换，新树和原树对应位置的结构相同且点权相等。

下图中节点内的数字为权值，节点外的 $id$ 表示节点编号。

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

现在给出一棵二叉树，希望你找出它的一棵子树，该子树为对称二叉树，且节点数最多。请输出这棵子树的节点数。

注意：只有树根的树也是对称二叉树。本题中约定，以节点 $T$ 为子树根的一棵“子 树”指的是：节点$T$ 和它的全部后代节点构成的二叉树。

inputFormat:
第一行一个正整数 $n$，表示给定的树的节点的数目，规定节点编号 $1 \sim n$，其中节点 $1$ 是树根。

第二行 $n$ 个正整数，用一个空格分隔，第 $i$ 个正整数 $v_i$ 代表节点 $i$ 的权值。

接下来 $n$ 行，每行两个正整数 $l_i, r_i$，分别表示节点 $i$ 的左右孩子的编号。如果不存在左 / 右孩子，则以 $-1$ 表示。两个数之间用一个空格隔开。

outputFormat: 输出文件共一行，包含一个整数，表示给定的树的最大对称二叉子树的节点数。

hint:
**样例 1 解释**

![](https://cdn.luogu.com.cn/upload/image_hosting/4lfen5aa.png)
最大的对称二叉子树为以节点 $2$ 为树根的子树，节点数为 $1$。

**样例 2 解释**

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

最大的对称二叉子树为以节点 $7$ 为树根的子树，节点数为 $3$。

**数据规模与约定**

共 $25$ 个测试点。

$v_i ≤ 1000$。

- 测试点 $1 \sim 3, n ≤ 10$，保证根结点的左子树的所有节点都没有右孩子，根结点的右 子树的所有节点都没有左孩子。
- 测试点 $4 \sim 8, n ≤ 10$。
- 测试点 $9 \sim 12, n ≤ 10^5$，保证输入是一棵“满二叉树” 。
- 测试点 $13 \sim 16, n ≤ 10^5$，保证输入是一棵“完全二叉树”。
- 测试点 $17 \sim 20, n ≤ 10^5$，保证输入的树的点权均为 $1$。
- 测试点 $21 \sim 25, n ≤ 10^6$。

本题约定：

层次：节点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一节 点的层次等于其父亲节点的层次加 $1$。

 树的深度：树中节点的最大层次称为树的深度。

 满二叉树：设二叉树的深度为 $h$，且二叉树有 $2^h-1$ 个节点，这就是满二叉树。

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

完全二叉树：设二叉树的深度为 $h$，除第 $h$ 层外，其它各层的结点数都达到最大 个数，第 $h$ 层所有的结点都连续集中在最左边，这就是完全二叉树。

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


title: [NOIP2018 提高组] 旅行

background: NOIP2018 提高组 D2T1

description:
小 Y 是一个爱好旅行的 OIer。她来到 X 国，打算将各个城市都玩一遍。

小 Y 了解到，X 国的 $n$ 个城市之间有 $m$ 条双向道路。每条双向道路连接两个城市。 不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。并且， 从任意一个城市出发，通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些 道路从一个城市前往另一个城市。

小 Y 的旅行方案是这样的：任意选定一个城市作为起点，然后从起点开始，每次可 以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该 城市时经过的道路后退到上一个城市。当小 Y 回到起点时，她可以选择结束这次旅行或 继续旅行。需要注意的是，小 Y 要求在旅行方案中，每个城市都被访问到。

为了让自己的旅行更有意义，小 Y 决定在每到达一个新的城市（包括起点）时，将 它的编号记录下来。她知道这样会形成一个长度为 $n$ 的序列。她希望这个序列的字典序 最小，你能帮帮她吗？  对于两个长度均为 $n$ 的序列 $A$ 和 $B$，当且仅当存在一个正整数 $x$，满足以下条件时， 我们说序列 $A$ 的字典序小于 $B$。

- 对于任意正整数 $1 ≤ i < x$，序列 $A$ 的第 $i$ 个元素 $A_i$ 和序列 $B$ 的第 $i$ 个元素 $B_i$ 相同。
- 序列 $A$ 的第 $x$ 个元素的值小于序列 $B$ 的第 $x$ 个元素的值。

inputFormat:
输入文件共 $m + 1$ 行。第一行包含两个整数 $n,m(m ≤ n)$，中间用一个空格分隔。

接下来 m 行，每行包含两个整数 $u,v (1 ≤ u,v ≤ n)$ ，表示编号为 $u$ 和 $v$ 的城市之 间有一条道路，两个整数之间用一个空格分隔。

outputFormat: 输出文件包含一行，$n$ 个整数，表示字典序最小的序列。相邻两个整数之间用一个 空格分隔。

hint:
【数据规模与约定】

对于 $100\%$ 的数据和所有样例， $1 \le n \le 5000 $ 且 $m = n − 1$ 或 $m = n$ 。

对于不同的测试点， 我们约定数据的规模如下：

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


title: [NOIP2018 提高组] 填数游戏

background: NOIP2018 提高组 D2T2

description:
小 D 特别喜欢玩游戏。这一天，他在玩一款填数游戏。

这个填数游戏的棋盘是一个 $n \times m$ 的矩形表格。玩家需要在表格的每个格子中填入一个数字（数字 $0$ 或者数字 $1$），填数时需要满足一些限制。

下面我们来具体描述这些限制。

为了方便描述，我们先给出一些定义：

-  我们用每个格子的行列坐标来表示一个格子，即（行坐标，列坐标）。注意：行列坐标均从 $0$ 开始编号。
- 合法路径 $P$：一条路径是合法的当且仅当：
    1. 这条路径从矩形表格的左上角的格子 $(0,0)$ 出发，到矩形的右下角格子 $(n - 1,m - 1)$ 结束；
    2. 在这条路径中，每次只能从当前的格子移动到右边与它相邻的格子，或者从当前格子移动到下面与它相邻的格子。

  例如：在下面这个矩形中，只有两条路径是合法的，它们分别是 $P_1$：$(0,0)\to (0,1)\to (1,1)$ 和 $P_2$：$(0,0) \to (1,0) \to (1,1)$。

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

对于一条合法的路径 $P$，我们可以用一个字符串 $w(P)$ 来表示，该字符串的长度为 $n + m - 2$，其中只包含字符 $\texttt R$ 或者字符 $\texttt D$，第 $i$ 个字符记录了路径 $P$ 中第 $i$ 步的移动方法。$\texttt R$ 表示移动到当前格子右边与它相邻的格子，$\texttt D$ 表示移动到当前格子下面与它相邻的格子。例如，上图中对于路径 $P_1$，有 $w(P_1) = \texttt {RD}$；而对于另一条路径 $P_2$，有 $w(P_2) = \texttt {DR}$。

同时，将每条合法路径 $P$ 经过的每个格子上填入的数字依次连接后，会得到一个长度为 $n + m - 1$ 的 $01$ 字符串，记为 $s(P)$。例如，如果我们在格子 $(0,0)$ 和 $(1,0)$ 上填入数字 $0$，在格子 $(0,1)$ 和 $(1,1)$ 上填入数字 $1$（见上图红色数字），那么对于路径 $P_1$，我们可以得到 $s(P_1) = 011$，对于路径 $P_2$，有 $s(P_2) = 001$。

游戏要求小 D 找到一种填数字 $0$、$1$ 的方法，使得对于两条路径 $P_1$，$P_2$，如果 $w(P_1) > w(P_2)$，那么必须 $s(P_1) ≤ s(P_2)$。我们说字符串 $a$ 比字符串 $b$ 小，当且仅当字符串 $a$ 的字典序小于字符串 $b$ 的字典序，字典序的定义详见第一题。但是仅仅是找一种方法无法满足小 D 的好奇心，小 D 更想知道这个游戏有多少种玩法，也就是说，有多少种填数字的方法满足游戏的要求？

小 D 能力有限，希望你帮助他解决这个问题，即有多少种填 $0$、$1$ 的方法能满足题目要求。由于答案可能很大，你需要输出答案对 $10^9 + 7$ 取模的结果。

inputFormat: 输入文件共一行，包含两个正整数 $n,m$，由一个空格分隔，表示矩形的大小。其中 $n$ 表示矩形表格的行数，$m$ 表示矩形表格的列数。

outputFormat: 输出共一行，包含一个正整数，表示有多少种填 $0$、$1$ 的方法能满足游戏的要求。 注意：输出答案对 $10^9+7$ 取模的结果。


title: [NOIP2018 提高组] 保卫王国

background: NOIP2018 提高组 D2T3

description:
Z 国有 $n$ 座城市，$(n - 1)$ 条双向道路，每条双向道路连接两座城市，且任意两座城市都能通过若干条道路相互到达。

Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件：

- 一座城市可以驻扎一支军队，也可以不驻扎军队。
- 由道路直接连接的两座城市中至少要有一座城市驻扎军队。
- 在城市里驻扎军队会产生花费，在编号为 $i$ 的城市中驻扎军队的花费是 $p_i$。

小 Z 很快就规划出了一种驻扎军队的方案，使总花费最小。但是国王又给小 Z 提出了 $m$ 个要求，每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一给出回答。具体而言，如果国王提出的第 $j$ 个要求能够满足上述驻扎条件（不需要考虑第 $j$ 个要求之外的其它要求），则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第 $j$ 个要求无法满足，则需要输出 $-1$。现在请你来帮助小 Z。

inputFormat:
第一行有两个整数和一个字符串，依次表示城市数 $n$，要求数 $m$ 和数据类型 $type$。$type$ 是一个由大写字母 `A`，`B` 或 `C` 和一个数字 `1`，`2`，`3` 组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在【数据规模与约定】中 有具体的描述。

第二行有 $n$ 个整数，第 $i$ 个整数表示编号 $i$ 的城市中驻扎军队的花费 $p_i$。

接下来 $(n - 1)$ 行，每行两个整数 $u,v$，表示有一条 $u$ 到 $v$ 的双向道路。

接下来 $m$ 行，每行四个整数 $a, x, b, y$，表示一个要求是在城市 $a$ 驻扎 $x$ 支军队，在城市 $b$ 驻扎 $y$ 支军队。其中，$x,y$ 的取值只有 $0$ 或 $1$：
- 若 $x$ 为 $0$，表示城市 $a$ 不得驻扎军队。
- 若 $x$ 为 $1$，表示城市 $a$ 必须驻扎军队。
- 若 $y$ 为 $0$，表示城市 $b$ 不得驻扎军队。
- 若 $y$ 为 $1$，表示城市 $b$ 必须驻扎军队。

输入文件中每一行相邻的两个数据之间均用一个空格分隔。

outputFormat: 输出共 $m$ 行，每行包含一个个整数，第 $j$ 行表示在满足国王第 $j$ 个要求时的最小开销， 如果无法满足国王的第 $j$ 个要求，则该行输出 $-1$。


title: [SNOI2017] 炸弹

description:
在一条直线上有 $n$ 个炸弹，每个炸弹的坐标是 $ x_i $，爆炸半径是 $ r_i $，当一个炸弹爆炸时，如果另一个炸弹所在位置 $ x_j $ 满足：
$ |x_j-x_i| \le r_i $ ，那么，该炸弹也会被引爆。
现在，请你帮忙计算一下，先把第 $i$ 个炸弹引爆，将引爆多少个炸弹呢？

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

inputFormat:
第一行，一个数字 $n$ ，表示炸弹个数。
第 $2 \sim n+1$ 行，每行两个整数，表示 $x_i$，$r_i$，保证 $x_i$ 严格递增。

outputFormat: 一个数字，表示 $\sum \limits_{i=1}^n i\times$ 炸弹 $i$ 能引爆的炸弹个数。


title: [SCOI2012] 奇怪的游戏

description:
Blinker 最近喜欢上一个奇怪的游戏。

这个游戏在一个 $N \times M$ 的棋盘上玩，每个格子有一个数。每次 Blinker 会选择两个相邻的格子，并使这两个数都加上 $1$。

现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出 $-1$。

inputFormat:
输入的第一行是一个整数 $T$，表示输入数据有 $T$ 轮游戏组成。

每轮游戏的第一行有两个整数 $N$ 和 $M$，分别代表棋盘的行数和列数。
接下来有 $N$ 行，每行 $M$ 个数。

outputFormat: 对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出 $-1$。

hint:
对于 $30\%$ 的数据，保证 $ T\le 10,1\le N,M \le 8$。
对于 $100\%$ 的数据，保证 $T \le 10,1 \le N,M\le 40$，所有数为正整数且小于 $10^9$。


title: [SHOI2010] 最小生成树

description:
Secsa最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个 $ n $ 个点、 $ m $ 条边的无向图的最小生成树有一个Krustal算法和另一个Prim的算法。另外，他还知道，某一个图可能有多种不同的最小生成树。例如，下面图3中所示的都是图2中的无向图的最小生成树：

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

当然啦，这些都不是今天需要你解决的问题。Secsa想知道对于某一条无向图中的边AB，至少需要多少代价可以保证AB边在这个无向图的最小生成树中。为了使得AB边一定在最小生成树中，你可以对这个无向图进行操作，一次单独的操作是指：先选择一条图中的边 P1P2，再把图中除了这条边以外的边，每一条的权值都减少 $ 1 $ 。如图4所示就是一次这样的操作：

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

inputFormat:
输入文件的第一行有3个正整数 $ n,m,Lab $ 分别表示无向图中的点数、边数、必须要在最小生成树中出现的AB边的标号。

接下来 $ m $ 行依次描述标号为 $ 1,2,3 \ldots m $ 的无向边，每行描述一条边。每个描述包含3个整数 $ x,y,d $ ，表示这条边连接着标号为 $ x,y $ 的点，且这条边的权值为 $ d $ 。

输入文件保证 $ 1 \leq x,y \leq N $ ， $ x \neq y $ ，且输入数据保证这个无向图一定是一个连通图。

outputFormat: 输出文件只有一行，这行只有一个整数，即，使得标号为 $ Lab $ 边一定出现最小生成树中的最少操作次数。


title: [SCOI2003] 蜘蛛难题

description:
有一堆管道，还有一个蜘蛛$\text{Willy}$，如下图所示。所有管道的是上端开口，下端封底，直径都是$1cm$，连接两个管道的连接容量无限，但体积可以忽略不计。

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

在第一个管道上方有一个水源，从中有水不断往下流，速度为每秒$0.25cm^3$。由于管道横截面积为$0.25cm^3$，所以单给一个管道注水时水面每秒上升$1cm$。根据物理知识，在前$2$秒中，水注如左边的管道底部，第$[3,5]$秒时注入右边的管道，第$[6,9]$秒同时注入两个管道（虽然流量不变，但是由于同时给两个管道注水，因此水面上升的速度仅为每秒$0.5cm$），接触到蜘蛛。 给出管道和管道之间连接的位置，以及蜘蛛$\text{Willy}$的位置，求水面接触到$\text{Willy}$的时间。假设蜘蛛的实际位置比给出的略高一点，因此如果蜘蛛在左边管道的$n=4$的位置，答案应该是$5$秒。因为前两秒后水面虽然看起来接触到了$\text{Willy}$，但实际上比$\text{Willy}$略低一点。

inputFormat:
所有位置都用有序数对$(x, y)$表示，其中y坐标从上到下逐渐增大；$x$坐标从左到右逐渐增大，因此左上角的坐标为$(0,0)$，其他所有坐标值为$0$到$100$之间的整数。输入第一行为一个整数$p(1<=p<=20)$，表示管道的数目；以下$p$行，每行用$x, y, h$三个整数描述一根管道。$(x,y)$为管道左上角坐标；$h$为管道高度$(1<=h<=20)$。以下一行为一个整数$L(0<=L<=50)$，为连接的个数。

以下$L$行每行用三个整数$x, y, d$描述一个连接，$(x,y)$为左端点的坐标，$d$为连接的长度$(1<=d<=20)$。最后一行为两个整数$a,b$，表示$\text{Willy}$在管道$a$的$y$坐标为$b$的位置。管道按照在文件中出现的顺序编号为$1,2,3…p$

以下为一些假设： 水源总是在第一根管道的正上方, 连接不会穿越管道,任意两个连接的$y$坐标都不相同,任意两个管道的左上角的$x$坐标都不相同,任意连接的两个端点都在管道上（不会出现悬空的情形）

outputFormat: 仅一个整数，为水面接触到$\text{Willy}$的时间。如果水面无法接触到$\text{Willy}$，输出$-1$。


title: 坐标

background:
题解：https://blog.csdn.net/kkkksc03/article/details/84928342

小奔知道我的Minecraft的坐标参数有三个，分别是$X$，$Y$，$Z$，但是在小奔的眼中，有第四个参数$Q$，表示对这个坐标的喜爱，比如有些位置是小奔的家，$Q$的值会大，而有些地方是危险的矿洞，所以$Q$的值小。

description: 有$N$个坐标。对于第i个坐标的参数{$Xi$,$Yi$,$Zi$,$Qi$}和{$Xj$,$Yj$,$Zj$,$Qj$}存在$Xi$-$Xj$=$Yi$-$Yj$=$Zi$-$Zj$=$Qi$-$Qj$则称该坐标为优美坐标，现给出$N$个坐标，小奔想知道所有优美坐标的$j$-$i$的最小值和$i$+$j$的最大值，你能帮帮他吗？

inputFormat:
输入有$n$+1行，第一行为一个数$n$，接下来输入$n$行，每行$X$,$Y$,$Z$,$Q$四个整
数。

outputFormat:
输出只有一行，包括j-i的 最小值和i+j的最大值，中间有空格隔开， 数据
保证有解。


title: [USACO04OPEN] Cube Stacking

description:
约翰和贝茜在玩一个方块游戏。编号为 $ 1\ldots n $ 的 $ n $ ( $ 1 \leq n \leq 30000 $ )个方块正放在地上，每个构成一个立方柱。

游戏开始后，约翰会给贝茜发出 $ P $ ( $ 1 \leq P \leq 100000 $ )个指令。指令有两种：

1. 移动（M）：将包含 X 的立方柱移动到包含 Y 的立方柱上。
2. 统计（C）：统计含 X 的立方柱中，在 X 下方的方块数目。

写个程序帮贝茜完成游戏。

inputFormat:
第1行输入 $ P $ ，之后 $ P $ 行每行输入一条指令，形式为 `M X Y` 或者 `C X`。

输入保证不会有将立方柱放在自己头上的指令。

outputFormat: 对于每个统计指令，输出一行一个整数，代表其结果。


title: [USACO04OPEN] The Cow Lineup

description:
约翰的 $ N $（$ 1 \leq N \leq 100000 $）只奶牛站成了一列。每只奶牛都写有一个号牌，表示她的品种，号牌上的号码在 $ 1 \ldots K $（$ 1 \leq K \leq 10000 $ ）范围内。

比如有这样一个队列：1,5,3,2,5,3,4,4,2,5,1,2,3

根据约翰敏锐的数学神经，他发现一些子序列在这个队列里出现，比如"3,4,1,3"，而另一些没有。子序列的各项之间穿插有其他数，也可认为这个子序列存在。现在，他想用 $1 \sim K$ 之间的整数构造一个最短的子序列，使之不在奶牛序列里出现。达个子序列的长度是多少呢？

inputFormat: 第1行输入两个整数 $ N $ 和 $ K $ ，接下来 $ N $ 行输入奶牛序列.

outputFormat: 输出一行，最短的不出现子序列的长度。

hint:
样例解释：

所有长度为 $1$ 和 $2$ 的可能的子序列都出现了，但长度为 $3$ 的子序列"2,2,4"却没有出现。


title: [USACO04OPEN] MooFest G 加强版

description:
每一年，约翰的 $ N $ 只奶牛参加奶牛狂欢节。这是一个全世界奶牛都参加的大联欢。狂欢节包括很多有趣的活动，比如干草堆叠大赛、跳牛栏大赛，奶牛之间有时还相互扎屁股取乐。当然，她们会排成一列嚎叫，来欢庆她们的节日。奶牛们的叫声实在刺耳，以致于每只奶牛的听力都受到不同程度的损伤。现在告诉你奶牛 $ i $ 的听力为 $ v_i $ ，这表示如果奶牛 $ j $ 想说点什么让她听到，必须用高于 $ v_i \times dis(i,j) $ 的音量。因此，如果奶牛 $ i $ 和 $ j $ 想相互交谈，她们的音量必须不小于 $ \max (v_i,v_j) \times dis(i,j) $。其中 $ dis(i,j) $ 表示她们间的距离。

现在 $ N $ 只奶牛都站在一条直线上了，每只奶牛还有一个坐标 $ x_i $。如果每对奶牛都在交谈，并且使用最小音量，那所有 $ N(N-1)/2 $ 对奶牛间谈话的音量之和为多少？

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

接下来 $ N $ 行，每行输入两个数 $ v_i $ 和 $ x_i $ ，分别代表第 $ i $ 头奶牛的听力和坐标。

outputFormat: 输出一个数，代表这 $ N(N-1)/2 $ 对奶牛谈话时的音量之和。

hint:
### 数据范围

因为原数据下 $O(N^2)$ 算法可以通过，所以新添加了一些增强数据。

原数据作为子任务 $1$，新添加的数据作为子任务 $2$。

- 子任务 $1$（$1$ 分）：$1 \leq N,V_i,x_i \leq 2 \times 10^4$。
- 子任务 $2$（$99$ 分）：$1 \leq N,V_i,x_i \leq 5 \times 10^4$。


title: 仰望半月的夜空

background:
“你不久也会遇到喜欢的女生吧。听好了，你可得好好守护她喔。”

这是父亲给予戎崎裕一的教诲

父亲称不上是一个合格的父亲

但是，却正是这样的父亲，连接了戎崎裕一和秋庭里香

![](https://www.cnblogs.com/images/cnblogs_com/reverymoon/1200086/o_0.png)

秋庭里香，明明是那样的傲娇，却不得不去守护的女生

但同时，又是一个为了回忆，为了懵懂的爱情而坚强着的女生

你是不是在她身上看到了小夜子的身影呢？夏目吾郎医生

你是不是在他身上看到了过去的自己呢？夏目吾郎医生

也许疾病切断了人与人之间的联系，但是曾经存在的痕迹，定将会化作美好的回忆，流传下去

愿你们幸福

description:
半月的夜空中，寄托了多少人与人之间的思念啊

曦月知道，这些思念会汇集成一个字符串 $S$（$n = |S|$）。

由于思念汇集的过于复杂，因此曦月希望提炼出所有的思念。

我们定义 $Y_S(i)$ 表示对于字符串 $S$ 而言，长度为 $i$ 的子串中，字典序最小的，左端点最小的左端点的值

比如对于串 $S = \texttt{"baa"}$，$Y_S(1) = 2$、$Y_S(2) = 2$、$Y_S(3) = 1$。

曦月会告知你 $S$ 串，你只需要告诉曦月 $Y_S(i)$（$1 \le i \le n$）即可。

inputFormat:
第一行，两个参数，分别是 $\sigma \in \{10, 26, 10^7\}$ 和 $n$。

如果 $\sigma = 26$，那么第二行将是一个长为 $n$ 的小写字母字符串 $S$。

其他情况下，第二行将输入 $n$ 个位于 $[0, \sigma]$ 内的整数。

outputFormat: 输出一行，第 $i$ 个数表示 $Y_S(i)$ 的值。

hint:
数据范围的图不见了 QAQ

最大范围是 $1 \le n \le 3 \times {10}^5$。


title: [USACO12OPEN] Bookshelf S

description:
Farmer John 闲来无事的时候总喜欢坐下来看书。这些年来，他一共收集了 $N$ 本书（$1 \leq N \leq 2000$），他打算搭一个新的书架来装这些书。

每本书都有个宽度 $w_i$ 和高度 $h_i$，书必须按顺序来摆放（即同一层书架摆的书必须是连续的一个区间）。每层书架的总宽度不能超过 $L$（$1 \leq L \leq 10^9$），每层书架的高度等于这一层最高的书的高度，整个书架的高度等于每层书架的高度之和。

现在请你帮 FJ 求出书架高度的最小值。

inputFormat:
第一行两个整数 $N,L$。

接下来 $N$ 行，每行两个整数 $h_i,w_i$（$1 \leq h_i \leq 10^6$，$1 \leq w_i \leq L$）。

outputFormat: 输出一个整数，书架高度最小值。

hint: 第一层放第一本书，第二层放第二，三，四本书，第三层放第五本书，总高度为 $5+13+3=21$，可以证明不存在更优的方案。


title: xtq 的神笔

background: xtq 在小学四年级的时候得到了一套神奇的画笔。为了测试神笔的威力（以及展现自己过人的艺术天赋），他决定先为美术老师临摹几幅画。

description:
每幅画的形态可以抽象为排成一列的 $n$ 个格子，其中第 $i$ 个格子具有一个权值 $a_i$。

xtq 有足够多不同颜色的画笔，每当他使用一根笔，他可以在格子上画下至少长度为 $k$ 的连续一段，然后再换另一根笔从下一个格子继续画，其中 $k<n$。

美术老师为了考验 xtq 的绘画功力，为他设置了一些挑战。

他可以从 $1$ 到 $k$ 的任意一个格子开始画到编号为 $n$ 的格子，其中从第 $i$ 个格子开始会获得 $b_i$ 的得分。

假设 xtq 使用同一根画笔，从编号为 $i$ 的格子连续地画到编号为 $j$ 的格子，他就会获得（$a_i \mathbin{\mathrm{or}} a_{i+1} \mathbin{\mathrm{or}} a_{i+2} \mathbin{\mathrm{or}} \cdots \mathbin{\mathrm{or}} a_j) + (a_i \mathbin{\mathrm{and}} a_{i+1} \mathbin{\mathrm{and}} a_{i+2} \mathbin{\mathrm{and}} \cdots \mathbin{\mathrm{and}} a_j) + \gcd(a_i, a_{i+1}, a_{i+2}, \ldots, a_j)$ 的分数，其中 $\gcd$ 代表最大公约数。

现在，xtq 希望找到一种安排画笔使用的方案，使得对于每一幅需要临摹的画，他总共获得的分数尽量多。

inputFormat:
第一行，一个正整数 $T$，表示画的数量。

对于每一幅画：

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

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

第三行，$k$ 个整数 $b_1, b_2, b_3, \ldots , b_k$。

outputFormat: 对于每一幅画，输出一个整数，代表 xtq 完成这幅画最多能获得的分数。


title: 归程

description:
dkw在玩一款叫做《ION8102》的游戏，这个游戏分为序章，第一章，第二章。

她已经满血通过了序章，来到了第一章的第一关。

这关的名字叫归程，她需要到达指定地点，这一路上要经过 $m$ 扇机关门。

每扇机关门上有一个钥匙孔，只有特制钥匙可以放进去，里面有 $k$ 把转轮锁，每个转轮锁都要恰好转到目标位置 $a_i$ 才能开门，每个转轮锁的最大刻度都是 $v$ ，刻度标号从 $0$ 到 $v$ ，每个转轮锁初始位置都是 $0$ 。

dkw身上有 $n$ 把钥匙，每把钥匙都有 $k$ 个转动量 $b_i$ ，分别代表这把钥匙转一圈，可以让机关门中的这个转轮锁走多少个位置。

每扇机关门还有一个圈数限制 $c$ ，也就是你总共只能用钥匙转最多 $c$ 圈，并且每把钥匙只能正着转，只能转整数圈。

任务要求顺次打开这 $m$ 扇门，这么简单的问题dkw当然秒了，但是dkw好奇的是：对于每一扇门，有多少种方案能顺利打开呢？

两种方案不同，当且仅当两种方案中总圈数不同或某一圈所用钥匙不同。

如果你解答了dkw的好奇心，那么你将会收到她的一份大~礼物——100分！

inputFormat:
第一行包含四个正整数 $n,m,k,v$ ，含义详见题目描述。

接下来 $n$ 行，每行包含 $k$ 个非负整数，依次代表这把钥匙的转动量 $b_i$ 。

接下来 $m$ 行，首先是一个非负整数 $c$ 代表圈数限制，接着是 $k$ 个非负整数，依次代表这扇门的目标位置 $a_i$ 。

outputFormat: 对于每个询问，输出一行一个非负整数代表这次询问的答案，对 $2333$ 取模。


title: [USACO04OPEN] Cave Cows 1

description:
很少人知道其实奶牛非常喜欢到洞穴里面去探险。

洞窟里有 $ N $ ( $ 1 \leq N \leq 100 $ )个洞室，由 $ M $ ( $ 1 \leq M \leq 1000 $ )条双向通道连接着它们。每对洞室间至多只有一条双向通道，有 $ K $ ( $ 1 \leq K \leq 14 $ )个洞室，里面放有1捆干草．牛吃1捆干草，体重指数就会增加1。

贪吃的贝茜要到洞窟里面探险，她希望能吃尽量多的干草，但每条通道有一个宽度阈值，如果体重指数超过相应的阈值，贝茜就会被卡住。

她从洞窟1出发，体重指数为0。在洞里溜达一圈后，她要返回洞窟1。

那她最多能吃多少捆干草呢？注意，贝茜经过一个洞室，不一定非要吃掉里面的干草。

inputFormat:
第1行输入 $ N,M,K $ 。

之后 $ K $ 行每行一个整数，表示在这个洞室放有一捆干草；接下来 $ M $ 行每行三个整数，表示一条双向通道的起点终点和宽度阈值。

outputFormat: 最多能吃掉的干草数。


title: [USACO04OPEN] Cave Cows 2

description:
洞窟里有一道长长的通道．它由 $ N $ ( $ 1 \leq N \leq 25000 $ )段道尾相连构成，编号分别为 $ 1 \ldots N $ 。

每个通道有一个阈值，其范围在 $ [1,10^9] $ 。依次通过 $ i \ldots j $ 的通道，那奶牛的体重指数就不能超过 $ i \ldots j $ 通道中阈值的最小值。贝茜有
$ Q $ ( $ 1 \leq Q \leq 25000 $ )个问题，想请教你由 $ i $ 到 $ j $ 的通道的阈值的最小值。

inputFormat:
第1行输入 $ N $ 和 $ Q $ 。

接下来 $ N $ 行输入每个通道的阈值，之后 $ Q $ 行每行两个整数，对应问题中的 $ i $ 和 $ j $（ $ i<j $ ）。

outputFormat: 对于每个问题，输出其结果。


title: [USACO04OPEN] Cave Cows 3

description:
约翰的 $ N $ ( $ 1 \leq N \leq 50000 $ )只牛在一个黑魃魃的洞里探险，他们只能通过叫声交流。

两只牛之间的曼哈顿距离决定了声音传播的时间。即牛1与牛2交流，需要的时间为
 $ |x_1-x_2|+|y_1-y_2| $ 。其中 $ -10^6 \leq x_1,x_2,y_1,y_2 \leq 10^6 $ 。

那任意一对牛之间交流时间的最大值为多少？

inputFormat: 第1行输入 $ N $ ，接下来每行输入一只牛的坐标。

outputFormat: 交流时间最大值（即最大曼哈顿距离）。

hint:
样例解释：

$ (2,7) $ 和 $ (8,1) $ 两点间的距离最大，为12。


title: [USACO04OPEN] Cave Cows 4

description:
一道竖直的石墙横在贝茜前面，她必须越过去。

石墙可以看成一个xz平面，贝茜开始的时候在(0，0)，只要她到达 $ z=T $
 ( $ 1 \leq T \leq 200000 $ )的位置，就算翻越成功。

墙上有 $ N $ ( $ 1 \leq N \leq 50000 $ )块石头突出，成为贝茜的落蹄石。如果两个落蹄石之间x方向和z方向的距离均不超过2，那贝茜就可以攀上另一块落蹄石。

帮助贝茜计算她是否能够翻越石墙，如果可以，最少需要踩多少块落蹄石。

inputFormat:
第1行输入 $ N $ 和 $ T $ 。

接下来 $ N $ 行，每行输入坐标 $ (x,z) $ ，表示一个石头的位置．其中 $ x \leq 10^6 $ ， $ z \leq T $ ，保证 $ (0,0) $ 不会出现。

outputFormat: 如果可以翻越则输出最少需要的落蹄石数（起点不计入），否则输出 $ -1 $ 。


title: zhtobu3232的线段树

background:
$zhtobu3232$发现了一道线段树题,在$30s$后$zhtobu3232$敲出了一份线段树并且ac了这题

当然，这是$zhtobu3232$刚刚学oi时候的事情了，现在的他只需$1s$就可以敲出一份完美的线段树板子

现在$ztb$想要重温一下他之前切过的水题,不过他的笔记本电脑年代有些久远，导致内存条损坏了很多，从而线段树也开始损坏了，现在他不关心当年敲了什么水题而只关心这个线段树可以表示出多少合法的区间，请你计算出这个数字并对$998244353$取模

顺便说一句$ztb$认为这个问题比线段树简单多了，因为线段树的节点少了,所以维护的信息也少了，他已经用$1ms$敲好了$std$,接下来就等着你帮他验题了

description:
我们定义一颗长度为n的线段树是这样的算法流程执行build(0,n)后建出的二叉树

(注意这里的线段树应该和大家平常写的没什么区别(除了区间是左开右闭表示的以外)，会线段树的可以忽略)

```C

node build (l,r)
{
	node p=newnode();p.l=l+1;p.r=r;
    if(r-l==1)return p;
    mid=(l+r)/2;
    node.leftson=build(l,mid);
	node.rightson=build(mid,r);
    return p;
}

```

而我们定义一个区间$(l,r)$在线段树上的**拆分**是将这个区间表示为线段树上若干个节点的集合，满足这些节点对应的区间不相交,不嵌套,这些区间的并集恰好是$(l,r)$，并且没有两个节点是兄弟关系

拆分的伪代码如下

```C
void solve(l,r,dl,dr)
{
	if(dl==l&&dr==r){S.push(node(l+1,r));return;}
	 mid=(l+r)/2;
    if(dl<mid)solve(l,mid,dl,min(dr,mid));
    if(mid<dr)solve(mid,r,max(dl,mid),dr);
}

```
当我们执行完$solve(0,n,l-1,r)$之后得到的S集合就是区间$(l,r)$在$(1,n)$这颗线段树上的**拆分**了

(换句话说就是你平时写线段树时将一个区间拆成$O(logn)$个区间的操作)

现在我们给出了m个区间$(l,r)$，这些区间在线段树$(1,n)$上拆分出来的节点都是非法节点，换句话说这些节点都不可以使用了

现在请你计算有多少个区间$(l,r)$是合法的，满足两个限制条件

第一：$1 \leq l \leq r \leq n$

第二：这个区间在线段树$(1,n)$上的拆分不含有非法的节点

答案对998244353取模

inputFormat:
**为了避免您被题意杀，请务必按照题目中给出的左开右闭法建线段树，采用其他的建树方式可能导致线段树的形态和std中的线段树不符导致wa**

第一行两个整数n,m表示线段树的长度和区间个数

接下来m行每行两个整数l,r,表示$(l,r)$这个区间在线段树上拆分出的节点全部为非法节点

outputFormat: 仅一行一个整数，表示所有合法的区间个数对998244353取模之后的值


title: [COCI2017-2018#7] Timovi

description:
We need to arrange M kids in N teams. We begin by placing K kids in each team, starting
from the first to the $N^{th}$
team. When we finish with the $N^{th}$
team, we switch directions and
continue, placing K kids in each team, from the $(N-1)^{th}$
to the first team, respectively. When
we finish with the first team, we switch directions again and continue the process from the
second to the $N^{th}$
team, respectively, and so on until there are no kids left to distribute. For
example, if we have three teams, we will place K kids in teams in the following order: first
team, second team, third team, second team, first team, second team, etc.

If, at any points, there are less than K kids left to place in the current team, we place all the
remaining kids in that team and end the process.

Output the number of kids in each team when the process ends.

inputFormat:
The first line of input contains the integers N (2 ≤ N ≤ 200 000), K and M
(1 ≤ K ≤ M ≤ 2 000 000 000) from the task.

outputFormat:
In a single line, output the number of kids in each of the N teams, respectively from the first
to the $N^{th}$
team.

translation:
把$m$个人放在$n$个队伍里。
规则：
- 每次放$k$个人
- 顺序为$1^{th}$->$2^{th}$->$3^{th}$->……->$(n-1)^{th}$->$n^{th}$->$(n-1)^{th}$->$(n-2)^{th}$->……->$2^{th}$->$1^{th}$->$2^{th}$->……
- 一直重复到$\text{当前剩余人数}<k$为止。此时剩下的人全部放在当前队里
### **输入格式：** 一行，分别是$\text{n、k、m}$
### **输出格式：** 一行，$n$个数，分别是每个队伍分到的人数

hint: In test cases worth a total of 40 points, it will hold M / K ≤ 200 000.


title: [COCI2017-2018#7] Go

description:
Branimirko is still a passionate player of the world-renowned game Pokémon Go. Recently,
he decided to organize a competition in catching Pokémon. It will be held in Ilica street in
Zagreb, and the main sponsor is his friend Slavko. The reward is, of course, candy!

Ilica is, as we all know, the longest street in Zagreb. There are N houses on the same side of
the street, and each house has a house number between 1 and N. The competition begins
at house number K.

Before the competition, Branimirko looked at the map and saw M Pokémon. Each Pokémon
is located at its (distinct) house number Ai
, is valued at Bi candy, and can be caught only in
the next Ti seconds, after which it disappears from the map and is impossible to catch.

Branimirko can visit one house number per second. Also, when he catches a Pokémon, that
Pokémon disappears from the map.

Since Branimirko really likes candy, he asked for your help.

Help him and determine the maximal amount of candy he can get!

inputFormat:
The first line of input contains integers N, K (1 ≤ K ≤ N ≤ 1 000) and M (1 ≤ M ≤ 100), the
number of houses, the starting house number and the number of Pokémon.

Each of the following M lines contains integers $A_i$
(1 ≤ $A_i$ ≤ N), $B_i$
(1 ≤ $B_i$ ≤ 100) and $T_i$
(1 ≤ $T_i$ ≤
2 000) from the task.
In the input data, the Pokémon will always be in a strictly ascending order by house number $A_i$ .

outputFormat: You must output the required maximal amount of candy from the task.

translation:
Branimirko 是世界著名游戏 Pokémon Go 的一位热情玩家。最近，他决定组织一场抓小精灵的比赛。比赛将在 Zagreb 的 Ilica 大街举行，主要赞助商是他的朋友 Slavko。奖励当然是糖果!

我们都知道，Ilica 是 Zagreb 最长的街道。在街道的同一侧有 $N$ 栋房子，房子从左到右分别依次有 $1$ 到 $N$ 的门牌号。

比赛前，Branimirko 看了看地图，发现了一共有 $M$ 只小精灵。每个小精灵都位于自己的各不相同的房子里，第 $i$ 个房子门牌号为 $A_i$，小精灵价值 $B_i$ 个糖果，并且只能在 $T_i$ 秒内被抓，之后它就会从地图上消失。

Branimirko 第 $1$ 秒在门牌号为 $K$ 的房子。接下来每一秒它可以移动到门牌号相邻的房子，或者不移动。当他在一个时刻和一只小精灵处在相同的房子时，他就会抓住这只小精灵，获得其对应的糖果，且这只小精灵就从地图上消失了。

因为 Branimirko 真的很喜欢糖果，所以他请求你的帮助。

帮助他求出他可以得到多少糖果。

### 输入格式

输入的第一行包含三个整数 $N,K$（$1\le K\le N\le 10^3$）和 $M$（$1\le M\le 100$），代表房子数目，比赛开始的房子门牌号和小精灵的数量。

接下来的 $M$ 行每一行都包含三个整数 $A_i$（$1\le A_i\le N$），$B_i$（$1\le B_i\le 100$）和 $T_i$（$1\le T_i\le 2000$）。在输入数据中，小精灵始终按照房间号 $A_i$ 严格升序给出。

### 输出格式

输出可获取的最大糖果数量。

### 说明

在测试用例中，对于 $20\%$ 的数据，满足 $M\le 10$。

对于另外 $20\%$ 的数据，满足 $M\le 20$。

### 样例 1 解释

一种策略是，Branimirko 首先在第 $3$ 个房子（$5$ 颗糖果）捕捉小精灵，然后分别在第 $7$ 个房子（$10$ 颗糖果）和第 $9$ 个房子（$100$ 颗糖果），总共 $115$ 颗糖果。

注意到 Branimirko 无法在 $1$ 号房子里抓住小精灵，因为他无法从他的起始位置（$5$ 号房子）及时到达这里。

hint:
In test cases worth 20% of total points, it will hold M ≤ 10.

In additional 20% of total points, it will hold M ≤ 20.

**Clarification of the first test case:**

One strategy is that Branimirko first catches the Pokémon at house number 3 (5 candy), then,
respectively, house numbers 7 (10 candy) and 9 (100 candy) for a total of 115 candy.

Notice that Branimirko can’t catch the Pokémon at house number 1, because he can’t reach it in time
from his starting position (house number 5).


title: [COCI2017-2018#7] Clickbait

description:
While surfing online, Slavko came across an ad displaying a system of containers and pipes
(an example of such system is illustrated in the image below) with the message: “If container
**1** starts filling up with water, determine the order in which the containers get filled up.”

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

The system consists of K containers denoted with numbers from 1 to K, and we can describe
it using a matrix of characters with N rows and M columns. The containers are **in the shape of a rectangle**, and the outlines of the containers and pipes are shown with the following
characters:

-  ‘-’ if it’s a horizontal part of the outline,
-  ‘|’ if it’s a vertical part of the outline, and
-  ‘+’ if it’s a spot where the horizontal and vertical parts of the outline connect. An exception is where the containers and pipes connect. In that case, the container outline dominates (see sample tests).

In an arbitrary place within each container, there is a string of digits that represent the label
of the container, and all the other fields in the matrix are equal to ‘.’ (dot).

All containers except the one labeled with 1 have **exactly one** supply pipe that enters the
container in its **upper side**. The container labeled with 1 does not have a supply pipe.

The containers can have multiple (also possible, zero) discharge pipes that leave the
container out of its **lateral side**. The places where discharge pipes leave a container will be
in mutually **distinct rows** in the matrix.

The pipes directly connect two containers, which means that **it is not possible** to split the
pipes or connect multiple pipes into one, and no two pipes will intersect. On their way,
looking from the source to the destination container, the pipes always descend to the
following row or stay in the same row. In other words, they never go back to the previous
row, so the water can flow freely from one container to another.

The water enters a container until it is full. If the water level reaches the level of the
discharge pipe, the water will flow through that pipe until the container the pipe leads into is
filled up.

Help Slavko and determine the order in which the containers will fill up.

**Please note:**
- The test data is such that each character ‘+’ is surrounded with **exactly one character** ‘-’ to the left or the right side and **exactly one** character ‘|’ to the upper or lower side, and **all other** adjacent characters in directions up, down, left and right will be equal to ‘.’ (dot).
- The only places where the pipe in the matrix is in a field adjacent to the container outline are the places where the pipe enters or exits the container. In other words, a pipe will never run right next to a container (except where it connects with the
container). The entry for the supply pipe is labeled with the character ‘|’ above a container, whereas the exit of the discharge pipe is labeled with the character ‘-’ on the lateral side of a container.

inputFormat:
The first line contains two integers N and M (1 ≤ N, M ≤ 1000), matrix dimensions.

The following N lines contain M characters describing the container system.

outputFormat:
You must output K lines. The $i^{th}$
line contains the label of the container that fills up $i^{th}$
. A
solution will always exist and will be unique.

translation:
在上网的时候，Slavko遇到了一个广告，这个广告上面有一个由容器和管道组成的系统（如图是一个系统的例子）和一行字：“如果往编号为1的容器里注水，请确定这些容器被注满水的顺序。”
这个系统包含K个编号为1到K的容器，并且我们可以用一个N×M的矩阵来描述它。**这些容器的形状为长方形**。容器和管道的轮廓将用这些字符表示：
- 如果字符为‘-’，那么这个位置是容器和管道的轮廓的水平部分。
- 如果字符为‘|’，那么这个位置是容器和管道的轮廓的垂直部分。
- 如果字符为‘+’，那么这个位置同时是容器和管道的轮廓的水平和垂直部分。（即容器的四个角，管道的拐弯部分），一个例外是容器与管道的相交部分，在这个位置不使用+。
在每一个容器内的某个位置内，都存在一个表示这个容器编号的数字串。矩阵内既不是容器和管道的轮廓，又不是表示容器编号的数字串的位置上的字符为'.'。
除了编号为1的容器以外，所有的容器的**顶部都接入且只接入了一条可以使水进入容器的**管道。编号为1的容器的顶部没有管道。
每个容器的**侧面**可以接入多条（也可以没有）可以使水流出容器的管道。**没有两个可以使水流出容器的管道与容器的连接处在同一个高度。**
管道必须有方向的连接两个容器，这也就意味着一条管道**不能**在某些地方分成两条管道，或是两条管道交汇成一条管道，并且没有两条管道会相交。并且管道永远不会向上拐弯，所以可以保证管道里的水可以正常的向下流动并且流入对应接入的容器里。
水只能进入没有被装满水的容器。如果一个容器中的水位达到了可以使水流出的管道的高度，水将会流入这个管道的另一端所接入的容器里，直到那个容器满了为止。
请帮助Slavko确定这些容器被注满水的顺序。
**请注意：**
- 在矩阵中，每一个字符'+'都**有且仅有一个**'-'字符在其左边或右边与其相邻，并且**有且仅有一个**'|'字符在其上边或下边与其相邻。其余的与其相邻的字符将均为'.'。
- 在字符矩阵中，管道与容器轮廓相邻的唯一可能的位置是管道与容器连接的位置。换句话说，除了管道与容器连接的情况，管道不可能与容器相邻。在与容器连接的位置，管道使水流入容器的一端用'|'标识，使水流出容器的一端用'-'标识。

输入格式

第一行，两个整数N,M(1≤N,M≤1000)，表示矩阵的大小。
接下来的N行，每行M个字符，描述了如题目所述的容器系统。

输出格式

你必须输出K行。第i行表示第i个被注满水的容器的编号。输入保证存在唯一解。

说明

对于$70%$的数据，满足N,M≤100。
样例1的解释：
开始向容器1注水。
容器1中的水位升高，并且在某个时刻达到通向容器2的管道的高度。水流进管道并最终流向容器2，直到容器2装满水为止。
此后，容器1中的水位继续升高，直到达到通向容器3的管道的高度，水流进管道并最终流向容器3，直到容器3装满水为止。
最后，容器1中的水位持续升高，直到容器1装满水。

hint:
In test cases worth 70% of total points, it will hold N, M ≤ 100.

**Clarification of the first test case:**

Container 1 starts filling up with water.

The water level in container 1 grows, and in one moment reaches the level of the discharge pipe leading to container 2. The water flows through the pipe until container 2 fills up.

After that, the water level in container 1 keeps growing until it reaches the level of the discharge pipe leading to container 3, which fills up next.

Finally, the water level in container 1 keeps growing and the container fills up.


title: [COCI2017-2018#7] Dostavljač

description:
Ever since Krešo started growing chili peppers, N restaurants all over Croatia showed
interest in his peppers so they could enrich their dishes with real spice. Because of high
demand, Krešo decided to start working as a delivery guy of chili peppers.

The restaurants are denoted with numbers from 1 to N and are mutually connected with N -
1 roads such that traveling between any two restaurants is possible. Krešo begins his
journey in the restaurant denoted with 1. In one unit of time, he can either drive to the
adjacent restaurant or deliver the peppers to the current restaurant. For each restaurant, we
know the required amount of peppers $A_i$.

Since delivering goods is tiring, Krešo decided to spend a total of M units of time on delivery
and travel, after which he plans to take a break.

Determine the maximal amount of peppers Krešo can deliver in the given timeframe. You
can assume that Krešo always carries an unlimited supply of peppers.

inputFormat:
The first line of input contains two integers N and M (1 ≤ N, M ≤ 500), the number of
restaurants and the time Krešo plans to spend delivering peppers.

The second line of input contains N integers $A_i$
(1 ≤ $A_i$ ≤ $10^6$
), the required amount of peppers
for restaurants denoted with i (1 ≤ i ≤ N).

Each of the following N - 1 lines contains two integers U and V (1 ≤ U, V ≤ N, U ≠ V) that
represent the road between restaurants U and V.

outputFormat: You must output the maximal amount of peppers Krešo can deliver in the given timeframe.

translation:
自从 Krešo 开始种植辣椒以来，克罗地亚各地的 $N$ 家餐馆都对他的辣椒感兴趣，因此他们可以用真正的香料来丰富他们的菜肴。由于需求量很大，Krešo 决定开始作为辣椒的送货员。

餐馆用从 $1$ 到 $N$ 的数字表示，并且与 $N - 1$ 个道路相互连接，使得可以在任何两个餐馆之间旅行。Krešo 在 $1$ 号餐厅开始他的旅程。在一个单位的时间里，他可以开车到相邻的餐厅或将辣椒送到现在的餐馆。对于每家餐厅，我们都知道所需的辣椒数量 $A_i$。

由于交付货物很累，Krešo 决定在交付和旅行上花费总共 $M$ 个单位的时间，之后他计划休息一下。

确定 Krešo 在给定时间范围内可以提供的最大辣椒数量。你可以假设 Krešo 总是带有无限量的辣椒。

### 输入格式

第一行输入包含两个整数 $N$ 和 $M$（$1 \le N, M \le 500$），餐馆数量和 Krešo 计划用于交付辣椒的时间。

第二行输入包含 $N$ 个整数 $A_i$（$1 \le A_i \le 10^6$），用 $i$ 表示的餐馆所需的辣椒数量（$1 \le i \le N$）。

以下 $N - 1$ 行中的每一行包含两个整数 $U$ 和 $V$（$1 \le U, V \le N$，$U \ne V$），其表示餐馆 $U$ 和 $V$ 之间的道路。

### 输出格式

您必须输出 Krešo 在给定时间范围内可以提供的最大量的辣椒。

hint:
**Clarification of the first test case:**

In the first step, Krešo will deliver the peppers to restaurant 1.

In the second step, Krešo will travel to restaurant 3.

In the third step, Krešo will deliver the peppers to restaurant 3.

He is left with 2 units of time, in which he can drive to restaurant 2, but he lacks one unit of time to
deliver the peppers to that restaurant.


title: 【模板】多项式多点求值

description: 给定一个 $n$ 次多项式 $f(x)$ ，现在请你对于 $i \in [1,m]$ ，求出 $f(a_i)$ 。

inputFormat:
第一行两个正整数 $n,m$ 表示多项式的次数及你要求的点值的数量。

第二行 $n+1$ 个非负整数，由低到高地给出多项式的系数。

第三行 $m$ 个非负整数，表示 $a_i$ 。

outputFormat:
一共 $m$ 行，每行 $1$ 个非负整数。

第 $i$ 行的数字表示 $f(a_i)$ 。

答案对 $998244353$ 取模。


title: [NOIP2018 提高组] 旅行 加强版

description:
小 Y 是一个爱好旅行的 OIer。她来到 X 国，打算将各个城市都玩一遍。

小Y了解到，X 国的 $n$ 个城市之间有 $m$ 条双向道路。每条双向道路连接两个城市。 不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。并且， 从任意一个城市出发，通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些 道路从一个城市前往另一个城市。

小 Y 的旅行方案是这样的：任意选定一个城市作为起点，然后从起点开始，每次可 以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该 城市时经过的道路后退到上一个城市。当小 Y 回到起点时，她可以选择结束这次旅行或 继续旅行。需要注意的是，小 Y 要求在旅行方案中，每个城市都被访问到。

为了让自己的旅行更有意义，小 Y 决定在每到达一个新的城市（包括起点）时，将 它的编号记录下来。她知道这样会形成一个长度为 $n$ 的序列。她希望这个序列的字典序 最小，你能帮帮她吗？  对于两个长度均为 $n$ 的序列 $A$ 和 $B$，当且仅当存在一个正整数 $x$，满足以下条件时， 我们说序列 $A$ 的字典序小于 $B$。

- 对于任意正整数 $1 ≤ i < x$，序列 $A$ 的第 $i$ 个元素 $A_i$ 和序列 $B$ 的第 $i$ 个元素 $B_i$ 相同。
- 序列 $A$ 的第 $x$ 个元素的值小于序列 $B$ 的第 $x$ 个元素的值。

inputFormat:
输入文件共 $m + 1$ 行。第一行包含两个整数 $n,m(m ≤ n)$，中间用一个空格分隔。

接下来 m 行，每行包含两个整数 $u,v (1 ≤ u,v ≤ n)$ ，表示编号为 $u$ 和 $v$ 的城市之 间有一条道路，两个整数之间用一个空格分隔。

hint:
【数据规模与约定】

对于 $100\%$ 的数据和所有样例， $1 \le n \le 500000 $ 且 $m = n - 1$ 或 $m = n$ 。

具体规定详见正常版本（除 testcase11-13）


title: 块速递推

background:
shadowice1984 发现了一道题：求斐波那契数列第 $n$ 项模 $10^9+7$ 的值，$n \leq 10^9$。

shadowice1984 想了一个星期可他还是不会做。

当然，这是 shadowice1984 刚学 OI 时候的事情了，今天他学习了矩阵快速幂并且花了一整天解决了上面的问题。

他决定出一道题来测试你的矩阵快速幂水平如何，为了检查他花了一个星期写出的 std 到底有没有错，他决定让你来帮他验题。

description:
给定一个数列 $a$ 满足递推式

$$a_{n}=233a_{n-1}+666a_{n-2},a_{0}=0,a_{1}=1$$

求这个数列第 $n$ 项模 $10^9+7$ 的值，一共有 $T$ 组询问。

为了在某种程度上减少你的输入和输出量，我们采用以下的代码来生成询问：

```C
namespace Mker
{
	unsigned long long SA,SB,SC;
	void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}
	unsigned long long rand()
	{
	    SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;
	    unsigned long long t=SA;
		SA=SB,SB=SC,SC^=t^SA;return SC;
	}
}
```
在调用 `Mker::init()` 函数之后这个随机数生成器便可以正常工作了，当你第 $i$ 次调用 `Mker::rand()` 函数时返回的便是第 $i$ 次询问的 $n$ 值。

为了减少你的输出量，你只需要输出所有询问答案的异或和。

inputFormat: 仅一行四个整数，表示 $T,SA,SB,SC$ 的值，你可以在读入 $T$ 之后直接调用 `Mker::init()` 来完成输入工作。

outputFormat: 仅一行一个整数，表示所有答案的异或和。

hint:
$SA,SB,SC$ 均在 `unsigned long long` 数据类型的范围之内，由此可以发现返回的 $n$ 值也是 `unsigned long long` 数据类型的范围之内。

前 6 个测试点每个测试点 $1$ 分。

对于 1,2 测试点 $T \leq 5000$。

对于 3,4,5,6 测试点 $T \leq 500000$。

对于所有测试点 $1 \leq T \leq 5×10^7$。


title: [CQOI2006] 简单题

description:
有一个 $n$ 个元素的数组，每个元素初始均为 $0$。有 $m$ 条指令，每条指令为两种操作中的一种：
1. 让其中一段连续序列数字反转；（即 $0$ 变 $1$，$1$ 变 $0$）
2. 询问某个元素的值。

例如当 $n=20$ 时，$10$ 条指令如下：

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

inputFormat:
第一行包含两个整数 $n,m$，表示数组的长度和指令的条数。

接下来 $m$ 行，每行的第一个数 $t$ 表示操作的种类：

* 若 $t=1$，则接下来有两个数 $L,R$，表示反转区间 $[L,R]$ 的每个数；
* 若 $t=2$，则接下来只有一个数 $i$，表示询问的下标。

outputFormat: 每个操作 $2$ 输出一行（非 $0$ 即 $1$），表示每次操作 $2$ 的回答。


title: [ZJOI2004] 嗅探器

description:
某军搞信息对抗实战演习，红军成功地侵入了蓝军的内部网络。

蓝军共有两个信息中心，红军计划在某台中间服务器上安装一个嗅探器，从而能够侦听到两个信息中心互相交换的所有信息。

但是蓝军的网络相当的庞大，数据包从一个信息中心传到另一个信息中心可以不止有一条通路。

现在需要你尽快地解决这个问题，应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获？

inputFormat:
输入文件的第一行一个整数 $n$，表示蓝军网络中服务器的数目。

接下来若干行是对蓝军网络的拓扑结构描述，每行是两个整数 $i,j$ 表示编号为 $i$ 和编号为 $j$ 的两台服务器间存在双向连接。

服务器的编号从 $1$ 开始，一行两个 $0$ 表示网络的拓扑结构描述结束，再接下来是两个整数 $a,b$ 分别表示两个中心服务器的编号。

outputFormat: 输出满足条件的服务器编号。如果有多个解输出编号最小的一个，如果找不到任何解，输出 `No solution`。

hint: 对于 $100\%$ 的数据，$1\le n\le 2 \times 10^5$，边数不超过 $5 \times 10^5$。


title: 【模板】可持久化文艺平衡树

background: 这是一道模板题。

description:
您需要写一种数据结构，来维护一个序列，其中需要提供以下操作（**对于各个以往的历史版本**）：

1. 在第 $p$ 个数后插入数 $x$。
2. 删除第 $p$ 个数。
3. 翻转区间 $[l,r]$，例如原序列是 $\{5,4,3,2,1\}$，翻转区间 $[2,4]$ 后，结果是 $\{5,2,3,4,1\}$。
4. 查询区间 $[l,r]$ 中所有数的和。

**和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本（操作 $4$ 即保持原版本无变化），新版本即编号为此次操作的序号。**

**本题强制在线。**

inputFormat:
第一行包含一个整数 $n$，表示操作的总数。

接下来 $n$ 行，每行前两个整数 $v_i, \mathrm{opt}_i$，$v_i$ 表示基于的过去版本号（$0 \le v_i < i$），$\mathrm{opt}_i$ 表示操作的序号（$1 \le \mathrm{opt}_i \le 4$）。

若 $\mathrm{opt}_i=1$，则接下来两个整数 $p_i, x_i$，表示操作为在第 $p_i$ 个数后插入数 $x$ 。
若 $\mathrm{opt}_i=2$，则接下来一个整数 $p_i$，表示操作为删除第 $p_i$ 个数。
若 $\mathrm{opt}_i=3$，则接下来两个整数 $l_i, r_i$，表示操作为翻转区间 $[l_i, r_i]$。
若 $\mathrm{opt}_i=4$，则接下来两个整数 $l_i, r_i$，表示操作为查询区间 $[l_i, r_i]$ 的和。

**强制在线规则：**
**令当前操作之前的最后一次 $4$ 操作的答案为 $lastans$（如果之前没有 $4$ 操作，则 $lastans=0$）。**
**则此次操作的 $p_i,x_i$ 或 $l_i,r_i$ 均按位异或上 $lastans$ 即可得到真实的 $p_i,x_i$ 或 $l_i,r_i$。**

outputFormat: 对于每个序号为 $4$ 的查询操作，输出一行一个数表示区间的和。

hint:
**强制在线：以下针对 $p_i, x_i, l_i, r_i$ 的限制均是按位异或 $lastans$ 后的限制。**

- 对于 $6$ 个测试点，$n \le 5000$。
- 对于另外 $6$ 个测试点，$v_i = i - 1$。
- 欢迎用户加强数据，可联系管理员或出题人。

对于 $100\%$ 的数据，$1 \le n \le 2 \times {10}^5$，$|x_i| < {10}^6$。

假设基于的历史版本的序列长度为 $len \ge 1$，有：
若 $\mathrm{opt}_i=1$，则 $0 \le p_i \le len$。
若 $\mathrm{opt}_i=2$，则 $1 \le p_i \le len$。
若 $\mathrm{opt}_i=3$，则 $1 \le l_i \le r_i \le len$。
若 $\mathrm{opt}_i=4$，则 $1 \le l_i \le r_i \le len$。

假设基于的历史版本的序列长度为 $0$，有：
$\mathrm{opt}_i=1$，$p_i=0$。


title: Tweetuzki 爱伊图

background:
Tweetuzki 的教练最近常常在群里发有关「伊图科技」的文章。「伊图科技」是一家专注于计算机视觉技术的上海创业公司，其人脸识别技术在世界处于领先地位。2018 年 6 月，在全球工业界黄金标准 FRVT 测试中，依图在千万分之一误报下识别准确率接近 $99\%$，是全球工业界在此项指标下的最好水平，这是依图科技连续第二年摘得此项竞赛的冠军，也是首个夺得此项竞赛冠军的中国团队。2018 年 11 月 16 日，美国国家标准与技术研究院（NIST）公布了全球权威人脸识别比赛（FRVT）最新报告，依图算法继续保持第一，在千万分之一误报下的识别准确率超过 $99\%$，是目前全球人脸识别技术的最好水平。

更重要的是，伊图科技的创始人，是附中的毕业生——Tweetuzki 的学长呢！人脸识别真的好难呢！Tweetuzki 常常幻想，要是自己的程序能有学长们的亿万分之一厉害，那就很好了呢！

description:
Tweetuzki 希望设计出一个程序，这个程序应当能识别输入矩阵中隐藏的数字。

输入的是一个 $r \times c$ 的字符矩阵，矩阵中的元素只有 `. `或 `#`。其中 `#` 可以构成一些数字。输入的矩阵将严格遵守以下规则：

- 除 $1$ 占 $5 \times 1$ 的长方形区域外，其余数字均占 $5 \times 3$ 的长方形区域。

- 相邻两个数字间至少有一列 `.`，即**数字不会贴在一块儿**；且数字**只会左右排放**，不会上下排放。这两点综合起来可以表述为：对于两个数字 $A$ 和 $B$（$A$ 在 $B$ 的左侧），若它们在横向上延伸的区间分别为 $[l_A, r_A]$ 和 $[l_B, r_B]$，那么一定满足 $l_B \ge r_A + 2$。

- 数字的组成严格按照如下所列：

  ```plain
  数字的组成方式：
  #   # # #   # # #   # . #   # # #   # # #   # # #   # # #   # # #   # # #
  #   . . #   . . #   # . #   # . .   # . .   . . #   # . #   # . #   # . #
  #   # # #   # # #   # # #   # # #   # # #   . . #   # # #   # # #   # . #
  #   # . .   . . #   . . #   . . #   # . #   . . #   # . #   . . #   # . #
  #   # # #   # # #   . . #   # # #   # # #   . . #   # # #   # # #   # # #

  所代表的数字：
  1     2       3       4       5       6       7       8       9       0
  ```

  **数字不会倾斜、放大或缩小。**具体可见样例。

- 除构成数字的长方形区域外，其余位置皆由 `.` 填充。保证所有的 `#` 的连通块一定都能够组成数字，且一定满足上述规则。

由于 Tweetuzki 太弱了，于是向你求助，聪明的你，能不能帮助 Tweetuzki 解决这个问题呢？

inputFormat:
第一行两个正整数 $r, c$ $(5 \le r \le 10, 3 \le c \le 10^5)$，表示矩阵的行数和列数。
接下来 $r$ 行，每行输入 $c$ 个字符，用空格隔开，保证只含有 `.` 和 `#` 两种字符。输入矩阵保证合法且一定含有隐藏数字。

outputFormat: 输出仅包含一行一个只含数字的字符串，**按照顺序**输出这个矩阵中隐藏的数字。

hint:
### 样例解释

建议复制进记事本（或各种 IDE）中用等宽字体查看。

###  子任务

**_Subtask_ #1 _(30 points)_**：矩阵中仅有数字 $1$。
**_Subtask_ #2 _(30 points)_**：矩阵中不含有数字 $1$ 和 $4$。
**_Subtask_ #3 _(40 points)_**：无特殊性质。


title: 【模板】插头 DP

background:
ural 1519

陈丹琦《基于连通性状态压缩的动态规划问题》中的例题。

description: 给出 $n\times m$ 的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？

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

从第二行到第 $(n+1)$ 行，每行有一个长度为 $m$ 的只含 `*` 和 `.` 的字符串，`*` 表不能铺线，`.` 表必须铺。

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

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

- 对于 $100\%$ 的数据，保证 $2\le n,m\le 12$。


title: WD与循环

background: WD整日沉浸在循环中，无法自拔……

description:
这天，WD蒟蒻为了解决一个小问题写了个很长很长的for循环：
```cpp
int cnt = 0;
for (int a_1 = 0; a_1 <= m; a_1++) {
    for (int a_2 = 0; a_1 + a_2 <= m; a_2++) {
    ...
        for (int a_n = 0; a_1 + a_2 + ... + a_n <= m; a_n++) {
            cnt = (cnt + 1) % 19491001;
        }
    }
}
printf("%d\n", cnt);
```
CX过来看了一眼，说：**WD你个笨蛋，这道题不是SB题吗？**WD一脸懵逼，只好请你来教教他啦……

inputFormat: 第一行一个数$T$，表示数据组数。接下来每行两个数$n,m$，分别表示循环重数和每层循环的上界。

outputFormat: 共$T$行，每行一个数表示答案。


title: WD与地图

background: WD 整日沉浸在地图中，无法自拔……

description:
CX 让 WD 研究的地图可以看做是 $n$ 个点，$m$ 条边的有向图，由于政府正在尝试优化人民生活，他们会废弃一些无用的道路来把省下的钱用于经济建设。

城市都有各自的发达程度 $s_i$。为了方便管理，政府将整个地图划分为一些地区，两个点 $u,v$ 在一个地区当且仅当 $u,v$ 可以互相到达。政府希望知道一些时刻某个地区的前 $k$ 发达城市的发达程度总和，以此推断建设的情况。

也就是说，共有三个操作：

`1 a b` 表示政府废弃了从 $a$ 连向 $b$ 的边，保证这条边存在。

`2 a b` 表示政府把钱用于建设城市 $a$，使其发达程度增加 $b$。

`3 a b` 表示政府希望知道 $a$ 城市所在地区发达程度前 $b$ 大城市的发达程度之和。如果地区中的城市不足 $b$ 个输出该地区所有城市的发达程度总和。

inputFormat:
第一行两个数 $n,m,q$，表示共 $n$ 个点，$m$ 条边，$q$ 次询问。

第二行 $n$ 个正整数，表示 $s_i$，即每个城市的发达程度。

接下来 $m$ 行每行两个数 $u,v$，表示初始时有一条从 $u$ 连向 $v$ 的边。

接下来 $q$ 行，表示 $q$ 组询问，格式如题目描述。

outputFormat: 对于每个询问操作，输出一个数，表示发达程度之和。


title: xtq的棋盘

background: 自从二年级起，xtq就热爱棋类游戏。

description:
xtq有一个$1$行，$n+1$列的棋盘，从左到右编号为$0$到$n$。初始时刻，在$m$位置有一颗棋子。

xtq会在接下来的时间里随机操作。具体地说，如果某一秒棋子不位于$n$，那么他将有$prb$的概率将棋子向左移动一格，$1-prb$的概率向右移动一格；否则，他必然将棋子向左移动一格。

现在xtq想问你，期望多少秒之后棋子能够到达$0$。由于答案可能很大，并且为了避免不必要的精度误差，你只需要给出答案对于$10^9+7$取模的结果即可（可以证明，答案必然是一个有理数）。

inputFormat:
一行四个正整数$n,m,p,q$。

其中，$p,q$表示$prb = \frac{p}{q}$。

outputFormat: 一行，一个正整数，表示期望移动次数对$10^9+7$取模的结果。

hint:
对于$20\%$的数据，$n\le 4, 1\le p\le q\le 4$而且保证答案在取模前是一个整数。

对于$40\%$的数据，$n\le 300$。

对于$70\%$的数据，$n\le 1000000$。

对于$100\%$的数据，$1\le m\le n\le 10^9, 1\le p\le q\le 10^9$并且$p,q$互质。

此外，在全部的数据点中，有$30\%$的数据是满足$prb = \frac{1}{2}$的。

有理数对质数$p$取模定义如下：

设$\frac{a}{b}$对$p$取模的结果为$x$，那么需要满足$0\le x<p$且$a \equiv bx (mod p)$。

保证对于$100\%$的数据，一定存在满足要求的$x$。


title: xtq的口令

background:
三年级时，xtq就展现出高超的身体素质，以至于体育老师允许他不用参加同学们的体育锻炼，而是可以自由活动。

xtq现在正在观察同学们跑步。

description:
$n$个同学在排队跑步。

体育老师发了一条指令，要求这$n$名同学加快跑步速度。然而，由于风太大，只有部分同学听到并执行了老师的指令。同时，没有听到指令的同学如果观察到其他的同学执行了老师的指令，他们也会执行老师的指令。

现在我们一般化这个情况。我们将位于队首的同学编号为$1$，将接下来的同学以此类推，最后位于队尾的同学编号为$n$。

经过观察，xtq给出了每位同学的若干位观察对象，这意味着当这位同学看到他的任何一个观察对象加快跑步速度（执行指令）时，他也会加快跑步速度（执行指令）。保证对于任何第i位同学，他的所有观察对象的编号都小于自己（一个同学只会观察排在自己前面同学中的一部分）。

现在有$q$条询问或修改，

询问：每次询问给出$L,R$，询问内容如下：如果编号在$[L,R]$区间范围内的同学听到了老师的指令，至少还需要几位同学听到了老师的指令，才能使得所有同学最后都能加快跑步速度。 格式为$1$ $L$ $R$。

修改：每次修改给出$L,R$以及$x$，代表编号在$[L,R]$的同学添加第$x$位同学为自己的观察对象。保证$x<L\le R$。不保证在修改以前$x$同学不是$[L,R]$范围内的任何一位同学的观察对象。但是，当一组$2$ $L$ $R$ $x$的修改完成后，$x$同学一定被$[L,R]$区间内的所有同学观察。格式$2$ $L$ $R$ $x$。

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

接下来n行，每行第一个整数$a_i$，代表第$i$位同学被共计$a_i$位同学观察。接下来$a_i$个整数，代表观察第$i$位同学的编号。若$a_i=0$，代表没有同学观察这位同学。由于一个同学只会被自己后面的同学观察，所以输入的编号第一大于这位同学自己的编号

###### 请注意，输入的编号是 观察第$i$位同学 的同学编号，而不是 被第$i$位同学观察 的同学编号。

接下来$q$行，每行一个询问或修改，格式见题目描述

outputFormat: 对于每个询问操作，输出至少还需要几位同学知道指令，才能使最终每位同学都接执行了老师的指令。


title: 红包发红包

background: 红包（redbag）发明了一个抢红包的系统。

description:
这个抢红包系统是这样的：假如现在有 $w$ 元，那么你抢红包能抢到的钱就是 $[0,w]$ 等概率均匀随机出的一个实数 $x$。

现在红包发了一个 $w$ 元的红包，有 $n$ 个人来抢。那么请问第 $k$ 个人期望抢到多少钱？

输出答案对 $10^9+7$ 取模后的结果。

inputFormat: 一行三个整数，$w,n,k$。

outputFormat:
第 $k$ 个人期望抢到的钱数对 $10^9+7$ 取模后的结果。

补充：期望可能是分数，关于分数取模，可以问度娘。

hint:
注意红包发明的抢红包系统和微信的抢红包系统不一样，红包发明的抢红包系统中的钱不一定是整数分。

- 对于 $30\%$ 的数据，$k=1$
- 另有 $30\%$ 的数据，期望值取模前为整数，$k\le 10$。

对于全部数据，$0< w< (10^9+7)$，$n\le 10^{18},k\le n$。


title: 能量采集

description:
**题面已修改，请大家注意。**

请你求下列式子：$\sum_{i=1}^N\sum_{j=1}^Ngcd(i,j)$ ，答案对大质数取模。

不好意思读错剧本了。

给定一个 $n$ 个点 $m$ 条边的有向图，每个点有初始能量 $a_i$ 。

每过一秒，每个点的能量便会等量地流向所有出边，另外，会有一份流向自己（你可以当做有一个自环）。

现在 $dkw$ 有 $q$ 次询问，每次询问会给你一个时间 $t$ ，$dkw$想知道 $t$ 秒时每个点的能量。

不保证图中没有重边和自环，答案对$998244353$取模。

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

第二行包含$n$个整数，从$a_1$到$a_n$ ，代表初始能量。

接下来 $m$ 行，每行包含两个正整数 $x_i,y_i$ ，代表一条有向边，从 $x_i$ 指向 $y_i$ ，我们约定点编号从 $1$ 到 $n$ 。

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

outputFormat: 为了防止输出过大，对于每个询问你只需要输出一行一个非负整数，代表 $n$ 个点的能量（取模）的异或和对$998244353$取模的结果。


title: 不强制在线的动态快速排序

background: 曦月最近学会了快速排序，但是她很快地想到了，如果要动态地排序，那要怎么办呢？

description:
为了研究这个问题，曦月提出了一个十分简单的问题

曦月希望维护一个允许重复的集合$S$，支持：

* 插入$[L, R]$，也就是插入$L, L + 1 ... , R$，这$R - L + 1$个数

* 询问$Sort(S)$

---

$Sort(S)$的定义为：

我们将集合$S$中的元素**从小到大按照快速排序**排好序，记为$a_1, a_2 ... a_n$

那么，$Sort(S) = \bigoplus \limits_{i = 2}^n (a_i^2 - a_{i - 1}^2)$，其中$\bigoplus$表示异或和

关于异或的定义，请咨询度娘

inputFormat:
第一行，一个数$q$

后$q$行，或者是$1\;l\;r$，表示插入$[l, r]$，或者是$2$，表示一次询问

outputFormat: 对于每个询问，一行一个答案

hint:
对于样例一的解释：

$S$中只有一个数，因此返回$0$

---

对于$30$分的数据，$q \leqslant 100$

对于$50$分的数据，$q \leqslant 5 * 10^4$

对于另外的$20$分的数据，满足$L = R$

对于$100$分的数据，$q \leqslant 3 * 10^5$，$1 \leqslant L \leqslant R \leqslant 10^9$

保证数据有梯度，可能略微地有卡常，请把自己的常数优化到极致


title: 中国象棋

background: $ gjm $  非常喜欢研究棋类问题，最近，他在钻研中国象棋 $QwQ$

description:
现在，$ gjm $ 脑海里有一个 $ N $ × $ N $ 的棋盘，其上共有 $ N $ × $ N $个格子，$ gjm $ 开始在棋盘上的格点上摆放卒，已知卒仅会攻击往左边一个格点和往右边一个格点上的棋子，现在 $ gjm $ 开始在棋盘上摆放任意多个卒，满足：

$(1)$ 每一行都至少摆放有两个卒

$(2)$ 任意两个卒都不会互相攻击

$ gjm $ 现在想知道，满足上述条件，有多少种摆放卒的方案？由于答案可能很大，你只需输出方案数对 $ P $  取模的结果即可。

两种方案被认为不同当且仅当存在同一格点的摆放情况不同。

inputFormat: 一行两个正整数，分别为$ N $ 和 $ P $。

outputFormat: 一行一个整数，即在$ N $ × $ N $ 棋盘中摆放卒的方案数对 $ P $ 取模的结果 。


title: 旅行

background: $jjc$ 非常喜欢旅行~~（smy）~~！

description:
**$NOIP$ $2018$** 已经结束了，$jjc$ 决定去全国各地旅行，每个地方都有许多巨佬，他拥有一张地图来帮助他规划一条从 $A $ 地 到 $B $ 地 的路线，地图上有 $N $ 个地点编号为 $1$~$N$ ，有 $ M $ 条道路将不同(或相同)地点有向连通。

现在，$jjc$ 已经知道了通过第 $ i $ 条路从 $u_i $ 地 直接走到 $v_i $ 地 会遇到多少名巨佬，他将记录遇见的每一名巨佬的名字（不管是否记录过）。但是，每记录一名巨佬的名字就需要使用一张便签，便签以袋为单位出售，$jjc$ 选购的便签每一小袋有 $P$ 张。$jjc$ 不希望他购买的便签被浪费，因此他希望他旅程结束后他购买的每一袋便签都 **恰好** 被用完。除此以外，$jjc$ 正在存钱来$......QwQ$，他得减少消费，因此他希望这次旅行能消耗尽量少的便签。

然而，他不知道怎么才能找到最合适的路径，作为巨佬中的一员，你能帮 $jjc $ 解决这个问题，找到符合条件的最佳路径吗？

inputFormat:
第一行，给出五个整数，依次是$N$、$M$、$P$、起点$A$的编号、终点$B$的编号

从第二行到第$M+1$行描述道路的信息，每行三个整数，依次是第$i$条道路连接的两个地点的起点编号$u_i$、终点编号$v_i$ 及这条道路上会遇见的巨佬数量$num_i$

outputFormat:
若存在满足条件路线，请输出两行，第一行一个整数，表示选择最佳路径上会遇见的巨佬总数，第二行输出从起点$A$到终点$B$的最佳路径的详细路线，数据保证答案是唯一的。

若无满足条件的路线 ，请输出一行一个字符串“$jjc$ $fails$ $in$ $travelling$” $($不含引号$)$


title: 秘密任务

background:
>飞雪连天射白鹿，笑书神侠倚碧鸳。

>谨纪念金庸先生。

 但是这与本题没有联系。

description:
wgr 是 $R$ 国军队总指挥官。现在，他决定组织两个小队分别去执行两个秘密任务。

wgr 将派出 $N$ 名战士来执行这两个任务，他们的编号为 $1 \sim N$ 。由于任务无比重要，wgr 需要使派出的队伍配合绝对默契 。配合绝对默契指队伍中**任何**两名战士的配合都是默契的。同时，他还需要使两个队伍的战斗力差距尽可能小，队伍的战斗力定义为 $F=2^{k}$，$k$ 为队伍的人数，不允许有人剩余。

wgr 已经知道哪些战士之间的配合是默契的，但由于时间紧迫，wgr 来不及慢慢整理资料了，现在，他请你以最快的速度帮他完成资料的整理，并告诉他：

1. 一共有多少种不同的分组方案。两种方案被认为是不同的当且仅当其两支队伍战斗力差值不同。
2. 所有分组方案中，最小的战斗力差值是多少，由于这个差值可能很大，请对  $10^9+7$ 取模后再输出。
3. 有多少对战士配合默契但是不可能被分在同一小组。

**注意：** 特别地，由于队伍的默契程度十分重要，一支队伍 $N$ 名战士另一支队伍 $0$ 名战士也是合法的分组方案。

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

接下来 $M$ 行每行两个正整数 $x,y$，表示编号为 $x$ 的战士与编号为 $y$ 的战士之间配合默契。

outputFormat:
输出共两行。

第一行，如果存在合法的方案，输出一行两个数，为分组方案数与最小的战斗力差值模 $10^9+7$ 的结果；如果不存在合法的分组方案，第一行输出一个数 $-1$ 即可。

第二行，输出一个整数，表示有多少对战士配合默契但是不可能被分在同一小组。

hint:
本题共有三个 Subtask。

- Subtask 1：共 $5$ 个测试点，一个测试点 $5$ 分，满足 $N≤30$；
- Subtask 2：共 $3$ 个测试点，一个测试点 $10$ 分，满足 $N≤300$；
- Subtask 3：共 $3$ 个测试点，一个测试点 $15$ 分，满足 $N≤2500$。

对于所有的数据，不会重复说明同一组关系，$1\le x,y\le  n$ 且 $x\neq y$。此外保证 $0\le m≤n\times (n-1)/2$。

本题开启 Special Judge：

- 若你的答案第一行输出正确你可以得到该测试点 $60\%$ 的分数；
- 若你的答案第二行输出正确你可以得到该测试点 $40\%$ 的分数。

为了确保你能够得到部分分，**请按格式要求输出**。


title: WD与数列

background: WD整日沉浸在数列中，无法自拔……

description:
WD很喜欢数列。他认为两个序列$A,B$是匹配的，当且仅当$|A|=|B|$且对于$1\le i,j\le |A|,A_i-B_i=A_j-B_j$.即长度相同且一个数列同时加上一个数可以和另一个数列完全一样。

现在CX给了他一个长度为$n$的大数列，WD希望知道，数列中有多少对不相交的子串使得他们是匹配的。

inputFormat: 第一行一个数$n$，表示数列长度。第二行$n$个数，表示序列中的数字。

outputFormat: 共一行一个数，为匹配的子串个数。

hint:
对于样例，任意两个不相交且长度相等的子串都是匹配的，长度为1时有10种，长度为2时有3种，因此总共有13种。

$subtask1(11pts):~1\le n\le 100$

$subtask2(34pts):~1\le n\le 1,000$

$subtask3(55pts):~1\le n\le 300,000$

对于所有数据，数列中数字的**绝对值**$\le 10^9$。$subtask3$的时限为3s，其它为1s.


title: 心上秋

background:
辗转经由他人唇齿

多少日夜听闻你的故事

难道这情之一字

竟连抛生死亦不可探知

听说北国的那座城池

被冬雪覆了终日

等到故人长诀渐行渐远

转眼已隔两世

谁向生而死 谁患得患失

相顾也再无多时

画中人暗自 竟心荡神痴

一滴泪氤氲满纸

挥墨描眉目 提笔勾鬓丝

寥寥几笔竟如此

夜半无人处 对月展卷时

忽然看懂这相思

落款谁提了名字

————《心上秋》

description:
竟宁元年（前33年）正月，昭君出塞前一晚。

画师跌跌撞撞地来到昭君居住的宫殿。

     听说北国的那座城池
     被冬雪覆了终日
     等到故人长诀渐行渐远
     转眼已隔两世
                ——《心上秋》

如果再也不能相见的话，画师想着，他想给昭君留下些什么。

他想把他的画笔送给昭君。

**昭君的宫殿里有$N$个房间，有$N-1$条道路连接这些房间。**

**画师现在在宫殿的入口大厅$S$房间，他依稀记得，昭君的房间在$T$号。**

窗外，风雨大作，宫内忽暗忽明，一个人影也没有。

画家走进晦暗的通道，每条通道里的墙壁上都画有若干片枫叶，这是之前昭君让画师画的。昭君说，她特别喜欢秋天，尤其喜欢秋天的枫叶。

      并肩长谈过多少往事，恍然间黄昏已至    ——《心上秋》

通道内晦暗无比，画师想点亮通道内备好的蜡烛，他记得昭君有个习惯，**每个通道内的蜡烛数量就是墙上枫叶的数量。昭君若想点燃一条通道内的蜡烛，就会全部点燃，此时昭君认为这条通道已被点亮，并且不会再点亮任何枫叶数少于这条通道的通道**。

这应该是最后一次来到这个地方了，画师想着，他要按昭君的习惯，走到昭君的房间。

**现在画师想知道，他从宫殿大厅$S$走到昭君房间$T$，最多可以点亮多少通道。**

inputFormat:
第一行一个数$N$，表示宫殿房间数量。

接下来有$N-1$行，每行三个数$u_{i},v_{i},leaf_{i}$，表示$u,v$之间有一条通道，通道上画有$leaf_{i}$片枫叶。

接下来一个数$M$。

最后$M$行，每行两个数$S_{i},T_{i}$

outputFormat: 输出$M$行，对于每组$S_{i},T_{i}$，输出最多能够点亮的通道数。


title: WD与积木

background: WD整日沉浸在积木中，无法自拔……

description:
WD想买 $n$ 块积木，商场中每块积木的高度都是 $1$，俯视图为正方形（边长不一定相同）。由于一些特殊原因，商家会给每个积木随机一个大小并标号，发给 WD。

接下来 WD 会把相同大小的积木放在一层，并把所有层从大到小堆起来。WD 希望知道所有不同的堆法中层数的期望。**两种堆法不同当且仅当某个积木在两种堆法中处于不同的层中，由于WD只关心积木的相对大小，因此所有堆法等概率出现，而不是随机的大小等概率（可以看样例理解）。**
输出结果 $\bmod \space 998244353$ 即可。

（如果还是不能够理解题意，请看样例）

inputFormat:
第一行一个数$T$，表示询问个数。

接下来 $T$ 行每行一个数 $n$，表示 WD 希望使用 $n$ 块积木。

outputFormat: 共 $T$ 行，每行一个数表示答案 $\bmod \space 998244353$。


title: [Ynoi2014] 置身天上之森

background:
![](https://cdn.luogu.com.cn/upload/pic/45593.png)
如果，我是说如果
我再过五天就会死掉的话
你可以再温柔的对待我一点吗？
![](https://cdn.luogu.com.cn/upload/pic/45555.png)
运气真好
牺牲我一个就可以了
怎么样，就是这么一回事
![](https://cdn.luogu.com.cn/upload/pic/45566.png)
你现在愿意答应我最后的愿望吗？
那个...就是...比如说...对了
![](https://cdn.luogu.com.cn/upload/pic/45577.png)
让你吻我之类的
你愿意吗
![](https://cdn.luogu.com.cn/upload/pic/45586.png)
在自己消失之前
心怀不想消失的愿望
希望让某个人记住我
希望能留下羁绊
我这么希望着，又有什么不可以的吗
![](https://cdn.luogu.com.cn/upload/pic/45501.png)

description:
线段树是一种特殊的二叉树，满足以下性质：
每个点和一个区间对应，且有一个整数权值；
根节点对应的区间是 $[1,n]$；
如果一个点对应的区间是 $[l,r]$，且 $l<r$，那么它的左孩子和右孩子分别对应区间 $[l,m]$ 和 $[m+1,r]$，其中 $m=\lfloor\frac{l+r}{2}\rfloor$；
如果一个点对应的区间是 $[l,r]$，且 $l=r$，那么这个点是叶子；
如果一个点不是叶子，那么它的权值等于左孩子和右孩子的权值之和。
珂朵莉需要维护一棵线段树，叶子的权值初始为 $0$，接下来会进行 $m$ 次操作:
操作 $1$：给出 $l,r,a$，对每个 $x$（$l\leq x\leq r$），将 $[x,x]$ 对应的叶子的权值加上 $a$，非叶节点的权值相应变化；
操作 $2$：给出 $l,r,a$，询问有多少个线段树上的点，满足这个点对应的区间被 $[l,r]$ 包含，且权值小于等于 $a$。

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

接下来 $m$ 行，每行包含四个整数 $op,l,r,a$，表示一次操作，其中 $op$ 表示操作类型。

outputFormat: 对每个 $op=2$ 的操作，输出一行，包含一个整数，表示答案

hint:
Idea：zcysky，

Solution：nzhtl1477( $O( m\sqrt{n\log n})$ solution )，ccz181078( $O( m\sqrt{n})$ solution )

Code：nzhtl1477( $O( m\sqrt{n} \log n)$ code )，ccz181078( $O( m\sqrt{n\log n})$ code )，

Data：nzhtl1477

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$1\leq l\leq r\leq n$，$1\leq op\leq 2$，$-10^5\leq a\leq 10^5$。


title: [Ynoi2014] 在太阳西斜的这个世界里

background:
![](https://cdn.luogu.com.cn/upload/pic/45500.png)
现在我的梦想实现了 也留下了美好的回忆
可以说没有任何遗憾了吧
![](https://cdn.luogu.com.cn/upload/pic/45511.png)
今天真是多谢你了
让我体验了许多美好
这全都是托你的福
我留下了如同美梦一般的回忆 不过时间到了
最后我还想拜托你一件事
![](https://cdn.luogu.com.cn/upload/pic/45522.png)
希望你可以把我忘掉

description:
珂朵莉需要维护一棵初始为空的红黑树，进行 $n$ 次操作。

对于重复的整数，我们认为插入时间晚的一个更小。

操作有两类：

* $op=1$：在红黑树上插入一个整数$x$。
* $op=2$：给出 $x$，询问从 $1$ 到 $x$ 的整数中等概率选取一个插入到红黑树上，造成的旋转次数的期望值，方便起见，你只要输出 期望值$\times x$，（可以证明这是一个整数）。

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

接下来 $n$ 行，每行两个由空格分隔的整数 $op,x$，表示一次操作。

outputFormat: 对每个 $op=2$ 的操作，输出一行，包含一个整数，表示答案。

hint:
红黑树是一棵二叉查找树，每个点有颜色（红/黑）。

每次执行插入操作时，新插入的点为红色，操作方式和普通二叉查找树相同。

如果出现两个红色的点互为父子，如图进行调整（操作是左右对称的，对称操作在图中不再重复列出；黑色三角形表示空或以黑色点为根的子树），调整可能需要连续进行多次。

调整完毕后，把根设为黑色。

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

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

$1\leq n\leq 2\times 10^5$，$1\leq op\leq 2$，$1\leq x\leq 10^8$。


title: [Ynoi2014] 等这场战争结束之后

background:
我真的能变强吗？
![](https://cdn.luogu.com.cn/upload/pic/45502.png)
【就算你不愿意，我也会逼你变强】
那么承蒙你的一片美意，我就直说了吧
![](https://cdn.luogu.com.cn/upload/pic/45503.png)
那个嘛...
我才不想变强呢~！
【那这样吧，只要你从战场上活着回来】
【我可以答应你随便一个要求，随便什么都行】
诶？
![](https://cdn.luogu.com.cn/upload/pic/45504.png)
【结婚什么的当然免谈啦】
你说什么都行的...
![](https://cdn.luogu.com.cn/upload/pic/45505.png)
点心...
你之前不是在食堂做了点心吗
那么黄油蛋糕你会做吗
![](https://cdn.luogu.com.cn/upload/pic/45506.png)
我的姐姐...也就是前辈们当中
有一个人每次从战场上活着回来之后
都会一脸陶醉地品尝黄油蛋糕
所以...拜托你了
【偏偏挑这个...】
【没问题，我会让你吃到吐的】
【所以，你一定要活着回来】

description:
给你一个图，每个点有点权，最开始没有边。

有一些操作：

1. 添加一条 $x$ 与 $y$ 之间的双向边。
2. 回到第 $x$ 次操作后的状态（注意这里的 $x$ 可以是 $0$，即回到初始状态）。
3. 查询 $x$ 所在联通块能到的点中点权第 $y$ 小的值，如果不存在，那么输出 $-1$。

inputFormat:
第一行输入两个整数 $n,m$，表示有 $n$ 个点，$m$ 个操作。

之后一行 $n$ 个数，表示每个点的点权。

之后 $m$ 行，每行有三种可能的操作：

`1 x y`

`2 x`

`3 x y`

意义见题面。

outputFormat: 对所有 $3$ 的操作，输出一行，包含一个整数，表示答案。

hint:
Idea：nzhtl1477，

Solution：nzhtl1477( $O( nm/w )$ Time , $O( n\log n )$ Space )，ccz181078( $O( m\sqrt{n\log n} )$ Time ，$O(n\sqrt{n\log n} )$ Space ) ，shadowice1984( $O( m\sqrt{n\log n} )$ Time , $O( n\log n )$ Space ) , zx2003( $O( m\sqrt{n} )$ Time ，$O( n )$ Space )

Code：nzhtl1477( $O( nm/w )$ Time , $O( n\log n )$ Space )，ccz181078( $O( m\sqrt{n\log n} )$ Time , $O( n\sqrt{n\log n} )$ Space ) ，shadowice1984( $O( m\sqrt{n\log n} )$ Time ，$O( n\log n )$ Space )，zx2003( $O( m\sqrt{n} )$ Time ，$O( n )$ Space )

Data：nzhtl1477( partially uploaded )

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


title: [Ynoi2014] 不归之人与望眼欲穿的人们

background:
【第一船队发来联络了】
【是关于第15号悬浮岛的战斗结果】
【15号悬浮岛的保卫作战...】
【失败了...】
![](https://cdn.luogu.com.cn/upload/pic/45508.png)
![](https://cdn.luogu.com.cn/upload/pic/45509.png)
![](https://cdn.luogu.com.cn/upload/pic/45510.png)
![](https://cdn.luogu.com.cn/upload/pic/45512.png)
![](https://cdn.luogu.com.cn/upload/pic/45513.png)
![](https://cdn.luogu.com.cn/upload/pic/45514.png)

description: 珂朵莉给了你一个序列，支持单点修改，或者询问满足区间 or 和**大于等于**一个数的区间的最短可能长度，无解输出 $-1$。

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

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

接下来 $m$ 行，形如：

* $1\ i\ x$ 表示将 $a_i$ 修改为 $x$。
* $2\ k$ 表示询问最短的一个长度，满足存在一个该长度的区间，其 or 和 $\geq k$。

outputFormat: 对所有 $2$ 操作，输出一行，包含一个整数，表示答案，无解输出 $-1$。

hint:
Idea：kczno1，

Solution：kczno1( $O( m\sqrt n\log a )$ solution )，liu_cheng_ao($O( m\log^2 n\log^2 a$ ) solution )，142857cs($O( m\log n\log^2 a$ ) solution )

Code：kczno1( $O( m\sqrt n\log a )$ code )，liu_cheng_ao($O( m\log^2 n\log^2a$ ) code )

，Data：kczno1

对于 $100\%$ 的数据，$0\leq a_i,k\leq 2^{30}$，$1\leq n,m\leq 5\times 10^4$。


title: [Ynoi2014] 人人本着正义之名

background:
那是什么？
【不是第六兽，是新的兽？】
【我从来没见过那种玩意啊】
![](https://cdn.luogu.com.cn/upload/pic/45515.png)
【全员退避】
【现已确认出现预料之外的兽】
【根据这一事态，将作战确认为失败，放弃15号岛】
怎么会...
![](https://cdn.luogu.com.cn/upload/pic/45516.png)
我和他约好了的
绝对要活着回去
![](https://cdn.luogu.com.cn/upload/pic/45517.png)
对他说“我回来了”，然后品尝黄油蛋糕
所以，要是世界终结的话我会很伤脑筋的
![](https://cdn.luogu.com.cn/upload/pic/45518.png)
融没于晨雾之中的树林
啊...？
![](https://cdn.luogu.com.cn/upload/pic/45519.png)
【牛奶迹.耀眼花瓣.狂风气团】
【挂于墙上的鲱鱼.倒立的刺猬.袋中的风琴】
这是什么...？
![](https://cdn.luogu.com.cn/upload/pic/45520.png)
你其实...很想战斗的对吧
虽然我不知道你有什么打算，但是已经够了
![](https://cdn.luogu.com.cn/upload/pic/45521.png)
你已经不用战斗了
因为你的战斗，已经由我，由我们继承下来了
【其实我很感激你】
【一直以来，我心里就只想着死】
![](https://cdn.luogu.com.cn/upload/pic/45523.png)
【渴望去往那些等着我回去的家伙身边，这是我唯一的愿望】
【但是遇见你们之后，我有了一些改变】
【我又开始渴望获得一个容身之处了】
【遇见你之后，我得到了一些救赎】
【能够等到你平安归来，我现在...】
【嗯，可以说，感受到了一丝幸福】
啊...？
![](https://cdn.luogu.com.cn/upload/pic/45524.png)
【不...等一下，你别这么露骨地和我拉开距离啊】
【也别露出一副“这个不知廉耻的生物是怎样”的表情啊】
【不过话说回来，你观察我观察地很仔细啊】
哈哈...
因为喜欢上了嘛~
![](https://cdn.luogu.com.cn/upload/pic/45525.png)
![](https://cdn.luogu.com.cn/upload/pic/45526.png)
【由不得我啊】
你要去的话我会生气的，我会大发雷霆的
【珂朵莉...】
![](https://cdn.luogu.com.cn/upload/pic/45527.png)
【对不起】
![](https://cdn.luogu.com.cn/upload/pic/45528.png)
我等你
![](https://cdn.luogu.com.cn/upload/pic/45529.png)
我会等着你的，所以一定要回来哦
![](https://cdn.luogu.com.cn/upload/pic/45530.png)
【我保证，一定会回来的】
嗯
说好了哦~
![](https://cdn.luogu.com.cn/upload/pic/45531.png)

description:
你需要帮珂朵莉维护一个长为 $n$ 的 `01`序列 $a$，有 $m$ 个操作：
- `1 l r`：把区间 $[l,r]$ 的数变成 $0$。
- `2 l r`：把区间 $[l,r]$ 的数变成 $1$。
- `3 l r`：$[l,r-1]$ 内所有数 $a_i$，变为 $a_i$ 与 $a_{i+1}$ 按位或的值，这些数同时进行这个操作。
- `4 l r`：$[l+1,r]$ 内所有数 $a_i$，变为 $a_i$ 与 $a_{i-1}$ 按位或的值，这些数同时进行这个操作。
- `5 l r`：$[l,r-1]$ 内所有数 $a_i$，变为 $a_i$ 与 $a_{i+1}$ 按位与的值，这些数同时进行这个操作。
- `6 l r`：$[l+1,r]$ 内所有数 $a_i$，变为 $a_i$ 与 $a_{i-1}$ 按位与的值，这些数同时进行这个操作。
- `7 l r`：查询区间 $[l,r]$ 的和。

本题强制在线，每次的 $l,r$ 需要与上次答案做 $\operatorname{xor}$ 运算，如果之前没有询问，则上次答案为 $0$。

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

第二行 $n$ 个整数表示序列 $a$。

之后 $m$ 行，每行三个整数 $opt,l,r$，表示是哪一种操作以及操作对应的区间。

outputFormat: 对于每个查询操作输出一行一个数表示答案。


title: [Ynoi2014] 长存不灭的过去、逐渐消逝的未来

background:
![](https://cdn.luogu.com.cn/upload/pic/45532.png)
【她遵守了约定哦...】
【从不可能存活的战场上】
【一心想着要见到技官...想要向技官撒娇...】
【才保留下了一点点寿命...平安回来了哦...】
没错...她遵守了约定...
可我却什么都没能和她说
什么都没能为她做
什么都...
![](https://cdn.luogu.com.cn/upload/pic/45534.png)
......
珂朵莉......
![](https://cdn.luogu.com.cn/upload/pic/45535.png)
以前我碰上他人的悲剧或是不幸这种无可奈何的事情时
总是设法想去改变什么
但是我的力量一直过于渺小...
![](https://cdn.luogu.com.cn/upload/pic/45536.png)
到最后什么忙都没帮上...
我应该已经有深切体会了才对...
我想让珂朵莉幸福...
真受不了那个家伙...
像我这样的男人，到底有什么地方能让她看上啊...
![](https://cdn.luogu.com.cn/upload/pic/45537.png)
【你连这点事情都想不明白吗？】
【因为你...是让我见识了许许多都第一次的人...】
【在露天摊贩街上，是你第一次救了我】
【是你第一次带我去视野开阔的地方眺望风景】
【是你让我第一次产生了各种各样的感情】
【你是第一个让我依赖的人，也是第一个将我击败的对手】
![](https://cdn.luogu.com.cn/upload/pic/45538.png)
【啊...真要数起来根本数不完...】
【所以，我第一个喜欢上的人是你，是理所当然的事情】
![](https://cdn.luogu.com.cn/upload/pic/45539.png)
【这点小事你好歹得察觉到啊，笨~蛋】
【我...究竟是怎么了？】
【我记得我回到仓库，做了奇怪的梦】
![](https://cdn.luogu.com.cn/upload/pic/45540.png)
【你久久不回来...】
【你怎么了，露出这种表情？】
欢迎回来...珂朵莉
![](https://cdn.luogu.com.cn/upload/pic/45541.png)
欢迎回来...
![](https://cdn.luogu.com.cn/upload/pic/45542.png)

description:
珂朵莉定义项为指若干个（$\ge1$）数字（$0\cdots 9$）相连得到的字符串（如 `123` `000` 是合法的项，`** *-1 +5` 是不合法的项）。一个合法的表达式可以为一个项（如 `233`）、两个表达式以 `+ -*` 相连（如`2*3+5*5` `6-6*6`）、一个表达式在左右添一对括号（如 (`2*3*3`)）。

注意：空串不是一个合法的表达式。

在一开始，你会得到一个长为 $n$ 的字符串，之后会给定 $m$ 个操作。 有两种操作：

`1 x y` 表示将位置 $x$ 的字符改成 $y$。

`2 l r` 表示询问 $[l,r]$ 的字符串作为表达式求值在$\bmod {10^9+7}$ 意义下的结果。若该串不是一个合法的表达式，结果为 $-1$。

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

第二行有一个长为 $n$ 的字符串。

接下来 $m$ 行，每行为 `1 x y` 或 `2 l r`，分别表示两种操作。

outputFormat: 对所有 $2$ 的操作，输出一行，包含一个整数，表示答案。

hint:
Idea：mcfx，Solution：mcfx，Code：mcfx，Data：mcfx

$1\leq n,m \leq 10^5$，$1 \leq l\leq r\leq n$，$1\leq x\leq n$。

字符集为 `0 1 2 3 4 5 6 7 8 9 + - * ( )`

若将 `(` 作为 $1$，`)` 作为 $-1$，其他字符作为 $0$，则保证在任意时刻，该串的任意前缀和的绝对值不超过 $50$。


title: 我是仙人掌

background:
我遵守了...
约...约定
![](https://cdn.luogu.com.cn/upload/pic/45543.png)
【你非常努力啊】
我非常非常努力哦...
![](https://cdn.luogu.com.cn/upload/pic/45545.png)
【虽然昨天也说过这句话了...】
【欢迎回来，珂朵莉】
![](https://cdn.luogu.com.cn/upload/pic/45546.png)
我回来了...
终于说出口了...
【是啊，我终于听见了】
红色的头发，会不会奇怪？
【很漂亮的颜色，和你很搭哦】
是吗...
我...我已经没事了
【真的吗？身体状况没问题吗？】
【要是硬撑的话，我可不会饶过你啊】
没事的，做饭啊洗衣服啊，还留着很多活要干呢
【可别太拼了哦】
![](https://cdn.luogu.com.cn/upload/pic/45547.png)
哼，你就做好心理准备等着吧
![](https://cdn.luogu.com.cn/upload/pic/45548.png)

description:
珂朵莉给你一个无向图，每次查询的时候给一堆二元组 $(x_i,y_i)$。

求图中有多少个点 $u$ 与至少一个这次询问给出的二元组 $(x_i,y_i)$ 满足
 $\mathrm{dist}(u,x_i)\leq y_i$，$\mathrm{dist}$ 表示这两个点在图中的距离。

如果不连通 $\mathrm{dist} = +\infty$。

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

$n$ 表示顶点个数，$m$ 表示边数。

之后 $m$ 行每行两个整数 $x,y$ 表示这两个点之间连有一条边~，边权都为 $1$。

之后 $q$ 次询问，每个询问先给你一个整数 $a$。

之后 $a$ 行每行两个整数，$x,y$ ，表示一个二元组。

outputFormat: $q$ 行，每行一个数表示这次询问的答案。

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

$1\leq n\leq 1000$，$1\leq m,q \leq 10^5$，$\sum a\leq2.1\times 10^6$。


title: [Ynoi2015] 纵使日薄西山

background:
【你好像很开心嘛】
因为很少有机会和你单独出来走动嘛
应该说，好像以前一直没有吧？
【我们第一次见面的时候，不就一起逛过很多地方吗？】
![](https://cdn.luogu.com.cn/upload/pic/45549.png)
诶？啊...对
但是那个...总觉得和现在的感觉不太一样嘛
好吧，快点走吧！
【珂朵莉...】
![](https://cdn.luogu.com.cn/upload/pic/45550.png)
![](https://cdn.luogu.com.cn/upload/pic/45551.png)
真是的，别发出那种像是快哭的声音啦，你是大人吧
我没事，你看
诶...
啊，这...这孩子也没事
![](https://cdn.luogu.com.cn/upload/pic/45552.png)
【要是出现什么意外，我...】
【我还以为自己又会在这么近的地方失去你...】
![](https://cdn.luogu.com.cn/upload/pic/45553.png)
![](https://cdn.luogu.com.cn/upload/pic/45554.png)
红色头发的少女
在
看着这里

description:
珂朵莉想让你维护一个长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$，支持修改序列中某个位置的值。

每次修改后问对序列重复进行以下操作，需要进行几次操作才能使序列变为全 $0$（询问后序列和询问前相同，不会变为全 $0$）：

选出序列中最大值的出现位置，若有多个最大值则选位置标号最小的一个，设位置为 $x$，则将 $a_{x-1},a_x,a_{x+1}$ 的值减 $1$，如果序列中存在小于 $0$ 的数，则把对应的数改为 $0$。

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

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

接下来一行一个整数 $q$。

接下来 $q$ 行，每行两个用空格分隔的整数 $x_i,y_i$，表示把 $a_{x_i}$ 修改为 $y_i$。

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

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

$1\leq n,q\leq 10^5$，$1\leq x_i\leq n$，$1\leq a_i,y_i\leq 10^9$。


title: [Ynoi2015] 即便看不到未来

background:
![](https://cdn.luogu.com.cn/upload/pic/45556.png)
我不会再闷闷不乐了
那撕裂胸口的悲伤
还有快流下来的眼泪
全都是塑造出现在的我的东西
![](https://cdn.luogu.com.cn/upload/pic/45557.png)
烦恼
灰心
痛苦
喜悦
全部不可或缺
现在站在这里的不是别人
![](https://cdn.luogu.com.cn/upload/pic/45558.png)
毫无疑问是我自己，是珂朵莉
对，至少现在如此
![](https://cdn.luogu.com.cn/upload/pic/45559.png)
记忆慢慢地缺失
人格在逐渐崩坏
抱歉
你们当中
已经有一半的人我不记得了...
忘记的名字还可以重新记住
但是失去的记忆却无可挽回
这个将要崩坏的自己，还能被称作珂朵莉吗...？
![](https://cdn.luogu.com.cn/upload/pic/45560.png)
可即便这样的感情，我也想要毫无保留地去珍惜
因为如果连这种感情都失去的时候
我大概就会...彻底消失吧

description:
珂朵莉给了你一个序列，每次查询一段区间中长度为 $1,2,\ldots,10$ 的极长值域连续段个数。
定义值域连续段为：

* 把区间里面所有数排序后去重，设排序后得到的序列为 $b$。
* 如果对于二元组 $(l,r)$ 满足 $b_l,b_{l+1},\ldots,b_r$ 中每个数为前一个数 $+1$。
* 而且对于二元组 $(l,r+1)$，$(l-1,r)$ 均不满足，我们称 $(l,r)$ 为一个长度为 $r-l+1$ 的极长值域连续段。

inputFormat:
第一行两个整数 $n,m$，表示序列的长度和查询的次数。

之后一行 $n$ 个整数表示这个序列。

之后 $m$ 行每行两个整数 $l,r$ 表示查询的区间。

outputFormat: 对于每次询问，输出一个长度为 $10$ 的字符串，第 $i$ 个字符表示长度为 $i$ 的极长连续段个数 $\bmod 10$的结果。

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

对于 $100\%$ 的数据，$1\leq n,m,a_i\leq10^6$，$1\leq l\leq r\leq n$。


title: [Ynoi2015] 此时此刻的光辉

background:
难道说...
这么说来...给珂朵莉她们...
正给珂朵莉带来痛苦的是...
![](https://cdn.luogu.com.cn/upload/pic/45561.png)
【威廉？】
【威廉，说真的，你到底怎么了？】
【出什么事了？】
【啊...】
![](https://cdn.luogu.com.cn/upload/pic/45562.png)
你不慌张吗
【别看我这样，其实我心脏确实有在猛跳】
【但是呢，虽然我不知道发生了什么事】
![](https://cdn.luogu.com.cn/upload/pic/45563.png)
【可一直爱逞强的你，难得会对我露出软弱的一面嘛~】
【高兴的心情，还有希望你打起精神的心情加在一起】
【要远远胜过惊慌的情绪】
![](https://cdn.luogu.com.cn/upload/pic/45564.png)
你...
【你刚才，流露着一副要是没人管你就会自己消失的表情哦？】
【虽然非常难为情，但我实在不能撇下你】
![](https://cdn.luogu.com.cn/upload/pic/45565.png)
你是个...好女人啊...
![](https://cdn.luogu.com.cn/upload/pic/45567.png)
【抱歉，我没有听清楚，再说一遍】
没什么啦...
![](https://cdn.luogu.com.cn/upload/pic/45568.png)
【啊...你还死撑】
【再说一遍，再说一遍就好】
和我结婚吧
![](https://cdn.luogu.com.cn/upload/pic/45569.png)
【不对...嗯？】
我终于找到了
找到了渴望去保护的人
找到了渴望回去的归宿
觉得自己还可以继续生存下去
总算真切地认识到自己还有继续生存的价值和资格
所以...
我要给你幸福
![](https://cdn.luogu.com.cn/upload/pic/45570.png)
【嗯】
【我也不会离开你身边的】
【永远，永远和你在一起哦】

description: 珂朵莉给你了一个长为 $n$ 的序列，有 $m$ 次查询，每次查询一段区间的乘积的约数个数 $\bmod 19260817$ 的值。

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

第二行 $n$ 个整数表示这个序列 $a_i$。

之后 $m$ 行，每行两个整数 $l,r$ 表示查询的区间

outputFormat: $m$ 行，每行输出一个整数表示答案

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

$1\leq n,m\leq 10^5$，$1 \leq a_i \leq10^9$。


title: [Ynoi2015] 盼君勿忘

background:
说起来，幸福本身就是因人而异的
有些人认为只要能混口饭吃就行了
有些人只要有书读就能满足
![](https://cdn.luogu.com.cn/upload/pic/45571.png)
有些人认为只有全力地生存才是最重要的
有些人只要得到克服某种目标的瞬间就能满足
有些人只要某个人得到幸福，自己就会跟着幸福
也有些人则令人伤透脑筋地刚好相反
![](https://cdn.luogu.com.cn/upload/pic/45572.png)
但是，大部分人都没有自觉
他们不知道究竟什么能给自己带来幸福
但是，他们会异口同声地表示想要获得幸福
那样的人即使能察觉到幸福
也没办法变得幸福
最重要的是要敢于正视自己的内心
![](https://cdn.luogu.com.cn/upload/pic/45573.png)
【珂朵莉已经基本上不剩什么了】
![](https://cdn.luogu.com.cn/upload/pic/45574.png)
【心灵和身体，珂朵莉基本上快要全部失去了】
![](https://cdn.luogu.com.cn/upload/pic/45575.png)
【全部被我替换了】
![](https://cdn.luogu.com.cn/upload/pic/45576.png)
【幸好你在失去一切之前，回到了这里】
【喜悦和悲伤】
【还有喜欢某个人的情绪】
【现在依旧还残存着一些吧？】
嗯...
确实还有那么一丝...
【那就没问题了】
【珂朵莉你，依旧是珂朵莉】
![](https://cdn.luogu.com.cn/upload/pic/45578.png)
![](https://cdn.luogu.com.cn/upload/pic/45579.png)
威...廉...？
![](https://cdn.luogu.com.cn/upload/pic/45580.png)

description: 珂朵莉给了你一个序列，每次查询一个区间 $[l,r]$ 中所有子序列分别去重后的和 $\bmod\ p$。

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

第二行 $n$ 个整数表示这个序列。

之后 $m$ 行，每行三个整数 $l,r,p$ 表示查询的区间与模数。

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

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

对于 $100\%$ 的数据，$1\leq n,m,a_i \leq 10^5$，$1\leq p\leq 10^9$，$1\leq l\leq r\leq n$。


title: [Ynoi2015] 世上最幸福的女孩

description:
我有一个请求
最后的请求
我感觉自己好像跟他有过约定
说好了那个人以后不必再战斗
说好了那个人的战斗全部由我来继承
而且我还有话想对他说，所以拜托你了
![](https://cdn.luogu.com.cn/upload/pic/45581.png)
【无论如何都要？】
嗯，无论如何都要
【但是，如果再来一次，珂朵莉就会彻底消失了哦？】
【不光是回忆，包括那所有珍贵的情感】
【全都会彻底消失的哦！？】
那还挺让人受不了的呢
但是呢，比起消失，我更加讨厌就这么结束啊
【珂朵莉...】
所以，拜托你了
让我再一次，回到那个地方吧
![](https://cdn.luogu.com.cn/upload/pic/45582.png)
“珂朵莉，加油”
![](https://cdn.luogu.com.cn/upload/pic/45583.png)
![](https://cdn.luogu.com.cn/upload/pic/45584.png)
![](https://cdn.luogu.com.cn/upload/pic/45585.png)
威廉…
谢谢你…

inputFormat:
在最后的最后，珂朵莉给了你一个长为 $n$ 的序列，有 $m$ 个操作：

1. 全局加（即序列的所有数加）。
2. 查询区间最大子段和。

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

第二行 $n$ 个数表示这个序列。

之后 $m$ 行，每行一个操作。

* $1\ x$ : 所有数都加上 $x$。
* $2\ l\ r$ : 查询区间 $[l,r]$ 内的最大子段和（可以不选数，此时最大子段和是 $0$）。

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

$1\leq n \leq 3\times 10^5$，$1 \leq m \leq 6\times 10^5$，序列中的数绝对值 $\leq 2\times 10^9$，$1$ 操作中的 $x$ 的绝对值 $\leq 5\times 10^7$。