title: [GDCPC2023] Computational Geometry

description:
Given a convex polygon $P$ with $n$ vertices, you need to choose two vertices of $P$, so that the line connecting the two vertices will split $P$ into two smaller polygons $Q$ and $R$, both with positive area.

Let $d(Q)$ be the diameter of polygon $Q$ and $d(R)$ be the diameter of polygon $R$, calculate the minimum value of $(d(Q))^2 + (d(R))^2$.

Recall that the diameter of a polygon is the maximum distance between two points inside or on the border of the polygon.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($4 \le n \le 5 \times 10^3$) indicating the number of vertices of the convex polygon $P$.

For the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 10^9$) indicating the $i$-th vertex of the convex polygon $P$. Vertices are given in counter-clockwise order. It's guaranteed that the area of the convex polygon is positive, and there are no two vertices with the same coordinate. It's possible that three vertices lie on the same line.

It's guaranteed that the sum of $n$ of all test cases will not exceed $5 \times 10^3$.

outputFormat: For each test case output one line containing one integer indicating the answer.

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

给定一个有 $n$ 个顶点的凸多边形 $P$，您需要选择 $P$ 的两个顶点，并用一条同时穿过这两个顶点的直线，将 $P$ 分成两个面积均为正数的小多边形 $Q$ 和 $R$。

记 $d(Q)$ 表示多边形 $Q$ 的直径，$d(R)$ 表示多边形 $R$ 的直径，求 $(d(Q))^2 + (d(R))^2$ 的最小值。

请回忆：一个多边形的直径，指的是该多边形内部或边界上任意两点之间的距离的最大值。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$4 \le n \le 5 \times 10^3$）表示凸多边形 $P$ 的顶点数量。

对于接下来 $n$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$0 \le x_i, y_i \le 10^9$），表示凸多边形 $P$ 的第 $i$ 个顶点。顶点按逆时针顺序给出。保证该凸多边形面积为正，且没有顶点会重合。可能存在三个顶点位于同一条直线上的情况。

保证所有数据 $n$ 之和不超过 $5 \times 10^3$。

**【输出格式】**

每组数据输出一行一个整数表示答案。

**【样例解释】**

第一组样例数据如下图所示。小多边形的直径用红色虚线标出。事实上，顶点 $(1, 0)$ 和 $(1, 1)$ 是这一组数据中唯一能选择的一对顶点。您不能选择顶点 $(0, 0)$ 和 $(2, 0)$，或顶点 $(0, 0)$ 和 $(1, 1)$，因为它们无法将 $P$ 分成两个面积均为正数的小多边形。

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

第二组样例数据如下图所示。小多边形的直径用红色虚线标出。

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

hint:
The first sample test case is shown as follows. The diameter of smaller polygons are marked by red dashed segments. In fact, $(1, 0)$ and $(1, 1)$ are the only pair of vertices we can choose in this test case. You can't choose $(0, 0)$ and $(2, 0)$, or $(0, 0)$ and $(1, 1)$, because they can't split $P$ into two smaller polygons both with positive area.

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

The second sample test case is shown as follows. The diameter of smaller polygons are marked by red dashed segments.

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


title: [Opoi 2024] 数据转换

type: P

background:
![](data:image/jpeg;base64,[encoded data, 5872 characters])

![](https://tse2-mm.cn.bing.net/th/id/OIP-C.ojcWO_62WQhtFFaZSdmbgAHaEo?w=244&h=180&c=7&r=0&o=5&pid=1.7)

Arrda 家里面有很多五花八门的用电器和数据线，而且很多用电器的插头种类都不一样，这导致每次 Arrda 想要共享两个用电器的数据时都要一半天用来买到合适的数据线，而且有的时候数据线很贵！

于是 Arrda 想让你求出花钱最少的数据转换方案。

description:
Arrda 家中有 $n$ 类，$2n$ 种数据线接头，每一类插头有 $2$ 种不同接头，种类分别为 $i$ 和 $n+i$，**有且只有同一类的不同接头可以互相连接（你可以理解为 $i$ 是凸出的接头，$n + i$ 是凹的接头，可以连接可以理解为插上）**。

商城里售卖着 $m$ 种双向数据线，每根双向数据线两端各有一个接头，种类分别为为 $u_i,v_i$。同时，第 $i$ 种双向数据线有一个购买价格 $w_i$，每种数据线可以购买无限条。

Arrda 想要交换两个用电器的数据，其中两个用电器的接头种类编号为 $S,T$，求能使这两个用电器能直接或由若干条数据线相连的最小总价格（毕竟买数据线需要钱），如果无解，输出 `I have no idea how to solve it.`，注意，**两个用电器的接口不能直接连接数据线，因为它们在用电器上，而非数据线两端！**

inputFormat:
第一行两个整数 $n,m$，意义见题面。

接下来 $m$ 行，每行三个整数 $u_i,v_i,w_i$。

接下来一行两个整数 $S,T$。

outputFormat:
一个非负整数表示能使这两个用电器能直接或由若干条数据线相连的最小总价格。

若无解，请输出 `I have no idea how to solve it.`。

hint:
### 样例 1 解释：

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

```
1=5->6=2->3=7->8=4
```

可以证明，没有总代价更小的方案。

### 样例 4 解释

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

```
1=6->8=3->5=10->3=8->6=1->9=4->7=2
```
`4->6` 有两种数据线，我们选择代价为 $182080546$ 的那一根，因为其代价更小。

可以证明，没有总代价更小的方案。

### 数据范围

对于 $100\%$ 的数据，$1\le n,m \le 10^5$，$1\le u_i,v_i,s,t \le 2 \times n$，$1\le w_i \le 10^9$。


title: [SDCPC2023] Not Another Path Query Problem

background: > What age is it that you are still solving traditional path query problems?

description:
After reading the paper *Distributed Exact Shortest Paths in Sublinear Time*, you have learned how to solve the distributed single-source shortest paths problem in $\mathcal{O}(D^{1/3} \cdot (n \log n)^{2/3})$. To give your knowledge good practice, Little Cyan Fish prepared the following practice task for you.

Little Cyan Fish has a graph consisting of $n$ vertices and $m$ bidirectional edges. The vertices are numbered from $1$ to $n$. The $i$-th edge connects vertex $u_i$ to vertex $v_i$ and is assigned a weight $w_i$.

For any path in the graph between two vertices $u$ and $v$, let's define the value of the path as the bitwise AND of the weights of all the edges in the path.

As a fan of high-value paths, Little Cyan Fish has set a constant threshold $V$. Little Cyan Fish loves a path if and only if its value is at least $V$.

Little Cyan Fish will now ask you $q$ queries, where the $i$-th query can be represented as a pair of integers $(u_i, v_i)$. For each query, your task is to determine if there exists a path from vertex $u_i$ to vertex $v_i$ that Little Cyan Fish would love it.

inputFormat:
There is only one test case in each test file.

The first line contains four integers $n$, $m$, $q$ and $V$ ($1 \le n \le 10^5$, $0 \le m \le 5 \times 10^5$, $1 \leq q \leq 5 \times 10^5$, $0 \leq V < 2^{60}$) indicating the number of vertices, the number of edges, the number of queries and the constant threshold.

For the following $m$ lines, the $i$-th line contains three integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i,v_i \le n$, $u_i \ne v_i$, $0 \leq w_i < 2^{60}$), indicating a bidirectional edge between vertex $u_i$ and vertex $v_i$ with the weight $w_i$. There might be multiple edges connecting the same pair of vertices.

For the following $q$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \ne v_i$), indicating a query.

outputFormat: For each query output one line. If there exists a path whose value is at least $V$ between vertex $u_i$ and $v_i$ output `Yes`, otherwise output `No`.

translation:
**【题目背景】**

> 都什么年代了还在做传统路径查询问题？

**【题目描述】**

在阅读《Distributed Exact Shortest Paths in Sublinear Time》这篇论文后，您学会了如何在 $\mathcal{O}(D^{1/3} \cdot (n \log n)^{2/3})$ 的复杂度内解决分布式单源最短路问题。为了测试您是否真的学有所成，小青鱼为您准备了如下问题。

小青鱼有一张包含 $n$ 个节点与 $m$ 条无向边的图，节点编号从 $1$ 到 $n$。第 $i$ 条边连接节点 $u_i$ 和 $v_i$，边权为 $w_i$。

对于任意一条连接节点 $u$ 和 $v$ 的路径，定义路径的价值为路径上所有边的边权进行按位与（bitwise AND）计算的结果。

小青鱼很喜欢高价值的路径，因此他设定了一个固定的阈值 $V$。称小青鱼喜爱一条路径，当且仅当这条路径的价值至少为 $V$。

接下来，小青鱼将会提出 $q$ 次询问，第 $i$ 次询问可以用一对整数 $(u_i, v_i)$ 表示。对于每次询问，您需要判断节点 $u_i$ 到 $v_i$ 是否存在一条小青鱼喜爱的路径。

**【输入格式】**

每个测试文件仅有一组测试数据。

第一行输入四个整数 $n$，$m$，$q$ 和 $V$（$1 \le n \le 10^5$，$0 \le m \le 5 \times 10^5$，$1 \leq q \leq 5 \times 10^5$，$0 \leq V < 2^{60}$）表示图中的节点数以及边数，小青鱼的询问数以及固定阈值。

对于接下来 $m$ 行，第 $i$ 行输入三个整数 $u_i$，$v_i$ 和 $w_i$（$1 \le u_i,v_i \le n$，$u_i \ne v_i$，$0 \leq w_i < 2^{60}$）表示一条连接节点 $u_i$ 和 $v_i$ 的无向边，边权为 $w_i$。两个节点之间可能存在多条边。

对于接下来 $q$ 行，第 $i$ 行输入两个整数 $u_i$ 和 $v_i$（$1 \leq u_i, v_i \leq n$，$u_i \ne v_i$）表示一次询问。

**【输出格式】**

每次询问输出一行。若节点 $u_i$ 和 $v_i$ 之间存在一条价值至少为 $V$ 的路径输出 `Yes`，否则输出 `No`。

**【样例解释】**

接下来我们用 $\&$ 表示按位与计算。

第一组样例数据解释如下。

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

- 对于第一次询问，一条合法的路径为 $1 \to 3 \to 4 \to 5 \to 6$，其价值为 $7 \,\&\, 14 \,\&\, 7 \,\&\, 6 = 6 \ge 5$。
- 对于第三次询问，一条合法的路径为 $7 \to 3 \to 4 \to 5 \to 6$，其价值为 $15 \,\&\, 14 \,\&\, 7 \,\&\, 6  = 6 \ge 5$。
- 对于第四次询问，因为节点 $1$ 与 $8$ 之间不存在任何路径，因此答案为 `No`。

对于第二组样例数据仅有的一次询问，可以考虑由第 $2$ 和第 $4$ 条边组成的路径，其价值为 $5 \,\&\, 6 = 4 \ge 4$。

hint:
We now use $\&$ to represent the bitwise AND operation.

The first sample test case is shown as follows.

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

- For the first query, a valid path is $1 \to 3 \to 4 \to 5 \to 6$, whose value is $7 \,\&\, 14 \,\&\, 7 \,\&\, 6 = 6 \ge 5$.
- For the third query, a valid path is $7 \to 3 \to 4 \to 5 \to 6$, whose value is $15 \,\&\, 14 \,\&\, 7 \,\&\, 6  = 6 \ge 5$.
- For the fourth query, as there is no path between vertex $1$ and $8$, the answer is `No`.

For the only query of the second sample test case, we can consider the path consisting of the $2$-nd and the $4$-th edge. Its value is $5 \,\&\, 6 = 4 \ge 4$.


title: [SDCPC2023] Puzzle: Sashigane

description:
Given a grid with $n$ rows and $n$ columns, there is exactly one black cell in the grid and all other cells are white. Let $(i, j)$ be the cell on the $i$-th row and the $j$-th column, this black cell is located at $(b_i, b_j)$.

You need to cover all white cells with some L-shapes, so that each white cell is covered by exactly one L-shape and the only black cell is not covered by any L-shape. L-shapes must not exceed the boundary of the grid.

More formally, an L-shape in the grid is uniquely determined by four integers $(r, c, h, w)$, where $(r, c)$ determines the turning point of the L-shape, and $h$ and $w$ determine the direction and lengths of the two arms of the L-shape. The four integers must satisfy $1 \le r, c \le n$, $1 \le r + h \le n$, $1 \le c + w \le n$, $h \ne 0$, $w \ne 0$.

- If $h < 0$, then all cells $(i, c)$ satisfying $r + h \le i \le r$ belong to this L-shape; Otherwise if $h > 0$, all cells $(i, c)$ satisfying $r \le i \le r + h$ belong to this L-shape.
- If $w < 0$, then all cells $(r, j)$ satisfying $c + w \le j \le c$ belong to this L-shape; Otherwise if $w > 0$, all cells $(r, j)$ satisfying $c \le j \le c + w$ belong to this L-shape.

The following image illustrates some L-shapes.

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

inputFormat:
There is only one test case in each test file.

The first line contains three integers $n$, $b_i$ and $b_j$ ($1 \le n \le 10^3$, $1 \le b_i, b_j \le n$) indicating the size of the grid and the position of the black cell.

outputFormat:
If a valid answer exists first output `Yes` in the first line, then in the second line output an integer $k$ ($0 \leq k \leq \frac{n^2-1}{3}$) indicating the number of L-shapes to cover white cells. Then output $k$ lines where the $i$-th line contains four integers $r_i$, $c_i$, $h_i$, $w_i$ separated by a space indicating that the $i$-th L-shape is uniquely determined by $(r_i, c_i, h_i, w_i)$. If there are multiple valid answers you can print any of them.

If there is no valid answer, just output `No` in one line.

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

给定一个 $n$ 行 $n$ 列的网格，网格中包含恰好一个黑色方格，其余方格均为白色。令 $(i, j)$ 表示位于第 $i$ 行第 $j$ 列的格子，这个黑色方格位于 $(b_i, b_j)$。

您需要用若干 L 形覆盖所有白色格子，使得每个白色格子都恰好被一个 L 形所覆盖，同时唯一的黑色方格不能被任何 L 形覆盖。L 形不能超过网格的边界。

更正式地，网格中的一个 L 形由四个整数 $(r, c, h, w)$ 唯一确定，其中 $(r, c)$ 确定了 L 形的转折点，$h$ 和 $w$ 确定了 L 形两臂的方向和长度。四个整数满足 $1 \le r, c \le n$，$1 \le r + h \le n$，$1 \le c + w \le n$，$h \ne 0$，$w \ne 0$。

- 若 $h < 0$，则所有满足 $r + h \le i \le r$ 的格子 $(i, c)$ 均属于该 L 形；否则若 $h > 0$，则所有满足 $r \le i \le r + h$ 的格子 $(i, c)$ 均属于该 L 形。
- 若 $w < 0$，则所有满足 $c + w \le j \le c$ 的格子 $(r, j)$ 均属于该 L 形；否则若 $w > 0$，则所有满足 $c \le j \le c + w$ 的格子 $(r, j)$ 均属于该 L 形。

下图展示了几种 L 形。

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

**【输入格式】**

每个测试文件仅有一组测试数据。

第一行输入三个整数 $n$，$b_i$，$b_j$（$1 \le n \le 10^3$，$1 \le b_i, b_j \le n$）表示网格的大小以及黑色格子的位置。

**【输出格式】**

如果存在符合要求的覆盖方案，首先输出一行 `Yes`，接下来在第二行输出一个整数 $k$（$0 \leq k \leq \frac{n^2-1}{3}$）表示覆盖白色格子的 L 形数量。接下来输出 $k$ 行，第 $i$ 行输出四个由单个空格分隔的整数 $r_i$，$c_i$，$h_i$ 和 $w_i$，表示第 $i$ 个 L 形由 $(r_i, c_i, h_i, w_i)$ 唯一确定。如果有多种合法答案，您可以输出任意一种。

如果不存在符合要求的覆盖方案，仅需要输出一行 `No`。

**【样例解释】**

第一组样例数据展示如下。

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

hint:
We illustrate the first sample test case as follows.

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


title: [SDCPC2023] Computational Geometry

description:
Given a convex polygon $P$ with $n$ vertices, you need to choose three vertices of $P$, denoted as $a$, $b$ and $c$ in counter-clockwise order. There must be exactly $k$ edges from $b$ to $c$ in counter-clockwise order (that is to say, $a$ is not an endpoint of these $k$ edges).

Consider cutting through $P$ with segment $ab$ and $ac$. Let $Q$ be the polygon consisting of $ab$, $ac$ and the $k$ edges between $b$ and $c$. It's easy to see that this polygon has $(k + 2)$ edges.

Find the maximum possible area of $Q$.

Note that $ab$ and $ac$ can overlap with edges of $P$.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $k$ ($3 \le n \le 10^5$, $1 \le k \le n-2$) indicating the number of vertices of the convex polygon $P$ and the number of edges from $b$ to $c$ in counter-clockwise order.

For the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) indicating the $x$ and $y$ coordinate of the $i$-th vertex of the convex polygon $P$. Vertices are given in counter-clockwise order. It's guaranteed that the area of the convex polygon is positive, and there are no two vertices with the same coordinate. It's possible that three vertices lie on the same line.

It's guaranteed that the sum of $n$ of all test cases will not exceed $10^5$.

outputFormat: For each test case output one line containing one real number indicating the maximum possible area of $Q$. Your answer will be considered correct if its relative or absolute error is less than $10^{-9}$.

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

给定一个有 $n$ 个顶点的凸多边形 $P$，您需要选择 $P$ 的三个顶点，按逆时针顺序记为 $a$，$b$ 和 $c$。要求在 $b$ 沿逆时针方向到 $c$ 之间恰有 $k$ 条边（也就是说，$a$ 不是这 $k$ 条边的端点）。

考虑用线段 $ab$ 和 $ac$ 将 $P$ 割开。将由线段 $ab$，$ac$，以及 $b$ 和 $c$ 之间的 $k$ 条边围成的 $(k + 2)$ 边形记作 $Q$。

求 $Q$ 可能的最大面积。

注意，$ab$ 和 $ac$ 可以与 $P$ 的边重合。

**【输入格式】**

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入两个整数 $n$ 和 $k$（$3 \le n \le 10^5$，$1 \le k \le n-2$），表示凸多边形 $P$ 的顶点数和 $b$ 沿逆时针方向到 $c$ 之间的边数。

对于接下来的 $n$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$-10^9 \le x_i, y_i \le 10^9$），表示凸多边形 $P$ 第 $i$ 个顶点的 $x$ 坐标和 $y$ 坐标。顶点按逆时针顺序给出。保证凸多边形的面积为正，且没有顶点会重合。可能存在三个顶点位于同一条直线上的情况。

