title: 琪露诺的冰雪小屋

background: 琪露诺有一片正方形的雪地，她想在上面盖一栋小冰屋。

description:
琪露诺偶然间得到了一片 $N\times N$ 大小的正方形的雪地，她想在上面盖一栋冰雪小屋。

但调皮的⑨才不会认真地收集冰块呢，她要在这片土地上使用冰雪弹幕来制造冰砖，然后一块一块地搭起一个房子。

琪露诺制造冰砖的方式是这样的：她会站在某个方格上，然后向上，下，左，右，左上，左下，右上，右下这八个方向之一发射强力的冰雪弹幕，弹幕能影响到该方向一条直线上一定的距离以内的所有方格。

地面的每个方格都有一个冷冻度，初始为 $0$。被冰雪弹幕影响一次，冷冻度 $+1$，冷冻度的上限为 $4$。

在发射弹幕的间隙中，琪露诺会来到所有冷冻度为 $4$ 的格子，把那里的雪堆到一起，制作一个冰砖（大小为 $1\times1\times1$ 方格），并且将冷冻度重新归零。

琪露诺会拿着这些冰砖来盖房子。这个房子的长度、宽度和坐落位置她在一开始就已经规划好了，但她并不愿意提早确定房子的高度。

琪露诺是这样计划的：这个房子外观上看起来是一个长方体。

她会先盖起这个房子的四面墙（厚度为 $1$ 个方格），并在贴近地面的位置（废话）留一个宽度和高度分别为 $1$ 和 $2$ 的空位不放冰砖，作为房门。（显然，门无法开在墙的拐角处，但可以紧贴拐角）。

在她喜欢的时候，她会结束四面墙的建造，并一次性在墙顶部盖上一个厚度为 $1$ 方格的屋顶，使房子成为一个空心有顶的长方体。

计划已经非常充分了，但琪露诺还是不放心，所以她想请你帮她写一个程序，来随时提醒着她别出什么差错。这个程序需要具备的功能将在下文详细介绍。

----------------------
雪地由 $N$ 行 $N$ 列，$N\times N$ 个方格组成。（下标从 $0$ 开始，也就是说，存在第 $0$ 行第 $0$ 列，但不存在第 $N$ 行第 $N$ 列）每个方格都有一个冷冻度,范围 $[0,4]$，初始为 $0$。注意，空间是三维的，而冷冻度只是地面的属性。

琪露诺想将房子的左上角放在第 $H_R$行，$H_C$ 列（外墙也是房子的一部分，因此左上角位置不应该是房子的内部,而是外墙,并且是墙的拐角）。

这个房子的长度（平行于每列）是 $H_X$，宽度（平行于每行）是 $H_Y$，包含墙。保证房子所占空间不会超出雪地的范围。

除了最后搭建屋顶，琪露诺只会在高度 $[0,H_M-1]$ 放置冰砖。

一开始，琪露诺一个冰砖也没有。
在以下的介绍中，我们用俯视图来作示意：
```plain
0000
0000
4x90
0x01
```
数字代表当前该格子的冷冻度。如果位置紧贴地面（高度为 $0$）的地方放上了冰砖，那么用字母 $x$ 表示。

如果紧贴地面的位置没有冰砖，但是位置正上方的高空存在冰砖，那么仍然用数字表示地面的冷冻度，但这个数字会增加 $5$。即如果在示意图中看到了一个数字 $t\ge5$，表示该位置地面是空的，但高处有冰砖，且地面的冷冻度为 $t-5$。

第一个操作：`ICE_BARRAGE R C D S`
---------------
表示琪露诺站在第 $R$ 行 $C$ 列的位置，朝着方向 $D$ 发射了一个强度为 $S$ 的弹幕。
$R,C,D,S\in\mathbf{Z},0\le D\le7,0\le R,C,S<N$。
方向编号 $0$ 表示上 $(R-1,C)$，$1$ 表示左上 $(R-1,C-1)$，
$2$ 表示左 $(R,C-1)$，$3$ 表示左下 $(R+1,C-1)$，
$4$ 表示下 $(R+1,C)$，$5$ 表示右下 $(R+1,C+1)$，
$6$ 表示右 $(R,C+1)$，$7$ 表示右上 $(R-1,C+1)$。
强度为 $S$ 的弹幕，可以使“处在发射方向直线上，距离琪露诺不超过 $S$ 格的所有格子（包括她站的格子）”的冷冻度都 $+1$。有以下几种特殊情况：

1. 如果某个格子冷冻度为 $4$，那么该格子冷冻度不变。
2. 如果弹幕所经路途上，有一个位置的地面上（高度为 $0$）已经放了冰砖（就是弹幕撞上了琪露诺已经盖了一半的房子），那么弹幕将被阻挡，无法影响到冰砖所在的格子以及冰砖后面被挡住的格子。
3. 弹幕超出雪地的部分忽略不计。

对于这个操作，需要如下输出一行：`CIRNO FREEZED k BLOCK(S)`
如果这个弹幕将某个方格的冷冻度成功增加了 $1$，那么认为这个弹幕冻住了该方格。

`k` 表示这个弹幕总共冻住了多少方格。

如图：发射弹幕前地图如下：
```plain
00000
00000
00000
000x0
00000
```
执行操作 `ICE_BARRAGE 1 1 5 4`，地图变为：
```plain
00000
01000
00100
000x0
00000
```
输出：`CIRNO FREEZED 2 BLOCK(S)`
解释：琪露诺站在第一行第一列，面对右下角发射了一个强度为 $4$ 的弹幕，但弹幕被 `x` 所阻挡，只能影响到 `x` 之前的格子。

第二个操作：`MAKE_ICE_BLOCK`
-------------------------
琪露诺走遍地图上所有冷冻度为 $4$ 的方格，每个方格可以收集一个冰砖，然后将它们的冷冻度归零。

对于这个操作，你需要给出如下输出一行：`CIRNO MADE x ICE BLOCK(S),NOW SHE HAS y ICE BLOCK(S)`
表示琪露诺制造了 $x$ 个冰砖，目前她有 $y$ 个冰砖。
比如琪露诺一开始有 $0$ 个冰砖，并且状态如下：
```plain
0xxx
0x4x
0x9x
0400
```
执行操作 `MAKE_ICE_BLOCK` 后变为
```plain
0xxx
0x0x
0x5x
0000
```
输出：`CIRNO MADE 3 ICE BLOCK(S),NOW SHE HAS 3 ICE BLOCK(S)`
在这个示例中，房子已经完成了一部分，`x` 表示墙，`9` 这个位置地面没有冰砖，但高处有（可以猜出是门）。房间内唯一一块空地、门的位置，以及房间外的一个位置的冷冻度都达到了 $4$，因此可以收集到 $3$ 块冰砖，收集后将三个位置冷冻度都归零。

第三个操作：`PUT_ICE_BLOCK R C H`
-----------------
表示在第 $R$ 行，第 $C$ 列，高度为 $H$ 的地方放一个冰砖。$0\le R,C<N,0\le H<H_M$。

贴近地面的位置高度为 $0$。如果冰砖放置成功，那么琪露诺库存的冰砖数量将减 $1$。

如果放置的位置贴近地面，该位置冷冻度立即归 $0$。

有以下几种情况，序号越小优先级越高，并且只能满足一种情况。

如果满足 $1$ 的话就忽视后面的，不满足 $1$ 的前提下才可能满足 $2\cdots\cdots$ 以此类推。

1. 琪露诺目前没有任何冰砖，无法放置。这种情况下你需要输出：`CIRNO HAS NO ICE_BLOCK`
2. 冰砖将放在半空中，无法依附其他任何冰砖，或者目标位置已有冰砖了。
这种情况下你需要输出一行：`BAKA CIRNO,CAN'T PUT HERE`，并无视此次操作，不做任何工作。
3. 冰砖放在了规划建造房子的区域之外，即
$R<H_R$ 或 $R>H_R+H_x-1$
或 $C<H_C$ 或 $C>H_C+H_Y-1$。请输出一行：`CIRNO MISSED THE PLACE`
尽管琪露诺放错了地方，但你并不能阻止她放置这个冰砖。
4. 冰砖留在了房子的内部，本应留空的地方被占用了，即
$H_R+1\le R\le H_R+H_X-2$ 且 $H_C+1\le C\le H_C+H_Y-2$
在屋顶的高度固定下来前，我们将所有满足上式的情况都认为是放在了房屋内部。
请输出一行：`CIRNO PUT AN ICE_BLOCK INSIDE THE HOUSE`
尽管琪露诺放错了地方，但你并不能阻止她放置这个冰砖。
5. 冰砖放在了正确的位置（不必考虑是否堵住了留给门的地方）
请输出一行：`CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS x ICE_BLOCK(S)`
`x` 表示放过这块冰砖后琪露诺剩余的冰砖。

第四个操作：`REMOVE_ICE_BLOCK R C H`
---------
表示取走第 $R$ 行，第 $C$ 列，高度为 $H$ 处的冰砖。
有以下几种情况，序号越小优先级越高，并且只能满足一种情况。

如果满足 $1$ 的话就忽视后面的，不满足 $1$ 的前提下才可能满足 $2\cdots\cdots$ 以此类推。

1. 目标位置没有冰砖，输出一行：`BAKA CIRNO,THERE IS NO ICE_BLOCK`
2. 目标位置有冰砖，并且在这个冰砖被移走后，至少有一个冰砖形成了一个悬空的块。
如下面的“侧视图”，`x` 表示冰砖，`0` 表示空位。
```plain
xxxx
x000
x000
x000
```
$\ \ $在移走左上角的冰砖后，第一行右边三个冰砖没有了依靠，形成了一个悬空的连通块，就属于这种情况。
$\ \ $这个冰砖将成功移走，琪露诺的冰砖库存将会 $+1$。并且所有的悬空连通块都会掉下来摔碎并消失
$\ \ $（既不会进入冰砖库存，也不会在地面上留有任何痕迹）。
$\ \ $输出一行：`CIRNO REMOVED AN ICE_BLOCK,AND k BLOCK(S) ARE BROKEN`，`k` 表示摔碎的冰砖数量。
3. 琪露诺挪走了冰砖，并且其他冰砖不受任何影响。
$\ \ \ $琪露诺的冰砖库存 $+1$，输出一行：`CIRNO REMOVED AN ICE_BLOCK`

第五个操作：`MAKE_ROOF`
--------
这个操作只会出现一次，并且只会作为最后一个操作。
这个操作表明琪露诺已经完成了冰雪小屋的四墙，只剩屋顶了！

一般情况下，琪露诺将放置最后的 $H_X\times H_Y$ 个冰砖，把它们放置在墙壁最高的高度 $+1$ 的那一层，
形成一个屋顶。然后她移除所有多余的冰砖，接下来补好所有残缺的墙壁。

你需要按顺序来执行整个过程，一旦遇到某种用 $\bullet$ 标识的特殊情况，则执行完该情况后退出流程。

在特殊情况之间所描述的均为一般情况，只要之前没有因为满足某种特殊情况而退出流程，均认为满足了一般情况。

首先，琪露诺将会一次性放置最多 $H_X\times H_Y$ 个冰砖来建造屋顶。

为什么是最多呢？请注意一点：如果之前错误放置在房子内部的冰砖恰好充当了屋顶的一部分，那么就不用在这个位置再放冰砖了。并且，所有比屋顶高的冰砖在之后将视为错误放置在了房子外部。

注意，放屋顶的时候可能会触及到高度为 $H_M$ 的那个平面。

建造屋顶前后将会碰到两种特殊情况：
- 琪露诺剩余的冰砖不足以建造屋顶。输出一行：`SORRY CIRNO,NOT ENOUGH ICE_BLOCK(S) TO MAKE ROOF`
- 墙壁的最高高度小于 $2$ 个方格，或者内部有效空间小于两个方格。
墙壁所在的一圈不算内部空间。计算内部有效空间时请忽视错误放置的冰砖，因为它们将来要被移除。
输出一行：`SORRY CIRNO,HOUSE IS TOO SMALL`

（特殊情况结束）

此后，我们认为琪露诺已经造好了屋顶，接下来该移除所有多余冰砖了。在移除过程中，琪露诺会尽可能让更少的冰砖摔碎。如果墙壁上某个冰砖因为移走了多余的冰砖而将要摔碎，那么她会先拆掉墙壁上的那个冰砖，然后在填补墙壁残缺时重新补回来（显然，这种行为不会影响到墙壁有无残缺的定性，但可以少损失一个冰砖）。她不会故意拆掉一个处在墙壁上且不会摔碎的冰砖。
输出两行：
`K1 ICE_BLOCK(S) INSIDE THE HOUSE NEED TO BE REMOVED`
`K2 ICE_BLOCK(S) OUTSIDE THE HOUSE NEED TO BE REMOVED`
`K1`表示房子内部错误放置的冰砖数量，`K2`表示房子外部错误放置的冰砖数量。

将有可能遭遇一种特殊情况：
- 琪露诺移除了所有多余的冰砖，但在移除过程中，屋顶塌陷了。
输出一行：`SORRY CIRNO,HOUSE IS BROKEN WHEN REMOVING BLOCKS`

（特殊情况结束）

此后，我们认为琪露诺已经移除了所有多余的冰砖，接下来该填补墙壁的残缺了。

墙壁有残缺的定义是：除了宽为 $1$，高为 $2$ 的门以外，
在房子内部看外面还能看到其他缺口。

如果某个空位将来要作为门的一部分，则不属于残缺。并且房子只能有一个门。

如果墙壁没有残缺，则不要填补，否则需要填补。你需要记下墙壁是否有残缺，之后会用到。

填补的策略是：使用尽可能少的冰砖，在正确的位置填补墙壁，使房屋的状态不满足墙壁有残缺的定义（即不能放置多余的冰砖，通过遮挡视线来达到目的）。在此定义下，**大多数**情况我们无需考虑四角的柱子是否完整，因为在房间里看不到。

将有可能遭遇一种特殊情况：
- 琪露诺剩余的冰砖不足以填补墙壁的残缺。
输出一行：`SORRY CIRNO,NOT ENOUGH ICE_BLOCKS TO FIX THE WALL`

（特殊情况结束）

此后，我们认为房子被成功建成了，这时你需要输出几行内容来对房子进行评价。

首先输出这么一行来庆祝房子的建成：`GOOD JOB CIRNO,SUCCESSFULLY BUILT THE HOUSE`
1. 在贴近地面的位置找不到一个宽度为 $1$，高度为 $2$ 的位置留给门。
	输出一行：`HOUSE HAS NO DOOR`，然后琪露诺会尽可能利用墙壁上的残缺来开一个门。
    否则，输出一行：`DOOR IS OK`
2. 接下来输出一行表示填补之前墙壁的完整程度
	2.1. 在之前的记录中，墙壁不完整而需要修补。输出：`WALL NEED TO BE FIXED`
    2.2. 在之前的记录中，墙壁完整而无需修补。输出：`WALL IS OK`
3. 接下来一行表示四角的完整程度。
	如果四个角的柱子有不完整的地方，就输出：`CORNER NEED TO BE FIXED`
    在这种情况下，如果琪露诺剩余的冰砖足够修复拐角的空缺，那么她直接会修复这个空缺。
    如果不够的话，她会再多收集几个冰砖，数量恰好修复这个空缺，然后修复这个空缺。
    否则，输出：`CORNER IS OK`

接下来，输出一行：`CIRNO FINALLY HAS k ICE_BLOCK(S)`
`k` 表示琪露诺最后剩余的冰砖的数量。

最后，如果在之前的记录中，墙壁完整无缺，没有一个位置需要填补。房子内外都无任何多余的方块，没有一个位置需要移除。没有出现房子没门的情况，房子四角的柱子也在造屋顶前完全造好，而不是通过修补完善的。并且门恰好开在了某面墙的正中央（如果长度为偶数，中间的两个都算），输出一行：
`CIRNO IS PERFECT!`

inputFormat:
第一行一个正整数 $N$，表示雪地的大小。

第二行一个正整数$H_M$，表示琪露诺放置方块的最大高度。

第三行四个正整数 $H_R,H_C,H_X,H_Y$，表示房子左上角位置的行列坐标，房子的长度以及宽度。

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

接下来 $M$ 行，每行表示一个操作，输入格式见题目描述。

outputFormat: 在题目描述中已经介绍。

samples:
8
10
4 0 4 4
63
ICE_BARRAGE 2 1 1 3
ICE_BARRAGE 0 1 3 1
MAKE_ICE_BLOCK
PUT_ICE_BLOCK 3 2 0
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 2 0 6 7
ICE_BARRAGE 3 0 6 7
ICE_BARRAGE 4 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
MAKE_ICE_BLOCK
PUT_ICE_BLOCK 4 0 1
PUT_ICE_BLOCK 4 0 0
PUT_ICE_BLOCK 4 0 1
PUT_ICE_BLOCK 3 0 1
REMOVE_ICE_BLOCK 4 0 1
PUT_ICE_BLOCK 4 2 0
PUT_ICE_BLOCK 6 1 0
PUT_ICE_BLOCK 4 3 0
PUT_ICE_BLOCK 5 3 0
PUT_ICE_BLOCK 6 3 0
PUT_ICE_BLOCK 7 3 0
ICE_BARRAGE 0 1 4 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
MAKE_ICE_BLOCK
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
MAKE_ICE_BLOCK
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
MAKE_ICE_BLOCK
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
ICE_BARRAGE 1 0 6 7
MAKE_ICE_BLOCK
REMOVE_ICE_BLOCK 6 1 0
PUT_ICE_BLOCK 5 0 0
PUT_ICE_BLOCK 6 0 0
PUT_ICE_BLOCK 7 0 0
PUT_ICE_BLOCK 7 1 0
PUT_ICE_BLOCK 7 2 0
PUT_ICE_BLOCK 4 0 1
PUT_ICE_BLOCK 5 0 1
PUT_ICE_BLOCK 6 0 1
PUT_ICE_BLOCK 7 0 1
PUT_ICE_BLOCK 7 1 1
PUT_ICE_BLOCK 7 2 1
PUT_ICE_BLOCK 7 3 1
PUT_ICE_BLOCK 6 3 1
PUT_ICE_BLOCK 5 3 1
PUT_ICE_BLOCK 4 3 1
PUT_ICE_BLOCK 4 2 1
MAKE_ROOF

samples:
CIRNO FREEZED 2 BLOCK(S)
CIRNO FREEZED 2 BLOCK(S)
CIRNO MADE 0 ICE BLOCK(S),NOW SHE HAS 0 ICE BLOCK(S)
CIRNO HAS NO ICE_BLOCK
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 7 BLOCK(S)
CIRNO FREEZED 7 BLOCK(S)
CIRNO FREEZED 0 BLOCK(S)
CIRNO MADE 8 ICE BLOCK(S),NOW SHE HAS 8 ICE BLOCK(S)
BAKA CIRNO,CAN'T PUT HERE
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 7 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 6 ICE_BLOCK(S)
CIRNO MISSED THE PLACE
CIRNO REMOVED AN ICE_BLOCK,AND 1 BLOCK(S) ARE BROKEN
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 5 ICE_BLOCK(S)
CIRNO PUT AN ICE_BLOCK INSIDE THE HOUSE
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 3 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 2 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 1 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 0 ICE_BLOCK(S)
CIRNO FREEZED 6 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 7 BLOCK(S)
CIRNO MADE 8 ICE BLOCK(S),NOW SHE HAS 8 ICE BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO MADE 8 ICE BLOCK(S),NOW SHE HAS 16 ICE BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO MADE 8 ICE BLOCK(S),NOW SHE HAS 24 ICE BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO FREEZED 8 BLOCK(S)
CIRNO MADE 8 ICE BLOCK(S),NOW SHE HAS 32 ICE BLOCK(S)
CIRNO REMOVED AN ICE_BLOCK
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 32 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 31 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 30 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 29 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 28 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 27 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 26 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 25 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 24 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 23 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 22 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 21 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 20 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 19 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 18 ICE_BLOCK(S)
CIRNO SUCCESSFULLY PUT AN ICE_BLOCK,NOW SHE HAS 17 ICE_BLOCK(S)
0 ICE_BLOCK(S) INSIDE THE HOUSE NEED TO BE REMOVED
0 ICE_BLOCK(S) OUTSIDE THE HOUSE NEED TO BE REMOVED
GOOD JOB CIRNO,SUCCESSFULLY BUILT THE HOUSE
DOOR IS OK
WALL IS OK
CORNER IS OK
CIRNO FINALLY HAS 1 ICE_BLOCK(S)
CIRNO IS PERFECT!

hint:
共分为 $6$ 个 **Subtask**，每个 **Subtask** 的数据都满足一定条件，并且同时满足序号更大的 **Subtask** 的条件。
如 **Subtask #0** 同时满足 **Subtask #0~5** 的条件。
每一个 **Subtask** 的得分取所有测试点的最低分。

**Subtask #0** $20\%$
琪露诺只想玩玩冰雪弹幕，她不会放置任何冰砖，也不会盖房子(即只有操作一和操作二)。

**Subtask #1** $10\%$
琪露诺不会移除已经放置的冰砖。

**Subtask #2** $20\%$
琪露诺很有信心，她将在没有 `MAKE_ROOF` 的情况下建造她的冰屋(这种情况下，放置方块的高度仍然会小于 $H_M$ 且没有 `MAKE_ROOF` 操作)。

**Subtask #3** $20\%$
琪露诺在移除方块时会谨慎考虑,不会造成任何冰砖摔落。`MAKE_ROOF` 操作移除多余冰砖时，也不会造成屋顶塌陷。

**Subtask #4** $20\%$
琪露诺不喜欢把门开到四角的柱子旁边(数据保证在所有可能作为门的墙壁空缺中，有一种可能使得门不紧贴四角的柱子)。

**Subtask #5** $10\%$
$4\le N\le 16$，$5\le H_M\le 20$，$10\le M\le 10^3$，保证不属于冰屋范围内的所有空地至多构成一个连通块。

注意：判断墙壁是否有残缺时，候选的开门位如果被方块堵住，在当时还未被清空。"能看到残缺"以当时的情况作为判断依据。


title: 仓鼠的数学题

type: P

background: **请注意本题时限1s，开启O2优化，你可能需要输入输出优化**

description:
仓鼠在某oj上看到了一个问题，设$S_k(x)=\sum_{i=0}^x i^k$，这个题输入$a_0,a_1...a_n$，假设$0^0=1$，要求计算$\sum_{k=0}^{n}S_k(x)a_k$。

仓鼠想了两秒就秒了这个题，他发现数据范围居然只有1000，就顺手加了两个0。

但是仓鼠懒得造数据了，就把这道题丢给了你。

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

第一行输入$n+1$个空格分隔的非负整数。分别是$a_0 \cdots a_n$。

outputFormat:
输出$n+2$个空格分隔的整数，表示答案多项式的各项系数$c_0...c_{n+1}$，表示答案多项式为$\sum_{i=0}^{n+1}c_ix^i$。多项式的系数对998244353取模。

可以证明多项式的次数$\leq n+1$。

hint:
对于10%的数据，$n \leq 500$。

对于30%的数据，$n \leq 3000$。

对于70%的数据，$n \leq 100000$。

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

输入和输出多项式系数均为模998244353意义下，为$[0,998244352]$的非负整数。


title: 国事访问

background: 这是战火纷飞的2333年，世界被分为XC联盟和WJ联盟，两个联盟互相开火。

description: 这是战火纷飞的2333年，世界被分为XC联盟和WJ联盟，两个联盟互相开火。Q国总统ZR想到Yugo国进行十分紧急的国事访问，但不能坐飞机，只能坐车。由于路上有许多不同的国家而且有些无政府国，所以有许多路是坏的。路没有从自己通向自己的（作死吗。。。）。你需要确定一条具体的路线，并且由于WJ联盟的人随时可能过来，你需要把这条路线经过的所有城市周围的其他路都毁掉。你是上帝视角，你需要帮助ZR总统到达Yugo，你可以毁掉一些原本是好的路，也可以把坏的路修好，但不能新修路。给你一份地图，地图上，ZR国坐落在1城，Yugo首都在n城。帮助ZR总统尽快到达Yugo，你可以获得ZR总统在WJ联邦银行的30亿存款和1000万人的军队，和ZR总统一起瓜分地球（以上是诈骗内容。。。）。

inputFormat:
第一行，n，m，（2<=n<=1000,0<=m<=1000），n是Yugo首都，m是公路数量。

第2至m+1行，a，b，c，a是公路起始城市，b是公路结束城市，c是路的情况（1：能通行/0：不能通行）。

outputFormat: 第一行，k，需要改变路状态的最小数量。

hint:
把 1 2 1 路径变成不可用

把 1 3 0 路径变成可用

把 2 3 1 路径变成不可用

即可


title: [USACO1.3] 滑雪课程设计Ski Course Design

description:
农民约翰的农场里有 $n$ 座山峰，每座山都有一个在 $0$ 到 $100$ 之间的整数的海拔高度。在冬天,因为山上有丰富的积雪，约翰经常开办滑雪训练营。

不幸的是，约翰刚刚得知税法在滑雪训练营方面有新变化，明年开始实施。在仔细阅读法律后，他发现如果滑雪训练营的最高和最低的山峰海拔高度差大于 $17$ 就要收税。因此，如果他改变山峰的高度（使最高与最低的山峰海拔高度差不超过 $17$ ），约翰可以避免支付税收。

如果改变一座山 $x$ 单位的高度成本是 $x^2$ 单位，约翰最少需要付多少钱才能使海拔最高的山峰与海拔最低的山峰的高度之差不超过 $17$ 约翰只愿意改变整数单位的高度。

inputFormat:
输入的第一行是一个整数，代表山峰的数量 $n$。

第 $2$ 行到$(n + 1)$ 行，每行一个整数。第 $i$ 行的整数 $a_i$ 代表第 $i$ 座山的海拔高度。

outputFormat: 输出一行一个整数，代表约翰需要支付修改山海拔高度的总金额。

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

约翰保持高度为 $4$、$20$ 和 $21$ 的山的高度。他增高高度为 $1$ 的山，变成高度 $4$ ，花费 $3^2 = 9$。他降低了高度为 $24$ 的山变成高度 $21$，也花费 $3 ^ 2 = 9$。因此总共花费 $9 + 9 = 18$。

