title: [ICPC2018 Qingdao R] Tournament

description:
DreamGrid, the king of Gridland, is making a knight tournament. There are $n$ knights, numbered from 1 to $n$, participating in the tournament. The rules of the tournament are listed as follows:

- The tournament consists of $k$ rounds. Each round consists of several duels. Each duel happens between exactly two knights.
- Each knight must participate in exactly one duel during each round.
- For each pair of knights, there can be at most one duel between them during all the $k$ rounds.
- Let $1 \le i, j \le k$, $i \ne j$, and $1 \le a, b, c, d \le n$, $a, b, c, d$ be four distinct integers. If
    - Knight $a$ fights against knight $b$ during round $i$, and
    - Knight $c$ fights against knight $d$ during round $i$, and
    - Knight $a$ fights against knight $c$ during round $j$,
- then knight $b$ must fight against knight $d$ during round $j$.

As DreamGrid's general, you are asked to write a program to arrange all the duels in all the $k$ rounds, so that the resulting arrangement satisfies the rules above.

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

The first and only line contains two integers $n$ and $k$ ($1 \le n, k \le 1000$), indicating the number of knights participating in the tournament and the number of rounds.

It's guaranteed that neither the sum of $n$ nor the sum of $k$ in all test cases will exceed $5000$.

outputFormat:
For each test case:

- If it's possible to make a valid arrangement, output $k$ lines. On the $i$-th line, output $n$ integers $c_{i, 1}, c_{i, 2}, \dots, c_{i, n}$ separated by one space, indicating that in the $i$-th round, knight $j$ will fight against knight $c_{i, j}$ for all $1 \le j \le n$.
If there are multiple valid answers, output the lexicographically smallest answer.
Consider two answers $A$ and $B$, let's denote $a_{i, j}$ as the $j$-th integer on the $i$-th line in answer $A$, and $b_{i, j}$ as the $j$-th integer on the $i$-th line in answer $B$. Answer $A$ is lexicographically smaller than answer $B$, if there exists two integers $p$ ($1 \le p \le k$) and $q$ ($1 \le q \le n$), such that
    - for all $1 \le i < p$ and $1 \le j \le n$, $a_{i, j} = b_{i, j}$, and
    - for all $1 \le j < q$, $a_{p, j} = b_{p, j}$, and finally $a_{p, q} < b_{p, q}$.
-If it's impossible to make a valid arrangement, output ``Impossible`` (without quotes) in one line.

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

translation: $n$ 个骑士要进行 $m$ 轮对决，每一轮每个骑士都要有一个对手。而且每个对手只能打一次。假设 $a$ 与 $b$ 打了，$c$ 与 $d$ 打了，那么后面的任意一轮如果 $a$ 与 $c$ 打了，那么 $b$ 就必须和 $d$ 打，问是否存在方案，存在就输出字典序最小的一组，否则输出 ```Impossible```。


title: [ICPC2018 Qingdao R] Repair the Artwork

type: P

description:
DreamGrid has a paper strip with $n$ grids in a line and he has drawn some beautiful patterns in some grids. Unfortunately, his naughty roommate BaoBao drew some other patterns in some other grids when he wasn't at home. Now DreamGrid has to erase BaoBao's patterns without destroying his own patterns.

Let's number the grids from 1 to $n$ from left to right. Each grid either contains DreamGrid's pattern, or contains BaoBao's pattern, or is empty.

Each time, DreamGrid can select two integers $l$ and $r$ (these two integers can be different each time) such that

- $1 \le l \le r \le n$, and
- for all $l \le i \le r$, the $i$-th grid either contains BaoBao's pattern, or is empty,

and change the $i$-th grid to an empty grid for all $l \le i \le r$.

How many ways can DreamGrid change all the grids containing BaoBao's pattern to empty grids by performing the above operation exactly $m$ times? As the answer may be large, please print the answer modulo $10^9 + 7$.

Let $\{(a_1, b_1), (a_2, b_2), \dots (a_m, b_m)\}$ be a valid erasing sequence ($1 \le a_i \le b_i \le n$), where $(a_i, b_i)$ indicates that DreamGrid selects integers $a_i$ and $b_i$ in the $i$-th operation. Let $\{(c_1, d_1), (c_2, d_2), \dots, (c_m, d_m)\}$ be another valid erasing sequence ($1 \le c_i \le d_i \le n$), where $(c_i, d_i)$ indicates that DreamGrid selects integers $c_i$ and $d_i$ in the $i$-th operation. These two sequences are considered different, if there exists an integer $k$ ($1 \le k \le m$) such that $a_k \ne c_k$ or $b_k \ne d_k$.

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

The first line contains two integers $n$ and $m$ ($1 \le n \le 100$, $1 \le m \le 10^9$), indicating the number of grids and the number of times to perform the operation.

The second line contains $n$ integers $a_i$ ($a_i \in \{0, 1, 2\}$).

- If $a_i = 0$, the $i$-th grid is empty.
- If $a_i = 1$, the $i$-th grid contains DreamGrid's pattern.
- If $a_i = 2$, the $i$-th grid contains BaoBao's pattern.

It's guaranteed that at most 50 test cases have $n > 50$.

outputFormat: For each test case, output one line containing the number of ways modulo $10^9 + 7$.

translation:
给定整数 $T(1\le T\le100)$. 对于每组数据 :

给定整数 $n, m(n\le 100, m\le10^9)$. 接下来给出一个长度为 $n$ 的数组 $a$, 保证 $a_i\in \{0, 1, 2\}$.

你需要执行下面的操作恰好 $m$ 次：

- 指定正整数 $l, r \le n$, 满足 $\forall i\in \mathbf{N}$ 且 $i\in[l, r]$, 有 $a_i \ne 1$.
- 将所有满足 $i \in [l, r]$ 的 $a_i$ 赋值为 $0$.

求有多少种不同的操作方式, 使得进行所有 $m$ 次操作后, $\forall i\in[l, r], a_i \ne 2$. 由于答案可能很大，请输出答案对 $10^9 + 7$ 取模的值.

**注意 : 对于每个数据点, 至多有 50 组数据满足 $n>50$.**

Translated by @[Ja50nY0un9](/user/363302).


title: [ICPC2018 Qingdao R] Mirror

description:
There is a non-transparent obstacle and a single-sided mirror in an infinite two-dimensional plane. The obstacle can be represented as a triangle and the mirror can be represented as a $\textbf{directional}$ line segment pointing from $(x_{m,1}, y_{m,1})$ to $(x_{m,2}, y_{m,2})$, with the right side being reflective.

There are $m$ stones at point $(x_1,y_1)$ and DreamGrid would like to move all the stones to point $(x_2,y_2)$. The following constraints must be satisfied:

- DreamGrid can only carry one stone each time.
- Once DreamGrid picks up a stone, he can only put it down at point $(x_2,y_2)$.
- Let $L$ be the path DreamGrid walked, then for each point $p$ on $L$, DreamGrid should see all the stones directly or through the mirror.

Note that:

- If some part of the line vision is inside the obstacle (it's ok that the line vision passes a point or edge of the obstacle), it's considered, that DreamGrid cannot see the stone with this line of vision.
- If one of the two endpoints of the mirror is on the line of vision, it's considered, that DreamGrid can see the stone both in the mirror and through the mirror.
- The reflection process is governed by laws of physics --- the angle of incidence is equal to the angle of reflection. The incident ray is in the same half-plane as the reflected ray, relative to the mirror.
- If the line of vision is parallel to the mirror, reflection doesn't take place, and the mirror isn't regarded as an obstacle.
- DreamGrid cannot move into the obstacle but can move on the edges or the vertices of the obstacle.
- DreamGrid cannot move through the mirror but can move on the mirror. Note that if DreamGrid is on the line segment of the mirror other than the two endpoints, he can only see the side he comes from, and cannot see through the mirror.

DreamGrid would like to know the shortest distance to move all stones from $(x_1,y_1)$ to $(x_2, y_2)$.

inputFormat:
There are multiple test cases. The first line of input is an integer $T$ (about 100), indicates the number of test cases. For each test case:

The first line contains one integer $m$ ($1 \le m \le 10^6$), indicating the number of stones.

The second line contains four integers $x_1$, $y_1$, $x_2$ and $y_2$, indicating the start point and the target point.

The third line contains four integers $x_{m,1}$, $y_{m,1}$, $x_{m,2}$ and $y_{m,2}$, indicating the coordinates of the mirror.

Each of the next $3$ lines has two integers $x_i$ and $y_i$, indicating the coordinates of the vertices of the obstacle.

All the coordinates will not exceed $100$ in absolute value. Both the start point and target point are outside the obstacle and the mirror. The mirror and the obstacle have no points in common.

It is guaranteed that no three points are collinear.

outputFormat:
For each test case, output a real number indicating the shortest distance, or output $-1$ if DreamGrid cannot move all the stones under the constraints.

Your answer will be considered correct if and only if the absolute error or relative error of your answer is less than $10^{-6}$.

translation:
### 题目描述

在一个无限二维平面上包含一个不透明障碍物和一个单面镜子。障碍物被表示为一个三角形，而镜子被表示为一个从点 $(x_{m,1}, y_{m,1})$ 指向 $(x_{m,2}, y_{m,2})$ 的有方向的线段，线段的右侧是反射面。

有 $m$ 个石头位于点 $(x_1,y_1)$，DreamGrid 希望将所有石头移动到点 $(x_2,y_2)$。需要满足以下条件：

DreamGrid 每次只能携带一个石头。
一旦 DreamGrid 拿起一个石头，他只能将其放置在点 $(x_2,y_2)$。

设 $L$ 为 DreamGrid 走过的路径，对于路径上的每一个点 $p$，DreamGrid 必须能直接或通过镜子看到所有的石头。

**注意：**

如果视线的某部分在障碍物内（视线穿过障碍物的点或边界是允许的），则认为 DreamGrid 无法通过这条视线看到石头。

如果镜子的一个端点在视线上，认为 DreamGrid 既可以在镜子中看到石头，也可以透过镜子看到石头。

反射过程遵循物理规律：入射角等于反射角。入射光线和反射光线在镜子的同一侧。

如果视线与镜子平行，则不发生反射，镜子不被视为障碍物。
DreamGrid 不能移动进入障碍物，但可以在障碍物的边缘或顶点上移动。

DreamGrid 不能穿过镜子移动，但可以在镜子上移动。注意，如果 DreamGrid 在镜子的线段上（不包括两个端点），他只能看到他来的那一侧，并且不能透过镜子看到。
DreamGrid 想要知道移动所有石头从 $(x_1,y_1)$ 到 $(x_2, y_2)$ 的最短距离。

### 输入格式

输入包括多个测试用例。第一行是一个整数 $T$（大约 100），表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $m$（$1 \le m \le 10^6$），表示石头的数量。

第二行包含四个整数 $x_1$, $y_1$, $x_2$ 和 $y_2$，表示起始点和目标点。

第三行包含四个整数 $x_{m,1}$, $y_{m,1}$, $x_{m,2}$ 和 $y_{m,2}$，表示镜子的坐标。

接下来的 $3$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示障碍物顶点的坐标。

所有坐标的绝对值不超过 $100$。起始点和目标点都在障碍物和镜子之外。镜子和障碍物没有公共点。

保证没有三个点是共线的。

### 输出格式

输出对于每个测试用例，输出一个实数表示最短距离，如果 DreamGrid 无法在约束条件下移动所有石头，则输出 $-1$。

如果你的答案的绝对误差或相对误差小于 $10^{-6}$，则认为你的答案是正确的。

hint:
We now welcome our special guest Mashiro, who heartily donates this problem to our problemset, to explain the sample test cases for us using her sketch book.

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

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

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

$\textit{(Image from pixiv. ID: 32084305)}$

In the figures above, we indicate the start point as point $A$ and the target point as point $B$. The mirror is indicated by the line segment pointing from $M1$ to $M2$, with the right side being reflective.

For the first sample test case, the optimal path is $A \to C \to B \to C \to A \to C \to B$.

For the second sample test case, as DreamGrid cannot see $A$ from $B$, it's impossible to move all the two stones from $A$ to $B$ while following the constraints in the problem description.


title: [ICPC2018 Qingdao R] Soldier Game

description:
DreamGrid and BaoBao are playing a game.  There are $n$ soldiers in the game, numbered from $1$ to $n$. The $i$-th soldier has a power value of $a_i$. DreamGrid and BaoBao are going to divide the soldiers into several teams according to the rules below:

- A team must consist of 1 or 2 soldiers.
- Every soldier must belong to exactly 1 team.
- If a team consists of two soldiers (let's say they are the $i$-th and the $j$-th soldier), there must be $|i - j| = 1$.

The power value of a team is defined as the sum of the team members' power values. For the sake of fairness, they want to minimize the difference between the maximum team power value and the minimum team power value after the division. You are asked to find the minimum difference.

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 \le n \le 10^5$), indicating the number of soldiers.

The second line contains $n$ integers $a_1, a_2, ... , a_n$ ($-10^9 \le a_i \le 10^9$), where $a_i$ indicates the power value of the $i$-th soldier.

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

outputFormat: For each test case output one line containing one integer, indicating the minimum difference between the maximum team power value and the minimum team power value.

translation:
**DreamGrid** 和 **BaoBao** 在玩游戏。游戏中有 $n$ 个士兵，编号为 $1\sim n$。第 $i$ 名士兵的权利值为 $a_i$。**DreamGrid** 和 **BaoBao** 将按照以下规则将士兵分成几个小组:

- 一个队伍必须由 $1$ 或 $2$ 名士兵组成。

- 每个士兵必须只属于一个队伍。

- 如果一个团队由两名士兵 $i,j$ 组成，则必须有 $|i - j| = 1$。

团队的权力值被定义为队内士兵权力值的总和。

为了公平起见，他们希望最小化分区后的**最大团队力量值**与**最小团队力量值**之间的**差值**。你被要求找出最小的差值。

有多测。

$1\leq n\leq 10 ^ 5$，$|a_i|\leq 10 ^ 9$，$\sum n\leq 10 ^ 6$。


title: [ICPC2018 Qingdao R] Books

description:
DreamGrid went to the bookshop yesterday. There are $n$ books in the bookshop in total. Because DreamGrid is very rich, he bought the books according to the strategy below:

- Check the $n$ books from the 1st one to the $n$-th one **in order**.
- For each book being checked now, if DreamGrid has enough money (not less than the book price), he'll buy the book and his money will be reduced by the price of the book.
- In case that his money is less than the price of the book being checked now, he will skip that book.

BaoBao is curious about how rich DreamGrid is. You are asked to tell him the maximum possible amount of money DreamGrid took before buying the books, which is a non-negative integer. All he knows are the prices of the $n$ books and the number of books DreamGrid bought in total,  indicated  by $m$.

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 \le 10^5$, $0 \le m \le n$), indicating the number of books in the bookshop and the number of books DreamGrid bought in total.

The second line contains $n$ non-negative integers $a_1, a_2, ... , a_n$ ($0 \le a_i \le 10^9$), where $a_i$ indicates the price of the $i$-th book checked by DreamGrid.

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

outputFormat:
For each test case output one line.

If it's impossible to buy $m$ books for any initial number of money, output ``Impossible'' (without quotes).

If DreamGrid may take an infinite amount of money, output ``Richman'' (without quotes).

In other cases, output a non-negative integer, indicating the maximum number of money he may take.

translation:
共有 $n$ 本书，第 $i$ 本书的价格为 $a_i$。买书的策略为：按编号顺序从小到大遍历每本书，若书的价格不超过剩余钱数，则购买，否则跳过。

问初始最多有多少钱能恰好买 $m$ 本书。若初始可以有无穷多的钱，则输出 `Richman`。若不能恰好买 $m$ 本数，则输出 `Impossible`。

多组测试数据。

$1\leq n\leq 10 ^ 5$，$0\leq m\leq n$，$0\leq a_i\leq 10 ^ 9$，$\sum n\leq 10 ^ 6$。


title: [ICPC2018 Qingdao R] Airdrop

description:
PUBG is a multiplayer online battle royale video game. In the game, up to one hundred players parachute onto an island and scavenge for weapons and equipment to kill others while avoiding getting killed themselves. Airdrop in this game is a key element, as airdrops often carry with them strong weapons or numerous supplies, helping players to survive.