保证所有数据 $n$ 之和不超过 $10^5$。

**【输出格式】**

每组数据输出一行一个实数表示 $Q$ 的最大可能面积。只要您的答案的相对误差或绝对误差小于$10^{-9}$ 即视为正确。

**【样例解释】**

对于第一组样例数据，$Q$ 就是整个三角形，面积为 $0.5$.

第二和第三组样例数据解释如下。

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

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

hint:
For the first sample test case, $Q$ is the whole triangle. Its area is $0.5$.

The second and third sample test case are shown below.

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

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


title: 「QFOI R1」抱抱

description:
小 R 是一个可爱的女孩子，她希望跟大家抱抱，顺便给大家分蛋糕吃。

蛋糕是一个大小为 $a\times b\times c$ 的长方体，其中每个单位正方体都被赋予了一个坐标 $(x,y,z)$（$1\le x\le a,1\le y\le b,1\le z\le c$）。

共进行 $m$ 次切蛋糕操作，每次按如下三种方式之一切分：

1. 切出 $x\le k$ 的部分分给大家。
2. 切出 $y\le k$ 的部分分给大家。
3. 切出 $z\le k$ 的部分分给大家。

由于她自己也想吃蛋糕，她希望知道在每次切蛋糕后，还剩下多少体积没有分给大家。

inputFormat:
第一行四个整数 $a,b,c,m$，表示蛋糕的大小和切蛋糕次数。

接下来 $m$ 行，每行两个整数 $op,k$，表示进行【题目描述】中的第 $op$ 种操作，参数为 $k$。

outputFormat: $m$ 行，每行一个整数，表示剩余部分体积。

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

第一次切蛋糕，将所有 $x\le 2$ 的部分切掉，剩余的单位正方体有 $(3,1,1),(3,1,2),(3,1,3),(3,2,1),(3,2,2),(3,2,3),(3,3,1),(3,3,2),(3,3,3)$ 共 $9$ 个。

第二次切蛋糕，将所有 $y\le 1$ 的部分切掉，剩余的单位正方体有 $(3,2,1),(3,2,2),(3,2,3),(3,3,1),(3,3,2),(3,3,3)$ 共 $6$ 个。

---

**样例 $2$ 解释**

第四次切蛋糕没有任何作用，因为第二次切蛋糕时 $y\le 654321$ 的部分已经被切掉，此时已经不存在 $y\le 111111$ 的单位正方体。

注意每次操作中的参数 $k$ 是初始时决定的绝对坐标，不会随着操作的进行而改变。

---

**数据范围**

本题共 $20$ 个测试点，每个测试点 $5$ 分。

对于全部数据，保证 $1\le a,b,c\le 10^6$，$1\le m\le 2\times 10^5$，$op\in\{1,2,3\}$，若 $op=1$ 则 $1\le k\le a$，若 $op=2$ 则 $1\le k\le b$，若 $op=3$ 则 $1\le k\le c$。

- 对于测试点 $1\sim 5$：保证 $a,b,c,m\le 100$。
- 对于测试点 $6\sim 10$：保证 $b=c=1$，$op=1$。
- 对于测试点 $11\sim 15$：保证 $c=1$，$op\in\{1,2\}$。
- 对于测试点 $16\sim 20$：无特殊限制。


title: 「PFLOI R1」PFL 变换

background:
五大高手云集于此，思想的火花激烈碰撞。很快，PFLOI Round 1 准备完毕。

开始了……

description:
新的征途已经开始：智力踏上了寻香蕉之旅。道路上共有 $n$ 个香蕉，编号从 $1$ 到 $n$。

智力看到如此美食，非常激动。但是智力不想吃得太饱或太少，所以它会吃**刚好** $m$ 个香蕉。

智力是一个挑剔的人，只有当它吃的 $m$ 个香蕉的编号的异或和**恰好为** $2^{\lfloor\log_2 n\rfloor+1}-1$ 时他才会满意。请你帮忙找出他应该吃哪些香蕉，好让他满意。

如果怎样都不能满足智力的需求，就请输出 `-1` 吧。

------------

**形式化题面**：

请你从 $1$ 到 $n$ 中选出 $m$ 个数，使得它们的异或和恰好为 $2^{\lfloor\log_2 n\rfloor+1}-1$。若无解输出 `-1`。

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

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

对于每组测试数据，每行两个整数 $n$ 和 $m$，含义见题面。

outputFormat:
对于每组测试数据，若有解，输出一行共 $m$ 个整数，表示你选择的 $m$ 个数；若无解，输出 `-1`。

**本题采用 Special Judge**。若有多种可能的解，任意输出一个即可。


title: 汪了个汪