---

#### 数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 1000$，$0 \leq a_i \leq 100$。


title: 主主树

background: byx 和诗乃酱都非常都非常喜欢种树。有一天，他们得到了两颗奇怪的树种，于是各自取了一颗回家种树，并约定几年后比一比谁种出来的树更加牛 X。

description:
很快，这棵树就开花结果了。byx 和诗乃酱惊讶的发现，这是一棵主主树，树上长满了主主和主主的朋友们。这棵树上一共有五种人，主主（$\verb!J!$），记记（$\verb!HK!$），高高（$\verb!W!$），王王（$\verb!E!$）和歪歪（$\verb!YYY!$）。他们发现，他们的主主树上的人数相同，都为 $N$。

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

研究发现，这五种人的输赢如上图所示（一样的人不能 PK），箭头指向输的人。至于为什么，留给同学们自己思考。

比赛如期进行。

byx 和诗乃酱要进行 $M$ 场比赛，每一场比赛他们会选出树上的两个人来比较看谁更牛 X。

第 $i$ 个人寿命为 $\text{Life}_i$ 秒，每次比完赛他们就会 $-1$s。当他们生命为 $0$s 时他们就不能再比赛了。

同时，当 $\verb!J!$ 的寿命为 $0$ 时，同一棵树上的 $\verb!YYY!$ 可以为他 $+1$s。每个 $\verb!YYY!$ 只能给每个 $\verb!J!$ 续一次。

那么问题来了：

现在给定 $N,M(1\le N\le 100,1\le M\le 1000)$，诗乃酱和 byx 每一个人所属种类（$\verb!J!,\verb!HK!,\verb!W!,\verb!YYY!$ 或 $\verb!E!$）以及每一个人的生命，生命不超过 $50$。请你算算 byx 最多能够赢得多少场比赛呢。

数据保证每一场一定都有人用。两个人之间只能比一场。

inputFormat:
第一行包含两个数 $N,M$，含义看上面。

第二行 $N$ 个字串（$\verb!J!,\verb!HK!,\verb!W!,\verb!YYY!$ 或 $\verb!E!$），表示 byx 的人所属种类，用空格隔开。

第三行 $N$ 个字串（$\verb!J!,\verb!HK!,\verb!W!,\verb!YYY!$ 或 $\verb!E!$），表示诗乃酱的人所属种类，用空格隔开。

第四行 $N$ 个数，表示 byx 的人的生命。

第五行 $N$ 个数，表示诗乃酱的人的生命。

outputFormat: 一个数，byx 能赢的场次。

hint: 第一场主主赢记记，第二场高高赢王王，第三场歪歪赢记记。


title: 方方方的数据结构

description:
在很久很久以前，有一个长度为 $n$ 的数列，一开始数列全是 $0$。

方方方觉得这个数列太单调了，打算对它进行 $m$ 次操作，每次操作为区间加法或者区间乘法。

方方方进行一些操作之后，还可能会对某个数进行询问。

但是进行过一些操作之后，方方方可能会发现之前某次操作失误了，需要撤销这次操作，其它操作和其它操作的前后顺序保持不变。

方方方想好这些操作之后，马上想到了一个优秀的数据结构可以维护这些东西，可是他懒得写标程了，就生成了 $10$ 个**随机数据**，就把这道题扔给了你。

**数据全是随机的，生成方式见最下方的提示。**

inputFormat:
第一行两个数 $n,m$，表示数列的长度和操作个数。

接下来 $m$ 行每行 $2$ 或 $4$ 个数。

1. 如果第一个数为 $1$，接下来跟三个数 $l,r,d$，表示把区间 $[l,r]$ 中的数加上 $d$。
2. 如果第一个数为 $2$，接下来跟三个数 $l,r,d$，表示把区间 $[l,r]$ 中的数乘上 $d$。
3. 如果第一个数为 $3$，接下来跟一个数 $p$，表示询问 $p$ 位置的数 $\bmod\ 998244353$。
4. 如果第一个数为 $4$，接下来跟一个数 $p$，表示将第 $p$ 行输入的操作撤销（保证为加或者乘操作，一个操作不会被撤销两次）。

outputFormat: 对于每个 $3$ 操作输出一行表示答案。

hint:
对于 $20\%$ 的数据，$n,m \leq 500$，时限 1s。

对于 $50\%$ 的数据，$n,m \leq 30000$，时限 1s。

对于 $100\%$ 的数据，$1 \leq n,m \leq 150000$，$1 \le l \le r \le n$，$3$ 操作的 $p$ 满足 $1 \le p \le n$，$4$ 操作的 $p$ 满足 $1 \le p \le m$，$0 \leq d \leq 1073741823$（原因见数据生成器），时限 4.5s。

数据生成器：

```cpp
#include <bits/stdc++.h>
using namespace std;
int rand_() {return rand()&32767;}
int br() {return rand_()*32768+rand_();}
vector<int> cs;
int main()
{
    srand(...); //这里要填一个种子
    int n=...,m=...; //这里要填n、m
    cout<<n<<" "<<m<<"\n";
    for(int i=1;i<=m;i++)
    {
        int o=rand()%4+1;
        if(o<=2)
        {
            cout<<o<<" ";
            int l=br()%n+1,r=br()%n+1;
            if(l>r) swap(l,r); cs.push_back(i);
            cout<<l<<" "<<r<<" "<<br()<<"\n";
        }
        else if(o==3) cout<<o<<" "<<br()%n+1<<"\n";
        else
        {
            if(!cs.size()) {--i; continue;}
            int s=br()%cs.size(),g=cs[s];
            cs.erase(cs.begin()+s);
            cout<<o<<" "<<g<<"\n";
        }
    }
}
```


title: koishi的数学题

description:
Koishi 在 Flandre 的指导下成为了一名数学大师，她想了一道简单的数学题。

输入一个整数 $n$，设 $\displaystyle f(x) = \sum_{i=1}^n x \bmod i$，你需要输出 $f(1), f(2), \ldots , f(n)$。

按照套路，Koishi 假装自己并不会做这道题，就来求你帮忙辣。

inputFormat: 一个正整数 $n$。

outputFormat: 一行用空格分隔的 $n$ 个整数 $f(1), f(2), \ldots , f(n)$。


title: 大爷的字符串题

background:
在那遥远的西南有一所学校，

/\*被和谐部分\*/

然后去参加该省省选虐场，

然后某蒟蒻不会做，所以也出了一个字符串题：

description:
给你一个字符串 $a$，每次询问一段区间的贡献。

贡献定义：

每次从这个区间中拿出一个字符 $x$ ，然后把 $x$ 从这个区间中删除，直到区间为空。你要维护一个集合 $S$。

- 如果 $S$ 为空，你 rp 减 $1$。
- 如果 $S$ 中有一个元素不小于 $x$，则你 rp 减 $1$，清空 $S$。
- 之后将 $x$ 插入 $S$。

由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少 rp？rp 初始为 $0$。

询问之间不互相影响~

inputFormat:
第一行两个整数 $n$，$m$，表示字符串长度与询问次数。

之后一行 $n$ 个数，第 $i$ 个整数表示给出的字符串的第 $i$ 个字符 $x_i$。

接下来 $m$ 行，每行两个整数 $l, r$，表示一次询问的区间。

outputFormat: 对于每次询问，输出一行一个整数表示答案。

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

- 对于 $10\%$ 的数据，是样例。
- 对于另外 $10\%$ 的数据，保证 $n,m \le 100$；
- 对于另外 $10\%$ 的数据，保证 $n,m \le 10^3$；
- 对于另外 $10\%$ 的数据，保证 $n,m \le 10^4$；
- 对于另外 $10\%$ 的数据，保证 $n,m \le 10^5$；
- 对于 $100\%$ 的数据，$1 \leq n,m \le 2 \times10^5$，$1 \leq a_i \leq 10^9$，$1 \leq l, r \leq n$。

保证数据像某省省选 day1T2 一样 sb，大家尽情用暴力水过题吧！

没事，你只要在一个好学校，就算这题只能拿到 10 分，也可以进队了。


title: [AHOI2017初中组] guide

description:
农场主John最近在网上买了一辆新车，在购买汽车配件时，John不小心点了两次“提交”按钮。导致汽车上安装了两套GPS系统，更糟糕的是John在使用GPS导航时，两套系统常常给出不同的路线。从地图上看，John居住的地区有N(2 ≤ N ≤ 100,000)个十字路口和M(1 ≤ M ≤ 500,000)条限定通行方向的道路。第i条道路连接路口 A\_i (1 ≤ A\_i ≤ N)和B\_i (1 ≤ B\_i ≤ N)，两个路口之间可能连接有多条道路。允许双向通⾏的道路是将两条单向通⾏的道路隔开所形成的。

John的家在路口1位置，农场在路口N的位置。John可以沿着⼀系列单向道路从家驾车到农场。所有GPS系统的底层地图信息都是⼀样的，区别仅在于对每一条道路的通⾏时间计算不同。对于第i条道路第一套GPS系统计算通行时间为P\_i个单位时间，而第二套GPS系统则给出Q\_i个单位时间。（所有道路的通行时间都是范围在1到100，000之间的整数）John想要驾车从家到农场。可是，一路上GPS系统总是不厌其烦的提醒John（请从路口X开往路口Y），这是由于John选取了某套GPS系统建议的路径，而另一套GPS系统则认为这不是从路口X到农场的最短路径。我们称之为GPS系统的抱怨。

请你计算一下如果John选择合适的路径到达农场能听到的最少GPS系统的抱怨数 。如果John经过某条道路两套GPS系统都发出抱怨，则抱怨总数加2。

inputFormat:
第一行，两个整数N和M。

接下来M行，其中第i行描述了道路i的信息，A\_i B\_i P\_i Q\_i。

outputFormat: 一个整数，表示John一路上能听到的最小抱怨数。


title: 【模板】点分治 1

background: 感谢 hzwer 的点分治互测。

description: 给定一棵有 $n$ 个点的树，询问树上距离为 $k$ 的点对是否存在。

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

第 $2$ 到第 $n$ 行，每行三个整数 $u, v, w$，代表树上存在一条连接 $u$ 和 $v$ 边权为 $w$ 的路径。

接下来 $m$ 行，每行一个整数 $k$，代表一次询问。

outputFormat: 对于每次询问输出一行一个字符串代表答案，存在输出 `AYE`，否则输出 `NAY`。

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

- 对于 $30\%$ 的数据，保证 $n\leq 100$。
- 对于 $60\%$ 的数据，保证 $n\leq 1000$，$m\leq 50$ 。
- 对于 $100\%$ 的数据，保证 $1 \leq n\leq 10^4$，$1 \leq m\leq 100$，$1 \leq k \leq 10^7$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^4$。

#### 提示

- **本题不卡常**。
- 如果您 #7 一直 RE/TLE，不妨看看 [这个帖子](https://www.luogu.com.cn/discuss/show/188596)。


title: 【模板】动态树（LCT）

description:
给定 $n$ 个点以及每个点的权值，要你处理接下来的 $m$ 个操作。
操作有四种，操作从 $0$ 到 $3$ 编号。点从 $1$ 到 $n$ 编号。

- `0 x y` 代表询问从 $x$ 到 $y$ 的路径上的点的权值的 $\text{xor}$ 和。保证 $x$ 到 $y$ 是联通的。
- `1 x y` 代表连接 $x$ 到 $y$，若 $x$ 到 $y$ 已经联通则无需连接。
- `2 x y` 代表删除边 $(x,y)$，不保证边 $(x,y)$ 存在。
- `3 x y` 代表将点 $x$ 上的权值变成 $y$。

inputFormat:
第一行两个整数，分别为 $n$ 和 $m$，代表点数和操作数。

接下来 $n$ 行，每行一个整数，第 $(i + 1)$ 行的整数 $a_i$ 表示节点 $i$ 的权值。

接下来 $m$ 行，每行三个整数，分别代表操作类型和操作所需的量。

outputFormat: 对于每一个 $0$ 号操作，你须输出一行一个整数，表示 $x$ 到 $y$ 的路径上点权的 $\text{xor}$ 和。

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

对于全部的测试点，保证：
- $1 \leq n \leq 10^5$，$1 \leq m \leq 3 \times 10^5$，$1 \leq a_i \leq 10^9$。
- 对于操作 $0, 1, 2$，保证 $1 \leq x, y \leq n$。
- 对于操作 $3$，保证 $1 \leq x \leq n$，$1 \leq y \leq 10^9$。


title: 曼哈顿计划E

background:
1942 年 6 月，美国开始实施利用核裂变反应来研制原子弹的计划，亦称曼哈顿计划。后来两颗原子弹在广岛和长崎爆炸，世界见证了核武器的威力，并在它的威胁下颤抖不已。2200 年，dedsec 组织利用美国军方的网络安全漏洞渗入了美国的和武器系统，并密谋使用隐藏在曼哈顿的核武器储备毁灭世界。然而 dedsec 的一名成员 Badboy17 反对这一计划，她把这一计划告知了艾登。为了拯救他的家人，避免地球变为废土，艾登不得不再次发挥他的黑客能力拯救世界。

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

description:
艾登尝试黑入 dedsec 的系统并取得控制权，然而 dedsec 有所反应并予以反击。

dedsec 的网络可以看做是一个 $n$ 个点 $n-1$ 条边的连通图（一棵树），每个节点有一个稳定值。

艾登可以选择网络中上的一条链，并对那一条链上的节点进行破解（把这一条链从树上拆下来）。

假设这一条链长度为 $m$，现在你会得到 $m$ 个节点。

然后艾登要和 dedsec 开始攻防战，双方轮流行动，每次可以从任意一个稳定值大于 $0$ 的节点里依照计算规则进行一些操作，操作后，稳定值不能小于 $0$，否则计算机会爆炸，最后不能进行操作的一方算作失败

由于 dedsec 占据了防守的地理优势，dedsec 先进行操作

艾登虽然精于黑客技术，但他的手机没电了。现在他把这个消息告诉了你，希望你帮他拯救世界，所以你需要写一个程序，来帮你判断是否存在一种方式，艾登可以取胜。当然，dedsec 的防守可能完美无缺，艾登根本无法取胜，你只好跑到 shelter 里去当试验品。

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

对于每组测试数据，第一行一个整数 $n$，表示有 $n$ 个点。

第二行至第 $n$ 行，每行两个整数 $u,v$，表示网络中有一条边连接 $u,v$。

第 $n+1$ 行 $n$ 个整数 $w$，第 $w_i$ 表示 $i$ 号节点的稳定值。

第 $n+2$ 行一个整数 $k$，描述操作的规则：

- 如果 $k=1$，你可以减少任意正整数的稳定值。
- 如果 $k=2$，接下来一行一个正整数 $s$，表示双方每次可以减少 $s$ 的非负整数幂的稳定值。
- 如果 $k=3$，接下来一行一个正整数 $s$，表示双方每次可以减少大于等于 $s$ 的稳定值。
- 如果 $k=4$，表示双方每次可以减少任意正整数的稳定值，或者把一个稳定值数量大于等于 $2$ 的节点分裂成两个，分开后的两个节点的稳定值之和等于原来的节点（比如 $7$ 分成 $3+4$）。
- 如果 $k=5$，双方都不能进行操作。

outputFormat:
对于每一组测试数据，输出一行：

如果存在一种方式，你可以获胜，输出 `Mutalisk ride face how to lose?`。

如果不存在一种方式可以取胜，输出 `The commentary cannot go on!`。


title: [AHOI2017初中组] cover

background: 以下为不影响题意的简化版题目。

description: 一个 $n\times n$ 的网格图（标号由 $1$ 开始）上有 $m$ 个探测器，每个探测器有个探测半径 $r$ ，问这 $n\times n$ 个点中有多少个点能被探测到。

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

接下来 $m$ 行，每行两个整数 $x,y$表示第 $i$ 个探测器的坐标。

outputFormat: 能被探测到的点的个数。


title: [AHOI2017初中组] alter

description: 有 $n$ 盏灯排成一列，其中有些灯开着，有些灯关着。小可可希望灯是错落有致的，他定义一列灯的状态的不优美度为这些灯中最长的连续的开着或关着的灯的个数。小可可最多可以按开关 $k$ 次，每次操作可以使该盏灯的状态取反：原来开着的就关着，反之开着。现在给出这些灯的状态，求操作后最小的不优美度。

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

第二行是一个长度为 $n$ 的字符串，其中有两种字符：`N` 和 `F`。其中 `N` 表示该灯开着，`F` 表示该灯关着。

outputFormat: 最小的不优美度。

hint:
$30\%$ 的数据：$1\le k \le n\le20$；

$50\%$ 的数据：$1\le k \le n\le300$；

另有 $15\%$ 的数据：$1\le k \le n\le 10^5$，字符串为全 `N` 或全 `F`；

$100\%$ 的数据：$1\le k \le n\le 10^5$。

本题已经加入 hack 数据。


title: [AHOI2017初中组] rexp

background: 为了解决形形色色的字符串匹配问题，正则表达式是一个强有力的工具。正则表达式通过定义一套符号体系，能够表示出需要查找的字符串所具有的性质。如 `a|aa` 能匹配 `a` 或 `aa`，`(a|b)c` 能匹配 `ac` 或 `bc`。

description:
完整的正则表达式过于复杂，在这里我们只考虑由 `(`、`)`、`|` 和 `a` 组成的正则表达式。运算遵循下列法则：

1. 有括号时，我们总是先算括号内的部分；

2. 当两个字符串（或由括号定义的子串）间没有符号时，我们总把它们连起来作为一个整体；

3. `|` 是或连接符，表示两边的字符串任取其一，若同一层里有多个或连接符，可以看作在这些或连接符所分开的若干字符串里任取其一。

例如，`(aaa)aa|aa|(a(aa)a)`、`(aaaaa)|(aa)|aaaa` 和 `aaaaa|aaaa|aa` 是等价的，它们都能匹配长度为 $2,4$ 或 $5$ 的全 `a` 字符串。

下面给定一个简化正则表达式，试编程计算它最多能匹配多长的全 `a` 字符串。

inputFormat: 输入一行一个合法的简化正则表达式。

outputFormat: 一行一个整数，表示能匹配的最长全 `a` 字符串长度。

hint:
**【数据范围】**

对于 $20\%$ 数据，表达式长度不超过 $100$，且不存在括号。

对于 $40\%$ 数据，表达式长度不超过 $100$。

对于 $70\%$ 数据，表达式长度不超过 $2 \times 10^3$。

对于 $100\%$ 的数据，表达式长度不超过 $10^5$。

保证表达式合法（即 `|` 两端和括号内运算结果均非空字符串）。


title: [CTSC2000] 冰原探险

description:
传说中，南极有一片广阔的冰原，在冰原下藏有史前文明的遗址。整个冰原被横竖划分成了很多个大小相等的方格。在这个冰原上有 $N$ 个大小不等的矩形冰山，这些巨大的冰山有着和南极一样古老的历史。

每个矩形冰山至少占据一个方格，且其必定完整地占据方格。冰山和冰山之间不会重叠，也不会有边或点相连。以下两种情况均是不可能出现的：

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

$\text{ACM}$ 探险队在经过多年准备之后决定在这个冰原上寻找遗址。根据他们掌握的资料，在这个冰原上一个大小为一格的深洞中，藏有一个由史前人类制作的开关。而唯一可以打开这个开关的是一个占据接近一格的可移动的小冰块。显然，在南极是不可能有这样小的独立冰块的，所以这块冰块也一定是史前文明的产物。他们在想办法把这个冰块推到洞里去，这样就可以打开一条通往冰原底部的通道，发掘史前文明的秘密。冰块的起始位置与深洞的位置均不和任何冰山相邻。

这个冰原上的冰面和冰山都是完全光滑的，轻轻的推动冰块就可以使这个冰块向前滑行，直到撞到一座冰山就在它的边上停下来。冰块可以穿过冰面上所有没有冰山的区域，也可以从两座冰山之间穿过（见下图）。冰块只能沿网格方向推动。

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

请你帮助他们以最少的推动次数将冰块推入深洞中。

inputFormat: 输入文件第一行为冰山的个数 $N$ ，第二行为冰块开始所在的方格坐标 $X_{1}$ , $Y_{1}$ ，第三行为深洞所在的方格坐标 $X_{2}, Y_{2}$ ，以下 $N$ 行每行有四个数，分别是每个冰山所占的格子左上角和右下角坐标 $X_{i_{1}}, Y_{i_{1}}, X_{i_{2}}, Y_{i_{2}}$

outputFormat: 输出文件包含一个整数，为最少推动冰块的次数。如果无法将冰块推入深洞中，则输出 $0$ 。

hint:
$1 \leq N \leq 4000$

样例解释：移动方案如图所示。

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


title: 曼哈顿交易

background:
will 在曼哈顿开了一家交易所，每天，前来买卖股票的人络绎不绝。

现在，will 想要了解持股的情况。由于来交♂易的人实在是太多了，需要你写一个程序来帮他完成这个任务。

description:
- 前来交易的 $N$ 个人排成了一行，为了简便起见，每个人都只持有一种股票。
- 不同的的人可能会持有相同的股票。
- 定义一种股票的热度为持有该股票的人数。
- 每次，will 会给出这样的询问：在一段连续区间的人之中，热度第 $k$ 小的股票的热度是多少？

inputFormat:
- 第一行两个正整数 $N,M$，分别表示人数和询问的次数。
- 接下来一行 $N$ 个正整数，表示每个人所持的股票 $a_i$。
- 接下来 $M$ 行，每行三个正整数 $l,r,k$，表示询问区间 $[l, r]$ 中的第 $k$ 小的热度，保证 $l\leq r$。

outputFormat:
- 对于每个询问，输出一行一个数，表示区间 $[l, r]$ 中的第 $k$ 小的热度值。
- 如果 $k$ 大于区间里股票的种类数，输出 $-1$。


title: [AH2017/HNOI2017] 单旋

description:
H国是一个热爱写代码的国家，那里的人们很小去学校学习写各种各样的数据结构。伸展树（splay）是一种数据结构，因为代码好写，功能多，效率高，掌握这种数据结构成为了H国的必修技能。有一天，邪恶的“卡”带着他的邪恶的“常数”来企图毁灭H国。“卡”给H国的人洗脑说，splay如果写成单旋的，将会更快。“卡”称“单旋splay”为“spaly”。虽说他说的很没道理，但还是有H国的人相信了，小H就是其中之一，spaly马上成为他的信仰。而H国的国王，自然不允许这样的风气蔓延，国王构造了一组数据，数据由m（不超过10^5）个操作构成，他知道这样的数据肯定打垮spaly，但是国王还有很多很多其他的事情要做，所以统计每个操作

所需要的实际代价的任务就交给你啦。数据中的操作分为5种：

1. 插入操作：向当前非空spaly中插入一个关键码为key的新孤立节点。插入方法为，先让key和根比较，如果key比根小，则往左子树走，否则往右子树走，如此反复，直到某个时刻，key比当前子树根x小，而x的左子树为空，那就让key成为x的左孩子；或者key比当前子树根x大，而x的右子树为空，那就让key成为x的右孩子。该操作的代价为：插入后，key的深度。特别地，若树为空，则直接让新节点成为一个单个节点的树。（各节点关键码互不相等。对于“深度”的解释见末尾对spaly的描述。）

2. 单旋最小值:将spaly中关键码最小的元素xmin单旋到根。操作代价为：单旋前xmin的深度。（对于单旋操作的解释见末尾对spaly的描述。）

3. 单旋最大值:将spaly中关键码最大的元素xmax单旋到根。操作代价为：单旋前xmax的深度。

4. 单旋删除最小值：先执行2号操作，然后把根删除。由于2号操作之后，根没有左子树，所以直接切断根和右子树的联系即可。（具体见样例解释）。操作代价同2号操作。

5. 单旋删除最大值：先执行3号操作，然后把根删除。操作代价同3号操作。

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

对于不是H国的人，你可能需要了解一些spaly的知识，才能完成国王的任务：

1. spaly是一棵二叉树，满足对于任意一个节点x，它如果有左孩子lx，那么lx的关键码小于x的关键码。如果有右孩子rx，那么rx的关键码大于x的关键码。

2. 一个节点在spaly的深度定义为：从根节点到该节点的路径上一共有多少个节点（包括自己）。

3. 单旋操作是对于一棵树上的节点x来说的。一开始，设f为x在树上的父亲。如果x为f的左孩子，那么执行zig(x)操作（如上图中，左边的树经过zig(x)变为了右边的树）,否则执行zag(x)操作（在上图中，将右边的树经过zag(f)就变成了左边的树）。每当执行一次zig(x)或者zag(x),x的深度减小1，如此反复，直到x为根。总之，单旋x就是通过反复执行zig和zag将x变为根。

inputFormat:
输入文件名为 splay.in。

第一行单独一个正整数 m (1 <= m <= 10^5)。

接下来 m 行，每行描述一个操作：首先是一个操作编号 c（ 1<=c<=5），既问题描述中给出的 5 种操作中的编号，若 c= 1，则再输入一个非负整数 key，表示新插入节点的关键码。

outputFormat:
输出文件名为 splay.out。

输出共 m 行，每行一个整数，第 i 行对应第 i 个输入的操作的代价。

hint:
20%的数据满足： 1 <= m <= 1000。

另外 30%的数据满足： 不存在 4,5 操作。

100%的数据满足： 1<=m<=10^5； 1<=key<=10^9。 所有出现的关键码互不相同。 任何一个非插入操作，一定保证树非空。 在未执行任何操作之前，树为空。


title: [AH2017/HNOI2017] 影魔

background:
影魔，奈文摩尔，据说有着一个诗人的灵魂。事实上，他吞噬的诗人灵魂早已成千上万。

千百年来，他收集了各式各样的灵魂，包括诗人、牧师、帝王、乞丐、奴隶、罪人，当然，还有英雄。

每一个灵魂，都有着自己的战斗力，而影魔，靠这些战斗力提升自己的攻击。