![](https://cdn.luogu.com.cn/upload/image_hosting/qv9hzuoe.png)
textit{Airdrop in the game(?)

Consider the battle field of the game to be a two-dimensional plane. An airdrop has just landed at point $(x_0, y_0)$ (both $x_0$ and $y_0$ are integers), and all the $n$ players on the battle field, where $(x_i, y_i)$ (both $x_i$ and $y_i$ are integers) indicates the initial position of the $i$-th player, start moving towards the airdrop with the following pattern:

- If the position of a living player at the beginning of this time unit is not equal to $(x_0, y_0)$, he will begin his next move.
- + Let's say he is currently at point $(x, y)$. For his next move, he will consider four points $(x, y - 1)$, $(x, y + 1)$, $(x - 1, y)$ and $(x + 1, y)$.
- + He will select one of the four points whose Manhattan distance to the airdrop $(x_0, y_0)$ is the smallest to be the destination of his next move. Recall that the Manhattan distance between two points $(x_a, y_a)$ and $(x_b, y_b)$ is defined as $|x_a - x_b| + |y_a - y_b|$.
- + If two or more points whose Manhattan distance to the airdrop is the same, he will use the following priority rule to break the tie: $(x, y - 1)$ has the highest priority to be selected, $(x, y + 1)$ has the second highest priority, $(x - 1, y)$ has the third highest priority, and $(x + 1, y)$ has the lowest priority.
- + At the end of this time unit, he arrives at his destination.
- If the position of a living player at the beginning of this time unit is equal to $(x_0, y_0)$, he will continue to fatten his backpack with the supplies in the airdrop and stays at $(x_0, y_0)$.

But the battle is tough and it's almost impossible for all the players to arrive at the airdrop safely. If two or more players meet at point $(x', y')$ other than $(x_0, y_0)$, where both $x'$ and $y'$ are integers, they will fight and kill each other and none of them survive.

BaoBao is a big fan of the game and is interested in the number of players successfully arriving at the position of the airdrop, but he doesn't know the value of $x_0$. Given the value of $y_0$ and the initial position of each player, please help BaoBao calculate the minimum and maximum possible number of players successfully arriving at the position of the airdrop for all $x_0 \in \mathbb{Z}$, where $\mathbb{Z}$ is the set of all integers (note that $x_0$ can be positive, zero or negative).

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 $y_0$ ($1 \le n \le 10^5$, $1 \le y_0 \le 10^5$), indicating the number of players and the $y$ value of the airdrop.

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

It's guaranteed that the sum of $n$ in all test cases will not exceed $10^6$, and in each test case no two players share the same initial position.

outputFormat: For each test case output one line containing two integers $p_\text{min}$ and $p_\text{max}$ separated by one space. $p_\text{min}$ indicates the minimum possible number of players successfully arriving at the position of the airdrop, while $p_\text{max}$ indicates the maximum possible number.

translation:
### 题目描述
有 $n$ 个玩家在一个平面直角坐标系中打 PUBG. 此时一个空投落在了 $(x_0, y_0)$ 处.

现在场上还剩 $n$ 个「存活」的玩家. 从空投落地的时刻起, 每一个时刻执行如下操作 :

1. 移动阶段

对于每个「存活」的玩家 :
- 如果其不在 $(x_0, y_0)$ :
  - 向空投方向沿 $x$ 轴**或** $y$ 轴方向移动 $1$ 个单位距离, 使得移动后位置与 $(x_0, y_0)$ 的曼哈顿距离尽可能小.
  - 在上一条规则的基础上, 如果有多种符合要求的移动方式, 则优先沿 $y$ 轴移动.
- 如果其在 $(x_0, y_0)$, 则不进行操作.

2. 战斗阶段

移动阶段结束后, 如果**除 $(x_0, y_0)$ 外**任意一点存在超过 $1$ 名玩家, 则将这一点所有玩家判定为「死亡」并移出游戏.

---

可以证明, 经过足够多次操作后, 所有仍「存活」的玩家都会处在 $(x_0, y_0)$ 位置.

给定 $y_0$, 求 $x_0$ 取任意整数值时, 最终「存活」玩家数的最大值与最小值.

### 输入输出格式与数据范围
首先给出一个整数 $T$, 表示数据组数. 接下来对于每组数据 :

第一行给出两个正整数 $n, y_0$, 意义如题所述.

接下来 $n$ 行, 每行两个正整数 $x, y$, 表示 $n$ 个玩家的坐标.

$n$ 和所有点的坐标值都不超过 $10^5$, 且保证不存在两名玩家初始处在同一位置. 单个测试点的 $\sum n \le 10^6$.

**注意 : $x_0$ 可以取 $0$ 或负值, 且不受坐标值不超过 $10^5$ 的限制.**

对于每组数据, 输出一行 2 个空格分开的整数, 分别表示最终「存活」玩家数的最大值和最小值.

Translated by @[Ja50nY0un9](/user/363302).

hint:
We now explain the first sample test case.

To obtain the answer of $p_\text{min} = 1$, one should consider $x_0 = 3$. The following table shows the position of each player at the end of each time unit when $x_0 = 3$.

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

To obtain the answer of $p_\text{max} = 3$, one should consider $x_0 = 2$. The following table shows the position of each player at the end of each time unit when $x_0 = 2$.

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


title: [ICPC2018 Qingdao R]  Sub-cycle Graph

description:
Given an undirected simple graph with $n$ ($n \ge 3$) vertices and $m$ edges where the vertices are numbered from 1 to $n$, we call it a ``sub-cycle`` graph if it's possible to add a non-negative number of edges to it and turn the graph into exactly one simple cycle of $n$ vertices.

Given two integers $n$ and $m$, your task is to calculate the number of different sub-cycle graphs with $n$ vertices and $m$ edges. As the answer may be quite large, please output the answer modulo $10^9+7$.

Recall that

- A simple graph is a graph with no self loops or multiple edges;
- A simple cycle of $n$ ($n \ge 3$) vertices is a connected undirected simple graph with $n$ vertices and $n$ edges, where the degree of each vertex equals to 2;
- Two undirected simple graphs with $n$ vertices and $m$ edges are different, if they have different sets of edges;
- Let $u < v$, we denote $(u, v)$ as an undirected edge connecting vertices $u$ and $v$. Two undirected edges $(u_1, v_1)$ and $(u_2, v_2)$ are different, if $u_1 \ne u_2$ or $v_1 \ne v_2$.

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

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

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

outputFormat: For each test case output one line containing one integer, indicating the number of different sub-cycle graphs with $n$ vertices and $m$ edges modulo $10^9+7$.

translation:
### 题目描述

对于一个有 $n(n\ge3)$ 个点和 $m$ 条边的无向简单图，其中点的编号为 $1$ 到 $n$。如果加非负整数条边能使这个图是变为 $n$ 个点的简单环，我们称这个是一个 “半环” 图。

给定两个整数 $n$ 和 $m$，你的任务是计算有多少个**不同的** $n$ 个点，$m$ 条边的 “半环” 图。考虑到答案会很大，请将答案模 $10^{9} + 7$ 的结果输出。

定义

- 一个简单图是指一个没有自环和重边的图；
- $n$ 个点的 “简单环” 是指任意一个有 $n$ 个点和 $n$ 条边的无向简单连通图，其中所有点的度均为 $2$；
- 如果两个有着 $n$ 个点和 $m$ 条边的无向简单图是不同的，那么它们具有着不同的边集；
- 现在有两个点 $u$ 和 $v(u < v)$，记 $(u,v)$ 表示连接 $u,v$ 两点的无向边。两条无向边 $(u_1,v_1)$ 和 $(u_2,v_2)$ 如果是不同的，那么 $u_1\ne u_2$ 或 $v_1\ne v_2$。

### 输入格式

此题有多组数据。

第一行有一个整数 $T$（约为 $2\times 10^{4}$），指测试用例的数量。对于每组数据：

一组数据只有一行，两个整数 $n$ 和 $m$（$3 \le n \le 10^{5}$，$0\le m \le \frac{n(n-1)}{2}$），表示图的点数和边数。

$n$ 的总和不超过 $3\times 10^{7}$。

### 输出格式

对于每组数据，你只需要输出一行表示答案。

hint:
The 12 sub-cycle graphs of the second sample test case are illustrated below.

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


title: [ICPC2018 Qingdao R] Function and Function

description:
If we define $f(0) = 1, f(1) = 0, f(4) = 1, f(8) = 2, f(16) = 1, \dots$, do you know what function $f$ means?

Actually, $f(x)$ calculates the total number of enclosed areas produced by each digit in $x$. The following table shows the number of enclosed areas produced by each digit:

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

For example, $f(1234) = 0 + 0 + 0 + 1 = 1$, and $f(5678) = 0 + 1 + 0 + 2 = 3$.

We now define a recursive function $g$ by the following equations:

$$\begin{cases} g^0(x) = x \\ g^k(x) = f(g^{k-1}(x)) & \text{if } k \ge 1 \end{cases}$$

For example, $g^2(1234) = f(f(1234)) = f(1) = 0$, and $g^2(5678) = f(f(5678)) = f(3) = 0$.

Given two integers $x$ and $k$, please calculate the value of $g^k(x)$.

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

The first and only line contains two integers $x$ and $k$ ($0 \le x, k \le 10^9$). Positive integers are given without leading zeros, and zero is given with exactly one `0'.

outputFormat: For each test case output one line containing one integer, indicating the value of $g^k(x)$.

translation:
### 题目描述

如果我们定义 $f(0) = 1$，$f(1) = 0$，$f(4) = 1$，$f(8) = 2$，$f(16) = 1$ …… 你知道函数 $f$ 意味着什么吗？

其实，$f(x)$ 计算的是 $x$ 中每个数字所产生的封闭区域的总数。下表显示了每个数字产生的封闭区域数：

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

例如，$f(1234) = 0 + 0 + 0 + 1 = 1$，$f(5678) = 0 + 1 + 0 + 2 = 3$。

现在，我们用以下等式定义递归函数 $g$：

$$\begin{cases} g^0(x) = x \\ g^k(x) = f(g^{k-1}(x)) & \text{if } k \ge 1 \end{cases}$$

例如，$g^2(1234) = f(f(1234)) = f(1) = 0$，$g^2(5678) = f(f(5678)) = f(3) = 0$。

给定两个整数 $x$ 和 $k$，请计算 $g^k(x)$ 的值。

### 输入格式

有多个测试用例。输入的第一行包含一个整数 $T$（大约 $10 ^ 5$），表示测试用例的数量。
之后的每行包含两个整数 $x$ 和 $k$（$0 \le x, k \le 10^9$）。正整数不带前导零，零则正好是一个 "0"。

### 输出格式

对每个测试用例输出一行，其中包含一个整数，表示 $g^k(x)$ 的值。


title: 「Cfz Round 3」Battle

description:
Alice 和 Bob 正在进行一个游戏，游戏的规则如下：

- Alice 初始时拥有一个整数 $n$，Bob 初始时拥有一个整数 $m$；
- 从 Alice 开始，两人轮流对**对方拥有的整数**进行操作：设对方此时拥有的整数为 $h$，使 $h$ 的值**减去** $h \bmod p$，其中 $\bmod$ 表示**取模**运算，$p$ 是给定的一个定值；
- 两人中率先使对方拥有的整数变为 $0$ 的人获得胜利，若在两人分别进行 $10^{10^{9961}}$ 次操作后仍无人获得胜利，则认为游戏平局。

你需要判断谁将会获得胜利，或报告游戏将会平局。

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

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

接下来依次输入每组测试数据。对于每组测试数据，输入三个整数 $n,m,p$。

outputFormat:
对于每组数据，一行一个字符串表示答案：

- 若 Alice 将会获得胜利，则输出 `Alice`；
- 若 Bob 将会获得胜利，则输出 `Bob`；
- 若游戏将会平局，则输出 `Lasting Battle`。

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

对于第 $1$ 组数据，Alice 在第一次操作中就会将 Bob 拥有的整数从 $2$ 变为 $2-(2\bmod 10)$ 即 $0$，所以 Alice 将会获得胜利。

对于第 $2$ 组数据，Alice 在第一次操作中会将 Bob 拥有的整数从 $11$ 变为 $11-(11\bmod 11)$ 即 $11$，而 Bob 在第一次操作中会将 Alice 拥有的整数从 $9$ 变为 $9-(9 \bmod 11)$ 即 $0$，所以 Bob 将会获得胜利。

对于第 $3$ 组数据，可以证明游戏将会平局。

#### 「数据范围」

对于所有数据，$1 \leq T \leq 5000$，$1 \leq n, m, p \leq 2\times 10^9$。

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


title: [POI 2023/2024 R1] Budowa lotniska

background: 译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Budowa lotniska](https://sio2.mimuw.edu.pl/c/oi31-1/p/bud/)。

description:
给你一个 $n\times n$ 的地图，地图上有 `.` 有 `X`。

求出最大的 $k$，使得：

在地图上能找到 $m(m\leq 2)$ 个 $1\times k$ 或 $k\times 1$ 的长条，使得长条不交且长条内全是 `.`。

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

接下来 $n$ 行，描述地图。

outputFormat: 一行一个非负整数，最大的 $k$。

samples:
10 2
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
..........
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

samples:
10 2
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X
XX.XXXXX.X


title: [POI 2023/2024 R1] CzatBBB

background: 译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [CzatBBB](https://sio2.mimuw.edu.pl/c/oi31-1/p/cza/)。

description:
给出一个 $n$ 个字母的字符串 $S$ 和一个参数 $k$，设 $R$ 为字符串 $S$ 的后 $k$ 个字母形成的字串。

假设字符串 $S'$ 为 $S$ 添加一个新字母生成的新字符串。

添加的规则如下所示： 对于字母 $X$ 字母，计算它在字符串 $S$ 中紧接着 $R$ 出现的次数。出现频率最高的字母为新添加的字母，如果有多个出现频率最高的字母，取最小的一个。如果 $R$ 在字符串 $S$ 中的其他地方都没有出现，则取 $X = a$。最后，我们扩展字符串 $S$，在其末尾添加字母 $X$。

例如，设 $S = \text{abaaabababa}$，$k = 3$ 则 $R$ 与后一个字母一起出现的字串为的：$\text{abaa}$、$\text{abab}$、$\text{abab}$。它最常与字母 $\text{b}$ 一起出现，因此我们在 $S$ 中加上 $\text{b}$，生成 $S' = \text{abaaabababab}$。

现在 $S' = \text{abaaabababab}$，$R = \text{bab}$，$R$ 与后一个字母一起出现的字串为：$\text{baba}$、$\text{baba}$，如 $\text{baba}$、$\text{baba}$，因此我们在 $S'$ 后面加上 $a$。

以此类推，这样的操作会进行无数次。

你的任务是编写一个程序，输出新字符串最后 $a$ 至 $b$ 个字符。

inputFormat:
第一行输入包含四个整数 $n$、$k$、$a$ 和 $b$。

第二行输入包含一个 $n$ 个字母的字符串，由小写英文字母组成的 $n$ 个字母字符串，表示单词 $S$。

outputFormat: 输出字符串 $S'$ 的第 $a$ 个字符 至第 $b$ 个字符，表示扩展单词 $S'$ 中位于以下位置的字母。

samples: 见附件 见附件


title: [POI 2023/2024 R1] Przyciski

background: 译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Przyciski](https://sio2.mimuw.edu.pl/c/oi31-1/p/prz/)。

description:
一个 $n\times n$ 的方阵，里面有 $m$ 个按钮。

你需要按下若干个（至少一个）按钮，使得每行每列被按下的按钮个数奇偶性相同。

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

接下来 $m$ 行，每行两个正整数，表示一个按钮的坐标。

outputFormat:
如果无解，输出一行 `NIE`。

如果有解，第一行输出 `TAK`，第二行输出一个正整数 $k$，表示按下按钮的个数，第三行输出若干个正整数，表示你按下的按钮的编号。


title: [POI 2023/2024 R1] Satelity

background: 译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Satelity](https://sio2.mimuw.edu.pl/c/oi31-1/p/sat/)。

description:
有 $2n$ 个卫星，$1\sim n$ 属于 A 公司，$n+1\sim 2n$ 属于 B 公司。

两个卫星**应当**能够通信**当且仅当**它们属于同一个公司或者有额外要求。

你需要给每个卫星分配一个等长的**独一无二**的识别码，识别码应当只包含字母 `ABC`，两个卫星**实际**能够通信**当且仅当**识别码有至少一位相同。要求你的识别码方案满足要求。输出你的方案。

inputFormat:
本题多测，读入直到文件结束。

对于每组数据，第一行三个正整数 $n,p,M$，其中 $M$ 意为你的识别码长度不得超过 $M$。

接下来 $p$ 行，每行两个正整数，表示这两个卫星有额外要求应当能够通信。

outputFormat:
对于每组数据，第一行一个正整数 $m(1\leq m\leq M)$，表示你的方案的识别码长度。

接下来 $2n$ 行，每行一个长度为 $m$ 的只含 `ABC` 的字符串，识别码。


title: [POI 2023/2024 R1] Zapobiegliwy student

background: 译自 [XXXI Olimpiada Informatyczna - I etap](https://sio2.mimuw.edu.pl/c/oi31-1/dashboard/) [Zapobiegliwy student](https://sio2.mimuw.edu.pl/c/oi31-1/p/zap/)。

description:
考虑如下的一个简单问题：

> 你有 $n$ 个线段在数轴上，你要选出尽量多的线段，使它们两两不交。

我知道你一定会做，但你需要解决这个：

你有 $n$ 个线段在数轴上，你要选出尽量多的线段对 $(u_i,v_i)_{i=1}^k$，即最大化 $k$。

满足 $k+1$ 个要求：

- $u_1,u_2,\cdots,u_k$ 两两不交。
- $v_1,u_2,u_3,\cdots,u_k$ 两两不交。
- $u_1,v_2,u_3,u_4,\cdots,u_k$ 两两不交。
- $\cdots$
- $u_1,u_2,\cdots,u_{k-1},v_k$ 两两不交。

其中 $\forall i$，$u_i$ 与 $v_i$ 不能相同。

inputFormat:
第一行一个正整数 $n(n\geq2)$。

接下来 $n$ 行每行两个正整数 $a_i,b_i(1\leq a_i<b_i\leq10^9)$，表示一个线段的两个端点。

两个线段 $i,j$ 不交当且仅当 $b_i\leq a_j$ 或 $b_j\leq a_i$。

outputFormat:
第一行一个正整数 $k$。

接下来 $k$ 行，每行两个正整数 $u_i,v_i$，表示一对线段的编号。


title: 「LAOI-4」Mex Tower (Easy ver.)

background: **本题与 Hard Version 的区别为本题需给出一个合法的方案。**

description:
定义 $\operatorname{mex}(x, y)$ 表示在集合 $\{x, y\}$ 中最小的未出现的 **自然数**。例如，$\operatorname{mex}(1, 5) = 0$，$\operatorname{mex}(3, 0) = 1$。

继而，我们定义对自然数序列 $a_1\dots a_n$ 的一次操作，是将序列 $a$ 替换为 **长度为 $\bm{n - 1}$ 的** 序列 $b_1\dots b_{n-1}$，其中 $b_i = \operatorname{mex}(a_i, a_{i+1})$。

你需要构造一个长度为 $n$ 的自然数序列 $a_1\dots a_n$，满足 $0 \leq a_i \leq 10^9$；然后对它进行 $n - 1$ 次操作。显然最终序列 $a$ 只会剩下一个数，你需要最大化这个数的值。

如果有多种可能的数列，可以输出任何一种合法方案。

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

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

对于每组数据，仅一行，一个正整数 $n$。

outputFormat: 对于每组数据，输出一行 $n$ 个整数，表示你构造的 $a_1\dots a_n$。


title: SDOI2024

background:
AzureHair 在 NOIP 2022 中被喵了个喵创死，于是患上了不治之症——T2 恐惧症，于是他在 NOIP 2023 中果断跳过了 T2 并杠 T3 两小时无果，遗憾离场，他的同学决定帮他治疗这种不治之症。

在他的同学给他治愈了 T2 恐惧症后，他自信的开始了他的 SDOI，遂分讨写了 $2$ 个小时没写出来，遗憾离场……

description: AzureHair 的同学把 AzureHair 和 $n$ 只猫猫关在一个房间里，并且要求 AzureHair 每过一天就交出 $\frac{n}{2}$ 只猫猫，但是如果 $n$ 是奇数时，AzureHair 就会纠结于要交出 $\frac{n+1}{2}$ 只猫猫还是交出 $\frac{n-1}{2}$ 只猫猫。AzureHair 不想让自己纠结，所以请你计算出直到所有猫猫都被拿出房间时，AzureHair 的最小纠结次数是多少。

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

第一行一个整数 $T$。

接下来 $T$ 行，每行一个整数 $n$。

outputFormat: $T$ 行，每行一个整数表示最小纠结次数。

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

对于 $13$ 只猫猫，只纠结 $3$ 次的过程如下：

选择交出 $7$ 只猫猫，剩余 $6$ 只；

不纠结，交出 $3$ 只猫猫，剩余 $3$ 只；

选择交出 $2$ 只猫猫，剩余 $1$ 只；

选择交出 $1$ 只猫猫，所有猫猫均被取走。

容易证明不存在少于 $3$ 次纠结的方案。

**【数据范围】**

对于 $10\%$ 的数据，保证 $1\le n \le 10$。

对于 $30\%$ 的数据，保证 $1\le n \le 10^{5}$。

对于 $100\%$ 的数据，保证 $1\le n \le 2^{60}$，$1 \le T \le 5\times 10^5$。


title: [COCI 2023/2024 #1] AN2DL

description:
While wandering around Building $21$, you came across a wall completely covered with numbers, arranged in a table of $n$ rows and $m$ columns. Soon you noticed that there was a frame leaning against the wall large to frame $r$ rows and $s$ columns of the table on the wall. And next to the frame you found a pencil and
a piece of paper containing an empty table.

You are sad that the table on the piece of paper is empty, so you decided to play around with the frame to fill it.

You leaned the frame against the wall so that the number in the $i$-th row and $j$-th column is in the upper left corner, and the borders of the frame are parallel to the edges of the wall. Considering the numbers inside the frame, and since you like large numbers, you have decided to write the largest among them in the $i$-th row and $j$-th column of the table on the piece of paper.

You repeated the process for every possible position of the frame on the wall (such that the frame is
entirely on the wall, and that there are exactly $r \times s$ numbers inside it), making sure that the edges of the frame are parallel to the edges of the wall.

When you were done, the table on the piece of paper was even more beautiful than the one on the wall.What numbers are in the table on the piece of paper?

### 题目大意

给定 $n,m,r,s$ 和一个 $n\times m$ 的整数矩阵 $A$，求它每个 $r\times s$ 的子矩阵的元素最大值。

inputFormat:
第一行两个整数 $n,m$ 表示矩阵的高和宽。

接下来 $n$ 行每行 $m$ 个整数，表示矩阵 $A$。

最后一行两个整数 $r,s$。

outputFormat: $n-r+1$ 行，每行 $m-s+1$ 个数，第 $i$ 行 $j$ 列的数表示以 $(i,j)$ 为左上角的 $r\times s$ 的子矩阵元素的最大值，即 $\max\limits_{i\leq x\leq i+r-1,j\leq y\leq j+s-1}A_{x,y}$。

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

只有一个 $3\times 3$ 的子矩阵，且是整个矩阵，它的元素最大值是 $4$。

### 【样例解释#2】

矩阵和它的每个 $2\times 1$ 的子矩阵如下图所示，其中标红的数为最大值：

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

### 【数据范围】

对于 $100\%$ 的数据，$1\leq n,m\leq 4000$，$\lvert A_{i,j}\rvert\leq 10000$，$1\leq r\leq n$，$1\leq s\leq m$。

**本题采用捆绑测试。**

| 子任务 | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: |
| $1$ | $n,m\leq 40$，$r=n$，$s=m$ | $12$ |
| $2$ | $n,m\leq 40$ | $17$ |
| $3$ | $n,m\leq 1000$ | $25$ |
| $4$ | 无特殊性质 | $56$ |

### 【说明】

本题分值按 COCI 原题设置，满分 $110$。

题目译自 [COCI2022-2023](https://hsin.hr/coci/) [CONTEST #1](https://hsin.hr/coci/contest1_tasks.pdf) _**T3 AN2DL**_。


title: [COCI 2023/2024 #1] Kocke

description:
在 Donald 的十三岁生日上，他的父亲给了他一套乐高积木。在这套积木中，有 $n$ 个大小相同的积木，且第 $i$ 个积木的颜色为 $i$ 。

他想要用这些积木搭一面墙。他想要把这 $n$ 个积木搭在有 $k$ 排成一行的位置的底座上，对积木 $1\sim n$ 依次进行以下操作：

- 如果这个积木编号为 $1$，则可以放在任意位置。
- 否则选择一个上一个放置的积木相邻位置，在它的**顶端**放上这个积木。

他用一个长度为 $k$ 序列表示这面墙：对于第 $i$ 位，如果个位置没有积木，则是 $0$，否则是这个位置最顶端积木的颜色。

问一共有多少种不同的序列，对 $10^9+7$ 取模。

inputFormat: 一行两个整数 $n,k$ 表示积木数量和位置数量。

outputFormat: 一个整数表示问题答案对 $10^9+7$ 取模的结果。


title: [COCI 2023/2024 #1] Mostovi

description:
When Leonhard Euler resolved the famous Königsberg bridge problem,he had no clue he had discovered a whole new area of mathematics -graph theory!

Unfortunately, the Königsberg bridge problem is far too easy for the programmers of this era, so Euler came up with another problem - the Zagreb bridge problem!

The bridges of Zagreb form a graph with $n$ nodes and $m$ edges where the edges represent the bridges and the nodes represent the riverine islands. The graph is connected, in other words, it’s possible to get from any node to any other by traveling across the edges. Now Euler asked, how many edges are there such that after their removal the graph becomes disconnected?

Again, Euler didn’t know that this problem is also famous today (those damn Codeforces blogs). So the author of this problem decided to give you an even harder one, how many edges are there such that after the removal of the nodes which it connects, the remaining $n − 2$ nodes become disconnected?

### 题目大意

给定一张 $n$ 个点 $m$ 条边的无向连通图，求有多少条边满足删去这条边两端的两个点之后，剩余的 $n-2$ 个点不连通。

inputFormat:
一行两个正整数 $n,m$ 分别表示点数和边数。

接下来一行每行两个正整数 $a_i,b_i$ 表示有一条边连接 $a_i,b_i$。

outputFormat: 一行一个整数表示符合条件的边的数量。


title: [EC Final 2020] Namomo Subsequence

description:
``gshfd1jkhaRaadfglkjerVcvuy0gf`` said Prof. Pang.

To understand Prof. Pang's word, we would like to calculate the number of $\textit{namomo subsequence}$s of it. The word by Prof. Pang is a string $s$ with $n$ characters where each character is either an English letter (lower or upper case) or a digit. The $i$-th character of $s$ is denoted by $s[i]$ ($1\le i\le n$). A subsequence $t$ of $s$ is defined by a list of indices $t_1, \ldots, t_6$ such that $1\le t_1 < t_2 < \ldots < t_6\le n$. Let $compare(c_1, c_2)$ be a function on two characters such that $compare(c_1, c_2)=1$ when $c_1=c_2$ and $compare(c_1, c_2)=0$ otherwise. $t$ is a namomo subsequence of $s$ if and only if for any $1\le i<j\le 6$, $compare(s[t_i], s[t_j]) = compare(namomo[i], namomo[j])$, where $namomo[x]$ represents the $x$-th character of the string ``namomo`` ($1\le x\le 6$).

Output the number of namomo subsequences of a given string $s$ modulo $998244353$.

inputFormat: The first line contains a string $s$ with $n$ characters ($6\le n\le 1000000$). $s$ contains only lower case English letters (`a` -- `z`), upper case English letters (`A` -- `Z`) and digits (`0` -- `9`).

outputFormat: Output one integer -- the answer modulo $998244353$.

translation:
### 题目描述

庞教授说：“gshfd1jkhaRaadfglkjerVcvuy0gf 。”

为了理解庞教授的话，我们需要计算字符串中的 $\textit{namomo 子序列}$ 的数量。庞教授的话是一个包含 $n$ 个字符的字符串 $s$，其中每个字符要么是英文字母（大小写皆可），要么是数字。字符串 $s$ 的第 $i$ 个字符表示为 $s[i]$（$1\le i\le n$）。一个 $s$ 的子序列 $t$ 是由一系列索引 $t_1, \ldots, t_6$ 定义的，其中 $1\le t_1 < t_2 < \ldots < t_6\le n$。设 $compare(c_1, c_2)$ 是一个函数，其对两个字符的比较定义为：当 $c_1=c_2$ 时，$compare(c_1, c_2)=1$，否则 $compare(c_1, c_2)=0$。当且仅当对于任意的 $1\le i<j\le 6$，都有 $compare(s[t_i], s[t_j]) = compare(namomo[i], namomo[j])$ 时，$t$ 是 $s$ 的一个 namomo 子序列，其中 $namomo[x]$ 表示字符串 "namomo" 的第 $x$ 个字符 ($1\le x\le 6$)。

输出给定字符串 $s$ 的 namomo 子序列的数量，结果对 $998244353$ 取模。

### 输入格式

第一行包含一个字符串 $s$，长度为 $n$ ($6\le n\le 1000000$)。字符串 $s$ 仅包含小写字母（`a` -- `z`）、大写字母（`A` -- `Z`）以及数字（`0` -- `9`）。

### 输出格式

输出一个整数——结果对 $998244353$ 取模。

翻译者：[Immunoglobules](https://www.luogu.com.cn/user/1066251)


title: [EC Final 2020] Rectangle Flip 2

description:
Prof. Pang enters a trap room in a dungeon. The room can be represented by an $n$ by $m$ chessboard. We use $(i, j)$ ($1\le i\le n$, $1\le j\le m$) to denote the cell at the $i$-th row and $j$-th column. Every second, the floor of one cell breaks apart (so that Prof. Pang can no longer stand on that cell.) After $nm$ seconds, there will be no cell to stand on and Prof. Pang will fall through to the next (deeper and more dangerous) level.

But Prof. Pang knows that calm is the key to overcome any challenge. So instead of being panic, he calculates the number of rectangles such that every cell in it is intact (i.e., not broken) after every second. (A rectangle represented by four integers $a, b, c$ and $d$ ($1\le a\le b\le n, 1\le c\le d\le m$) includes all cells $(i, j)$ such that $a\le i\le b, c\le j\le d$. There are $
\frac{n(n+1)}{2} \times \frac{m(m+1)}{2}$ rectangles in total.)

inputFormat:
The first line contains two integers $n$, $m$ ($1\le n, m\le 500$) separated by a single space.

The $(i+1)$-th line contains two integers $a$, $b$ separated by a single space representing that the cell $(a, b)$ breaks apart at the $i$-th second. It is guaranteed that each cell appears exactly once in the input.

outputFormat: Output $nm$ lines. The $i$-th line should contain the number of rectangles such that every cell in it is intact after the first $i$ cells break apart.

translation:
### 题目描述

庞教授进入了一个地下城的陷阱房间。这个房间可以用一个 $n$ 行 $m$ 列的棋盘来表示。我们用 $(i, j)$ ($1\le i\le n$, $1\le j\le m$) 来表示第 $i$ 行第 $j$ 列的单元格。每秒钟，有一个单元格的地板会破裂（这样庞教授就不能再站在这个单元格上了）。经过 $nm$ 秒后，将没有单元格可供站立，庞教授将跌落到下一个（更深且更危险的）层级。

但庞教授知道冷静是克服任何挑战的关键。因此，他没有惊慌，而是计算了在每秒钟后，所有单元格都完好的矩形的数量（即，每个单元格在矩形中都没有破裂）。一个矩形由四个整数 $a, b, c$ 和 $d$ ($1\le a\le b\le n, 1\le c\le d\le m$) 表示，包含所有 $(i, j)$ 使得 $a\le i\le b, c\le j\le d$。总共有 $
\frac{n(n+1)}{2} \times \frac{m(m+1)}{2}$ 个矩形。

### 输入格式

第一行包含两个整数 $n$, $m$ ($1\le n, m\le 500$)，用空格分隔。

第 $(i+1)$ 行包含两个整数 $a$, $b$，表示在第 $i$ 秒钟单元格 $(a, b)$ 破裂。保证每个单元格在输入中出现恰好一次。

### 输出格式

输出 $nm$ 行。第 $i$ 行应包含在前 $i$ 个单元格破裂之后，每个单元格都完好的矩形的数量。

### 提示

在示例中：在第一秒后，有 $3$ 个面积为 $1$ 的矩形和 $2$ 个面积为 $2$ 的矩形满足条件。因此第一行应该输出 $5$。在第二秒后，仅第二列中的单元格保持完好。答案应该是 $3$。在第三秒后，仅一个单元格保持完好。答案应该是 $1$。在第四秒后，所有单元格都破裂，所以答案应该是 $0$。

翻译者：[Immunoglobules](https://www.luogu.com.cn/user/1066251)

hint: In the example, after the first second, there are $3$ rectangles of area $1$ and $2$ rectangles of area $2$ that satisfy the constraint. So the first line should contain a $5$. After the second second, only cells in the second column remains intact. The answer should be $3$. After the third second, only one cell remains intact. The answer should be $1$. After the fourth second, all cells broke apart so the answer should be $0$.


title: [EC Final 2020] Random Shuffle

description:
Prof. Pang is selecting teams that advance to the world final contest. As the regionals are cancelled, he uses random shuffle to rank the teams. There are $n$ teams in total. His code is as follows:

```cpp
uint64_t x;//uint64_t represents 64-bit unsigned integer
int n;
uint64_t rand() {//this is a xor-shift random generator
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    return x;
}
int main() {
    cin >> n;
    cin >> x;
    for (int i = 1; i <= n; i++) {//random shuffle [1, 2,..., n]
        a[i] = i;
        swap(a[i], a[rand() % i + 1]);
    }
    for (int i = 1; i <= n; i++) {//print the result
        cout << a[i] << (i == n ? '\n' : ' ');
    }
}
```

He compiled and ran his code and then entered $n$ and some special nonnegative integer $x$. He printed the result on paper.

One day later, Prof. Pang forgot his choice for $x$. You are given the result of the code and the integer $n$. Please recover the number $x$ that Prof. Pang had entered.

inputFormat:
The first line contains a single integer $n$ ($50\le n\le 100000$) -- the number of teams.

The next line contains $n$ integers -- the result printed by Prof. Pang's code. It is guaranteed that the result is correct, i.e., there exists an integer $x$ ($0\le x\le 2^{64}-1$) that leads to the result.

outputFormat: Output the integer $x$ ($0\le x\le 2^{64}-1$) Prof. Pang had entered. If there are multiple possible $x$'s, print any one.

hint: Note that the second line of the sample input is wrapped to fit in the width of page.


title: [EC Final 2020] City Brain

description:
Prof. Pang works for the City Brain program of Capital Grancel. The road network of Grancel can be represented by an undirected graph. Initially, the speed limit on each road is $1$m/s. Prof. Pang can increase the speed limit on a road by $1$m/s with the cost of $1$ dollar. Prof. Pang has $k$ dollars. He can spend any nonnegative integral amount of money on each road. If the speed limit on some road is $a$m/s, it takes $1/a$ seconds for anyone to go through the road in either direction.

After Prof. Pang spent his money, Prof. Du starts to travel from city $s_1$ to city $t_1$ and Prof. Wo starts to travel from city $s_2$ to city $t_2$. Help Prof. Pang to spend his money wisely to minimize the sum of minimum time of Prof. Du's travel and Prof. Wo's travel. It is guaranteed that $s_1$ and $t_1$ are connected by at least one path and that $s_2$ and $t_2$ are connected by at least one path.

inputFormat:
The first line contains three integers $n$, $m$, $k$ ($1\le n \le 5000$, $0\le m \le 5000$, $0\le k\le 10^9$) separated by single spaces denoting the number of vertices, the number of edges in the graph and the number of dollars Prof. Pang has.

Each of the following $m$ lines contains two integers $a$, $b$ ($1\le a, b\le n, a\neq b$) separated by a single space denoting the two endpoints of one road. There can be multiple roads between the same pair of cities.

The following line contains four integers $s_1$, $t_1$, $s_2$, $t_2$ ($1\le s_1, t_1, s_2, t_2\le n$) separated by single spaces denoting the starting vertices and ending vertices of Prof. Du and Prof. Wo's travels.

outputFormat: Output one decimal in the only line -- the minimum sum of Prof. Du's travel time and Prof. Wo's travel time. The answer will be considered correct if its absolute or relative error does not exceed $10^{-9}$.


title: [EC Final 2020] Tube Master III

description:
Prof. Pang is playing ``Tube Master``.

The game field is divided into $n \times m$ cells by $(n + 1) \times m$ horizontal tubes and $n \times (m + 1)$ vertical tubes. The product $n m$ is an $\textbf{even}$ number. There are $(n + 1) (m + 1)$ crossings of the tubes. The 2D coordinate of the crossings are $(i, j)$ ($1\le i\le n+1$, $1\le j\le m+1$). We name the crossing with coordinate $(i, j)$ as crossing $(i, j)$. We name the cell whose corners are crossings $(i, j), (i+1, j), (i, j+1), (i+1, j+1)$ as cell $(i, j)$ for all $1\le i\le n$, $1\le j\le m$. Additionally, each cell $(i, j)$ contains an integer ${count}_{i, j}$.

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

The above figure shows a game field with $n = 3, m = 2$ (the third sample).

Prof. Pang decides to use some of the tubes. However, the game poses several weird restrictions.

- Either $0$ or $2$ tubes connected to each crossing are used.
- There are exactly ${count}_{i, j}$ turning points adjacent to cell $(i, j)$. A turning point is a crossing such that exactly $1$ horizontal tube and exactly $1$ vertical tube connected to it are used. A turning point $(x, y)$ is adjacent to cell $(i, j)$ if crossing $(x, y)$ is a corner of cell $(i, j)$.

It costs $a_{i, j}$ to use the tube connecting crossings $(i, j)$ and $(i, j+1)$. It costs $b_{i, j}$ to use the tube connecting crossings $(i, j)$ and $(i+1, j)$. Please help Prof. Pang to find out which tubes he should use such that the restrictions are satisfied and the total cost is minimized.

inputFormat:
The first line contains a single positive integer $T$ denoting the number of test cases.

For each test case, the first line contains two integers $n$, $m$ ($1 \leq n, m \leq 100$) separated by a single space.

The $i$-th of the following $n$ lines contains $m$ integers ${count}_{i, 1}, {count}_{i, 2}, \dots, {count}_{i, m}$ ($0 \leq {count}_{i, j} \leq 4$) separated by single spaces.

The $i$-th of the following $n+1$ lines contains $m$ integers ${a}_{i, 1}, {a}_{i, 2}, \dots, {a}_{i, m}$ ($1 \leq {a}_{i, j} \leq 10^9$) separated by single spaces.

The $i$-th of the following $n$ lines contains $m+1$ integers ${b}_{i, 1}, \mathit{b}_{i, 2}, \dots, {b}_{i, m+1}$ ($1 \leq {b}_{i, j} \leq 10^9$) separated by single spaces.

It is guaranteed that $nm$ is an $\textbf{even}$ number and that the total sum of $nm$ over all test cases does not exceed $10^4$.

outputFormat:
For each test case, output an integer that denotes the minimum cost.

If there is no valid configuration, output $\texttt{-1}$ instead.


title: [EC Final 2020] Rooks

description:
Prof. Pang plays chess against his rival Prof. Shou. They are the only two players in the game. The chessboard is very large and can be viewed as a 2D plane. Prof. Pang placed $n_1$ rooks and Prof. Shou placed $n_2$ rooks. Each rook is a point with integer coordinates on the chessboard. One rook is $\textit{attacked}$ by another rook if they satisfy all of the following conditions:

- They are placed by different players.
- They have the same $x$-coordinate or $y$-coordinate.
- There is no other rook on the line segment between them.

Help Prof. Pang and Prof. Shou to decide which rooks are attacked.

inputFormat:
The first line contains two integers $n_1, n_2$ ($1\le n_1, n_2\le 200000$) separated by a single space denoting the number of rooks placed by Prof. Pang and the number of rooks placed by Prof. Shou.

The $i$-th ($1\le i\le n_1$) line of the next $n_1$ lines contains two integers $x, y$ ($-10^9\le x, y\le 10^9$) separated by a single space denoting the location $(x, y)$ of the $i$-th rook placed by Prof. Pang.

The $i$-th ($1\le i\le n_2$) line of the next $n_2$ lines contains two integers $x, y$ ($-10^9\le x, y\le 10^9$) separated by a single space denoting the location $(x, y)$ of the $i$-th rook placed by Prof. Shou.

It is guaranteed that the $n_1+n_2$ rooks placed by the players are distinct (i.e., no two rooks can have the same location).

outputFormat:
Output a string with length $n_1$ on the first line. The $i$-th ($1\le i\le n_1$) character should be $1$ if the $i$-th rook placed by Prof. Pang is attacked and $0$ otherwise.

Output a string with length $n_2$ on the second line. The $i$-th ($1\le i\le n_2$) character should be $1$ if the $i$-th rook placed by Prof. Shou is attacked and $0$ otherwise.


title: [EC Final 2020] Prof. Pang's sequence

description:
Prof. Pang is given a fixed sequence $a_1, \ldots, a_n$ and $m$ queries.

Each query is specified by two integers $l$ and $r$ satisfying $1\le l\le r\le n$. For each query, you should answer the number of pairs of integers $(i, j)$ such that $l\le i\le j\le r$ and the number of distinct integers in $a_i, \ldots, a_j$ is odd.

inputFormat:
The first line contains a single integer $n$ ($1\le n\le 5\times 10^5$).

The next line contains $n$ integers $a_1, \ldots, a_n$ ($1\le a_i\le n$ for all $1\le i\le n$) separated by single spaces.

The next line contains a single integer $m$ ($1\le m\le 5\times 10^5$).

Each of the next $m$ lines contains two integers $l$ and $r$ ($1\le l\le r\le n$) separated by a single space denoting a query.

outputFormat: For each query, output one line containing the answer to that query.


title: [EC Final 2020] Prof. Pang Earning Aus

description:
Prof. Pang has only $1$ Au in his pocket. (Yes, Prof. Pang is from Austan and he uses the currency Au there.)

He will make use of a balloon store and a candy store to make money: In the balloon store, Prof. Pang can buy $k_{ab}$ balloons for the price of $1$ Au or buy $k_{cb}$ balloons for the price of $1$ candy. In the candy store, Prof. Pang can buy $k_{ac}$ candies for the price of $1$ Au or buy $k_{bc}$ candies for the price of $1$ balloon. Prof. Pang can also sell one balloon and get $k_{ba}$ Aus. He can sell one candy and get $k_{ca}$ Aus. The only constraint to him is that there are only $n_b$ balloons in the balloon store and only $n_c$ candies in the candy store. He can buy balloons and candies only when supplies last. Even if he sells some of his balloons or candies, the number of balloons and candies in the stores will not increase.

Each of the six transactions can be performed in any order for any times ($0$ or more) but they are not separable (for example, Prof. Pang can not buy $k_{ab}/2$ balloons for the price of $1/2$ Au).

Please find out how many Aus he can make at most.

inputFormat:
The first line contains a single integer $T$ ($1\le T\le 1000$) denoting the number of test cases.

Each of the next $T$ lines contains eight integers $n_b$, $n_c$, $k_{ab}$, $k_{ba}$, $k_{ac}$, $k_{ca}$, $k_{bc}$, $k_{cb}$ ($1\le n_b, n_c\le 10^9$, $1\le k_{ab}, k_{ba}, k_{ac}, k_{ca}, k_{bc}, k_{cb}\le 100$) separated by single spaces.

outputFormat: For each test case, print one line containing the answer.

hint: In the first example, Prof. Pang buys $2$ balloons with $1$ Au and then sells $2$ balloons and gets $4$ Aus. Then he buys $2$ candies with $1$ Au, sells $2$ candies and gets $4$ Aus.


title: [EC Final 2020] Plants vs Zombies

description:
Prof. Pang is playing $\textit{Plants vs Zombies}$.

Imagine that the game is played on a number axis. The following are the elements in the game:

- $n$ zombies. The $i$-th zombie appears at $0$ on the number axis at time $t_i$ with health point $h_i$. The zombies have the same moving speed $V$ and they all move to the right.
- $m$ spikeweeds. The $i$-th spikeweed is of position $p_i$ and attack power $a_i$.
- One peashooter at the position of $10^{100}$. It shoots $K$ peas of attack power $D$ every second.

Every second in the game is processed as follows:

- When the $x$-th second begins, the zombies whose $t_i$s equal $x$ appear at position $0$.
- After that, for each appeared and alive zombie $u$, it will suffer from the spikeweeds whose positions are in $(P_u, P_u + V]$ where $P_u$ is the current position of the $u$-th zombie. So its health point will be decreased by $\sum\limits_{1\le i\le m, P_u < p_i \le P_u + V} a_i$. The zombie dies if its health point is no more than zero. Otherwise, it is still alive and its position will be increased by $V$.
- When the $x$-th second ends, the peashooter shoots $K$ peas in a row. For each pea, it will hit the zombie that is alive and of the maximum position currently. If there are multiple zombies of the maximum position, the pea hits the one of the minimum index. The health point of the zombie being hit decreases by $D$. This zombie dies if its health point is decreased to some value no more than $0$. The peas are processed one by one, not simultaneously. (For example, if a zombie is killed by the first pea, the second pea cannot hit it since it dies before the second pea is shot.) If no alive zombie exists, the remain peas will hit nothing.

Prof. Pang wants to know the death time (in seconds) of all the $n$ zombies.

inputFormat:
The first line contains five integers $n,m,V,K,D$ ($1\le n,m \le 10^5, 1\le V,K,D \le 10^9$) separated by single spaces.

Each of the following $n$ lines contains two integers $t_i, h_i$ ($1\le t_i,h_i \le 10^9$) separated by a single space.

Each of the following $m$ lines contains two integers $p_i, a_i$ ($1\le p_i,a_i \le 10^9$) separated by a single space.

outputFormat: Output one line containing $n$ integers, where the $i$-th integer denotes the death time (in seconds) of the $i$-th zombie.

hint:
During the first second:

- The first zombie appears and then moves to position 1. It suffers $6$ damage points ($2$ from the first spikeweed, $4$ from the two peas).
- The third zombie appears and then moves to position 1. It suffers $2$ damage points (from the first spikeweed) and dies (since its health point becomes $-1$).

During the second second:

- The first zombie moves to position $2$ and suffers $6$ damage points ($4$ from the second spikeweed, $2$ from the first pea) and dies (since its health point becomes $-1$).
- The second zombie appears and then moves to position $1$. It suffers $4$ damage points ($2$ from the first spikeweed, $2$ from the second pea).

During the third second:

- The second zombie moves to position $2$, suffers $4$ damage points ($4$ from the second spikeweed) and dies (since its health point becomes $0$).
- The peas hit no zombie during this second.

So the death times of the zombies are $2$, $3$, $1$, respectively.


title: [EC Final 2020] Circle

description:
Prof. Pang does research on the minimum covering circle problem. He does not like random algorithms so he decides to find an efficient deterministic one. He starts with the classical idea of binary search. In each iteration of the binary search, the following problem needs to be solved:

Given the radius $r$ of a circle and a convex hull $C$, let $S$ be defined as

$$S=\{p\ |\  \text{the circle with center $p$ and radius $r$ covers $C$}\}.$$

Find the area of $S$.

inputFormat:
The first line contains a single positive integer $T$ denoting the number of test cases.

For each test case, the first line contains two integers $n$ and $r$ ($1\le n\le 1000$, $1\le r\le 30000$) separated by a single space denoting the number of vertices of the convex hull and the radius. If $n=1$, the convex hull contains only $1$ point. If $n=2$, the convex hull is a line segment.

Each of the following $n$ lines contains two integers $x, y$ ($-10000\le x, y\le 10000$) separated by a single space denoting a vertex at $(x, y)$. It is guaranteed that no two vertices coincide and no three vertices are collinear. Vertices are listed in counter-clockwise order.

It is guaranteed that the sum of $n$ over all test cases does not exceed $200000$.

outputFormat: Output a single decimal indicating the answer. Your answer will be considered correct if the absolute or relative error is no more than $10^{-6}$.


title: [EC Final 2020] Allin

description:
$\textbf{Texas hold 'em}$ (also known as $\textbf{Texas holdem}$, $\textbf{hold 'em}$, and $\textbf{holdem}$) is one of the most popular variants of the card game of poker. $\textbf{Please read the following rules as they may be different from the regular rules.}$ $\textbf{Two}$ cards, known as $\textbf{hole cards}$, are dealt $\textbf{face-down}$ to each player. Each player only knows his own hole cards. And then $\textbf{five community cards}$ are dealt in three stages $\textbf{face-up}$. The stages consist of a series of three cards (``the flop``), later an additional single card (``the turn`` or ``fourth street``), and a final card (``the river`` or ``fifth street``). All players know the face-up cards that are already dealt. All cards are drawn from a standard 52-card deck. A standard 52-card deck comprises $13$ ranks in each of the four French suits: clubs ($\clubsuit$), diamonds ($\diamondsuit$), hearts ($\heartsuit$) and spades ($\spadesuit$). Each suit includes an Ace (A), a King (K), Queen (Q) and Jack (J), each depicted alongside a symbol of its suit; and numerals or pip cards from the Deuce (Two) to the Ten, with each card depicting that many symbols (pips) of its suit. $\textbf{No card can be drawn more than once.} $

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

Individual cards are ranked as follows (high-to-low): A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2. $\textbf{Each player seeks the best five-card poker hand from any combination of the seven cards}$ -- $\textbf{the five community cards and his two hole cards}.$

The following table shows the possible five-card poker hand types in $\textbf{increasing order}$ of their values. Each type has a specific ordering of the five cards that is described below. $\textbf{The following part is describing how to compare two hands}$, $\textbf{which is the same as the regular rule.}$

- $\textbf{Highcard}$: Simple value of the card. The cards are ordered as $a_1a_2a_3a_4a_5$ such that $a_1>a_2>a_3>a_4>a_5$. ($a_i$ represents the rank of $i$-th card.)
![](https://cdn.luogu.com.cn/upload/image_hosting/4f6fchzz.png)
- $\textbf{Pair}$: Two cards with the same value. The cards are ordered as $a_1a_2a_3a_4a_5$ such that $a_1=a_2$, $a_3>a_4>a_5$, $a_1 \ne a_3$, $a_1 \ne a_4$, $a_1 \ne a_5$.
![](https://cdn.luogu.com.cn/upload/image_hosting/fakv9qbh.png)
- $\textbf{Two pairs}$: Two times two cards with the same value. The cards are ordered as $a_1a_2a_3a_4a_5$ such that $a_1=a_2$, $a_3=a_4$, $a_1 > a_3$, $a_1 \ne a_5$, $a_3 \ne a_5$.
![](https://cdn.luogu.com.cn/upload/image_hosting/89uwdv5l.png)
- $\textbf{Three of a kind}$: Three cards with the same value. The cards are ordered as $a_1a_2a_3a_4a_5$ such that $a_1=a_2=a_3$,$a_4 > a_5$, $a_1 \ne a_4$, $a_1 \ne a_5$.
![](https://cdn.luogu.com.cn/upload/image_hosting/lbzmp0in.png)
- $\textbf{Straight}$: Sequence of 5 cards in increasing value. The cards are ordered as $a_1a_2a_3a_4a_5$ such that $a_i$ is exactly one rank above $a_{i+1}$ for all $1\le i\le 4$. $\textbf{Specially, if a5 is Ace, a4 can be 2. In this case, Ace is considered one rank below 2.}$
![](https://cdn.luogu.com.cn/upload/image_hosting/7mu6yjj3.png)
- $\textbf{Flush}$: 5 cards of the same suit. The cards are ordered as $a_1a_2a_3a_4a_5$ such that all the five cards have the same suit and $a_1>a_2>a_3>a_4>a_5$.
![](https://cdn.luogu.com.cn/upload/image_hosting/rlnqq9fx.png)
- $\textbf{Full house}$: Combination of three of a kind and a pair. The cards are ordered as $a_1a_2a_3a_4a_5$ such that $a_1=a_2=a_3$, $a_4=a_5$.
![](https://cdn.luogu.com.cn/upload/image_hosting/99za5m4u.png)
- $\textbf{Four of a kind}$: Four cards of the same value. The cards are ordered as $a_1a_2a_3a_4a_5$ such that $a_1=a_2=a_3=a_4$.
![](https://cdn.luogu.com.cn/upload/image_hosting/d15acddn.png)
- $\textbf{Straight flush}$: Straight of the same suit. The cards are ordered as $a_1a_2a_3a_4a_5$ such that all the five cards have the same suit and that $a_i$ is exactly one rank above $a_{i+1}$ for all $1\le i\le 4$. $\textbf{Specially, if a5 is Ace, a4 can be 2. In this case, Ace is considered one rank below 2.}$
![](https://cdn.luogu.com.cn/upload/image_hosting/f7zis4qc.png)
- $\textbf{Royal flush}$: Straight flush from Ten to Ace. The cards are ordered as $a_1a_2a_3a_4a_5$ such that $a_1, a_2, a_3, a_4, a_5$ are Ace, King, Queen, Jack, Ten of the same suit.
![](https://cdn.luogu.com.cn/upload/image_hosting/mgyidu8m.png)

To compare two hands, first, we will compare the type of two hands. For example, one hand is $\textbf{Four of a kind}$, the other hand is $\textbf{Full house}$, $\textbf{Four of a kind}$ always win $\textbf{Full house}$.

If the types of two hands are the same, we compare the ranks of the cards. We will order the card as described above, and compare them one by one. Firstly, we will compare the first card. If a hand's first card has a higher rank, it wins. If the first cards of the two hands have the same rank, we will compare the second card, and so on. If the cards have the same rank in every position, no one wins. The suit of cards never matters. For example, $\clubsuit$ 5, $\diamondsuit$ 5, $\heartsuit$ 5, $\spadesuit$ 2, $\clubsuit$ 2 can win $\diamondsuit$ 3, $\spadesuit$ 3, $\heartsuit$ 3, $\diamondsuit$ A, $\heartsuit$ A. Since they are both $\textbf{Full house}$, and we will compare the ranks of the three cards of a kind at first.

Consider the case that the hole cards of Alice are $\clubsuit$ A, $\diamondsuit$ 4 and the hole cards of Bob are $\heartsuit$ 2, $\spadesuit$ 3. The community cards are $\spadesuit$ A, $\heartsuit$ 4, $\spadesuit$ 5, $\clubsuit$ Q, $\heartsuit$ Q. The best hand of Alice (five cards among her hole cards and the community hards) is $\clubsuit$ A, $\spadesuit$ A, $\clubsuit$ Q, $\heartsuit$ Q, $\spadesuit$ 5, which is $\textbf{Two pairs}$. The best hand of Bob is $\spadesuit$ 5, $\heartsuit$ 4, $\spadesuit$ 3, $\heartsuit$ 2, $\spadesuit$ A, which is $\textbf{Straight}$. Thus, Bob wins.

Players have betting options to check, call, raise, or fold. $\textbf{In this problem, we do not care about the meanings of these bets.}$ Rounds of betting take place before the flop is dealt and after each subsequent deal. The player who has the best hand and has not folded by the end of all betting rounds wins all of the money bet for the hand, known as the pot. In certain situations, a ``split-pot`` or ``tie`` can occur when two players have hands of equivalent value. This is also called a ``chop-pot``. $\textbf{In this problem, we assume the two players never fold.}$ So the player with the best five-card poker hand from any combination of the seven cards wins. If the two players have hands of equal values, no one wins.

To simplify the statement, we do not introduce the detailed rules here.

Daddy Dream is a world-famous $\textbf{Texas hold 'em}$ player. As a strong challenger, Wolf Chicken wants to beat Daddy Dream. Wolf Chicken plays first after ``the flop`` (three cards are dealt face-up). Both players know the three face-up cards and each player knows his own two hole cards. Wolf Chicken will choose to allin if and only if he will certainly win whatever the ``the turn``, ``the river`` (the remaining two community cards that have not been revealed) and Daddy Dream's hole cards are. Otherwise, Wolf Chicken will choose to check.

Given Wolf Chicken's two hole cards and the three flop cards, help him to determine whether he can allin.

inputFormat:
The first line contains a single integer $T$ ($1\le T \le 100000$) denoting the number of test cases.

For each test case, there is one line containing five strings $h_1, h_2, c_1, c_2, c_3$ separated by single spaces denoting the first hole card, the second hole card, the first community card, the second community card and the third community card.

For each card, the first character of its corresponding string denotes its rank. (Possible ranks are `2` ,`3`,`4`,`5`,`6`,`7`,`8`,`9`,`T`,`J`,`Q`,`K`,`A`. `T` denotes $10$.) The second character denotes its suit. `C` denotes clubs. `D` denotes diamonds. `H` denotes hearts. `S` denotes spades.

It is guaranteed that each card appears at most once in one test case.

outputFormat: For each test case, print one line. Print $\texttt{allin}$ if Wolf Chicken will certainly win. Otherwise, print $\texttt{check}$.


title: [EC Final 2020] Square

description:
Father Study loves math very much.

Given a sequence of integers $a_1,a_2,...,a_n$, Father Study wants to calculate another sequence of integers $t_1,t_2,...,t_n$ satisifing
- For each $i~(1 \le i \le n)$, $t_i > 0$.
- For each $i~(1\le i < n)$, $a_i \times t_i \times a_{i+1} \times t_{i+1}$ is a square number. (In mathematics, a square number or perfect square is an integer that is the square of an integer, in other words, it is the product of some integer with itself.)
- $\prod_{i=1}^{n}{t_i}$ is minimized.

Please help Father Study to calculate the answer --- the minimum value of $\prod_{i=1}^{n}{t_i}$. Because the answer is too large, please output the answer modulo $1000000007$.

inputFormat:
The first line contains a single integer $n$ ($1\le n \le 100000$).

The second line contains $n$ integers $a_1, a_2, ..., a_n$ ($1 \le a_i \le 1000000$) separated by single spaces.

outputFormat: Output one integer -- the answer modulo $1000000007$.


title: [EC Final 2020] Fillomino

description:
Prof. Pang is the king of Pangland. Pangland is a board with size $n\times m$. The cell at the $i$-th row and the $j$-th column is denoted as cell $(i, j)$ for all $1\le i\le n, 1\le j\le m$. If two cells share an edge, they are connected. The board is $\textbf{toroidal}$, that is, cell $(1,y)$ is also connected to $(n,y)$ and $(x,1)$ is also connected to $(x,m)$ for all $1\le x\le n, 1\le y\le m$.

Prof. Pang has three sons. We call them the first son, the second son and the third son. Each of them lives in a cell in Pangland. The $i$-th son lives in cell $(x_i, y_i)$. No two sons live in the same cell. Prof. Pang wants to distribute the cells in Pangland to his sons such that

- Each cell belongs to exactly one son.
- There are $cnt_i$ cells that belong to the $i$-th son for all $1\le i\le 3$.
- The cells that belong to the $i$-th son are connected for all $1\le i\le 3$.
- The cell that the $i$-th son lives in must belong to the $i$-th son himself for all $1\le i\le 3$.

Please help Prof. Pang to find a solution if possible.

inputFormat:
The first line contains a single integer $T$ ($1\leq T\leq 10^5$) denoting the number of test cases.

For each test case, the first line contains two integers $n, m$ ($3\leq n,m \leq 500$) separated by a single space.

The next line contains three positive integers $cnt_1,cnt_2,cnt_3$ ($cnt_1+cnt_2+cnt_3 = n m$) separated by single spaces.

The $i$-th line of the next $3$ lines contains two integers $x_i, y_i$ ($1\le x_i\le n, 1\le y_i\le m$) separated by a single space.

It is guaranteed that $(x_1,y_1)$, $(x_2, y_2)$, $(x_3, y_3)$ are distinct.

It is guaranteed that the sum of $nm$ over all test cases is no more than $10^6$.

outputFormat: For each test case, if there is no solution, output $\texttt{-1}$ in one line. Otherwise, output $n$ lines. Each line should contain $m$ characters. The $j$-th character in the $i$-th line should be $\texttt{A}$ if cell $(i, j)$ belongs to the first son, $\texttt{B}$ if cell $(i, j)$ belongs to the second son and $\texttt{C}$ if cell $(i, j)$ belongs to the third son. Cell $(x_i, y_i)$ must belong to the $i$-th son for all $1\le i\le 3$. The cells that belong to the $i$-th son must be connected for all $1\le i\le 3$.


title: [语言月赛 202401] 小跳蛙

type: B

description:
有 $n - 1$ 只小跳蛙在池塘中，依次被编号为 $1, 2, \cdots, n - 1$。池塘里有 $n$ 个位置，每一个位置上有一个数字 $a_i$。如果 $a_i = 0$，则表示这个位置是一个空位；否则表示这个位置上存在一个编号为 $a_i$ 的小跳蛙。

接下来的 $n-1$ 分钟，小跳蛙们将进行跳跃。第 $i$ 分钟，编号为 $i$ 的小跳蛙将跳到空位上。

请你输出 $n-1$ 分钟后池塘中每个位置的数字，即每个位置是否为空、小跳蛙编号是多少。

inputFormat:
输入共两行。

第一行一个整数 $n$。
第二行 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$。

outputFormat: 输出一行 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$。 表示 $n-1$ 分钟后池塘的状态。

hint:
### 样例解释 #1

- 第一分钟后：`0 2 1 3 4`
- 第二分钟后：`2 0 1 3 4`
- 第三分钟后：`2 3 1 0 4`
- 第四分钟后：`2 3 1 4 0`

因此最终池塘的状态为 `2 3 1 4 0`

### 数据规模与约定

对于 $50\%$ 的数据，满足 $1 \leq n \leq 10 ^ 3$。

对于 $100\%$ 的数据，满足 $1 \leq n \leq 10^6$，保证序列 $a$ 是一个 $0 \sim n - 1$ 这些数字的排列。


title: 「Daily OI Round 3」Tower

background:
定义 $(x_1,y_1),(x_2,y_2)$ 的 `A 距离` 为 $\max\{|x_1-x_2|,|y_1-y_2|\}+1$，下文中的距离都指的是 `A 距离`。

比如说，$(1,1)$ 和 $(3,8)$ 的 `A 距离` 为 $\max\{|1-3|,|1-8|\}+1=8$。

比如说，$(46,1)$ 和 $(35,9)$ 的 `A 距离` 为 $\max\{|46-35|,|1-9|\}+1=12$。

description:
A 国的国土可以看成是 $n\times m$ 的矩阵，第 $x$ 行第 $y$ 列坐标为 $(x,y)$。

国土可以是山地，用 `#` 表示，可以是平地，用 `.` 表示。

A 国在每一个平地建了一个能量塔，能量塔搜集能量的范围是正方形的。如果 $e$ 满足到该能量塔 `A 距离` **不超过** $e$ 的地方是 A 国的国土，并且该地方是平地，则称 $e$ 是该能量塔的基准能量。

一个能量塔的综合能量 $E$ 为该能量塔基准能量 $e$ 的最大值。

特殊地，如果这个地方没有能量塔，该处综合能量 $E=0$，否则，该处的综合能量就是能量塔的综合能量。

记第 $i$ 行第 $j$ 列的综合能量为 $E_{i,j}$。

记一个国家的能量总和 $\xi=\sum\limits^n_{i=1}\sum\limits_{j=1}^mE_{i,j}^2$。

你需要求一个国家的能量总和 $\xi$。

当然，由于特殊的原因（比如宇宙射线的影响），某一个地方的平地可能会突然变成山地，当地的能量塔也会被摧毁，而且影响到附近能量塔的综合能量 $E$。

作为 A 国的参谋，国王想让你预备方案，看看每一个非山地的点变成山地之后，该国家的能量总和是多少。

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

下面是一个 $n\times m$ 的矩阵，第 $i$ 行第 $j$ 列为 `#` 或 `.`，描述 A 国的地形。

outputFormat:
输出共 $n+1$ 行。

第一行一个整数 $\xi$，表示 A 国开始的能量总和。

下面是一个 $n\times m$ 的矩阵，第 $i+1$ 行第 $j$ 个整数表示 $(i,j)$ 变成山地之后该国家的能量总和 $\xi_{i,j}$，特殊地，如果 $(i,j)$ 原来是山地，输出 $-1$。


title: 「Cfz Round 2」Weighted Mean

description:
给定一个长度为 $n$ 的序列 $a$ 和一个整数 $m$，保证序列 $a$ 中的每个元素均为不大于 $m$ 的正整数，且每个元素互不相等。

你需要构造一个长度为 $n$ 的序列 $b$，满足：

- 序列 $b$ 中的每个元素均为不大于 $m$ 的正整数；
- $\dfrac{\sum\limits_{i=1}^n (a_i \cdot b_i)}{\sum\limits_{i=1}^n b_i}$ 为整数，即 $a_i$ 的权为 $b_i$ 时，序列 $a$ 的加权平均数为整数；
- 不存在有序三元整数组 $(i,j,k)$，满足 $1\le i<j<k\le n$ 且 $b_i=b_j=b_k$；

或报告无解。

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

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

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

- 第一行输入两个整数 $n,m$。
- 第二行输入 $n$ 个整数，表示给定的序列 $a$。

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

- 若存在满足条件的序列 $b$，则输出用空格分隔的 $n$ 个整数，表示你构造的序列 $b$；
- 若不存在满足条件的序列 $b$，则输出 $-1$。

**所有满足要求的输出均可通过。**

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

对于第 $1$ 组测试数据，给出的样例的加权平均数为 $\dfrac{1 \times 1+2 \times 2 + 3 \times 1}{1+2+1}=2$，为整数。

输出 `1 5 1` 也视作正确，其加权平均数为 $2$。

但是输出 `1 6 1` 不正确，虽然其加权平均数为 $2$，但是 $b_2>5$。

输出 `1 2 3` 也不正确，其加权平均数为 $\dfrac{7}{3}$，不为整数。

输出 `1 1 1` 也不正确，虽然其加权平均数为 $2$，但是存在有序三元组 $(1,2,3)$ 满足 $1 \leq 1 < 2 < 3 \leq 3$ 且 $b_1=b_2=b_3$。

对于第 $2$ 组测试数据，可以证明不存在满足条件的序列 $b$。

对于第 $3$ 组测试数据，给出的样例的加权平均数为 $\dfrac{1 \times 1+2 \times 1 + 5 \times 3+9 \times 4}{1+1+3+4}=6$，为整数。

#### 「数据范围」

设 $\sum n$ 表示单个测试点中 $n$ 的和。

对于所有数据，$1 \le T \le 1000$，$1 \le n \le 10^6$，$1 \le a_i \le m \le 10^9$，$\sum n \le 10^6$，保证序列 $a$ 中的每个元素间互不相等。

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


title: [语言月赛 202312] 禁止在 int 乘 int 时不开 long long

description:
在比赛中，根据数据范围，分析清楚变量的取值范围，是非常重要的。int 类型变量与 int 类型变量相乘，往往可能超出 int 类型可以表示的取值范围。

现在，给出两个 int 类型变量 $x,y$ 及其取值范围，请问 $x\times y$ 的值是否可能超过 int 类型可以表示的范围？

> 提示：int 类型可以表示的范围为 $[-2147483648, 2147483647]$，即 $[-2^{31},2^{31}-1]$。也就是，int 类型可以表示的最小值为 $-2147483648$，最大值为 $2147483647$。

inputFormat:
输入共两行。

输入的第一行为两个整数 $x_l,x_u$，表示变量 $x$ 的取值范围为 $x_l \le x \le x_u$。

输入的第二行为两个整数 $y_l,y_u$，表示变量 $y$ 的取值范围为 $y_l \le y \le y_u$。

outputFormat:
输出一行一个字符串：

- 若会超过，则输出 `long long int`；
- 若不会超过，则输出 `int`。


title: [语言月赛 202312] 函数零点

description:
小 F 在做梦时得到了一个神秘函数 $\phi(x)$，这是一个连续函数。

零点 $x=x_0$ 是一系列特殊的数，使得 $\phi(x_0)=0$，很可惜的是，$\phi(x)$ 函数相当复杂，无法精确计算其零点。

> **零点存在定理**
>
> 若 $\phi(a)\cdot \phi(b)<0$，则在区间 $(a,b)$ 内，函数 $\phi(x)$ 至少存在一个零点。

小 F 计算了 $0 \sim N$ 范围内，每个整数 $w$ 的函数值 $\phi(w)$，请问，运用零点存在定理，可以确定在 $(0,N)$ 范围内，函数 $\phi(x)$ **至少**有多少零点？

inputFormat:
输入共两行。

输入的第一行为一个整数 $N$。

输入的第二行为 $N+1$ 个整数，依次代表 $\phi(0),\phi(1),\cdots,\phi(N)$。

**保证第二行中所有数据不为 $0$**。

outputFormat: 输出一行一个整数，代表在 $(0,N)$ 上，$\phi(x)$ 至少有多少个零点。

hint:
### 样例 1 说明

$\phi(0)=-2,\phi(1)=1,\phi(2)=3,\phi(3)=-2,\phi(4)=1,\phi(5)=2$。在 $(0,1)$，$(2,3)$，$(3,4)$ 上各至少有一个零点。

- $\phi(0) \times \phi(1) = -2 < 0$，按照零点存在定理，在 $0 < x < 1$ 的区域一定会有至少一个零点。
- $\phi(1) \times \phi(2) = 3 > 0$，无法保证在 $1 < x < 2$ 的区域存在零点。
- $\phi(2) \times \phi(3) = -6 < 0$，按照零点存在定理，在 $2 < x < 3$ 的区域一定会有至少一个零点。
- $\phi(3) \times \phi(4) = -2 < 0$，按照零点存在定理，在 $3 < x < 4$ 的区域一定会有至少一个零点。
- $\phi(4) \times \phi(5) = 2 > 0$，无法保证在 $4 < x < 5$ 的区域存在零点。

故至少能保证有 $3$ 个零点。

### 数据规模与约定

 - 对于 $30\%$ 的测试数据，$1 \le N \le 5000$，$\phi(i) \in \{-1, 1\}$。
 - 对于 $100\%$ 的测试数据，$1 \le N \le 10^5$，$0<|\phi(i)|\le10^9$。


title: [语言月赛 202312] 打表过样例

background:
众所周知，一名负责任的出题人，不应当让如下的打表程序获得过多的分数。

```cpp
#include<iostream>
int main() {
    std::cout << "Specific Value\n";
}
```

> 这个程序的功能是，输出一个特定的内容，以尝试通过一些测试点而获得分数。
>
> 经典的例子是：<https://www.luogu.com.cn/problem/P8819>，输出无解可以获得 45 分的成绩。

description:
很不幸，你遇到了不负责任的出题人。

在某道试题里，共有 $N$ 个测试点，组成了 $k$ 个 Subtask，第 $i$ 个 Subtask 包含 $p_i$ 个测试点，第 $j$ 个测试点的编号为 $w_{i,j}$。请注意，一个测试点可能属于多个 Subtask。

> **Subtask**
>
> 每个 Subtask 包含多个测试点和一个分值，当且仅当通过全部这些测试点时，才能获得这个 Subtask 的分值。一道题目的得分为通过的所有 Subtask 分值之和。

这是一道输出仅有一个数的题目，编号为 $i$ 的测试点，标准答案为 $A_i$。

很不幸，由于命题人不负责任，$A_i$ 中出现了大量重复，让打表选手有了可乘之机。

现在，你通过某种手段获得了全部的数据，请问输出哪个数，可以得到最高的分数？最高的分数是多少？

如果有多个数均可得到最高的分数，你只需要任意给出一个。

inputFormat:
输入共 $k+3$ 行。

输入的第一行为一个正整数 $k$。

接下来 $k$ 行：

- 第 $i$ 行的第一个数为 $p_i$，代表第 $i$ 个 Subtask 包含的测试点数目。
- 接下来 $p_i$ 个数，第 $j$ 个代表测试点编号 $w_{i,j}$。
- 最后一个数为 $S_i$，代表这个 Subtask 的分值。

输入的第 $k+2$ 行为一个正整数 $N$。

输入的第 $k+3$ 行为 $N$ 个非负整数，第 $i$ 个代表 $A_i$。

outputFormat:
输出两行，每行一个整数。

第一行表示获得的最大分值。

第二行表示输出的数。

**如果有多个数可以取到相同的最大分值，任意输出一个即可。**


title: [语言月赛 202312] 铅球杯

description:
蓝边铅球组织了“铅球杯”数据标注大赛。为了实现 Au 大满贯的宏大征途，LeAuingZ 报名参加了比赛。

蓝边铅球给出了 $N$ 个 int 类型变量的名字及其值，并要求 LeAuingZ 对 $k$ 句话进行数据标注。每句话由大小写英文字母、空格、半角逗号、半角句号和 `{`、`}` 组成。在 `{}` 之间的，为 $N$ 个变量名中的一个，LeAuingZ 需要将每一句话中全部的 `{变量名}` 替换为变量的值并输出。

例如，有 $a=3,b=4$，对于句子 `We know a is {a}, b is {b}.`，替换后将得到 `We know a is 3, b is 4.`。

LeAuingZ 觉得这个任务很无聊，决定编写一个程序来快速获得 Au。

inputFormat:
输入共 $N+k+1$ 行。

输入的第一行为两个整数 $N,k$。

接下来 $N$ 行，每行一个小写英文字符串、一个整数，分别代表变量名和变量的值。

接下来 $k$ 行，每行一个需要标注的句子。

outputFormat: 输出 $k$ 行，每行一个标注好的句子。

samples:
5 2
abc 1
a 2
b 3
c 4
d 5
We have {a} apples.
We {d}onot have pencils.

samples:
We have 2 apples.
We 5onot have pencils.

hint:
- 对于 $20\%$ 的测试数据，$k=1$。
- 对于另外 $30\%$ 的测试数据，$1 \le N \le 26$，变量名长度均为 $1$。
- 对于 $100\%$ 的测试数据，$1 \le N \le 5000$，$1 \le k \le 20$。变量名仅含英文小写字母，变量名长度不超过 $20$，变量的值在 int 范围内，标注前句子长度不超过 $5 \times 10^4$，保证 `{}` 成对合法出现。每句话由大小写英文字母、空格、半角逗号、半角句号和 `{`、`}` 组成。


title: [语言月赛 202312] 灵活控分

background: 时间回到 2014 年，T 小学正在举行期末考试。你是一名叫做肖芬途的学生，正在参加某门科目的期末考试。这门科目满分 $100$ 分。

description:
但是，由于考卷太难，老师宣布这门科目将采取「开根号乘十」的评分策略。具体的，如果试卷的分数是 $x$ 分，那么最终成绩单上的分数则为 $\left \lfloor 10 \sqrt x \right  \rfloor$ 分。

> 提示：对于非负数 $x$，$\sqrt x$ 代表 $x$ 的算术平方根。如果非负数 $y \times y = y ^ 2 = x$，那则称 $y = \sqrt x$。例如，$\sqrt 9 = 3$。
> 提示：$\left \lfloor x \right \rfloor$ 代表小于等于 $x$ 的最大整数。例如，$\left \lfloor 4.2 \right \rfloor = 4$。

已知这门考试的试卷分数和成绩单分数**一定都是整数**。对于这门考试，肖芬途的班主任要求他的成绩单分数至少要达到 $a$ 分。由于肖芬途是天才，可以随意控制他的试卷分数，因此他想要挑战用最少的卷面分数让成绩单分数达到 $a$ 分。

现在他想要知道这个最少的卷面分数是多少。

形式化地讲，给定一个非负整数 $a$，你需要找到最小的非负整数 $x$，使得 $\left \lfloor 10 \sqrt x \right  \rfloor \geq a$。

inputFormat: 输入共一行一个整数 $a$，代表老师要求肖芬途的成绩单至少达到的分数。

outputFormat: 输出共一行一个整数，代表为了达到要求，肖芬途卷面分数的最小值。

hint:
### 样例 1 解释

不难发现 $10 \sqrt {35} \approx 59.16$，$\left \lfloor  10 \sqrt {35} \right  \rfloor = 59$，而 $10 \sqrt {36} = 60$，因此肖芬途至少需要考到 $36$ 分。

### 数据规模与约定

对于 $100\%$ 的数据，$0 \leq a \leq 100$。


title: [语言月赛 202312] 异或构造题？

description:
给定 $n$ 个非负整数 $a _ 1, a _ 2, \cdots, a _ n$，你需要确定一个非负整数 $x$，使得 $a _ 1 \oplus a _ 2 \oplus \cdots \oplus a _ n \oplus x$ 最小。

你需要计算 $x$ 和 $a _ 1 \oplus a _ 2 \oplus \cdots \oplus a _ n \oplus x$。

其中 $\oplus$ 代表异或，$x \oplus y$ 在 C++ 中可表示为 `x ^ y`。
对于两个非负整数 $x,y$，它们的**异或**是指，将它们作为二进制数，对二进制表示中的每一位进行如下运算得到的结果：
 - $x$ 和 $y$ 的这一位上不同时，结果的这一位为 $1$；
 - $x$ 和 $y$ 的这一位上相同时，结果的这一位为 $0$。

例如：$0\oplus 0=0$，$1\oplus 0=1$，$0\oplus 1=1$，$1\oplus 1=0$。

inputFormat:
输入共两行。

第一行一个整数 $n$，代表序列 $a$ 的长度。
第二行 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，代表序列 $a$。

outputFormat: 输出共一行两个整数 $x$ 和 $a _ 1 \oplus a _ 2 \oplus \cdots \oplus a _ n \oplus x$。


title: [语言月赛 202312] 颜料覆盖

background: 一副精美的画作可能需要很多次重复的颜料涂抹。涂抹的一层层颜料会产生许多覆盖。这一次我们将这一个情景简化后交给了你，希望你能够解开颜料覆盖的奥秘。

description:
给定一个 $n$ 行 $m$ 列的矩阵 $a$。每一行代表画作的一块区域。每一行从前往后分别代表 $m$ 次绘画。

用 $a _ {i, j}$ 代表序列中第 $i$ 行第 $j$ 列的元素，$a _ {i, j}$ 代表区域 $i$ 在第 $j$ 次绘画中被涂抹的颜料强度。如果 $a _ {i, j} = 0$，那么代表区域 $i$ 在第 $j$ 次中未被涂抹。

现在，对于每个区域，你需要找出涂抹强度最大的一次是哪一次。同时，你需要找出，在这一次之前，有多少次涂抹（不计算未涂抹的情况）强度比这一次小。

保证对于某个区域，不会出现两次涂抹强度相同且最大。

inputFormat:
输入共 $n + 1$ 行。

第一行为两个整数 $n, m$，分别代表区域数和绘画次数。
接下来 $n$ 行，每行 $m$ 个整数，代表矩阵 $a$。

outputFormat: 输出共 $n$ 行，每行两个整数，分别代表涂抹强度最大的一次是哪一次，和在这一次之前，有多少次涂抹（不计算未涂抹的情况）强度比这一次小。

hint:
### 样例 1 解释
- 第一行（第一个区域）中，第 $\color{red}4$ 次涂抹的强度最大，为 $3$。在第 $4$ 次之前，有且仅有第 $2$ 次这一次「有涂抹（不为 $0$）」且「强度比第 $4$ 次小」，故答案为 `4 1`。
- 第二行（第二个区域）中，第 $\color{red}3$ 次涂抹的强度最大，为 $1$。在第 $3$ 次之前，该区域没有被涂抹过（即第 $3$ 次之前全为 $0$），故答案为 `3 0`。
- 第三行（第三个区域）中，第 $\color{red}5$ 次涂抹的强度最大，为 $5$。在第 $5$ 次之前，有 $\color{red}4$ 次「有涂抹」且「强度比第 $5$ 次小」，因此答案为 `5 4`。

### 数据规模与约定

对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 10 ^ 6$，$1 \leq n \times m \leq 10 ^ 6$，$0 \leq a _ {i, j} \leq 10 ^ 9$。

| 测试点 | $n$ | $m$ | 特殊性质  |
| :-: | :-: | :-: | :-: |
| $1$ | $= 1$ | $= 1$ | 无 |
| $2 \sim 3$ | $\leq 10$ | $\leq 10$ | 无 |
| $4 \sim 6$ | $\leq 10 ^ 3$ | $\leq 10 ^ 3$ | 无 |
| $7 $ | $\leq 1$ | $\leq 10 ^ 6$ | 无 |
| $8$ | $\leq 10 ^ 6$ | $\leq 1$ | 无 |
| $9 \sim 10$ | $\leq 10 ^ 6$ | $\leq 10 ^ 6$ | 每一行的第一个元素是这一行的最大值 |
| $11 \sim 12$ | $\leq 10 ^ 6$ | $\leq 10 ^ 6$ | 每一行的最后一个元素是这一行的最大值 |
| $13 \sim 14$ | $\leq 10 ^ 6$ | $\leq 10 ^ 6$ | 每一行有且仅有一个非 $0$ 元素 |
| $15 \sim 20$ | $\leq 10 ^ 6$ | $\leq 10 ^ 6$ | 无 |

保证在矩阵的某一行中不存在两个元素相同且最大，保证不存在某一行全部为 $0$。


title: 「LAOI-5」膜你赛

background: LAOI 团员们出了一场有 $10^{100}$ 道题的 CSP-J 膜你赛！

description:
比赛是 ICPC 赛制，先以过题数为第一关键字不升排序，再以罚时数为第二关键字不降排序。

有 $n$ 个巨佬前来爆切这场比赛，比赛一共 $m$ 分钟。

在第 $i$ 分钟（$0 \le i \le m-1$）的开始，$s_i$ 号巨佬先提交了 $t_i$ 个 WA 的评测（每个罚时 $x$ 分钟），然后通过了某一道题目。**于是，TA 的通过数增加 $1$，总罚时增加 $x \times t_i + i$ 分钟。**

第 $i$ 个巨佬共有 $k_i$ 个 WA，共过了 $a_i$ 道题（保证 $\sum_{i=1}^n a_i=m$）。为什么巨佬们没有把题目全部切完呢？因为他们觉得题目太简单了，觉得没意思，走了。

如果巨佬 $i$ 在**结束自己的所有提交**之后，发现自己在排行榜上的第一名（**不能并列**），那么称他「爆切比赛」。

试构造数列 $\{s_m\}$ 和 $\{t_m\}$，使得第 $i$ 个巨佬共有 $k_i$ 个 WA，共过了 $a_i$ 道题，且使「爆切比赛」的人数尽量多。

inputFormat:
共三行。

第一行三个整数 $n,m,x$。

第二行 $n$ 个整数，表示 $\{a_n\}$。

第三行 $n$ 个整数，表示 $\{k_n\}$。

outputFormat:
第一行输出最大的「爆切比赛」的人数。

第二、三行输出一组最大方案：

第二行 $m$ 个整数，表示 $\{s_m\}$。

第三行 $m$ 个整数，表示 $\{t_m\}$。


title: 「Cfz Round 3」Mex of Sequence

description:
**请注意本题特殊的时间限制。**

给定一个长度为 $n$ 的序列 $a$ 和一个整数 $m$。

我们定义一次操作为，**同时**将序列 $a$ 中的**每个**元素 $a_i$ 替换为序列 $a$ 中除 $a_i$ 以外的所有元素的 $\operatorname{mex}$。

你需要求出进行 $m$ 次操作后的序列 $a$。

其中，一个序列的 $\operatorname{mex}$ 为该序列中**未出现过的最小自然数**，例如：

- $\operatorname{mex}\{1,2,3\}=0$；
- $\operatorname{mex}\{0\}=1$；
- $\operatorname{mex}\{1,0,2,4\}=3$；
- $\operatorname{mex}\{2,1,3,0,2\}=4$。

特别地，当序列为空时，该序列的 $\operatorname{mex}$ 为 $0$。

outputFormat: 对于每组测试数据，输出一行，包含用空格分隔的 $n$ 个整数，表示进行 $m$ 次操作后的序列 $a$。

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

对于第 $1$ 组数据，因为 $\operatorname{mex}\{0,1,2\}=3$，$\operatorname{mex}\{1,1,2\}=0$，$\operatorname{mex}\{1,0,2\}=3$，$\operatorname{mex}\{1,0,1\}=2$，所以进行 $1$ 次操作后的序列 $a$ 为 $\{3,0,3,2\}$。

#### 「数据范围」

设 $\sum n$ 表示单个测试点中 $n$ 的和。

对于所有数据，$1 \le T \le 1000$，$1 \le n \le 10^6$，$1 \le m \le 10^9$，$0 \le a_i \le 10^9$，$\sum n \le 10^6$。

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


title: XOR Pairs

background: CT 每天只知道在伦敦哼哼蓝调，在校领导面前溜达，懒惰而浪荡的生活使他非常的潦倒，于是，他决定痛改前非学习数学……

description:
CT 在做数学题。

CT 手里一个长度为 $n$ 的序列 $a$，现在给定 CT $q$ 次操作，对于每次操作：
- 把 $a_x$ 改成 $y$ 。
- 求修改后数组中合法二元组的个数。

**注：** 对于一对满足 $a_i\oplus a_j > \max\{a_i,a_j\}$ 的 $(a_i,a_j)(i<j)$ 二元组，我们称其为合法二元组。其中 $\oplus $ 表示按位异或，$\max\{x,y\}$ 表示 $x,y$ 中的较大值。

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

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

接下来 $q$ 行，每行两个整数 $x,y$，代表一次把 $a_x$ 改成 $y$ 的操作。

outputFormat:
对于每一次操作：

一个整数表示所求的答案。


title: [NFLSPC #6] 所以 k 小生成树怎么做？

description:
给定一张无向带权无自环无重边的连通图，求前 $k$ 小生成树的权值。

- 生成树的权值为其所有边权之和。
- 两棵生成树不同，当且仅当存在一条边在一棵生成树上，但不在另一棵生成树上。
- 若第 $i$ 小生成树不存在，则输出 $-1$。

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

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$，分别表示无向边的两端及其权值。

outputFormat: 输出 $k$ 行，第 $i$ 行一个整数表示第 $i$ 小生成树的权值。

hint:
对于所有数据，$1\leq n \leq 5\times 10 ^ 4$，$n - 1\leq m\leq 10 ^ 5$，$1\leq k\leq 10 ^ 5$，$1\leq mk\leq 10 ^ 7$，$1\leq u_i, v_i\leq n$，$1\leq w_i\leq 10 ^ 9$。保证图连通，无自环，无重边。

- 子任务 1（$10$ 分）：$m ^ 2k\leq 10 ^ 6$。
- 子任务 2（$20$ 分）：保证每条边至多属于一个简单环。
- 子任务 3（$20$ 分）：$mk\leq 10 ^ 6$。
- 子任务 4（$50$ 分）：无特殊限制。

Source：NFLSPC #6 A by Alex_Wei


title: [NFLSPC #6] 真理祭坛

background:
天色已晚，围观的人群散得差不多了。人们可能都没有注意到，还有一个瘦小的身影在向真理祭坛跑去。

「你是哪个领域的科学家？怎么就你一个人？」排险者歪了歪头，看着眼前的小 Y 问道。

「我不是科学家。我只是一个高中生。」

「学生？」排险者很困惑，「那你想问什么？」

「我想知道宇宙的终极规律。」

「既然你只是个学生，你认为我该如何让你理解宇宙的规律呢？」

「啊？」小 Y 似乎感到很惊讶，片刻之后，他的脸上出现了些许失望的神情。「宇宙的真理不应该简洁到每个人都能理解吗……难道不是吗？」

「真理可没这么简单。且不说宇宙，我在此随意给你一些『道理』，你能用简洁的语言描述它吗？」

小 Y 抬起头来，看着排险者用全息投影显示在天空中的几串密密麻麻的零和一，陷入了沉思。

description:
有 $n$ 个 **命题变项**，记作 $P_0, P_1, \cdots, P_{n - 1}$，其 **真值** 是一个布尔值，要么为 $0$ 要么为 $1$。

我们称一个 **道理** 是一个输入 $n$ 个布尔值、输出一个布尔值的函数，即一个 $\{0, 1\}^n \to \{0, 1\}$ 的映射。

满足特定条件的字符串称为 **合式公式**（Well-Formed Formula，WFF），每个合式公式都对应着唯一一个道理，称为该公式的 **真值表**。具体地：

- 一个命题变项 $P_i$ 是合式公式，它的真值表总是输出其所接受的第 $i$ 个输入值（$n$ 个输入值的编号依次为 $0, 1, \cdots, n - 1$）。
- 如果 $k$ 个字符串 $A_1, A_2, \cdots, A_k$（$k \geq 1$）都是合式公式，则 $(A_1 \land A_2 \land \cdots \land A_k)$ 也是合式公式，它的真值表在接受输入 $I$ 时输出的值为 $A_1, A_2, \cdots, A_k$ 分别的真值表接受 $I$ 时输出的值的最小值。
- 如果 $k$ 个字符串 $A_1, A_2, \cdots, A_k$（$k \geq 1$）都是合式公式，则 $(A_1 \lor A_2 \lor \cdots \lor A_k)$ 也是合式公式，它的真值表在接受输入 $I$ 时输出的值为 $A_1, A_2, \cdots, A_k$ 分别的真值表接受 $I$ 时输出的值的最大值。
- 如果 $A$ 是合式公式，则 $\lnot A$ 也是合式公式，设 $A$ 的真值表接受输入 $I$ 时输出 $x$，则 $\lnot A$ 的真值表接受 $I$ 时输出 $1 - x$。

定义一个合式公式的 **大小** 为其所包含的 $\land$ 和 $\lor$ 的数量。现给定一个道理，请找到一个合式公式，使得其真值表是该道理，在此前提下让公式的大小尽可能小。

inputFormat:
**本题为提交答案题**，所有数据 `formula1.in` 至 `formula10.in` 已在附加文件中。

输入的第一行包含一个整数 $n$。

输入的第二行包含一个长度为 $2^n$ 的字符串 $a_{0 \sim 2^n - 1}$，描述给定的道理：如果对于任意 $0 \leq i < n$，输入的第 $i$ 个值是 $\left\lfloor\frac{x}{2^i}\right\rfloor \bmod 2$，则道理的输出为 $a_x$。

输入的第三行包含 $10$ 个评分参数，具体用处见「说明/提示」。

outputFormat:
针对给定的 $10$ 个输入文件，你需要分别提交你的输出文件 `formula1.out` 至 `formula10.out`。

每个输出文件包含一行，表示你给出的合式公式。其中括号用 `()` 表示，命题变项 $P_i$ 用数字 $i$ 表示（由于 $n \leq 10$，这一定是单个字符），$\land$ 用 `&` 表示，$\lor$ 用 `|` 表示，$\lnot$ 用 `!` 表示。**请不要擅自省略括号。**

hint:
对于所有数据，$1 \leq n \leq 10$。

对于每组数据，我们采用如下方式评分：

- 如果你的输出长度大于 $10^5$，得 $0$ 分。
- 如果你的输出不是合式公式，得 $0$ 分。
- 如果你的合式公式的真值表与输入给定的道理不同，得 $0$ 分。
- 如果上述条件都不满足，设 $s_{1 \sim 10}$ 为评分参数，$S$ 为你的公式的大小，则得分为 $\sum_{i = 1}^{10}[S \leq s_i]$。

每组数据满分 $10$ 分，共 $10$ 组数据，总分 $100$ 分（乘以得分系数前）。**保证存在满分解**。

---

我们提供了工具来测试你的输出。

下载附加文件 `checker.cpp` 并编译得到可执行文件 `checker.exe`（Windows）或 `checker`（Linux），其用法如下：

- 在终端中输入 `checker.exe X`（Windows）或 `./checker X`（Linux），或直接运行后输入 `X` 并换行，可以对第 $X$ 组数据 `formulaX.in/out` 进行测试。
- 在终端中输入 `checker.exe A B`（Windows）或 `./checker A B`（Linux），或直接运行后输入 `A B` 并换行，可以对输入文件名为 $A$、输出文件名为 $B$ 的数据进行测试。
- 如果输入不合法或输出有错误，会有相应提示。
- 如果没有错误，则会给出你的合式公式的大小。
- 输入文件可以与输入格式的描述完全相符，也可以略去评分参数一行。若 checker 检测到存在评分参数一行，还会给出你的得分。

Source：NFLSPC #6 C by chenxia25


title: [NFLSPC #6] 来点不那么魔怔的题面

description:
给定一个 $1\sim n$ 的排列 $p$ 和一个整数 $k$，要求找到 $p$ 的一个子序列 $\{p_{i_1}, p_{i_2}, \cdots, p_{i_m}\}$（$1\le i_1 < i_2 < \cdots < i_m\le n$）满足：

- 恰好有 $k$ 个 $j$ 满足 $1\le j\le m$ 且 $p_{i_j}$ 是 $p_{i_1}, p_{i_2}, \cdots, p_{i_m}$ 中从小往大数第 $j$ 个。

如果有多解，输出任意一组解即可。如果不存在合法的子序列，输出 $-1$。

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

接下来一行 $n$ 个整数 $p_1, p_2, \cdots, p_n$ 表示给定的排列。

outputFormat:
如果无解，输出一行一个整数 $-1$。

否则第一行输出一个整数 $m$ 表示子序列的长度。你需要保证 $1\le m\le n$。

接下来一行输出 $m$ 个整数 $i_1, i_2, \cdots, i_m$ 表示子序列的下标。你需要保证 $1\le i_j\le n$ 且 $i_j < i_{j+1}$（$1\le j < m$）。

hint:
对于所有数据，$1\le n\le 10 ^ 5$，$1\le k\le n$，$p_1, p_2, \cdots, p_n$ 为 $1\sim n$ 的排列。

- 子任务 1（$10$ 分）：$n\leq 20$。
- 子任务 2（$10$ 分）：$k = 2$。
- 子任务 3（$30$ 分）：$k = 3$。
- 子任务 4（$30$ 分）：$n\leq 10 ^ 3$。
- 子任务 5（$20$ 分）：无特殊限制。

Source：NFLSPC #6 D by tzc_wk


title: [NFLSPC #6] 挑战大数因子分解

background:
`NFLSPC #6` 在即，来不了现场的 *SolarPea* 要把自己的题目的 std 发给能去现场的 *PolarSea*。

为了防止有选手窃听他们的通信以获得 std，他们打算使用一个公钥加密算法来确保通信的安全性。

于是 *SolarPea* 使用了他在知乎上看到的有 “最大的加解密速度和安全性” 的算法，这个算法的安全性 “依赖于大数因子分解难题”：

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

你是一名拥有 `factorization oracle` 的参赛选手，并且你已经获得了公钥和明文。请你利用手上的 `factorization oracle`，破解出 std 吧。

description:
由于图片可能看不清，我们重新描述这个加密算法：

- 假设 *SolarPea* 要给 *PolarSea* 发一个消息 $M'$，那么他们会进行如下的操作。
- *PolarSea* 首先生成五个大整数 $P, S_4, S_6, S_7, S_1$，使得 $P < S_6 < S_4P$ 且 $S_5 = S_4P + S_6$ 且 $(S_6\bmod P) ^ 3 < S_4 ^ 3 < S_1 ^ 3 < (S_1 + 1) ^ 3 < S_7 ^ 3 < P$，并计算 $S_3 = S_4P + S_5$。
- 然后 *PolarSea* 将 $S_3, S_5, S_7, S_1$ 发给 *SolarPea*。
- *SolarPea* 拿到了 *PolarSea* 给他发的四个数。首先，他需要构造一个 $M$ 使得 $S_1 < M < S_7$，并且和 *PolarSea* 商量好一个通过 $M$ 算出 $M'$ 的方法（例如若 $M'$ 为比较小的正整数，则可以令 $M = M' + S_1$），这个方法是不保密的，所以拿到 $M$ 就相当于拿到 $M'$ 了，所以你可以不用关心 $M'$ 而是只关心 $M$。
- *SolarPea* 生成了两个满足 $(S_3 - S_5) ^ 3 < r < w$ 的数 $w, r$，并计算 $C = (S_3 - S_5) ^ 3w + MS_5 + r(S_3 - S_5)$，然后将 $C$ 发给 *PolarSea*。
- *PolarSea* 只需计算 $\frac{C \operatorname{\bmod} P}{(2S_5 - S_3) \operatorname{\bmod} P}$ 即可获得 $M$。

现在你截获了 *PolarSea* 和 *SolarPea* 之间的所有通信（即 $S_3, S_5, S_7, S_1, C$），请你利用已知的信息破解出 $M$。

inputFormat:
第一行，读入四个整数 $S_3, S_5, S_7, S_1$，表示公钥。

第二行，读入一个整数 $C$，表示密文。

outputFormat: 输出一行，包含一个值在 $S_1 < M < S_7$ 的整数 $M$，表示破解的明文。可以证明在给定限制下 $M$ 唯一。


title: [NFLSPC #6] 1064 病毒

background:
你的电脑中了 1064 病毒，现在电脑里储存的所有数字都开始坍缩了！

为了更彻底地毁灭你的电脑，对于十进制下的 $n$ 位数，邪恶的 1064 病毒会将它按照某种规则迭代至少 $n + 1$ 次，以确保你无法还原。

面对 1064 病毒，你手足无措。但是作为 OIer 的你想知道道道道道道道道道道道到到到到到到到到

description:
定义数字串为只含有数码 $0\sim 9$ 的串，奇数数码为 $1, 3, 5, 7, 9$，偶数数码为 $0, 2, 4, 6, 8$。

对数字串 $x$，设其中奇数数码，偶数数码和总数码个数分别为 $a, b, c$，则 $a + b = c = |x|$。定义 $g(x)$ 为将 $a, b, c$ 依次写下得到的数字串，**不忽略前导零**。例如 $g(\texttt{0}) = \texttt {011}$，$g(\texttt{1064}) = \texttt{134}$，$g(\texttt {822}) = \texttt {033}$，$g(\texttt{1092515503}) = \texttt{7310}$。

设 $f_k(x)$ 表示将 **数字** $x$ **忽略前导零** 写成数字串 $x'$ 后，将 $g(x')$ 迭代 $k$ 次得到的数字串对应的数字，即设 $x ^ * = g(g(\cdots g(x')))$（共有 $k$ 个 $g$），则 $f_k(x)$ 为将 $x ^ *$ 写成数字后的结果。

给定 $n, k$（**保证 $n < k$**），求 $\sum_{i = 0} ^ {10 ^ n - 1} f_k(i)$。

多组数据。

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

接下来 $T$ 行，每行两个整数 $n, k$ 表示一组数据。

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

hint:
对于所有数据，$1\leq T\leq 60$，$0\leq n < k \leq 10 ^ 5$，$\sum k\leq 10 ^ 5$。

- 测试点 1（$30$ 分）：$n\leq 5$，$k\leq 15$。
- 测试点 2（$70$ 分）：无特殊限制。

Source：NFLSPC #6 F by Alex_Wei


title: [NFLSPC #6] 挑战停机问题

background: 作为新时代的 OIer/XCPCer，你已经不满足于挑战 NPC 问题了。你想挑战数学的不可判定性——图灵停机问题。

description:
图灵给了你一个程序。程序开始运行之初，有且仅有一个变量 $A$，初始值为 $0$。程序共有 $n$ 行，行号为 $1 \sim n$，每行是如下几种形式之一：

- `A a`：令 $A \gets A + a$，然后执行下一行。
- `G x`：执行第 $x$ 行。
- `I l r x y`：如果 $A \in [l, r]$ 则执行第 $x$ 行，否则执行第 $y$ 行。
- `E`：直接结束程序。

保证最后一行是 `E`。

图灵希望你判断这个程序从第一行开始执行会不会结束。为了进一步检验你到底是不是真的会判定停机问题（还是装的？），图灵还要求你给出 $A$ 最终的值，如果程序不会结束且不存在一个时刻使得在其以后 $A$ 不再变化，则输出 `@Turing ?`。

inputFormat:
本题多测。第一行一个正整数 $T$ 表示数据组数，对于每组数据：

- 第一行一个整数 $n$，表示程序的行数。
- 接下来 $n$ 行，描述程序。

outputFormat:
对于每个询问，输出两行：

- 第一行一个字符串 `Yes` 或 `No`，表示程序是否会结束。
- 第二行一个整数 $A_{0}$ 或字符串 `@Turing ?`，表示 $A$ 最终的值。

hint:
对于所有数据，$1 \leq T \leq 1000$，$1 \leq n, \sum n \leq 10^5$，$1 \leq a \leq 10^9$，$0 \leq l \leq r \leq 10^9$，$1 \leq x, y \leq n$。保证输入涉及到的所有数字都是整数。

- 子任务 1（15 分）：不存在 `I` 类语句。
- 子任务 2（20 分）：$r \leq 100$。
- 子任务 3（40 分）：$\sum \max r \leq 10^5$。
- 子任务 4（25 分）：无特殊限制。

Source：NFLSPC #6 G by chenxia25


title: [NFLSPC #6] 树

background: # 请不要使用 C++14 (GCC 9) 提交

description:
给定一棵 $n$ 个点的树，标号从 $0$ 到 $n-1$，每个点有一个 $0$ 到 $n-1$ 之间的颜色。

$q$ 次询问，每次查询 $x$ 的祖先中颜色为 $c$ 的点中离 $x$ 最近的一个（也就是深度最大的一个）的编号，**强制在线**。

**点的颜色在数据生成完之后进行了一次随机打乱（也就是作用了一个均匀随机的排列）**。

inputFormat:
**由于本题输入量较大，我们采用交互题的方式进行评测**。

你不需要也不应该实现主函数 `main`，你需要实现以下两个函数：

```
extern "C" void init(int n,vector<int> fa,vector<int> col)
```

* $n$：节点的个数。
* $fa$：长度为 $n$ 的数组，$fa_i$ 表示节点 $i$ 的父亲。特别地，$fa_0=-1$。
* $col$：长度为 $n$ 的数组，$col_i$ 表示节点 $i$ 的颜色。再次强调：**$col$ 在数据生成完之后进行了一次随机打乱**。
* 这个函数会被调用恰好一次，它给了你树的信息。你可以在这次函数调用的时候计算一些需要用到的信息。

```
extern "C"  int query(int x,int c)
```

* $x$：查询的节点编号。
* $c$：查询的颜色。
* 你应该返回 $x$ 的祖先中离 $x$ 最近的颜色为 $c$ 的节点的编号。若不存在这样的节点，返回 `-1`。
* 这个函数恰好被调用 $q$ 次。
* 每次调用函数时你并不知道以后的询问，也就是说，询问是 **强制在线** 的。

使用下发 grader 测试代码时，输入格式为：

- 第一行输入两个数 $n,q$。
- 第二行输入 $n$ 个数 $fa_0,\cdots,fa_{n-1}$。
- 第三行输入 $n$ 个数 $col_0,\cdots,col_{n-1}$。
- 接下来 $q$ 行，每行两个数 $x,c$，表示一组询问。

outputFormat:
测试代码时，输出格式为：

- $q$ 行，每行一个数，表示答案。
- 接下来，下发 grader 会输出你的耗时（注意这里并不会检查正确性）。

注意：这里给出的输入输出格式为下发 grader 的输入输出格式，仅为测试使用，**你实现的函数不应该对标准输入输出流进行任何操作**。

hint:
对于所有数据，$2\leq n\leq 2\times 10^6$，$q=5n\leq 10^7$，$-1\leq fa_i<i$，$0\leq col_i<n$，$fa_0=-1$ 且对任意 $1\leq i < n$，$fa_i\geq 0$。

- 子任务 1（$5$ 分）：$n\leq 1000$。
- 子任务 2（$20$ 分）：$n\leq 200000$。
- 子任务 3（$30$ 分）：$fa_i=i-1$。
- 子任务 4（$45$ 分）：无特殊限制。

每个子任务评分方式为子任务内所有点的得分取最小值。交互库运行时长不超过 600ms，消耗空间不超过 140MB。

**本题在 OJ 上显示的时限不是真正的时限**。若你的代码没有在规定的时间和空间内正常运行并正确回答所有询问，该测试点获得 0 分。若你实现的函数运行时间不小于 2400ms，你将获得 `Time Limit Exceeded`（实际测试时会通过让 grader 死循环来实现这一点）。否则若你实现的函数共运行了 $x$（$x<2400$） 毫秒，你获得的分数为：
- $x\leq 1200$，返回 `Accepted`, 获得该测试点全部分数。
- $1200<x<2400$，返回 `Partially Correct`, 获得该测试点 $(\frac {2400 - x} {1200}) ^ 2$ 倍的分数。

**测试点信息上显示的不是真正的耗时，SPJ 详细信息里显示的才是你实现的部分的耗时**。

Source：NFLSPC #6 H by asmend


title: [NFLSPC #6] 9.pop_book();

background: *Alek 岁*在操场上跑圈。他看到有人超过他，很不爽。于是他采取了以下策略：

description:
在长度为 $m$ 的环形操场上有 $n$ 个人，第 $i$ 个人在 $t_i$ 时刻从位置 $p_i$ 出发以 $v_i$ 单位长度每秒的速度移动。现在 $0$ 时刻 *Alek 岁*在位置 $0$ 处，速度为 $0$，会跟着经过他的速度最快的人移动。$q$ 次询问 $T_i$ 时刻 *Alek 岁*的移动距离。可以证明这是一个整数。

注：从位置 $0$ 出发逆时针方向 $x$（$0\leq x < m$）单位长度的位置称为位置 $x$。所有人的运动方向都是逆时针。

多组数据。

inputFormat:
第一行一个整数 $T$ 表示数据组数。对于每组数据：

- 第一行三个整数 $n, m, q$，分别表示人数，操场长度和询问个数。
- 接下来 $n$ 行，每行三个整数 $p_i, v_i, t_i$，分别表示第 $i$ 个人出发时的位置，移动速度（单位长度每秒）和出发时间。
- 接下来 $q$ 行，每行一个整数 $T_i$ 表示一次询问。

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

hint:
对于所有数据，$1\leq T\leq 10 ^ 3$，$1\leq n, \sum n\leq 5\times 10 ^ 5$，$1\leq m, q, \sum q \leq 10 ^ 6$，$1\leq v_i, t_i, T_i\leq 10 ^ 9$，$0\leq p_i < m$。保证 $t_i$ 单调不降，$T_i$ 单调递增。

- 子任务 1（$10$ 分）：$n\leq 5$。
- 子任务 2（$10$ 分）：$n\leq 50$。
- 子任务 3（$20$ 分）：$n\leq 500$。
- 子任务 4（$20$ 分）：$n\leq 5\times 10 ^ 3$。
- 子任务 5（$20$ 分）：$n\leq 5\times 10 ^ 4$。
- 子任务 6（$20$ 分）：无特殊限制。

**请注意，子任务并没有保证 $\sum q$ 的数量级**。

本题 IO 量较大，建议使用 `scanf/printf` 或关闭流同步的 `cin/cout` 或快速读入和快速输出。

Source：NFLSPC #6 I by Alex_Wei


title: [NFLSPC #6] 绝不能忘记的事……

background: > 那件事…… 绝对不能忘记！

description:
你在电脑内记录了一条绝对不能忘记的事。但是，因为 1064 病毒的入侵，它被电脑忘记了。更可怕的是，1064 病毒似乎拥有某种跨物种传播的能力，导致你也忘记了这件事。

万幸，在 1064 病毒让你和你的电脑忘记这件事之前，你及时将这件事的记录复制了 $n$ 份。但是，由于你和你的电脑在执行这件艰巨的任务的过程中受到 1064 病毒的影响忘记了很多可以忘记的事，所以你进行的操作有点奇怪。

- 首先，这件事的记录是一个长度未知（因为你已经忘记了它的长度）的字符串，称作 **记录串**。对于一份复制，你将记录串切成了三段非空的字符串 **片段**。**不同复制的场合，切割的方案不一定相同**。你暂且将这三份 **片段** 依次称作 **前面**，**中间** 和 **后面**。
- 因为电脑忘记了很多可以忘记的事，所以某些复制中的某些片段可能被忘记了。具体而言，前面有可能被替换为 `QIANMIANWANGLE`，中间有可能被替换为 `ZHONGJIANWANGLE`，后面有可能被替换为 `HOUMIANWANGLE`；在发生替换的场合，表示电脑 **完全忘记** 了这一段片段；否则，表示电脑 **完全记得** 该片段。
- 你终于想起了一件绝不能忘记的事：那就是那绝不能忘记的记录串中，**恰出现了一次** `NFLSPC#6QIDONG` 作为连续子串。除此之外，记录串中的所有其它字符都是 **小写英文字符**。并且，因为你和你的电脑始终记得这件事有多么重要，所以你在划分的时候，无意中让某一个片段恰好为 `NFLSPC#6QIDONG`；你的电脑也在每一份记录中忠实地记得这一段片段。
- 于是，你的电脑最终还记得的东西，就是：$n$ 份复制，每份复制由三段非空字符串构成，依次表示这份复制的三份片段；其中恰有一段为 `NFLSPC#6QIDONG`，另外两段要么是一串仅由小写英文字母构成的非空串，要么是对应的前面/中间/后面忘了。
- 邪恶的 1064 病毒不肯罢休，它篡改了你电脑中的信息，使得你的 $n$ 份复制不一定是自洽的。

你确信 1064 病毒没有能力篡改过多的信息，并且它绝对敌不过你和你的电脑对彼此牢牢记住的 `NFLSPC#6QIDONG` 的信念。因此，你的复制仍然满足上文中所述的性质（恰有一段是 `NFLSPC#6QIDONG`，另外两段要么忘了要么是小写字母非空串）。

你的目标是，寻找到初始的那绝不能忘记的记录串。这个记录串需要满足的条件是，恰出现一次 `NFLSPC#6QIDONG`，其余字符均是小写英文字符，且其匹配尽量多的复制串。

- 记录串与复制串匹配的要求是，记录串存在一种划分，使得三段划分与复制串的三段分别相同，或者复制串中这段划分忘了（此时本段划分中，记录串为任何非空英文字符串均合法）。

你希望求出该记录串能匹配的最多复制串数目。至于记录串本身，你更希望将它深深地埋藏于心底，因此你不需要求出它。

> 那忘记的事只会使你的心灵更加轻盈 / 那未曾忘记的事则会让你的心灵更加坚硬 /

inputFormat:
**为了避免输入量过大，输入进行了一定程度的压缩。请务必认真阅读输入格式**。

第一行一个正整数 $n$，表示记录数目。

接下来 $n$ 行，每行三个非空字符串，其中第一段要么是非空小写字符串，要么是 `Q`（表示 `QIANMIANWANGLE`），要么是 `N`（表示 `NFLSPC#6QIDONG`），不存在其它可能；第二段则是非空小写字符串、`Z`（表示 `ZHONGJIANWANGLE`）、`N` 三者之一；最后一段是非空小写字符串、`H`（表示 `HOUMIANWANGLE`）、`N` 三者之一。保证三段中恰有一段为 `N`。

outputFormat: 一行一个整数，表示所有记录串中，能匹配的最多的复制的数目。

hint:
对于所有数据，保证输入的所有字符串长度之和不超过 $10 ^ 6$。

- 子任务 1（$20$ 分）：保证复制中除了 `NFLSPC#6QIDONG` 恰出现一次以外，其它部分全部忘记。也即，输入的复制串仅可能为 `N Z H`，`Q N H`，`Q Z N` 三者之一。
- 子任务 2（$30$ 分）：保证所有复制串的 “后面” 段都是 `NFLSPC#6QIDONG`。也即，输入的复制串必然形如 `* * N`，其中 `*` 指代任意符合格式的输入。
- 子任务 3（$50$ 分）：无特殊限制。

Source：NFLSPC #6 J by Troverld


title: [NFLSPC #6] 啊，忘记了。

background: > 好像忘了什么事…… 算了，想必不是什么重要的事吧。

description:
你在你的电脑上发现了 $n$ 份文本。冥冥之中，你没来由地感觉这似乎全都是一份记录的复制。

- 首先，原始记录是一个长度未知（甚至可以为空）的字符串，称作 **记录串**。对于一份复制，其将记录串切成了三段 **可以为空** 的字符串 **片段**。**每份复制中切割方案不保证相同**。你暂且将这三份 **片段** 依次称作 **前面**，**中间** 和 **后面**。
- 某些复制中的某些片段可能被忘记了。具体而言，前面有可能被替换为 `QIANMIANWANGLE`，中间有可能被替换为 `ZHONGJIANWANGLE`，后面有可能被替换为 `HOUMIANWANGLE`；在发生替换的场合，表示这一段片段被 **完全遗忘** 了；否则，表示该片段被 **完整保存**。
- 你有一种预感，记录串中的所有字符都是 **小写英文字符**。
- $n$ 份复制不一定自洽。

你的目标是，寻找初始的记录串。这个记录串需要满足所有字符均是小写英文字符。你希望其匹配尽量多的复制串。

- 记录串与复制串匹配的要求是，存在记录串的一种划分，使得其中记录串的三段与复制串的三段分别相同，或者复制串中这段划分忘了（此时本段划分中，记录串为任何可以为空的小写英文字符串均合法）。

你希望求出该记录串能匹配的最多复制串数目。**至于记录串本身，你感觉它并不是很重要，所以你不需要求出它**。

> / 我，毋畏遗忘 /

inputFormat:
**为了避免输入过大，输入进行了一定程度的压缩。请务必认真阅读输入格式**。

第一行一个正整数 $n$，表示记录数目。

接下来 $n$ 行，每行三个非空字符串，其中第一段要么是非空小写字符串，要么是 `Q`（表示 `QIANMIANWANGLE`），要么是 `E` 表示这是一段空串（因为空串不可见所以选取 `E` 作为占位符），不存在其它可能；第二段则是非空小写字符串、`Z`（表示 `ZHONGJIANWANGLE`）、`E` 三者之一；最后一段是非空小写字符串、`H`（表示 `HOUMIANWANGLE`）、`E` 三者之一。

outputFormat: 一行一个整数，表示所有记录串中，能匹配的最多的复制的数目。

hint:
### 样例 1 解释

你希望这个串是 `nflsalgonflspcqidong`。你确信，不会再有其它串比它更匹配现存的记录了。

### 数据范围与约定

对于所有数据，保证输入的所有字符串长度之和不超过 $5\times 10 ^ 5$。

- 子任务 1（$30$ 分）：保证所有复制的 “后面” 段都是 `H`。
- 子任务 2（$70$ 分）：无特殊限制。

Source：NFLSPC #6 K by Troverld


title: [NFLSPC #6] 等差数列

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

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

description:
*Alek 岁*在某知名 OJ *代码力量*上做了 $a_i$ 道难度为 $i$ 的题。他希望做一些题使得 $a_i$ 形成 **公差非正** 的等差数列，这样画出来的统计图表很好看。

尽管 *Alek 岁*一天能做 42 道题，但他依然希望做尽可能少的题达到目标。你需要求出新做题数的最小值。

你可以认为 OJ 上有足够多的各种难度的题目。

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

对于每组数据：
- 第一行一个整数 $n$ 表示难度总数。
- 第二行 $n$ 个整数 $a_i$。

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

hint:
对于所有数据，$1\leq T\leq 100$，$1\leq n, \sum n\leq 10 ^ 5$，$1\leq a_i\leq 10 ^ 9$。

- 子任务 1（$30$ 分）：$\sum n \leq 10 ^ 3$。
- 子任务 2（$70$ 分）：无特殊限制。

Source：NFLSPC #6 L by Alex_Wei


title: 「Daily OI Round 3」Pigeon

background: > 最近，忙吗，也不说打个电话。哦，是吗，嘿嘿原来没给过你号码。但这，不是，你不找我的理由，下次罚你陪我等到太阳出头。——recollect_i 的博客

description: recollect_i 给了你长度为 $n$ 的序列 $x$，你需要求出一个实数 $y$ 使得对于所有 $1\leq i<j\leq n$，$\vert x_j-y\vert>\vert x_i-y\vert$，或报告无解。

inputFormat:
第一行一个整数 $n$，表示序列长度。

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

outputFormat:
如果有解，第一行输出字符串 `lovely`，第二行输出一个实数 $y$。

为了避免精度问题，如果您输出的方案满足对于所有 $ 1\leq i<j\leq n$，$\vert x_j-y\vert-\vert x_i-y\vert>10^{-6}$，则认为您的答案正确。

同时您需要保证 $-2\times 10^9\leq y\leq 2\times 10^9$，且 $y$ 的小数点后不超过 $10$ 位，否则无法保证评测的正确性。

如果无解，一行输出字符串 `pigeon`。

hint:
#### 【提示】

输出格式中 $>10^{-6}$ 只是为了避免精度问题，您可以当成要求 $\vert x_j-y\vert>\vert x_i-y\vert$。

可以证明，如果有解，则一定存在 $y$ 满足 $-2\times 10^{9}\leq y\leq2\times 10^{9}$ 且对于所有 $1\leq i<j\leq n$，$\vert x_j-y\vert-\vert x_i-y\vert>0.2$，且小数点后位数不超过 $3$。

#### 【数据范围】

对于全部数据保证：$5\leq n\leq10^5$，$-10^9\leq x_i\leq10^9$。


title: [语言月赛 202312] NK

description:
给定两个正整数 $N, K$，请你统计符合以下条件的正整数 $x$ 的数量：

- $1 \leq x \leq N ^ N$。
- $(x \bmod K)$ 是 $N$ 的倍数。
- $x$ 的个位是 $N$。

$x \bmod K$ 代表 $x$ 除以 $K$ 的余数，例如 $7 \bmod 3 = 1$。

inputFormat: 输入一行两个整数 $N, K$。

outputFormat: 输出一行一个整数，代表符合题干中所有条件的 $x$ 的数量。

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

- 对于 $30\%$ 的数据，$1 \leq N, K \leq 6$。
- 对于 $100\%$ 的数据，$1 \leq N \leq 9$，$1 \leq K \leq 10 ^ 6$。


title: [入门赛 #18] 禁止在 int 乘 int 时不开 long long

description:
在比赛中，根据数据范围，分析清楚变量的取值范围，是非常重要的。int 类型变量与 int 类型变量相乘，往往可能超出 int 类型可以表示的取值范围。

现在，给出两个 int 类型变量 $x,y$ 及其取值范围，请问 $x\times y$ 的值是否可能超过 int 类型可以表示的范围？

> 提示：int 类型可以表示的范围为 $[-2147483648, 2147483647]$，即 $[-2^{31},2^{31}-1]$。也就是，int 类型可以表示的最小值为 $-2147483648$，最大值为 $2147483647$。

inputFormat:
输入共两行。

输入的第一行为两个整数 $x_l,x_u$，表示变量 $x$ 的取值范围为 $x_l \le x \le x_u$。

输入的第二行为两个整数 $y_l,y_u$，表示变量 $y$ 的取值范围为 $y_l \le y \le y_u$。


title: [COCI 2023/2024 #2] Pahuljice

description:
Lana 喜欢画雪花。如下定义一个大小为 $x$ 的雪花：

+ 雪花的中间是一个 $\texttt{'+'}$。
+ 在 $\texttt{'+'}$ 的上方和下方各有 $x$ 个 $\texttt{'|'}$。
+ 在 $\texttt{'+'}$ 的左方和右方各有 $x$ 个 $\texttt{'-'}$。
+ 在 $\texttt{'+'}$ 的左上方和右下方各有 $x$ 个 $\texttt{'\textbackslash'}$。
+ 在 $\texttt{'+'}$ 的左下方和右上方各有 $x$ 个 $\texttt{'/'}$。

雪花之间可以重叠。如下是雪花的几个例子：

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

三张图分别含有一个大小为 $1$ 的雪花，重叠的两个大小分别为 $2$ 和 $1$ 的雪花，一个大小为 $1$ 的雪花（作为大小为 $2$ 的雪花不完整）。

给定一个 $n\times m$ 的字符矩阵，请找出其中最大的雪花的大小。

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

接下来 $n$ 行每行一个长为 $m$ 的字符串，给出一个 $n\times m$ 的矩阵，保证只包含 $\texttt{'+'},\texttt{'-'},\texttt{'|'},\texttt{'/'},\texttt{'\textbackslash'},\texttt{'.'}$。

outputFormat: 输出一行一个整数表示最大的雪花大小。若没有则输出 $0$。


title: [COCI 2023/2024 #2] Pingvin

description:
给定一个 $n\times n\times n$ 的立方体，被分为 $n^3$ 个单位立方体，其中一些单位立方体是障碍不能通行。

给定起点坐标和终点坐标，每一步可以从一个单位立方体移到一个相邻的（有共同面的）非障碍的单位立方体，问从起点到终点最少走多少步。

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

接下来一行 $3$ 个整数 $x_s,y_s,z_s$ 表示起始位置。

接下来一行 $3$ 个整数 $x_t,y_t,z_t$ 表示终点位置。

接下来给出 $n$ 个 $n\times n$ 的 $01$ 矩阵，第 $i$ 个立方体的第 $j$ 行第 $k$ 列表示 $(j,k,i)$ 是否是障碍（是 $1$ 表示障碍）。

保证起始和终点位置不是障碍。

outputFormat: 输出一行一个整数表示最少步数，若无法到达输出 $-1$。


title: [COCI 2023/2024 #2] Dizalo

description:
$n$ 个人坐电梯，第 $i$ 个人在第 $a_i$ 层下电梯，$a_{1\sim n}$ 构成一个排列。

电梯是长条形的，所以 $n$ 个人初始时按编号顺序在电梯里列成一列，电梯会从下往上依次经过第 $1\sim n$ 层。

当一个人要下电梯时，所有在他前面的人也必须暂时下电梯，然后可以以任意顺序返回电梯。在他后面的人不需要也不会下电梯。

如果每次临时下电梯的人总是以最优策略来决定返回电梯的顺序，请你求出所有人下电梯的总次数最少是多少。

给定 $q$ 次操作，每次给定 $x_i$ 表示移除编号为 $x_i$ 的人，你需要在第一次操作前以及每次操作之后求出答案。

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

第二行 $n$ 个数 $a_{1\sim n}$，保证构成一个 $1\sim n$ 的排列。

第三行 $q$ 个数 $x_{1\sim q}$，表示 $q$ 次询问。

outputFormat: 输出一行 $q+1$ 个数，表示第一次操作前的答案以及每次操作后的答案。


title: [COCI 2023/2024 #2] Kuglice

description:
一个双端队列里面有 $n$ 个球，每个球有一个颜色。A 和 B 玩一个游戏：

A 先手，两个人轮流操作，每次从队列的最左端或者最右端拿出一个球，如果这种颜色的球是第一次被拿出，拿出它的人获得 $1$ 分。所有球都拿完后游戏结束。

假设 A 和 B 都以最优策略操作，请求出最终得分是多少。

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

第二行 $n$ 个整数 $a_{1\sim n}$ 表示从左到右每个球的颜色。

outputFormat: 输出一行两个以 `:` 隔开的整数（形如 `a:b`），`a` 表示 A 最终的得分，`b` 表示 B 最终的得分。


title: [COCI 2023/2024 #2] Zatopljenje

description:
Mr. Malnar 有一张地形图，上面画着一个区域内每个位置的海拔高度。具体的，有 $n$ 个位置排成一排，第 $i$ 个位置高出海平面 $h_i$ 米。

海平面可能会上升。给定 $q$ 次询问，对于第 $i$ 次询问你需回答：如果海平面高度上升 $x_i$ 米，那么 $[l_i,r_i]$ 区间中会形成多少个岛？一个岛的定义为一个极长的，每个位置的高度都大于 $x_i$ 的段。

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

上图分别表示了样例 1 的第一组询问以及样例 2 的第二组询问。左图 $[2,5]$ 区间中有 $[2,2],[4,5]$ 两个岛，而右图中有 $[1,1],[4,4],[8,8],[10,10]$ 四个岛。

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

第二行 $n$ 个整数 $h_{1\sim n}$ 表示每个位置的初始海拔。

接下来 $q$ 行每行 $3$ 个整数 $l_i,r_i,x_i$ 表示一次询问。

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


title: [语言月赛 202401] 二进制与一

description:
给定一个正整数 $n$，以及操作次数 $q$。对于每次操作，给出一个正整数 $k$，要求：让 $n$ 加上一个非负整数 $x$，使得 $n$ 在二进制下的第 $k$ 位（从右往左数）是 $1$，并在符合要求的情况下，令 $x$ 最小。

请注意，每次操作都会让 $n$ 变为 $n + x$，会影响后续操作。

小山需要求出，所有的 $x$ 之和是多少。

inputFormat:
输入共 $q + 1$ 行。

第一行两个整数 $n$ 和 $q$。
接下来 $q$ 行，每行一个正整数 $k$，表示要让 $n$ 在二进制下从右往左数的第 $k$ 位是 $1$。

outputFormat: 一行一个整数，表示所有的 $x$ 之和。


title: [USACO21OPEN] Acowdemia I B

description:
由于对计算机科学的热爱，以及有朝一日成为 「Bessie 博士」的诱惑，奶牛 Bessie 开始攻读计算机科学博士学位。经过一段时间的学术研究，她已经发表了 $N$ 篇论文（$1 \le N \le 10^5$），并且她的第 $i$ 篇论文得到了来自其他研究文献的 $c_i$ 次引用（$0 \le c_i \le 10^5$）。

Bessie 听说学术成就可以用 $h$ 指数来衡量。$h$ 指数等于使得研究员有至少 $h$ 篇引用次数不少于 $h$ 的论文的最大整数 $h$。例如，如果一名研究员有 $4$ 篇论文，引用次数分别为 $(1,100,2,3)$，则 $h$ 指数为 $2$，然而若引用次数为 $(1,100,3,3)$ 则 $h$ 指数将会是 $3$。

为了提升她的 $h$ 指数，Bessie 计划写一篇综述，并引用一些她曾经写过的论文。由于页数限制，她至多可以在这篇综述中引用 $L$ 篇论文（$0 \le L \le 10^5$），并且她只能引用每篇她的论文至多一次。

请帮助 Bessie 求出在写完这篇综述后她可以达到的最大 $h$ 指数。

注意 Bessie 的导师可能会告知她纯粹为了提升 $h$ 指数而写综述存在违反学术道德的嫌疑；我们不建议其他学者模仿 Bessie 的行为。

inputFormat:
输入的第一行包含 $N$ 和 $L$。

第二行包含 $N$ 个空格分隔的整数 $c_1,\ldots,c_N$。

outputFormat: 输出写完综述后 Bessie 可以达到的最大 $h$ 指数。

hint:
### 样例解释 1

Bessie 不能引用任何她曾经写过的论文。上文中提到，$(1,100,2,3)$ 的 $h$ 指数为 $2$。

### 样例解释 2

如果 Bessie 引用她的第三篇论文，引用数会变为 $(1,100,3,3)$。上文中提到，这一引用数的 $h$ 指数为 $3$。

### 测试点性质

- 测试点 $1-7$ 满足 $N\le 100$。
- 测试点 $8-10$ 满足 $N\le 1000$。
- 测试点 $11-17$ 满足 $N \le 10^5$。


title: [USACO21OPEN] Acowdemia II B

description:
Bessie 正在申请计算机科学的研究生，并取得了一所久负盛名的计算机科学实验室的面试通知。然而，为了避免冒犯任何人，Bessie 有意先确定实验室的 $N$ 名现有成员的相对资历（$1\le N\le 100$）。没有两名实验室成员的资历相同，但确定他们的资历深浅可能并不好办。为此，Bessie 将会对实验室的出版物进行调查。

每份出版物均包含一个作者列表，为所有 $N$ 名实验室成员的一个排列。列表按每名实验室成员对这篇文章的贡献降序排列。如果多名研究员的贡献相等，则按字典序排列。由于更有资历的实验室成员负有更多的管理责任，更有资历的研究员从不会比资历较浅的研究员做出更多的贡献。

例如，在一个由资历较浅的学生 Elsie、资历较深的教授 Mildred、以及十分资深的教授 Dean 组成的实验室中，可能存在一篇论文 Elsie-Mildred-Dean，如果他们做出了不等的贡献（也就是说，Elsie 做出的贡献比 Mildred 更多，Mildred 比 Dean 更多）。然而，也有可能存在一篇论文 Elsie-Dean-Mildred，如果 Mildred 和 Dean 做出了相等的贡献，而 Elsie 做出了更多的贡献。

给定实验室的 $K$ 份出版物（$1\le K\le 100$），对于实验室中每对研究员，如果可能的话帮助 Bessie 判断其中谁的资历更深。

inputFormat:
输入的第一行包含两个整数 $K$ 和 $N$。

第二行包含 $N$ 个空格分隔的字符串，为实验室的成员的名字。每个字符串均由小写字母组成，且至多包含 $10$ 个字符。

以下 $K$ 行，每行包含 $N$ 个空格分隔的字符串，表示一份出版物的作者列表。

outputFormat:
输出 $N$ 行，每行 $N$ 个字符。在第 $i$ 行内，对于所有 $j\neq i$，当可以确定第 $i$ 名成员比第 $j$ 名成员资历更深时字符 $j$ 为 `1`，当可以确定第 $i$ 名成员比第 $j$ 名成员资历更浅时字符 $j$ 为 `0`，当不能由给定的出版物确定时为 `?`。

第 $i$ 行的字符 $i$ 应为 `B`，因为这是 Bessie 最喜欢的字母。

samples:
1 3
dean elsie mildred
elsie mildred dean

samples:
2 3
elsie mildred dean
elsie mildred dean
elsie dean mildred

hint:
### 样例解释 1

在这个样例中，单独一份论文 elsie-mildred-dean 并不能提供足够的信息判断 Elsie 比 Mildred 资历更深或更浅。然而，我们可以推断出 Dean 一定比这两名研究员资历更深，从而资历排序为 Elsie<Mildred<Dean 和 Mildred<Elsie<Dean 均是可能的。

### 样例解释 2

在这个样例中，唯一能与两篇论文相一致的资历排序为 Elsie<Mildred<Dean，这是因为基于第一个样例所提供的信息，第二篇论文可以帮助我们推断出 Mildred 比 Elsie 的资历更深。