title: [ICPC2021 Macao R] the Matching System

description:
As the leader of the safety department, you are asked to check an ancient matching system in your company.

The system is fed with two strings, a to-be-matched string and a pattern string, and will determine whether the former can match the latter. The former string is a strict binary string(i.e., contains only $\textbf{0}$ and $\textbf{1}$), and the latter string consists of four types of characters $\textbf{0}$, $\textbf{1}$, $\textbf{*}$, $^$, where $\textbf{*}$ means match zero or more arbitrary binary characters, and $^$ means match exactly one binary character.

The system has two matching methods: maximum matching and minimum matching.

Consider the starting positions of the two strings. The maximum matching method will make different decisions based on the current character of the pattern string:
- $\textbf{*}$: The system will enumerate $i$ from $L$ to $0$, where $L$ is the remaining length of the to-be-matched string. Before each enumeration starts, the system consumes 1 unit of energy. Then it temporarily assumes that the current $\textbf{*}$ in the pattern string matches the consecutive $i$ characters in the to-be-matched string, and tries to match the remaining positions of two strings recursively. As long as one attempt is successful, the system will give up the remaining enumeration and stop the whole system. Otherwise, it will try the next enumeration until all attempts are tried and finally return to the previous $\textbf{*}$ enumeration.
- $\textbf{0,1}$: The system will stop and return to the previous $\textbf{*}$ enumeration if the to-be-matched string has been exhausted. Otherwise, it consumes $1$ unit of energy to compare the current characters between the pattern string and the to-be-matched string. It will continue analyzing the remaining positions of these two strings if the result is the same, otherwise, return back to the previous $\textbf{*}$ enumeration.
- $^$: The system will stop and return to the previous $\textbf{*}$ enumeration if the to-be-matched string has been exhausted. Otherwise, it consumes $1$ unit of energy and moves on of two strings.

When the pattern string is exhausted, the system will check the to-be-matched string at the same time. It will return ``Yes`` and stop the whole process if the to-be-matched string is also exhausted, otherwise, it will return to the previous $\textbf{*}$ enumeration. After all attempts are tried and no matching method is found, the system will eventually return ``No``.

Minimum matching does a similar thing except for the enumeration order of $\textbf{*}$ (i.e., enumerate $i$ from $0$ to $L$).

These two matching methods seem not very effective, so you want to hack them. Please construct both a pattern string and a to-be-matched string of length $n$ for each matching method, so that the system answers ``Yes`` and the energy consumption is as large as possible.

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

The first and only line contains an integer $n$ ($1 \le n \le 10^3$) indicating the length of strings need to be constructed.

outputFormat:
Please output the pattern string, the to-be-matched string, and the energy cost for the maximum matching method in the first $3$ lines. Then output the pattern string, the to-be-matched string, and the energy cost for the minimum matching method in the next $3$ lines.

If there are multiple constructing ways, you can output any of them.

The energy cost may be very large, so you need to output the value modulo $(10^9+7)$. Note that this is only for your convenience and you need to maximize the energy cost before the modulus.

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

作为安全部门的负责人，你被要求检查公司的一个古老匹配系统。

该系统输入两个字符串，一个待匹配字符串和一个模式字符串，并确定前者是否能匹配后者。前者字符串是严格的二进制字符串（即仅包含 $\textbf{0}$ 和 $\textbf{1}$），而后者字符串由四种类型的字符组成 $\textbf{0}$、$\textbf{1}$、$\textbf{*}$ 和 $^$，其中 $\textbf{*}$ 表示匹配零个或多个任意二进制字符，$^$ 表示匹配恰好一个二进制字符。

该系统有两种匹配方法：最大匹配和最小匹配。

考虑两个字符串的起始位置。最大匹配方法将根据模式字符串的当前字符做出不同的决定：
- $\textbf{*}$: 系统将从 $L$ 到 $0$ 枚举 $i$，其中 $L$ 是待匹配字符串的剩余长度。在每次枚举开始之前，系统消耗 1 单位的能量。然后，它临时假设模式字符串中的当前 $\textbf{*}$ 匹配待匹配字符串中的连续 $i$ 个字符，并尝试递归地匹配两个字符串的剩余位置。只要有一次尝试成功，系统将放弃剩余的枚举并停止整个系统。否则，它将尝试下一次枚举，直到所有尝试都尝试完毕，最后返回到先前的 $\textbf{*}$ 枚举。
- $\textbf{0,1}$: 如果待匹配字符串已经耗尽，则系统将停止并返回到先前的 $\textbf{*}$ 枚举。否则，它将消耗 $1$ 单位的能量来比较模式字符串和待匹配字符串之间的当前字符。如果结果相同，它将继续分析这两个字符串的剩余位置，否则，返回到先前的 $\textbf{*}$ 枚举。
- $^$: 如果待匹配字符串已经耗尽，则系统将停止并返回到先前的 $\textbf{*}$ 枚举。否则，它将消耗 $1$ 单位的能量并继续分析两个字符串。

当模式字符串耗尽时，系统将同时检查待匹配字符串。如果待匹配字符串也已经耗尽，则系统将返回“是”并停止整个过程，否则，它将返回到先前的 $\textbf{*}$ 枚举。在尝试了所有尝试并找不到匹配方法后，系统最终将返回“否”。

最小匹配执行类似的操作，除了 $\textbf{*}$ 的枚举顺序（即从 $0$ 到 $L$ 枚举 $i$）。

这两种匹配方法似乎不太有效，所以你想黑掉它们。请为每种匹配方法构造一个长度为 $n$ 的模式字符串和待匹配字符串，使得系统返回“是”，能量消耗尽可能大。

**【输入格式】**

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

第一行仅包含一个整数 $n$（$1 \le n \le 10^3$），表示需要构造的字符串的长度。

请输出最大匹配方法的模式字符串、待匹配字符串和能量消耗的前 $3$ 行。然后输出最小匹配方法的模式字符串、待匹配字符串和能量消耗的后 $3$ 行。

**【输出格式】**

如果有多种构造方式，你可以输出任何一种。

能量消耗可能非常大，所以你需要输出取模 $(10^9+7)$ 后的值。请注意，这仅供您方便，您需要在取模之前最大化能量消耗。

翻译来自于：[ChatGPT](https://chatgpt.com/)。


title: [ICPC2021 Macao R] Laser Trap

type: P

description:
BaoBao is playing the famous game $\textit{Elden Ring}$ these days. It's an open-world game in which you can control your character to travel from places to places. However, your character could also enter a trap and you need to figure out how to escape. Right now, BaoBao's character is stuck in a 2-dimensional plane with deadly lasers. There are $n$ laser generators (each can be regarded as a point) shooting laser beams between every pair of them (so there are $\frac{n(n-1)}{2}$ laser beams in total). The beams start and end at generator points and do not stretch to infinity.

Starting at point $(0,0)$, BaoBao wants to escape to point $(10^{10^{10^{10^{10}}}}, 10^{10^{10^{10^{10}}}})$ without touching any laser beam or generator. In order to do so, BaoBao can ask her friend DreamGrid to remove any number of laser generators, together with any laser beam that starts or ends at these generators. Output the minimum number of laser generators that need to be erased for the escape.

Note that BaoBao does not need to move in a specific direction to escape. Her escaping route can even be a curve if necessary.

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^6$) indicating the number of laser generators.

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

It is guaranteed that no two generators coincide, and no laser beam or generator will touch $(0,0)$.

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

outputFormat: For each test case output one line containing one integer indicating the minimum number of generators that need to be removed.

translation:
一直角坐标系中，BaoBao 在原点位置，平面上有 $n$ 个发射装置，任意两个发射器之间都有激光束，共 $(n-1) \times n / 2$ 条激光，BaoBao 的朋友可以去除任何发射器，问最少去除多少发射器，能使 BaoBao不会被激光所伤还能从 $(0,0)$ 逃逸到 $\left(10^{10^{10^{10^{10}}}}, 10^{10^{10^{10^{10}}}}\right)$。

tip.发射器不会重合，也不会存在激光束穿过 $(0,0)$。

hint:
The second and the third sample test cases are shown below. Solid dots and lines represent the remaining laser generators and beams, while hollow dots and dashed lines represent the removed laser generators and beams. The arrow is the escaping route.

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

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


title: [ICPC2021 Macao R] Shortest Path Fast Algorithm

description:
Recently, BaoBao has learned the Shortest Path Fast Algorithm (SPFA, or more formally, Bellman-Ford-Moore Algorithm) to solve the shortest path problem efficiently. He realizes that the algorithm looks so similar to the Dijkstra's algorithm after replacing the FIFO queue with priority queue, and shows you the below pseudo code.

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

By picking the best vertex from $Q$ we mean picking the vertex with the smallest priority value (in case that multiple vertices have the smallest priority value, pick the vertex with the largest index among them).

You, the future computer scientist, find the BaoBao-modified SPFA algorithm works so slow in some carefully construted graph. However, BaoBao is sure that his algorithm works well, unless you show him a simple undirected graph that makes the variable $\tt{cnt}$ in the SPFA function no less than a certain $k$ $\textbf{at some time}$. For convenience, the source vertex of the SPFA function is specified to be vertex $1$.

Just teach him a lesson!

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

The first and only line of the input contains a single integer $k$ where $k = 1$ for the sample test case and $k = 10^5$ for the only secret test case.

outputFormat:
Output several lines in the following format to describe the input data of a simple undirected graph that makes the variable $\tt{cnt}$ in the SPFA function no less than $k$ $\textbf{at some time}$.

The first line contains two integers $n$ ($1 \le n \le 100$) and $m$ ($0 \le m \le 10^3$), indicating the number of vertices and edges in the graph.

Then $m$ lines follow, the $i$-th of which contains three integers $u_i$, $v_i$ ($1 \le u_i, v_i \le n$) and $w_i$ ($1 \le w_i \le 10^6$), indicating that the $i$-th edge in the graph has a weight of $w_i$ and connects the $u_i$-th and the $v_i$-th vertices.

Note that a simple graph contains no self-loops and no multiple edges.

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

最近，宝宝学习了最短路径快速算法（SPFA，或更正式地说，贝尔曼-福特-摩尔算法）以有效地解决最短路径问题。他意识到，如果用优先队列代替先进先出队列，该算法看起来与 Dijkstra 算法非常相似，并向你展示了下面的伪代码。

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

选择 $Q$ 中最佳顶点意味着选择具有最小优先级值的顶点（如果有多个顶点具有最小优先级值，则选择其中索引最大的顶点）。

作为未来的计算机科学家，你发现宝宝修改后的 SPFA 算法在某些精心构造的图中运行速度非常慢。然而，宝宝确信他的算法很好，除非你向他展示一个简单的无向图，在该图中，SPFA 函数中的变量 $\tt{cnt}$ 在某个时刻不少于某个 $k$。为方便起见，SPFA 函数的源顶点被指定为顶点 $1$。

就给他个教训吧！

**【输入格式】**

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

输入的第一行包含一个整数 $k$，其中 $k = 1$ 为示例测试用例，$k = 10^5$ 为唯一的秘密测试用例。

**【输出格式】**

输出几行以以下格式描述简单无向图的输入数据，使得 SPFA 函数中的变量 $\tt{cnt}$ 在某个时刻不少于 $k$。

第一行包含两个整数 $n$（$1 \le n \le 100$）和 $m$（$0 \le m \le 10^3$），表示图中的顶点数和边数。

然后，跟着 $m$ 行，第 $i$ 行包含三个整数 $u_i$、$v_i$（$1 \le u_i, v_i \le n$）和 $w_i$（$1 \le w_i \le 10^6$），表示图中的第 $i$ 条边的权重为 $w_i$，连接了第 $u_i$ 个和第 $v_i$ 个顶点。

注意，简单图不包含自环和重边。

**【提示说明】**

为方便起见，你可以从比赛网站上复制与给定伪代码对应的 $\tt{C++}$ 代码。将代码保存为 $\tt{spfa.cpp}$，使用 $\text{g++ spfa.cpp -O2 -o spfa}$ 进行编译，你将得到一个名为 $\tt{spfa}$ 的可执行文件。运行 $\tt{spfa}$，将你的输出提供给它的标准输入，它将打印出 $\tt{cnt}$ 的 $\textbf{最终}$ 值。给出示例输出后，它将打印出 $4$，这意味着示例输出不足以通过秘密测试用例。

注意，给定的代码不会检查你的输出的有效性（例如，它不会检查你的输出是否真的是一个简单图）。即使可执行文件打印出一个很大的值，如果你的输出无效，你仍然可能失败测试。

