title: [NWRRC2014] Hiking in the Hills

description:
Helen is hiking with her friends in a highland. Their plan is to hike from their camp $A$ to a beautiful showplace $B$ .

Unfortunately, Helen started feeling dizzy due to altitude sickness. Help her group find a route such that the topmost height on that route is as small as possible.

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

inputFormat:
The input file contains full information about the landscape of a square region $10^{6} \times 10^{6}$ in the following format. The first line contains integer $n$ — the number of triangles in the landscape $(2 \le n \le 2000)$ . Each of following $n$ lines contains nine integers $x_{i_1}, y_{i_1}, z_{i_1}, x_{i_2}, y_{i_2}, z_{i_2}, x_{i3}, y_{i3}, z_{i3}$ — coordinates of a triangle. All coordinates belong to the closed interval $[0 , 10^{6}]$. The two last lines contain three integers each: $x_{A}, y_{A}, z_{A}$ and $x_{B}, y_{B}, z_{B}$ — coordinates of the camp A and the showplace $B$ .

The given triangles are guaranteed to describe a consistent continuous landscape. Projections of triangles onto $XY$ plane are non-degenerate and fill the square without overlapping. A vertex of one triangle never lays inside an edge of another triangle. Points $A$ and $B$ belong to the landscape surface and are different.

outputFormat:
Output a polyline route from $A$ to $B$ with the smallest possible topmost height. The first line should contain $m$ , the number of vertices in this polyline. Each of following $m$ lines should contain three integer coordinates of a polyline vertex: $x_{i}, y_{i},$ and $z_{i}.$ Vertices must be listed along the polyline, from $A$ to $B$ (including these two endpoints).

All coordinates of polyline vertices should be integer. Each polyline edge must belong to some triangle from the input file (possibly, to its edge). The number of vertices in the polyline must not exceed $5n$.

translation:
### 题目描述

H正在和她的朋友在高原徒步，他们计划着从他们的营地A徒步到一个风景名胜B。

