title: [CCC 2008 J1] Body Mass Index

description:
The Body Mass Index (BMI) is one of the calculations used by doctors to assess an adult’s health. The doctor measures the patient’s height (in metres) and weight (in kilograms), then calculates the BMI using the formula:

$$\text{BMI} = \dfrac{\text{weight}}{\text{height} \times \text{height}}$$

Write a program which prompts for the patient’s height and weight, calculates the BMI, and displays the corresponding message from the table below.

| BMI Category | Message |
| :----------: | :----------: |
| More than $25$ | Overweight |
| Between $18.5$ and $25.0$ (inclusive)  | Normal weight |
| Less than $18.5$ | Underweight |

inputFormat: 第一行输入体重，第二行输入身高（以米为单位）。

outputFormat: 输出所得 BMI 值对应的信息。

translation:
给出两个浮点数 $weight(1.0 \leq weight \leq 100.0)$ 与 $height(1.0 \leq height \leq 2.0)$，请你帮忙判断其 BMI 值所对应的信息：

| BMI 范围 | 对应信息 |
| :----------: | :----------: |
| 大于 $25$ | Overweight |
| 介于 $18.5$ 与 $25.0$ 之间  | Normal weight |
| 小于 $18.5$ | Underweight |

BMI 计算公式：

$$\text{BMI} = \dfrac{\text{weight}}{\text{height} \times \text{height}}$$

hint:
**Explanation for Output in Sample Input 1**:

The BMI is $69 \div (1.73 \times 1.73)$, which is approximately $23.0545$. According to the table, this is a "Normal weight".

**Explanation for Output in Sample Input 2**:

The BMI is $84.5 \div (1.8 \times 1.8)$, which is approximately $26.0802$. According to the table, this is "Overweight".


title: [CCC 2008 J2] Do the Shuffle

type: P

description:
Those tiny music machines that play your digital music are really computers that keep track of and play music files. The CCC music player $(C^3MP)$ is currently in development and will be hitting the stores soon! In this problem, you have to simulate a $C^3MP$.

The $C^3MP$ music player will hold $5$ songs in memory, whose titles will always be `A`, `B`, `C`, `D`, `E`. The $C^3MP$ also keeps track of a playlist, which is an ordering of all the songs. The $C^3MP$ has 4 buttons that the user will press to rearrange the playlist and play the songs.

Initially, the $C^3MP$ playist is `A,B,C,D,E`. The $4$ control buttons do the following:

- button $1$: move the first song of the playlist to the end of the playlist. For example: `A,B,C,D,E` will change to `B,C,D,E,A`.

- button $2$: move the last song of the playlist to the start of the playlist. For example, `A,B,C,D,E` will change to `E,A,B,C,D`.

- button $3$: swap the first two songs of the playlist. For example, `A,B,C,D,E` will change to `B,A,C,D,E`.

- button $4$: stop rearranging songs and output the playlist.

inputFormat: You need to write a program to simulate a CCC music player. Your program should repeatedly ask for two positive integers b and n. Here b represents the button number that the user wants to press, $1 \leq b \leq 4$, and n represents the number of times that the user wants to press button b. You can assume that n always satisfies $1 \leq n \leq 10$.

outputFormat: The input will always finish with the pair of inputs $(b = 4, n = 1)$ when this happens, you should print the order of songs in the current playlist and your program should end. You can assume that the user will only ever press button $4$ once.

translation:
你有一个含有五个字符的字符数组，该字符数组初始值为 $\{\text{A,B,C,D,E}\}$，每次操作数据输入都是两个数 $b(1 \leq b \leq 4)$ 和 $n(1 \leq n \leq 10)$，你需要根据 $b$ 的值进行操作：

- $b = 1$ 的情况：将前面第一个字符移到末尾去，执行 $n$ 次。

- $b = 2$ 的情况：将末尾字符移到首位去，执行 $n$ 次。

- $b = 3$ 的情况：交换前 $2$ 个字符的位置，执行 $n$ 次。

- $b = 4$ 的情况：输出当前的字符数组（每个字符用空格隔开），并终止程序。


title: [JOISC 2023 Day3] Tourism

description:
JOI Kingdom is an insular country consisting of $N$ islands, numbered from $1$ to $N$. The islands are connected by $N − 1$ bridges, numbered from $1$ to $N − 1$. The bridge $i\ (1 ≤ i ≤ N − 1)$ connects the island $A_i$ and the island $B_i$ bidirectionally. It is possible to travel from any island to any other island by passing through a number of
bridges.
In JOI Kingdom, there are $M$ sightseeing spots, numbered from $1$ to $M$. The sightseeing spot $j\ (1 ≤ j ≤ M)$ is located in the island $C_j$.
There are $Q$ travelers. They plan to visit sightseeing spots in JOI Kingdom. The travelers are numbered from $1$ to $Q$. Each traveler makes a trip in the following way.

1. The traveler chooses an island $x\ (1 ≤ x ≤ N)$. Taking an airplane, the traveler arrives at the island $x$.
2. The traveler takes the following actions a number of times. The order and the kinds of actions are arbitrary.

    - The traveler chooses a sightseeing spot in the current island, and visits there.
    - The traveler moves to another island by passing through a bridge.

3. Taking an airplane, the traveler leaves JOI Kingdom.
    The traveler $k\ (1 ≤ k ≤ Q)$ wants to visit all of the sightseeing spots $L_k, L_{k + 1}, . . . , R_k$. However, since the budget is limited, the traveler $k$ wants to minimize the number of islands where the traveler $k$ visits at least once.

Write a program which, given information of JOI Kingdom and the travelers, calculates, for each $k\ (1 ≤ k ≤ Q)$, the minimum possible number of islands where the traveler $k$ visits at least once.

outputFormat: Write $Q$ lines to the standard output. The $k$-th line $(1 ≤ k ≤ Q)$ of output should contain the minimum possible number of islands where the traveler $k$ visits at least once.

translation:
给出一颗 $n$ 个节点的树，和一个长度为 $m$ 的序列 $a$，$q$ 次询问包含 $a_{l\cdots r}$ 中所有节点的最小联通块大小。

$n,m,q\le 10^5$

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

The traveler 1 makes a trip in the following way, and visits all of the sightseeing spots 1, 2, 3.
1. The traveler 1 arrives at the island 2.
2. The traveler 1 visits the sightseeing spot 1 in the island 2.
3. The traveler 1 moves from the island 2 to the island 1 by passing through the bridge 1.
4. The traveler 1 moves from the island 1 to the island 3 by passing through the bridge 2.
5. The traveler 1 visits the sightseeing spot 2 in the island 3.
6. The traveler 1 moves from the island 3 to the island 6 by passing through the bridge 5.
7. The traveler 1 visits the sightseeing spot 3 in the island 6.
8. The traveler 1 departs from the island 6 and leaves JOI Kingdom.

The islands 1, 2, 3, 6 are the four islands where the traveler 1 visits at least once. If the number of islands traveler 1 visits at least once is less than or equal to 3, it is impossible to visit all of the sightseeing spots 1, 2, 3.
Therefore, output 4 in the first line.
The traveler 2 makes a trip in the following way, and visits all of the sightseeing spots 4, 5, 6.
1. The traveler 2 arrives at the island 3.
2. The traveler 2 moves from the island 3 to the island 7 by passing through the bridge 6.
3. The traveler 2 visits the sightseeing spot 6 in the island 7.
4. The traveler 2 moves from the island 7 to the island 3 by passing through the bridge 6.
5. The traveler 2 moves from the island 3 to the island 1 by passing through the bridge 2.
6. The traveler 2 moves from the island 1 to the island 2 by passing through the bridge 1.
7. The traveler 2 moves from the island 2 to the island 4 by passing through the bridge 3.
8. The traveler 2 visits the sightseeing spot 4 in the island 4.
9. The traveler 2 moves from the island 4 to the island 2 by passing through the bridge 3.
10. The traveler 2 moves from the island 2 to the island 5 by passing through the bridge 4.
11. The traveler 2 visits the sightseeing spot 5 in the island 5.
12. The traveler 2 departs from the island 5 and leaves JOI Kingdom.

The islands 1, 2, 3, 4, 5, 7 are the six islands where the traveler 2 visits at least once. If the number of islands
traveler 2 visits at least once is less than or equal to 5, it is impossible to visit all of the sightseeing spots 4, 5, 6.
Therefore, output 6 in the second line.
This sample input satisfies the constraints of Subtasks 1, 2, 4, 5, 6.

The islands 1, 2, 3, 4, 5, 7 are the six islands where the traveler 2 visits at least once. If the number of islands
traveler 2 visits at least once is less than or equal to 5, it is impossible to visit all of the sightseeing spots 4, 5, 6.
Therefore, output 6 in the second line.

This sample input satisfies the constraints of Subtasks 1, 2, 4, 5, 6.

**【样例解释 #2】**

This sample input satisfies the constraints of Subtasks 1, 2, 3, 6.

**【样例解释 #3】**

This sample input satisfies the constraints of Subtasks 1, 2, 6.

**【数据范围】**

- $1 ≤ N ≤ 100 000$.
- $1 ≤ M ≤ 100 000$.
- $1 ≤ Q ≤ 100 000$.
- $1 ≤ A_i ≤ N\ (1 ≤ i ≤ N − 1)$.
- $1 ≤ B_i ≤ N\ (1 ≤ i ≤ N − 1)$.
- It is possible to travel from any island to any other island by passing through a number of bridges.
- $1 ≤ C_j ≤ N\ (1 ≤ j ≤ M)$.
- $1 ≤ L_k ≤ R_k ≤ M\ (1 ≤ k ≤ Q)$.
- Given values are all integers.

**【子任务】**

1. (5 points) $N ≤ 300, M ≤ 300, Q ≤ 300$.
2. (5 points) $N ≤ 2 000, M ≤ 2 000, Q ≤ 2 000$.
3. (7 points) $A_i = i, B_i = i + 1\ (1 ≤ i ≤ N − 1)$.
4. (18 points) $L_1 = 1, R_{k} + 1 = L_{k+1}\ (1 ≤ k ≤ Q − 1), R_Q = M$.
5. (24 points) $A_i = \lfloor\frac{i+1}2\rfloor, B_i = i + 1\ (1 ≤ i ≤ N−1)$. Here, $⌊x⌋$ is the largest integer not exceeding x.
6. (41 points) No additional constraints.


title: [CCC 2008 J3] GPS Text Entry

description:
For her birthday, Sandy got a Global Positioning System (GPS) unit, which is an electronic device she can use to track the local hiking trails. Along the way Sandy can mark waypoints that can be recorded on a map when she gets home. A description of each waypoint can be entered in the unit, however the device does not have a keypad. Instead it has four cursor buttons, up, down, left, and right, and a button to accept the letter. The keypad looks like the following:

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

The screen displays a grid of the letters and symbols that can be used to “type out” the description. Here is the layout of the grid:

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

When you enter the name of the waypoint, the cursor starts at the `A`. You must move the cursor to the location of the next letter or symbol and then accept that letter. The cursor can only move to squares which are adjacent horizontally or vertically (not diagonally). Once you have entered all the letters in the description, you need to move the cursor to `enter` and accept the entire phrase.

You are to write a program that will calculate the number of cursor movements it takes to “type in” a phrase. For example, to enter the word `GPS`, starting from the `A` position, you would move down $1$ to select `G`, then move right $3$ and down $1$ to select `P`, then move down 1 and left $3$ to select `S` and finally move down $1$ and right $5$ to select `enter`. This is a total of $15$ cursor movements. Note that the total number of cursor movements does not change if you choose to move down and then across or across and then down. Also note that you cannot move beyond the boundaries of the grid (e.g., you cannot move off the grid nor `wrap-around` the grid).

inputFormat: The input for your program will be a string of at most $40$ characters. You may assume that all characters in the string are contained in the grid

outputFormat:
The output for your program will be an integer that is the total number of cursor movements needed
to enter the string using the grid layout given.

translation:
给你一个字符串，其长度最多为 $40$，你需要通过键盘打出这个字符串，你的打字工具目前使用的键盘如下：

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

初始时你在 `A` 处，你需要将此字符串从左往右依次打出。每次移动，你可以向上下左右任一方向移动一格，注意你不能从某个地方“瞬移”到另一个地方，只能通过上述方式移动，且当你输入完所有字符串时要按下 `enter` 键。

hint: 数据保证合法。


title: [JOISC 2023 Day3] Cookies

description:
Rie likes to make cookies. She made $N$ types of cookies. She made $A _ i$ cookies of type $i(1 \leq i \leq N)$. In order to sell the cookies made by her, she will pack them into boxes. However, the following conditions should be satisfied.

- For every box, the types of the cookies in it should be different.
- For every box, the number of cookies in it should be equal to one of the following $M$ numbers: $B _ 1, B _ 2, \cdots, B _ M$.

Write a program which, given information of cookies made by Rie and the conditions to pack the cookies into boxes, determines whether it is possible to pack all the cookies into boxes. Moreover, if it is possible to pack all the cookies into boxes, your program should output a way to pack the cookies into the minimum number of boxes.

inputFormat:
Read the following data from the standard input.

> $N$
> $A _ 1 \ A _ 2 \ \cdots \ A _ N$
> $M$
> $B _ 1 \ B _ 2 \ \cdots \ B _ M$

outputFormat:
If it is possible to pack all the cookies into boxes so that the conditions are satisfied, let $x$ be the number of used boxes, $c _ k$ be the number of cookies in the $k$-th box ($1\leq k \leq x$), and $v _ {k, 1}, v _ {k, 2}, \cdots, v _ {k, c _ k}$ be the types of the cookies in the $k$-th box. Write these numbers to the standard output as in the following format.

> $x$
> $c _ 1 \ v _ {1, 1} \ v _ {1, 2} \ \cdots \ v _ {1, c _ 1}$
> $c _ 2 \ v _ {2, 1} \ v _ {2, 2} \ \cdots \ v _ {2, c _ 2}$
> $\vdots$
> $c _ x \ v _ {x, 1} \ v _ {x, 2} \ \cdots \ v _ {x, c _ x}$

Here, the number of used boxes $x$ should be the minimum possible number. If there are several ways to pack the cookies into boxes satisfying the conditions, output any one of them.

If it is impossible to pack all the cookies into boxes so that the conditions are satisfied, write $-1$ to the standard output.

translation:
#### 题目描述

莉婕喜欢做饼干。她制作了 $N$ 种饼干。第 $i$ 种饼干有 $A_i$ 个。为了出售她制作的饼干，她将它们装入盒子中。但是，应该满足以下条件。

+ 对于每个盒子，其中的饼干种类应不同。

+ 对于每个盒子，其中的饼干数量应等于以下 $M$ 个数字之一：$B_1,B_2,⋯ ,B_M$。

编写一个程序，给出莉婕制作的饼干信息和将饼干装箱的条件，确定是否可能将所有饼干包装到盒子中。此外，如果可以将所有饼干包装在盒子中，则您的程序应输出最少的盒子数量。
#### 输入格式

从标准输入读取以下数据。
> $N$
> $A _ 1 \ A _ 2 \ \cdots \ A _ N$
> $M$
> $B _ 1 \ B _ 2 \ \cdots \ B _ M$

#### 输出格式
如果可以将所有的饼干装入盒子并且满足上述条件，则设 $x$ 是所需的盒子数，$c_k$ 是第 $k$ 个盒子中的饼干数 $(1≤k≤x)$，$v_{k,1},v_{k,2},⋯ ,v_{k,c_k}$ 是第 $k$ 个盒子中的饼干种类。请将这些数字按以下格式编写到标准输出。
> $x$
> $c _ 1 \ v _ {1, 1} \ v _ {1, 2} \ \cdots \ v _ {1, c _ 1}$
> $c _ 2 \ v _ {2, 1} \ v _ {2, 2} \ \cdots \ v _ {2, c _ 2}$
> $\vdots$
> $c _ x \ v _ {x, 1} \ v _ {x, 2} \ \cdots \ v _ {x, c _ x}$

在此，使用的盒子数量 $x$ 应该是可能的最小数量。如果有多种方式可以满足条件地将饼干装入盒子，请输出其中任何一种方法。

如果无法将所有饼干包装在盒子中以满足条件，输出 $-1$。

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

对于该样例输入，可以按照以下方式将 $7$ 个饼干装入 $3$ 个盒子中满足条件：

+ 将第 $1$ 类和第 $7$ 类的饼干装入第一个盒子中。每种类型放 $1$ 个。
+ 将第 $2$ 类和第 $6$ 类的饼干装入第二个盒子中。每种类型放 $1$ 个。
+ 将第 $3$ 类、第 $4$ 类和第 $5$ 类的饼干装入第三个盒子中。每种类型放 $1$ 个。

因为不能用少于或等于 $2$ 个盒子来包装 $7$ 个饼干，所以以上方法是正确的。判断为正确答案。还有其他正确方法。