background: 你说得对，但是小 P 在 [[NOIP2022] 喵了个喵](https://www.luogu.com.cn/problem/P8866) 中没有输出操作次数，获得了 $0$ 分的好成绩。

description:
小 P 喜欢上了一款叫做《汪了个汪》的游戏。这个游戏有一个牌堆和一个金字塔形的棋盘，总共有 $3$ 关。具体地，如图所示，棋盘的边长为 $n$，第 $i$ 行有 $i$ 个格子，共 $\dfrac{n(n+1)}{2}$ 个格子。

牌堆中有 $1, 2 \dots n$ 的数字卡片 **各无穷多张**。你需要将这些数字卡片放到对应的棋盘格子中，每个格子恰好放一张数字卡片，要求满足棋盘的每一行的第一个元素 **互不相同**。

小 P 发现，这个游戏的难度会随着关卡编号而增加：

- 在第 $0$ 关中，你不必满足其他条件。
- 在第 $1$ 关中，你需要保证一行内相邻的两个数互不相同，且所有由任意一行内相邻两个数组成的 **无序二元组** 互不相同。
- 在第 $2$ 关中，你需要满足第 $1$ 关的限制，并且一行内的 **所有数** 必须互不相同。

例如，下面是 $n=5$ 时可以通过第 $2$ 关的摆放方式：

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

现在给定 $n$ 与关卡编号，请你帮小 P 找出一种合适的摆放方式来通过这一关。可以证明在游戏限制下一定存在一种过关方式。

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

仅一行，包含两个整数 $n, t$，其中 $t$ 表示关卡编号。

outputFormat:
输出到标准输出。

输出 $n$ 行，第 $i$ 行包含 $i$ 个正整数（以空格分隔），表示棋盘第 $i$ 行从左到右所有的数。

如果有多种合法的解，你可以输出任何一种。

hint:
**【说明与提示】**

本题下发校验器（`checker.cpp`）。将 `checker.cpp` 编译成可执行文件 `checker` 后，在当前目录执行 `checker woof.in woof.out woof.ans` 即可校验你的答案是否符合规范。其中 `woof.in` 可以替换为对应输入文件名称，`woof.out` 可以替换为对应输出文件名称，也即构造结果。`woof.ans` 可以为任意文件。

返回结果说明：

- `The numbers are not in the valid range.`：说明你的输出不满足每个数字都在 $1\sim n$ 的范围内。
- `The first column does not satisfice.`：说明你的输出不满足每行开头的数互不相同。
- `The pairs of numbers are not distinct.`：说明你的输出不满足所有由任意一行内相邻两个数组成的无序二元组互不相同。
- `The adjacent numbers are not distinct.`：说明当前关卡编号 $\ge1$ 且你的输出不满足关卡 $1$ 的条件。
- `The numbers in a row are not distinct.`：说明当前关卡编号 $\ge2$ 且你的输出不满足关卡 $2$ 的条件。
- `Well done.`：说明你的构造满足要求。

---

#### 【数据范围】

| 测试点编号 | $n \leq$ | $t =$ | 特殊性质 |
| :--------: | :------: | :---: | :------: |
| $1$ | $6$ | $0$ | 无 |
| $2$ | $6$ | $2$ | 无 |
| $3 \sim 4$ | $4000$ | $2$ | A |
| $5 \sim 7$ | $500$ | $1$ | 无 |
| $8 \sim 13$ | $500$ | $2$ | 无 |
| $14 \sim 16$ | $4000$ | $1$ | 无 |
| $17 \sim 20$ | $4000$ | $2$ | 无 |

+ 特殊性质 A：保证 $n + 1$ 或 $n + 2$ 为质数。

对于 $100 \%$ 的数据，保证 $1 \leq n \leq 4000$，$t \in \{0, 1, 2\}$。


title: 「yyOI R1」youyou 的序列

description:
给定一个长度为 $n$ 的序列 $a_{1\dots n}$，以及 $q$ 次操作。

定义一次操作为：交换 $a_k$ 与 $a_{k+1}$ 的值，并**立即**询问所有以 $a_i \;( i\in [1,n])$ 为峰的[子序列](https://oi-wiki.org/string/basic/#%E5%AD%90%E5%BA%8F%E5%88%97)数量之和，对 $4294967296$ 取模。**这里的交换是暂时的，也就是说，它仅在下一次操作前有效。**

在此我们认为，一个长度至少为 $1$ 的序列 $[a_1,a_2 ,\cdots,a_{s-1},a_s,a_{s+1},\cdots,a_{n-1},a_n ]$，满足 $a_1<a_2<\cdots<a_{s-1}<a_s>a_{s+1}>\cdots >a_{n-1}>a_n$，则称此序列为以 $a_s$ 为峰的序列。

你的任务是回答出所有操作的答案。

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

第二行输入 $n$ 个正整数，表示一开始的序列 $a_{1\dots n}$。

第三行，输入一个整数 $k$，表示进行第一次操作（定义见上），保证 $1\le k <n$。

---

第 $2$ 到第 $q$ 次操作的 $k$ 值由如下方法得到：

```cpp
int Answer(unsigned int ans)
{
    unsigned int BASE=998244353ll*ans+ans*ans+ans/9991+ans%2159;
    BASE^=9810;
    BASE^=51971;
    BASE=BASE>>7;
    BASE=BASE<<11;
    BASE^=751669;
    BASE^=23465695622566ll;
    return BASE%(n-1)+1;
}
```
当你每完成一次询问后，将你这次询问的答案 $ans$ 作为参数，**恰好**调用一次 `Answer(ans)` 。

得到的返回值即为下一次操作的 $k$。

**注意：本输入方式仅用于减少输入量，标准算法不依赖于此输入方式。**

outputFormat: 你需要输出所有操作的答案，每个答案输出一行。


title: [NICA #3] 星空（Easy Version）

type: B

background: **Easy Version 和 Hard Version 差别在于数据范围。**

description:
小 R 有一个长度为 $n$ 的序列 $a$，保证序列中的每个数都是 $2$ 的整数次幂。

小 M 有一个数 $x$，她希望重新排列序列 $a$，使得不存在一个 $i\in[1,n)$ 满足 $a_i+a_{i+1}>x$。重排的方式为：选择一个 $1\sim n$ 的排列 $p$，然后令新序列 $a'$ 满足 $a'_i=a_{p_i}$。$a'$ 即为重排后的序列。

现在你想要知道有多少种重排的方式能满足小 M 的要求。两种重排方式不同当且仅当选择的排列 $p$ 不同。答案对 $10^9+7$ 取模。

inputFormat:
第一行输入两个正整数 $n,x$，表示序列长度和小 M 想的那个数；

第二行输入 $n$ 个正整数 $a_i$，表示序列；

outputFormat: 输出一行表示答案。答案对 $10^9+7$ 取模。


title: [NICA #3] 星空（Hard Version）

description:
小 R 有一个长度为 $n$ 的序列 $a$，保证序列中的每个数都是 $2$ 的整数次幂。

小 M 有一个数 $x$，她希望重新排列序列 $a$，使得不存在一个 $i\in[1,n)$ 满足 $a_i+a_{i+1}>x$。重排的方式为：选择一个 $1\sim n$ 的排列 $p$，然后令新序列 $a'$ 满足 $a'_i=a_{p_i}$。$a'$ 即为重排后的序列。

现在你想要知道有多少种重排的方式能满足小 M 的要求。两种重排方式不同当且仅当选择的排列 $p$ 不同。

outputFormat: 输出一行表示答案。答案对 $10^9+7$ 取模。


title: 「yyOI R1」youyou 的军训

background: 在 youyou 的班上，身高可能是一个敏感的话题。

description:
youyou 的班上一共有 $n$ 位同学，$m$ 对朋友，第 $i$ 对朋友关系对于身高有一个敏感值 $k_i$，敏感值可能会改变。

我们定义两位同学如果互为**朋友**，那么必然存在某对关系，将两位同学**直接**相连。

我们定义两位同学如果互为**好友**，那么必然存在直接或间接的关系，将两位同学相连。

例如存在关系 $(1,2)$ 和 $(2,3)$，那么，$1$ 与 $2$ 是朋友，但 $1$ 与 $3$ 就是好友。

现在，马上就要军训了，同学们要去领军训的服装，如果一位同学领到了尺码为 $p$ 的服装，所有同学会与朋友关系敏感值小于 $p$ 的朋友断交。即对于所有的朋友关系，若其敏感值小于 $p$，那么该朋友关系就会断开。不过在下一位同学领到服装时，所有**之前**的断开的朋友关系会恢复。

由于军训领服装是一个复杂的过程，而 youyou 对此十分感兴趣，所以给出 $q$ 次操作，且一共有三种操作:

- 操作 $1$，形如 `1 x`，表示有一位同学领到尺码为 $x$ 的服装。

- 操作 $2$，形如 `2 x`，表示询问第 $x$ 位同学还有多少位好友（包括自己）。

- 操作 $3$，形如 `3 x y`，表示第 $x$ 对朋友的敏感值变为 $y$，特别地，**敏感值的相对大小不会变化$^*$**（详情见下方），同时原来已经断开的关系不会恢复。

**注意：好友跟朋友是两个概念，朋友一定是好友，但好友不一定是朋友。**

$^*$：相对大小不会变化，指对于当前所有的敏感值而言，修改后的敏感值与原来的敏感值**排名相同**。

例如，若原来所有对朋友之间敏感值是 $\{1,2,3,5,6\}$，$3$ 的排名为 $3$，因此 $3$ 只能修改为 $3,4$ 中的一个，这样才能保证排名不变，即相对大小位置不会变换。

inputFormat:
第一行，输入三个正整数 $n,m,q$。

后面 $m$ 行，给定 $m$ 对朋友关系，对于第 $i$ 行给定三个正整数 $x_i,y_i,k_i$。

最后 $q$ 行，给定 $q$ 次操作。对于每次操作，给定一个正整数为 $op$，即操作类型。

当 $op=1$ 时，再给定一个正整数 $x$，表示有一位同学领到尺码为 $x$ 的服装；

当 $op=2$ 时，再给定一个正整数 $x$，表示一次询问；

当 $op=3$ 时，再给定两个正整数 $x,y$，表示一次修改。

outputFormat: 对于每次询问操作，输出一个 $x$ 表示询问的同学还有几位**好友**（**包括自己**）。保证对于每一个测试点，都会有一个询问操作。

hint:
## 样例解释 #1

如图所示，这是初始的关系图。

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

第一次操作为：有一位同学领到尺码为 $26963$ 的服装，这样，图中所有的边都会断开。

下一次操作：第三对朋友即边 $(2,3)$ 的权变为 $40$。

下一次操作：询问同学 $4$ 的好友数量，因为没有任何存在的边，因此答案为 $1$。

## 数据范围
| 测试点编号 | $n$ | $q$ | 特殊性质 |
| :-----------: | :-----------: | :-----------: | :-----------: |
| $1,2$ | $\le 10$ | $\le 4 \times 10^5$ | 无 |
| $3$ | $\le 10^3$ | $\le 10^3$ | 无 |
| $4$ | $\le 10^5$ | $\le 4 \times 10^5$ | 没有操作 $3$ |
| $5,6$ | $\le 10^5$ | $\le 10^3$ | 无 |
| $7$ | $\le 10^5$ | $\le 4 \times 10^5$ | 没有操作 $1$ |
| $8,9,10$ | $\le 4 \times 10^5$ | $\le 4 \times 10^5$ | 无 |

用 $c_i$ 表示询问中同学领到服装尺码的大小，$e_i$ 表示修改后敏感值的大小。

对于 $100\%$ 的数据，$1 \le n,m,q,x_i,y_i \le 4  \times  10^5$，$1 \le k_i,c_i,e_i \le 1 \times 10^9$，$m\le \min\{\frac{n(n-1)}{2},4 \times 10^5\}$。

同时数据保证在任何时刻，所有对朋友关系之间的敏感值**互不相同**。

**请注意常数因子对时间和空间产生的影响。**


title: 「KDOI-06-J」贡献系统

description:
洛谷贡献系统上线了！

现在有 $n$ 个人即将参加一场洛谷月赛，每个人的等级分**互不相同**。第 $i$ 个人的等级分是 $r_i$，贡献值是 $c_i$。

假设第 $i$ 个人的等级分在这 $n$ 个人中的排名是 $a_i$（排名按等级分从大到小排序），且在月赛中的排名是 $b_i$，没有两个人的排名相同。也就是说，$a$ 和 $b$ 都是 $1$ 到 $n$ 的排列。比赛结束后，每个人都会执行以下操作：

+ 若 $a_i=b_i$，则第 $i$ 个人的等级分不会发生任何变化，因此第 $i$ 个人不会进行任何操作；
+ 若 $a_i>b_i$，则第 $i$ 个人的等级分会上升，因此第 $i$ 个人会给出题人点赞，导致出题人的贡献值上升 $c_i$（$c_i$ 可能是负数，此时会导致出题人的贡献值下降）；
+ 若 $a_i<b_i$，则第 $i$ 个人的等级分会下降，因此第 $i$ 个人会给出题人点踩，导致出题人的贡献值下降 $c_i$（$c_i$ 可能是负数，此时会导致出题人的贡献值上升）。

作为这场月赛唯一的出题人，初始时你的贡献值为 $0$。你想知道，对于所有可能的排列 $b$（显然，排列 $a$ 在比赛前已经被确定），在比赛结束后你的贡献值最大是多少。

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

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

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

对于每组测试数据，第一行一个正整数 $n$，表示参赛选手人数。

第二行包含 $n$ 个非负整数 $r_1,r_2,\ldots,r_n$，表示参赛选手的等级分。保证对于任意 $1\le i< n$，$r_i>r_{i+1}$。

第三行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$，表示参赛选手的贡献值。

outputFormat:
输出到标准输出。

对于每组测试数据，输出一行一个整数，表示最大的贡献值。

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

对于第一组测试数据，设五个人按输入顺序分别为 A，B，C，D，E，则当月赛中的排名顺序为 ABECD 时贡献值最大，为 $0+0-(-50)-(-22)+208=280$。可以证明，这是唯一能使贡献值达到最大的排名顺序。

对于第二组测试数据，设八个人按输入顺序分别为 A，B，C，D，E，F，G，H，则当月赛中的排名顺序为 ABCDEGFH 时可以使贡献值达到最大值 $1$，注意此时有多种可能的使贡献值最大的排名顺序。

**【样例 #2】**

见选手目录下的 `contrib/contrib2.in` 与 `contrib/contrib2.ans`。

**【样例 #3】**

见选手目录下的 `contrib/contrib3.in` 与 `contrib/contrib3.ans`。

***

**【数据范围】**

对于所有数据保证：$1\le T\le 5$，$1\le n\le 2\times 10^5$，$0\le r_i\le 10^9$，$-10^9\le c_i\le 10^9$，且对于任意 $1\le i<n$，$r_i>r_{i+1}$。

| 测试点编号  |    $n\le $     | 特殊限制 |
| :---------: | :------------: | :------: |
|  $1\sim3$   |      $8$       |    无    |
|     $4$     |     $100$      |   ABC    |
|     $5$     |     $100$      |    C     |
|  $6\sim 7$  |     $100$      |    无    |
|  $8\sim 9$  | $5\times 10^3$ |    AB    |
| $10\sim 11$ | $5\times 10^3$ |    C     |
| $12\sim 14$ | $5\times 10^3$ |    无    |
|    $15$     | $2\times10^5$  |    AB    |
| $16\sim 18$ | $2\times10^5$  |    B     |
| $19\sim 21$ | $2\times10^5$  |    C     |
| $22\sim 25$ | $2\times 10^5$ |    无    |

+ 特殊性质 A：对于任意 $1\le i<n$，保证 $c_i=c_{i+1}$；
+ 特殊性质 B：对于任意 $1\le i<n$，保证 $c_i\le c_{i+1}$；
+ 特殊性质 C：对于任意 $1\le i\le n$，保证 $c_i\ge 0$。


title: [APC001] F - Extend

background: ~~**本题输入输出量较大，请酌情使用较快的输入输出方式**~~。已扩大时限从 $1s\to 1.5s$。

description:
对于一棵有 $n$ 个节点，根为 $k$ 的树，最开始有且仅有一个“可扩展的”节点 $z$，我们有两种扩展形式：

- $\text{I}$ 类扩展：从一个“可扩展的”节点 $u$ 开始扩展，把 $u$ 的子树中所有节点和所有满足与 $u$ 距离 $\leq p$ 且是 $u$ 祖先的节点标记为“可扩展的”。
- $\text{II}$ 类扩展：从一个“可扩展的”节点 $u$ 开始扩展，把所有与 $u$ 深度相等的节点标记为“可扩展的”。

你需要将所有结点都标记为“可扩展的”，求最小进行扩展的次数。

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

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

接下来一行一个整数 $t$，表示询问次数。

接下来 $t$ 行，每行两个整数 $z,p$，意义如上。

outputFormat:
$t$ 行，对于每次询问：

- 若无法将所有节点都标记为“可扩展的”，输出 `-1`。

- 否则一行一个整数，表示答案。

hint:
样例 $1$ 解释：两次询问都可以先对 $2$ 节点进行 $\text{II}$ 类扩展，然后对 $3$ 进行 $\text{I}$ 类扩展。可以保证对于两次询问，这样操作都是最优的。

对于所有数据，$1\leq z,k,u,v\leq n\leq 10^5,1\leq t\leq 2\times 10^6,0\leq p\leq 10^{18}$。


title: [GESP202303 一级] 长方形面积

description: 小明刚刚学习了如何计算长方形面积。他发现，如果一个长方形的长和宽都是整数，它的面积一定也是整数。现在，小明想知道如果给定长方形的面积，有多少种可能的长方形，满足长和宽都是整数？如果两个长方形的长相等、宽也相等，则认为是同一种长方形。约定长方形的长大于等于宽。正方形是长方形的特例，即长方形的长和宽可以相等。

inputFormat: 输入一行，包含一个整数 $A$，表示长方形的面积。约定 $2 \leq A \leq 1000$。

outputFormat: 输出一行，包含一个整数 $C$，表示有 $C$ 种可能的长方形。

hint:
【样例 1 解释】

有 $2$ 种长方形面积为 $4$，它们的长宽分别为 $2 \times 2$，$4 \times 1$。

【样例 2 解释】

有 $2$ 种长方形面积为 $6$，它们的长宽分别为 $3 \times  2$，$6 \times 1$。


title: [GESP202303 一级] 每月天数

description: 小明刚刚学习了每月有多少天，以及如何判断平年和闰年，想到可以使用编程方法求出给定的月份有多少天。你能做到吗？

inputFormat: 输入一行，包含两个整数 $A, B$，分别表示一个日期的年、月。约定 $2000 \leq A \leq 3000$，$1 \leq B \leq 12$。

outputFormat: 输出一行，包含一个整数，表示输入月份有多少天。


title: [GESP202303 二级] 百鸡问题

description:
“百鸡问题”是出自我国古代《张丘建算经》的著名数学问题。大意为：
> “每只公鸡 $5$ 元，每只母鸡 $3$ 元，每 $3$ 只小鸡 $1$ 元；现在有 $100$ 元，买了 $100$ 只鸡，共有多少种方案？”

小明很喜欢这个故事，他决定对这个问题进行扩展，并使用编程解决：如果每只公鸡 $x$ 元，每只母鸡 $y$ 元，每 $z$ 只小鸡 $1$ 元；现在有 $n$ 元，买了 $m$ 只鸡，共有多少种方案？

inputFormat: 输入一行，包含五个整数，分别为问题描述中的 $x$，$y$，$z$，$n$，$m$。约定 $1 \le x,y,z \le 10$，$1 \le n,m \le 1000$。

outputFormat: 输出一行，包含一个整数 $C$，表示有 $C$ 种方案。

hint:
【样例 1 解释】

这就是问题描述中的“百鸡问题”。$4$ 种方案分别为：
- 公鸡 $0$ 只、母鸡 $25$ 只、小鸡 $75$ 只。
- 公鸡 $4$ 只、母鸡 $18$ 只、小鸡 $78$ 只。
- 公鸡 $8$ 只、母鸡 $11$ 只、小鸡 $81$ 只。
- 公鸡 $12$ 只、母鸡 $4$ 只、小鸡 $84$ 只。


title: [GESP202303 二级] 画三角形

description: 输入一个正整数 $n$，请使用大写字母拼成一个这样的三角形图案（参考样例输入输出）：三角形图案的第 $1$ 行有 $1$ 个字母，第 $2$ 行有 $2$ 个字母，以此类推；在三角形图案中，由上至下、由左至右依次由大写字母 $\texttt{A}-\texttt{Z}$ 填充，每次使用大写字母 $\texttt Z$ 填充后，将从头使用大写字母 $\texttt A$ 填充。

inputFormat: 输入一行，包含一个正整数 $n$。约定 $2 \le n \le 40$。

outputFormat: 输出符合要求的三角形图案。注意每行三角形图案的右侧不要有多余的空格。


title: [GESP202306 一级] 时间规划

description: 小明在为自己规划学习时间。现在他想知道两个时刻之间有多少分钟，你能通过编程帮他做到吗？

inputFormat: 输入 $4$ 行，第一行为开始时刻的小时，第二行为开始时刻的分钟，第三行为结束时刻的小时，第四行为结束时刻的分钟。输入保证两个时刻是同一天，开始时刻一定在结束时刻之前。时刻使用 $24$ 小时制，即小时在 $0$ 到 $23$ 之间，分钟在 $0$ 到 $59$ 之间。

outputFormat: 输出一行，包含一个整数，从开始时刻到结束时刻之间有多少分钟。


title: [GESP202306 一级] 累计相加

description:
输入一个正整数 $n$，求形如：

$1+(1+2)+(1+2+3)+(1+2+3+4)+ \cdots  +(1+2+3+4+5+ \cdots  +n)$ 的累计相加。

inputFormat: 输入一个正整数 $n$。约定 $1<n \le 100$。

outputFormat: 输出累计相加的结果。


title: [GESP202306 二级] 找素数

description: 小明刚刚学习了素数的概念：如果一个大于 $1$ 的正整数，除了 $1$ 和它自身外，不能被其他正整数整除，则这个正整数是素数。现在，小明想找到两个正整数 $A$ 和 $B$ 之间（包括 $A$ 和 $B$）有多少个素数。

inputFormat: 输入只有一行两个正整数 $A, B$。约定 $2 \le A \le B \le 1000$。

outputFormat: 输出一行，包含一个整数 $C$，表示找到 $C$ 个素数。

hint:
【样例解释 1】

在 $2$ 和 $10$ 之间有 $4$ 个素数，分别为：$2$、$3$、$5$、$7$。


title: [GESP202306 二级] 自幂数判断

description: 自幂数是指，一个 $N$ 位数，满足各位数字 $N$ 次方之和是本身。例如，$153$ 是 $3$ 位数，其每位数的 $3$ 次方之和，$1^3+5^3+3^3=153$，因此 $153$ 是自幂数；$1634$ 是 $4$ 位数，其每位数的 $4$ 次方之和，$1^4+6^4+3^4+4^4=1634$，因此 $1634$ 是自幂数。现在，输入若干个正整数，请判断它们是否是自幂数。

inputFormat:
输入第一行是一个正整数 $M$，表示有 $M$ 个待判断的正整数。约定 $1 \le M \le 100$。

从第 $2$ 行开始的 $M$ 行，每行一个待判断的正整数。约定这些正整数均小于 $10^8$。

outputFormat:
输出 $M$ 行，如果对应的待判断正整数为自幂数，则输出英文大写字母 $\texttt T$，否则输出英文大写字母 $\texttt F$。

提示：不需要等到所有输入结束在依次输出，可以输入一个数就判断一个数并输出，再输入下一个数。


title: [GESP202306 三级] 春游

description: 老师带领同学们春游。已知班上有 $N$ 位同学，每位同学有从 $0$ 到 $N-1$ 的唯一编号。到了集合时间，老师确认是否所有同学都到达了集合地点，就让同学们报出自己的编号。到达的同学都会报出自己的编号，不会报出别人的编号，但有的同学很顽皮，会多次报出。你能帮老师找出有哪些同学没有到达吗 ?。

inputFormat:
输入包含 $2$ 行。第一行包含两个整数 $N$ 和 $M$，表示班级有 $N$ 位同学，同学们共有 $M$ 次报出编号。约定 $2 \le N,M \le 1000$。
第二行包含 $M$ 个整数，分别为 $M$ 次报出的编号。约定所有编号是小于 $N$ 的非负整数。

outputFormat: 输出一行。如果所有同学都到达，则输出 $N$；否则由小到大输出所有未到达的同学编号，空格分隔。


title: [GESP202306 三级] 密码合规

description:
网站注册需要有用户名和密码，编写程序以检查用户输入密码的有效性。合规的密码应满足以下要求 :。

1. 只能由 $\texttt a \sim \texttt z$ 之间 $26$ 个小写字母、$\texttt A \sim \texttt Z$ 之间 $26$ 个大写字母、$0 \sim 9$ 之间 $10$ 个数字以及 `!@#$` 四个特殊字符构成。

2. 密码最短长度 $:6$ 个字符，密码最大长度 $:12$ 个字符。

3. 大写字母，小写字母和数字必须至少有其中两种，以及至少有四个特殊字符中的一个。

inputFormat: 输入一行不含空格的字符串。约定长度不超过 $100$。该字符串被英文逗号分隔为多段，作为多组被检测密码。

outputFormat: 输出若干行，每行输出一组合规的密码。输出顺序以输入先后为序，即先输入则先输出。

hint:
【样例 1 解释】

输入被英文逗号分为了四组被检测密码：`seHJ12!@`、`sjdkffH$123`、`sdf!@&12HDHa!`、`123&^YUhg@!`。其中 `sdf!@&12HDHa!` 长度超过 12 个字符，不合规；`123&^YUhg@!` 包含四个特殊字符之外的字符不合规。


title: [GESP样题 二级] 画正方形

description:
输入一个正整数 $n$，要求输出一个 $n$ 行 $n$ 列的正方形图案（参考样例输入输出）。图案由大写字母组成。

其中，第 $1$ 行以大写字母 $\texttt A$ 开头，第 $2$ 行以大写字母 $\texttt B$ 开头，以此类推；在每行中，第 $2$ 列为第 $1$ 列的下一个字母，第 $3$ 列为第 $2$ 列的下一个字母，以此类推；特别的，规定大写字母 $\texttt Z$ 的下一个字母为大写字母 $\texttt A$。

inputFormat: 输入一行，包含一个正整数 $n$。约定 $2 \le n \le 40$。

outputFormat: 输出符合要求的正方形图案。


title: [GESP样题 二级] 勾股数

description: 勾股数是很有趣的数学概念。如果三个正整数 $a,b,c$，满足 $a^2+b^2=c^2$，而且 $1 \le a \le b \le c$，我们就将 $a, b, c$ 组成的三元组 $(a,b,c)$ 称为勾股数。你能通过编程，数数有多少组勾股数，能够满足 $c \le n$ 吗？

inputFormat: 输入一行，包含一个正整数 $n$。约定 $1 \le n \le 1000$。

outputFormat: 输出一行，包含一个整数 $C$，表示有 $C$ 组满足条件的勾股数。


title: [GESP样题 一级] 闰年求和

description: 小明刚刚学习了如何判断平年和闰年，他想知道两个年份之间（**不包含起始年份和终止年份**）的闰年年份具体数字之和。你能帮帮他吗？

inputFormat: 输入一行，包含两个整数，分别表示起始年份和终止年份。约定年份在 $1$ 到 $2022$ 之间。

outputFormat: 输出一行，包含一个整数，表示闰年年份具体数字之和。


title: [GESP样题 一级] 当天的第几秒

description: 小明刚刚学习了小时、分和秒的换算关系。他想知道一个给定的时刻是这一天的第几秒，你能编写一个程序帮帮他吗？

inputFormat: 输入一行，包含三个整数和一个字符。三个整数分别表示时刻的时、分、秒；字符有两种取值，大写字母'A'表示上午，大写字母'P'表示下午。

outputFormat: 输出一行，包含一个整数，表示输入时刻是当天的第几秒。


title: [GESP样题 三级] 逛商场

description:
小明是个不太有计划的孩子。这不，刚到手的零花钱，就全部拿着逛商场去了。

小明的原则很简单，见到想买的物品，只要能买得起，就一定会买下来之后才会继续往前走；如果买不起就直接跳过。

一天下来，小明到底买了多少物品呢？

inputFormat:
输入共 $3$ 行：

第一行是一个整数 $N$，表示商场中共有 $N$ 种小明想买的物品（$1≤N≤100$）；

第二行共有 $N$ 个整数，分别表示小明先后见到想买的物品的价格；

第三行是一个整数 $X$，表示开始时小明共有 $X$ 元零花钱。

outputFormat: 输出 $1$ 行，包含一个整数，表示小明买到的物品数。


title: [GESP样题 三级] 进制转换

description:
小美刚刚学习了十六进制，她觉得很有趣，想到是不是还有更大的进制呢？在十六进制中，用 `A` 表示 $10$、`F` 表示 $15$。如果扩展到用 `Z` 表示 $35$，岂不是可以表示 $36$ 进制数了嘛！

所以，你需要帮助她写一个程序，完成十进制转 $R$ 进制（$2\le R\le 36$）的工作。

inputFormat: 输入两行，第一行包含一个正整数 $N$，第二行包含一个正整数 $R$，保证 $1\le N\le 10^6$。

outputFormat: 输出一行，为 $N$ 的 $R$ 进制表示。


title: [GESP202306 四级] 幸运数

description:
小明发明了一种 "幸运数"。一个正整数，其偶数位不变（个位为第 $1$ 位，十位为第 $2$ 位，以此类推），奇数位做如下变换：将数字乘以 $7$，如果不大于 $9$ 则作为变换结果，否则把结果的各位数相加，如果结果不大于 $9$ 则作为变换结果，否则（结果仍大于 $9$）继续把各位数相加，直到结果不大于 $9$，作为变换结果。变换结束后，把变换结果的各位数相加，如果得到的和是 $8$ 的倍数，则称一开始的正整数为幸运数。

例如，$16347$：第 $1$ 位为 $7$，乘以 $7$ 结果为 $49$，大于 $9$，各位数相加为 $13$，仍大于 $9$，继续各位数相加，最后结果为 $4$；第 $3$ 位为 $3$，变换结果为 $3$；第 $5$ 位为 $1$，变换结果为 $7$。最后变化结果为 $76344$，对于结果 $76344$ 其各位数之和为 $24$，是 $8$ 的倍数。因此 $16347$ 是幸运数。

inputFormat:
输入第一行为正整数 $N$，表示有 $N$ 个待判断的正整数。约定 $1 \le N \le 20$。

从第 $2$ 行开始的 $N$ 行，每行一个正整数，为待判断的正整数。约定这些正整数小于 $10^{12}$。

outputFormat:
输出 $N$ 行，对应 $N$ 个正整数是否为幸运数，如是则输出 'T'，否则输出 'F'。

提示：不需要等到所有输入结束在依次输出，可以输入一个数就判断一个数并输出，再输入下一个数。


title: [GESP202306 四级] 图像压缩

description:
图像是由很多的像素点组成的。如果用 $0$ 表示黑，$255$ 表示白，$0$ 和 $255$ 之间的值代表不同程度的灰色，则可以用一个字节表达一个像素（取值范围为十进制 `0-255`、十六进制 `00-FF`）。这样的像素组成的图像，称为 $256$ 级灰阶的灰度图像。

现在希望将 $256$ 级灰阶的灰度图像压缩为 $16$ 级灰阶，即每个像素的取值范围为十进制 `0-15`、十六进制 `0-F`。压缩规则为：统计出每种灰阶的数量，取数量最多的前 $16$ 种灰阶（如某种灰阶的数量与另外一种灰阶的数量相同，则以灰阶值从小到大为序），分别编号 `0-F`（最多的编号为 `0`，以此类推）。其他灰阶转换到最近的 $16$ 种灰阶之一，将某个点的灰阶值（灰度，而非次数）与 $16$ 种灰阶中的一种相减，绝对值最小即为最近，如果绝对值相等，则编号较小的灰阶更近。

inputFormat:
输入第 $1$ 行为一个正整数 $n(10\le n \le 20)$，表示接下来有 $n$ 行数据组成一副 $256$ 级灰阶的灰度图像。

第 $2$ 行开始的 $n$ 行，每行为长度相等且为偶数的字符串，每两个字符用十六进制表示一个像素。约定输入的灰度图像至少有 $16$ 种灰阶。约定每行最多 $20$ 个像素。

outputFormat:
第一行输出压缩选定的 $16$ 种灰阶的十六进制编码，共计 $32$ 个字符。

第二行开始的 $n$ 行，输出压缩后的图像，每个像素一位十六进制数表示压缩后的灰阶值。

samples:
10
00FFCFAB00FFAC09071B5CCFAB76
00AFCBAB11FFAB09981D34CFAF56
01BFCEAB00FFAC0907F25FCFBA65
10FBCBAB11FFAB09981DF4CFCA67
00FFCBFB00FFAC0907A25CCFFC76
00FFCBAB1CFFCB09FC1AC4CFCF67
01FCCBAB00FFAC0F071A54CFBA65
10EFCBAB11FFAB09981B34CFCF67
01FFCBAB00FFAC0F071054CFAC76
1000CBAB11FFAB0A981B84CFCF66


title: 「yyOI R1」youyou 的篡改（Easy Ver.）

background: **Easy Version 与 Hard Version 仅最后所求内容不同，其他描述均一致。**

description:
youyou 准备举办一场比赛，这场比赛有 $n$ 道题，每一道题都有一个难度值 $v_i$。

youyou 给出一个计数分量 $k(k\le n)$，他认为，第 $x(x \geq k)$ 道题的可做性 $a_x$ 应当是第 $1\sim x$ 题所有题目中将难度值从小到大排序后难度较大的 $k$ 道题目难度值之和。

由于第 $1 \sim k-1$ 题难度过于简单，youyou 不想考虑这些题目的可做性。

那么这场比赛的总可做性即为第 $k$ 道题至第 $n$ 道题可做性之和，即 $\sum^{n}_{i=k}a_i$
 的值。

youyou 可以篡改题目 $m$ 的难度为任意正整数，但是他并不希望这场比赛过难或者过简单，所以他要求总可做性必须介于 $[l,r]$ 之间。

youyou 想知道，他通过篡改题目 $m$ 的难度，可以将总可做性最大篡改为多少？

特别的，如不存在一组解请输出 $-1$。

inputFormat:
第一行输入五个正整数，分别为 $n,m,k,l,r$。

第二行输入 $n$ 个整数，第 $i$ 个数 $v_i$ 为第 $i$ 道题难度值。

outputFormat: 仅一行，输出一个数，表示在满足条件的前提下，总可做性可改为的最大值。


title: [信息与未来 2015] 夏令营小旗手

description:
$2015$ 年江苏省“信息与未来”小学夏令营在洪泽县实验小学进行，组委会决定在洪泽实验小学的学生中挑选一名小旗手，推选方法如下：

洪泽实验小学有 $n$ 名学生，每名学生有一个学号，学号为 $1\sim n$。同时，每名同学有一张选票，可以推选一名同学为小旗手，最后，得票最多者当选；若得票最有多名（票数相同），则学号小者当选。

例如 $n=8$，选票为 $2,3,4,4,3,4,1,6$，$4$ 号学生得票最多（$3$ 票），当选小旗手。

inputFormat:
两个整数 $n,x_1$，$n$ 为学生数，$x_1$ 为第一个选票上的学号，之后的选票 $x_i(i\ge2)$ 由下面的递推关系给出：

$x_i = ((x_{i-1}\times 37+33031)\bmod n)+1$。

其中 $\bmod$ 为取余运算。例如，$13 \bmod 8 = 5,21 \bmod 21 = 0$。根据这个公式，就能从 $x_1$ 推出 $x_{2\sim n}$。

outputFormat: 一个整数，即选出的小旗手的学号。


title: [信息与未来 2015] 中间值

description:
给出一个正整数 $n$，生成长度为 $n$ 的数列 $a$，其中 $a_i=i(1\le i\le n)$。

- 若 $n$ 为奇数，则输出 $a$ 的中间数（位于 $a$ 正中位置的数）；
- 若 $n$ 为偶数，则输出位于 $a$ 中间两个数的和。

inputFormat: 一个正整数 $n$。

outputFormat: 一个正整数。若 $n$ 为奇数，则输出其中间值；若 $n$ 为偶数，则输出两个中间值的和。


title: [信息与未来 2015] 分数计数

description:
有 $n$ 个球队，编号为 $1\sim n$，共进行 $n$ 场比赛，每场比赛有一个胜队。计分方法如下：
- 是连胜中的第一次胜利，则本次胜利得 $1$ 分。
- 是连胜中的第二次胜利，则本次胜利得 $2$ 分。
- 是连胜中的第三次胜利，则本次胜利得 $3$ 分。
- 连胜超过三次以上的胜场，每场得 $3$ 分。

例如 $n=12$，比赛的胜队为 $1,2,1,1,3,2,1,1,1,1,4,2$，计分如下：
- 队 $1$：$1+1+2+1+2+3+3=13$ 分；
- 队 $2$：$1+1+1=3$ 分；
- 队 $3\sim 4$：$1$ 分。
- 队 $5\sim 12$：$0$ 分。

求得分最多的队伍的分数。

inputFormat:
两个整数 $n,x_1$，$n$ 为球队数，$x_1$ 为第一次胜队号，第 $i(i\ge2)$ 场比赛胜队的编号由
以下公式确定：

$x_i = ((x_{i-1}\times 3703+1047) \bmod n)+1$。

outputFormat: 一个整数，即得分最多队的分数。


title: [信息与未来 2015] 连续数的和

description: 给出两个整数 $n$ 和 $k$，求出 $1\sim n$ 中连续 $k$ 个数的和为完全平方数的个数。

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

outputFormat: 一行一个整数，即 $1\sim n$ 中连续 $k$ 个数的和为平方数的个数。


title: [信息与未来 2015] 买木头

description:
有 $n$ 个木材供应商，每个供应商有长度相同的一定数量的木头。长木头可以锯短，但短木头不能接长。有一个客人要求 $m$ 根长度相同的木头，要求计算出：此时供货商提供的木头满足客人要求的最大长度是多少。

例如 $n=2,m=30$，两个供货商的木头为：
- $12,10$（第 $1$ 个供货商的木头长度为 $12$，共有 $10$ 根）；
- $5,10$（第 $2$ 个供货商的木头长度为 $5$，共有 $10$ 根）。

计算的结果为 $5$，即长度为 $12$ 的木头一根可锯出两根长度为 $5$ 的木头，多余的无用；长度为 $5$ 的木头不动，此时，可以得到 $30$ 根长度为 $5$ 的木头。

inputFormat:
一行四个整数 $n,m,l_1,s_1$。其中 $l_1$ 是第一个供货商木头的长度，$s_1$ 是第一个供货商木头的数量。其他供货商木头
的长度和数量 $l_i$ 和 $s_i(i\ge2)$由下面的公式给出：
- $l_i=((l_{i-1}\times37011+10193) \bmod 10000)+1$；
- $s_i=((s_{i-1}\times73011+24793) \bmod 100)+1$。

outputFormat: 一个整数，即满足要求的 $m$ 根长度相同的木头的最大长度。


title: [信息与未来 2015] 拴奶牛

description:
有 $n$ 头奶牛，有 $k$ 个木桩，每个木桩有一个位置，一个木桩上只能拴一头奶牛。由于奶牛好斗，所以在拴奶牛的时候，要求距离最近的奶牛的距离尽可能大。

例如 $n=4,k=6$，木桩的位置为 $0,3,4,7,8,9$，此时为下图。
$$
\underline\text{\qquad O\quad l\quad l\quad O\quad O\quad l\quad l\quad O\quad O\quad O\qquad}\\
\text{\qquad 0\quad\ \quad\ \ \quad 3\ \quad 4\quad\quad\quad\quad 7\quad\ 8\quad\ 9\qquad}\\
$$
有许多种拴牛方案，例如：
- $0,3,4,9$：此时最近距离为 $1$（$3,4$ 之间）；
- $0,3,7,9$：此时最近距离为 $2$。

inputFormat:
三个整数 $n,k,p_1$，其中 $p_1$ 为第 $1$ 个木桩的位置，其他木桩 $p_i(i\ge2)$ 的位置由下面公式给出：

$p_i = p_{i-1} + ((p_{i-1}\times2357+137) \bmod 10)+1$。

outputFormat: 一个整数，即奶牛间最近距离的最大值。


title: [信息与未来 2015] 求回文数

description:
一个正整数，正读和反读都相同的数为回文数，例如 $22,131,2442,37073,6,\cdots$。所有的 $1$ 位数都是回文数。

现给出一个正整数 $n$，求出 $[1,n]$ 中的回文数的个数。

inputFormat: 一个整数 $n$。

outputFormat: 一个整数，即 $1\sim n$ 中全部回文数的个数。


title: [信息与未来 2015] 加数

description:
给出一个正整数 $n$，在 $n$ 的右边加入 $\left\lfloor\dfrac n2\right\rfloor$，然后在新数的右边
再加入 $\left\lfloor\dfrac{\left\lfloor\dfrac n2\right\rfloor}2\right\rfloor$，一直这样进行下去，直到加入的数为 $0$ 为止（注意，$0$ 不应当被加入）。

求加数结束后新数的长度。

inputFormat: 一行一个整数 $n$。

outputFormat: 一行一个整数，为加数结束后新数的长度。

hint:
### 样例解释
- $\left\lfloor\dfrac{37}2\right\rfloor=18$，加到 $n$ 的右边成为 $3718$；
- $\left\lfloor\dfrac{18}2\right\rfloor=9$，加到新数的右边成为 $37189$；
- $\left\lfloor\dfrac{9}2\right\rfloor=4$，加到新数的右边成为 $371894$；
- $\left\lfloor\dfrac{4}2\right\rfloor=2$，加到新数的右边成为 $3718942$；
- $\left\lfloor\dfrac{2}2\right\rfloor=1$，加到新数的右边成为 $37189421$；
- $\left\lfloor\dfrac12\right\rfloor=0$，加数结束，最后得到的数是一个 $8$ 位数。
### 数据范围
$1\le n\le10^5$。


title: 「KDOI-07」能量场

background: 4202 年，小 K 作为一名已经工作了 3143 天的 gaLaxy enGineer Master，在 XS41 星系的 OIPA115 星球上建立了据点，帮助人类探索未知。在这里，他建起了一些能量场。原本他决定使用一些卒来运输能量，然而在他操控的两个红色卒碰撞并损失所有能量后决定还是应该使用能量管道连接他们，~~并使能量管道呈 $(180+\mathrm{eps})^\circ$ 角~~。

description:
小 K 有 $n$ 个能量场，第 $i$ 个能量场存储 $a_i$ 点能量。

小 K 在能量场之间建立了 $n$ 条不同的双向能量管道，使得能量场两两连通。

对于一条能量管道，它的能量级为两端能量场能量之和。

小 K 对一组 $n$ 个不同能量管道集合的满意度是所有能量管道能量级的乘积。

现在小 K 想知道，对于所有不同的合法的搭建能量管道的方式，满意度的总和是多少。由于小 K 的满意度是一个 $[0,998244353)$ 之间的整数，所以你只需要输出满意度总和对 $998244353$ 取模后的值即可。

两种搭建管道的方式是不同的当且仅当存在至少一条管道连接能量场 $i,j$，且恰好在其中一种搭建管道的方式中出现。

---

**【形式化题意】**

有一个 $n$ 个点的完全图 $G(V,E)$。每个点有点权 $a_i$。$i,j$ 两点之间的边权 $w_{i,j}=a_i+a_j$。

定义一个连通子图 $G'(V,E')$ 使得 $E'\in E$ 的权值为 $\prod_{e\in E'}w_e$。注意，子图的点集是全集。

求 $G(V,E)$ 的连通子图中所有基环树的权值和，对 $998244353$ 取模。

基环树要求无重边无自环。

inputFormat:
第一行一个正整数 $n$，表示能量场数量。

第二行 $n$ 个非负整数 $a_i$，表示第 $i$ 个能量场存储的能量。

outputFormat: 一行，一个非负整数，表示对于所有不同搭建能量管道的方式，满意度的总和，对 $998244353$ 取模。


title: 「Cfz Round 3」Change

description:
给定一个质数 $p$ 和三个整数 $a,b,c$，你需要对一个初始为 $0$ 的整数 $x$ 进行操作，每次操作可以进行如下的两种之一：

- 第一种操作：令 $x$ 的值变为 $(x \times a) \bmod p$。
- 第二种操作：令 $x$ 的值变为 $(x+b) \bmod p$。

其中，$\bmod$ 表示**取模**运算。

你需要求出能否在**正整数次**操作后得到 $c$，若能则输出 `Yes`，否则输出 `No`。

本题中字符串大小写不敏感，即 `yes`、`yeS`、`yEs`、`Yes`、`YEs`、`YeS`、`yES`、`Yes` 都被认为是 `Yes`，`No` 同理。

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

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

接下来依次输入每组测试数据。对于每组测试数据，输入一行四个整数 $p,a,b,c$。

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

- 若能在正整数次操作后得到 $c$，则输出 `Yes`；
- 若不能在正整数次操作后得到 $c$，则输出 `No`。

本题中字符串大小写不敏感，即 `yes`、`yeS`、`yEs`、`Yes`、`YEs`、`YeS`、`yES`、`Yes` 都被认为是 `Yes`，`No` 同理。

hint:
#### 「样例解释 #1」

对于第 $1$ 组数据，进行 $1$ 次第二种操作后进行 $2$ 次第一种操作即可。

对于第 $2$ 组数据，进行 $1$ 次第二种操作后进行 $1$ 次第一种操作即可。

对于第 $3$ 组数据，可以证明无论如何操作都无法得到 $3$。

#### 「数据范围」

对于所有数据，$1\le T \le 100$，$0\le a,b,c < p \le 10^9$，保证 $p$ 是质数。

**只有你通过本题的所有测试点，你才能获得本题的分数。**


title: 「Cfz Round 2」01 String

description:
定义一个 $\tt{01}$ 串是合法的，当且仅当它的首字符为 $\tt 0$ 而尾字符为 $\tt 1$。我们继而定义一个 $\tt{01}$ 串 $T$ 的权值 $f(T)$ 为，将 $T$ 划分若干个连续的合法子串的方案数。

例如 $f(\tt{001}) = \text{1}$，因为它仅可以被分割为 $[\tt 001]$；$f(\tt{0101101}) = \text{4}$，因为它可以被分割为 $[\tt 0101101][01, 01101][01011, 01][01, 011, 01]$ 共四种不同的方案；而 $f(\tt{1001010101}) = \text{0}$。

给定一个长度为 $n$ 的 $\tt{01}$ 串 $S$。定义 $f_k(l, r) = \begin{cases} f(S_{l\dots r}) & k = 0 \\ \displaystyle\sum_{l\leq l' \leq r' \leq r} f_{k-1}(l', r') & k \gt 0\end{cases}$，你需要求出 $f_k(1, n)$ 的值。

由于答案可能很大，所以你只需要输出答案对 $10^9+7$ 取模的结果。

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

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

接下来依次输入每组测试数据。对于每组测试数据：

+ 第一行输入两个整数 $n,k$，分别表示 $\lvert S\rvert$ 和给定的参数。
+ 接下来一行，输入一个长度为 $n$ 的 $\tt{01}$ 串表示 $S$。

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


title: [JOI Open 2018] 冒泡排序 2

description:
冒泡排序是一个对序列排序的算法。现在我们要将一个长度为 $N$ 的序列 $A_0,A_1,\ldots ,A_{N-1}$ 按不降顺序排序。当两个相邻的数没有按正确顺序排列时，冒泡排序会交换这两个数的位置。每次扫描这个序列就进行这种交换。更确切地说，在一趟**扫描**中，对于 $i=0,1,\ldots ,N-2$，并按这个顺序，如果 $A_i>A_{i+1}$，那么我们就交换这两个数的位置。众所周知任何序列经过有限趟扫描后一定可以按非降顺序排好序。对于一个序列 $A$，我们定义**用冒泡排序的扫描趟数**为使用如上算法使得 $A$ 排好序的情况下所扫描的趟数。

JOI 君有一个长度为 $N$ 的序列 $A$。他打算处理 $Q$ 次修改 $A$ 的值的询问。更明确地说，在第 $(j+1)\ (0\le j\le Q-1)$ 次询问，$A_{X_j}$ 的值会变为 $V_j$。

JOI 君想知道处理每次修改之后，用冒泡排序的扫描趟数。

inputFormat:
LOJ 上为交互题，方便起见，这里使用传统题的方式进行评测。

第一行两个整数 $N,Q$。

第二行 $N$ 个整数 $A_0,A_1,\ldots ,A_{N-1}$。

接下来 $Q$ 行，每行两个整数 $X_j,V_j$。

outputFormat: 输出 $Q$ 行，第 $(j+1)\ (0\le j\le Q-1)$ 行表示处理第 $(j+1)$ 个询问后，对这个序列冒泡排序的扫描趟数。


title: [ICPC2020 Nanjing R] Ah, It's Yesterday Once More

description:
In 2018, hosted by Nanjing University of Aeronautics and Astronautics (NUAA), the $\textit{International Collegiate Programming Contest}$ (ICPC) regional was held in Nanjing again after a few years' gap. There were over $400$ teams in the contest and team $\textit{Power of Two}$ from Tsinghua University won the champion.

Two years have passed and after the great success in 2018 and 2019, NUAA continues to hold the ICPC Nanjing Regional in 2020. Although we can't gather in Nanjing this time due to the pandemic, we should still be grateful for the hard work done by all staff and volunteers for this contest. Thank you all for your great contribution to this contest!

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

In the 2018 contest, problem K, $\textit{Kangaroo Puzzle}$, requires the contestants to construct an operation sequence for the game. Let's first recall the content of that problem:

> The puzzle is a grid with $n$ rows and $m$ columns ($1 \le n, m \le 20$) and there are some (at least $2$) kangaroos standing in the puzzle. The player's goal is to control them to get together. There are some walls in some cells and the kangaroos cannot enter the cells with walls. The other cells are empty. The kangaroos can move from an empty cell to an adjacent empty cell in four directions: up, down, left, and right. It's guaranteed that kangaroos can reach from any empty cell to any other empty cells by going through adjacent empty cells. It is also guaranteed that there is no cycle in the puzzle -- that is, it's impossible that one kangaroo can move from an empty cell, pass by several distinct empty cells, and then back to the original cell.
>
> There is exactly one kangaroo in every empty cell in the beginning and the player can control the kangaroos by pressing the button U, D, L, R on the keyboard. The kangaroos will move simultaneously according to the button you press. For instance, if you press the button R, a kangaroo would move one cell to the right if it exists and is empty, and will stay still if it does not exist or is not empty.
>
> In this problem, the contestant needs to construct an operating sequence of at most $5 \times 10^4$ steps consisting of U, D, L, R only. If after operating these steps in order there are still two kangaroos standing in different cells, the contestant will be given a `Wrong Answer` verdict.

Our dear friend, Kotori, also took part in the contest and submitted a code of randomized algorithm. To her surprise, this simple solution is judged as a correct answer. We now present her solution as follows:

```cpp
#include <bits/stdc++.h>
using namespace std;
string s = "UDLR";
int main()
{
  srand(time(NULL));
  for (int i = 1; i <= 50000; i++) putchar(s[rand() % 4]);
  return 0;
}
```

For contestants who are not familiar with C and C++: the above code will output a random string of length $5 \times 10^4$ consisting only of characters `U`, `D`, `L` and `R`, where each character has equal probability to appear in each position in the string.

Kotori suspects that things might not be that simple for this problem, so right now, in this $\textit{2020 ICPC Nanjing Regional}$ contest, you need to construct an input data to hack her solution. Due to the randomness, your input data only needs to satisfy a successful hacking rate of at least $25\%$.

Formally speaking, we've prepared $500$ randomly generated strings that each character has equal probability to appear in each position and will use them as the controlling sequence against your answer. For your answer to be accepted, there should be at least $125$ times that after using your answer as the map of cells and the whole controlling sequence is executed, there are still kangaroos in different cells.

Note that your input data should be completely legal. That is to say:

- The map in your answer should not be larger than $20 \times 20$;
- Your answer should contain at least two empty cells;
- All empty cells in your answer should be reachable starting from any empty cell;
- No cycles consisting of empty cells are allowed.

inputFormat: There is no input for this problem. You're on your own!

outputFormat:
You should first output one line containing two integers $n$ and $m$ ($1 \le n, m \le 20$) separated by a space, indicating the number of rows and columns of the map in your answer.

You should then output $n$ lines where the $i$-th line contains a binary string $s_{i,1}s_{i,2}\cdots s_{i,m}$ ($s_{i,j} \in \{\text{`0'}, \text{`1'}\}$) of length $m$. If $s_{i,j} = \text{`1'}$ then the cell in the $i$-th row and the $j$-th column is empty; Otherwise that corresponding cell contains a wall and cannot be entered.

Note again that your answer only need to achieve a successful hacking rate of at least $25\%$. Not that hard isn't it?

translation:
### 题目描述
2018 年，由南京航空航天大学主办的 $\textit{国际大学生程序设计竞赛}$（ICPC）地区赛时隔数年再次在南京举行。来自清华大学的 $\textit{Power of Two}$ 队获得了冠军。

两年过去了，在 2018 年和 2019 年取得巨大成功后，南京航空航天大学继续在 2020 年举办 ICPC 南京赛区的比赛。虽然这次由于疫情的影响，我们不能齐聚南京，但我们仍然应该感谢所有工作人员和志愿者为这次比赛付出的辛勤劳动。感谢你们为本次比赛做出的巨大贡献！

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

在 2018 年的竞赛中 K 题 $\textit{Kangaroo Puzzle}$ 中，要求参赛者为游戏构建一个操作序列。让我们先回顾一下该问题的内容：

> The puzzle is a grid with $n$ rows and $m$ columns ($1 \le n, m \le 20$) and there are some (at least $2$) kangaroos standing in the puzzle. The player's goal is to control them to get together. There are some walls in some cells and the kangaroos cannot enter the cells with walls. The other cells are empty. The kangaroos can move from an empty cell to an adjacent empty cell in four directions: up, down, left, and right. It's guaranteed that kangaroos can reach from any empty cell to any other empty cells by going through adjacent empty cells. It is also guaranteed that there is no cycle in the puzzle -- that is, it's impossible that one kangaroo can move from an empty cell, pass by several distinct empty cells, and then back to the original cell.
>
> There is exactly one kangaroo in every empty cell in the beginning and the player can control the kangaroos by pressing the button U, D, L, R on the keyboard. The kangaroos will move simultaneously according to the button you press. For instance, if you press the button R, a kangaroo would move one cell to the right if it exists and is empty, and will stay still if it does not exist or is not empty.
>
> In this problem, the contestant needs to construct an operating sequence of at most $5 \times 10^4$ steps consisting of U, D, L, R only. If after operating these steps in order there are still two kangaroos standing in different cells, the contestant will be given a ``Wrong Answer'' verdict.

我们的好友 Kotori 也参加了比赛，并提交了随机算法代码。令她惊讶的是，这个简单的解决方案竟然被评为正确答案。现将她的解决方案介绍如下：

```cpp
#include <bits/stdc++.h>
using namespace std;
string s = "UDLR";
int main()
{
  srand(time(NULL));
  for (int i = 1; i <= 50000; i++) putchar(s[rand() % 4]);
  return 0;
}
```

对于不熟悉 C 和 C++ 的参赛者：上述代码将输出一个长度为 $5 \times 10^4$ 的随机字符串，该字符串仅由字符 `U`、`D`、`L` 和 `R` 组成，其中每个字符在字符串中每个位置出现的概率相等。

Kotori 怀疑这个问题可能没那么简单，所以现在，在这个 $\textit{2020 ICPC 南京赛区}$ 竞赛中，你需要构建一个输入数据来破解她的解决方案。由于随机性，你的输入数据只需满足至少 $25\%$ 的 hack 成功率即可。

从形式上讲，我们准备了 $500$ 个随机生成的字符串，每个字符在每个位置出现的概率相等，并将它们用作对您的答案的控制序列。为了使您的答案被接受，在使用您的答案作为单元格映射并执行整个控制序列后，至少应该有 $125$ 个的不同单元格中有袋鼠。

请注意，您的输入数据必须完全合法。也就是说:

- 答案中的地图不应大于 $20 × 20$；
- 您的答案应至少包含两个空单元格；
- 答案中的所有空单元格都应可以从任意空单元格出发到达；
- 不允许包含空单元格的环（也就是说，空单元格组成一棵树）。

hint:
### Note
The sample output we provide you is (obviously) incorrect. It only serves the purpose of showing you the output format. This is a $3 \times 4$ map with $4$ walls, so there will be $8$ kangaroos in the empty cells at the beginning.


title: [ICPC2020 Nanjing R] Baby's First Suffix Array Problem

description:
A suffix array for string $s$ of length $n$ is a permutation $sa$ of integers from $1$ to $n$ such that $s[sa_1.. n], s[sa_2..n], \dots, s[sa_n..n]$ is the list of non-empty suffixes of $s$ sorted in lexicographical order. The rank table for suffixex of $s$ is a permutation $rank$ of integers from $1$ to $n$ such that $rank_{sa_i} = i$.

Kotori has a string $s=s_1s_2\dots s_n$. She would like to ask $m$ queries. And in the $i$-th query, a substring $x=s[l_i..r_i]$ of $s$ is given, Kotori would like to know the rank of suffix $s[k_i..r_i]$ of $x$.

Note $s[l..r]$ means the substring of $s$ which starts from the $l$-th position and ends at the $r$-th position, both inclusive.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 5 \times 10^4$) -- the length of the string and the number of queries.

The second line contains a string $s$ of length $n$ consisting only of lowercase English letters.

Each of the next $m$ lines contains three integers $l_i$, $r_i$ and $k_i$ ($1 \le l_i \le r_i \le n, l_i \le k_i \le r_i$) denoting a query.

It is guaranteed that neither the sum of $n$ or the sum of $m$ of all test cases will exceed $5 \times 10^4$.

outputFormat: For each query output one line containing one integer denoting the answer.

translation:
有一个长度为 $n$ 的字符串 $s=[s_1,s_2,..,s_n]$，有 $m$ 个询问，每个询问给定 $l,r,k$，现将 $s$ 的子串 $[s_l,..,s_r]$ 的 $r-l+1$ 个后缀字符串按字典序从小到大排序，问 $[s_k,..,s_r]$ 在其中的排名。

有 $T$ 组数据。

数据保证 $1 \leq n,m,\sum n,\sum m \leq 5 \times 10^4$；对于每组询问，保证 $1 \leq l \leq k \leq r \leq n$。


title: [ICPC2020 Nanjing R] Certain Scientific Railgun

description:
Misaka Mikoto is the third-ranked Level 5 esper in $\textit{Academy City}$ and has been nicknamed $\textit{Railgun}$ due to her signature move. One day, several evil robots invade Academy City and Misaka is planning to terminate all of them.

Consider Academy City as a 2-dimensional plane. There are $n$ robots in total and the position of the $i$-th robot is $(x_i, y_i)$. Misaka will start moving from $(0, 0)$ and her railgun ability will terminate all robots sharing the same $x$- or $y$-coordinate with her. More formally, if Misaka is now located at $(x_m, y_m)$, all robots whose $x_i = x_m$ or $y_i = y_m$ will be terminated.

As Misaka hates decimals and Euclidean geometry, she will only move from one integer point to another integer point and can only move horizontally (parallel to the $x$-axis) or vertically (parallel to the $y$-axis). As moving among the city is quite tiresome, Misaka asks you to calculate the minimum distance she has to move to terminate all robots.

Recall that an integer point is a point whose $x$-coordinate and $y$-coordinate are both integers.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \leq n \leq 10^5)$ indicating the number of robots.

For the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) indicating the position of the $i$-th robot.

It is guaranteed that the sum of $n$ of all test cases will not exceed $10^5$.

outputFormat: For each test case output one line containing one integer indicating the minimum distance Misaka needs to move to terminate all robots.

translation:
平面上有 $n$ 个点。御坂美琴初始位于 $(0,0)$。她可以随意平行于 $x$ 轴或 $y$ 轴移动，并可以在任意位置使用电磁炮消灭所有 $x$ 或 $y$ 坐标与她相同的点。要消灭所有点，求她最小的移动距离。

$T$ 组数据，$n,\sum n\le 10^5$，$|x_i|,|y_i|\le 10^9$。

hint:
### Note

For the second sample test case, Misaka should first go to $(0, 1)$, then to $(0, 2)$, then to $(0, -3)$, then to $(0, -4)$.

For the third sample test case, Misaka should first go to $(1, 0)$, then to $(1, 1)$, then to $(3, 1)$.


title: [语言月赛 202309] 等式判断

description:
给出三个整数 $a,b,c$，保证 $b \neq 0$。

- 如果 $a + b = c$，请你输出 $\texttt{plus}$。
- 如果 $a - b = c$，请你输出 $\texttt{minus}$。
- 如果以上两条均不满足，请输出 $\texttt{illegal}$。

inputFormat: 输入只有一行三个整数，依次表示 $a,b,c$。

outputFormat: 输出一行一个字符串表示答案。

samples:
1 2 3
plus

samples:
3 2 1
minus

samples:
1 1 4
illegal

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

对全部的测试点，保证 $-2^{31} \leq a,b,c < 2^{31}$，$b \neq 0$。


title: [JOI Open 2018] 猫或狗

background: **特别提醒，由于洛谷交互机制的特殊性，你不能在程序中引用 `catdog.h`，只需要实现要求的几个函数即可。**

description:
你的儿子 JOI 君喜欢养宠物。在你家的花园里有 $N$ 个小屋可供饲养宠物，这 $N$ 个房子从 $1$ 到 $N$ 编号。有 $N-1$ 条双向路径双向连接这 $N$ 个小屋，并且对于任意两个小屋，都可以通过某些路径在它们之间移动。每个小屋最多可以住一只宠物。

JOI 君想要养猫和狗，但是他很担心宠物们可能会经常打架。对于每个小屋的如下状态：住了一只猫，住了一只狗，没有住宠物，他都按如下方式定义了花园的**危险级别**：

- 对于每只猫和每只狗，为了不让他们通过未阻塞的道路相遇，需要阻塞的最小路径数。

在定义危险级别后，JOI 君开始指定后 $Q$ 天使用花园的计划。初始时，所有小屋里都没有宠物。第 $i$ 天的计划是如下内容中的一个：

- 在目前没有宠物的小屋 $v$ 中养一只猫。
- 在目前没有宠物的小屋 $v$ 中养一只狗。
- 将小屋 $v$ 中的宠物送给邻居，这意味着在小屋 $v$ 中就没有宠物了。

你作为家长，有责任检查你的儿子的计划是否危险。更确切地说，你需要求出这 $Q$ 天每天进行完计划后，这个花园的危险级别。

---

**为了在线地回答询问，本题采用交互的方式进行评测。**

你需要实现四个函数 `initialize`，`cat`，`dog` 和 `neighbor`。

最初，函数 `initialize` 被调用。这个函数的作用是接受花园的信息。

- `initialize(N, A, B)`
  - $N$：花园中小屋的数量。
  - $A, B$：长度为 $N-1$ 的数组。意味着对于 $0\le i\le N-2$，在小屋 $A_i$ 和小屋 $B_i$ 之间存在一条路径。保证对于任意两个不同的小屋，沿某些路径可以在它们之间移动。

然后，对于这 $Q$ 天的计划，按时间顺序会调用如下函数：

- `cat(v)`：调用此函数，在目前没有宠物的小屋 $v$ 中养一只猫。
- `dog(v)`：调用此函数，在目前没有宠物的小屋 $v$ 中养一只狗。
- `neighbor(v)`：调用此函数，让小屋 $v$ 中的宠物离开。

这些函数应返回在这个计划执行后花园的危险值。

目前不支持对 Java 和 Pascal 语言提交的测评。

inputFormat:
样例交互器按如下格式读取输入：

第一行一个整数 $N$。

接下来 $N-1$ 行，每行两个整数 $A_i,B_i$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $T_j,v_j$。

这里，如果在第 $j$ 天的调用是 $\texttt{cat}$，则 $T_j=1$，如果是 $\texttt{dog}$，则 $T_j=2$，如果是 $\texttt{neighbor}$，则 $T_j=3$。

outputFormat:
样例交互器按如下格式输出第 $j$ 天的函数调用结果 $D_j$：

第 $j$ 行输出 $D_j$。

hint:
**【样例】**

考虑有 $5$ 个小屋和 $4$ 条路径的情况。这四条路径连接小屋 $1$ 和小屋 $2$，小屋 $2$ 和小屋 $3$，小屋 $2$ 和小屋 $4$，小屋 $4$ 和小屋 $5$。

1. 假设他首先在小屋 $3$ 养了一只猫，在小屋 $5$ 养了一只狗。通过阻塞小屋 $2$ 和小屋 $4$ 之间的道路，他可以避免猫和狗相遇。因此，此时的危险等级是 $1$。
2. 假设他之后在小屋 $2$ 养了一直新猫，在小屋 $1$ 养了一只新狗。通过阻塞小屋 $2$ 和小屋 $4$ 之间的道路与小屋 $1$ 和小屋 $2$ 之间的道路，他可以避免猫和狗相遇。因此，此时的危险等级是 $2$。
3. 假设他最后将小屋 $2$ 的猫给了邻居。他只需要阻塞小屋 $2$ 和小屋 $3$ 之间的道路。因此，此时的危险等级是 $1$。

**【数据范围】**

本题有三个子任务。每个子任务的分值与附加限制如下表所示：

| 子任务编号 | 分值 |         $N$          |         $Q$          |
| :--------: | :--: | :------------------: | :------------------: |
|    $1$     | $8$  |    $1\le N\le 15$    |   $1\le Q\le 100$    |
|    $2$     | $30$ |  $1\le N\le 1\ 000$  |  $1\le Q\le 1\ 000$  |
|    $3$     | $62$ | $1\le N\le 100\ 000$ | $1\le Q\le 100\ 000$ |


title: [JOI Open 2018] 山体滑坡

description:
I 先生有一个 $C$ 天的电缆建设计划。第 $(i+1)\ (0\le i\le C-1)$ 天的计划用三个整数 $T_i,X_i,Y_i$ 表示，分别表示：

- 如果 $T_i=0$，他们会架设一段连接城镇 $X_i$ 与城镇 $Y_i$ 的电缆。保证在第 $(i+1)$ 天开始的时候城镇 $X_i$ 与城镇 $Y_i$ 之间没有电缆。
- 如果 $T_i=1$，他们会拆除一段连接城镇 $X_i$ 与城镇 $Y_i$ 的电缆。保证在第 $(i+1)$ 天开始的时候城镇 $X_i$ 与城镇 $Y_i$ 之间有电缆。

JOI 国经常发生山体滑坡。如果在城镇 $x$ 与 $x+1\ (0\le x\le N-2)$ 之间发生山体滑坡，则只有连接两端编号均不超过 $x$ 与编号均不少于 $x+1$ 城镇的电缆可用。在 JOI 国，每当山体滑坡发生，他们就会选择一些城镇建设基站。基站应满足对于任意城镇，都可以通过一些可用的电缆与基站连通。

I 先生在建设阶段就在考虑山体滑坡发生时应建设多少基站。他有 $Q$ 个问题：第 $(j+1)$ 个问题用两个整数 $W_j,P_j$ 表示，表示他想知道在 $(W_j+1)$ 天结束时，如果在城镇 $P_j$ 和 $P_j+1$ 之间发生山体滑坡，至少应该建立多少基站。

你作为 I 先生的助理，负责写一个程序去回答 I 先生的问题。

inputFormat:
LOJ 上为交互题，方便起见，这里使用传统题的方式进行评测。

第一行三个整数 $N,C,Q$。

接下来 $C$ 行，每行三个整数 $T_i,X_i,Y_i$。

接下来 $Q$ 行，每行两个整数 $W_j,P_j$。

outputFormat: 输出 $Q$ 行，第 $j+1$ 行输出 $D_j$ 表示对第 $(j+1)$ 个问题的回答。


title: [信息与未来 2015] 求回文数（加强版）

outputFormat: 一个整数，即 $1\sim n$ 中全部回文数的个数，答案对 $20091119$ 取模。


title: [信息与未来 2015] 连续数的和（加强版）

background: 注意原版的一般方法在加强版最多获得 $30\sim 40\text{pts}$。

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

outputFormat: 一行一个整数，即 $1\sim n$ 中连续 $k$ 个数的和为平方数的个数。


title: [JOI Open 2018] 木琴

background:
**特别提醒，由于洛谷交互机制的特殊性，你不能在程序中引用 `xylophone.h`，而需要把 `xylophone.h` 中的内容加入文件的开头。即，在程序中 `solve` 函数的前面加入以下几行语句：**

```cpp
void solve(int N);
int query(int s, int t);
void answer(int i, int a);
```

description:
木琴是一种乐器，人可以通过敲击木条来演奏它。单个木条总是发出同样音高的音，因此一个木琴包含不同种音高的木条。

JOI 君买了一个有 $N$ 个木条的木琴。这 $N$ 个木条排成一排，从左到右编号为 $1$ 到 $N$。编号为 $i\ (1\le i\le N)$ 的木条能发出音高为 $A_i\ (1\le A_i\le N)$ 的音。不同的木条发出不同音高的音。他知道音高最低的木条要比音高最高的编号小。

因为 JOI 君不知道每个木条的音高是什么，他决定研究这些木条的音高。

JOI 有一种独特的音感，当他连续听到多个音时，他能分辨出最高音和最低音差多少。他可以一次敲击一些木条，然后听它们发出的声音。也就是说，对于两个整数 $s$ 和 $t\ (1\le s\le t\le N)$，他可以连续敲击编号从 $s$ 到 $t$ 的木条，以知道 $A_s,A_{s+1},\ldots ,A_t$ 中最大值与最小值的差。

他想在 $10\ 000$ 次敲击之内知道每个木条的音高。

---

**【实现细节】**

你需要实现函数 `solve` 以求出每个木条的音高。

- `solve(N)`

  - $N$：木条的数量。
  - 这个函数每个测试点调用恰好一次。

你的程序可以调用评分器实现的如下函数。

- `query(s, t)`

  这个函数返回在给定区间中木条音高最大值与最小值的差。

  - $s, t$：$s$ 是要敲击的木条区间中第一个数，$t$ 是最后一个数。也就是说，你需要敲击编号在 $[s,t]$ 区间内的所有木条。
  - 必须保证 $1\le s\le t\le N$。
  - 你不能调用 `query` 函数超过 $10\ 000$ 次。
  - 如果上述条件不满足，你的程序会被判为 **Wrong Answer**。

- `answer(i, a)`

  你的程序应当用这个函数回答每个木条的音高。

  - $i, a$：这意味着你回答了 $A_i$ 的值为 $a$，其中 $A_i$ 指木条 $i$ 的音高。
  - 必须保证 $1\le i\le N$。
  - 你不能对于相同的 $\texttt i$ 调用超过一次这个函数。
  - 你必须在函数 $\texttt{solve}$ 结束前调用恰好 $N$ 次此函数。
  - 如果上述条件不满足，你的程序会被判为 **Wrong Answer**。
  - 如果你的回答与实际音高有不同，你的程序会被判为 **Wrong Answer**。

暂不支持 Java 与 Pascal 提交的测评。


title: [ICPC2020 Nanjing R] Fireworks

description:
Kotori is practicing making fireworks for the upcoming hanabi taikai$^1$. It takes her $n$ minutes to make a single firework, and as she is not really proficient in making fireworks, each firework only has a probability of $p \times 10^{-4}$ to be perfect.

After she finishes making a firework, she can just start making the next firework, or take $m$ minutes to light all the remaining fireworks finished before. If there is at least one perfect firework among the lit ones, she will be happy and go to rest. Otherwise, she will continue practicing. Can you tell her the minimum expected practicing time before she goes to rest if she takes the optimal strategy?

Notice that no matter how many fireworks remain, it always takes $m$ minutes to light them all.

$^1$ Hanabi taikai: Romaji of the Japanese word ``花火大會``, which means the firework... err... party?

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case:

The first and only line contains three integers $n$, $m$ and $p$ ($1 \le n, m \le 10^9$, $1 \le p \le 10^4$).

outputFormat:
For each test case, output one line containing one number indicating the minimum expected practicing time.

Your answer will be considered correct if and only if the absolute or relative error does not exceed $10^{-4}$.

translation:
Kotori 正在制作烟花。她制作一支烟花需要 $n$ 分钟，每支烟花有 $p\times 10 ^ {-4}$ 的概率是完美的。

当 Kotori 制作好一支烟花时，她可以选择继续制作，也可以选择用 $m$ 分钟点燃所有烟花。如果其中有完美的烟花，那么她会很开心，并停下来休息，否则她会继续制作烟花。你能告诉她在最优策略下，最少期望多长时间才能停下来休息吗？

注意，无论已经制作好了多少支烟花，Kotori 都需要 $m$ 分钟将它们点燃。

多组数据，$1\leq T, p\leq 10 ^ 4$，$1\leq n, m\leq 10 ^ 9$。要求相对误差或绝对误差不超过 $10 ^ {-4}$。


title: [ICPC2020 Nanjing R] Go

description:
$\textit{Go}$ is an adversarial game with the objective of surrounding a larger total area of the board with one's stones than the opponent's. The core idea of the game is the concept of $\textit{liberty}$, which is an open point, or rather, an intersection of vertical and horizontal lines on the chessboard with no stones on it, bordering the group.

A stone, white or black, is called $\textit{alive}$ if it has at least one liberty directly orthogonally adjacent (up, down, left, or right), or must be in the same connected group with a stone of the same color which is alive. We say two stones of the same color are directly connected if they're orthogonally adjacent. We say two stones $s_1$ and $s_k$ of the same color are in the same connected group if there exists a sequence of stones $s_1, s_2,\cdots, s_k$ such that for all $1 \le i < k$, $s_{i-1}$ and $s_i$ are of the same color and are directly connected.

For example, in the left part of the below figure, neither of the two white stones is alive, as they're captured by the surrounding black stones; While in the right part, the rightmost white stone is also not alive, even if the leftmost black stone is also not alive.

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

Given a chessboard with $n$ vertical and $n$ horizontal lines where some stones might be lying on, please calculate the number of white stones captured by the black ones (that is to say, calcaulate the number of white stones not alive). The results for the above examples are $2$ and $1$, respectively.

However, our dear friend Kotori thinks that this problem is too simple for our clever contestants to solve, so she would like to heat things up by instead asking you to flip the color of each stone (that is to say, change a black stone to a white one, or vice versa$^1$) independently and find out the corresponding answer after each flip.

By flipping independently we mean that before flipping the color of a stone, the other stones should change back to their original color. Also note that the data in this problem is not from the real world, which means that the size of the chessboard is not necesssarily $19 \times 19$, and the number of white and black stones can be any integer.

$^1$ Vice versa: The reverse is also true. Here it can be replaced with ``change a white stone to a black one``. This is a very common phrase in modern English especially in academic writing, so please bear it in mind.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains one integer $n$ ($2\le n \le 10^3$) indicating the length of the board side.

For the next $n$ lines, the $i$-th line contains a string $s_{i,1},s_{i,2},\cdots,s_{i,n}$ ($s_{i,j}$ $\in$ $\{\text{`x' (ascii: 120)}$, $\text{`o' (ascii: 111)}$, $\text{`.' (ascii: 46)}\}$), where $s_{i,j} = \text{`x'}$ indicates that the intersection on the $i$-th row and the $j$-th column contains a black stone. Similarly $s_{i, j} = \text{`o'}$ for a white stone and $s_{i,j} = \text{`.'}$ for an empty intersection.

It's guaranteed that the sum of $n$ over all test cases does not exceed $5 \times 10^3$.

outputFormat:
For each test case output an integer $E$ modulo $(10^9 + 7)$ which is the answer encoded as follows:
- Sort all the stones with their row number (from top to bottom) as the primary sort key and their column number (from left to right) as the secondary sort key;
- $E=\sum \limits_{i=1}^m (10^6 + 7)^{m-i}a_i$, where $m$ is the number of stones and $a_i$ is the number of white stones not alive after flipping the color of the $i$-th stone.

$\underline{\text{NOTE that the MODULUS and the BASE are} \textbf{ DIFFERENT}}$. (We're begging you to notice this sentence. If this is not a pdf file I would rather it flashes and twinkles like crazy.)

translation:
### 题目描述

**围棋**是一种对抗性游戏，目的是用自己的石头比对手的石头包围更大的棋盘总面积。游戏的核心理念是**自由**，即一个开放点，或者更确切地说，是棋盘上垂直线和水平线的交叉点，上面没有石头，与群体接壤。

一个白色或黑色的石头，如果它至少有一个直接正交相邻的自由（上、下、左或右），或者必须与一块有生命的相同颜色的石头在同一个连接组中，那么它是有生命的，被称为**活着**。我们说，如果两块颜色相同的石头正交相邻，它们就直接相连。如果存在一系列石头 $s_1,s_2,…,s_k$ ，对于所有 $1\leq i<k$ ， $s_{i-1}$ 和 $s_i$ 颜色相同且正交相邻，则相同颜色的两块石头 $s_1$ 和 $s_k$ 属于同一连通组。

例如，在下图的左侧，两块白色的石头都没有活着，因为它们被周围的黑色石头捕获了；而在右边的部分，最右边的白色石头也没有生命，即使最左边的黑色石头也没有。

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

给定一个有 $n$ 条垂直线和 $n$ 条水平线的棋盘，其中可能有一些石头躺在上面，请计算黑色石头捕获的白色石头的数量（也就是说，计算没有生命的白色石头数量）。上述例子的结果分别为 $2$ 和 $1$ 。

然而，我们亲爱的朋友 Kotori 认为这个问题让我们聪明的参赛者解决太简单了，所以她想让你独立翻转每块石头的颜色（也就是说，把黑色的石头变成白色的石头，反之亦然$^1$），并在每次翻转后找到相应的答案。

独立翻转的意思是，在翻转石头的颜色之前，其他石头应该变回原来的颜色。还要注意，这个问题中的数据不是来自真实世界，这意味着棋盘的大小不一定是 $19×19$ ，黑白石头的数量可以是任意整数。

$^1$反之亦然：在这里，它可以用 ```把白色的石头变成黑色的石头``` 来代替。这是现代英语中非常常见的短语，尤其是在学术写作中，所以请记住。

### 输入格式

有多个测试样例。输入的第一行包含一个整数 $T$ 表示测试样例的数量。对于每个测试样例：

第一行包含一个整数 $n$ ($2\leq n\leq 10^3$)，表示棋盘的边长。

对于接下来 $n$ 行，第 $i$ 行包含一个字符串 $s_{i,1},s_{i,2},…,s_{i,n}$ 。其中 $s_{i,j}=‘x’$ 表示第 $i$ 行第 $j$ 列有一个黑石头，$s_{i,j}=‘o’$ 表示第 $i$ 行第 $j$ 列有一个白石头，$s_{i,j}=‘.’$ 表示第 $i$ 行第 $j$ 列是空的。

保证所有测试样例的 $n$ 之和不超过 $5×10^3$ 。

### 输出格式

对于每个测试用例输出一个整数 $E\bmod10^9+7$ 作为如下编码的答案：

- 对所有石头进行排序，以其行号（从上到下）为第一关键字，以其列号（从左到右）为第二关键字；
- $E=\sum\limits_{i=1}^m(10^6+7)^{m-i}a_i$ ，其中 $m$ 是石头的数量， $a_i$ 是翻转第 $i$ 次颜色后没有生命的白色石头的数量。

$\underline{\textbf{注意}\text{：\textsf{模数}和\textsf{基数}是}\textbf{不同}{的}}$ 。（我们恳求你注意这句话。如果这不是 pdf 文件，我宁愿它像疯了一样闪烁。）

### 说明/提示

对于第二个测试样例，按照 $(1,2),(2,1),(2,2),(2,3),(3,1),(3,2)$ 的顺序翻转石头后，死亡的白色石头数量分别为 $1,0,1,2,0,0$ 。

对于第三个测试样例，棋盘上的所有石头，无论是黑色还是白色，都不是活着的。

hint:
For the second sample test case, after flipping the stones in the order of $(1,2)$, $(2,1)$, $(2,2)$, $(2,3)$, $(3,1)$, $(3,2)$, the number of dead white stones are $1$, $0$, $1$, $2$, $0$, $0$, repectively.

For the third sample test case all stones on the chessboard, black or white, are not alive.


title: [ICPC2020 Nanjing R] Harmonious Rectangle

description:
A vertex-colored rectangle is a rectangle whose four vertices are all painted with colors. For a vertex-colored rectangle, it's harmonious if and only if we can find two adjacent vertices with the same color, while the other two vertices also have the same color with each other.

For example, $\begin{bmatrix} 1 & 0\\ 1 & 0 \end{bmatrix}$, $\begin{bmatrix} 0 & 0\\ 1 & 1 \end{bmatrix}$ and $\begin{bmatrix} 1 & 1\\ 1 & 1 \end{bmatrix}$ are harmonious, while $\begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}$ is not (same number for same color, and different numbers for different colors).

For each point in $\{(x,y) | 1 \le x \le n, 1 \le y \le m, x,y \in \mathbb{Z}\}$, where $\mathbb{Z}$ is the set of all integers, Kotori wants to paint it into one of the three colors: red, blue, yellow. She wonders the number of different ways to color them so that there exists at least one harmonious rectangle formed by the points, whose edges are all parallel to the $x$- or $y$-axis. That is to say, there exists $1 \le x_1 < x_2 \le n$ and $1 \le y_1 < y_2 \le m$ such that

$$\begin{cases}
\text{color}(x_1, y_1) = \text{color}(x_1, y_2)\\
\text{color}(x_2, y_1) = \text{color}(x_2, y_2)\\
\end{cases}
$$
or
$$\begin{cases}
\text{color}(x_1, y_1) = \text{color}(x_2, y_1)\\
\text{color}(x_1, y_2) = \text{color}(x_2, y_2)\\
\end{cases}
$$

where $\text{color}(x, y)$ is the color of point $(x, y)$.

Two coloring plans are considered different if there exists a point having different colors in the two coloring plans.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^4$) indicating the number of test cases. For each test case:

The first and only line contains three integers $n$, $m$($1 \le n, m \le 2 \times 10^3$).

outputFormat: For each test case output one line containing one integer indicating the number of different ways of coloring modulo $(10^9 + 7)$.

translation:
### 题目描述

一个顶点着色的矩形是指四个顶点都被涂上颜色的矩形。对于一个顶点着色的矩形来说，如果我们可以找到两个相邻顶点的颜色相同，而另外两个顶点也互相颜色相同，则称这个矩形是和谐的。

例如，矩阵
$\begin{bmatrix} 1 & 0\\ 1 & 0 \end{bmatrix}$，$\begin{bmatrix} 0 & 0\\ 1 & 1 \end{bmatrix}$ 和 $\begin{bmatrix} 1 & 1\\ 1 & 1 \end{bmatrix}$ 都是和谐的，而 $\begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}$ 不是（相同的颜色有相同的数字，不同的颜色有不同的数字）。

对于集合中的每个点 $\{(x,y) |	1 \le x \le n, 1 \le y \le m, x,y \in \mathbb{Z}\}$，其中 $\mathbb{Z}$ 是所有整数的集合，Kotori 想将其涂成三种颜色之一：红色、蓝色或黄色。她想知道有多少种不同的着色方案，使得至少存在一个由这些点形成的边都平行于 $x$ 或 $y$ 轴的和谐矩形。也就是说，存在 $1 \le x_1 < x_2 \le n$ 和 $1 \le y_1 < y_2 \le m $，满足以下条件之一：