可惜的是，H有了点高原反应。请你帮助他们找到一条路线，使该路线的最高高度尽可能小。
![](https://cdn.luogu.com.cn/upload/image_hosting/o2199eky.png)（$1:10^5$）

### 输入格式

输入数据包含整个$10^6 \times 10^6$的的完整信息，格式如下：

第一行包含了一个整数$n$，表示着这个空间内的三角形的数量。接下来的$n$行，每行包含九个整数，分别是
$x_{i_1},y_{i_1},z_{i_1},x_{i_2},y_{i_2},z_{i_2},x_{i_3},y_{i_3},z_{i_3}$
，是一个三角形的坐标。每个三角形的坐标都在区间[$0, 10^6$]之间。最后两行分别包含了A处的坐标和B处的坐标。

给定的三角形保证在一个一致的坐标系。三角形在XY平面上的投影是非简并的，并且填充正方形而不重叠。一个三角形的顶点永远不会位于另一个三角形的边内。A点和B点属于同一个坐标系，且两者不同位置。

### 输出格式

输出从A到B的路线，其最高高度可能最小。第一行应包含m，即此多段线中的顶点数。下面的每m条线都应该包含多段线顶点的三个整数坐标。

顶点必须沿路线列出，从A到B（包括这两个端点）。
路线顶点的所有坐标都应为整数。每个多段线边必须属于输入文件（可能是其边）中的某个三角形。路线的拐点数不能超过5n。


title: [NWRRC2014] Instruction

type: P

description:
Ingrid is a head of a big railway station and, among other duties, is responsible for routing trains to the right platforms. The station has one entrance, and there are many switches that direct trains to other switches and platforms.

Each switch has one inbound track and two outbound tracks, platforms have one inbound track, and station entrance has one outbound track. Each outbound track is connected to one inbound track and vice versa. Every switch and platform is reachable from station entrance.

Platforms have a rail dead ends and you may assume that trains disappear from the platform immediately after arriving to it.

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

Each morning Ingrid looks at the timetable and writes switch toggling instruction: when and which switch to toggle. She would like to automate this process to save a lot of time.

inputFormat:
The first line of the input file contains a single integer $n$ — the total number of switches and platforms on the station $(3 \le n \le 51)$ .

The i-th of the following $n$ lines describes a switch or a platform with an index $i$ . Description starts with a character `p` for a platform or `s` for a switch. Next number $q_{i}$ indicates the number of the switch the inbound track is connected to or $0$ if it is connected to station entrance $(0 \le q_{i} < i)$ . Description of the platform also contains a unique lowercase English letter — the platform identifier.

Trains spend exactly one minute to move between two connected switches or a switch and a platform. In the morning, each switch is toggled in a way that a train would pass to the one of the two outbound tracks connected to the switch/platform with the lower number.

Next line of the input file contains a single integer $m (1 \le m \le 1000)$ — the number of trains in timetable.

Each of the following $m$ lines contains integer $a_{i} (0 \le a_{i} \le 10 000$ ; $a_{i} > a_{i−1})$ — the time in minutes when a train arrives to the station entrance, and the letter $p_{i}$ — identifier of the destination platform for this train.

outputFormat:
In the first line output integer $c$ — the number of commands in the switch toggling instruction. For each command, output two integers $s_{i}$ and $t_{i} (1 \le s_{i} \le n$ ; $0 \le t_{i} \le 10^{9})$ — the number of the switch and the time to toggle it. Assume that the switch is toggled between minutes $t_{i} − 1$ and $t_{i}.$

Output commands in order of non-decreasing time. The number of commands should not exceed $100 000$ .

translation:
## 题目描述

英格丽德是一家大型火车站的站长，除其他职责外，还负责将火车开到正确的站台。车站有一个入口，有许多道岔将列车引导至其他道岔和站台。

每个道岔有一条入站轨道和两条出站轨道，站台有一条入站轨道，车站入口有一条出站轨道。每个出站磁道连接到一个入站磁道，反之亦然。每个道岔和站台都可以从车站入口到达。

月台有一个铁路死胡同，你可以假设火车到达月台后立即从月台上消失。

每天早上，英格丽德都会查看时间表，并编写切换指令：何时以及切换哪个开关。她希望将此过程自动化以节省大量时间。

## 输入格式

输入文件的第一行包含一个整数n—站点上交换机和平台的总数

以下n行的第i行描述了具有索引i的交换机或平台。说明以字符p开头表示平台，以字符s开头表示交换机。下一个数字q`i`表示入站轨道连接到的道岔的编号，如果连接到车站入口，则表示0(0≤q$i$≤i)平台说明还包含一个唯一的小写英文字母 -- 平台标识符。

列车在两个相连的道岔或道岔与站台之间移动只需一分钟。早上，每一个道岔都会以一种方式进行切换，列车将通过连接到道岔/站台的两条出站轨道中编号较低的一条。
输入文件的下一行包含一个整数m(0≤m≤1000) -- 时刻表上的列车数量。

以下m行中的每一行都包含整数a*i* (0≤a$i$ ≤10000;a$i$>a$i-1$) -- 列车到达车站入口的时间（以分钟为单位），以及字母p*i* -- 列车目的站台的标识符。

## 输出格式

在第一行输出整数c中，开关切换指令中的命令数。对于每个命令，输出两个整数 s`i`和 t$i$ (1≤s$i$ ≤n;0≤ t$i$ ≤10^9) -- 开关的编号和切换开关的时间。假设开关在分钟之间切换 t$i$-1 和 `t`。

按非递减时间顺序输出命令。命令的数量不应超过100000。

samples:
7
s 0
s 1
s 1
p 2 a
p 2 b
p 3 c
p 3 d
5
0 a
1 c
3 b
4 a
5 d

samples:
5
s 0
p 1 y
s 1
p 3 z
p 3 x
3
7 y
8 y
15 y

hint:
Below is the time trace for the first example.

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

Time limit: 2 s, Memory limit: 256 MB.


title: [NWRRC2014] Joy of Flight

description:
Jacob likes to play with his radio-controlled aircraft. The weather today is pretty windy and Jacob has to plan flight carefully. He has a weather forecast — the speed and direction of the wind for every second of the planned flight.

The plane may have airspeed up to $v_{\max}$ units per second in any direction. The wind blows away plane in the following way: if airspeed speed of the plane is $(v_x, v_y)$ and the wind speed is $(w_x, w_y)$, the plane moves by $(v_x+w_x, v_y+w_y)$ each second.

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

Jacob has a fuel for exactly $k$ seconds, and he wants to learn, whether the plane is able to fly from start to finish in this time. If it is possible he needs to know the flight plan: the position of the plane after every second of flight.

inputFormat:
The first line of the input file contains four integers $S_x, S_y, F_x, F_y$ — coordinates of start and finish ($−10 000 ≤ S_x, S_y, F_x, F_y ≤ 10 000$).

The second line contains three integers $n, k$ and $v_{\max}$ — the number of wind condition changes, duration of Jacob’s flight in seconds and maximum aircraft speed ($1 ≤ n, k, v_{\max} ≤ 10 000$).

The following $n$ lines contain the wind conditions description. The $i$-th of these lines contains integers $t_i, w_{x_i}$ and $w_{y_i}$ — starting at time $t_i$ the wind will blow by vector $(w_{x_i}, w_{y_i})$ each second ($0 = t_1 < ··· < t_i < t_{i+1} < ··· < k; \sqrt{w_{x_i}^2 + w_{y_i}^2} ≤ v_{\max}$).

outputFormat:
The first line must contain `Yes` if Jacob’s plane is able to fly from start to finish in k seconds, and `No` otherwise.

If it can to do that, the following $k$ lines must contain the flight plan. The $i$-th of these lines must contain two floating point numbers $x$ and $y$ — the coordinates of the position ($P_i$) of the plane after $i$-th second of the flight.

The plan is correct if for every $1 ≤ i ≤ k$ it is possible to fly in one second from $P_{i−1}$ to some point $Q_i$, such that distance between $Q_i$ and $P_i$ doesn’t exceed $10^{−5}$, where $P_0 = S$. Moreover the distance between $P_k$ and $F$ should not exceed $10^{-5}$ as well.

translation:
## 简述

大意就是一架飞机要从起点飞到终点，飞机有最大空速，飞行最大时间，给出风速的变化和风如何影响飞机飞行，求出飞机是否能到达终点，如果能就输出飞机的位置变化。

## 题目描述

雅各布（Jacob）喜欢玩他的无线电摇制飞机。今天的风很大，雅各布必须小心地计划飞行。他有一个天气预报——飞行计划中每秒钟的风速和风向。

飞机每秒在任何方向的空速最大都可以达到 $v_{max}$ 。风吹动飞机的方式如下：如果飞机的空速是 $(v_x,v_y)$ 并且风速是 $(w_x,w_y)$ ，那么飞机每秒将移动 $(v_x+w_x,v_y+w_y)$ 。

![P7069-1](https://cdn.luogu.com.cn/upload/image_hosting/2uyb1zpd.png)

雅各布（Jacob）有一种刚好能使用$k$秒的燃料，他想知道，飞机是否能在这段时间内从起点飞到终点。如果可能的话，他需要知道飞行计划：每飞行一秒后飞机的位置。

## 输入格式

输入文件的第一行有四个整数 $S_x,S_y,F_x,F_y$ ，代表起始位置 $(-10000 \le S_x,S_y,F_x,F_y \le 10000)$ 。

第二行有三个整数 $n,k 和 v_{max}$ ——风况变化的次数，雅各布（Jacob）飞行持续的时间（以秒为单位）和飞机最大空速。

剩下的 $n$ 行是对风向的描述，第 $i$ 行有三个整数 $t_i,w_{xi} 和 w_{yi}$ ——从时间 $t_i$ 开始，风速为每秒 $(w_{xi},w_{yi})$ （一个向量） $(0=t_1< \cdots <t_i<t_{i+1}< \cdots <k; \sqrt{{w^2_{xi}}+{w^2_{yi}}} \le v_{max})$ 。

## 输出格式

如果 $k$ 秒内雅各布（Jacob）的飞机能从起点飞到终点则应输出 `Yes` ，否则输出 `No` 。

如果它能飞到，接下来的 $k$ 行必须包括飞行计划。第 $i$ 行必须包括两个浮点数 $x$ 和 $y$ （保留几位貌似没说）——飞行了第 $i$ 秒的平面位置 $(P_i)$ 。

如果对于每个 $1 \le i \le k$ 都能在一秒内从点 $P_{i-1}$ 飞到某个点 $Q_i$ ，使得 $Q_i$ 和 $P_i$ 间距离不超过 $10^{-5}$ ，其中 $P_0=S$ ，那么这个计划就是正确的。此外 $P_k$ 和 $F$ 间的距离也应不超过 $10^{-5}$ 。

## 说明/提示

时间限制： $2s$ ；内存限制： $256MB$

by XYY1411

2020/12/08

hint: Time limit: 2 s, Memory limit: 256 MB.


title: [NWRRC2014] Kebab House

description:
The young man Vahtang Bumerang makes kebabs at the world-famous fast-food chain Kebab House. Each kebab contains many ingredients.

This morning Vahtang has received an order to make $n$ kebabs. At first, he should put $q_{1}$ ingredients to the first kebab, then $q_{2}$ ingredients in the second one and so on. Vahtang spends one second to put one ingredient to a kebab, so it takes $q_{i}$ seconds to make the i-th kebab. When he finishes the kebab he immediately proceeds to the next one.

Vahtang often dreams about his lovely boomerang while making kebabs. Each dream takes exactly one second and Vahtang forgets to put one ingredient to kebab during this second. Fortunately, he never dreams twice in any consecutive $(t + 1)$ seconds.

Due to dreams about boomerang, some kebabs may have lesser than the desired number of ingredients, but customers are still happy if the $i$-th kebab has at least $x_{i}$ ingredients in it.

Vahtang wants to calculate the number of ways to have dream seconds during his work while keeping all customers happy. Can you help him? The real answer may be very huge, so you have to calculate it modulo $10^{9} + 7$ .

inputFormat:
The first line of the input file contains two integers $n$ and $t$ — the number of kebabs and minimal possible time between dream seconds $(1 \le n \le 1000$ ; $0 \le t \le 100)$ .

Each of the next $n$ lines contains two integers $q_{i}, x_{i}$ — the number of ingredients in the $i$-th kebab and the minimum number of ingredients to make the $i$-th customer happy $(1 \le q_{i} \le 250$ ; $0 \le x_{i} \le q_{i}).$

outputFormat: The only line of the output file must contain one integer -- the number of ways to distribute dream seconds modulo $10^{9} + 7$ .

translation:
## 题目描述

一个叫Vahtang Bumerang的年轻人在世界知名的连锁快餐店做肉串，每个肉串包含许多成分。

今晨，VB接到了一个肉串订单，首先，他应该将$ q_{1}$种配料放入第一个烤肉串，将$ q_{2}$种配料放入第二个，依此类推。VB将一种配料放进一个肉串需要 $1$ 秒，所以做第 $i$ 个肉串需要 $q_{i}$ 秒。当他完成一个肉串时，他会立即制作一个肉串。

VB在做肉串时经常梦见他可爱的boomerang，做一次梦要一秒钟，而VB却忘了在这一秒钟里将一种配料放到肉串上。幸运的是，他从不在任何连续的 $ (t + 1) $ 秒内做梦超过一次。

由于梦见boomerang，一些肉串可能少于订单所需的配料数量，但如果第 $i$ 个肉串中至少含有 $x_{i}$ 种配料，则客户仍然会感到满意。

VB想知道在让顾客开心的前提下自己有多少种不同的梦见boomerang的方案，请你计算在满足条件下分配做梦秒数的方法数量，答案可能很大，请输出其对$ 10^{9} + 7 $ 取模的结果。

## 输入格式

第一行包含两个整数 $n$ 和 $t$ ，表示烤肉串的数量和两次幻想之间的最小可能秒数。$ (1 \le n \le 1000, 0≤t≤100) $

接下来 $n$ 行，每行包含两个整数 $ q_{i}, x_{i}$ 表示第 $i$ 个订单规定肉串中的配料数量以及使第 $i$ 个客户满意的最少配料数量。$(1 \le q_{i}≤250 ; 0 \le x_{i} \le q_{i})$

输出仅一行，包含一个整数-以模数形式分配梦想秒数的方法数量在 $mod$  $10^9+7$ 意义下的答案。

## 说明/提示

时间限制: 2 s, 空间限制: 256 MB


title: [NWRRC2013] Arrangement of Contest

description:
Little Dmitry and little Petr want to arrange a contest. Their little friends submitted several task proposals and now Dmitry and Petr want to select some of them for the contest. As they are just little boys, they cannot estimate quality of tasks, but they know for sure that in good contest title of the first problem starts with A , the title of the second one -- with $B$ , and so on.

Given titles of the proposed tasks, help little brothers to determine the maximal number of problems in a good contest they can arrange.

inputFormat:
The first line contains single integer $n$ -- the number of problem proposals received by the little brothers $(1 \le n \le 100)$ .

Next $n$ lines contain titles of proposed problems, one per line. The length of each title does not exceed $30$ characters. Each title starts with an uppercase letter and contains only English letters, digits and underscores.

outputFormat: Output a single number -- the maximal number of problems in a good contest. In case there is no good contest that may be arranged, output $0$ .

translation:
**题目描述**

小D和小P想要举行比赛。

他们收到了许多建议书，现在他们想要从这些报名书中挑选一些好的建议。

他们采纳的建议符合以下标准：第一个建议的开头为A，第二个建议的开头为B，以此类推。

请你帮助他们，确定他们所能采纳的建议的最大数量。

**输入格式**

第一行，一个正整数 $n$，表示建议数。

第 $2$ 至 $n+1$ 行，一行一个字符串，表示建议名称。

**输出格式**

一个整数，表示他们所能采纳的建议的最大数量。

**说明/提示**

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

samples:
12
Arrangement_of_Contest
Ballot_Analyzing_Device
Correcting_Curiosity
Dwarf_Tower
Energy_Tycoon
Flight_Boarding_Optimization
Garage
Heavy_Chain_Clusterization
Intellectual_Property
J
Kids_in_a_Friendly_Class
Lonely_Mountain

samples:
3
Snow_White_and_the_7_Dwarfs
A_Problem
Another_Problem


title: [NWRRC2013] Ballot Analyzing Device

description:
Election committee of Flatland is preparing for presidential elections. To minimize human factor in ballot counting they decided to develop an automated Ballot Analyzing Device $(BAD).$

There are $n$ candidates running for president. The ballot contains one square field for each candidate. The voter must mark exactly one of the fields. If no field is marked or there are two or more marked fields, the ballot is invalid. Each voter puts $his/her$ ballot to a special scanner in BAD. The scanner analyzes marks on the ballot and creates a special voting string of $n$ characters: $‘X'$ for marked field and $‘. '$ for unmarked one. Now voting strings must be analyzed to get the report. Your task is to develop a report generator for BAD.

Given voting strings for all ballots, your program must print the voting report. Candidates in the report must be arranged in order of decreasing number of votes. If two candidates have the same number of votes, they must have the same order as in a voting ballot. For each candidate calculate $his/her$ result in percent (if the candidate received $p$ votes, the result in percent is $100p/m)$ . The last line of the report must indicate the percentage of the invalid ballots.

inputFormat:
The first line contains two integers $n$ and $m$ -- the number of candidates and the number of ballots $(2 \le n \le 10$ ; $1 \le m \le 1000)$ . The following $n$ lines contain last names of candidates. Each name is a string of at most $100$ English letters. There is no candidate named `Invalid`.

Then $m$ lines follow, each of them contains one voting string.

outputFormat:
Print n+ $1$ lines. First print results for candidates in percent. For each candidate print $his/her$ last name followed by a space and then $his/her$ result in percent and a percent sign $‘\%'.$ The last line must specify the percentage of invalid ballots: a word `Invalid` followed by a space, the percentage of invalid ballots and a percent sign.

Round all numbers to exactly two digits after the decimal point. If the number is exactly in the middle of two representable numbers, output the greater one (e.g . output `12 . $35`$ for $12$ . $345$) .

translation:
有 $n$ 名选手参加一个比赛，有 $m$ 个人为他们投票。第 $i$ 个人的投票情况用一个长度为 $n$，并且仅包含 `.` 和 `X` 两个字符的字符串，其中，如果第 $j$ 位是 `X`，则第 $i$ 个人将票投给了第 $j$ 名选手，否则没有。规定每个投票者能且仅能将票投给一个人，否则都算无效票（即投的票数 $\geqslant 2$ 或者 $=0$）。请将每名选手按照他们所得到的票的比例排序（如果有两名选手得到的票的比例相同，在投票次序中先出现的那名选手排在前面），并输出他们的名字和得票比例，最后还要输出无效票所占的比例。

Translated by Eason_AC
2020.11.12

samples:
4 7
Loudy
Apples
Dogman
Miller
.X..
X...
....
..X.
..XX
..X.
..X.

samples:
Dogman 42.86%
Loudy 14.29%
Apples 14.29%
Miller 0.00%
Invalid 28.57%


title: [NWRRC2013] Correcting Curiosity

description:
Curiosity is the rover that explores the Gale Crater on Mars. Recently it found an evidence of water in Martian soil, which will make it easier to plan the future manned missions. $ $

Curiosity can communicate with Earth directly at speeds up to $32 Kbit/s$ , but on average $14$ minutes and $6$ seconds will be required for signals to travel between Earth and Mars.

`You have just seen a stone and applied brakes, but you know that the rover is already passing that stone` -- Matt Heverly, the rover's driver, explains. `So we just plan the route, then write down a list of simple textual commands: move one meter ahead, turn left, make a photo and so on`.

Sometimes it is necessary to react very fast to some unexpected events. For example, if the cameras have seen something interesting, then you might want to change the route of the rover to make an additional photo. To do that, you send a substitution command of the form $s/〈string〉/〈replacement〉/g$ . This replaces all occurrences of $〈string〉,$ starting with the leftmost one, to $〈replacement〉.$

More formally, if A is a non-empty string and $B$ is a string, then to apply the substitution command $s/A/B/g$ to a string $S$ , you should do the following:

Find the leftmost occurrence of A in $S$ , such that $S =$ SL $+$ A $+$ SR.

If there is no such occurrence, stop. Then, $S$ is the answer.

Let $R$ be the result of applying $s/A/B/g$ to SR.

The answer is SL $+ B + R$ .

This means that:

If there are two overlapping occurrences of A in $S$ , only the leftmost one is replaced. For example, applying $`s/aba/c/g`$ to `abababa` yields `cbc`: after replacing the first occurrence of `aba` the string turns to `cbaba`, and only the last occurrence of `aba` can be replaced after that.

No substitution uses the results of previous substitutions. For example, applying $`s/a/ab/g`$ to `a` yields `ab`, applying $`s/a/ba/g`$ to `a` yields `ba`.

You know that the longer is the command, the bigger is the time necessary to transmit it. So, you have to write a program that finds shortest command that transforms the initial string to the final string.

inputFormat: The first line contains the initial and the final strings. Both strings are non-empty and their lengths do not exceed $2000$ characters. The strings contain only English letters, spaces and punctuation signs (commas, colons, semicolons and hyphens: $‘,', ‘:', ‘;', ‘-').$ The given strings are not equal.

outputFormat: Output the substitution command that transforms initial string to final string and has the minimum length. If there are several shortest substitution commands, output any of them.

translation:
# [NWRRC2013] Correcting Curiosity

## 题目描述

“好奇号”是探索火星上盖尔陨石坑的火星车。最近，它在火星土壤中发现了水存在的证据，这将使未来的火星登陆任务变得更加容易。$ $

“好奇号”可以用高达$32 Kbit/s$的速度与地球直接通信 ，但在地球和火星之间传输信号分别平均需要$14$秒和$6$秒。

`你刚刚看到一块石头并踩下了刹车，但你知道火星车已经经过那块石头了` -- 火星车司机Matt Heverly解释道。`所以我们需要规划路线，然后写下一个简单的命令列表：如向前移动一米，左转，拍照等等`.

有时你有必要对一些突发事件做出非常迅速的反应。例如，当相机看到了一些有趣的东西，那么你可能会想改变火星车的路线来拍摄的照片。为此，您需要发送一个形式为 $s/〈string〉/〈replacement〉/g$ . 这将替换所有出现的 $〈string〉,$ 从最左边的开始, 到 $〈replacement〉.$

更确切地说，如果A是非空字符串，而$B$是字符串, 则要将替换命令$s/A/B/g$应用于字符串$s$，执行以下操作：

在$S$中查找最左边出现的A，这样$S=$SL$+$A$+$SR。

如果没有A，请停止操作。$S$就是答案。

让$R$成为对SR应用$s/A/B/g$的结果。

那么答案是SL$+B+R$。

这就说明:

如果在$S$中有两个重叠的A，那么只替换最左边的一个。例如，将$`s/aba/c/g`$应用于`abababa`会产生`cbc`：在替换第一个`aba `之后，字符串将变为`cbaba `，在此之后只能替换最后一个出现的` aba `。

如果没有替换就使用先前替换的结果。例如，将$`s/a/ab/g`$应用于`a`产生`ab`，将$`s/s/a/ba/g`$应用于`a`产生`ba`。

命令越长，传输它所需的时间就越长。因此，需要你编写一个程序，找到最短的命令，将初始字符串转换为最终字符串。

## 输入格式

第一行输入包含初始字符串和最终字符串。这两个字符串都不是空的，并且它们的长度不超过$2000$。字符串仅包含英文字母、空格和标点符号（逗号、冒号、分号和连字符：$'，'，'：'，'；'，'-'）。$给定的字符串不相同。

## 输出格式

输出将初始字符串转换为最终字符串并最短的替换命令。如果有多个最短的替换命令，请输出其中任何一个。

## 样例 #1

### 样例输入 #1

```
move left, move right; move up
move left, move down, move up
```

### 样例输出 #1

```
s/right;/down,/g
```

## 样例 #2

### 样例输入 #2

```
If not found: move x; else move -x
If found: move x; else move -x
```

### 样例输出 #2

```
s/ not//g
```

## 样例 #3

### 样例输入 #3

```
abababa
cbc
```

### 样例输出 #3

```
s/aba/c/g
```

## 提示

时间限制: 2 s, 内存限制: 256 MB.


title: [NWRRC2013] Dwarf Tower

description:
Little Vasya is playing a new game named "Dwarf Tower". In this game there are $n$ different items, which you can put on your dwarf character. Items are numbered from $1$ to $n$ . Vasya wants to get the item with number $1$ .

There are two ways to obtain an item:

You can buy an item. The i-th item costs $c_i$ money.

You can craft an item. This game supports only $m$ types of crafting. To craft an item, you give two particular different items and get another one as a result.

Help Vasya to spend the least amount of money to get the item number $1$ .

inputFormat:
The first line contains two integers $n$ and $m (1 \le n \le 10000 , 0 \le m \le 100000) -$ the number of different items and the number of crafting types.

The second line contains $n$ integers $c_i -$ values of the items $(0 \le c_i \le 10^9)$ .

The following $m$ lines describe crafting types, each line contains three distinct integers $a_i, x_i, y_i$ -- $a_i$ is the item that can be crafted from items $x_i$ and $y_i (1 \le  a_i, x_i, y_i \le n , a_i \ne x_i, x_i \ne y_i, y_i \ne a_i)$.

outputFormat: Print a single integer -- the least amount of money to spend.

translation:
### 题目描述
小Vasya 在玩一个新游戏叫做 Dwarf Tower。在这个游戏中有 $n$ 个不同的衣物给你的矮人。衣物从 $1$ 到 $n$ 进行编号。Vasya 想要获得编号为 $1$ 的衣物。

现在有两种方法获得一件衣物：

1. 你可以买它，第 $i$ 件物品花费 $c_i$ 元。

1. 你还可以制作它，这个游戏支持 $m$ 中制作方法。要制作一个衣物，你需要花费两个特定的衣物。

算出 Vasya 至少需要多少钱来获得一号衣物。

### 输入格式
第一行输入两个整数 $n$ , $m$ $(1 \le n \le 10000 , 0 \le m \le 100000) $ 代表有 $n$ 种衣物和有 $m$ 种制作方法。

第二行输入 $n$ 个整数，第 $i$ 个整数代表 $c_i$ $(0 \le c_i \le 10^9)$ 。

接下来 $m$ 行每行有三个整数 $a_i, x_i, y_i$ $(1 \le a_i, x_i, y_i \le n , a_i \ne x_i, x_i \ne y_i, y_i \ne a_i)$ ，$a_i$ 代表 $a_i$ 可以被 $x_i$ 和 $y_i$ 制作。

### 输出格式
一个整数，代表 Vasya 至少需要多少钱来获得一号衣物。


title: [NWRRC2013] Energy Tycoon

description:
Little Vasya is playing a new computer game -- turn-based strategy `Energy Tycoon`.

The rules of the game are quite simple:

The board contains $n$ slots arranged in a line.

There are power plants, one power plant occupies one or two consecutive slots, and produces one unit of energy.

Each turn the game allows you to build one new power plant, you can put it on the board if you wish. If there is no place for the new power plant, you can remove some older power plants.

After each turn, the computer counts the amount of energy produced by the power plants on the board and adds it to the total score.

![](/upload/images2/enegrgytycoon.png)

Vasya already knows the types of power plant he will be able to build each turn. Now he wants to know, what the maximum possible score he can get is. Can you help him?

inputFormat: The first line of the input contains one integer $n (1 \le n \le 100 000)$ -- the number of slots on the board. The second line contains the string $s$ . The i-th character of the string is $1$ if you can build one-slot power plant at the i-th turn and the character is $2$ if you can build two-slot power plant at the i-th turn. The number of turns does not exceed $100 000$ .

outputFormat: The output should contain a single integer -- the maximal score that can be achieved.

translation:
Vasya 正在玩一款新的电脑游戏 `Energy Tycoon`

游戏的规则非常简单：

有一行 $n$ 个空位。

有一些能源装置，每个能源装置会占用 $1$ 或 $2$ 个相邻的空位，并且每回合产生一个单位的能量。

在游戏里，每个回合可以建造一个新的能源装置（也可以不建造）。如果没有地方建新的能源装置，可以拆除一些旧的能源装置。

每一回合过后，电脑会统计这一回合内所有已经建造的能源装置产生的能量，并将其加到总分中。

Vasya 已经知道了每个回合他可以建造的能源装置的类型。现在他想知道，他能得到的最大分数是多少。你能帮他吗?


title: [NWRRC2013] Flight Boarding Optimization

description:
Peter is an executive boarding manager in Byteland airport. His job is to optimize the boarding process. The planes in Byteland have $s$ rows, numbered from $1$ to $s$ . Every row has six seats, labeled A to $F$ .

![](/upload/images2/flgithseat.png)

There are $n$ passengers, they form a queue and board the plane one by one. If the i-th passenger sits in a row $r_{i}$ then the difficulty of boarding for him is equal to the number of passengers boarded before him and sit in rows $1$ . . . $r_{i}−1$ . The total difficulty of the boarding is the sum of difficulties for all passengers. For example, if there are ten passengers, and their seats are $6A, 4B, 2E, 5F, 2A, 3F, 1C, 10E, 8B, 5A,$ in the queue order, then the difficulties of their boarding are $0 , 0 , 0 , 2 , 0 , 2 , 0 , 7 , 7 , 5$ , and the total difficulty is $23$ .

To optimize the boarding, Peter wants to divide the plane into $k$ zones. Every zone must be a continuous range of rows. Than the boarding process is performed in $k$ phases. On every phase, one zone is selected and passengers whose seats are in this zone are boarding in the order they were in the initial queue. $ $

In the example above, if we divide the plane into two zones: rows $5-10$ and rows $1-4$ , then during the first phase the passengers will take seats $6A, 5F, 10E, 8B, 5A,$ and during the second phase the passengers will take seats $4B, 2E, 2A, 3F, 1C,$ in this order. The total difficulty of the boarding will be $6$ .

Help Peter to find the division of the plane into $k$ zones which minimizes the total difficulty of the boarding, given a specific queue of passengers.

inputFormat:
The first line contains three integers $n (1 \le n \le 1000) , s (1 \le s \le 1000)$ , and $k (1 \le k \le 50$ ; $k \le s)$ . The next line contains $n$ integers $r_{i} (1 \le r_{i} \le s)$ .

Each row is occupied by at most $6$ passengers.

outputFormat: Output one number, the minimal possible difficulty of the boarding.

translation:
## 题目描述

Peter是 Byteland 机场的高级登机管理人员。他的工作是优化登机流程。Byteland 中的飞机有$s$行，编号从1到$s$。每排有六个座位，标有$A$到$F$。

有$n$名乘客，他们排成一队，一个接一个地登上飞机。如果第$i$位乘客坐在第$r_i$排，那么，他登机的难度等于在他前面登机的并且坐在第1......$r_i$ $-$1排的乘客人数之和。

登机的总难度是所有乘客的登机难度之和。例如，如果有十名乘客，他们的座位分别是$6A、4B、2E、5F、2A、3F、1C、10E、8B、5A$，按照排队顺序排列，那么他们登机的难度分别是$0、0、0、2、0、2、0、7、7、5$，总难度是$23$。

为了优化登机，Peter希望将飞机划分成$k$个区域。每个分区都必须是连续的行数。然后分成$k$段执行登机流程。在每个阶段，选择一个区域，座位在该区域的乘客将按照他们在初始队列中的顺序登机。

在上面的示例中，如果我们将平面划分为两个区域：第 $5-10$ 行和第$1-4$ 行，则在第一阶段，乘客将依次就座$6A、5F、10E、8B、5A$。在第二阶段，乘客将依次就座$4B、2E、2A、3F、1C$。登机的总难度为$6$。

帮助Peter找到将飞机划分为$k$个区域的方法，在给定特定乘客队列的情况下，将登机的总难度降至最低。

## 输入格式

第一行包括三个整数$n(1≤n≤1000)$,$s(1≤s≤1000)$和$k(1≤k≤1000)$

第二行包括$n$个整数$r_i(1≤r_i≤s)$

## 输出格式

输出一行一个数，最小的登机总难度


title: [NWRRC2013] Garage

description:
Wow! What a lucky day! Your company has just won a social contract for building a garage complex. Almost all formalities are done: contract payment is already transferred to your account.

So now it is the right time to read the contract. Okay, there is a sandlot in the form of $W \times H$ rectangle and you have to place some garages there. Garages are $w \times h$ rectangles and their edges must be parallel to the corresponding edges of the sandlot (you may not rotate garages, even by $90^{◦}).$ The coordinates of garages may be non-integer.

You know that the economy must be economical, so you decided to place as few garages as possible. Unfortunately, there is an opposite requirement in the contract: placing maximum possible number of garages.

Now let's see how these requirements are checked. . . The plan is accepted if it is impossible to add a new garage without moving the other garages (the new garage must also have edges parallel to corresponding sandlot edges).

![](https://www.acmicpc.net/upload/images2/garage.png)

Time is money, find the minimal number of garages that must be ordered, so that you can place them on the sandlot and there is no place for an extra garage.

inputFormat: The only line contains four integers: $W , H , w , h$ -- dimensions of sandlot and garage in meters. You may assume that $1 \le w \le W \le 30 000$ and $1 \le h \le H \le 30 000$ .

outputFormat: Output the optimal number of garages.

translation:
你有一个 $W \times H$ 的大长方形。你又有无数个 $w \times h$ 的小长方形。请问，最少放入几个小长方形后，你无法再往这个大长方形里放入更多的小长方形。

所有小长方形不能重叠，也不能旋转。


title: [NWRRC2013] Heavy Chain Clusterization

description:
A group of biologists is trying to find a cure for a viral disease. They have tried many antibodies of various origins that could potentially fight the viral antigens, and have selected $n$ antibodies that seem to work best during experiments.

Each antibody is identified by its heavy chain -- a sequence of amino acids.

The set of antibodies form a similarity cluster, if at least one of the following holds:

k-prefixes (first $k$ amino acids) of all their heavy chains are equal;

k-suffixes (last $k$ amino acids) of all their heavy chains are equal.

In order to simplify the future research, biologists want to group antibodies to similarity clusters.

You need to split the given antibodies to a minimum number of similarity clusters.

inputFormat:
The first line contains two integers $n$ and $k$ -- the number of heavy chains and the length of sequence of amino acids to coincide $(1 \le n \le 5 000 , 1 \le k \le 550)$ .

The following $n$ lines contain sequences of amino acids that form heavy chains of antibodies. Each amino acid described with an uppercase English letter. Each heavy chain contains at least $k$ and no more than $550$ amino acids.

outputFormat:
The first line of output must contain a single integer -- the minimum number of similarity clusters. The following lines must contain descriptions of clusters, one per line.

Each description starts with $m_i$ -- the number of antibodies in the cluster and is followed by $m_i$ integers -- numbers of these antibodies. Antibodies are numbered in the order of appearance in the input starting from one.

Each antibody must be present in exactly one cluster.

translation:
现有$n$个抗生素，每一个抗生素都可以通过它的一个氨基酸序列被辨认。

如果有一组抗生素满足以下任意一个条件，这些抗生素才可以形成一个“相似群体”：

1. 组内所有抗生素的氨基酸序列的前$k$个氨基酸元素组成的序列全部相同

2. 组内所有抗生素的氨基酸序列的后$k$个氨基酸元素组成的序列全部相同

特别的，一种抗生素可以成为一个相似群体。

为了简化后续研究，生物学家们想要给抗生素分类，使得这$n$个抗生素被分成若干个相似群体。你需要找出一种方案，使得分类后的相似群体数量最少。

------

第一行包含两个正整数，$n$和$k$，含义如题意描述。（$1≤n≤5000，1≤k≤550$）

接下来有$n$行，每行包含一个氨基酸序列。氨基酸序列被描述为由大写英语字母组成的字符串，每个序列包含不少于$k$个，不多于$550$个英文字符。每个英文字符代表一种不同的氨基酸。

------

第一行包含一个正整数$ans$，表示被分成的相似群体最小可能的数目。

接下来有$ans$行，每行第一个数为$m_i$，表示第$i$个相似群体有$m_i$个元素。接下来有$m_i$个数，第$j$个数表示这个相似群体包含输入中的第$j$个抗生素。（编号从$1$开始。）

每一个抗生素必须恰好出现一次。


title: [NWRRC2013] Intellectual Property

description:
Erast Kopi is famous Sudoku puzzle designer. Resounding success of his puzzle compilations caused a number of imitations and plagiarisms. Prior to sending a lawsuit he decided to get more evidence.

Sudoku puzzle is a table $9 \times 9$ , divided into $3 \times 3$ subtables of $3 \times 3$ cells each. Each cell may contain a digit from $1$ to $9$ . The task is to fill empty cells with digits in a way that each row, each column and each of the $9$ subtables $3 \times 3$ contains each digit from $1$ to $9$ exactly once.

Kopi has a database of Sudoku puzzles and he wants to check if it contains similar puzzles. The puzzle $P$ is similar to the puzzle $Q$ , if it is possible to transform the puzzle $P$ into the puzzle $Q$ using a sequence of the following operations:

choose two digits $x$ and $y$ and replace all digits $x$ with $y$ and vice versa;

swap two triples of rows: $(1 , 2 , 3) , (4 , 5 , 6) , (7 , 8 , 9)$ ;

swap two rows in one triple of rows;

swap two triples of columns: $(1 , 2 , 3) , (4 , 5 , 6) , (7 , 8 , 9)$ ;

swap two columns in one triple of columns;

flip along top-left -- bottom-right axis. After this operation columns become rows and vice versa.

![](/upload/images2/ip.png)

Help Kopi to find similar puzzles in his database.

inputFormat:
The first line of the input contains single integer $n$ -- the number of puzzles in the database $(1 \le n \le 20)$ .

The rest of the input contains description of $n$ puzzles: $P_1 , P_2$ , . . . , Pn. Each puzzle is described by nine lines that contain nine characters each. Each character is either a digit from $1$ to $9$ , or a dot $(‘. ')$ denoting an empty cell. An empty line separates consecutive puzzles in the database.

There are no spaces in the input file.

The puzzles are not guaranteed to be solvable.

outputFormat:
Check if the puzzle $P_1$ is similar to puzzles $P_2$ , P3 , . . . , $P_n$ (in this order), than check if the puzzle $P_2$ is similar to puzzles P3 , P4 , . . . , $P_n$ (in this order) and so on.

If the puzzle $P_i$ is similar to the puzzle $Pj (1 \le i < j \le n)$ output `Yes`, otherwise output `No`. If the answer is positive, the next line should contain an integer qij -- the number of operations required to transform the puzzle $P_i$ to the puzzle $Pj$ . The number of operations is not required to be minimal, however it must not exceed $1000$ . In the following qij lines write the operations that transform the puzzle $P_i$ to the puzzle $Pj$ , one per line.

Operations are encoded in the following way:

`D $x$ y` for swapping digits $x$ and $y$ ;

`R a b` for swapping triples of rows (3a $− 2$ , 3a $− 1 , 3a)$ and (3b $− 2$ , 3b $− 1 , 3b);$

`r a b` for swapping rows a and $b$ , rows must belong to same triple of rows;

`C a b` for swapping triples of columns (3a $− 2$ , 3a $− 1 , 3a)$ and (3b $− 2$ , 3b $− 1 , 3b);$

`c a b` for swapping columns a and $b$ , columns must belong to same triple of columns;

`F` for flipping along top-left -- bottom-right axis.

The columns are numbered from left to right and the rows are numbered from top to bottom as they are given in the input file, starting from one.

translation:
对于两个 $9\times9$ 数独谜题（不管是否有解）$A,B$，定义 $A$ 和 $B$ 等价当且仅当 $A$ 可以通过下列操作进行若干次变换后成为 $B$。
- 选择两个数字 $x,y$，将所有 $x$ 变成 $y$，所有 $y$ 变成 $x$。
- 在 $(1,2,3),(4,5,6),(7,8,9)$ 三个三元组中，选择两个，作为整体交换以它为下标的行。
- 选择在同一个三元组中的两个数 $x,y$，交换谜题的第 $x$ 行和第 $y$ 行。
- 在 $(1,2,3),(4,5,6),(7,8,9)$ 三个三元组中，选择两个，作为整体交换以它为下标的列。
- 选择在同一个三元组中的两个数 $x,y$，交换谜题的第 $x$ 列和第 $y$ 列。
- 把 $A$ 转置。

现在给定 $n(n\le20)$ 个数独谜题，判断它们两两是否等价。若等价，还需要输出一种变换的方法。`D x y` 表示将两个数字交换，`R a b` 表示整体交换三元组 $(3a-2,3a-1,3a),(3b-2,3b-1,3b)$ 对应的行，`r a b` 表示交换两个行，同理有 `C a b` 和 `c a b` 作为列操作。`F` 表示取转置。

translated by @Starlight237

samples:
Yes
7
C 1 2
D 5 3
F
r 7 9
c 6 5
C 2 3
D 1 8
No
Yes
0
No
Yes
8
R 1 2
C 2 3
c 4 5
F
r 5 6
c 7 9
D 1 8
D 3 5
No


title: [NWRRC2013] J

description:
The $J$ programming language, developed in the early $1990s$ by Kenneth $E$ . Iverson and Roger Hui, is a synthesis of APL (also by Iverson) and the FP and FL function-level languages created by John Backus.

Wikipedia. $J$ (programming language)

APL language family is famous for its support of advanced operations on vectors and arrays, and $J$ is not an exception. For example, all unary and binary numeric operations in these languages by default are applicable to vectors and arrays of different dimensions. Plus operation $(‘+')$ can add not only scalars, like in other languages, but also scalars and vectors (the scalar is added to each component of the vector), or vectors and vectors (the vectors are added component-wise).

The expressive power of $J$ is amazing (as well as its cryptic syntax), but for this problem we need just a small subset of the language. We consider a single expression, where we may use one vector variable $X$ , one scalar variable $N$ -- the length of the vector $X$ , and the following operations:

We can add $(‘+'),$ subtract $(‘-')$ or multiply $(‘ \times ')$ two vectors, vector and scalar, or two scalars.

We can use unary minus $(‘-')$ and unary squaring operations $(‘ \times :')$ for scalars and vectors $(component-wise).$

We can fold a vector with plus operation $(‘+/')$ -- that is, compute the sum of a vector (unary operation).

Operations are evaluated right-to-left, natural precedence of operations is ignored in $J$ . The order of evaluation can be altered by parentheses. More precisely the syntax is specified in the following BNF.

$〈expressio_n〉 ::= 〈ter_m〉 | 〈ter_m〉 (‘+' | ‘-' | ‘ \times ') 〈expressio_n〉 | (‘-' | ‘ \times :' | ‘+/') 〈expressio_n〉$

$〈ter_m〉 ::= ‘('〈expressio_n〉‘)' | ‘X' | ‘N' | 〈number〉$

$〈number〉 ::= (‘0' | ‘1' |$ . . . $| ‘9')^{+}$

To correctly impose one more limitation on expression syntax, let us define complexity of an expression:

complexity of scalars (numbers, $‘N',$ and result of fold) is zero;

complexity of $‘X'$ is one;

complexity of addition and subtraction is the maximum of their operands' complexities;

complexity of multiplication is the sum of its operands' complexities;

complexity of unary squaring is twice the complexity of its operand.

For example, the complexity of expression $`(3-+/ \times : \times :X)-X \times \times :X`$ is $3$ , while the complexity of its subexpression $` \times : \times :X`$ is $4$ .

Your program is given a scalar-valued expression and a value of the vector $X$ , and it should compute the expression result modulo $10^{9}.$ The complexity of each subexpression in the given expression does not exceed $10$ .

inputFormat:
The first line contains one integer number $N (1 \le N \le 10^{5})$ -- the length of the vector $X$ .

The second line contains $N$ integers -- components of the vector $X (0 \le X_{i} < 10^{9}).$

The third line contains the expression to be computed, a non-empty string of not more than $105$ symbols. Each number in the expression is less than $109$ . The fold is never applied to a scalar.

outputFormat: Output a single integer number -- the expression result modulo $10^{9}.$

translation:
本题中，J 语言为一个表达式，满足如下的 Backus-Naur 范式：
```
<expression> ::= <term> | <term> ('+' | '-' | '*') <expression> | ('-' | > '*:' | '+/') <expression>
<term> ::= '(' <expression> ')' | 'X' | 'N' | <number>
<number> ::= ('0' | '1' | ... | '9')+
```
对于一个双目运算符，当操作数为数值和向量时，它的效果是将数值和向量中的每一维分量分别做运算；当操作数为两个向量时，它的效果是将向量中的每一维分量对应做运算。特别地，在本题中，所有的向量均相同。

Backus-Naur 范式中出现的记号解释如下：
- 加法、减法、乘法运算 `'+','-','*'`
- 单目运算 `'-','*:','+/'`。`-A` 表示对 A 取负，`*:A` 表示对 A 求平方，`+/` A 称为**折叠**，表示对向量 A 的所有分量求和。
- 括号 `'(',')'`。没有括号时，所有运算符优先级相同，括号可以改变运算顺序，效果同通常的括号。
- 数字。
- 字母 `'N','X'`。N 在处理时等价于一个事先被给定的数字，X 则等价于一个事先被给定的向量。
- 单元。表达式、数字和字母被统称为单元。
- 表达式。若干个单元用双目和单目运算符按照符合语法规则的方式连接起来，所得到的字符串称为一个表达式。表达式中不得包含上文中没有提到的其他字符。
- 注意：J 语言的表达式是**右结合**的，你可以理解为从右往左计算，但是对于不满足交换律的减法操作，我们规定 `A-B` 仍然表示用 A 减去 B 而不是 B 减去 A。对于一个数字，我们规定它仍然是从左往右读的。比如 `123` 应当理解为 100+20+3 而不是 300+20+1。

每个表达式被定义了一个**复杂度**，我们规定所有数值（标量）的复杂度为 0，`X` 的复杂度为 1，加法运算和减法运算 `A+B,A-B` 的复杂度为 `A` 和 `B` 复杂度的最大值。`A*B` 的复杂度为两者复杂度之和，单目取反运算不改变表达式的复杂度，平方运算将表达式的复杂度变成它的两倍，折叠运算将表达式的复杂度变成 0。

你首先需要读入 $N,X(N\le10^5)$，保证 N 等于 X 的长度。X 中所有分量全为不超过 $10^9$ 的正整数。然后一行读入一个表达式 `expr`，保证它的复杂度不超过 10，并且长度不超过 $10^5$ 个字符，且完全符合语法规则。你需要求出 `expr` 的值模 $10^9$ 的结果（保证值一定是个标量而不是向量）。

translated by @Starlight237


title: [NWRRC2013] Kids in a Friendly Class

description:
Kevin resembles his class in primary school. There were girls and boys in his class. Some of them were friends, some were not. But if one person considered another person a friend, the opposite was also true.

Interestingly, every girl had exactly a friends among girls and exactly $b$ friends among boys, whereas every boy had exactly $c$ friends among girls and exactly $d$ friends among boys.

Kevin does not remember the size of his class. Help him reconstruct the class with minimal possible number of kids, such that the above conditions are satisfied.

inputFormat: The only line contains four integers $a , b , c$ , and $d (1 \le a , b , c , d \le 50)$ .

outputFormat:
Output an example of a class of minimal possible size satisfying the above conditions.

The first line should contains two positive integers: $m$ -- the number of girls, and $n$ -- the number of boys.

Let's assign numbers $1$ through $m$ to the girls and $m + 1$ through $m + n$ to the boys.

Each of the next lines should contain a pair of distinct integers describing a pair of friends by their numbers. Each pair of friends should appear exactly once in this list.

translation:
### 题目描述
凯文的班级里有女生也有男生。他们中有些人是朋友，有些人不是。但是，如果A认为B是他的朋友，那么B也认为A是他的朋友。

有趣的是，每个女生都有 a 个女性朋友和 b 个男性朋友，而每个男生都有 c 个女性朋友和 d 个男性朋友。

凯文不记得自己班级的人数。请算出班级的人数，使得班级人数尽可能少，同时又能满足上面的条件。
### 输入格式
只有一行，包括4个整数 a , b , c，d (1≤a,b,c,d≤50) .
### 输出格式
输出一个班级人数，使得其数量尽可能小又满足上述条件。

第一行应该包括两个正整数 m —— 女生人数 n —— 男生人数。

用编号1 到 m 表示女生，编号 m+1 到m+n 表示男生。

接下来的每一行，都应该包含一对不同的整数，来表示一对朋友，而且每对朋友只出现一次。


title: [NWRRC2013] Lonely Mountain

description:
"This was made by Thror, your grandfather, Thorin", he said in answer to the dwarves' excited questions. "It is a plan of the Mountain. "

---

J. R. R. Tolkien. The Hobbit, or There and Back Again

The plan of the Lonely Mountain consists of two parallel projections of the mountain to two projection planes. Both planes are perpendicular to the ground and each other. Each projection has a mountain-like shape.

![](https://www.acmicpc.net/upload/images2/lonely.png)

Since Bilbo Baggins has never seen the mountain, he tries to imagine it. Is it really the Lonely Mountain or some ridges and other mountains surround it? In any case, it must be tremendous to hold the whole dwarves' kingdom!

Bilbo decided to estimate the maximum possible volume of the Lonely Mountain and nearby mountains (if any) based on the plan provided by Gandalf.

inputFormat:
The first line contains single integer number $n_{x}$ -- the number of points in the parallel projection of the mountain to the plane Oxz $(2 \le n_{x} \le 100 000)$ . The second line contains $n_{x}$ pairs of integer numbers $x_{i}, z_{i}$ -- the coordinates of the polygonal chain, representing the projection $(−10^{9} \le x_{1} < x_{2} <$ x3 $< · · · < x_{n_{x}} \le 10^{9}; 0 \le z_{i} \le 10^{9}; z_{1} = z_{n_{x}} = 0)$ .

The following two lines contain projection to the Oyz plane in the same format.

outputFormat:
The only line of the output file must contain a single number $V$ -- the maximum possible volume of the Lonely Mountain.

The absolute or relative precision of you answer should be at least $10^{−6}.$ E.g . if $V′is$ the actual maximum possible volume, the following must hold: $mi_n(|V−V′|,|V−V′|/V′) \le 10^{−6}.$

If there are no mountains corresponding to the given projections, output a single line `Invalid plan`.

translation:
给定一个几何体的正视图和侧视图，求其最大体积。

### 输入格式

第一行一个整数 $n_x$ 表示正视图中点的数量。

第二行按 $x_i$ 递增的顺序给出 $n_x$ 个点对 $(x_i,z_i)$ 描述其正视图，保证 $z_1=z_{n_x}=0$

第三、四行同理，描述其侧视图。

所有的输入都是整数。

### 输出格式

若不存在一个合法方案，输出 ```Invalid plan```，否则输出最大体积。

你的答案与正确答案的绝对误差不应超过 $10^{-6}$.


title: [COCI2020-2021#1] 3D Histogram

background: ~~原题目背景其实是一个出毒瘤题的套路，有兴趣的同学可以去看看，这里懒得翻译了~~

description:
在一个三维直方图中，放入 $n$ 个三维块，这些三维块的宽度均为 $1$，且能使得在正面看是一个从左到右分别高度为 $a_i$ 的二维直方图，在上面看是一个从左到右分别高度为 $b_i$ 的二维直方图。

求在直方图中能放入的最大体积长方体的体积是多少，长方体的所有边均要与三维块的长宽高平行。

inputFormat:
第一行一个整数 $n$ 代表三维块数量。
接下来 $n$ 行每行两个整数 $a_i,b_i$，如题目描述。

outputFormat: 一行一个整数代表能放入的最大长方体体积。

hint:
#### 样例 1 解释

描述的直方图如下图所示：

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

能放入的最大长方体体积为 $2 \times 4 \times 3=24$。

#### 数据规模与约定

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

- Subtask 1（20 pts）：$1 \le n \le 2000$。
- Subtask 2（90 pts）：$1 \le n \le 2 \times 10^5$。

对于 $100\%$ 的数据，$1 \le a_i,b_i \le 10^6$。

**本题满分 $110$ 分。**

#### 说明

翻译自 [Croatian Open Competition in Informatics 2020 ~ 2021 Round 1 C 3D Histogram](https://hsin.hr/coci/archive/2020_2021/contest1_tasks.pdf)。


title: [COCI2020-2021#1] Papričice

description:
给定一个 $n$ 个点的树，这 $n$ 个点编号为 $1$ 到 $n$。

现在要选择断掉两条边，会形成三个连通块，假设这三个连通块内的点数分别为 $a,b,c$，那么您要做的就是最小化 $\max\{a,b,c\}-\min\{a,b,c\}$ 的大小，求这个最小值。

inputFormat:
第一行一个整数 $n$ 代表树的点数。
接下来 $n-1$ 行每行两个整数 $x,y$ 代表树的一条边。

outputFormat: 一行一个整数代表答案。

hint:
#### 样例 1 解释

能构造的最优解三个连通块的点数都为 $1,1,2$，所以输出 $2-1=1$。

#### 样例 2 解释

断掉点 $1$ 到点 $3$ 的边，点 $3$ 到点 $5$ 的边，形成的三个连通块点数相同。

#### 样例 3 解释

如下图所示：

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

#### 数据规模与约定

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

- Subtask 1（15 pts）：$3 \le n \le 200$。
- Subtask 2（35 pts）：$3 \le n \le 2000$。
- Subtask 3（60 pts）：$3 \le n \le 2 \times 10^5$。

对于 $100\%$ 的数据，$1 \le x,y \le n$。

**本题满分 $110$ 分。**

#### 说明

翻译自 [Croatian Open Competition in Informatics 2020 ~ 2021 Round 1 D Papričice
](https://hsin.hr/coci/contest1_tasks.pdf)。


title: [COCI2020-2021#1] Tenis

description:
你是网球比赛的组织者，一场有 $n$ 个选手的比赛就要举办了，选手编号为 $1$ 到 $n$。在赛前你测试了他们在三种场地（A 场地，B 场地，C 场地）分别的初始排名，在这场比赛中，两个人之间比赛的场数恰好为一次，也就是说总共有 $\dfrac{n \times (n-1)}{2}$ 场比赛。

比赛不会出现平局，会选择这次比赛所在的场地类型中初始排名靠前的选手获胜。你办的比赛也有一些黑幕，你就希望让你办的比赛中的获胜者能在他所更擅长的场地类型上比赛（即在他初试排名靠前的场地类型上比赛），如果有多个场地满足要求，那么选择输的那一方排名较靠前的。如果还有多个场地满足要求，选择编号小的（A $<$ B $<$ C）。

你想知道，每个场地上举行了多少场比赛，且每个人赢的场数。

inputFormat:
第一行一个整数 $n$ 代表选手个数。
第二行 $n$ 个整数代表选手们在 A 场地的初始排名，由强到弱依次给出。
第三行 $n$ 个整数代表选手们在 B 场地的初始排名，由强到弱依次给出。
第四行 $n$ 个整数代表选手们在 C 场地的初始排名，由强到弱依次给出。

outputFormat:
第一行三个整数分别代表在 A 场地，B 场地，C 场地举办了多少场比赛。
第二行 $n$ 个整数代表每个选手获胜了几场。

hint:
#### 样例 1 解释

对于选手1和2之间的比赛，应该在2号场地进行，因为胜者（选手1）在该场地排名最好（第一位）。对于选手1和3之间的比赛，获胜者在三个场地上的排名相同，但输家在2号场地的排名更高。对于选手2和3之间的比赛，1号场地和3号场地的排名相同，因此选择索引较小的1号场地。

#### 数据规模与约定

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

- Subtask 1（35 pts）：$1 \le n \le 300$。
- Subtask 2（15 pts）：$1 \le n \le 3000$。
- Subtask 3（60 pts）：$1 \le n \le 10^5$。

**满分 $110$ 分。**

#### 说明

翻译自 [Croatian Open Competition in Informatics 2020 ~ 2021 Round 1 E Tenis
](https://hsin.hr/coci/archive/2020_2021/contest1_tasks.pdf)。


title: [COCI2020] Paint

description:
你一定用过画图软件的一键填充功能吧？如果拓展到像素层面中，如果一个大连通块内所有像素的颜色相同，那么将一个像素染色，那么整个连通块内的所有像素都会被染色。

现在给定一个 $R\times S$ 的像素图，给定 $Q$ 个染色操作：

- 将 $(r_i,s_i)$ 染为颜色 $c_i$。

求染色过后的整个像素图。

inputFormat:
第一行两个整数 $R,S$ 代表像素图大小。
接下来 $R$ 行每行 $S$ 个整数，代表像素图的初始颜色。
第 $R+2$ 行一个整数 $Q$ 代表操作个数。
接下来 $Q$ 行每行三个整数 $r_i,s_i,c_i$ 代表一次染色操作。

outputFormat: $R$ 行每行 $S$ 个整数代表染色后的像素图。

hint:
#### 样例 1 解释

假设 $0$ 为白色，$1$ 为红色，$2$ 为蓝色，$3$ 为绿色，$4$ 为黄色，那么如下图所示：

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

#### 数据规模与约定

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

- Subtask 1（8 pts）：$1 \le R \times S \le 10^4$，$1 \le Q \le 10^4$。
- Subtask 2（9 pts）：$R=1$，$1 \le S \le 2 \times 10^5$，$1 \le Q \le 10^5$。
- Subtask 3（31 pts）：$1 \le R \times S \le 2 \times 10^5$，$1 \le Q \le 10^5$，颜色只有 $0$ 和 $1$。
- Subtask 4（52 pts）：$1 \le R \times S \le 2 \times 10^5$，$1 \le Q \le 10^5$。

对于 $100\%$ 的数据，$1 \le r_i \le R$，$1 \le s_i \le S$，$0 \le c_i \le 10^5$，颜色区间为 $[0,10^5]$。

#### 说明

翻译自 [Croatian Olympiad in Informatics 2020 A Paint](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf)。


title: 弹珠游戏（2021 CoE-I C）

description:
$\operatorname{Alice}$ 对弹珠游戏已经有些厌烦了，她经常在电脑上玩这个游戏。她之所以感到厌烦是因为在这个游戏上她已经是专家级别，她总是能够和电脑打成平手。$\operatorname{Bob}$ 为 $\operatorname{Alice}$ 创造了一款新的电脑游戏。以下是这款两人电脑游戏的规则：

（1）游戏在如下图所示的菱形棋盘上进行；

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

（2）两名玩家轮流放置弹珠，可以在横向、纵向、$45$ 度斜线、$135$ 度斜线方向未放置弹珠的位置**连续放置 $1$ 至 $3$ 颗弹珠**，玩家在可以放置弹珠的情况下，必须至少放置 $1$ 颗弹珠。以下是合法的单次放置操作的示例（黑色圆点表示放置了弹珠，白色圆点表示未放置弹珠，进行该次操作前棋盘为空）：

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

以下是非法的单次放置操作的示例（黑色圆点表示放置了弹珠，白色圆点表示未放置弹珠，进行该次操作前棋盘为空）：

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

非法原因的解释：（$a$）三颗弹珠不在同一条斜线（或者垂直线）上；（$b$）两颗弹珠之间相隔一个空位；（$c$）三颗弹珠不在同一条斜线上；（$d$）三颗弹珠不在同一条斜线（或者垂直线）上；（$e$）一次性放置了 $4$ 颗弹珠；（$f$）三颗弹珠不在同一条水平线（或者垂直线、或者斜线）上。

（3）如果某位玩家无法再继续放置弹珠，则该名玩家输掉游戏，另外一名玩家获胜。

$\operatorname{Alice}$ 总是第一个进行游戏，而且经常是和 $\operatorname{Bob}$ 玩这个游戏，$\operatorname{Bob}$ 在进行若干游戏操作后可能会离开，将游戏交由电脑代理，电脑总是按照最优策略放置弹珠。
给定 $\operatorname{Bob}$ 离开后的游戏状态，你的任务是确定 $\operatorname{Alice}$ 是否可能在对阵电脑时获得胜利。

inputFormat:
**输入包含多组测试数据**。

输入第一行包含一个整数 $T$，表示测试数据的组数。接着是一个空行。再接下来是 $T$ 组表示棋盘状态的数据，每组数据由七行字符构成，表示 $\operatorname{Bob}$ 离开后的游戏状态，`*` 表示该位置已经放置了弹珠，`.` 表示该位置未放置弹珠。相邻两组测试数据之间有一个空行。

outputFormat: 对于每组测试数据，如果 $\operatorname{Alice}$ 能够获胜，输出 `Possible.`，否则输出 `Impossible.`。

samples:
Possible.
Possible.
Possible.
Possible.
Impossible.
Possible.

hint:
#### 样例说明

第一组数据，$\operatorname{Alice}$ 可以选择在棋盘左下角的斜线方向所剩下的 $3$ 个空余位置一次性连续放置 $3$ 颗弹珠，使得后续电脑无法再放置弹珠，因此 $\operatorname{Alice}$ 能够获胜。

第二组数据，$\operatorname{Alice}$ 可以选择沿着第四行剩下的 $3$ 个空余位置一次性连续放置 $3$ 颗弹珠，使得后续电脑无法再放置弹珠，因此 $\operatorname{Alice}$ 能够获胜。

第三组数据，棋盘剩下倒数第二列两个连续的空余位置，$\operatorname{Alice}$ 可以一次放置 $2$ 颗弹珠，使得后续电脑无法放置弹珠，因此 $\operatorname{Alice}$ 会获胜。

第四组数据，类似于第二组测试数据，棋盘剩下第三行两个连续的空余位置，因此 $\operatorname{Alice}$ 会获胜。

第五组数据，棋盘只剩下两个不连续的空余位置，由于 $\operatorname{Alice}$ 一次只能选择一个空余位置放置 $1$ 颗弹珠，因此不管 $\operatorname{Alice}$ 如何操作，电脑总能一次性将剩下的棋盘使用弹珠填满，使得 $\operatorname{Alice}$ 无法再继续放置弹珠，因此 $\operatorname{Alice}$ 会输掉比赛。

第六组数据，$\operatorname{Alice}$ 可以选择在棋盘右上角斜线方向的中间两个空余位置放置 $2$ 颗弹珠，使得棋盘状态转化为样例输入的第五组数据，因此 $\operatorname{Alice}$ 会赢得比赛。

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

#### 数据范围

对于 $10\%$ 的数据，$0 \lt T \leq 10$。

对于 $60\%$ 的数据，$0 \lt T \leq 10^3$。

对于 $80\%$ 的数据，$0 \lt T \leq 10^5$。

对于 $100\%$ 的数据，$0 \lt T \leq 10^6$。

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

#### 提示

本题输入量较大，请使用合适的读入方式。


title: 自动兑换机（2021 CoE-I D）

description: Mca 市的地铁公司决定采取一项新措施——勿需购票，投币上车。有传闻说此举是为了减少乘客购票的排队时间。地铁运营商找到了本市计算机协会（Association for Computing Machinery，ACM）旗下的自动收款机（Automated Checkout Machine，ACM）公司，要求开发一款自动兑换机（Automatic exChange Machine，ACM）来满足乘客的需求。他们雇用你来担任首席程序员为此机器编写程序。自动兑换机内部存放有各种面值的硬币，当乘客将纸币放入机器时，机器会自动根据当前可用的硬币面值将乘客的纸币兑换成等值的硬币。当然，乘客不愿意口袋里面装着一大堆硬币去挤地铁，因此兑换成的硬币数量越少越好。如果现有的硬币面值无法完成兑换要求，应该输出一行信息，提示乘客需要寻求人工窗口的服务。

inputFormat:
**输入包含多组测试数据**。

第一行一个整数 $T$，表示数据组数。每组测试数据一行，第一个为整数 $c$，表示硬币面值的种类，接下来是 $c$ 个整数，每个整数 $d_i（1 \leq i \leq c）$ 表示一种硬币的面值，以美分为单位，最后是一个实数 $m$，表示乘客需要兑换的纸币的总面值，以美元为单位。

outputFormat: 对于每行输入均输出一行，如果不存在兑换方案，输出 `No solution.`。否则，按以下格式输出具有最少硬币数量的兑换方案：首先输出方案中硬币的总个数，然后一个空格，接着按照样例输出的格式打印兑换序列，即依照面值从小到大的顺序，将方案使用的各个面值及其对应的硬币个数予以输出。如果存在多种具有最少硬币数量的兑换方案，输出字典序（即按 **[ASCII](https://baike.baidu.com/item/ASCII)** 序）最小的兑换方案。


title: 雨水收集系统（2021 CoE-I E）

background: Rain 市的环保部门为部分建筑的顶层安装了雨水收集装置，使得能够将雨水进行循环利用。雨水收集系统通过每栋建筑的顶层地面来收集雨水，利用特殊的管道将雨水集中引流到一个蓄水池中以待后续使用。环保部门计划根据降水量来估计蓄水池的容量大小以便进行设计制造。

description: 为了简化问题的处理，将每栋建筑的顶层视为一个边与坐标轴平行的矩形，使用矩形的一条对角线顶点坐标来表示该矩形。每次降雨时，降雨云沿着特定的方向以一定的速度做匀速运动，降雨云所经过的区域均会有雨水降落。将降雨云抽象为一个凸多边形，给定初始时降雨云的位置以及移动方向和速率，确定在某段时间内雨水收集系统能够接受降雨的面积大小。

inputFormat:
**输入包含多组测试数据**。

输入的第一行为一个整数 $T$，表示测试数据的组数，接下来共 $T$ 组数据，相邻两组测试数据之间有一个空行。每组测试数据的第一行为一个整数 $n$，表示建筑的数量。接下来 $n$ 行，每行四个整数，表示第 $i$ 栋建筑顶层所对应矩形的对角线顶点坐标。接下来一行是一个整数 $m$，表示降雨云对应凸多边形的顶点数目，接下来是 $m$ 个表示该凸多边形的顶点坐标（**不保证有序，即顶点可能不是按照顺时针或逆时针顺序给出，但给定的坐标点唯一地确定了表示降雨云的凸多边形**）：（$x_1$，$y_1$），（$x_2$，$y_2$），...，（$x_m$，$y_m$）。再接下来是起点 $s$（$x_s$，$y_s$）和终点 $e$（$x_e$，$y_e$）的坐标值，表示降雨云沿着从起点 $s$ 到终点 $e$ 的直线方向做平移运动。后续是一个整数 $v$，表示降雨云沿着直线方向的移动速率为 $v$ 单位距离/分钟，最后一行表示降雨的起始时间 $hh_{start}$ 时 $mm_{start}$ 分和结束时间  $hh_{end}$ 时 $mm_{end}$ 分，以 $24$ 小时计时法表示。

outputFormat: 输出在指定时间内能够接受降雨的建筑顶层面积之和，精确到小数点后一位。如果你的输出和参考输出绝对误差在$10^{-1}$之内，均认为正确。

hint:
#### 样例说明

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

第一组测试数据，此组测试数据一共有 $2$ 栋建筑 $\operatorname{B_1}$ 和 $\operatorname{B_2}$，降雨云 $\operatorname{C}$ 为一个正方形（正方形的左下角位于坐标点（$-10$，$8$），边长为 $5$），降雨云沿着从起点（$15$，$0$）到终点（$25$，$0$）的方向匀速移动，移动速率为 $1$ 单位距离/分钟，降雨起始时间为 $15$ 时 $30$ 分，结束时间为 $16$ 时 $05$ 分，降雨时间为 $35$ 分钟，降雨云沿着箭头所示方向移动了 $35$ 单位距离。如上图所示，能够接受降雨的面积为阴影区域的面积，易知面积为 $50.0$。

![](https://cdn.luogu.com.cn/upload/image_hosting/two4uh3q.png)
第二组测试数据，降雨云的移动方向不同，从起点（$-5$，$8$）到终点（$19$，$1$）的方向匀速移动，降雨时间为 $60$ 分钟，沿着箭头所示方向的移动距离为 $60$ 单位距离，其他条件相同，能够接受降雨的面积为上图中的阴影区域，其面积为 $60.5$。注意，第二组测试数据的示意图中，为了示意的方便，所绘制的降雨云“最终位置”并不是其实际的最终位置。

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

#### 数据范围与约定

对于 $100\%$ 的数据，$1 \leq T \leq 10^3$，$1 \leq n \leq 50$，$3 \leq m \leq 100$，$0 \lt v \leq 100$。所有坐标值均为整数，位于闭区间 $[-10^5,10^5]$。

输入数据保证表示建筑顶层的矩形不会发生重叠。降雨的结束时间一定晚于起始时间。表示降雨云移动方向的起点 $s$ 和终点 $e$ 不同。


title: [COCI2020] Pastiri

description:
给定一棵 $N$ 点的树，点编号为 $1$ 到 $N$，现在在 $K$ 个点上有羊，你的任务是在树上分配一些牧羊人。

这些牧羊人很懒，只会看管离他最近的羊。当然如果有多个离他最近的羊，那么他会都看管。

当然，牧羊人可以和羊在同一个点上，但这样牧羊人只会看管这一个点上的那个羊。

求一种牧羊人的分配方案使得牧羊人总数最小。

inputFormat:
第一行两个整数 $N,K$ 代表树的点数和有羊的点数。
接下来 $N-1$ 行每行两个整数 $a_i,b_i$ 代表树的一条边。
第 $N+1$ 行 $K$ 个整数 $o_i$，代表有羊的点的编号。

outputFormat:
第一行一个整数 $X$ 代表牧羊人总数的最小值。
第二行 $X$ 个整数代表每个牧羊人分配到哪个点上。
如果有多种解，输出一种即可。

hint:
#### 样例 3 解释

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

#### 数据规模与约定

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

- Subtask 1（8 pts）：$1 \le N \le 5 \times 10^5$，任意一个点 $i$ 都与 $i+1$ 相连（$1 \le i \le N-1$）。
- Subtask 2（18 pts）：$1 \le K \le 15$，$1 \le N \le 5 \times 10^5$。
- Subtask 3（23 pts）：$1 \le N \le 2000$。
- Subtask 4（51 pts）：$1 \le N \le 5 \times 10^5$。

对于 $100\%$ 的数据，$1 \le K \le N$，$1 \le a_i,b_i \le N$，$1 \le  o_i \le N$。

**本题使用 Special Judge，checker 提供者 @[Lynkcat](https://www.luogu.com.cn/user/120911)，感谢他的贡献。**

#### 说明

翻译自 [Croatian Olympiad in Informatics 2020 B Pastiri](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf)。


title: [CERC2016] Easy Equation

description:
Given an integer $k$ greater than $1$, it is possible to prove that there are infinitely many triples of positive integers $(a, b, c)$ that satisfy the following equation:

$$a^2+b^2+c^2=k(ab+bc+ca)+1$$

Given positive integers $n$ and $k$, find $n$ arbitrary triples $(a_1, b_1, c_1), (a_2, b_2, c_2), \cdots , (a_n, b_n, c_n)$ that all
satisfy the equation. Furthermore, all $3n$ integers $(a_1, b_1, c_1), (a_2, b_2, c_2), \cdots , (a_n, b_n, c_n)$ should be different positive integers with at most $100$ decimal digits each.

inputFormat:
The first line contains two integers $k$ and $n\;(2 \leq k \leq 1000, 1 \leq n \leq 1000)$ — the constant k in the
equation and the target number of triples.

outputFormat: Output $n$ lines. The $i$-th line should contain three space separated integers $a_i$, $b_i$ and $c_i$ with at most $100$ digits each — the $i$-th of the solutions you found.

translation:
### 题目描述：
假设 $k$ 大于 $1$，
可以证明有无穷多个正整数三元组 $(a, b, c)$ 满足以下方程:

   $a^2 + b^2 + c^2 = k(ab + bc + ca) + 1$

给定正整数 $n$ 和 $k$，找出 $n$ 个三元组 $(a_1, b_1, c_1), (a_2, b_2, c_2), ⋯ ,(a_n, b_n, c_n)$ 使它们都满足方程。另外，这 $3n$ 个正整数 $(a_1, b_1, c_1), (a_2, b_2, c_2), ⋯ ,(a_n, b_n, c_n)$ 应该是不同的，每个数最多有 $100$ 位。

### 输入格式：
第一行包含两个整数：
方程中的常数 $k$ 和
所求三元组的数量 $n$ $(2 ≤ k ≤ 1000, 1 ≤ n ≤ 1000)$;

### 输出格式：
输出有 $n$ 行。第 $i$ 行应该包含三个空格分隔的正整数 $ai$, $bi$ 和 $ci$，
为你找到的第 $i$ 个解。每个数最多 $100$ 位。


title: [CERC2016] Lost Logic

description:
Gustav is reading about *2-satisfiability*, a well known problem of assigning truth values to boolean
variables in order to satisfy a list of *constraints* — simple logical formulas involving two variables each.

We are using $n$ variables $x_1, x_2, \cdots , x_n$ that can take on values $0$ (false) and $1$ (true). A constraint is a
formula of the form $a\to b$ where both $a$ and $b$ are possibly negated variables. As usual, $\to$ denotes
logical implication: $a \to b$ is $0$ only when $a$ is $1$ and $b$ is $0$. The negation of variable $a$ is denoted by $!a$.

Given an assignment of values to variables, we say that the constraint is *satisfied* if it evaluates to $1$.
Gustav has constructed a list of constraints and correctly concluded that there are *exactly three* different
assignments of values to variables that satisfy all the constraints. Gustav has wrote down all three
assignments but has, unfortunately, lost the list of constraints.
Given three assignments of $n$ values to variables, find any list consisting of at most $500$ constrains such
that the three given assignments are the *only* assignments that satisfy all the constraints.

inputFormat:
The first line contains an integer $n (2 \leq n \leq 50)$ — the number of variables. Three lines follow, each
describing one assignment. The $k$-th line contains $n$ space-separated integers $v_1^k,v_2^k,\cdots,v_n^k$, where each $v_i^k$ is either $0$ or $1$ and denotes the value of the variable $x_i$ in the $k$-th assignment. All three assignments will be different.

outputFormat:
If there is no solution output a single line containing the integer $−1$.
Otherwise, the first line should contain an integer $m$ where $1 \leq m \leq 500$ — the number of constraints
in your solution. The $k$-th of the following $m$ lines should contain the $k$-th constraint. Each constraint
should be a string constructed according to the following rules:

- A *variable* is a string of the form “$\texttt{x}i$” where $i$ is an integer between $1$ and $n$ inclusive written
  without leading zeros.
- A *literal* is a string consisting of a variable possibly preceded by the “$\texttt{!}$” character.
- A *constraint* is a string of the form “$a\texttt{ -> }b$” where both $a$ and $b$ are literals. The implication sign
  consists of the “minus” character and the “greater-than” character and there is a single space
  character both before and after the implication sign.

translation:
给定 $3$ 组随机布尔变量 $v_{i,1},...,v_{i,n}(1\leq i\leq 3)$，每组均为 $n$ 个。你需要构造关于布尔变量 $x_1,...,x_n$ 的若干组**条件**，使得满足全部条件的布尔变量赋值**有且仅有** $(v_{i,1},...,v_{i,n})(1\leq i\leq 3)$ 这 $3$ 组。

由于机器限制，你所构造每组条件的形式均应为：$A\rightarrow B$。这组条件的限制了：当 $A$ 为 $1$ 时 $B$ 一定为 $1$。其中，$A,B$ 可能形如：

- $x_i$：表示第 $i$ 个变量的值。
- $!x_i$：表示第 $i$ 个变量取反后的值。

例如，如果你构造了 $x_1\rightarrow x_2$，那么表示你规定 $x_1=1$ 时必有 $x_2=1$；如果你构造了 $!x_1\rightarrow x_2$，那么你规定了 $x_1=0$ 时必有 $x_2=1$。你需要找到一种使用不超过 $500$ 组条件来满足题意的方法，或者判定这样的条件组合不可能存在。如果有多组解，输出任意一组均可。

数据保证 $2\leq n\leq 50,v_{i,j}\in\{0,1\}(1\leq i\leq 3,1\leq j\leq n)$。


title: [COCI2020] Semafor

background:
你可能非常熟悉七段 LED 显示器，它广泛地应用于各种数字设备内，比如计算器，手表，红绿灯等等。由于它的简单与美观，该设计已被全球接受，不过年轻的 Matej 反对这个设计，并设计出了"五段 LED 显示器"，声称可以更有效地获得与七段 LED 显示器相同的功能。

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

description:
Matej 的第一步就是将这项设计应用到足球业界中，他目前正在克罗地亚足球协会中做演讲，决定将他的设计用在换人板上。

换人板由 $m$ 个五段 LED 显示器组成，换人板将显示一个数，这个数由换人板上的 $m$ 个数字组成，代表被换下的球员的号码。Matej 决定开始演示他的换人板操作。刚开始他的换人板上显示了数字 $x$。Matej 将做出下面两种操作的一种：

* 将一段关闭的 LED 灯打开。
* 将一段打开的 LED 灯关闭。

Matej 总共会执行 $n$ 次操作，他需要保证每 $k$ 次操作他的换人板显示的是一个数（每个五段 LED 显示器上都显示了一个 $0$ ~ $ 9$ 内的数字）。

执行完 $n$ 次操作后你会得到一个最终状态，对于每个最终状态是一个数的情况，Matej 想知道分别有多少种满足上述限制的不同的操作序列能达到这些最终状态。我们说两个操作序列不同，当且仅当这两个操作序列中第 $i$ 次操作时操作了不同的五段 LED 显示器并且在某此操作后两种操作序列产生的状态不同。

inputFormat: 第一行四个整数 $m,n,k,x$，意义见题目描述。

outputFormat: 共 $10^m$ 行。第 $i$ 行输出一个整数表示最终状态显示的数为 $i-1$ 时所有的操作序列的个数。答案对 $10^9+7$ 取模。

hint:
#### 样例 1 解释
刚开始的时候换人板上显示 $5$。因为 $k=1$。所以每次操作后换人板上都必须显示的是一个数。Matej 将会进行 $n=2$ 次操作，因此最终他可以显示出 $3$ 或 $5$ 两个数。为了显示 $3$，我们只能先将 $5$变成 $9$ 然后再将 $9$ 变成 $3$。为了显示 $5$，我们即可以通过 $5-9-5$ 的方法实现也可以通过 $5-8-5$ 的方法实现，因此有两种操作序列。

#### 数据规模与约定

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

* Subtask 1（6 pts）：$m=1$，$1 \leq n \leq 12$。
* Subtask 2（15 pts）：$m=1$，$1 \leq n \leq 10^{15}$。
* Subtask 3（12 pts）：$m=2$，$1 \leq n \leq 1500$，$k=n$。
* Subtask 4（12 pts）：$m=2$，$1 \leq n \leq 10^{15}$，$1\leq k \leq 15$。
* Subtask 5（15 pts）：$m=2$，$1 \leq n \leq 10^{15}$，$1\leq k \leq 1500$。
* Subtask 6（40 pts）：$m=2$，$1 \leq n \leq 10^{15}$。

对于 $100\%$ 的数据，$1 \leq k \leq n \leq 10^{15} $，$0 \leq x \leq 10^m$。

### 说明

翻译自 [Croatian Olympiad in Informatics 2020 C Task Semafor](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf)。


title: [COCI2020] Zagrade

background:
**本题为交互题**。

众所周知，中央情报局的工作是收集，处理和分析国家安全信息。现在他们拥有了大量的计算机密码，并且正在开发一些相当复杂的工具，来破坏受密码保护的系统。

现在，您的任务是破坏中央情报局服务器的安全性。自然，他们很清楚人们在输入密码的时候通常会输入什么东西，因此尝试输入 `123456` , `1q2w3e4r` 或 `Welcome` 肯定是没有用的。幸运的是，我们发现了某些可能对您有用的信息。

description:
现在已知中央情报局服务器的主密码由 $n$ 个字符（$n$ 为偶数）构成，其中一半是左括号，一半是右括号。一些记性不好的服务器管理员会忘记这个主密码，所以服务器提供了找回密码的工具。管理员最多可以使用 $Q$ 次这个工具，每次使用时都会询问这个密码 $l$ 到 $r$ 位的括号串是否合法。

对于一个括号串合法的定义：

* `()` 是一个合法的括号串。
* 若 `A` 是一个合法的括号串，那么 `(A)` 也是一个合法的括号串。
* 若 `A` 与 `B` 都是合法的括号串，那么 `AB` 也是合法的括号串。

现在你需要写出一个程序来模拟管理员找回密码的过程。

在进行交互之前，您的程序应该从输入中读取偶数 $n$ 和整数 $Q$ ，这两个数字的含义见题目描述。

之后，您的程序可以通过向**标准输出**输出来发送查询请求。每个查询必须在单独的行中打印，并采用 `? a b`，其中 $1 \leq a \leq b \leq n$。每个查询之后，您的程序应**清空缓冲区**并从**标准输入**中读取答案。

当你推理出密码时，请在**标准输出**中输出： `! x1 x2 x3 …… xn` 的形式，之后你的程序应**清空缓冲区**并正常终止程序运行。

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

接下来若干行，每行对于每个查询给出答案。

outputFormat:
若干行，表示查询。

最后一行表示最后得出的答案。

hint:
### 样例解释
`? 1 6` 对应的是整个串，当然是合法的。
`? 1 2` 对应的是 `((` 不合法。
`? 2 4` 对应的是 `(()` 不合法。
`? 2 5` 对应的是 `(())` 合法。
`? 3 4` 对应的是 `()` 合法。

### 数据规模与约定

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

* Subtask 1（14 pts）：$1\leq n\leq 1000$，$Q=\frac{n^2}{4}$，保证整个括号序列合法。
* Subtask 2（7 pts）：$1\leq n\leq 1000$，$Q=\frac{n^2}{4}$。
* Subtask 3（57 pts）：$1\leq n\leq 100000$，$Q=n-1$，保证整个括号序列合法。
* Subtask 4（12 pts）：$1\leq n\leq 100000$，$Q=n-1$。

对于 $100\%$ 的数据，$1\leq n\leq 100000$，$n-1\leq Q$。

### 说明

翻译自 [Croatian Olympiad in Informatics 2020 D Zagrade](https://hsin.hr/coci/archive/2019_2020/olympiad_tasks.pdf)。


title: 「MCOI-06」Lost Desire

background:
頰滴る　紅い涙

不安定な視界の中

差し出した手を取れたら

あぁ…そんな世界を夢みた

-------

哭いて…

激しく  燃やした 黒い感情

届かぬ この手に

Cry 闇の中で

最果てから 光へ手を翳して

揺らいだ想いさえも 闇の奥底へ堕ちてく

[网易云本曲试听链接](https://music.163.com/song?id=1809745288&userid=1399272307)

description:
设正整数 $n, m$ 互质，$k$ 为整数，定义函数 $F(n, m, k)$ 为小于 $\displaystyle m+n$ 的正整数集合 $\{1, 2, \cdots, m + n - 1\}$ 中，所有满足 $\displaystyle\sum_{x \in S} x \equiv k \pmod n$ 的 $m$ 元子集 $S$ 的个数。

现给定正整数 $N, M, K$，求所有 $F(i,j,x)$ 之积，使得 $1\le i\le N$，$1\le j\le M$，$1\le x\le K$，并且 $i$ 与 $j$ 互质。

由于结果很大，所以你只需要求出结果对特定素数 $p$ 取模的值。

**同时请注意实现程序时常数因子带来的影响。**

inputFormat:
**本题多测。** 每个测试点共有 $T$ 组数据。

第一行两个正整数 $T,p$ 。

接下来 $T$ 行，每行三个正整数 $N, M, K$，由空格分开。

outputFormat: 对于每组数据：一行，一个整数，表示所求的值（对 $p$ 取模）。

hint:
本题采用捆绑测试，分 $5$ 个 Subtask 。

+ 对于 Subtask 1 ~~(Tutorial)~~：
  + $T=1$
  + $1\leq N,M,K\leq 6$
  + $p=10^9+7$。
+ 对于 Subtask 2 ~~(PST 4.0)~~：
  + $T=1$
  + $1\leq N,M,K\leq200$
  + $p=10^9+7$。
+ 对于 Subtask 3 ~~(PRS 7.5)~~：
  + $T=100$
  + $1\leq N,M,K\leq 1000$
  + $p=10^9+7$。
+ 对于 Subtask 4 ~~(FTR 9.8)~~：
  + $T=10^3$
  + $1 \leq N,M,K\le 10^5$
  + $10^9\le p\le2\times10^9$。
+ 对于 Subtask 5 ~~(BYD 11.0)~~：
  + $T=9999$
  + $1 \leq N,M,K\le 5\times10^5$
  + $10^9\le p\le2\times10^9$。

Subtask $1\sim5$ 的分值分别为 $5,7,11,17,60$ 。

特别的，假设您在一个测试点中前 $x$ 个询问正确，则您得该测试点的分值的 $\left\lfloor100\times\sqrt\dfrac{x}{T}\right\rfloor\%$ 分。您在任何一个 Subtask 的得分则为对应 Subtask 中所有测试点得分的最小值。

特别的，**TLE 一律不得分。**（无需补满未在时间范围内解决的测试点的答案，会导致奇怪的错误。）

**再次提醒注意实现程序时常数因子带来的影响。**

---

Idea: Powerless Std&Data: w33z （Data was corrected on 2021.10.05）

Sub4 added by Prean, Sub 5 by w33z.

This problem was added on 2021.10.01. Thanks for their help.

2021.10.01 - 2021.12.07 : 68 days 1st kill (Leasier).

2021.10.01 - 2022.01.21 : 113 days 2nd kill (wkywkywky).

2021.10.01 - 2022.02.26 : 149 days 3rd kill (NaNH2).


title: 章节划分

background:
  作文周，顾名思义，一天写一篇，高产似那啥。

  小灰毛的作文被老师无数次公开处刑，昨天自己的奶奶变成了别人作文里的外婆，今天憋出来的小面变成了明天别人的酸辣粉。素材一用，就报废了啊 qwq。

  于是，不甘心的小灰毛决定加倍高产。

description:
天依决定了 $n$ 个素材，它们将**依次**在作文中被叙写。其中，第 $i$ 个素材的立意特征值是 $a_i$。

但天依发现她构思的大作实在是太长啦，所以她想把它们划分为**恰好 $k$ 个**章节，每个章节包含一段**连续且非空的**素材。假设第 $i$ 个章节包含素材 $[l_i,r_i]$，天依将选取立意特征值最大的素材来升华，得到该章节的立意值 $b_i$，满足 $b_i=\max\limits_{i\in[l_i,r_i]}\{a_i\}$。

最后，整篇作文的凝练度为每个章节立意值的**最大公约数**，即 $\gcd\limits_{i\in[1,k]}\{b_i\}$。

天依当然希望**最大化**作文的凝练度，那么凝练度的最大值是多少呢？

---

#### 简化题意

有一个长度为 $n$ 的序列 $a$。要求将这个序列**恰好**分成**连续且非空**的 $k$ 段，并定义第 $i$ 段的立意值为该段的所有元素的最大值，记为 $b_i$。要求最大化 $\gcd\limits_{i\in[1,k]}\{b_i\}$ 并输出这个最大值。

inputFormat:
第一行包含两个整数 $n,k$，表示素材的长度和需要划分的章节数。

接下来第二行包含 $n$ 个整数，表示每个素材的立意特征值。

outputFormat: 一行一个整数，表示你的答案。


title: [RC-04] 01 背包

description:
有一个容积为 $+\infty $ 的背包，你要往里面放物品。

你有 $n$ 个物品，第 $i$ 个体积为 $a_i$。

你有一个幸运数字 $p$，若放入的物品体积和为 $k$，你会得到 $p^k$ 的收益。**特别地，$0^0=1$。**

求所有 $2^n$ 种放入物品的方案的收益和。答案很大，因此请输出它对 $998244353$ 取模的值。

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

接下来一行 $n$ 个正整数 $a_1\sim a_n$，描述这 $n$ 个物品的体积。

outputFormat: 输出一个整数，为所有 $2^n$ 种方案的收益和对 $998244353$ 取模的值。


title: 「dWoi R1」Sixth Monokuma's Son

background:
题目首先定义矩阵环为，给定一个矩阵 $A$，初始全为白色，在其中选定一个子矩阵 $A_1$ 标黑，再在 $A_1$ 内选定一个子矩阵 $A_2$ 标白，就会形成一个矩阵环。注意，矩阵环至少上下左右都有被选定的部分，且整个矩阵环不是一个长方形的矩阵。

假设 `+` 为黑，`-` 为白，下面这个就是矩阵环：

```
---+++++--
---++--+--
---+++++--
---+++++--
----------
```

下面就不是矩阵环：

```
------- ------
---+++- --+++-
---+-+- --+++-
------- --+++-
```

因此，矩阵环会出现上，下，左，右四条边，每个方向有多少个涂黑的部分，就是那个方向的厚度。比如对于第一张符合要求的图，上方，右方的厚度为 $1$，左方，下方的厚度为 $2$。

**注意，一个完整的矩阵不是一个矩阵环。**

---

接下来是正经的题目背景：

最原得到了“狱原发现一些小昆虫”这个线索后，立刻采取了行动。首先，他利用入间的 ~~遗物~~，那个类似喷火器的东西，吸进了一些空气，然后，他打算利用机望的机械眼进行查看。

description:
机望的机械眼能扫到一片 $n \times m$ 的区域，第 $i$ 行第 $j$ 列发现了 $a_{i,j}$ 的不对劲值。

因为机望被外部力量折磨的厉害，所以机望只能锁定一个矩阵环进行查看。机望想求助于你，他想让你锁定一个矩阵环，使得这个矩阵环中的所有位置的不对劲值的和最大，**上方，下方的厚度为 $1$ 且上方的那一行在整个区域的第一行，下方的那一行在整个区域的最后一行**。至于左右的厚度，机望不限制更多要求。

inputFormat:
第一行两个整数 $n,m$ 代表整片区域的大小。
接下来 $n$ 行每行 $m$ 个整数 $a_{i,j}$ 代表每一个位置的不对劲值。

outputFormat:
一行一个整数代表答案。
如果不能选出一个符合要求的矩阵环，输出 $-1$。

hint:
#### 样例说明

关于样例 1 的解释：

可以选择如下形式的矩阵环（但其实两个解是一样的，因为第一列所有数之和为 $0$）：

```
++++  -+++
++-+  -+-+
++-+  -+-+
++++  -+++
```

其中 + 为选定的，- 为未选定的。

关于样例 3，提供者 @[cmll02](https://www.luogu.com.cn/user/171487)，感谢他的贡献。

#### 数据规模与约定

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

- Subtask 1（5 pts）：$n \le 2$ 或 $m \le 2$。
- Subtask 2（5 pts）：$a_{i,j}>0$。
- Subtask 3（40 pts）：$m \le 1000$。
- Subtask 4（50 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le n \le 10$，$1 \le m \le 10^5$，$|a_{i,j}| \le 100$。


title: [CSP-J2020] 优秀的拆分

description:
一般来说，一个正整数可以拆分成若干个正整数的和。

例如，$1=1$，$10=1+2+3+4$ 等。对于正整数 $n$ 的一种特定拆分，我们称它为“优秀的”，当且仅当在这种拆分下，$n$ 被分解为了若干个**不同**的 $2$ 的**正整数**次幂。注意，一个数 $x$ 能被表示成 $2$ 的正整数次幂，当且仅当 $x$ 能通过正整数个 $2$ 相乘在一起得到。

例如，$10=8+2=2^3+2^1$ 是一个优秀的拆分。但是，$7=4+2+1=2^2+2^1+2^0$ 就不是一个优秀的拆分，因为 $1$ 不是 $2$ 的正整数次幂。

现在，给定正整数 $n$，你需要判断这个数的所有拆分中，是否存在优秀的拆分。若存在，请你给出具体的拆分方案。

inputFormat: 输入只有一行，一个整数 $n$，代表需要判断的数。

outputFormat:
如果这个数的所有拆分中，存在优秀的拆分。那么，你需要从大到小输出这个拆分中的每一个数，相邻两个数之间用一个空格隔开。可以证明，在规定了拆分数字的顺序后，该拆分方案是唯一的。

若不存在优秀的拆分，输出 `-1`。

hint:
### 样例 1 解释

$6=4+2=2^2+2^1$ 是一个优秀的拆分。注意，$6=2+2+2$ 不是一个优秀的拆分，因为拆分成的 $3$ 个数不满足每个数互不相同。

---

### 数据规模与约定

- 对于 $20\%$ 的数据，$n \le 10$。
- 对于另外 $20\%$ 的数据，保证 $n$ 为奇数。
- 对于另外 $20\%$ 的数据，保证 $n$ 为 $2$ 的正整数次幂。
- 对于 $80\%$ 的数据，$n \le 1024$。
- 对于 $100\%$ 的数据，$1 \le n \le {10}^7$。


title: [CSP-J2020] 直播获奖

description:
NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 $w\%$，即当前排名前 $w\%$ 的选手的最低成绩就是即时的分数线。

更具体地，若当前已评出了 $p$ 个选手的成绩，则当前计划获奖人数为 $\max(1, \lfloor p \times w \%\rfloor)$，其中 $w$ 是获奖百分比，$\lfloor x \rfloor$ 表示对 $x$ 向下取整，$\max(x,y)$ 表示 $x$ 和 $y$ 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。

作为评测组的技术人员，请你帮 CCF 写一个直播程序。

inputFormat:
第一行有两个整数 $n, w$。分别代表选手总数与获奖率。
第二行有 $n$ 个整数，依次代表逐一评出的选手成绩。

outputFormat: 只有一行，包含 $n$ 个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。

hint:
### 样例 1 解释

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

---
### 数据规模与约定

各测试点的 $n$ 如下表：

| 测试点编号 | $n=$ |
| :--: | :--: |
| $1 \sim 3$ | $10$ |
| $4 \sim 6$ | $500$ |
| $7 \sim 10$ | $2000$ |
| $11 \sim 17$ | $10^4$ |
| $18 \sim 20$ | $10^5$ |

对于所有测试点，每个选手的成绩均为不超过 $600$ 的非负整数，获奖百分比 $w$ 是一个正整数且 $1 \le w \le 99$。

---
### 提示

在计算计划获奖人数时，如用浮点类型的变量（如 C/C++ 中的 `float` 、 `double`，Pascal 中的 `real` 、 `double` 、 `extended` 等）存储获奖比例 $w\%$，则计算 $5 \times 60\%$ 时的结果可能为 $3.000001$，也可能为 $2.999999$，向下取整后的结果不确定。因此，建议仅使用整型变量，以计算出准确值。


title: [CSP-J2020] 表达式

description:
小 C 热衷于学习数理逻辑。有一天，他发现了一种特别的逻辑表达式。在这种逻辑表达式中，所有操作数都是变量，且它们的取值只能为 $0$ 或 $1$，运算从左往右进行。如果表达式中有括号，则先计算括号内的子表达式的值。特别的，这种表达式有且仅有以下几种运算：
1. 与运算：`a & b`。当且仅当 $a$ 和 $b$ 的值都为 $1$ 时，该表达式的值为 $1$。其余情况该表达式的值为 $0$。
2. 或运算：`a | b`。当且仅当 $a$ 和 $b$ 的值都为 $0$ 时，该表达式的值为 $0$。其余情况该表达式的值为 $1$。
3. 取反运算：`!a`。当且仅当 $a$ 的值为 $0$ 时，该表达式的值为 $1$。其余情况该表达式的值为 $0$。

小 C 想知道，给定一个逻辑表达式和其中每一个操作数的初始取值后，再取反某一个操作数的值时，原表达式的值为多少。

为了化简对表达式的处理，我们有如下约定：

表达式将采用**后缀表达式**的方式输入。

后缀表达式的定义如下：
1. 如果 $E$ 是一个操作数，则 $E$ 的后缀表达式是它本身。
2. 如果 $E$ 是 $E_1~\texttt{op}~E_2$ 形式的表达式，其中 $\texttt{op}$ 是任何二元操作符，且优先级不高于 $E_1$ 、$E_2$ 中括号外的操作符，则 $E$ 的后缀式为 $E_1' E_2' \texttt{op}$，其中 $E_1'$ 、$E_2'$ 分别为 $E_1$、$E_2$ 的后缀式。
3. 如果 $E$ 是 $E_1$ 形式的表达式，则 $E_1$ 的后缀式就是 $E$ 的后缀式。

同时为了方便，输入中：

1. 与运算符（&）、或运算符（|）、取反运算符（！）的左右**均有一个空格**，但**表达式末尾没有空格**。
2. 操作数由小写字母 $x$ 与一个正整数拼接而成，正整数表示这个变量的下标。例如：`x10`，表示下标为 $10$ 的变量 $x_{10}$。数据保证**每个变量在表达式中出现恰好一次**。

inputFormat:
第一行包含一个字符串 $s$，表示上文描述的表达式。
第二行包含一个正整数 $n$，表示表达式中变量的数量。表达式中变量的下标为 $1,2, \cdots , n$。
第三行包含 $n$ 个整数，第 $i$ 个整数表示变量 $x_i$ 的初值。
第四行包含一个正整数 $q$，表示询问的个数。
接下来 $q$ 行，每行一个正整数，表示需要取反的变量的下标。注意，每一个询问的修改都是**临时的**，即之前询问中的修改不会对后续的询问造成影响。
数据保证输入的表达式合法。变量的初值为 $0$ 或 $1$。

outputFormat: 输出一共有 $q$ 行，每行一个 $0$ 或 $1$，表示该询问下表达式的值。

hint:
### 样例 1 解释

该后缀表达式的中缀表达式形式为 $(x_1 \operatorname{and} x_2) \operatorname{or} x_3$。

- 对于第一次询问，将 $x_1$ 的值取反。此时，三个操作数对应的赋值依次为 $0$，$0$，$1$。原表达式的值为 $(0\&0)|1=1$。
- 对于第二次询问，将 $x_2$ 的值取反。此时，三个操作数对应的赋值依次为 $1$，$1$，$1$。原表达式的值为 $(1\&1)|1=1$。
- 对于第三次询问，将 $x_3$ 的值取反。此时，三个操作数对应的赋值依次为 $1$，$0$，$0$。原表达式的值为 $(1\&0)|0=0$。

### 样例 2 解释

该表达式的中缀表达式形式为 $(\operatorname{not}x_1)\operatorname{and}(\operatorname{not}((x_2\operatorname{or}x_4)\operatorname{and}(x_3\operatorname{and}(\operatorname{not}x_5))))$。

### 数据规模与约定

- 对于 $20\%$ 的数据，表达式中有且仅有与运算（&）或者或运算（|）。
- 对于另外 $30\%$ 的数据，$|s| \le 1000$，$q \le 1000$，$n \le 1000$。
- 对于另外 $20\%$ 的数据，变量的初值全为 $0$ 或全为 $1$。
- 对于 $100\%$ 的数据，$1 \le |s| \le 1 \times 10^6$，$1 \le q \le 1 \times 10^5$，$2 \le n \le 1 \times 10^5$。

其中，$|s|$ 表示字符串 $s$ 的长度。


title: [CSP-J2020] 方格取数

description: 设有 $n \times m$ 的方格图，每个方格中都有一个整数。现有一只小熊，想从图的左上角走到右下角，每一步只能向上、向下或向右走一格，并且不能重复经过已经走过的方格，也不能走出边界。小熊会取走所有经过的方格中的整数，求它能取到的整数之和的最大值。

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

接下来 $n$ 行每行 $m$ 个整数，依次代表每个方格中的整数。

outputFormat: 一个整数，表示小熊能取到的整数之和的最大值。

hint:
### 样例 1 解释

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

### 样例 2 解释

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

### 数据规模与约定
- 对于 $20\%$ 的数据，$n, m \le 5$。
- 对于 $40\%$ 的数据，$n, m \le 50$。
- 对于 $70\%$ 的数据，$n, m \le 300$。
- 对于 $100\%$ 的数据，$1 \le n,m \le 10^3$。方格中整数的绝对值不超过 $10^4$。

------------
2024/2/4 添加一组 hack 数据。


title: [CSP-S2020] 儒略日

description:
为了简便计算，天文学家们使用儒略日（Julian day）来表达时间。所谓儒略日，其定义为从**公元前 4713 年 1 月 1 日正午 12 点到此后某一时刻间所经过的天数**，不满一天者用小数表达。若利用这一天文学历法，则每一个时刻都将被均匀的映射到数轴上，从而得以很方便的计算它们的差值。

现在，给定一个不含小数部分的儒略日，请你帮忙计算出该儒略日（一定是某一天的中午 12 点）所对应的公历日期。

我们现行的公历为格里高利历（Gregorian calendar），它是在公元 1582 年由教皇格里高利十三世在原有的儒略历（Julian calendar）的基础上修改得到的（注：儒略历与儒略日并无直接关系）。具体而言，现行的公历日期按照以下规则计算：

1. 公元 1582 年 10 月 15 日（含）以后：适用格里高利历，每年一月 $31$ 天、 二月 $28$ 天或 $29$ 天、三月 $31$ 天、四月 $30$ 天、五月 $31$ 天、六月 $30$ 天、七月 $31$ 天、八月 $31$ 天、九月 $30$ 天、十月 $31$ 天、十一月 $30$ 天、十二月 $31$ 天。其中，闰年的二月为 $29$ 天，平年为 $28$ 天。当年份是 $400$ 的倍数，或日期年份是 $4$ 的倍数但不是 $100$ 的倍数时，该年为闰年。
2. 公元 1582 年 10 月 5 日（含）至 10 月 14 日（含）：不存在，这些日期被删除，该年 10 月 4 日之后为 10 月 15 日。
3. 公元 1582 年 10 月 4 日（含）以前：适用儒略历，每月天数与格里高利历相同，但只要年份是 $4$ 的倍数就是闰年。
4. 尽管儒略历于公元前 45 年才开始实行，且初期经过若干次调整，但今天人类习惯于按照儒略历最终的规则反推一切 1582 年 10 月 4 日之前的时间。注意，**公元零年并不存在**，即公元前 1 年的下一年是公元 1 年。因此公元前 1 年、前 5 年、前 9 年、前 13 年……以此类推的年份应视为闰年。

inputFormat:
第一行一个整数 $Q$，表示询问的组数。
接下来 $Q$ 行，每行一个非负整数 $r_i$，表示一个儒略日。

outputFormat:
对于每一个儒略日 $r_i$，输出一行表示日期的字符串 $s_i$。共计 $Q$ 行。 $s_i$ 的格式如下：

1. 若年份为公元后，输出格式为 `Day Month Year`。其中日（Day）、月（Month）、年（Year）均不含前导零，中间用一个空格隔开。例如：公元
2020 年 11 月 7 日正午 12 点，输出为 `7 11 2020`。
2. 若年份为公元前，输出格式为 `Day Month Year BC`。其中年（Year）输出该年份的数值，其余与公元后相同。例如：公元前 841 年 2 月 1 日正午 12
点，输出为 `1 2 841 BC`。

samples:
见附件中的 julian/julian3.in
见附件中的 julian/julian3.ans


title: [CSP-S2020] 函数调用

description:
函数是各种编程语言中一项重要的概念，借助函数，我们总可以将复杂的任务分解成一个个相对简单的子任务，直到细化为十分简单的基础操作，从而使代码的组织更加严密、更加有条理。然而，过多的函数调用也会导致额外的开销，影响程序的运行效率。

某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类：

1. 将数据中的指定元素加上一个值；
2. 将数据中的每一个元素乘以一个相同值；
3. **依次**执行若干次函数调用，保证不会出现递归（即不会直接或间接地调用本身）。

在使用该数据库应用时，用户可一次性输入要调用的函数序列（一个函数可能被调用多次），在**依次**执行完序列中的函数后，系统中的数据被加以更新。某一天，小 A 在应用该数据库程序处理数据时遇到了困难：由于频繁而低效的函数调用，系统在执行操作时进入了无响应的状态，他只好强制结束了数据库程序。为了计算出正确数据，小 A 查阅了软件的文档，了解到每个函数的具体功能信息，现在他想请你根据这些信息帮他计算出更新后的数据应该是多少。

inputFormat:
第一行一个正整数 $n$，表示数据的个数。
第二行 $n$ 个整数，第 $i$ 个整数表示下标为 $i$ 的数据的初始值为 $a_i$。
第三行一个正整数 $m$，表示数据库应用程序提供的函数个数。函数从 $1 \sim m$ 编号。
接下来 $m$ 行中，第 $j$（$1 \le j \le m$）行的第一个整数为 $T_j$，表示 $j$ 号函数的类型：

1. 若 $T_j = 1$，接下来两个整数 $P_j, V_j$ 分别表示要执行加法的元素的下标及其增加的值；
2. 若 $T_j = 2$，接下来一个整数 $V_j$ 表示所有元素所乘的值；
3. 若 $T_j = 3$，接下来一个正整数 $C_j$ 表示 $j$ 号函数要调用的函数个数，
  随后 $C_j$ 个整数 $g^{(j)}_1, g^{(j)}_2, \ldots , g^{(j)}_{C_j}$ 依次表示其所调用的函数的编号。

第 $m + 4$ 行一个正整数 $Q$，表示输入的函数操作序列长度。
第 $m + 5$ 行 $Q$ 个整数 $f_i$，第 $i$ 个整数表示第 $i$ 个执行的函数的编号。

outputFormat: 一行 $n$ 个用空格隔开的整数，按照下标 $1 \sim n$ 的顺序，分别输出在执行完输入的函数序列后，数据库中每一个元素的值。**答案对** $\boldsymbol{998244353}$ **取模。**

samples:
见附件中的 call/call3.in
见附件中的 call/call3.ans


title: [CSP-S2020] 动物园

description:
动物园里饲养了很多动物，饲养员小 A 会根据饲养动物的情况，按照《饲养指南》购买不同种类的饲料，并将购买清单发给采购员小 B。

具体而言，动物世界里存在 $2^k$ 种不同的动物，它们被编号为 $0 \sim 2^k - 1$。动物园里饲养了其中的 $n$ 种，其中第 $i$ 种动物的编号为 $a_i$。

《饲养指南》中共有 $m$ 条要求，第 $j$ 条要求形如“如果动物园中饲养着某种动物，满足其编号的二进制表示的第 $p_j$ 位为 $1$，则必须购买第 $q_j$ 种饲料”。其中饲料共有 $c$ 种，它们从 $1 \sim c$ 编号。本题中我们将动物编号的二进制表示视为一个 $k$ 位 01 串，第 $0$ 位是最低位，第 $k - 1$ 位是最高位。

根据《饲养指南》，小 A 将会制定饲料清单交给小 B，由小 B 购买饲料。清单形如一个 $c$ 位 $01$ 串，第 $i$ 位为 $1$ 时，表示需要购买第 $i$ 种饲料；第 $i$ 位为 $0$ 时，表示不需要购买第 $i$ 种饲料。 实际上根据购买到的饲料，动物园可能可以饲养更多的动物。更具体地，如果将当前未被饲养的编号为 $x$ 的动物加入动物园饲养后，饲料清单没有变化，那么我们认为动物园当前还能饲养编号为 $x$ 的动物。

现在小 B 想请你帮忙算算，动物园目前还能饲养多少种动物。

inputFormat:
第一行包含四个以空格分隔的整数 $n, m, c, k$。
分别表示动物园中动物数量、《饲养指南》要求数、饲料种数与动物编号的二进制表示位数。
第二行 $n$ 个以空格分隔的整数，其中第 $i$ 个整数表示 $a_i$。
接下来 $m$ 行，每行两个整数 $p_i, q_i$ 表示一条要求。
数据保证所有 $a_i$ 互不相同，所有的 $q_i$ 互不相同。

outputFormat: 仅一行一个整数表示答案。

samples:
见附件中的 zoo/zoo3.in
见附件中的 zoo/zoo3.ans

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

动物园里饲养了编号为 $1, 4, 6$ 的三种动物，《饲养指南》上的三条要求为：

1. 若饲养的某种动物的编号的第 $0$ 个二进制位为 $1$，则需购买第 $3$ 种饲料。
2. 若饲养的某种动物的编号的第 $2$ 个二进制位为 $1$，则需购买第 $4$ 种饲料。
3. 若饲养的某种动物的编号的第 $2$ 个二进制位为 $1$，则需购买第 $5$ 种饲料。

饲料购买情况为：

1. 编号为 $1$ 的动物的第 $0$ 个二进制位为 $1$，因此需要购买第 $3$ 种饲料；
2. 编号为 $4, 6$ 的动物的第 $2$ 个二进制位为 $1$，因此需要购买第 $4, 5$ 种饲料。

由于在当前动物园中加入一种编号为 $0, 2, 3, 5, 7, 8, \ldots , 15$ 之一的动物，购物清单都不会改变，因此答案为 $13$。

**【数据范围】**

对于 $20 \%$ 的数据，$k \le n \le 5$，$m \le 10$，$c \le 10$，所有的 $p_i$ 互不相同。
对于 $40 \%$ 的数据，$n \le 15$，$k \le 20$，$m \le 20$，$c \le 20$。
对于 $60 \%$ 的数据，$n \le 30$，$k \le 30$，$m \le 1000$。
对于 $100 \%$ 的数据，$0 \le n, m \le 10^6$，$0 \le k \le 64$，$1 \le c \le 10^8$。


title: [CSP-S2020] 贪吃蛇

description:
草原上有 $n$ 条蛇，编号分别为 $1, 2, \ldots , n$。初始时每条蛇有一个体力值 $a_i$，我们称编号为 $x$ 的蛇实力比编号为 $y$ 的蛇强当且仅当它们当前的体力值满足 $a_x > a_y$，或者 $a_x = a_y$ 且 $x > y$。

接下来这些蛇将进行决斗，决斗将持续若干轮，每一轮实力最强的蛇拥有选择权，可以选择吃或者不吃掉实力最弱的蛇：

1. 如果选择吃，那么实力最强的蛇的体力值将减去实力最弱的蛇的体力值，实力最弱的蛇被吃掉，退出接下来的决斗。之后开始下一轮决斗。
2. 如果选择不吃，决斗立刻结束。

每条蛇希望在自己不被吃的前提下在决斗中尽可能多吃别的蛇（显然，蛇不会选择吃自己）。

现在假设每条蛇都足够聪明，请你求出决斗结束后会剩几条蛇。

本题有多组数据，对于第一组数据，每条蛇体力会全部由输入给出，之后的每一组数据，会相对于上一组的数据，修改一部分蛇的体力作为新的输入。

inputFormat:
第一行一个正整数 $T$，表示数据组数。
接下来有 $T$ 组数据，对于第一组数据，第一行一个正整数 $n$，第二行 $n$ 个非负整数表示 $a_i$。
对于第二组到第 $T$ 组数据，每组数据：
第一行第一个非负整数 $k$ 表示体力修改的蛇的个数。
第二行 $2k$ 个整数，每两个整数组成一个二元组 $(x,y)$，表示依次将 $a_x$ 的值改为 $y$。一个位置可能被修改多次，以最后一次修改为准。

outputFormat: 输出 $T$ 行，每行一个整数表示最终存活的蛇的条数。

samples:
见附件中的 snakes/snakes3.in
见附件中的 snakes/snakes3.ans

samples:
见附件中的 snakes/snakes4.in
见附件中的 snakes/snakes4.ans

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

第一组数据，第一轮中 $3$ 号蛇最强，$1$ 号蛇最弱。若 $3$ 号蛇选择吃，那么它将在第二轮被 $2$ 号蛇吃掉。因此 $3$ 号蛇第一轮选择不吃，$3$ 条蛇都将存活。

对于第二组数据，$3$ 条蛇体力变为 $5, 6, 25$。第一轮中 $3$ 号蛇最强，$1$ 号蛇最弱，若它选择吃，那么 $3$ 号蛇体力值变为 $20$，在第二轮中依然是最强蛇并能吃掉 $2$ 号蛇，因此 $3$ 号蛇会选择两轮都吃，最终只有 $1$ 条蛇存活。

**【数据范围】**

对于 $20 \%$ 的数据，$n = 3$。
对于 $40 \%$ 的数据，$n \le 10$。
对于 $55 \%$ 的数据，$n \le 2000$。
对于 $70\%$ 的数据，$n \le 5 \times {10}^4$。
对于 $100\%$ 的数据：$3 \le n \le {10}^6$，$1 \le T \le 10$，$0 \le k \le {10}^5$，$0 \le a_i, y \le 10^9$。保证每组数据（包括所有修改完成后的）的 $a_i$ 以不降顺序排列。


title: Mivik 卷积

background: 卷王之王卷穿肠（doge

description:
从前有一只 Mivik，他喜欢卷积。他定义两个仅与 $x$ 有关的多项式函数 $f\left(x\right)$ 和 $g\left(x\right)$ 的 Mivik 卷积如下：

$$
f\left(x\right)\otimes g\left(x\right)=\sum_{k=0}^{\deg f +\deg g}\max_{i\in [0,\deg f] \land j\in [0,\deg g]\land i+j=k}\left\{\left[x^i\right]f\left(x\right)+\left[x^j\right]g\left(x\right)\right\} x^k
$$

其中 $\deg f$ 表示 $f$ 的最高项次数，$\left[x^i\right]f\left(x\right)$ 代表 $f\left(x\right)$ 这一函数中 $x^i$ 这一项的系数。

请注意，Mivik 卷积是左结合的，也就是说 $a\otimes b\otimes c=(a\otimes b)\otimes c$。

Mivik 定义 Mivik 函数为能表示为 $f\left(x\right)=ax+b$ 形式的函数，其中 $a$、$b$ 均为整数。例如 $f\left(x\right)=-3+2x$ 是 Mivik 函数，而 $f\left(x\right)=\frac{1}{x}$ 不是。

Mivik 又定义一个函数 $f\left(x\right)$ 是 simple 的，当且仅当存在一个 Mivik 函数的序列 $S$（大小为 $\left|S\right|$），使得：

$$
f\left(x\right)=S_1\otimes S_2\otimes S_3\otimes\cdots\otimes S_{\left|S\right|}.
$$

现在 Mivik 给了你一个多项式函数，问你这个函数是不是 simple 的；如果是，请顺便告诉他任意一种可能的 $S$。

inputFormat:
第一行一个正整数 $n$，代表这个多项式函数的项数。

第二行 $n$ 个整数，次数从低到高依次代表这个多项式函数的系数 $f_i$。保证最高项系数不为 $0$。

outputFormat:
如果这个函数不是 simple 的，输出一行 `nice`。

否则，先输出一行 `simple`，然后接下来一行输出你构造的 $S$ 的大小 $\left|S\right|$。接下来在 $\left|S\right|$ 行给出你构造的 $S$ 序列，每行两个整数 $a$ 和 $b$，描述一个 Mivik 函数 $f\left(x\right)=ax+b$。


title: [eJOI2020 Day1] Exam

description:
给定一个长度为 $N$ 的序列 $A_i$，你可以进行无数次下面这个操作：

- 选定一个大小不小于 $2$ 的区间，使得这个区间里的数等于这个区间里的最大值。

你需要用这些操作使得 $A_i=B_i$，求最多能使得多少数满足要求。

inputFormat:
第一行一个整数 $N$ 代表序列长度。
第二行 $N$ 个整数代表序列 $A_i$。
第三行 $N$ 个整数代表序列 $B_i$。

hint:
#### 样例 1 解释

可以选择对区间 $[1,2]$ 进行操作，最多能有 $2$ 个数满足要求。

#### 样例 2 解释

$A_2$ 或 $A_3$ 能满足要求，但他们不能同时满足要求。

#### 数据规模与约定

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

- Subtask 1（14 pts）：$N \le 10$。
- Subtask 2（12 pts）：$N \le 10^5$，所有 $B_i$ 都相等。
- Subtask 3（13 pts）：$N \le 5000$，$A_i$ 为严格单调递增序列。
- Subtask 4（23 pts）：$N \le 10^5$，$A_i$ 两两不同。
- Subtask 5（16 pts）：$N \le 200$。
- Subtask 6（22 pts）：$N \le 5000$。

对于 $100\%$ 的数据：

- $2 \le N$。
- $1 \le A_i \le 10^9$。
- $1 \le B_i \le 10^9$。

#### 说明

翻译自 [eJOI 2020 Day1 C Exam](https://ejoi2020.ge/static/assets/Day1/Problems/Exam.pdf)。


title: [eJOI2020 Day2] XOR Sort

description:
给定一个长为 $N$ 的序列 $A_i$，你可以进行如下操作：

> 选定一个位置 $i$，将 $A_i$ 修改为 $A_i \oplus A_{i+1}$ 或 $A_i \oplus A_{i-1}$。

你想知道，需要用多少次操作才能把 $A_i$ 变为：

- $S=1$，严格单调递增序列，即 $A_i<A_{i+1}$。
- $S=2$，非严格单调递增序列，即 $A_i \le A_{i+1}$。

inputFormat:
第一行两个整数 $N,S$，代表序列长度以及测试点类型。
第二行 $N$ 个整数 $A_i$ 代表这个序列。

outputFormat:
第一行一个整数 $K$ 代表操作次数，你不需要使得 $K$ 最小，你只需要满足 $0 \le  K \le 4 \times 10^4$。
接下来 $K$ 行每行两个整数 $i,j$ 代表要把 $A_i$ 修改为 $A_i \oplus A_j$，其中 $j=i+1$ 或 $i-1$。


title: [eJOI2020 Day1] Fountain

description:
大家都知道喷泉吧？现在有一个喷泉由 $N$ 个圆盘组成，从上到下以此编号为 $1 \sim N$，第 $i$ 个喷泉的直径为 $D_i$，容量为 $C_i$，当一个圆盘里的水大于了这个圆盘的容量，那么水就会溢出往下流，直到流入半径大于这个圆盘的圆盘里。如果下面没有满足要求的圆盘，水就会流到喷泉下的水池里。

现在给定 $Q$ 组询问，每一组询问这么描述：

- 向第 $R_i$ 个圆盘里倒入 $V_i$ 的水，求水最后会流到哪一个圆盘停止。

如果最终流入了水池里，那么输出 $0$。

**注意，每个询问互不影响。**

inputFormat:
第一行两个整数 $N,Q$ 代表圆盘数和询问数。
接下来 $N$ 行每行两个整数 $D_i,C_i$ 代表一个圆盘。
接下来 $Q$ 行每行两个整数 $R_i,V_i$ 代表一个询问。

outputFormat: $Q$ 行每行一个整数代表询问的答案。

hint:
#### 样例 1 解释

前两个询问的解释如下图所示：

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

因为每个询问互不影响，对于第三个询问，第 $5$ 个圆盘里的水不会溢出。

#### 数据规模与约定

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

- Subtask 1（30 pts）：$N \le 1000$，$Q \le 2000$。
- Subtask 2（30 pts）：$D_i$ 为严格单调递增序列。
- Subtask 3（40 pts）：无特殊限制。

对于 $100\%$ 的数据：

- $2 \le N \le 10^5$。
- $1 \le Q \le 2 \times 10^5$。
- $1 \le C_i \le 1000$。
- $1 \le D_i,V_i \le 10^9$。
- $ 1\le R_i \le N$。

#### 说明

翻译自 [eJOI 2020 Day1 A Fountain](https://ejoi2020.ge/static/assets/Day1/Problems/Fountain.pdf)。


title: [eJOI2020 Day1] Triangulation

background:
[使用说明](https://www.luogu.com.cn/paste/1nsbzh41)

---

题目中的 $(A,B)$ 代表一条从 $A$ 连到 $B$ 的对角线。

定义正多边形的顶点 $A$ 到顶点 $B$ 的 eJ 距离为点 $A$ 顺时针走到点 $B$ 需要的边数和点 $A$ 逆时针走到点 $B$ 需要的边数的最大值。根据这个定义，也可以拓展出正多边形的顶点 $A$ 到一条正多边形的对角线 $B$ 的 eJ 距离的定义，即点 $A$ 顺时针走到对角线 $B$ 的一个端点（离的最近的端点）需要的边数和逆时针走需要的边数的最大值。

比如点 $0$ 到对角线 $(0,5)$ 的 eJ 距离为 $5$，顺时针走需要经过 $5$ 条边，逆时针要经过 $2$ 条，答案为 $\max\{5,2\}=5$。

description:
给定一个 $N$ 边形，点顺时针编号为 $0 \sim N-1$，现在小 A 画了 $n-3$ 条对角线，保证这 $n-3$ 条对角线除了顶点外没有额外交点。

现在小 A 想让小 J 猜猜哪条对角线离点 $0$ 的 eJ 距离最近，并回答这个距离。

小 J 并不能通过读心术知道答案，所以他只能找小 A 索要一些线索。小 A 给了小 J $n$ 的值，并且答应小 J 可以找小 A 询问一对顶点之间是否有对角线，但小 J 的询问次数有限制。

小 J 还要 AK eJOI，所以这个问题就交给了你。

#### 交互规则

你需要调用 `triangulation.h` 头文件。

```cpp
int solve(int n)
```

- 这个函数只能被调用一次。
- $n$：多边形顶点个数。
- 假设答案对角线为 $(a,b)$，这个函数应该返回 $a \times n+b$。
- 如果有多条对角线离点 $0$ 最近，可以只返回其中一条。

solve 函数可以调用若干次下面这个函数：

```cpp
int query(int x, int y)
```

- $x,y$：代表一组询问。
- $0 \le x,y \le n-1$。
- 如果 $(x,y)$ 存在，返回 $1$，否则返回 $0$。

hint:
#### 样例 1

样例输入格式仅包含一个整数 $n$。

|调用函数|返回值|
|:-:|:-:|
|`solve(7)`||
|`query(0,3)`|$0$|
|`query(0,5)`|$1$|
|`query(1,5)`|$1$|
||solve 函数返回 $1 \times7+5=12$|
||正确|

#### 数据规模与约定

对于 $100\%$ 的数据，$5 \le n \le 100$。

假设 $q$ 为你单组数据的询问次数，令 $w=\dfrac{n \times (n-3)}{2}$，你单组数据的分数为：

- 询问不合法，答案错误或 $w<q$，你会得到 $0\%$ 的分数。
- $n<q \le w$，你会得到 $10+60 \times \dfrac{w-q}{w-n}\%$ 的分数。
- $q \le n$，你会得到 $100\%$ 的分数。

感谢 @[FZzzz](https://www.luogu.com.cn/user/174045) 提供的 checker & grader。

#### 说明

翻译自 [eJOI 2020 Day1 B Triangulation](https://ejoi2020.ge/static/assets/Day1/Problems/Triangulation.pdf)。


title: [eJOI2020 Day2] Dots and Boxes

background: 小 T 和小 A 在玩一种点格游戏。

description:
首先，小 T 拿出了一张拥有 $(N+1) \times (M+1)$ 个格点的方格纸（这些格子从上到下，从左到右可以编号为第 $1 \sim N+1$ 行第 $1 \sim M+1$ 列的格点），每个格点向上下左右的那个格点（如果那个方向有格点的话）连边，不难发现，会形成一个 $N \times M$ 的方格矩阵。但是小 T 拿出的是没有连边的格点方格纸，小 T 和小 A 的目标就是在格点之间连线。

游戏规则是这样的，每一轮玩家可以在两个格点之间连线，如果连完线能连好一个格子，那么这个格子就属于这个玩家了。然后玩家可以继续连线，直到连完线不能获得格子为止，就换到下一个玩家。当所有玩家都不能连线时，游戏结束。

比如下面这张图即为当 $N=2,M=3$ 时两位玩家可能的连线结果：

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

其中虚线为这一轮玩家连的线。

小 A 和小 T 已经玩了许久了，你发现他们现在的方格纸满足每一个格子周围的四条边都有 **$0$ 条或 $2$ 条未被连线**，比如下面这张图就满足要求，上面这张图除了第一幅图也都满足要求：

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

并且刚好轮到小 A 了。

定义小 A 和小 T 的分数 $S_A,S_T$ 为玩家从现在开始得到的分数，那么整个游戏的分数即为 $S_A-S_T$，小 A 要让整个游戏的分数变得越大越好，小 T 则反之，他们都会按照他们的目标做最优策略。

你要求出他们做最优策略下得到的分数。

inputFormat:
第一行两个整数 $N,M$ 代表方格纸的大小。

接下来 $N+1$ 行每行 $M$ 个 **不用空格隔开的** 整数，包含 $0$ 和 $1$，第 $i$ 行第 $j$ 个数为 $0$ 就代表第 $i$ 行第 $j$ 列的格点与第 $i$ 行第 $j+1$ 列的格点之间没有连线，$1$ 则反之。

接下来 $N$ 行每行 $M+1$ 个 **不用空格隔开的** 整数，包含 $0$ 和 $1$，第 $i$ 行第 $j$ 个数 $0$ 就代表第 $i$ 行第 $j$ 列的格点与第 $i+1$ 行第 $j$ 列的格点之间没有连线，$1$ 则反之。

hint:
#### 样例 1 解释

下图为其中一种连线方式，红色为小 A 的操作，蓝色为小 T 的操作：

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

#### 样例 2 解释

这个样例为题目描述中的第二个图片。

#### 数据规模与约定

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

- Subtask 1（20 pts）：给出的输入只包含一个连通块。
- Subtask 2（20 pts）：$N \times M \le 12$。
- Subtask 3（20 pts）：给出的输入只包含两个连通块。
- Subtask 4（20 pts）：$N,M \le 7$。
- Subtask 5（20 pts）：无特殊限制。

对于 $100\%$ 的数据，$3 \le N, M \le 20$，**每一个格子周围的四条边都有 $0$ 条或 $2$ 条未被连线**。

其中一个连通块定义为已连上的边与方格纸的边缘围起来的块，比如说下面这个图有 $5$ 个连通块：

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

注意已被玩家占有的方格不属于任意一个连通块。

#### 说明

翻译自 [eJOI 2020 Day2 C Dots and Boxes](https://ejoi2020.ge/static/assets/Day2/Problems/Game.pdf)。


title: [yLOI2020] 不离

background:
> 乱玄黄时序，探风林实虚。
> 我要你共我奇谈怪趣。
> 任日月斑斓，待春秋兴残。
> 我要我们有聚无散。

——银临《不离》

description:
这道题目来自 zxy 哔哔，咕咕让哔哔选一首歌作为题目名，但是哔哔说没有想好，于是咕咕就帮他选了这首歌。

哔哔在玩一款叫做《暗黑破坏神》的游戏，某天哔哔灵光乍现，以游戏为背景出了一道神仙题并告诉了咕咕。咕咕并不会做，于是对题目进行了一定的简化。因此，经过简化后，这道题已经和《暗黑破坏神》没什么关系了。

游戏中人物有两个属性，我们分别称之为「力量」和「精神」，同时哔哔有 $n$ 件装备，穿戴第 $i$ 件装备需要人物在穿戴前的力量值不低于 $a_i$，精神值不低于 $b_i$。在穿戴第 $i$ 件装备后，人物的力量值会增加 $c_i$，精神值会增加 $d_i$。

哔哔可以自由选择穿装备的顺序，只要满足力量和精神不低于对应值，就可以穿戴该装备。

现在，咕咕想知道，如果想让哔哔穿戴上所有的装备，那么人物的初始力量值（即没有穿任何装备之前的力量值）最小应该是多少？在初始力量值最小的前提下，初始精神值（即没有穿任何装备之前的精神值）最小应该是多少？

显然，初始力量和初始精神都应该是非负整数。

inputFormat:
第一行有一个整数，表示该测试点所在的子任务编号 $T$。
第二行有一个整数，表示哔哔的装备件数 $n$。
第 $3$ 到第 $(n+2)$ 行，每行四个整数，第 $(i+2)$ 行的整数依次表示 $a_i,b_i,c_i,d_i$。

outputFormat: 输出一行两个用空格隔开的整数，分别表示最小的初始力量值以及在初始力量值最小的前提下最小的初始精神值。

hint:
### 样例 1 解释

当初始力量值为 $1$，精神值为 $2$ 时，可以穿戴第 $2$ 件装备。在穿戴该装备后，增加 $3$ 点力量和 $4$ 点精神，人物的属性变为 $4$ 点力量和 $6$ 点精神，此时可以穿戴第 $1$ 件装备。

### 数据规模与约定

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

- 子任务 $1$（$5$ 分）：保证 $n=0$。
- 子任务 $2$（$5$ 分）：保证 $n=1$。
- 子任务 $3$（$20$ 分）：保证 $a_i,b_i \le 100$，$n \le 6$。
- 子任务 $4$（$10$ 分）：保证 $a_i,b_i \le 10^5$，$n \le 6$。
- 子任务 $5$（$10$ 分）：保证 $a_i,b_i \le 10$。
- 子任务 $6$（$10$ 分）：保证 $a_i,b_i \le 100$。
- 子任务 $7$（$10$ 分）：保证 $b_i=0$，$n \le 6$。
- 子任务 $8$（$10$ 分）：保证 $b_i=0$。
- 子任务 $9$（$10$ 分）：保证 $n \le 6$。
- 子任务 $10$（$10$ 分）：无特殊约定。

对于全部的测试点，保证 $0 \le n \le 10^5$，$0 \le a_i,b_i,c_i,d_i \le 10^9$。

### 提示
有 $4$ 个样例文件，请见附加文件中的 forever.zip。

对于第三个样例，满足 $b_i = 0$。


title: [yLOI2020] 牵丝戏

background:
> 风雪依稀秋白发尾， 灯火葳蕤，揉皱你眼眉。
> 假如你舍一滴泪，假如老去我能陪。
> 烟波里成灰，也去得完美。

——银临 & Aki阿杰《牵丝戏》

description:
扶苏和扶咕咕最近在玩一款叫做「ddt」的游戏，因为玩「ddt」时一直在循环《牵丝戏》，所以想到牵丝戏就想到了这个游戏。

为了简化问题，我们认为这是一款一对一回合制游戏。双方玩家各有一个属性，被称为 delay 值，简称 $d$ 值。$d$ 值会根据回合中玩家使用的道具类型和数量来进行相应的增加。我们定义玩家 $x$ 的回合为玩家 $x$ 从发动攻击到结束的整个过程。**在玩家 $x$ 的回合中，只有玩家 $x$ 可以使用道具和发动攻击，并且玩家 $x$ 一定会发动攻击**。当一个玩家的回合结束以后，下一回合将是两个玩家中 $d$ 值**较小**的玩家的回合。当两个玩家的 $d$ 值相同时，因为扶苏氪金很多，下一回合一定是**扶苏的回合**。

这款游戏共有 $m$ 种道具，第 $i$ 种道具会将本回合的伤害增加**不计算其他道具的原始伤害**的 $\frac{k_i}{10^5}$ 倍，同时会增加 $p_i$ 点 $d$ 值。每回合**每种道具只能使用一次，本回合的道具不会对下回合产生伤害增益效果**。同时，每回合结束以后，发动攻击的玩家一定会增加 $w$ 点 $d$ 值。

而使用道具是受到双方 $d$ 值差限制的。具体的，任何回合所使用的道具应该满足本回合结束以后双方 $d$ 值（包括发动攻击的玩家一定增加的 $w$ 点 $d$ 值）之差的绝对值**不超过** $100$。一个显然的事实是，只要保证了 $w \le 100$，玩家就一定存在一种选择道具的方法（包括不选择），来满足这个限制。

例如，在扶咕咕的回合中，若她的原始伤害 $t=10^5$，初始时 $d$ 值 $d_0=3$，规定 $w=2$，她使用了两个道具，$k_1=114$，$k_2=514$，$p_1=19$，$p_2=81$，那么本回合她造成的伤害为

$$t + t \times k_1 + t \times k_2 = 10^5 + 114 + 514 =  100628$$

她回合结束后的 $d$ 值为

$$d_0 + w + p_1 + p_2 = 3 + 2 + 19 + 81 = 105$$

而假如下回合还是她的回合，并且她没有使用道具，那么她下回合造成的伤害为

$$t =  100000$$

她下回合结束后的 $d$ 值为

$$105 + w = 105 + 2 = 107$$

现在扶苏和扶咕咕正在对战。给定游戏的道具列表，和他们的原始伤害、 $d$ 值。游戏一共会进行 $n$ 回合，不妨认为无论造成多大的伤害，双方都不会死亡。请你最大化「扶苏对扶咕咕造成的伤害 - 扶咕咕对扶苏造成的伤害」这个差的值。

当然，扶咕咕也会尽可能最大化「她对扶苏造成伤害 - 扶苏对她造成伤害」的值。不妨认为扶苏是 yLOI 世界中最聪明的男孩子，扶咕咕是 yLOI 世界中最聪明的女孩子，也就是**他们都会选择最优的策略来使用道具而不会出错**，题目所求即为在这种情况下伤害差的最大值。

inputFormat:
第一行有一个整数，表示该测试点所在的子任务编号 $T$。
第二行有三个整数，分别表示游戏的回合数 $n$，游戏的装备数 $m$ 以及每回合固定增加的 $d$ 值 $w$。
第三行有 $m$ 个整数，第 $i$ 个整数表示 $k_i$。
第四行有 $m$ 个整数，第 $i$ 个整数表示 $p_i$。
第五行有四个整数，依次表示扶苏的初始伤害 $x_a$，扶咕咕的初始伤害 $x_b$，扶苏的初始 $d$ 值 $d_a$，扶咕咕的初始 $d$ 值 $d_b$。

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

hint:
### 样例 1 解释

- 第一回合开始前，扶苏 $d$ 值为 $2$，扶咕咕 $d$ 值为 $3$，第一回合由扶苏出手。扶苏不使用道具，伤害为 $100000$，$d$ 值增加 $1$，总伤害差为 $100000$。
- 第一回合结束后，双方 $d$ 值均为 $3$，第二回合由扶苏出手。扶苏使用第一个道具，伤害为 $100050$，$d$ 值增加 $21$，总伤害差为 $200050$。
- 第二回合结束后，扶苏 $d$ 值为 $24$，扶咕咕 $d$ 值为 $3$，第三回合由扶咕咕出手。扶咕咕使用 $1$ 、 $2$ 两个道具，伤害为 $200102$，$d$ 值增加 $121$，总伤害差为 $-52$。这回合结束后，双方 $d$ 值差恰好为 $100$，符合要求。

### 数据规模与约定

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

- 子任务 $1$（$5$ 分）：保证 $n=0$。
- 子任务 $2$（$10$ 分）：保证 $m=0$。
- 子任务 $3$（$15$ 分）：保证 $n,m \le 5$。
- 子任务 $4$（$20$ 分）：保证 $n \le 3$。
- 子任务 $5$（$20$ 分）：保证 $m \le 10$。
- 子任务 $6$（$30$ 分）：无特殊约定。

对于全部的测试点，保证 $0 \le n \le 10^3$，$0 \le m \le 10^5$，$1 \le p_i,w \le 100$，$1 \le x_a,x_b,k_a,d_a,d_b \le 10^9$，$x_a$ 与 $x_b$ 是 $10^5$ 的倍数，$1 \le |d_a-d_b| \le 100$。

### 提示

共有 4 个样例文件，请见附加文件中的 opera.zip。
对于样例 2，满足 $m = 0$。
对于样例 3，满足 $n \leq 3$。


title: [yLOI2020] 泸沽寻梦

background:
> 我应是泸沽烟水里的过客，
> 孑然弹铗，划天地开阖。
> 邂逅过的，梦醒之余，
> 却忘了该如何洒脱。

——银临《泸沽寻梦》

description:
> 南有仙地，名曰摩梭，摩梭有湖，泸沽是也。

茶茶在泸沽湖中寻找自己的梦。氤氲雾气中，茶茶的 $n$ 个梦排成了一个序列。茶茶的所有梦境都是拉瓦的样子。为了区分这些拉瓦，茶茶规定从左到右第 $i$ 个的拉瓦的美颜值是一个非负整数 $a_i$。面对着这些梦，茶茶会进行 $m$ 次操作，每次操作会给定两个数字 $p,x$，然后将 $a_p$ 和 $a_{p+1}$ 都对 $x$ 做按位异或。每次操作完之后，茶茶都想知道，当前的梦序列中，有多少个子区间 $[l,r]$，满足 $l \le r$ 且区间的异或和为 $0$，请你回答茶茶的问题。

区间 $[l,r]$ 的异或和定义为 $a_l \otimes a_{l + 1} \otimes \dots a_{r - 1} \otimes a_r$。其中 $\otimes$ 代表二进制按位异或运算，即 C++ 语言的「^」运算符。两个区间不同当且仅当两区间左端点不同或两区间右端点不同或两区间左右端点均不同。

为了避免输出过大，你只需要输出四个整数，分别表示你所有回答的按位异或之和、你共有多少次回答的答案是奇数，你的所有答案中的最大值、你的所有答案中的最小值。

inputFormat:
第一行有两个整数，分别表示梦境的数量 $n$ 和操作的次数 $m$。
第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数表示第 $i$ 个拉瓦的美颜值 $a_i$。
接下来 $m$ 行，每行两个整数，依次表示一次操作的 $p$ 和 $x$。

outputFormat: 输出四行，每行一个整数，依次表示你所有回答的按位异或之和、你共有多少次回答的答案是奇数，你的所有答案中的最大值、你的所有答案中的最小值。

hint:
### 样例 1 解释

- 第一次操作后，序列变为 ${2,1,3,4,5}$，有且仅有区间 $[1,3]$ 的异或和为 $0$，故本次询问的答案为 $1$。
- 第二次操作后，序列变为 ${2,2,0,4,5}$，区间 $[1,2]$、$[1,3]$、$[3,3]$ 的异或和为 $0$，故本次询问的答案为 $3$。
- 第三次操作后，序列变为 ${2,2,3,7,5}$，有且仅有区间 $[1,2]$ 的异或和为 $0$，故本次询问的答案为 $1$。所有答案的异或和为 $3$，有 $3$ 次回答的答案为奇数，所有答案中的最大值为 $3$，最小值为 $1$。

### 数据规模与约定

**本题采用多测试点捆绑测试**，共有 5 个子任务。

- 子任务 $1$（$10$ 分）：保证 $n,m \le 100$。
- 子任务 $2$（$10$ 分）：保证 $n,m \le 300$。
- 子任务 $3$（$20$ 分）：保证 $n,m \le 3000$。
- 子任务 $4$（$30$ 分）：保证 $n,m \le 10^5$。
- 子任务 $5$（$30$ 分）：无特殊限制。

对于前四个子任务，保证 $a_i,x \le n$；
对于全部的测试点，保证 $1 \le n,m \le 10^6$，$0 \le a_i,x \le 10^9$，$1 \le p<n$。

### 提示

- 请注意，$a_i,x \leq Y$ 不能说明 $a_i \otimes x \leq Y$。
-  请注意大量数据读入对程序效率造成的影响。
- 本题的特殊输出方式只是为了避免输出过大造成程序超时，与本题解法无关。
- 请注意常数因子对程序效率造成的影响。
- 本题共有两个样例文件，请见附加文件中的 dream.zip。


title: [yLOI2020] 凉凉

background:
> 凉凉三生三世恍然如梦，须臾的年风干泪痕。
> 若是回忆不能再相认，就让情分落九尘。
> 凉凉十里何时还会春盛，又见树下一盏风存。
> 落花有意流水无情，别让恩怨爱恨凉透那花的纯，吾生愿牵尘。

——张碧晨&杨宗纬《凉凉》

description:
这是 yLOI 系列竞赛中第一道以歌曲命名但歌手不是银临的题目。这道题目的歌曲和问题没什么关系，只是我们的主人公叫凉凉，于是扶苏为他选择了这首歌。

凉凉在和「七瑾在成都喝着凉茶看 jk 边咕咕边嘎嘎边哔哔边在瓦片上吭吭哧哧切企鹅」群的部分群友在青岛面基结束后，和扶苏一起乘坐地铁被七瑾送到了青岛北站。在乘坐地铁的途中，他们经过了「做物理站（错埠岭站）」，做完了高考物理的凉凉给一点都不想做物理的扶苏提了一个物理问题，扶苏不会做，所以凉凉决定考你一道经济学问题。

青岛共有 $n$ 条地铁线路和 $m$ 个地铁站点。每条线路的地铁都在地下以某一固定的深度运行，而如果某深度为 $i$ 的地铁经过了地铁站 $j$，那么地铁站 $j$ 就要在深度为 $i$ 的地方挖一个站台作为上下客口，开挖该上下客口的花费为 $a_{i,j}$。我们忽略建设上下客口通向地面的通道的费用，而只考虑在该深度建上下客口的花费。显而易见，对于线路 $u$ 和线路 $v$，如果他们都经过了同一个地铁站，那么他们线路不能处在同一深度，否则两线地铁将会相撞。而如果 $u$ 和 $v$ 不存在任何一个相同的经过站点，那么这两条线既可以处在同一高度，也可以不处在同一高度。

在这个问题中，你可以认为任何两个地铁不会在除了站点以外的行驶途中相遇，也即你无需考虑两个地铁因为行驶线路交叉而在两站点之间相遇的情况。

将站点从 $1$ 至 $m$ 编号，线路从 $1$ 至 $n$ 编号，现在给定你 $n$ 条线路的经过站点列表和在每个站点的每个深度的建站花费，请你求出让所有的地铁正常运行的最小建站花费总和。

inputFormat:
第一行有两个整数，分别表示地铁线路的数量 $n$ 和站点个数 $m$。
第 $2$ 到第 $(n+1)$ 行，每行 $m$ 个整数，第 $(i+1)$ 行的第 $j$ 个整数表示 $a_{i,j}$。
第 $(n+2)$ 行到第 $(2n+1)$ 行，每行若干个整数，第 $(n+i+1)$ 行表示地铁 $i$ 号线的运行线路信息：

>每行首先有一个整数 $c$，表示该线经过的站点个数，接下来该行有 $c$ 个互不相同的整数 $u$，依次表示该地铁经过的站点编号。

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

hint:
### 样例 1 解释

$1$ 号线和 $2$ 号线都经过了站点 $1$，因此他们不能处于同一深度。
令 $1$ 号线在深度 $2$ 运行，$2$ 号线在深度 $1$ 运行，则需要修建站点 $1$ 的深度 $1$ 、 $2$ 的上下客口（花费为 $4+4=8$），站点 $2$ 的深度为 $2$ 的上下客口（花费为 $1$），站点 $3$ 的深度为 $1$ 的上下客口（花费为 $1$），总花费为 $10$。可以证明，这是最优的方案。

### 数据规模与约定

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

- 对于 $5\%$ 的数据，保证 $n=1$。
- 对于 $35\%$ 的数据，保证 $n,m \le 6$。
- 对于 $70\%$ 的数据，保证 $n \le 10$。
- 对于 $100\%$ 的数据，保证 $1 \le n \le 14$，$1 \le m \le 10^5$，$1 \le a_{i,j} \le 10^9$，$1 \le c,u \le m$。

### 提示

本题共有两个附加样例文件，见附加文件中的 cold.zip。

(本来有个更大的样例，但是因为附件不让传这么大的，就被删掉了)


title: [yLOI2020] 金陵谣

background:
> 水几绕，山几重，何处金陵城。
> 访名都，寻形胜，龙虎倚江东。
> 书留翰墨，曲落潮声。
> 草木几度枯荣。

——银临《金陵谣》

description:
江苏南京，亦称金陵，是一座历史文化名城。有了古城的衬托，江苏省的高考模拟题都显地那么棘手，难以解决。切切在一轮复习过程中便碰到一道江苏省模拟题，在七瑾的帮助下，切切很快秒杀了该题，但切切觉得不够，想用这道题来刁难你。解决本题就能吃到切切和七瑾撒的糖。

给定四个正整数 $a, b, c, d$，求有多少对正整数 $(x, y)$ 满足

$$\frac a x + \frac b c = \frac d y$$

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

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

接下来 $T$ 行，每行四个整数，依次表示一组数据的 $a, b, c, d$。

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

hint:
### 样例 1 解释

求 $\frac 1 x + \frac 1 3 = \frac 2 y$ 的正整数解对数，分别是 $(x = 3, y = 3)$，$(x = 6, y = 4)$，$(x = 15, y = 5)$。

### 数据规模与约定

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

- 对于测试点 $1$，保证 $T = 0$。
- 对于测试点 $2 \sim 16$，共 $15$ 个测试点，对于 $a, b, c, d$ 四个数中至少存在一个数为 $1$ 共有 $15$ 种情况，每个测试点对应一种情况。
- 对于测试点 $17 \sim 20$，没有特殊约定。

对于全部的测试点，保证 $0 \leq T \leq 20$，$1 \leq a, b, c, d \leq 10^6$，$d \times c \leq 10^6$。

### 提示

+ 众所周知，高考不考数论。
+ 本题共有两个样例文件，见附加中的 song.zip。


title: [yLOI2020] 灼

background:
> 声嘶力竭，向悲泣的虚空祈祷至最后，
> 神为何依然残酷冷漠。
> 天国或地狱，也奢求你无垢眼眸，
> 就让我，再次被你拯救。

——银临《灼》

description:
> 这里是 NS05，勒本星球已无生命反应，请求救援！普尔！——你听得到吗？我会一直在这里，等待你的归来。

扶苏被困在了勒本星球，灼闻羽驾驶着一架宇宙飞船正打算穿越虫洞到达勒本星球拯救扶苏。

在一条数轴上有 $n$ 个虫洞，第 $i$ 个虫洞的坐标为 $x_i$。进入这些虫洞的任意一个都可以直接到达勒本星球拯救扶苏。飞船到达数轴所在直线上后，会因为磁场的效应失去操控能力，飞船每秒会**等概率**向左或向右移动一个单位长度。

灼闻羽非常焦急，他给出了 $q$ 个飞船进入数轴所在直线的初始坐标，对于每个坐标，他想知道期望需要多少秒才能到达一个虫洞。

如果你计算出的期望是个分数，你需要求出这个分数对 $998244353$ 取模的答案。有关分数取模的定义你可以参考「提示」中的内容。

为了避免输出过大，你只需要输出四个整数，分别表示你所有回答（对 $998244353$ 取模之后，下同）的按位异或之和、你共有多少次回答的答案是奇数，你的所有答案中的最大值、你的所有答案中的最小值。

inputFormat:
第一行是一个整数，表示测试点所对应的编号 $T$。
第二行有两个整数，分别表示虫洞的个数 $n$ 和初始坐标的个数 $q$。
第三行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个虫洞的坐标 $x_i$。
接下来 $q$ 行，每行一个整数，表示一个飞船进入数轴所在直线的初始坐标 $y_j$。

**保证给出的 $y_j$ 以不降序排序**。

hint:
### 样例 1 解释

数轴上 $1, 3$ 两点有虫洞。当飞船初始坐标为 $1$ 或 $3$ 时，可以直接进入虫洞，花费 $0s$；当初始坐标为 $2$ 时，有 $\frac 1 2$ 的概率向左一个单位，花费 $1s$ 进入虫洞，也有 $\frac 1 2$ 的概率向右一个单位，花费 $1s$ 进入虫洞，期望用时为 $\frac 1 2 \times (1 + 1) = 1$。

因此，三次询问的答案分别为 $0, 1, 0$。

### 数据规模与约定

本题共有 $10$ 个测试点，每个测试点 $10$ 分。

- 对于 $10\%$ 的数据，保证 $n = 1$。
- 对于 $20\%$ 的数据，保证对于任意一个虫洞，总存在另一个虫洞，使得他们之间的距离不超过 $2$。例如，样例中两个虫洞的距离为 $2$。
- 对于 $30\%$ 的数据，保证对于任意一个虫洞，总存在另一个虫洞，使得他们之间的距离不超过 $3$。
- 对于 $50\%$ 的数据，保证 $x_i,q \leq 100$。
- 对于 $70\%$ 的数据，保证 $x_i, q \leq 10^5$。
- 对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq q \leq 5 \times 10^6$，$1 \leq x_i, y_j \leq 10^9$，$y_j$ 不小于 $x_i$ 中的最小值，且 $y_j$ 不大于 $x_i$ 中的最大值，$y_j$ 按照不降序给出。

### 提示

- 如果你不知道什么是分数取模，可以参考如下的内容：

  对于一个形如 $\frac a b$ 的既约分数，其中 $b \lt 998244353$，它对 $998244353$ 取模后的值为 $a \times b^{998244351} \bmod {998244353}$ 。
- 为了方便用脚造数据，数据**并不**保证 $x_i$ 互不相同。
- 请注意大量数据读入对程序效率造成的影响。
- 本题的特殊输出方式只是为了避免输出过大造成程序超时，与本题解法无关。
- 请注意，$T$ **不是**数据组数。
- 本题共有两个附加文件，见附加文件中的 zhuo.zip。


title: 「EZEC-5」人赢

background:
> “我们在 小 Z 面前秀个恩爱吧。”\
>“好的。”

小 Z 发现他身边都是人赢，这使他非常自闭。

小 Z 又看着身边的潇，不禁陷入了沉思……

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

description:
潇有一个数组 $k$，下标为 $1$ 到 $n$ 。

潇定义 $f(x,y)=\begin{cases} \min(k_x,k_y) \times (x + y) &x \ne y \\ k_x\times x&x=y \end{cases}$ 。

潇想知道对于任意的 $1 \le x,y \le n$，$f(x,y)$ 的最大值是多少。但是她不会做，于是就问了善良的 小 Z，然而非常想在妹子面前表现的 小 Z 发现他也不会做，就只能够求助善良的你了。

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

第二行 $n$ 个整数 $k$，第 $i$ 个整数为 $k_i$。含义如上文。

outputFormat: 一行一个整数，表示对于任意的 $1 \le x,y \le n$，$f(x,y)$ 的最大值。

hint:
### 数据范围

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

- Subtask 1（20 points）：$1 \le n \le 5000$。

- Subtask 2（10 points）：保证所有 $k_{i}$ 都相等。

- Subtask 3（20 points）：$k_i \le 10^3$。

- Subtask 4（50 points）：无特殊性质。

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le k_{i} \le 10^9$。

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

本题加强版：[link](https://www.luogu.com.cn/problem/P7291)。


title: Galgame

background: 众所周知，as_lky 喜欢 Galgame。

description:
as_lky 搞到了很多 Galgame（真的很多！）。一款 Galgame 可以被描述为很多场景（Scene）的结合，它们形成了一棵 **以 1 为根** 的二叉树，每一个结点都是一个场景，一个结点的左儿子和右儿子分别对应在该场景选 A 选项和 B 选项能够到达的场景（可能会到达空场景，即游戏结束），我们称其为 A 场景和 B 场景。

as_lky 如下定义了两个不同的 Galgame 场景哪个更有趣（两款 Galgame 谁更为有趣也就取决于它们的初始场景谁更有趣）：

1. 如果这两个场景能够到达的场景总数（即通过任意选择能够到达的不同场景总数，包括该场景本身）不一样，那么能到达的场景数更多的那个更有趣；
2. 如果这两个场景的 A 场景不一样有趣，那么 A 场景更有趣的场景更有趣；
3. 否则这两个场景谁更有趣完全等价于他们 B 场景谁更有趣。

值得注意的是，空场景能到达的场景数被定义为 0。

![示例](https://cdn.luogu.com.cn/upload/image_hosting/4d2208qd.png)

例如，对于上图给出的例子（若无法正常查看请 `右键 -> 查看图像`），我们这样判定 1 和 7 这两个场景谁更有趣：

- 首先，1 和 7 能到达的场景数都是 6，因此我们首先尝试比较其 A 场景：2 和 8。
- 由于 2 和 8 能到达的场景数不同（分别是 3 和 2），则 2 场景比 8 场景更有趣；继而可以得到 1 场景比 7 场景更有趣。

as_lky 定义两个 Galgame 场景本质相同，当且仅当这两个场景都为空场景，或者它们的 A 场景本质相同且 B 场景本质相同。

as_lky 认为一款 Galgame 的有趣度是所有可能的、本质不同的、不及这款 Galgame 有趣的 Galgame 数量。现在 as_lky 给了你一款 Galgame，请告诉他这款 Galgame 的有趣度是多少。as_lky 觉得这个数字可能有些大，所以他想让你输出这个数字对 $998244353$ 取模的结果。

inputFormat:
第一行一个正整数 $n$，代表这款 Galgame 中共有多少场景。

接下来 $n$ 行，每行两个非负整数 $a_i$ 和 $b_i$，分别代表该场景的 A 场景和 B 场景，0 代表空场景。保证数据合法。

outputFormat: 一行一个非负整数，代表有趣度对 $998244353$ 取模的结果。

hint:
### 样例解释

样例一：下图分别给出了 as_lky 给你的 Galgame（左）和所有四种没有该 Galgame 有趣的 Galgame（右）：（若无法正常查看请 `右键 -> 查看图像`）

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

### 测试点约束

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

对于全部数据，有 $1\le n\le 10^6$，$0\le a_i,b_i\le n$。

每个子任务的具体限制见下表：

| 子任务编号 | 分值 | $n\le$ | 特殊性质 |
|:-:|:-:|:-:|:-:|
| 1 | 10 | $10$ | $\times$ |
| 2 | 20 | $5000$ | $\times$ |
| 3 | 30 | $10^6$ | $\surd$ |
| 4 | 40 | $10^6$ | $\times$ |

特殊性质：保证数据均匀随机生成，即 $n$ 给定时，若所有场景数为 $n$ 的本质不同 Galgame 共有 $S$ 种，则每种本质不同的 Galgame 出现概率均为 $\frac{1}{S}$。

**本题读入量较大，请使用较快的读入方式。**


title: [JSOI2010] 蔬菜庆典

description:
JYY 在火星上找到一片埋有宝藏的岛，并且带走了一些宝藏。之后 JYY 被火星人发现偷宝藏，抓了起来。火星人打算吃掉 JYY，除非 JYY 能在火星年度蔬菜庆典的游戏中赢得足够多的火星币来支付他带走宝藏的费用。

游戏在蔬菜广场上进行。首先放进广场的是一个巨大的转基因南瓜，接着各种其他巨大的蔬菜被陆续拖进广场，连同大南瓜一共 $n$ 个，第 $i$ 个放入的蔬菜会用一根绳子和先前放入的某个蔬菜连接起来。按照火星人的说法，蔬菜 $i$ 是蔬菜 $p_i$ 的 Dlihc，蔬菜 $p_i$ 是蔬菜 $i$ 的 Tnerap。JYY 立即看出，一开始的大南瓜没有 Tnerap，后来的每个蔬菜都恰好有一个 Tnerap；每个蔬菜可能有一个或多个的 Dlihc，也可能没有。$n$ 个蔬菜全部在广场上安置好后，火星人在每个蔬菜上贴一张纸条，蔬菜 $i$ 的纸条上写着一个整数 $v_i$，表示这个蔬菜的价钱。

游戏一个接一个地进行着。在整个晚会将要结束时，JYY 终于等到了适合自己的那一个。（你不能指望有恐高症的 JYY 会在蔬菜间玩走钢丝，尽管那样能有丰厚的报酬）。游戏规则是：游戏者（也就是 JYY）每次可以选择任意一个既有 Dlihc 又有 Tnerap 的蔬菜 $i$，将它的价钱 $v_i$ 改成 $v_p+v_c-v_i$，其中 $p$ 代表蔬菜 $i$ 的 Tnerap 的编号，$c$ 代表蔬菜 $i$ 的任意一个 Dlihc 的编号。火星人给的时间比较宽裕，足够 JYY 进行任意多次操作。当 JYY 决定不再操作时，游戏结束。之后所有巨型蔬菜将被火星政府按蔬菜上的标价收购。买菜所得的钱归 JYY 所有，用以支付他的债务。

JYY 想知道，他最多能把这些蔬菜卖出多少钱，或者他能通过一系列操作使得蔬菜的总价无限制地增大。请你帮助 JYY 解决这个问题。

inputFormat:
输入文件有多组数据，每组数据的格式为：

第一行一个整数 $n$ 表示广场上蔬菜的个数。

接下来 $n$ 行，每行两个整数 $p_i,v_i$，第 $i$ 行中的整数代表蔬菜 $i$ 的 Tnerap 的编号和蔬菜 $i$ 的价格。

当 $n=0$ 时表示输入结束。

outputFormat: 对于每组数据，输出一行。若蔬菜的总价能无限制增大，输出 `+inf`。否则输出一个整数，表示所有蔬菜的最大总价。

hint:
### 样例解释 1

共有两组数据。

对于第一组数据，我们只能对蔬菜 $3$ 进行操作，它的值只能是 $1$ 或 $4$，所以答案为 $3+2+4+2+2=13$。

对于第二组数据，可以按照如下方法使得所有蔬菜的价钱无限制地增大：

$$\begin{matrix}1\to 3+3-1=5\\5\to 3+2-5=0\\0\to 3+3-0=6\\6\to 3+2-6=-1\\-1\to 3+3-(-1)=7\\\cdots\end{matrix}$$

### 数据范围

对于 $100\%$ 的数据，$n\leq 2\times 10^5,-10^7\leq v_i\leq 10^7$。


title: Ame 和 Gura 的奇妙探险

background:
#### 鉴于洛谷的 SPJ 编译可能依赖于用户选择的编译器版本，且 SPJ 使用了 C++11，请 C++ 选手使用 C++11 或以上进行提交。

~~Lewdson~~ Watson Amelia 和 Gawr Gura 在玩 Mivicraft。

Gura 想将地狱里的交通升级为冰船隧道，但在此之前她先得有一把精准采集的镐子。尝试了一遍又一遍，但终究未能成功的她只好可怜兮兮地找到 Ame。Ame 立刻说道：“So easy! I'll get it in my first try.”

（第一次之后）“Well let's try it again!”

（第二次之后）“Hmmm maybe something's getting wrong today?”

（第三次之后）“I'll give you a ground pound you silly enchanting table!”

（第四次之后）“.. Damn.”

于是 Ame 决定借助一些 技 巧 来拿到精准采集的镐子。她通过查询资料得知 Mivicraft 产生随机数使用了梅森旋转算法（Mersenne Twister，MT19937）。Mivicraft 会通过一个 MT19937 引擎产生一系列的随机数来生成世界的区块。

description:
Ame 知道，只要她能够找到初始化 MT19937 引擎时使用的种子，她就能够推断出自己如何才能获得一把精准采集的镐子。于是她游历世界，并通过聪明的侦探头脑算出了这个 MT19937 引擎 **刚被初始化后** 生成的 $N$ 个随机数（注：这里的 $N$ 是 MT19937 引擎中的一个参数）。现在她把这 $N$ 个随机数给了你，希望你能够推断出初始化 MT19937 引擎时使用的种子（$0\le\text{种子}<2^{32}$）。值得注意的是，Mivicraft 使用的并非标准的 MT19937 引擎，其中的一些参数与论文相比有所改变，Ame 把它们附加到了输入中。请你帮帮 Ame 吧！

好心的 Mivik 为你准备了一份简单易懂的 MT19937 实现，请在附件中查看。

inputFormat:
第一行 10 个非负整数，分别对应 MT19937 中的 10 个参数：$N$、$M$、$A$、$U$、$S$、$B$、$T$、$C$、$L$ 和 $F$。

接下来 $N$ 行，每行一个非负整数，依次表示 MT19937 引擎刚被初始化后生成的 $N$ 个随机数。

outputFormat: 一行一个非负整数，代表 MT19937 引擎初始化时使用的种子。数据保证有解，如果有多个解，你只需要输出任意一个即可。

samples:
见 sample/1.in
见 sample/1.out

samples:
见 sample/2.in
见 sample/2.out

hint:
### 样例解释 #1

十个参数全部使用标准的 MT19937 参数，种子为 `233333`。也就是说，你可以通过下面的程序产生同样的随机数序列：

```cpp
#include <iostream>
#include <random>

std::mt19937 engine(233333);
int main() {
	for (int i = 0; i < 624; ++i)
		std::cout << engine() << std::endl;
	return 0;
}
```

### 测试点约束

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

对于全部数据，有 $10\le M<N\le 2\times 10^5$，$0\le A,B,C<2^{32}$，$1\le U,S,T,L\le 31$，$1\le F<2^{32}$，保证 $F$ 是奇数。

每个子任务的具体限制见下表：

| 子任务编号 | 分值 | 特殊限制 |
|:-:|:-:|:-:|
| 1 | 20 | 种子小于等于 $1000$ |
| 2 | 30 | $U=S=T=L=16$，$A=B=C=0$ |
| 3 | 50 | 无 |

**注：下发文件使用 UTF-8 编码，请使用可识别该编码的编辑器打开。**

**附件下载备用链接：[百度网盘](https://pan.baidu.com/s/1ZJQfZK93Qw2lYrDHLQJh2Q) 提取码：jf9e**


title: 「RdOI R1」一次函数(function)

background:
**请使用较快的读入方式。**

众所周知，一次函数的解析式如下：

$$y=kx+b$$

或者，我们可以表示为：

$$f(x)=kx+b$$

这个就是一次函数的解析式，下文中用到的解析式均用 $y=kx+b$ 表示。

- 如果不知道什么是一次函数的[戳我](https://baike.baidu.com/item/%E4%B8%80%E6%AC%A1%E5%87%BD%E6%95%B0)。
- 如果不知道什么是函数图像的[戳我](https://baike.baidu.com/item/%E5%87%BD%E6%95%B0%E5%9B%BE%E5%83%8F/514135)。

description:
设 $S_k$ 表示直线 $l_{k1}:y=kx+k-1$，$l_{k2}:y=(k+1)x+k$ 与 $x$ 轴围成的三角形的面积，求：

$$\sum_{i=1}^nS_i$$

本题中，共有 $t$ 次询问，每次询问给出 $n_i$，求上式在 $n=n_i$ 时的取值。

若 $n<1$，该和式的值视作 $0$。

inputFormat:
一共 $t+1$ 行。

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

接下来 $t$ 行，每行一个整数 $n_i$，含义如题面所述。

outputFormat:
一共 $t$ 行。

每一行，每行一个数表示你所求得的答案。

结果可能是分数，请**约分**至最简分数，分数请用 `xxx/xxx` 表示，如 $\dfrac{1}{2}$ 表示为 `1/2`，$\dfrac{2}{4}$ 表示为 `1/2`，请注意约分。

注：若答案为 $0$，请输出 `0`。

hint:
【样例解释】

当 $n=0$ 时，根据题意，输出 $0$。

当 $n=1$ 时，$S_1$ 就是 $y=x$、$y=2x+1$ 与 $x$ 轴所夹面积，为 $\dfrac{1}{4}$。

---

【数据范围】

- 对于 $5\%$ 的数据，$t \le 100,n=0$。
- 对于另外 $20\%$ 的数据，$t \le 100,n \le 2020$。
- 对于另外 $20\%$ 的数据，$t \le 5 \times 10^4,n \le 5 \times 10^3$。
- 对于 $100\%$ 的数据，$1 \le t \le 2 \times 10^6,0 \le n \le 2 \times 10^6$。

---

【说明/提示】

- 建议画图思考。
- **请注意输出答案的时候约分**。
- **请使用较快的读入方式**。

---

【文件读入读出】**（模拟，提交代码时不需使用）**

- 文件名：`function.cpp`
- 读入文件名：`function.in`
- 读出文件名：`function.out`


title: 「EZEC-6」象棋

background:
> 万籁停吹奏
$\newline$支颐听秋水问蜉蝣
$\newline$既玄冥不可量北斗
$\newline$却何信相思最温柔

description:
象棋将会由两个玩家进行游玩，其中红方为先手，黑方为后手。象棋里有很多种棋子，PF 对其中的“炮”情有独钟，炮的操作为：如果任意一方的某个炮和对方的某个炮之间的位置上**有且仅有一个炮**，那么这一方可以将对方的炮移出棋盘，并将他的炮移到对方的炮的位置。

PF 厌倦了传统象棋的玩法，因此他拿出了一张 $1$ 行 $n$ 列的棋盘。棋盘上的每个位置都有且仅有一个炮，每个炮都隶属于红方或黑方。对于每个回合，操作方可以进行一次操作，也可以不进行操作，然后将操作权交给对手。若双方均同意结束或者无棋可动，游戏结束。

游戏将进行 $T$ 局。每一局 PF 都是红方。定义游戏的胜利条件为一方的剩余的炮的数量大于对方。他想知道，若双方均使用最佳策略，他是否有必胜策略。

inputFormat:
第一行一个整数 $T$，表示测试数据的数量。

对于每组数据，第一行一个整数 $n$，表示棋盘大小。

接下来一行一个字符串，其中第 $i$ 个整数 $a_i$ 表示第 $i$ 个棋子的种类，其中 $1$ 表示红方的炮， $0$ 表示黑方的炮。

outputFormat: 输出共 $T$ 行，若第 $i$ 组有必胜策略，输出 `WIN`，若为平局输出 `TIE`，否则输出 `LOSE`。


title: [传智杯 #3 练习赛] 直角三角形

description:
一个直角三角形的两个直角边是 $a,b(a\le b)$，其斜边是 $c$，且 $a,b,c$ 都是正整数。

现在我们已经知道了斜边长度 $c$，请问这个直角三角形的两个直角边的长度是什么？

inputFormat: 输入一个整数 $c(1\le c \le 1.41 \times 10^4)$。

outputFormat: 输出两个整数 $a,b$ 表示答案。保证有整数解。如果有多个可能的答案，请确保 $a$ 尽可能的小。


title: [传智杯 #3 练习赛] 单位转换

description:
我们知道计算机的大小单位有 B, KB, MB 等，现在请你编写一个计算器进行大小单位换算。

提示，$1$ GB = $2^{10}$ MB = $2^{20}$ KB = $2^{30}$ B。

inputFormat:
输入一个字符串，由一个 0 到 1023 之间的整数，一个单位名称（大写字母），一个等于号和问号，以及第二个单位名称。

单位只有可能是 `GB`,`MB`,`KB`,`B` 之间的一个。

outputFormat: 输出一个数字，精确到小数点后 6 位。


title: [传智杯 #3 练习赛] 评委打分

description:
小 A 参加一个综艺节目。一共有 $n(3 \le n \le 10^6)$ 名评委参与打分（分数范围是 0 到 100 的整数），每个评委依次亮出自己的得分。

为了节目效果，要求从第三个评委开始，每当第 $i$ 个评委给出打分后，立刻计算出出这个选手在前 $i$ 名评委的打分中，去掉一个最高分和一个最低分，剩下 $i-2$ 个评委的平均分，保留 $2$ 位小数。

inputFormat:
第一行输入一个整数 $n$，表示评委人数。

第二行输出 $n$ 个整数，表示各个评委的打分。

outputFormat: 输出共 $n-2$ 行，每行表示对应的答案。