Translate by @[ZeXic_B](https://www.luogu.com.cn/user/661274)

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

In this sample input, it is possible to pack the $7$ cookies into $3$ boxes so that the conditions are satisfied as follows.

- Pack cookies of types $1, 7$ into the first box. Pack one cookie for each type.
- Pack cookies of types $2, 6$ into the second box. Pack one cookie for each type.
- Pack cookies of types $3, 4, 5$ into the third box. Pack one cookie for each type.

Your program is judged as correct if it outputs the above way to pack the cookies because it is impossible to pack the $7$ cookies into less than or equal to $2$ boxes so that the conditions are satisfied. There are other ways to pack the cookies which are judged as correct.

This sample input satisfies the constraints of Subtasks 1, 3, 4, 5, 6.

**【样例解释 #2】**

In this sample input, it is impossible to pack the $15$ cookies into boxes so that the conditions are satisfied.

Therefore, output $-1$.

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6.

**【样例解释 #3】**

This sample input satisfies the constraints of Subtasks 4, 5, 6.

**【数据范围】**

对于所有测试数据，满足 $1 \leq N \leq 15 000$，$A _ i \geq 1$（$1 \leq i \leq n$），$A _ 1 + A _ 2 + \cdots + A _ N \leq 15 000$，$1 \leq M \leq N$，$1 \leq B _ j \leq N$（$1 \leq j \leq M$），$B _ j < B _ {j + 1}$（$1 \leq j \leq M - 1$），保证所有输入均为整数。

| **子任务编号** | **分值** | **限制** |
| :----------: | :----------: | :----------: |
| $1$ | $6$ | $N \leq 500$，$A _ i = 1$（$1 \leq i \leq N$） |
| $2$ | $7$ | $N \leq 500$，$M = 1$ |
| $3$ | $12$ | $A _ 1 + A _ 2 + \cdots + A _ N \leq 15$ |
| $4$ | $45$ | $A _ 1 + A _ 2 + \cdots + A _ N \leq 500$ |
| $5$ | $15$ | $A _ 1 + A _ 2 + \cdots + A _ N \leq 3000$ |
| $6$ | $15$ | 没有额外的限制 |


title: [JOISC 2023 Day4] Security Guard

description:
In JOI Kingdom, there are $N$ islands, numbered from $1$ to $N$. Each island has the insecurity level. The insecurity level of the island $i\ (1 \le i \le N)$ is $S_i$.

In JOI Kingdom, ships between pairs of islands are mostly used as the methods of transportations. There are $M$ ships, numbered from $1$ to $M$. The ship $j\ (1 \le j \le M)$ connects the island $A_j$ and the island $B_j$. We can run ships when necessary. It is possible to travel from any island to any other island by taking a number of ships.

In JOI Kingdom, there is a plan to introduce new ships. We can choose any pairs of islands where newly introduced ships connect.

One day, an incident occurred. A ship at anchor was attacked. Prime minister K of JOI Kingdom decided to introduce new ships. He also demands that ships in JOI Kingdom should satisfy the following **Security
Condition**.

- When a ship is anchored at the island $i\ (1 \le i \le N)$, the number of security guards on the ship is greater than or equal to $S_i$.

However, since it is expensive to hire security guards, we want to minimize the number of hired security guards. As long as the condition “it is possible to travel from any island to any other island by taking a number of ships” is satisfied, it is possible to abolish ships which are currently running.

Therefore, we will run ships as follows. Here, $k$ is the number of newly introduced ships.

1. For each of the $k$ newly introduced ships, we choose two islands where it connects.
2. We choose a number of (more than or equal to $0$) ships, and we abolish them. It is allowed to abolish newly introduced ships.
3. For each of the ships, we anchor it at one of the two islands where it connects. We make a number of security guards get on it. Moreover, the following conditions should be satisfied.

*Condition*     For every pair $u, v\ (1 \le u \le N, 1 \le v \le N)$ of islands, it is possible to transport a passenger from the island $u$ to the island $v$ by repeating the following operations a number of times. In the process, Security Condition should be satisfied all the time.

 -  We make a passenger or security guards get on a ship which is anchored at the island where the passenger or security guards are staying.
- We make a passenger or security guards get off a ship at the island where the ship is currently anchored.
- We move a ship from the island where the ship is currently anchored to the other island where the ship connects.

Since the budget is limited, we can introduce at most $Q$ new ships. For each $k\ (0 \le k \le Q)$, Prime minister K wants to know the minimum possible number of hired security guards if the number of newly introduced ships is $k$.
Write a program which, given the information of islands and the routes of the ships and the number of new ships we can introduce, calculates the minimum possible number of hired security guards for each $k$.

inputFormat:
Read the following data from the standard input.

> $N\ M\ Q$
>
> $S_1\ S_2\ \cdots\ S_N$
>
> $A_1\ B_1$
>
> $A_2\ B_2$
>
> $\vdots$
>
> $A_M\ B_M$

outputFormat: Write $Q+1$ lines to the standard output. The $(k+1)$-th line $(0 \le k \le Q)$ of output should contain the minimum possible number of hired security guards if the number of newly introduced ships is $k$.

translation:
在 JOI 王国中，有 $N$ 座岛屿，编号从 $1$ 到 $N$。每座岛屿都有不安全程度 $S_i$。

在 JOI 王国中，使用船只作为交通工具连接各个岛屿。现有 $M$ 艘船只，编号从 $1$ 到 $M$，第 $j$ 艘船只连接着岛屿 $A_j$ 和 $B_j$。我们可以在需要时运行这些船只。乘坐几艘船只后，可从任意岛屿抵达其他所有岛屿。

今天，JOI 王国的首相 K 毅然决定引入新的船只，并要求所有船只必须遵守以下安全条件。

当一艘船只停泊在岛屿 $i\ (1\leq i \leq N)$ 时，其上的保安人数大于等于 $S_i$。

鉴于雇佣保对于每艘船只，将其停泊在与其相连的两座岛屿中的一座上，并在其上安置一定数量的保安人员。此外，还应满足以下条件：安十分昂贵，我们希望最小化雇佣的保安人数。只要满足“通过乘坐若干艘船只可从任意岛屿到达其他任意岛屿”这个条件，就可以废除目前正在运营的一些船只。

我们将按如下方法运营船只。这里，$k$ 是要引入的新的船只数。

+ 对于这 $k$ 艘新的船只，选择它们相连接的两座岛屿。

+ 我们选取一些（多于或等于 $0$ 艘，以下称为“废除船只”）船只予以废除。允许废除已经运行的新船只。

+ 对于每艘船只，将其停泊在与其相连的两座岛屿中的一座上，并在其上安置一定数量的保安人员。此外，还应满足以下条件：对于所有岛屿对 $u, v\ (1\leq u\leq N,1\leq v\leq N)$，重复下面的操作若干次后可以将一位乘客从岛屿 $u$ 运送到岛屿 $v$。在整个过程中，必须使当一艘船只停泊在某座岛屿 $i$ 上时，其上的保安人数大于等于 $S_i$。

1. 在停泊在该岛屿上的船只上载客或保安。
2. 在抵达另一座岛屿之前，在停泊在目前所处的船只上卸客或保安。
3. 从目前所处的岛屿开往与之相连的另一座岛屿并停泊在那里。

由于预算有限，我们最多可以引入 $Q$ 艘新船。对于每个 $k\ (0\leq k\leq Q)$，首相 K 想要知道在引入 $k$ 艘新船的情况下，满足所有条件时最小可能雇用的保安人数。请编写一个程序，根据岛屿和船只路线的信息以及可以引入的新船数量，计算每个 $k$ 对应的最小人数。

Translate by @[ZeXic_B](https://www.luogu.com.cn/user/661274)

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

If the number of newly introduced ships is $0$, we need $7$ security guards. For example, the conditions are satisfied if we allocate the ships and $7$ security guards as follows.

- The ship $1$ is initially anchored at the island $2$, and two security guards get on the ship $1$.
- The ship $2$ is initially anchored at the island $2$, and two security guards get on the ship $2$.
- The ship $3$ is initially anchored at the island $4$, and three security guards get on the ship $3$.

Let us explain how to transport a passenger in the following two cases.

- We transport a passenger from the island $1$ to the island $4$.
- We transport a passenger from the island $3$ to the island $2$.

We can transport a passenger from the island $1$ to the island $4$ as follows. The islands where the ships $1, 2, 3$ are anchored, and the numbers of security guards on the ships $1, 2, 3$ are written in this order. The numbers of security guards on the islands $1, 2, 3, 4$ are written in this order.

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

We can transport a passenger from the island $3$ to the island $2$ as follows.

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

Since it is impossible to satisfy the conditions if the number of security guards is less than or equal to $6$, output $7$.

This sample input satisfies the constraints of Subtasks $2, 3, 4, 5, 6, 7$.

#### 【样例解释 #2】

If the number of newly introduced ships is $0$, similarly as Sample Input $1$, we need $7$ security guards.

If the number of newly introduced ships is $1$, we need $5$ security guards. For example, the conditions are satisfied if we allocate the ships and $5$ security guards as follows.

- We introduce a new ship connecting the island $2$ and the island $4$. (In the following, we call it the ship $4$.)
- We abolish the ship $3$.
- We initially anchor the ship $1$ at the island $2$, and make two security guards get on the ship $1$.
- We initially anchor the ship $2$ at the island $2$, and make one security guard get on the ship $2$.
- We initially anchor the ship $4$ at the island $2$, and make two security guards get on the ship $4$.

This sample input satisfies the constraints of Subtasks $5, 6, 7$.

#### 【样例解释 #3】

If the number of newly introduced ships is $0$, we need $2$ security guards. For example, the conditions are satisfied if we allocate the ships and $2$ security guards as follows.

- We abolish the ship $3$.
- We initially anchor the ship $1$ at the island $1$, and make one security guard get on the ship $1$.
- We initially anchor the ship $2$ at the island $1$, and make one security guard get on the ship $2$.

This sample input satisfies the constraints of Subtasks $4, 5, 6, 7$.

#### 【样例解释 #4】

This sample input satisfies the constraints of all the subtasks.

#### 【样例解释 #5】

This sample input satisfies the constraints of Subtasks $3, 4, 5, 6, 7$.

#### 【样例解释 #6】

This sample input satisfies the constraints of Subtasks $5, 6, 7$.

#### 【数据范围】

对于所有测试数据，满足：

- $2 \le N \le 2\times 10 ^ 5$;
- $N - 1 \le M \le 4\times 10 ^ 5$;
- $0 \le Q \le 2\times 10 ^ 5$;
- $1 \le S_i \le 10 ^ 9\ (1 \le i \le N)$;
- $1 \le A_j < B_j \le N\ (1 \le j \le M)$;
- $(A_x, B_x) \neq (A_y, B_y)\ (1 \le x < y \le M)$;
- It is possible to travel from any island to any other island by taking a number of ships;
- Given values are all integers.

| 子任务编号 | 分值 | 特殊限制 |
| :----------: | :----------: | :----------: |
| $1$ | $12$ | $M = N - 1$，$Q = 0$，$S_i \le 2\ (1 \le i \le N)$，$A_j = j$，$B_j = j + 1\ (1 \le j \le M)$ |
| $2$ | $13$ | $M = N - 1$，$Q = 0$，$A_j = j$，$B_j = j + 1\ (1 \le j \le M)$ |
| $3$ | $12$ | $M = N - 1$，$Q = 0$ |
| $4$ | $13$ | $Q = 0$ |
| $5$ | $8$ | $N \le 16$ |
| $6$ | $18$ | $N \le 3 000$ |
| $7$ | $24$ | 无 |


title: [语言月赛202305] 排排队，做游戏

type: B

description:
$n$ 名小朋友站成了一排，他们会按照体育老师的指令进行排队做游戏。

体育老师会向他们依次下发 $T$ 条指令，每条指令包含一个小于等于 $n$ 的正整数 $k$。

对某一条指令，小朋友们会按照如下步骤进行排队：

1. 该指令下发前，排在从左到右数第 $1, k + 1, 2k + 1, \cdots$ 位的小朋友，在指令下发后应该依次站在从左到右第 $1, 2, \cdots$ 个位置。
2. （如果 $k \geq 2$）该指令下发前，排在从左到右数第 $2, k + 2, 2k + 2, \cdots$ 位的小朋友，在指令下发后应该依次站在第一步中的小朋友（原来从左到右数第 $1, k + 1, 2k + 1, \cdots$ 位的小朋友）右边的第 $1, 2, \cdots$ 个位置。
3. （如果 $k \geq 3$）$3, k + 3, 2k + 3, \cdots$ 的小朋友站在第二步的小朋友右边，（如果 $k \geq 4$）$4, k + 4, 2k + 4, \cdots$ 的小朋友站在 $3, k + 3, 2k + 3, \cdots$ 的小朋友右边，以此类推，直至所有小朋友都被安排过（无论位置是否有变化）。

我们依次给出初始时从左到右每个小朋友的学号 $a _ 1, a _ 2, \cdots, a _ n$。现在我们想要知道，在 $T$ 次指令下发后，从左到右每个小朋友的学号依次是什么。

inputFormat:
输入共三行。

第一行为两个整数 $n, T$，代表小朋友的数量和指令数。
第二行为 $n$ 个整数 $a _ 1, a _ 2, \cdots, a _ n$，代表初始时从左到右每个小朋友的学号。
第三行为 $T$ 个整数，代表体育老师下发的 $T$ 条指令。

outputFormat: 输出共一行 $n$ 个整数，代表在 $T$ 次指令下发后，从左到右每个小朋友的学号。


title: [语言月赛202305] 制糊串

background: 在这个问题中，我们用 $s[x,y]$ 表示从字符串 $s$ 的第 $x$ 个字符到第 $y$ 个字符连起来构成的字符串。例如，若 $s = \texttt{abcdef}$，则 $s[2,4] = \texttt{bcd}$。

description:
给出两个字符串 $s$ 和 $t$，有 $q$ 次询问。

每次给出 $l_1, r_1$ 和 $l_2, r_2$，请判断 $s[l_1, r_1]$ 和 $t[l_2, r_2]$ 谁的字典序更小。

inputFormat:
第一行是一个字符串 $s$。
第二行是一个字符串 $t$。
第三行是一个整数，表示询问次数 $q$。
接下来 $q$ 行，每行四个整数 $l_1, r_1, l_2, r_2$，表示一次询问。

outputFormat:
对每次询问，输出一行一个字符串：

- 如果 $s[l_1, r_1]$ 的字典序更小，请输出 $\texttt{yifusuyi}$。
- 如果 $t[l_2, r_2]$ 的字典序更小，请输出 $\texttt{erfusuer}$。
- 如果两者的字典序一样大，请输出 $\texttt{ovo}$。

samples:
Yifusuyi
yifusuYi
3
1 2 7 8
1 2 1 2
7 8 7 8

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

以下用 $|s|$ 表示 $s$ 的长度，$|t|$ 表示 $t$ 的长度。

- 对 $30\%$ 的数据，$|s| = |t| = 1$。
- 对 $60\%$ 的数据，$q = 1$。
- 对 $100\%$ 的数据，$1 \leq |s|, |t|, q \leq 10^3$，$1 \leq l_1 \leq r_1 \leq |s|$，$1 \leq l_2 \leq r_2 \leq |t|$。输入字符串仅含大小写英文字母。


title: [语言月赛202305] Numeric Hack

background:
这是一道 **hack 题**。在本题目中，你将得到一个问题和一个解决对应问题的代码，但是给出的代码不能对于某些输入给出正确的输出。不能给出正确的输出的情况包括：

1. 输出错误的结果。
2. 运行超时。
3. 产生一些运行时未定义行为。目前技术可检测的未定义行为仅包括数组越界。

对于这一问题，你需要提交一份符合要求的输入数据，使得给定的代码不能给出正确的输出。你可以直接使用『提交答案』功能，也可以提交一份以任何语言写成的数据生成器。

---
**提示：如果你使用提交答案功能，请在提交其他题目时记得将语言改回你所使用的语言。**

description:
以下给出这道题目的叙述：

给定三个整数 $n, k, d$，请你找到一个最小的整数 $n'$，使得 $n' > n$ 且 $n' \bmod k = d$。

这里的 $d$ 是非负整数。也就是说，你需要保证 $n' = ak + d$，其中 $a$ 是一个整数，$d \geq 0$。

inputFormat: 输入共一行三个整数 $n, k, d$。

outputFormat: 输出一行一个整数，代表满足 $n' > n, n' \bmod k = d$ 的最小的 $n'$。

hint:
### 样例组与实际输入的说明

如果你直接采用『提交答案』的方式，请将输入数据命名为 `1.in`，并打成 zip 压缩包进行提交。但是由于不稳定因素，我们**不推荐**使用这种方式进行提交。

如果你采用提交数据生成器的方式，你的生成器应当**输出对应的输入数据**。

显然，你的程序不应该读入『输入格式』里提到的任何内容（而应该构造它们），也不应该输出『样例输出』里提到的任何内容（而是只输出你构造的输入数据）。你不应该使用样例测试你的程序，这只是对这一问题的样例说明。

### 数据规模要求

你给出的数据必须满足如下要求：

1. 完全符合『输入格式』的规定，不能有多余的输入，但是可以有行末空格和文末回车。
2. 数据中所有的数字都应为整数。
3. $|n| \leq 10 ^ 4$，$0 \leq d < k \leq 10 ^ 4$。

### 目标代码

你需要 hack 如下的代码：

```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, k, d;
	cin >> n >> k >> d;
	++n;
	if (n % k == d) {
		cout << n << endl;
		return 0;
	}
	if (n % k < d) {
		n += (d - n % k);
	} else {
		n += (k + d - n % k);
	}
	cout << n << endl;
	return 0;
}
```

目标代码的编译选项为 `-std=c++14 -fno-asm -O2`。编译器为洛谷提供的 g++。你可以在『在线 IDE』中选择 C++14 语言来获得完全相同的编译环境。

### 判分说明

本题仅有一个测试点对应一个问题，hack 成功则对应测试点返回 accepted。

#### 数据判定

你给出的数据必须完全符合『数据规模要求』，否则将得到 Unaccepted 的结果。

#### 超时判定

程序每执行若干条指令，我们会检测一遍程序的运行时间。我们保证两次检测之间的指令条数是一个输入规模无关的量，也即每执行 $O(1)$ 条指令会进行一次检测。且两次检测之间的指令条数不会太多，一般不超过 $100$ 条 C++ 语句。

如果程序的运行时间超过 $500 \text{ms}$，则判定为程序运行超时，返回 accepted 结果。

#### 结果错误判定

如果程序在规定的时间内结束且给出了一个输出，我们会比较这个输出和**完全正确的输出**，如果二者不同，则判定为 hack 成功，返回 accepted 结果。

#### 未定义行为判定

我们会在每次**显式**的调用数组元素前判断数组下标是否超过数组范围，如果超过，则判定为 hack 成功，返回 accepted 结果。

这就是说，如果你希望通过未定义行为进行 hack，只能对显式的调用数组元素的行为进行 hack。

### 关于评测信息的说明

如果 hack 成功，对应测试点的信息为 accepted。如果返回其他信息，说明程序本身有误。

例如，如果返回 TLE，不代表成功的将对应程序 hack 至超时，而是表示数据生成器本身运行超时，测试点不得分。

特别的，返回 UKE 结果可能是数据不合法（有多余内容、缺少内容或数据范围不符合要求）。


title: [语言月赛202305] 超链接

description:
在某局域网中，一共有 $N$ 个网页，依次从 $1$ 编号到 $N$。

每个网页上都有一些超链接，第 $i$ 个网页上一共有 $T_i$ 个超链接，依次指向 $A_{i,1},\cdots,A_{i,T_i}$ 号网页。

某 E 现在从 $1$ 号网页开始，点击不超过两次超链接，一共能到达多少网页？

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

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

接下来第 $i$ 行，第一个数为 $T_i$。接下来 $T_i$ 个数，每个数代表一个超链接指向的网页。

outputFormat: 输出一行一个整数，代表你的答案。

hint:
### 样例解释

 - 点击 $0$ 次：$1$ 号页面；
 - 点击 $1$ 次：$2,3$ 号页面；
 - 点击 $2$ 次：$1, 2, 3, 4,5$ 号页面。

共 $5$ 个页面。

### 数据规模与约定

 - 对于 $30\%$ 的测试数据，$T_i = 1$;
 - 对于 $100\%$ 的测试数据，$1 \le N \le 1000$，$0 \le T_i \le 100$，$1 \le A_{i,j} \le N$，同一个网页中不同超链接指向的网页编号不同，不保证不存在指向自己的超链接。


title: [语言月赛202306] 教学楼

description:
zyl 来到新的学校。学校很大，他想找到自己的教室在哪栋楼。

zyl 的班主任告诉了他教室在几楼，但学校有三座教学楼：图书馆，综合楼，艺术楼。这三栋教学楼的最高楼层数分别为 $3, 5, 9$。

zyl 得知，他想要找的教室在这座三栋教学楼中的一栋中。同时，zyl 掌握了如下信息：

- 教室所在的楼层数 $n$。
- 三栋楼的**人流量** $a, b, c$（保证 $a, b, c$ 两两不同）。

显然，教室所在的楼层数一定**不大于**其所在的教学楼的最高楼层数。在满足该条件的基础上，他又得知，教室处在所有可能的教学楼中**人流量最小**的一栋。

现在，请你按照上述条件，帮助他找出他的教室处在哪栋教学楼。

inputFormat:
输入共两行。

第一行一个整数 $n$，表示教室所在的楼层数。

第二行三个整数 $a, b, c$，分别代表图书馆，综合楼，艺术楼的人流量。

outputFormat:
输出共一行一个字符串，表示教室所在的教学楼。

其中，`library` 表示图书馆，`comprehensive` 表示综合楼，`art` 代表艺术楼。

hint:
### 样例 1 解释

教室在 $4$ 楼，图书馆的最高楼层为 $3$，因此教室不可能在图书馆。而剩下两栋楼中，综合楼的人流量较小，所以教室在综合楼。

### 数据规模与约定

- 对于 $40\%$ 的数据，$n\le3$。
- 对于 $100\%$ 的数据，$1\leq n \leq 9$，$0\leq a,b,c\leq 20000$，且 $a,b,c$ 互不相同。


title: [CCC 2008 J4] From Prefix to Postfix

description:
Prefix notation is a non-conventional notation for writing arithmetic expressions. The standard way of writing arithmetic expressions, also known as infix notation, positions a binary operator between the operands, e.g., $3 + 4$, while in prefix notation the operator is positioned before the operands, e.g., $+$ $3$ $4$. Similarly, the prefix notation for $5$ $-$ $2$ is $-$ $5$ $2$. A nice property of prefix expressions with binary operators is that parentheses are not required since there is no ambiguity about the order of operations. For example, the prefix representation of $5 - (4 - 2)$ is $-5$ $-$ $4$ $2$, while the prefix representation of $(5 - 4) - 2$ is $-$ $-$ $5$ $4$ $2$. The prefix notation is also known as Polish notation, due to Jan Łukasiewicz, a Polish logician, who invented it around $1920$.

Similarly, in postfix notation, orreverse Polish notation, the operator is positioned after the operands.

For example, postfix representation of the infix expression $(5 - 4) - 2$ is $5$ $4$ $-$ $2$ $-$. Your task is to write a program that translates a prefix arithmetic expression into a postfix arithmetic expression.

inputFormat: Each line contains an arithmetic prefix expression. The operators are $+$ and $-$, and numbers are all single-digit decimal numbers. The operators and numbers are separated by exactly one space with no leading spaces on the line. The end of input is marked by $0$ on a single line. You can assume that each input line contains a valid prefix expression with less than $20$ operators.

outputFormat: Translate each expression into postfix notation and produce it on a separate line. The numbers and operators are separated by at least one space. The final $0$ is not translated.

translation:
给定一个前缀表达式，请你将其转换为一个逆波兰表示法。

每个表达式运算符个数小于等于 $20$。

以下是前缀表达式和逆波兰表达式的范例：

在书写正常算式 $(5 - 4) - 2$ 时，如果要将其改成前缀表达式，就是 $-$ $-$ $5$ $4$ $2$，而改写成逆波兰表达式，就是 $5$ $4$ $-$ $2$ $-$。

注意本题有多组数据，每次当你读入到 $0$ 时，视为结束程序。


title: [语言月赛202306] 教室

description:
zyl 来到了新教室，数学老师想让他帮忙摆桌子。

老师要求桌子的总数和学生的总数一样多，但是 zyl 不知道班级中一共有多少名学生。

在教室的后面有 $n$ 个柜子，编号为 $1\sim n$，第 $i$ 个柜子由 $a_i\times b_i$ 个格子组成，且每个格子都被 $c_i$ 个学生共同使用。一个学生**会且只会**使用一个柜子中的一个格子。也就是说，第 $i$ 个柜子会有 $a_i\times b_i \times c_i$ 名学生使用。

通过这些信息，zyl 就能够算出**学生总数**了。

现在要把桌子排成 $m$ 列，要求尽量把桌子摆成一个整齐的矩形，即，尽量保证每一列的桌子一样多。但如果最后多出几张桌子无法组成完整的一排，就将这些桌子在原最后一排的后面摆成新的一排。

zyl 想要知道，所有的桌子摆好后，一共有多少排，最后一排又有多少张桌子。

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

第一行两个整数 $n,m$，分别表示柜子的个数和桌子的列数。
接下来 $n$ 行，每行三个整数 $a_i,b_i,c_i$，描述第 $i$ 个柜子的信息。

outputFormat: 输出共一行两个整数，分别表示摆完桌子后的总排数和最后一排的桌子数量，用空格隔开。

hint:
### 样例 1 解释
第 $1$ 个柜子有 $2$ 行 $3$ 列，每个格子被 $3$ 个同学使用，故这个柜子一共有 $6$ 个格子，有 $18$ 名同学使用这个柜子。

同理可得后两个柜子分别有 $12$ 名、$20$ 名同学使用，故一共有 $50$ 名同学，代表班级中有 $50$ 张桌子。

桌子需要摆成 $8$ 列，首先每一列摆 $6$ 个桌子，此时桌子有 $6$ 排。其次，剩下 $2$ 张桌子放在第 $6$ 排的后面，组成第 $7$ 排，这样一共有 $7$ 排桌子，第 $7$ 排有 $2$ 张桌子。

### 数据规模与约定

对于 $40\%$ 的数据，保证桌子按要求能恰好构成一个矩形。

对于 $100\%$ 的数据，$1\leq n\leq 100$，$1\leq
a_i,b_i,c_i\leq 10$，$1\leq m\leq 50$。


title: [语言月赛202306] 演唱会

description:
一个特殊的节日，zyl 举办了一场演唱会，他想要规划一下演唱会的曲目。

根据同学的要求，他要从 $n$ 首歌（编号 $1\sim n$）中选出 $m$ 首加入演唱会歌单。

选择的规则很简单，班上有 $a$ 名学生（不包括 zyl），学号为 $1\sim a$。zyl 会按照学号统计每位同学从每首歌中得到的快乐值，记为 $h_{i,j}$。一首歌的「欢乐度」是它所给予其他所有同学的「快乐值」总和。

巧妙的是，由于歌曲风格迥异，**同一个学生一定会从不同的歌中会收获不同的快乐值，且不会有任何两首歌的欢乐度相同**。

zyl 选出欢乐度最高的 $m$ 首歌，并将它们按欢乐度**从大到小**排好序。

但 zyl 注意到了她的快乐值...

无论如何，zyl 一定会把她最喜欢的歌放进歌单（她获得快乐值最高的歌即为她最喜欢的歌）！
如果她最喜欢的歌之前已经在歌单中，那么 zyl 会把这首歌提到歌单的第一个位置（即，仅将该歌曲的位置变为第一位，其余歌曲的相对位置不变）；但如果不在，zyl 则会把已经选择好的歌单里的最后一首歌给删掉。然后把她最喜欢的曲目放在歌单的最后。

现在 zyl 将统计的快乐值数据和她的学号交给你，请你帮他列出演唱会的歌单。

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

第一行共四个整数 $n, m, a, b$，分别代表待选的歌的数量，需要选出的歌的数量，班上的人数，她的学号。
接下来 $a$ 行，每行 $n$ 个整数，第 $i+1$ 行第 $j$ 个数代表学号为 $i$ 的学生从第 $j$ 首歌收获的快乐值 $h_{i,j}$。

outputFormat: 输出共一行用空格隔开的 $m$ 个整数，依次代表演唱会的歌单上的歌的编号。


title: [JOI 2023 Final] Advertisement 2

description:
There are $N$ residents in JOI Kingdom, numbered from $1$ to $N$. Resident $i$ ($1\le i\le N$) lives at the coordinate $X_i$ on the real line, and its **power of influence** is $E_i$. It may be the case that more than one residents live at the same coordinate. A resident with a large power of influence has a high advertising potential. But such a resident is careful in buying books.

Rie published a book on informatics. In order to encourage many people to buy copies of the book, she can donate copies of the book to some residents. If she donates a copy of the book to Resident $i$ ($1\le i\le N$), Resident $i$ will get a copy of Rie’s book. Moreover, among the residents who did not yet get copies of the book, every resident $j$ ($1\le j\le N$) satisfying the following condition will buy a copy of the book and get it.

-  The distance between Resident $i$ and Resident $j$ on the real line is less than or equal to $E_i - E_j$. In other words, $|X_i − X_j| \le E_i − E_j$ is satisfied.

If all the residents read Rie’s book, the Olympiads in Informatics will be greatly recognized. Write a program which calculates the minimum number of residents who will be donated copies of Rie’s book so that all the residents in JOI Kingdom will get copies of Rie’s book.

inputFormat:
Read the following data from the standard input.

> $N$
> $X_1$ $E_1$
> $X_2$ $E_2$
> $\vdots$
> $X_N$ $E_N$

outputFormat: Write one line to the standard output. The output should contain the minimum number of residents who will be donated copies of Rie’s book.

translation:
JOI 王国有 $N$ 位居民，从 $1$ 到 $N$ 编号。居民 $i$（$1\le i\le N$）居住在数轴上坐标 $X_i$ 处，其**影响力**为 $E_i$。同一个坐标可能住了多于一位居民。居民的影响力越高，广告效应也越高，但买书也越谨慎。

Rie 出版了一本关于信息学的书。为了让更多人购买这本书，她可以给一些居民送书。如果她给居民 $i$（$1\le i\le N$）送了一本书，除了居民 $i$ 将得到一本 Rie 的书外，在还没有得到这本书的居民中，每一个满足以下条件的居民 $j$（$1\le j\le N$）都会购买这本书：

- 居民 $i$ 和 居民 $j$ 在数轴上的距离小于或等于 $E_i - E_j$。换句话说，$|X_i - X_j| \le E_i - E_j$ 成立。

如果所有的居民都读了 Rie 的书，信息学竞赛将得到极大的认可。请写一个程序，计算 Rie 最少将书赠送给多少位居民，就可以让 JOI 王国的所有居民都会得到 Rie 的书。

hint:
## Samples

### Sample 1

For example, if Rie donates copies of the book in the following way, all the residents in JOI Kingdom will get copies of Rie’s book.

- Rie donates a copy of the book to Resident 3.
  - Since $|X_3 - X_1| = 1$ and $E_3 - E_1 = 2$, Resident 1 will buy a copy of Rie’s book and get it.
  - Since $|X_3 - X_2| = 1$ and $E_3 - E_2 = 1$, Resident 2 will buy a copy of Rie’s book and get it.
  - Since $|X_3 - X_4| = 3$ and $E_3 - E_4 = -1$, Resident 4 will not buy a copy of Rie’s book.
  Therefore, Residents 1, 2, 3 will get copies of Rie’s book.
- Rie donates a copy of the book to Resident 4. Since all the residents except Resident 4 already got copies of Rie’s book, all the residents in JOI Kingdom finally get copies of Rie’s book.

Since it is impossible to donate copies of the book to less than two residents so that all the residents in JOI Kingdom will get copies of Rie’s book, output 2.

This sample input satisfies the constraints of Subtasks 2, 3, 4.

### Sample 2

This sample input satisfies the constraints of all the subtasks.

### Sample 3

This sample input satisfies the constraints of Subtasks 2, 3, 4.

## Constraints

- $1\le N\le 5\times 10^5$.
- $1\le X_i\le 10^9$ ($1\le i\le N$).
- $1\le E_i\le 10^9$ ($1\le i\le N$).
- Given values are all integers.

## Subtasks

1. (10 points) $E_1=E_2=\cdots=E_N$.
2. (23 points) $N\le 16$.
3. (36 points) $N\le 10^3$.
4. (31 points) No additional constraints.


title: [JOI 2023 Final] Maze

description:
President K loves solving mazes. He found cells from which he may create a maze. The cells are rectangular grid with $R$ horizontal rows and $C$ vertical columns. Each cell is colored either white or black. The cell in the $i$-th row ($1 \leqslant i \leqslant R$) from the top and the $j$-th column ($1 \leqslant j \leqslant C$) from the left is called Cell $(i, j)$.

President K will solve the maze under the condition that he can pass the white cells, but he cannot pass the black cells. More precisely, he will solve the maze in the following way.

1. Among the white cells, he will choose Cell $(S_r, S_c)$, which is the starting cell of the maze, and Cell $(G_r, G_c)$, which is the goal cell of the maze.
2. It is possible to move from one cell to another white cell which is adjacent to the current cell in one of the four directions (top, bottom, left, or right). By repeating this, he will find a path from the starting cell to the goal cell.

President K already fixed the starting cell and the goal cell. However, he noticed that in some situations of the colors of the cells, there might not be a path from the starting cell to the goal cell consisting of white cells only. He has a stamp of size $N \times N$. He will perform the following **Operations** several times so that there will be a path from the starting cell to the goal cell consisting of white cells only.

**Operation.** He chooses a square region of $N \times N$ cells, and paint the cells in the region white. More precisely, he chooses integers $a, b$ satisfying $1 \leqslant a \leqslant R - N + 1$ and $1 \leqslant b \leqslant C − N + 1$, and for every pair $(i, j)$ of integers satisfying $a \leqslant i \leqslant a + N − 1$ and $b \leqslant j \leqslant b + N − 1$, he paints Cell $(i, j)$ white.

Since his hands becomes dirty if he uses the stamp, he wants to minimize the number of operations. Given
information of the colors of the cells, the size of the stamp, and the locations of the starting cell and the goal cell, write a program which calculates the minimum number of operations he has to perform so that there will be a path from the starting cell to the goal cell consisting of white cells only.

inputFormat:
Read the following data from the standard input.

> $R$ $C$ $N$
$S_r$ $S_c$
$G_r$ $G_c$
$A_1$
$A_2$
$.$
$.$
$.$
$A_R$

$A_i (1 \leqslant i \leqslant R)$ is a string of length $C$ consisting of `.` or `#`. The $j$-th character ($1 \leqslant j \leqslant C$) of $A_i$ represents the color of Cell $(i, j)$. Its color is white if the character is `.`, and its color is black if the character is `#`.

outputFormat:
Write one line to the standard output. The output should contain the minimum number of operations President
K has to perform so that there will be a path from the starting cell to the goal cell consisting of white cells only.

translation:
给定一张 $R\times C$ 的地图，其中 ```.``` 可以走，而 ```#``` 不能走。一次操作可以将 $N \times N$ 的正方形范围内所有点变成 ```.```，给定起点和终点，求最少需要几次操作使得起点和终点连通（只能上下左右移动）。

$R\times C\le 6\times 10^6$，$N\le R\le C$。

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

If he chooses $(a, b) = (1, 2)$ and perform an operation, Cells $(1, 2), (1, 3), (2, 2), (2, 3)$ become white. Then there will be a path from the starting cell to the goal cell consisting of white cells only. For example, the path $(1, 1) → (1, 2) → (1, 3) → (2, 3) → (2, 4)$ satisfies the condition.

If he does not perform an operation, there is no path from the starting cell to the goal cell consisting of white cells only. Therefore, output $1$.

该样例满足子任务 $2, 3, 4, 5, 6, 7, 8$ 的限制。

#### 【样例解释 #2】

该样例满足所有子任务的限制。

#### 【样例解释 #3】

该样例满足子任务 $2, 3, 4, 5, 6, 7, 8$ 的限制。

#### 【样例解释 #4】

Even if he does not perform an operation, there might be a path from the starting cell to the goal cell consisting of white cells only.

该样例满足所有子任务的限制。

#### 【数据范围】

对于所有测试数据，满足 $1 ≤ N ≤ R ≤ C$, $R × C ≤ 6 \times 10^6$, $1 ≤ S_r ≤ R$, $1 ≤ S_c ≤ C$, $1 ≤ G_r ≤ R$, $1 ≤ G_c ≤ C$, $(S_r, S_c) \neq (G_r, G_c)$.

保证 $A_i (1 ≤ i ≤ R)$ 是一个长为 $C$ 且只由 `.` 或 `#` 构成的字符串。保证格子 $(S_r, S_c)$ 与格子 $(G_r, G_c)$ 均为白色。

保证 $R, C, N, S_r, S_c, G_r, G_c$ 均为整数。

| 子任务编号 | 分值 | 限制 |
| :-: | :-: | :-: |
| $1$ | $8$ | $N = 1, R × C ≤ 1.5 \times 10^6$ |
| $2$ | $19$ | $R × C ≤ 10^3$ |
| $3$ | $16$ | 答案不超过 $10$, $R × C ≤ 1.5 \times 10^6$ |
| $4$ | $19$ | $R × C ≤ 6 \times 10^4$ |
| $5$ | $5$ | $R × C ≤ 1.5 \times 10^5$ |
| $6$ | $19$ | $R × C ≤ 1.5 \times 10^6$ |
| $7$ | $8$ | $R × C ≤ 3 \times 10^6$ |
| $8$ | $6$ | 无 |


title: [语言月赛202306] 课桌

description:
自习课上，同学们可以适当地互相换座位。zyl 想要换到她的后面一排……

可是，想要换到那里，需要**依次**和 $n$ 个同学换座位。同学们的课桌上都摆着若干本书。与一个同学换座位，需要把双方课桌上的书调换位置。

zyl 自己有 $x$ 本书。他每和一个人换座位，都会把双方课桌上的书调换位置，消耗**双方书数量之和**的体力。

请你求出，他最后消耗的体力的总和。

inputFormat:
输入共两行。

第一行两个整数 $n, x$，分别表示 zyl 换座位的路上需要经过的课桌数量和 zyl 自己课桌上的书的数量。
第二行 $n$ 个整数 $a_1, a_2, \cdots, a_n$，表示 zyl 换座位路上遇到的课桌上书本的数量。

outputFormat: 共一行一个整数，表示 zyl 消耗的体力值。

hint:
### 样例 1 解释
和第一个同学换座位，花费 $3+1=4$ 体力值，
和第二个同学换座位，花费 $3+3=6$ 体力值，
和第三个同学换座位，花费 $3+2=5$ 体力值，
和第四个同学换座位，花费 $3+4=7$ 体力值。

总共花费 $4+6+5+7=22$ 体力值。

### 数据范围与约定
设同学桌上书本的总数为 $s$，即 $s = a_1 + a_2 + a_3 + \dots a_n$。

- 对于 $60\%$ 的数据，满足 $n\leq 1000$，$x \leq 100$，$1\le a_i,s \leq 10^7$。
- 对于 $100\%$ 的数据，满足 $1\leq n\leq 2\times10^{6}$， $1\leq x \leq 10^{4}$，$1\leq a_i,s\leq 2\times10^{9}$。


title: [POI 2020/2021 R3] Droga do domu

background:
译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Droga do domu](https://szkopul.edu.pl/problemset/problem/ZfS_tobZ_7xdR6D5s6Tegur3/statement/)。

d1t1。

description:
$n$ 个点，$m$ 条边，无重边自环，边有长度。

$1$ 号点是学校，$n$ 号点是家。

$s$ 条公交线路。公交逢点必停，且一个点不会停两次。在一条边上行驶的时间就是它的长度。给定了第一班公交发车时间和发车间隔。

在时刻 $t$ 从学校出发，至多换乘 $k$ 次，求最早什么时候到家。

只计算路上时间和等车时间。换乘时间不计。

inputFormat:
第一行：五个整数 $n,m,s,k,t$。

接下来 $m$ 行：每行三个整数 $a,b,c$，表示有一条边连接 $a,b$，长度为 $c$。

接下来 $2s$ 行：每两行描述一条公交线路：

- 第一行三个整数 $l,x,y$，表示它共停靠 $l$ 个点，第一班在时刻 $x$ 发车，每两班之间时间间隔为 $y$。
- 第二行 $l$ 个整数 $v_1,\dots,v_l$，依次为它停靠的 $l$ 个点。

outputFormat:
一行一个整数，答案。

如果不能到家，那么输出一行一个字符串 `NIE`。


title: [KMOI R1] 五五五五（Easy）

background: “迟序之数，非出神怪，有形可检，有数可推。”——祖冲之

description:
小宋有一个序列 $a_1,a_2\dots,a_n$，其中对于 $i\in [1,n]$，满足 $a_i\in[0,9]$。

对于 $1\le l\le r\le n$，他记 $f(l,r)$ 等于 $\overline{a_la_{(l+1)}\dots a_r}$ 的末尾连续 $5$ 的个数。

例如：对于序列 $a=\{1,1,4,5,1,4\}$，$f(2,4)=1,f(1,3)=0$。

现在请你求出:

$$\Big(\sum\limits_{l=1}^
{n}\sum\limits_{r=l}^{n} f(l,r)\Big) \bmod 10^9+7$$

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

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示序列 $a$。

outputFormat: 一个正整数 $ans$，表示答案。


title: [JOI 2023 Final] Stone Arranging 2

description:
JOI-kun has $N$ go stones. The stones are numbered from $1$ to $N$. The color of each stone is an integer between $1$ and $10^9$, inclusive. In the beginning, the color of Stone $i$ ($1 \le i \le N$) is $A_i$.

From now, JOI-kun will perform $N$ operations. He will put the stones on the table in a line. The operation $i$ ($1 \le i \le N$) will be performed as follows:

1. JOI-kun will put Stone $i$ on the immediate right of Stone $i - 1$. However, when $i = 1$, JOI-kun will put Stone 1 on the table.
2. If there is a stone among Stones $1,2,\cdots,i-1$ whose current color is the same as Stone $i$, let $j$ be the maximum index of such stones, and JOI-kun will paint all of Stones $j+1,j+2,\cdots,i-1$ with the color $A_i$.

In order to confirm whether the operations are correctly performed, JOI-kun wants to know in advance the colors of the stones after all the operations are performed.

Given information of the go stones, write a program which determines the colors of the stones after the $N$ operations are performed.

inputFormat:
Read the following data from the standard input.

> $N$
> $A_1$
> $A_2$
> $\vdots$
> $A_N$

outputFormat: Write $N$ lines to the standard output. The $i$-th line ($1 \le i \le N$) should contain the color of Stone $i$ after the $N$ operations are performed.

translation:
JOI 君有 $N$ 枚棋子，棋子从 $1$ 到 $N$ 编号。每个棋子的颜色是介于 $1$ 和 $10^9$ 之间的整数，包括 $1$ 和 $10^9$。一开始，第 $i$（$1 \le i \le N$）枚棋子的颜色是 $A_i$。

接下来，JOI 君将执行 $N$ 步操作。他将把棋子放在桌子上排成一行。第 $i$（$1 \le i \le N$）步操作如下：

1. JOI 君会将第 $i$ 枚棋子放在第 $i - 1$ 枚棋子的紧邻的右侧。 特别地，当 $i = 1$ 时，JOI 君会直接将第 1 枚棋子放在桌子上。
2. 如果前 $i-1$ 枚棋子中有至少一枚棋子当前的颜色与棋子 $i$ 相同，设 $j$ 为这些棋子的编号的最大值，那么 JOI 君会把第 $j+1,j+2,\cdots,i-1$ 枚棋子的颜色都涂成 $A_i$。

为了确认操作有没有正确完成，JOI 君想提前知道所有操作完成后棋子的颜色。

给定棋子的信息，编写一个程序，确定在执行 $N$ 次操作后每枚棋子的颜色。

hint:
## Samples

### Sample 1

The operations are performed as in the following table.

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

Finally, the colors of Stones 1, 2, 3, 4, 5, 6 will be 1, 1, 1, 2, 2, 2, respectively.

This sample input satisfies the constraints of Subtasks 1, 3.

### Sample 2

This sample input satisfies the constraints of all the subtasks.

## Constraints

- $1 \le N \le 2\times 10^5$.
- $1 \le A_i \le 10^9$ ($1 \le i \le N$).
- Given values are all integers.

## Subtasks

1. (25 points) $N \le 2 000$.
2. (35 points) $A_i \le 2$ ($1 \le i \le N$).
3. (40 points) No additional constraints.


title: [JOI 2023 Final] Cat Exercise

description:
There are $N$ cat towers, numbered from $1$ to $N$. The height of Tower $i$ ($1 \le i \le N$) is $P_i$. The heights of the towers are distinct integers between $1$ and $N$, inclusive. There are $N - 1$ adjacent pairs of towers. For each $j$ ($1 \le j \le N - 1$), Tower $A_j$ and Tower $B_j$ are adjacent to each other. In the beginning, it is possible to travel from a tower to any other tower by repeating moves from towers to adjacent towers.

In the beginning, a cat stays in a tower of height $N$.

Then we perform **cat exercises**. In cat exercises, we repeatedly choose a tower and put an obstacle on it. However, we cannot put an obstacle on a tower where we already put an obstacle on it. During the process, the following will happen.

- If the cat does not stay in the chosen tower, nothing will happen.
- If the cat stays in the chosen tower and there is an obstacle on every tower which is adjacent to the chosen tower, the cat exercises will finish.
- Otherwise, among the towers where the cat can arrive by repeating moves from towers to adjacent towers without obstacles, the cat will move to the highest tower except for the current tower by repeating moves from towers to adjacent towers. In this process, the cat takes the route where the number of moves from towers to adjacent towers becomes minimum.

Given information of the heights of the towers and pairs of adjacent towers, write a program which calculates the maximum possible sum of the number of moves of the cat from towers to adjacent towers if we put obstacles suitably.

inputFormat:
Read the following data from the standard input.

> $N$
> $P_1$ $P_2$ $\cdots$ $P_N$
> $A_1$ $B_1$
> $A_2$ $B_2$
> $\vdots$
> $A_N$ $B_N$

outputFormat: Write one line to the standard output. The output should contain the maximum possible sum of the number of moves of the cat from towers to adjacent towers.

translation:
有 $N$ 个猫爬架，编号从 $1$ 到 $N$。第 $i$（$1 \le i \le N$）个架子的高度是 $P_i$。架子的高度是 $1$ 和 $N$ 之间的不同整数，包括 $1$ 和 $N$。有 $N - 1$ 对架子彼此相邻。对于每个 $j$（$1 \le j \le N-1$），第 $A_j$ 个架子和第 $B_j$ 个架子彼此相邻。从任意一个架子开始，总能通过不断移动到相邻的架子来到达所有其它架子。

一开始，一只猫待在高度为 $N$ 的那个架子中。

接下来对这只猫进行锻炼。在锻炼中，我们每次选择一个架子并在其上放置障碍物。但是，我们不能在已经放置障碍物的架子上再放置障碍物。在此过程中，会发生以下情况。

- 如果猫不待在选定的架子中，则什么也不会发生。
- 如果猫待在选定的架子中，并且与选定架子相邻的每个架子上都有障碍物，则锻炼结束。
- 否则，猫将沿最短路径前往，仅通过移动到相邻的架子且不经过放置过障碍物的架子，能到达的所有架子中，高度最高的那个。

给定每个架子的高度和架子彼此相邻的方式，编写一个程序，计算如果我们适当放置障碍物，猫最多需要移动多少次。从一个架子移动到相邻的架子被称为一次移动。

hint:
## Samples

### Sample 1

If we perform the cat exercises in the following way, the cat moves 3 times in total.

- We put an obstacle on Tower 1. The cat does not move.
- We put an obstacle on Tower 2. The cat moves from Tower 2 to Tower 3. Then, the cat moves from Tower 3 to Tower 4.
- We put an obstacle on Tower 4. The cat moves from Tower 4 to Tower 3.
- We put an obstacle on Tower 3. Then the cat exercises finish.

Since there is no way to perform cat exercises where the cat moves more than or equal to 4 times from towers to adjacent towers, output 3.

This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 5, 7.

### Sample 2

This sample input satisfies the constraints of Subtasks 4, 6, 7.

## Constraints

- $2 \le N \le 2\times 10^5$.
- $1 \le P_i \le N$ ($1 \le i \le N$).
- $P_i \neq P_j$ ($1 \le i < j \le N$).
- $1 \le A_j < B_j \le N$ ($1 \le j \le N - 1$).
- In the beginning, it is possible to travel from a tower to any other tower by repeating moves from towers to adjacent towers.
- Given values are all integers.

## Subtasks

1. (7 points) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$), $N \le 16$．
2. (7 points) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$), $N \le 300$．
3. (7 points) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$), $N \le 5 000$．
4. (10 points) $N \le 5 000$．
5. (20 points) $A_i = i, B_i = i + 1$ ($1 \le i \le N - 1$)．
6. (23 points) $A_i =\left\lfloor\frac{i+1}2\right\rfloor, B_i = i + 1$ ($1 \le i \le N - 1$). Here $\lfloor x \rfloor$ is the largest integer which is smaller than or equal to $x$.
7. (26 points) No additional constraints.