description:
奈文摩尔有 $n$ 个灵魂，他们在影魔宽广的体内可以排成一排，从左至右标号 $1$ 到 $n$。第 $i$ 个灵魂的战斗力为 $k_i$，灵魂们以点对的形式为影魔提供攻击力。对于灵魂对 $i, j\ (i<j)$ 来说，若不存在 $k_s\ (i<s<j)$ 大于 $k_i$ 或者 $k_j$，则会为影魔提供 $p_1$ 的攻击力。另一种情况，令 $c$ 为 $k_{i + 1}, k_{i + 2}, \cdots, k_{j -1}$ 的最大值，若 $c$ 满足：$k_i < c < k_j$，或者 $k_j < c < k_i$，则会为影魔提供 $p_2$ 的攻击力，当这样的 $c$ 不存在时，自然不会提供这 $p_2$ 的攻击力；其他情况的点对，均不会为影魔提供攻击力。

影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了，他想知道，对于任意一段区间 $[a, b]$，位于这些区间中的灵魂对会为影魔提供多少攻击力，即考虑所有满足 $a\le i<j\le b$ 的灵魂对 $i, j$ 提供的攻击力之和。

顺带一提，灵魂的战斗力组成一个 $1$ 到 $n$ 的排列：$k_1, k_1, \cdots, k_n$。

inputFormat:
第一行四个整数 $n,m,p_1,p_2$。

第二行 $n$ 个整数 $k_1, k_2,\cdots, k_n$。

接下来 $m$ 行,每行两个数 $a,b$，表示询问区间 $[a,b]$ 中的灵魂对会为影魔提供多少攻击力。

outputFormat: 共输出 $m$ 行，每行一个答案，依次对应 $m$ 个询问。


title: 曼哈顿序列

background:
为了研究**一类动态仙人掌图上基于完全可持久化后缀全局平衡树维护的按操作序分治的分支定界启发式带花树上下界最小费用流最后输出两点曼哈顿距离的问题**，will需要生成一些字母序列。

在写生成器的过程中，因为will太弱了，他遇到了一些问题。现在，需要机智的你来帮他解决这些问题。

description:
序列生成器的工作流程如下：

- will先钦定了一个母序列，长度为N，序列里都是小写字母。

- 子序列定义为：将母序列在任意位置删掉零或多个字符剩下的**非空**序列。例如：ab和ac是abc的子序列，但ca不是。

- 显然，长度为N的序列有$2^N-1$个子序列。

- 将这$2^N-1$个子序列按照字典序排列。will会按照字典序依次生成子序列。

- will希望去掉重复的子序列，如果几个子序列重复（按照字典序大小相等），只生成一个。

- 现在，他想知道，生成器第K次生成的子序列是什么？

inputFormat:
- 第一行两个正整数N，K。N表示母序列长度，K表示询问；

- 接下来一行N个小写字母，表示母序列；

outputFormat: - 一行若干个小写字母表示一个序列，为生成器第K次生成的序列。

hint:
## 样例的解释

对于母序列abb，有7个子序列，按字典序排列：

- a
- ab
- ab
- abb
- b
- b
- bb

去重后的第3个是abb；

## 数据范围

- 对于20%的数据，$N\leq 15$；

- 对于50%的数据，$N\leq 1000$；

- 对于80%的数据，$N\leq 200000$；

- 对于100%的数据，$N\leq 1000000, K\leq 10^9$，且保证存在第K次的输出；

- 前80%数据的时限为1s，后20%的数据时限为2s。


title: 曼哈顿计划EX

background:
- 曼哈顿计划EX， The X Makes It Sound Cool

- 艾登黑进了dedsec的系统以后，发现核弹发射已经进入了倒计时，他必须停止核弹的发射进程。

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

description:
- 艾登拥有一个计算机网络，每一台计算机都至少有着Intel Xeon E50 v40 + 40路GTX10800Titan的恐怖配置，并由无线网络直接或间接连接，这可以用一个无向连通图来表示。但是他的计算机网络有一个问题——不够安全，dedsec可能会攻击他的网络，切断一些无线连接，从而导致整个计算机网络不连通。为了避免这种情况，艾登决定从这些计算机中挑出一些计算机作为计算节点，其他计算机作为信息的中转站，进行停止核弹发射进程的任务。虽然台台都是顶配，但是艾登的计算机也会有从山寨厂买回的配件和原装正版配件的差别——每台电脑的工作能力是不同的，记为$ w_{i}$。现在艾登想知道，对于一个工作能力的要求，整个网络的安全系数最大是多少？

- 设给出的图为$G = (V , E)$，其中$V$ = $V_{1}$（计算节点） + $V_{2}$（中转节点）

- 我们定义安全系数k为：最大的k，使得任意两点$u,v\in V_{1}$都至少有k条互不相交的u到v的链（互不相交定义为：没有重复的边，可以重复有重复的点）

- 我们定义整个图的工作能力$W = \sum_{v \in V_{1}}{w_{v}}$

inputFormat:
- 第1行，三个整数n,m,q表示有n台计算机，m个无线网络，q次询问

- 第2行，n个整数，表示计算机的$w_{i}$

- 第3行到m+2行，每行两个整数u,v，表示有u，v之间存在直接的无线网络，什么都不保证

- 第m+3行到m+q+2行，每行一个整数k，表示一个询问

outputFormat:
- 一共q行，每行一个整数，表示要达到k的工作能力的前提下，整个网络最大的安全系数，如果只用一台计算机就能满足要求，输出"nan"

- 如果没有办法满足需求，输出"Nuclear launch detected"

- 仅输出nan并不能得分

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

## 样例解释

- 对于询问1，选择任何一台计算机作为计算节点都是一个合法答案

- 对于询问2，至少要选择3台计算机，任选三个都是合法方案。选出的三个点构成三角形，对于任意两个点都有两种相互到达的方法（在三角形上顺时针和逆时针走），所以答案是2

- 对于询问3，选择所有的计算机都不足以满足任务

## 数据规模

- 对于30%的数据，n<=20，保证 $qn^{4}$ 不大于1e8

- 对于100%的数据，n<=550,m<=3000,q<=2017,询问以及$w_{i}$均不超过$10^{6}$

- 所有数字均为正整数


title: 首都效应

background: Yugo的最大城市就是它的首都，Yugo国的城市差异十分大：边缘城市几乎没人，但中心城市全是人。

description:
Jace是Alara的总统，和Q国总统一样，因为战乱，他必须乘坐车来Yugo首都。随行的记录员Tezzeret负责调查Yugo的真正实力，他的任务是数清沿途的城市的房子数量。

Yugo的城市已经被编号，他数着数着，发现了一个规律：把城市编号分为几个连续的数字段，对每一数段，该数字乘上这个数段的长度的平方再全部相加，就能得到这个城市的房子数量。例：第233城房数：2\*1^2+3\*2^2=14。

Tezzeret被告知他需要计算沿途的房子数总量（从进入Yugo的A城一直到首都Y城的房子总数），然而计算量太大，你能不能用pc帮他解决这个计算量巨大的问题？

inputFormat: 1行，A，Y(1 ≤ A ≤ B ≤ 10^15)，分别是进入Yugo的第一城和首都。

outputFormat: 1行，房子总量


title: 小果的键盘

background: 小果有一个只有两个键的键盘。

description: 一天，她打出了一个只有这两个字符的字符串。当这个字符串里含有 `VK` 这个字符串的时候，小果就特别喜欢这个字符串。所以，她想改变至多一个字符（或者不做任何改变）来最大化这个字符串内 `VK` 出现的次数。给出原来的字符串，请计算她最多能使这个字符串内出现多少次 `VK`（只有当 `V` 和 `K` 正好相邻时，我们认为出现了 `VK`。）

inputFormat:
第一行给出一个数字 $n$，代表字符串的长度。

第二行给出一个字符串 $s$。

outputFormat: 第一行输出一个整数代表所求答案。


title: umi的函数

background: umi 找到了一个神秘的函数 $f$。

description:
这个函数接受两个字符串 $s1,s2$。这些字符串只能由小写字母组成，并且具有相同的长度。这个函数的输出是另一个长度与 $s1,s2$ 相同的字符串 $g$。$g$ 的第 $i$ 个字符等于 $s1$ 的第 $i$ 个字符和 $s2$ 的第 $i$ 个字符的最小值，简单来说，$g_i=min(s1_i,s2_i)$。

例如：$f(\verb!ab!,\verb!ba!)= \verb!aa!$，$f(\verb!nzwzl!,\verb!zizez!)=\verb!niwel!$。

她现在有两个相同长度的只有小写字母的字符串 $x,y$。找出任何一个满足 $f(x,z)=y$ 的字符串 $z$。如果找不到这样的字符串的话，请输出 $-1$。

inputFormat:
第一行给出以下两个字符串的长度 $n$。

第二行给出一个字符串 $x$。

第三行给出一个字符串 $y$。

outputFormat: 第一行输出一个字符串，代表你找到的符合条件的字符串。找不到的话，请输出 $-1$。


title: 小鸟的设备

background: 小鸟有 $n$ 个可同时使用的设备。

description:
第 $i$ 个设备每秒消耗 $a_i$ 个单位能量。能量的使用是连续的，也就是说能量不是某时刻突然消耗的，而是匀速消耗。也就是说，对于任意实数，在 $k$ 秒内消耗的能量均为 $k\times a_i$ 单位。在开始的时候第 $i$ 个设备里存储着 $b_i$ 个单位能量。

同时小鸟又有一个可以给任意一个设备充电的充电宝，每秒可以给接通的设备充能 $p$ 个单位，充能也是连续的，不再赘述。你可以在任意时间给任意一个设备充能，从一个设备切换到另一个设备的时间忽略不计。

小鸟想把这些设备一起使用，直到其中有设备能量降为  $0$。所以小鸟想知道，在充电器的作用下，她最多能将这些设备一起使用多久。

inputFormat:
第一行给出两个整数 $n,p$。

接下来 $n$ 行，每行表示一个设备，给出两个整数，分别是这个设备的 $a_i$ 和 $b_i$。

outputFormat:
如果小鸟可以无限使用这些设备，输出 $-1$。

否则输出小鸟在其中一个设备能量降为 $0$ 之前最多能使用多久。

设你的答案为 $a$，标准答案为 $b$，只有当 $a,b$ 满足
$\dfrac{|a-b|}{\max(1,b)} \leq 10^{-4}$ 的时候，你能得到本测试点的满分。


title: 李彬的几何

background: 李彬有一个凸多边形(不知道什么是凸多边形的同学可以查百度百科)P。

description:
P 有 n 个顶点p1,p2 ,p3 ,…,pn 。顶点 pi在 2 维平面上的坐标为( xi,yi )。这些顶点是按照顺时针顺序给出的。

李彬可以指定一个实数 D，然后将每个顶点最多移动 D 个单位距离。现在李彬想知道，如果他想使这个凸多边形不再是凸多边形，那么 D 的最小值是多少。

inputFormat:
第一行给出 1 个整数 n。

接下来 n 行，每行给出一个顶点，给出两个整数，分别是这个顶点的 xi和 yi。保证以顺时针顺序给出，并且形成一个严格的凸多边形。

outputFormat:
输出一个实数 D，代表使这个凸多边形不再凸的最小 D 值。

设你的答案为 a,标准答案为 b,只有当 a,b 满足$\frac{|a-b|}{max(1,b)} \le 10^{-4}$的时候，你是对的。


title: 萃香抱西瓜

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

伊吹萃香 (Ibuki Suika) 正在魔法之森漫步，突然，许多西瓜 (Suika) 从四周飞来，划出了绚丽的轨迹。虽然阵势有点恐怖，但她还是决定抱走一些西瓜。

description:
萃香所处的环境被简化为一个长为 $h$，宽为 $w$ 的网格平面。$X$ 坐标范围为 $[1,w]$，$Y$ 坐标范围为 $[1,h]$。

她初始时（第 $1$ 个时刻）站在坐标为 $(sx,sy)$ 的方格。

西瓜可能在任意一个方格出现，在每个时间单位，它们可能向任何一个方向移动，也可能静止不动。西瓜的位置和移动的轨迹是已知的。西瓜的总数为 $n$ 个，但只有 $m$ 个西瓜可以被萃香抱走，因为其他都太大了，可能会砸伤她。

整个过程会持续 $T$ 个时刻。萃香希望可以抱走全部的 $m$ 个西瓜，并且在任何时候避免与任何一个过大的西瓜处在同一位置。抱走的方式为在某个时刻，与该西瓜处于同一位置。另外，由于萃香不愿耗费过多体力到处乱跑，她每个时刻可以选择静止不动，也可以选择移动到相邻的四个格子之一，只要不越出环境边界。如果选择移动到相邻格子，则算作移动了一次。第 $1$ 个时刻萃香刚站定，无法移动。

在每个时刻，如果萃香选择移动，可以认为萃香与西瓜同时从原来的位置移到了新的位置，没有先后顺序。

萃香想要知道，不被任何一个大西瓜砸中，并得到所有的m个小西瓜的情况下，最少需要移动多少次。

inputFormat:
第一行五个整数 $h,w,T,sx,sy$ ，含义见题目描述。

第二行两个整数 $n,m$，含义见题目描述。

接下来 $n$ 段数据，每一段描述了一个西瓜的出现位置，时间，移动方式，是否可以被抱走等内容，具体如下:

首先一行，两个整数 $t1,t2$，表示西瓜在 $t1$ 时刻出现，$t2$ 时刻消失。若 $t2=T+1$，表示西瓜在最后一个时刻也不消失。保证西瓜至少存在一个时刻。

接下来一行一个整数 $a$，只能为 $0$ 或 $1$，$0$ 表示这个西瓜需要避开，$1$ 表示这个西瓜需要抱走。数据保证需要抱走的西瓜恰好有 $m$ 个。

接下来 $t2-t1$ 行，每一行两个整数 $x,y$，顺序描述了从 $t1$ 时刻到 $t2-1$ 时刻，该西瓜的坐标。西瓜的移动不一定是连续的，并且是一瞬间完成的，所以无需考虑萃香是否站在了移动路径上。

outputFormat: 如果萃香在整个 $T$ 时刻内无法避免被大西瓜砸中或者无法收集到所有 $m$ 个小西瓜，输出 $-1$，否则输出一个整数，表示萃香需要移动的最少次数。

hint:
### 样例说明
第 $2 \sim 4$ 个时刻萃香站着不动，在第 $6$ 个时刻，西瓜出现在萃香旁边，萃香移动到 $(3,4)$ 位置即可抱走这个西瓜。

### 数据范围和提示

本题采用捆绑测试。

Subtask $1$：具有特殊性质 A 和 B；

Subtask $2 \sim 3$：仅具有特殊性质 A；

Subtask $4 \sim 5$：仅具有特殊性质 B；

Subtask $6 \sim 10$：不具有任何一个特殊性质。

特殊性质 A：对于所有西瓜，均满足 $t1=1,t2=T+1$。
所有西瓜全程都静止在原地，不会发生移动。

特殊性质 B：$m=0$。

对于全部子任务，满足：

$1 \le x \le w,1 \le y \le h$

$1\le n \le 20,
0 \le m \le 10,
m \le n$

$1 \le h,w \le 5,
1 \le T \le 100,
1 \le t1 \le T,
2 \le t2 \le T+1,
t1< t2$

保证一个位置不会同时出现两个或两个以上西瓜。


title: [JSOI2008] 小店购物

background: JSOI集训队的队员发现，在他们经常活动的集训地，有一个小店因为其丰富的经营优惠方案深受附近居民的青睐，生意红火。

description:
小店的优惠方案十分简单有趣：

一次消费过程中，如您在本店购买了精制油的话，您购买香皂时就可以享受 $2.00$ 元 / 块的优惠价；如果您在本店购买了香皂的话，您购买可乐时就可以享受 $1.50$ 元 / 听的优惠价……诸如此类的优惠方案可概括为：如果您在本店购买了商品 $A$ 的话，您就可以以 $P$ 元 / 件的优惠价格购买商品 $B$（购买的数量不限）。

有趣的是，你需要购买同样一些商品，由于不同的买卖顺序，老板可能会叫你付不同数量的钱。比如你需要一块香皂（原价 $2.50$ 元）、一瓶精制油（原价 $10.00$ 元）、一听可乐（原价 $1.80$ 元），如果你按照可乐、精制油、香皂这样的顺序购买的话，老板会问你要 $13.80$ 元；而如果你按照精制油、香皂、可乐这样的顺序购买的话，您只需付 $13.50$ 元。

该处居民发现 JSOI 集训队的队员均擅长电脑程序设计，于是他们请集训队的队员编写一个程序：在告诉你该小店商品的原价，所有优惠方案及所需的商品后，计算至少需要花多少钱（不允许购买任何不必要的商品，即使这样做可能使花的钱更少）。

inputFormat:
输入文件第一行为一个整数 $n\ (1 \le n \le 50)$，表示小店的商品总数。

接下来是 $n$ 行，其中第 $i+1$ 行由一个实数 $c_i\ (0<c_i \le 1000)$ 和一个整数 $m_i\ (0 \le m_i \le 100)$ 组成，其间由一个空格分隔，分别表示第 $i$ 种商品的原价和所需数量。第 $n+2$ 行又是一个整数 $k\ (1 \le k \le 500)$，表示小店的优惠方案总数。

接着 $k$ 行，每行有二个整数 $A,B(1 \le A,B \le n)$ 和一个实数 $P(0 \le P<1000)$，表示一种优惠方案，即如果您购买了商品 $A$，您就可以以 $P$ 元 / 件的优惠价格购买商品 $B$，$P$ 小于商品 $B$ 的原价。所有优惠方案的 $(A,B)$ 都是不同的。为了方便老板不收分币，所以所有价格都不出现单位分。

outputFormat: 输出只有一个实数，表示最少需要花多少钱。输出实数须保留两位小数。

hint: 数据范围见输入格式


title: 冰精冻西瓜

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

盛夏，冰之妖精琪露诺发现了一大片西瓜地，终于可以吃到美味的冻西瓜啦。

description:
琪露诺是拥有操纵冷气程度的能力的妖精，一天她发现了一片西瓜地。这里有 $n$ 个西瓜，由 $n-1$ 条西瓜蔓连接，形成一个有根树，琪露诺想要把它们冷冻起来慢慢吃。

这些西瓜蔓具有神奇的性质，可以将经过它的冷气的寒冷程度放大或缩小，每条西瓜蔓放大/缩小冷气寒冷程度的能力值为 $w_i$，表示冷气经过它后，寒冷程度值 $x$ 会变为 $ x\times w_i$。每个西瓜也有一个寒冷程度值，炎热的夏日，所有西瓜的寒冷程度值初始都为 $0$。

琪露诺会做出两种动作:

①.对着西瓜 $i$ 放出寒冷程度为 $x$ 的冷气。这股冷气顺着西瓜蔓向“西瓜树”的叶子节点蔓延，冷气的寒冷程度会按照上面的规则变化。遇到一个西瓜连了多条西瓜蔓时，每条叶子节点方向的西瓜蔓均会获得与原先寒冷程度相等的冷气。途径的所有西瓜的寒冷程度值都会加上冷气的寒冷程度值。

**冷气只会向释放点的子树蔓延，不会向根方向蔓延**

⑨.向你询问西瓜 $i$ 的寒冷程度值是多少。

等等，为什么会有⑨？因为笨蛋琪露诺自己也会忘记放了多少冰呢。

所以，帮她计算的任务就这么交给你啦。

inputFormat:
第一行一个整数 $n$，表示西瓜的数量。

西瓜编号为 $1\sim n$，$1$ 为这棵“西瓜树”的根。

接下来 $n-1$ 行，每行有两个整数 $u$、$v$ 和一个实数 $w$，表示西瓜 $u$ 和西瓜 $v$ 之间连接有一条藤蔓，它放大/缩小冷气寒冷程度的能力值为 $w$。

接下来一行一个整数 $m$，表示操作的数量。

接下来 $m$ 行，每行两个或三个整数。

第一个数只能是 $1$ 或 $9$。

如果为 $1$，接下来一个整数 $i$ 和一个实数 $x$，表示对西瓜 $i$ 放出寒冷程度为 $x$ 的冷气。

如果为 $9$，接下来一个整数 $i$，表示询问编号为 $i$ 的西瓜的寒冷程度值。

outputFormat: 对于每个操作⑨，输出一行一个实数，表示对应西瓜的寒冷程度值。

hint:
子任务可能出现如下的特殊性质:

“西瓜树”退化为一条链

输入数据中的实数均保留8位小数，选手的答案被判作正确当且仅当输出与标准答案误差不超过10^-7。请特别注意浮点数精度问题。

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

实际数据中，冷气的寒冷程度x的范围为 [-0.1,0.1]

(样例中的冷气寒冷程度的范围为[1,5])

命题人:orangebird,鸣谢oscar。


title: 签到题 III

background: pj组选手zzq近日学会了求最大公约数的辗转相除法。

description:
类比辗转相除法，zzq定义了一个奇怪的函数：

```cpp
typedef long long ll;
ll f(ll a,ll b)
{
    if(a==b) return 0;
    if(a>b) return f(a-b,b+b)+1;
    else return f(a+a,b-a)+1;
}
```
zzq定义完这个函数兴高采烈，随便输入了两个数，打算计算f值，发现这个函数死循环了...于是zzq定义这个函数递归死循环的情况下f值为0。

现在zzq输入了一个数n，想要求出$\sum_{i=1}^n \sum_{j=1}^n f(i,j)$。

inputFormat: 一行一个数n。

hint:
对于10%的数据，$n \leq 300$。

对于40%的数据，$n \leq 2000$。

对于70%的数据，$n \leq 5 \times 10^5$。

对于100%的数据，$1 \leq n \leq 5 \times 10^{11}$。


title: 总统选举

background:
黑恶势力的反攻计划被小 C 成功摧毁，黑恶势力只好投降。秋之国的人民解放了，举国欢庆。此时，原秋之国总统因没能守护好国土，申请辞职，并请秋之国人民的大救星小 C 钦定下一任。

作为一名民主人士，小 C 决定举行全民大选来决定下一任。为了使最后成为总统的人得到绝大多数人认同，小 C 认为，一个人必须获得超过全部人总数的一半的票数才能成为总统。如果不存在符合条件的候选人，小 C 只好自己来当临时大总统。为了尽可能避免这种情况，小 C 决定先进行几次小规模预选，根据预选的情况，选民可以重新决定自己选票的去向。

由于秋之国人数较多，统计投票结果和选票变更也成为了麻烦的事情，小 C 找到了你，让你帮他解决这个问题。

description:
秋之国共有 $n$ 个人，分别编号为 $1,2,…,n$，一开始每个人都投了一票，范围 $1 \sim n$，表示支持对应编号的人当总统。

共有 $m$ 次预选，每次选取编号 $[l_i,r_i]$ 内的选民展开小规模预选，在该区间内获得超过区间大小一半的票的人获胜。如果没有人获胜，则由小 C 钦定一位候选者获得此次预选的胜利（获胜者可以不在该区间内），每次预选的结果需要公布出来，并且每次会有 $k_i$ 个人决定将票改投向该次预选的获胜者。

全部预选结束后，公布最后成为总统的候选人。

inputFormat:
第一行两个整数 $n,m$，表示秋之国人数和预选次数。

第二行 $n$ 个整数，分别表示编号 $1 \sim n$ 的选民投的票。

接下来 $m$ 行，每行先有四个整数，分别表示 $l_i,r_i,s_i,k_i$，$s_i$ 表示若此次预选无人胜选，视作编号为 $s_i$ 的人获得胜利，接下来 $k_i$ 个整数，分别表示决定改投的选民。

outputFormat: 共 $m+1$ 行，前 $m$ 行表示各次预选的结果，最后一行表示最后成为总统的候选人，若最后仍无人胜选，输出 $-1$。

hint:
对于前 $20 \%$ 的数据，$1 \leq n,m \leq 5000$。

对于前 $40 \%$ 的数据，$1 \leq n,m \leq 50000$，$\sum k_i \leq 50000$。

对于前 $50 \%$ 的数据，$1 \leq n,m \leq {10}^5$，$\sum k_i \leq 2 \times {10}^5$。

对于数据点 6~7，保证所有选票始终在 $1 \sim 10$ 之间。

对于 $100 \%$ 的数据，$1 \leq n,m \leq 5 \times {10}^5$，$\sum k_i \leq 10^6$，$1 \leq l_i \leq r_i \leq n$，$1 \leq s_i \leq n$。


title: 魔法

background:
小 Y 在 AK 曼哈顿 OI 之后，开始研究膜法。

一个精心构造的魔法阵可以产生强大的魔力，但是也有非常严苛的要求。

魔法阵的强度与咒语的数目相关，但是咒语太多可能会产生冲突，小Y当然会解决这个问题啦，但是他想考一考你。

description:
魔法阵由 $N$ 个枢纽组成。

每个枢纽可以有五种属性：金、木、水、火、土。它们之间满足相生相克的关系。

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

一开始，魔法阵中没有咒语。

每次，小 Y 会添加一条咒语，它会要求两个枢纽的属性满足相生/相克的关系。然后你需要回答：是否存在一种为每个枢纽分配一个属性的方案，满足所有的要求。

为了调整法阵，小 Y 有时候需要删除一条写过的咒语。

小 Y 觉得这个问题太简单了，于是他使用改变时间线的能力，让每一次操作在之前某一次操作后形成的魔法阵的基础上进行。

inputFormat:
第一行两个正整数 $N,M$，表示枢纽的个数和操作个数。

接下来 $M$ 行，每行四个数表示一次操作。

第一个数 $k$ 表示这次操作在第 $k$ 次操作结束后的魔法阵上进行，如果 $k=0$，则表示在初始的魔法阵上进行。

第二个数 $t$ 表示操作类型。

- $t=1$：接下来输入 $u,v$，表示加入一条咒语，要求 $u$ 生 $v$。

- $t=2$：接下来输入 $u,v$，表示加入一条咒语，要求 $u$ 克 $v$。

- $t=3$: 接下来输入 $x$，表示删除第 $x$ 次操作加入的咒语。

outputFormat: 对于每一次操作，如果操作后存在为每个枢纽分配一个属性的方案，满足所有的要求，输出 `excited`，否则输出 `naive`。

samples:
excited
excited
excited
naive
excited
excited

hint:
对于 $30\%$ 的数据，满足 $N,M\leq 100$;

对于另 $30\%$ 的数据，满足 $k_i=i-1$;

