title: [CERC2017] Hidden Hierarchy

description:
You are working on the user interface for a simple text-based file explorer. One of your tasks is to build a navigation pane displaying the directory hierarchy. As usual, the filesystem consists of directories which may contain files and other directories, which may, in turn, again contain files and other directories etc. Hence, the directories form a hierarchical tree structure. The top-most directoryin the hierarchy is called the root directory. If directory $d$ directly contains directory $e$ we will say that $d$ is the parent directory of $e$ while $e$ is a subdirectory od $d$. Each file has a size expressed in bytes. The directory size is simply the total size of all files directly or indirectly contained inside that directory.

All files and all directories except the root directory have a name — a string that always starts with a letter and consists of only lowercase letters and “``.``” (dot) characters. All items (files and directories) directly inside the same parent directory must have unique names. Each item (file and directory) can be uniquely described by its path — a string built according to the following rules:
   - Path of the root directory is simply “``/``” (forward slash).
   - For a directory $d$, its path is obtained by concatenating the directory names top to bottom along the hierarchy from the root directory to $d$, preceding each name with the “``/``” character and placing another “``/``” character at the end of the path.
   - For a file $f$ , its path is the concatenation of the parent directory path and the name of file $f$ .

We display the directory hierarchy by printing the root directory. We print a directory $d$ by outputting a line of the form “$m_d \ p_d \ s_d$” where $p_d$ and $s_d$ are the path and size of directory $d$ respectively, while $m_d$ is its expansion marker explained shortly. If $d$ contains other directories we must choose either to collapse it or to expand it. If we choose to expand $d$ we print (using the same rules) all of its subdirectories in lexicographical order by name. If we choose to collapse directory $d$, we simply ignore its contents.

The expansion marker $m_d$ is a single blank character when $d$ does not have any subdirectories, “``+``” (plus) character when we choose to collapse $d$ or a “``-``” (minus) character when we choose expand $d$.

Given a list of files in the filesystem and a threshold integer $t$, display the directory hierarchy ensuring that each directory of size at least $t$ is printed. Additionally, the total number of directories printed should be minimal. Assume there are no empty directories in the filesystem — the entire hierarchy can be deduced from the provided file paths. Note that the root directory has to be printed regardless of its size. Also note that a directory of size at least $t$ only has to be printed, but not necessarily expanded.

inputFormat:
The first line contains an integer $n(1 \le n \le 1 000)$ — the number of files. Each of the following $n$ lines contains a string $f$ and an integer $s(1 \le s \le 10^6)$ — the path and the size of a single file. Each path is at most $100$ characters long and is a valid file path according to the rules above. All paths will be different.

The following line contains an integer $t(1 \le t \le 10^9)$ — the threshold directory size.

outputFormat: Output the minimal display of the filesystem hierarchy for the given threshold as described above.

translation:
## 题目描述

假设你正在开发一个简单的以输入文字为基础的文件夹浏览器。你的工作之一就是要构建一个导航目录来显示这些文件夹的上下关系。通常而言，这些文件夹很可能是互相嵌套的——比如，某个文件夹下还有一个文件夹，当然也可能会包含某些文件。因此，这些文件夹会形成一种树状结构。在这个目录中，最顶端的那个文件夹称之为根目录。如果文件夹d中直接含有文件夹e，那么我们称之为文件夹d是文件夹e的父文件夹，而文件夹e是文件夹d的子文件夹。每个文件都有一个用字节数来表示的大小。一个文件夹的大小是被直接或不直接包含于其中的所有文件的大小之和。

所有的文件和文件夹（除根目录外）都有一个名字——一个只由小写字符和点（“."）组成并且只由小写字母开头的字符串。包含于同一个父目录下的文件或文件夹的名字必定各不相同。而且，路径与文件是一一对应的。生成路径的规则如下：

- 根目录路径是“/”
- 文件夹d的路径是从根目录开始，沿着文件夹的父子关系，顺次往下，在每个文件夹名字前添加一个“/”，相互连接，并在路径的最末尾添加一个“/”。
- 文件f的路径是由它的父文件夹的路径加上文件名得到的。

通过打印根目录，我们能够显示文件夹的上下父子关系。打印文件夹d时，我们输出一个“md pd sd”形式的字符串。其中，pd是文件夹d的路径，sd是文件夹d的大小，md是文件夹d的扩展标记。如果文件夹d包含其他文件夹，我们可以选择是否展开它。如果我们要展开文件夹d，我们就要以字典序打印它里面包含的所有文件和文件夹。如果我们不打开文件夹d，那么我们就可以忽略其中的内容。

如果d是一个空文件夹（即没有包含任何文件或文件夹），那么md就仅仅是一个空字符。当我们要展开这个文件夹的时候，md是一个“-”，而如果我们不展开这个文件夹的是md是一个“+”。

现在，输入一列文件和一个限制性整数t。请你打印（按照前述展开打印方法）所有的大小不小于t的文件夹。并且，打印的文件夹总数一定是最小的。保证不存在空文件夹即整个文件夹上下关系都可从输入的文件路径中推断得出。注意，大小不小于t的文件夹必须要被打印，但不一定要展开。根目录不论多大都要被打印。

## 输入输出格式

### 输入格式

第一行输入包含一个整数n（1<=n<=1000）表示文件的总数。之后的n行中，每行包含一个字符串f和一个整数s（1<=s<=10^6）。其中，f表示文件路径和单个文件的大小。每个路径最多含有100个字符并保证是一个合法路径。所有的路径保证各不相同。

之后的一行包含限制性整数t（1<=t<=10^9）。

### 输出格式

按照前述方法输出最少的展开文件的方法。

samples:
9
/sys/kernel/notes 100
/cerc/problems/a/testdata/in 1000000
/cerc/problems/a/testdata/out 8
/cerc/problems/a/luka.cc 500
/cerc/problems/a/zuza.cc 5000
/cerc/problems/b/testdata/in 15
/cerc/problems/b/testdata/out 4
/cerc/problems/b/kale.cc 100
/cerc/documents/rules.pdf 4000
10000

samples:
- / 1009727
- /cerc/ 1009627
/cerc/documents/ 4000
- /cerc/problems/ 1005627
- /cerc/problems/a/ 1005508
/cerc/problems/a/testdata/ 1000008
+ /cerc/problems/b/ 119
+ /sys/ 100

samples:
8
/b/test/in.a 100
/b/test/in.b 1
/c/test/in.a 100
/c/test/in.b 1
/c/test/pic/in.a.svg 10
/c/test/pic/in.b.svg 10
/a/test/in.a 99
/a/test/in.b 1
101


title: [CERC2017] Intrinsic Interval

type: P

description:
Given a permutation $\pi$ of integers $1$ through $n$, an interval in $\pi$ is a consecutive subsequence consisting of consecutive numbers. More precisely, for indices $a$ and $b$ where $1 \le a \le b \le n$, the subsequence $\pi^b_a = (\pi_a, \pi_{a+1}, . . . ,\pi_b)$ is an interval if sorting it would yield a sequence of consecutive integers.

For example, in permutation $\pi = (3, 1, 7, 5, 6, 4, 2)$, the subsequence $\pi^6_3$ is an interval (it contains the numbers $4$ through $7$) while $\pi^3_1$ is not.

For a subsequence $\pi^y_x$ its intrinsic interval is any interval $\pi^b_a$ that contains the given subsequence $(a \le x \le y \le b)$ and that is, additionally, as short as possible. Of course, the length of an interval is defined as the number of elements it contains.

Given a permutation $\pi$ and $m$ of its subsequences, find some intrinsic interval for each subsequence.

inputFormat:
The first line contains an integer $n(1 \le n \le 100 000)$ — the size of the permutation $\pi$. The following line contains $n$ different integers $\pi_1, \pi_2, . . . , \pi_n (1 \le \pi_j \le n)$ — the permutation itself.

The following line contains an integer $m(1 \le m \le 100 000)$ — the number of subsequences. The $j-th$ of the following $m$ lines contains integers $x_j$ and $y_j(1 \le x_j \le y_j \le n)$ — the endpoints of the $j-th$ subsequence.

outputFormat: Output $m$ lines. The $j-th$ line should contain two integers $a_j$ and $b_j$ where $1 \le a_j \le b_j \le n$ — the endpoints of some intrinsic interval of the $j-th$ subsequence $\pi^{y_j}_{x_j}$.

translation:
### 题目描述

对于正整数 $1,2,3 \cdots n$ 的一个排列 $\pi$，若它的一个子串 $\pi[a..b]$ 排序后是连续正整数，则称 $\pi[a..b]$ 是一个“区间”。例如对排列 $pi={3,1,7,5,6,4,2}$，子串 $\pi[3..6]$ 是一个“区间”（因为它包含 $4,5,6,7$），$\pi[1..3]$ 则不是。

一个子串的“本征区间”是包含该子串的最短区间。“包含”是指：若 $\pi[x..y]$ 的本征区间是 $\pi[a..b]$，则 $a \le x \le y \le b$。

给定一个排列 $\pi$ 及其 $m$ 个子串，求每个子串的“本征区间”。

### 输入格式

第一行一个整数 $n(1 \le n \le 100000)$。

第二行 $n$ 个整数，代表排列 $\pi$。

第三行一个整数 $m(1 \le m \le 100000)$。

此后 $m$ 行，每行两个整数 $x,y(1 \le x \le y \le n)$，代表子串 $\pi[x..y]$。

### 输出格式

输出 $m$ 行，每行两个整数 $a,b(1 \le a \le b \le n)$，代表子串对应的本征区间 $\pi[a..b]$。


title: 【模板】"动态DP"&动态树分治（加强版）

background:
树剖常数小！跑不满！

shadowice1984 为了向你证明他能卡树剖并且会卡树剖从而出了这道毒瘤题。

保证答案均在 `int` 范围内。

然后就被离线算法针对了……

因此这道题变成了强制在线。