$\begin{cases} \text{color}(x_1, y_1) = \text{color}(x_1, y_2)\\ \text{color}(x_2, y_1) = \text{color}(x_2, y_2)\\ \end{cases}$

或者

$\begin{cases} \text{color}(x_1, y_1) = \text{color}(x_2, y_1)\\ \text{color}(x_1, y_2) = \text{color}(x_2, y_2)\\ \end{cases}$

其中 $\text{color}(x, y)$ 表示点 $(x, y)$ 的颜色。

如果两个着色计划中存在一个点在两个着色计划中颜色不同，那么认为这两个着色计划是不同的。

### 输入格式：
输入包含多个测试用例。第一行输入一个整数 $T$ $(1 \le T \le 10^4)$，表示测试用例的数量。对于每个测试用例：

第一行输入三个整数 $n, m$ $(1 \le n, m \le 2 \times 10^3)$，表示边界的大小。

### 输出格式：
对于每个测试用例，输出一行，包含一个整数，表示着色的不同方案数量模 $(10^9 + 7)$。


title: [ICPC2020 Nanjing R] Interested in Skiing

description:
Kotori is interested in skiing. The skiing field is an infinite strip going along $y$-axis on the 2-dimensional plane where all points $(x, y)$ in the field satisfies $-m \le x \le m$. When skiing, Kotori cannot move out of the field, which means that the absolute value of his $x$-coordinate should always be no more than $m$. There are also $n$ segments on the ground which are the obstacles and Kotori cannot move across the obstacles either.