对于100%的数据，满足 $N,M \leq 100000, 0\leq k_i < i, u_i \neq v_i, 1 \leq u_i,v_i \leq N$，保证所有删除操作都合法。


title: 核心密码B

background:
懒得拷题目背景了，参见核心密码A...

请注意两道题的唯一差别。

description:
令g(n)表示n能表示成几种不同的完全k次方数（k>1），求$f(n)=\sum_{i=2}^n \frac{g(i)}{i}$。

例如，$64=2^6=4^3=8^2$，所以g(64)=3。

inputFormat:
多组询问，第一行一个整数T表示询问组数。

接下来T行，每行一个整数n，表示询问f(n)。

outputFormat:
T行，每行一个实数，表示f(n)，保留十四位小数。

**由于精度误差，你的答案和标准答案差的绝对值在$2 \times 10^{-14}$以内即可通过**


title: 简单的数学题

description:
由于出题人懒得写背景了，题目还是简单一点好。

输入一个整数 $n$ 和一个整数 $p$，你需要求出：

$$\left(\sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)\right) \bmod p$$

其中 $\gcd(a,b)$ 表示 $a$ 与 $b$ 的最大公约数。

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

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

hint:
对于 $20\%$ 的数据，$n \leq 1000$。

对于 $30\%$ 的数据，$n \leq 5000$。

对于 $60\%$ 的数据，$n \leq 10^6$，时限 1s。

对于另外 $20\%$ 的数据，$n \leq 10^9$，时限 3s。

对于最后 $20\%$ 的数据，$n \leq 10^{10}$，时限 4s。

对于 $100\%$ 的数据，$5 \times 10^8 \leq p \leq 1.1 \times 10^9$ 且 $p$ 为质数。


title: 小A的糖果

description:
小 A 有 $n$ 个糖果盒，第 $i$ 个盒中有 $a_i$ 颗糖果。

小 A 每次可以从其中一盒糖果中吃掉一颗，他想知道，要让任意两个相邻的盒子中糖的个数之和都不大于 $x$，至少得吃掉几颗糖。

inputFormat:
输入的第一行是两个用空格隔开的整数，代表糖果盒的个数 $n$ 和给定的参数 $x$。

第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 盒糖的糖果个数 $a_i$。

outputFormat: 输出一行一个整数，代表最少要吃掉的糖果的数量。

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

吃掉第 2 盒中的一个糖果即可。

---

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

第 2 盒糖吃掉 $6$ 颗，第 4 盒吃掉 $2$ 颗，第 6 盒吃掉 $3$ 颗。

---

#### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $n \leq 20$，$a_i, x \leq 100$。
- 对于 $70\%$ 的数据，保证 $n \leq 10^3$，$a_i, x \leq 10^5$。
- 对于 $100\%$ 的数据，保证 $2 \leq n \leq 10^5$，$0 \leq a_i, x \leq 10^9$。


title: [CH弱省胡策R2] TATT

description:
四维空间真是美妙。现在有 $n$ 个四维空间中的点，请求出一条最长的路径，满足任意一维坐标都是单调不降的。

注意路径起点是任意选择的，并且路径与输入顺序无关（路径顺序不一定要满足在输入中是升序）。

**路径的长度是经过的点的数量，任意点只能经过一次。**

inputFormat: 第一行一个整数 $n$。接下来 $n$ 行，每行四个整数 $a_i,b_i,c_i,d_i$。表示四维坐标。

outputFormat: 一行一个整数，表示最长路径的长度。


title: 松江 1843 路

description:
涞坊路是一条长 $L$ 米的道路，道路上的坐标范围从 $0$ 到 $L$，路上有 $N$ 座房子，第 $i$ 座房子建在坐标为 $x_i$ 的地方，其中住了 $r_i$ 人。

松江 1843 路公交车要在这条路上建一个公交站，市政府希望让最多的人得到方便，因此希望所有的每一个的居民，从家到车站的距离的**总和**最短。

公交站应该建在哪里呢？

inputFormat:
第一行输入 $L$、$N$。

接下来 $N$ 行，每行两个整数 $x_i$ 和 $r_i$。

outputFormat: 一个整数，最小的每个人从家到车站的距离的总和。


title: [CTSC2017] 密钥

description:
一个密钥是一个长度为 n = 2k + 1 的字符串，它包含 1 个字母 X、k 个字母 A 和k 个字母 B。例如 k = 3 时，BAXABAB 就是一个密钥。

如下图所示，可以按顺时针顺序把这 2k+1 个字母排成一个圈：

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

在 k 个字母 A 中，有一部分可以定义为 “强的’’。具体来说，从 X 出发顺时针走到某个 A 时，如果途中 A 的数目**严格多于**B的数目，则称此字母 A 为强的。

对于上面的例子来说，顺时针方向从字母 X 数起第 1 个和第 2 个字母 A 是强的，而第 3 个字母 A 不是强的。

一个密钥的**特征值**就是其中包含的强的字母 A 的个数。

天才小朋友 KT 给出了一个结论：

假设 k 个字母 A 所在的位置已经固定，但是剩下的 k 个 B 和 1 个 X 的位置是未知的。（注意，满足这样要求的密钥一共有 k + 1 个，因为字母 X 还剩下 k + 1 个可能的位置。）

可以证明：所有这 k + 1 个可能的密钥的特征值是各不相同的，它们恰好为0, 1, 2, …, k。

下面的图是一个具体的示例，从左到右的四个子图中分别有 3 个，2 个，1 个，0个字母 A 是强的。

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

类似地，如果固定 k 个字母 B 的位置，那满足条件的所有 k + 1 个密钥的特征值也各不相同，恰好为 0, 1, …, k。

现在你需要解决以下三个问题：

1. 给定密钥中所有 A 的位置，当密钥的特征值为 0 时，请问 X 在哪个位置。

2. 给定密钥中所有 A 的位置，当密钥的特征值为 S 时，请问 X 在哪个位置。

3. 给定密钥中所有 B 的位置，当密钥的特征值为 S 时，请问 X 在哪个位置。

注意：字符串的 2k + 1 个字母的位置由 1 到 2k + 1 编号。

【例子 1】

假定 k = 3, S = 2。那么：

当 A 的位置是 {2,4,6} 且特征值为 0 时，X 的位置在 7；

当 A 的位置是 {2,4,6} 且特征值为 2 时，X 的位置在 3；

当 B 的位置是 {2,4,6} 且特征值为 2 时，X 的位置在 5。

【例子 2】

假定 k=9。S=7。那么：

当 A 的位置是 {3,4,5,9,10,12,13,16,19} 且特征值为 0 时，X 的位置在 14；

当 A 的位置是 {3,4,5,9,10,12,13,16,19} 且特征值为 7 时，X 的位置在 18；

当 B 的位置是 {3,4,5,9,10,12,13,16,19} 且特征值为 7 时，X 的位置在 17。

inputFormat:
只包含一组测试数据。

第一行包含一个整数 k，意义如题所述。

第二行包含一个整数 seed，这个数将用于生成一个 k 元集合 P。

第三行包含一个整数 S，意义如题所述。

保证 0 ≤ S ≤ k ≤ 10^7。1 ≤ seed ≤ 10000。

在 cipher/下，包含两个用于生成输入数据的文件 cipher.cpp/pas。其中读入部分已经完成，在数组 p[] 中，若 p[i] = 0，表示 i 不属于集合 P，否则，i 属于集合P。