title: [POI 2020/2021 R3] Les Bitérables

background:
译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Les Bitérables](https://szkopul.edu.pl/problemset/problem/Lpz563_ATiESIrNZxiT5bwIx/statement/)。

d1t2。

description:
有 $t$ 个时刻，第 $i$ 个时刻给出了局面 $p_1,p_2,\dots,p_{s_i}$，表示在数轴的 $(0,d)$ 范围内，有且仅有 $p_1,p_2,\dots,p_{s_i}$ 这些位置上有物品。

在 $0$ 位置和 $d$ 位置有无穷多个物品。

你可以花费一个代价，将一个物品向左移动一个位置或向右移动一个位置。

问你在相邻两个时刻之间，把前一个局面转化为后一个局面，最少需要多少代价。

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

接下来 $n$ 行，每行描述一个时刻的局面，首先是一个非负整数 $s_i$，接下来是 $s_i$ 个正整数，分别为 $p_1,p_2,\dots,p_{s_i}$。保证 $0<p_1<p_2<\dots<p_{s_i}<d$。

outputFormat: $n-1$ 行，每行一个整数，你的答案。


title: [语言月赛202306] 棋

description:
zyl 和「她」在 $n\times m$ 的格子纸上下五子棋。**「她」总是先手**。

现在你会得知以下信息：

- 格子纸的大小 $n, m$，代表棋盘共 $n$ 行 $m$ 列。
- $n$ 个仅由字符 `~`、`*`、`$` 构成的长度为 $m$ 的字符串（即 $n \times m$ 个字符）。对于第 $i$ 个字符串的第 $j$ 个字符，`~` 表示第 $i$ 行第 $j$ 列的格子是空的，`*` 表示「她」已经在这一格落下棋子，`$` 表示 zyl 已经在这一格落下棋子。

类似于五子棋的基本规则，一局棋局由「先手」开始，双方轮流落子。如果有同一行，同一列，或者同一 $45\degree$ 斜对角线有**同一方**的**连续五个**棋子，那这一方便是胜者。

现在，请你以以下方式判断当前的棋局：如果已有一方获胜，请你判断是哪一方获胜。否则，请你判断当前轮到哪一方落子。

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

第一行两个整数 $n,m$，表示格子纸的大小。
接下来 $n$ 行，每行一个长度为 $m$ 的,仅由字符 `~`、 `*`、`$` 组成的字符串，代表棋局的情况。

outputFormat:
输出共一行一个字符串或一个字符，表示棋局的情况。

- 如果已有一方获胜，输出一个字符串 `Pleasing!` 或 `zylwins!`。`Pleasing!` 表示「她」获胜，`zylwins!` 表示 zyl 获胜。
- 否则，输出一个字符 `W` 或 `Z`。`W` 表示当前轮到「她」落子，`Z` 表示轮到 zyl 落子。

hint:
### 样例 1 解释
在第三列有连续的五个 `*`，所以「她」获胜了。

### 数据规模与约定

对于前 $40\%$ 的数据，保证没有任何一方获胜。

对于 $100\%$ 的数据， $5\leq n,m \leq 30$，字符串仅由 `~`、`*`、`$` 组成，而且不会出现任意同一行，同一列或是同一 $45\degree$ 斜对角线上有连续 6 个或以上连续且相同的 `*` 或 `$`，并且最多只有一条连续的 $5$ 个 `*` 或 `$`。 `*` 的总数不小于 `$` 的总数，且至多比 `$` 的总数大 $1$。保证输入的字符串至少存在一个字符 `~`。


title: [POI 2020/2021 R3] Surowa zima

background:
译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Surowa zima](https://szkopul.edu.pl/problemset/problem/QCCQf92wAoWAOoJ3tHoypvp3/statement/)。

d1t3。

description:
有一条长 $l$ 米的道路（数轴）。路上有 $n$ 个充电站。每天整条路上（坐标 $[0,l]$）都会落满雪。

有一台机器能扫雪。充一次电可以扫至多 $k$ 米的雪。扫雪是和移动同时进行的，详见样例解释。机器一秒能移动一米，充电不消耗时间。

简单来说，**移动不扫雪不消耗电，需要一秒；移动并扫雪消耗最大电量的 $\bold{\frac1k}$，需要一秒；扫雪必须移动。**

给出每天机器的初始位置，机器初始没电，问每天清除所有雪的最少时间。终点任意。

带修，即充电站可能损坏或修好（第一天之前都是好的），但保证每天都至少有一个好的充电站（所以不会无解）。

inputFormat:
第一行四个整数 $n,l,k,d$。

第二行 $n$ 个整数 $x_1,x_2,\dots,x_n$，表示充电站的位置，保证 $0\leq x_1<x_2<\dots<x_n\leq l$。

接下来 $3d$ 行，描述 $d$ 天的事件：

- 第一行三个整数 $z,u,p$，分别表示昨晚修好的充电站数量，损坏的数量，和机器的初始位置。
- 第二行 $z$ 个整数，表示被修好的充电站编号。
- 第三行 $u$ 个整数，表示损坏的充电站编号。

outputFormat: $d$ 行，每行一个整数，表示每天的答案。

samples: 见附件 见附件


title: 「NnOI R2-T4」Colorful Days♪

description:
给出如下定义：

1. 定义 $ AB $ 为 $ A $ 数组后拼接 $ B $ 数组。
2. 定义 $ A^{0}=\{\} $（即空数组），且对 $i=1,2,3,\cdots$，$ A^{i}=A^{i-1}A$。
2. 定义 $ \operatorname{LCS}(A,B) $ 为 $ A $ 数组和 $ B $ 数组的**最长公共子序列**长度。

现给定长度为 $ n $ 的数组 $ S $ 和长度为 $ m $ 的数组 $ T $，数组中的数均为正整数。

你现在需要找到最小的非负整数 $k$，使得 $ \operatorname{LCS}(S^k,T) $ 最大。

出题人很仁慈，如果你无法最小化 $k$，你也可以拿到一部分分数。

inputFormat:
第一行四个整数 $ n,m,c_1,c_2 $，后两个整数为输出参数 0 或 1。

第二行 $ n $ 个正整数，代表 $ S $ 数组。

第三行 $ m $ 个正整数，代表 $ T $ 数组。

outputFormat: 输出两个整数 $ c_1 \cdot \operatorname{LCS}(S^k,T)$ 和 $c_2\cdot k$。

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

当 $k = 2$ 时，$S^k = \text{\{23 34 \textcolor{red}{53 23 34} 53\}}$，其中标红的是 $S^k$ 和 $T$ 的最长公共子序列。

**【数据范围】**

**提示：本题开启捆绑测试。**

对于 $ 100\% $ 的数据，保证 $ 1 \le n,m,S_i,T_i \le 10^6 $，$ c_1,c_2 \in \{0,1\} $。

$$
\def\r{\cr\hline}
\def\None{\text{None}}
\def\arraystretch{1.5}
\begin{array}{c|c|c}
\textbf{Subtask} & \textbf{Sp. Constraints} & \textbf{Score}\r
\textsf1& c_1=c_2=0 & 2 \r
\textsf2& n \le 10^3，m \le 10^2 & 8 \r
\textsf3& n \le 10^4，m \le 10^3 & 15 \r
\textsf4& c_2=0 & 15 \r
\textsf5& n,m \le 10^5，S_i,T_i \le 26 & 20 \r
\textsf6& 无特殊限制 & 40 \r
\end{array}
$$

在赛后新添加的 hack 测试点会加入 subtask7。

### 题目来源

| 项目 | 人员 |
|:-:|:-:|
|idea| 船酱魔王 |
|data| 船酱魔王 |
|check| Sudohry |
|solution| 船酱魔王 |


title: [CCC 2008 J5/S5] Nukit

background: 注：J5 与 S5 仅数据范围有所不同，在此选取 S5 的数据范围及数据进行评测。

description:
Canada’s top two nuclear scientists, Patrick and Roland, have just completed the construction of the world’s first nuclear fission reactor. Now it is their job to sit and operate the reactor all day, every day. Naturally they got a little bored after doing this for a while and as a result, two things have happened. First, they can now control the individual reactions that happen inside the reactor. Second, to pass the time, they have invented a new game called Nukit.

At the beginning of Nukit, a number of particles are put in the reactor. The players take alternating turns, with Patrick always going first. When it is a player’s turn to move, they must select some of the remaining particles to form one of the possible reactions. Then those particles are destroyed. Eventually there will be so few particles that none of the reactions can be formed; at this point, the first person who is unable to form a reaction on their turn loses.

In our universe you can assume that there are only $4$ types of particles: `A`, `B`, `C`, `D`. Each reaction is a list of particles that can be destroyed on a single turn. The five reactions are:

$1.$ `AABDD`

$2.$ `ABCD`

$3.$ `CCD`

$4.$ `BBB`

$5.$ `AD`

For example, the first reaction `AABDD` says that it is allowable to destroy two `A`, one `B`, and two `D` particles all at the same time on a turn.

It turns out that, no matter how many particles start off in the reactor, exactly one of Patrick or Roland has a perfect winning strategy. By player $X$ has a perfect winning strategy, we mean that no matter what the other player does, player $X$ can always win by carefully choosing reactions.

For example, if the reactor starts off with one `A`, five `B`, and three `D` particles then Roland has the following perfect winning strategy: “if Patrick forms reaction `BBB` initially, then form reaction `AD` afterward; if Patrick forms reaction AD initially, then form reaction `BBB` afterward.” (The strategy works because either way, on Patrick’s second turn, there are not enough particles left to form any reactions.)

Given the number of each type of particle initially in the reactor, can you figure out who has a perfect winning strategy?

inputFormat: The first line of input contains $n$, the number of test cases $(1 \leq n < 100)$. Each test case consists of $4$ integers separated by spaces on a single line; they represent the initial number of `A`, `B`, `C` and `D` particles. You can assume that there are initially between $0$ and $30$ (inclusive) of each type of particle.

outputFormat: For each test case, output the player who has a perfect winning strategy, either `Roland` or `Patrick`.

translation:
Patrick 和 Roland 在玩一个游戏，它的规则如下：

初始时给你 $4$ 个整数（每个整数的大小都不超过 $30$），依次表示：

- 当前 `A` 字符的个数；
- 当前 `B` 字符的个数；
- 当前 `C` 字符的个数；
- 当前 `D` 字符的个数。

每次操作，可以选择下面 $5$ 个操作方式进行操作：

1. `AABDD`
2. `ABCD`
3. `CCD`
4. `BBB`
5. `AD`

举个例子，当选择了 `AABDD` 时，就说明你想要删除 $2$ 个 `A`，$1$ 个 `B`，$2$ 个 `D`。其他的同理。

但是请注意，**如果当前某个字符数量小于你所要删除的那个字符的数量**，你便不能执行该操作。

如果每个操作都无法执行的话，便视为输掉此游戏。

现在他们想要玩 $n$ 轮游戏 $(1 \leq n < 100)$，每轮游戏 Patrick 先手，Roland 后手。假设两人都足够聪明。如果 Patrick 赢了，输出 `Patrick`，否则输出 `Roland`。

samples:
Roland
Patrick
Roland
Roland
Roland
Patrick

hint:
Partial Explanation for Sample Output:

The first output occurs since Patrick loses immediately, since he cannot form any reaction. (Roland’s perfect winning strategy is “do nothing.”)

The second output occurs since Patrick has the perfect winning strategy “form reaction ABCD,” which makes Roland lose on his first turn.

The third output is explained in the problem statement.


title: [语言月赛202306] 纸条

description:
zyl 桌上有 $n$ 张纸条（编号 $1\sim n$），他要把这些纸条按被写下的时间的前后顺序排好，但是纸条上不会有日期，zyl 需要自己判断。

zyl 可以根据纸条内容的连贯性来确定**紧跟**在一张纸条之后纸条有哪些。同时，他可以通过纸条的破损程度判断内容不连贯的纸条的时间先后顺序。显然，对于一段连贯内容的最后一张纸条，紧跟在它后面的纸条只能通过破损程度来判断。

现在，你会收到按以下规则给出的，每张纸条的信息：

首先，你会得知在这一段连贯内容中紧跟在这张纸条后面的纸条的数量 $m$。

其次，按照时间前后依次告诉你这些纸条的编号。

如果没有「连贯内容中紧跟在后面的纸条」（即在连贯内容的最后一张，$m = 0$），则会按照破损程度给出紧跟它的下一张纸条的编号，如果没有「按照破损程度紧跟它的下一张纸条」，你会得到一个 $-1$ 信号。

**如果对于这一部分理解有困难，可以参照「输入格式」及「样例组」进行理解。**

请你帮助 zyl 将纸条排序，并将这 $n$ 张纸条按时间顺序排序后的编号输出。

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

第一行一个整数 $n$，表示纸条的张数。

第 $2\sim n+1$ 行，第 $i+1$ 行具体内容如下：
第一个整数 $m$，表示在连贯内容内 $i$ 号纸条之后有多少张纸条。
- 如果 $m>0$，则接下来 $m$ 个整数，表示按照时间前后紧跟在 $i$ 号纸条后的纸条编号。
- 如果 $m = 0$，接下来一个整数，表示按照纸条的破损程度，紧跟在 $i$ 号纸条后面的纸条编号。如果其后没有纸条，则该整数为 $-1$。

outputFormat: 输出共一行 $n$ 个整数，表示按时间先后排好序后纸条的编号。

hint:
### 样例 1 解释

纸条 $2,1,3$ 是内容连贯的纸条，纸条 $5,4$ 是另一组内容连贯的纸条。

### 数据规模与约定

对于 $20\%$ 的数据，$n\leq 5$。
对于 $100\%$ 的数据，$0\leq m<n\leq 2\times10^{3}$。


title: [CCC 2008 S1] It’s Cold Here!

description: Canada is cold in winter, but some parts are colder than others. Your task is very simple, you need to find the coldest city in Canada. So, when given a list of cities and their temperatures, you are to determine which city in the list has the lowest temperature and is thus the coldest.

inputFormat: The input is a sequence of city names and temperature values. Temperatures are integer, possibly preceded with a `-` sign. There is a single space between the city name and the temperature. No city name contains any whitespace and is always less than $256$ characters in length. There is at least one city in the list, no more than $10000$ cities, and the last city is always Waterloo. You may assume that the temperature is not less than $-273$ and not more than $200$.

outputFormat:
You are to output the name of the coldest city on a single line with no whitespace before or after
the name. You may assume that there will not be more than one city which is the coldest.

translation:
每个城市都有不同的气温，你想要知道哪个城市的气温最低。

现在你统计了一些城市的气温 $(1 \leq$ 城市数量 $\leq 10000$，$-273 \leq$ 气温 $\leq 200)$，请你实现一个代码，求出气温最低的城市名。

输入的最后一个城市总是 `Waterloo`。

samples:
Saskatoon -20
Toronto -2
Winnipeg -40
Vancouver 8
Halifax 0
Montreal -4
Waterloo -3


title: [CCC 2008 S2] Pennies in the Ring

description: The game “Pennies in the Ring” is often played by bored computer programmers who have gotten tired of playing solitare. The objective is to see how many pennies can be put into a circle. The circle is drawn on a grid, with its center at the coordinate $(0, 0)$. A single penny is placed on every integer grid coordinate (e.g., $(1, 1)$,$(1, 2)$, etc.) that lies within or on the circle. It’s not a very exciting game, but it’s very good for wasting time. Your goal is to calculate how many pennies are needed for a circle with a given radius.

inputFormat: The input is a sequence of positive integer values, one per line, where each integer is the radius of a circle. You can assume the radius will be less than or equal to $25000$. The last integer will be indicated by $0$. You may assume that the grid is large enough for two pennies to be on adjacent integer coordinates and not touch.

outputFormat: You are to output, each on its own line, the number of pennies needed for each circle. You do not need to output $0$ for the last $0$. You may assume that the number of possible pennies is less than $2$ billion (which is only $20$ million dollars: computer scientists have lots of money).

translation:
你在玩一个游戏，它给了你一个圆的半径$(1 \leq $ 半径 $\leq 25000)$。假设圆的圆心是在一个半径 $\times$ 半径的图中的正中间，请你求出，有多少个点是包含在圆内的（当一个点在圆的边上时也算）。

本题有多组数据，当读入到 $0$ 时视为程序结束。


title: [CCC 2008 S3] Maze

description:
In order to make a few dollars, you have decided to become part of a scientific experiment. You are fed lots of pizza, then more pizza and then you are asked to find your way across the city on a scooter powered only by pizza. Of course, the city has lots of intersections, and these intersections are very controlled. Some intersections are forbidden for you to enter; some only let you move north/south as you leave the intersection; others let you move only east/west as you leave the intersection; and the rest let you go in any compass direction (north, south, east or west).

Thankfully your scientific friends have given you a map of the city (on the back of a pizza box), with an arrangement of symbols indicating how you can move around the city. Specifically, there are 4 different symbols on the box:

- The symbol `+` indicates we can move in any direction (north/south/east/west) from this location.

- The symbol `-` indicates we can move only east or west from this location.

- The symbol `|` indicates we can move only north or south from this location.

- The symbol `*` indicates we cannot occupy this location.

Your task is to determine how many intersections you must pass through to move from the northwest corner of the city to the south-east corner of the city.

inputFormat:
The input begins with a number $t (1 \leq t \leq 10)$ on its own line, which indicates how many different cases are contained in this file. Each case begins with a number $r$ on one line, followed by a number $c$ on the next line $(1 \leq r, c \leq 20)$. The next $r$ lines contain $c$ characters, where each character is
one of {`+`, `*`, `-`, `|`}. You may assume the north-west corner of the city can be occupied (i.e., it will not be marked with `*`).

outputFormat: The output will be $t$ lines long, with one integer per line. The integer on line $i (1 \leq i \leq t)$ indicates the minimum number of intersections required to pass through as you move from the north-west corner of the city to the south-east corner of the city. If there is no way to get from the north-west corner to the south-east corner, output $−1$ for that test case.

translation:
一共有 $t(1 \leq t \leq 10)$ 组数据。

对于每组数据，给你一个 $r(1\leq r \leq 20)$ 行 $c(1\leq c \leq 20)$ 列的地图，你需要从地图的左上角，走到地图的右下角。

这个地图不是普通的地图，它并不是随随便便上下左右都能走的，你需要根据该格子上的字符，来对应其能走的方向：

- 为 `+`：上下左右都能走。

- 为 `-`：只能左右移动。

- 为 `|`：只能上下移动。

- 为 `*`：无法移动（不仅在该点无法往上下左右移动，而且甚至**无法到达该点**）。

请你判断它能不能从左上角走到右下角 （保证**左上**角不为 `*`），如果能，输出最小的步数，如果不能，输出 $-1$。

注：初始时在左上角和在右下角结束时都算 $1$ 步。


title: [CCC 2008 S4] Twenty-four

description:
Twenty-four is a popular card game designed to be played by four players. Each player is dealt a deck of cards, which are kept face down. On every turn, each of the four players turns over the top card of his or her deck, so that it is visible to all. The goal is to find an arithmetic expression using the values of the cards (with $A$ meaning $1$, $J$ meaning $11$, $Q$ meaning $12$, and K meaning $13$) that evaluates to the number $24$. For example, for the example in the illustration, one possible expression would be:

$((A \times K) - J) \times Q$

$((1 \times 13) - 11) \times 12$

The first player to find such an expression wins the turn, and adds all four cards to the bottom of his or her deck.

Each valid arithmetic expression must use all four cards, and must combine their values using addition, subtraction, multiplication, or division. Parentheses are allowed to specify precedence of operations. Juxtaposing cards to make multiple-digit decimal numbers is not allowed (e.g. you cannot place the cards $2$ and $4$ beside each other to make $24$). Non-integer quotients of division are also not allowed, even as a partial result (of a subexpression of the overall expression).

In some cases, the players may take a very long time to find an expression evaluating to $24$. In fact, in some cases, no such expression exists. Your task is to determine, given four cards, an expression that evaluates to the largest number less than or equal to $24$.

inputFormat: The first line contains an integer $1 \leq N \leq 5$ indicating the number of card hands that follow. Each hand consists of four lines. Each of these lines is an integer $1 \leq C \leq 13$ indicating the value of a card.

outputFormat: For each hand, output a line containing an integer n if the cards can be combined using arithmetic operators to evaluate to $n$. The value $n$ should be the largest possible value amongst all possible arithmetic expressions using these $4$ cards, so long as $n \leq 24$.

translation:
有一个算 $24$ 点的游戏，每局游戏都会给你 $4$ 个整数$(1 \leq$ 每个数 $\leq 13$，表示你所需要用其来凑出 $24$ 点。你可以将其中的两个数通过加减乘除的运算，得到一个新数，一直重复如此的操作，直到你剩下一个整数，那便是你游戏的答案。

现在，你需要根据给出的那 $4$ 个整数，来计算出一个整数 $n$，使其最接近 $24$，同时也不能超出 $24$，问 $n$ 是多少。

你一共玩了 $N(1 \leq N \leq 5)$ 局这样的游戏，请你求出每局游戏对应的 $n$。


title: [信息与未来 2022] 幸运数字

description:
如果一个十进制数字从左到右读时，所有数位都是**从小到大严格递增**的，我们就称它是幸运数字。例如：

- $9$、$27$、$1234$ 都是幸运数字；
- $11$、$80$、$243$、$1503$ 不是幸运数字。

对于给定的 $a$ 和 $b$，请你求出 $a,a+1,a+2,\cdots,b$ 中幸运数字的数量。

inputFormat: 输入一行空格分隔的两个整数 $a$ 和 $b$。

outputFormat: 输出一行一个整数，代表 $a,a+1,a+2,\cdots,b$ 中幸运数字的数量。


title: [信息与未来 2022] 沙滩面积

description:
我们获得了一幅陆地和水域情况的卫星照片，照片可以看成是一个 $n$ 行 $m$ 列的矩形，矩形中的每个格子要么是陆地（用半角点号 $\texttt{.}$ 表示），要么是水域（用井号 $\texttt{\#}$ 表示）。

虽然卫星照片可以清楚的辨别出陆地和水域，但陆地的具体类型却并不明确。现在我们了解到，对于一块是水域的方格，它向上、下、左、右四个方向 $k$ 步之内可达的陆地格子，均会形成沙滩。例如，下图展示了 $k=2$ 的情况，蓝色的格子代表水域，标为黄色的陆地格子是沙滩。

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

你的任务是根据卫星照片计算出属于“沙滩”格子的数量。注意：卫星照片只拍摄了包含水域的部分，**水域附近的沙滩可能出现在卫星照片边界之外**。你可以假设卫星照片之外不存在任何水域。

inputFormat:
输入的第一行是空格分隔的三个整数 $n,m$ 和 $k$，代表拍摄的卫星照片共有 $n$ 行 $m$ 列，以及形成沙滩的范围 $k$。

接下来 $n$ 行，每行一个字符串。字符串的长度恰好是 $m$，代表卫星照片的一行，其中：

- 井号 $\texttt{\#}$ 表示一片水域；
- 半角点号 $\texttt{.}$ 表示一片陆地。

outputFormat: 输出一行一个整数，代表沙滩格子的数量。

hint:
对于 $40\%$ 的数据，满足 $n=m=1$；
对于 $100\%$ 的数据，满足 $1\leq n,m\leq 100$，$1\leq k\leq 10$。


title: [信息与未来 2022] 完美字符串

description:
你可能见过下面这一句英文：

> "The quick brown fox jumps over the lazy dog."

短短的一句话就包含了所有 $26$ 个英文字母！因此这句话广泛地用于字体效果的展示。更短的还有：

> "The five boxing wizards jump quickly."

所以你很好奇：还有没有更多这样包含所有 $26$ 个英文字母的句子？于是你用爬虫在互联网上爬取了许多英文文本，并且提取出了其中的单词。你现在希望从一个很长的单词序列中找出**一段连续出现的**单词，它满足：

- 所有 $26$ 个英文字母都至少出现一次；
- 长度尽可能短，即包含的字母总数尽可能少。

inputFormat:
输入的第一行包含一个整数 $n$，代表单词序列的长度，即单词的数量。

输入的第二行包含 $n$ 个空格分隔的英文单词（**单词仅由小写字母构成**）。输入数据保证每个小写英文字母都至少出现一次。

outputFormat: 输出一行一个整数，是你找到的单词序列中的字母总数。

samples:
13
there is a quick brown fox jumping over the lazy dog and cat

hint:
最短满足条件的单词序列是 "is a quick brown fox jumping over the lazy dog"，共有 $37$ 个字母。

对于 $40\%$ 的数据，满足 $n\leq 100$；
对于 $100\%$ 的数据，满足 $1\leq n\leq 100,000$。每个单词的长度不超过 $10$ 个字符，且单词全部由小写英文字母 $\texttt{a-z}$ 构成。


title: [信息与未来 2022] 样本分类

description:
在人工智能中，“分类”是一项非常重要的任务。例如，公安系统通过人工智能分类潜在的电信诈骗，并进行及时的预警。现在我们考虑一种最简单的“线性二分类器”，它由 $n$ 个整数参数（常数）$a_1,a_2,\cdots,a_n$ 组成。在输入一组整数 $x_1,x_2,\cdots,x_n$ 时，如果

$$
a_1\cdot x_1+a_2\cdot x_2+\dots+a_n\cdot x_n\leq 0
$$

成立，则分类器输出 $\texttt{true}$，否则分类器输出 $\texttt{false}$。如果分类器的输入（称为“特征”）选择得当，即便是简单的线性分类器也能取得很好的分类效果。

现在，我们得到了两个用于同一分类任务的分类器：

- 分类器 $A$，当 $a_1\cdot x_1+a_2\cdot x_2+\dots +a_n\cdot x_n\leq 0$ 时输出 $\texttt{true}$，否则输出 $\texttt{false}$
- 分类器 $B$，当 $b_1\cdot x_1+b_2\cdot x_2+\dots +b_n\cdot x_n\leq 0$ 时输出 $\texttt{true}$，否则输出 $\texttt{false}$

由于 $A$ 和 $B$ 是两个不同的分类器，它们可能会在某些输入的 $x$ 上产生分歧，给出不同的分类结果——这样的问题值得我们特别关注。因此，你的任务就是求出一组 $x_1,x_2,\cdots,x_n$，使得分类器 $A$ 和 $B$ 返回不同的结果。

为了帮助大家理解，我们假设 $a_i$ 和 $b_i$ 分别保存在数组 $\text{a}$ 和 $\text{b}$ 中（数组下标从 $1$ 到 $n$）。你的任务就是求出数组 $\text{x}$ 的元素 $\texttt{x[1]},\texttt{x[2]},\cdots,\texttt{x[n]}$，使下面的函数 $\texttt{diverge}$ 返回 $\texttt{true}$：

```cpp
int n; // 参数/输⼊的个数
bool classify(int param[], int x[]) {
 int y = 0;
 for (int i = 1; i <= n; i++) {
 y += param[i] * x[i];
 }
 if (y <= 0) {
 return true;
 } else {
 return false;
 }
}
bool diverge(int x[]) {
 return classify(a, x) != classify(b, x);
}
```

inputFormat:
输入的第一行包含一个整数 $n$，代表分类器参数的个数。

输入的第二行包含 $n$ 个整数，代表分类器 $A$ 的参数 $a_i$（$1\le i\le n$）。

输入的第三行包含 $n$ 个整数，代表分类器 $B$ 的参数 $b_i$（$1\le i\le n$）。

~~**输入数据保证两个分类器的参数不是完全相同的**。~~

传题人 Update：本题保证两个分类器的参数不对应成比例且同号，即所有 $\dfrac{a_i}{b_i}$ 不全为同一正值，可以证明这种情况下一定有解。

outputFormat: 输出一行 $n$ 个整数，分别是 $x_1,x_2,\cdots,x_n$。其中 $x_i$（$1\leq i\leq n$）可以是正数、负数或零，但**绝对值不能超过 $10,000$**。如果有多组满足要求的解，输出任意一个即可。


title: 「NnOI R1-T3」元组

background: 小 L 很喜欢树，很喜欢 $ \operatorname{LCA} $，很喜欢有序元组，于是有了这样一道题。

description:
对于一棵 $ n $ 点有根树（根为 $ 1 $），定义有序 $ p $ 元组 $ (a_1,a_2,......,a_p) $ 为 $ k $ 级 $ \operatorname{LCA} $ $ p $ 元组当且仅当：

* $ 1 \le a_1<a_2<......<a_p \le n $

* 存在 $ x $ 使得对于任意有序严格递增 $ k $ 元组 $ b \subseteq a $ 均满足 $ \operatorname{LCA}_{i=1}^{k}\{b_i\} = x $。

注意，$ \operatorname{LCA}(x,y) $ 指树上 $ x $ 点和 $ y $ 点的最近公共祖先，且 $ \operatorname{LCA}_{i=1}^{k}\{b_i\} $ 指的是所有的 $ b_i $ 的 $ \operatorname{LCA} $。

求出 $ k $ 级 $ \operatorname{LCA} $ $ p $ 元组的个数，对 $ 10^9+7 $ 取模。

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

接下来 $ n-1 $ 行，每行两个整数代表一条边的两个端点的编号。

outputFormat: 输出一个整数代表要求的答案。


title: [POI 2020/2021 R3] Komunikacja międzyplanetarn

background:
译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Komunikacja międzyplanetarn](https://szkopul.edu.pl/problemset/problem/43LcdhShos7i99wnVNtQYUUK/statement/)。

d2t1。

description:
二维平面上有 $n$ 个点。

对于每个点，算出它到其他所有点的欧式距离之和。

相对误差不超过 $0.1\%$ 即可。

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

接下来 $n$ 行，每行两个整数 $x,y$，表示一个点的坐标。

outputFormat: $n$ 行，每行一个实数，表示每个点的答案。


title: [POI 2020/2021 R3] Nawiasowania

background:
译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Nawiasowania](https://szkopul.edu.pl/problemset/problem/YmEnXY44jxuLdZPFrhWOfOQi/statement/)。

d2t2。

description:
有 $n$ 张卡片，每张上写了一个左括号或右括号。

按 $1\sim n$ 的顺序排列这些卡片，得到的括号序列是合法的。

给你一个长度为 $n$ 的排列 $p$。

按 $p$ 所示次序排列这些卡片，即新第 $i$ 张放原第 $p_i$ 张，得到的括号序列也是合法的。

构造符合要求的括号序列，按 $1\sim n$ 的顺序输出。

如果有多解，任意一种都行。无解输出 `NIE`。

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

第二行 $n$ 个整数表示排列 $p$。

outputFormat:
如果有解，输出一行 $n$ 个字符，左括号或右括号。

如果无解，输出 `NIE`。

samples: 见附件 NIE


title: [POI 2020/2021 R3] Suma liczb pierwszych

background:
译自 [XXVIII Olimpiada Informatyczna - III etap](https://sio2.mimuw.edu.pl/c/oi28-3/dashboard/) [Suma liczb pierwszych](https://szkopul.edu.pl/problemset/problem/8brtPux-IyytS6rOoOR1cJTL/statement/)。

d2t3。

description:
给你一个数字 $n$，求 $l,r$，使 $[l,r]$ 区间内的所有质数之和等于 $n$。

如果有多解，任意一组均可；无解输出 `NIE`。

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

outputFormat:
如果有解，一行两个正整数 $l,r$，你的答案。

如果无解，输出 `NIE`。


title: [KMOI R1] 五五五五（Hard）

background: “事类相推，各有攸归，故枝条虽分而同本干知，发其一端而已。又所析理以辞，解体用图，庶亦约而能周，通而不黩，览之者思过半矣。”——刘徽

description:
小宋有一个序列 $A=\{a_1,a_2\dots,a_n\}$，其中 $\forall i\in [1,n],a_i\in[0,9]$。

对于 $1\le l\le r\le n$，他记 $f(l,r)$ 等于 $\overline{a_la_{(l+1)}\dots a_r}$ 的末尾连续 $5$ 的个数。

例如：对于序列 $a=\{1,1,4,5,1,4\}$，$f(2,4)=1,f(1,3)=0$。

不过小宋会对这个序列不断地操作，具体地，他会做以下操作：

- $(1,x,y)$：将第 $x$ 个数改为 $y$（$x\in[1,n],y\in[0,9]$）。

- $2$: 将序列 $a$ 反转，例如 $\{1,1,4,5\}$ 反转之后就是 $\{5,4,1,1\}$。

- $3$：对序列进行询问。

- $(4,l,r)$：对序列进行询问。

对于每一种操作 $3$，请你输出:

$$\Big(\sum\limits_{l=1}^
{n}\sum\limits_{r=l}^{n} f(l,r)\Big) \bmod 10^9+7$$

对于每一个操作 $4$，请你输出：

$$\Big(\sum\limits_{i=l}^{r}a_i\Big) \bmod 10^9+7$$

inputFormat:
第一行两个正整数 $n,q$，表示序列的数个数和询问的个数。

第二行 $n$ 个整数 $a_1, a_2,\dots a_n$，表示序列 $A$。

接下来 $q$ 行，每行一个或三个正整数，表示一次操作。

outputFormat: 对于每一次操作 $3$ 和操作 $4$，输出答案。


title: [JOI 2023 Final] Modern Machine

description:
Bitaro is given JOI machine as a birthday present. JOI machine consists of one ball, $N$ light tiles, and $M$
buttons. The light tiles are numbered from $1$ to $N$. When Bitaro turns the power on, Light tile $i$ ($1 \leq i \leq N$) emit light of color $C_i$ (blue ($\texttt B$) or red ($\texttt R$)). The buttons are numbered from $1$ to $M$. If Bitaro pushes Button $j$ ($1 \leq j \leq M$), the following happen.
1. The ball is placed on Light tile $A_j$.
2. Light tile $A_j$ becomes red (regardless of its original color).
3. The following operations are performed until the ball is removed.
    Let $p$ be the index of the light tile where the ball is currently placed.
    - If Light tile $p$ is blue,
    Light tile $p$ becomes red. After that, if $p = 1$, the ball is removed. Otherwise, the ball moves to
Light tile $p − 1$.
    - If Light tile $p$ is red,
    Light tile $p$ becomes blue. After that, if $p = N$, the ball is removed. Otherwise, the ball moves
to Light tile $p + 1$.

Bitaro is interested in JOI machine. He plans to perform $Q$ experiments. In the $k$-th experiment ($1 \leq k \leq Q$),
after Bitaro turns the power on, Bitaro pushes Buttons $L_k, L_{k + 1},\dots , R_k$ in this order. After Bitaro pushes a button, he will not push the next button and wait until the ball is removed.

Given information of JOI machine and the experiments, write a program which calculates, for each experi-
ment, the number of light tiles whose colors are red when the experiment finishes.

inputFormat:
Read the following data from the standard input.
> $N$ $M$
> $C_1\ C_2 \dots C_N$
> $A_1\ A_2 \dots A_M$
> $Q$
> $L_1\ R_1$
> $L_2\ R_2$
> $\dots$
> $L_Q\ R_Q$

outputFormat: Write $Q$ lines to the standard output. In the $k$-th line ($1 \leq k \leq Q$), the output should contain the number of light tiles whose colors are red when the $k$-th experiment finishes.

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

The first experiment proceeds as follows.
1. Bitaro pushes Button 1, and ball is placed on Light tile 4.
2. Light tile 4 becomes red. Since the original color of Light tile 4 is red, the color of Light tile 4 does not
change.
3. After that, the following operations are performed.
（1）Since the current color of Light tile 4 is red, Light tile 4 becomes blue, and the ball moves to Light
tile 5.
（2）Since the current color of Light tile 5 is blue, Light tile 5 becomes red, and the ball moves to Light
tile 4.
（3）Since the current color of Light tile 4 is blue, Light tile 4 becomes red, and the ball moves to Light
tile 3.
（4）Since the current color of Light tile 3 is red, Light tile 3 becomes blue, and the ball moves to Light
tile 4.
（5）Since the current color of Light tile 4 is red, the color of Light tile 4 becomes blue, and the ball
moves to Light tile 5.
（6）Since the current color of Light tile 5 is red, the color of Light tile 5 becomes blue, and the ball is
removed.

After the experiment, Light tile 1 is the only light tile whose current color is red. Therefore, output 1.

本样例满足子任务 1,2,3,6,7 的限制。

**【样例解释 #2】**

For the first experiment, Light tiles 1, 2, 3, 4, 5 are the light tiles whose current colors are red after the experiment. Since there are five such light tiles, output 5.

For the second experiment, there is no light tile whose current color is red after the experiment. Therefore,
output 0.

本样例满足子任务 3,6,7 的限制。

**【样例解释 #3】**

本样例满足子任务 1,2,3,6,7 的限制。

**【样例解释 #4】**

本样例满足子任务 3,4,5,6,7 的限制。

**【样例解释 #5】**

本样例满足子任务 3,5,6,7 的限制。

**【样例解释 #6】**

本样例满足子任务 6,7 的限制。

**【数据规模】**

对全部的测试点，保证：
- $3 \leq N \leq 1.2 \times 10^5$；
- $1 \leq M \leq 1.2 \times 10^5$；
- $C_i \in \{\texttt{B},\texttt{R}\}$；
- $1 \leq A_j \leq N$；
- $1 \leq Q \leq 1.2 \times 10^5$；
- $1 \leq L_k \leq R_k \leq M$；
- $N, M, A_j, Q, L_k, R_k$ 均为整数。

**【子任务】**

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

1. (3 points) $N,M \leq 300$，$Q = 1$。
2. (12 points) $N, M \leq 7000$，$Q = 1$。
3. (10 points) $Q \leq 5$。
4. (11 points) $N = 10$，$C_i = \texttt R$。
5. (26 points) 存在一个整数 $t \in [0, N]$，满足对 $1 \leq i \leq t$，$C_i = \texttt R$；且对 $t < i \leq N$，$C_i = \texttt B$。
6. (17 points) $A_j \leq 20$ 或 $A_j > N - 20$。
7. (21 points) 无特殊约定。


title: [语言月赛202306] 魔方

description:
正阶魔方的形状是正方体，每个面由相等的若干个小正方形构成。对于 $n$（$n \geq 2$）阶魔方，它的六个面中的每个面均由 $n\times n$ 个小正方形构成。

魔方的六个面被染上了 $6$ 种不同的颜色，被染上色的小正方形又构成一个个小正方体，这些小正方体被称为「块」。

容易发现，每个块有 $1\sim3$ 个面被染色。因此，魔方有三个围绕块的重要概念：

- 角块：有 $3$ 个面被染色的块。一个 $n$ 阶魔方的角块数总是 $8$。
- 棱块：只有 $2$ 个面被染色的块。一个 $n$ 阶魔方的棱块数为 $12 \times (n - 2)$。
- 中心块：只有 $1$ 个面被染色的块。一个 $n$ 阶魔方的中心块个数等于 $6\times (n-2)^2$。

现在给你一个正阶魔方的阶数 $n$，请你依次求出它的角块，棱块，中心块的数量。

inputFormat: 输入共一行一个整数 $n$，表示魔方的阶数。

outputFormat: 输出共一行三个整数，依次表示 $n$ 阶魔方的角块，棱块，中心块的数量。数字之间用一个空格隔开。

hint:
**样例解释 #1：**

一个 $3$ 阶魔方的角块数总是 $8$，棱块数为 $12 \times (3 - 2)=12$，中心块个数等于 $6\times (3-2)^2=6$。

### 数据规模与约定

- 对于 $40\%$ 的数据，$2\leq n\leq 17$。
- 对于 $100\%$ 的数据，$2\leq n \leq 10^{6}$。


title: [语言月赛202306] 信

description:
信是具有重量的。信封有重量，信纸也有重量。由于信封和信纸都很薄，我们认为每平方厘米信封的重量为 $x$ 毫克，每平方厘米信纸的重量为 $y$ 毫克。 此外，有的信封中还会有一些礼物，这些礼物**一定**有重量。

zyl 收到了 $n$ 封信，他能精确测量出每封信中信封的面积 $S$（单位：平方厘米）、信纸的面积 $s$（单位：平方厘米）以及整封信的重量 $M$（单位：毫克），保证这三个数据都是整数。在拆开信件的过程中，他会按照如下规则积累**惊喜值**（初始时惊喜值为 $0$）：

- 如果信封没有任何礼物（即信封中礼物重量为 $0$），他的惊喜值不变。但是，如果连续 $b$ 封及以上的信里都没有礼物，则从第 $b$ 封信开始，每拆开一封没有礼物的信，zyl 的惊喜值都会减半，然后**向下取整**，直到拆开一封有礼物的信。如果惊喜值原本即为 $0$，则不会变化。
- 如果信封里有礼物，设礼物的质量为 $M'$ 毫克，则 zyl 的惊喜值会增加 $M'$。如果礼物的质量大于信封和信纸的总质量，则会额外增加 $0.5\ M'$，然后**向上取整**。如果连续 $a$ 封及以上的信里有礼物，则从第 $a$ 封信开始，每拆开一封有礼物的信，zyl 的惊喜值都会在计算完这次本身的加成后再乘 $2$，直至拆开一封没有礼物的信。

现在按照 zyl 拆信的顺序给出 $n$ 封信的信息，请你求出 zyl 在拆信过程中最高的惊喜值和最终的惊喜值。

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

第一行五个整数 $n,x,y,a,b$，含义如题所示。
接下来 $n$ 行，每行三个整数 $S,s,M$。表示这封信的信封面积，信纸面积和总质量，单位分别为平方厘米
、平方厘米、毫克。

outputFormat: 输出共一行两个整数，第一个表示拆信过程中的最高惊喜值，第二个表示最终的惊喜值，二者之间使用空格隔开。


title: 「NnOI R1-T2」风屿

background: 「与风为名，屿之齐鸣。」——风屿

description:
风屿是一块 $ n $ 行，$ m $ 列的群岛，第 $ i $ 行第 $  j $ 列记为 $ (i,j) $。

风屿的重力系统很奇怪，$ (i,j) $ 的重力系数 $ g_{i,j}=a_i+b_j $。$ a,b $ 是两个已知的长度分别为 $ n,m $ 的数组。

我们定义岛 $ (x,y) $ 和 $ (z,w) $ **相邻**当且仅当 $ |x-z|+|y-w|=1 $，定义 $ (x,y) $ 和 $ (z,w) $ **连通**当且仅当两种情况至少有一种满足：

* $ (x,y),(z,w) $ 相邻，且 $ g_{x,y}=g_{z,w} $。

* 存在另一个岛 $ (u,v) $ 使得 $ (x,y) $ 和 $ (u,v) $ 连通且 $ (u,v) $ 和 $ (z,w) $ 连通，也就是说，连通关系**具有传递性**。

我们定义无序互异的岛集 $ \{(x_i,y_i)\} $ 为**同色连通块**，当且仅当岛集中任意两岛连通。

找到最大的同色连通块，并求出大小和这样的块的个数。

inputFormat:
**本题多测**，第一行一个正整数 $ T $，代表该测试点内测试数据组数。

对于每组测试数据：

第一行 $ n $，$ m $，表示风屿的行数和列数。

接下来一行 $ n $ 个整数，代表 $ a $ 数组。

接下来一行 $ m $ 个整数，代表 $ b $ 数组。

outputFormat: $ T $ 行，每行代表该组测试数据的答案（最大块大小和个数）。


title: 『MGOI』Simple Round I | B. 魔法照相馆

background: > 照片留下了值得留恋的瞬间，但对于魔法士来说最重要的是向前看。——殿堂魔法士 W

description:
小 M 正在准备入学所必需的魔法士证件，因此他来到了纵深巷的魔法照相馆。

在等待的时候，小 M 注意到魔法照相馆有三个幕布，颜色从左到右分别是红色、蓝色和白色。店主 zx 先生会根据客人的需求拉上或拉下这三个幕布，如下图所示：

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

幕布摆放在左边，按照红蓝白的顺序排列。人则坐在幕布右边，而 zx 先生则站在最右边给人拍照。幕布从右往左数，第一个没有拉上的幕布颜色将成为照片的背景颜色。

每次 zx 先生拉上或拉下一个幕布都需要消耗一个时间单位，而拍照不消耗时间。小 M 已经知道了他前面所有总共 $n$ 个客人的需求。在初始状态为 **全部拉下** 的情况下，请你帮助小 M 计算他至少需要等待多少个时间单位。

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

第二行一个由 `RBW` 三个大写字母组成的长度为 $n$ 的字符串，其中第 $i$ 个字符表示第 $i$ 个客人的需求，`R` 是红色，`B` 是蓝色，`W` 是白色。

outputFormat: 一行一个整数，表示小 M 至少需要等待的时间单位。

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

开始三个幕布是全部拉下的。

- 第一位客人要求蓝色，所以拉上白色，消耗一个时间单位。
- 第二位客人要求蓝色，无需改动。
- 第三位客人要求红色，所以在之前基础上拉上蓝色，消耗一个时间单位。
- 第四位客人要求白色，所以拉下白色，消耗一个时间单位。
- 第五位客人要求蓝色，所以拉上白色，拉下蓝色，消耗两个时间单位。

共计消耗五个时间单位。

**【数据范围】**

本题共有五个测试点。

| 测试点编号 | $n =$ | 特殊性质 |
| :------------: | :----------: | :----------: |
| $1$ | $1$ | 无 |
| $2$ | $1000$| 有 |
| $3$ | $1000$ | 无 |
| $4$ | $10^5$ | 有 |
| $5$ | $10^5$ | 无 |

特殊性质：只出现 `W` 和 `B` 两种颜色。


title: [ICPC2022 Xi'an R] Bridge

description:
There are $n$ countries numbered from $1$ to $n$ in Erathia. Each country can be regarded as a chain with $m+1$ nodes numbered from $1$ to $m+1$. Initially, node $(a, b)$ is connected with node $(a, b + 1)$ by a street where node $(a, b)$ denotes the $b$-th node of the $a$-th country. There are no bridges between any two countries at first.

You need to process $q$ queries of the following two types.

- $1\ a\ b$ ($1\leq a < n, 1\leq b\leq m$). Build a bridge between node $(a, b)$ and node $(a + 1, b)$. It is guranteed that at any time, **each node is connected with at most one bridge**.
- $2\ a$ ($1\leq a\leq n$). A hero will walk through Erathia. This hero starts from $(a, 1)$. If the hero is at $(x, y)$ and there is a unvisited bridge connected to him, he passes it, or he goes to $(x, y + 1)$. Once he arrived the $(m+1)$-th node of any conutry, he stops. Please note that 'unvisited bridge' is **independently** judged for each query.

Your task is to print which country the hero is in at last for the second kind of query. It can be proved that the hero's route is always unique under these constraints.

inputFormat:
The first line contains three integers $n$, $m$ and $q$ ($1 \leq n, m, q \leq 10 ^ 5$).

Each of the following $q$ lines represents a query with format described above.

outputFormat: For each query of type $2$, output a line with an integer representing the answer.

translation:
### 题目描述

Erathia 大陆上有 $n$ 个国家，从 $1$ 到 $n$ 编号。每个国家可以看成由 $m + 1$ 个结点组成的链，结点从 $1$ 到 $m + 1$ 编号。结点 $(a, b)$ 和 $(a, b + 1)$ 由一条街道连接，其中 $(a, b)$ 表示国家 $a$ 的第 $b$ 个结点。一开始，国家之间没有桥。

你需要处理 $q$ 个操作：

- $1\ a\ b$（$1\leq a < n$，$1\leq b\leq m$）：在 $(a, b)$ 和 $(a + 1, b)$ 之间建造一座桥。**保证每个结点最多和一座桥相连**。
- $2\ a$（$1\leq a\leq n$）：一名英雄走过 Erathia 大陆。他从 $(a, 1)$ 出发。如果这名英雄当前在结点 $(x, y)$ 且有一座未被访问过的桥与之连接，那么他会走过这个桥到达桥的另一端，否则他会走到 $(x, y + 1)$。一旦他到达某个国家的第 $m + 1$ 个结点，他就会停下来。注意两个询问之间的 “未被访问过的桥” 是独立的。

你的任务是对每个操作 $2$ 求出英雄最终所在的国家。

$1\leq n, m, q\leq 10 ^ 5$。

### 输入格式

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

接下来 $q$ 行，每行若干个整数表示一组询问。格式见题目描述。

### 输出格式

对于每个操作 $2$，输出一行一个整数表示答案。

hint:
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem A.

**Author**: MonkeyKing.


title: [ICPC2022 Xi'an R] Cells Coloring

description:
You are given an $n \times m$ grid. Some of the cells are obstacles, the others are empty. Choose a non-negative integer $k$ and color all empty cells with $k+1$ colors $0, 1, 2, \ldots k$. You can not color two cells in the same row or same column with the same **non-zero** color.

You are given two non-negative integers $c$ and $d$. For a coloring plan, define $z$ as the number of the cells with color $0$. Define the cost of the plan is $ck+dz$.

Find the minimum cost.

inputFormat:
The first line contains four integers $n$, $m$ ($1\leq n, m\leq 250$), $c$ and $d$ ($0\leq c, d\leq 10 ^ 9$).

The $i$-th line of the next $n$ lines contains a string of $m$ characters. The $j$-th character is `*` if the cell in the $i$-th row and the $j$-th column is an obstacle. The $j$-th character is `.` if the cell in the $i$-th row and the $j$-th column is empty.

outputFormat: Output a line with a single number, representing the answer.

translation:
### 题目描述

给定一个 $n\times m$ 的网格。一些格子是障碍，其它格子是空的。选择一个非负整数 $k$，并用 $k + 1$ 种颜色 $0, 1, \ldots, k$ 给空格子染色。不能有同一行或同一列的两个格子被染成了相同的 **非零** 颜色。

给定两个非负整数 $c, d$。对于一组染色方案，定义 $z$ 表示染成颜色 $0$ 的格子数量，则该方案的代价为 $ck + dz$。

求出最小代价。

$1\leq n, m \leq 250$，$0\leq c, d\leq 10 ^ 9$。

### 输入格式

第一行四个整数 $n, m, c, d$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串。字符串的第 $j$ 个字符为 `*` 表示第 $i$ 行第 $j$ 列的格子为障碍，为 `.` 表示为空。

### 输出格式

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

hint:
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem B.

**Author**: csy2005.


title: [ICPC2022 Xi'an R] Clone Ranran

description:
Ranran needs to prepare a contest! A contest is made of $c$ problems, and Ranran can do one of the following two things:

- Clone himself in $a$ minutes. That is, after $a$ minutes, there will be one more Ranran.
- Prepare a problem in $b$ minutes. That is, after $b$ minutes, there will be one more problem.

Note that a cloned Ranran can also do the two things above. A Ranran cannot do the two things at the same time.

Ranran wants to prepare the contest as fast as possible. But he is very lazy, so he asks you to find the minimum number of minutes to prepare the contest.

You need to answer $T$ queries independently.

inputFormat:
The first line contains an integer $T$ ($1\leq T\leq 10 ^ 5$).

Each of the next $T$ lines contains three integers $a$, $b$ and $c$ ($1\leq a, b, c\leq 10 ^ 9$), representing a query.

outputFormat: For each test case, output a line with a single integer representing the answer.

translation:
### 题目描述

然然需要准备一场有 $c$ 个问题的比赛！他可以进行两种操作：

- 在 $a$ 分钟内克隆一个自己；
- 在 $b$ 分钟内准备好一个问题。

克隆的然然也可以进行上述操作，但然然不能同时进行这两个操作。

然然希望尽快准备好比赛，但是他很懒，所以他让你求出准备比赛的最小分钟数。

共有 $T$ 组数据。

$1\leq T\leq 10 ^ 5$，$1\leq a, b, c\leq 10 ^ 9$。

### 输入格式

第一行一个整数 $T$。

接下来 $T$ 行，每行三个整数 $a, b, c$。

### 输出格式

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

hint:
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem C.

**Author**: MagicSpark.


title: [ICPC2022 Xi'an R] Contests

description:
There are $n$ contestants and they take part in $m$ contests. You are given the ranklist of each contest. The ranklist of the $k$-th contest is a sequence $a_k$, indicating that the $a_{k, i}$-th contestant's rank is $i$.

SolarPea and PolarSea are two of the $n$ contestants. SolarPea wants to prove that he is stronger than PolarSea.

Define $x$ is $l$-stronger than $y$, if and only if there exists a sequence $b$ of length $l + 1$, such that $b_1 = x$, $b_{l + 1} = y$, and for all $1\leq i\leq l$, $b_i$ has a smaller rank than $b_{i + 1}$ in at least one contest.

There are $q$ queries. In the $i$-th query, SolarPea is contestant $x$ and PolarSea is contestant $y$. Please find the minimum positive number $l$ such that SolarPea is $l$-stronger than PolarSea.

inputFormat:
The first line contains two integers $n$ ($2\leq n\leq 10 ^ 5$) and $m$ ($1\leq m\leq 5$).

The $i$-th of the next $m$ lines contains $n$ intergers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$. It is guaranteed that $a_i$ is a permutaion of $1,2,\ldots,n$.

The next line contains an integer $q$ ($1\leq q\leq 10 ^ 5$).

Each of the next $q$ lines contains two integers $x$ and $y$ ($1 \le x,y \le n, x \neq y$), representing a query.

outputFormat: For each query, output a number $l$ representing the answer. If there is no legal $l$, output $-1$.

translation:
### 题目描述

$n$ 个选手参加了 $m$ 场比赛。给出每场比赛的排行榜。第 $k$ 场比赛的排行榜是一个 $n$ 阶排列 $a_k$，表示选手 $a_{k, i}$ 的排名为 $i$。

SolarPea 和 PolarSea 也是选手。SolarPea 想要证明他比 PolarSea 更强。

定义选手 $x$「$l$ - 强于」选手 $y$，当且仅当存在长度为 $l + 1$ 的序列，满足 $b_1 = x$，$b_{l + 1} = y$，且对于所有 $1\leq i\leq l$，均有 $b_i$ 在至少一场比赛中排名小于 $b_{i + 1}$。

给出 $q$ 组询问。在第 $i$ 组询问中，SolarPea 是选手 $x$，PolarSea 是选手 $y$。求出最小的正整数 $l$，使得 $x$「$l$ - 强于」$y$。

$2\leq n\leq 10 ^ 5$，$1\leq q\leq 10 ^ 5$，$1\leq m\leq 5$，$1\leq x, y\leq n$，$x\neq y$。

### 输入格式

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

接下来 $m$ 行，每行 $n$ 个整数，表示第 $i$ 场比赛的排行榜。保证 $a_i$ 是 $1, 2, \ldots, n$ 的排列。

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

接下来 $q$ 行，每行两个整数 $x, y$ 表示一组询问。

### 输出格式

对于每组询问，输出一行一个整数表示答案。若不存在这样的 $l$，输出 $-1$。

hint:
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem D.

**Author**: csy2005.


title: [ICPC2022 Xi'an R] Find Maximum

description:
We define a function $f(x)$ over all non-negative integer $x$ as follows:
$$
f(x) =
\begin{cases}
1 & (x = 0) \\
f(\frac{x}{3}) + 1 & (x > 0\land x\bmod3 = 0) \\
f(x - 1) + 1  & (x > 0\land x\bmod 3\neq 0)
\end{cases}
$$
Calculate $\max_{x = l} ^ r f(x)$.

You need to answer $T$ queries independently.

inputFormat:
The first line contains a single integer $T$ ($1\leq T\leq 10 ^ 4$).

Each of the next $T$ lines contains two integers $l$ and $r$ ($1\leq l\leq r\leq 10 ^ {18}$), representing a query.

outputFormat: Output $T$ lines. The $i$-th line contains a single integer, representing the answer to the $i$-th query.

translation:
### 题目描述

定义在所有非负整数 $x$ 上的函数 $f(x)$ 如下：

$$
f(x) =
\begin{cases}
1 & (x = 0) \\
f(\frac{x}{3}) + 1 & (x > 0\land x\bmod3 = 0) \\
f(x - 1) + 1  & (x > 0\land x\bmod 3\neq 0)
\end{cases}
$$

计算 $\max_{x = l} ^ r f(x)$。

共有 $T$ 组数据。

$1\leq T\leq 10 ^ 4$，$1\leq l\leq r\leq 10 ^ {18}$。

### 输入格式

第一行一个整数 $T$。

接下来 $T$ 行，每行两个整数 $l, r$ 表示一组询问。

### 输出格式

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

hint:
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem E.

**Author**: MagicSpark.


title: [ICPC2022 Xi'an R] Hotel

description:
You are doing volunteer work for a programming competition in an ancient hotel. Unfortunately, the hotel provides no phone signal or tap water since it can be dated back to the Qin Dynasty, and you have to assign the contestants to the hotel rooms manually instead of using the internet apps. Fortunately, the hotel has sufficient rooms, and you have taken a computer that lets you do some computation locally.

There are $n$ teams, each with exactly $3$ contestants. There are $2$ types of rooms in the hotel, the single room and double room, which can receive at most $1$ and $2$ contestants, respectively. To avoid embarrassing contestants, if two contestants are assigned to a double room, they must come from the same team and have the same gender.

The cost of each room of the same type is the same, but different types may have different costs. Your program needs to calculate the minimum price the host has to pay. The teams are waiting in the registration hall now, and the competition finance officer relies on you to save costs and make a fortune by the residual value. Be quick, or the finance officer will sue you for violating his reputation!

inputFormat:
The first line of input contains three integers $n$, $c_1$ and $c_2$ ($1 \leq n, c_1, c_2 \leq 1\,000$), denoting the number of teams, the cost of a single room and a double room respectively.

In the following $n$ lines, each line contains a string $S$ with exactly $3$ uppercase English letters. The letters in a string denote the genders of the contestants in one team and will be represented by $\texttt{A}$ to $\texttt{Z}$, respecting the diversity of human beings.

outputFormat: The output should contain a single integer, denoting the minimum cost of hotel allocation for contestants.

translation:
### 题目描述

你正在一个古代的酒店里为一场编程竞赛做志愿工作。酒店的历史可以追溯到秦朝，所以酒店不提供手机信号和自来水。你无法使用网络软件，不得不手动为参赛者分配房间。幸运的是，酒店拥有充足的房间，并且你有一台电脑帮你做一些计算。

共有 $n$ 个队伍，每个队伍恰有 $3$ 名选手。酒店有两种房间，单人间和双人间，分别可以容纳 $1$ 和 $2$ 名选手。为了避免使选手尴尬，如果两名选手分配到了同一个双人间，他们必须来自同一个队伍，并拥有相同的性别。

相同种类的房间的花费相同，但不同种类的房间花费可能不同。你需要计算主办方最少需要花多少钱。选手们已经在登记厅等候多时，而竞赛财务经理依靠你来节省开支，私吞剩下来的钱发大财。你需要尽快完成任务，否则财务经理将起诉你侵犯了他的名誉权！

$1\leq n, c_1, c_2\leq 1000$。

### 输入格式

第一行三个整数 $n, c_1, c_2$，分别表示队伍数量，单人间单价和双人间单价。

接下来的 $n$ 行，每行一个长度为 $3$ 的字符串 $S$ 表示一个队伍的参赛队员的性别。为了尊重人类的多样性，$S$ 可能包含从 $\texttt A$ 到 $\texttt Z$ 的所有大写字母。

### 输出格式

输出一行一个整数表示分配房间的最小代价。

samples:
10 438 438
WWW
SOU
PUN
ETC
OME
CFI
NAL
GOO
DHO
TEL

hint:
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem F.

**Author**: fstqwq.


title: [ICPC2022 Xi'an R] Perfect Word

description:
You are given $n$ strings and required to find the length of the longest *perfect word*.

A string $t$ is called a *perfect word*, if and only if every non-empty substring of $t$ appears in the given strings.

A string $s$ is called a substring of $t$ if and only if it can be obtained by removing several (possibly zero) characters from the beginning or end of $t$.

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

Each of the next $n$ lines contains a string consisting of lowercase English letters.

It is guaranteed that the total length of the given strings is no more than $10 ^ 5$.

outputFormat: Output an integer, representing the length of the longest perfect word.

translation:
### 题目描述

给定 $n$ 个字符串，你需要找到最长的「完美单词」。

字符串 $t$ 称为「完美单词」，当且仅当它的所有非空子串都出现在给定的字符串中。

字符串 $s$ 称为 $t$ 的子串，当且仅当 $s$ 可由 $t$ 在开头和结尾分别删去零个或若干个字符得到。

$1\leq n\leq 10 ^ 5$，字符串仅由小写字母组成，且总长不超过 $10 ^ 5$。

### 输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行一个字符串。

### 输出格式

输出一行一个整数表示最长的「完美单词」的长度。

hint:
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem G.

**Author**: MonkeyKing.


title: [ICPC2022 Xi'an R] Power of Two

description:
$$
2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}}}}}}
$$

SolarPea likes blowing up PolarSea's blog by sending power tower of $2$. As the tower is too high, the stack of the web page overflows. So the blog no longer works.

Now SolarPea has $n$ powers of two $a_1, a_2, \ldots, a_n$, $x$ bitwise AND operators, $y$ bitwise OR operators and $z$ bitwise XOR operators. It is guaranteed that $n = x + y + z$.

Solarpea wants to construct an arithmetic expression with these numbers and operators. Formally, define $x_0 = 0$ and $x_i = x_{i - 1}\ \mathrm{op}_i\ b_i$, where $b$ is a permutation of $a$, which means we can rearrange $a$ to get $b$, and $\mathrm{op}_i$ is one of the three types of bitwise operators above. Then $x_n$ is the result of the expresstion.

The larger the expression, the more likely it is to make PolarSea's blog unable to work. SolarPea wants you to help him to find the largest $x_n$ and construct such an expression. If there are multiple solutions, output any of them.

You need to process $T$ test cases independently.

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

For each test case, the first line contains four integers $n$, $x$, $y$ and $z$ ($0\leq x, y, z\leq n \leq 65\,536, n = x + y + z$). The next line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($0\leq c_i < n$), where $a_i = 2 ^ {c_i}$.

It is guaranteed that the sum of $n$ over all test cases is no more than $1\,048\,576$.

outputFormat:
For each test case, output three lines.

The first line contains a $01$-string of length $n$, representing the binary form of the largest $x_n$.

The next line contains a single $1$-indexed string $\mathrm{op}$ of length $n$, where $\mathrm{op}_i$ represents the $i$-th operator. Here, we denote AND as `&` (ASCII 38), OR as `|` (ASCII 124), and XOR as `^` (ASCII 94). You should guarantee that there is exactly $x$ AND operators, $y$ OR operators and $z$ XOR operators.

The third line contains $n$ integers $d_1, d_2, \ldots, d_n$, the $i$-th of which representing the logarithm of $b_i$ with base $2$. That is, $d$ is a permutaion of $c$.

If there are multiple solutions, output any of them.

hint:
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem H.

**Author**: Alex_Wei.

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


title: [ICPC2022 Xi'an R] Square Grid

description:
Given a square grid, its lattice points labeled from $(0, 0)$ to $(n, n)$, and a number $t$.

You need to answer $q$ queries in this format: given $A = (x_0, y_0)$ and $B = (x_1, y_1)$, how many ways are there to move from $A$ to $B$ in exactly $t$ steps so that in each step you move from a lattice point to one of its neighbors (up, down, left, right). Calculate the answer modulo $998\,244\,353$.

inputFormat:
The first line contains three integers $n$ ($1 \leq n \leq 10^5$), $t$ ($1 \leq t \leq 10^9$) and $q$ ($1 \leq q \leq 3 \times 10^5$).

Each of the following $q$ lines contains four integers $x_0$, $y_0$, $x_1$ and $y_1$ ($0 \leq x_0, y_0, x_1, y_1 \leq n$), representing a query.

outputFormat: For each query, output a line containing one integer, representing the answer to the query modulo $998\,244\,353$.

translation:
给定正方形网格，格点坐标从 $(0,0)$ 到 $(n,n)$。

$q$ 组询问，每次询问从 $(x_0, y_0)$ 走恰好 $t$ 步，每步只能朝上、下、左、右走一格，不走出边界，走到 $(x_1, y_1)$ 的方案数，对 $998\,244\,353$ 取模。所有询问的 $t$ 相同。

hint:
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem I.

**Author**: djq_cpp.


title: [ICPC2022 Xi'an R] Strange Sum

description:
Given a sequence $a_1, a_2, \ldots, a_n$.

You are going to select zero or more elements of $a$ so that: if you select $a_i$, then in any interval of length $i$ (formally, in $a[j, j + i - 1]$ for any $1 \le j \le n - i + 1$) you can select at most $2$ elements.

Calculate the maximal sum of the elements you select.

inputFormat:
The first line contains an integer $n$ ($2 \leq n \leq 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \leq a_i \leq 10^9$).

outputFormat: Output a single integer denoting the answer.

hint:
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem J.

**Author**: JohnVictor.


title: [ICPC2022 Xi'an R] Streets

description:
You are given $n$ vertical lines with x-coordinates $x_1, x_2, \ldots, x_n$ and weights $a_1, a_2, \ldots, a_n$ and $m$ horizontal lines with y-coordinates $y_1, y_2, \ldots, y_m$ and weights $b_1, b_2, \ldots, b_m$.

Call a rectangle good if and only if all of its four edges lie on the given lines. On this basis, define the cost of a good rectangle as the sum of the costs of its four segments. The cost of a segment is the product of its length and the weight of the line it belongs.

Find the maximum area of good rectangles with cost no more than $c$. Note that the length and the width of the rectangle can be zero, so the answer always exists.

You need to answer $T$ queries with different $c$.

inputFormat:
The first line contains three integers $n$, $m$ ($2\leq n, m\leq 5\,000$) and $T$ ($1\leq T\leq 100$).

The second line contains $n$ integers $x_1, x_2, \ldots, x_n$ ($1\leq x_1 < x_2 < \ldots < x_n \leq 10 ^ 5$).

The third line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\leq a_i\leq 10 ^ 7$).

The fourth line contains $m$ integers $y_1, y_2, \ldots, y_m$ ($1\leq y_1 < y_2 < \ldots < y_m \leq 10 ^ 5$).

The fifth line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1\leq b_i\leq 10 ^ 7$).

Each of the next $T$ lines contains a single integer $c$ ($1\leq c\leq 4\times 10 ^ {12}$), representing a query.

outputFormat: For each query, output one line representing the answer.

translation:
### 题目描述：
给定 $n$ 条垂直的线和 $m$ 条水平线，每条线有重量。定义一个矩形是好的，当且仅当矩形的四个边都落在这些线上，好矩形的代价等于其内部四条边的长度与对应线重量的乘积之和。请找出最大面积的好矩形，使得其代价不超过 $c$。注意，矩形的长度和宽度可以为零。

### 输入格式：
第一行三个正整数 $n,m,T(2 \leq n, m \leq 5 \times 10^3, 1 \leq T \leq 100)$，依次表示垂直线、水平线的数量以及查询的次数。

第二行 $n$ 个正整数 $x_1,x_2,\cdots,x_n(1 \leq x_1 < x_2 < \cdots < x_n \leq 10^5)$，其中 $x_i$ 表示第 $i$ 条垂直线的位置。

第三行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，其中 $a_i$ 表示第 $i$ 条垂直线的重量。

第四行 $m$ 个正整数 $y_1,y_2,\cdots,y_m(1 \leq y_1 < y_2 < \cdots < y_m \leq 10^5)$，其中 $y_i$ 表示第 $i$ 条水平线的位置。

第五行 $m$ 个正整数 $b_1,b_2,\cdots,b_m(1 \leq b_i \leq 10^7)$，其中 $b_i$ 表示第 $i$ 条水平线的重量。

接下来 $T$ 行，每行一个正整数 $c(1 \leq c \leq 4\times 10^{12})$，表示一次查询。

### 输出格式：
对于每次查询，输出一个整数表示最小代价不超过 $c$ 的最大好矩形的面积。

translated by @[cff_0102](/user/542457)

hint:
**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem K.

**Author**: Alex_Wei.