Kotori will start skiing from $(0, -10^{10^{10^{10^{10}}}})$ (you can regard this $y$-coordinate as a negative infinity) and moves towards the positive direction of the $y$-axis. Her vertical (parallel to the $y$-axis) speed is always $v_y$ which cannot be changed, however she can control her horizontal (parallel to the $x$-axis) speed in the interval of $[-v_x, v_x]$. The time that Kotori changes her velocity can be neglected.

Your task is to help Kotori calculate the minimum value of $v_x^*$ that once $v_x>v_x^*$ she can safely ski through the skiing field without running into the obstacles.

inputFormat:
There is only one test case in each test file.

The first line of the input contains three positive integers $n$, $m$ and $v_y$ ($1 \le n \le 100$, $1 \le m \le 10^4$, $1 \le v_y \le 10$), indicating the number of obstacles, the half width of the skiing field and the vertical speed.

For the following $n$ lines, the $i$-th line contains four integers $x_1$, $y_1$, $x_2$ and $y_2$ ($-m \le x_1, x_2 \le m$, $-10^4 \le y_1, y_2 \le 10^4$, $x_1 \ne x_2$ or $y_1 \ne y_2$) indicating the $i$-th obstacle which is a segment connecting point $(x_1, y_1)$ and $(x_2, y_2)$, both inclusive (that is to say, these two points are also parts of the obstacle and cannot be touched). It's guaranteed that no two obstacles intersect with each other.

outputFormat:
Output one line containing one number indicating the minimum value of $v_x^*$. If it is impossible for Kotori to pass through the skiing field, output ``-1`` (without quotes) instead.

Your answer will be considered correct if and only if its absolute or relative error does not exceed $10^{-6}$.

translation:
### 题目描述
Kotori 对滑雪很感兴趣。滑雪场是在二维平面上沿着 $y$ 轴无限延伸的直线，其中场中的所有点 $(x,y)$ 满足 $-m\le x\le m$。滑雪时，Kotori 不能离开场地，这意味着他的 $x$ 坐标的绝对值应该始终不超过 $m$。地面上也有 $n$ 个路段是障碍，Kotori 无法越过障碍。

Kotori 将从 $(0, -10^{10^{10^{10^{10}}}})$  开始滑雪（你可以将此 $y$ 坐标视为负无穷大），并朝着 $y$ 轴的正方向移动。她的垂直（平行于 $y$ 轴）速度始终是 $v_y$，此值不变，但是她可以在 $[-v_x, v_x]$ 的间隔内控制她的水平（平行于 $x$ 轴的）速度。Kotori 改变速度的时间可以忽略不计。

你的任务是帮助 Kotori 计算 $v_x^*$ 的最小值，即一旦 $v_x>v_x^*$，她就可以安全地穿过滑雪场而不会遇到障碍物。

### 输入格式

每个测试文件中只有一个测试用例。

输入的第一行包含三个正整数 $n, m$ 和 $v_y$（$1\le n\le 100$，$1\le m\le 10^4$，$1\le v_y\le 10$），分别表示障碍物的数量、滑雪场的半宽和垂直速度。