[百度网盘链接>>   密码：9vr3](http://pan.baidu.com/s/1i55NdWx) 请自行编译

```cpp
#include <stdio.h>
#include <string.h>
int p[20000005];
int seed, n, k, S;
int getrand() {
	seed = ((seed * 12321) ^ 9999) % 32768;
	return seed;
}
void generateData() {
	scanf( "%d%d%d", &k, &seed, &S );
	int t = 0;
	n = k * 2 + 1;
	memset(p, 0, sizeof(p));
	for( int i = 1; i <= n; ++i ) {
		p[i] = (getrand() / 128) % 2;
		t += p[i];
	}
	int i = 1;
	while( t > k ) {
		while ( p[i] == 0 ) ++i;
		p[i] = 0;
		--t;
	}
	while( t < k ) {
		while( p[i] == 1 ) ++i;
		p[i] = 1;
		++t;
	}
}
int main() {
	generateData();
	return 0;
}
```

outputFormat:
输出三行，每行一个数，依次对应问题描述中的三个子问题的答案。

即：
1. 第一个数表示当 k 元集合 P 代表 A 的位置且特征值为 0 时 X 的位置。

2. 第二个数表示当 k 元集合 P 代表 A 的位置且特征值为 S 时 X 的位置。

3. 第三个数表示当 k 元集合 P 代表 B 的位置且特征值为 S 时 X 的位置。

hint:
【样例解释】

第一个样例中, P 数组为 1 的元素的下标分别为 5, 6, 7, 8, 9。

【数据范围与约定】

对于 30% 的数据，k ≤ 10^3。

对于 50% 的数据，k ≤ 10^5。

对于 100% 的数据，k ≤ 10^7。

对于每个测试点, 得分为以下三部分得分之和：

1. 如果第一问回答正确，你将获得 3 分。

2. 如果第二问回答正确，你将获得 4 分。

3. 如果第三问回答正确，你将获得 3 分。

**如果你仅仅知道部分答案，请也务必按此格式要求输出三个数。否则你可能会因格式错误无法得分。**


title: [CTSC2017] 网络

description:
一个一般的网络系统可以被描述成一张无向连通图。图上的每个节点为一个服务器，连接服务器与服务器的数据线则看作图上的一条边，边权为该数据线的长度。两个服务器之间的通讯距离定义为其对应节点之间最短路的长度。

现在，考虑一个当前图结构为树的网络系统。你作为该网络系统的管理员，被要求在这个系统中新加入一条给定长度的数据线。数据线可以连在任意两个服务器上。你的任务是，求出在所有合法的方案中，通讯距离最远的两个服务器之间的最小距离。

inputFormat:
输入包含多组数据。对于每组数据，输入的第一行包含二个正整数 N, L, 其中 N 表示服务器个数，L 为新加入数据线的长度。

接下来 n − 1 行，第 i 行有三个正整数 ai, bi, li，表示有一条长度为 li 的数据线连接服务器 ai, bi。服务器的编号为 1 ∼ N。

输入的末尾以两个 0 作为结束。

outputFormat: 对于每组数据，输出一行一个整数，描述在所有合法的方案中，通讯距离最远的两个服务器之间的最小距离。

hint:
一共有 20 个测试点。编号为 1 ∼ 20。每个测试点为 5 分。

保证在任一测试点中，数据的组数不会超过 15，且所有数据的 N 之和不超过数据范围中标明的 N 的最大值的 5 倍。

保证所有的输入数据均为不超过 2^31 − 1 的非负整数，保证 N ≥ 1。

保证数据合法。

对于给定的测试点，其限制条件如下表所示。

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


title: [CTSC2017] 游戏

description:
小 R 和室友小 B 在寝室里玩游戏。他们一共玩了 n 局游戏，每局游戏的结果要么是小 R 获胜，要么是小 B 获胜。

第 1 局游戏小 R 获胜的概率是 $p_1$，小 B 获胜的概率是 1 − $p_1$。除了第一局游戏之外，每一局游戏小 R 获胜的概率与上一局游戏小 R 是否获胜有关。

具体来说：

1. 如果第 $i − 1$（$1 < i ≤ n$）局游戏小 R 获胜，那么第 $i$ 局游戏小 R 获胜的概率为 $p_i$，小 B 获胜的概率为 $1 − p_i$。

2. 如果第 $i − 1$（$1 < i ≤ n$）局游戏小 B 获胜，那么第 $i$ 局游戏小 R 获胜的概率为 $q_i$，小 B 获胜的概率为 $1 − q_i$。

小 D 时常过来看小 R 和小 B 玩游戏，因此他知道某几局游戏的结果。他想知道在他已知信息的条件下，小 R 在 $n$ 局游戏中总共获胜的局数的期望是多少。

小 D 记性不太好，有时他会回忆起某局游戏的结果，并把它加入到已知信息中；

有时他会忘记之前某局游戏结果，并把它从已知信息中删除。你的任务是：每当小 D 在已知信息中增加或删除一条信息时，根据小 D 记得的已知信息，帮助小 D 计算小 R 在 $n$ 局游戏中总共获胜局数的期望是多少。

需要注意的是：如果小 D 忘了一局游戏的结果，之后又重新记起，两次记忆中的游戏结果不一定是相同的。你不需要关心小 D 的记忆是否与实际情况相符，你只需要根据他的记忆计算相应的答案。

inputFormat:
第一行两个正整数 $n, m$ 和一个字符串 $\textrm{type}$。表示小 R 和小 B 一共玩了 $n$ 局游戏，

小 D 一共进行了 $m$ 次修改已知信息的操作，该数据的类型为 $\textrm{type}$。$\textrm{type}$ 字符串是为了能让大家更方便地获得部分分，你可能不需要用到这个输入，其具体含义见【限制与约定】。

接下来 $n$ 行，第 1 行包含一个实数 $p_1$，表示第一局比赛小 R 获胜的概率是 $p_1$。第 $i$（$1 < i ≤ n$）行包含两个实数 $p_i, q_i$。表示在第 $i − 1$ 局游戏小 R 获胜的情况下，第 $i$ 局游戏小 R 获胜的概率是 $p_i$；$q_i$ 表示在第 $i − 1$ 局游戏小 B 获胜的情况下，第 $i$ 局游戏小 R 获胜的概率是 $q_i$。

接下来 $m$ 行，每行描述一个小 D 已知信息的变化，操作分为两类。

1. `add i c` 表示小 D 回忆起了第 $i$ 局比赛的结果，并把它加入到已知信息中。若 $c = 0$ 表示第 $i$ 局比赛小 B 获胜，若 $c = 1$ 表示第 $i$ 局比赛小 R 获胜。数据保证 $i, c$ 均为整数且 $1 ≤ i ≤ n, 0 ≤ c ≤ 1$，如果这个操作不是第一个操作，保证在上一个操作结束后的已知信息中没有第 $i$ 局比赛的结果。

2. `del i` 表示小 D 忘记了第 $i$ 局比赛的结果，并把它从已知信息中删除。数据保证 $i$ 是整数且 $1 ≤ i ≤ n$，保证在上一个操作结束后的已知信息中有第 $i$ 局比赛的结果。

outputFormat: 对于每个操作，输出一行实数，表示操作结束后，在当前已知信息的条件下，小 R 在 $n$ 局游戏中总共获胜的局数的期望是多少。

hint:
【评分标准】

如果你的答案与正确答案的绝对误差在 $10^{-4}$ 以内，则被判定为正确。

如果你的所有答案均为正确，则得满分，否则得 $0$ 分。

请注意输出格式：每行输出一个答案，答案只能为一个实数。每行的长度不得超过 $50$。错误输出格式会被判定为 $0$ 分。

【限制与约定】

对于 $100\%$ 的数据，$1 ≤ n ≤ 200000$，$1 ≤ m ≤ 200000$，$0 < p_i, q_i < 1$。

对于 $100\%$ 的数据，输入保留最多四位小数。

本题共有 $20$ 个数据点，每个数据点 $5$ 分, 每个测试点的具体约定如下表：

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

【小 R 教你学数学】

你可. 能. 会用到以下公式

1. 条件概率的计算方法

我们记 $p(A|B)$ 表示在已知事件 $B$ 发生时事件 $A$ 发生的概率，条件概率可以用以下公式计算：

$p(A|B)=\frac {p(AB)}{p(B)}$

其中 $p(AB)$ 表示事件 $B$ 和事件 $A$ 同时发生的概率，$p(B)$ 表示事件 $B$ 发生的概率。

2. 贝叶斯公式 (bayes)

由条件概率的计算方法，我们容易得到贝叶斯公式

$p(A|B)=\frac {p(B|A)p(A)}{p(B)}$

3. 全概率公式

如果随机变量 $x$ 有 $k$ 个取值，分别为 $x_1, x_2,\ldots , x_k$ 那么

$p(A)=\sum^{k}_{i=1} {p(A|x=x_i)p(x=x_i)}$

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

【温馨提示】

在本题中，如果你希望获得全部的分数，你可能需要考虑由于浮点数运算引入的误差。只使用加法和乘法运算不会引入太大的误差，但请谨慎使用减法和除法。

1. 两个大小相近的数相减可以引入非常大的相对误差。

2. 如果一个矩阵的行列式值非常小，那么求解该矩阵的逆可以带来相当大的误差。

当然，如果你的算法在数学上是正确的，但没有考虑浮点数运算的误差问题，可能仍然可以获得一部分的分数。


title: [WC2017] 排序

background: **本题暂时只能使用代码提交。**

description:
牛牛最近学习了排序的相关知识。他对排序算法的运行效率产生了浓厚的兴趣并对此展开了一系列的研究。

为了优化排序的运行时间，牛牛找到了来参加冬令营的你，希望你帮助他设计一台计算机进行排序（**升序**）。

这台计算机的设计方法如下：

- 需要进行排序的序列存储在大小为 $n$ 的数组 $Q$ 中。

- 进行计算的最小单元是比较器，一个比较器可以用一个三元组 $(i,j,t)$ 表示（$i,j,t$ 均为整数），其中 $1 \le i<j \le n$，$1 \le t \le m$。它的功能是：在时刻 $t$ 比较 $Q_{i}$ 与 $Q_{j}$ 的大小，若 $Q_{i}>Q_{j}$，就交换 $Q_{i}$ 与 $Q_{j}$ 的值，否则什么也不做。

- 若要让计算机**工作**（**但不一定解决问题**），则需要任意两个比较器之间**不能发生冲突**。两个比较器 $(A,B,S)$ 与 $(C,D,T)$ **会发生冲突**当且仅当 $A,B,C,D$ 中有**至少两个相等的数**，**并且** $S=T$。例如：比较器 $(1,3,1)$ 和 $(2,4,1)$ 不会发生冲突，而比较器 $(1,2,3)$ 和 $(2,3,3)$ 会发生冲突。

在运行时，这台计算机中的每个比较器都会按照预先设定好的参数在指定的时间进行相应的操作。这台计算机运行时需要消耗的时间为所有的比较器中参数 $t$ 的**最大值** $w$，该值越小意味着运行时间越短。

为了检验你设计的计算机，牛牛提供了测试数据。**每组测试数据**包含 $q$ 个**问题**，即 $q$ 个长度为 $n$ 的排列 $P$。请你为**每组测试数据**设计一台运行时间不超过 $m$ 的计算机（否则计算机将**超时**），使得这台计算机能对**测试数据中所有的** $P$ 排序。

inputFormat:
为了方便你区分不同的子任务，每个输入文件第一行为一个整数 $I$，表示当前测试点的编号。

第二行一个整数 $J$ 表示**这个测试点**中的**测试数据**组数。

**每组测试数据**第一行三个整数 $q,n,m$。

接下来 $q$ 行每行 $n$ 个整数，描述一个 $1$ 到 $n$ 的排列 $P$。

**数据保证有解。**

outputFormat:
对于**每组测试数据**，第一行输出一个整数 $f$ 表示你设计的计算机中比较器个数。

接下来 $f$ 行，每行 $3$ 个整数 $i,j,t$，描述你的计算机的一个比较器 $(i,j,t)$。

若 $i,j \notin [1,n]$，则计算机**不能工作**。

hint:
### 输入数据及 checker 下载

在[这里](http://pan.baidu.com/s/1miBgJ3q)下载。

**警告：所有数据（包括 SPJ）均为 Windows（64 位）格式。**

### 关于 UKE 的问题

由于本题 SPJ 的时间复杂度较高，请用比较器个数尽量少的方案来通过该题，否则可能出现 SPJ TLE 的问题，导致评测结果为 UKE。

SPJ 的时间复杂度为：
$$O\left ( \sum_{i=1}^{J}q_i\times (n_i+f_i) \right )$$

### 评分方式

共 $8$ 个**测试点**，分别有 $6,12,13,10,10,10,19,20$ 组**测试数据**，共 $100$ 组，**每组测试数据满分 $1$ 分。**

在**每组测试数据**中，若 $1 \le w\le m$ 且 $f\le 10^{6}$，比较器之间不会发生冲突，计算机能对**测试数据中所有的** $P$ 排序，则该**测试数据**得分，否则不得分。

如果你输出了不足 $J$ 个计算机，那么我们将默认你输出的第 $i$ 个计算机对应第 $i$ 组测试数据。

如果你的输出不符合格式要求，我们不保证你能得到该测试点的分数。

### 数据特性

对于 $100\%$ 的数据，$1 \le m \le 150$，$J \in \{1,6,10,12,13,19,20\}$，$0 \le I \le 8$，其余请自行下载数据查看。

这里给出部分数据的部分特性：

- **测试点 $4$（$10$ 分）** 中，对于输入的每一个排列 $P$，它每一个环的大小都互不相同。循环可以理解为，将一个长度为 $n$ 的排列 $P$ 看成一张 $n$ 个点 $n$ 条边的无向图（**基环森林**），其中 $i$ 号点和 $P_{i}$ 号点之间有一条边，这张图中的**每一个联通块都是一个环**（**即该图由若干个环组成**），如 $P=\{\color{blue}1,\color{green}3,2,\color{purple}6,\color{red}10,\color{purple}7,4,\color{red}5,8,9\color{black}\}$（**每个颜色代表一个环**）。

- **测试点 $7$（$19$ 分）** 中，对于输入的每一个排列 $P$，都存在若干个互不相交的区间 $[l_i,r_i]$，使得在对每一个区间 $[l_i,r_i]$ 循环左移一次后，数组有序，如 $P=\{\color{blue}3,1,2,\color{green}7,4,5,6,\color{purple}8,\color{red}9\color{black}\}$（**每个颜色代表一个区间**）。循环左移的例子为：$(1,2,3,4)$ 循环左移一步为 $(2,3,4,1)$。
- **测试点 $7$ 的前 $8$ 组测试数据（$8$ 分）** 中，满足对于输入的每一个排列 $P$，都存在整数 $i$，使得对区间 $[1,i]$ 循环左移一次后，数组有序，如 $P=\{\color{red}5,1,2,3,4\color{black},6,7,8\}$。

### 测试你的输出

我们在文件中提供了 `checker`（**Windows x64**）来检测你的输出的得分，使用这个工具的方法为：

`checker.exe sort<I>.in sort<I>.out sort<I>.out`

其中 $I$ 为**测试点**编号（**输入时不带尖括号**），`checker.exe` 为校验器，`sort<I>.in` 为题目提供的输入文件，`sort<I>.out` 为你的对应的输出文件（**输入两遍**）。运行此命令将给出以 `sort<I>.in` 为输入文件，以 `sort<I>.out` 为输出文件时你的得分情况。

在你调用这个程序后，`checker` 将根据你给出的输出文件给出每一个**测试数据**的测试结果，其中包括（如果你输出的计算机同时出现了多种错误，将会返回其中一种）：

| 测试结果 | 含义 |
| :----------- | :----------- |
| `FAIL!` | 未知错误：SPJ 运行失败。 |
| `Input error!` | 输入文件非法：你改动了输入文件。 |
| `The number of the comparators is invalid!` | 检测到 $f>10^6$。 |
| `Unexpected EOF` | 给出的计算机不完整。 |
| `The running time of the comparator should be in [1, 150]` | 检测到 $w \notin [1,150]$。 |
| `Invalid sorting network!` | 给出的计算机不能工作。 |
| `The answer is incorrect` | 给出的计算机不能解决所有问题。 |
| `Invalid! m=(X) but M=(X)` | 给出的计算机超时：$w=Y,m=X$（$Y>X$）。 |
| `Correct! m=(X) and M=(X)` | 给出的计算机正确：$w=Y,m=X$（$Y\le X$）。 |

最后，如果 `checker` 正常运行到了最后，将会额外输出一行 `Total points: (Z)`，表示你在**这个测试点**一共得了 $Z$ 分。

### 提醒

**请注意「测试点」、「测试数据」和「问题」的区别！**

**请牢记下面的图示：**

- 整道题目

  - 测试点 $1$

    - 测试数据 $1.1$

      - 问题 $1.1.1$

    - 测试数据 $1.2$

      - 问题 $1.2.1$

    - 测试数据 $1.3$

      - 问题 $1.3.1$

      - 问题 $1.3.2$

      - ……

      - 问题 $1.3.5$

    - ……

    - 测试数据 $1.6$

  - 测试点 $2$

  - ……

  - 测试点 $8$


title: [APIO2017] 斑斓之地

background: 本题原为交互题，这里采用传统题形式进行评测。

description:
在很久以前的黄金时代，澳大利亚的土地是矩形的，它可以被划分成 $R$ 行 $C$ 列的网格状，行的编号从北到南依次为 $1$ 到 $R$ ，列的编号从西到东依次为 $1$ 到 $C$，$(r,c)$ 表示第 $r$ 行第 $c$ 列的土地。一天，伟大的彩虹蛇从 $(s_r,s_c)$ 出发在澳大利亚的土地上移动，彩虹蛇连续进行了 $M$ 次移动，每次它会向正北 (`N`)、正南 (`S`)、正东 (`E`) 或正西 (`W`) 方向移动一格，其经过的所有的格子（包括起点和终点）都会变成河流。保证在任一时刻，彩虹蛇都不会离开这片 $R$ 行 $C$ 列的矩形土地。

数百万年之后，你想购买一块矩形区域纪念伟大的彩虹蛇。你想给所购买矩形区域内每一块不是河流的格子都染上颜色，要求相邻的格子颜色必须相同，两个格子相邻当且仅当两个格子有一条公共边，你所购买区域之外的格子无须染色。

现在给出彩虹蛇 $M$ 次移动的方向，你有 $Q$ 个购买矩形区域的方案，问每个方案最多能够将土地染上多少种不同的颜色。

inputFormat:
第一行：四个整数 $R$，$C$，$M$ 和 $Q$；

第二行：两个整数 $s_r$ 和 $s_c$；

第三行: 一个包含 $M$ 个字符的字符串 $S$，每个字符是 `N`、`S`、`E`、`W` 之一（如果 $M=0$ 则此行留空）；

第四到 $Q+3$ 行: 每行四个整数 $a_r,a_c,b_r$ 和 $b_c$，表示你购买的土地范围，左上角是 $(a_r,a_c)$，右下角是 $(b_r,b_c)$。

outputFormat: 对于每个询问做出回答，输出最多能够将土地染上多少种不同的颜色。


title: [APIO2017] 商旅

description:
在广阔的澳大利亚内陆地区长途跋涉后，你孤身一人带着一个背包来到了科巴。你被这个城市发达而美丽的市场所深深吸引，决定定居于此，做一个商人。科巴有$N$个集市，集市用从$1$到$N$的整数编号，集市之间通过$M$条单向道路连接，通过每条道路都需要消耗一定的时间。

在科巴的集市上，有$K$种不同的商品，商品用从$1$到$K$的整数编号。每个集市对每种商品都有自己的定价，买入和卖出商品的价格可以是不同的。并非每个集市都可以买卖所有的商品：一个集市可能只提供部分商品的双向交易服务；对于一种商品，一个集市也可能只收购而不卖出该商品或只卖出而不收购该商品。如果一个集市收购一种商品，它收购这种商品的数量是不限的，同样，一个集市如果卖出一种商品，则它卖出这种商品的数量也是不限的。

为了更快地获得收益，你决定寻找一条盈利效率最高的环路。环路是指带着空的背包从一个集市出发，沿着道路前进，经过若干个市场并最终回到出发点。在环路中，允许**多次**经过同一个集市或同一条道路。在经过集市时，你可以购买或者卖出商品，一旦你购买了一个商品，你需要把它装在背包里带走。由于你的背包非常小，任何时候你最多只能持有一个商品。在购买一个商品时，你不需要考虑你是否有足够的金钱，但在卖出时，需要注意只能卖出你拥有的商品。

从环路中得到的收益为在环路中卖出商品得到的金钱减去购买商品花费的金钱，而一条环路上消耗的时间则是依次通过环路上所有道路所需要花费的时间的总和。环路的盈利效率是指从环路中得到的收益除以花费的时间。需要注意的是，一条没有任何交易的环路的盈利效率为$0$。

你需要求出所有**消耗时间为正数**的环路中，盈利效率**最高**的环路的盈利效率。答案**向下取整**保留到整数。如果没有任何一条环路可以盈利，则输出 0 。

inputFormat:
从标准输入中读取输入数据。

第一行包含3个正整数，$N$、$M$和$K$，分别表示集市数量、道路数量和商品种类数量。

接下来的$N$行，第$i$行中包含$2K$个整数$B_{i,1},S_{i,1},B_{i,2},S_{i,2},\dots B_{i,K},S_{i,K}$描述一个集市。对于任意的$1 \leq j \leq K$, 整数$B_{i,j}$和$S_{i,j}$分别表示在编号为$i$的集市上购买、卖出编号为$j$的商品时的交易价格。如果一个交易价格为$-1$，则表示这个商品在这个集市上不能进行这种交易。

接下来$M$行，第$p$行包含 3 个整数，$V_p$、$W_p$和$T_p$, 表示存在一条从编号为$V_p$的市场出发前往编号为$W_p$的市场的路径花费$T_p$分钟。

outputFormat:
输出到标准输出中。

输出包含一个整数，表示盈利效率最高的环路盈利效率，答案**向下取整**保留到整数。如果没有任何一条环路可以盈利，则输出 0 。

hint:
## 样例解释

在样例中，我们考虑下面两条环路，“1 - 2 - 3 - 1” 和 “1 - 4 - 3 - 1”。

考虑环路 “1 - 2 - 3 - 1” ：这条环路消耗的总时间是$(3+3+1)=7$分钟。在这条环路中，最佳的交易方式是：在编号为 1 的集市中购买编号为 2 的商品（花费的金钱为 5）；在编号为 2 的集市中卖出编号为 2 的商品（得到的金钱为 15），然后立即购买编号为 1 的商品（花费的金钱为 6）；带着编号为 1 的商品经过编号为 3 的集市，在回到编号为 1 的城市后卖出（得到的金钱为 9）。在这个环路中，总盈利为$-5+15-6+9=13$ 。 这个环路的盈利效率为$13/7$ ，向下取整后为 1 。

考虑环路 “1 - 4 - 3 - 1” ：这条环路消耗的总时间是$(1+1+1)=3$分钟。在这条环路中，最佳的交易方式是：在编号为 1 的集市中购买编号为 2 的商品（花费的金钱为 5）；在编号为 4 的集市中卖出编号为 2 的商品（得到的金钱为 11）；然后经过编号为 3 的集市回到编号为 1 的城市。在这个环路中，总盈利为$-5+11=6$。 这个环路的盈利效率为$6/3$，向下取整后为 2 。

综上所述，盈利效率最高的环路的盈利效率为 2 。

## 子任务

在所有的子任务中，保证$1 \leq N \leq 100$，$1 \leq M \leq 9900$，$1 \leq K \leq 1000$, 如果在编号为$i (1 \leq i \leq N)$的集市中，编号为$j (1 \leq j \leq K)$的商品既可以购买又可以卖出，则$0 \leq S_{i,j} \leq B_{i,j} \leq 1000000000$。对于编号为$p (1 \leq p \leq M)$的道路，保证$V_p \not= W_p$且$1 \leq T_p \leq 10000000$。 不存在满足$1 \leq p < q \leq M$的$p$，$q$使得$(V_p, W_p)=(V_q, W_q)$。

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


title: 文艺数学题

background: 小Y在AK曼哈顿OI，CTSC和APIO之后，开始研究数学题。

description:
小Y有一张N个点，M条边的无向图（**可能有重边、自环**），每条边都有一个权值w。

你需要计算：所有**生成树的边权的最大公约数**之和，具体操作见样例。

由于答案可能很大，需要**对1000000007取模**。

inputFormat:
第一行两个正整数N，M，表示点数和边数。

接下来M行，每行三个正整数u，v，w，表示一条边连接u和v，权值为w。

outputFormat: 输出一行一个数，表示答案**对1000000007取模**的值。


title: [SDOI2017] 龙与地下城

description:
小 Q 同学是一个热爱学习的人，但是他最近沉迷于各种游戏，龙与地下城就是其中之一。

在这个游戏中，很多场合需要通过掷骰子来产生随机数，并由此决定角色未来的命运，因此骰子堪称该游戏的标志性道具。

骰子也分为许多种类，比如 $4$ 面骰、$6$ 面骰、$8$ 面骰、$12$ 面骰、$20$ 面骰，其中 $20$ 面骰用到的机会非常多。当然，现在科技发达，可以用一个随机数生成器来取代真实的骰子，所以这里**认为骰子就是一个随机数生成器**。

在战斗中，骰子主要用来决定角色的攻击是否命中，以及命中后造成的伤害值。举个例子，假设现在已经确定能够命中敌人，那么 $YdX$（也就是掷出 $Y$ 个 $X$ 面骰子之后所有骰子显示的数字之和）就是对敌人的基础伤害。在敌人没有防御的情况下，这个基础伤害就是真实伤害。

众所周知，骰子显示每个数的概率应该是相等的，也就是说，对于一个 $X$ 面骰子，显示 $0, 1, 2,\dots ,X−1$ 中每一个数字的概率都是 $\dfrac {1}{X}$。

更形式化地说，这个骰子显示的数 $W$ 满足离散的均匀分布，其分布列为

| $H$ | $0$ | $1$ | $2$ | $\cdots$ | $X-1$ |
| :--: | :--: | :--: | :--: | :--: | :--: |
| $P$ | $\dfrac {1}{X}$ | $\dfrac {1}{X}$ | $\dfrac {1}{X}$ | $\cdots$ | $\dfrac {1}{X}$ |

除此之外还有一些性质：

- $W$ 的**一阶原点矩**（**期望**）为

$$v_1(W)=E(W)=\sum_{i=0}^{X-1}i\cdot P(W=i)=\frac {X-1}{2}$$

- $W$ 的**二阶中心矩**（**方差**）为

$$\mu_2(W)=E((W-E(W))^2)=\sum_{i=0}^{X-1}(i-E(W))^2\cdot P(W=i)=\frac {X^2-1}{12}$$

言归正传，现在小 Q 同学面对着一个生命值为 A 的没有防御的敌人，能够发动一次必中的 $YdX$ 攻击，显然只有造成的伤害不少于敌人的生命值才能打倒敌人。但是另一方面，小 Q 同学作为强迫症患者，不希望出现 overkill，也就是造成的伤害大于 $B$ 的情况，因此**只有在打倒敌人并且不发生 overkill 的情况下小 Q 同学才会认为取得了属于他的胜利**。

因为小 Q 同学非常谨慎，他会进行 $10$ 次模拟战，每次给出敌人的生命值 $A$以及 overkill 的标准 $B$，他想知道此时取得属于他的胜利的概率是多少，你能帮帮他吗？

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

对于每组测试数据：

第一行是两个整数 $X,Y$，分别表示骰子的面数以及骰子的个数；

接下来 $10$ 行，每行包含两个整数 $A,B$，分别表示敌人的生命值 $A$ 以及 overkill 的标准 $B$。

outputFormat:
对于每组测试数据，输出 $10$ 行，对每个询问输出一个实数，要求绝对误差不超过 $0.013\, 579$。

也就是说，记输出为 $a$，答案为 $b$，若满足 $|a-b|\leq 0.013\,579$，则认为输出是正确的。


title: [SDOI2017] 苹果树

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

description:
夏天近了，又到了恋爱的季节，小Q家门前的苹果树上结满了红红圆圆的苹果。

这株苹果树是一个有着$n$个结点的有根树，其中结点被依次编号为$1$至$n$。$1$号结点为根，其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些苹果，第$i$个结点上有$a_i (a_i > 0)$个苹果，每取走其中一个苹果就可以得到$v_i (v_i > 0)$的幸福度（若在这个结点取走$k \leq a_i$个苹果，则可以收获$kv_i$的幸福度）。如果在一个结点取走了至少一个苹果，则必须要在其父结点处取走至少一个苹果。

现在，给定正整数$k$，请从树上取走若干苹果。如果总计取走了$t$个苹果，且所有取了至少一个苹果的那些结点的最大深度为$h$（这里规定根结点的深度为$1$），则要求$t-h \leq k$。问最大可以收获多少的幸福度？（这些幸福度全都归属于恋爱中的小Q。）

inputFormat:
本题有多组测试数据，输入的第一行给定整数$Q$，表示有$Q$组数据。之后依次给出$Q$组数据。

对于每一组数据来说，第一行包含两个整数$n$和$k$。

之后$n$行，每行给出三个整数，描述了每一个结点。其中第$i$行的第一个整数给出了$i$的父结点标号

（如果$i = 1$，则其父结点为$0$），第二个整数为$a_i$，第三个整数为$v_i$。

outputFormat:
输出一共有$Q$行，对应了$Q$组数据。

对于每一组数据，输出一个整数，表示最大可以收获的幸福度。

hint:
有$10\%$的数据，满足$nk \leq 3000000$且给定的树的高度为$2$。

有$20\%$的数据，满足$nk \leq 25000000$且给定的树的高度为$2$。

有$20\%$的数据，满足$nk \leq 25000000$且所有$a_i$均为$1$。

还有$20\%$的数据，满足$nk \leq 3000000$，没有上述额外限制。

对于$100\%$的数据，满足$1 \leq Q \leq 5$；$1 \leq n \leq 20000$；$1 \leq k \leq 500000$；$1 \leq nk \leq 25000000$；$1 \leq a_i \leq 10^8$；$1 \leq v_i \leq 100$。


title: [SDOI2017] 切树游戏

background: hack数据 by boshi & Remmina

description:
小Q是一个热爱学习的人，他经常去维基百科学习计算机科学。

就在刚才，小Q认真地学习了一系列位运算符，其中按位异或的运算符$\oplus$对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律，即$i \oplus j = j \oplus i$。

他发现，按位异或可以理解成被运算的数字的二进制位对应位如果相同，则结果的该位置为$0$，否则为$1$，例如：$1(01) \oplus 2(10) = 3(11)$。

他还发现，按位异或可以理解成参与运算的数字的每个二进制位都进行了不进位的加法，例如：$3(11) \oplus 3(11) = 0(00)$。

现在小Q有一棵$n$个结点的无根树$T$，结点依次编号为$1$到$n$，其中结点$i$的权值为$v_i$。

定义一棵树的价值为它所有点的权值的异或和，一棵树$T$的连通子树就是它的一个连通子图，并且这个图也是一棵树。

小Q想要在这棵树上玩切树游戏，他会不断做以下两种操作：

- `Change x y` 将编号为$x$的结点的权值修改为$y$。

- `Query k` 询问有多少棵$T$的非空连通子树，满足其价值恰好为$k$。

小Q非常喜(bu)欢(hui)数学，他希望你能快速回答他的问题，你能写个程序帮帮他吗？

inputFormat:
第一行包含两个正整数$n$ , $m$，分别表示结点的个数以及权值的上限。

第二行包含$n$个非负整数$v_1, v_2,\dots , v_n$，分别表示每个结点一开始的权值。

接下来$n-1$行，每行包含两个正整数$a_i , b_i$，表示有一条连接$a_i$和$b_i$的无向树边。

接下来一行包含一个正整数$q$，表示小Q操作的次数。

接下来$q$行每行依次表示每个操作。

outputFormat: 输出若干行，每行一个整数，依次回答每个询问。因为答案可能很大，所以请对$10007$取模输出。

samples:
4 4
2 0 1 3
1 2
1 3
1 4
12
Query 0
Query 1
Query 2
Query 3
Change 1 0
Change 2 1
Change 3 3
Change 4 1
Query 0
Query 1
Query 2
Query 3

hint:
对于$100\%$的数据，$1 \leq a_i,b_i,x \leq n$ , $0 \leq v_i,y,k < m$，修改操作不超过$10000$个。

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


title: [SDOI2017] 天才黑客

background: $\text{SD0062}$ 号选手小 Q 同学为了偷到 SDOI7012 的试题，利用高超的黑客技术潜入了 SDOI 出题组的内联网的中央控制系统，然而这个内联网除了配备有中央控制系统，还为内联网中的每条单向网线设定了特殊的通信口令，这里通信口令是一个字符串，不同网线的口令可能不同。这让小 Q 同学感觉有些棘手，不过这根本难不倒他，很快他就分析出了整个内联网的结构。

description:
内联网中有 $n$ 个节点（从 $1$ 到 $n$ 标号）和 $m$ 条**单向**网线，中央控制系统在第 $1$ 个节点上，每条网线单向连接内联网中的某两个节点，从 $1$ 号节点出发经过若干条网线总能到达其他任意一个节点。每个节点都可以运行任意的应用程序，应用程序会携带一条通信口令，当且仅当程序的口令与网线的口令相同时，程序才能通过这条网线到达另一端的节点继续运行，并且通过每条网线都需要花费一定的时间。

每个应用程序可以在任意一个节点修改通信口令，修改通信口令花费的时间可以忽略不计，但是为了减小修改量，需要先调用一个子程序来计算当前程序的口令和网线的口令的最长公共前缀（记其长度为 $\mathrm{len}$），由于获取网线的口令的某个字符会比较耗时，调用一次这个子程序需要花费 $\mathrm{len}$ 个单位时间。

除此之外，小 Q 同学还在中央控制系统中发现了一个字典，每条网线的口令都是字典中的某个字符串。具体来说，这个字典是一棵 $k$ 个节点（从 $1$ 到 $k$ 标号）的有根树，其中根是第 $1$ 个节点，每条**边**上有一个字符，字符串 $S$ 在字典中当且仅当存在某个点 $u$ 使得从根节点出发往下走到 $u$ 的这条路径上的字符顺次拼接构成 $S$。

现在小 Q 同学在 $1$ 号节点同时开启了 $(n-1)$ 个应用程序，这些应用程序同时运行且互不干扰，每个程序的通信口令都为空，他希望用最短的时间把这些程序分别发送到其他节点上，你需要帮小 Q 同学分别计算出发送到第 $i$（$i=2,3,\dots ,n$）个节点的程序完成任务的最短时间。

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

对于每组测试数据，第一行是三个整数 $n,m,k$，分别表示内联网的节点数、内联网的网线条数、字典树的节点数，

接下来 $m$ 行，每行包含四个整数 $a_i,b_i,c_i,d_i$，表示沿着这条网线可以从第 $a_i$ 个节点花费 $c_i$ 个单位时间到达第 $b_i$ 个节点，网线的口令是由从字典树的根到 $d_i $这个点的路径上的字符顺次拼接构成的字符串（**可能为空**），需要注意的是**这个内联网可能有自环和重边**。

接下来 $(k-1)$ 行，每行包含三个整数 $u_i,v_i,w_i$，表示字典树上有一条 $u_i \rightarrow v_i$ 的边，边上有字符 $w_i$，保证给出的边构成一棵以 $1$ 为根的有根树，并且每个点连出去的边上的字符互不相同。

outputFormat: 对于每组测试数据，输出 $(n-1)$ 行，第 $i$ 行表示发送到第 $(i+1)$ 个节点的程序完成任务的最短时间。

hint:
样例解释：下图展示了样例中内联网的结构。字符串用红色字体标出。

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

记 $\mathrm{LCP}(S,T)$ 为字符串 $S,T$ 的**最长公共前缀**的长度。例如，$\mathrm{LCP}(\texttt{\textcolor{red}{starry}killer},\texttt{\textcolor{red}{starry}dust})=6$。记 $\epsilon$ 为空字符串。

从 $1$ 到 $3$ 的一条可行路径是 $1 \rightarrow 2 \rightarrow 3$，所需时间是$(2 + \mathrm{LCP}(\epsilon , \texttt{1112})) + (2 +\mathrm{LCP}(\texttt{1112} ,\texttt{1112})) = 8$。

但这条路径不是最优的，最优路径是 $1 \rightarrow 2 \rightarrow 4 \rightarrow 2 \rightarrow 3$。

| 测试点编号 | $n\le $ | $m\le $|  $k\le$ | 备注 |
| :--: | :--: | :--: | :--: | :--: |
| $1\sim 5$ | $5\,000$ | $5\,000$ | $20\,000$ | - |
| $6\sim 14$ | $50\,000$ | $50\,000$ | $20\,000$ | $nk\le 200\,000$ |
| $15\sim 20$ | $50\,000$ | $50\,000$ | $20\,000$ | - |

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

- $T \leq 10$；
- $2 \leq n \leq 50000$，$1 \leq m \leq 50000$，$1 \leq k \leq 20000$；
- $n>5000$ 或 $m > 5000$ 的数据不超过 $2$ 组；
- $1 \leq a_i,b_i \leq n$，$0 \leq c_i \leq 20000$，$1 \leq d_i \leq k$；
- $1 \leq u_i,v_i \leq k$，$1 \leq w_i \leq 20000$。


title: [SDOI2017] 遗忘的集合

description:
小 Q 在他的个人主页上放出了一个悬赏：征集只含正整数的非空集合 $S$，其中的每个元素都不超过 $n$，并且满足一些附加条件。

众所周知，我们可以很轻松地对于任意不超过 $n$ 的正整数 $x$，计算出把 $x$ 表示成 $S$ 中元素之和的方案数 $f(x)$，在这里我们约定，在任意方案中每个数字可以出现多次，但是不考虑数字出现的顺序。

例如，当 $S=\{1,2,3,4,5\}$ 时，我们可以计算出 $f(2) = 2, f(3) = 3, f(4) = 5, f(5) = 7$。

再例如，当 $S=\{1,2,5\}$ 时，我们可以计算出 $f(4) = 3, f(5) = 4, f(6) = 5, f(7) = 6$。

麻烦地是现在小 Q 忘记了 $S$ 里有哪些元素，幸运地是他用存储设备记录下了所有 $f(i)\bmod p$ 的值，小 Q 希望你能利用这些信息帮他恢复出 $S$ 原来的样子。

具体来说，他希望你找到这样一个正整数的**非空**集合 $S$，其中的每个元素都不超过 $n$，并且对于任意的 $i = 1, 2,\cdots ,n$，满足把 $i$ 表示成 $S$ 中元素之和的方案数在模 $p$ 意义下等于 $f(i)$，其中 $p$ 是记录在存储设备中的一个质数。他向你保证：**一定存在**这样的集合$S$。

然而，小 Q 觉得他存储的信息并不足以恢复出唯一的 $S$，也就是说，可能会存在多个这样的集合 $S$，所以小 Q 希望你能给出所有解中**字典序最小**的解。

对于满足条件的两个不同的集合 $S_1$ 和 $S_2$，我们认为 $S_1$ 的字典序比 $S_2$ 的字典序小，当且仅当存在非负整数 $k$，使得 $S_1$ 的前 $k$ 小元素与 $S_2$ 的前 $k$ 小元素完全相等，并且，要么 $S_1$ 的元素个数为 $k$，且 $S_2$ 的元素个数至少为 $(k + 1)$，要么 $S_1$ 和 $S_2$ 都有至少 $(k + 1)$ 个元素，且 $S_1$ 的第 $(k + 1)$ 小元素比 $S_2$ 的第 $(k + 1)$ 小元素小。

inputFormat:
第一行包含两个整数 $n$ 和 $p$，满足 $p$ 是质数。

第二行包含 $n$ 个整数 $f(1), f(2),\cdots , f(n)$，含义见题目描述。

保证每一行中相邻的整数由恰好一个空格隔开，并且末尾没有多余的空格。

outputFormat:
你需要输出两行信息来描述字典序最小的解，其中第一行包含一个整数 $m\ (m > 0)$，表示 $S$ 的元素个数，第二行包含 $m$ 个正整数 $s_1, s_2,\cdots ,s_m$，表示将 $S$ 的所有元素按升序排序后得到的序列。

你需要保证输出的每一行中相邻的整数由恰好一个空格隔开，并且每一行的末尾没有多余的空格。


title: [SDOI2017] 文本校正

description:
小Q在研发一种数据混淆的算法时不慎将重要的文档都给混淆了。幸运的是，将这些文档校正对于他来说并不是难事。他凭借着敏锐的观察力成功地用肉眼完成了校正。

为了防止这种情况再次发生，小Q希望开发一种文本校正工具，他的目标是将一个文本串$T$分成连续的$3$段，要求每段都不能为空，然后按一定顺序将这$3$段从左往右拼接起来，将其还原为初始文本串$S$。

在进行了大量肉眼校正工作之后，小Q需要休息一下，因此他把这个任务交给了你。请写一个程序，判断是否可以还原，并给出一个合法的还原方案。

inputFormat:
第一行包含一个正整数$Case$，表示需要进行的校正次数。

接下来$Case$个部分依次表示每次校正工作，每个部分第一行包含两个正整数$n$，$m$，分别表示文本串的长度以及字符集的大小。

每个部分第二行包含$n$个正整数$S_1,S_2,\dots ,S_n$，表示$S$串。

每个部分第三行包含$n$个正整数$T_1,T_2,\dots ,T_n$，表示$T$串。

outputFormat:
对于每次校正工作，若无解，则仅输出一行"NO"(不含引号)，否则第一行输出"YES"(不含引号)，接下来三行每行两个正整数$l_i$，$r_i$，按拼接顺序依次表示$T$的$3$个子串。

若存在多种还原方案，请输出任意一种。

hint:
对于$100\%$的数据，$3 \leq n \leq 1000000$，$1 \leq Si,Ti \leq m \leq 1000000$。

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

spj by @Wen_kr


title: 幽幽子吃西瓜

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

西行寺幽幽子是冥界的亡灵，她是一个标准的吃货，现在她的面前摆着一个妖梦替她准备的大西瓜。

description:
妖梦费了好大的劲为幽幽子准备了一个大西瓜，甚至和兔子铃仙打了一架。现在妖梦闲来无事，就蹲在一旁看幽幽子吃西瓜。西瓜可以看作一个标准的球体，瓜皮是绿色的，瓜瓤是红色的，瓜皮的厚度可视为0。妖梦恰好以正视的角度看着这个西瓜。幽幽子是一个吃货，妖梦一走神，自己背后的刀就不见了，而西瓜也被切掉了一块。幽幽子切西瓜时刀面始终垂直于桌面，并且切下的一块在俯视图中正好是一个以西瓜中心为顶点，半径为西瓜半径的扇形。如图所示，是一种满足条件的情况

俯视:

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

正视:

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

妖梦看着红红绿绿的西瓜，忽然陷入思考，红色的西瓜瓤占整个西瓜可视面积的百分之多少呢？但她对几何一窍不通，于是想问问幽幽子，但幽幽子正抱着切下来的西瓜大吃特吃，没有理会妖梦。于是她想让你来帮她解决这个问题。

为了方便描述问题，我们为俯视图建立一个平面极坐标系，极点在俯视图圆形(扇形)的正中央，极轴方向竖直向下。极轴所对应的角度为0度，角度逆时针依次增加，直到转一圈又回到极轴。因此角度范围是[0,360)。幽幽子会切掉西瓜从a°到b°的这一整块。

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

接下来T行每行两个整数a,b。表示切掉范围的起始角度和终止角度。若a>b，则切掉的角度为[a,360)∪[0,b]这一范围。

outputFormat:
T行，每行一个实数后跟一个百分号“%”，表示被切掉一部分的西瓜的正视图(平行投影)中，红色的西瓜瓤占西瓜总可视面积的百分比。在此题中，妖梦的视野方向平行于俯视图的极轴，并且极轴射线指向妖梦。

输出的实数四舍五入保留一位小数，你的答案被判作正确，当且仅当与标准答案完全相同。

hint:
样例说明:

第一个样例中，切掉的西瓜恰好在背面，在妖梦的角度看起来与未切过的西瓜并无区别，因此输出0%。第二个样例中，切掉了从315°~45°这一部分,经过计算，得到答案为sqrt(2)/2，化成小数得到0.707,即70.7%

本题目共有10个测试点。

对于第1个测试点，a,b∈{0,90,180,270}。

对于第2个测试点，270<=a<=359,0<=b<=90。

对于第3,4个测试点，180<=a<=359,0<=b<=179。

对于全部测试点，0<=a,b<=359,a≠b。

1<=T<=10000

命题人:orangebird


title: 普通数学题

background:
一天zzq没有题可以出了。于是他随便写了一个式子，求$\sum_{i=0}^n \sum_{j=0}^m i~xor~j~xor~x$，其中xor表示异或。

zzy一看，这不是水题吗，就随便加了一个函数：$\sum_{i=0}^n \sum_{j=0}^m d(i~xor~j~xor~x)$，其中xor表示异或，d(x)表示x的约数个数。**注意d(0)=0。**

现在zzq不会做了，只好写了一个暴力造了数据，然后把这道题丢给了你。

description:
输入三个数n、m、x，要求计算$\sum_{i=0}^n \sum_{j=0}^m d(i~xor~j~xor~x)$，其中xor表示二进制下的异或，d(x)表示x的约数个数。

由于答案比较大，要求输出答案 mod 998244353。

inputFormat: 一行三个数n、m、x。

hint:
对于20%的数据，$n,m,x \leq 2000$。

对于50%的数据，$n,m,x \leq 10^6$。

对于80%的数据，$n,m,x \leq 10^8$。

对于100%的数据，$1 \leq n,m,x \leq 10^{10}$。


title: Azuki loves coloring

description: NEKOPARA Vol.3 发售之后，在新作中不是主角的 Azuki 终于可以休息了。为了打发时间，她开始给一个由 $n$ 个格子组成的序列涂色，每个格子可以涂黑白灰三种颜色之一。为了美观，Azuki 希望序列中没有两个黑色的格子相邻，也没有两个白色的格子相邻。这样的序列有很多，Azuki 定义每个序列的权值是其中一个黑色格子和一个白色格子相邻的情况的出现次数，如序列“灰黑白黑”的权值为 $2$。Azuki 想知道，对于满足 $0\le i\le k$ 的每一个 $i$，长度为 $n$ 且权值为 $i$ 的序列有多少种。由于答案很大，因此她只需要知道答案 $\text{mod }998244353$ 的值就可以了。Azuki 答应你，如果你解决了这个问题，她就可以给你做~~美味的蛋糕吃~~。

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

outputFormat: 一行 $k+1$ 个正整数，分别代表权值为 $0,1,\dots,k$ 的序列的个数 $\text{mod }998244353$ 的值。


title: 由乃与大母神原型和偶像崇拜

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

由乃最近没事干，去研究轻拍学去了

就是一个叫做flip flappers，轻拍翻转小膜女的番

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

然后研究的过程中她看到了一个叫做大母神原型的东西

大母神不仅是部落保护神，而且是部落间互相识别的标记（以后泛化为不同的图形符号、服饰和祭祀仪式），在部落联盟出现后，具有领导力的部落神祇，上升为整个联盟的共神，进而成为酋邦和王国的共神

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

大概就是说这个东西是母系社会时候的偶像，然后象征着母亲可以创造生命也可以毁灭生命什么什么的，分别是善母与恶母，既孕育一切，又吞噬一切

然后我们熟知的神话里面就有大母神，比如女娲其实就是个大母神。。。

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

原始部落时期的大母神既具有生育和哺乳的能力，也具有保护部落、带来丰收的神力。

到了神话时期，大母神进一步分化，演变出形形色色的女神，分别象征了女性能量的不同面向：孕育女神、大地女神、爱与美女神、保护女神、战争女神、丰收女神、智慧女神、命运女神……

这些是善母

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

世间的事物总是两面性的：一切生命诞生于土地，最终要回归土地；创造的必然也拥有毁灭的能力。大母神也同样具有痛苦、恐怖、吞噬和危险的一面。

比如童话故事里面的女巫，其实就是大母神的另一面的体现，也就是恶母

糖果屋的故事讲的就是韩赛尔和格雷特被继母赶出家里，因为没饭吃了，然后进了森林发现了一个糖果屋，里面有个女巫，专门吃小孩子

然而如果我们仔细想想这个故事，会发现它没有那么简单

比如说，女巫真的是吃小孩子吗？如果女巫是个善良的老婆婆，无偿救助在森林里面困住的小孩子呢？

还有就是当韩赛尔和格雷特杀死了女巫，回到家中发现她们的继母也死了

这是否意味着她们实际上杀死的是她们的继母？

所以这个故事本质上讲的是她们杀了她们的母亲，也就是打败了大母神

很多神话故事里面都有打败大母神的情节

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

你看到这里也许已经觉得由乃精神不正常了

然而由乃自从不小心##了自己的##后早就不正常了

由乃研究了很久大母神原型，但是仍然一脸懵逼

于是就出数据结构题骗钱去了

由乃：给你一个序列，每次询问一个区间是否是值域连续段

zzy：你把题意说详细点

由乃：就是说不能有重复数字，比如1 2 2 3就不行，然后4 2 3 1就可以

yql：sb分块

ddd：sb bitset

由乃：woc你们好树链啊，我。。我带修

zzq：#######sb题

由乃：我就是要出原题

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

给你一个长为 $n$ 的序列 $a$

每次两个操作：

1. 修改 $x$ 位置的值为 $y$

2. 查询区间 $[l,r]$ 是否可以重排为值域上连续的一段

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

inputFormat:
第一行两个数 $n，m$

第二行 $n$ 个数表示 $a_i$

后面 $m$ 行每行三个数 $opt$ $x$ $y$，或者$opt$ $l$ $r$，代表操作

outputFormat:
如果可以，输出“damushen”

否则输出“yuanxing”


title: 签到题IV

background: 这场月赛好像其他题背景都很长，这题就不写背景了。 ![](https://cdn.luogu.com.cn/upload/pic/1436.png)

description:
给定一个长度为 $n$ 的序列 $[a_1,a_2\cdots a_n]$，其中每个数都是正整数。

你需要找出有多少对 $(i,j)$，$1 \leq i \leq j \leq n$ 且$\gcd(a_i,a_{i+1}...a_j) \operatorname{xor} (a_i \operatorname{or} a_{i+1} \operatorname{or} \cdots \operatorname{or} a_j)=k$，其中 $\operatorname{xor}$ 表示二进制异或，$\operatorname{or}$ 表示二进制或。

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

第二行 $n$ 个整数 $a_1,a_2\cdots a_n$。

outputFormat: 输出合法的 $(i,j)$ 的对数。


title: 由乃救爷爷

background:
大家看过葫芦娃吧？

没看过也没关系，让由乃告诉你吧

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

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

传说明斯克航空航天局里关着两个坦克，strv103b和krv。

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

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

鼠爷不小心打破了明斯克航空航天局，两个坦克逃了出来，从此其他坦克过上了水深火热的生活。

明斯克航空航天局急忙去告诉一个叫做serb的光头，只有YY出七辆图纸车，才能消灭这两个卖头势力。

serbYY出了七个连图纸都没有的车，却被瑞典人从bbs中窥见 。他们摧毁不了这七个YY车，

就把serb和鼠爷抓去。但是这时候七个坦克模型已经建出来了。

她们分别是 T28原型，T100lt，907工程，蟋蟀15，WZ111，FV215b183，FV215b

她们为了消灭卖头势力，救出serb和鼠爷，一个接一个去与卖头势力搏斗。

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

T28原是正面很硬的TD，但装甲在金币弹面前一点用都没有，直接被krv卖头打死。

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

T100lt是隐蔽超好的眼车，却因为没有视野，被103b活活黑死。

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

907工程是铁头，被krv顶牛直接抽包抽死。

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

蟋蟀15会黑枪，却因为辣鸡的转向被krv绕死。

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

WZ111有三百穿，被103b穿侧面一发爆了弹药架。

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

FV215b183有183炮，103b和krv瑟瑟发抖，不敢打她，于是她解救了其他所有坦克。

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

但是自己的兄弟FV215b因为瑞典人的诱惑，决定叛变（因为183OO大），TK了183一发，然后183着火烧死了，结果所有坦克都被103b和krv降服了。

瑞典人把七个坦克还有鼠爷一起给serb，让serb做出两辆最强坦克加入瑞典阵营。serb用尽了他所有的脑洞，做出了两辆车E100WT和T-50-2

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

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

krv和103b看到之后蛤蛤大笑

krv：E100WT，10mm的脸，不被HE糊死才怪

103b：E100WT，灯塔般的隐蔽，不被黑死才怪

krv：T-50-2，这血量，我一炮就可以打死

103b：T-50-2，看是你机动好还是我黑枪准

serb：百运，胶水，让她们看看你们的厉害

description:
故事还没讲完

krv骑坡卖头，却发现百运凭借优秀的精度炮炮打穿她的观察孔

krv慌了，跑去城市里面伸缩，被百运站桩撸死

strv103b跑去草后黑枪，看见胶水在肉侦，却发现自己根本打不中她，然后就被胶水点亮了，百运一梭子128的ARCR飞了过来

strv103b怂了，准备跑路了，但是还没等到自己切换回行走模式，胶水已经开始断她的腿了，被胶水断死

瑞典车们高呼不可战胜，从此不敢嚣张了

然后serb把百运和胶水加入了WOT

从此
其他坦克过上了更加水深火热的生活

然而你又不玩WOT，这事情不管你什么事啊

然而yql是大家的妹妹，所以这件事很重要：

yql在AK曼哈顿OI，CTSC，APIO之后，开始研究数学题。

由乃在挂了字符串OI，CTSC，APIO之后，开始研究大母神原型。

yql出了个数学题，由乃画出了一个表示大母神的图腾。

然后把这两个合成了一个题：

然而由于未知原因那个题挂掉了。。。

由乃想起来SCOI 2017 电子科技大学出了个卡常的rmq，然后发生了一件很有趣的事情

就是一位姓王的同学凭借奇奇怪怪的常数优化怒草了那个题，还比标程块了233倍

所以由乃也出了个卡常rmq，因为没题出了

outputFormat: 输出一个unsigned long long 表示每次询问的答案的和


title: 钟氏映射

background:
2233年，CSSYZ学校的数学老师兼数学竞赛顾问钟JG已经2200+岁啦！

为了庆生，他或她给广大人民群众出了道题。

description:
设集合$N=M=\left\{x|x\in N_+,x\leq k,k\in N_+\right\}$

设$f$为$N$到$M$的映射。

求满足：

$f[f(x)]=x$的不同的映射$f$的个数，由于答案较大，输出答案对$14233333$取余的数即可。

inputFormat: 输入一个正整数$k$

outputFormat: 输出满足$f[f(x)]=x$的不同的映射$f$的个数对$14233333$取余得到的数。


title: 妖梦斩木棒

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

妖梦是住在白玉楼的半人半灵，拥有使用剑术程度的能力。

description:
有一天，妖梦正在练习剑术。地面上摆放了一支非常长的木棒，妖梦把它们切成了等长的n段。现在这个木棒可以看做由三种小段构成，中间的n-2段都是左右都被切断的断头，我们记做’X’，最左边的一段和最右边的一段各有一个圆头，记做’（‘和’）’。幽幽子吃饱后闲来无事，决定戏弄一下妖梦。她拿来了许多这样的三种小段木棒，来替换掉妖梦切下来的n段中的一部分，然后问妖梦一些问题。这些操作可以这样描述:

1 x C 将第x个小段的木棒替换成C型，C只会是’X’,’(‘,’)’中的一种

2 l r 询问妖梦从第l段到第r段之间(含l,r)，有多少个完整的木棒

完整的木棒左右两端必须分别为’(‘和’)’，并且中间要么什么都没有，要么只能有’X’。

虽然妖梦能够数清楚这些问题，但幽幽子觉得她回答得太慢了，你能教给妖梦一个更快的办法吗？

inputFormat:
第一行两个整数n，m，n表示共有n段木棒，m表示有m次操作。

木棒的初始形状为(XXXXXX......XXXXXX)。

接下来m行，每行三个整数/字符，用空格隔开。第一个整数为1或2，表示操作的类型，若类型为1，则接下来一个整数x，一个字符C。若类型为2，接下来两个整数l,r。含义见题目描述。

outputFormat: 对于每一个操作2，输出一行一个整数，表示对应询问的答案。


title: AC 自动机（简单版 II）

description: 有 $N$ 个由小写字母组成的模式串以及一个文本串 $T$。每个模式串可能会在文本串中出现多次。你需要找出**哪些**模式串在文本串 $T$ 中出现的次数最多。

inputFormat:
输入含多组数据。保证输入数据不超过 $50$ 组。

每组数据的第一行为一个正整数 $N$，表示共有 $N$ 个模式串，$1 \leq N \leq 150$。

接下去 $N$ 行，每行一个长度小于等于 $70$ 的模式串。下一行是一个长度小于等于 $10^6$ 的文本串 $T$。保证不存在两个相同的模式串。

输入结束标志为 $N=0$。

outputFormat: 对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。

samples:
2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0


title: 辉夜姬的十道难题

background:
妹红最近玩了一款叫 $2048$ 的小游戏。

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

(图为个人无撤销最高纪录~ 纯手玩)。

description:
$2048$ 是一个非常简单的数字游戏，它在 $4\times 4$ 的棋盘上进行，通过移动来合并数字，达到 $2048$ 即算胜利。妹红最近沉迷上了这个游戏，事情传到辉夜那里后，辉夜决定用曾经无人破解的十道难题来考考妹红。

游戏规则：

1. 游戏在 $n\times m$ 的方格棋盘上进行。

2. 两个玩家，其中一个可以移动棋盘上的数字，记做 M，另外一个可以向棋盘上放数字，记做 C。

3. 移动数字的规则如下：可以向上/下/左/右四个方向的其中之一移动。选定好方向后，所有数字都会向该方向靠拢，相同的两个数字相撞时会合并成一个新数字，这个数字是它们的和。在一次移动中，每个数字最多只能合并一次，优先合并靠近移动方向棋盘边缘的数字。

以 $n=2,m=4$ 的情况举例如下（$0$ 表示该位置为空）：

```
2 2 2 2
2 2 0 2
```

向左移动后变为：

```
4 4 0 0
4 2 0 0
```

每次合并后，将会获得一定的分数，获得的分数等于所有合并后数字相加之和。若无任何合并发生，则不得分。在上例中，得分为 $12$。

移动前后，若棋盘上的所有数字大小和位置均没有变化，则不算做有效移动，否则即是有效移动。

4. 向棋盘放置数字的规则如下：只能选择棋盘上没有数字的位置放置一个数字，可以放置的数字和放置方法在每个子任务中会具体描述。

5. 游戏开始时棋盘为空，分数为 $0$。先由玩家 C 行动两步，接着玩家 M 和 C 轮流行动，中间的每一步都必须是有效的。当轮到玩家 M 时，若不能够进行有效移动，则游戏结束，此时的得分为最终得分。

本题目为提交答案题，共有 $10$ 个子任务需要你来完成。将你的答案写到 $10$ 个文件中，分别命名为 ```gamex.out```，$x$ 表示子任务的编号（$0\ldots 9$）。

子任务内无部分分，你可以得到该任务的分数当且仅当你的输出和标准答案完全相同。

十道难题如下:

0. $n=1,m=2$。玩家 C 行动时可以放置 $2$ 或 $4$。若用 $x$ 表示在一局游戏中玩家 M 最多可以行动 $x$ 次，那么这个 $x$ 的最值是多少？输出两行，第一行一个整数表示 $x$ 的最小值，第二行一个整数表示 $x$ 的最大值。

1. $n=10738029,m=921023$。玩家 C 行动时可以放置 $2$ 或 $4$。若用 $x$ 表示棋盘上所有数字之和，请问 $x$ 的最大值是多少。因为这个值可能过大，只需要输出它除以 $10^9+7$ 的余数即可。

2. $n=2,m=2$。玩家 C 行动时可以放置 $2,4$。用 $x$ 表示目标数字， $x$ 一定为 $2$ 的正整数幂。玩家 M 的目标是使盘面上出现大于等于数字 $x$ 的数，玩家 C 的目标是在盘面上出现数字 $x$ 之前使游戏结束。在两方均最优决策的情况下，求一个最大的 $x$，使得玩家 M 能达到自己的目标。

3. $n=4,m=4$。玩家 C 行动时可以放置 $2,4$。输出两行，每行一个数字。第一行的数字表示能达到的最大分数。第二行的数字表示当数字总和达到最大时，分数的最小值。

4. $n=7393,m=9133$。玩家 C 可以放置数字 $2$ 共 $6144$ 次。棋盘初始为空，初始分数为 $0$。首先由玩家 C 连续行动，直到用完所有放置机会或中途主动放弃。然后连续向上移动直到向上方向不能构成有效移动。输出一行一个整数，表示最大得分。

5. $n=7,m=233$。初始分数为 $0$,玩家 C 可以放置数字 $2$ 共 $233$ 次，数字 $4$ 共 $66$ 次。棋盘第一行一开始有若干数字，第 $i$ 列的数字为 $\text{lowbit}(i)\times 2$，$\text{lowbit}(i)$ 表示数字 $i$ 的二进制形式只取最后一个 $1$ 构成的数字。如 $\text{lowbit}(1\ldots 8)$ 为 $1,2,1,4,1,2,1,8$。棋盘的其他位置均为空。首先由玩家 C 连续行动，直到用完所有放置机会或中途主动放弃。然后连续向上移动直到向上方向不能构成有效移动。输出一行一个整数，表示最大得分。

6. $n=3,m=3$。玩家 C 行动时可以放置 $2,4$。用 $x$ 表示目标数字，$x$ 一定为 $2$ 的正整数幂。玩家 M 的目标是使盘面上出现数字 $x$，玩家 C 的目标是在盘面上出现数字 $x$ 之前使游戏结束。在两方均最优决策的情况下，输出一个最大的 $x$，使得玩家 M 能达到自己的目标。

7. $n=3,m=3$。玩家 C 行动时可以放置 $2,4$。玩家 M 的目标是让得分最大化，玩家 C 的目标是让得分最小化，在两方均最优决策的情况下，输出一个整数，表示最终的分数。

8. $n=3,m=3$。玩家 C 行动时，有 $90\%$ 的几率放置一个 $2$，$10\%$ 的几率放置一个 $4$，放置在各个空位的几率均等。用 $x$ 表示目标数字，玩家 M 的目标是使盘面上出现大于等于数字 $x$ 的数。在玩家 M 最优决策的情况下，输出一行，$9$ 个实数，四舍五入到小数点后 $2$ 位，用空格隔开，分别表示 $x=2,4,8,16,32,64,128,256,512$ 时，达成目标数字的概率。

9. $n=3,m=3$。玩家 C 行动时，有 $90\%$ 的几率放置一个 $2$，$10\%$ 的几率放置一个 $4$，放置在各个空位的几率均等。玩家 M 的目标是让分数最大化。在玩家 M 最优决策的情况下，输出一个实数，四舍五入保留整数，表示分数的期望值。

妹红虽然对 $2048$ 有一定了解，但她并不能解决全部的问题，于是就交给了学 OI 的你。

inputFormat: 见题目描述

outputFormat: 见题目描述

samples:
样例任务（无需提交）:
 n=2,m=2。 玩家C行动时只可以放置2。请输出一个整数，表示棋盘上可能出现的最大数字。

hint:
如果对移动规则有疑惑，可以到 $2048$ 网站进行尝试:

http://gabrielecirulli.github.io/2048/

by-orangebird


title: 小魔女帕琪

background:
从前有一个聪明的小魔女帕琪，兴趣是狩猎吸血鬼。

帕琪能熟练使用七种属性（金、木、水、火、土、日、月）的魔法，除了能使用这么多种属性魔法外，她还能将两种以上属性组合，从而唱出强力的魔法。比如说为了加强攻击力而将火和木组合，为了掩盖弱点而将火和土组合等等，变化非常丰富。

description:
现在帕琪与强大的夜之女王，吸血鬼蕾咪相遇了，夜之女王蕾咪具有非常强大的生命力，普通的魔法难以造成效果，只有终极魔法：帕琪七重奏才能对蕾咪造成伤害。帕琪七重奏的触发条件是：连续施放的 $7$ 个魔法中，如果魔法的属性各不相同，就能触发一次帕琪七重奏。

请注意，无论前 $6$ 个魔法是否已经参与施放终极魔法，只要连续 $7$ 个魔法的属性各不相同，就会再触发一次终极魔法。例如，如果用序号来代表一种魔法，魔法的施放序列为 $1, 2, 3, 4, 5, 6,7, 1$，则前 $7$ 个魔法会触发一次终极魔法，后 $7$ 个魔法会再触发一次终极魔法。

现在帕琪有 $7$ 种属性的能量晶体，第 $i$ 种晶体可以施放出属性为 $i$ 的魔法，共有 $a_i$ 个。每次施放魔法时，会等概率随机消耗一个现有的能量晶体，然后释放一个对应属性的魔法。

现在帕琪想知道，她触发帕琪七重奏的期望次数是多少，可是她并不会算，于是找到了学 OI 的你。

inputFormat: 输入只有一行 $7$ 个整数，第 $i$ 个整数代表 $a_i$。

outputFormat: 输出一行一个实数代表答案，四舍五入保留三位小数。

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

显然一定会触发一次帕琪七重奏。

#### 数据规模与约定

- 对于 $30\%$ 的数据，保证 $\sum_{i = 1}^7 a_i \leq 10$。
- 对于 $100\%$ 的数据，保证 $0 \leq a_i \leq 10^9$，且 $\sum_{i = 1}^7 a_i \leq 10^9$。


title: 小 Y 拼木棒

background: 上道题中，小 Y 斩了一地的木棒，现在她想要将木棒拼起来。

description:
有 $n$ 根木棒，现在从中选 $4$ 根，想要组成一个正三角形，问有几种选法？

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

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

第二行往下 $n$ 行，每行 $1$ 个整数，第 $i$ 个整数 $a_i$ 代表第 $i$ 根木棒的长度。

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

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

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

关于标题：因为一些不可抗力的原因，名称进行了更改。深表歉意。


title: Power收集

background:
据说在红雾异变时，博丽灵梦单身前往红魔馆，用十分强硬的手段将事件解决了。

然而当时灵梦在 Power 达到 MAX 之前，不具有“上线收点”的能力，所以她想要知道她能收集多少 P 点，然而这个问题她答不上来，于是她找到了学 OI 的你。

description:
可以把游戏界面理解成一个 $N$ 行 $M$ 列的棋盘，有 $K$ 个格子上有 $P$ 点，其价值为 $\operatorname{val}(i,j)$。

初始灵梦可以选择在第一行的任意一个格子出发，每秒她必须下移一格。

灵梦具有一个左右移动的速度 $T$，可以使她每秒向左或右移动至多 $T$ 格，也可以不移动，并且不能折返。移动可视为瞬间完成，不经过路途上的点，只能获得目标格子的 P 点。

求最终她能获得的 POWER 值最大是多少？

inputFormat:
第一行四个数字，$N,M,K,T$。

接下来 $K$ 行每行 $3$ 个数字 $x,y,v$，代表第 $x$ 行第 $y$ 列有一个 $val$ 为 $v$ 的 P 点，数据保证一个格子上最多只有 $1$ 个 P 点。

outputFormat: 一个数字

hint:
对于 $40\%$ 的测试点，$1 \le N,M,T,K \le 200$。

对于 $100\%$ 的测试点，$1 \le N,M,T,K \le 4000$。

$v \le 100$，$N,M,K,T$ 均为整数。

by-szc


title: 红色的幻想乡

background: 蕾米莉亚的红雾异变失败后，很不甘心。

description:
经过上次失败后，蕾米莉亚决定再次发动红雾异变，但为了防止被灵梦退治，她决定将红雾以奇怪的阵势释放。

我们将幻想乡看做是一个 $n \times m$的方格地区，一开始没有任何一个地区被红雾遮盖。蕾米莉亚每次站在某一个地区上，向东南西北四个方向各发出一条无限长的红雾，可以影响到整行/整列，但不会影响到她所站的那个地区。如果两阵红雾碰撞，则会因为密度过大而沉降消失。灵梦察觉到了这次异变，决定去解决它。但在解决之前，灵梦想要了解一片范围红雾的密度。可以简述为两种操作:

``1 x y`` 蕾米莉亚站在坐标 $(x,y)$ 的位置向四个方向释放无限长的红雾。

``2 x1 y1 x2 y2`` 询问左上点为$(x1,y1)$，右下点为 $(x2,y2)$ 的矩形范围内，被红雾遮盖的地区的数量。

inputFormat:
第一行三个整数 $n,m,q$，表示幻想乡大小为 $n \times m$，有 $q$ 个询问。

接下来 $q$ 行，每行 $3$ 个或 $5$ 个整数,用空格隔开，含义见题目描述。

outputFormat: 对于每一个操作 $2$，输出一行一个整数，表示对应询问的答案。

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

用``o``表示没有红雾，``x``表示有红雾，两次释放红雾后幻想乡地图如下:

```
oxox
xoxo
oxox
xoxo
```

---

#### 数据规模与约定

- 对于 $20\%$ 的数据，$1 \le n,m,q \le 200$。
- 对于 $40\%$ 的数据，$1 \le n,m,q \le 10^3$。
- 对于 $100\%$ 的数据，$1 \le n,m,q \le 10^5$，$1 \le x_1,x_2,x \le n$，$x_1 \le x_2$，$1 \le y_1,y_2,y \le m$，$y_1 \le y_2$。


title: [USACO1.2] 命名那个数字 Name That Number

description:
在威斯康辛州牛守志大农场经营者之中，都习惯于请会计部门用连续数字给母牛打上烙印。但是,母牛本身并没感到这个系统的便利,它们更喜欢用它们喜欢的名字来呼叫它们的同伴，而不是用像这个的语句"C'mon, #4364, get along."。请写一个程序来帮助可怜的牧牛工将一只母牛的烙印编号翻译成一个可能的名字。因为母牛们现在都有手机了，使用标准的按键的排布来把将数目翻译为文字:( 除了 "Q" 和 "Z")

```
2: A,B,C     5: J,K,L    8: T,U,V
3: D,E,F     6: M,N,O    9: W,X,Y
4: G,H,I     7: P,R,S
```
可接受的名字都被放在这样一个叫作"dict.txt" 的文件中，它包含一连串的少于 5,000个（准确地说是4617个）可被接受的牛的名字。 (所有的名字都是大写的且已按字典序排列) 请读入母牛的编号并返回那些能从编号翻译出来并且在字典中的名字。举例来说,编号 4734 能产生的下列各项名字: GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI 碰巧，81个中只有一个"GREG"是有效的(在字典中)。

写一个程序来对给出的编号打印出所有的有效名字，如果没有则输出NONE。编号可能有12位数字。

inputFormat:
第一行一行包含一个编号(长度可能从1到12)。

接下来4617行，每行一个字符串表示可以被接受的名字

outputFormat:
(file namenum.out)

以字典顺序输出一个有效名字的不重复列表，一行一个名字。 如果没有有效名字，输出'NONE'。 //注释：似乎数字只有8^4种排列（1与0不能用）


title: AC 自动机（简单版）

description:
给定 $n$ 个模式串 $s_i$ 和一个文本串 $t$，求有多少个不同的模式串在文本串里出现过。
两个模式串不同当且仅当他们**编号**不同。

inputFormat:
第一行是一个整数，表示模式串的个数 $n$。
第 $2$ 到第 $(n + 1)$ 行，每行一个字符串，第 $(i + 1)$ 行的字符串表示编号为 $i$ 的模式串 $s_i$。
最后一行是一个字符串，表示文本串 $t$。

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

hint:
### 样例 1 解释

$s_2$ 与 $s_3$ 编号（下标）不同，因此各自对答案产生了一次贡献。

### 样例 2 解释

$s_1$，$s_2$，$s_4$ 都在串 `abcd` 里出现过。

### 数据规模与约定

- 对于 $50\%$ 的数据，保证 $n = 1$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^6$，$1 \leq |t| \leq 10^6$，$1 \leq \sum\limits_{i = 1}^n |s_i| \leq 10^6$。$s_i, t$ 中仅包含小写字母。


title: 【模板】后缀自动机（SAM）

description:
给定一个只包含小写字母的字符串 $S$。

请你求出 $S$ 的所有出现次数不为 $1$ 的子串的出现次数乘上该子串长度的最大值。

inputFormat: 一行一个仅包含小写字母的字符串 $S$。

outputFormat: 一个整数，为所求答案。

hint:
对于 $10 \%$ 的数据，$\lvert S \rvert \le 1000$。
对于 $100\% $的数据，$1 \le \lvert S \rvert \le {10}^6$。

- 2023.7.30：添加一组 hack 数据。


title: 【模板】多项式乘法（FFT）

background:
这是一道多项式乘法模板题。

注意：本题并不属于中国计算机学会划定的提高组知识点考察范围。

description:
给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$。

请求出 $F(x)$ 和 $G(x)$ 的卷积。

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

接下来一行 $n+1$ 个数字，从低到高表示 $F(x)$ 的系数。

接下来一行 $m+1$ 个数字，从低到高表示 $G(x)$ 的系数。

outputFormat: 一行 $n+m+1$ 个数字，从低到高表示 $F(x) \cdot G(x)$ 的系数。

hint:
保证输入中的系数大于等于 $0$ 且小于等于 $9$。

对于 $100\%$ 的数据：$1 \le n, m \leq {10}^6$。


title: 【模板】后缀排序

background: 这是一道模板题。

description: 读入一个长度为 $ n $ 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序（用 ASCII 数值比较）从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 $ 1 $ 到 $ n $。

inputFormat: 一行一个长度为 $ n $ 的仅包含大小写英文字母或数字的字符串。

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

samples:
ababa
5 3 1 4 2


title: 【模板】三维偏序（陌上花开）

background: 这是一道模板题，可以使用 bitset，CDQ 分治，KD-Tree 等方式解决。

description:
有 $ n $ 个元素，第 $ i $ 个元素有 $ a_i,b_i,c_i $ 三个属性，设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 且 $ j \ne i $ 的 $j$ 的数量。

对于 $ d \in [0, n) $，求 $ f(i) = d $ 的数量。

inputFormat:
第一行两个整数 $ n,k $，表示元素数量和最大属性值。

接下来 $ n $ 行，每行三个整数 $ a_i ,b_i,c_i $，分别表示三个属性值。

outputFormat: $ n $ 行，第 $ d + 1 $ 行表示 $ f(i) = d $ 的 $ i $ 的数量。

hint: $ 1 \leq n \leq 10^5$，$1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5 $。


title: 【模板】manacher

description:
给出一个只由小写英文字符 $\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z$ 组成的字符串 $S$ ,求 $S$ 中最长回文串的长度 。

字符串长度为 $n$。

inputFormat: 一行小写英文字符 $\texttt a,\texttt b,\texttt c,\cdots,\texttt y,\texttt z$ 组成的字符串 $S$。

outputFormat: 一个整数表示答案。


title: 【模板】模意义下的乘法逆元

background: 这是一道模板题

description:
给定 $n,p$ 求 $1\sim n$ 中所有整数在模 $p$ 意义下的乘法逆元。

这里 $a$ 模 $p$ 的乘法逆元定义为 $ax\equiv1\pmod p$ 的解。

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

outputFormat: 输出 $n$ 行，第 $i$ 行表示 $i$ 在模 $p$ 下的乘法逆元。

hint:
$ 1 \leq n \leq 3 \times 10 ^ 6$，$n < p < 20000528 $。

输入保证 $ p $ 为质数。


title: 【模板】线性基

background: 这是一道模板题。

description: 给定 $n$ 个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。

inputFormat:
第一行一个数 $n$，表示元素个数

接下来一行 $n$ 个数

outputFormat: 仅一行，表示答案。


title: 毒瘤之神的考验

background:
Salamander 的家门口是一条长长的公路。

又是一年春天将至，Salamander 发现路边长出了一排毒瘤！

Salamander 想带一些毒瘤回家，但是，这时毒瘤当中钻出来了一个毒瘤之神！

毒瘤之神：你想要带毒瘤走吗？想要带走毒瘤，就必须回答我的问题！如果答不出来的话，你还是乖乖回家吧！

description:
毒瘤之神会问 $T$ 次，每次给定 $n, m$，Salamander 需要回答出 $\left( \sum_{i=1}^n \sum_{j=1}^m \varphi(ij) \right)\! \bmod 998244353$。

Salamander 这么辣鸡当然不会做啦，于是把问题丢给了你。

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

接下来 $T$ 行，每行包含两个正整数，用空格隔开，表示这次询问的 $n, m$。

outputFormat: 包含 $T$ 行，每行一个整数表示答案。


title: 【模板】卢卡斯定理/Lucas 定理

background: 这是一道模板题。

description:
给定整数 $n, m, p$ 的值，求出 $C_{n + m}^n \bmod p$ 的值。

输入数据保证 $p$ 为质数。

注: $C$ 表示组合数。

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

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

对于每组数据:

一行，三个整数 $n, m, p$。

outputFormat: 对于每组数据，输出一行，一个整数，表示所求的值。


title: [FJOI2017] 矩阵填数

description:
给定一个 $h \times w$ 的矩阵，矩阵的行编号从上到下依次为 $1 \sim h$，列编号从左到右依次 $1 \sim w$。

在这个矩阵中你需要在每个格子中填入 $1 \sim m$ 中的某个数。

给这个矩阵填数的时候有一些限制，给定 $n$ 个该矩阵的子矩阵，以及该子矩阵的最大值 $v$，要求你所填的方案满足该子矩阵的最大值为 $v$。

现在，你的任务是求出有多少种填数的方案满足 $n$ 个限制。

两种方案是不一样的当且仅当两个方案至少存在一个格子上有不同的数。由于答案可能很大，你只需要输出答案对 $10 ^ 9 + 7$ 取模后的结果。

inputFormat:
输入数据的第一行为一个数 $T$，表示数据组数。

对于每组数据，第一行为四个数 $h,w,m,n$。

接下来 $n$ 行，每一行描述一个子矩阵的最大值 v。每行为五个整数 $x1,y1,x2,y2,v$，表示一个左上角为$(x1,y1)$,右下角为$(x2,y2)$的子矩阵的最大值为 $v$。 $1 \le x1 \le x2 \le h$, $1 \le y1 \le y2 \le w$

outputFormat: 对于每组数据输出一行，表示填数方案 mod $1,000,000,007$ 后的值。


title: [FJOI2017] 远古山脉问题

description:
远古山脉可以看作是一个由山脉元素组成的序列，每个元素有一个高度，远

古山脉的变化规则如下：

1. I h x：在第x个山脉元素右边插入高度为h的山脉元素。

2. R l r：从第l个山脉元素到第r个山脉元素的高度翻转， 例如,$a_1,a_2,a_3,a_4,a_5$，对$(2,5)$翻转就变为$a_1,a_5,a_4,a_3,a_2$

3. M t x：在第x个山脉元素右边插入第t个山脉。

山脉元素按从左到右的顺序从$1$开始编号。一开始时没有山脉元素，记为第$0$个山脉。对于第$i$个山脉，经过任意一种变化后就变成第$i+1$个山脉。山脉中会收集山脉能量，假设山脉中最高的山脉元素的编号为$x$，如果有$m$个相同的高度，取左数第$\left \lceil \frac{m}{2} \right \rceil$个元素，那么山脉收集的能量为:

$$\sum_{i=l}^{x-1}\left\{\begin{matrix} x-i & if\ h_{i}>h_{i+1}\\ 0 & if\ h_{i}\leq h_{i+1} \end{matrix}\right.+\sum_{i=x+1}^{r}\left\{\begin{matrix} i-x & if\ h_{i}>h_{i-1}\\ 0 & if\ h_{i}\leq h_{i-1} \end{matrix}\right.$$

其中$h_{i}$代表第$i$个山脉元素的高度。

山脉序列问题需要回答的基本询问是：从第$l$个山脉元素到第$r$个山脉元素组成子山脉能收集的能量是多少？

inputFormat:
文件的第一行有1个正整数$n$， ($n\le 50000$)，表示山脉变化和询问的总次数。

接下来n行，每行是四种格式之一：

1. I h x: 在第$x$个山脉元素右边插入高度为$h$的山脉元素， $0\le h\le 20000$。

2. R l r: 从第$l$个山脉元素到第$r$个山脉元素的高度翻转。

3. M t x: 在第$x$个山脉元素右边插入第$t$个山脉。

4. Q l r: 询问由第l个山脉元素到第$r$个山脉元素组成子山脉能收集的能量是多少。

对于第$i$个山脉，经过任意一种变化后就变成第$i+1$个山脉。

保证以上所有输入整数在long long范围内

outputFormat: 对于每个询问，输出一行答案，答案对1000000007取模。


title: [FJOI2017] 回文子序列问题

description:
设 X 和 Y 是2个给定的正整数序列 $X=( x_1 , x_2 ,\cdots, x_m )$和$Y=( y_1, y_2 ,\cdots, y_n )$。

X 和 Y的一个公共子序列是指X 和 Y的一个公共子序列$(x_{i1}=y_{j1},x_{i2}=y_{j2},\cdots,x_{it}=y_{jt})$, 其中 $i1<i2<\cdots<it$ 。

当一个序列正读和反读都相同时，称该序列是回文。例如，序列$(1,3,5,3,1)$就是回文。 X 和 Y的一个公共回文子序列是指X 和 Y的一个公共子序列，且该子序列是回文。 在X 和 Y的所有公共回文子序列中，长度最长的就称为X 和 Y的一个最长公共回文子序列。在一般情况下， X 和 Y会有多个最长公共回文子

序列。例如，对于给定的正整数序列$X=(1,9,3,9,1)$ 和 $Y=(1,3,9,3,1)$，其子序列$(1,3,1)$和$(1,9,1)$都是X 和 Y的最长公共回文子序列。

我们的问题是，对于给定的正整数序列X 和 Y，确定其最长公共回文子序列的长度。

对于给定的2个正整数序列$X=( x_1 , x_2 ,\cdots, x_n )$和$Y=( y_1 , y_2 ,\cdots, y_n )$，计算出它们的最长公共回文子序列的长度。

inputFormat: 文件有多个测试项（$ \le 10$）。每个测试项的第一行有1个正整数$n$， ($1\le n\le 500$)，表示2个输入序列X和Y的长度均为$n$。接下来的2行分别给出输入正整数序列$X=(x_1,x_2,\cdots,x_n)$和$Y=(y_1,y_2,\cdots, y_n)$。其中序列中每个元素均为正整数（ $\le 20000$）。文件最后以一个0结束。

outputFormat: 将计算出的每个测试项的最长公共回文子序列的长度依次输出到文件中， 每行输出一个长度。


title: [FJOI2017] 树的平均路长问题

description:
一棵树 $T$ 的平均路长 $IPL(T)$定义为：

$IPL(T)=\sum_{v\varepsilon T}length(path(v))$

其中， $v$ 是树 $T$ 中的内结点， $length(path(v))$是从树根到结点$v$的路径长度。

红黑树是一类特殊的二叉搜索树，其中每个结点被“染成”红色或黑色。若将二叉搜索树结点中的空指针看作是指向一个空结点，则称这类空结点为二叉搜索树的前端结点。并规定所有前端结点的高度为$-1$。除了前端结点外，其他结点均为内结点。

一棵红黑树是满足下面“红黑性质”染色二叉搜索树：

1. 每个结点被染成红色或黑色；

2. 每个前端结点为黑色结点；

3. 任一红结点的儿子结点均为黑结点；

4. 在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。

从红黑树中任一结点 $x$ 出发(不包括结点 $x$)，到达一个前端结点的任意一条路径上的黑结点个数称为结点 $x$ 的黑高度，记作 $bh(x)$。红黑树的黑高度定义为其根结点的黑高度。

给定正整数 $n$，试设计一个算法，计算出在所有含有 $n$ 个结点的红黑树中，平均路长的最大值。

inputFormat: 文件有多个测试项。每行有1个正整数$n$， ($1\le n\le 30000$)，表示红黑树的结点数。文件最后以一个$0$结束。

outputFormat:
对每行中红黑树的结点数 $n$，将计算出的平均路长的最大值输出到文件中。

每行输出一个最大值。 文件最后以一个$0$ 结束。


title: 小D的地下温泉

background: 小D最喜欢泡温泉了。小D找某奸商租下了一块$N$行$M$列的地，左上角为$(1,1)$，右下角为$(N,M)$。小D本以为这块地里全是温泉，结果这块地极不稳定，曾经发生过一些地形变动，所以其中一些地方全是土。

description:
一开始他会告诉你当前这块地的情况，但是小D有一些假操作，希望你操作给他看：

1. 由小D指定$w$个位置，他希望知道其中哪个位置下水泡温泉的范围最大。泡温泉的范围定义为指定位置通过向上下左右四个方向能到达的位置的个数。若询问的位置为土，则范围为0。如果如果有多个位置均为最大，输出给出顺序较前的那个。位置编号为$1,2,...,w$。

2. 由小D指定$w$个位置，他会使用膜法按顺序翻转这$w$个地方的地形。即若原位置是土，则该位置变为温泉；若原位置是温泉，则该位置变为土。因为小D不希望活动范围减少得太快，所以他在将温泉变为土时不会将一个区域分割。

inputFormat:
第一行输入两个整数，$N,M$，为土地大小。

接下来的$N$行每行输入$M$个字符，为'.'（代表温泉）或'\*'（代表土）（不包括引号）

第$N+2$行输入一个整数，$Q$，为操作数量。

接下来的$Q$行，每行先读入两个整数$opt$和$w$，表示操作类型和指定点的数量，在同一行还有$2\times w$个数$x_{1},y_{1},x_{2},y_{2},...,x_{w},y_{w}$，分别表示$w$个操作的位置为$(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{w},y_{w})$。

outputFormat: 对于每个操作1，输出询问的答案并换行

hint:
对于30%的数据，$N,M\le 100,\sum w\le 100$

对于70%的数据，$N,M\le 1000$

对于100%的数据，$1\le N\times M,Q\le 10^{6},\sum w\le 10^{6},w\geq 1$

数据在windows下制作


title: [TJOI2007] 线段

description:
在一个 $n \times n$ 的平面上，在每一行中有一条线段，第 $i$ 行的线段的左端点是$(i, L_{i})$，右端点是$(i, R_{i})$。

你从 $(1,1)$ 点出发，要求沿途走过所有的线段，最终到达 $(n,n)$ 点，且所走的路程长度要尽量短。

更具体一些说，你在任何时候只能选择向下走一步（行数增加 $1$）、向左走一步（列数减少 $1$）或是向右走一步（列数增加 $1$）。当然，由于你不能向上行走，因此在从任何一行向下走到另一行的时候，你必须保证已经走完本行的那条线段。

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

以下 $n$ 行，在第 $i$ 行（总第 $(i+1)$ 行）的两个整数表示 $L_i$ 和 $R_i$。

outputFormat: 仅包含一个整数，你选择的最短路程的长度。


title: [TJOI2007] 迷路

background:
小 A 和小 B 在一个二维空间中迷路了，每个人在这个空间中都按照自己特定的路线行

走，由于他们的路线都是周期性的，因此你可以把这种路线理解为一种“轨道”：即一条封

闭的路线，路线的终点和起点重合，这样才能“周期”的行走。

description:
两个人行走的速度都是每秒一个单位距离，而且他们的路线都是平行于坐标轴的。基于

此，如果两个人无限的走下去，我们想知道他们每一秒相离最近的距离。（我们只考虑两人

在每秒行走后相离的距离，不考虑他们在这 1 秒内某个时刻的距离）

inputFormat:
输入文件中有两个相似的部分，分别描述小 A 和小 B 的行走轨道。在每一个部分中的

第一行有三个整数，sx、sy 和 m，前两个整数表示其初始位置，第三个整数表示轨道中折线

的数目，以下 m 行，每行有一个整数 d 和一个非空格字符 c，d 和 c 之间用一个空格隔开。

d 表示小 A 或小 B 沿坐标的正方向行走的距离，而 c 为’X’或’Y’，表示是 X 坐标轴还是 Y

坐标轴。输入数据保证在每一个部分中，我们从起点(sx, sy)开始，执行 m 次行走步骤后，一定能

回到起点，即这个轨道是封闭的。

outputFormat:
输出文件中只包含一个实数，精确到小数点后两位。表示能观测到的两个人的最近距离，

如果可能在某个时间两个人到达同一个点，则输出 0.00。

hint:
100%的数据中，对于任何 m 和 d，有 1 ≤ m, d ≤ 100，轨道的初始坐标的绝对值不超

过 2 000。


title: [TJOI2007] 圆

description:
平面上有 n 个圆，任意两个不同的圆之间只有相离（可以外切）和包含（可以内切）两

种关系。初始时整个平面是黑色的，我们按照输入给定的顺序在平面上画出这些圆，我们画

一个圆的时候，把这个圆覆盖的区域全部反色，即如果区域中的一个点原来是黑色，则将它

涂为白色；如果这个点原来是白色，则将它涂成黑色。

按照这个步骤把所有的圆都画出来后，请输出平面上的所有白色区域的面积之和。

inputFormat:
输入文件的第一行有一个整数 n，表示圆的个数。以下 n 行，每行用三个整数 x, y 和 r

描述一个圆，表示圆心(x, y)和半径 r。在平面上画圆的顺序和输入给定的顺序相同。

outputFormat:
你只需要向输出文件输入一个实数，精确到小数点后两位，表示平面上白色区域面积之

和。

hint: 100%的数据中，n ≤ 100，对于所有的圆，|x|, |y|, r ≤ 1 000。


title: [TJOI2007] 球赛

background:
超级球迷 H 每周六晚上都会坐在电视前看球，从不错过一场比赛。

但是上周末，H 突然有一个重要的约会，于是他只能教他三岁的弟弟小 H 记录所有比赛

的比分。但是当他约会回来时，他发现小 H 不仅认真的记录了每一场比赛的最终比分，还

把一些比赛的中间比分也记录下来，而更糟糕的是，小 H 并没有区分比赛的两个队，同一

场比赛的比分可能被记录成 1-2，也可能是 2-1。因此，若是有一场比赛的最终得分是 5-3，

可能实际上被小 H 记录的分数有

1-0 3-2 2-3 3-4 5-3

description:
现在 H 已经拿到了小 H 记录的所有比分，他想知道，在这个周末他由于约会至少错过

了多少场比赛。注意小 H 记录的比分是没有先后顺序的。

inputFormat:
输入文件中可能包含多组测试数据，文件中第一行是一个整数 n，表明以下一共有 n 组

测试数据。

对于每一组数据，第一行有一个整数 s，表示小 H 记录的比分数目，以下每行用 x-y 的

格式描述一条比分，x 和 y 都是非负整数。

outputFormat:
对于输入数据中的每一个测试数据，你需要输出一个整数 m，表示在这个测试数据中，

H 至少错过了 m 场比赛。

hint:
在第一组输入数据中，两场比赛对应的比分可能是 1-0 2-0 0-3 和 2-1。

在第二组输入数据中，三场比赛对应的比分可能是 0-0 5-0、3-1 和 2-2。

100%的数据中 n ≤ 5，s ≤ 1 000，每一场比赛的比分都在 longint(Pascal) / long(C++)

（2147483647）范围内。


title: [TJOI2007] 可爱的质数/【模板】BSGS

description: 给定一个质数 $p$，以及一个整数 $b$，一个整数 $n$，现在要求你计算一个最小的非负整数 $l$，满足 $b^l \equiv n \pmod p$。

inputFormat: 仅一行，有 $3$ 个整数，依次代表 $p, b, n$。

outputFormat: 仅一行，如果有 $l$ 满足该要求，输出最小的 $l$，否则输出 `no solution`。

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

- 对于所有的测试点，保证 $2\le b,n < p<2^{31}$。


title: [TJOI2007] 调整队形

background:
学校艺术节上，规定合唱队要参加比赛，各个队员的衣服颜色不能很混乱：合唱队员应排成一横排，且衣服颜色必须是左右对称的。

例如：“红蓝绿蓝红”或“红蓝绿绿蓝红”都是符合的，而“红蓝绿红”或“蓝绿蓝红”就不符合要求。

合唱队人数自然很多，仅现有的同学就可能会有3000个。老师希望将合唱队调整得符合要求，但想要调整尽量少，减少麻烦。以下任一动作认为是一次调整：

description:
1、在队伍左或右边加一个人（衣服颜色依要求而定）；

2、在队伍中任两个人中间插入一个人（衣服颜色依要求而定）；

3、剔掉一个人；

4、让一个人换衣服颜色；

老师想知道就目前的队形最少的调整次数是多少，请你编一个程序来回答他。

因为加入合唱队很热门，你可以认为人数是无限的，即随时想加一个人都能找到人。同时衣服颜色也是任意的。

inputFormat:
第一行是一个整数n(1<=n<=3000)。

第二行是n个整数，从左到右分别表示现有的每个队员衣服的颜色号，都是1到3000的整数。

outputFormat: 一个数，即对于输入队列，要调整得符合要求，最少的调整次数。


title: [TJOI2007] 跳棋

background:
在一个n×n的棋盘上，布满了0和1，如图（a）所示（n=7），为叙述方便，将0用字母表示，如图（b）。

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

description:
跳棋规则：

（1）从某个0格出发，可以向上，下，左，右4个方向连续越过若干个（至少1个）

1格而跳入下一个0格。如图（b）中从A出发，可跳到B，或者到E，但不能直接到K。在跳到B之后还可以继续跳到F;在跳到E之后可继续跳到F或K。直到不能再跳为止。

（2）每个0格只能到达一次，给出的起始点不能再到达，也不能越过。

跳过的距离为跳过1格个数加1，如从A到B，跳过距离为3，从B到F，跳过距离为2。

问   题： 当棋盘和起始点给出之后，问最远能跳的距离是多少？

如上图（b）中，从A出发，可跳过的路线不止一条，其中一条为：

A － B － F － L － K － E  （可能不唯一）

3    2    3    3     3

它的距离为14。

inputFormat:
第一行三个整数  n（1≤n≤100），x，y（起点坐标，上图（b）中A处坐标为1，3）

接下来n行，每行n个数（0或1），数与数之间用一个空格分隔。

outputFormat: 一个整数，即最大可跳距离（若不能跳，输出0）。

hint: $\text{upd 2022.7.27}$：新增加一组 Hack 数据。


title: [TJOI2007] 足彩投注

background:
了解足球彩票的人可能知道，足球彩票中有一种游戏叫做“胜负彩”，意为猜比赛的胜负。下面是一些与胜负彩有关的术语：

注      ：每一组有效组合数据。

投    注：彩民以现金购买足球彩票的行为。

单式投注：彩民对于所有球队的比赛成绩均只选择一种预测结果的投注方式。投注的数量（注数）为1。

复式投注：彩民对于某些场次的比赛成绩选择两种以上的预测结果的投注方式。投注的数量为复式投注的组合数。例如，某彩民对一场比赛预测了两个结果（例如，胜平），           另一场比赛预测了三个结果（胜负平），其他比赛都只预测了一种结果，那么注数就是2×3 = 6。这样的一个复式投注，可以看成一个包含六种单式投注的集合。

胜负彩的玩法一般是这样的。彩票机构指定一轮比赛中的若干场，让彩民去猜每场比赛的结果（胜、负、平）。根据彩民猜中比赛的场次，来确定中奖的额度。

description:
我们现在考虑一个简化的模型。对于一轮比赛，彩民需要竞猜其中n场比赛的结果，每场比赛的胜负平都有一个概率p(i, r)。其中，i表示第i场比赛。r = 0, 1, 2，分别表示比赛结果的（主队）负、平、胜。p(i, r)则表示第i场比赛、结果为r的概率。此外，还有一个概率q(i, r)，表示第i场比赛，投注购买结果为r的概率。

例如，如果q(1,0) = 0.5，我们可以知道第一场比赛有50%的投注会买主队输球。我们假设这n场比赛互不相关，即p(i, r)的结果不会受p(j, r’)的影响，q(i, r)的结果也不会受q(j, r’)的影响（r ≠ r’）。

在这个模型里，我们规定，必须猜中全部n场比赛的结果才能获奖。总奖金为M，由所有获奖的投注平分。因此，对于一个单式投注Ri = {ri1, ri2, …, rin}，rij表示投注Ri对第j场比赛的预测结果，它的中奖概率为：

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

设投注总数为N，那么中奖的投注总数为：

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

于是，投注Ri所能得到的奖金的期望（平均意义下能够获得的奖金数）就是：

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

以上考虑的仅仅是单式投注的情况，即仅考虑单注Ri的中奖情况。对于复式投注，情况要复杂一些。采用复式投注时，投注的是一个集合R = {R1, R2, …, Rk}，其中k是投注的数量。例如，三场比赛，第一场猜“胜负”，第二场猜“平”，第三场猜“负平”，则k = 4，R集合如下：

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

复式投注R中，只要有一个Ri猜对所有比赛结果，即可中奖。因此，复式投注R所能获得的奖金的期望就是：

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

我们的问题是，给定n场比赛的信息（胜负平的概率和彩民购买三种结果的概率），以及复式投注中可以购买的最大注数U，要求设计一种复式投注的方案，在不超过最大注数（复式投注的注数k ≤ U）的前提下，使得获得奖金的期望最大。

inputFormat:
第一行四个整数n, N, M, U（n, U ≤ 10^4, N, M ≤ 10^9）。

以下n行，每行六个实数。第i + 1行的六个实数为p(i, 0), p(i, 1), p(i, 2), q(i, 0), q(i, 1)和q(i, 2)，用来描述第i场比赛的相关信息。其中，p(i, 0) + p(i, 1) + p(i, 2) = 1, q(i, 0) + q(i, 1) + q(i, 2) = 1, q(i, j) ≠ 0。

outputFormat:
一个实数，表示最大的奖金期望的自然对数

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

输出保留3位小数（四舍五入）。


title: [TJOI2007] 书架

description: Knuth 先生家里有个精致的书架，书架上有 $N$ 本书，如今他想学到更多的知识，于是又买来了 $M$ 本不同的新书。现在他要把新买的书依次插入到书架中，他已经把每本书要插入的位置标记好了，并且相应的将它们放好。由于 Knuth 年龄已大，过几天他已经记不清某些位置上放的到底是什么书了，请问你能帮助他吗？

inputFormat: 输入文件的第一行为整数 $N$，接下来 $N$ 行分别是书架上依次放着的 N 本书的书名（书名由不含空格的字符串构成，长度不超过 $10$）。下一行将要输入一个整数 $M$，接下来的 $M$ 行分别为这本书的书名和要插入的位置。下一行将要输入一个整数 $Q$，接下来共有 $Q$ 次询问，每行都是一个整数表示询问的位置。（书架上位置的编号从 $0$ 开始）

outputFormat: 输出 $Q$ 行，每行对应着相应查询位置的书名。

samples:
3
Math
Algorithm
Program
2
Picture 2
System 1
3
0
1
3

hint:
原来有三本书 Math、Algorithm、Program，后来又买了两本书，分别插入到 $2$ 和 $1$ 的位置，每次插入时其他书都要向后挪一个位置，最后书架上书的序列为：

```plain
0  Math
1  System
2  Algorithm
3  Picture
4  Program
```
$Q$ 次询问依次为 $0$, $1$, $3$ 位置的书，所以答案为：Math、System、Picture

对于 $30\%$ 的数据，$1 \leqslant N \leqslant 100$, $1 \leqslant M \leqslant 10^3$, $1 \leqslant Q \leqslant 10^3$

对于 $100\%$ 的数据，$1 \leqslant N \leqslant 200$, $1 \leqslant M \leqslant 10^5$, $1 \leqslant Q \leqslant 10^4$

对于 $100\%$ 的数据都符合题目中所描述的限制关系，数据保证每次插入的位置均不超过当时书架上书的数量，而且保证 $Q$ 次查询中的每个位置上一定有书。


title: [TJOI2007] 脱险

background: 一批探险队员正在一个迷宫一样的山洞里摸索，突然他们得到了一个糟糕的消息，由于附近发生地震，这个山洞将有可能在 $T$ 个单位时间后坍塌。现在他们要用最快的速度找出一个方案，使得在 $T$ 个单位时间内逃出的队员最多。已知探险队员在一个单位时间内可以向前后左右任一方向移动一格，也可以停留在原地不动。有一个糟糕的情况是，虽然山洞的内部比较宽敞，但山洞的出口都非常狭窄，一个单位时间只能允许一名队员通过。

description:
山洞的地图用一个 $R \times C$ 的字符矩阵表示：

- `.` 表示在开始的时候没有探险队员的空地，空地可以容纳任意多的探险队员；
- `P`表示在开始的时候有探险队员的空地，我们假设在开始的时候所有的队员都在不同的位置上，且没有队员恰好位于出口所在的方格；
- `*` 表示障碍物，探险队员不能经过被障碍物占据的方格；
- `O`（大写字母 `O`）表示出口，输入数据保证出口一定位于地图的边界上，即只有第 $1$ 行，第 $R$ 行，第 $1$ 列，第 $C$ 列有可能出现 `O`。

另外，输入数据保证整个地图被边界和出口围住，即第 $1$ 行，第 $R$ 行，第 $1$ 列，第 $C$ 列只能是 `*` 或 `O`。

inputFormat: 输入文件的第一行是用空格隔开的两个整数 $R$ 和 $C$，表示地图的大小。第二行是整数 $T$，即山洞将要坍塌的时间。接下来 $R$ 行，每行包含 $C$ 个字符，表示一幅山洞地图。

outputFormat: 输出一行，包含一个整数，即 $T$ 个单位时间内最多能逃出的人数。

hint:
山洞有两个出口，但只有右边的出口是可以到达的。虽然在 $3$ 个单位时间内两人都可以到达出口左侧的方格处，但由于在出口处一个单位时间只能允许一人通过，故 $4$ 个单位时间内只能逃出一人。两人都逃出需要 $5$ 个单位时间。

- 对于 $30\%$ 的数据，队员数和出口数均不超过 $10$；
- 对于 $100\%$ 的数据，$3 \le R, C \le 12，0 < T \le 50$。


title: [TJOI2007] 小朋友

background: 幼儿园里有N个小朋友，老师要从中选出来一部分做丢手绢的游戏，可是老师没有想到这么小的孩子里面有些人之间还有矛盾。老师想找出尽量多的小朋友去玩游戏，但是又很头疼，他不想看到找出来玩游戏的小朋友里面还有任何两个人之间存在着矛盾。如果告诉你小朋友之间存在的M对矛盾关系，你能否帮助幼儿园老师计算出他最多可以选出多少个小朋友来做这个丢手绢的游戏？

description:
关于矛盾限制的说明：

如果我们把存在着矛盾的两个小朋友看作是无向图中相连的两个点，那么题目中的数据保证M对矛盾所构成的图中不会有超过3个点的环。（图1符合要求，图2则不符合）

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

inputFormat: 输入文件的第一行是用空格隔开的两个整数N和M，表示一共有N个小朋友，这些小朋友之间有M对矛盾关系。接下来的M行，每行将有一对整数a和b（用空格隔开），表示小朋友a与小朋友b有矛盾。（小朋友的编号都是从1开始的）

outputFormat: 输出一行，包含一个整数，即幼儿园老师最多可以选出来做游戏的人数。

hint:
幼儿园有6个小朋友，矛盾关系中1 - 2 - 3组成一个环，3 - 4 - 5组成一个环，因此只能在这两个环中分别选一个小朋友，并且不能选择3号小朋友。

对于20%的数据，1 ≤ N ≤ 20

对于40%的数据，1 ≤ N ≤ 50

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

对于100%的数据都符合题目中所描述的矛盾限制关系。


title: [TJOI2007] 路标设置

background: B 市和 T 市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，我们把公路上相邻路标的最大距离定义为该公路的“空旷指数”。

description: 现在政府决定在公路上增设一些路标，使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。请注意，公路的起点和终点保证已设有路标，公路的长度为整数，并且原有路标和新设路标都必须距起点整数个单位距离。

inputFormat:
第 $1$ 行包括三个数 $L,N,K$，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。

第 $2$ 行包括递增排列的 $N$ 个整数，分别表示原有的 $N$ 个路标的位置。路标的位置用距起点的距离表示，且一定位于区间 $[0,L]$ 内。

outputFormat: 输出 $1$ 行，包含一个整数，表示增设路标后能达到的最小“空旷指数”值。

hint:
公路原来只在起点和终点处有两个路标，现在允许新增一个路标，应该把新路标设在距起点 $50$ 或 $51$ 个单位距离处，这样能达到最小的空旷指数 $51$。

$50\%$ 的数据中，$2 \leq N \leq 100$，$0 \leq K \leq 100$。

$100\%$ 的数据中，$2 \leq N \leq 100000$, $0 \leq K \leq100000$。

$100\%$ 的数据中，$0 < L \leq 10000000$。


title: [TJOI2008] 通讯网破坏

background: 由于争夺资源引起的矛盾冲突，A国和B国进入了战争一触即发的状态。现在A国的间谍机构设法得到了B国的通讯网络布置情况，其中每个城市可以看作一个点，在某些点之间有无向边，表示这些城市之间可以进行双向的直接通讯。A国打算先发制人，通过核武器毁灭某个中间城市M，一举切断B国某两个重要城市S,T之间的联系，即从图中删除掉M点之后，S和T变得不连通。但是由于B国的防御力量也很强大，这样的核打击只能成功进行一次且只能毁灭一个城市。

description: 现在A国的首脑提出了很多种作战策略，作为A国的首席计算机科学家，你的任务是编写一个程序决定这些策略可行与否。

inputFormat:
输入文件的第一行为两个整数N和M，表示B国的城市数和可以直接通讯的城市对数目。接下来的M行，每行包括两个整数Ci和Di (1 ≤ Ci, Di ≤ N 且 Ci ≠ Di)，表示城市Ci 和Di之间可以直接通讯。输入数据保证每对(Ci,Di)最多出现一次。

接下来一行是一个整数Q，表示A国首脑作出的策略数。接下来的Q行，每行包括三个整数Si, Ti, Mi (1 ≤ Si, Ti, Mi ≤ N，且Mi,Si,Ti三个数互不相等)，表示这个策略的内容是通过毁灭Mi来切断Si和Ti之间的联系。

outputFormat: 输出Q行，表示对应的策略可行与否。如果毁灭Mi以后，Si和Ti之间不能通讯，说明此策略可行，则应在第i行输出“yes”，否则输出“no”。

hint:
对于30%的数据，1 ≤ N ≤ 100,  1 ≤ Q ≤ 100

对于100%的数据，1 ≤ N ≤ 20000,  1 ≤ M ≤ 100000,  1 ≤ Q ≤ 100000

输入数据保证原图的任意两点是连通的。


title: [TJOI2008] Binary Land

background:
Binary Land是一款任天堂红白机上的经典游戏，讲述的是两只相爱的企鹅Gurin和Malon的故事。两只企鹅在一个封闭的迷宫中，你可以控制他们向上下左右四个方向移动。但是他们的移动有一个奇怪的规则，即如果你按“上”或“下”方向键，两只企鹅会同时向上移动或向下移动1格；如果你按“左”方向键，则Malon向左移动1格，同时Gurin向右移动1格；如果你按“右”方向键，则Malon向右移动1格，Gurin向左移动1格。当然，如果某只企鹅被障碍挡住，它就不会移动了。另外，在迷宫的某些格子处有蜘蛛网，如果任何一只企鹅进入这种格子，则游戏失败。两只企鹅不会相互阻挡，即在相向运动时他们可以“穿过”彼此，也可以同时处于同一格子里。迷宫的某个格子上有一颗红心，游戏的任务就是使两只企鹅同时到达这个格子。

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

description: 请编写程序找出完成任务所需的最少的操作步数。如果无法完成目标，输出“no”。

inputFormat:
第一行包含两个整数R, C 表示迷宫的长和宽。

按下来有R行，每行包含C个字符，描述了一个迷宫。其中’#’表示企鹅不能通过的障碍物，’X’表示蜘蛛网，’.’表示空地，’G’表示Gurin的初始位置，’M’表示Malon的初始位置，’T’表示终点位置。

输入数据保证标有’G’,’M’,’T’的格子分别只有一个，保证企鹅不可能走到迷宫以外。

outputFormat: 输出只有一行，为最少的操作步数。如果不能完成任务，输出“no”。

hint:
满足要求的一个操作序列为：上－右－左－左

3 ≤ R, C ≤ 30


title: [TJOI2008] 公共子串

description:
一个字符串的子串是在这个串基础上去掉0个或者若干个字符所形成的，例如abc, aa和abbc都是字符串aabbcc的子串，而aba不是。 现给你三个字符串，请问他们三个共同含有多少种子串（不算空串）?

注意： 有些相同的公共子串尽管出现在不同的位置，但仍算1种，详见样例。

inputFormat: 每组测试数据只有3行，每行都是一个只包含有小写字母的字符串。

outputFormat: 输出3个字符串共有的公共子串种类数。

hint:
3个字符串共有的公共子串有： “a”, “p”, “ap”, “pa”, “aa”, “apa”。 其中子串 “a” 有多个，但由于统计的是公共子串种类，所以 “a” 只算1种子串。

100%的数据中，字符串的长度不超过100。字符串中只含有小写字母。


title: [TJOI2008] 彩灯

description:
Peter 女朋友的生日快到了，他亲自设计了一组彩灯，想给女朋友一个惊喜。已知一组彩灯是由一排 $N$ 个独立的灯泡构成的，并且有 $M$ 个开关控制它们。从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有 $2^N$ 个样式。由于技术上的问题，Peter 设计的每个开关控制的彩灯没有什么规律，当一个开关被按下的时候，它会把所有它控制的彩灯改变状态（即亮变成不亮，不亮变成亮）。假如告诉你他设计的每个开关所控制的彩灯范围，你能否帮他计算出这些彩灯有多少种样式可以展示给他的女朋友？

注： 开始时所有彩灯都是不亮的状态。

inputFormat: 每组测试数据第一行为两个整数 $N$ 和 $M$，用空格隔开。紧接着是有 $M$ 行，每行都是一个长度为 $N$ 的字符串，表示一个开关控制彩灯的范围（$N$ 盏灯），如果第 $i$ 个字母是大写字母 `O`，则表示这个开关控制第 $i$ 盏灯，如果第 $i$ 个字母是大写字母 `X`，则表示这个开关不控制此灯。

outputFormat: 输出这些开关和彩灯可以变换出来的样式数目。由于这个值可能会很大，请求出它对于整数 $2008$ 的余数。

hint:
可见样例中第一个开关控制了所有的彩灯，而后两个开关分别控制了第一个和第二个彩灯，这样我们可以只用后两个开关控制彩灯，可以变换出来所有的 $2^2$ 个状态。

对于 $30\%$ 的数据，$N$ 和 $M$ 不超过 $15$。

另外有 $40\%$ 的数据，$N$ 和 $M$ 有一个为 $50$。

对于 $100\%$ 的数据，$N$ 和 $M$ 不超过 $50$。


title: [TJOI2008] 贪吃蛇

background: 佳佳和金明在玩一个新版的对战型贪吃蛇游戏：在一个长方体中，某些格子是障碍物，其余的格子里都有食物。佳佳把贪吃蛇放到其中一个有食物的格子中，然后金明控制贪吃蛇移动一步到相邻的有食物的格子中，然后佳佳再控制它移动一步，就这样双方轮流进行下去。要注意的是移动的时候只能向上下左右前后的六个方向之一移动，且不能走出长方体的边界（当然，有障碍物的格子也是不能走的）。并且游戏要求贪吃蛇每步都必须能吃到新的食物，即不能走回以前经过的格子（包括起点也不能走回）。游戏进行到某方不能再按照上述规则移动蛇时，这一方就输掉了。

description: 佳佳和金明都是十分聪明的孩子，他们在游戏中总是会选择对自己最有利的策略。因为贪吃蛇的初始位置是由佳佳指定的，现在佳佳想知道，能不能找到这样一个初始位置使得自己一定可以获胜呢？

inputFormat:
输入文件的第一行包含一个整数N，表示此文件包含的测试样例数。接下来就是N组样例的描述。

每组样例描述的第一行包含三个整数H,R,C，表示长方体的高度，长度和宽度。接下来是H个R行C列的矩阵，每个矩阵描述此长方体的一层。矩阵包含的字符只有’.’和’X’两种，其中’.’表示初始时有食物的格子，’X’表示障碍。这H个矩阵描述之间都用一个空行隔开。

outputFormat: 输出N行，表示对应的游戏中佳佳是不是一定可以获胜。如果佳佳可以获胜，输出“yes”，否则输出“no”。

hint:
对于40%的数据，H \* R \* C ≤ 16

对于100%的数据，H \* R \* C ≤ 100,  N ≤ 10

输入数据保证每个长方体至少包含一个不是障碍物的格子。


title: [TJOI2008] 小偷

background:
一位著名的小偷进入了一个充满宝石的储藏室，这个储藏室是由一连串房间构成的，房间的标号从 $0$ 开始，想进入第 $i$ 个房间就必须从第 $i-1$ 个房间进入，如图：

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

description:
上图为三个房间的情况，黑色的部分为连通两个房间的门，从左向右的编号分别为 $0,1,2\cdots$。已知当小偷从第 $0$ 个门进入储藏室时，储藏室的计时系统开始计时，每个门都有自己的关闭时间。每个屋里有不同种类的宝石，对于每种宝石，它的价值和小偷拿走它所耗费的时间也是不同的，为了简化问题，我们设想小偷在各个屋子之间走动的时间可以忽略不计，而且所有屋子里各种宝石的数量都是无限多的，那么请问小偷在能成功逃出来的情况下，可能获得宝石的最大价值。

附：对于每扇门，小偷都必须在严格早于此门关闭的时候出来才可以。

inputFormat: 每组测试数据的第一行有两个整数 $N$ 和 $M$，分别代表储藏室有 $N$ 个房间，并且有 $M$ 种宝石。第二行中会有 $N$ 个正整数，分别表示第 $i$ 个门关闭的时间（门的编号从 $0$ 开始），接下来的 $M$ 行，每行有三个整数 $r,v$ 和 $t$，分别代表这种宝石所在的房间编号为 $r$，它的价值为 $v$，小偷拿走它所耗费的时间为 $t$。

outputFormat: 输出小偷在成功逃出储藏室的情况下获得宝石的最大价值。

hint:
### 样例解释

虽然在第 $2$ 个房间中价值为 $5$ 的宝石好，但是不如拿两次价值为 $3$ 的宝石，在拿两次第 $0$ 房间中价值为 $1$ 的宝石，总价值为 $8$。

### 数据范围及约定

对于 $100\%$ 的数据，储藏室的屋子数量不超过 $50$，每扇门关闭的时间不超过 $1000$，并且宝石的数量不超过 $100$，价值不超过 $1000$。


title: [TJOI2009] 火星人的手机

background:
你应火星人之邀为他们设计一款新型的手机。我们知道在标准的地球人手机上，数字键共有 $10$ 个，$26$ 个字母 `a`…`z` 分别与某个数字键相关联，并且一个数字键上的若干字母必须是字母表中连续的一段。比如下图是地球手机的一个标准方案：

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

description:
我们要输入一个字母，必须连续按它所在的数字键若干次，次数即为这个字母在这个键的第几个位置。例如在上图的方案中，若我们要输入 `C`，就需要按三次数字键 `2`；若要输入 `M`，需按一次数字键 `6`。

火星人手机的构造与地球人手机类似，上面有 $M$ 个火星数字键，你需要把火星文的 $N$ 个字母放置在这 $M$ 个键上。（同样要求一个数字键上必须是连续的若干个火星字母）现在给定一段火星文中各个字母的出现次数，你设计的手机必须使得输入这段文字所需的按键次数最少。

inputFormat: 输入文件的第一行包括两个数字 $N$ 和 $M$，分别表示火星文字母数和火星手机的按键数。接下来有 $N$ 行，每行包含一个数字，依次表示每个字母在文章中的出现次数。这个次数不超过 $1000$。

outputFormat:
输出文件的第一行包括一个数字，表示最少的按键次数。

接下来的 $M$ 行表示一种设计方案：每行包含一个数，依次表示每个数字键上有几个火星字母。（这些数字可以为 $0$）

如果有多种方案可以得到最少的按键次数，你需要输出第一个数字键上包含字母最少的方案；如果仍有多种方案，你需要在其中选择第二个数字键上字母最少的方案；依此类推。


title: Isaac

background:
居润国迷上了一款游戏《以撒的结合重生》。他已经打到了最后一关，这一关有特殊的走位技巧。

1. 居润国从时刻 $0$ 开始，要控制以撒从起点走到终点。

2. 居润国只能在第 $k$ 时刻恰好走到终点。（从一个房间走到另一个房间居润国需要花费一个单位时间，居润国手速快，不会在同一个房间停留，以撒可以在这些房间中来回走动）

3. 若房间 $u$ 和 $v$ 相连，则居润国能控制以撒通过这两个房间的通道当且仅当以撒的血量大于等于 $f(u, v)$

4. 在这些房间之间有一堆怪物在游走。

5. 居润国为了求稳，于是上网找到了一个解码器，在代码中发现这些怪物们游走的房间有固定的规律：怪物每次都会从一个房间移动到另一个房间（也需花费一个单位时间），且他们总是在几个固定的房间按照固定的顺序内游走，游走的房间个数为 $T$。

为了不在玩游戏时失误，居润国希望能够避开所有的怪物走到终点，即无伤通过最后一关，同时希望你找到居润国控制的以撒完成这个任务至少需要的血量。对编程一窍不通的他找到了你，希望寻求解决。如果要是你无法解决，那么就光明正大地告诉他： `'IMP0SSBLE!!'` 他一定不会打死你的。

description: 求居润国是否能在上述条件要求下无伤通过最后一关。如果可以，输出居润国控制的以撒最少所需的血量 $B$，否则输出 `'IMP0SSBLE!!'`

inputFormat:
第一行有五个数，分别为 $n,m,s,t,k$，分别表示一共有 $n$ 个房间，以及 $m$ 对相邻房间及其通过所需要的血量，以 $s$ 为起点，$t$ 为终点，要在 $k$ 时刻恰好走到终点。

接下来 $m$ 行每行分别有三个数，分别是 $u,v,w$，表示房间 $u$ 和房间 $v$ 相邻，两个房间互相通过的血量均为 $w$。

接下来一行是单独的一个数 $a$，表示一共有 $a$ 只怪物

接下来有 $a$ 个数据分别表示每个怪物的游走规律

每个数据的第一个数 $T$ 表示怪物游走的房间个数，接下来有 $T$ 个房间编号表示从**第零时刻开始**怪物将从第一个房间按顺序和周期游走。

outputFormat: 仅一行，居润国控制以撒的最少所需血量 $B$，或是 `'IMP0SSBLE!!'`

hint:
共 $20$ 组数据。

对于 $15\%$ 的数据，$a = 0$，$k \leq 20$。

对于 $25\%$ 的数据，$a \leq 3$，$k \leq 1500$。

对于 $50\%$ 的数据，$a \leq 3$，$k \leq 10^4$。

对于 $70\%$ 的数据，$a \leq 20$，$k \leq 10^6$。

对于 $85\%$ 的数据，$a \leq 30$，$k \leq 10^8$。

对于 $100\%$ 的数据，$a \leq 30$，$k \leq 2*10^9$，$2 \leq T \leq 4$，$n \leq 50$，$m \leq 1250$。

所有输入皆在 int 范围内。

所有数据皆大于零，**可能会有重边，若一条边输入多次 则以最后一次出现的权值为准。**


title: [SHOI2012] 魔法树

background: SHOI2012 D2T3

description:
Harry Potter 新学了一种魔法：可以改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。

这棵果树共有 $N$ 个节点，其中节点 $0$ 是根节点，每个节点 $u$ 的父亲记为 $fa[u]$，保证有 $fa[u] < u$ 。初始时，这棵果树上的果子都被 Dumbledore 用魔法清除掉了，所以这个果树的每个节点上都没有果子（即 $0$ 个果子）。

不幸的是，Harry 的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry 的魔法可以这样描述：`A u v d` 。表示将点 $u$ 和 $v$ 之间的路径上的所有节点的果子个数都加上 $d$。

接下来，为了方便检验 Harry 的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：`Q u`。表示当前果树中，以点 $u$ 为根的子树中，总共有多少个果子？

inputFormat:
第一行一个正整数 $N (1 \leq N \leq 100000)$，表示果树的节点总数，节点以 $0,1,\dots,N - 1$ 标号，$0$ 一定代表根节点。

接下来 $N - 1$ 行，每行两个整数 $a,b (0 \leq a < b < N)$，表示 $a$ 是 $b$ 的父亲。

接下来是一个正整数 $Q(1 \leq Q \leq 100000)$，表示共有 $Q$ 次操作。

后面跟着 $Q$ 行，每行是以下两种中的一种：

1. `A u v d`，表示将 $u$ 到 $v$ 的路径上的所有节点的果子数加上 $d$。保证 $0 \leq u,v < N,0 < d < 100000$

2. `Q u`，表示询问以 $u$ 为根的子树中的总果子数，注意是包括 $u$ 本身的。

outputFormat: 对于所有的 `Q` 操作，依次输出询问的答案，每行一个。答案可能会超过 $2^{32}$ ，但不会超过 $10^{15}$ 。


title: [NOI2017] 整数

background: 在人类智慧的山巅，有着一台字长为 $1\,048\,576$ 位（此数字与解题无关）的超级计算机，著名理论计算机科学家 P 博士正用它进行各种研究。不幸的是，这天台风切断了电力系统，超级计算机无法工作，而 P 博士明天就要交实验结果了，只好求助于学过 OI 的你...

description:
P 博士将他的计算任务抽象为对一个整数的操作。

具体来说，有一个整数 $x$，一开始为 $0$。

接下来有 $n$ 个操作，每个操作都是以下两种类型中的一种：

- `1 a b`：将 $x$ 加上整数 $a\cdot 2^b$，其中 $a$ 为一个整数，$b$ 为一个非负整数

- `2 k` ：询问 $x$ 在用二进制表示时，位权为 $2^k$ 的位的值（即这一位上的 $1$ 代表 $2^k$）

保证在任何时候，$x\geqslant 0$。

inputFormat:
输入的第一行包含四个正整数 $n,t_1,t_2,t_3$，$n$ 的含义见题目描述，$t_1$，$t_2$，$t_3$ 的具体含义见子任务。

接下来 $n$ 行，每行给出一个操作，具体格式和含义见题目描述。

outputFormat: 对于每个询问操作，输出一行，表示该询问的答案（$0$ 或 $1$）。对于加法操作，没有任何输出。