翻译来自于：[ChatGPT](https://chatgpt.com/)。

hint:
For your convenience, you can copy the $\tt{C++}$ code, which corresponds to the given pseudo code, from the contest website. Save the code as $\tt{spfa.cpp}$, use $\text{g++ spfa.cpp -O2 -o spfa}$ to compile it and you will get an executable file named $\tt{spfa}$. Run $\tt{spfa}$, feed your output to its standard input and it will print out the $\textbf{final}$ value of $\tt{cnt}$. Given the sample output it will print out $4$, which means the sample output is not sufficient to pass the secret test case.

Note that the given code does not check the validity of your output (for example it does not check if your output is really a simple graph). You might still fail the test if your output is invalid, even if the executable prints out a large value.


title: [ICPC2021 Macao R] Pass the Ball!

description:
There are $n$ children playing with $n$ balls. Both children and balls are numbered from $1$ to $n$.

Before the game, $n$ integers $p_1, p_2, \cdots, p_n$ are given. In each round of the game, child $i$ will pass the ball he possesses to child $p_i$. It is guaranteed that no child will pass his ball to himself, which means $p_i \neq i$. Moreover, we also know that after each round, each child will hold exactly one ball.

Let $b_i$ be the ball possessed by child $i$. At the beginning of the game, child $i$ ($1 \le i \le n$) will be carrying ball $i$, which means $b_i=i$ initially. You're asked to process $q$ queries. For each query you're given an integer $k$ and you need to compute the value of $\sum\limits_{i=1}^{n} i \times b_i$ after $k$ rounds.

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

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

The second line contains $n$ integers $p_1, p_2, \cdots, p_n$ ($1 \le p_i \le n$) indicating how the children pass the balls around.

For the following $q$ lines, the $i$-th line contains one integer $k_i$ ($1 \le k_i \le 10^9$) indicating a query asking for the result after $k_i$ rounds.

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

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

有 $n$ 个孩子和 $n$ 个球在玩游戏。孩子和球都从 $1$ 编号到 $n$。

游戏开始前，给出了 $n$ 个整数 $p_1, p_2, \cdots, p_n$。在游戏的每一轮中，孩子 $i$ 会把他手里的球传给孩子 $p_i$。保证没有孩子会把他手里的球传给自己，也就是说 $p_i \neq i$。此外，我们还知道在每一轮之后，每个孩子手里都会正好持有一个球。

设 $b_i$ 表示孩子 $i$ 所持有的球。在游戏开始时，孩子 $i$（$1 \le i \le n$）将携带球 $i$，也就是说 $b_i=i$。你需要处理 $q$ 个查询。对于每个查询，你会得到一个整数 $k$，你需要计算在 $k$ 轮后 $\sum\limits_{i=1}^{n} i \times b_i$ 的值。

**【输入格式】**

输入的第一行包含两个整数 $n$（$2 \le n \le 10^5$）和 $q$（$1 \le q \le 10^5$），表示孩子的数量和查询的数量。

第二行包含 $n$ 个整数 $p_1, p_2, \cdots, p_n$（$1 \le p_i \le n$），表示孩子之间传球的方式。

接下来的 $q$ 行中，第 $i$ 行包含一个整数 $k_i$（$1 \le k_i \le 10^9$），表示询问在 $k_i$ 轮后的结果。

**【输出格式】**

对于每个查询，输出一行包含一个整数，表示答案。

**【样例解释】**

示例测试用例解释如下。

$$
\begin{array}{|c|c|c|c|c|c|} \hline \textbf{轮次} & \textbf{b1} & \textbf{b2} & \textbf{b3} & \textbf{b4} & \textbf{答案} \\\hline
1 & 3 & 1 & 4 & 2 & 25 \\\hline
2 & 4 & 3 & 2 & 1 & 20 \\\hline
3 & 2 & 4 & 1 & 3 & 25 \\\hline
4 & 1 & 2 & 3 & 4 & 30 \\\hline
\end{array}
$$

翻译来自于：[ChatGPT](https://chatgpt.com/)。

hint:
The sample test case is explained below.

$$
\begin{array}{|c|c|c|c|c|c|} \hline \textbf{Round} & \textbf{b1} & \textbf{b2} & \textbf{b3} & \textbf{b4} & \textbf{Answer} \\\hline
1 & 3 & 1 & 4 & 2 & 25 \\\hline
2 & 4 & 3 & 2 & 1 & 20 \\\hline
3 & 2 & 4 & 1 & 3 & 25 \\\hline
4 & 1 & 2 & 3 & 4 & 30 \\\hline
\end{array}
$$


title: [ICPC2021 Macao R] Sandpile on Clique

description:
The $\textit{Abelian Sandpile Model}$ is a famous dynamical system displaying self-organized criticality. It has been studied for decades since it was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper. The sandpile prediction is of wide interest in physics,
computer science, and mathematics, both for its beautiful algebraic structure and for its relevance to applications like load balancing and derandomization of models like internal diffusion-limited aggregation. The sandpile model is related to many other models and physical phenomena, like the rotor-routing model, avalanche models.

In the sandpile model, we are given an undirected graph $G$ whose vertices are indexed from $1$ to $n$. We're also given $n$ integers $a_1, a_2, \cdots, a_n$ where $a_i$ indicates that there are $a_i$ chips placed on vertex $i$ initially. Each turn we will pick an arbitrary vertex $v$ such that the number of chips on $v$ is not smaller than the number of edges connecting $v$, denoted as $d_v$. For each neighbor of $v$, it will receive one chip from $v$. Therefore, $v$ will lost $d_v$ chips. This process is called firing or toppling. Firing will keep happening until no vertex $v$ has at least $d_v$ chips.

It can be proven that the order of firing doesn't affect the result. Meanwhile, it is also possible that the firing will never terminate. This instance is described as ``recurrent``. Now you are given a clique and the initial number of chips. Determine whether this instance is a recurrent one. If not, please output the final number of chips for each node respectively.

A clique (also called a complete graph) is a graph where every two vertices are connected with an edge.

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

The first line of the input contains an integer $n$ ($2 \leq n \leq 5 \times 10^5$) indicating the size of the clique.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($0 \leq a_i \leq 10^9$) where $a_i$ indicates the initial number of chips placed on vertex $i$.

outputFormat:
Output one line. If the given sandpile instance will terminate, output $n$ integers separated by a space where the $i$-th integer indicates the final number of chips on the $i$-th vertex. Otherwise output ``Recurrent`` (without quotes) instead.

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

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

阿贝尔沙堆模型（Abelian Sandpile Model）是一个著名的显示自组织临界性的动力学系统。自从它由 Per Bak、Chao Tang 和 Kurt Wiesenfeld 在 1987 年的一篇论文中引入以来，它已经被研究了数十年。沙堆模型的预测引起了物理学、计算机科学和数学的广泛关注，这不仅是因为它美丽的代数结构，还因为它与负载平衡和内部扩散有关的模型的应用，如去随机化。沙堆模型与许多其他模型和物理现象相关，如转子路由模型、雪崩模型。

在沙堆模型中，给定一个顶点编号从 $1$ 到 $n$ 的无向图 $G$。我们还给出了 $n$ 个整数 $a_1, a_2, \cdots, a_n$，其中 $a_i$ 表示初始时放置在顶点 $i$ 上的筹码数量。每个回合，我们将选择一个任意的顶点 $v$，使得 $v$ 上的筹码数量不小于与 $v$ 相连的边数，记为 $d_v$。对于 $v$ 的每个邻居，它将从 $v$ 接收一枚筹码。因此，$v$ 将失去 $d_v$ 枚筹码。这个过程被称为 ``firing`` 或 ``toppling``。直到没有顶点 $v$ 至少有 $d_v$ 枚筹码时，firing 才会停止。

可以证明，firing 的顺序不会影响结果。同时，也可能 firing 永远不会终止。这种情况被描述为“recurrent”。现在给定一个团和初始筹码数量，请确定这个实例是否是一个 recurrent 实例。如果不是，请分别输出每个节点的最终筹码数量。

团（也称为完全图）是一个图，其中任意两个顶点都有边相连。

**【输入格式】**

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

输入的第一行包含一个整数 $n$（$2 \leq n \leq 5 \times 10^5$），表示团的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$0 \leq a_i \leq 10^9$），其中 $a_i$ 表示放置在顶点 $i$ 上的初始筹码数量。

**【输出格式】**

输出一行。如果给定的沙堆实例将终止，则输出由空格分隔的 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 个顶点上的最终筹码数量。否则输出 ``Recurrent``（不包括引号）。

请不要在每行末尾输出额外的空格，否则您的解决方案可能被认为是错误的！

**【样例解释】**

对于第一个样例测试用例：

- 我们只能在开始时选择顶点 $1$。筹码数量变为 $\{1, 1, 4, 1, 4\}$。
- 现在我们可以选择顶点 $3$ 或 $5$，因为它们都至少有 $4$ 枚筹码。我们选择顶点 $3$，筹码数量变为 $\{2, 2, 0, 2, 5\}$。选择顶点 $5$ 会得到相同的结果。
- 现在我们选择顶点 $5$。筹码数量变为 $\{3, 3, 1, 3, 1\}$。没有顶点至少有 $4$ 枚筹码，因此 firing 终止。

对于第二个样例测试用例，我们可以重复选择顶点 $1$ 和 $2$。firing 永远不会终止。

翻译来自于：[ChatGPT](https://chatgpt.com/)

hint:
For the first sample test case:

- We can only select vertex $1$ at the beginning. The number of chips becomes $\{1, 1, 4, 1, 4\}$.
- We can now select vertex $3$ or $5$ because both of them have at least $4$ chips. We select vertex $3$ and the number of chips becomes $\{2, 2, 0, 2, 5\}$. Selecting vertex $5$ will lead to the same result.
- We now select vertex $5$. The number of chips becomes $\{3, 3, 1, 3, 1\}$. There is no vertex with at least $4$ chips so the firing terminates.

For the second sample test case, we can select vertex $1$ and $2$ repeatedly. The firing never terminates.


title: [ICPC2021 Macao R] Cyclic Buffer

description:
There is a cyclic buffer of size $n$ with readers from the $1$-st position to the $k$-th position (both inclusive). Let $a_i$ ($1 \le i \le n$) be the integer at the $i$-th position of the buffer initially. What's more, $a_1, a_2, \cdots, a_n$ form a permutation of $n$.

We're going to visit all the integers from $1$ to $n$ (both inclusive) in increasing order. An integer can be visited only when it is residing in positions with readers (that is to say, when it is in the first $k$ positions). In case that an integer cannot be visited, we can shift the whole buffer in either directions any number of times.

- If we shift the buffer to the left once, integers in the $i$-th position will be moved to the $(i - 1)$-th position if $i > 1$, and integer in the $1$-st position will be moved to the $n$-th position.
- If we shift the buffer to the right once, integers in the $i$-th position will be moved to the $(i + 1)$-th position if $i < n$, and integer in the $n$-th position will be moved to the $1$-st position.

What's the minimum number of times to shift the buffer so that we can visit all the integers in increasing order?

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

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^6$) indicating the size of the buffer and the number of readers.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$) where $a_i$ indicates the integer in the $i$-th position of the buffer initially.

It's guaranteed that the given $n$ integers form a permutation of $n$. It's also guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

outputFormat: For each test case output one line containing one integer indicating the minimum number of times to shift the buffer so that all integers can be visited in increasing order.

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

有一个大小为 $n$ 的循环缓冲区，读入流从第 $1$ 个位置到第 $k$ 个位置（两者都包含在内）。设 $a_i$ ($1 \le i \le n$) 是缓冲区初始时第 $i$ 个位置上的整数。此外，$a_1, a_2, \cdots, a_n$ 形成 $n$ 的一个排列。

我们将以递增顺序访问从 $1$ 到 $n$ 的所有整数（两者都包含在内）。只有当整数位于具有读入流的位置（即位于前 $k$ 个位置）时，才能访问整数。如果某个整数无法访问，则可以将整个缓冲区向任意方向移动任意次数。

- 如果我们向左移动缓冲区一次，则位于第 $i$ 个位置的整数将移动到第 $(i - 1)$ 个位置（如果 $i > 1$），并且位于第 $1$ 个位置的整数将移动到第 $n$ 个位置。
- 如果我们向右移动缓冲区一次，则位于第 $i$ 个位置的整数将移动到第 $(i + 1)$ 个位置（如果 $i < n$），并且位于第 $n$ 个位置的整数将移动到第 $1$ 个位置。

我们需要移动缓冲区的最小次数，以便以递增顺序访问所有整数。

**【输入格式】**

每个测试文件中包含多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 10^6$)，表示缓冲区的大小和读入流的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$)，其中 $a_i$ 表示缓冲区初始时第 $i$ 个位置上的整数。

保证给定的 $n$ 个整数构成 $n$ 的一个排列。还保证所有测试用例中 $n$ 的总和不超过 $10^6$。

**【输出格式】**

对于每个测试用例，输出一行，包含一个整数，表示移动缓冲区的最小次数，以便所有整数可以以递增顺序访问。

**【样例解释】**

对于第一个样例测试用例：
- 向右移动一次，使缓冲区变为 $\{1, 2, 4, 3, 5\}$。现在 $1$ 和 $2$ 可以按顺序访问，因为它们位于前 $3$ 个位置。
- 向左移动两次，使缓冲区变为 $\{4, 3, 5, 1, 2\}$。现在 $3$、$4$ 和 $5$ 可以按顺序访问，因为它们位于前 $3$ 个位置。

翻译来自于：[ChatGPT](https://chatgpt.com/)

hint:
For the first sample test case:
- Shift to the right once so the buffer becomes $\{1, 2, 4, 3, 5\}$. $1$ and $2$ can now be visited in order as they are in the first $3$ positions.
- Shift to the left twice so the buffer becomes $\{4, 3, 5, 1, 2\}$. $3$, $4$ and $5$ can now be visited in order as they are in the first $3$ positions.


title: [ICPC2021 Macao R] Permutation on Tree

description:
Given a tree with $n$ vertices where vertex $r$ is the root, we say a permutation $p_1, p_2, \cdots, p_n$ of $n$ is good if it satisfies the following constraint:

- Let $a_x$ be the index of $x$ in the permutation (That is, $p_{a_x} = x$). For all $1 \le u, v \le n$, if vertex $u$ is an ancestor of vertex $v$ in the tree, then $a_u < a_v$.

Define the score of a permutation to be $\sum\limits_{i=1}^{n-1} |p_i - p_{i+1}|$ where $|x|$ is the absolute value of $x$. Calculate the sum of scores of all different good permutations.

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

The first line contains two integers $n$ and $r$ ($2 \le n \le 200$, $1 \le r \le n$) indicating the size of the tree and the root.

For the following $(n - 1)$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) indicating an edge connecting vertex $u_i$ and $v_i$ in the tree.

outputFormat: For each test case output one line containing one integer indicating the sum of scores of all different good permutations. As the answer may be large, output the answer modulo $(10^9 + 7)$.

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

给定一个有 $n$ 个顶点的树，其中顶点 $r$ 是根，如果一个排列 $p_1, p_2, \cdots, p_n$ 满足以下约束条件，我们称其为好排列：

- 设 $a_x$ 是排列中 $x$ 的索引（即 $p_{a_x} = x$）。对于所有 $1 \le u, v \le n$，如果顶点 $u$ 是树中顶点 $v$ 的祖先，则 $a_u < a_v$。

定义排列的分数为 $\sum\limits_{i=1}^{n-1} |p_i - p_{i+1}|$，其中 $|x|$ 表示 $x$ 的绝对值。计算所有不同好排列的分数之和。

**【输入格式】**

每个测试文件中包含一个测试用例。输入的第一行包含两个整数 $n$ 和 $r$ ($2 \le n \le 200$, $1 \le r \le n$)，表示树的大小和根。

接下来的 $(n - 1)$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)，表示树中连接顶点 $u_i$ 和 $v_i$ 的边。

**【输出格式】**

对于每个测试用例，输出一行，包含一个整数，表示所有不同好排列的分数之和。由于答案可能很大，输出答案对 $(10^9 + 7)$ 取模的结果。

**【样例解释】**

对于第一个样例测试用例，有三个好排列：$\{2, 1, 3, 4\}$、$\{2, 1, 4, 3\}$ 和 $\{2, 3, 1, 4\}$。它们的分数分别为 $4$、$5$ 和 $6$，因此答案为 $4 + 5 + 6 = 15$。

对于第二个样例测试用例，只有一个好排列：$\{1, 2, 3\}$。它的分数为 $2$。

翻译来自于：[ChatGPT](https://chatgpt.com/)。

hint:
For the first sample test case, there are three good permutations: $\{2, 1, 3, 4\}$, $\{2, 1, 4, 3\}$ and $\{2, 3, 1, 4\}$. Their scores are $4$, $5$ and $6$ respectively so the answer is $4 + 5 + 6 = 15$.

For the second sample test case, there is only one good permutation: $\{1, 2, 3\}$. It's score is $2$.


title: [ICPC2021 Macao R] LCS Spanning Tree

description:
Given a complete undirected graph of $n$ vertices and $n$ strings $s_1, s_2, \cdots, s_n$, the weight of edge connecting vertices $i$ and $j$ is equal to the length of the longest common substring (LCS) between $s_i$ and $s_j$. Compute the maximum total weight of any spanning tree on this graph.

A substring of a string can be obtained by removing some (possibly zero) characters from the beginning and/or the end of that string. For example, ``maca``, ``aca`` and ``cau`` are all substrings of ``macau``, while ``acu`` is not.

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

The first line of the input contains one integer $n$ ($1 \leq n \leq 2 \times 10^6$) indicating the number of vertices and strings.

For the following $n$ lines, the $i$-th line contains one string $s_i$ ($1 \le |s_i| \le 2 \times 10^6$) consisting only of lowercase English letters.

It's guaranteed that the sum of lengths of all strings will not exceed $2 \times 10^6$.

outputFormat: Output one line containing one integer indicating the answer.

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

给定一个有 $n$ 个顶点的完全无向图和 $n$ 个字符串 $s_1, s_2, \cdots, s_n$，连接顶点 $i$ 和 $j$ 的边的权重等于字符串 $s_i$ 和 $s_j$ 的最长公共子串（LCS）的长度。计算此图上任意生成树的最大总权重。

一个字符串的子串可以通过从该字符串的开头和/或结尾删除一些（可能为零）字符来获得。例如，“maca”、“aca” 和“cau”都是“macau”的子串，而“acu”不是。

**【输入格式】**

每个测试文件中包含一个测试用例。

输入的第一行包含一个整数 $n$ ($1 \leq n \leq 2 \times 10^6$)，表示顶点和字符串的数量。

接下来的 $n$ 行，第 $i$ 行包含一个字符串 $s_i$ ($1 \le |s_i| \le 2 \times 10^6$)，由小写英文字母组成。

保证所有字符串的长度之和不超过 $2 \times 10^6$。

**【输出格式】**

输出一行，包含一个整数，表示答案。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: [ICPC2021 Macao R] Colorful Tree

description:
Your task is to maintain a colorful tree and process queries.

At the beginning, there is only one vertex numbered $1$ with color $C$ on the tree. Then there are $q$ operations of two types coming in order:
- $0$ $x$ $c$ $d$: Add a new vertex indexed $(n+1)$ with color $c$ to the tree, where $n$ is the current number of existing vertices. An edge connecting vertex $x$ and $(n+1)$ with length $d$ will also be added to the tree.
- $1$ $x$ $c$: Change the color of vertex $x$ to $c$.

After each operation, you should find a pair of vertices $u$ and $v$ ($1 \le u, v \le n$) with $\textbf{different}$ colors in the current tree so that the distance between $u$ and $v$ is as large as possible.

The distance between two vertices $u$ and $v$ is the length of the shortest path from $u$ to $v$ on the tree.

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 of the input contains two integers $q$ and $C$ ($1 \le q \le 5 \times 10^5$, $1 \le C \le q$) indicating the number of operations and the initial color of vertex $1$.

For the following $q$ lines, each line describes an operation taking place in order with $3$ or $4$ integers.
- If the $i$-th line contains $4$ integers $0$, $x_i$, $c_i$ and $d_i$ ($1 \le x_i \le n$, $1 \le c_i \le q$, $1 \le d \le 10^9$), the $i$-th operation will add a new vertex $(n + 1)$ with color $c_i$ to the tree and connect it to vertex $x_i$ with an edge of length $d_i$.
- If the $i$-th line contains $3$ integers $1$, $x_i$ and $c_i$ ($1 \le x_i \le n$, $1 \le c_i \le q$), the $i$-th operation will change the color of vertex $x_i$ to $c_i$.

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

outputFormat: For each operation output the maximum distance between two vertices with different colors. If no valid pair exists output $0$ instead.

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

你的任务是维护一棵有色树并处理查询。

一开始，树上只有一个编号为 $1$ 的顶点，颜色为 $C$。然后按顺序进行 $q$ 个操作，有两种类型：
- $0$ $x$ $c$ $d$：向树中添加一个颜色为 $c$ 的新顶点，其编号为 $(n+1)$，其中 $n$ 是当前存在的顶点数。同时，添加一条连接顶点 $x$ 和 $(n+1)$ 的长度为 $d$ 的边。
- $1$ $x$ $c$：将顶点 $x$ 的颜色更改为 $c$。

在每次操作之后，你应该找到当前树中颜色 $\textbf{不同}$ 的两个顶点 $u$ 和 $v$（$1 \le u, v \le n$），使得它们之间的距离尽可能大。

两个顶点 $u$ 和 $v$ 之间的距离是树上从 $u$ 到 $v$ 的最短路径的长度。

**【输入格式】**

输入的第一行包含两个整数 $q$ 和 $C$（$1 \le q \le 5 \times 10^5$，$1 \le C \le q$），表示操作的数量和顶点 $1$ 的初始颜色。

接下来的 $q$ 行中，每行描述一个按顺序进行的操作，包含 $3$ 或 $4$ 个整数。
- 如果第 $i$ 行包含 $4$ 个整数 $0$、$x_i$、$c_i$ 和 $d_i$（$1 \le x_i \le n$，$1 \le c_i \le q$，$1 \le d \le 10^9$），则第 $i$ 个操作将向树中添加一个颜色为 $c_i$ 的新顶点 $(n + 1)$，并将其与顶点 $x_i$ 连接，边的长度为 $d_i$。
- 如果第 $i$ 行包含 $3$ 个整数 $1$、$x_i$ 和 $c_i$（$1 \le x_i \le n$，$1 \le c_i \le q$），则第 $i$ 个操作将顶点 $x_i$ 的颜色更改为 $c_i$。

保证所有测试用例中 $q$ 的总和不超过 $5 \times 10^5$。

**【输出格式】**

对于每个操作，输出两个不同颜色顶点之间的最大距离。如果不存在有效的顶点对，则输出 $0$。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: [ICPC2021 Macao R] Link-Cut Tree

description:
BaoBao just learned how to use a data structure called link-cut tree to find cycles in a graph and decided to give it a try. BaoBao is given an undirected graph with $n$ vertices and $m$ edges, where the length of the $i$-th edge equals $2^i$. She needs to find a simple cycle with the smallest length.

A simple cycle is a subgraph of the original graph containing $k$ ($3 \le k \le n$) vertices $a_1, a_2, \cdots, a_k$ and $k$ edges such that for all $1 \le i \le k$ there is an edge connecting vertices $a_i$ and $a_{(i \mod k) + 1}$ in the subgraph. The length of a simple cycle is the total length of the edges in the cycle.

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$ ($3 \le n \le 10^5$, $1 \le m \le 10^5$) indicating the number of vertices and edges in the original graph.

For the following $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$) indicating an edge connecting vertices $u_i$ and $v_i$ with length $2^i$. There are no self loops nor multiple edges. Note that the graph is not necessarily connected.

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

outputFormat:
For each test case output one line. If there are no simple cycles in the graph output ``-1`` (without quotes); Otherwise output $k$ integers separated by a space in increasing order indicating the indices of the edges in the simple cycle with the smallest length. It can be shown that there is at most one answer.

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

translation:
BaoBao刚学会如何用一种叫做 LCT 的数据结构去找图中的环，因此决定试一试。BaoBao 得到一个有 $n$ 个点，$m$    条边的无向图，其中第 $i$ 条边的权值为 $2^i$。她需要找到一个权值最小的环。

环是原图的子图，包含 $k$ ($3 \le k \le n$) 个点 $a_1, a_2, \cdots, a_k$ 和 $k$ 条边，使得对于所有的 $1 \le i \le k$ ，子图中存在边连接点 $a_i$ 和 $a_{(i \mod k) + 1}$ 。环的权值为环上所有边的权值之和。

每一个测试点有多组测试数据。 第一行有一个整数 $T$ 表示数据组数。

第二行有两个整数 $n$ 和 $m$ ($3 \le n \le 10^5$, $1 \le m \le 10^5$)，分别为点数和边数。

接下来 $m$ 行， 第 $i$ 行包括两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$) 表示有一条边连接 $u_i$ 和 $v_i$ ，权值为 $2^i$。 请注意，图 **不一定** 连通。