description:
同 [P4719](https://www.luogu.com.cn/problem/P4719)。

给定一个 $n$ 个点的带点权树，进行 $m$ 次修改点权的操作。

你需要在每次修改之后输出树上最大带权独立集的权值之和。

inputFormat:
同 [P4719](https://www.luogu.com.cn/problem/P4719)。

第一行两个正整数 $n$，$m$ 表示树的点数和总操作个数

第二行 $n$ 个整数 $V_1,\dots,V_n$ 表示每个点的点权。

接下来 $(n - 1)$ 行，每行两个整数 $u, v$，表示存在一条连接 $u$ 与 $v$ 的边。

接下来 $m$ 行每行两个整数 $x$，$y$ 表示将 $x$ 的点权修改为 $y$。

对于第 $1$ 行，$x$ 即为被操作的点的编号。

对于第 $2$ 到 $m$ 行，被操作的点的编号 $=x\oplus lastans$。

其中 $lastans$ 是上一次操作后输出的答案，$\oplus$ 表示按位异或操作。

outputFormat: 输出 $m$ 行，第 $i$ 行表示表示第 $i$ 次操作之后树上最大带权独立集的权值和。

hint:
数据范围 $n \leq 1 \times 10^6$，$m \leq 3 \times 10^6$。保证任意时刻各点点权的绝对值 $\leq 100$。

时限为标程的二倍，如果卡常数的话请使用 `int` 类型。


title: [CERC2017] Justified Jungle

description:
As you probably know, a tree is a graph consisting of $n$ nodes and $n - 1$ undirected edges in which any two nodes are connected by exactly one path. A forest is a graph consisting of one or more trees.

In other words, a graph is a forest if every connected component is a tree. A forest is justified if all connected components have the same number of nodes.

Given a tree $G$ consisting of n nodes, find all positive integers $k$ such that a justified forest can be obtained by erasing exactly $k$ edges from $G$. Note that erasing an edge never erases any nodes. In particular when we erase all $n - 1$ edges from $G$, we obtain a justified forest consisting of $n$ one-node components.

inputFormat: The first line contains an integer $n(2 \le n \le 1 000 000)$ — the number of nodes in $G$. The $k-th$ of the following $n - 1$ lines contains two different integers $a_k$ and $b_k(1 \le a_k, b_k \le n)$ — the endpoints of the $k-th$ edge.

outputFormat: The first line should contain all wanted integers $k$, in increasing order.

translation:
### 题目描述
给你一棵包含 $ N $ 个节点的树 $ (N \leq 10^6) $，求可以通过删除树上的多少条边，使得得到的森林满足其中所有的树都包含相同数量的节点。输出所有合法的删边数量。

合法的删边数量 $ k $ 指的是存在至少一种方案，删去了恰好 $ k $ 条边，得到的森林满足其中所有的树都包含相同数量的节点。

### 输入格式
第一行有一个正整数 $ N $ ，表示树的点数。
接下来 $ N - 1 $ 行，每行两个正整数 $ a , b $ ，表示一条连接点 $ a $ 与点 $ b $ 的无向边。

### 输出格式
输出一行，包含若干个以空格分隔的正整数，表示所有合法的删边数量。


title: [CERC2017] Kitchen Knobs

description:
You are cooking on a gigantic stove at a large fast-food restaurant. The stove contains $n$ heating elements arranged in a line and numbered with integers $1$ through $n$ left to right. Each element is operated by its control knob. The knobs are a bit unusual: each knob is marked with seven non-zero digits evenly distributed around a circle. The power of the heating element is equal to the positive integer obtained by reading the digits on its control knob clockwise starting from the top of the knob.

[![PujzQA.md.png](https://s1.ax1x.com/2018/07/12/PujzQA.md.png)](https://imgchr.com/i/PujzQA)

In a single step, you can rotate one or more consecutive knobs by any number of positions in any direction. However, all knobs rotated in one step need to be rotated by the same number of positions in the same direction.

Find the smallest number of steps needed to set all the heating elements to maximal possible power.

inputFormat: The first line contains an integer $n(1 \le n \le 501)$ — the number of heating elements. The $j-th$ of the following $n$ lines contains an integer $x_j$ — the initial power of the $j-th$ heating element. Each $x_j$ consists of exactly seven non-zero digits.

outputFormat: Output a single integer — the minimal number of steps needed.

translation:
题目描述

你正一家大型的快餐餐厅的巨型灶台上烹饪。这个灶台上有n个炉子排成一排，并按序标为1-n号。每个炉子都会被它的控制手柄所控制。这些手柄可不一般：每个手柄上面都有1-7的号码围成一圈。灶台的火力就是从它的控制手柄顶端开始顺时针读取数字而得到的。

【图片】：样例数据1输入的初始手柄位置如图所示。

每一步你都可转动一个或多个相邻手柄——向任意方向转动任意几下。但是，同一步转动的手柄只能向同一方向转动同样的次数。

找到最少的步数来吧所有的炉子都设定到可能的最大火力。

输入输出格式

输入格式

第一行包含一个整数（1<=n<=501）表示炉子的数量。接下去第j行包含7个非零整数，其中第一个是初始火力大小。

输出格式

输出一个整数，表示需要的步数。

hint: In the first example, one of the ways to achieve maximal possible power is: rotate knobs $2$ through $3$ by $3$ positions in the counterclockwise direction, rotate knob $3$ by $3$ positions in the counterclockwise direction, and rotate knobs $4$ through $6$ by $2$ positions in the clockwise direction.


title: [CERC2017] Lunar Landscape

description:
A satellite is surveying a possible rover landing area on the moon. The landing area is modeled as a square grid embedded in the standard coordinate system.

The satellite has taken $n$ photos, each capturing a square area of the surface. Careful camera calibration has ensured that all photos are aligned with the grid — all four vertices have integer coordinates. Due to the satellite’s changing orbit there are two types of photos:
   - Photos of type ``A`` have sides that are parallel to coordinate axes. Such a photo is specified by giving the integer coordinates $(x, y)$ of the square’s middle point and the length of its side $a$ — always an even integer.
   - Photos of type ``B`` have sides at a $45^{\circ}$ angle to the coordinate axes. Such a photo is specified by giving the integer coordinates $(x, y)$ of the square’s middle point and the length of its diagonal $d$ — always an even integer.

Find the total surface area captured in the satellite photos.

inputFormat:
The first line contains an integer $n(1 \le n \le 200 000)$ — the number of photos. The $j-th$ of the following $n$ lines is either of the form “$A \ x_j \ y_j  \ a_j$” or “$B \ x_j \ y_j \ d_j$” representing a photo of type ``A`` or ``B``,respectively.

The $x_j$ and $y_j$ are the integer coordinates of the middle point of the photo $(-1 000 \le x_j, y_j \le 1 000)$. The $a_j$ and $d_j$ are even integers $(2 \le a_j, d_j \le 1 000)$ — the side length and the diagonal length, respectively.

outputFormat: Output a number with exactly two digits after the decimal point — the total area of the surface. The answer has to exactly correspond to the judge’s solution (no rounding errors are tolerated).

translation:
（具体字母格式懒得操作）

月球的景观

题目描述

一个卫星正在为探测车在月球上寻找一个合适的降落区。降落区被看做在平面直角坐标系中的一个方形区域。

这颗卫星已经照了n张照片，每张照片都涵盖了月球表面的一块正方形区域。经过对相机的精细校准，可以保证所有照片涵盖的区域都和坐标对齐——正方形四个角的坐标都为整数。由于卫星的轨道一直在变化，所以照片有两种形式：
·A类照片的边缘和坐标轴平行。对于这样的照片，题目将会给出它中心的坐标(x,y)和它的边长a（a为偶数）。
·B类照片的边缘和坐标轴呈45°角。对于这样的照片，题目将会给出它中心的坐标(x,y)和它对角线的长度d（d为偶数）。

求出卫星图片拍摄到平面的总大小。

输入输出格式

输入格式：

第一行有一个整数n(1≤n≤200000)表示照片的数量。接下来n行中第j行的格式是"A xj yj aj"或"B xj yj dj" ，分别表示这张照片的类型是A或B。

xj和yj是这张图片中心的坐标(1000≤xj,yj≤1000)。aj和dj为偶数(2≤aj,dj≤1000)，分别表示正方形的边长和对角线长度。

输出格式：

输出平面总的大小，保留两位小数。答案必须和标准答案严格相等（精度问题零容忍↖(^ω^)↗）。


title: [CERC2014] Parades

description:
In The City of Eternal Festivities, there are $n$ street junctions and $n-1$ bidirectional streets,each street connecting two of the junctions. Between every two junctions, there is exactly one (direct or indirect) path connecting them. No junction is an endpoint for more than 10 streets.

Every 13th of September (the 256th day of the year), there are many festivities going on in The City. In particular, the citizens want to organize $m$ parades. The parade number $i$ starts at junction $u_i$ and ends at $v_i$, following the unique path between the endpoints.

As the mayor of The City, you are responsible for citizens’ safety. Therefore you decreed that no two parades are ever allowed to use the same street, though they can have common junctions,or even common endpoints.

To appease your citizens, try to organize as many parades as possible, without breaking the safety regulations.

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

The first line of each test case contains a single integer: the number of junctions $n(2 \le n \le 1000)$. Each of the next $n - 1$ lines contains two integers $a, b(1 \le a ≠ b \le n)$, denoting that junctions $a$ and $b$ are connected by a street. Each junction has at most $10$ streets leaving it.

The next line contains a single integer: the number of planned parades $m, 0 \le m \le (_2^n)$.

Each of the next $m$ lines contains two integers $u_i, v_i (1 \le u_i ≠ v_i \le n)$,meaning that a parade is planned to start at junction $u_i$, and finish at junction $v_i$. No two parades share both endpoints.

outputFormat: For each test case, output one line containing the largest number of parades that can be organized with no street used by more than one parade.

translation:
在永恒庆典的城市里，有N个街道路口和N-1个双向街道，每条街道连接两个路口。在每两个路口之间，正好有一条（直接或间接）连接它们的路径。没有路口是超过10条街道的终点。

九月的每第十三天（一年中的第二百五十六天），城市里会有很多庆祝活动。特别是市民要组织M游行。游行I从路口UI开始，结束于VI，是两端点之间的唯一路径。

作为城市的市长，你要对市民的安全负责。因此，你颁布法令，不允许两个游行使用同一条街，尽管它们可以有共同的连接点，甚至共同的端点。

为了安抚你的公民，在不违反安全条例的情况下，组织尽可能多的游行。

第一行输入包含测试用例T的数量。测试用例的描述如下：

每个测试用例的第一行包含一个整数：结点数n（2≤n≤1000）。 接下来的n-1行中的每一行包含两个整数a，b（1≤a≠b≤n），表示端点a和b由街道连接。 每个交叉路口最多有10条街道。

下一行包含一个整数：计划游行的数量m($0≤m≤{n\choose   2})$)。

接下来的m行中的每一行包含两个整数ui，vi（1≤ui≠vi≤n），这意味着游行计划从交叉点ui开始，并在交叉点vi处完成。 没有两个游行共享两个端点。

对于每个测试用例，输出一行包含最多数量的游行，这些游行可以被组织，不会有多个游行使用的相同的街道。


title: [CERC2014] Mountainous landscape

description:
You travel through a scenic landscape consisting mostly of mountains – there are $n$ landmarks (peaks and valleys) on your path. You pause for breath and wonder: which mountain are you currently seeing on the horizon?

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

Formally: you are given a polygonal chain $P_1,P_2,\cdots,P_n$ in the plane. The $x$ coordinates of the points are in strictly increasing order. For each segment $P_i P_{i+1}$ of this chain, find the smallest index $j > i$, for which any point of $P_j P_{j+1}$ is visible from $P_i P_{i+1}$ (lies **strictly above** the ray $P_i \ P^{\rightarrow}_{i+1}$).

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

The first line of each test case contains an integer $n(2 \le n \le 100 000)$ – the number of vertices on the chain.

Each of the following $n$ lines contains integer coordinates $x_i, y_i$ of the vertex $P_i (0 \le x_1 < x_2 < \cdots < x_n \le 10^9, 0 \le y_i \le 10^9)$.

outputFormat: For each test case, output a single line containing $n-1$ space-separated integers. These should be the smallest indices of chain segments visible to the right, or $0$ when no such segment exists.

translation:
- 给定平面内一个由点依次连接起来形成的折线 $P_1,P_2,\cdots,P_n$，保证 $x$ 坐标递增。
- 对于折线上的所有线段，找到最小的 $j>i$，使得存在一个在 $P_jP_{j+1}$ 上的点可以被 $P_iP_{i+1}$ 上的任何一个点看到，也就是**严格**在射线 $P_iP_{i+1}$ 上方。若没有，输出 $0$.
- 多组数据。

$2\le n\le 10^5$，坐标均在 $10^9$ 以内。


title: [CERC2014] Sums

description:
Given an integer $N$, express it as the sum of at least two consecutive positive integers. For example:

   - $10 = 1 + 2 + 3 + 4$
   - $24 = 7 + 8 + 9$

If there are multiple solutions, output the one with the smallest possible number of summands.

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

Each test case consists of one line containing an integer $N(1 \le N \le 10^9)$.

outputFormat:
For each test case, output a single line containing the equation in the format:
``N = a + (a+1) + ... + b`` as in the example. If there is no solution, output a single word ``IMPOSSIBLE`` instead.

translation:
## 题目大意

一共有 $T$ 组数据，每组数据给定一个数 $N$，请将 $N$ 分解为几个连续正整数的和，如果有多种情况，请输出最小数最大的情况。

## 输入格式：

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

第 $2$ 行至第 $T+1$ 行，每行一个整数 $N$，表示要拆分的数字。

## 输出格式

 $T$ 行，每行一个式子，表示拆分结果。

如果无解，请输出 `IMPOSSIBLE`。


title: [CERC2014] Wheels

description:
A very important and complicated machine consists of $n$ wheels, numbered $1, 2, . . . , n$. They are actually cogwheels, but the cogs are so small that we can model them as circles on the plane.

Every wheel can spin around its center.

Two wheels cannot overlap (they do not have common interior points), but they can touch.

If two wheels touch each other and one of them rotates, the other one spins as well, as their micro-cogs are locked together.

A force is put to wheel $1$ (and to no other wheel), making it rotate at the rate of exactly one turn per minute, clockwise. Compute the rates of other wheels’ movement. You may assume that the machine is not jammed (the movement is physically possible).

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

Each test case consists of one line containing the number of wheels $n(1 \le n \le 1000)$ .

Each of the following lines contain three integers $x, y$ and $r(-10 000 \le x, y \le 10 000, 1 \le r \le 10 000)$ where $(x, y)$ denote the Cartesian coordinates of the wheel’s center and $r$ is its radius.

outputFormat: For each test case, output $n$ lines, each describing the movement of one wheel, in the same order as in the input. For every wheel, output either ``p/q clockwise`` or ``p/q counterclockwise``,where the irreducible fraction $p/q$ is the number of wheel turns per minute. If $q$ is $1$, output just $p$ as an integer. If a wheel is standing still, output ``not moving``.

translation:
一个非常重要和复杂的机器由$n$个轮子组成，编号为$1,2,…,n$。它们其实是齿轮，但是齿太小了，我们可以把它们近似看成成平面上的圆。

每一个齿轮都能围绕它的中心旋转。

两个齿轮不会重叠（因为它们内部没有共同的点），但它们可以互相接触。

如果两个齿轮相互接触，其中一个齿轮转动，另一个齿轮也随之转动，因为它们的齿被卡在一起。

一个力作用于齿轮1（并且力没有作用于其他齿轮），使它以每分钟转一圈的速度顺时针旋转。计算其他齿轮的运动速度。你可以假设机器没有卡住（运动在物理理论上是可以的）。

输入格式：

输入包括多组数据，第一行为组数$T$；

对于每组数据如下：

第一行包括一个齿轮数$n,(1 \le n \le 1000)$。

接下来$n$行每行包含三个整数$x,y,r,(10000≤x,y≤10000,1≤r≤10000)$，其中$(x,y)$表示齿轮中心的笛卡尔坐标（直角坐标），$r$是其半径。

输出格式：

对于每组数据，输出$n$行，第$i$行为第$i$个齿轮的运动状态。对于每个齿轮，输出或`p/q clockwise`或`p/q counterclockwise`，其中最简分数`p/q`是每分钟齿轮转数。如果$q$为$1$，则输出整数$p$。如果齿轮静止不动，则输出`not moving`。

samples:
1 clockwise
3/2 counterclockwise
2 counterclockwise
3/2 clockwise
not moving


title: [CERC2014] Vocabulary

description:
According to a popular belief, computer programmers drink a lot of coffee and know only a few words. The vocabulary of a typical programmer consists of just three words. Besides, he rarely knows how to spell them. To help programmers with their spelling mistakes, we published a book titled $The \ Dictionary \ of \ the \ Three \ Words \ Every \ Typical \ Programmer \ Should \ Know$.

You got a copy of the book but, soon after that, you spilled your coffee over it.

Now, youcannot read some of the characters. Fortunately, the three words were, as usually in dictionaries,distinct and printed in lexicographical order.
Before you attempt to use that fact to recover the missing characters, you want to know in how many different ways you can do it. Since you expect this number might be large, you want to know it modulo $10^9 + 9$.

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

Each test case consists of three lines, each containing a single nonempty word – in the order they appear in the dictionary. Words consist of small letters of the English alphabet and question marks, the latter denoting missing characters. Each word is at most $1 000 000$ characters long.

outputFormat: For each test case, output one line containing the number of different ways you can substitute each question mark with one of the $26$ letters from ``a`` to ``z`` in such a way that the three words are distinct and in lexicographical order. The number should be printed modulo $10^9 + 9$.

translation:
给你三个字符串，这些字符串有些单词模糊不可认了，用"?"来代表。
现在你可以用任意英文小写字母来代表它们。要求是使得给定的三个字符串中
所有的"?"被你认定的字母代替后，各不相同且按字典序出现。问有多少种方式。

输入：先给出一个数字N，代表数据组数。
接下来3*N行，每行给出一个字符串。长度<=1000 000

输出：输出结果 Mod 10^9+9

samples:
3
?heoret?cal
c?mputer
?cience
jagiellonian
?niversity
kra?ow
?
b
c


title: [CERC2014] Virus synthesis

description:
Viruses are usually bad for your health. How about fighting them with... other viruses? In this problem, you need to find out how to synthesize such good viruses.

We have prepared for you a set of strings of the letters $A, G, T$ and $C$. They correspond to the DNA nucleotide sequences of viruses that we want to synthesize, using the following operations:

   - Adding a nucleotide either to the beginning or the end of the existing sequence.
   - Replicating the sequence, reversing the copied piece, and gluing it either to the beginning or to the end of the original (so that e.g., $AGTC$ can become $AGTCCTGA$ or $CTGAAGTC$).

We’re concerned about efficiency, since we have very many such sequences, some of them very long. Find a way to synthesize them in a minimum number of operations.

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

Each test case consists of a single line containing a non-empty string. The string uses only the capital letters $A, C, G$ and $T$ and is not longer than $100 000$ characters.

outputFormat: For each test case, output a single line containing the minimum total number of operations necessary to construct the given sequence.

translation:
初始有一个空串，利用下面的操作构造给定串 $S$ 。

1、串开头或末尾加一个字符

2、串开头或末尾加一个该串的逆串

求最小化操作数， $|S| \leq 10^5$，字符集为 $\{A,T,C,G\}$。

Translated by  @wasa855

samples:
4
AAAA
AGCTTGCA
AAGGGGAAGGGGAA
AAACAGTCCTGACAAAAAAAAAAAAC


title: [CERC2014] Bricks

description:
You are given a sequence of white $(W)$ and black $(B)$ bricks. The goal is to partition it into some number of non-empty, contiguous blocks, each one having the same ratio of white and black bricks.

Of course one can always “partition” the sequence into one single block (which is not very interesting). We want, however, to have as many blocks as possible. Consider for example the following sequences and its partitions:

   - $BWWWBB = BW + WWBB$ (ratio 1:1),
   - $WWWBBBWWWWWWWWWB = WWWB + BBWWWWWW + WWWB$ (ratio 3:1).

Note that both of these partitions are optimal with respect to the number of blocks.

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

Each test case starts with one line containing an integer $n(1 \le n \le 10^5)$ which is the length of the description of a sequence. Each of the following $n$ lines consists of an integer $k(1 \le k \le 10^9)$ and one of the characters $W$ or $B$, meaning that $k$ bricks of the given color follow next in the sequence. It is guaranteed that the total length of the brick sequence does not exceed $10^9$.

outputFormat: For each test case, output a single line containing the largest possible number of blocks.

translation:
题目描述
给你一个由'B'和'W'组成的序列，将其按分成最多的区间且每个区间的'B':'W'的值相等

输入输出格式

输入格式：
多组数据，第一行一个整数T表示数据组数
每组数据的第一行为一个整数n，接下来n行，每行一个整数k和一个字符（'B'或'W'）表示在上一个序列后有一个长度为k的'B'或'W'的序列，序列的总长度不超过10^9

输出格式：
共T行，每行一个整数表示能分成的最多的区间数


title: [CERC2014] Pork barrel

description:
Winning the election was simpler than you expected: it was enough to promise to finally build a good quality, country-wide road infrastructure, of course without crippling the budget... Your happiness did not last long, however: it seems, that the citizens have found a way to actually hold you accountable for your promise!

There are $n$ major cities in your country. The Ministry of Transport has prepared a detailed map, outlining $m$ possible highway connections, together with their costs. The Quality Assurance Committee will not let you build a highway cheaper than $l$, and the National Spendings Regulatory Committee will not let you build a highway more expensive than $h$. To claim a “country-wide” network, you have to connect (possibly indirectly) as many pairs of cities, as it is possible within these two constraints. You have to find the cheapest way to do it, and you have to find it quickly! Of all networks that meet the constraints and connect the most pairs of cities,compute the cost of the cheapest one.

To make things worse, both committees are heavily influenced by your angry competitors:each time you publish your hard-prepared plan, they immediately change their rulings $l$ and $h$,and you are forced to start from scratch.

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

The first line of each test case contains integers $n$ and $m(1 \le n \le 1000, 0 \le m \le 100 000)$ – the number of cities in the country, and of possible direct connections, respectively.

Each of the following $m$ lines contains three integers $x, y, w (1 \le x ≠ y \le n, 1 \le w \le 1 000 000)$, denoting that the cities $x$ and $y$ can be connected by a bidirectional highway at cost $w$. There might be many ways to connect a single pair of cities.

The following line contains an integer $q(1 \le q \le 1 000 000)$ – the number of rulings of the committees. Each of the following $q$ lines contains two integers. The first of the lines contains the initial rulings $l_1, h_1$, given directly. The rest of the rulings are encoded. The numbers in the $j-th$ of the lines for $j > 1$ are $l_j + c_{j -1}$ and $h_j + c_{j-1}$, where $l_j$ and $h_j$ are the actual rulings and $c_{j-1}$ is the correct answer for the preceding rulings $l_{j-1}$ and $h_{j-1}$.

All rulings satisfy $1 \le l_j \le h_j \le 1 000 000$.

outputFormat: For each test case, output $q$ lines, one for each ruling. In the $j-th$ of them,output the minimal cost $c_j$ of building a highway network which adheres to the committees’ constraints, and creates the maximum number of connected pairs of cities.

translation:
给定 $n$ 个点 $m$ 条边有边权的无向图，有 $q$ 个询问，每次询问权值在 $[L,R]$ 内的边组成的最小生成森林的权值。

本题强制在线。对于每组测试数据的第 $j\,(j\ge 2)$ 组询问，输入的 $L',R'$ 需要均减去第 $j-1$ 组询问对应的答案后，才可以得到该询问 $L,R$ 实际的值。

数据范围：$n \le 1000, m \le 100000, q \le 1000000$。


title: [CERC2014] The Imp

description:
You arrive in Ye Olde Magic Shoppe with some hard-earned gold to purchase wondrous and unique magic items. There are $n$ such items in the shop, each of them locked in a special magic box. The $i-th$ box costs $c_i$ gold pieces to buy, and contains an item worth $v_i$ gold pieces. The costs and item values are known to you, as you have previously read, mastered, and memorized Ye Olde Magic Catalogue.

A mortal, such as you, can safely carry only one magic item. You therefore aim to get the most precious one. And obtain it you would, if not for a malicious, magical creature, known as The Imp.

The Imp can cast a mischievous spell, which transforms the content of any magic box into worthless dust. Of course, he will use the spell just after you buy a box, to make you pay for the item and not get it. You are thus forced to buy another box, and then the next one...

The Imp has enough magic to cast the spell at most $k$ times. He can, of course, refrain from using it, allowing you to keep an item. You can walk away at any time, empty-handed (though it would surely be a disgrace). However, if you get an item, you must keep it and leave the shop.

You aim to maximize your gain (the value of the acquired item minus all the expenses paid previously), while The Imp wants to minimize it. If both you and the creature use the optimal strategy, how much gold will you earn?

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of
the test cases follow:

Each test case starts with a line containing the number of items $n(1 \le n \le 150 000)$ and the the maximum number of The Imp’s spells $k(0 \le k \le 9)$.

The next $n$ lines contain the items’values and costs, the $i-th$ line containing the numbers $v_i$ and $c_i$, in that order $(0 \le v_i, c_i \le 10^6)$.

outputFormat: For each test case, output one line containing your gain.

translation:
## 题目描述

你带着一些来之不易的金币来到了 Ye Olde 魔法商店，想要购买一些妙不可言的魔术物品。商店里有 $n$ 个魔术实体，每个实体都锁在一个特殊的魔术宝箱中。第 $i$ 个宝箱（和其中的实体）的售价为 $c_i$个金币，而其中实体的价值相当于 $v_i$ 个金币。你作为曾经完整钻研了《Ye Olde 魔法目录》的顶级做题家，当然毫无疑问地记住了每个盒子和其中实体的售价和价值。

然而像你这样的凡人，只能安全地携带一件魔法实体。因此，你想要得到最宝贵的一个。你本可以直接得到它的——如果不是因为调皮而又神奇的小恶魔的话。

小恶魔可以使用魔法，从而将某一个魔术宝箱内的实体转化为毫无价值的灰尘。当然，他会在你购买一个魔术宝箱后立即对其使用该魔法，这样你就为这个宝箱付了钱而没能得到里面的实体。因此，你被迫另买一个，再买一个……

小恶魔拥的魔力最多可以用来使用 $k$ 次魔法。当然，他可以不用完这 $k$ 次魔法，而你也可以随时空手走开（尽管这是一个奇耻大辱）。但是，如果你成功地买到了到一个实体（而没有被变成灰尘），则你必须保留该实体并离开商店。

你的目标是最大化你的收益（所购实体的价值减去支付的所有费用（包括购买当前实体和之前的灰尘）），而小恶魔则希望将其最小化。如果你和小恶魔都使用最佳策略，那么你的收益将会相当于多少金币？

## 输入格式

**本题每个测试点包含多组数据。**

第一行包含一个正整数 $T$ 表示测试数据组数。
每组数据的第一行包括两个数 $n$ 和 $k$ ，分别表示魔术实体个数和小恶魔使用魔法的最大次数。
接下来 $n$ 行，第 $i$ 行包括两个数 $v_i$ 和 $c_i$，意义如【题目描述】所述。同一行的数用空格隔开。

## 输出格式

对于每组数据，输出一行一个数表示答案。

## 数据范围与提示

$1\le n\le1.5\times10^5,0\le k\le9,0\le v_i,c_i\le10^6$。


title: [CERC2014] Outer space invaders

description:
The aliens from outer space have (finally!) invaded Earth. Defend yourself, or be disintegrated!

Or assimilated. Or eaten. We are not yet sure.

The aliens follow a known attack pattern. There are $n$ attackers, the $i-th$ one appears at time $a_i$, at distance $d_i$ from you. He must be destroyed no later than at time $b_i$, or else he will fire his weapon, which will definitely end the fight.

Your weapon is an area-blaster, which can be set to any given power. If fired with power $R$,it momentarily destroys all aliens at distance $R$ or smaller. It also consumes $R$ fuel cells.

Determine the minimal cost (measured in fuel cells) of destroying all the aliens, without being killed.

inputFormat:
The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

Each test case starts with a line containing the number of aliens $n(1 \le n \le 300)$. Of the next $n$ lines, the $i-th$ one contains three integers $a_i, b_i, d_i, (1 \le a_i < b_i \le 10 000, 1 \le d_i \le 10 000)$.

The $i-th$ alien appears at time $a_i$, is idle until $b_i$, and his distance from you is $d_i$.

outputFormat: For each test case, output one line containing the minimum number of cells needed to destroy all the aliens.

translation:
### 题目描述
来自外太空的外星人（最终）入侵了地球。保卫自己，或者解体，被他们同化，或者成为食物。迄今为止，我们无法确定。

外星人遵循已知的攻击模式。有 $N$ 个外星人进攻，第 $i$ 个进攻的外星人会在时间 $a_i$ 出现，距离你的距离为 $d_i$，它必须在时间 $b_i$ 前被消灭，否则被消灭的会是你。

你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率 $R$，它会瞬间摧毁与你的距离在 $R$ 以内的所有外星人（可以等于），同时它也会消耗 $R$ 单位的燃料电池。

求摧毁所有外星人的最低成本（消耗多少燃料电池），同时保证自己的生命安全。

### 输入格式

第一行输入一个数 $T$,表示有 $T$ 组数据。

每组数据的第一行为外星人的数量 $n$（$1\leq n\leq 300$）。

接下来 $n$ 行，每行有三个数 $a_i,b_i,d_i$，表示这个外星人在时间 $a_i$ 出现，距离你 $d_i$，在 $b_i$ 前时刻死亡。

### 输出格式

共 $T$ 行，每行输出摧毁所有外星人的最低成本。


title: [COCI2017-2018#6] Davor

description:
After successfully conquering the South Pole, Davor is preparing for new challenges. Next up is the Arctic expedition to Siberia, Greenland and Norway. He begins his travels on 31 December 2018, and needs to collect N kunas (Croatian currency) by then. In order to do this, he has decided to put away X (X ≤ 100) kunas every Monday to his travel fund, X + K kunas every Tuesday, X + 2* K every Wednesday, and so on until Sunday, when he will put away X + 6* K kunas. This way, he will collect money for 52 weeks, starting with 1 January 2018 (Monday) until 30 December 2018 (Sunday).

If we know the amount of money N, output the values X and K so that it is possible to collect the **exact** money amount in the given timespan. The solution will always exist, and if there are multiple, output the one with the greatest X  and smallest K .

inputFormat: The first line of input contains the integer N (1456 ≤ N ≤ 145600), the number from the task.

outputFormat:
The first line of output must contain the value of X (0 < X ≤ 100 ), and the second the value of
K (K > 0 ).

translation:
在征服南极之后，Davor 开始了一项新的挑战。下一步是在西伯利亚、格林兰、挪威的北极圈远征。他将在 $2018$ 年 $12$ 月 $31$ 日开始出发，在这之前需要一共筹集 $n$ 元钱。他打算在每个星期一筹集 $x$ 元，星期二筹集 $x+k$ 元，……，星期日筹集 $x+6k$ 元，并连续筹集 $52$ 个星期。其中 $x,k$ 为正整数，并且满足 $1 \le x \le 100$。

现在请你帮忙计算 $x,k$ 为多少时，能刚好筹集 $n$ 元。

如果有多个答案，输出 $x$ 尽可能大，$k$ 尽可能小的。注意 $k$ 必须大于 $0$。


title: [COCI2017-2018#6] Alkemija

description:
In ancient times, when alchemists were searching for gold, the world was familiar with a total
of N distinct substances, denoted with 1 to N. During many years of hard work, searching for
the secret formula, alchemists discovered a series of interesting regularities - alchemical
reactions
. In one reaction, it’s possible to transform substance set {
$X_1$,$X_2$, …, $X_L$} to another
substance set {$Y_1$, $Y_2$, …, $Y_R$}. For example, the substance set {1, 4, 5} might react once and
create the new substance set {2, 6}.

Joško is a modern alchemist and has M distinct substances denoted with $A_1$, $A_2$, …, $A_M$. He
has an unlimited quantity of each substance from that set. Joško wants to know which
substances he can create using a list of reactions of ancient alchemists, so he’s asking you
to help him solve this problem.

inputFormat:
The first line of input contains two integers N and M (1 ≤ M ≤ N ≤ 100 000), the numbers from the task.

The second line of input contains M integers $A_i$ (1 ≤ $A_i$ ≤ N), labels of the substances Joško has in the beginning.

The third line of input contains the integer K (1 ≤ K ≤ 100 000), the number of known
reactions.

The following 3·K lines contain a list of reactions. Each reaction is described with 3 lines in the following way:

- The first line contains the integers L and R (1 ≤ L, R ≤ N).
- The second line contains L distinct integers $X_i$ (1 ≤ $X_i$ ≤ N).
- The third line contains R distinct integers $Y_i$ (1 ≤ $Y_i$ ≤ N).
- This describes the reaction with which the substance set {$X_1$, $X_2$, …, $X_L$} transforms into substance set {$Y_1$, $Y_2$, …, $Y_R$}.

The sum of all L values won’t exceed 100 000.

The sum of all R values won’t exceed 100 000.

outputFormat:
The first line of output must contain the integer X, the number of obtainable substances.

The second line of output must contain X distinct integers $B_i$, sorted ascendingly, that represent the labels of the obtainable substances.

translation: 一共存在 $N$ 种元素，现在你只拥有其中的 $M$ 个。现在给你 $K$ 个式子，每个式子都有两排，第一排为他所需要的元素，第二排为他所可以获得的元素。你的元素是无限的，问你最后最多可以获得哪些元素？

hint:
In test cases worth 60% of total points, it will hold:

- N, K ≤ 500.
- The sum of all L values and the sum of all R values won’t exceed 500.

**Clarification of the first test case:**

There are 2 reactions.

The first reaction transforms substance set {1, 2} into substance set {3}.

The second reaction transforms substance set {1, 3} into substance set {4}.

Joško initially has substances from the set {1, 2}.

Using the first reaction, Joško can obtain substance 3, after which he has substances from the set {1, 2, 3}.

After that, using the second reaction, he can also obtain substance 4.

**Clarification of the second test case:**

Joško initially has substances from the set {1, 4, 5}.

Using the second reaction, it is possible to obtain substance 6, after which it is possible to apply the third reaction, giving substance 2.

The first reaction is impossible to apply because Joško doesn’t have substance 3.


title: [COCI2017-2018#6] Mate

description:
Little Mate got an array of lowercase letters from the English alphabet as a present from his
parents. In order to have at least some use of such a clever present, he decided to use it for
finding rhymes when writing his next song.

To find a specific rhyme, Mate wants to select a word of length D that ends with an array of
characters XY, i.e. where the next to last letter is X, and the last Y. Mate’s process of
selecting a word is by first crossing out some letters in a given sequence, and then merging
the letters he didn’t cross out into a single word. He wants to know in how many different
ways he can cross out the letters so that he meets the given conditions.

The selection of two words is considered distinct if the sets of positions of the crossed-out
letters are different.

inputFormat:
The first line of input contains an array of lowercase letters of the English alphabet S (2 ≤ |S|
≤ 2000).

The second line of input contains the integer Q (1 ≤ Q ≤ 500 000), the number of different
rhymes for which Mate needs to select words.

Each of the following Q lines contains the integer D (2 ≤ D ≤ |S|) and an array of lowercase
letters of the English alphabet XY from the task.

outputFormat: The $i^{th}$ out of Q lines must contain the required number of ways for the $i^{th}$ rhyme. Since that number can be quite large, output only the value **modulo 1 000 000 007**.

translation: 给定一个字符串 $S$，一共有 $Q$ 个询问，每一个询问给定一个数字 $N$ 和 两个字符 $A$ 和 $B$，问你在 $S$ 中有多少长度为 $N$ 的子串为 $A, B$ 结尾，其中 $A$ 为倒数第二个字符，$B$ 为最后一个字符。注意，选取的字母可以不连续。

hint:
In test cases worth 40% of total points, it will hold |S| ≤ 50.

In test cases worth an additional 40% of total points, it will hold |S| ≤ 200.

**Clarification of the first test case:**

Word of length 2 that ends with “na” can be obtained in the following ways:

~~b a n a~~$\ $**n a**, ~~b a~~$\ $**n a**$\ $~~n a~~, ~~b a~~$\ $**n** ~~a n~~$\ $**a**


title: [COCI2017-2018#6] Cover

description:
You are given N points in the coordinate system. They need to be covered with one or more
rectangles, such that the following conditions are met:

- The sides of each rectangle are parallel with the coordinate axes,
- The center of each rectangle is in the origin, i.e. point (0, 0),
- Each given point is located either inside of the rectangle or on its boundaries.

Of course, it is possible to cover all the points using only one rectangle, but this rectangle
could have a very large surface area. Our goal is to find a selection of required rectangles
such that the sum of their surface areas is minimal.

inputFormat:
The first line of input contains the integer N (1 ≤ N ≤ 5000), the number of points.

Each of the following N lines contains two integers X and Y (-50 000 000 ≤ X, Y ≤ 50 000
000, XY ≠ 0), the coordinates of each point.

outputFormat: You must output the required minimal sum of surface areas of the rectangles.

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

**Clarification of the first test case:** We choose the rectangle whose opposite angles are the given
points, since it meets the conditions from the task.

**Clarification of the second test case:** We choose two rectangles with their centers in the origin. The
first is of dimensions 50 x 20 and covers point (25, 10). The second is of dimensions 18 x 60 and covers the first two points. If we wanted to cover all the points using one rectangle, it would be of
dimensions 50 x 60.


title: [COCI2006-2007#6] MAGIJA

background: 知名魔术师 Al'Dimi Kartimi 需要你帮助他来设计他扑克牌的背面图案。

description:
众所周知，扑克牌的背面是一个矩形，通过做两边的中垂线可以将矩形分成相等的四部分。

Al'Dimi Kartimi 首先绘制了左上角部分的图案，图案共有 $r$ 行 $m$ 列，由字符 `#` 和字符 `.` 组成。绘制完后，他将该图案沿矩形垂直方向的中垂线镜面对称地绘制了矩形右上角的部分。然后他沿矩形水平方向的中垂线镜面对称地绘制了矩形的下半部分。

在绘制后，Al'Dimi Kartimi 会故意犯一个小错误，以此来帮助他识别这是哪张扑克牌的背面。具体的，他会选择第 $x$ 行第 $y$ 列的字符，若该字符是 `#`，则将其改成 `.`，否则将其改成 `#`。

下面是三个背面图案的例子（错误的字符以灰色高亮）。

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

给定左上角的图案以及 $x, y$，请输出整张扑克牌背面的图案。

inputFormat:
第一行有两个整数，分别表示左上角图案的行数 $r$ 和列数 $c$。

第 $2$ 到第 $(r + 1)$ 行，每行一个长度为 $c$ 的字符串，第 $(i + 1)$ 行的第 $j$ 个字符 $s_{i, j}$ 表示图案第 $i$ 行第 $j$ 列的字符。

第 $(r + 2)$ 行有两个整数，分别表示小错误所在的行数 $x$ 和列数 $y$。

outputFormat: 输出 $2r$ 行，每行一个长度为 $2c$ 的字符串，表示整个背面的图案。

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

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

- $1 \leq r, c \leq 50$。
- $1 \leq x \leq 2r$，$1 \leq y \leq 2c$。
- $s_{i, j} \in \{\texttt \#, \texttt . \}$

#### 说明

**题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #6](https://hsin.hr/coci/archive/2006_2007/contest6_tasks.pdf) *T2   MAGIJA***。


title: Chino的树学

background: Chino非常喜欢树

description:
Chino树是一棵具有某种性质的满二叉树，具体来说，对于这棵树的每一个非叶子节点，它的左子节点$(A)$的右子节点$(C)$与它的右子节点$(B)$的左子节点$(D)$的值相同，且$C$与$D$下方的子树也完全相同。现在，Chino想知道，要如何从根节点走到其中任意叶节点使路上经过的节点的权值之和最大。

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

$Orz yky,dyh,wjk,jjy,cxr,gsy,cpy,zcy,tyz,yy,hz,zhr,ygg$

inputFormat:
第一行，一个数，$n$，代表该二叉树的层数。

第二行，$2^n-1$个数，代表该二叉树的先序遍历。

outputFormat: 一行，一个数，代表点权最大和。

hint:
![](https://cdn.luogu.com.cn/upload/pic/23674.png )
![](https://cdn.luogu.com.cn/upload/pic/23675.png )
![](https://cdn.luogu.com.cn/upload/pic/23673.png )
答案longlong救星


title: [IOI2000] 邮局 加强版

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

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

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

inputFormat:
第一行包含两个整数：第一个是村庄 $V$ 的数量，第二个是邮局的数量 $P$。

第二行包含 $V$ 个整数。这些整数是村庄的位置。

outputFormat: 第一行包含一个整数 $S$，它是每个村庄与其最近的邮局之间的所有距离的总和。


title: [NOI2018] 归程

description:
本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。

魔力之都可以抽象成一个 $n$ 个节点、$m$ 条边的无向连通图（节点的编号从 $1$ 至 $n$）。我们依次用 $l,a$ 描述一条边的**长度、海拔**。

作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此**有积水的边一定是海拔相对最低的一些边**。我们用**水位线**来描述降雨的程度，它的意义是：所有海拔**不超过**水位线的边都是**有积水**的。

Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。Yazid 的家恰好在魔力之都的 $1$ 号节点。对于接下来 $Q$ 天，每一天 Yazid 都会告诉你他的出发点 $v$ ，以及当天的水位线 $p$。

每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。
需要特殊说明的是，第二天车会被重置，这意味着：
- 车会在新的出发点被准备好。
- Yazid 不能利用之前在某处停放的车。

Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他**步行经过的边**的总长度。请你帮助 Yazid 进行计算。

本题的部分测试点将强制在线，具体细节请见【输入格式】和【子任务】。

inputFormat:
单个测试点中包含多组数据。输入的第一行为一个非负整数 $T$，表示数据的组数。

接下来依次描述每组数据，对于每组数据：

第一行 $2$ 个非负整数 $n,m$，分别表示节点数、边数。

接下来 $m$ 行，每行 $4$ 个正整数 $u, v, l, a$，描述一条连接节点 $u, v$ 的、长度为 $l$、海拔为 $a$ 的边。
在这里，我们保证 $1 \leq u,v \leq n$。

接下来一行 $3$ 个非负数 $Q, K, S$ ，其中 $Q$ 表示总天数，$K \in {0,1}$ 是一个会在下面被用到的系数，$S$ 表示的是可能的最高水位线。

接下来 $Q$ 行依次描述每天的状况。每行 $2$ 个整数 $v_0,  p_0$ 描述一天：
- 这一天的出发节点为 $v = (v_0 + K \times \mathrm{lastans} - 1) \bmod n + 1$。
- 这一天的水位线为 $p = (p_0 + K \times \mathrm{lastans}) \bmod (S + 1)$。

其中 $\mathrm{lastans}$ 表示上一天的答案（最小步行总路程）。特别地，我们规定第 $1$ 天时 $\mathrm{lastans} = 0$。
在这里，我们保证 $1 \leq v_0 \leq n$，$0 \leq p_0 \leq S$。

对于输入中的每一行，如果该行包含多个数，则用单个空格将它们隔开。

outputFormat:
依次输出各组数据的答案。对于每组数据：

- 输出 $Q$ 行每行一个整数，依次表示每天的最小步行总路程。

hint:
### 更多样例

更多样例请在附加文件中下载。

#### 样例 3

见附加文件中的 `return3.in` 与 `return3.ans`。

该样例满足海拔为一种，且不强制在线。

#### 样例 4

见附加文件中的 `return4.in` 与 `return4.ans`。

该样例满足图形态为一条链，且强制在线。

#### 样例 5

见附加文件中的 `return5.in` 与 `return5.ans`。

该样例满足不强制在线。

### 样例 1 解释

第一天没有降水，Yazid 可以坐车直接回到家中。

第二天、第三天、第四天的积水情况相同，均为连接 1，2 号节点的边、连接 3，4 号点的边有积水。

对于第二天，Yazid 从 2 号点出发坐车只能去往 3 号节点，对回家没有帮助。因此 Yazid 只能纯靠徒步回家。

对于第三天，从 4 号节点出发的唯一一条边是有积水的，车也就变得无用了。Yazid 只能纯靠徒步回家。

对于第四天，Yazid 可以坐车先到达 2 号节点，再步行回家。

第五天所有的边都积水了，因此 Yazid 只能纯靠徒步回家。

### 样例 2 解释

本组数据强制在线。

第一天的答案是 $0$，因此第二天的 $v=\left( 5+0-1\right)\bmod 5+1=5$，$p=\left(2+0\right)\bmod\left(3+1\right)=2$。

第二天的答案是 $2$，因此第三天的 $v=\left( 2+2-1\right)\bmod 5+1=4$，$p=\left(0+2\right)\bmod\left(3+1\right)=2$。

第三天的答案是 $3$，因此第四天的 $v=\left( 4+3-1\right)\bmod 5+1=2$，$p=\left(0+3\right)\bmod\left(3+1\right)=3$。

### 数据范围与约定

所有测试点均保证 $T\leq 3$，所有测试点中的所有数据均满足如下限制：

- $n\leq 2\times 10^5$，$m\leq 4\times 10^5$，$Q\leq 4\times 10^5$，$K\in\left\{0,1\right\}$，$1\leq S\leq 10^9$。
- 对于所有边：$l\leq 10^4$，$a\leq 10^9$。
- 任意两点之间都直接或间接通过边相连。

**为了方便你快速理解，我们在表格中使用了一些简单易懂的表述。在此，我们对这些内容作形式化的说明：**

- 图形态：对于表格中该项为 “一棵树” 或 “一条链” 的测试点，保证 $m = n-1$。除此之外，这两类测试点分别满足如下限制：
  - 一棵树：保证输入的图是一棵树，即保证边不会构成回路。
  - 一条链：保证所有边满足 $u + 1 = v$。
- 海拔：对于表格中该项为 “一种” 的测试点，保证对于所有边有 $a = 1$。
- 强制在线：对于表格中该项为 “是” 的测试点，保证 $K = 1$；如果该项为 “否”，则有 $K = 0$。
- 对于所有测试点，如果上述对应项为 “不保证”，则对该项内容不作任何保证。

$n$|$m$|$Q=$|测试点|形态|海拔|强制在线
-|-|-|-|-|-|-
$\leq 1$|$\leq 0$|$0$|1|不保证|一种|否
$\leq 6$|$\leq 10$|$10$|2|不保证|一种|否
$\leq 50$|$\leq 150$|$100$|3|不保证|一种|否
$\leq 100$|$\leq 300$|$200$|4|不保证|一种|否
$\leq 1500$|$\leq 4000$|$2000$|5|不保证|一种|否
$\leq 200000$|$\leq 400000$|$100000$|6|不保证|一种|否
$\leq 1500$|$=n-1$|$2000$|7|一条链|不保证|否
$\leq 1500$|$=n-1$|$2000$|8|一条链|不保证|否
$\leq 1500$|$=n-1$|$2000$|9|一条链|不保证|否
$\leq 200000$|$=n-1$|$100000$|10|一棵树|不保证|否
$\leq 200000$|$=n-1$|$100000$|11|一棵树|不保证|是
$\leq 200000$|$\leq 400000$|$100000$|12|不保证|不保证|否
$\leq 200000$|$\leq 400000$|$100000$|13|不保证|不保证|否
$\leq 200000$|$\leq 400000$|$100000$|14|不保证|不保证|否
$\leq 1500$|$\leq 4000$|$2000$|15|不保证|不保证|是
$\leq 1500$|$\leq 4000$|$2000$|16|不保证|不保证|是
$\leq 200000$|$\leq 400000$|$100000$|17|不保证|不保证|是
$\leq 200000$|$\leq 400000$|$100000$|18|不保证|不保证|是
$\leq 200000$|$\leq 400000$|$400000$|19|不保证|不保证|是
$\leq 200000$|$\leq 400000$|$400000$|20|不保证|不保证|是


title: [NOI2018] 冒泡排序

background: 请注意，题目中存在 $n=0$ 的数据。

description:
最近，小 S 对冒泡排序产生了浓厚的兴趣。为了问题简单，小 S 只研究对 **$1$ 到 $n$ 的排列**的冒泡排序。

下面是对冒泡排序的算法描述。

```plain
输入：一个长度为 n 的排列 p[1...n]
输出：p 排序后的结果。
for i = 1 to n do
	for j = 1 to n - 1 do
		if(p[j] > p[j + 1])
			交换 p[j] 与 p[j + 1] 的值
```

冒泡排序的交换次数被定义为交换过程的执行次数。可以证明交换次数的一个下界是 $\frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert$，其中 $p_i$ 是排列 $p$ 中第 $i$ 个位置的数字。如果你对证明感兴趣，可以看提示。

小 S 开始专注于研究长度为 $n$ 的排列中，满足交换次数 $= \frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert$ 的排列（在后文中，为了方便，我们把所有这样的排列叫「好」的排列）。他进一步想，这样的排列到底多不多？它们分布的密不密集？

小 S 想要对于一个给定的长度为 $n$ 的排列 $q$，计算字典序严格大于 $q$ 的“好”的排列个数。但是他不会做，于是求助于你，希望你帮他解决这个问题，考虑到答案可能会很大，因此只需输出答案对 $998244353$ 取模的结果。

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

对于每组数据，第一行有一个正整数 $n$，保证 $n \leq 6 \times 10^5$。

接下来一行会输入 $n$ 个正整数，对应于题目描述中的 $q_i$，保证输入的是一个 $1$ 到 $n$ 的排列。

outputFormat:
输出共 $T$ 行，每行一个整数。

对于每组数据，输出一个整数，表示字典序严格大于 $q$ 的「好」的排列个数对 $998244353$ 取模的结果。

hint:
### 更多样例

更多样例请在附加文件中下载。

#### 样例 3

见附加文件中的 `inverse3.in` 与 `inverse3.ans`。

### 样例 1 解释

字典序比 $1 \ 3 \ 2$ 大的排列中，除了 $3 \ 2 \ 1$ 以外都是「好」的排列，故答案为 $3$。

### 数据范围

下面是对本题每个测试点的输入规模的说明。

对于所有数据，均满足 $T = 5$（样例可能不满足）。

记 $n_\mathrm{max}$ 表示每组数据中 $n$ 的最大值，$\sum n$ 表示所有数据的 $n$ 的和。

| 测试点 | $n_\mathrm{max} =$ | $\sum n \leq$ | 特殊性质 |
|:-:|:-:|:-:|:-:|
| 1 | $8$ | $5 \ n_\mathrm{max}$ | 无 |
| 2 | $9$ | $5 \ n_\mathrm{max}$ | 无 |
| 3 | $10$ | $5 \ n_\mathrm{max}$ | 无 |
| 4 | $12$ | $5 \ n_\mathrm{max}$ | 无 |
| 5 | $13$ | $5 \ n_\mathrm{max}$ | 无 |
| 6 | $14$ | $5 \ n_\mathrm{max}$ | 无 |
| 7 | $16$ | $5 \ n_\mathrm{max}$ | 无 |
| 8 | $16$ | $5 \ n_\mathrm{max}$ | 无 |
| 9 | $17$ | $5 \ n_\mathrm{max}$ | 无 |
| 10 | $18$ | $5 \ n_\mathrm{max}$ | 无 |
| 11 | $18$ | $5 \ n_\mathrm{max}$ | 无 |
| 12 | $122$ | $700$ | $\forall i \enspace q_i = i$ |
| 13 | $144$ | $700$ | 无 |
| 14 | $166$ | $700$ | 无 |
| 15 | $200$ | $700$ | 无 |
| 16 | $233$ | $700$ | 无 |
| 17 | $777$ | $4000$ | $\forall i \enspace q_i = i$ |
| 18 | $888$ | $4000$ | 无 |
| 19 | $933$ | $4000$ | 无 |
| 20 | $1000$ | $4000$ | 无 |
| 21 | $266666$ | $2000000$ | $\forall i \enspace q_i = i$ |
| 22 | $333333$ | $2000000$ | 无 |
| 23 | $444444$ | $2000000$ | 无 |
| 24 | $555555$ | $2000000$ | 无 |
| 25 | $600000$ | $2000000$ | 无 |

### 提示

下面是对交换次数下界是 $\frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert$ 的证明。

排序本质上就是数字的移动，因此排序的交换次数应当可以用数字移动的总距离来描述。对于第 $i$ 个位置，假设在初始排列中，这个位置上的数字是 pi，那么我们需要将这个数字移动到第 $p_i$ 个位置上，移动的距离是 $\lvert i - p_i \rvert$。从而移动的总距离就是 $\sum_{i=1}^n \lvert i - p_i \rvert$，而冒泡排序每次会交换两个相邻的数字，每次交换可以使移动的总距离至多减少 $2$。因此 $\frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert$ 是冒泡排序的交换次数的下界。

并不是所有的排列都达到了下界，比如在 $n = 3$ 的时候，考虑排列 $3 \ 2 \ 1$，这个排列进行冒泡排序以后的交换次数是 $3$，但是 $\frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert$ 只有 $2$。


title: [NOI2018] 你的名字

background: 实力强大的小 A 被选为了 ION2018 的出题人，现在他需要解决题目的命名问题。

description:
小 A 被选为了 ION2018 的出题人，他精心准备了一道质量十分高的题目，且已经把除了题目命名以外的工作都做好了。

由于 ION 已经举办了很多届，所以在题目命名上也是有规定的，ION 命题手册规定：每年由命题委员会规定一个小写字母字符串，我们称之为那一年的命名串，要求每道题的名字必须是那一年的命名串的一个非空连续子串，且不能和前一年的任何一道题目的名字相同。

由于一些特殊的原因，小 A 不知道 ION2017 每道题的名字，但是他通过一些特殊手段得到了 ION2017 的命名串，现在小 A 有 $Q$ 次询问：每次给定 ION2017 的命名串和 ION2018 的命名串，求有几种题目的命名，使得这个名字一定满足命题委员会的规定，即是 ION2018 的命名串的一个非空连续子串且一定不会和 ION2017 的任何一道题目的名字相同。

由于一些特殊原因，所有询问给出的 ION2017 的命名串都是某个串的连续子串，详细可见输入格式。

inputFormat:
第一行一个字符串 $S$ ，之后询问给出的 ION2017 的命名串都是 $S$ 的连续子串。
第二行一个正整数 $Q$，表示询问次数。
接下来 $Q$ 行，每行有一个字符串 $T$ 和两个正整数$l,r$，表示询问如果 ION2017 的命名串是 $S_{l\ldots r}$，ION2018 的命名串是 $T$ 的话，有几种命名方式一定满足规定。

outputFormat: 输出 $Q$ 行，第 $i$ 行一个非负整数表示第 $i$ 个询问的答案。

samples:
scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9


title: [NOI2018] 屠龙勇士

description:
小 D 最近在网上发现了一款小游戏。游戏的规则如下：

- 游戏的目标是按照编号 $1 \rightarrow n$ 顺序杀掉 $n$ 条巨龙，每条巨龙拥有一个初始的生命值 $a_i$ 。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 $p_i$ ，直至生命值非负。只有在攻击结束后且当生命值 **恰好** 为 $0$ 时它才会死去。
- 游戏开始时玩家拥有 $m$ 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。

小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格，于是小 D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：

- 每次面对巨龙时，机器人会选择当前拥有的，攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑，则选择 **攻击力最低** 的一把剑作为武器。
- 机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 $x$ 次，使巨龙的生命值减少 $x \times ATK$ 。
- 之后，巨龙会不断使用恢复能力，每次恢复 $p_i$ 生命值。若在使用恢复能力前或某一次恢复后其生命值为 $0$ ，则巨龙死亡，玩家通过本关。

那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数 $x$ 设置为多少，才能用最少的攻击次数通关游戏吗？

当然如果无论设置成多少都无法通关游戏，输出 $-1$ 即可。

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

接下来 $T$ 组数据，每组数据包含 $5$ 行。

- 每组数据的第一行包含两个整数，$n$ 和 $m$ ，代表巨龙的数量和初始剑的数量；
- 接下来一行包含 $n$ 个正整数，第 $i$ 个数表示第 $i$ 条巨龙的初始生命值 $a_i$；
- 接下来一行包含 $n$ 个正整数，第 $i$ 个数表示第 $i$ 条巨龙的恢复能力 $p_i$；
- 接下来一行包含 $n$ 个正整数，第 $i$ 个数表示杀死第 $i$ 条巨龙后奖励的剑的攻击力；
- 接下来一行包含 $m$ 个正整数，表示初始拥有的 $m$ 把剑的攻击力。

outputFormat:
一共 $T$ 行。

第 $i$ 行一个整数，表示对于第 $i$ 组数据，能够使得机器人通关游戏的最小攻击次数 $x$ ，如果答案不存在，输出 $-1$。


title: [NOI2018] 情报中心

description:
C 国和 D 国近年来战火纷飞。

最近，C 国成功地渗透进入了 D 国的一个城市。这个城市可以抽象成一张有 $n$ 个节点，节点之间由 $n − 1$ 条双向的边连接的无向图，使得任意两个点之间可以互相到达。也就是说，这张无向图实际上是一棵树。

经过侦查，C 国情报部部长 GGB 惊讶地发现，这座看起来不起眼的城市竟然是 D 国的军事中心。因此 GGB 决定在这个城市内设立情报机构。情报专家 TAC 在侦查后，安排了 $m$ 种设立情报机构的方案。这些方案中，第 $i$ 种方案是在节点 $x_i$ 到节点 $y_i$ 的最短路径的所有边上安排情报人员收集情报，这种方案需要花费 $v_i$ 元的代价。

但是，由于人手不足，GGB 只能安排上述 $m$ 种方案中的两种进行实施。同时 TAC 指出，为了让这两个情报机构可以更好的合作，它们收集情报的范围应**至少有一条公共的边**。为了评估一种方案的性能，GGB 和 TAC 对所有的边进行了勘察，给每一条边制定了一个情报价值 $c_i$，表示收集这条边上的情报能够带来 $c_i$ 元的收益。注意，情报是唯一的，因此当一条边的情报被两个情报机构收集时，也同样只会有 $c_i$ 的收益。

现在，请你帮 GGB 选出两种合法的设立情报机构的方案进行实施，使得这两种方案收集情报的范围至少有一条公共的边，并且在此基础上**总收益减去总代价的差**最大。

注意，这个值可能是负的，但仍然是合法的。如果无法找到这样的两种方案，请输出 `F`。

inputFormat:
从文件 `center.in` 中读入数据。

本题包含多组测试数据。

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

每组数据包含 $(n + m + 1)$ 行：

第 $1$ 行包含一个整数 $n$，表示城市的点数；

第 $2$ 到第 $n$ 行中，第 $(i + 1)$ 行包含三个整数 $a_i$，$b_i$，$c_i$，表示城市中一条连接节点 $a_i$ 和 $b_i$、情报价值为 $c_i$ 的双向边，保证 $a_i < b_i$ 且 $b_i$ 互不相同；

第 $(n + 1)$ 行包含一个整数 $m$，表示 TAC 设立的 $m$ 种设立情报机构的方案；

第 $(n + 2)$ 到 $(n + m + 1)$ 行中，第 $(n + i + 1)$ 行包含三个整数 $x_i$，$y_i$，$v_i$，表示第 $i$ 种设立情报机构的方案是在节点 $x_i$ 到节点 $y_i$ 的最短路径上的所有边上安排情报人员收集情报，并且需要花费 $v_i$ 元的代价。

outputFormat:
输出到文件 `center.out` 中。

输出文件包含 $T$ 行；

对于每组数据，输出一行：如果存在合法的方案，则输出一个整数表示最大的总收益减去总代价的差；否则输出 `F`。

hint:
### 样例 1 解释

这个样例中包含两组数据。这两组数据的城市相同，只是在情报的价值和情报机构的方案上有所不同。城市地图如下：

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

* 对于第一组数据，方案一中的节点 $1$ 到节点 $4$ 的最短路径为 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4$，方案二中的节点 $3$ 到节点 $5$ 的最短路径为 $3 \rightarrow 2 \rightarrow 1 \rightarrow 5$。选择这两种方案需要花费 $5 + 8 = 13$ 的代价，并且每一条边的情报都被收集从而得到 $1 + 3 + 2 + 8 = 14$ 的收益，因此总收益减去总代价为 $14 − 13 = 1$。
* 对于第二组数据，方案一中的节点 $1$ 到节点 $5$ 的最短路径为 $1 \rightarrow 5$，方案二中的节点 $2$ 到节点 $3$ 的最短路径为 $2 \rightarrow 3$。这两种方案收集情报的范围没有公共的边，因此非法，所以这组数据不存在合法方案，应输出 `F`。

### 样例 2 解释

见附加文件中的 `center2.in` 与 `center2.ans`。

这个样例只包含一组数据。这一数据中，最优方案为选择第 $2$ 种和第 $3$ 种方案。

这组数据的城市地图如下，其中**加粗**的边表示被情报中心收集情报的边，红色的边表示只被第 $2$ 种方案的情报中心收集情报的边，蓝色的边表示只被第 $3$ 种方案的情报中心收集情报的边，紫色的边表示同时被两个情报中心收集情报的边。

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

### 样例 3

见附加文件中的 `center3.in` 与 `center3.ans`。

这个样例和第 $4$ 个测试点的性质相同。每个测试点的性质见下文的表格。

### 样例 4

**由于附加文件大小限制，附加文件不再提供该组样例**。

见附加文件中的 `center4.in` 与 `center4.ans`。

这个样例，无疑是善良的出题人无私的馈赠。大量精心构造的 $n\le 100,m\le 200$ 的测试数据，涵盖了测试点中所有出现性质的组合。你可以利用这个测试点，对自己的程序进行全面的检查。足量的数据组数、不大的数据范围和多种多样的数据类型，能让程序中的错误无处遁形。出题人相信，这个美妙的样例，可以给拼搏于 AC 这道题的逐梦之路上的你，提供一个有力的援助。

### 数据范围

各测试点的数据规模和性质如下表：

| 测试点 | $n \le$ | $m \le$ | $T \le 50$ | 特殊性质 |
| :-: | :-: | :-: | :-: | :-: |
| 1 | $2$ | $3$ | 保证 | 无 |
| 2 | $10$ | $30$ | 保证 | 无 |
| 3 | $200$ | $300$ | 保证 | 无 |
| 4 | $10^3$ | $2,000$ | 保证 | $a_i = b_i - 1$ |
| 5 | $10^4$ | $3 \times 10^4$ | 保证 | $a_i = b_i - 1$ |
| 6 | $5 \times 10^4$ | $3 \times 10^4$ | 保证 | $a_i = b_i - 1$ |
| 7 | $10^4$ | $3 \times 10^4$ | 保证 | $c_i=0$ |
| 8 | $5 \times 10^4$ | $10^5$ | 保证 | $c_i=0$ |
| 9 | $5 \times 10^4$ | $10^5$ | 保证 | $c_i=0$ |
| 10 | $10^4$ | $n$ | 保证 | $S_1$ |
| 11 | $5 \times 10^4$ | $n$ | 不保证 | $S_1$ |
| 12 | $5 \times 10^4$ | $n$ | 不保证 | $S_1$ |
| 13 | $10^4$ | $3 \times 10^4$ | 保证 | $S_2$ |
| 14 | $10^4$ | $3 \times 10^4$ | 保证 | $S_2$ |
| 15 | $5 \times 10^4$ | $10^5$ | 不保证 | $S_2$ |
| 16 | $5 \times 10^4$ | $10^5$ | 不保证 | $S_2$ |
| 17 | $10^4$ | $3 \times 10^4$ | 保证 | 无 |
| 18 | $5 \times 10^4$ | $ 10^5$ | 保证 | 无 |
| 19 | $5 \times 10^4$ | $ 10^5$ | 不保证 | 无 |
| 20 | $5 \times 10^4$ | $ 10^5$ | 不保证 | 无 |

表格中的特殊性质如下：
* 特殊性质 $S_1$：对于任意 $i, j$，保证 $x_i$ 到 $y_i$ 的最短路径所经过的编号最小的节点不同于 $x_j$ 到 $y_j$ 的最短路径所经过的编号最小的节点；

* 特殊性质 $S_2$：对于任意 $i$，保证 $x_i$ 到 $y_i$ 的最短路径所经过的编号最小的节点为节点 $1$。

对于所有的数据，$1 \le n \le 5 \times 10^4$，$0 \le m \le 10^5$，$0 \le c_i \le 10^9$，$0 \le v_i \le 10^{10} \times n$。每个测试点中，所有 $n$ 的和不会超过 $1\,000\,233$，所有 $m$ 的和不会超过 $2\,000\,233$。


title: [NOI2018] 多边形

description:
久莲是一个喜欢出题的女孩子。

在今年的 World Final 结束以后，久莲特别喜欢计算几何，于是她打算在 NOI 的考场上也出一个计算几何：这是一道只有题目名字和计算几何相关的题目。

首先，久莲给出了一棵 $n\ (n \ge 2)$ 个节点的有根树 $T$，根节点编号为 $1$。定义叶子节点为除了根以外所有度数恰好为 $1$ 的节点。下图是一个树 $T$ 的例子，其中叶子节点集合为 $\{3, 4, 5\}$。

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

接着通过这棵树，久莲构造了一个序列 $A$：
- 从根节点开始深度优先遍历整棵树，遍历时按照编号从小到大的顺序来访问孩子，这样可以得到一个树 $T$ 的 DFS 序。
- 接着按照在 DFS 序中的出现顺序从前往后，久莲把所有叶子节点排成一排得到了一个序列 $A$。

更进一步地，通过序列 $A$，久莲定义了两个叶子节点 $u, v$ 的距离 $d(u, v)$：假设 $u$ 在 $A$ 中是第 $i$ 个元素，$v$ 是第 $j$ 个元素，则 $d(u, v) = \min(|i − j|, |A| − |i − j|)$。其中 $|A|$ 为序列的长度，即 $T$ 的叶子个数，$i, j$ 指的是出现的位置，从 $1$ 开始计数。

上面的例子中，序列 $A$ 为 $\{4, 5, 3\}$，其中 $d(3, 5) = d(3, 4) = d(4, 5) = 1$，$3, 4, 5$ 的出现位置分别为 $3, 1, 2$。

最后，久莲给出了一个参数 $K$，利用这棵有根树 $T$ 和序列 $A$，我们可以构造一张 $n$ 个点的**无重边无自环**的无向图 $G$：两个不同的点 $u, v$ 之间有边当且仅当它们满足下列条件中的至少一个：
- 在树 $T$ 中存在连接 $u, v$ 的边。
- 在树 $T$ 中 $u, v$ 都是叶子节点且 $d(u, v) \le K$。

当 $K = 1$ 或 $2$ 时，上面的例子得到的图 $G$ 都如下图所示：

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

现在久莲想让你来计算一下 $G$ 中不同的哈密尔顿回路数量有多少条，答案可能很大，请对 $998244353$ 取模后输出。

下面是一些补充定义：
- 无重边无自环的无向图 $G$ 的一条哈密尔顿回路 $H$ 是 $G$ 中边的一个子集，其中每一个点恰好有两条不同的相邻边在 $H$ 中，且任意两个点都可以通过 $H$ 中的边直接或间接到达。
- 无重边无自环的无向图 $G$ 的两条哈密尔顿回路 $H_1, H_2$ 是不同的当且仅当存在一条边 $e$ 使得 $e$ 在 $H_1$ 中且不在 $H_2$ 中。

inputFormat:
从文件 `polygon.in` 中读入数据。

第一行输入两个整数 $n, K$，表示树 $T$ 的点数以及久莲选定的参数 $K$。

第二行输入 $n - 1$ 个整数 $f_i\ (1 \le f_i \le i)$，其中 $f_i$ 表示树 $T$ 上存在边 $( f_i, i + 1)$。

outputFormat:
输出到文件 `polygon.out` 中。

输出一行一个整数，表示哈密尔顿回路数量对 $998244353$ 取模后的结果。


title: P 哥的桶

description:
P 哥现在有 $n$ 个桶，它们排成了一排，这些桶可以装下任意多个球。每个球有一个固定的价值。

P 哥时不时地会找新球，并把新找的球丢进某个桶里面。我们用 $1\;k\;x$ 来表示 P 哥找了一个价值为 $x$ 的球，并且丢进了 $k$ 号桶里面。

P 哥每次会在特定的桶里面拿出一些球。我们用 $2\;l\;r$ 来表示 P 哥在 $l$ 号桶到 $r$ 号桶之间拿球。P 哥希望拿出来的球的价值异或和尽可能大。

**注意：P 哥拿出这些球后会把它们物归原位。**

inputFormat:
第一行两个整数 $n, m$，依次表示 P 哥的操作次数、这组数据会涉及到的最大编号。

接下来 $n$ 行，每行三个整数，表示操作。操作格式如题。

outputFormat: 对于每个 2 操作，输出 P 哥拿出的球的最大价值异或和。

hint:
对于 $20 \%$ 的数据，满足 $n,m\leq 100$。

对于 $40 \%$ 的数据，满足 $n,m\leq 1000$。

另有 $20 \%$ 的数据，所有询问满足 $l=1$，$r=m$。

对于 $100 \%$ 的数据，满足 $1 \le n, m \leq 5 \times 10^4$，$1 \le l\leq r\leq m$，$1 \le k \leq m$，$0 \le x \leq 2^{31}-1$。


title: OIer们的烦恼

background:
OIer 们有一个烦恼，他们本来可以随心所欲玩游戏上网的，自从学校机房开启 URL 过滤后，OIer 们就开始在 luogu上 面找游戏玩。

但是他们刚玩 slay.one 几天之后 slay.one 就被封禁了，只有工作日的中午 2 小时可以嗨皮，并且会有帅气的老师来巡视机房，他们该怎么办呢？

description:
有 3 个帅气的老师 $A$，$B$ 和 $C$。

有 5 个学生 $a$，$b$，$c$，$d$，$e$。当他们当中的某一个人开始玩游戏时，会显示一条消息 `XX started playing games!`。当他们当中的某一个人停止玩游戏时，会显示一条消息 `XX stopped playing games!`。

当某个老师来巡视机房时，会显示一条消息：`XX came!`。如果某个老师走了，会显示一条消息：`XX left!`。

如果老师发现某个学生**正在**玩游戏时，请输出该学生的姓名。

inputFormat:
有 $N$ 条消息。

第一行输入 $N$，第 $2$ 行输入 $3$ 个老师的名字，第 $3$ 行输入 $5$ 个学生的名字，接下来 $n$ 行输入 $N$ 条消息。

outputFormat:
输出全部在老师巡视时被发现玩游戏学生的名字，按字典序输出。

如果全部学生都被发现玩游戏，额外输出 `How Bad Oiers Are!`。

如果没有人被发现或者没有人玩游戏，输出 `How Good Oiers Are!`。

samples:
10
A B C
a b c d e
A came!
a started playing games!
b started playing games!
A left!
c started playing games!
d started playing games!
e started playing games!
B came!
PS:zhe_ge_yang_li_hen_zheng_chang!
B left!

samples:
10
I_Love_You I_Hate_You Why_Not_love_Me
Gay Che_Wan_Dang QwQ WuMaRu PDD
I_Love_You came!
Gay:Why do you love me?
I_Love_You died!
I_Love_You left!
Che_Wan_Dang prepared to play Dong_Fang!
But nobody came!
QwQ:I am so QwQ,I love myself!
PDD started playing Gay!
Gay died!And WuMaRu cried!
WuMaRu:dai su ki!

samples:
20
Sans QwQ QAQ
A B C D E
A started playing B!
B started fighting with A!
A won!
A get 10000000 Exp!
QwQ:I and QAQ are looking at you all!
C died!
D died!
E recovered 123456789 HP!
E started playing games!
Sans came!
Sans:It is really a nice day today!
Sans:The birds are singing!
Sans:The flowers in bloom!
Sans:In a beautiful day like this!
Sans:People like you!
Sans:Should burn in hell!
E tried to attack Sans!
Sans was killed!
Sans:Papyrus,do you want something?
E still played his Undertale!

samples:
20
a b c
A B C D E
A came!
a started playing games!
b came!
b came together!
b came! dan_shi_zhe_ju_hua_bu_dui!
A came came came!
b start playing games!
b left!
c came!
c left!
A left!
B started playing games!
A started playing game!
C started palying games!
E started playing games!
lu_ren_jia came!
lu_ren_jia:What are you doing?
C&D:We are studying!
lu_ren_jia:Good boy!
C:qwq

hint:
对于 $20\%$ 的数据，$1\leq N\leq 23.3333333333333$
对于 $30\%$ 的数据，$1\leq N\leq 999.999$，有一个点答案为 `How Good Oiers Are!`。
对于 $60\%$ 的数据，$1\leq N\leq 100,000$。
对于$99.9999999999999999999\%$的数据，不保证全部消息都符合题意。
对于 $100\%$ 的数据，$1\leq N\leq 233,333$，数据有梯度。

### Tips:
1.消息中肯定有奇奇怪怪的东西
2.消息必须**完全符合题意**才有效
3.样例很恶心，数据很纯真
4.数据满足不会同时有多个**老师**巡视。
5.注意仔细阅读**题目**和**样例**，**该题有坑！**


title: P哥破解密码

background:
P 哥是一个经常丢密码条的男孩子。

在 ION8102 赛场上，P 哥又弄丢了密码条，笔试满分的他当然知道这可是要扣 $5$ 分作为惩罚的，于是他开始破解 IONXunil 系统的密码。

description:
定义一个串合法，当且仅当串只由 $\verb!A!$ 和 $\verb!B!$ 构成，且没有连续的 $3$ 个 $\verb!A!$。P 哥知道，密码就是长度为 $N$ 的合法字符串数量对 $19260817$ 取模的结果。但是 P 哥不会算，所以他只能把 $N$ 告诉你，让你来算。

至于为什么要对这个数取模，好像是因为纪念某个人，但到底是谁，P 哥也不记得了。

然而他忘记字符串长度 $N$ 应该是多少了，于是他准备试 $M$ 组数据。

inputFormat:
第一行给出一个整数 $M$ 表示询问次数。

接下来 $M$ 行每行给出一个正整数 $N$，表示该组询问中字符串的长度。

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

hint:
### 样例部分解释 :。

长度为 $1$ 时只有 $\verb!A!$ 和 $\verb!B!$ 两种排列，都是合法的。

长度为 $3$ 时除了 $\verb!AAA!$ 是不合法的其他都是可以的，故有 $2^3-1$ 种。

### 数据范围。

- 对于 $20\%$ 数据，全部 $N\leq20$，$M\leq2$；
- 对于 $70\%$ 数据，全部 $N\leq10^7$；
- 对于 $100\%$ 数据，全部 $N\leq10^9$，$M\leq10$。


title: Scarlet loves WenHuaKe

background: Scarlet上大学了，在此之前，她加强了一道高考模拟题QAQ

description:
Scarlet尝试在$n$行$m$列的中国象棋棋盘上放置$2\times n$ 个炮，使得它们互不攻击。

大家都知道Scarlet沉迷搞事，她想问你有多少个方案。

inputFormat: 一行两个整数，分别表示$n$ 和 $m$

outputFormat: 一个整数，表示方案数对$998244353$取模后的值

hint:
对于20%的数据，$n,m\leq5$

对于另25%的数据，$n,m\leq2000$

对于另20%的数据，$n=m$

对于剩下的35%的数据，$m-n\leq10$

对于100%的数据，有$1\leq n\leq m\leq100000$


title: Counting swaps

background:
Just like yesterday (in problem U of the practice session), Bob is busy, so Alice keeps on playing some single-player games and puzzles. In her newest puzzle she has a permutation of numbers from 1 to n. The goal of the puzzle is to sort the permutation using the smallest possible number of swaps.

Instead of simply solving the puzzle, Alice is wondering about the probability of winning it just by playing at random. In order to answer this question, she needs to know the number of optimal solutions to her puzzle.

description:
You are given a permutation p1, …, pn of the numbers 1 through n. In each step you can choose two numbers x < y and swap px with py.

Let m be the minimum number of such swaps needed to sort the given permutation. Compute the number of different sequences of exactly m swaps that sort the given permutation. Since this number may be large, compute it modulo 10^9 + 9.

inputFormat:
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of two lines. The first line contains the integer n. The second line contains the sequence p1, …, pn: a permutation of 1, …, n.

In the easy subproblem C1, 1 ≤ n ≤ 10.

In the hard subproblem C2, 1 ≤ n ≤ 105.

outputFormat: For each test case, output a single line with a single integer: x%(10^9+9), where x is the number of ways to sort the given sequence using as few swaps as possible.

translation:
给定你一个 $ 1∼n $ 的排列 $p$，可进行若干次操作，每次选择两个整数 $x,y$，交换 $px,py$。

请你告诉穰子，用最少的操作次数将给定排列变成单调上升的序列 $1,2,…,n$，有多少种方式呢？请输出方式数对 $10^9+9$ 取模的结果。

Translated by @LJC00118

hint:
In the first test case, we can sort the permutation in two swaps. We can make the first swap arbitrarily; for each of them, there’s exactly one optimal second swap. For example, one of the three shortest solutions is “swap p1 with p2 and then swap p1 with p3”.

In the second test case, the optimal solution involves swapping p1 with p2 and swapping p3 with p4. We can do these two swaps in either order.

The third sequence is already sorted. The optimal number of swaps is 0, and thus the only optimal solution is an empty sequence of swaps.
题目来源：[IPSC2016](https://ipsc.ksp.sk/2016/real/problems/c.html)


title: 果冻

background:
[赛时答疑](https://www.luogu.org/discuss/show/80694)

**数据已经修复**

[生存世界]Steve:你们哪位dalao可以收留我啊qwq

在minecraft一个很友善、亲和的服务器里面，Steve很喜欢在里面畅游，服务器采用小镇机制，于是有很多小镇。有一个镇叫果冻镇，镇长长得很像（误）喜欢吃果冻，他很喜欢对着镜子（误）吃着blingbling的果冻。突然，他收到捷报，镇上不久就要造反。他吓得一跳，赶紧从床上跳了起来qwq,吃了一口果冻（误），着手处理这件事情。

description:
镇上有一个镇长以及n-1个镇员，所有的镇员都有着他的直属上司fi。每个镇镇员与镇长都有一个距离di(也就是他与镇长之间上司的人数+1)。镇长想要所有镇员都是自己的直属下司，也就是与他的距离为1。

他每分钟可以让自己的一个镇员变为自己的直属下司，在第t (t>0)分钟的时候，（也就是每一分钟的意思，而t将从1开始），这个镇员变为自己的直属下司，镇长可以收获(di+t)&k的安全指数（其中，&为按位与运算）。然后**这个镇员的下司都会跟着这个镇员一起变动**（也就是这个镇员的直属下司仍然是这个镇员的，除非镇长把这个下司变为自己的直属下司）。

当所有镇员都是自己的直属下司后，qwq镇长就可以安心吃他的果冻了。他现在想问你，应该怎样变动，才能使安全指数最大。因为镇长很想快点吃到果冻，_(:зゝ∠)\_他就把这个任务交给你了。

inputFormat:
第一行是两个正整数n和k（具体意义请见题目描述）
从第二行开始，下面连续n行，每行有两个字符串（由大写字母、小写字母、下划线、数字、上引号或者逗号组成），分别表示的是这个镇员和他的直属上司。**特别地，第二行是镇长，他没有直属上司，所以第二行只有一个字符串，表示镇长**。数据保证第二个字符串在第一个字符串前出现过。

outputFormat: 一个整数，表示最大的安全值。

samples:
7 3
LDLD
tk_sky LDLD
Jayden_deng LDLD
only_xiaohuang tk_sky
Muddled_xiaopan tk_sky
Inkn only_xiaohuang
ipdjkl only_xiaohuang

hint:
**样例解释**
第二个样例:  （图片有可能会挂，请耐心等待一会哦qwq）
![](https://s1.ax1x.com/2018/10/28/ic6RmQ.png)
![](https://s1.ax1x.com/2018/10/28/ic6Wwj.png)
![](https://s1.ax1x.com/2018/10/28/ic6fTs.png)
![](https://s1.ax1x.com/2018/10/28/ic64kn.png)
![](https://s1.ax1x.com/2018/10/28/ic6gOg.png)
由于~~出题人过懒~~，移动子节点的情况就未列举。请自行hack自己。（滑稽）

**数据范围：**
记下列两种特殊情况：
1.保证字符串长度为1
2.树退化成一条链
![]( https://cdn.luogu.com.cn/upload/pic/39861.png)
对于所有的数据，保证k在int范围内，字符串长度不超过10^6。n,k均为正整数。


title: LJJ爱数数

background: 题解请查看[https://www.cnblogs.com/Blog-of-Eden/p/9367521.html](https://www.cnblogs.com/Blog-of-Eden/p/9367521.html)

description:
PJY某次翻阅杂志时，看到一道题：

求出所有的**正整数**三元组{a,b,c}，满足a,b,c<=n，**a,b,c三个数的最大公约数为1**，且**1/a+1/b=1/c**。

PJY嫌这道题太水，于是把它甩给了爱数数的LJJ，并加上了数据范围**n<=1e12**，让LJJ数出**有多少组满足条件的三元组{a,b,c}**
（注意当a不等于b时，{a,b,c}和{b,a,c}是不同的三元组，要算两次）

LJJ数到一半，发现这个数量太大了，于是他把问题抛给了你。请你输出这个数量。

inputFormat: 输入仅一行：一个正整数n（n<=1e12）

outputFormat: 输出仅一行：一个整数，表示满足条件的三元组{a,b,c}的数量


title: 【模板】单源最短路径（标准版）

background:
2018 年 7 月 19 日，某位同学在 [NOI Day 1 T1 归程](https://www.luogu.org/problemnew/show/P4768) 一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢？

$100 \rightarrow 60$；

$\text{Ag} \rightarrow \text{Cu}$；

最终，他因此没能与理想的大学达成契约。

小 F 衷心祝愿大家不再重蹈覆辙。

description:
给定一个 $n$ 个点，$m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

数据保证你能从 $s$ 出发到任意点。

inputFormat:
第一行为三个正整数 $n, m, s$。
第二行起 $m$ 行，每行三个非负整数 $u_i, v_i, w_i$，表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。

outputFormat: 输出一行 $n$ 个空格分隔的非负整数，表示 $s$ 到每个点的距离。

hint:
样例解释请参考 [数据随机的模板题](https://www.luogu.org/problemnew/show/P3371)。

$1 \leq n \leq 10^5$；

$1 \leq m \leq 2\times 10^5$；

$s = 1$；

$1 \leq u_i, v_i\leq n$；

$0 \leq w_i \leq 10 ^ 9$,

$0 \leq \sum w_i \leq 10 ^ 9$。

本题数据可能会持续更新，但不会重测，望周知。

2018.09.04 数据更新 from @zzq


title: LJJ 爱数树

description:
Eden 偶然间拿到了一张藏宝图，值得一提的是，这是张无向联通图，有 $n$ 个节点，$n-1$ 条长度为 $1$ 的边，即一颗树。每个节点上都标有该地点的宝藏数量 $w_i$。

然而宝藏太多，不能一次性搬完，Eden 花费其所有积蓄买来 $k$ 个摄像头，每个摄像头能观测的距离范围是 $r$（我们规定树上任意两点距离为其最短路径的长度）。为了确保宝藏尽可能不被他人拿走，Eden 将要在这棵树上的至多 $k$ 个节点处布置摄像头（于是与该节点距离 $\le r$ 的节点都能被观测到）。

Eden 想要使能被观测到的节点的宝藏数量（即 $w_i$）之和最大化，于是他把这个问题交给了爱数树的 LJJ。让 LJJ 枚举所有可能放置摄像头的情况，来筛选出最优的方案。

LJJ 数到一半，发现这个方案数量太多了，于是他把问题抛给了你，
请你输出能被观测到的节点的 $w_i$ 之和的最大值。

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

第 $1$ 行：一个正整数 $T$，表示有 $T$ 组数据。

接下来每组数据：\
第 $1$ 行：$3$ 个用空格分隔开的正整数 $n, k, r$。\
第 $2$ 行：$n$ 个用空格分隔开的正整数，第 $i$ 个数表示 $w_i$。\
第 $3$ 至 $n+1$ 行：每行两个整数 $x,y$，表示 $x$ 到 $y$ 之间有一条边。

outputFormat: 对于每组数据，一行输出一个整数，表示能被观测到的节点的 $w_i$ 之和的最大值。

hint:
对于 $10\%$ 的数据，保证 $n\le20$，$r\le 20$，$w_i\le20$；

对于 $40\%$ 的数据，保证 $n\le50$，$r\le 50$，$w_i\le50$；

对于另外 $20\%$ 的数据，保证 $k\le2$；

对于另外 $10\%$ 的数据，保证给出的树是一条链。

对于 $100\%$ 的数据，保证 $1\le k \le n\le10^3$，$1\le r\le 10^3$，$1\le w_i\le10^6$，$1\le T\le 5$，$1\le x,y\le n$。

官方题解请查看 [https://www.cnblogs.com/Blog-of-Eden/p/9367521.html](https://www.cnblogs.com/Blog-of-Eden/p/9367521.html)。


title: Oier们的镜子(mirror)

background:
原创By：[b2019dy](https://www.luogu.org/space/show?uid=78488) 、[disangan233](https://www.luogu.org/space/show?uid=72679)

$gcd$是一个很臭美的OIer，他有一些神奇的镜子。

description:
$gcd$手里一共有$n$个物体，它们的编号为$A_1,A_2,A_3\cdots A_n$。这些物体中有元素板也有镜子，元素板上带有元素，镜子一开始不带元素。

一个元素板可以与**至多**一面镜子相对应，那样的话那面镜子将会带上元素板上的元素。

一面镜子无法对应其他镜子。

现在告诉你物体总数$n$和每个物体**对应后**所带的元素个数，请问一共有多少种对应情况。

inputFormat:
第一行：整数$n$表示物品总数。
第二行：共$n$个整数表示每一个物品最终的元素数。

outputFormat: 输出方案总数对$1000000007$取模的值。

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

对于$50\%$的数据，$n\leq 10$。

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

## 样例解释

因为出题人太懒现将解释中的"(其余)全是元素板"缩写为"suki"！"对应"缩写为$\to$

### 样例1
* suki。
* $A1,A2\to A3$。

#### 答案为：$2$。

### 样例2
* suki。
* $A2,A3\to A4$，suki。
* $A1,A4\to A5$，suki。
* $A1,A2,A3\to A5$，suki。
* $A2\to A3$，suki。
* $A2\to A3$，$A1,A4$->$A5$。
* $A3\to A2$，suki。
* $A3\to A2$，$A1,A4$->$A5$。

### 答案为：$8$。


title: OIer们的东方梦

background:
**#11,#12 两组 Hack 数据由 uid=20285 提供**

OIer 们做~~魂魄妖~~梦都想去幻想乡玩一下。这一次，他们在睡~~古明地~~觉时在梦中穿越去了幻想乡，幻想乡有很多的少(ju)女(ruo)，但是他们被~~老太婆~~少女的美色~~和蒟蒻的美味~~所吸引，在幻想乡中迷失了方向。

勇敢的~~死肥宅~~少年啊，现在你手里有一份幻想乡人间之里的地图，你知道 OIer 们的位置，你可以远程给OIer们传递信息，请你带领迷路的 OIer 们走进回到现实生活的祭坛吧！

description:
给你一个 $N\times M$ 的地图，如图所示：
```
5400000S01
1111101101
000003X301
3111111101
E000300031
1111X30001
```

其中有很多稀奇古怪的东西：

* $S$ 表示出发点，$E$ 表示终点。
* $0$ 表示空地，你想怎么走就怎么走，走一格需要 $1s$。
* $1$ 表示墙，你无法通行（~~除非你受到了**风神少女**的庇护~~）。
* $2$ 表示小妖怪，你需要 $3s$ 的时间去消灭小妖怪，才能经过该位置。（PS: 妖怪被消灭后只要离开当前格子立刻复活）
* $3$ 表示大妖怪，你需要 $8s$ 的时间去消灭大妖怪，才能经过该位置。
* $4$ 表示太阳花田，到达该位置可以获得太阳花，获得太阳花后遇到妖怪时可**直接**通过该妖怪的位置。
* $5$ 表示楼观剑（科普君：楼观剑，英文名 $Louguan\ is\ very\ jian$，是妖怪做的剑，楼观剑斩不断的东西几乎没有)，到达该位置可以花费 $5s$ 获得它，获得它后可以砍墙砍妖怪将其变成空地（当然也可以不砍，砍墙砍妖怪不需要时间，楼观剑可以一直使用**不会损坏**，有了楼观剑依然可以使用隙间，但是楼观剑不能砍隙间~~和一点用都没有的麻薯，麻薯妖梦UUZ是一家嘛~~）
* $M$ 表示麻薯（是 $mashu$ 不是 $mafu$~~不知道麻薯是什么的一把楼观剑给你砍过来~~)，碰到麻薯后你可以把它吃了(路人甲：那你为什么还要加这个东西? 出题人：有 $S$ 肯定要有 $M$ 啊。路人乙：我就是死外边，从隙间中跳下去，也不会吃麻薯！嗯~真香！）
* $X$ 表示紫妈的隙间，碰到隙间后会传送至其他的任意一个隙间(数据**不**保证只有 0 或 2 个隙间，**就是说可以有很多隙间乱传**)，每次传送耗时 $1s$。(经过当前格子时可以不经过隙间)

答案输出 OIer 们到达终点所需最短时间。如果无法到达，输出 "We want to live in the TouHou World forever"。
翻译：此生无悔入东方，来世~~睡遍~~愿生幻想乡。

**温馨提示：不排除存在可以往回走等稀奇古怪的最优走法**

inputFormat:
数据共有 $N+1$行。

第 $1$ 行输入 $N$ 和 $M$。
第 $2$ 到 $N+1$ 行输入 $N\times M$ 的地图。

outputFormat: 一行，最短时间或者 "We want to live in the TouHou World forever"。

hint:
对于 $30\%$ 的数据，$1\leq N,M\leq 50$。
对于 $50\%$ 的数据，$1\leq N,M\leq 100$。
对于 $100\%$ 的数据，$1\leq N,M\leq 1000$。

保证有一组数据答案为 "We want to live in the TouHou World forever"，数据有梯度。

### 样例解释

**样例 1**：在 $7s$ 时到达楼观剑，在 $12s$ 时获得楼观剑，一路向下砍到达终点。
**样例 2**：在 $10s$ 时到达 $(3,3)$，在 $32s$ 时到达$(3,10)$，向上进入隙间后到达终点。
**样例 3**：这个就不用解释了吧(出题人放飞自我)。


title: Phi的反函数

description: 求最小的正整数x，使得$\varphi(x)=n$

outputFormat: 输出x，如果$x>2^{31}$或者不存在，则输出-1


title: [COI2008] KOLEKCIJA

description:
Igor 有一个包含 $n$ 首歌的歌单，歌曲从 $1$ 至 $n$ 编号，他今天要听 $m$ 首歌。

当播放第 $i$ 首歌时，连续 $k$ 首歌的信息会被显示在一个列表上，这连续 $k$ 首歌必须包含第 $i$ 首歌，但是没有其他要求。

当一首歌被显示在列表上时，它的信息会被读取一次。如果一首歌多次被显示在列表上，他的信息也**只会被读取一次**（无论两次显示是否连续）。

请给出一种方案，使得系统读取歌曲信息的次数**最少**。

inputFormat:
第一行有两个整数，分别表示歌单的歌曲数 $n$ 和给定的参数 $k$。

第二行有一个整数，表示 Igor 要听的歌曲数 $m$。

第 $3$ 到第 $(m + 2)$ 行，每行一个整数，表示 Igor 要听的第 $i$ 首歌的编号 $a_i$。

outputFormat:
**本题存在 Special Judge**。

请在第一行输出一个整数 $t$，表示读取歌曲信息的最少次数。

第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的 $l_i, r_i$，表示听第 $i$ 首歌的时候显示第 $l_i$ 到第 $r_i$ 首歌的信息。

你的输出需要保证 $r_i - l_i + 1 = k$，$1 \leq l_i \lt r_i \leq n$，且按照你给出的方案读取的歌曲数为 $t$。

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

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

- $1 \leq k \lt n \leq 10^9$，$1 \leq m \leq 3 \times 10^5$。
- $1 \leq a_i \leq n$，$a_i$ 互不相同。

#### 计分标准

- 如果输出的数字不足 $(2 \cdot m + 1)$ 个，或输出第一行的数字 $t$ 与答案不同，则获得测试点 $0\%$ 的分数。
- 如果 $t$ 与答案相同，输出方案错误，则获得该测试点 $50\%$ 的分数。
- 如果 $t$ 与答案相同，且输出方案正确，则获得该测试点 $100\%$ 的分数。

#### 说明

**题目译自 [COCI2007-2008](https://hsin.hr/coci/archive/2007_2008/) [COI2008](https://hsin.hr/coci/archive/2007_2008/olympiad_tasks.pdf) *T2 KOLEKCIJA***，翻译与 SPJ 均来自[一扶苏一](https://www.luogu.com.cn/user/65363)。


title: Zrz_orz Loves Secondary Element

description:
众所周知的是，zrz_orz是全机房最强的死宅。~~他甚至使用嘴遁使得Samcompu不得不在自己的网站上挂上时崎狂三~~。(话说Samcompu好像醒悟了又把狂三给去掉了。)作为新一代死宅的一员，从电脑壁纸到输入法皮肤，到处都是二次元的痕迹。所以，他经常在梦里梦见一些二次元的角色。

zrz_orz的梦，是由$n$个点和$n-1$条边构成的连通图。其中有$m$个节点上有一个二次元的角色。对于zrz_orz来说，每一个二次元的角色都有一个对应的$pos_i$和$val_i$表示这个角色在图上的哪一个节点以及与之聊天对zrz_orz来说会增加多少愉悦值。(由于某种原因，聊天的过程可以不用计入时间。)可惜的是，zrz_orz每一次做梦都只会做$tim_i$个单位时间。现在请你告诉他，他每一次做梦最多能获得多少愉悦值。

注：

1.zrz_orz每一次做梦都只会从1号节点开始走！

2.每一次做梦后zrz_orz梦境中的图都不会改变！

**3.每一次做完梦之后zrz_orz就必须要回到1号节点，否则他就会迷失在梦境里！**

inputFormat:
第1行三个正整数$N$,$M$,$T$表示图的节点数、二次元角色的数量、做梦的天数。

接下来$N-1$行每行三个正整数$u_i$,$v_i$,$w_i$表示第$i$条边连接的两个节点以及zrz_orz走过这条边所花费的时间。

接下来$M$行每行两个正整数$pos_j$和$val_j$表示第$j$个二次元角色在节点上的位置以及能给zrz_orz带来的愉悦值。

接下来$T$行每行一个正整数$tim_k$表示第$k$天zrz_orz做梦的时间。

outputFormat: 一共$T$行。每一行包括一个正整数表示zrz_orz每天最多能获得的最大愉悦值。

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

第一天哪里都去不了。

第二天1->3->6->7->6->3->1获得最大愉悦值为7。

第三天所有的地方都可以走一遍。

Subtask 1(20 pts):

$ 1 \leqslant T \leqslant 10 \qquad 1 \leqslant N \leqslant 1000 \qquad 1 \leqslant M \leqslant 20 \qquad 1 \leqslant  tim_k \leqslant 1000$

Subtask 2(40 pts):

$ 1 \leqslant T \leqslant 10^5 \qquad 1 \leqslant N \leqslant 10^5 \qquad 1 \leqslant M \leqslant 20 \qquad 1 \leqslant  tim_k \leqslant 10^5$

Subtask 3(40 pts):

$ 1 \leqslant T \leqslant 5*10^4 \qquad 1 \leqslant N \leqslant 5000 \qquad 1 \leqslant M \leqslant 100 \qquad 1 \leqslant  tim_k \leqslant 100 \qquad 1 \leqslant w_i \leqslant 5$

For all test points:

$ 1 \leqslant pos_j,u_i,v_i \leqslant N \qquad 1 \leqslant \sum val_j \leqslant 2e9 \qquad 1 \leqslant w_i \leqslant 20 \qquad 1 \leqslant tim_k \leqslant 10^5 $

注意: 标记的分数就是这个Subtask的分数，每一个Subtask必须全对才能得分。Subtask 2的时限为1.5s。

$$ \color{white} \text{NOIP 2合1} $$


title: [国家集训队] 丢失的题面（ydc的题面）

description:
曾经，有一个题面摆在 ydc 的面前没有珍惜，直到失去时才后悔莫及，

如果上天再给他一次机会，ydc 一定会牢牢的记住这个题面。

没办法，已经失去了，所以这道题只能让你帮 ydc 做了。

已知的信息只有，这道题是传统题，采用全文比较的方式，时间限制 1s，空间限制 256MB。

ydc 还给你提供了这道题的所有数据（见附件）。

inputFormat: 已给出

outputFormat: 已给出

hint:
### 来源

中国国家集训队互测2015

### Author

于纪平


title: 小凯的数字

background:
NOIP2018 原创模拟题T1

NOIP DAY1 T1 or DAY 2 T1 难度

是否发现与NOIP2017 DAY1 T1 有异曲同工之妙

description:
小凯有一天突发奇想，写下了一串数字：$\overline{l(l+1)(l+2)...(r-1)r}$

例如：$l=2,r=5$时，数字为：$2345$

$l=8,r=12$时数字为：$89101112$

小凯很喜欢数字 $9$，所以他想问你他写下的数字除以 $9$ 的余数是多少

例如：$l=2,r=5$时，$2345\,\,mod\,\,9 = 5$

inputFormat:
输入格式：

第一行为数字 $Q$,表示小凯有 $Q$ 个问题

第 $2$ 到 $Q+1$ 行，每行两个数字 $l,r$ 表示数字范围

outputFormat:
输出格式：

对于每行的问题输出一行，一个数字，表示小凯问题的回答


title: LJJ爱数书

description:
LJJ的家里有一本“数书”，也就是说里面全都是数字的书，LJJ十分喜爱它。
数书里有一个序列A，每次操作可以**使一段连续的区间加1或减1**并**对K取模**（K-1加1后变为0，0减1后变为K-1），我们定义**和谐函数F(A,K)表示最少的操作次数，使得序列的所有元素都变为0**。
例如A={3,3,2,3}，K=4时，通过把A变成{0,0,3,0}，再把A变成{0,0,0,0}就能达到要求，所以F(A,K)=2。

现在，输入长度为**n（n<=200000）**的序列A，设A[L][R]表示序列A第L个位置到第R个位置的连续子序列。
 有**m（m<=100000）**次询问，每次询问**输入L,R,K**，求**F(A[L][R],K)的值**。

**注：数据保证K>Max{A[1],A[2],....,A[n]}。**

inputFormat:
第1行：两个整数n,m，表示序列长度为n，有m次询问。
第2行：n个整数，第i个整数表示A[i]
第3至m+2行：每行三个整数L,R,K（1<=L<=R<=n，K<=2^30）

outputFormat: 共m行：每行一个整数，表示每组询问的答案F(A[L][R],K)


title: Barracuda

background:
小正方形的冒险旅途，并不顺利。

一路上，小正方形看到了壮美秀丽的小岛被污染，看到了雄伟壮观的火山，还碰到了许许多多的敌人。

眼下，小正方形正在对付一个巨大的三角形。

description:
大三角形给小正方形讲起自己的过去：过去的它是一个挖宝工，后来被黑暗之主污染才会落到此番境地。

它也希望小正方形去战胜黑暗之主，不过限于黑暗之主的眼线密布，因此必须给小正方形设置障碍才能骗过那些“眼线”。

他给小正方形的问题是：它有 $n$ 个小三角形，每个小三角形有一定的质量，它对这些三角形进行了 $n + 1$ 次称量，然而由于托盘天平(?)的问题，有一次称量的结果是有误的。

现在，大三角形想要知道最重的小三角形的 编号。

一组输入是合法的，当且仅当输入满足以下条件：

不存在一组 $i$,$j$，使得当我们**假定**第 $i$ 条称量数据有误时能求出一种合法方案且我们**假定**第 $j$ 条称量数据有误时也能求出一种合法方案。

合法方案定义如下：

1、最重的三角形只有一个。

2、不存在重量不确定的三角形。

3、所有三角形的重量均为正整数。

inputFormat:
输入的第一行为一个正整数 $n$，表示小三角形的数目。

接下来 $n + 1$ 行，每行按照以下格式输入：

首先是一个正整数 $m$，表示这次称量抓了几个小三角形。

接下来 $m$ 个整数，表示称量的小三角形的编号。

最后一个整数 $weight$ ，表示这次称量的结果。

outputFormat: 若合法，输出最重小三角形的编号，否则输出 "illegal"(不含引号)。

hint:
样例一：

若第一次称量结果错误，则无法得出正确解。

若第二次称量结果错误，则第二个小三角形重量为负，显然不对。

若第三次称量结果错误，我们得出 $1$ 号小三角形重量为 $2$，$2$号小三角形重量为 $3$，$2$号小三角形最重。

本题采用捆绑测试，共有三个 $subtask$，描述如下：

$subtask 0 - 30Pts$ 保证小三角形的重量 <= 20且 $n <= 5$，在这个 $subtask$ 中，你每通过一个点可获得 $10$ 分。

$subtask 1 - 30Pts$ 保证小三角形的重量 <= 100 并且 $n <= 100$，数据为随机生成。

$subtask 2 - 40Pts$ 保证小三角形的重量 <= 100 并且 $n <= 100$

在后两个 $subtask$ 中，你必须通过所有数据才能得分。

对于 $100\%$ 的数据， $1 <= m <= n$


title: Lycanthropy

background:
小正方形亲眼看见了自己昔日的朋友被卷进了黑暗的深渊，然而它无力阻止……

现在它的朋友已经向它发起了攻击，因此小正方形不得不抵抗。

description:
我们把山顶上的湖泊看作一条长度为 $m$ 的直线，一开始水深都在水平线上，我们视作此时的水深为 '0'

接下来，在一瞬间，小正方形的"朋友"们跳起并扎入水中，导致在入水点的水降低而远离入水点的水升高，注意两个 "朋友" 可能在同一地点入水。

小正方形的每个朋友有一个体积数值 $v$，当体积为 $v$ 的一个朋友跳入水中，我们设入水点为 $i$，将会导致 $i - v + 1$ 到 $i$ 的水位依次降低 $1,2,\cdots,v$

同样地，第 $i$ 到 $i + v - 1$ 的水位会依次降低 $v,v - 1,\cdots,1$.

相对应地，$i - v$ 的水位不变， $i - v - 1$ 到 $i - 2 * v$ 水位依次增加 $1,2,\cdots,v$， $i - 2 * v$ 到 $i - 3 * v + 1$ 水位依次增加 $v,v - 1,\cdots,1$

同样，$i + v$ 水位不变，$i + v + 1$ 到 $i + 2 * v$ 水位增加 $1,2,\cdots,v$，$i + 2 * v$ 到 $i + 3 * v - 1$ 水位依次增加 $v,v - 1,\cdots,1$

现在小正方形想要穿过这个湖，他想要知道在这 $n$ 个"朋友"跳入水中后湖上每个节点的水位，你能帮帮它吗？

inputFormat:
第一行为两个整数 $n$,$m$，表示"朋友"的数目与湖泊的宽度。

接下来 $n$ 行，一行两个整数 $v,x$，表示第 $i + 1$ 个朋友的体积与入水点。

outputFormat: 一行 $m$ 个整数，第 $i$ 个整数表示 $i$ 号位的水深。


title: Annihilate

background:
前情提要：小正方形与黑暗之主展开了大战，最后小正方形击败了黑暗之主，成功从黑暗之主的手上夺下最后一个三角。

三角旋转着，净化着，正当三角即将净化完成时，黑暗之主突然到来，阻断了三角形的净化，吸收了三角的能量。

可是，因为三角的能量太过巨大，导致黑暗之主发生了变异，现在的黑暗之主一次次复制，最终成为了一条蜈蚣……

现在，小正方形还能阻止黑暗之主毁灭世界吗？

description:
黑暗之主的蜈蚣几乎可以毁灭一切，因此小正方形陷入了苦战……

小正方形现在需要减弱黑暗之主的攻击。

一个黑暗之主的攻击可以用一个仅有小写字母的字符串表示。

现在黑暗之主向小正方形发动了若干攻击，对于两个攻击，小正方形能选出它们最长的公共**子串**，并把这一段消除。

现在小正方形想要知道，对于**任意两个**黑暗之主的攻击，它们的最长公共子串长度是多少，你能帮帮它吗？

inputFormat:
第一行为一个整数 $n$，表示字符串数目。

接下来 $n$ 行，一行一个字符串，保证所有字符串长度之和 <= 1000000

outputFormat:
输出共有 $n$ 行，每行 $n - 1$个正整数

第一行第一个正整数表示第1个串与第2个串的最长公共子串

第二个正整数表示第1个串与第3个串的最长公共子串

……

第二行第一个正整数表示第2个串与第1个串的最长公共子串

以此类推。

hint:
对于 $30\%$ 的数据，$n <= 5$，每个字符串长度 $<= 500$

对于 $100\%$ 的数据，$2 <= n <= 50$，字符串长度之和 $ <= 1000000$

**注意：本题内存限制仅为 64 MB,请尽量使用内存运用优秀的方法。**

另外，对于占 60 Pts 的测试点，您每通过一个点即可获得 10 Pts

对于剩下的测试点，您只有全部通过才能获得 40 Pts.

**对于所有数据点，不保证数据为随机生成。**


title: T'ill It's Over

background:
小正方形被黑暗之主碾成了粉末。

一切，就这么结束了吗？

就当大家都以为再无翻盘的希望时，

已经被净化的两个世界之树的部分，微微闪烁……

description:
小正方形被三角的力量复活了，它即将与黑暗之主展开最后的战斗。

小正方形最后的目标，就是净化黑暗之主。

黑暗之主的蜈蚣长度为 $n$，一开始每一节的光明程度为 $1$

当一节蜈蚣的光明程度达到一个指定的值 ($k$)，我们就视作这节蜈蚣被净化。

为了净化黑暗之主，小正方形准备了 $m$ 种方案，这些方案按本质上的不同大约可分为四种：

1. 将一节光明程度为 $a$ 的蜈蚣的光明程度 变为 $b$。（注意，$b$ 可能 $<=a$）

2. 将一节光明程度在 $a1$ 到 $a2$ 区间的蜈蚣的光明程度变为 $b1$

3. 将一节光明程度为 $a1$ 的蜈蚣的光明程度变为 $b1$ 到 $b2$ 区间的任意值。

4. 将一节光明程度在 $a1$ 到 $a2$ 区间的蜈蚣的光明程度变为 $b1$ 到 $b2$ 区间的任意值。

由于小正方形使用每种方案需要消耗一定程度的属性能量，因此每种方案都有一个独立的使用次数的上限，在一种方案中我们用 $l$ 来表示这个上限。

小正方形想要知道，自己最多能够净化几节黑暗之主的蜈蚣。

inputFormat:
第一行为三个正整数 $n$，$m$，$k$，表示黑暗之主蜈蚣身体的长度，小正方形的方案总数与上文所述的 $k$。

接下来 $m$行，每行开头为两个正整数 $op$,$l$，表示方案的种类与使用次数的上限，方案的输入方式如下：

若 $op = 1$，则接下来两个整数 $a$，$b$，意义如上文所述。

若 $op = 2$，则接下来三个整数 $a1$,$a2$,$b1$，意义如上文所述。

若 $op = 3$，则接下来三个整数 $a1$,$b1$,$b2$，意义如上文所述。

若 $op = 4$，则接下来四个整数 $a1$,$a2$,$b1$,$b2$，意义如上文所述。

数据保证，所有 $1 <= a,b,a1,b1,a2,b2 <= k$

outputFormat: 一行一个整数，表示最多能净化的节数。


title: 经验

background:
[赛时答疑](https://www.luogu.org/discuss/show/80694)

**简略版已经更新，时限改为500ms**

攒够经验附魔去~~

Steve在minecraft中总是会遇上难题：
他想要修理n本附魔书，每本附魔书的等级为ai，他总是不知道铁砧修理和经验值的机制。他便在mcwiki上搜索到了一些资料：
![](https://d1u5p3l4wpay3k.cloudfront.net/minecraft_zh_gamepedia/pChart4mw/e8160a1cad02998149d79c65237dc775.png)

----图为经验值与等级的关系，摘自mcwiki

他看到这个图，就想：我等级升的越高，我所需要的经验值便越多，那么如果我等级刚好够铁砧修理的话，那我所耗费的经验不就越少了吗？他便继续搜索了下去，并将铁砧机制附在了下面,让你帮他解决问题：

description:
**累积惩罚：**

无论是重命名、修复、还是合并操作，其经验花费都会因其物品先前在铁砧上的操作而增加，这些额外增加的花费被称作“累积惩罚”。对于一件从未放上铁砧的物品，累积惩罚为0。

一个物品每次在铁砧上操作过后（不包括重命名），其累积惩罚都会先乘2再加1。如此一来，一个物品在操作过N次后累积惩罚是2^N-1。6次操作之后，累积惩罚是63级，此时生存模式下无法再作进一步的修复和附魔工作。31次操作后，惩罚等级是2147483647级，此时在任何模式下都不能再进行操作。

当合并两个物品时，玩家会同时受到两件物品的累积惩罚。合并后物品的累积惩罚根据先前两个物品中较高者计算。例如，合并两个累积惩罚分别是3级和15级的物品会额外花费18级的惩罚经验，而合并后的物品惩罚是31级（15*2+1）。

累积惩罚甚至会作用在不会磨损的物品上，譬如附魔书。因此，合并4本时运 I 的附魔书，会得到一本累积惩罚为3的时运 III 附魔书。

     累计操作数	      惩罚

         0	           0

         1	           1

         2	           3

         3	           7

         4	           15

         5	           31

使用合成方格进行的物品修复操作会移除所有累积惩罚，但也会丢失所有的魔咒。

**合并物品：**

铁砧界面中第一格/左边的物品称为目标物品；第二格/右边的物品称为牺牲物品——合并后会消失。如果牺牲物品附有魔咒，铁砧会同时试图将牺牲物品的附魔合并至目标物品上。无论目标物品上的魔咒是否产生实际变化，铁砧都将根据目标物品与牺牲物品上的魔咒收取玩家的等级耗费。

对于牺牲物品上的每个魔咒来说：如果目标物品也拥有相同的魔咒：

当牺牲物品的魔咒等级较高时，目标物品魔咒的等级将上升至牺牲物品上的等级。

当牺牲物品的魔咒等级相同时，目标物品上魔咒的等级将提升1级，除非其等级已为最高。

当牺牲物品的魔咒等级较低时，目标物品上该魔咒的等级不变。

合并物品的总花费将是下列费用之和：

1.目标物品和牺牲物品的累积惩罚之和。

2.如果同时进行重命名，则额外产生重命名的费用。

3.如果目标物品耐久度未满，则耗费2级用于维修。

4.如果牺牲物品拥有魔咒，则产生附魔费用。

5.如果牺牲物品是一本附魔书，则不会产生维修费用，铁砧会尝试将书本上的魔咒合并至目标物品上。亦可同时对目标物品进行重命名。此时的附魔花费一般会少于合并两个类似物品的费用。

-----摘自mc wiki，稍作删改

**简略版：**
给出附魔书，只有同等等级的才能合并。合并的代价为两本书的累计代价之和。合成后的书的累计代价为合成前最大代价的2倍加上1。求最高等级和最小花费（要求最高等级为第一关键字）,Steve因为开了挂，所以最高等级不限

现给出$n$本附魔书，每本附魔书有它的等级$ai$,问如何才能得到附魔书的最大等级$x$，在此基础上，请计算合成它消耗的最小等级$y$。（我们假设每本附魔书初始的累积惩罚为1）。

Steve很懒，他不想看上面的话，他只想要让你编写出一个程序计算出$x$与$y$。但Steve为了不外传，他只要求你输出$x$在模$y$意义下的乘法逆元$k$即可。如果没有，请输出$-1$.

inputFormat:
第一行为一个整数$n$

接下来$n$行，每行均有一个整数$ai$，表示每本附魔书的初始等级，不保证数据有序.

outputFormat:
一个整数$k$,表示$x$在模$y$意义下的乘法逆元,如果没有，请输出$-1$.
PS：乘法逆元$k$也可以这样理解: $k$是使得 $kx\equiv1(mod$ $y)$的最小正整数

hint:
**样例解释**

第一个样例：
合并两个第一等级的，合并花费2经验，代价升为3
再合并两个第二等级的，花费3+1=4经验，代价升为7
再合并两个第三等级的，花费7+1=8经验，代价升为15
最后合并两个第四等级的，花费15+1=16经验，代价升为31

经验总花费：2+4+8+16=30，最大等级：5

对于第一个样例: $x=5$,$y=30$;

对于第二个样例: $x=3$,$y=10$;

**数据范围**

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

保证数据随机，$x$,$y$,$k$在long int范围内

**温馨提示**

本题读入量较大，请使用较快的读入方法，在此，提供一种快速读入的样式：(需包含头文件<cctype>)

```
#include<cctype>
inline void read(int &x){
     char ch=getchar();x=0;
     while(!isdigit(ch))   ch=getchar();
     while(isdigit(ch))   x=x*10+ch-'0',ch=getchar();
}
```


title: Samcompu Loves Water

background: Samcompu拥有大量的**"水"**资源！！

description:
Samcompu需要制定一个**水**计划。这个计划的主要目的就是为了避开老师监视的时间来水。

老师在中途会离开机房$T$次，第$i$次将会离开$tim_i$秒。Samcompu划水的时候可不是随便乱水的。他可是拥有**"水"**资源的。在他的库存中有$N$个可以水的网站。Samcompu拥有一种黑科技，他可以几乎不耗任何时间在网站与网站之间跳转并且把跳转的网页的信息秒存。也就是说，Samcompu并不需要在每一次跳转的时候花费时间去浏览网页。当然，这只局限于$N$个网站之间的$N-1$个跳转方式(保证每一个网站都可以跳转到另外的所有网站)。对于第$i$种跳转方式，第$u_i$个网站到第$v_i$个网站的跳转存在一个危险程度$w_i$，这个危险值可能会造成电脑卡死，如果Samcompu不能及时处理，那么就会**完美地**被老师发现。

值得一提的是，在被查水表很多次后，Samcompu总结出了一个规律：

老师走得越久，能够保证在被老师发现之前处理好电脑卡死的危险程度的上限就越高。简单来说，两者就是成正比的关系，比例系数为1。

可惜的是，Samcompu的黑科技并不稳定，在老师第$i$次离开的时候，第$K_i$个跳转方式就不可用了。

当然，每一次水都可以从任意一个网站开始，也可以从任意一个网站结束。

现在Samcompu想知道，对于第$i$次老师离开机房时，他能够有多少种不同的安全的水的方案。两种水的方案不同当且仅当这两种水的方案的第一个网站或者最后一个网站不同。

(补充说明: 一个安全的水的方案当且仅当当前是老师第$j$次离开教室时跳转的路径中不存在一个跳转方式$i$使得$tim_j \leqslant w_i$，每一次水完后不可用的跳转方式就会恢复。)

inputFormat:
第一行两个正整数$T$, $N$

接下来$N-1$行，每一行三个正整数$u_i$, $v_i$, $w_i$

接下来$T$行，每一行两个正整数$tim_i$, $K_i$

outputFormat: $T$行，每行一个正整数表示有多少中安全的水的方案。

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

第一次连接1和2的边不可用，当前能经过的边的危险程度需要<1，并没有合法的方案。

第二次连接1和3的边不可用，当前能经过的边的危险程度需要<2，合法的方案有  (1,2)    (2,1)    (3,4)    (4,3)  共四种。

第三次连接3和4的边不可用，当前能经过的边的危险程度需要<3，合法的方案有  (1,2)    (1,3)    (2,1)    (2,3)    (3,1)    (3,2)  共六种。

提醒:本题计算答案按照点对的方式计算.也就是说,如果起点和终点一样,则只看做同一种方案.特别的,$(x,y)$和$(y,x)\ (x \neq y)$算作两种不同的方案.

数据范围：

Subtask 1(30 pts):

$$ T=1 \qquad 1 \leqslant K_i \leqslant N \leqslant 10^3 \qquad 1 \leqslant tim_i, w_i \leqslant 10^3 $$

Subtask 2(50 pts):

$$ 1 \leqslant T \leqslant 5*10^3 \qquad 1 \leqslant K_i \leqslant N \leqslant 10^4 \qquad 1 \leqslant tim_i, w_i \leqslant 10^3 $$

Subtask 3(20 pts):

$$ 1 \leqslant T \leqslant 10^4 \qquad 1 \leqslant K_i \leqslant N \leqslant 10^4 \qquad 1 \leqslant tim_i, w_i \leqslant 10^3 $$

数据保证不同的$K_i$最多只有$10^3$个。

温馨提醒：由于出题人数据比较毒瘤，所以请尽量卡常。


title: 银河英雄传说V2

background:
小H昨天看到了luogu P1196这一题，触发了他内心中对英雄的感慨/雾。可是无奈他不会这一题，只好去请教小W。在讲完那一题之后，小W灵机一动——不如改一下这道题吧。

于是，一个很水的签到题出现了。

description:
某dalao：把题目说简单一点，方便让我一分钟A掉！

于是小W只好把题意简化一下：

给定n个长度为1的序列，第i个序列中有一个元素，值为ai，接下来有三种操作：

1. `M x y`，表示把x所在的序列放到y所在的序列之后。如果x,y已经在同一个序列，则不进行操作。
2. `D x`，表示把x所在的序列中从x处断开，也就是把x及x之后的元素单独取出来作为一个序列。
3. `Q x y`，表示查询x到y之间（包括x和y）所有元素的值之和。如果x和y不在同一个序列之中，输出-1.

inputFormat:
第一行为两个数n,m，分别代表元素个数和操作次数。第二行有n个数，为ai。
接下来m行，每行包括三种情况：M x y，D x或Q x y，与题目描述对应。

outputFormat: 对于每一个Q x y，输出一个数，表示所有元素的值之和。

hint:
（出题人非常良心地给了一个大一点的样例！）

样例1解释：

首先有5个序列（一个横排为一个序列），排列如下：
```
1
2
3
4
5
```

第一个操作将1放到4的后面，变成
```
2
3
4,1
5
```

第二个操作将3放到2后面，变成
```
2,3
4,1
5
````

然后查询第5个元素到第2个元素之间的和，由于不存在，输出-1；

将3所在的序列加到4所在的序列后面，变成
```
4,1,2,3
5
```

接下来变成了5,4,1,2,3，也就是所有元素都在1个序列了，因此接下来的两个合
并操作没有用了，然后把1之后的数字删除，变成：

```
1,2,3
5,4
```

查询2到2，输出2的值，也就是55352；

查询2到1，输出2+1的值，也就是113122.

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

~~为了避免某些乱搞（可能避免不了）~~，**前5个点按照传统方式计分，每个测试点10分；后五个点为subtask，必须全部通过才能得分，否则不得分。**

对于所有数据，1<=x,y<=n，1<=ai<=10^9


title: 寻找宝藏

background:
如果时光回到从前，或许，一切只是虚无……

小 W 坐着时光穿梭机到达了一个四维时空，在这里，开始了他的寻宝之旅。

description:
整个四维时空可以看做是一个四维的网格图，小 W 在 $(1,1,1,1)$ 这个位置，出口在 $(m,m,m,m)$。但由于小 W 毕竟是外来时空的人，他的行动在这里受到了一些限制。每次他只能使四个坐标中的一个加上 $1$。也就是说，他每次只能向右，向上，向前和向*（蒟蒻的出题人想不出来怎么形容了）走一步。

这个时空中有 $n$ 个宝藏，第 $i$ 个宝藏的坐标是 $(a_i,b_i,c_i,d_i)$，价值为 $v_i$。

小 W 想知道，他能够拿走宝藏的最大价值和是多少。由于小 W 也是一个喜欢未雨绸缪的人，他也希望能够找到多种不同的方案使它们都可以达到最大价值和的要求。不过这个数有可能很大，输出它对 $998244353$ 取模的结果即可。

注意！两个方案不同当且仅当两个方案中至少有一个宝藏选择的不同，如果仅仅路线不同而最终都选择了相同的宝藏不算不同的方案。

（小心两个宝藏待在相同的位置哦……）

inputFormat:
第一行两个数 $n,m$，分别代表宝藏个数和网格坐标的最大值。

接下来 $n$ 行，每行 $5$ 个数，分别是 $a_i,b_i,c_i,d_i,v_i$。

outputFormat: 输出两行，第一行是最大价值和，第二行是满足条件的方案个数对 $998244353$ 取模的结果。

hint:
对于样例 1，最好的办法是 $(1,1,1,1)$ 慢慢走到 $(3,1,3,1)$，再慢慢走到 $(5,5,5,5)$，获得 $16$ 的价值。最好的路径只有这 $1$ 条。

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

对于所有数据，$1\le a_i,b_i,c_i,d_i\le m$，$1\le v_i\le 10^9$。


title: kry loves 2048

background: kls是一个人赢。

description:
kls最近在玩一款类似2048的游戏，规则是这样的：

一开始，有$n$个方块，每个方块上有一个$1$到$m$的整数。

kls可以进行两种操作：

1. 选择两个数字相同的方块（不一定要相邻），将它们合并成一个数字为原来的两倍的方块；

2. 减小一个方块上的数字。

操作的次数没有限制，最终的得分为所有方块上的最大的数字。

因为kls要去陪妹子了，没有时间继续玩，他想让你帮忙计算一下，最多能得到多少分。

inputFormat:
因为数据可能很大，读入容易超时，所以kls给你们提供了一个c++的随机数生成器。

```cpp
void generate_array(int a[], int n, int m, int seed) {
    unsigned x = seed;
    for (int i = 0; i < n; ++i) {
        x ^= x << 13;
        x ^= x >> 17;
        x ^= x << 5;
        a[i] = x % m + 1;
    }
}
```

把这个函数复制到你的程序里。用一个足够大的数组，以及输入数据给出的$n$，$m$和$seed$作为参数，调用这个函数。然后这个数组里就是一开始的方块上的数字（下标从0开始）。

输入一行三个数$n,m,seed$，含义如上。

outputFormat: 一行一个数，表示最大得分。

hint:
### 样例解释

样例1生成出来的数是 6 10 7 5 4。

样例2生成出来的数是 8 12 48 4 4。

### 数据范围

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

对于60%的数据，$n, m \le 10^5$；

对于100%的数据，$n, m \le 10^7$，$1 \le seed \le 10^9$。


title: 选择题

description:
docriz 正在考试，他遇到了一个奇怪的选择题：这个选择题共有 $n$ 个选项，其中只有一个选项是正确的。他完全不会做这题，所以只能靠蒙。

蒙这道题分为 $n - 2$ 轮，在第 $1$ 轮开始之前，docriz 会在这 $n$ 个选项中随机蒙一项，之后的每轮流程如下：首先，nocriz 会过来帮他排除一个选项，由于 nocriz 事先知道答案，所以他会在现有的除正确的那一项和 docirz 正在选的那一项外的选项里，随机删去一个。之后，docriz 可以选择是否更换自己蒙的选项，如果更换，则随机更换到除正在选的那一项之外的任意一项。

docriz 在这 $n - 2$ 轮中，由于和 nocriz 达成的神秘协定，需要恰好更换 $k$ 次选项。他想知道，如何更换，使得自己蒙对的概率最大，输出这个概率。为了方便，你需要输出这个概率的分数形式在模 $10^9 + 7$ 意义下的结果。

inputFormat: 一行两个整数 $n, k$，意义如上所述。

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

hint:
样例 $1$ 到 $4$ 分别为 $\frac{2}{3}, \frac{1}{3}, \frac{3}{4}, \frac{5}{8}$。

对于 $30\%$ 的数据，保证 $5 \leq n \leq 10$。

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

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

对于另外 $10\%$ 的数据，保证 $k = n - 2$。

对于另外 $5\%$ 的数据，保证 $n \leq 10^2$。

对于另外 $10\%$ 的数据，保证 $n \leq 10^3$。

对于 $100\%$ 的数据，保证 $5 \leq n \leq 10^5, 0 \leq k \leq n - 2$。


title: 【模板】莫队二次离线（第十四分块(前体)）

description: 珂朵莉给了你一个序列 $a$，每次查询给一个区间 $[l,r]$，查询 $l \leq i< j \leq r$，且 $a_i \oplus a_j$ 的二进制表示下有 $k$ 个 $1$ 的二元组 $(i,j)$ 的个数。$\oplus$ 是指按位异或。

inputFormat:
第一行三个数表示 $n,m,k$。

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

之后 $m$ 行，每行两个数 $l,r$ 表示一次查询。

outputFormat: 输出 $m$ 行，每行一个数表示查询的结果。

hint:
对于5%的数据，为样例。

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

对于50%的数据，空间限制为 512 MiB。

对于100%的数据，$1 \leq n, m \leq 100000$，$0 \leq a_i, k < 16384$。


title: 【模板】2-SAT

description:
有 $n$ 个布尔变量 $x_1$$\sim$$x_n$，另有 $m$ 个需要满足的条件，每个条件的形式都是 「$x_i$ 为 `true` / `false` 或 $x_j$ 为 `true` / `false`」。比如 「$x_1$ 为真或 $x_3$ 为假」、「$x_7$ 为假或 $x_2$ 为假」。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

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

接下来 $m$ 行每行 $4$ 个整数 $i$, $a$, $j$, $b$，表示 「$x_i$ 为 $a$ 或 $x_j$ 为 $b$」($a, b\in \{0,1\}$)

outputFormat:
如无解，输出 `IMPOSSIBLE`；否则输出 `POSSIBLE`。

下一行 $n$ 个整数 $x_1\sim x_n$（$x_i\in\{0,1\}$），表示构造出的解。

hint:
$1\leq n, m\leq 10^6$ , 前 $3$ 个点卡小错误，后面 $5$ 个点卡效率。

由于数据随机生成，可能会含有（ 10 0 10 0）之类的坑，但按照最常规写法的写的标程没有出错，各个数据点卡什么的提示在标程里。


title: 難題「龍の頸の玉　-五色の弾丸-」

background:
輝夜が出した難題の一つ。この玉にはそれぞれ星が入っていて、
七つ集めるとどんな願いでもかなうという。

辉夜所出的难题之一。这些玉石各自都被画上了星星，
据说收集齐七颗就能够实现任何的愿望。

description:
五颗龙玉在同一平面上形成一个外切圆半径为r的正五边形，其中一颗（$aa$）在外心与辉夜的连线上。五边形的外心（外切圆圆心）绕着辉夜以R的半径v的速度顺时针旋转（不自转）。五颗龙玉每t秒钟发射一圈弹幕，一圈 $k$ 个子弹。$aa$ 发出的子弹中有一个子弹是背对辉夜的方向的，其他的龙玉发出的子弹方向与 $aa$ 相同，我们可以认为子弹是无限快的。作为一个 neet，辉夜不能让子弹打到自己。

永琳对此表示很担心，于是请你写一个程序判断辉夜的安全。

下面是图示：

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

注：红色为龙玉旋转轨迹
p.s.感谢几何画板为本题提供技术支持；感谢上海爱丽丝幻乐团提供信仰加成

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

对于每组数据，共一行四个浮点数和一个整数 $r,R,v,t,k$，含义如题面所示。

outputFormat: 每组数据一行，安全输出 `yes`，危险输出 `no`。


title: 【模板】矩阵求逆

description: 求一个 $N\times N$ 的矩阵的逆矩阵。答案对 ${10}^9+7$ 取模。

inputFormat:
第一行有一个整数 $N$，代表矩阵的大小；

接下来 $N$ 行，每行 $N$ 个整数，其中第 $i$ 行第 $j$ 列的数代表矩阵中的元素 $a_{i j}$。

outputFormat:
若矩阵可逆，则输出 $N$ 行，每行 $N$ 个整数，其中第 $i$ 行第 $j$ 列的数代表逆矩阵中的元素 $b_{i j}$，答案对 ${10}^9+7$ 取模；

否则只输出一行 `No Solution`。


title: JerryC Loves Driving

background: JerryC最近迷上了狂野飙车！！！

description:
众所周知，JerryC是一位疯狂的Female。他最近买了一台跑车~~(但是却没有驾驶证)~~，所以他就只能到一个偏僻的地方练习开车。

当然，JerryC是不可能正常开车的。她首先决定要开$(B-A+1)$段路程的车，第$i$段路程的速度都是从$1$开始加速的。每一秒会加上$1$的单位速度。当速度加到$(i+A-1)$的时候，JerryC就会把速度降为$1$，然后开始下一段路程。

对于第$i$段路程的第$j$秒，JerryC获得的愉悦值为$\lfloor \frac{i+A-1}{j} \rfloor * (-1)^j$。(反正JerryC就是不喜欢奇数。)

现在请你求出JerryC最后的总愉悦值。

P.s. ：

如果上面的东西没有看懂，那么简单版就是这个意思：

给出A，B，求出下面式子的值。

$$\sum_{i=A}^B \sum_{j=1}^{i}\lfloor \frac{i}{j} \rfloor * (-1)^j$$

inputFormat: 一行，两个正整数A，B

outputFormat: 一行，一个整数表示最终的愉悦值。

hint:
对于50%的数据：$1 \leqslant A \leqslant B \leqslant 5*10^3$

对于70%的数据：$1 \leqslant A \leqslant B \leqslant 5*10^4$

对于100%的数据：$1 \leqslant A \leqslant B \leqslant 2*10^7$


title: 跑酷

background:
[赛时答疑](https://www.luogu.org/discuss/show/80694)

跑酷这东西，还是得看人品的（比如 zm 和 mt）…

description:
在 Minecraft 中，跑酷可以算得上是一门技术了，Steve 现在想在一个跑道上（二维）进行跑酷。但是 Steve 不知道能不能跑到终点，于是他便查询了 MC Wiki，来获得更多的知识。内容具体如下：

### 生命值

1. 我们规定每个玩家的初始生命为 $20$ 点。
2. 掉落伤害的计算:
   - 如果玩家的高度为 $3$ 格或以下，免除此伤害。
   - 如果玩家的高度为 $4$ 格或以上，便会造成 $x-3$ 点伤害，$x$ 为摔落的高度。
   - 这里的高度均指相对高度，即当前方块与下一个方块之间的高度差。
3. 掉落伤害降低的情况：见特殊方块。

4. 当生命值为 $0$ 的时候，视为不能到达终点。

### 跑酷

1. 对于站在一个方块上的玩家来说，玩家最多可以往前面跳 $3$ 格并且可以往上跳一个格子。
2. 对于站在一个方块上的玩家来说，玩家最多也可以往前跳 $4$ 格，但是不能向上跳一个格子。
3. 为了计算方便，我们规定下落时玩家不会移动，也就是说，如果下一个方块比现在方块的高度要低的话，我们只能正好下落到下一个方块的位置。
4. 默认终点为最后一个方块。

### 特殊方块

1. **粘液块**：会使你跳跃至 $60\%$ 坠落距离的高度，如果有小数，我们向下取整。当你达到最高点的时候，只能往前再移动一格。当然，如果落在前方的方块上，同样要受到摔落伤害。你也可以按住 Shift 键来免除反弹。我们认为在粘液块上面进行跑酷不受减速的限制。
2. **蜘蛛网**：下落时会让你免除伤害。我们也认为玩家在蜘蛛网上跑酷不受减速的限制。

Steve 找到了你，让你帮他去解决这个问题。判断 Steve 能不能到达终点。

- 如果能到达终点，输出最少的跳跃次数；
- 如果不能到达终点，请输出：`qwq`。

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

从第二行开始，下面连续 $n$ 行，表示有 $n$ 个方块。每个方块都有它的属性：横坐标，高度和是否为特殊方块。（普通方块输入为 $\verb!P!$，粘液块为 $\verb!N!$，蜘蛛网为 $\verb!Z!$）

outputFormat:
如果能到达终点，输出一个整数，表示最少的跳跃次数；
如果不能到达终点，请输出 `qwq`。

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

数据保证输入的横坐标单调递增。每一个横坐标只有一格方块。

数据保证不会在相邻的横坐标中间出现两个特殊方块。

对于方块而言，默认是都没有浮空方块的存在；也就是说，所有方块下面都会有支撑柱。

为了方便，不能先跳跃再下落。也就是说，只能下落到前面一格的方块。

对于 $30\%$ 的数据 $n\le 10$；
对于另外 $20\%$ 的数据，保证不存在特殊方块；
对于这前面的 $50\%$ 的数据，保证 Steve 往前跳只能跳四格远或者三格远一格高；
对于 $100\%$ 的数据 $1\le n\le 1000$，$1\le x_{\rm max}\le 10000$，$1\le height\le 1000$。

保证数据有一定梯度。


title: Jerry Loves Lines

background: Jerry很喜欢在纸上面画直线呢..

description:
Jerry在纸上面画上了$N$条直线,每一条直线都可以用$y=k_ix+b_i$来表示.现在Jerry想知道对于$M$条可以表示为$X=A_j$的直线,从下往上数排名第$K$的交点的$y$坐标是多少.

如有$x$条直线与一条$X=A_j$的直线交于同一点,算$x$个点.

inputFormat:
第一行三个正整数$N$,$M$,$K$

接下来$N$行,每一行两个非零整数$k_i$和$b_i$描述了一条直线.

接下来$M$行,每行一个整数$A_j$表示一个询问.

outputFormat: $M$行,每一行一个整数表示答案.

hint:
对于$30\%$的数据: $1 \leqslant N,M \leqslant 2000$

对于$100\%$的数据: $1 \leqslant N \leqslant 2000, 1 \leqslant M \leqslant 5*10^5$

其他所有读入的数全在int范围内,且保证$1 \leqslant K \leqslant N$.

温馨提示:如果对自己的做法的常数感到不放心,请吸入氧气..(食用O2优化)如果有着充足自信,尽管放手浪..

$\color{white}{\text{int*int会爆int!!!}}$


title: yyf hates ganhuodong

background: 非酋yyf知道自己太非了，于是他开始爆肝活动。yyf终于成为了一名肝帝，但他还是想尽量节省 $\mathrm{loveca}$ 的花费，不然的话如果花了太多 $\mathrm{loveca}$，yyf会心疼的。

description:
给你如下 $11$ 个正整数：

$a$：完成一首歌曲所能获得的活动$\mathrm{pt}$

$b$：完成一首歌曲所需的 $\mathrm{LP}$

$c$：你开始肝活动时的 $\mathrm{LP}$ 上限

$d$：你开始肝活动时的 $\mathrm{LP}$

$e$：你开始肝活动时的经验值上限

$f$：你开始肝活动时的经验值

$g$：打一首歌能获得的经验值

$h$：升一级增加的 $\mathrm{LP}$ 上限

$k$：升一级增加的经验值上限

$x$：离活动结束的剩余时间（小时）

$y$：你的目标活动$\mathrm{pt}$

假设yyf打歌不需要花费时间，每打一首歌需要花费一定的 $\mathrm{LP}$ 来获取一定的活动$\mathrm{pt}$ 以及一定的经验值。yyf的初始活动$\mathrm{pt}$ 为 $0$

$\mathrm{LP}$ 每小时自动恢复 $1$ 点，$\mathrm{LP}$ 达到上限后不会自动恢复（本题不需考虑这种情况），但可以通过后文所述方式超过上限。

经验值达到上限后会升级，升级时会增加 $\mathrm{LP}$上限并恢复“新的 $\mathrm{LP}$上限”（增加后的）点 $\mathrm{LP}$，恢复后的 $\mathrm{LP}$ 可以超过 $\mathrm{LP}$ 上限，且溢出的经验值会计入下一次升级，下一次升级所需要的经验值（经验值上限）会增加。

可以随时耗费一个 $\mathrm{loveca}$ 来获得当前 $\mathrm{LP}$上限点 $\mathrm{LP}$（可以超过上限）。

你的目标是获得大于等于 $y$ 的活动$\mathrm{pt}$，请求出最少需要耗费多少个 $\mathrm{loveca}$。

形式化地说，你初始的 $\mathrm{LP}$ 可以视作 $d+x$，你有两种操作：

1. 设你操作前的经验值为 $\mathrm{exp}$，$\mathrm{LP}$上限为 $\mathrm{LPmax}$，$\mathrm{LP}$ 值为 $l$（当且仅当 $l \ge b$ 时能进行操作 $1$ ），经验值上限为 $\mathrm{EXPmax}$，则在你操作后活动$\mathrm{pt}$ 加上 $a$ 。
- 若 $\mathrm{exp+g \ge EXPmax}$，则你的剩余 $\mathrm{LP}$值为 $l-b+\mathrm{LPmax}+h$，经验值为
 $\mathrm{(exp+g)\bmod EXPmax}$，$\mathrm{LP}$上限加上 $h$，经验值上限加上 $k$
- 否则你的剩余 $\mathrm{LP}$值为 $l-b$，经验值为 $\mathrm{exp+g}$

2. 设你操作前的 $\mathrm{LP}$上限为 $\mathrm{LPmax}$，$\mathrm{LP}$值为 $l$ ，则你操作后的剩余 $\mathrm{LP}$值为 $\mathrm{LPmax}+l$

你的目标为使你的活动$\mathrm{pt}$ 大于等于 $y$ ，请求出最少需要的操作 $2$ 数量

## 由于打歌不计时间可以在活动结束的瞬间打任意次歌，即进行任意次操作1，也就是初始LP可以视作d+x

inputFormat: 共一行，为上述所有共 $11$ 个正整数，含义如上所述

outputFormat: 一个正整数，代表最少需要耗费的 $\mathrm{loveca}$ 数量


title: yyf hates choukapai

background: 非酋yyf总是抽不到自己想要的卡，因此还十分讨厌抽卡。但玩sif不可能不抽卡，于是他去请教了一下欧皇dew。dew告诉了他关于抽卡的秘密，然而yyf还是不知道如何让自己欧气尽量地大，于是他找到了你。

description:
dew告诉yyf，人在抽每张卡时欧气值都是固定的，第 $i$ 张卡的欧气值为 $a_i$ ，而在连抽时，欧气值等于第一张卡的欧气值。

“每次抽卡的欧气之和”指每次单抽的欧气之和加上每次连抽的欧气之和，一次连抽的欧气不加权，只计算一次

yyf想 $c$ 连抽（连续抽 $c$ 张卡） $n$ 次，单抽 $m$ 次，因为一直单抽太累，**yyf不想连续单抽超过 $d$ 次（可以连续单抽恰好 $d$ 次）**。共有 $c*n+m$ 张卡，抽卡的顺序不能改变，每张卡都必须且只能抽一次，只能改变哪几张卡连抽、哪几张卡单抽。那么yyf每次抽卡的欧气之和最多能达到多少，又如何实现呢？

inputFormat:
第 $1$ 行 $4$ 个正整数 $n\ m\ c\ d$

第 $2$ 行 $c*n+m$ 个正整数，其中第 $i$ 个正整数 $a_i$ 代表第 $i$ 张卡的欧气值

outputFormat:
第 $1$ 行一个正整数代表yyf每次抽卡的欧气之和的最大值

第 $2$ 行 $n$ 个正整数代表每次连抽的第一张卡的编号，如果有多种方案满足要求任意输出一种 （如果不会输出方案也请在第二行随意输出 $n$ 个整数，否则可能 $0$ 分）

方案请升序输出

hint:
$20\%$的数据有$1 \le n \le 5$，$1 \le m \le 5$，$2 \le c \le 5$

$50\%$的数据有$1 \le n \le 40$，$1 \le m \le 200$，$2 \le c \le 20$

另有$20\%$的数据有$d=m$

$100\%$的数据有$1 \le n \le 40$，$1 \le m \le 80000$，$2 \le c \le 3000$，$1 \le a_i \le 10000$，$1 \le d \le m$，$d*(n+1) \ge m$

共 $10$ 个测试点，每个测试点答案错误 $0$ 分，答案正确方案错误 $6$ 分，答案正确方案正确 $10$ 分。

样例解释：输出的方案就是样例解释了QAQ

样例一：单抽 $1$ ，连抽 $2$~$4$，连抽 $5$~$7$，单抽 $8$，连抽 $9$~$11$，单抽 $12$，欧气值总和为 $2+7+5+8+5+9=36$

样例二：单抽 $1$ ，连抽 $2$~$3$，单抽 $4$，单抽 $5$，连抽 $6$~$7$，单抽 $8$，单抽 $9$，欧气值总和为 $7+3+7+7+5+10+2=41$

可以证明在满足条件的情况下上述两种方案是欧气值总和最大的


title: yyf hates dagequ

background:
非酋yyf在dew的指点下抽到了不错的卡，但他还是太非了，对于随机触发的技能，他总是无法触发。yyf想知道自己究竟有多非，所以他请你来计算他的期望得分，与自己的得分来比较。

## 此题已放宽精度限制并显示错误答案和正确答案，请不要以此面向数据

description:
给你一些卡牌的技能，技能分为$2$种类型：
1. 加分，每连击$c$次有$p\%$的概率加$s$分
2. 改判，每连击$c$次有$p\%$的概率触发强判定效果，持续$t$个节奏图标（设连击数为$c$的倍数时为第$i$个节奏图标，则强判定效果在第$[i+1,i+t]$个节奏图标被触发）

这些技能在连击数为$c$的倍数且连击数不为$0$时有概率触发，多个技能可以同时触发

其中，加分技能有 $\mathrm{score}$ 个，改判技能有 $\mathrm{judge}$ 个

再给你$n$个节奏图标（yyf是按给出的顺序击打的）yyf击打的原始（相对于“强判定效果”修正后）结果，分为$2$，$1$，$0$三种

在“强判定效果”的持续期间内所有的击打结果$1$会视作击打结果$2$，击打结果$0$仍视作击打结果$0$，击打结果$2$仍视作击打结果$2$ 。下文中的“击打结果”若无说明均指修正后的击打结果。

“连击数”的定义为到目前为止连续的击打结果为$2$的次数（若这次的击打结果为$2$则这次击打也算入当前的连击数，否则当前的连击数为$0$）

多个“强判定效果”可以重叠，但持续时间不会叠加（设当前“强判定效果”剩余时间为 $t_1$，此时同时触发两个“强判定效果”，持续时间分别为 $t_2$ 和 $t_3$ ，则下一次击打时的“强判定效果”剩余时间为 $\max(t_1-1,t_2,t_3)$）。

一次击打的得分为这次的击打结果乘以当前的连击数加一。即：设当前的击打结果为 $x$ ，当前的连击数为 $\mathrm{combo}$ ，则这次击打的得分为 $\mathrm{x*(combo+1)}$

最终得分为每次（共$n$次）击打的得分之和加上加分技能的加分之和

请求出yyf这次打歌的期望得分

inputFormat:
第一行三个非负整数 $\mathrm{n\ score\ judge}$

下面的 $\mathrm{score}$ 行，每行三个正整数 $c\ p\ s$，代表一个加分技能

下面的 $\mathrm{judge}$ 行，每行三个正整数 $c\ p\ t$，代表一个改判技能

最后一行 $n$ 个整数，每个整数都∈$[0,2]$，第 $i$ 个整数代表第 $i$ 次击打的原始结果

outputFormat: 共一行一个实数代表yyf的期望得分，与答案的相对误差在 $10^{-5}$ 内算对


title: ycz的妹子

background: ycz 有很多很多的妹子（ycz：瞎说）

description:
机房神犇 ycz 有 $n$ 个青梅竹马，她们分别住在 $1~n$ 号城市中。小时候的她们美丽可爱，但是由于女大十八变，有些妹子的颜值发生了变化，但是十分重感情的 ycz 神犇不忍心抛弃她们，于是记录下来了她们颜值变化的值，我们用 $C, x, y$ 表示第 $x$ 个城市的妹子的颜值下降了 $y$ 。长大之后的 ycz 非常有魅力，有许多妹子被 ycz 迷得神魂颠倒，我们用$I, x, y$ 表示第 $x$ 个城市有一个妹子喜欢上了 ycz ，她的颜值为 $y$ （ $y$ 有可能是负数，但是 ycz 来者不拒）。但在中途有一些妹子和 ycz 吵架了，于是就分手了，我们用 $D, x$ 表示**第 $x$ 个妹子**和 ycz 分手了。

最近神犇 ycz 要去全国各地找他的妹子们，为了方便计算，我们珂以把 ycz 的妹子所在的城市当作是一条直线，并且挨在一起。神犇 ycz 由于忙于和他的妹子们联系此时已经很累了，于是交给你一个这样的任务：他想知道他在某个时间去找他的所有妹子们珂以获得多大的愉悦度，这个愉悦度为他找的妹子的颜值数，你要做的就是求出这个愉悦度之和（注意长大后妹子们的颜值可能为负数/滑稽）。

注意：每个城市只允许有一个妹子，也就是说后来喜欢上 ycz 的妹子会赶走之前这个城市喜欢 ycz 的妹子~~（一城不容二女）~~。

UPD:

青梅竹马都是喜欢 ycz 的。

分手的第 $x$ 个妹子不是第 $x$ 城市的妹子，是指从前往后数第 $x$ 个有妹子的城市的妹子。

青梅竹马长大后就是妹子。

修改的值 $y$ 不为负数，但是颜值减去之后可能为负数。

inputFormat:
ycz 有 $5 \times 10^5$ 座城市，开始时，前 $n$ 座城市各有一个妹子，第 $i$ 座城市妹子初始的颜值为 $a_i$。

有 $m$ 次以下四种操作。

 - `C x y` 第 $x$ 座城市的妹子颜值减少 $y$
 - `I x y` 第 $x$ 座城市出现了一个颜值为 $y$ 的妹子，如果在此之前，第 $x$ 座城市已经有妹子，则之前的妹子被驱赶。
 - `D x` 第 $x$ 个有妹子的城市 中的妹子与 ycz 分手
 - `Q` ycz 想知道他所有妹子的颜值总和是多少

outputFormat: 对于每一个$Q$输出一个整数


title: [BalticOI 2016 Day2] 城市

description:
在 Byteland 有 $n$ 个城市，并且其中有 $k$ 个国王经常来访的主要城市。

其中有 $m$ 条道路，每条道路连接两个城市。然而不幸的是，这些道路的环境极差使得国王无法全速驶过。

对于每条道路，翻修的成本是已知的。你的任务是选择性的翻修道路使得 $k$ 个主要城市都可以经过翻修后的道路互相连通，且总成本尽量小。

inputFormat:
第一行，三个整数 $n,k$ 和 $m$，分别表示城市的个数，主要城市的个数和道路的个数。城市的编号分别为 $1,2,\dots,n$。

第二行，$k$ 个整数，表示主要城市。

接下来 $m$ 行，每行三个整数 $a,b$ 和 $c$，表示有一条双向道路从城市 $a$ 连接到城市 $b$，且翻修成本为 $c$。

outputFormat: 输出一行，表示满足以上条件的最小的总成本。


title: [BalticOI 2016 Day2] 交换

description:
给定一个包含 $n$ 个数的序列 $x_1,x_2,\dots,x_n$。$1,2,\dots,n$ 每个数在序列中刚好出现一次。
你可以通过交换修改这个序列。你需要进行连续的 $n-1$ 轮操作，编号 $k=2,3,\dots,n$，第 $k$ 轮你可以选择交换 $x_k$ 和 $x_{\lfloor k/2\rfloor}$ 或是什么都不做。
如果存在一个数 $j(1 \leq j \leq n)$，使得对于所有 $k < j$ 且 $a_j < b_j,$ $a_k = b_k$ 成立，那么序列 $a_1\dots a_n$ 「**字典序小于**」序列 $b_1\dots b_n$。
你能得到的字典序最小的序列是什么？

inputFormat:
第一行，一个整数 $n$。
第二行，$n$ 个整数，表示序列 $x_1,x_2,\dots,x_n$。

outputFormat: 输出 $n$ 个整数，表示你能得到的字典序最小的序列。


title: [BalkanOI2018] Election

description:
**翻译自 [BalkanOI 2018](http://boi2018.ro) Day1 T1「[Election](http://boi2018.ro/assets/Tasks/BOI/Day_1/election/elections_en.pdf)」**

有一个长度为 $N$ 的字符串 $S[1\dots N]$，它仅由 `C` 和 `T` 两种字母组成。
现在有 $Q$ 个查询，每个查询包含两个整数 $L$ 和 $R$，表示：设新字符串 $S'=S[L\dots R]$，至少在 $S'$ 中要删除多少个字符，才能保证：对于 $S'$ 的每一个前缀和后缀，其 `C` 的数量都不小于 `T` 的数量。

inputFormat:
第一行有一个整数 $N$。
第二行有一个长度为 $N$ 的字符串 $S$。
第三行有一个整数 $Q$。
在接下来的 $Q$ 行中，每行有两个整数 $L$ 和 $R$，表示一组查询。

outputFormat: 对于每组查询输出一行，表示至少在 $S'$ 中要删除多少个字符，才能保证题面要求。

hint:
#### 样例解释
查询 1：`CCCTTTTTTCC`；
查询 2：`TTTTTT`；
查询 3：`CCCTTT`。

子任务 #1（28 分）：$1 ≤ N, Q ≤ 2000$；
子任务 #2（54 分）：$1 ≤ N, Q ≤ 7\times 10^4$；
子任务 #3（18 分）： $1 ≤ N, Q ≤ 5\times 10^5$。

感谢 Planet6174 提供的翻译


title: [BalkanOI2018] Minmaxtree

description:
**翻译自 [BalkanOI 2018](http://boi2018.ro) Day1 T3「[Minmaxtree](http://boi2018.ro/assets/Tasks/BOI/Day_1/minmaxtree/minmaxtree_en.pdf)」**

有一棵有 $N$ 个结点的无权树，结点分别编号为 $1\dots N$。现在要给每条边赋一个权值，使之变为一棵带权树。这棵带权树满足 $K$ 个条件，条件分为两类：
1. $\ \texttt{M }x\ y\ z\ \ $ 从结点 $x$ 到结点 $y$ 的链上最大的边权为 $z$；
2. $\ \texttt{m }x\ y\ z\ \ $ 从结点 $x$ 到结点 $y$ 的链上最小的边权为 $z$。

**保证这 $K$ 组条件的 $z$ 互不相同。**

请构造出这棵树，并输出每条边的边权。

inputFormat:
第一行有一个整数 $N$。
在接下来的 $N-1$ 行中，每行两个整数，表示一条边连接的两个结点。
第 $N+1$ 行有一个整数 $K$。
在接下来的 $K$ 行中，每行开头有一个字母，字母为 $\texttt{M}$ 或 $\texttt{m}$，接下来有三个整数 $x, y, z$。

outputFormat: 输出 $n-1$ 行，每行三个整数 $x, y, v$，用空格分隔，表示带权树的一条带权边。

hint:
子任务 #1（7 分）：$1 ≤ N, z ≤ 1000$；
子任务 #2（22 分）：只有条件 1，没有条件 2。
子任务 #3（29 分）：所有条件 1 中给出的 $x$ 到 $y$ 的链互不相交；所有条件 2 中给出的 $x$ 到 $y$ 的链也互不相交。
子任务 #4（42 分）：没有其他限制。
对于所有数据，$1 ≤ N, K ≤ 70000$，$0 ≤ z ≤ 10^9$。

感谢 Planet6174 提供的翻译


title: [BalkanOI2018] Parentrises

description:
**翻译自 [BalkanOI 2018](http://boi2018.ro) Day2 T1「[Parentrises](http://boi2018.ro/assets/Tasks/BOI/Day_2/parentrises/parentrises_en.pdf)」**

**「括号串」**是一个仅由 `(` 和 `)` 构成的字符串。如果在括号串中插入一些 `1` 和 `+` 可以将其转化为正确的表达式，该字符串就是一个**「良括号串」**。例如，`(())` 和 `(())` 是良括号串，而 `)(` 和 `(` 不是。空字符串可视为良括号串。（就是你们学 Catalan 数时学的那个啊）
将一个**括号串**（不是良括号串）的每个括号都涂成红绿蓝三种颜色之一，如果有一种方案同时满足：
+ 忽略该串的所有蓝色括号后它是**良括号串**；
+ 忽略该串的所有红色括号后它是良括号串；

该串就是 **RGB 可读**的。

你会接到两类任务之一。任务类型用一个整数 $P$ 表示，$P=1$ 或 $2$。

* $P=1$：你会接到 $T$ 组询问，每组询问包含一个括号串，试问该串是否 RGB 可读，如果是，请输出一种染色方案，如果否请输出 `impossible`；
* $P=2$：你会接到 $T$ 组询问，每组询问包含一个数 $N$，试求：有多少个长度为 $N$ 的 RGB 可读的良括号串。输出答案模 $(10^9+7)$ 的结果。

inputFormat:
第一行有一个整数 $P$。
第二行有一个整数 $T$。
+ 如果 $P=1$，在接下来的 $T$ 行中，每行有一个括号串，表示询问。
+ 如果 $P=2$，在接下来的 $T$ 行中，每行有一个数 $N$，表示询问。

outputFormat:
如果 $P=1$，对于每组询问，
+ 如果该串是 RGB 可读的，请输出一种染色方案；
+ 如果该串不是 RGB 可读的，请输出 `impossible`；

如果 $P=2$，对于每组询问，请输出长度为 $N$ 的 RGB 可读的良括号串的个数模 $(10^9+7)$ 的结果。

hint:
样例 $1$ 解释：

对于查询 1，忽略原串的所有蓝色括号后它变为 `()()`；忽略原串的所有红色括号后它也变为 `()()`。
对于查询 2，忽略原串的所有蓝色括号后它变为 `()`；忽略原串的所有红色括号后它变为 `()()`。

$P = 1$：
设 $L$ 为字符串总长。
* 子任务 #1（5 分）：$1 ≤ T ≤ 5,$ $1 ≤ len(S) ≤ 13$。
* 子任务 #2（11 分）：$1 ≤ L ≤ 100$。
* 子任务 #3（6 分）：$1 ≤ L ≤ 1000$。
* 子任务 #4（28 分）：$1 ≤ L ≤ 10^6$。

$P = 2$：
* 子任务 #5（6 分）：$1 ≤ N, T ≤ 15$。
* 子任务 #6（16 分）：$1 ≤ N, T ≤ 30$。
* 子任务 #7（28 分）：$1 ≤ N, T ≤ 300$。

感谢 Planet6174 提供的翻译