对于下面的 $n$ 行，第 $i$ 行包含四个整数 $x_1, y_1, x_2$ 和 $y_2$（$-m\le x_1, x_2\le m$，$-10^4\le y_1, y_2\le 10^4$，$x_1\ne x_2$ 或 $y_1\ne y_2$），这四个整数表示第 $i$ 个障碍物，该障碍物是连接点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的线段，两者都包括在内（也就是说，这两个点也是障碍物的一部分，不能触摸）。保证没有两个障碍物相互交叉。

### 输出格式

输出一行，其中包含一个数字，表示 $v_x^*$ 的最小值。如果 Kotori 无法通过滑雪场，请输出 `-1`（不带引号）。

当且仅当其绝对或相对误差不超过 $10^{-6}$ 时，您的答案才会被认为是正确的。

------------

翻译来自 [fire_wolf](https://www.luogu.com.cn/user/690669)。


title: [ICPC2020 Nanjing R] Just Another Game of Stones

description:
Kotori and Umi are playing games of stones, which is hosted by Honoka. The rule is the same as the classic one: There are some piles of stones and the players take turns to remove any positive number of stones from one pile. The one who can't make a legal move loses the game.

This time however, things will be a little different. As the host, Honoka will prepare the games from $n$ candidate piles of stones, where the $i$-th pile initially has $a_i$ stones. Honoka will perform $q$ operations of the following two types:

- Given three integers $l$, $r$ and $x$, for all $l \le i \le r$ change the number of stones in the $i$-th candidate pile to $\max(b_i, x)$, where $b_i$ is the current number of stones in the $i$-th candidate pile.
- Given three integers $l$, $r$ and $x$, start a game of stones consisting of $(r-l+2)$ piles where the $i$-th pile contains $b_{l-1+i}$ stones for all $1 \le i < (r-l+2)$, and the $(r-l+2)$-th pile contains $x$ stones. Note that this operation is only querying for answer and will not affect the state of the $n$ candidate piles of stones.

Kotori is always the first to move. As a big fan of Kotori, you would like to know, for each game of stones, the number of ways Kotori can play in the first step to ensure her victory if both players use the best strategy. We consider two ways different if Kotori is taking stones from different piles, or from the same pile but is taking different number of stones.

inputFormat:
There is only one test case in each test file.

The first line of the input contains two integers $n$ and $q$ ($1 \le n, q \le 2 \times 10^5$) indicating the number of candidate piles and the number of operations.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($0 \le a_i \le 2^{30}-1$) where $a_i$ indicates the initial number of stones in the $i$-th pile.

For the following $q$ lines, the $i$-th line contains four integers $op_i$, $l_i$, $r_i$ and $x_i$ ($op_i \in \{1, 2\}$, $1 \le l_i \le r_i \le n$, $0 \le x_i \le 2^{30}-1$) indicating the $i$-th operation, where $op_i$ is the type of operation and the others are the parameters of the operation. Operations are given in the order they're performed.

outputFormat: For each operation of the second type output one line containing one integer indicating the answer.

translation:
给定 $n$ 个石堆，第 $i$ 个石堆的石子数为 $a_i$，有 $q$ 次操作：

`1 l r x` 表示将所有满足 $l \leq i \leq r$ 的 $a_i$ 赋值为 $\max(a_i,x)$。

`2 l r x` 表示用石堆 $[l,r]$ 和一个石子数为 $x$ 的石堆进行 Nim 游戏，求出第一次先手取完石子后游戏变为后手必败局面的可操作总方案数。

（如果你还不了解 Nim 游戏，[点这里](https://oi-wiki.org//math/game-theory/impartial-game/)）。

对于 $100\%$ 的数据保证 $1 \le q,n \le 2 \times 10^5$，$0 \le a_i,x_i \le 2^{30}-1$，$op \in \{1,2\}$，$1 \le l_i,r_i \le n$。

hint:
For the first operation the players will play a game of stones consisting of $1$, $2$, $1$ and $1$ stone(s) in each pile respectively. The only winning play for Kotori is reduce the pile with $2$ stones to $1$ stone.

After the second operation, number of stones in the candidate piles changes to $1$, $3$, $3$, $4$ and $1$ respectively.

For the fourth operation the players will play a game of stones consisting of $1$, $3$, $3$, $4$ and $4$ stone(s) in each pile respectively. The winning plays for Kotori is to reduce the pile with $1$ stone to $0$ stone, or to reduce any pile with $3$ stones to $2$ stones.


title: [ICPC2020 Nanjing R] K Co-prime Permutation

description:
Kotori is very good at math (really?) and she loves playing with permutations and primes.

One day, she thinks of a special kind of permutation named $\textit{k co-prime permutation}$. A permutation $p_1,p_2,\cdots,p_n$ of $n$ is called a $k$ co-prime permutation of $n$ if there exists exactly $k$ integers $i$ such that $1 \le i \le n$ and $\text{gcd}(p_i,i)=1$, where $\text{gcd}(x,y)$ indicates the greatest common divisor of $x$ and $y$.

Given $n$ and $k$, please help Kotori construct a $k$ co-prime permutation of $n$ or just report that there is no such permutation.

Recall that a permutation of $n$ is a sequence of length $n$ containing all integers from $1$ to $n$.

inputFormat:
There is only one test case in each test file.

The first and only line contains two integers $n$ and $k$ ($1 \le n \le 10^6$, $0 \le k \le n$).

outputFormat:
Output one line containing $n$ integers $p_1, p_2, \cdots, p_n$ separated by one space, indicating the permutation satisfying the given constraints. If no such permutation exists output ``-1`` (without quotes) instead. If there are multiple valid answers you can print any of them.

Please, DO NOT output extra spaces at the end of each line, otherwise your answer may be considered incorrect!

translation:
### 题目描述

给定两个整数 $n$ 和 $k$，构造一个 $1 \sim n$ 的排列 $p_1,p_2,\cdots,p_n$，使得存在 $k$ 个整数 $i$ 满足 $1 \le i \le n$ 且 $\text{gcd}(p_i,i)=1$。

$\text{gcd}(x,y)$ 表示 $x$ 和 $y$ 的最大公约数。

### 输入格式

只有一组测试数据。

第一行输入两个整数 $n$ 和 $k$ $(1 \le n \le 10^6, 0 \le k \le n)$。

### 输出格式

输出一行 $n$ 个整数 $p_1, p_2, \cdots, p_n$，用空格分隔，表示一个满足给定的约束的排列。如果没有存在的排列则输出 ``-1``。如果有多个有效的答案，输出任意一个均可。

请不要在行末输出多余的空格，否则你的答案可能会被认为是错误的。

### 样例 #1

#### 样例输入 #1

```
5 3
```

#### 样例输出 #1

```
1 4 5 2 3
```

### 样例 #2

#### 样例输入 #2

```
1 0
```

#### 样例输出 #2

```
-1
```


title: [ICPC2020 Nanjing R] Let's Play Curling

description:
Curling is a sport in which players slide stones on a sheet of ice toward a target area. The team with the nearest stone to the center of the target area wins the game.

Two teams, Red and Blue, are competing on the number axis. After the game there are $(n+m)$ stones remaining on the axis, $n$ of them for the Red team and the other $m$ of them for the Blue. The $i$-th stone of the Red team is positioned at $a_i$ and the $i$-th stone of the Blue team is positioned at $b_i$.

Let $c$ be the position of the center of the target area. From the description above we know that if there exists some $i$ such that $1 \le i \le n$ and for all $1 \le j \le m$ we have $|c - a_i| < |c - b_j|$ then Red wins the game. What's more, Red is declared to win $p$ points if the number of $i$ satisfying the constraint is exactly $p$.

Given the positions of the stones for team Red and Blue, your task is to determine the position $c$ of the center of the target area so that Red wins the game and scores as much as possible. Note that $c$ can be any real number, not necessarily an integer.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) indicating the number of stones for Red and the number of stones for Blue.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$) indicating the positions of the stones for Red.

The third line contains $m$ integers $b_1, b_2, \cdots, b_m$ ($1 \le b_i \le 10^9$) indicating the positions of the stones for Blue.

It's guaranteed that neither the sum of $n$ nor the sum of $m$ will exceed $5 \times 10^5$.

outputFormat: For each test case output one line. If there exists some $c$ so that Red wins and scores as much as possible, output one integer indicating the maximum possible $\textbf{score}$ of Red (NOT $c$). Otherwise output ``Impossible`` (without quotes) instead.

translation:
# [ICPC2020 Nanjing R] Let's Play Curling

## 题目描述

红队和蓝队在冰面上向目标区域滑动冰壶，距离目标区域中心最近的队伍获胜。

两支队伍在一条直线上竞争。比赛结束后，有   $(n+m)$ 个冰壶在直线上, $n$ 个是红队的，剩下 $m$ 个是蓝队的。 红队的第 $i$ 个冰壶被放在 $a_i$ ，蓝队的第 $i$ 个冰壶被放在 $b_i$ 。

设 $c$ 是中心。如果存在一些 $i$ 使得 $1 \le i \le n$ 并且对于所有 $1 \le j \le m$ 都有 $|c - a_i| < |c - b_j|$ 红队就赢得比赛。另外，如果满足条件的 $i$ 的数目是 $p$ ，则认为红队赢得 $p$ 分。

给你红蓝两队的冰壶的位置，请你确定中心 $c$ 的值，使红队得分最多。注意， $c$ 是任意实数，不一定是整数。

## 输入格式

有很多测试样例。第一行输入一个整数 $T$ ，表示样例数量。对于每个测试样列：

第一行包括两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$) 分别表示红队和蓝队的冰壶数量。

第二行包括 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$) 表示红队的冰壶的位置。

第三行包括 $m$ 个整数 $b_1, b_2, \cdots, b_m$ ($1 \le b_i \le 10^9$)表示蓝队的冰壶的位置。

数据保证 $n$ 的总和以及 $m$ 的总和都不会超过 $5 \times 10^5$ 。

## 输出格式

每一个测试样列输出一行。如果存在 $c$ 使得红队获胜且得分最多, 输出一个整数表示红队最大 $\textbf{ 得分 }$ (不是 $c$) 。否则输出 ``Impossible`` ( 不带等号 ) 。

## 样例 #1

### 样例输入 #1

```
3
2 2
2 3
1 4
6 5
2 5 3 7 1 7
3 4 3 1 10
1 1
7
7
```

### 样例输出 #1

```
2
3
Impossible
```

## 提示

对于第一个样例，当 $c = 2.5$ 时，红队的位于 2 和 3 的冰壶可以得分。

对于第二个样例，当 $c = 7$ 时，红队的位于 5 和 7 的冰壶可以得分。

hint:
For the first sample test case we can assign $c = 2.5$ so that the stones at position 2 and 3 for Red will score.

For the second sample test case we can assign $c = 7$ so that the stones at position 5 and 7 for Red will score.


title: [ICPC2020 Nanjing R] Monster Hunter

description:
There is a rooted tree with $n$ vertices and the root vertex is $1$. In each vertex, there is a monster. The hit points of the monster in the $i$-th vertex is $hp_i$.

Kotori would like to kill all the monsters. The monster in the $i$-th vertex could be killed if the monster in the direct parent of the $i$-th vertex has been killed. The power needed to kill the $i$-th monster is the sum of $hp_i$ and the hit points of all other living monsters who lives in a vertex $j$ whose direct parent is $i$. Formally, the power equals to
$$
hp_i + \sum_{\begin{array}{c}\text{the monster in vertex } j \text{ is \bf{alive}} \\ \text{and } i \text{ is the direct parent of } j \end{array}} hp_j
$$

In addition, Kotori can use some magic spells. If she uses one magic spell, she can kill any monster using $0$ power without any restriction. That is, she can choose a monster even if the monster in the direct parent is alive.

For each $m=0,1,2,\cdots,n$, Kotori would like to know, respectively, the minimum total power needed to kill all the monsters if she can use $m$ magic spells.

inputFormat:
There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($2 \le n \le 2 \times 10^3$), indicating the number of vertices.

The second line contains $(n-1)$ integers $p_2,p_3,\cdots,p_n$ ($1 \le p_i < i$), where $p_i$ means the direct parent of vertex $i$.

The third line contains $n$ integers $hp_1,hp_2,\cdots,hp_n$ ($1 \le hp_i \le 10^9$) indicating the hit points of each monster.

It's guaranteed that the sum of $n$ of all test cases will not exceed $2 \times 10^3$.

outputFormat:
For each test case output one line containing $(n+1)$ integers $a_0, a_1, \cdots, a_n$ separated by a space, where $a_m$ indicates the minimum total power needed to kill all the monsters if Kotori can use $m$ magic spells.

Please, DO NOT output extra spaces at the end of each line, otherwise your answer may be considered incorrect!

translation: 给定一棵树和点权 $hp_i$，如果需要标记一个点 $i$ 的话，你会付出 $hp_i$ 再加上**所有 $i$ 的直接子节点的权值**的代价，必须先标记 $i$ 的父节点才能标记 $i$（根节点除外）。你可以使用魔法，每使用一次魔法，可以选择一个**未被标记**的点 $x$ 进行无代价标记（即在 $x$ 的父节点未被标记的时候）。求所有点都被标记掉的最少代价。


title: [ICPC2020 Nanjing R] Degree of Spanning Tree

description:
Given an undirected connected graph with $n$ vertices and $m$ edges, your task is to find a spanning tree of the graph such that for every vertex in the spanning tree its degree is not larger than $\frac{n}{2}$.

Recall that the degree of a vertex is the number of edges it is connected to.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($2 \le n \le 10^5$, $n-1 \le m \le 2 \times 10^5$) indicating the number of vertices and edges in the graph.

For the following $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) indicating that there is an edge connecting vertex $u_i$ and $v_i$. Please note that there might be self loops or multiple edges.

It's guaranteed that the given graph is connected. It's also guaranteed that the sum of $n$ of all test cases will not exceed $5 \times 10^5$, also the sum of $m$ of all test cases will not exceed $10^6$.

outputFormat: For each test case, if such spanning tree exists first output ``Yes`` in one line, then for the following $(n-1)$ lines print two integers $p_i$ and $q_i$ on the $i$-th line separated by one space, indicating that there is an edge connecting vertex $p_i$ and $q_i$ in the spanning tree. If no valid spanning tree exists just output ``No`` in one line.

translation:
### 题目描述

给定一张 $n$ 个点 $m$ 条边的无向图，求一个生成树满足每个点的度数都不大于 $\frac{n}{2}$。

### 输入格式

多组数据，第一行，一个整数 $t$ 代表数据组数。

对于每组数据：

- 第一行两个整数 $n$, $m$，代表边数和点数；
- 接下来 $m$ 行，输入 $u_i,v_i$ 代表一条边（可能有重边和自环）。

### 输出格式

对于每组数据：

第一行输出 `Yes` 或 `No` 代表是否可行。

若可行，接下来 $n - 1$ 行输出每条生成树的边，顺序随意。

### 数据范围

$2 \leq n \leq 10^5$，$n - 1\leq m \leq 2\times10^5$，$\sum n\leq5\times10^5$，$\sum m\leq10^6$。

保证图连通。

hint:
### Note

For the first sample test case, the maximum degree among all vertices in the spanning tree is 3 (both vertex 1 and vertex 4 has a degree of 3). As $3 \le \frac{6}{2}$ this is a valid answer.

For the second sample test case, it's obvious that any spanning tree will have a vertex with degree of 2, as $2 > \frac{3}{2}$ no valid answer exists.


title: [ICPC2020 Nanjing R] Evil Coordinate

description:
A robot is standing on an infinite 2-dimensional plane. Programmed with a string $s_1s_2\cdots s_n$ of length $n$, where $s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$, the robot will start moving from $(0, 0)$ and will follow the instructions represented by the characters in the string.

More formally, let $(x, y)$ be the current coordinate of the robot. Starting from $(0, 0)$, the robot repeats the following procedure $n$ times. During the $i$-th time:

- If $s_i = \text{`U'}$ the robot moves from $(x, y)$ to $(x, y+1)$;
- If $s_i = \text{`D'}$ the robot moves from $(x, y)$ to $(x, y-1)$;
- If $s_i = \text{`L'}$ the robot moves from $(x, y)$ to $(x-1, y)$;
- If $s_i = \text{`R'}$ the robot moves from $(x, y)$ to $(x+1, y)$.-

However, there is a mine buried under the coordinate $(m_x, m_y)$. If the robot steps onto $(m_x, m_y)$ during its movement, it will be blown up into pieces. Poor robot!

Your task is to rearrange the characters in the string in any order, so that the robot will not step onto $(m_x, m_y)$.

inputFormat:
There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $m_x$ and $m_y$ ($-10^9 \le m_x, m_y \le 10^9$) indicating the coordinate of the mine.

The second line contains a string $s_1s_2\cdots s_n$ of length $n$ ($1 \le n \le 10^5$, $s_i \in \{\text{`U'}, \text{`D'}, \text{`L'}, \text{`R'}\}$) indicating the string programmed into the robot.

It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

outputFormat: For each test case output one line. If a valid answer exists print the rearranged string, otherwise print ``Impossible`` instead. If there are multiple valid answers you can print any of them.

translation:
一个机器人位于平面直角坐标系的原点处。给定一串指令，由 `UDLR` 四个字符构成，分别表示向上下左右移动 $1$ 单位长度。

$(m_x, m_y)$ 处埋有地雷，你需要任意重排指令使得机器人不会经过该坐标，判定是否有解并构造方案。

多组数据。指令长度不超过 $10 ^ 5$，长度总和不超过 $10 ^ 6$。

samples:
5
1 1
RURULLD
0 5
UUU
0 3
UUU
0 2
UUU
0 0
UUU

samples:
LDLRUUR
UUU
Impossible
Impossible
Impossible


title: [IOI2023] 封锁时刻

background:
这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。

本题仅支持 C++ 语言提交。

description:
匈牙利有 $N$ 个城市，编号依次为 $0$ 到 $N - 1$。

这些城市之间由 $N - 1$ 条双向道路连接，编号为 $0$ 至 $N - 2$。对每个 $j$（$0 \le j \le N - 2$），第 $j$ 条道路连接城市 $U[j]$ 和城市 $V[j]$，其长度为 $W[j]$，表示这两个城市之间的交通时间为 $W[j]$ 个时间单位。每条道路连接两个不同的城市，且每两个城市之间最多由一条道路连接。

两个不同城市 $a$ 和 $b$ 之间的一条**路径**是一个由不同城市组成的序列 $p_0, p_1, \ldots, p_t$，满足以下条件：
 * $p_0 = a$，
 * $p_t = b$，
 * 对每个 $i$（$0 \le i \lt t$），存在一条道路连接 $p_i$ 和 $p_{i + 1}$。

利用这些道路从任意一个城市到任意一个其他的城市都是有可能的。换言之，任意两个不同城市之间都存在路径。
可以证明两个不同城市之间的路径是唯一的。

一条路径 $p_0, p_1, \ldots, p_t$ 的**长度**是这条路径上连接相邻城市的 $t$ 条道路的长度之和。

在匈牙利，很多人都会在建国日去参加在两个主要城市举行的庆祝活动。当庆祝活动结束时，他们会回家。政府为了防止人群干扰当地人，所以决定在特定时刻封锁城市。每个城市被政府分配一个非负的**封锁时刻**。政府决定所有城市的封锁时刻总和不得超过 $K$。具体来说，对每个 $i$（$0 \leq i \leq N - 1$），分配给城市 $i$ 的封锁时刻是一个非负整数  $c[i]$。所有  $c[i]$ 之和不超过 $K$。

考虑一个城市 $a$ 和某个封锁时刻的分配方案，我们说城市 $b$ 是从城市 $a$ 可达的当且仅当以下两种情况中的任意一种情况成立。

情况 1：$b = a$。

情况 2：这两个城市之间的路径  $p_0, \ldots, p_t$ （$p_0 = a$ 且 $p_t = b$）满足以下条件：
* 路径 $p_0, p_1$ 的长度最多为 $c[p_1]$，并且
* 路径 $p_0, p_1, p_2$ 的长度最多为 $c[p_2]$，并且
* $\ldots$
* 路径 $p_0, p_1, p_2, \ldots, p_t$ 的长度最长为  $c[p_t]$。

今年，两个主要的庆祝地点位于城市 $X$ 和 $Y$。
对于每一个封锁时刻的分配方案，可以定义一个**便利分数**，其定义为下面两个数字之和：
- 从城市 $X$ 可达的城市个数。
- 从城市 $Y$ 可达的城市个数。

注意如果一个城市既能从城市 $X$ 可达也能从城市 $Y$ 可达，那么它在计算便利分数时计算两次。

你的任务是计算能被某个封锁时刻分配方案实现的最大便利分数。

inputFormat:
令 $C$ 表示场景数，即调用 `max_score` 的次数。
评测程序实例按以下格式读取输入：

* 第 $1$ 行：$C$

以下是 $C$ 个场景的描述。

评测程序实例按以下格式读取每个场景的描述：

* 第 $1$ 行：$N \; X \; Y \; K$
* 第 $2 + j$ 行（$0 \le j \le N - 2$）：$U[j] \; V[j] \; W[j]$

outputFormat:
评测程序实例按以下格式为每个场景打印单独一行

* 第 $1$ 行： `max_score` 的返回值

hint:
#### 【实现细节】

你要实现以下函数。

```
int max_score(int N, int X, int Y, int64 K, int[] U, int[] V, int[] W)
```

* $N$：城市的个数
* $X$，$Y$：两个主要庆祝城市
* $K$：封锁时刻总和的上界
* $U$，$V$： 长度为 $N - 1$ 的描述道路连接情况的数组
* $W$：长度为 $N - 1$ 的描述道路长度的数组
* 该函数要返回能被某个封锁时刻分配方案实现的最大便利分数
* 每个测试用例可以多次调用该函数

#### 【例子】

考虑以下调用：

```
max_score(7, 0, 2, 10,
          [0, 0, 1, 2, 2, 5], [1, 3, 2, 4, 5, 6], [2, 3, 4, 2, 5, 3])
```

这对应以下道路网络：

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

假设封锁时刻如下分配：

| **城市**         | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|:----------------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| **封锁时刻** | $0$ | $4$ | $0$ | $3$ | $2$ | $0$ | $0$ |

注意所有封锁时刻之和为 $9$，不超过 $K = 10$。城市 $0$，$1$ 和 $3$ 都是从城市 $X$（$X = 0$）可达的，而城市 $1$，$2$ 和 $4$ 都可以从城市 $Y$（$Y  = 2$）可达。 因此，便利分数为 $3+3 = 6$。不存在封锁时刻分配方案使得便利分数大于 $6$，所以该函数应该返回 $6$。

考虑另外一个调用：

```
max_score(4, 0, 3, 20, [0, 1, 2], [1, 2, 3], [18, 1, 19])
```

这对应以下道路网络：

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

假设封锁时间如下分配：

| **城市**         | $0$ | $1$ | $2$ | $3$ |
|:----------------:|:---:|:---:|:---:|:---:|
| **封锁时刻** | $0$ | $1$ | $19$| $0$ |

城市 $0$ 从城市 $X$（$X = 0$）可达，而城市 $2$ 和 $3$ 都是可以从城市 $Y$（$Y=3$）可达的。因此，便利分数是 $1 + 2 = 3$。不存在封锁时刻分配方案使得便利分数大于 $3$，所以函数应该返回 $3$。

#### 【约束条件】

* $2 \le N \le 200\,000$
* $0 \le X \lt Y \lt N$
* $0 \le K \le 10^{18}$
* $0 \le U[j] \lt V[j] \lt N$ (对每个 $j$ 满足 $0 \le j \le N - 2$)
* $1 \le W[j] \le 10^6$ (对每个 $j$ 满足 $0 \le j \le N - 2$)
* 利用这些道路可以从任意一个城市走到任意另外一个城市。
* $S_N \le 200\,000$，其中 $S_N$ 是所有调用函数 `max_score` 的  $N$ 的总和。

#### 【子任务】

我们说一个道路网络是**线性的**如果道路 $i$ 连接城市 $i$ 和 $i+1$（对每个$0 \le i \le N - 2$ 的 $i$）。

1. （8 分）从城市 $X$ 到城市 $Y$ 的路径长度大于 $2K$。
1. （9 分）$S_N \le 50$，道路网络是线性的。
1. （12 分）$S_N \le 500$，道路网络是线性的。
1. （14 分）$S_N \le 3\,000$，道路网络是线性的。
1. （9 分）$S_N \le 20$
1. （11 分）$S_N \le 100$
1. （10 分）$S_N \le 500$
1. （10 分）$S_N \le 3\,000$
1. （17 分）无额外的约束条件。


title: [IOI2023] 足球场

description:
Debrecen 市有一片正方形的森林名叫 Nagyerdő，可以看作是 $N \times N$ 的方格。
方格的行由北向南从 $0$ 到 $N - 1$ 编号，列由西向东从 $0$ 到 $N - 1$ 编号。
方格中第 $r$ 行第 $c$ 列的格子被称为单元格 $(r, c)$。

森林里的每个单元格要么是**空**的，要么是**有树**的。
森林里至少有一个空单元格。

DVSC 是这个城市最著名的体育俱乐部，目前正计划在森林里修建一座新的足球场。
大小为 $s$ 的球场（这里 $s \ge 1$）是 $s$ 个**互不相同的空**单元格 $(r_0, c_0), \ldots, (r_{s - 1}, c_{s - 1})$ 的集合。
形式化地说，这意味着：

- 对于从 $0$ 到 $s - 1$（包含两端）的每个 $i$，单元格 $(r_i, c_i)$ 是空的；
- 对于满足 $0 \le i \lt j \lt s$ 的每组 $i$ 和 $j$，$r_i \neq r_j$ 和 $c_i \neq c_j$ 二者中至少有一个成立。

踢球时足球在球场的单元格之间传递。
**直传**是以下两种动作之一：

* 球场包含第 $r$ 行中单元格 $(r,a)$ 和 $(r,b)$ 之间的**全部**单元格，球从单元格 $(r,a)$ 传递到单元格 $(r,b)$（$0 \le r,a,b \lt N, a \ne b$）。包含关系的形式化定义为：
  - 若 $a \lt b$，则球场应包含满足 $a \le k \le b$ 的每个单元格 $(r,k)$；
  - 若 $a \gt b$，则球场应包含满足 $b \le k \le a$ 的每个单元格 $(r,k)$。
* 球场包含第 $c$ 列中单元格 $(a,c)$ 和 $(b,c)$ 之间的**全部**单元格，球从单元格 $(a,c)$ 传递到单元格 $(b,c)$（$0 \le c,a,b \lt N, a \ne b$）。包含关系的形式化定义为：
  - 若 $a \lt b$，则球场应包含满足 $a \le k \le b$ 的每个单元格 $(k, c)$；
  - 若 $a \gt b$，则球场应包含满足 $b \le k \le a$ 的每个单元格 $(k, c)$。

如果可以通过至多 $2$ 次直传将球从球场的任意单元格传递到另外的任意单元格，那么称这样的球场是**规则**的。
注意，任何大小为 $1$ 的球场都是规则的。

例如，考虑一片大小为 $N = 5$ 的森林，其中单元格 $(1,0)$ 和 $(4,2)$ 有树，其余单元格均为空。
下图显示了三个可能的球场。有树的单元格用深色表示，组成球场的单元格划有斜线。

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

左边的球场是规则的。然而，中间的球场不是规则的，原因是把球从单元格 $(4,1)$ 传递到单元格 $(4,3)$ 至少需要 $3$ 次直传。右边的球场也不是规则的，原因是无法通过直传将球从单元格 $(3,0)$ 传递到单元格 $(1,3)$。

体育俱乐部希望建造尽可能大的规则球场。
你的任务是找出最大的 $s$ 值，使得森林里可以建造大小为 $s$ 的规则球场。

inputFormat:
你要实现以下函数：

```
int biggest_stadium(int N, int[][] F)
```

* $N$：森林的大小。
* $F$：一个长度为 $N$ 的数组，每个元素都是长度为 $N$ 的数组，用于描述森林里的单元格。对于每组满足 $0 \le r \lt N$ 且 $0 \le c \lt N$ 的 $r$ 和 $c$，$F[r][c] = 0$ 表示单元格 $(r, c)$ 是空的，$F[r][c] = 1$ 表示该单元格是有树的。
* 这个函数应该返回森林里可以建造的规则球场的最大大小。
* 对于每个测试用例，这个函数恰好被调用一次。

outputFormat:
考虑以下调用：

```
biggest_stadium(5, [[0, 0, 0, 0, 0],
                    [1, 0, 0, 0, 0],
                    [0, 0, 0, 0, 0],
                    [0, 0, 0, 0, 0],
                    [0, 0, 1, 0, 0]])
```

这个例子描述的森林显示在下图的左边，一个大小为 $20$ 的规则球场显示在下图的右边：

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

由于不存在大小为 $21$ 或更大的规则球场，函数应该返回 $20$。

hint:
## 约束条件

* $1 \le N \le  2\,000$
* $0 \le F[i][j] \le 1$（对满足 $0 \le i \lt N$ 且 $0 \le j \lt N$ 的所有 $i$ 和 $j$）
* 森林里至少存在一个空单元格。也就是说，对于某组满足 $0 \le i \lt N$ 且 $0 \le j \lt N$ 的 $i$ 和 $j$，有 $F[i][j] = 0$。

## 子任务

1. （6 分）至多只有一个单元格有树。
2. （8 分）$N \le 3$
3. （22 分）$N \le 7$
4. （18 分）$N \le 30$
5. （16 分）$N \le 500$
6. （30 分）没有额外的约束条件。

在每个子任务中，如果你的程序能够正确判定**全部**空单元格组成的集合能否构成一个规则球场，那么你将在该子任务获得 25% 的部分分。

更准确地讲，对于所有空单元格组成的集合是一个规则球场的测试用例，你的解答的得分情况如下：

* 如果返回正确答案（也就是所有空单元格的数量），则得满分；
* 否则得 0 分。

对于所有空单元格组成的集合**不是**一个规则球场的测试用例，你的解答的得分情况如下：

* 如果返回正确答案，则得满分；
* 如果返回所有空单元格的数量，则得 0 分；
* 如果返回其他值，则得 25% 的分数。

每个子任务的得分是这个子任务中所有测试用例得分的最低值。

## 评测程序示例

评测程序示例按以下格式读取输入：

* 第 $1$ 行：$N$
* 第 $2 + i$ 行（$0 \le i \lt N$）：$F[i][0] \; F[i][1] \; \ldots \; F[i][N - 1]$

评测程序示例按以下格式打印你的答案：

* 第 $1$ 行：函数 `biggest_stadium` 的返回值


title: [IOI2023] 山毛榉树

background:
这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 main 函数。

本题仅支持 C++ 语言提交。

description:
Vétyem Woods 是一片著名的缤纷多彩的森林。其中最老最高的一棵山毛榉树叫 Ős Vezér。

树 Ős Vezér 可以被建模成 $N$ 个**结点**和 $N-1$ 条**边**的集合。结点的编号为从 $0$ 到 $N-1$，边的编号为从 $1$ 到 $N-1$。每条边均连接树上两个不同的结点。具体地说，边 $i$（$1 \le i \lt N$）从结点 $i$ 连接到结点 $P[i]$，这里 $0 \le P[i] \lt i$。结点 $P[i]$ 被称为是结点 $i$ 的**父结点**，而结点 $i$ 被称为是结点 $P[i]$ 的一个**子结点**。

每条边都有某种颜色。一共有 $M$ 种可能的颜色，编号为从 $1$ 到 $M$。边 $i$ 的颜色为 $C[i]$。不同的边可能有相同的颜色。

注意，在上面的定义中，$i = 0$ 的情形并不对应树上的边。方便起见，我们令 $P[0] = -1$ 和 $C[0] = 0$。

例如，假定 Ős Vezér 有 $N = 18$ 个结点和 $M = 3$ 种可能的颜色，以及 $17$ 条边。边的描述为 $P = [-1, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 10, 11, 11]$，边的颜色为 $C = [0, 1, 2, 3, 1, 2, 3, 1, 3, 3, 2, 1, 1, 2, 2, 1, 2, 3]$。这棵树如下图所示：

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

Árpád 是一位才华横溢的护林人，他喜欢研究树上被称为**子树**的部分。
对所有满足 $0 \le r \lt N$ 的  $r$，结点 $r$ 的子树是一个满足以下性质的结点集合 $T(r)$：

* 结点 $r$ 属于 $T(r)$。
* 如果某个结点 $x$ 属于 $T(r)$，则 $x$ 的所有子结点都属于$T(r)$。
* 除了上述情况以外，其他结点都不属于 $T(r)$。

集合 $T(r)$ 的大小记作 $|T(r)|$。

Árpád 最近发现了一个复杂但有趣的子树性质。Árpád 的发现需要用到大量的纸和笔做演算，他认为你需要做同样的事情才能完成理解。他还会给你几个例子，让你能够对它们做详细的分析。

假设我们有某个给定的 $r$，以及子树 $T(r)$ 中结点的某个置换 $v_0, v_1, \ldots, v_{|T(r)|-1}$。

对于所有满足 $1 \le i \lt |T(r)|$ 的 $i$，令 $f(i)$ 为颜色 $C[v_i]$ 在长为 $i-1$ 的颜色序列 $C[v_1], C[v_2], \ldots, C[v_{i-1}]$ 中的出现次数。

（注意，$f(1)$ 必定为 $0$，原因是其定义中要考察的颜色序列是空的。）

置换 $v_0, v_1, \ldots, v_{|T(r)|-1}$ 被称为是一个**绝妙置换**，当且仅当以下性质成立：

* $v_0 = r$。
* 对于所有满足 $1 \le i \lt |T(r)|$ 的 $i$，结点 $v_i$ 的父结点是 $v_{f(i)}$。

对于所有满足 $0 \le r \lt N$ 的 $r$，子树 $T(r)$ 是一棵**绝妙子树**，当且仅当 $T(r)$ 中结点存在某个绝妙置换。注意，根据定义，仅包含单独一个结点的子树都是绝妙的。

考虑上面给出的树的例子。可以看到，子树 $T(0)$ 和 $T(3)$ 不是绝妙的。子树 $T(14)$ 是绝妙的，因为它仅包含一个结点。接下来，我们将要说明子树 $T(1)$ 也是绝妙的。

考虑一个由不同整数构成的序列 $[v_0, v_1, v_2, v_3, v_4, v_5, v_6] = [1, 4, 5, 12, 13, 6, 14]$。这个序列是 $T(1)$ 中结点的一个置换。下图给出了这个置换。序列中每个结点旁边的数字，是该结点在置换中的索引。

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

我们将要验证，这是一个**绝妙置换**。

* $v_0 = 1$。
* $f(1) = 0$，原因是 $C[v_1] = C[4] = 1$ 在序列 $[\,]$ 中出现了 $0$ 次。
 * 相应地，$v_1$ 的父结点是 $v_0$。也就是说，$4$ 的父结点是 $1$。（形式化地，$P[4] = 1$。）
* $f(2) = 0$，原因是 $C[v_2] = C[5] = 2$ 在序列 $[1]$ 中出现了 $0$ 次。
 * 相应地，$v_2$ 的父结点是 $v_0$。也就是说，$5$ 的父结点是 $1$。
* $f(3) = 1$，原因是 $C[v_3] = C[12] = 1$ 在序列 $[1, 2]$ 中出现了 $1$ 次。
 * 相应地，$v_3$ 的父结点是 $v_1$。也就是说，$12$ 的父结点是 $4$。
* $f(4) = 1$，原因是 $C[v_4] = C[13] = 2$ 在序列 $[1, 2, 1]$ 中出现了 $1$ 次。
 * 相应地，$v_4$ 的父结点是 $v_1$。也就是说，$13$ 的父结点是 4。
* $f(5) = 0$，原因是 $C[v_5] = C[6] = 3$ 在序列 $[1, 2, 1, 2]$ 中出现了 $0$ 次。
 * 相应地，$v_5$ 的父结点是 $v_0$。也就是说，$6$ 的父结点是 $1$。
* $f(6) = 2$，原因是 $C[v_6] = C[14] = 2$ 在序列 $[1, 2, 1, 2, 3]$ 中出现了  $2$ 次。
 * 相应地，$v_6$ 的父结点是 $v_2$。也就是说，$14$ 的父结点是 $5$。

由于我们能为 $T(1)$ 中的结点找到一个**绝妙置换**，子树 $T(1)$ 因此是一棵**绝妙子树**。

你的任务是，帮助 Árpád 确定 Ős Vezér 的每棵子树是否是绝妙的。

inputFormat:
你需要实现以下函数。

```
int[] beechtree(int N, int M, int[] P, int[] C)
```

* $N$：树中的结点数量。
* $M$：树中边的可能颜色的数量。
* $P$，$C$：长度为 $N$ 的两个数组，以描述树中的边。
* 该函数应当返回长度为 $N$ 的某个数组 $b$。
  对所有满足 $0 \le r \lt N$ 的 $r$，如果 $T(r)$ 是绝妙的，则 $b[r]$ 应为 $1$，否则应为 $0$。
* 该函数在每个测试用例上恰好被调用一次。