保证所有测试样例 $n$ 之和， $m$ 之和均不超过 $10^6$.

对每一组测试数据输出一行。如果图中没有环，输出 ``-1`` 。 否则 **升序** 输出边的编号，共 $k$ 个整数 ， 显然答案唯一。

第一个测试样例如图，图中标注出的为边的编号，环 $2$, $4$, $5$, $6$ 边权为 $2^2 + 2^4 + 2^5 + 2^6 = 116$，为最小环。

![](https://cdn.luogu.com.cn/upload/image_hosting/vqpea23u.png?x-oss-process=image/resize,m_lfit,h_170,w_225)

hint: The first sample test case is shown below. The integers beside the edges are their indices (outside the parentheses) and lengths (inside the parentheses). The simple cycle with the smallest length consists of edges $2$, $4$, $5$ and $6$ with a length of $2^2 + 2^4 + 2^5 + 2^6 = 116$.


title: 「HCOI-R1」哀之变化

background:
哀喜欢数字。

她还喜欢变化。

description:
有一整数 $a$ 初始为 $1$。

哀想让 $a$ 进行恰好 $k$ 次变化，每次从以下两种变化中选择一个：

- $a\gets a - 1$；
- $a\gets a \times 2$。

哀很好奇，经过 **恰好** $k$ 次变化后 $a$ 能否变成 $n$。

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

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

接下来 $T$ 行，每行两个整数，依次为 $k$ 和 $n$，表示哀的一次询问。

outputFormat: 共 $T$ 行，对于每次询问，若 $a$ 可以变成 $n$，输出 `Yes`，否则输出 `No`。

hint:
### 样例解释 1

+ 若 $k = 2$，$n = 5$，可以证明无解。
+ 若 $k = 2$，$n = 4$，一种可能的操作方式如下：
	+ 第一步，$a \gets a\times 2 = 2$；
	+ 第二步，$a \gets a\times 2 = 4$。
+ 若 $k = 3$，$n = 3$，一种可能的操作方式如下：
	+ 第一步，$a \gets a\times 2 = 2$；
	+ 第二步，$a \gets a\times 2 = 4$。
	+ 第三步，$a \gets a-1 = 3$。

### 数据规模与约定

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

+ Subtask 0（10 pts）：$T \leq 10$，$k \leq 15$。
+ Subtask 1（25 pts）：$n, k \leq 2\times 10^3$。
+ Subtask 2（65 pts）：无特殊限制。

对于所有数据，$1 \leq T \leq 10^5$，$0 \leq n, k \leq 10^{18}$。


title: 「FAOI-R3」移民计划 (C)

description:
给定两个正整数 $n,a$。

现有两个正整数数列 $\{h_n\},\{s_n\}$ 和一个正整数 $W$，满足：

$$\begin{cases} s_1=a, \\  s_i=\lceil \dfrac{h_{i-1}}{i} \rceil, \\  h_i=i \times s_i,\\  W=h_1\times h_2\times \ldots\times h_n. \end{cases}$$

试计算 $W$ 的值。**答案对 $10^9+7$ 取模。**

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

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

下面 $T$ 行，每行两个整数 $n,a$。

outputFormat: $T$ 行，每行一个整数，对应一组数据的答案。


title: 「KDOI-06-J」旅行

description:
小 C 在 C 国旅行。

C 国有 $n\times m$ 个城市，可以看做 $n\times m$ 的网格。定义 $(i,j)$ 表示在网格中第 $i$ 行第 $j$ 列的城市。

该国有 $2$ 种交通系统：

* 对于所有 $1\leq i<n,1\leq j\leq m$，$(i,j)$ 到 $(i+1,j)$ 有一段由 L 公司修的单向铁路；
* 对于所有 $1\leq i\leq n,1\leq j<m$，$(i,j)$ 到 $(i,j+1)$ 有一段由 Z 公司修的单向铁路；

在每一个城市有一个售票口，$(i,j)$ 城市的售票口可以用 $a_{i,j}$ 元购买一张 L 公司的铁路票，$b_{i,j}$ 元购买一张 Z 公司的铁路票。当你拥有一个公司的一张铁路票时，你可以乘坐这个公司的任意一段铁路，并消耗掉这张铁路票。注意，一张铁路票可以且仅可以使用一次。

小 C 原来在城市 $(1,1)$。他想要在 C 国旅游，但是他不想浪费任何的钱（即，当他旅游完毕时手上不应该有多余的车票）。对于所有 $1\leq x\leq n,1\leq y\leq m$，求他花 $k$ 元钱并在城市 $(x,y)$ 结束旅行的方案数，对 $998\ 244\ 353$ 取模。

两种旅行方案不同，当且仅当小 C 经过的城市不同，或他在某一个城市购买的某家公司的铁路票数量不同。

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

输入的第一行包含三个正整数 $n,m,k$，表示网格的大小和钱的数目。

接下来 $n$ 行，每行 $m$ 个正整数，第 $i$ 行第 $j$ 个正整数表示 $a_{i,j}$。

接下来 $n$ 行，每行 $m$ 个正整数，第 $i$ 行第 $j$ 个正整数表示 $b_{i,j}$。

outputFormat:
输出到标准输出。

输出一共 $n$ 行，每行 $m$ 个整数，表示到每个点钱恰好花完并结束旅行的方案数，对 $998\ 244\ 353$ 取模。


title: 「KDOI-06-S」树上异或

description:
给定一棵包含 $n$ 个节点的树，第 $i$ 个点有一个点权 $x_i$。

对于树上的 $n-1$ 条边，每条边选择删除或不删除，有 $2^{n-1}$ 种选择是否删除每条边的方案。

对于每种删除边的方案，设删除后的图包含 $k$ 个连通块，定义这个方案的权值为图中连通块点权异或和的乘积。形式化地说，若这张图包含连通块 $C_1,C_2,\ldots,C_k$，其中 $C_i$ 是第 $i$ 个连通块的顶点集合，设 $v_i=\bigoplus_{u\in C_i} x_u$，则这个方案的权值为 $v_1\times v_2\times \cdots\times v_k$。

求这 $2^{n-1}$ 种删除边的方案的**权值**之和，答案对 $998~244~353$ 取模。

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

输入的第一行包含一个正整数 $n$，表示树的节点个数。

第二行 $n$ 个非负整数 $x_1,x_2,\ldots,x_n$，表示每个点的点权。

第三行 $n-1$ 个正整数 $f_2,f_3,\ldots,f_n$，表示节点 $i$ 与 $f_{i}$ 之间有一条无向边。

outputFormat:
输出到标准输出。

输出包含一行一个整数，表示所有 $2^{n-1}$ 种删除边的方案的**权值**之和，答案对 $998~244~353$ 取模。


title: 「Daily OI Round 3」War

background: 《赤壁之战》是一款开放世界冒险游戏，这意味着从你踏入提瓦特的第一刻起，只要合理规划自己的体力，不论翻山越岭、还是横渡江河，总有办法见到新的风景。

description:
有 $n$ 条船，船编号为 $1$ 至 $n$。每条船上有 $m$ 个士兵，士兵编号为 $1$ 至 $m$。

开始时，有若干组船由铁索相连。具体的关系给出如下：

给出 $s$ 组关系，形如 $l_1,r_1,l_2,r_2$，表示 $\forall k \in [0,r_1-l_1]$，第 $l_1+k$ 条船与第 $l_2+k$ 条船相连，保证 $r_1-l_1+1=r_2-l_2+1$ 且 $l_1 < l_2$。

保证 $\forall p \in [1,n]$，最多存在一组关系使得 $l_2 \le p \le r_2$。

然后有 $q$ 个操作，操作如下（操作按照时间先后顺序编号为 $1 \sim q$）：

操作 $1$：向编号为 $p$ 的船的 $[L,R]$ 区间的士兵发射一支火箭。这样操作之后，这个区间的所有士兵都会着火。由于铁锁连环的缘故，所有与 $p$ 直接相连或间接相连的船的 $[L,R]$ 区间的士兵都会着火。注意，士兵可能着火多次。

操作 $2$：撤回编号为 $p$ 的操作，保证这个操作必定是操作 $1$。**保证不会多次撤回同一个操作，并且以后的询问都不考虑已经撤销的操作所带来的影响。**

操作 $3$：询问船 $p$ 上区间为 $[L,R]$ 的士兵是否全部着火。如果全部着火请输出 `Yes`，否则输出 `No`。

inputFormat:
第一行四个整数分别是 $n,m,s,q$，含义如题所示。

接下来 $s$ 行，每行四个整数，表示一个铁索关系。

接下来 $q$ 行，表示操作。

每行第一个整数 $op$ 表示操作种类。

- 若 $op=1$，你需要输入三个整数 $p,L,R$，并按照题目要求执行操作 $1$。

- 若 $op=2$，你需要输入一个整数 $p$，并按照题目要求执行操作 $2$。

- 若 $op=3$，你需要输入三个整数 $p,L,R$，并按照题目要求执行操作 $3$。

outputFormat:
若干行，表示每个 $3$ 操作的答案。

**温馨提示：全部输出 `No` 或者 `Yes` 会得到 $0\text{ pts}$ 的高分。**

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

首先给出了两条关系式，第一条表示了 $1$ 与 $2$，$2$ 与 $3$，$3$ 与 $4$，$4$ 与 $5$，$5$ 与 $6$ 的船是相连的。第二条表示了 $7$ 与 $8$，$8$ 与 $9$，$9$ 与 $10$ 的船是相连的。

第一个操作向第 $4$ 条船的 $1$ 到 $5$ 号士兵发射火箭，因为 $1$ 到 $6$ 号船是相连的，所以 $1$ 到 $6$ 号船上的 $1$ 到 $5$ 号士兵都着火了。

第二个操作询问第一条船的 $2$ 到 $3$ 号是否着火。显然着火了，所以输出 `Yes`。

第三个操作撤回了第一个操作，所以所有士兵操作后都没有着火。

第四个操作询问第一条船的 $2$ 到 $3$ 号是否着火。显然没有着，所以输出 `No`。

第五个操作将十号船的 $[2,7]$ 士兵着火，第六个操作将九号船的 $[3,6]$ 着火。然后第七个操作撤回了第六个操作。注意：目前，第七到十号船的 $[2,7]$ 的士兵是着火的。

第八号操作将七号船的 $[8,13]$ 着火，第九个操作询问是否 $[2,12]$ 全部着火。显然此时已经全部着火了。

#### 【数据范围】

对于全部数据保证：$1 \le n\leq 10^9$，$1 \le m\leq 5\times 10^5$，$0 \le q\leq 10^5$，$0 \le s\leq 200$。


title: [EC Final 2022] Chinese Checker

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

Prof. Pang is playing Chinese Checkers. The game board is the same as the figure shown above. There are $n$ checkers on the board. Prof. Pang wants to know how many different moves there are on the current board.

One **move** consists of several **steps**. At first, Prof. Pang needs to choose one checker $a$ to move. In each step, Prof. Pang needs to choose another checker $b$ as the pivot, and move the checker $a$ to the symmetrical position about the checker $b$. (In one move, Prof. Pang cannot change his choice of $a$ between steps. **If after a step, the checker $a$ will return to its position before the move, this step is not allowed.**) There are several conditions about the pivot $b$:

- The segment connecting $a$ and $b$ needs to be parallel to one of the coordinate axis. Note: There are three axes on the hexagonal board. One of them is horizontal and any pair of axes intersect at an angle of $\pi/3$.
- $a$ and $b$ **do not** need to be adjacent.
- There cannot be extra checkers other than $b$ on the segment connecting $a$ and its symmetrical position.
- The symmetrical position should be on the hexagonal board and is not occupied by any other checker.

A move must have at least one step. After the first step, Prof. Pang can stop at any time he wants. And Prof. Pang can choose any checker on the board as the moving checker. Output the number of different moves Prof. Pang can make. Two moves are different if and only if the sets of positions of all checkers are different after these two moves, i.e., the checkers are indistinguishable.

inputFormat:
The first line contains an integer $T~(1\leq T\leq 100)$ -- the number of test cases.

For each test case, the first line contains an integer $n~(1\leq n\leq 121)$ -- the number of checkers.

Each of the following $n$ lines contains two integers, indicating the position of a checker. The first number indicates which row it is in, and the second number indicates which one of this row it is. They are counting from top to bottom and left to right, starting from $1$.

It is guaranteed that checkers' positions are different.

outputFormat: For each test case, output one integer in a line -- the number of different moves.

translation:
棋盘上有 $n$ 个棋子，你需要求对于当前局面，下一次移动有多少种不同的走法。

一次移动由若干步组成。假设当前要移动的棋子为 $a$，在每一步中，首先需要选择另一个棋子 $b$ 作为跳台，然后将 $a$ 走到关于 $b$ 的对称位置（在一次移动中，你无法更改需要移动的棋子 $a$。并且在某一步中，棋子 $a$ 回到此次移动前所在的位置是不被允许的）。

关于跳台 $b$ 的选择有一些条件：

- $a$ 和 $b$ 之间的连线应当平行于棋盘的某条坐标轴。注：棋盘上一共有三条坐标轴，其中一条与水平线平行，并且任意两条坐标轴之间的夹角均为 $\frac{\pi}{3}$。

- $a$ 和 $b$ 不必相邻。

- 除了跳台 $b$ 以外，$a$ 和其关于 $b$ 的对称点的连线上不能有其他棋子。

- 对称点的位置应当落在棋盘上，并且没有被其他棋子占据。

一次移动需要至少走一步。在第一步以后，你可以随时停下来。你可以选择棋盘上任意一个棋子作为移动棋子。请输出有多少种不同的走法。

两种走法不同当且仅当两次移动后所有棋子的位置组成的集合不同，并且棋子之间不可区分。

### 输入格式
第一行一个整数 $T$，表示数据组数。

对于每组数据，第一行一个整数 $n$，表示棋子数量。

接下来 $n$ 行，每行两个整数，表示棋子位置。第一个整数表示棋子所在行，第二个整数表示棋子所在列（棋子在这一行的第几个位置上，注意每一行的起始位置和列数有可能是不一样的）。行列的编号从 $1$ 开始，分别从上到下，从左到右递增。

保证每个棋子的位置互不相同。

### 输出格式
输出 $T$ 行，每行一个整数，表示不同走法的数量。


title: [EC Final 2022] Chase Game

description:
Prof. Shou is being chased by Prof. Pang on an undirected unweighted simple graph. Initially, Prof. Shou is at vertex $1$. His destination is vertex $n$. Prof. Pang is at vertex $k$.

In each second, Prof. Shou may choose an adjacent vertex and walk to that vertex. Then Prof. Shou is attacked by Prof. Pang. The damage of this attack is equal to $d-dis$ where $d$ is Prof. Pang's attack range and $dis$ is the distance (number of edges in the shortest path) between Prof. Shou and Prof. Pang on the graph. However, when $dis$ is greater than or equal to $d$, Prof. Pang cannot deal any positive damage. In this case, instead of attacking with non-positive damage, he will teleport to the vertex where Prof. Shou is and then deal $d$ damage. (When $dis$ is less than $d$, Prof. Pang will stay at his current vertex.)

Please find the minimum sum of damage Prof. Shou will take to reach vertex $n$ from vertex $1$. Prof. Shou will take the last attack at vertex $n$.

inputFormat:
The first line contains $4$ integers $n, m, k, d$ ($2\le n\le 10^5, n-1\le m\le 2\times 10^5, 1\le k\le n, 1\le d\le 2\times 10^5$).

Each of the next $m$ lines contains two integers $a, b$ ($1\le a, b\le n, a \ne b$) representing an edge of the graph. The edges are distinct. ($a\ b$ and $b\ a$ represents the same edge. Thus, only one of these two lines may appear in the input.)

It is guaranteed that the graph is connected.

outputFormat: Output one integer representing the answer in one line.

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

Shou 教授被 Pang 教授在一个无向无权简单图上追赶。最初，Shou 教授在顶点 $1$。他的目的地是顶点 $n$。Pang 教授在顶点 $k$。

每秒钟，Shou 教授可以选择一个相邻的顶点并走向该顶点。然后，Shou 教授会受到 Pang 教授的攻击。此次攻击的伤害等于 $d-dis$，其中 $d$ 是 Pang 教授的攻击范围，$dis$ 是图上从 Shou 教授到 Pang 教授的距离（最短路径上的边数）。然而，当 $dis$ 大于或等于 $d$ 时，Pang 教授无法造成任何正伤害。在这种情况下，他将不会使用非正的伤害攻击，而是会传送到 Shou 教授所在的顶点，然后造成 $d$ 伤害。（当 $dis$ 小于 $d$ 时，Pang 教授将停留在当前顶点。）

请找出 Shou 教授从顶点 $1$ 到顶点 $n$ 所需的最小伤害总和。Shou 教授将在顶点 $n$ 处受到最后一次攻击。

**【输入格式】**

第一行包含 $4$ 个整数 $n, m, k, d$ ($2\le n\le 10^5, n-1\le m\le 2\times 10^5, 1\le k\le n, 1\le d\le 2\times 10^5$)。

接下来的 $m$ 行中，每行包含两个整数 $a, b$ ($1\le a, b\le n, a \ne b$)，表示图的一条边。边是不同的。($a\ b$ 和 $b\ a$ 表示相同的边。因此，在输入中只会出现这两行中的一行。)

保证图是连通的。

**【输出格式】**

输出一行整数，表示答案。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: [EC Final 2022] Chase Game 2

description:
Prof. Pang and Prof. Shou like playing a chase game.

The game map consists of $n$ rooms and $n-1$ bi-directional channels. The game map is connected. That means, the map forms a tree.

At first, Prof. Pang is in room $u$, while Prof. Shou is in room $v$ ($u\neq v$). Prof. Pang and Prof. Shou take turns to play, and Prof. Shou goes first. In one's turn, the player knows his own position and the other player's position and can decide either to stay in the current room or to move to another room which is connected with the current room directly by a channel. When Prof. Pang and Prof. Shou are in the same room, Prof. Shou is caught by Prof. Pang.

Prof. Pang and Prof. Shou are smart enough. Prof. Pang wants to catch Prof. Shou in a finite number of turns. Prof. Shou does not want to be caught by Prof. Pang in any finite number of turns.

Prof. Shou gets tired of being caught every time and finds Prof. Fei for help. Prof. Shou asks Prof. Fei to add some channels so that Prof. Pang cannot catch him in finite number of turns for any pair of initial rooms $(u,v)$. Prof. Fei is lazy, so he hopes to add as few channels as possible. If no matter how to add the channels there is always a pair of rooms $(u,v)$ such that Prof. Pang can catch Prof. Shou, output $-1$.

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

For each test case, the first line contains a single integer $n$ ($2\le n\le 10^5$) denoting the number of rooms.

For the next $n-1$ lines, each line contains two integers $u$ and $v$ ($1\le u, v\le n$) denoting a channel connecting room $u$ and room $v$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\times 10^5$, and the rooms and channels always form a tree.

outputFormat: For each test case, print a number denoting the smallest number of added channels, or just print $-1$.

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

庞教授和寿教授喜欢玩追逐游戏。

游戏地图由 $n$ 个房间和 $n-1$ 条双向通道组成。游戏地图是连通的。这意味着地图形成一棵树。

一开始，庞教授在房间 $u$，而寿教授在房间 $v$（$u\neq v$）。庞教授和寿教授轮流玩游戏，寿教授先开始。在自己的回合中，玩家知道自己所在的位置和另一个玩家的位置，可以决定留在当前房间或者移动到与当前房间直接通过通道相连的另一个房间。当庞教授和寿教授在同一个房间时，寿教授被庞教授抓住。

庞教授和寿教授足够聪明。庞教授希望在有限的回合内抓住寿教授。寿教授不希望在任何有限的回合内被庞教授抓住。

寿教授厌倦了每次都被抓住，找到了费教授寻求帮助。寿教授请求费教授添加一些通道，使得无论初始房间对 $(u,v)$ 如何，庞教授都无法在有限的回合内抓住他。费教授很懒，所以他希望尽可能少地添加通道。如果无论如何添加通道，总是存在一对房间 $(u,v)$，使得庞教授能够抓住寿教授，输出 $-1$。

**【输入格式】**

第一行包含一个整数 $T$ ($1\le T\le 10^4$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($2\le n\le 10^5$)，表示房间的数量。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ ($1\le u, v\le n$)，表示连接房间 $u$ 和房间 $v$ 的通道。

保证所有测试用例中 $n$ 的总和不超过 $2\times 10^5$，并且房间和通道始终构成一棵树。

对于每个测试用例，输出一个数字表示添加的通道的最小数量，或者只输出 $-1$。

**【输出格式】**

输出一行整数，表示答案。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: [EC Final 2022] Magic

description:
**Warning: Unusual memory limit!**

You are given a sequence $a_0,\ldots,a_{2n}$. Initially, all numbers are zero.

There are $n$ operations. The $i$-th operation is represented by two integers $l_i, r_i$ ($1\le l_i < r_i\le 2n, 1\le i\le n$), which assigns $i$ to $a_{l_i},\ldots,a_{r_i-1}$.  It is guaranteed that all the $2n$ integers, $l_1,l_2,\ldots, l_n, r_1, r_2, \ldots, r_n$, are distinct.

You need to perform each operation exactly once, in arbitrary order.

You want to maximize the number of $i$ $(0\leq i< 2n)$ such that $a_i\neq a_{i+1}$ after all $n$ operations. Output the maximum number.

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

The $i$-th line of the next $n$ lines contains a pair of integers $l_i, r_i$ ($1\le l_i < r_i\le 2n$). It is guaranteed that all the $2n$ integers, $l_1,l_2,\ldots, l_n, r_1, r_2, \ldots, r_n$, are distinct.

translation:
- 你有一个序列 $a_0,a_1,a_2\dots a_{2n}$，初始全为 $0$。
- 给定 $n$ 个区间赋值操作，第 $i$ 个操作 $(l_i,r_i)(1\le l_i,r_i\le 2n)$ 表示把区间 $[l_i,r_i)$ 全部赋值为 $i$，**保证所有 $l_i,r_i$ 互不相同**。
- 你可以指定一个执行操作的顺序，最大化 $\sum_{i=0}^{2n-1}[a_i\ne a_{i+1}]$，输出这个最大值。
- $1\le n\le 5\times 10^3$，**注意空间限制**。


title: [EC Final 2022] Aqre

description:
Given an $n \times m$ matrix, you need to fill it with $0$ and $1$, such that:

- There cannot be **four** consecutive horizontal or vertical cells filled with the same number.
- The cells filled with $1$ form a connected area. (Two cells are adjacent if they share an edge. A group of cells is said to be connected if for every pair of cells it is possible to find a path connecting the two cells which lies completely within the group, and which only travels from one cell to an adjacent cell in each step.)

Please construct a matrix satisfying the conditions above and has as many $1$s as possible. Output the maximum number of $1$s, and the matrix.

inputFormat:
The first line contains an integer $T~(1\leq T\leq 10^3)$ -- the number of test cases.

For each test case, the first line contains two integers $n, m~(2\leq n, m\leq 10^3)$.

### It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $10^6$.

outputFormat: For each test case, output the maximum number of $1$s in the first line. Then output the matrix in the following $n$ lines. If there are multiple solution, output any.

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

给定一个 $n \times m$ 矩阵，你需要用 $0$ 和 $1$ 填充它，使得满足以下条件：

- 不能有**四个**连续的水平或垂直单元格填有相同的数字。
- 填有 $1$ 的单元格形成一个连通区域。（如果它们共享一个边，则两个单元格是相邻的。如果对于每对单元格，可以找到一条完全位于该区域内的连接两个单元格的路径，并且每一步只能从一个单元格移动到相邻的单元格，则一组单元格被称为连通的。）

请构造一个满足上述条件且具有尽可能多的 $1$ 的矩阵。输出 $1$ 的最大数量以及该矩阵。

**【输入格式】**

第一行包含一个整数 $T~(1\leq T\leq 10^3)$，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n, m~(2\leq n, m\leq 10^3)$。

保证所有测试用例中 $n\cdot m$ 的总和不超过 $10^6$。

**【输出格式】**

对于每个测试用例，输出第一行中 $1$ 的最大数量。然后在接下来的 $n$ 行中输出矩阵。如果有多种解决方案，则输出任意一个。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: [EC Final 2022] Dining Professors

description:
Prof. Pang invited $n$ professors to his banquet. The professors sit at a round table. For all $i$ from $1$ to $n$, professor $i$ sits adjacent to professor $(i \bmod n) + 1$ and $((i + n - 2)\bmod n) + 1$.

Prof. Pang prepared $n$ dishes. There are $n$ positions on the table. Position $i$ is in front of professor $i$. Professor $i$ can access only the dishes placed at positions $i$, $(i \bmod n) + 1$, and $((i + n - 2)\bmod n) + 1$. Prof. Pang will place exactly one dish at each position.

Among the dishes, $a$ of them are spicy and $n-a$ of them are not spicy. Some (possibly $0$) professors are unable to have spicy food. If a professor can have spicy food, his/her **satisfaction level** is the number of dishes (no matter spicy or not) he/she can access. If a professor cannot have spicy food, his/her satisfaction level is the number of not spicy dishes he/she can access.

Prof. Pang knows whether each professor can have spicy food or not. Please help him to arrange the dishes on the table so that the sum of satisfaction levels over all the professors is maximized. Output the maximum sum.

inputFormat:
The first line contains two integers $n, a$ ($3\le n\le 10^5, 0\le a\le n$).

The second line contains $n$ integers $b_1, \ldots, b_n$. $b_i$ is $0$ or $1$. $b_i=1$ means professor $i$ can have spicy food. $b_i=0$ means professor $i$ cannot have spicy food.

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

庞教授邀请了 $n$ 位教授参加他的宴会。教授们坐在一个圆桌周围。对于所有 $i$，从 $1$ 到 $n$，教授 $i$ 坐在教授 $(i \bmod n) + 1$ 和 $((i + n - 2)\bmod n) + 1$ 旁边。

庞教授准备了 $n$ 道菜。桌子上有 $n$ 个位置。位置 $i$ 在教授 $i$ 的前面。教授 $i$ 只能接触到放在位置 $i$、$(i \bmod n) + 1$ 和 $((i + n - 2)\bmod n) + 1$ 处的菜。庞教授将在每个位置上放置一道菜。

在这些菜中，有 $a$ 道是辣的，$n-a$ 道是不辣的。有些（可能为 $0$）教授不能吃辣的食物。如果一位教授可以吃辣的食物，他/她的**满意度水平**是他/她可以接触到的菜的数量（无论是辣的还是不辣的）。如果一位教授不能吃辣的食物，他/她的满意度水平是他/她可以接触到的不辣的菜的数量。

庞教授知道每位教授是否可以吃辣的食物。请帮助他安排桌子上的菜，使得所有教授的满意度水平之和最大化。输出最大的总和。

**【输入格式】**

第一行包含两个整数 $n, a$ ($3\le n\le 10^5, 0\le a\le n$)。

第二行包含 $n$ 个整数 $b_1, \ldots, b_n$。$b_i$ 是 $0$ 或 $1$。$b_i=1$ 表示教授 $i$ 可以吃辣的食物。$b_i=0$ 表示教授 $i$ 不能吃辣的食物。

**【输出格式】**

输出一行一个整数，表示答案。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: [EC Final 2022] Coloring

description:
You are given $n$ elements numbered from $1$ to $n$. Element $i$ has value $w_i$ and color $c_i$. Each element also has a pointer $a_i$ to some other element.

Initially, the color of element $s$ is $1$, while the color of all the other elements is $0$. More formally, $c_s=1$ and $c_i=0$ for all $i\neq s$ $(1 \le i \le n)$.

You can perform the following operation for any number of times:

- Assign $c_i\leftarrow c_{a_i}$ at a cost of $p_i$.

Your score is equal to the sum of values of all the elements with color $1$ after the operations minus the sum of costs of the operations.

Find the maximum possible score you can obtain.

inputFormat:
The first line contains two integers $n,s$ ($1 \leq s\le n \leq 5\times 10^3$) $-$ the number of elements and the element with color $1$ initially.

The second line contains $n$ integers $w_1,w_2,\dots,w_n$ ($-10^9\le w_i\le 10^9$) $-$ the value of the elements.

The third line contains $n$ integers $p_1,p_2,\dots,p_n$ ($0\le p_i\le 10^9$) $-$ the cost of changing the color of each element.

The fourth line contains $n$ integers $a_1,a_2,\dots,a_n$ ($1\le a_i\le n$, $a_i\neq i$).

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

给定 $n$ 个元素，编号从 $1$ 到 $n$。元素 $i$ 的值为 $w_i$，颜色为 $c_i$。每个元素还有一个指针 $a_i$ 指向另一个元素。

最初，元素 $s$ 的颜色为 $1$，而所有其他元素的颜色都为 $0$。更正式地说，对于所有 $i\neq s$ $(1 \le i \le n)$，有 $c_s=1$ 和 $c_i=0$。

你可以任意多次执行以下操作：

- 以代价 $p_i$ 将 $c_i\leftarrow c_{a_i}$。

你的得分等于所有颜色为 $1$ 的元素值的总和减去操作的总代价。

找出你能够获得的最大可能得分。

**【输入格式】**

第一行包含两个整数 $n$ 和 $s$（$1 \leq s\le n \leq 5\times 10^3$）$-$ 元素数量以及初始颜色为 $1$ 的元素。

第二行包含 $n$ 个整数 $w_1,w_2,\dots,w_n$（$-10^9\le w_i\le 10^9$）$-$ 元素的值。

第三行包含 $n$ 个整数 $p_1,p_2,\dots,p_n$（$0\le p_i\le 10^9$）$-$ 改变每个元素颜色的代价。

第四行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le n$, $a_i\neq i$）。

**【输出格式】**

输出一行一个整数，表示答案。

**【样例解释】**

在第一个样例中，你可以依次执行以下操作：

- 以代价 $p_2$ 将 $c_2\leftarrow c_{a_2}$，然后 $c=[1,1,0]$；
- 以代价 $p_1$ 将 $c_1\leftarrow c_{a_1}$，然后 $c=[0,1,0]$；
- 以代价 $p_3$ 将 $c_3\leftarrow c_{a_3}$，然后 $c=[0,1,1]$；
- 以代价 $p_2$ 将 $c_2\leftarrow c_{a_2}$，然后 $c=[0,0,1]$。

操作后，只有元素 $3$ 的颜色为 $1$，因此你的得分等于 $w_3-(p_2+p_1+p_3+p_2)=1$。可以证明无法获得大于 $1$ 的得分。

翻译来自于：[ChatGPT](https://chatgpt.com/)

hint:
(There won’t be extra line breakers
in the actual test cases.)

In the first sample, you can successively perform the following operations:

- Assign $c_2\leftarrow c_{a_2}$ at a cost of $p_2$, then $c=[1,1,0]$;
- Assign $c_1\leftarrow c_{a_1}$ at a cost of $p_1$, then $c=[0,1,0]$;
- Assign $c_3\leftarrow c_{a_3}$ at a cost of $p_3$, then $c=[0,1,1]$;
- Assign $c_2\leftarrow c_{a_2}$ at a cost of $p_2$, then $c=[0,0,1]$.

After the operations, only the color of element $3$ is $1$, so your score is equal to $w_3-(p_2+p_1+p_3+p_2)=1$. It can be shown that it is impossible to obtain a score greater than $1$.


title: [EC Final 2022] Binary String

description:
You are given a binary string $a_0a_1a_2\dots a_{n-1}$ arranged on a cycle. Each second, you will change every $01$ to $10$ simultaneously. In other words, if $a_i = 0$ and $a_{(i+1) \bmod n} = 1$, you swap $a_i$ and $a_{(i+1)\bmod n}$. For example, we will change $\texttt{100101110}$ to $\texttt{001010111}$.

You need to answer how many different strings will occur in infinite seconds, modulo $998244353$.

Note: Two strings $a_0a_1\dots a_{n-1}$ and $b_0b_1\dots b_{n-1}$ are different if there exists an integer $i\in \{0,1,\ldots, n-1\}$ such that $a_i\neq b_i$. Thus, the cyclic shifts of a string may be different from the original string.

inputFormat:
The first line contains an integer $T$ $(1\leq T\leq 10^6)$ $-$ the number of test cases.

For each test case, the first line contains a binary string $a_0 a_1 \dots a_{n-1}$ $(a_i \in \{0, 1\})$.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed $10^7$.

outputFormat: For each test case, output one integer representing the answer in one line.

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

给定一个排列在环上的二进制字符串 $a_0a_1a_2\dots a_{n-1}$。每一秒钟，你会同时将每个 $01$ 变为 $10$。换句话说，如果 $a_i = 0$ 且 $a_{(i+1) \bmod n} = 1$，则交换 $a_i$ 和 $a_{(i+1)\bmod n}$。例如，我们将 $\texttt{100101110}$ 变为 $\texttt{001010111}$。

你需要回答在无限秒内会出现多少种不同的字符串，取模 $998244353$。

注意：如果存在整数 $i\in \{0,1,\ldots, n-1\}$ 使得 $a_i\neq b_i$，则两个字符串 $a_0a_1\dots a_{n-1}$ 和 $b_0b_1\dots b_{n-1}$ 是不同的。因此，字符串的循环移位可能与原始字符串不同。

**【输入格式】**

第一行包含一个整数 $T$ $(1\leq T\leq 10^6)$ $-$ 测试用例的数量。

对于每个测试用例，第一行包含一个二进制字符串 $a_0 a_1 \dots a_{n-1}$ $(a_i \in \{0, 1\})$。

保证所有测试用例中字符串长度的总和不超过 $10^7$。

**【输出格式】**

对于每个测试用例，输出一行一个整数，表示答案。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: [EC Final 2022] Best Carry Player 2

description:
Given a positive integer $x$, find the minimum positive integer $y$ such that the number of $\textbf{carries}^1$ of $x+y$ is exactly $k$.

We adds numbers $\textbf{by column addition in base-ten}$, just like what we normally do in primary school. For example, there are two carries in the following addition.

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

$^1$ which means ``进位`` in Chinese.

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

For each test case, the first line contains two integers $x, k$ $(1\leq x < 10^{18}, 0\leq k \leq 18)$.

outputFormat: For each test case, output one integer representing the answer in one line. If there is no solution, output $-1$ instead.

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

给定一个正整数 $x$，找到最小的正整数 $y$，使得 $x+y$ 的 $\textbf{进位}$ 数量恰好为 $k$。

我们按照十进制中的列加法进行相加，就像我们在小学时所做的那样。例如，下面的加法中有两次进位。

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

**【输入格式】**

第一行包含一个整数 $T$ $(1\leq T\leq 10^5)$ $-$ 测试用例的数量。

对于每个测试用例，第一行包含两个整数 $x, k$ $(1\leq x < 10^{18}, 0\leq k \leq 18)$。

**【输出格式】**

对于每个测试用例，输出一行一个整数，表示答案。如果没有解决方案，则输出 $-1$。

翻译来自于：[ChatGPT](https://chatgpt.com/)。


title: [EC Final 2022] Minimum Suffix

description:
For a string $s$ of length $n$, we define $p_j = x$ if $s[x\ldots j]$ is the minimum suffix of $s[1\ldots j]$, for all $j=1,\ldots, n$. (A suffix is the minimum suffix of a string if it is lexicographically smaller than any other suffix of that string.)

You are to recover $s$ from $p_1,\ldots, p_n$. If there are multiple answers, find the lexicographically smallest one.

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

For each test case, the first line contains a single integer $n$ ($1\le n\le 3\times 10^6$) representing the length of $s$. The next line contains $n$ integers $p_1,\ldots, p_n$ ($1\le p_i\le i$ for all $1\le i\le n$).

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

outputFormat: For each test case, output one line. If there is no solution, output $-1$. Otherwise, output the lexicographically smallest $s$. Characters of $s$ are represented by positive integers. Smaller integers represent smaller characters in the lexicographical order.

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

对于长度为 $n$ 的字符串 $s$，如果 $s[x\ldots j]$ 是 $s[1\ldots j]$ 的最小后缀，则我们定义 $p_j = x$，其中 $j=1,\ldots, n$。（后缀是字符串的最小后缀，如果它在字典序上小于该字符串的任何其他后缀。）

你需要从 $p_1,\ldots, p_n$ 中恢复出 $s$。如果存在多个答案，则找出字典序最小的那个。

**【输入格式】**

第一行包含一个整数 $T$（$1\le T\le 10^5$），表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$（$1\le n\le 3\times 10^6$），表示 $s$ 的长度。接下来的一行包含 $n$ 个整数 $p_1,\ldots, p_n$（$1\le p_i\le i$，$1\le i\le n$）。

保证所有测试用例中 $n$ 的总和不超过 $3\times 10^6$。

**【输出格式】**

对于每个测试用例，输出一行。如果没有解决方案，则输出 $-1$。否则，输出字典序最小的 $s$。$s$ 中的字符由正整数表示。较小的整数表示字典序较小的字符。

**【提示说明】**

本题输入输出规模较大，建议使用快速的输入输出方式。

翻译来自于：[ChatGPT](https://chatgpt.com/)。

hint: As the input/output can be huge, it is recommended to use fast input/output methods.


title: [EC Final 2022] Map

description:
It is a famous math fact that if you drop a map of a park completely inside the park, then there exists a point on the map which overlays with the point it represents.

Mio likes this fact a lot so she drops a map of her favorite park completely inside the park. The park $P$ can be represented by a rectangle. A map of the park is just a smaller (or equal) version of the park printed on paper. The map is similar to the original rectangle. Each point on the map corresponds to a point in the park by the similarity transformation.

We can define a map formally: A map is a rectangle $M$ (of smaller or equal size) together with a positive real number $r$ and a bijective function $f:M \rightarrow P$ satisfying

- For every pair of different points $a, b\in M$, $|f(a)-f(b)|/|a-b|=r$.

$|x-y|$ represents the Euclidean distance between points $x$ and $y$.

Like in many games, Mio can teleport using the map. Precisely, when Mio is at some point $x$ on the map (including the boundary), she may teleport to the corresponding point $f(x)$ in the park. She may also choose not to teleport. The reverse is also true. When she is at point $y$ in the park (including the boundary), she may teleport to the point $f^{-1}(y)$ on the map representing her current location. And she may also choose not to teleport.

Mio can teleport at most $n$ (and at least $0$) times. Each teleport takes $k$ seconds. Mio can also walk on her foot at a speed of $1$ unit per second.

Given two points $s$ and $t$, find the minimum time Mio needs to reach $t$ from $s$.

Each teleport can be in any direction (from the map to the park, or from the park to the map). The map may be placed upside down. Since the map is inside the park, it is possible that Mio is on the map and in the park simultaneously. In this case, she may teleport in either direction.

For example, in the following figure, the park is $ABCD$, and the map is $A'B'C'D'$. When Mio is inside the map, she is on the map and in the park simultaneously. When she is at point $D'$, she can teleport from the map to the park (reaching $D$), and from the park to the map (reaching $D^{\prime\prime}$).

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

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

For each test case, the first line contains the $4$ corners of the rectangle representing the park. The corners are given in clockwise or counterclockwise order. It is guaranteed that the $4$ corners are distinct.

The second line contains the $4$ corners of the rectangle representing the map. The $i$-th corner of the map corresponds to the $i$-th corner of the park for all $1\le i\le 4$. Note that you can figure out whether the map is placed upside down or not by the order of the corners. The corners are given in clockwise or counterclockwise order. It is guaranteed that the map is inside the park. (The boundary of the map may intersect with the boundary of the park at $1$ or more points.) It is guaranteed that the map is valid, i.e., there is a positive real number and a bijective function from the map to the park satisfying the definition above.

The third line contains two points $s$ and $t$. It is guaranteed that $s$ and $t$ are inside (or on the boundary of) the park.

The fourth line contains two integers $k, n$ ($0\le k\le 2\times 10^6, 0\le n\le 100$), the time each teleport needs, and the maximum number of teleports.

Each point in the input is represented by a pair of integers whose absolute values are no more than $2\times 10^6$. Integers are separated by single spaces.

outputFormat: For each test case, output one number representing the answer in one line. Your answer is considered correct if its absolute or relative error does not exceed $10^{-9}$.

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

有一个著名的数学定理，如果你把一张公园的地图完全放在公园里，那么地图上存在一个点与它所代表的点重合。

Mio 非常喜欢这个定理，所以她把她最喜欢的公园的地图完全放在了公园里。公园 $P$ 可以用一个矩形表示。公园的地图只是一个较小（或相等）版本的公园在纸上的打印。地图与原始矩形相似。地图上的每个点都通过相似变换对应于公园中的一个点。

我们可以正式定义地图：地图是一个矩形 $M$（大小较小或相等），加上一个正实数 $r$ 和一个双射函数 $f:M \rightarrow P$，满足以下条件：

- 对于 $M$ 中的每对不同的点 $a, b$，$|f(a)-f(b)|/|a-b|=r$。

这里 $|x-y|$ 表示点 $x$ 和点 $y$ 之间的欧几里德距离。

就像许多游戏一样，Mio 可以使用地图进行传送。准确地说，当 Mio 在地图上的某个点 $x$（包括边界）时，她可以传送到公园中相应的点 $f(x)$。她也可以选择不传送。反之亦然。当她在公园中的点 $y$（包括边界）时，她可以传送到代表她当前位置的地图上的点 $f^{-1}(y)$。她也可以选择不传送。

Mio 最多可以传送 $n$ 次（最少为 $0$ 次）。每次传送需要 $k$ 秒。Mio 还可以以每秒 $1$ 个单位的速度步行。

给定两个点 $s$ 和 $t$，找出 Mio 从 $s$ 到 $t$ 需要的最短时间。

每次传送可以是任意方向（从地图到公园，或从公园到地图）。地图可以倒置放置。由于地图位于公园内部，所以 Mio 可能同时在地图上和在公园中。在这种情况下，她可以选择传送的方向。

例如，在下图中，公园是 $ABCD$，地图是 $A'B'C'D'$。当 Mio 在地图上时，她同时在地图上和在公园中。当她在点 $D'$ 时，她可以从地图传送到公园（到达 $D$），并从公园传送到地图（到达 $D^{\prime\prime}$）。

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

**【输入格式】**

第一行包含一个整数 $T$（$1\le T\le 100$），表示测试用例的数量。

对于每个测试用例，第一行包含表示公园矩形的 $4$ 个角点。角点按顺时针或逆时针顺序给出。保证 $4$ 个角点不相同。

第二行包含表示地图矩形的 $4$ 个角点。地图的第 $i$ 个角点对应于公园的第 $i$ 个角点，对于所有 $1\le i\le 4$。请注意，您可以通过角点的顺序确定地图是否倒置放置。角点按顺时针或逆时针顺序给出。保证地图位于公园内部。（地图的边界可能与公园的边界在 $1$ 个或多个点相交。）保证地图是有效的，即存在一个正实数和一个从地图到公园的双射函数，满足上述的定义。

第三行包含两个点 $s$ 和 $t$。保证 $s$ 和 $t$ 在公园内部（或在公园的边界上）。

第四行包含两个整数 $k, n$（$0\le k\le 2\times 10^6, 0\le n\le 100$），表示每次传送所需的时间，以及最大传送次数。

输入中的每个点由一对整数表示，其绝对值不超过 $2\times 10^6$。整数之间用单个空格分隔。

**【输出格式】**

对于每个测试用例，输出一行数字表示答案。如果没有解决方案，则输出 $-1$。否则，输出最小的时间。您的答案被认为是正确的，如果其绝对或相对误差不超过 $10^{-9}$。

翻译来自于：[ChatGPT](https://chatgpt.com/)。


title: [EC Final 2022] Inversion

description:
$\textbf{This is an interactive problem.}$

There is a hidden permutation $p_1, p_2, \dots, p_n$ of $\{1, 2, \dots, n\}$. You want to find it by asking the parity of the number of inversions of $p_l,\ldots, p_r$.

You can query in the format ${?~l~r}$, and the interactor will respond you $\left( \sum_{l\leq i < j\leq r} [p_i > p_j]\right) \bmod 2$. $[p_i>p_j]$ is $1$ when $p_i>p_j$ and $0$ when $p_i\le p_j$.

inputFormat:
Firstly, you should read the integer $n$ ($1\le n\le 2000$).

After that, you can make no more than $4 \times 10^4$ queries. To make a query, output ``${?~l~r}$'' ($1 \leq l \leq r \leq n$) on a separate line, then you should read the response from standard input.

To give your answer, print ``${!~p_1~p_2~\dots~p_n}$'' on a separate line. The output of the answer is \textbf{not} counted towards the limit of $4 \times 10^4$ queries.

After that, your program should terminate.

After printing a query, do not forget to output end of line and flush the output. To do this, use $\texttt{fflush(stdout)}$ or $\texttt{cout.flush()}$ in C++, $\texttt{System.out.flush()}$ in Java, $\texttt{flush(output)}$ in Pascal, or $\texttt{stdout.flush()}$ in Python.

It is guaranteed that the permutation is fixed in advance.

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

这是一个交互式问题。

有一个隐藏的排列 $p_1, p_2, \dots, p_n$，其中包含 $\{1, 2, \dots, n\}$ 的排列。你想通过询问 $p_l,\ldots, p_r$ 的逆序对数量的奇偶性来找到它。

你可以以 ${?~l~r}$ 的格式进行查询，交互器会回答你 $\left( \sum_{l\leq i < j\leq r} [p_i > p_j]\right) \bmod 2$。其中 $[p_i>p_j]$ 在 $p_i>p_j$ 时为 $1$，在 $p_i\le p_j$ 时为 $0$。

首先，你需要读入整数 $n$（$1\le n\le 2000$）。

之后，你可以进行不超过 $4 \times 10^4$ 次查询。要进行查询，输出 ${?~l~r}$（$1 \leq l \leq r \leq n$）在单独的一行上，然后你应该从标准输入中读取响应。

要给出你的答案，将 ${!~p_1~p_2~\dots~p_n}$ 打印在单独的一行上。答案的输出 $\textbf{不}$ 计入 $4 \times 10^4$ 次查询的限制。

之后，你的程序应该终止。

在打印查询后，不要忘记输出换行并刷新输出。要做到这一点，在 C++ 中使用 $\texttt{fflush(stdout)}$ 或 $\texttt{cout.flush()}$，在 Java 中使用 $\texttt{System.out.flush()}$，在 Pascal 中使用 $\texttt{flush(output)}$，或者在 Python 中使用 $\texttt{stdout.flush()}$。

保证排列提前固定。

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: [EC Final 2022] Rectangle

description:
Prof. Pang has $n$ rectangles, the coordinate of the lower left corner of the $i$-th rectangle is $(x_{i,1}, y_{i,1})$, and the coordinate of the upper right corner is $(x_{i,2}, y_{i,2})$. Rectangles may overlap.

You need to choose three straight lines such that:

- Each line should be parallel to the $x$-axis or the $y$-axis, which means its formula is $x = a$ or $y = a$.
- In the formula $x = a$ or $y = a$, $a$ should be an integer in $[1, 10^9]$.
- These three lines should be distinct.
- Each rectangle is $\textbf{touched}$ by at least one line. A line touches a rectangle if it intersects with the boundary and/or the interior of the rectangle.

You need to compute the number of ways to choose three lines. Since the answer can be very large, output it modulo $998244353$. Two ways are considered the same if only the order of three lines differs in these two ways.

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

For each test case, the first line contains an integer $n~(1 \le n \le 10^5)$. The $i$-th line of the next $n$ lines contains four integers $x_{i,1}, y_{i,1},x_{i,2}, y_{i,2}~(1\le x_{i,1}<x_{i,2}\le 10^9,1\le y_{i,1}<y_{i,2}\le 10^9)$.

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

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

庞教授有 $n$ 个矩形，第 $i$ 个矩形的左下角坐标是 $(x_{i,1}, y_{i,1})$，右上角坐标是 $(x_{i,2}, y_{i,2})$。矩形可以重叠。

你需要选择三条直线，使得：

- 每条直线应该与 $x$ 轴或 $y$ 轴平行，即其方程为 $x = a$ 或 $y = a$。
- 在方程 $x = a$ 或 $y = a$ 中，$a$ 应该是 $[1, 10^9]$ 区间内的整数。
- 这三条直线应该是不同的。
- 每个矩形至少被一条直线 $\textbf{触摸}$。如果一条直线与矩形的边界和/或内部相交，则称该直线触摸该矩形。

你需要计算选择三条直线的方法数。由于答案可能非常大，输出对 $998244353$ 取模的结果。如果两种方法只有三条直线的顺序不同，则认为它们是相同的。

**【输入格式】**

第一行包含一个整数 $T~(1 \le T \le 10^5)$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n~(1 \le n \le 10^5)$。接下来的 $n$ 行中，第 $i$ 行包含四个整数 $x_{i,1}, y_{i,1},x_{i,2}, y_{i,2}~(1\le x_{i,1}<x_{i,2}\le 10^9,1\le y_{i,1}<y_{i,2}\le 10^9)$。

保证所有测试用例中 $n$ 的总和不超过 $2\times 10^5$。

**【输出格式】**

对于每个测试用例，输出一行整数，表示答案。

**【样例解释】**

翻译来自于：[ChatGPT](https://chatgpt.com/)


title: [ICPC2022 Jinan R]  Skills

description:
Prof. Pang has $3$ different skills to practice, including soda drinking, fox hunting, and stock investing. We call them Skill $1$, Skill $2$, and Skill $3$. In each of the following $n$ days, Prof. Pang can choose one of the three skills to practice. In the $i$-th day ($1\le i\le n$), if Prof. Pang chooses Skill $j$ ($1\le j\le 3$) to practice, his level of Skill $j$ will increase by $a_{i,j}$. Initially, Prof. Pang's levels of all skills are $0$.

Prof. Pang forgets skills if he does not practice. At the end of each day, if he has not practiced Skill $j$ for $k$ days, his level of Skill $j$ will decrease by $k$. For example, if he practices Skill $1$ on day $1$ and Skill $2$ on day $2$, at the end of day $2$, he has not practiced Skill $1$ for $1$ day and has not practiced Skill $3$ for $2$ days. Then his levels of Skill $1$ and Skill $3$ will decrease by $1$ and $2$, respectively. His level of Skill $2$ does not decrease at the end of day $2$ because he practices Skill $2$ on that day. In this example, we also know that his levels of Skill $2$ and Skill $3$ both decrease by $1$ at the end of day $1$.

Prof. Pang's level of any skill will not decrease below $0$. For example, if his level of some skill is $3$ and at the end of some day, this level is decreased by $4$, it will become $0$ instead of $-1$.

Prof. Pang values all skills equally. Thus, he wants to maximize the sum of his three skill levels after the end of day $n$.

Given $a_{i,j}$ ($1\le i\le n, 1\le j\le 3$), find the maximum sum.

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

For each test case, the first line contains an integer $n~(1 \le n \le 1000)$. The $(i+1)$-th line contains three integers $a_{i,1}, a_{i,2}, a_{i,3}$ ($0\le a_{i,j}\le 10000$ for any $1\le i\le n, 1\le j\le 3$).

It is guaranteed that the sum of $n$ over all test cases is no more than $1000$.

outputFormat: For each test case, output the maximum possible sum of skill levels in one line.

translation:
#### 题目描述。
庞博士有 $3$ 项技能：喝汽水、猎狐和炒股，编号分别为 $1,2,3$。初始时，每项技能的熟练度为 $0$。

接下来有 $n$ 天。在第 $i$ 天，庞博士可以选择一项技能（假设是第 $j$ 项）进行练习，然后在这天结束时让这项技能的熟练度增加 $a_{i,j}$。同时，如果某一项技能（假设是第 $k$ 项）已经有 $x$ 天没有练习，那么在这天结束时，这项技能的熟练度会减少 $x$。当然，任何一项技能的熟练度都不可能小于 $0$。

现在，庞博士想知道：在第 $n$ 天结束后，这 $3$ 项技能的熟练度之和最大为多少。由于他非常忙，而且他的日程和对习惯的适应程度可能有变，所以庞博士把这 $T$ 个问题交给了你——每个问题的内容都一样，只是给出的数据可能有所不同而已。
#### 输入格式
第一行，一个正整数 $T~(1 \leq T \leq 1000)$，表示数据组数。

对于每组数据，输入 $(n + 1)$ 行。

* 第一行，一个正整数 $n~(1 \leq n \leq 1000)$，表示天数。

* 接下来 $n$ 行，每行 $3$ 个非负整数，表示题目描述中的 $a_{i,j}~(1 \leq i \leq n,1 \leq j \leq 3,0 \leq a_{i,j} \leq 10000)$。
#### 输出格式
对于每组数据，输出 $1$ 行 $1$ 个数，表示答案。


title: [ICPC2022 Jinan R] Stack Sort

description:
You are given a permutation with $n$ numbers, $a_1, a_2, \dots, a_n (1\leq a_i\leq n, a_i\neq a_j\textrm{ when }i\neq j)$.

You want to sort these numbers using $m$ stacks. Specifically, you should complete the following task:

Initially, all stacks are empty. You need to push each number $a_i$ to the top of one of the $m$ stacks one by one, in the order of $a_1,a_2,\ldots, a_n$. $\textbf{After pushing all numbers in the stacks}$, you pop all the elements from the stacks in a clever order so that the first number you pop is $1$, the second number you pop is $2$, and so on. **If you pop an element from a stack $S$, you cannot pop any element from the other stacks until $S$ becomes empty.**

What is the minimum possible $m$ to complete the task?

inputFormat:
The first line contains one integer $T~(1\le T \le 10^5)$, the number of test cases.

For each test case, the first line contains one positive 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)$ denoting the permutation. It is guaranteed that $a_1,\ldots, a_n$ form a permutation, i.e. $a_i\neq a_j$ for $i \neq j$.

It is guaranteed that the sum of $n$ over all test cases is no more than $5\times 10^5$.

outputFormat: For each test case, output the minimum possible $m$ in one line.

translation:
你有一个 $n$ 项的数组 $a$ 和 $m$ 个栈，满足：
- $1\leq a_i\le n$，每一项各不相同。
- 对于 $i=1,2...n$，使 $a_i$ 成为任意一个栈的栈顶。
- 在每一项入栈后有一种方法使得 $1,2...,n$ 可以按照递增顺序依次出栈。

求 $m$ 的最小值。


title: [ICPC2022 Jinan R] Tree Distance

description:
You are given an unrooted weighted tree $T$ with vertices $1, 2, \ldots, n$. Please answer some queries.

We define $\texttt{dist}(i,j)$ as the distance between vertex $i$ and vertex $j$ in $T$.

For each query, you are given two integers $l, r$. Please answer the value of

$$\min_{l\le i< j\le r}(\texttt{dist}(i,j)).$$

inputFormat:
The first line contains one integer $n~(1\leq n\le 2 \times 10^5)$, the number of vertices in the tree.

Each of the next $n-1$ lines describes an edge of the tree. Edge $i$ is denoted by three integers $a_i, b_i, w_i$ $(1\le a_i, b_i\le n, 1\le w_i\le 10^9)$, the labels of vertices it connects and its weight.

Then one line contains one integer $q~(1\leq q\le 10^6)$, the number of queries.

Each of the following $q$ lines contains two integers $l, r~(1\le l \le r\le n)$ describing a query.

It is guaranteed that the given edges form a tree.

outputFormat: For each query, output the answer in one line. If there is no $i,j$ such that $l\le i<j\le r$, the answer is $-1$.

translation:
给你一棵 $n$ 个点的树。记 $\operatorname{dist}(i,j)$ 为树上 $i,j$ 之间唯一简单路径的长度。

你要回答 $q$ 次询问：给定 $l,r$，求 $\min\limits_{l\leq i<j\leq r}(\operatorname{dist}(i,j))$。


title: [ICPC2022 Jinan R] Best Carry Player

description:
Prof. Pang is given $n$ numbers $a_1,\ldots, a_n$. It is easy to add the numbers up using a computer. But Prof. Pang treasures his computer so much and wants to reduce its workload. He decides to simulate the following program by hand.

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

Unlike a computer, the time needed for Prof. Pang to simulate the program is proportional to the total number of **carries**(which means “进位” in Chinese) when calculating $s+a[i]$ for each $i$ from $1$ to $n$. Prof. Pang adds numbers **by column addition in base-ten**, just like what we normally do in primary school. For example, there are two carries in the following addition.

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

Please permute the array $a_1,\ldots, a_n$ so that the total number of carries when Prof. Pang simulates the program is as small as possible. (By ''permute an array'', we mean that you can change the order of the elements arbitrarily.)

inputFormat:
The first line contains one integer $T~(1\le T \le 10^5)$, the number of test cases.

For each test case, the first line contains one positive integer $n~(1\le n \le 10^5)$. The next line contains $n$ integers $a_1,\ldots, a_n~(1 \le a_i\le 10^9)$ denoting the numbers Prof. Pang is given.

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

outputFormat: For each test case, output one line containing the minimum amount of carries.

translation:
### 简要题面

这里我们定义一个电脑运行 $a+b$ 的速度是 $a+b$ 中出现的进位的次数。

给定一个数组 $a_1,a_2,...,a_n$，请找出正确的排序使得计算这个数组的和时运行的速度最短，请找出最少的进位次数。

### 输入格式

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

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

对于每组数据：

第一行一个整数 $n$。

接下来一行 $n$ 个整数，表示输入的数组 $a$。

### 输出格式

对于每组数据，输出最小的进位次数。

### 数据范围

对于 $100 \%$ 的数据： $1 \leq \sum n \leq 10^5$， $1 \leq a_i \leq 10^9$


title: AGC022F Checkers 故事2

background:
>『长存不灭的过去，逐渐消逝的未来』
>
>以某种事物作为代价，以某种代价作为契机……？
>
>"I'm not crazy, my reality is just different to yours."
>
>黄沙卷狂风，庭迹一如故。

description:
令 $x=40^{76^{93}}$，平面上有 $n$ 个点，第 $i$ 个点的坐标为 $(x^i,0)$。

进行 $m$ 次操作，每次操作选择两点 $A$ 和 $B$，将 $A$ 绕 $B$ 顺时针旋转 $60°$ 并删去 $B$。

求最后剩下的所有点的重心有多少种可能的位置，对 $998244353$  取模。

$2 \le n\le 407693$，$1\le m\le n-1$。

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

outputFormat: 一行，为答案在模 $998244353$ 意义下的结果。

hint: 本题只有一个 Subtask，只有通过了全部数据点才能得分。


title: [COCI2022-2023#2] Tramvaji

description:
Patrik 和 Josip 在坐电车。他们共坐了 $n$ 站。

除了上车的那一站，其他每一站到站时，都会发生以下事件中的一种：

- Patrik 说：从上车到现在经过了 $t$ 分钟。

- Josip 说：从第 $y$ 站到这里花费了 $t$ 分钟。

现在，请你根据这些信息，求出哪两个站之间所需要的时间最短，以及这个时间。

inputFormat:
输入共 $n$ 行：

第一行，一个整数 $n$（$2\le n\le1000$），表示车站数量。

接下来 $n-1$ 行，第 $i$ 行表示第 $i+1$ 个车站发生的事件：

- 第一种操作：$\texttt{Patrik } t_i$（$1\le t_i\le10^9$）

- 第二种操作：$\texttt{Josip } y_i\texttt{ }t_i$（$y_i < i + 1$，$1\le t_i\le10^9$）

**每个车站都处在不同的位置。**

outputFormat:
一行，三个整数 $t$，$x_1$，$x_2$，表示最短时间，以及花费最短时间的起点和终点。

**如果有多组解，输出字典序最小的那一组。**

samples:
5
Patrik 4
Josip 2 4
Josip 2 6
Josip 4 2


title: [COCI2022-2023#2] Ekspert

description:
给定四个变量 $\texttt{A}$，$\texttt{B}$，$\texttt{C}$，$\texttt{D}$，初始值为 $x$，$y$，$0$，$1$。

你可以对它们进行如下操作：

选择两个变量，将他们相加的和存储在一个变量中。

请你使用该种操作不超过 $100$ 次，使任意一个变量的值等于 $x\times y$。

inputFormat: 一行，两个整数 $x$，$y$（$1\le x\times y\le10^{18}$），含义如题目所述。

outputFormat:
第一行，数出一个正整数 $n$（$0\le n\le100$），表示操作次数。

接下来 $n$ 行，第 $i$ 行记录第 $i$ 次操作，形如 $\texttt{R1 R2 R3}$，表示将 $\texttt{R1}$ 和 $\texttt{R2}$ 的和存储在 $\texttt{R3}$ 中。


title: 『SpOI - R1』Double Champions

description:
**本题包含多组数据。**

现在有若干个格子排在一行上。

再给出 $n$ 个区间，每个区间 $i$ 可以覆盖 $[l_i,r_i]$ 这个区间中的每一个格子（例如，区间 $[1,2]$ 可以覆盖格子 $1,2$）。

现在需要把这些区间分组，每个组带来的贡献为所有其旗下的区间的交的总长度。

你需要求出最少把这些区间分成多少组，才能使得每一组的贡献都 $\geq w$。如果不存在任何方案满足条件，输出 `No`。

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

对于每组数据，第一行两个整数 $n,w$。

接下来 $n$ 行，每一行两个整数 $l_i,r_i$，描述一个区间。

outputFormat: 对于每组数据，输出一行一个答案，表示最少要分的组数，或者字符串 `No`，表示无解。


title: 『SpOI - R1』强大到让你们所有人注视

description:
**本题包含多组测试。**

给定一个 $n$ 位的 $k$ 进制大数。

令 $S(l,r)$ 表示截取这个 $k$ 进制大数从高到低第 $l$ 位至第 $r$ 位构成的新 $k$ 进制数。

你需要求出 $\sum\limits_{1\leq l\leq r\leq n} S(l,r)$，注意这里的求和也建立在 $k$ 进制下。

由于答案可能很大，设 $(20070720)_{10}$ 在 $k$ 进制下是 $x$，你只需要输出答案对 $x$ 取模的结果。

**再次提醒：以上所有求和、运算和取值都建立在 $k$ 进制下。**

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

每组数据第一行两个正整数 $n,k$，表示这个大数。

每组数据第二行一个数列 $a$，从高位至低位依次表示这个大 $k$ 进制数的每一位上的数。保证 $\forall i\in[1,n],0\leq a_i<k$。

outputFormat:
每组数据一行，表示答案对 $x$ 取模的结果。由于这也是一个 $k$ 进制数，所以用空格隔开依次输出每一位。

**注意你的输出中不应含有前导零。**


title: [COCI2022-2023#2] Lampice

description:
Teo 的阳台是一个长 $n+1$，宽 $m+1$ 的矩形平台，上有 $2k$ 盏彩灯，这些彩灯的颜色用 $1 \sim k$ 之间的一个数字来表示。每种颜色的彩灯都有 $2$ 盏，它们的坐标都为正整数。

Teo 认为阳台上一个区域是好的，当且仅当：

- 这个小区域是矩形，且边都与阳台的边平行。

- 对于每一种颜色的 $2$ 盏彩灯，要么都在小区域内，要么都在小区域外。

- 小区域的左上角，右下角坐标均为整数。

- 小区域的长宽都**至少**为 $2$。

现在，Teo 想请你求出在他的阳台上，有多少个小区域是好的。

**注意：左下角坐标为 $(0,0)$，右上角坐标为 $(n,m)$。**

inputFormat:
第一行，三个整数 $n$，$m$，$k$（$1\le n\le150,1\le m\le1000,0\le k\le200000$），表示阳台的长，宽，和彩灯的颜色数。

接下来 $k$ 行，每行 $4$ 个整数 $x_1$，$y_1$，$x_2$，$y_2$，第 $i$ 行表示颜色为 $i$ 的两盏彩灯的坐标。

outputFormat: 一行，一个整数，表示好的小区域个数。


title: [COCI2022-2023#2] Prijateljice

description:
Leona 和 Zoe 拿到了一些单词。他们打算用这些单词玩一个游戏：

在每一个回合中，两人轮流说单词。这个单词需要满足以下要求：

它比前一个单词的字典序大，且开头字母必须和前一个字母相同，或在字母表上正好在前一个单词的开头字母的后面一个。

Leona 先说，他会选择字典序最小的单词说出来。轮到谁时，他说不出单词了，他就输了。

两人在玩这个游戏时，都会采用最优策略，也就是说，选择符合条件的单词中字典序最小的那个。

现在他们想知道，谁会赢呢。

inputFormat:
第一行，两个整数 $n$，$m$（$1 \le n,m \le 10^5$）。

接下来 $n$ 行，每行一个字符串，表示 Leona 拥有的单词。

接下来 $m$ 行，每行一个字符串，表示 Zoe 拥有的单词。

输入的单词均为小写字母，且互不相同。它们的总长度不超过 $10^6$，且按字典序排序。

outputFormat: 输出一行，一个字符串，为 $\texttt{Leona}$ 或 $\texttt{Zoe}$，表示获胜者。

samples:
3 3
ananas
atlas
banana
albatros
cikla
nogomet


title: 『STA - R4』冰红茶

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

某编程网站 BTC 长期在它的 Beginner Contest 的最后一题放科技模板题，于是 APJifengc 愤怒地在它的评测机上洒了若干瓶冰红茶，导致一些评测单元的运行速度快了 $10^{12}$ 倍，暴力跑得和正解一样快。

因为 BTC 不能出科技模板题了，所以 BTC 的站长想要让你维护一下 APJifengc 每次洒冰红茶后可用的评测单元个数，以便于统筹评测资源与灾后重建。

**已加入 Hack 数据，位于 Subtask 5，不计分。**

description:
有 $n$ 个 bot 排成一排，每天所有 bot 都会喝冰红茶。

要求动态维护一排 bot，有三种操作或询问：
- `1 l r k`，表示 $[l,r]$ 内的 bot 会喝 $k$ 瓶原味冰红茶、$[l,r]$ 外的 bot 会喝 $k$ 瓶热带风味冰红茶。
- `2 l r k`，表示 BTC 站长愤怒地把 $[l,r]$ 中最后连续喝了至少 $k$ 瓶口味相同的冰红茶的 bot 击毁。
- `3`，查询有多少个存活的 bot。

注：在 2 操作中，击毁不会改变 bot 的编号。

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

后 $q$ 行，每行描述一个操作或询问，形如以下三种中的一种：
- `1 l r k`；
- `2 l r k`；
- `3`。

outputFormat: 若干行，每行回答一个询问 3。

hint:
### 样例 1 解释

只说明操作 1 和操作 2。

第一次操作，三号和四号 bot 喝了 8 瓶原味冰红茶，其他 bot 喝了 8 瓶热带风味冰红茶。

第二次操作，三号和四号 bot 连续喝了 8 瓶原味冰红茶，被击毁，现在场上还有 3 个存活 bot。

第三次操作，二号 bot 喝了 3 瓶原味冰红茶，其他 bot 喝了 3 瓶热带风味冰红茶。

第四次操作，一号和五号 bot 连续喝了 11 瓶热带风味冰红茶，被击毁，现在场上还有 1 个存活 bot。

第五次操作，二号 bot 喝了 3 瓶原味冰红茶。

第六次操作，二号 bot 连续喝了 6 瓶原味冰红茶，被击毁，现在场上没有存活的 bot。

### 数据范围

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

- Subtask 1 (5pts)：$n,q\le 10^3$。
- Subtask 2 (20pts)：所有操作 2 中 $k\le 20$。
- Subtask 3 (25pts)：保证数据随机生成。
- Subtask 4 (50pts)：无特殊限制。

其中 Subtask 3 的测试数据生成方式如下：

1. 对于每次或询问，从三种类型中等概率选择一个；
2. 若选取的操作不为 3，那么从 $\left[1, n\right]$ 中等概率生成两个数 $l, r$，若 $l > r$，则交换 $l, r$，并将 $l, r$ 作为操作的参数；
3. 若选取的操作不为 3，那么从 $\left[1, 10^6\right]$ 中等概率生成一个数 $k$ 作为操作的参数。

对于全部数据，保证 $1\le n,q\le 2\times 10^5$，$1\le k\le 10^{6}$。


title: [JRKSJ R8] +1-1

description:
给你 $n$ 个点 $m$ 条边的无向图，每个结点上有一个字符 `(` 或者 `)`。

有 $q$ 次查询，每次查询给出 $x,y$，你需要判断是否存在一条从 $x$ 到 $y$ 的路径（不需要保证是简单路径）满足将路径上的点上的字符顺次写下来得到的字符串是合法括号串。

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

第二行一个只包含 `(` 和 `)` 的长度为 $n$ 的字符串表示结点 $1\dots n$ 上的字符。

下面 $m$ 行，每行两个整数 $u,v$ 表示图上的一条边。

下面 $q$ 行，每行两个整数 $x,y$。

outputFormat: 一个长度为 $q$ 的 01 串，第 $i$ 个字符表示第 $i$ 次询问的答案，1 表示存在这样的路径，0 表示不存在这样的路径。

hint:
合法括号串的定义：

* 空字符串是合法括号串
* 若 $A,B$ 是合法括号串，则 $AB$ 是合法括号串
* 若 $A$ 是合法括号串，则 $(A)$ 是合法括号串
* 除此之外的其他字符串均不是合法括号串

如 `()`、`(()())` 是合法括号串，`(()`、`())(` 不是合法括号串。

### 样例解释

**为了方便观察，输入的边和询问之间有一个换行。但数据中并不存在这个换行。**

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

其中 $1,2,3$ 号点的字符是 `(`，$4,5$ 号点的字符是 `)`。

$1\to 2$：显然，合法括号串不可能以 `(` 结尾。\
$3\to 4$：路径 $3\to 4$ 表示的字符串是 `()`。\
$1\to 4$：路径 $1\to 3\to 2\to 4\to 5\to 4$ 表示的字符串是 `((()))`。\
$1\to 5$：路径 $1\to 2\to 4\to 5$ 表示的字符串是 `(())`。\
$2\to 5$：路径 $2\to 3\to 4\to 5$ 表示的字符串是 `(())`。

### 数据规模与约定

本题采用捆绑测试。

- Subtask 1（20 pts）：$n,q\leq 500$，$m \leq 800$；
- Subtask 2（30 pts）：图是森林；
- Subtask 3（20 pts）：$q\le 10$；
- Subtask 4（30 pts）：无特殊限制。

对于所有数据，满足 $1\le n,q\le 5\times 10^5$，$0\le m\le \min(\frac{n\times(n-1)}{2},5\times 10^5)$，$1\le u,v,x,y\le n$，保证给出的图无重边、无自环。


title: [HUSTFC 2023] 简单的加法乘法计算题

description:
JokerShaco 有一个数字 $x$，最开始 $x=0$，他想要把 $x$ 变成 $y$。为了达到这个目标，他可以利用两个集合 $A$ 和 $B$。其中集合 $A$ 包含 $n$ 个元素，分别是从 $1$ 到 $n$ 的所有正整数；集合 $B$ 包含 $m$ 个元素。每次它可以对 $x$ 进行如下任意次操作：
- 选择 $A$ 中的一个元素 $a$，令 $x$ 加上 $a$。
- 选择 $B$ 中的一个元素 $b$，令 $x$ 乘以 $b$。

已知 $y$，$n$，$m$ 和 $B$ 中 $m$ 个元素的具体值，JokerShaco 想知道让 $x$ 变成 $y$ 的最少操作次数。

inputFormat:
第一行包含三个整数 $y\ (1\le y\le 5\cdot 10^6)$，$n\ (1\le n\le 5\cdot 10^6)$ 和 $m\ (1\le m\le 10)$，其含义如题目所述。

第二行包含 $m$ 个正整数，其中第 $i$ 个表示 $B$ 中的第 $i$ 个元素 $b_i\ (1\le b_i\le 5\cdot 10^6)$。

outputFormat: 输出一个整数，表示让 $x$ 变成 $y$ 的最少操作次数。在题目条件下可知一定能将 $x$ 变成 $y$。


title: [HUSTFC 2023] A+B problem

description:
Walk Alone 是一个字符串大师，在他的眼中每个字符串都表示一个 $26$ 进制的数，具体地说，按照字母表顺序从 $A$ 到 $Z$ 分别对应着十进制下 $0$ 到 $25$，那么 $BA$ 对应十进制下 $26\ (1\times 26+0)$，$BB$ 对应十进制下 $27\ (1\times 26+1)$，以此类推。

Walk Alone 想考考已经习惯了十进制加法的你，给你两个字符串 $s$ 和 $t$，请你计算出他们所表示的 $26$ 进制数的和，即 $s+t$，并同样以字符串形式告诉他，例如 $A+A=A$，$B+C=D$。为了简化问题，$s$ 和 $t$ 分别只包含一个大写字母，但请注意，答案不一定只包含一个大写字母。

inputFormat: 一行用空格分隔的两个大写字母，分别表示 $s$ 和 $t$。

outputFormat: 输出一行只包含大写字母的字符串，表示 $s+t$。输出的答案不包含前导 $0$，即类似 $AA$、$AB$ 的输出都是不合法的。

samples:
A A
A

samples:
B C
D

samples:
Z B
BA


title: [HUSTFC 2023] Azur Lane

description:
你是港区的一位指挥官，你可以通过培养指挥喵来增强舰队的实力，指挥喵由对应的喵箱培育。喵箱有 $k$ 个等级，等级越高稀有度越高。你每天会获得若干个喵箱（至少一个），然后再使用 ''一键放入'' 将这些喵箱放到喵窝里进行培育。''一键放入'' 会优先放入稀有度更高的喵箱（即按照稀有度从高到低排序后依次放入），放入的喵箱会排在已放入喵箱的后面，在**每天结束时**系统会自动扣除与喵窝中喵箱数量相等的钱。最开始时你的喵窝里没有喵箱。

因为你非常懒，所以你会等 $n$ 天后才把喵箱一起打开。在你 $n$ 天后进入喵窝时，你看到了 $m$ 个喵箱，用一个长度为 $m$ 的序列 $a$ 表示喵窝里按放入先后顺序排列的喵箱的等级。但是你已经忘了这 $n$ 天里你每天获得了多少喵箱了，你甚至忘了 $n$ 的值是多少，显然这有许多情况。你想知道，对于满足 $1 \leq n \leq m$ 的所有整数 $n$，在所有情况中，这 $n$ 天总共扣除的钱数至少为多少？

inputFormat:
第一行包含两个整数 $m\ (1 \leq m \leq 10^6)$，$k\ (1 \leq k \leq 10^6)$，分别表示喵窝中喵箱的数量和喵箱的最高等级。

第二行包含 $m$ 个整数 $a_{1}, a_{2}, \ldots, a_{m}\ (1 \leq a_i \leq k)$，表示喵窝中排列着的喵箱的等级。

outputFormat: 输出一行用空格间隔的 $m$ 个整数，其中第 $i$ 个整数表示当 $n=i$ 时在所有可能的情况下至少会扣除的钱数。如果没有合法的情况，请输出 $-1$。

hint:
样例一解释：

当 $n=1$ 时，无法在一天内获得这 $3$ 个喵箱（第二个喵箱的等级大于第一个喵箱的等级，不符合 ``一键放入'' 从高到低放入的原则），因此输出 $-1$。

当 $n=2$ 时，第一天获得第一个喵箱，此时喵窝内有 $1$ 个喵箱，当天花费为 $1$；第二天获得后两个喵箱，此时喵窝内有 $3$ 个喵箱，当天花费为 $3$。因此总钱数为 $4$。

当 $n=3$ 时，每天依次获得一个喵箱，总钱数为 $1+2+3=6$。


title: [HUSTFC 2023] 不定项选择题

description:
有一道共 $n$ 个选项的不定项选择题，它的答案至少包含一个选项，由于题目与选项的内容晦涩难懂，你打算通过尝试每一种可能的答案来通过这道题。

初始时所有选项都没有被勾选，你可以执行任意次下述操作：
- 勾选一个当前未被勾选的选项。
- 取消勾选一个当前已被勾选的选项。

当你勾选中的选项与答案一致时，你将会立即通过此题。在开始尝试前，你产生了一个疑问：在最坏的情况下，至少需要操作多少次才可以通过这道题？

inputFormat: 一行包含一个整数 $n\ (1\le n \le 20)$，表示选项的数量。

outputFormat: 输出一个整数，表示在最坏情况下通过题目的最少操作次数。

hint: 图片与题目无关。


title: [HUSTFC 2023] Fujisaki 讨厌数学

description:
众所周知，Fujisaki 在微积分（一）（上）、微积分（一）（下）、线性代数、离散数学（一）、概率论与数理统计这些课程中，只取得了非常低的分数，这导致他十分痛恨高等数学，因此他给大家带来了一道初等数学题。

已知 $x+x^{-1}=k$，其中 $k$ 是一个整数且 $k\ge 2$，Fujisaki 想让你帮他求出 $x^n+x^{-n}$ 的值。可以证明对于任意的整数 $n \ge 0$，这个值都是一个整数。由于结果可能会非常大，你只需要求出其对 $M$ 取模后的值。

outputFormat: 输出一个整数，表示答案对 $M$ 取模后的值。


title: [HUSTFC 2023] 基因编辑

description:
绮月有 $n$ 条 DNA 碱基序列 $S_1,S_2,\dots S_n$，每条碱基序列可以用一个仅包含 `A`、`C`、`G` 和 `T` 这四种大写字母的字符串表示。

绮月可以拼合两条 DNA 碱基序列，具体操作为将前一条碱基序列的一个前缀（可以为空）和后一条的一个后缀（可以为空）结合，如 `ACGC` 与 `CTAT` 拼合就有可能得到 `ACGCTAT`、`ACGCCTAT`、`ACAT` 或 `T`。

绮月据此定义，一个三元组 $(i,j,k)$ 是好的，当且仅当 $1\le i,j,k \le n$，$i\ne k$，$j \ne k$，且 $S_i$ 与 $S_j$ 拼合可以得到 $S_k$。

绮月想知道好的三元组的数量。

inputFormat:
第一行包含一个整数 $n\ (3\le n\le 2\times 10^5)$，表示碱基序列的数量。

接下来 $n$ 行，每行包含一个字符串，其中第 $i$ 个字符串定义为碱基序列 $S_i\ (1\le |S_i|\le 2\times 10^6)$。保证 $\sum |S_i| \le 2 \times 10^6$。

outputFormat: 输出一个整数，表示好的三元组的数量。


title: [HUSTFC 2023] 网格染色

description:
有一个由 $n\times n$ 个小正方形组成的网格图，其中每个小正方形的边长为 $1$，Walk Alone 和 Kelin 在这上面进行一场染色游戏，游戏的规则如下：
- Walk Alone 和 Kelin 轮流进行操作，Walk Alone 先手。
- 当轮到 Walk Alone 操作时，他选择一条尚未被染色的正方形边框并将其染成**红色**。操作结束时，如果这条边框是一个（或两个）正方形最后一条被染色的边框，则自动将该正方形也同样染成**红色**。
- 当轮到 Kelin 操作时，他选择一条尚未被染色的正方形边框并将其染成**蓝色**。操作结束时，如果这条边框是一个（或两个）正方形最后一条被染色的边框，则自动将该正方形也同样染成**蓝色**。
- 当所有的边框都被染色后，游戏结束。此时染成自己所属颜色的正方形数量更多的一方获胜；或者当数量相等时，达成平局。

例如，在 $2\times 2$ 的网格图中，一种可能的游戏过程如下：

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

已知网格图的边长 $n$，如果两人都积极进行游戏（按照最优策略，尽可能地让自己获胜，或者在自己无法获胜的前提下尽可能地达成平局），请你推断哪一方会获胜或达成平局。

inputFormat: 一行包含一个整数 $n\ (1\le n\le 10^9$)，表示网格图的边长。

outputFormat: 如果 Walk Alone 获胜，输出 `Walk Alone`；否则如果 Kelin 获胜，输出 `Kelin`；否则平局输出 `Draw`。


title: [HUSTFC 2023] 逆 KMP

description:
Walk Alone 是一个字符串大师，但是他已经对传统的字符串算法感到无聊，如 KMP 算法，所以他最近在思考逆向的 KMP。下面是他提出的问题：

给你一个长度为 $n$ 的整数序列 $a$，对于任意的整数 $i\ (1\le i\le n)$，满足 $0\le a_i<i$。你需要构造另一个整数序列 $s$，满足以下条件：
- 序列 $s$ 的长度为 $n$，并且其中任意元素 $s_i$ 满足 $1\le s_i\le n$；
- 对于所有的整数 $i\ (1\le i\le n)$ 和 $j\ (1\le j\le a_i)$，满足 $s_{j}=s_{i-a_i+j}$；
- 满足上述条件的前提下，序列 $s$ 中出现的不同元素的数量**最多**。

当然，Walk Alone 可以很轻松地解决这道题，但他想把这道题当作对你的考验。

inputFormat:
第一行包含一个整数 $n\ (1\le n\le 2\cdot 10^5)$，表示序列 $a$ 的长度。

第二行包含 $n$ 个整数，其中第 $i$ 个整数定义为 $a_i\ (0\le a_i<i)$。

outputFormat: 输出用空格间隔的 $n$ 个整数，其中第 $i$ 个整数定义为 $s_i$。如果存在多个合法答案，请输出字典序最小的那个。


title: [HUSTFC 2023] 新取模运算

description:
在这道题中，我们定义一个新的运算符号 $\oplus$ 并将其称为新取模运算。

当计算 $x \oplus y$ 时，如果 $x$ 不是 $y$ 的倍数，则得到 $x$ 除以 $y$ 的余数; 否则令 $x$ 不断除以 $y$ 直到 $x$ 不再是 $y$ 的倍数，假设它为 $x'$，然后得到 $x'$ 除以 $y$ 的余数。例如，$4\oplus 5=4$，$20\oplus 5=4$，$100\oplus 5=4$。

给定一个质数 $p$，接下来会有多组询问，对于每次询问会给出一个整数 $n$，你需要计算出 $n!\oplus p$ 的值。其中 $n!$ 是 $n$ 的阶乘，即所有小于等于 $n$ 的正整数的乘积。

inputFormat:
第一行包含两个整数 $T\ (1\le T\le 10^5)$ 和 $p\ (2\le p\le 10^6)$，分别表示询问的次数和给定的质数。

接下来 $T$ 行，每行包含一个整数 $n\ (1\le n\le 10^{18})$，含义如题目所述。

outputFormat: 对于每次询问，输出一行包含一个整数，即 $n!\oplus p$ 的值。


title: [HUSTFC 2023] 广义线段树

description:
对于任意长度为 $n$ 的序列 $a$，可以基于 $a$ 建立一个广义线段树。广义线段树是一个有 $(2n-1)$ 个节点的带权二叉树，对于每个编号为 $p$ 的节点，都有两个属性 $L_p$ 和 $R_p$，表示其维护的区间为 $[L_p,R_p]$，同时其权值 $M_p =\prod_{i=L_p}^{R_p}a_i$ 。另外，广义线段树还满足如下性质：
- 所有编号为 $p\in [n,2n-1]$ 的节点是叶节点，同时 $L_p = R_p = p + 1 - n$。
- 所有编号为 $p\in [1,n-1]$ 的节点是非叶节点，其必定有左儿子 $X_p$ 和右儿子 $Y_p$，且 $p < X_p < Y_p$。节点 $p$ 维护的区间为左右儿子维护区间之并，且保证维护区间连续。形式化地，有 $R_{X_p}=L_{Y_p}-1$，且 $L_p=L_{X_p}$，$R_p=R_{Y_p}$。

例如，下面是一个基于 $n=4$ 的序列 $a=\{1, 2, 3, 4\}$ 建立的广义线段树（节点内整数对 $(p,M_p)$ 分别表示编号和权值）。可以发现，广义线段树的形态并不唯一。

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

对这个广义线段树而言：
- $[L_7, R_7] = [4, 4]$，故 $M_7 = a_4$
- $[L_6, R_6] = [3, 3]$，故 $M_6 = a_3$
- $[L_5, R_5] = [2, 2]$，故 $M_5 = a_2$
- $[L_4, R_4] = [1, 1]$，故 $M_4 = a_1$
- $[L_3, R_3] = [L_4, R_5] = [1, 2]$，故 $M_3 = a_1 \times a_2$
- $[L_2, R_2] = [L_3, R_6] = [1, 3]$，故 $M_2 = a_1 \times a_2 \times a_3$
- $[L_1, R_1] = [L_2, R_7] = [1, 4]$，故 $M_1 = a_1 \times a_2 \times a_3 \times a_4$

分别给定长度为 $n$ 的序列 $a$，$b$ 以及节点数为 $(2n-1)$ 的广义线段树 $T$ 的形态（即每个节点的左右儿子编号），然后你需要执行 $n$ 次操作，第 $i$ 次操作为将 $a_i$ 变成 $a_i\times b_i$。

每次操作结束后，你需要基于修改后的序列 $a$ 建立与 $T$ 形态相同的广义线段树，并求出所有节点的权值和，即 $\sum_{i=1}^{2n-1}M_i$。由于结果可能会非常大，你只需要求出其对 $998\,244\,353$ 取模后的值。

inputFormat:
第一行包含一个整数 $n\ (1\le n\le 5\cdot 10^5)$，表示序列 $a$ 和 $b$ 的长度。

第二行包含 $n$ 个整数，其中第 $i$ 个整数定义为 $a_i\ (1 \le a_i < 998\,244\,353)$。

第三行包含 $n$ 个整数，其中第 $i$ 个整数定义为 $b_i\ (1 \le b_i < 998\,244\,353)$。

接下来 $n-1$ 行，其中第 $i$ 行包含两个整数 $X_i,Y_i\ (i<X_i<Y_i\le 2n-1)$，分别表示节点 $i$ 的左右儿子编号。保证输入的广义线段树形态符合题目要求。

outputFormat: 输出一行用空格间隔的 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 次修改后的答案对 $998\,244\,353$ 取模后的值。

hint:
样例中广义线段树的形态和题面中的例子相同。

第一次修改后，$a_1$ 变为 $a_1 \times b_1 = 1 \times 2 = 2$，因而新的 $a = \{2, 2, 3, 4\}$。可以计算出：
- $M_7 = a_4 = 4$
- $M_6 = a_3 = 3$
- $M_5 = a_2 = 2$
- $M_4 = a_1 = 2$
- $M_3 = a_1 \times a_2 = 2 \times 2 = 4$
- $M_2 = a_1 \times a_2 \times a_3 = 2 \times 2 \times 3 = 12$
- $M_1 = a_1 \times a_2 \times a_3 \times a_4 = 2 \times 2 \times 3 \times 4 = 48$

故权值之和为 $M_1 + M_2 + \ldots + M_7 = 75$。

第二次修改后，$a_2$ 变为 $a_2 \times b_2 = 2 \times 3 = 6$。后续的操作与第一次操作类似，此处不再赘述。


title: [HUSTFC 2023] 狭义线段树

description:
你打算建立一棵有 $(2n - 1)$ 个节点，其中有 $n$ 个叶子节点的二叉树。具体地，建立这棵树的伪代码如图所示。

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

不难发现，节点 $1$ 是根节点，并且所有节点的编号与其 DFS 序相同。另外，你认为叶子节点十分重要，因此你按照节点编号从小到大又把这 $n$ 个叶子节点分别称为 $1$ 号叶子，$2$ 号叶子，$\dots$，$n$ 号叶子。叶子节点会被其上方的节点管辖，具体来说，如果 $i$ 号叶子在节点 $j$ 的子树内，则称节点 $j$ 管辖 $i$ 号叶子，不妨用 $g(j,i)=1$ 表示；否则若节点 $j$ 不管辖 $i$ 号叶子，则 $g(j,i)=0$。注意，叶子节点同时也管辖自己本身。

同时，你认为一个好的二叉树要有点权，于是对于节点 $i$，定义其点权为 $v_i$。初始所有节点的点权都为 $0$。

在一次梦中，你正在改造这棵二叉树。你将会对这棵二叉树依次执行 $q$ 次操作，每次操作的格式和描述如下：
- $1\ s\ t\ v$：对于所有的整数 $i\ (i\in [s,t])$，将节点 $i$ 的点权加 $v$。
- $2\ s\ t\ v$：令 $\mathcal{S}={\textstyle \bigcup_{i\in [s,t]}}S_i$，其中 $S_i$ 表示节点 $i$ 管辖的叶子节点的集合。然后对于 $\mathcal{S}$ 中所有叶子节点，将其点权加 $v$。注意 $\mathcal{S}$ 是不重复集合，即在本次操作中，每个叶子节点最多被修改一次。
- $3\ l\ r$：计算 $\sum^{r}_{i=l}f(i)\bmod 998\,244\,353$，其中 $f(i)$ 表示管辖 $i$ 号叶子的所有节点的点权之和，即 $f(i)=\sum_{g(j,i)=1}{v_j}$。

你还想再加点操作，但是早八的铃声把你吵醒了，不过你还是决定实现一下这个奇思妙想。

inputFormat:
第一行包含一个整数 $n\ (3\le n\le 10^5)$，表示二叉树中叶子节点的数量。

第二行包含 $(2n-2)$ 个整数，其中第 $i$ 个整数表示节点 $i+1$ 的父亲节点编号。保证给出的树的形态与节点编号和题目所描述的相同。

第三行包含一个整数 $q\ (3\le q\le 10^5)$，表示操作次数。

接下来 $q$ 行，每行第一个整数 $opt\ (opt\in [1, 3])$ 表示操作类型，若 $opt=1$ 或 $opt=2$，则紧跟三个整数 $s,t,v\ (1\le s\le t\le 2n-1,\ 0\le v<998\,244\,353)$，表示一次修改操作；若 $opt=3$，则紧跟两个整数 $l,r\ (1\le l\le r\le n)$，表示一次询问操作。所有参数的含义如题目所述。

outputFormat: 对于每个 $opt=3$ 的操作，输出一行一个整数，表示本次询问的结果。


title: [HUSTFC 2023] 排列排序问题

description:
JokerShaco 有一个长度为 $n$ 的排列 $p$，他认为一个排列必须是有序的，所以他打算将其进行排序。

他可以对这个排列进行如下操作：
- 将这个排列切割成若干个序列（也可以不切割，保持原样），每个序列至少含有一个元素；
- 选择其中一些序列并将它们翻转；
- 将这些序列按照他的意愿重新组合拼接得到一个新的排列。

JokerShaco 认为切割操作非常累，他想知道如果必须把这个排列变得有序，至少需要切割多少次。

一个长度为 $n$ 的排列的定义为，包含从 $1$ 到 $n$ 这 $n$ 个不同的整数的序列，每个整数恰好出现一次。

序列翻转的定义为，假设存在一个长度为 $m$ 的序列 $[a_1,a_2,\dots,a_{m-1},a_m]$，那么将这个序列翻转后将会得到 $[a_m,a_{m-1},\dots,a_2,a_1]$。

inputFormat:
第一行包含一个整数 $n\ (1\le n\le 10^6$)，表示排列 $p$ 的长度。

第二行包含 $n$ 个整数，其中第 $i$ 个整数定义为 $p_i$。保证输入的 $p$ 一定是长度为 $n$ 的排列。

outputFormat: 输出一个整数，表示将排列 $p$ 变得有序所需的最少切割次数。


title: lmxcslD

background: 欢迎新斗友@[lmxcslD](https://www.luogu.com.cn/user/358957)

description:
定义一个长度为 $m$ 的非空序列 $p_1,p_2,...,p_m$ 是**乱**的当且仅当满足以下两个条件。

- 所有元素之和不超过 $n$，即 $\sum_{i=1}^m p_i\le n$。
- 对于任意一个元素 $p_i$ 满足 $p_i=1$ 或 $p_i$ 为质数。

定义一个**乱**的序列 $p_1,p_2,...,p_m$ 的**乱斗值**为该序列中所有元素减 $k$ 的平方和，即 $\sum_{i=1}^m (p_i-k)^2$。

特别的，定义一个**不乱**的序列的乱斗值为 $0$。

现在给定两个正整数 $n,k$，问所有序列中**乱斗值**最大的序列的**乱斗值**是多少。

inputFormat:
本题有多组测试数据。第一行输入一个正整数 $T$，表示测试数据组数，接下来分别输入 $T$ 组数据。

对于每组测试数据，输入一行两个正整数 $n,k$。

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


title: wbyblD

background: > D题，我不要被hack！！！

description:
有 $n+2$ 个点排成一排，编号为 $0\sim n+1$。对于第 $i$ 号点有两个整数 $a_i,b_i$，其中 $0\le i\le n+1$。规定初始时 $a_0=b_0=a_{n+1}=b_{n+1}=0$。

设你当前在第 $x$ 号点，当前的移动方向为 $y$，初始时 $x=0,y=1$。

你将按如下方式移动直到 $x,y$ 某一次变化后满足 $x=0,y=-1$ 或 $x=n+1,y=1$。

- 若 $y=1$，首先将 $x$ 增加 $1$，此时若 $a_x>0$ 则将 $y$ 变成 $-1$，否则 $y$ 不变，最后再将 $a_x$ 减少 $1$。
- 若 $y=-1$，首先将 $x$ 减少 $1$，此时若 $b_x>0$ 则将 $y$ 变成 $1$，否则 $y$ 不变，最后再将 $b_x$ 减少 $1$。

问最后结束时 $x$ 会在第几号点，事实上，最后 $x$ 仅可能在第 $0$ 号点或第 $n+1$ 号点。

inputFormat:
本题有多组测试数据。第一行输入一个正整数 $T$，表示测试数据组数，接下来分别输入 $T$ 组数据。

对于每组测试数据，第一行输入一个正整数 $n$。

接下来 $n$ 行每行输入两个非负整数 $a_i,b_i$，表示 $a_i,b_i$ 的初始值。

outputFormat: 对于每组测试数据输出一行一个整数表示最后结束时 $x$ 会在第几号点。


title: [NOIP2023] 三值逻辑

description:
小 L 今天学习了 Kleene 三值逻辑。

在三值逻辑中，一个变量的值可能为：真（$\mathit{True}$，简写作 $\mathit{T}$）、假（$\mathit{False}$，简写作 $\mathit{F}$）或未确定（$\mathit{Unknown}$，简写作 $\mathit{U}$）。

在三值逻辑上也可以定义逻辑运算。由于小 L 学习进度很慢，只掌握了逻辑非运算 $\lnot$，其运算法则为：
$$\lnot \mathit{T} = \mathit{F}, \lnot \mathit{F} = \mathit{T}, \lnot\mathit{U} = \mathit{U}.$$

现在小 L 有 $n$ 个三值逻辑变量 $x_1,\cdots, x_n$。小 L 想进行一些有趣的尝试，于是他写下了 $m$ 条语句。语句有以下三种类型，其中 $\leftarrow$ 表示赋值：

1. $x_i \leftarrow v$，其中 $v$ 为 $\mathit{T}, \mathit{F}, \mathit{U}$ 的一种；
2. $x_i \leftarrow x_j$；
3. $x_i \leftarrow \lnot x_j$。

一开始，小 L 会给这些变量赋初值，然后按顺序运行这 $m$ 条语句。

小 L 希望执行了所有语句后，所有变量的最终值与初值都相等。在此前提下，小 L 希望初值中 $\mathit{Unknown}$ 的变量尽可能少。

在本题中，你需要帮助小 L 找到 $\mathit{Unknown}$ 变量个数最少的赋初值方案，使得执行了所有语句后所有变量的最终值和初始值相等。小 L 保证，至少对于本题的所有测试用例，这样的赋初值方案都必然是存在的。

inputFormat:
**本题的测试点包含有多组测试数据。**

输入的第一行包含两个整数 $c$ 和 $t$，分别表示测试点编号和测试数据组数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。

接下来，对于每组测试数据：

- 输入的第一行包含两个整数 $n$ 和 $m$，分别表示变量个数和语句条数。
- 接下来 $m$ 行，按运行顺序给出每条语句。
  - 输入的第一个字符 $v$ 描述这条语句的类型。保证 $v$ 为 `TFU+-` 的其中一种。
  - 若 $v$ 为 `TFU` 的某一种时，接下来给出一个整数 $i$，表示该语句为 $x_i \leftarrow v$；
  - 若 $v$ 为 `+`，接下来给出两个整数 $i,j$，表示该语句为 $x_i \leftarrow x_j$；
  - 若 $v$ 为 `-`，接下来给出两个整数 $i,j$，表示该语句为 $x_i \leftarrow \lnot x_j$。

outputFormat: 对于每组测试数据输出一行一个整数，表示所有符合条件的赋初值方案中，$\mathit{Unknown}$ 变量个数的最小值。

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

第一组测试数据中，$m$ 行语句依次为

- $x_2 \leftarrow \lnot x_1$；
- $x_3 \leftarrow \lnot x_2$；
- $x_1 \leftarrow x_3$。

一组合法的赋初值方案为 $x_1 = \mathit{T}, x_2 = \mathit{F}, x_3 = \mathit{T}$，共有 $0$ 个$\mathit{Unknown}$ 变量。因为不存在赋初值方案中有小于 $0$ 个$\mathit{Unknown}$ 变量，故输出为 $0$。

第二组测试数据中，$m$ 行语句依次为

- $x_2 \leftarrow \lnot x_1$；
- $x_3 \leftarrow \lnot x_2$；
- $x_1 \leftarrow \lnot x_3$。

唯一的赋初值方案为 $x_1 = x_2 = x_3 = \mathit{U}$，共有 $3$ 个$\mathit{Unknown}$ 变量，故输出为 $3$。

第三组测试数据中，$m$ 行语句依次为

- $x_2 \leftarrow \mathit{T}$；
- $x_2 \leftarrow \mathit{U}$；

一个最小化 $\mathit{Unknown}$ 变量个数的赋初值方案为 $x_1 = \mathit{T}, x_2 = \mathit{U}$。$x_1 = x_2 = \mathit{U}$ 也是一个合法的方案，但它没有最小化 $\mathit{Unknown}$ 变量的个数。

**【样例解释 #2】**

该组样例满足测试点 $2$ 的条件。

**【样例解释 #3】**

该组样例满足测试点 $5$ 的条件。

**【样例解释 #4】**

该组样例满足测试点 $8$ 的条件。

**【数据范围】**

对于所有测试数据，保证：

- $1 \le t \le 6$，$1 \le n,m \le 10 ^ 5$；
- 对于每个操作，$v$ 为 `TFU+-` 中的某个字符，$1 \le i,j \le n$。

| 测试点编号 | $n,m\leq$ | $v$ 可能的取值 |
| :----------: | :----------: | :----------: |
| $1,2$ | $10$ | $\mathit{TFU+-}$ |
| $3$ | $10^3$ | $\mathit{TFU}$ |
| $4$ | $10^5$ | $\mathit{TFU}$ |
| $5$ | $10^3$ | $\mathit{U+}$ |
| $6$ | $10^5$ | $\mathit{U+}$ |
| $7$ | $10^3$ | $\mathit{+-}$ |
| $8$ | $10^5$ | $\mathit{+-}$ |
| $9$ | $10^3$ | $\mathit{TFU+-}$ |
| $10$ | $10^5$ | $\mathit{TFU+-}$ |


title: [NOIP2023] 词典

description:
小 S 的词典里有 $n$ 个两两不同的、长度均为 $m$ 的单词 $w_1,w_2,\cdots,w_n$。每个单词都是一个小写字母构成的字符串。

小 S 可以做以下操作任意多次（可以不做）：选择词典中的任意一个单词，交换其中任意两个字符。

对于每个 $1 \le i \le n$，小 S 想知道，是否可以通过以上操作得到新的 $n$ 个单词 $w'_1,w'_2,\cdots , w'_n$，使得对于每个 $j \neq i$，$w'_i$ 的字典序比 $w'_j$ 都要小。**对于 $n=1$ 的情况，我们约定：上述性质是自然成立的。**

对于两个同样长度的字符串 $s = s_1s_2\cdots s_L$ 和 $t = t_1t_2 \cdots t_L$，称字符串 $s$ 字典序小于字符串 $t$，当且仅当以下条件成立：存在位置 $i$，在第 $i$ 个字符之前 $s$ 和 $t$ 都相同，而且 $s_i < t_i$，即小写字母 $s_i$ 在英文字母顺序中先于 $t_i$。

inputFormat:
输入的第一行包含两个正整数 $n$ 和 $m$，分别表示单词个数和单词长度。

接下来 $n$ 行，每行包含一个长度为 $m$ 的小写字母字符串 $w_i$， 表示一个单词。

outputFormat: 输出一行，其中包含一个长度为 $n$ 的 `01` 字符串 $a$；对于 $1 \le i \le n$，如果题目描述中的性质成立，则 $a_i =$ `1`，否则 $a_i =$ `0`。

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

- 不做任何操作，第一个单词字典序最小，因此输出第一个字符为 `1`；
- 交换 `bananaa` 的前两个字符以及 `abandon` 的第三个和第六个字符，得到 `abondan`, `abnanaa`, `baannaa`, `notnotn`，此时第二个单词字典序最小，因此输出第二个字符为 `1`；
- 交换 `baannaa` 的第一个和最后一个字符得到 `aaannab`，其余字符串不变，此时第三个单词字典序最小，因此输出第三个字符为 `1`；
- 无论如何操作，第四个单词不会小于第二个单词，因此输出第四个字符为 `0`。

**【样例解释 #2】**

该组样例满足测试点 $4$ 的限制。

**【样例解释 #3】**

该组样例满足测试点 $7$ 的限制。

**【样例解释 #4】**

该组样例满足测试点 $10$ 的限制。

**【数据范围】**

对于所有测试数据，保证：$1 \le n \le 3000$，$1 \le m \le 3000$，$w_i$ 为长度为 $m$ 的小写字母字符串且两两不同。

| 测试点编号 | $n\leq$ | $m\leq$ |
| :----------: | :----------: | :----------: |
| $1$ | $1$ | $1$ |
| $2\sim 4$ | $26$ | $1$ |
| $5\sim 7$ | $15$ | $2$ |
| $8$ | $300$ | $300$ |
| $9$ | $10^3$ | $10^3$ |
| $10$ | $3000$ | $3000$ |


title: 游戏王

background:
**本题已经增加 hack 数据**。hack 数据位于 subtask 7，记 0 分。此外本题时限较大数据点较多，希望各位不要滥用评测资源。

你正在打块，突然家长走了进来，于是你假装在玩原神。

description:
你改造了原神的抽卡系统。

具体而言，在第 $i$ 次抽卡时，系统将会给出一个可重集合 $S_i$，表示这次抽卡中可供选择的角色。第 $j$ 个角色有两个属性：力量值 $s_{i,j}$ 与魔力值 $m_{i,j}$。你可以从中选择一名角色，并将其加入到自己的背包中；当然，你也可以不做任何选择。你的力量值被定义为背包中所有角色的力量值之和，同时你需要时刻保证背包中角色的魔力值之积不超过魔力上限 $v$。你的任务是最大化自己的力量值。

但是，你很快就厌烦了千篇一律的抽卡。为了给生活找点乐子，你想到了这样的问题：如果游戏从第 $l$ 次抽卡开始，到第 $r$ 次抽卡结束，你的力量值最大是多少呢？

你一口气提出了 $q$ 个这样的问题。现在，你需要计算出它们的答案。

**形式化题意**：

给出一个长为 $n$ 的序列 $\{S_n\}$，其中 $S_i$ 为多个二元组 $(s_{i,j},m_{i,j})$ 构成的可重集。有 $q$ 次询问，每次给定 $l,r$，你需要从 $S_l,S_{l+1},\cdots,S_r$ 的每个集合中分别选出 $0$ 个或 $1$ 个二元组。记选出的 $k$ 个二元组为 $(s'_i,m'_i),1\le i\le k$，则你需要在保证 $\prod_{i=1}^km'_i\le v$ 的基础上，最大化 $\sum_{i=1}^k s'_i$。

inputFormat:
输入的第一行包含两个正整数 $n,v$。

接下来 $n$ 行，每行首先读入 $|S_i|$，接下来读入 $|S_i|$ 对正整数 $(s_{i,j},m_{i,j})$，即 $S_i$ 中每一角色的力量值与魔力值。

随后一行，读入一个正整数 $q$。

接下来 $q$ 行，每行两个正整数 $l,r$，表示一次询问。**注意询问间两两独立，即每次询问都将被视作一次新的游戏。**

outputFormat: 输出共 $q$ 行。对于每次询问，输出你的体力值的最大值。

hint:
#### 样例解释

对于第一组询问，最优策略是从 $S_3$ 中选择 $(3,3)$。此时你的能力值为 $3$。

对于第三组询问，最优策略是从 $S_1$ 中选择 $(2,1)$，$S_2$ 中选择 $(5,3)$，$S_3$ 中选择 $(3,3)$，$S_4$ 中选择 $(3,1)$，此时魔力值之积等于 $1\times 3\times 3\times 1=9\le 10$，你的能力值等于 $2+5+3+3=13$。

#### 数据范围与约定

**本题使用子任务捆绑测试，只有通过子任务内全部测试点才可以获得该子任务的相应分数**。

记 $tot=\sum_{i=1}^n|S_i|$。

- 子任务 1（5 分）：保证 $n,tot\le 10$。
- 子任务 2（20 分）：保证 $n,v,tot,q\le 100$。
- 子任务 3（15 分）：保证所有 $m_{i,j}$ 在范围内均匀随机生成。
- 子任务 4（20 分）：保证 $1\le n,v,tot,q\le 10^4$。
- 子任务 5（15 分）：保证对于所有询问，均有 $l=1$ 或者 $r=n$。
- 子任务 6（25 分）：无特殊限制。

对于所有数据，保证 $1\le n,tot\le 10^5$，$1\le q\le 2\times 10^5$，$1\le m_{i,j}\le v\le 10^5$，$1\le s_{i,j}\le 10^4$，$1\le l\le r\le n$。


title: [POI2022~2023R1] kol

background:
题目译自 [POI2022~2023R1 kol](https://sio2.mimuw.edu.pl/c/oi30-1/p/kol/)。

注意：原题时限为 32s，为避免卡评测，此题时限改为 3s。

description:
你在一个 $m \times m$ 的棋盘上玩贪吃蛇游戏，已知原本蛇长度为 $1$，内容为 `0`，在 $(1,1)$ 处，棋盘上存在 $p$ 个“食物点”，当一条蛇吃了一个“食物点”时，它将会在其头部增加一个食物点对应数值的部分，下图可以更清楚的演示吃食物的过程（红色数字为蛇身）：

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

现在你进行了 $n$ 个操作，存在移动操作（上下左右）和查询操作（询问一个点是否被蛇覆盖），请编写一个程序求出它。

inputFormat:
第一行三个整数 $m$，$p$，$n \ (1 \leq m \leq 2000$，$1 \leq p \leq \min(m^2 - 1, 10^6)$，$1 \leq n \leq 10^6)$。

接下来 $p$ 行，每行三个整数 $w_i$，$k_i$，$c_i \ (1 \leq w_i,k_i \leq m$，$0 \leq c_i \leq m^2-1)$，表示坐标 $(w_i,k_i)$ 的点是一个存在食物为 $c_i$ 的食物点。

然后 $n$ 行，每行先是一个字符。

- 如果该字符为 `Z`，则紧接着后面两个左边 $w_j',k_j'$，表示询问 $(w_j',k_j')$ 的地方是否存在蛇身，不存在输出 $-1$，存在输出对应的内容（数值）。

- 否则，按照对应顺序移动：上（`G`）、下（`D`）、左（`L`）或右（`P`）。

outputFormat: 对应字符为 `Z` 的，输出对应的输出。


title: [POI2022~2023R1] ply

background: 题目译自 [POI2022~2023R1 ply](https://sio2.mimuw.edu.pl/c/oi30-1/p/ply/)。

description:
定义“合法括号串”及其深度如下：

- 空串是一个合法括号串，深度为 $0$。
- 如果 $w$ 是一个合法括号串，深度为 $h$，则 $(w)$ 也是一个合法括号串，深度为 $h+1$。
- 如果 $w_1$ 和 $w_2$ 都是合法括号串，深度分别为 $h_1$ 和 $h_2$，则 $w_1w_2$ 也是一个合法括号串，深度为 $\max(h_1,h_2)$。

定义翻转一个字符为：

- 如果当前字符为 `(`，修改为 `)`。
- 如果当前字符为 `)`，修改为 `(`。

你需要通过翻转 $s$ 当中某些字符使得深度不超过 $H$，求最小操作次数。

inputFormat:
第一行两个数字 $n \ (2 \leq n \leq 10^6)$ 和 $H \ (1 \leq H \leq \frac{n}{2})$，分别表示 $|s|$ 和要求修改后不超过的深度。

第二行一个字符串 $s$，表示原来的括号串。

outputFormat: 输出最小修改次数。


title: [POI2022~2023R1] poc

background: 题目译自 [POI2022~2023R1 poc](https://sio2.mimuw.edu.pl/c/oi30-1/p/poc/)。

description:
小 A 和小 B 在记录过往的车辆的类型！

已知类型分别有 $1 \sim k$ 个，每种车辆必然属于其中之一。

小 A 按顺序细心地记录了所有的车辆的类型，但是贪玩的小 B 只按顺序记录了一部分车辆。

小 A 记录的内容长度为 $n$，小 B 记录的长度为 $m$。

称在小 A 记录中的第 $i$ 辆车“可能被 B 记录到”当且仅当在小 A 的记录中存在一个包含 $i$ 的子序列与小 B 所记录的完全相同。

保证小 B 记录的序列一定是小 A 记录的子序列，问哪些车辆是可能会被小 B 记录到，哪些没有。

inputFormat:
第一行三个整数 $n,m,k \ (1 \leq n,m,k \leq 3 \times 10^5)$。

第二行一个长度为 $n$ 的序列，表示小 A 记录的序列。

第三行一个长度为 $m$ 的序列，表示小 B 记录的序列。

上述序列中的元素均满足 $1\leq$ 序列元素 $\leq k$。

outputFormat: 对于每个小 A 记录到的车辆，请确定它能否被记录到，能输出 $1$，不能输出 $0$。


title: [POI2022~2023R1] wyp

background: 题目译自 [POI2022~2023R1 wyp](https://sio2.mimuw.edu.pl/c/oi30-1/p/wyp/)。

description:
你在高速上开着你新买的车，高速上共有 $2$ 个车道（分为左右，初始时所有车辆都在右侧），$n$ 辆在前面的车，但是由于这些车开的实在是太慢了，你想要进行超车。

已知你的速度为 $V$，其他车速度为 $v_i$（保证 $V > v_i$），如果你的车的车头已经要撞上其他车了，那么你将会向左开进行超车，如果你当前右侧位置存在一个空隙使得你的车进入的了，那么你一定进行右侧。

注意此处存在其他车相撞的情况，后面的车的速度会改成与它前面一样的速度。

问你的车会进行几次左转操作。

inputFormat:
第一行四个整数 $n$，$D$，$W$，$M$（$1 \leq n \leq 10^5$，$ 1 \leq D \leq 10^9$，$1 \leq W,M \leq 1000$），分别表示卡车的数量，自己车的长度，自己车的速度为 $W/M$，默认自己车的车头坐标为 $0$。

接下来 $n$ 行，每行 $4$ 个整数 $x_i$，$d_i$，$w_i$，$m_i$（$1 \leq x_i,d_i \leq 10^9$，$1 \leq w_i,m_i \leq 1000$），分别表示其他车的坐标、长度，速度为 $w_i / m_i$。

保证按 $x_i$ 升序排序给出。

outputFormat: 输出要实行超车 $n$ 辆车要左转的次数。