title: [ICPC2020 WF] QC QC

background: ICPC2020 WF H

description:
Innovative Computable Quality Control (ICQC) has developed a ground-breaking
new machine for performing, well, quality control. Thanks to
its novel Deep Intelligence technology, an ICQC quality control (QC)
machine can automatically, with $100\%$ accuracy, detect manufacturing
errors in any machine in existence, whether it is a coffee machine, an
intergalactic space ship, or a quantum computer.

ICQC is now setting up its factory for producing these QC
machines. Like any other manufacturing process, some fraction of
the produced machines will suffer from malfunctions and these need to
be found and discarded. Fortunately, ICQC has just the product
for detecting malfunctioning machines!

Obviously, ICQC should not simply use a QC machine on itself, since
a malfunctioning machine might incorrectly classify itself as working
correctly. Instead, ICQC will take each batch of $n$ machines
produced during a day and have them test each other overnight.
In particular, during every hour of the night, each of the $n$ QC
machines can run a check on one of the other QC machines, and
simultaneously be checked by one other QC machine.

If the machine running the check is correct, it will correctly report
whether the tested machine is correct or malfunctioning, but if the
machine running the check is malfunctioning, it may report either result.
If a machine A is used to test a machine B multiple times it will return the same result every time, even if machine A is malfunctioning.
The exact testing schedule does not have to be fixed in advance,
so the choice of which machines should check which other machines during
the second hour of the night may be based on the result of the tests
from the first hour, and so on.

ICQC are $100\%$ confident that strictly more than a half of the $n$ QC
machines in each batch are working correctly, but the night is only $12$
hours long, so there is only time to do a small number of test rounds.
Can you help ICQC determine which QC machines are malfunctioning?

For example, consider Sample Interaction 1 below. After the fourth hour,
every machine has tested every other machine. For machine $1$,
only one other machine claimed that it was malfunctioning, and if it
was truly malfunctioning then at least $3$ of the other machines would
claim this. For machine $4$, only one other machine claims that it
is working, which implies that machine $2$ must be malfunctioning since
more than half of the machines are supposed to be working. Note that
even though machine $4$ is malfunctioning, it still happened to produce
the correct responses in these specific test rounds.

inputFormat:
## Interaction

The first line of input contains a single integer $b$ ($1 \le b \le 500$),
the number of batches to follow. Each batch is independent.
You should process each batch
interactively, which means the input you receive
will depend on the previous output of your program.

The first line of input for each batch contains a single integer $n$
($1 \le n \le 100$), the number of QC machines in the batch.
The interaction then proceeds in rounds. In each round, your program can
schedule tests for the next hour, by writing a line of
the form
"$\texttt{test}$ $\ x_1\ x_2\ \ldots\ x_n$"
indicating that each machine $i$ should run a test on machine $x_i$.
If $x_i=0$, then machine $i$ is idle in that round and performs no test.
All positive numbers in the sequence must be distinct.

After writing this line, there will be a result to read from the
input. The result is one line containing a string of length
$n$, having a '$\texttt{1}$' in position $i$ if machine $i$ says that machine $x_i$
is working correctly, '$\texttt{0}$' if machine $i$ says that machine $x_i$ is
malfunctioning, and '$\texttt{-}$' (dash) if machine $i$ was idle in the round.

When your program has determined which machines are malfunctioning,
but no later than after $12$ rounds of tests,
it must write a line of the form
"$\texttt{answer}$ $S$"
where $S$ is a binary string of length $n$, having a '$\texttt{1}$' in position $i$
if machine $i$ is working correctly, and a '$\texttt{0}$' if it is malfunctioning.

After writing the answer line, your program should start processing
the next batch by reading its number $n$. When all $b$ batches have been
processed, the interaction ends and your program should exit.

*Notes on interactive judging:*

- *The evaluation is non-adversarial, meaning that the result of each
machine testing each other machine is chosen in advance rather than in
response to your queries.*
- *Do not forget to flush output buffers after writing. See the Addendum to Judging Notes for details.*
- *You are provided with a command-line tool for local testing, together with input files
corresponding to the sample interactions.
The tool has comments at the top to explain its use.*

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

创新的可计算质量控制（ICQC）开发了一种开创性的新机器，用于执行良好的质量控制。得益于其新颖的深度智能技术，ICQC 质量控制（QC）机器能够以 $100\%$ 的准确度自动检测现有任何机器的制造错误，无论是咖啡机、星际飞船还是量子计算机。

ICQC 目前正在建立工厂生产这些 QC 机器。像任何其他制造过程一样，生产的机器中有一部分会出现故障，需要找到并丢弃。幸运的是，ICQC 只有检测故障机器的产品！

显然，ICQC 不应该简单地在自己身上使用 QC 机器，因为出现故障的机器可能会错误地将自己归类为正常工作。相反，ICQC 将在一天内生产每批 $n$ 机器，并让它们在一夜之间相互测试。特别是，在夜间的每一个小时，每个 $n$ QC机器都可以在另一台 QC 机器上运行检查，同时由另一台 QC 机器进行检查。

如果运行检查的机器是正确的，它将正确地报告测试机器是正确的还是故障的，但如果运行检查的机器是故障的，它可能会报告任何一个结果。如果使用机器 A 多次测试机器B，即使机器 A 出现故障，每次都会返回相同的结果。准确的测试时间表不必事先确定，因此，在夜间第二个小时，哪些机器应该检查哪些其他机器，可以根据第一个小时的测试结果来选择，以此类推。

ICQC $100\%$ 确信，严格来说，每批 $n$ QC 机器中有一半以上工作正常，但夜间只有$12$ 小时，因此只有时间进行少量测试。您能帮助 ICQC 确定哪些 QC 机器出现故障吗？

例如，考虑下面的样本交互作用 $1$。在第四个小时之后，每台机器都测试了其他每台机器。对于机器 $1$，只有另一台机器声称它有故障，如果它真的有故障，那么其他机器中至少有 $3$ 台会声称这一点。对于机器$4$，只有另一台机器声称它正在工作，这意味着机器 $2$ 一定有故障，因为超过一半的机器应该在工作。请注意，尽管机器 $4$ 出现故障，但在这些特定的测试回合中仍碰巧产生了正确的响应。

**【输入格式】**

第一行输入包含一个整数 $b$（$1≤ b≤500$），要遵循的批次数。每批都是独立的。您应该以交互方式处理每个批，这意味着您收到的输入将取决于您的程序之前的输出。

每个批次的第一行输入包含一个整数 $n$ （$1≤n≤100$），批次中 QC 机器的数量。然后，交互循环进行。在每一轮中，你的程序都可以通过写一行表格来安排下一个小时的测试 “ $\texttt{test}$ $x_1$ $x_2$ $x_n$”指示每台机器 $i$ 应在机器 $x_i$ 上运行测试。如果 $x_i$ 为 $0$，然后，机器 $i$ 在该轮中处于空闲状态，不执行任何测试。序列中的所有正数必须是不同的。

写下这一行后，将有一个从输入中读取的结果。结果是一行包含长度为 $n$ 的字符串，如果机器 $i$ 表示机器 $x_i$，则在位置 $i$ 处有“$\texttt{1}$”，$x_i$ 工作正常，“$\texttt{0}$” 如果机器 $i$ 显示机器 $x_i$ 出现故障，如果机器 $i$ 在循环中处于空闲状态，则为“$\texttt{-}$”（破折号）。

当您的程序确定哪些机器出现故障时，但不迟于 $12$ 轮测试之后，它必须以“$\texttt{answer}$ $S$”的形式写一行，其中 $S$ 是长度为 $n$ 的二进制字符串，如果机器 $i$ 正常工作，则在位置 $i$ 处有“$\texttt{1}$”，如果机器 $i$ 出现故障，则在位置 $i$ 处有“$\texttt{0}$”。

在写下答案行之后，你的程序应该通过读取下一批的编号 $n$ 来开始处理下一批。当所有 $b$ 批处理完成后，交互结束，程序应该退出。

关于互动评判的说明：
 - 评估是非对抗性的，这意味着每台机器测试另一台机器的结果是提前选择的，而不是响应您的查询。
- 写入后不要忘记刷新输出缓冲区。有关详细信息，请参见《评委须知》附录。
- 我们为您提供了一个用于本地测试的命令行工具，以及与示例交互相对应的输入文件。该工具顶部有注释解释其用途。


title: [ICPC2020 WF] Quests

type: P

background: ICPC2020 WF I

description:
To relax before competing in the ICPC World Finals, you have decided to play a
computer game called *Quests*. You have played it a
number of times already, and now you want to achieve a perfect
playthrough---to prepare for your perfect playthrough of the finals!

In the game, you have to complete a number
of quests, and you earn experience points (XPs) for completing each one. The
total number of XPs you have earned at any time determines your current level. You
reach a new level for every $v$ XPs that you earn. Formally, your level at
any time is the largest integer $L$ such that you have at least $L \cdot v$
XPs.

Each quest is assigned a number $x$ of XPs and a target
difficulty level $d$. If you complete the quest when your level is at least
$d$, you earn $x$ XPs. However, if you complete the quest when your level is
less than $d$, you will earn $c \cdot x$ XPs. The constant  $c$ is an XP multiplier
that results in a bonus for completing a
quest when you are at a lower level than the recommended level $d$.

You know all the $n$ quests and their respective $x$ and $d$ numbers by heart
(and you know the numbers $v$ and $c$ as well---you have played this game a lot).
You are also skilled enough to
complete any quest, regardless of its target difficulty level and your level.
You want to complete all the quests in an order that will allow you
to earn the largest possible number of XPs.

For example in the sample input, the maximum XPs you can earn is 43, which
is done as follows. First complete the second quest (you earn $4$ XPs,
because you are at level $0$, and you completed a quest with target difficulty
level $2$). Then complete the first quest (you earn $30$ XPs, because you are
still at level $0$, and the target difficulty level is $1$). With $34$ XPs, you
are now level $3$. Finally, complete the third quest (for which you earn $9$
XPs, without the multiplier, since you are already at level $3$).

inputFormat:
The first line of input contains three integers $n$, $v$, and $c$, where
$n$ $(1 \leq n \leq 2\,000)$ is the number of quests in the game, $v$
$(1 \leq v \leq 2\,000)$ is the number of XPs required to reach each level,
and $c$ $(2 \leq c \leq 2\,000)$ is the XP multiplier for completing a quest
before reaching its target difficulty level.

Following that are $n$ lines, each of which contains two integers $x$ and $d$
describing one quest, where $x$ $(1 \leq x \leq 2\,000)$ is the number of XPs
you earn for completing that quest if you are at or above its target difficulty
level and $d$ $(1 \leq d_i \leq 10^6)$ is the target difficulty level for that
quest.

outputFormat:
Output the maximum possible number of XPs you could earn by finishing all the
quests.

translation:
为了在 ICPC 之前放松，小 A 决定玩一个名叫 _Quests_ 的游戏。你之前已经玩了很多次，因此这次你决定打一盘最完美的游戏——为你在决赛中的完美表现作准备！

游戏中你需要完成若干个任务，完成每一个任务都可以积攒经验值。你在某一时刻积攒的在总经验值决定了你的游戏等级，具体地，每次达到一个新的等级需要 $v$ 点经验值，也就是说，假设你在某一时刻积攒的总经验值为 $X$，那么你在该时刻的等级就是最大的满足 $L\cdot v\leqslant X$ 的整数 $L$。

游戏中的第 $i$ 个任务的设定经验值为 $x_i$，参考难度为 $d_i$。如果你在等级 $\geqslant d_i$ 的情况下完成了第 $i$ 个任务，那么你将获得 $x_i$ 点经验值。然而，如果你在等级 $<d_i$ 的情况下完成了第 $i$ 个任务，那么你将获得 $c\cdot x_i$ 点经验值。

现在，你已经知道了 $v,c$ 的值以及所有任务的设定经验值 $x_i$ 和参考难度 $d_i$，你想知道在按照某一特定顺序依次完成任务的情况下，能够攒到的总经验值最大是多少。

数据范围：

- $1\leqslant n,v\leqslant 2000$，$2\leqslant c\leqslant 2000$。
- $1\leqslant x_i\leqslant 2000$，$1\leqslant d\leqslant 10^6$。

Translated by Eason_AC


title: [ICPC2020 WF] ’S No Problem

background: ICPC2020 WF J

description:
The Yllihc Engineering and Technological Institute (YETI),
located in upper northern Snowblovia, has two problems: snow
and money. Specifically, they have too much of the former and not
enough of the latter. Every winter (and fall and spring for that matter)
the campus is covered with blankets of snow. The maintenance staff
must clear all the sidewalks connecting the campus buildings, but they
have only two snow blowers and have been told in no uncertain
terms that they cannot expect to obtain any more in the near future.

To preserve the longevity of these two precious machines,
the staff has decided on the following snow removal procedure.
Each machine is assigned a fixed route connecting two of the
buildings on campus. Whenever snow must be removed, each snow blower
is taken from the building at one end of its route and used to clear snow,
ending up in the building at the other end of its route, where it is
stored until the next snowfall.
The reverse movement will occur during the next snow removal event---each
machine will trace its assigned route in the opposite direction.
This process cycles throughout the eleven-month snow season.
Note that a route might involve doubling back over sidewalks that
have already been cleared. Also, it is
possible that the same building might be an endpoint for both
snow blower routes.

The campus sidewalks are laid out in the form of a tree.
To run the machines as little as possible, the staff wants
to minimize the total distance
that the snow blowers must travel as they are guided along their routes.
Figure J.1 shows an optimal
solution for the sidewalk layout of the first sample input.

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

The YETI maintenance crew would ask the Computer Science Department
at YETI to figure this out, but they were wiped out in the Great
Blizzard of '$06$, so they have come to you for help.

inputFormat:
The first line of input contains an integer $n$ ($4\leq n\leq 100\,000$),
the number of buildings on the YETI campus. Buildings are numbered from $1$
to $n$.
Each of the remaining $n-1$ lines contains three integers
$a$, $b$, and $d$
indicating that a two-way sidewalk exists between buildings $a$ and $b$
($1 \leq a, b \leq n$; $a\ne b$) of length $d$ ($1\leq d\leq 500$).

outputFormat:
Output the minimum total distance the two machines must travel in
any snow removal event.

translation:
## 题目描述
位于斯诺布洛维亚北部的 某·工程技术学院 (YETI) 面临两个问题：雪和金钱。具体来说，他们有太多的前者而没有足够的后者。每年冬天（以及秋天和春天），校园都覆盖着雪毯。维护人员必须清理连接校园建筑的所有人行道，但他们只有两台吹雪机，并且已经明确告知他们在不久的将来不能再获得更多。

为了保持这两台珍贵机器的使用寿命，工作人员决定采用以下除雪程序。每台机器都被分配了一条连接校园内两座建筑物的固定路线。每当必须除雪时，每台吹雪机都会从其路线一端的建筑物中取出并用于清除积雪，最终进入其路线另一端的建筑物中，并存放在那里直到下一次降雪。在下一次除雪活动期间将发生反向运动——每台机器将沿相反方向追踪其分配的路线。这个过程在整个 1 个月的雪季循环。请注意，路线可能涉及翻过已清理的人行道。此外，同一建筑物可能是两条吹雪机路线的终点。

校园人行道以树的形式布置。为了尽可能少地运行机器，工作人员希望尽量减少吹雪机在沿路线引导时必须行驶的总距离。图 J.1 显示了第一个样本输入的人行道布局的最佳解决方案。

YETI 维护人员会要求 YETI 的计算机科学系解决这个问题，但他们在 06 年的大暴雪中失败了，所以他们来找你帮忙。
## 输入格式

输入的第一行包含一个整数 n(4≤n≤100000)，即 YETI 校园内的建筑物数量。 建筑物的编号从 1 到 n。其余n−1 行中的每一行包含三个整数 a、b和d，表示建筑物 a和 b之间存在双向人行道 (1≤a,b≤n) 长度为 d(1≤d≤500)。
## 输出格式
输出两台机器在任何除雪事件中必须行驶的最小总距离。


title: [ICPC2020 WF] Space Walls

background: ICPC2020 WF K

description:
Place-Y Technology Corp. plans to launch a new space station soon. The company
CEO is known for being obsessed with perfection. For example, he insists that all
the outer surfaces of the space station are regularly polished and cleaned of
what he calls ``space debris,'' mainly for the station to appear good in photos.
The engineering team tried but failed to convince the CEO that this was not needed. So instead they
developed an innovative technology to maintain the surfaces while minimizing human
operations outside the station. The maintenance is performed by several
small robots moving over the space station surface, just like robotic
vacuum cleaners. Before their first flight, Place-Y needs to assess the risks of
collision during the operation of the robots. And this is exactly where you step
in.

For the purposes of this problem, we model the space station as a collection of
axis-aligned unit cubes (not necessarily connected). Each robot starts at time $t=0$ in the center of an exposed face
of one of the station's unit cubes (that is, a face which is not shared by a second station
cube). The robot is oriented in one of the four directions parallel to an edge of the cube face.
Every time unit, the robot moves straight ahead to another cube face, possibly
pivoting $90$ degrees across the space station edges so that it always maintains
contact with the station.  Note that if two cubes share an edge, the robot cannot
slip between them (there is no gap).

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

Given the layout of the station and starting
positions of all the cleaning robots, determine the time of the earliest collision (if any).  The time a collision occurs is either the time unit when two or more robots are on the interior of the same cube
face or the time unit when two robots attempt to swap locations (see Sample Input 3 for the
latter case).

inputFormat:
The first line of input contains two integers $n$ and $k$, where $n$
($1 \le n \le 100$) is the number of regions describing the space station shape,
and $k$ ($0 \le k \le 100$) is the number of robots on the surface.

Each of the following $n$ lines contains six integer coordinates $x_1$, $y_1$, $z_1$,
$x_2$, $y_2$, and $z_2$ ($0 \le x_1 < x_2 \le 10^6$, $0 \le y_1 < y_2 \le 10^6$,
$0 \le z_1 < z_2 \le 10^6$) describing one region and denoting that all the points
$x,y,z$ satisfying $x_1 \le x \le x_2$, $y_1 \le y \le y_2$,
$z_1 \le z \le z_2$ are part of the space station. Note that some
unit cubes may be included in more than one region.

Then follow $k$ lines, each describing the starting position of one robot.  Such
a line contains three coordinates $x$, $y$, and $z$, and two directions $\vec{f}$
and $\vec{d}$. The coordinates specify that the robot starts at a face of the
unit cube $(x,y,z) - (x+1,y+1,z+1)$. The particular face is determined by
$\vec{f}$ and the initial direction of movement is determined by $\vec{d}$.
Both $\vec{f}$ and $\vec{d}$ are specified by one of the six strings $\tt x+$, $\tt x-$, $\tt y+$,
$\tt y-$, $\tt z+$, or $\tt z-$, where $\tt x+$ designates the positive direction
of the x-axis $(1,0,0)$, and so on. The axis letter in $\vec{f}$ will be different
from the axis letter in $\vec{d}$. It is guaranteed that the starting cube
belongs to the space station and the given face is an exposed face.

outputFormat:
Output the time of the first collision. If there will never be a collision,
output $\tt ok$.

translation:
### 输入格式

每个机器人每次启动一开始t=0
每次机器人到另一个面，可能会旋转90°两个立方体共享一条边时，机器人无法在之间走动。

第一行输入n,k,n是空间站形状的区域数,k是机器人的数量。

接下来n行6个数据分别是：($0 \le x_1 < x_2 \le 10^6$, $0 \le y_1 < y_2 \le 10^6$,
$0 \le z_1 < z_2 \le 10^6$)

是一个区域中的所有点。满足$x_1 \le x \le x_2$, $y_1 \le y \le y_2$,
$z_1 \le z \le z_2$
请注意，一些立方体可能包含在多个区域中。

接下来k行，每一行代表机器人的位置。有x,y,z以及两个方向f,d,指定面由f确定,初始移动方向由d确定.六种操作x+,x-,y+,y-,z+,z-.
x+表示（1,0,0）的方向，依此类推。f不等于d.

保证起始立方体属于空间站，并且给定的初始面是外面。

### 输出格式
输出第一次碰撞的时间。如果永远不会发生冲突，则输出ok


title: [ICPC2020 WF] Sweep Stakes

background: ICPC2020 WF L

description:
You may have already won! In fact, you did already win! You won your very own
island, in the deepest reaches of the unexplored ocean! Well, mostly unexplored.
As it happens, there was a small military base there before you, and when they
packed up and flew out they left behind an assortment of scraps, munitions,
tunnels, $\ldots$ and unexploded defensive ordnance. That's right: You now possess
your very own minefield.

The minefield consists of an $m\times n$ grid, with any square of the grid holding
0 or 1 mines. Fortunately, you were able to recover the engineers' plans from when
they deployed the mines. Unfortunately, the exact locations of the mines were never
written down: the engineers had a preselected independent probability of deploying
a mine in each square. However, you do know how many mines were placed in total.

You would like to estimate how safe various parts of your island are. Write a
program to compute the probability of mine counts over various subsets of the
minefield.

inputFormat:
The first line of input contains four integers $m$, $n$, $t$, and $q$, where $m$
and $n$ ($1 \leq m,n \leq 500$) are the dimensions of the minefield, $t$
($0 \leq t \leq mn$) is the total number of mines, and $q$ ($0 \leq q \leq 500$)
is the number of queries. The second line contains $m$ real numbers
$p_1, p_2, \ldots, p_m$ ($0 \leq p_i \leq 0.1$ for all $i$, with at most six digits
after the decimal point specified), and the third line
contains $n$ real numbers $q_1, q_2, \ldots, q_n$ ($0 \leq q_j \leq 0.1$ for all
$j$, with at most six digits after the decimal point specified).
The preselected probability of the engineers placing a mine on square $(i, j)$
is $p_i + q_j$. All choices of whether to place a mine on a given square were made
independently, and the value of $t$ is chosen so that the probability of deploying
exactly $t$ mines is at least $10^{-5}$.

Each of the remaining $q$ lines describes a single query. Each of those lines
begins with an integer $s$ ($0 \leq s \leq 500$), followed by $s$ pairs of integers
$i$ and $j$ ($1 \leq i \leq m$, $1 \leq j \leq n$), which are the coordinates of $s$
distinct squares in the grid.

outputFormat:
For each query with $s$ squares, output $s+1$ real numbers, which are the
probabilities of the $s$ given squares containing $0, 1, \ldots, s$ mines. Your
answer should have an absolute error of at most $10^{-6}$.

translation:
你赢得了自己的岛屿，在未开发海洋的最深处！那里有一个小型军事基地，当他们收拾行李飞走时，留下了各种碎片、弹药、隧道、炸弹……以及未爆炸的防御弹药。你现在拥有了自己的雷区。

雷场由 $m\times n$ 的网格组成，网格的任何正方形都有 0 或 1 枚地雷。幸运的是，你能够从工程师部署地雷时恢复他们的计划。不幸的是，地雷的确切位置从未被写下来：工程师们在每个方格部署地雷的预先选择的独立概率。然而，你知道总共埋设了多少枚地雷。

你想估计一下你所在岛屿的各个部分有多安全。请编写一个程序来计算雷区各子集上地雷计数的概率。误差需小于 $10^{-6}$。


title: [ICPC2020 WF] Trailing Digits

background: ICPC2020 WF M

description:
A large shipment of doodads has just arrived, and each doodad has a suggested retail price of $b$ cents. You've noticed that consumers are much more likely to purchase goods when most of the trailing digits are the same. For example, items are more likely to be priced at $99$ cents rather than $57$ cents. So to make your goods more appealing, you've decided to sell your goods in bundles. To make a bundle, you choose a positive integer $k$, and sell $k$ doodads for $k \times b$ cents. With an appropriate choice of $k$ you can have a more pleasing price. For example, selling $57$-cent doodads in bundles of size $7$ means that each bundle sells for $399$ cents, which has two trailing $9$s, rather than no trailing $9$s of $57$. This idea of trailing $9$s can be generalized to any other trailing digit: bundles of $692$ $57$-cent doodads sell for $39\,444$ cents (three trailing $4$s) and bundles of one million doodads sell for $57\,000\,000$ cents (six trailing $0$s).

After a little thought, you realize that you do not want to make your bundles too large---not only can the price be excessive, but who really needs several million doodads? For any type of doodad, your marketing department has a maximum bundle price of $a$.

Given the price of a doodad, the desired trailing digit, and the maximum price of a bundle, write a program that optimizes the trailing digits.

inputFormat: Input consists of a single line containing three integers $b$, $d$, and $a$, where $b$ ($1 \leq b < 10^{6}$) is the price of a doodad in cents, $d$ ($0 \leq d \leq 9$) is the desired trailing digit, and $a$ ($b \leq a < 10^{10\,000}$) is the maximum price of a bundle.

outputFormat: Output the maximum number of consecutive occurrences of $d$ that can appear at the end of a bundle price, given that the price of the bundle cannot exceed $a$.

translation:
## 题目描述
有一批货，每个价值 $b$ 元，可以把 $n$ 个货打包出售，价格是 $b \times n$ 元（前提是$b \times n\le a$），使末尾含有尽可能多的数字 $d$ ，求最多的 $d$ 数量。
## 输入格式
一行三个整数，$b$ , $d$ 和 $a$。
## 输出格式
一个整数，最多的 $d$ 数量。
## 说明/提示
对于全部数据，有 $1 \le b < 10^6$ , $0 \le d \le 9$ , $b \le a < 10^{10000}$


title: [ICPC2020 WF] What’s Our Vector, Victor?

background: ICPC2020 WF N

description:
Vector embeddings are a common tool in machine learning systems.
Complex real-world concepts (for instance, words in a dictionary) are mapped onto vectors of real numbers.
If embeddings are trained properly, related concepts remain close together in the vector space, so questions like "are these two words synonyms?" can be reduced to straightforward mathematical tests.

You have been hired by Ye Olde Ice Cream Shoppe to create an embedding model for flavors, so that when they are out of an ice cream flavor they can recommend related flavors to customers.
After training your embedding on six cloud datacenters for four months, you finally had the perfect flavor model!
You were ready to revolutionize the ice cream industry on your street and, dare we say it, your neighborhood!
Well, until you accidentally dripped some free ice cream on your keyboard and deleted half the data.
The Shoppe cannot afford the 30 billion rubles needed to retrain the model, so you are in trouble.

Fortunately, you still have various training results lying around.
For a given deleted vector, the training data tells you how close it was to some known flavor vectors.
The closeness of vectors $A$ and $B$ is just the standard Euclidean distance metric (that is, the length of the vector $A - B$).
Write a tool that reconstructs embeddings which are consistent with the training results.

inputFormat:
The first line contains two integers $d$ and $n$, where $d$ ($1 \leq d \leq 500$) is the number of dimensions of the
vectors, and $n$ ($1 \leq n \leq 500$) is the number of training results for a deleted embedding vector you want to reconstruct.
Each of the next $n$ lines describes a training result using $d + 1$ numbers $x_1, \dots, x_d$ and $e$.
In a training result, $x_1, \dots, x_d$ ($-100 \leq x_i \leq 100$) are the coordinates of a known vector, and
$e$ ($0 \leq e \leq 5\,000$) is the Euclidean distance from that vector to the deleted one.

Your submission will be tested only with the sample inputs given below and inputs generated according to the following procedure.
First, $d$ and $n$ are chosen.
Then, $n$ input vectors and $1$ output vector, each with dimension $d$, are chosen at random.
The $d \cdot (n + 1)$ coordinates are independent and uniformly distributed in the interval $[-100,100]$.
Next, the Euclidean distance from each input vector to the output vector is computed.
Finally, the output vector is discarded.
Calculations use double-precision floating-point numbers.
Numbers obtained using this procedure appear in the input with $17$ digits after the decimal point.

outputFormat: Output $d$ values, the coordinates of any vector that has the given distance to each training vector with an absolute or relative error of at most $10^{-5}$.

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

向量嵌入是机器学习系统中的一种常用工具。现实世界中的某些复杂的概念（例如词典中的单词）通过这种方法可以映射到一个实向量上。如果能让机器正确地训练向量嵌入，由于相关概念在向量空间中保持着紧密的联系，因此像“这两个单词是同义词吗？”这种问题可以简化为简单的数学测试了。

你最近被 Ye Olde 冰淇淋专柜受雇，专门负责为冰淇淋口味创建一个向量嵌入式模型，这样当一种口味的冰淇淋卖完以后，这个嵌入式模型就可以像顾客推荐其它味道相近的冰淇淋。在六个云数据中心里训练了四个月以后，你终于拥有了一个完美的模型，正准备好改变你所在街区的冰淇淋行业，乃至整个街区时，你不小心把一些免费的冰淇淋滴到了键盘上，导致一半的数据被删除。重新训练模型需要花费 300 亿卢布，而专柜显然承受不了这么高的价格，因此你陷入了巨大的麻烦之中。幸运的是，你可以通过剩下的数据来还原出被删除的向量。具体地，对于一个给定的被删除的向量，数据会告诉你它与某些已知的味道向量的接近程度。两个向量 $A,B$ 的接近程度即为这两个向量之间的标准欧几里得距离（即向量 $A-B$ 的长度）。

现在，给定向量所处的空间维度 $d$ 和已知向量个数 $n$，并给定所有 $n$ 个向量的坐标 $(x_{i,1},x_{i,2},\cdots,x_{i,d})$ 和到同一个被删除的向量的标准欧几里得距离 $e_i$，请你编写一个程序，求出被删除的向量的坐标。

**【输入格式】**

第一行输入两个整数 $d,n$，分别表示向量空间的维度和向量个数。
随后 $n$ 行，每行 $d+1$ 个实数 $x_{i,1},x_{i,2},\cdots,x_{i,d},e_i$，其中前 $d$ 个实数描述了第 $i$ 个向量的坐标，第 $d+1$ 个实数则表示第 $i$ 个向量与被删除的向量之间的标准欧几里得距离。

你提交的代码只会在样例输入数据和按以下方式生成的输入数据上进行测试：

- 在区间 $[1,500]$ 中选出两个整数作为 $d,n$。
- 随机生成 $n$ 个 $d$ 维输入向量和一个 $d$ 维输出向量。这 $d\cdot(n+1)$ 个坐标在区间 $[-100,100]$ 中独立且均匀地生成。
- 对于每个输入向量，计算其与输出向量之间的标准欧几里得距离。
- 忽略输出向量。

所有在上述过程中的计算使用双精度浮点数，用这种方式生成的所有实数均保留到小数点后 $17$ 位。

**【输出格式】**

输出 $d$ 个整数，描述被删除向量的坐标。你需要保证你输出的答案和标准答案之间的误差不会超过 $10^{-5}$。

**【样例】**

见『输入输出样例』部分。

**【数据范围】**

对于所有数据：

- $1\leqslant d,n\leqslant 500$。
- $-100\leqslant x_{i,j}\leqslant 100$。
- $0\leqslant e_i\leqslant 5000$。

Translated by Eason_AC


title: [ICPC2020 WF] Which Planet is This?!

background: ICPC2020 WF O

description:
It's the year 2521, and interstellar probes have reached planets in distant
solar systems. The Interstellar Consortium of Planet Cartographers (ICPC) has
created detailed maps of these planets, and they seem to indicate the
existence of alien life! On each map, the ICPC has recorded the locations of
what appear to be alien dwellings.

The ICPC was planning to release this exciting news to the public, but at the
last moment, disaster struck. One of the ICPC's interns deleted all
meta-data associated with the maps. So while the maps themselves are safe, the
ICPC does not know which maps belong to which planets. For this, they have come back
in time to ask for your help. Given two maps, can you determine whether they describe the same planet?
Hopefully, a 500-year head start will be enough time to solve this important
problem!

The planetary maps consist of sets of points on the (spherical) planet
surface. They are specified in terms of latitude (the angle north or south of
the equator) and longitude (the angle west or east of the noon meridian, which
is the location of the sun when the map's data was collected). Two maps for
the same planet always agree on the latitudes of the points, since the
planet's axis does not change. However, the longitudes of the points might
differ, because the planet rotates between measurements.

inputFormat:
The first line of input contains an integer $n$ ($1 \le n \le 400\,000$), the
number of points in each of the two maps to be compared. Then follow $n$ lines
describing the first map. Each of these lines contains two real numbers $a$
and $b$, where $a$ ($-90 < a < 90$) is the latitude and $b$ ($-180 < b \le
180$) is the longitude. Coordinates are expressed in degrees and have at most
four digits after the decimal point. No two points on the map will
have the same coordinates. The remaining $n$ lines describe the second map in the same format as the
first.

outputFormat:
Output $\texttt{Same}$ if there is a rotation around the planet's axis that transforms one map into
the other. Otherwise, output $\texttt{Different}$.

translation:
### 题目描述
这是2521年，星际探测器已经到达了遥远的太阳系的行星。星际行星制图者联盟(ICPC)已经绘制了这些行星的详细地图，它们似乎表明外星生命的存在!ICPC在每张地图上都记录了疑似外星人住所的位置。

ICPC本打算向公众公布这一激动人心的消息，但在最后一刻，灾难发生了。ICPC的一名实习生删除了所有与地图相关的元数据。因此，虽然地图本身是安全的，但ICPC并不知道哪些地图属于哪些行星。为此，他们及时回来请求您的帮助。给定两幅地图，你能确定它们是否描述的是同一颗行星吗?希望领先500年的时间足以解决这个重要的问题!

行星图由(球面)行星表面的点集组成。它们是根据纬度(赤道南北的夹角)和经度(正午子午线的西半球或东半球的夹角，这是地图数据采集时太阳的位置)来指定的。同一颗行星的两幅地图在纬度上总是一致的，因为行星的轴是不变的。然而，这两个点的经度可能不同，因为行星在两次测量之间会旋转。

### 输入格式
输入的第一行包含一个整数$n$ ($1 \le n \le 400000=4\times10^5$)，这是要比较的两个地图射中每个地图中的点数。然后跟随描述第一张地图的$n$条线。每条线包含两个实数$a$和$b$，其中$a$($-90<a<90$)是纬度，$b$($-180<a<180$)是经度。坐标以度表示，小数点后最多有四位数字。地图上没有两个点的坐标是相同的。其余的$n$行以与第一个相同的格式描述第二个映射。

### 输出格式
如果有一种围绕行星轴旋转的方式使得地图1和地图2相同，输出`Same`，否则输出`Different`


title: [Ynoi2010] Exponential tree

description:
对于给定的 $n,k$，你需要构造一个只含 $0,1$ 的矩阵 $A_{i,j}$，$0\le i,j\le n$，满足：

1. $A_{i,i}=1$
2. $A_{i,i+1}=1$
3. 对 $i>j$ 有 $A_{i,j}=0$
4. 若 $A_{i,j}=1$，$j-i>1$，则存在 $i<t<j$，满足 $A_{i,t}=A_{t,j}=1$
5. 对 $i\le j$ 有 $(A^k)_{i,j}>0$。

你需要输出满足 $A_{i,j}=1$ 且 $j-i>1$ 的每个 $(i,j)$，设这样的 $(i,j)$ 共有 $m$ 个。

若输出不满足要求，则不能得到该测试点的任何分数。若输出满足要求，则根据 $m$ 进行评分。

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

outputFormat: 第一行一个整数 $m$，接下来 $m$ 行，每行两个整数 $i,j$，依次表示每个满足 $A_{i,j}=1$ 且 $j-i>1$ 的二元组 $(i,j)$。


title: [CEOI2021] Tortoise

background: 译自 CEOI2021 Day2 T2. [Tortoise](https://hsin.hr/ceoi/competition/ceoi2021_day2_tasks.pdf)。

description:
Wilco 想购买糖果，为此它将访问 Nakamise 商店街。

Tom 想让 Wilco 少吃点糖果，为此它将在 Wilco 前购买一些糖果。商店街上共有 $N$ 个等距离的地点，它们要么是商店要么是空地。

每家商店都有一定数量的糖果（可能为 $0$） Wilco 将会从第一个地点走到最后一个，顺序访问所有地点。每当它到达一家商店时它会买走所有糖果。Tom 每一刻的移动速度是 Wilco 的两倍，且可以朝两个方向移动。但是，Tom 每一刻只能携带最多一颗糖果。一旦 Tom 拿到一颗糖果，它就会把它带走直到把它交给在空地上玩的小孩。假设购买和给出糖果均不消耗时间。

Tom 的目标是最小化 Wilco 能拿到的糖果。初始时它们均在第一个地点，Tom 任何时刻先于 Wilco 行动。即如果第一个地点是商店，Tom 可以先于 Wilco 购买一颗糖果。

那么在 Tom 的干扰下 Wilco 能拿到多少糖果呢？

inputFormat:
输入的第一行包含一个整数 $N$，含义如题目描述。

第二行有 $N$ 个整数 $a_1,a_2,\dots,a_N$ 表示商店街上的 $N$ 个地点，其中 $a_i=-1$ 时第 $i$ 个地点为空地，否则它为商店且有 $a_i$ 颗糖果出售。有可能一家商店没有糖果（即 $a_i=0$）

保证至少有一个地点是空地。

outputFormat: 输出 Wilco 将会买到的糖果数量。


title: [CEOI2021] Wells

background:
译自 CEOI2021 Day2 T3. [Wells](https://hsin.hr/ceoi/competition/ceoi2021_day2_tasks.pdf)。

本题数据不全，建议去 loj 提交：https://loj.ac/p/3597 。

description: 给出一个有 $N$ 个结点的树和一个正整数 $K$，确定是否存在一个顶点子集，使得任意恰好包含 $K$ 个顶点的路径都**恰好**有一个来自该子集的顶点。此外，您需要找到模 $10^9+7$ 的此类子集的数量（不存在则为 $0$）。

inputFormat:
第一行两个整数 $N$ 和 $K$。

接下来 $N-1$ 行，每行两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间存在一条无向边。

outputFormat:
第一行一个字符串，如果存在输出 `YES`，否则输出 `NO`。

第二行输出一个整数，表示满足条件的子集个数，如果不存在，输出 $0$。


title: [JRKSJ R5] 1-1 A

background: 本题是 1-1 的较易版本，较难版本为 [1-1 B](https://www.luogu.com.cn/problem/P8848)。

description:
给出一个序列 $a$，$\forall i\in [1,n],a_i\in \{1,-1\}$。

你可以将序列任意重排，需最小化重排后序列的最大子段和。

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

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

outputFormat:
一行 $n$ 个整数，以空格隔开，表示重排后的序列。

若有多解，则任意输出一个答案即可。

hint:
最大子段和的定义：序列中一段区间的和的最大值。即 $\max_{1\le l\le r\le n} \sum_{i=l}^r a_i$。

本题使用 $\text{Special Judge}$，只要你的输出满足题意即可通过。

**本题输入输出文件较大，请使用恰当的输入输出方式。**

### 数据规模
本题采用捆绑测试。

| $\text{Subtask}$ | $n\le$ | $\text{Score}$ |
| :----------: | :----------: | :----------: |
| $1$ | $10$ | $40$ |
| $2$ | $10^6$ | $60$ |

对于 $100\%$ 的数据，$1\le n\le 10^6$，$a_i\in \{1,-1\}$。


title: 「GLR-R4」大暑

background:
  「时见疏星落画檐，几点流萤小」

---

  全国音乐祭，在天依一行人抵达之时，芙城早已翻涌这狂欢的气氛，汇聚于此的某些紧张青年人们倒显得有些格格不入。

  “总之，这里一定是终点站吧。”

  排练又一次随着弦音结束。又开始，结束。

  “阿绫，我们出去走走吧。”

---

  **大暑** 「为所有视线涂抹上　一片蔚蓝的颜色　融化了苦涩」

description:
  “阿绫，你看这宣传册上这幅画，好奇怪呀。”

  在宣传册中“融艺术与科技为一体”的巨幅画作的制作过程如下：

  首先，工作人员画出 $n!$ 个 $n\times2$ 的点阵图，任意两个点阵图间互相远离，在后续的制作过程中**互相独立**。对于第 $i$ 个点阵图，令其左下角坐标为 $(0,0)$，该点阵的点集为 $X_i\cup Y_i$，其中 $X_i=\{(0,y)\mid y\in[0,n)\cap\mathbb N\}$，$Y_i=\{(1,y)\mid y\in[0,n)\cap\mathbb N\}$。

  接着，设集合 $\Sigma=\{\sigma_i\}_{i=1}^{n!}$ 包含 $\{0,1,\dots,n-1\}$ 的所有 $n$ 阶排列，对于第 $i$ 个点阵图，工作人员将用字典序第 $i$ 小的排列 $\sigma_i$ 为 $X_i,Y_i$ 连线配对：对于点 $P(0,y)\in X_i$，作一条线段将其与点 $Q(1,\sigma_{i,y})\in Y_i$ 相连。

  最后，是激动人心的上色步骤。对于第 $i$ 个点阵图中的每个 $P(0,y)\in X_i$，从 $P$ 出发，沿着上一步骤中作出的线段，走**任意线段或折线**，到达 $Y_i$ 中的任意一点，并为这条线段或折线染上第 $y$ 种颜色。此外，为了避免不同颜色混在一起，需要保证，在所有 $n!$ 个点阵图中，被多余一种颜色染过的线段长度之和为 $0$。

  呈现在天依一行人眼前的这幅画的上色明显很敷衍，所以天依想知道到底有多少种可供选择的上色方案。定义两种上色方案不同，当且仅当存在编号 $i\in[1,n!]$ 和任意一点 $P$，使得两个上色方案各自完成后，第 $i$ 个点阵图中染过点 $P$ 的颜色集合不同。

  你只需要告诉天依答案对 $p=335~544~323$ 取模后的结果。*天依可是为了简化你的计算，精挑细选了一个有趣的模数呢。*

  （请参考样例 #1 解释确认题意。）

inputFormat: 输入一行一个整数 $n$，表示作画过程的参数。

outputFormat: 输出一行一个非负整数，表示上色方案数对 $p$ 取模的结果。


title: 「DAOI R1」Ciky

background:
>
> She is Mine.
>

description:
深秋，落叶纷纷，瞳可开心了。

$ \texttt{Augen} $ 带着小朋友们一起在树林里捡了很多金黄的叶子。

他们捡的所有叶子都是正多边形，现在 $ \texttt{Augen} $ 准备把它们制作成标本装订成册送给瞳。

制作一个标本，需要沿一片叶子的边缘画上颜色，每一片叶子边缘的颜色不能相同。同时，每一个标本都有相对应的美丽程度。

将标本装订成册时，需满足以下条件：

- 第 $i$ 片叶子的周长不能大于第 $i+1$ 片叶子；
- 第 $i$ 片叶子的美丽程度不能大于第 $i+1$ 片叶子。

 $ \texttt{Augen} $ 拥有 $n$ 支不同颜色的笔，每支还可以画 $a_i$ 的长度。

$m$ 片叶子，第 $i$ 片叶子为正 $k_i$ 边形，每条边长 $b_i$ ，每片叶子的美丽程度$c_i$ 。

更简单地说，即，只有满足 $k_i*b_i \leq a_j$ 的情况下，可以用第 $j$ 支画笔，画第 $i$ 片叶子。

特别地，在一片叶子被第 $i$ 支画笔画完过后，它的周长会变成 $a_i$。一个画笔最多画一片叶子。

 $ \texttt{Augen} $ 希望能更多的送出标本或者使得制作出来的标本美丽程度总和最大。

 **注意：两个小问相互独立。**

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

第二行共 $n$ 个整数，第 $i$ 个整数表示 $a_i$ 。

第三行共 $m$ 个整数，第 $i$ 个整数表示 $b_i$ 。

第四行共 $m$ 个整数，第 $i$ 个整数表示 $c_i$ 。

第五行共 $m$ 个整数，第 $i$ 个整数表示 $k_i$ 。

outputFormat:
共两行 。

第一行，一个整数，表示册子中标本的个数的最大值 。

第二行，一个整数，表示制作出来的标本美丽程度的最大值 。

**注意：第二问并未要求将标本装入册子。**


title: [JOI 2022 Final] 星际蛋糕 (Intercastellar)

background:
在 30XX 年，由于科学家和工程师的不断努力，不同星球之间的互动变得非常活跃。比太郎是一只河狸，他现在是一项交流项目的大使。他的任务是向不同星球的居民介绍地球上的食物。他将在下午 1 点出发去 JOI 星球。

现在，比太郎正计划向 JOI 星球的居民介绍 castella。castella 已经被切成了若干段。castella 是一种由面粉、鸡蛋、糖和淀粉糖浆制成的烘烤海绵蛋糕。

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

description:
castella 的形状是一个在水平方向上很长的长方体。它被切成了 $N$ 段，其中从左往右的第 $i$ 段的长度为整数 $A_i$。

几分钟前，我们得知 JOI 星球的居民不喜欢偶数。为了解决此问题，你需要不断执行下列操作，直到不存在长度为偶数的段。

1. 在长度为偶数的段中，你选择最靠右的一段。
2. 你将选中的这一段切成两个长度相等的段。也就是说，假设选中的这一段的长度是 $k$，你将其切成长度为 $\displaystyle \frac{k}{2}$ 的两段。你不改变其他段的位置。

为了确认操作是否被正确地执行了，比太郎让你回答 $Q$ 个询问。第 $j$ 个询问如下：

- 当所有操作执行完毕后，从左往右的第 $X_j$ 段的长度为多少？

给定 castella 的信息与询问，请写一个程序回答所有询问。

inputFormat:
第一行，一个正整数 $N$。

接下来 $N$ 行，第 $i$ 行一个正整数 $A_i$。

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

接下来 $Q$ 行，第 $j$ 行一个正整数 $X_j$。

outputFormat: 输出 $Q$ 行，第 $j$ 行一个数，表示第 $j$ 个询问的答案。

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

一开始，castella 从左到右的段的长度分别为 $14, 9, 8, 12$。

当所有操作执行完毕后，castella 被切成了 $15$ 段。从左到右的段的长度分别为 $7, 7, 9, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3$。

这个样例满足子任务 $2, 3$ 的限制。

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

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

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

这个样例满足子任务 $2, 3$ 的限制。

----

**【数据范围】**

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

对于 $100 \%$ 的数据，$1 \le N, Q \le 2 \times {10}^5$，$1 \le A_i \le {10}^9$，$1 \le X_j \le {10}^{15}$，$X_j \le X_{j + 1}$，保证当所有操作执行完毕后，castella 被切成了至少 $X_Q$ 段。

- 子任务 $1$（$25$ 分）：$A_i \le 8$。
- 子任务 $2$（$35$ 分）：$N, Q \le 1000$。
- 子任务 $3$（$40$ 分）：无特殊限制。

----

**译自 [JOI 2022 Final](https://www.ioi-jp.org/joi/2021/2022-ho/index.html) T1「[インターカステラー](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t1.pdf) / [Intercastellar](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t1-en.pdf)」**


title: [JOI 2022 Final] 自学 (Self Study)

description:
在 JOI 高中高一的第三个学期的 $M$ 个星期的时间内，有 $N$ 门课，编号为 $1 \sim N$。每个星期有 $N$ 个课时，第 $i$ 个课时上课程 $i$ 的一节课。

比太郎是一位高一学生。对于 $N \times M$ 个课时中的每一个，他会选择如下行动中的一个：

- 行动 1：比太郎去上课。如果他去上了课程 $i$ 的一节课，那么他对课程 $i$ 的理解程度会增加 $A_i$。
- 行动 2：比太郎不去上课。他转而选择任意一门课，并且自学选中的那门课。如果他选中了课程 $i$ 进行了时长为一课时的自学，那么他对课程 $i$ 的理解程度会增加 $B_i$。

一开始，对每门课的理解程度都为 $0$。由于比太郎想要在课后练习算法竞赛，他在非上课时间内不会学习。当第三个学期的所有课时结束后，期末考就会举行。

比太郎不想挂科。所以他想要最大化在期末考时对每门课的理解程度的最小值。

给定学期的长度，课程的数量，以及对理解程度的提升数值，请写一个程序计算在期末考时对每门课的理解程度的最小值的最大可能值。

inputFormat:
第一行，两个正整数 $N, M$。

第二行，$N$ 个正整数 $A_1, A_2, \ldots, A_N$。

第三行，$N$ 个正整数 $B_1, B_2, \ldots, B_N$。

outputFormat: 输出一行，一个数，表示在期末考时对每门课的理解程度的最小值的最大可能值。

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

举个例子，如果比太郎按如下方式学习，则他对课程 $1, 2, 3$ 的理解程度将分别为 $19, 18, 19$。

- 第一周课程 $1$ 的课：自学课程 $2$；
- 第一周课程 $2$ 的课：自学课程 $2$；
- 第一周课程 $3$ 的课：去上课程 $3$ 的课；
- 第二周课程 $1$ 的课：去上课程 $1$ 的课；
- 第二周课程 $2$ 的课：自学课程 $3$；
- 第二周课程 $3$ 的课：去上课程 $3$ 的课；
- 第三周课程 $1$ 的课：自学课程 $3$；
- 第三周课程 $2$ 的课：自学课程 $2$；
- 第三周课程 $3$ 的课：去上课程 $3$ 的课。

由于对每门课的最小的理解程度不能大于等于 $19$，输出 $18$。

这个样例满足子任务 $3, 5$ 的限制。

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

这个样例满足子任务 $1, 3, 5$ 的限制。

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

这个样例满足子任务 $3, 5$ 的限制。

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

这个样例满足子任务 $2, 3, 4, 5$ 的限制。

----

**【数据范围】**

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

对于 $100 \%$ 的数据，$1 \le N \le 3 \times {10}^5$，$1 \le M \le {10}^9$，$1 \le A_i, B_i \le {10}^9$。

- 子任务 $1$（$10$ 分）：$M = 1$。
- 子任务 $2$（$25$ 分）：$N \cdot M \le 3 \times {10}^5$，$A_i = B_i$。
- 子任务 $3$（$27$ 分）：$N \cdot M \le 3 \times {10}^5$。
- 子任务 $4$（$29$ 分）：$A_i = B_i$。
- 子任务 $5$（$9$ 分）：无特殊限制。

----

**译自 [JOI 2022 Final](https://www.ioi-jp.org/joi/2021/2022-ho/index.html) T2「[自習](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t2.pdf) / [Self Study](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t2-en.pdf)」**


title: [JOI 2022 Final] 让我们赢得选举 (Let's Win the Election)

description:
JOI 共和国有 $N$ 个州，编号为 $1 \sim N$。在 2022 年，JOI 共和国将举行总统大选。选举将在每个州分别举行。每个州的获胜者将赢得该州的一张选票。

Rie 将竞选总统，她正计划赢得选举。她决定以发表演讲的方式来提高自己的可靠程度。在她发表演讲后，下列事件可能会发生。

- 如果在第 $i$ 个州的总演讲时间达到了 $A_i$ 小时，她将赢得该州的一张选票。
- 如果在第 $i$ 个州的总演讲时间达到了 $B_i$ 小时，她将获得一名来自该州的协作者。
- 有可能 Rie 在第 $i$ 个州无法获得协作者。此种情况下，$B_i = -1$，否则保证 $B_i > A_i$。

来自第 $i$ 个州的协作者可以在第 $i$ 个州外发表演讲。多个人可以同时在同一个州发表演讲。举个例子，如果两个人在某个州同时发表了 $x$ 小时的演讲，则该州的总演讲时间将增加 $2 x$ 小时。演讲的时间不必是整数个小时。我们可以忽略在两州之间的交通耗时。

大选日快到了，Rie 想要尽快得到 $K$ 张选票。

给定州的数量和每个州的信息，写一个程序计算得到 $K$ 张选票的最小耗时（以小时为单位）。

inputFormat:
第一行，一个正整数 $N$。

第二行，一个正整数 $K$。

接下来 $N$ 行，第 $i$ 行两个正整数 $A_i, B_i$。

outputFormat:
输出一行，一个数，表示得到 $K$ 张选票的最小耗时（以小时为单位）。

如果你的输出与正确答案的差值的绝对值不超过 $0.01$ 则你的提交将被判断为正确。你的输出应使用如下格式：

- 一个整数（例：`123`，`0`，`-2022`）。
- 一个依次包含一个整数，一个句点，和一个仅包含 $0 \sim 9$ 的数位的字符串的序列。其不应当包含分隔符。对小数点后的数位长度无限制（例：`123.4`，`-123.00`，`0.00288`）。

输出不应使用指数表示法。举个例子，`1.23456e+05` 和 `1.23456e5` 不被允许。

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

按照如下方案进行演讲，Rie 将在 $5.5$ 小时内赢得每个州的选票。

- 在第 $2$ 个州演讲 $2$ 个小时，赢得一张选票。
- 在第 $2$ 个州再演讲 $1$ 个小时，获得一个协作者。
- 在第 $3$ 个州与协作者一起演讲 $2$ 个小时，赢得一张选票。
- 在第 $1$ 个州与协作者一起演讲 $0.5$ 个小时，赢得一张选票。

这个样例满足子任务 $3, 4, 5, 6, 7$ 的性质。

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

按照如下方案进行演讲，Rie 将在 $32$ 小时内赢得 $4$ 张选票。

- 在第 $1$ 个州演讲 $4$ 个小时，赢得一张选票。
- 在第 $2$ 个州演讲 $11$ 个小时，赢得一张选票。
- 在第 $3$ 个州演讲 $6$ 个小时，赢得一张选票。
- 在第 $6$ 个州演讲 $11$ 个小时，赢得一张选票。

这个样例满足子任务 $1, 2, 3, 4, 5, 7$ 的限制。

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

按照如下方案进行演讲，Rie 将在 $11.5$ 小时内赢得 $3$ 张选票。

- 在第 $4$ 个州演讲 $7$ 个小时，赢得一张选票，并获得一个协作者。
- 在第 $1$ 个州演讲 $4$ 个小时，赢得一张选票。与此同时，协作者在第 $2$ 个州演讲 $4$ 个小时。
- 在第 $2$ 个州与协作者一起演讲 $0.5$ 个小时，赢得一张选票。

这个样例满足子任务 $2, 3, 4, 5, 7$ 的限制。

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

这个样例满足子任务 $3, 4, 5, 7$ 的限制。

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

这个样例满足子任务 $4, 5, 7$ 的限制。

----

**【数据范围】**

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

对于 $100 \%$ 的数据，$1 \le K \le N \le 500$，$1 \le A_i \le 1000$，$A_i \le B_i \le 1000$ 或 $B_i = -1$。

- 子任务 $1$（$5$ 分）：$B_i = -1$。
- 子任务 $2$（$5$ 分）：$B_i = -1$ 或 $B_i = A_i$。
- 子任务 $3$（$11$ 分）：$N \le 7$。
- 子任务 $4$（$12$ 分）：$N \le 20$。
- 子任务 $5$（$33$ 分）：$N \le 100$。
- 子任务 $6$（$11$ 分）：$K = N$。
- 子任务 $7$（$23$ 分）：无特殊限制。

----

**译自 [JOI 2022 Final](https://www.ioi-jp.org/joi/2021/2022-ho/index.html) T3「[選挙で勝とう](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t3.pdf) / [Let's Win the Election](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t3-en.pdf)」**


title: [JOI 2022 Final] 铁路旅行 2 (Railway Trip 2)

description:
IOI 铁路公司在一条铁轨上运营线路。铁轨为一条直线，该铁轨上有 $N$ 个车站，编号为 $1 \sim N$。车站 $i$ 与车站 $i + 1$ 之间由一条铁轨直接连接。

IOI 铁路公司正在运营 $M$ 条线路，编号为 $1 \sim M$。线路 $j$ 的起点为 $A_j$，终点为 $B_j$，列车在每一站均会停靠，即如果 $A_j < B_j$，一列 $j$ 号线的列车会按顺序在车站 $A_j, A_j + 1, \ldots, B_j$ 停靠。如果 $A_j > B_j$，一列 $j$ 号线的列车会按顺序在车站 $A_j, A_j - 1, \ldots, B_j$ 停靠。

JOI 君是一个旅行者。他有 $Q$ 个旅行计划。在第 $k$ 个旅行计划中他计划从车站 $S_k$ 通过乘坐列车前往车站 $T_k$。

然而，JOI 君因长途跋涉而疲惫不堪。他希望他乘坐的列车均有空座以便休息。因此 JOI 君决定，只有当某条线路的起点站是第 $K$ 个或更早的车站时，他才会在该站乘坐该条线路的列车。换句话说，对于线路 $j$，如果 $A_j < B_j$，那么他只会在车站 $A_j, A_j + 1, \ldots, \min \{ A_j + K - 1, B_j - 1 \}$ 乘上线路 $j$ 的列车。如果 $A_j > B_j$，那么他只会在车站 $A_j, A_j - 1, \ldots, \max \{ A_j - K + 1, B_j + 1 \}$ 乘上线路 $j$ 的列车。

在这些条件下，JOI 君希望尽量减少乘坐火车的次数。

给出 IOI 铁路公司的线路信息和 JOI 君的计划，写一个程序计算对于 JOI 君的每一个计划，他所需的最小乘车次数。

inputFormat:
第一行，两个正整数 $N, K$。

第二行，一个正整数 $M$。

接下来 $M$ 行，第 $j$ 行两个正整数 $A_j, B_j$。

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

接下来 $Q$ 行，第 $k$ 行两个正整数 $S_k, T_k$。

outputFormat: 输出 $Q$ 行，第 $k$ 行一个数，表示对于 JOI 君的第 $k$ 个计划，他实现该计划所需的最小乘车次数。如果无论如何无法实现第 $k$ 个计划，则输出 `-1`。

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

对于第一个计划，JOI 君要从车站 $5$ 前往车站 $3$。具体地，此计划可以通过如下方式实现：JOI 君在车站 $5$ 乘上 $1$ 号线的列车，并在车站 $3$ 下车。JOI 君总共乘坐了一次列车。由于不可能花费比 $1$ 更少的乘车次数实现该计划，在第一行输出 $1$。

对于第二个计划，JOI 君要从车站 $3$ 前往车站 $2$。具体地，此计划可以通过如下方式实现：JOI 君在车站 $3$ 乘上 $2$ 号线的列车，并在车站 $4$ 下车；然后在车站 $4$ 乘上 $1$ 号线的列车，并在车站 $2$ 下车。JOI 君总共乘坐了两次列车。由于不可能花费比 $2$ 更少的乘车次数实现该计划，在第二行输出 $2$。

对于第一个计划，JOI 君要从车站 $2$ 前往车站 $1$。由于无论如何无法实现该计划，在第三行输出 `-1`。

这个样例满足子任务 $1, 2, 6$ 的限制。

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

这个样例满足子任务 $1, 2, 6$ 的限制。

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

这个样例满足子任务 $1, 2, 4, 6$ 的限制。

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

这个样例满足子任务 $1, 2, 5, 6$ 的限制。

----

**【数据范围】**

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

对于 $100 \%$ 的数据，$2 \le N \le {10}^5$，$1 \le K \le N - 1$，$1 \le M \le 2 \times {10}^5$，$1 \le Q \le 5 \times {10}^4$，$1 \le A_j, B_j, S_k, T_k \le N$，$A_j \ne B_j$，$S_k \ne T_k$，$(A_j, B_j) \ne (A_k, B_k)$（$j \ne k$），$(S_k, T_k) \ne (S_l, T_l)$（$k \ne l$）。

- 子任务 $1$（$8$ 分）：$N, M, Q \le 300$。
- 子任务 $2$（$8$ 分）：$N, M, Q \le 2000$。
- 子任务 $3$（$11$ 分）：$Q = 1$。
- 子任务 $4$（$25$ 分）：$K = N - 1$。
- 子任务 $5$（$35$ 分）：$A_j < B_j$，$S_k < T_k$。
- 子任务 $6$（$13$ 分）：无特殊限制。

----

**译自 [JOI 2022 Final](https://www.ioi-jp.org/joi/2021/2022-ho/index.html) T4「[鉄道旅行 2 ](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t4.pdf) / [Railway Trip 2](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t4-en.pdf)」**


title: [JOI 2022 Final] 沙堡 2 (Sandcastle 2)

description:
JOI 君在沙滩上玩耍。他建造了一座沙堡。这座由 JOI 君建造的沙堡位于沙滩上的一个矩形区域内。这个矩形区域有 $H$ 行 $W$ 列。位于从上往下的第 $i$ 行、从左往右的第 $j$ 列的格子的高度为 $A_{i, j}$。**注意所有 $\boldsymbol{A_{i, j}}$ 的值互不相同。**

在沙堡上，JOI 君执行了下列动作。

1. 首先，JOI 君选择一个格子，他从该格子开始移动。
2. 然后，他从当前格子出发朝上下左右四个方向之一移动到相邻的格子上。他必须移动到低于当前格子的格子上。他可以重复此动作零次或更多次。

最终，如果我们从上往下看，他经过的格子将形成一个矩形。

给定每个格子的高度信息 $A_{i, j}$，写一个程序计算所有可能的由 JOI 君经过的格子组成的矩形的数量。

inputFormat:
第一行，两个正整数 $H, W$。

接下来 $H$ 行，第 $i$ 行 $W$ 个正整数 $A_{i, 1}, A_{i, 2}, \ldots, A_{i, W}$。

outputFormat: 输出一行，一个数，表示所有可能的由 JOI 君经过的格子组成的矩形的数量。

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

由于有 $10$ 个可能的由 JOI 君经过的格子组成的矩形，输出 $10$。

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

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

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

由于有 $15$ 个可能的由 JOI 君经过的格子组成的矩形，输出 $15$。

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

这个样例满足子任务 $2, 3, 4, 5$ 的限制。

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

举个例子，如下矩形可以由 JOI 君经过的格子组成。由于总共有 $65$ 个可能的矩形，输出 $65$。

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

这个样例满足子任务 $2, 3, 4, 5$ 的限制。

----

**【数据范围】**

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

对于 $100 \%$ 的数据，$1 \le H, W, H \cdot W \le 5 \times {10}^4$，$1 \le A_{i, j} \le {10}^7$，$A_{i_1, j_1} \ne A_{i_2, j_2}$（$(i_1, j_1) \ne (i_2, j_2)$）。

- 子任务 $1$（$9$ 分）：$H = 1$。
- 子任务 $2$（$10$ 分）：$H \cdot W \le 100$。
- 子任务 $3$（$5$ 分）：$H \cdot W \le 1500$。
- 子任务 $4$（$56$ 分）：$H \cdot W \le 7000$。
- 子任务 $5$（$20$ 分）：无特殊限制。

----

**译自 [JOI 2022 Final](https://www.ioi-jp.org/joi/2021/2022-ho/index.html) T5「[砂の城 2 ](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t5.pdf) / [Sandcastle 2](https://www.ioi-jp.org/joi/2021/2022-ho/2022-ho-t5-en.pdf)」**


title: 测测你的矩阵乘法

type: B

description:
给定两个大小为均为 $512 \times 512$，每个元素均为整数，值域为 $ [0, 1024) $ 矩阵 $A, B$，定义为

$$ \begin{aligned}
	A\left[i, j\right] &= \left(\left(i \mathbin{\mathrm{or}} j\right) + j\right) \mathbin{\mathrm{xor}} \mathrm{seed}_A \\
    B\left[i, j \right] &= \left( \left(i \mathbin{\mathrm{and}} j \right) + i \right) \mathbin{\mathrm{xor}} \mathrm{seed}_B
\end{aligned} $$

其中 $i, j \in [0, 512)$。

请计算 $C = A \times B$。

inputFormat:
输入为两个整数 $\mathrm{seed}_A, \mathrm{seed}_B$（$0 \leq \mathrm{seed}_A, \mathrm{seed}_B < 1024$）。

你可以使用以下代码模板，完成其中的 `multiply` 即可。

你可以修改 $N$（即数组长度），但是不能修改 $n$（矩阵大小，恒为 $512$）。

```cpp
#include <bits/stdc++.h>
const int n = 512, N = n;
void multiply (int c[N][N], int a[N][N], int b[N][N]) {
	// c = a * b
}
int c[N][N], a[N][N], b[N][N];
int main() {
	int seedA, seedB;
	scanf("%d%d", &seedA, &seedB);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            a[i][j] = ((i | j) + j) ^ seedA;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            b[i][j] = ((i & j) + i) ^ seedB;
    multiply(c, a, b);
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = 0; j < n; j++) sum ^= c[i][j];
        printf("%d\n", sum);
    }
}
```

outputFormat:
输出 $512$ 行，分别是 $C$ 每行的异或和。

输入中的代码会帮助你完成输出。


title: 「REOI-1」深潜的第六兽

background:
“〈十七兽〉全都不会飞。因此，在它们毁灭大地以后，悬浮大陆群还能像这样浮在天空。

“可是，只有〈深潜的第六兽〉在本身留在大地的同时，还能对悬浮大陆群发动攻击。它有两种能力，『分裂增生』和『快速茁壮』。

“留在地表的本体会让身体分裂出几万个碎块，然后随风飞扬，等待碰巧飘流到某座悬浮岛。抵达岛上以后，它会当场发育茁壮，大约六到八小时过后就能占据并毁灭整座岛。”

description:
现在有一只〈第六兽〉，在某一次的「分裂增生」时分裂出了 $n$ 个碎块，这些碎块会笔直向上飞去，如果其中一块碎块遇到了一座浮空岛（为了研究方便，我们不妨将它当成一条二维空间中的线段处理），便会迅速占据它，并一分为二，再次从浮空岛的两端笔直向上飞去。

不过好在，那些只是一些无关紧要最为荒凉毫无人烟的岛屿，但如果就这样放任它们继续肆虐，势必会给那些至关重要的浮空岛带来毁灭性的打击。于是乎，负责清理〈第六兽〉的军官们，决定以他们所在的岛屿为直线建立 $x$ 轴，并以重力的方向为正方向建立 $y$ 轴，他们总共监测到了 $m$ 座浮空岛，并确定了那些碎块分裂出的位置（距离 $x$ 轴的位置视作无限远），于是他们想知道，如果放任这些碎块，那么当它们到达军官的位置时，最终会有多少碎块。

注意，若一座浮空岛的 $ l_i $ 与 $ r_i $ 相同，即为一个点， 〈第六兽〉占据后仍然会分裂成两只，从这个点向上飞去。

**提示：浮空岛作为实体显然不会重叠。**

**简要题意：**

在一个平面直角坐标系上有 $m$ 条平行于 x 轴的线段，第 $i$ 条线段为 $(l_i,h_i)$ 与 $(r_i,h_i)$ 的连线。特别注意 $l_i$ 可与 $r_i$ 相等，此时线段变为一个点。

在直线 $y=10^9$ 上有 $n$ 个点，分别位于 $(x_i,10^9)$。

现在，这些点逐渐向下（y轴负方向）移动。若触碰到线段，则会一分为二，分裂出的两个点分别从线段的两端继续向下移动。

特别地，若线段为一个点，则会原地分裂成 2 个。

问所有初始点在经历了线段的分裂后，在最后会有多少个点掉在 $ x $ 轴上

inputFormat:
第一行输入两个数 $ n $ 和 $ m $。

接下来 $ m $ 行，每行三个数 $ l_i $ , $ r_i $ , $ h_i $ ,分别描述一座被视作线段的浮空岛的左端点横坐标，右端点横坐标，以及线段的纵坐标（ $ 0 \leq l_i,r_i,h_i \leq 10^5，l_i \leq r_i$）。

接下来一行 $ n $ 个数，$ x_i $表示第 $ i $ 个碎块的横坐标（ $ 0 \leq x_i \leq 10^5 $）。

outputFormat: 输出一个整数 $ ans $ ，表示最后会有多少个碎块落在 $ x $ 轴上，答案对 $998244353$ 取模。

hint:
样例解释：

注意， $y$ 轴正方向为重力方向。
在坐标轴中，横坐标为 $x$ 的碎块，先掉到纵坐标为2的线段上，然后分成两个从 $1$ 和 $3$ 往下掉，$3$ 的那个掉到了纵坐标为1的线段上，分成两个从 $2$ 和 $6$ 往下掉，第一个碎块一共变成了 $3$ 块，分别掉在 $1，2，6$ ，第二个碎块一共变成了两个碎块，分别掉在 $2，6$。

| 子问题 | 特殊限制条件 | 分值 |
| :-----------: | :-----------: | :-----------: |
| 1 | $ 1\leq n,m \leq 10 $ | 10 |
| 2 | $ 1\leq n,m \leq 100 $ | 5 |
| 3 | $ 1\leq n\leq 10^4， 1\leq m \leq 5\times 10^5 $ | 35 |
| 4 |$ 1\leq n,m \leq 5\times 10^5 $|50|

本题各个子问题之间不捆绑测试。

对于 $100\%$ 的数据 $ 1\leq n,m \leq 5\times 10^5 $，所有数字均为非负整数。


title: [RC-06] Operation Sequence

description:
给出 $n$，以及一个长度为 $n+1$ 的数组 $[a_1,a_2,\dots,a_{n+1}]$，初始时 $a_i=i\ (1\le i\le n)$，$a_{n+1}=0$。

你只能进行以下一种操作，通过输出特定字符串完成操作：

- 输出 `i j` ：其中 $i,j$ 为正整数，要求 $1\le i,j\le n+1$，表示把 $a_i$ 赋值为 $a_j$。

请把 $a$ 数组**的前 $n$ 位**向**右**循环移位 $K$ 位；即，在执行完毕你输出的所有操作后，要求 $a$ 数组第 $i\ (1\le i\le K)$ 位等于 $n-K+i$；第 $i\ (K+1\le i\le n)$ 位等于 $i-K$，第 $n+1$ 位任意。你只能进行至多 $T=\lfloor1.5n\rfloor$ 次赋值操作。

如果你进行的操作数多于 $T$ 也可以获得部分分，具体地，设你的操作次数为 $S$：

- 如果 $S\le T$，得 $100$ 分。
- 如果 $T<S\le 4T$，得 $50$ 分。
- 如果 $S>4T$，得 $0$ 分。

你在本题的得分是所有测试点中所有数据里得分的最小值。

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

第一行是数据组数 $T$。

对于每组数据：

第一行两个正整数 $n,K$。

outputFormat:
对于每组数据：

在第一行输出操作数 $k\ (0\le k\le 4T)$。**请注意，不需要最小化 $k$。**

接下来 $k$ 行，每行输出两个正整数 $i,j$，表示一次操作。$(1\le i,j\le n+1)$

hint: 所有数据均满足：$1\le T\le 10^4$，$1\le n\le 10^5$，$0\le K\le n-1$。保证同一个测试点中所有 $n$ 的和不超过 $5\times 10^5$。


title: [RC-06] Multiples

description:
给出 $n$，以及一个长度为 $n$ 的数组 $a$，$a_1\sim a_n$ 都是正整数，且 $a_i$ 在 $[1,10^9]$ 均匀随机生成。

对每个 $0\le k\le n$ 计算 $[1,m]$ 中有几个正整数 $x$ 恰好是 $k$ 个 $a_i$ 的倍数（也就是恰好存在 $k$ 个 $1\le i\le n$，$a_i\mid x$）。

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

接下来一行 $n$ 个正整数 $a_1\sim a_n$。

outputFormat: 输出一行 $n+1$ 个整数，第 $i$ 个是 $k=i-1$ 的答案。

hint:
本题没有部分分，只有 AC 才能得分。

所有数据均满足：$1\le n\le 2500$，$1\le m\le 10^9$，$1\le a_i\le 10^9$，且 $a_i$ 在 $[1,10^9]$ 中均匀随机生成。

**本题有 $6$ 组数据满足 $n=2500$，$2$ 组数据满足 $n\le 10$，共 $8$ 组数据。**

**所有数据都是如下方式生成：运行以下伪代码恰好一次生成，将其输出作为你的输入。**

```
function rnd(int l,int r):

return [l,r] 之内的随机整数

function main():

输入本组数据的 n,m
输出 n,m
输出 n 个正整数，都是 rnd(1,10^9) 的返回值
```

如果你不理解上面的生成方式，也可以阅读对应的 C++ 代码：

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	freopen("in.txt","w",stdout);
	int n,m;
	cin>>n>>m;
	cout<<n<<' '<<m<<'\n';
	mt19937_64 rng(time(0));
	const int M=1e9;
	for(int i=1;i<=n;i++)cout<<rng()%M+1<<' ';
}
```

样例不满足 $a_i$ 在 $[1,10^9]$ 均匀随机生成，因此样例不是合法的输入数据。测试数据中不包含样例。


title: [RC-06] Remake

description:
请你构造 $n$ 个正整数 $a_1\sim a_n$ 满足：

- $\forall X\in [L,R]$ 且 $X$ 是偶数，$\exists b_1\sim b_n$，使得 $\forall 1\le i\le n,b_i\in \{-1,1\}$ 且 $\sum _{1\le i\le n} a_ib_i=X$。$L,R$ 的值见数据范围。
- 设 $cnt_i$ 为满足 $a_j=i$ 的 $j$ 的个数，则 $cnt_i$ 要么等于 $0$，要么大于等于 $2$。
- $1\le n\le 40$。

为了验证你的 $a_i$ 确实满足条件，会给出 $Q$ 组询问，每次询问偶数 $X \in [L,R]$，请你输出一组合法的 $b_i$。

inputFormat:
第一行两个正整数 $M,Q$，$M$ 表示 $X$ 的上界。在测试数据中，保证 $M=10^9$。

接下来 $Q$ 行，每行一个正偶数 $X$。保证 $X\in [L,R]$。

注意 $L,R$ 并不会在输入中给出，你可以认为 $L=\min X,R=\max X$。

outputFormat:
第一行输出你构造的正整数个数 $n$。$(1\le n\le 40)$

接下来一行 $n$ 个正整数 $a_1\sim a_n$。$(1\le a_i\le 10^9)$

接下来 $Q$ 行，每行 $n$ 个字符，每个字符是 `+` 或 `-`。设第 $i$ 个字符为 $s_i$，设本次询问的值为 $X$，则需要满足 $\sum _{1\le i\le n} a_i([s_i=$ `+` $]-[s_i=$ `-` $])=X$，其中 $[P]$ 在 $P$ 成立时等于 $1$，否则等于 $0$。

你输出的 $a_i$ 需要满足题面中的要求。


title: [RC-06] Minimum and Maximum

background: 受洛谷限制，本题数据有所删减。评测全套数据请到 [InfOJ](http://119.27.163.117/contest/7/)。

description:
给定长度为 $n$ 的序列 $[a_1,a_2,\dots ,a_n]$。

$m$ 次询问，每次给出四个正整数 $L_1,R_1,L_2,R_2\ (1\le L_1\le R_1\le 4000,1\le L_2\le R_2\le 4000)$，问有多少个区间 $[l,r]\ (1\le l\le r\le n)$ 满足 $a_l,a_{l+1},\dots,a_r$ 中的最大值属于 $[L_1,R_1]$、最小值属于 $[L_2,R_2]$。

询问次数很大，所以询问是在程序内生成的。请自行阅读提示说明一栏的代码。

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

接下来一行 $n$ 个正整数 $a_1\sim a_n$。

接下来一行三个正整数 $p,q,seed$，为数据生成器的参数。你不需要理解数据生成器具体的运行过程，你只需要知道，如果正确生成了询问的话，一定有 $L_1,R_1,L_2,R_2\in [p,q]$。

outputFormat:
设第 $i$ 个询问的答案为 $ans_i$。输出一行一个整数，为 $\operatorname{xor}_{i=1}^q
(i\times ans_i)$ 的值。

hint:
**样例 1 解释**

五次询问的 $(L_1,R_1,L_2,R_2)$ 分别为 $(1,5,1,5),(1,2,2,4),(3,4,2,2),(2,4,2,2),(2,5,2,5)$，答案分别为 $15,1,1,2,6$。

输出 $(1\times 15)\ \mathrm{xor}\ (2\times 1)\ \mathrm{xor}\ (3\times 1)\ \mathrm{xor}\ (4\times 2)\ \mathrm{xor}\ (5\times 6)=24$。

**样例程序**

下面是我们提供的样例程序，你可以直接以其为基础编写你的程序。

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace Generator{
typedef unsigned long long ull;
typedef __uint128_t L;
ull seed;
int p,q;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
}F(2);
void init(){
	cin>>p>>q>>seed;//读入 p,q,seed
	assert(p!=q);
	F=FastMod(q-p+1);
}
unsigned long long rd () {
	seed ^= (seed << 13);
	seed ^= (seed >> 7);
	seed ^= (seed << 17);
	return seed;
}
void getlr(int &l1,int &r1,int &l2,int &r2){
	//将 l1,r1,l2,r2 作为参数传入，即可得到一组询问
	l1=F.reduce(rd())+p;
	r1=F.reduce(rd())+p;
	l2=F.reduce(rd())+p;
	r2=F.reduce(rd())+p;
	if(l1>r1)swap(l1,r1);
	if(l2>r2)swap(l2,r2);
}

}
int n,m,a[100005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	Generator::init();
	long long xorsum=0;
	for(int i=1,l1,r1,l2,r2;i<=m;i++){
		Generator::getlr(l1,r1,l2,r2);
		long long ans=/*ans保存你的答案*/;
		xorsum^=ans*i;
	}
	cout<<xorsum;
}
```

**数据范围**

本题有四个子任务。子任务一时间限制 $0.5$ 秒，其它子任务时间限制 $5$ 秒。

所有数据均满足：$1\le n\le 10^5$，$1\le m\le 2\times 10^7$，$1\le a_i\le 4000$，$1\le p\lt q\le 4000$，$0\le seed\lt 2^{64}$。

- 子任务 $1$（$5$ 分）：$n,m,a_i,q\le 10$。
- 子任务 $2$（$20$ 分）：$n\le 10^4$。
- 子任务 $3$（$20$ 分）：$a_i,q\le 10$。
- 子任务 $4$（$55$ 分）：无特殊限制。


title: 〈 TREEのOI 2022 Spring 〉Essential Operations

description:
你需要维护一个 $n$ 个元素的数列 $A$ ，并执行 $m$ 个操作：

- `1 l r x`：$[l,r]$ 区间全部数加 $x$；

- `2 l r x`：$[l,r]$ 区间全部数乘 $x$；

- `3 l r`：输出 $[l,r]$ 区间所有数的和 $S \bmod 19260817$ 的值；

- `4`：$A$ 数列回溯到上一次`4`操作**前**（如果不存在上一次则回溯到初始状态），同时**倒序执行**上一次回溯后到回溯前的所有`1`操作和`2`操作（见样例解释）。

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

第二行 $n$ 个整数，代表 $A$ 的初始状态。

第 $3\sim m+2$ 行：$m$ 个操作，格式见题目描述。

outputFormat: 对于每个 $3$ 操作，输出一个正整数后换行。

hint:
#### 样例解释：

##### 1

1. 初始状态 `1 2 3 4 5`；
2. `1 1 3 3` -> 此时数列为`4 5 6 4 5`；
3. `2 2 4 2` -> 此时数列为`4 10 12 8 5`；
4. `3 1 5` -> $ans=4+10+12+8+5=39$
5. `4` -> 回溯到初始状态`1 2 3 4 5` -> 依次执行`2 2 4 2`与`1 1 3 3` -> 此时数列为`4 7 9 8 5`；
6. `3 1 5` -> $ans=4+7+9+8+5=33$

##### 2

1. 初始状态 `1 1 1 1 1`
2. `1 1 3 1`: `2 2 2 1 1`
3. `2 2 4 2`: `2 4 4 2 1`
4. `4`: `2 3 3 2 1`
5. `1 1 5 1`: `3 4 4 3 2`
6. `2 1 5 2`: `6 8 8 6 4`
7. `4`: 回溯到`2 4 4 2 1`并依次执行`2 1 5 2` -> `1 1 5 1`: `5 9 9 5 3`
8. `3 1 5 2` 答案为 $31$

#### 数据范围

对于前 $10\%$ 的数据，没有 $4$ 操作。

对于前 $30\%$ 的数据，$n,m \le 10^3$。

对于前 $50\%$ 的数据，空间限制为 $400$ MB，另 $50\%$ 的数据空间限制为 $45$ MB。

对于 $100\%$ 的数据， $1 \le n \le 5 \times 10^5$，$0 \le A_i,x \le 10^3$，$1 \le m \le 10^5$ 。

d0j1a_1701 是个煽凉的出题人，所以时间限制为 $500$ ms。

---

#### 彩蛋

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

***

#### 【后记】

你穿着最新款高科技宇航服登上了月球。

那令人梦寐以求的环，就在眼前。

你缓缓走了过去。

只见环却从四周延伸出透明的屏障，里面散发出蓝绿的光芒，将你罩住。

你飞起来了！你已无法分清是你在控制环，还是环在控制你。

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

突然，一道刺眼的亮光照射了进来，你下意识地闭上了眼睛，耳旁呼呼地响。你感觉好像有风，但又不是普通的风。

突然，风停了。腿脚又站在了陆地上。睁开迷蒙的眼睛，你看见，rin 和 len 在玩一个绝对简单的游戏……


title: 「CGOI-2」No will to break

background:
-传播-由-缺失-它们-子民-思想-哦-思想-信念-

-它们-途径-缺失-切除-哦-虚空-全部-多样性-

-同族-内部-意志-缺失-容器-永远-屈服-哦-

-放-入-物质-全部-缺失-噫-空洞-壳-封印-

description:
一场战斗由 $n$ 个时刻组成，第 $i$ 个时刻有 $\frac{x_i}{x_i+y_i}$ 的概率是安全的。

在安全的时刻，你可以进行“聚集”。要求每连续的 $a$ 个时刻都至少要有 $b$ 个时刻进行聚集，在此前提下希望进行聚集的时刻数量尽量少；若不能满足此前提则认为进行聚集的时刻数量为 $0$。求进行聚集的时刻数量的期望，答案对 $998244353$ 取模。

inputFormat:
第一行输入三个整数 $n,a,b$，含义如上所述。

接下来 $n$ 行，第 $(i+1)$ 行输入两个整数 $x_i,y_i$，表示第 $i$ 个时刻有 $\frac{x_i}{x_i+y_i}$ 的概率是安全的。

outputFormat: 输出一个整数，表示期望对 $998244353$ 取模的值。

hint:
### 样例说明：

用 `1` 表示当前时刻是安全的，`0` 表示不是。

对于样例一，安全性序列只能是 `11111`，每连续三个时刻至少要有一个时刻用来聚集，可以选择第 $3$ 个时刻聚集，满足条件。聚集时刻数量为 $1$，可以证明不会小于 $1$。只有一种可能性，故期望也为 $1$。

对于样例二，安全性序列为 `100`，`101`，`110`，`111` 的概率相等，均为 $\frac14$，聚集时刻数量分别为 $0,2,1,1$，期望为 $\frac{0+2+1+1}4=1$。

---

### 数据范围：

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

| 编号| 限制 | 分数 |
| :-: | :-: | :-: |
| 0 | $n\le20$ | 10pts |
| 1 | $\forall i$，$x_i=0$ 或 $y_i=0$ | 10pts |
| 2 | $n\le3\times 10^3$ | 30pts |
| 3 | 无 | 50pts |

对于 $100\%$ 的数据，$1<n\le1.5\times10^4$，$1\le b<a\le\min(n,9)$，$x_i,y_i\ge0$，$0<x_i+y_i<998244353$。


title: 「DAOI R1」Flame

background: >尝尝天堂里的苹果有什么了不起，我要尝尝地狱里的苹果。

description:
黑暗里有黑色的火焰，只有目光敏锐的人才可以捕捉到,

借着这点卑微之光,走进地狱深处......

欢迎来到地狱的审判之地。

$ \texttt{hhpq.} $ 将 D 押入了地狱的审判之地，D 必须在业火之城成功生成一座业火监狱之前逃离，所以他想知道还有多少秒时间。

在这座业火之城中，共有 $n$ 个祭坛，共有 $m$ 条可以蔓延火苗的业火之路，且业火之路是双向连通。

已知在这一座业火之城共有 $k$ 个火种已被点燃的业火祭坛，且从第一秒开始，火种将开始从被点燃的业火祭坛向可以蔓延且未被点燃的业火祭坛蔓延。

当祭坛被点燃后，则会瞬间激活，和与之有路的祭坛连接业火圣壁。

当存在一片由业火圣壁构成的封闭图形时，则业火监狱生成成功。

### 简化题意
给出一个 $n$ 个点，$m$ 条边的无向图，每一个点有一个标记，初始有 $k$ 个点的标记为 `1`（将给出这 $k$ 个点的编号），其余的点标记为 `0`。

每一秒，对于每个标记为 `1` 的点，与它**有边相连**的点的标记都会变成 `1`。

求最少需要多少秒，图中标记为 `1` 的点与其相邻的边可以构成一个简单环。

**换言之，求最少多少秒后存在一个由 `1` 构成的集合形成简单环。**

inputFormat:
第一行三个正整数：$n,m,k$；

下面 $m$ 行，每行两个正整数：$x,y$（第 $x$ 座业火祭坛与第 $y$ 座业火祭坛有业火之路连接）；

最后一行 $k$ 个正整数：已被点燃（拥有火种）的祭坛编号。

outputFormat:
若可以逃离，输出 D 还有多少时间。

反之若无法生成业火监狱，输出 ``` Poor D! ```。


title: 「DAOI R1」Concert

background: > $ \texttt{I want to be an artist.} $

description:
$ \texttt{Erinyes} $ 的学校将举办一场音乐会，但是他若想加入其中就必须经过一场考核，试题如下：

给定两个整数 $ n,k $，表示有 $ n $ 个同学，你需要给每位同学分发一个数字，即对于整数 $ n $ 构造一个序列 $ a $。

同学得到的数字必须满足如下性质：

- 对于每个 $ i\;(1 \leq i \leq n-1) $，满足 $ a_i=\gcd(a_{i+1},a_{i+2},\dots,a_{n-1},a_n) $。
- 对于每个 $ i\;(1 \leq i \leq n) $，满足 $ 1 \leq a_i \leq 10^5 $。
- 对于每个 $ i\;(1 \leq i \leq 10^5) $，$ a_i $ 至多在序列中出现 $ k $ 次。

但这对 $ \texttt{Erinyes} $ 来说太简单了，所以他决定专心准备节目，而这个问题则将交给你。

你的任务是输出这样的序列的个数 $ l $ 以及所有这样的序列。但是由于答案可能会很大，所以我们对输出做了如下规定：

- 对于 $ l=0 $，输出 ```Impossible```。
- 对于 $ 1 \leq l \leq 4 $，输出序列实际个数，接下来 $ l $ 行，每行一个序列，表示你所构造的序列。
- 对于 $ l \geq 5 $，输出 ```5 or more```，接下来五行，每行一个序列，表示你所构造的序列中字典序最小的五个。
- 你必须按照字典序输出。

inputFormat:
第一行读入一个整数 $ t $，表示有 $ t $ 组数据。

对于每组数据，读入两个整数 $ n,k $。

outputFormat: 对于每组数据，第一行输出一个整数或一个字符串。倘若可以构造，接下来每行输出一个你所构造的字符串。

samples:
5 or more
1
2
3
4
5
Impossible
Impossible
Impossible

hint:
### 样例解释
对于第一组数据，可以发现此方案是最优解。

对于第二组数据，无论如何也无法构造出正确的序列。

对于第三组数据，无论如何也无法构造出正确的序列。

对于第四组数据，无论如何也无法构造出正确的序列。

### 数据规模
对于 $ 100\% $ 的数据，$ 1 \leq t \leq 100,1 \leq n \leq 10^5,0 \leq k \leq 10^5 $


title: 「Wdoi-2」比赤色更红的梦

background:
这里是东之国的远离人类村落的山中。博丽神社，就存在于那样的边境。

这座山，原本就没有人住，现在也是大部分人决不会踏足的地方。这里被人们称作幻想乡。

-----

一座洋馆，两次异变，揭开了幻想乡符卡战斗的序幕。

这是 118 季的夏天，从红色的西洋馆中，无数的红雾从中喷发而出，幻想乡的天染成了绯红色。博丽的巫女博丽灵梦与西洋的魔法使雾雨魔理沙察觉这片妖雾后匆忙出发。迎接她们的，是第一次在符卡规则下的异变。伴随着巨大的阴阳玉从空中砸下，摧毁了整座红魔馆，红雾异变宣告收尾，这是昔日的二色莲花蝶与黑白魔法使的表演。

但是这次，失去记忆的主角二人，遗忘了中途的种种事件，无论是那威严满满的吸血鬼，还是大图书馆中的那一串魔法阵。她们只知道，这是一次异变，急需她们解决。但是由于第一次异变的神秘性以及特殊性，她们希望你能告诉她们一共有多少个残机可以供她们挥霍。

description:
《东方红魔乡》的游戏剧情共有六关，分别称为 $\text{Stage 1}\sim \text{Stage 6}$。

当分数达到（即大于等于）$1000$ 万，$2000$ 万，$4000$ 万，$6000$ 万，会分别地奖励主角一个残机（即一条命）。此外，在 $\text{Stage 3}$ 和 $\text{Stage 5}$ 的中途，会奖励主角一个残机。主角**一开始**有 $2$ 个残机。

尽管灵梦和魔理沙二人失去了记忆，但是躲避弹幕的本能是不会被遗忘的，也就是说她们在游戏过程中不会消耗任何一个残机。现在主角**刚刚通关**了 $\text{Stage }x$，主角的分数是 $s$，请问主角现在有多少个残机？

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

- 第一行输入一个整数 $T$，表示数据组数。
- 对于每组数据，输入一行两个整数 $x$ 和 $s$。

outputFormat: - 对于每组数据，输出一行一个整数，表示主角现在拥有的残机数量。

hint:
### 样例解释

- 对于第 $1$ 组数据，主角只通过了第一关，且得分零分。故只有初始时的两个残机。
- 对于第 $2$ 组数据，主角通过了第一关，并且得到了非常多的分数，这足以让主角获得所有分数相关的残机奖励。答案为 $2$（初始时的残机）$+4$（得分奖励）$=6$ 个残机。
- 对于第 $3$ 组数据，主角把游戏通关了，但是分数非常少。主角获得了初始的两个残机、$\text{Stage 3}$ 中途的奖励残机和 $\text{Stage 5}$ 中途的奖励残机共 $4$ 个。

### 数据范围

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|c|c|}\hline
\textbf{Subtask} & \bm{x\le} & \bm{s\le} & \bm{T\le} & \textbf{分值}\\\hline
1 & 1 & 0 & 1 & 5\\\hline
2 & 6 & 0 & 100 & 10 \\\hline
3 & 6 & 10^9 & 10^4 & 10 \\\hline
4 & 6 & 10^{18} & 10^4 & 75 \\\hline
\end{array}$$

对于全部数据，满足 $1 \le T \le 10^4$，$1 \le x \le6$，$0 \le s \le 10^{18}$。


title: 「Wdoi-2」森罗结界

background:
119 季 5 月，明明本应是樱花盛开的春天，幻想乡却依然下着大雪。异变的主谋西行寺幽幽子在古书上看到，只要使妖樱西行妖满开便会有什么人复活，便出于兴趣命令妖梦收集幻想乡中的春度，一手策划成了这场异变。在收集春度的过程中散落的能量在西行妖的影响下化为樱点，散落在幻想乡各处。这一异变被称之为“春雪异变”。

出发前往解决异变的三位主角——博丽灵梦、雾雨魔理沙、十六夜咲夜怀着不同的目的，踏上了寻找异变主谋的征途。在这一过程中，她们发现了一个叫做“森罗结界”的东西。收集齐一定程度的樱点，就会立即开出森罗结界。开出森罗结界后可以短暂地屏蔽一切攻击，并且获得相应的增益。

然而，也许是因为世界秩序的 bug，如果森罗结界开得过多，数值显示将会产生问题，原本应该是一个数值的森罗结界信息会被汉字所替代。为了解决这些怪问题，她们找到了你，希望你能帮她们解决这个问题。

description:
### 简要题意

给定汉字的字符画，输入你能使用的 $\texttt{*}$ 的个数，要求输出一个**最大**的汉字数字（**可以不全部用完**），不考虑“千”、“百”等数量单位。

### 原始题意

森罗结界的信息显示系统可以看作一个宽度为 $7$，长度为无限大的矩形系统，在上面仅仅有两个字符 $\texttt{.}$ 与 $\texttt{*}$。

由于主角组失去了记忆，她们在解决异变的时候开了过多的森罗结界，使得原本应该显示数字的位置变成了汉字。在信息显示系统中，每个汉字（仅包含零、一、二到九）都以点阵字体的形式呈现。

显然，阅读汉字比阅读单纯的数字困难了许多。不过，信息显示系统告诉了主角们在显示系统上有 $n$ 个 $\texttt{*}$。主角们希望能够知道运用**不超过** $n$ 个 $\texttt{*}$ 的情况下，显示系统上能表示的最大数字是多少，来帮助她们解决异变。

为了评测和阅读的方便，您只需输出对应的整数即可。

---

如下分别给出了字符画的图片形式，以及文本形式。同时在下发文件里我们准备了每个数字对应的字符画的文本形式。

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

```plain
.......  .......  .......  *******  .......  .......  .......  .......  ..*....  *******
.......  .......  ..***..  *.*.*.*  *******  ...*...  ...*...  ..*.*..  ..*....  *.....*
.......  ..***..  .......  *.*.*.*  ...*...  ...*...  ...*...  ..*.*..  *****..  *.....*
.*****.  .......  .*****.  **...**  .******  .*****.  *******  ..*.*..  ..*.*..  *.....*
.......  .......  .......  *.....*  ...*..*  ..*.*..  ...*...  .*...*.  ..*.*..  *.....*
.......  .*****.  *******  *.....*  *******  .*...*.  ...*..*  *.....*  .*..*.*  *.....*
.......  .......  .......  *******  .......  .......  ...****  .......  *...***  *******
```

inputFormat: 输入一个正整数 $n$，表示主角组拥有的 $\texttt{*}$ 个数。

outputFormat: 输出一个整数，表示最大能够拼出的数字。由于汉字不便输出，您只需输出汉字对应的整数。

hint:
### 样例解释

对于样例 $1$，显然只能拼出数字一，故输出 $1$ 即可。

对于样例 $2$，可以拼出很多的数字如“一二”、“六”等，但是在这些数字中最大的数字是 $21$，且显然可以发现不存在更大的数字是可以被拼出的了。

### 数据范围

$$
\def\arraystretch{1.5}
\begin{array}{|c|c|c|}\hline
\textbf{Subtask} & \bm{n\le} & \textbf{分值}\\\hline
1 & 10 & 5\\\hline
2 & 100 & 15 \\\hline
3 & 10^3 & 20 \\\hline
4 & 10^6 & 60 \\\hline
\end{array}$$

对于全部数据，保证 $5 \leq n \leq 10^6$。


title: 「DAOI R1」Magic

background: > $ \text{-1,-1,+2} $

description:
乔木 来到了大魔王的面前，他决定使用魔法击败魔王。

给定一个整数 $n$，表示有 $n$ 个魔法阵，在每个魔法阵上都存在着一定的魔力值 $a_i$。

你每次可以选择三个魔法阵 $i,j,k\;(i,j,k$ 互不相同且 $a_i>0$，$a_j>0)$，然后 乔木 将会让第 $i$ 个魔法阵和第 $j$ 个魔法阵上的魔力值 $a_i,a_j$ 分别减 $1$，并让第 $k$ 个魔法阵上的魔力值 $a_k$ 加 $2$，我们将这称之为一次操作。

乔木 想要将所有的魔力汇聚到一起以发挥最大的威力。他想知道在经过若干次操作后，能否让其中 $n-1$ 个魔法阵上的魔力值为 $0$，并使汇聚的那一个魔法阵的魔力值为原魔法阵的所有魔力值之和。

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

一行输入一个数 $T$，表示数据组数。

接下来对于每组数据，先输入一个正整数 $n$，然后依次输入 $n$ 个整数，第 $i$ 个整数代表 $a_i$。

outputFormat: 对于每组数据输出一行，若可以实现，则输出 `YES`，否则输出 `NO`。

hint:
### 样例解释
- 对于第一组数据，可以将 $a_1$ 和 $a_3$ 对 $a_4$ 进行两次操作。
- 对于第二组数据，可以证明不行。

### 数据范围
- 对于 $5\%$ 的数据：$1\le n\le2$，$0\le a_i\le10^3$。
- 对于 $20\%$ 的数据：$1\le n\le10$，$0\le a_i\le10^3$。
- 对于 $100\%$ 的数据：$1\le \sum{n}\le2\times10^{6}$，$0\le a_i\le10^{9}$。

对于所有数据，保证 $1\le T\le100$ 且 $\sum\limits_{i=1}^{n} a_i \ge1$。


title: [传智杯 #4 决赛] 排排队

description:
cyq 在 tsyz 担任了体育老师，负责排队一事。

在 tsyz 中，每个人都有一个身高 $a_{i}$，并且只有**相邻**的两个人可以交换位置。cyq 带领的队伍有 $n$ 个人,他现在要给大家排队形。

给定一个长度为 $n$ 的序列 $b$，一个队形被认为美观，当且仅当对于所有的 $i = 1, 2, 3, \dots n$，$a_{i} =b_{i}$。cyq 想知道，他能否让大家的队形变得美观，并且交换相邻两个人的次数不超过 $n^2$ 次。这个问题把 $cyq$ 难住了，请你帮他来解决这个问题，如果存在合法的交换方案，输出 `YES`，并给出一组方案；否则，输出 `NO`。

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

第一行是一个整数 $T$，表示数据组数，对于每组数据：
第一行是一个整数，表示队伍的长度 $n$。
第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个人的身高 $a_i$。
第三行有 $n$ 个整数，第 $i$ 个整数表示美观队形里第 $i$ 个人的身高 $b_i$。

outputFormat:
对每组数据依次分别输出答案。

对于每组数据，若存在一种方案，则在第一行输出一个 `YES`，否则输出一个 `NO`。

如果输出 `YES`，下面则输出若干行每行两个整数 $i,j$，表示第 $i$ 个同学和第 $j$ 个同学交换位置，显然 $|i-j|=1$。在交换完成后，你还需要输出一行 `0 0` 表示你的操作结束了，请注意数组的下标从 1 开始编号至 $n$。

如果输出 `NO`，则接下来什么都不需要输出。

**请特别注意，对于每组数据，你的操作次数不能超过 $n^2$（不包括 `0 0` 一行），否则将得到 WA(Wrong Answer) 的结果**。

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

对于全部的测试点，保证 $1\leq T \leq 10$，$1\leq n \leq 10^3$，$1\leq a_{i},b_{i}\leq 10^9$，且各个测试点 $n$ 之和不超过 $1000$，即 $\sum n\leq 10^3$。

### 提示
- 请注意大量的输出输出对程序效率造成的影响，不要频繁刷新缓冲区。例如，对于使用 `std::cout` 的 C++ 选手，请使用 `'\n'` 而不是 `std::endl` 来换行；对于 java 选手，请选择高效率的输出方式，如使用 PrintWriter；python 选手可以正常的使用 print 而无需考虑效率问题。
- 请按照输出格式的要求输出您的答案，如果格式不符合要求，返回的评测信息将可能是 TLE、RE、WA、UKE 等任何结果。

### C++ 语言的高效输出样例
```cpp
#include <iostream>
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  for (int i = 1; i <= 5; ++i) {
    std::cout << i << '\n'; // 注意这里不能使用 std::endl
  }
}
```

### Java 语言的高效输出样例
```java
import java.io.PrintWriter;

public class Main {
  public static void main(String[] args) {
    PrintWriter ot = new PrintWriter(System.out);
    for (int i = 1; i <= 5; ++i) {
      ot.println(i);
    }
    ot.flush(); // 请务必保证在程序结束时运行本条语句，否则在缓冲区的内容无法输出
  }
}


title: [传智杯 #4 决赛] 三元组

description:
给定一个长度为 $n$ 的数列 $a$，对于一个有序整数三元组 $(i, j, k)$，若其满足 $1 \leq i \leq j \leq k \leq n$ 并且 $a_i +a_j  = a_k$，则我们称这个三元组是「传智的」。

现在请你计算，有多少有序整数三元组是传智的。

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

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

对于每组数据：

第一行是一个整数，表示数列的长度 $n$。
第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

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


title: [传智杯 #4 决赛] 生活在树上（easy version）

background:
**本题是 P8201 的简单版本，两道题目的解法略有不同。本题和 P8201 在题意上的区别在于本题给定树上的边权，而不是点权。**

小智生活在「传智国」，这是一个有 $n$ 个城市的国家，各个城市由 $n-1$ 条道路相连。

每个道路都有长度 $w_i$ ，我们定义，小智从城市 $a$ 走到城市 $b$ 的代价是 $\mathrm{dis}_{a, b} = \bigoplus \limits_{e \in \mathrm{path}\left(a, b\right)} w_e$，其中 $\bigoplus$ 表示**按位异或**（如果你不知道什么是**按位异或**，请参见题目下方的提示/说明），$\mathrm{path}\left(a,b\right)$ 表示 $a$ 到 $b$ 的简单路径上的边集。也即 $\mathrm{dis}_{a, b}$ 表示将 $a$ 与 $b$ 的简单路径上所有边写作 $e_1, e_2, e_3, \dots$ 后，求 $w_{e_1} \bigoplus w_{e_2}\bigoplus w_{e_3} \dots$ 的结果。

有一天，小智获得了去参加传智杯的机会，他在前往比赛地的路上想到了一个问题，但他好像不会做，于是他把这个题告诉了你。聪明的同学，你可以帮帮他吗？

description:
小智说：「由于我们的国家只有 $n$ 个城市和 $n-1$ 条道路，那么我们的国家就相当于是一棵树。我在想，在我们的国家中，是否有城市满足『到城市 $a$ 的代价和到城市 $b$ 的代价的异或等于 $k$』。好难哦，我想不出来，你能帮帮我吗？」

也就是说，给定城市 $a, b$ 和整数 $k$，请你计算是否存在城市 $t$ 满足 $\mathrm{dis}_{t, a} \bigoplus \mathrm{dis}_{t, b} = k$。

inputFormat:
第一行有两个整数 $n$，$m$，表示国家的城市数和询问的个数。

接下来 $n-1$ 行，每行有两个整数 $x, y, l$，表示城市 $x$ 与城市 $y$ 有一条长度为 $l$ 的边。

接下来 $m$ 行，每行有三个整数 $a, b, k$，表示小智从城市 $a$ 走到城市 $b$，$k$ 的含义与题目描述一致。

outputFormat:
共 $m$ 行，每行一个整数。

对于第 $i$ 个询问，如果存在至少一个城市 $t$ 满足要求，则输出 `Yes`。

如果不存在任何一个城市满足条件，则输出 `No`。

输出字符串大小写不敏感，例如，`Yes`、`yES`、`YES`、`yes` 等都算作 `Yes`。

hint:
### 相关概念解释
「树」：树是一个有 $n$ 个结点和 $n-1$ 条边的无向简单连通图。

「按位异或」：按位异或即 C++、python、java 语言中的 「^」 运算。它是一个二元运算，步骤是将两个数的二进制位按位比较，相同为 $0$，不同为 $1$。例如：$3 \bigoplus 5 = (011)_2 \bigoplus (101)_2 = (110)_2 = 6$。**请注意，这是一个按位运算，不是一个逻辑运算**。
### 样例 1 解释
下图为传智国的地图。

$\forall t \in \{1, 2, 3, 4, 5\}$，都不可能有 $\mathrm{dis} _{t,1} \bigoplus \mathrm{dis}_{t, 2} = 4$，$\mathrm{dis}_{t, 2} \bigoplus \mathrm{dis}_{t, 3} = 12$，于是输出 `No`；

而取 $t = 5$，有 $\mathrm{dis}_{t, 1} \bigoplus \mathrm{dis}_{t, 4} = 10$，于是输出 `Yes`。

![](https://cdn.luogu.com.cn/upload/image_hosting/9ikzjfh3.png)
### 数据规模与约定
对于所有测试点，保证 $1 < n \leq 5 \times 10^5$，$1 \leq m \leq 5 \times 10^5$，$0 \leq w_i < 2^{64}$。

对于每次询问，保证 $1 \leq a, b \leq n$ 且 $a \neq b$，$0 \leq k < 2^{64}$。


title: [传智杯 #4 决赛] [yLOI2021] 染色

background: 传智杯 2021 决赛 G 题。

description:
传智专修学院的老师给小智布置了一项任务。

老师给了小智一张纸，上面画着一棵有 $n$ 个节点的树（如果你不知道什么是树，可以参考上一题对此的解释）。老师还给了小智 $m$ 支彩色笔，每支笔的颜色都是不同的。老师想要让小智用这 $m$ 种颜色给树的节点涂色，使得这棵树满足如下约束：

1. 每个节点都被涂上了这 $m$ 个颜色之一的**一种**颜色。
2. 相邻两个节点（若存在一条边直接连接 $u$ 和 $v$，则我们称 $u,v$ 相邻）的颜色是不同的。
3. 任何一种颜色被使用的次数都不能超过 $\lfloor\frac{n}{3}\rfloor + 1$。

需要指出的是，虽然每个节点都必须被涂上一种颜色，但是每个颜色并不必须被使用。

如此简单的任务难不倒小智，所以小智提出了一个更困难的问题：他想知道一共有多少种染色的方案满足老师的要求。小智不会解答这个问题，所以来求助你，请你帮他解决他的问题。

因为方案数可能非常大，你只需要输出这个方案数除以 $998,244,353$ 的余数。两种染色方案不同当且仅当存在一个节点 $u$，使得 $u$ 在两种方案种被染上的颜色不同。

inputFormat:
第一行是两个整数，依次表示树的节点数 $n$ 和颜色的个数 $m$。
接下来 $(n - 1)$ 行，每行两个整数 $u, v$，表示树上有一条连接 $u, v$ 的边。

outputFormat: 输出一行一个整数，表示方案数除以 $998,244,353$ 的余数。

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

对于全部的测试点，保证 $1 \leq u, v \leq n\leq 100$，$n \leq m \leq 10^6$，保证给出的是一棵树。

### 提示

**请注意常数因子对程序效率造成的影响**。


title: [USACO22FEB]  Paint by Rectangles P

background: 翻译来自 @wlzhouzhuan。

description:
在她之前的作品受到好评后，Bessie 得到了一份设计绘画套装的工作。她通过在平面中选择 $N\ (1\le N\le 10^5)$ 个平行于坐标轴的矩形来设计该画作，没有两条边是共线的。这些矩形的边界定义了绘画着色区域的边界。

作为一名先锋艺术家，Bessie 觉得这幅画应该像一头荷斯坦奶牛。更具体地，由矩形构成的每个区域都被着色为黑色或白色，没有两个相邻区域具有相同的颜色，并且所有矩形之外的区域都被着色为白色。

选完矩形后，Bessie 想根据参数 $T$ 让你输出：

- 若 $T=1$，则输出区域总数；
- 若 $T=2$，则依次输出白色区域数量和黑色区域数量。

**注意：本题的时间限制为 4s，是默认的 2 倍。**

inputFormat:
第一行，输入 $N$ 和 $T$。

接下来 $N$ 行，每行读入 $x_1,y_1,x_2,y_2$，表示一个左下角为 $(x_1,y_1)$，右上角为 $(x_2,y_2)$ 的矩形。

数据保证 $x_i$ 形成了一个 $1\sim 2N$ 的排列，$y_i$ 同理。

outputFormat: 若 $T=1$，输出一个整数；否则输出两个整数，用空格隔开。

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

有 $2$ 个白色区域和 $2$ 个黑色区域，共有 $4$ 个区域。所有矩形的边界连通，因此该输入满足 subtask 3。

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

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

右上方的矩形不与其余的矩形连通，因此该输入不满足 subtask 4。

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

**【数据范围】**

- subtask 1：数据 $3\sim 4$ 满足 $N\le 10^3$；
- subtask 2：数据 $5\sim 7$ 满足不存在两个矩形相交；
- subtask 3：数据 $8\sim 10$ 满足 $T=1$，且所有矩形的边界连通；
- subtask 4：数据 $11\sim 13$ 满足 $T=2$，且所有矩形的边界连通；
- subtask 5：数据 $14\sim 18$ 满足 $T=1$；
- subtask 6：数据 $19\sim 23$ 满足 $T=2$。


title: [USACO22FEB] Sleeping in Class B

description:
Bessie the cow was excited to recently return to in-person learning! Unfortunately, her instructor, Farmer John, is a very boring lecturer, and so she ends up falling asleep in class often.
Farmer John has noticed that Bessie has not been paying attention in class. He has asked another student in class, Elsie, to keep track of the number of times Bessie falls asleep in a given class. There are $N$ class periods $(1\le N\le 10^5)$, and Elsie logs that Bessie fell asleep $a_i$ times $(0\le a_i\le 10^6)$ in the $i$-th class period. The total number of times Bessie fell asleep across all class periods is at most $10^6$.

Elsie, feeling very competitive with Bessie, wants to make Farmer John feel like Bessie is consistently falling asleep the same number of times in every class -- making it appear that the issue is entirely Bessie's fault, with no dependence on Farmer John's sometimes-boring lectures. The only way Elsie may modify the log is by combining two adjacent class periods. For example, if $a=[1,2,3,4,5]$, then if Elsie combines the second and third class periods the log will become $[1,5,4,5]$.

Help Elsie compute the minimum number of modifications to the log that she needs to make so that she can make all the numbers in the log equal.

inputFormat:
Each input will contain $T$ $(1\le T\le 10)$ test cases that should be solved independently.

The first line contains $T$, the number of test cases to be solved. The $T$ test cases follow, each described by a pair of lines. The first line of each pair contains $N$, and the second contains $a_1,a_2,\ldots,a_N$.

It is guaranteed that within each test case, the sum of all values in $a$ is at most $10^6$. It is also guaranteed that the sum of $N$ over all test cases is at most $10^5$.

outputFormat: Please write $T$ lines of output, giving the minimum number of modifications Elsie could perform to make all the log entries equal for each case.

translation:
$T$ 组数据，每组给定一个长度为 $N$ 的数组 $a_1, a_2, \dotsb , a_n$。

每次操作可选择两个相邻的数合并，得到的新数为两者之和。

求最少操作次数使得所有数相等。

数据范围： $1 \leq T \leq 10$，$\sum a_i \leq 10^6$，$\sum N \leq 10^5$，$1 \le T \le 10$。

**【输入格式】**

一行一个整数 $T$。

接下来 $T$ 组数据，每组数据第一行一个整数 $N$，第二行 $N$ 个整数，$a_1, a_2, \dotsb , a_n$，含义如题目描述。

**【输出格式】**

$T$ 行，每行一个整数，表示最少操作次数。可证明总存在一种操作满足题意。

**【样例解释】**

对于样例 $1$，显然可以通过如下 $3$ 次操作将原序列变成 `3 3 3`：

```plain
   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3
```

对于样例 $2$，显然可以通过如下 $2$ 次操作将原序列变成 `7`：

```plain
   2 2 3
-> 2 5
-> 7
```

对于样例 $3$，显然无需操作。

hint:
【样例解释】

For the first test case in this example, Elsie can change her log to consist solely of 3s with 3 modifications.
```
   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3
```
For the second test case, Elsie can change her log to 7 with 2 modifications.
```
   2 2 3
-> 2 5
-> 7
```
For the last test case, Elsie doesn’t need to perform any operations; the log already consists of equal entries.


title: [USACO22FEB]  Photoshoot 2 B

description:
In what seems to be a familiar occurrence, Farmer John is lining up his $N$ cows $(1\le N\le 10^5)$, conveniently numbered $1\cdots N$, for a photograph.
Initially, the cows are lined up in the order $a_1,a_2,\cdots ,a_N$ from left to right. Farmer John's goal is to line up the cows in the order $b_1,\cdots ,b_N$ from left to right. To accomplish this, he may perform a series of modifications to the ordering. Each modification consists of choosing a single cow and moving it some number of positions to the left.

Please count the minimum number of modifications required in order for Farmer John to line up his cows in the desired order.

inputFormat: The first line of input contains $N$. The second line contains $a_1,a_2,\cdots ,a_N$. The third line contains $b_1,\cdots ,b_N$.

outputFormat: Print the minimum number of modifications required to produce Farmer John's desired ordering.

translation:
## 题目描述
在一个似曾相识的场景中，Farmer John 正在将他的 $N$ 头奶牛$（1\leq N\leq 10^5）$排成一排（为了方便将它们按 $1\cdots N$ 编号），以便拍照。

最初，奶牛从左到右按照 $a_1,a_2,\cdots,a_N$ 的顺序排列。Farmer John 的目标是按照 $b_1,\cdots,b_N$ 从左到右的顺序排列奶牛。为此，他可以对排列顺序进行一系列修改。每次修改为选择一头奶牛并将其向左移动一些位置。

请计算农民约翰按所需顺序排列奶牛所需的最少修改次数。
## 输入格式
输入的第一行包含 $N$，第二行包含 $a_1,a_2,\cdots,a_N$，第三行包含 $b_1,b_2,\cdots,b_N$ 。
## 输出格式
输出产生 Farmer John 所需顺序所需的最少修改次数。
## 数据范围
测试用例 $3\sim 6$ 满足 $N\leq 100$

测试用例 $7\sim 10$ 满足 $N\leq 5000$

测试用例 $11\sim 14$ 不满足额外的约束。

### 样例解释1
在此示例中，奶牛已按所需顺序排列，因此无需修改。

### 样例解释2
在这个例子中，两个修改就足够了。 这是 Farmer John 重新排列奶牛的一种方法：

$1.$选择奶牛 $4$ 并将其向左移动四个位置。

$2.$选择奶牛 $2$ 并将其向左移动两个位置。

hint:
【样例解释 1】

In this example, the cows are already in the desired order, so no modifications are required.

【样例解释 2】

In this example, two modifications suffice. Here is one way Farmer John can rearrange his cows:

- Choose cow $4$ and move it four positions to the left.
- Choose cow $2$ and move it two positions to the left.
```
   5 1 3 2 4
-> 4 5 1 3 2
-> 4 5 2 1 3
```

【数据范围】

- Test cases 3-6 satisfy $N≤100$.
- Test cases 7-10 satisfy $N≤5000$.
- Test cases 11-14 satisfy no additional constraints.


title: [USACO22FEB] Blocks B

description:
In an effort to improve her vocabulary, Bessie the cow has obtained a set of four wooden blocks, each one a cube with a letter of the alphabet written on each of its six sides. She is learning how to spell by arranging the blocks in a row so the letters on top of the blocks spell words.

Given the letters on each of Bessie's four blocks, and a list of words she would like to spell, please determine which of words on her list she will be able to spell successfully using the blocks.

inputFormat: The first line of input contains $N$ $(1\le N\le 10)$, the number of words that Bessie would like to spell. The next four lines each contain a string with six uppercase letters, representing the letters on the six sides of one of Bessie's blocks. The next $N$ lines contain the $N$ words Bessie would like to spell. Each of these is between 1 and 4 uppercase letters long.

outputFormat: For each word on Bessie's list, output YES if she is able to spell it using the blocks and NO otherwise.

translation:
## 题目描述
为了提高词汇量，母牛贝西得到了一套四块木块，其中每块都是一个立方体，六面各写着一个字母。她正在通过将木块排成一排使得木块顶部的字母拼出单词来学习拼写。

给定 Bessie 的四个木块上的字母，以及她想拼写的单词列表，请确定列表中哪些单词可被她使用木块成功拼写。
## 输入格式
输入的第一行包含 $N (1\leq N\leq 10)$，为 Bessie 想要拼写的单词数。接下来的四行每行包含一个带有六个大写字母的字符串，表示 Bessie 的一个块的六个侧面上的字母。接下来的 $N$ 行包含 Bessie 想要拼写的 $N$ 个单词。其中每一个的长度在 $1$ 到 $4$ 个大写字母之间。
## 输出格式
对于 Bessie 列表中的每个单词，如果她能够使用木块拼写，则输出 YES，否则输出 NO。
## 样例解释
在本例中，Bessie 可以拼写 COW、ZOO 和 MOVE。 不幸的是，她不能拼写 MOO，因为唯一带有 M 的木块也不能用于 O。她不能拼写 FARM，因为没有字母 R 的木块。她不能拼写 CODE，因为 C、D 和 E 都属于同一个木块。

samples:
6
MOOOOO
OOOOOO
ABCDEF
UVWXYZ
COW
MOO
ZOO
MOVE
CODE
FARM

hint:
【样例解释】

In this example, Bessie can spell COW, ZOO, and MOVE. Sadly, she cannot spell MOO, since the only block with an M cannot also be used for an O. She cannot spell FARM since there is no block with a letter R. She cannot spell CODE since the C, D, and E all belong to the same block.


title: [USACO22FEB] Redistributing Gifts S

description:
Farmer John has $N$ gifts labeled $1\cdots N$ for his $N$ cows, also labeled $1\cdots N$ $(1\le N\le 500)$. Each cow has a wishlist, which is a permutation of all $N$ gifts such that the cow prefers gifts that appear earlier in the list over gifts that appear later in the list.

FJ was lazy and just assigned gift $i$ to cow $i$ for all $i$. Now, the cows have gathered amongst themselves and decided to reassign the gifts such that after reassignment, every cow ends up with the same gift as she did originally, or a gift that she prefers over the one she was originally assigned.

For each $i$ from $1$ to $N$, compute the most preferred gift cow $i$ could hope to receive after reassignment.

inputFormat: The first line contains $N$. The next $N$ lines each contain the preference list of a cow. It is guaranteed that each line forms a permutation of $1\cdots N$.

outputFormat: Please output $N$ lines, the $i$-th of which contains the most preferred gift cow $i$ could hope to receive after reassignment.

translation:
# 题目描述
FJ 有 $N$ 个礼物给他的 $N$ 头奶牛，这 $N$ 个礼物和 $N$ 头奶牛都被标记为 $1 \dotsm N (1 \le N \le 500)$ 。 每头奶牛都有一个愿望单，记录着一个含有 $N$ 个礼物的排列。比起在愿望单中出现更晚的礼物，奶牛更喜欢先出现在愿望单中的礼物。

因为 FJ 太懒了，他直接把 $i$ 号礼物分配给了 $i$ 号奶牛。现在，奶牛们聚在了一起，决定重新分配礼物，以便在重新分配后，每头奶牛都能得到跟原来一样，或是它更喜欢的礼物。

对于每个 $i$ （$i$ 从 $1$ 到 $N$），计算出重新分配后， $i$ 号奶牛可能拿到的最好的礼物（这个奶牛经过重新分配后能拿到的最喜欢的礼物）。

# 输入格式
第一行输入 $N$ 。之后 $N$ 行每行包含一个奶牛的愿望单。保证这 $N$ 行都是 $1 \dotsm N$ 的排列

# 输出格式
输出 $N$ 行，第 $i$ 行输出重新分配后 $i$ 号奶牛可能得到的最好礼物。

# 样例解释
在这个例子中，有两种可能的分配方案
- 最初的方案：一号奶牛得到一号礼物，二号奶牛得到二号礼物，三号奶牛得到三号礼物，四号奶牛得到四号礼物
- 重新分配后的方案：一号奶牛得到一号礼物，二号奶牛得到三号礼物，三号奶牛得到二号礼物，四号奶牛得到四号礼物。可以发现一号和四号奶牛都拿不到比FJ分配的更好的礼物。不过二号和三号都可以。

# 数据范围
- $2 \sim 3$ 号测试点满足 $N \le 8$
- $4 \sim 11$ 号测试点没有别的限制

由 [tzyt](https://www.luogu.com.cn/user/394488) 翻译

hint:
【样例解释】

In this example, there are two possible reassignments:

- The original assignment: cow 1 receives gift 1, cow 2 receives gift 2, cow 3 receives gift 3, and cow 4 receives gift 4.
- Cow 1 receives gift 1, cow 2 receives gift 3, cow 3 receives gift 2, and cow 4 receives gift 4.
Observe that both cows 1 and 4 cannot hope to receive better gifts than they were originally assigned. However, both cows 2 and 3 can.

【数据范围】

- Test cases 2-3 satisfy $N\le 8$.

- Test cases 4-11 satisfy no additional constraints.


title: [USACO22FEB]  Robot Instructions S

description:
Bessie is learning how to control a robot she has recently received as a gift.
The robot begins at point $(0,0)$ on the coordinate plane and Bessie wants the robot to end at point $(x_g,y_g)$. Bessie initially has a list of $N$ $(1\le N\le 40)$ instructions to give to the robot, the $i$-th of which will move the robot $x_i$ units right and $y_i$ units up (or left or down when $x_i$ and $y_i$ are negative, respectively).

For each $K$ from $1$ to $N$, help Bessie count the number of ways she can select $K$ instructions from the original $N$ such that after the $K$ instructions are executed, the robot will end at point $(x_g,y_g)$.

**Note: the time and memory limits for this problem are 4s and 512MB, twice the defaults.**

inputFormat:
The first line contains $N$. The next line contains $x_g$ and $y_g$, each in the range $−10^9\cdots 10^9$. The final $N$ lines describe the instructions. Each line has two integers $x_i$ and $y_i$, also in the range $−10^9\cdots 10^9$.

It is guaranteed that $(x_g,y_g)\neq (0,0)$ and $(x_i,y_i)\neq (0,0)$ for all $i$.

outputFormat: Print $N$ lines, the number of ways Bessie can select $K$ instructions from the original $N$ for each $K$ from $1$ to $N$.

translation:
## 题目描述
贝西正在学习如何控制她最近作为礼物收到的机器人。

机器人初始在坐标平面上的点 $(0,0)$，Bessie 希望机器人在点 $(x_g,y_g)$ 停止。 Bessie 最初有一个包含 $N(1\leq N \leq 40)$ 条指令的指令列表给机器人，其中第 $i$ 个指令将向右移动机器人 $x_i$
  单位和向上移动 $y_i$
  单位（或者当 $x_i$ 和 $y_i$ 为负数时分别向左或向下移动）。

对于从 $1$ 到 $N$ 的每个 $K$，帮助 Bessie 计算她可以从原始 $N$ 中选择 $K$ 条指令的方案数，使得在执行 $K$ 条指令后，机器人将在点 $(x_g,y_g)$ 处停止。

## 输入格式
第一行包含 $N$ 。下一行包含 $x_g$ 和 $y_g$，每个数都在 $-10^9\dots 10^9$ 的范围内。最后的 $N$ 行描述了指令。每行有两个整数 $x_i$ 和 $y_i$，也在 $-10^9\dots 10^9$ 范围内。

保证 $(x_g,y_g)\neq (0,0)$ 和对于所有的 $i，(x_i,y_i)\neq (0,0)$。

## 数据范围
数据 $2\sim 4$ 满足 $N\leq 20$。

数据 $5\sim 16$ 无额外约束。

### 样例解释
在此示例中，Bessie 可以通过六种方式选择指令：
```
(-2,0) (3,0) (4,0) (0,10) (0,-10) (0,10) (1 2 3 5 6 7)

(-2,0) (3,0) (4,0) (0,10) (1 2 3 5)

(-2,0) (3,0) (4,0) (0,10) (1 2 3 7)

(5,0) (0,10) (0,-10) (0,10) (4 5 6 7)

(5,0) (0,10) (4 5)

(5,0) (0,10) (4 7)
```
对于第一种方式，机器人的路径如下所示：

$(0,0) \to (-2,0) \to (1,0) \to (5,0) \to (5,10) \to (5,0) \to (5,10)$


title: [USACO22FEB] Email Filing S

description:
Farmer John has fallen behind on organizing his inbox. The way his screen is organized, there is a vertical list of folders on the left side of the screen and a vertical list of emails on the right side of the screen. There are $M$ total folders, numbered $1 \ldots M$ $(1 \le M \le 10^4)$. His inbox currently contains $N$ emails numbered $1\ldots N$ $(1 \le N \le 10^5)$; the $i$th email needs to be filed into folder $f_i$ $(1\le f_i\le M)$.

FJ's screen is rather small, so he can only view $K$ $(1\le K\le \min(N,M))$ folders and $K$ emails at once.  Initially, his screen starts out displaying folders
$1 \ldots K$ on the left and emails $1 \ldots K$ on the right. To access other folders and emails, he needs to scroll through these respective lists. For example, if he scrolls down one position in the list of folders, his screen will display folders $2 \ldots K+1$, and then scrolling down one position further it will display folders $3 \ldots K+2$.  When FJ drags an email into a folder, the email disappears from the email list, and the emails after the one that disappeared shift up by one position.  For example, if emails $1, 2, 3, 4, 5$ are currently displayed and FJ drags email 3 into its appropriate folder, the email list will now show emails $1, 2, 4, 5, 6$. FJ can only drag an email into the folder to which it needs to be filled.

Unfortunately, the scroll wheel on FJ's mouse is broken, and he can only scroll downwards, not upwards.  The only way he can achieve some semblance of upward scrolling is if he is viewing the last set of $K$ emails in his email list, and
he files one of these.  In this case, the email list will again show the last $K$ emails that haven't yet been filed, effectively scrolling the top email up by one. If there are fewer than $K$ emails remaining, then all of them will be
displayed.

Please help FJ determine if it is possible to file all of his emails.

inputFormat:
The first line of input contains $T$ $(1≤T≤10)$, the number of subcases in this input, all of which must be solved correctly to solve the input case. The $T$ subcases then follow. For each subcase, the first line of input contains $M,N$ and $K$. The next line contains $f_1\cdots f_N$.

It is guaranteed that the sum of $M$ over all subcases does not exceed $10^4$, and that the sum of $N$ over all subcases does not exceed $10^5$.

outputFormat: Output $T$ lines, each one either containing either YES or NO, specifying whether FJ can successfully file all his emails in each of the $T$ subcases.

translation:
# 题目描述
 $Farmer John$ 在整理收件箱方面已经落后了。他的屏幕排列方式是，屏幕左侧有一个垂直的文件夹列表，屏幕右侧有一个垂直的电子邮件列表。共有 $M$ 个文件夹，编号为 $1 \dotsm M (1 \le M \le 10^4)$ 。他的收件箱当前包含 $N$ 封编号为 $1 \dotsm N (1 \le N \le 10^5)$
 的电子邮件；第 $i$ 封电子邮件需要归档到文件夹 $f_i (1 \le f_i \le M) $。

 $FJ$ 的屏幕有些小，所以他同时只能查看 $K(1 \le M \le min(n,m))$个文件夹和 $K$ 封电子邮件。最初，他的屏幕左侧显示文件夹 $1 \dotsm K$，右侧显示电子邮件 $1 \dotsm K$。要访问其他文件夹和电子邮件，他需要滚动相应的列表。例如，如果他将文件夹列表向下滚动一个位置，他的屏幕将显示文件夹 $2 \dotsm K+1$，然后再向下滚动一个位置将显示文件夹 $3 \dotsm K+2$。当 $FJ$ 将一封电子邮件拖曳至一个文件夹时，该电子邮件将从电子邮件列表中消失，并且消失的电子邮件之后的电子邮件会向上移动一个位置。例如，如果当前显示的是电子邮件 $1,2,3,4,5$，然后 $FJ$ 将电子邮件 $3$ 拖曳至其对应的文件夹中，则电子邮件列表现在将显示电子邮件 $1,2,4,5,6$。$FJ$ 只可以将电子邮件拖曳至其需要归档的文件夹中。

 不幸的是，$FJ$ 的鼠标滚轮坏了，所以他只能向下滚动，不能向上滚动。他可以实现类似向上滚动的唯一情况是，他正在查看他的电子邮件列表中的最后 $K$ 封电子邮件，并且他归档了其中的一封。在这种情况下，电子邮件列表将再继续显示尚未归档的最后 $K$ 封电子邮件，实际上使得最上方的电子邮件向上滚动了一个位置。如果剩余少于 $K$ 封电子邮件，则将显示所有电子邮件。

 请帮助 $FJ$ 判断是否可能归档他的所有电子邮件。

 # 输入格式
输入的第一行包含 $T (1 \le T \le 10)$，为当前测试用例中的子测试用例数量，所有子测试用例必须全部正确才能通过当前测试用例。以下是 $T$ 个子测试用例。每一个子测试用例的第一行包含 $M$，$N$ 和 $K$。第二行包含 $f_1…f_N$。

输入保证所有子测试用例的 $M$ 之和不超过 $10^4$，所有子测试用例的 $N$ 之和不超过 $10^5$。

# 输出格式
输出 $T$ 行，每行包含 "YES" 或 "NO"，表示对于 $T$ 个子测试用例中的每一个，$FJ$ 是否可以成功归档他的所有电子邮件。

# 数据范围
- 测试点 2-10 中，所有子测试用例的 $M$ 之和不超过 $10^3$。
- 测试点 11-12 没有额外限制。

hint:
【数据范围】

- In inputs 2-10, the sum of $M$ over all subcases does not exceed $10^3$.
- In inputs 11-12, no additional constraints.


title: [USACO22FEB] Redistributing Gifts G

description:
Farmer John has $N$ gifts labeled $1…N$ for his $N$ cows, also labeled $1…N$ $(1≤N≤18)$. Each cow has a wishlist, which is a permutation of all $N$ gifts such that the cow prefers gifts that appear earlier in the list over gifts that appear later in the list.

FJ was lazy and just assigned gift $i$ to cow $i$ for all $i$. Now, the cows have gathered amongst themselves and decided to reassign the gifts such that after reassignment, every cow ends up with the same gift as she did originally, or a gift that she prefers over the one she was originally assigned.

There is also an additional constraint: a gift may only be reassigned to a cow if it was originally assigned to a cow of the same type (each cow is either a Holstein or a Guernsey). Given $Q$ $(1≤Q≤min(10^5,2^N))$ length-$N$ breed strings, for each one count the number of reassignments that are consistent with it.

inputFormat:
The first line contains $N$.
The next $N$ lines each contain the preference list of a cow. It is guaranteed that each line forms a permutation of $1…N$.

The next line contains $Q$.

The final $Q$ lines each contain a breed string, each $N$ characters long and consisting only of the characters G and H. No breed string occurs more than once.

outputFormat: For each breed string, print the number of reassignments that are consistent with it on a new line.

translation:
Farmer John 给他的 $N(1\leq N \leq 18)$ 头奶牛们准备了 $N$ 个礼物，每头奶牛有一个排列 $a$，表示该奶牛对第 $a_i$ 个礼物的“喜好程度”为 $i$。

起初第 $j$ 头牛手上有第 $j$ 号礼物。

现有 $Q(1\leq Q \leq min(10^5,2^N))$ 次询问，每次给出仅含 'H' 或 'G' 的字符串，表示每头奶牛的品种，并询问在同品种奶牛可以互相交换礼物的情况下，满足任意一头牛对交换后礼物的“喜好程度”都小于等于其对原先礼物的“喜好程度”的交换方案数。

samples:
4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG

hint:
【样例解释】

In this example, for the first breed string, there are two possible reassignments:

- The original assignment: cow $1$ receives gift $1$, cow $2$ receives gift $2$, cow $3$ receives gift $3$, and cow $4$ receives gift $4$.
- Cow $1$ receives gift $1$, cow $2$ receives gift $3$, cow $3$ receives gift
$2$, and cow $4$ receives gift $4$.

【数据范围】

- For $T=2,\cdots ,13$, test case T satisfies $N=T+4$.
- Test cases 14-18 satisfy $N=18$.


title: [USACO22FEB] Cow Camp G

description:
To qualify for cow camp, Bessie needs to earn a good score on the last problem of the USACOW Open contest. This problem has $T$ distinct test cases $(2≤T≤10^3)$ weighted equally, with the first test case being the sample case. Her final score will equal the number of test cases that her last submission passes.
Unfortunately, Bessie is way too tired to think about the problem, but since the answer to each test case is either "yes" or "no," she has a plan! Precisely, she decides to repeatedly submit the following nondeterministic solution:
```
if input == sample_input:
  print sample_output
else:
  print "yes" or "no" each with probability 1/2, independently for each test case
```
Note that for all test cases besides the sample, this program may produce a different output when resubmitted, so the number of test cases that it passes will vary.

Bessie knows that she cannot submit more than $K$ $(1≤K≤10^9)$ times in total because then she will certainly be disqualified. What is the maximum possible expected value of Bessie's final score, assuming that she follows the optimal strategy?

inputFormat: The only line of input contains two space-separated integers $T$ and $K$.

outputFormat: The answer as a decimal that differs by at most $10^{−6}$ absolute or relative error from the actual answer.

translation:
# [USACO22FEB] Cow Camp G

## 题目描述
为了有资格参加奶牛夏令营，贝西需要在USACOW公开赛的最后一道题上取得好成绩。这个问题有$T$个不同的测试点，这些测试点范围在$（2≤T≤10^3）$，第一个测试点为样本用例。她的最终分数将等于她上一次提交通过的测试点数。

但是，贝西太累了，无法思考这个问题，由于每个测试点的答案要么是“yes”，要么是“no”，她有一个计划！确切地说，她决定反复提交以下不确定的解决方案：
```
if input == sample_input:
  print sample_output
else:
  print "yes" or "no" each with probability 1/2, independently for each test case
```
但请注意，对于除示例之外的所有测试点，重新提交时，此程序可能会产生不同的输出，因此它通过的测试用例数量会有所不同。
贝西知道她提交的样例不能超过$K （1≤K≤10^9）$次，因为那样她肯定会被取消资格。假设贝西遵循最佳策略，她最终得分的最大可能期望值是多少？

## 输入格式

第一行输入包含两个空格分隔的整数$T$和$K$

## 输出格式

答案为小数，最多相差$10^{−6}$。
## 提示

【样例解释 1】

在样例中，贝西应继续重新提交，直到她提交了3份意见书或获得全额学分。贝西将获得概率为$\frac 78$的全学分和概率为$\frac 18$的半学分，因此贝西在该策略下的最终得分预期值为$\frac 78\cdot 2+\frac 18\cdot 1=\frac{15}{8}=1.875$。正如我们从这个公式中看到的，贝西分数的期望值可以通过取$p（x）\cdot x$中超过$x$的总和来计算，其中$p（x）$是获得$x$分数的概率。

【样例解释 2】

在这个样例中，如果贝西第一次通过的测试用例少于3个，她应该只提交两次。

【数据范围】

- 测试样例3-6满足$T≤25$和$K≤100$

- 测试样例7-9满足$K≤10^6$

- 测试样例10-17不满足其他约束.

hint:
【样例解释 1】

In this example, Bessie should keep resubmitting until she has reached 3 submissions or she receives full credit. Bessie will receive full credit with probability $\frac 78$ and half credit with probability $\frac 18$, so the expected value of Bessie's final score under this strategy is $\frac 78\cdot 2+\frac 18\cdot 1=\frac {15}{8}=1.875$. As we see from this formula, the expected value of Bessie's score can be calculated by taking the sum over $x$ of $p(x)\cdot x$, where $p(x)$ is the probability of receiving a score of $x$.

【样例解释 2】

Here, Bessie should only submit twice if she passes fewer than 3 test cases on her first try.

【数据范围】

- Test cases 3-6 satisfy $T≤25$ and $K≤100$.
- Test cases 7-9 satisfy $K≤10^6$.
- Test cases 10-17 satisfy no additional constraints.


title: [USACO22FEB] Moo Network G

description:
Farmer John's $N$ cows $(1≤N≤10^5)$ are spread far apart on his farm and would like to build a communication network so they can more easily exchange electronic text messages (all of which of course contain variations of "moo").

The ith cow is located at a distinct location $(x_i,y_i)$ where $0≤x_i≤10^6$ and $0≤y_i≤10$. The cost of building a communication link between cows $i$ and $j$ is the squared distance between them: $(x_i-x_j)^2+(y_i-y_j)^2$.

Please calculate the minimum cost required to build a communication network across which all the cows can communicate. Two cows can communicate if they are directly connected by a link, or if there is a sequence of links along which their message can travel.

**Note: the time limit for this problem is 4s, twice the default.**

inputFormat: The first line of input contains $N$, and the next $N$ lines each describe the $x$ and $y$ coordinates of a cow, all integers.

outputFormat: Please output the minimum cost of a network that will allow all cows to communicate. Note that this cost might be too large to fit into a 32-bit integer and may require use of 64-bit integers (e.g., "long long" integers in C++).

translation:
## 题目描述

农夫约翰有 $N$ 头牛（$1\le N\le10^5$） 它们在农场里分布的极其的远，因此希望你建立一个通讯网络，便于它们更容易地交换电子短信（当然，这些短信都包含 `moo` 的变形体，即数字）

第 $i$ 头牛位于位置 $(x_i，y_i)$ 其中 $0\le x\le 10^6$, $0\le y\le 10$. 在牛 $i$ 与牛 $j$ 之间建立通信链路的成本是它们之间的欧几里德距离的平方，即 $(x_i-x_j)^2+(y_i-y_j)^2$

请聪明的你构建一个所有奶牛都能交流的最低成本的通信网络。如果两头奶牛通过一条链接直接连接或者它们的信息可以沿着一条链接传播，那么认为他们可以通信。

#### 注意 此问题时间限制为4秒

## 输入格式
第一行输入为 $N$，接下来 $N$ 行分别描述奶牛的位置 $(x,y)$ 均为整数
## 输出格式
请输出允许所有奶牛通信的网络的最低成本。请注意，此开销可能太大，无法放入 32 位整数中，并且可能需要使用 64 位整数（例如，C++中的“long long”）。

### 说明/提示

测试点 2~3 满足 $N\le1000$。

测试点 4~15 没有特殊限制。

hint:
【数据范围】

- Test cases 2-3 satisfy $N≤1000$.
- Test cases 4-15 satisfy no additional constraints.


title: [USACO22FEB] Sleeping in Class P

description:
最近终于线下授课了，奶牛 Bessie 十分兴奋！不幸的是，Farmer John 是一个非常无聊的讲师，因此她经常课堂上睡觉。

Farmer John 注意到了 Bessie 上课走神。他要求班上的另一个学生 Elsie 跟踪记录给定课上 Bessie 睡觉的次数。一共有 $N$ 堂课，Elsie 记录下了 Bessie 在第 $i$ 堂课睡了 $a_i$ 次。所有课上 Bessie 一共睡觉的次数最多为 $10^{18}$。

Elsie 认为自己是 Bessie 的竞争对手，所以她想让 FJ 觉得在每堂课上 Bessie 都一直睡了同样多次——让 FJ 觉得这个问题显然完全是 Bessie 的错，而不是 FJ 有时上课很无聊的问题。

Elsie 修改记录只有以下两种方式：把两堂课的记录合起来，或者把一堂课的记录分成两堂课。例如，如果 $a=[1,2,3,4,5]$，那么如果 Elsie 将第二堂和第三堂课的记录合起来，记录就会变为 $[1,5,4,5]$。如果 Elsie 继续选择让第三堂课的记录分为两堂，记录就可能变为 $[1,5,0,4,5],[1,5,1,3,5],[1,5,2,2,5],[1,5,3,1,5]$ 或 $[1,5,4,0,5]$。

给定 $Q$ 个候选的 Bessie 最不喜欢的数字 $q_1,\ldots,q_Q$，对于每个数字，请帮助 Elsie 计算她至少要操作多少次，才能让记录里的所有数字都变成这个数字。

inputFormat:
第一行一个整数 $N$（$2\le N\le 10^5$）。

第二行 $N$ 个整数 $a_1,a_2,\ldots, a_N$（$1\le a_i\le 10^{18}$）。

第三行一个整数 $Q$（$1\le Q\le 10^5$）。

接下来 $Q$ 行，每行一个整数 $q_i$（$1\le q_i\le 10^{18}$），表示 Bessie 最不喜欢的数字。

outputFormat: 对于每个 $q_i$，计算 Elsie 把记录里的每个数都变成 $q_i$ 所需要的最小操作次数。如果不能把所有数都变成 $q_i$，输出 $-1$。

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

Elsie 需要至少 $4$ 次修改才能让记录里的所有数都变成 $3$。

$$
\begin{aligned}
&\ 1\ 2\ 3\ 1\ 1\ 4\\
\rightarrow&\ 3\ 3\ 1\ 1\ 4\\
\rightarrow&\ 3\ 3\ 1\ 5\\
\rightarrow&\ 3\ 3\ 6\\
\rightarrow&\ 3\ 3\ 3\ 3\\
\end{aligned}
$$

Elsie 不可能把记录中的所有数都变成 $5$，因此输出 $-1$。这是正确的。

**【数据范围】**

- 对于第 $2\sim 4$ 组数据，$N,Q\le 5000$。
- 对于第 $5\sim 7$ 组数据，所有 $a_i$ 最多为 $10^9$。
- 对于第 $8\sim 26$ 组数据，无附加限制。


title: [USACO22FEB] Phone Numbers P

description:
Bessie 获得了一个九键的新手机，键位如下所示：

```
123
456
789
```

Bessie 正在匆忙中尝试打出一个给定的电话号码，所以她决定通过用她的其中一个蹄子一次按下多个按钮的方式来节省时间。具体来说，Bessie 的蹄子可能按下一个键，两个共用一条边的键（总共有 $12$ 种可能），或者形成一个正方形的四个键（$1245$，$2356$，$4578$，$5689$）

例如，如果 Bessie 要打的电话号码是 $123659874$，她可能通过如下方法按键来尝试节省时间：

1. 同时按下 $1$ 和 $2$。
2. 按下 $3$。
3. 同时按下 $6,5,9,8$。
4. 同时按下 $7$ 和 $4$。

不幸的是，Bessie 大大高估了她执行这项任务的技能——如果 Bessie 的蹄子同时按下多个按键，那么所有这些按键会以任意顺序输入。所以如果 Bessie 尝试按上述按键顺序，结束时她输入的电话号码可能是 $123596847$ 或 $213659874$（或者其他可能的序列）。

给定一个 Bessie 已经输入的序列，请计算她可能想输入的电话号码的数量对 $10^9+7$ 取模后的值。

inputFormat:
第一行一个整数 $T$（$1\le T\le 10$），表示要求解的独立测试数据组数。

接下来 $T$ 行，每行一个非空且只包含 $1$ 到 $9$ 的数字串。保证输入中所有的数字串总长度不超过 $10^5$。

outputFormat: 对于每组数据，输出 Bessie 可能想输入的电话号码个数对 $10^9+7$ 取模后的值。

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

对于第一组数据。Bessie 可能想输入如下五个电话号码之一：

```plain
1478
1487
4178
4187
1748
```

例如，如果 Bessie 想输入 $4187$，她可能会尝试同时按下 $1$ 和 $4$，然后同时按下 $7$ 和 $8$。

对于第三组数据，因为这些数字组成了一个正方形，Bessie 可能想输入的电话是输入序列的任何排列。

**【数据范围】**

- 对于第 $2\sim 3$ 组数据，所有电话号码的长度最多为 $8$。
- 对于第 $4\sim 5$ 组数据，电话号码只包含 $1,2$ 和 $3$。
- 对于第 $6\sim 7$ 组数据，电话号码不包含 $5$。
- 对于第 $8\sim 9$ 组数据，电话号码只包含 $5,6,8,9$。
- 对于第 $10\sim 12$ 组数据，电话号码总长度不超过 $10^2$。
- 对于第 $13\sim 15$ 组数据，电话号码总长度不超过 $10^3$。
- 对于第 $16\sim 18$ 组数据，电话号码总长度不超过 $10^4$。
- 对于第 $19\sim 21$ 组数据，无附加限制。


title: 【模板】队列

description:
请你实现一个队列（queue），支持如下操作：
- `push(x)`：向队列中加入一个数 $x$。
- `pop()`：将队首弹出。如果此时队列为空，则不进行弹出操作，并输出 `ERR_CANNOT_POP`。
- `query()`：输出队首元素。如果此时队列为空，则输出 `ERR_CANNOT_QUERY`。
- `size()`：输出此时队列内元素个数。

inputFormat:
第一行，一个整数 $n$，表示操作的次数。

接下来 $n$ 行，每行表示一个操作。格式如下：

- `1 x`，表示将元素 `x` 加入队列。
- `2`，表示将队首弹出队列。
- `3`，表示查询队首。
- `4`，表示查询队列内元素个数。

outputFormat:
输出若干行，对于每个操作，按「题目描述」输出结果。

每条输出之间应当用空行隔开。

samples:
2
1
2
233
0
ERR_CANNOT_QUERY
ERR_CANNOT_POP
144

hint:
### 样例解释
首先插入 `2`，队首为 `2`、队列内元素个数为 `1`。
插入 `233`，此时队首为 `2`。
弹出队首，此时队首为 `233`。
弹出队首，此时队首为空。
再次尝试弹出队首，由于队列已经为空，此时无法弹出。
插入 `144`，此时队首为 `144`。

### 数据规模与约定

对于 $100\%$ 的测试数据，满足 $n\leq 10000$，且被插入队列的所有元素值是 $[1, 1000000]$ 以内的正整数。


title: 「Wdoi-5」天才⑨与天才拆分

background:
$\kern{75pt}$![](https://cdn.luogu.com.cn/upload/image_hosting/ghy90htm.png?x-oss-process=image/resize,m_lfit,h_340,w_450)

萌萌琪露诺在寺子屋的教室里面见到了哆来咪·苏伊特。心怀好意的哆来咪告诉了她期末考试的题目，只要解出这些题目就能免于被慧音老师头槌。兴奋的琪露诺告别了哆来咪，猛然发现自己已经身处在期末考试的考场之上！但是琪露诺实在是太笨了，醒来就把哆来咪告诉她的题目忘得一干二净，只记得试卷上有大量的⑨。

现在琪露诺已经在考试啦，你可以使用⑨的妖精链接回答她的问题，以平复她忘记了考试答案的悲痛。你能帮帮她吗？

温馨提示：考试作弊是不对的哦。

description:
琪露诺定义一个十进制正整数为「$k$ 阶天才数」，当且仅当该整数的**位数**为 $k$ 的倍数，且**每一个数位**均为 $9$。例如，$9999$ 是 $2$ 阶天才数，而 $999$ 不是 $2$ 阶天才数，但是它是 $1$ 阶天才数，也是 $3$ 阶天才数。

琪露诺给定你 $t$ 个询问，每个询问有两个整数 $n$ 和 $k$，希望你能帮帮她，告诉她能不能把 $n$ 拆分成若干个 $k$ 阶天才数的和。

inputFormat:
- 第一行是一个整数 $t$，代表询问的个数。
- 接下来 $t$ 行，每行两个整数 $k$ 和 $n$，代表一个询问。

outputFormat: - 输出共 $t$ 行。如果对应的询问答案是可以，输出一行一个字符串 `aya`，否则输出一行一个字符串 `baka`。

hint:
本题共有 $20$ 个测试点，每个测试点 $5$ 分。最终分数为所有测试点分数之和。

$$
\def{\n}{\text{无特殊限制}}
\def{\arraystretch}{1.5}\begin{array}{|c|c|c|c|}\hline
\textbf{Task} & \bm t= & \bm {n_i \le} & \bm {k_i \le} \cr\hline
1 & 1 & 233 & 1 \cr\hline
2\sim 6 & 1 & 10^3 & 1 \cr\hline
7\sim 8 & 10 & 10^9 & 1 \cr\hline
9 & 10^3 & 10^9 & 1 \cr\hline
10 & 10^3 & 10^{18} & 1 \cr\hline
11\sim 20 & 10^3 &  10^{18} & 10 \cr\hline
\end{array}
$$

对于全部数据，满足 $1\le t\le 10^3$，$1\le n_i\le 10^{18}$，$1\le k_i\le 10$。


title: [传智杯 #4 决赛] DDOSvoid 的馈赠

description:
小智马上就要 AK（All killed，指使本场比赛的全部题目 AC）本场“传智杯”全国大学生 IT 技能大赛（决赛）然后离场了。临走前，DDOSvoid 打算给小智 $n$ 个字符串 $s_1, s_2, \dots, s_n$ 作为纪念。在本题中，我们将这 $n$ 个字符串称作「模板串」。

小智本身有 $m$ 个字符串 $t_1, t_2, \dots t_m$。在本题中，我们将这 $m$ 个字符串称为「查询串」。

DDOSvoid 的礼物不是无条件的，他有 $q$ 个问题，每个问题给定两个参数 $x, y$，要求小智回答他：一共有多少个模板串 $s_i$，满足 $s_i$ 既是 $t_x$ 的子串，也是 $t_y$ 的子串？

只有回答对这 $q$ 个问题，小智才能得到 DDOSvoid 馈赠的礼物。请你帮帮小智，回他 DDOSvoid 的问题。

我们称一个字符串 $t$ 是 $s$ 的子串，当且仅当将 $s$ 的开头若干个（可以为 0 个）连续字符和结尾若干个（可以为 0 个）连续字符删去后，剩下的字符串和 $t$ 相同。例如，我们称 `ab` 是 `abc` 的子串，但 `ac` 不是 `abc` 的子串。

inputFormat:
第一行有三个整数，依次表示模板串个数 $n$，查询串个数 $m$，以及询问的个数 $q$。
接下来 $n$ 行，每行一个字符串，依次表示模板串 $s_1,s_2, \dots s_n$。
接下来 $m$ 行，每行一个字符串，依次表示查询串 $t_1, t_2, \dots t_m$。
接下来 $q$ 行，每行两个整数 $x, y$，表示一个询问。

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

samples:
3 3 3
aaba
baba
aba
ababa
aabab
babaa
1 2
1 3
2 3

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

对于全部测试点，保证 $1\leq n,m,q,|s_i|,|t_i| \leq 10^5$，且模板串的长度之和、查询串的长度之和均不超过 $10^5$，即 $\sum\limits_{i = 1}^n |s_i|,\sum\limits_{i = 1}^m|t_i| \leq 10^5$，其中 $|x|$ 表示字符串 $x$ 的长度。保证输入的字符串只含有小写字母，$1 \leq x\neq y \leq m$。

### 提示

**请注意常数因子对程序效率造成的影响**。


title: [传智杯 #4 决赛] 小智的疑惑

description:
传智专修学院给了小智一个仅包含小写字母的字符串 $s$，他想知道，里面出现了多少次子串 `chuanzhi` 呢。

我们称一个字符串 $t$ 是 $s$ 的子串，当且仅当将 $s$ 的开头若干个（可以为 0 个）连续字符和结尾若干个（可以为 0 个）连续字符删去后，剩下的字符串和 $t$ 相同。例如，我们称 `ab` 是 `abc` 的子串，但 `ac` 不是 `abc` 的子串。

inputFormat: 输入只有一行一个字符串，表示字符串 $s$。

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

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

对于全部的测试点，保证 $1 \leq |s| \leq 4 \times 10^5$，$|s|$ 表示 $s$ 的长度，且 $s$ 中只有小写字母。


title: [传智杯 #4 决赛] 游戏

background: 小智正在看 B 站非著名 up 主脚踢喷火幼儿园（下称喷火）和他的朋友 ATA_Radio_STN 和 sltheen 正在游玩著名游戏《PLAYERUNKNOWN’S BATTLEGROUNDS》（绝地求生：大逃杀）。

description:
喷火刚刚跳伞落地，周围危机四伏，他的手中有一个初始背包，他捡到的所有物资都会装在这个背包里，游戏地图被简化为一个 $n \times m$ 的网格图，每个格子里要么是物资，要么是敌人。

物资分为主/副武器和弹药，其中弹药又分为子弹与投掷物。每种武器会对应使用某种子弹。例如：Beryl M762 突击步枪使用 7.62mm 子弹，M416 突击步枪使用 5.56mm 子弹，而 AKM 突击步枪也使用 7.62mm 子弹。

当喷火走到一个含有物资的格子的时候，他会拾起地上的物资并放入背包。但背包容量有限，因此当背包装满的时候，他将会扔掉一部分物资以装下新的物资。他将按照以下规则丢弃物资：
1.	如果捡到的是武器，那么按照霰弹枪>突击步枪>射手步枪>栓动步枪>空手的优先级进行替换。优先替换主武器，且主武器优先级必须严格高于副武器。如果替换主武器，那么替换下来的主武器被**直接丢弃**，不再用其替换副武器。
2.	若有不需要的子弹（指主副武器均不使用的子弹），最优先丢掉这些子弹，直至空间足够装下新的物资。
3.	若丢掉全部不需要子弹后空间仍旧不足，或有多种不需要的子弹，优先丢掉最晚拾取时间最早的弹药（包括主副武器使用的子弹和投掷物），直至空间足够装下新的物资（需要注意的是，即使新物资是「不需要的子弹」，在丢掉所有原有的「不需要的子弹」后如果背包空间还是不够，则喷火依然会丢掉其他弹药直到捡起所有「不需要的子弹」）。
4.	无论捡到的是新物资，还是已经有的物资，该物资的最晚拾取时间都将被更新为当前时间点。
5.	武器最多同时持有两种，即主/副武器，同优先级的主/副武器不进行替换。

每个格子的物资只会拾取一次。当第二次进入某个格子的时候，物品不会刷新，即不会捡起上次在这个格子丢掉的物品，也不会再次捡到初始时的物品。

当喷火走到含有敌人的格子的时候，他会与敌人进行战斗，他的战斗力很强悍，只需要有足够的子弹即可消灭敌人。每个敌人有两个参数 $a,b$，代表需要消耗 $a$ 发主武器子弹，若主武器子弹不够，则不消耗主武器子弹，而消耗 $b$ 发副武器子弹。若主副武器均没有足够子弹，则喷火被敌人反杀，然后敌人会在喷火的盒子上做蹲起嘲讽他。

每个格子的敌人只会出现一次。如果第二次进入某一个有敌人的格子，则什么都不会发生。

现在，喷火跳在了第一行第一列的格子上，ATA_Radio_STN 已经为喷火摸清了地图形势，而 sltheen 会给喷火下指示，喷火想知道，当他执行完最后一条指示之后，他是否还存活，若存活，按照最晚拾取时间时间从早到晚，输出背包内物品种类和数量，若死亡，输出他死亡格子的坐标。

下附可能出现的物资、物资类别、物资使用的子弹种类、物资所需空间以及物资对应编号。

武器：
| 武器名称 | 武器类型| 使用的子弹类型 | 编号 |
| --- | --- | ---  | ---|
| 空手 | 空手 | N/A | 0|
|BerylM762|突击步枪|7.62mm子弹|1|
|AKM|突击步枪|7.62mm子弹|2|
|SKS|射手步枪|7.62mm子弹|3|
|Kar98K|栓动步枪|7.62mm子弹|4|
|M416|突击步枪|5.56mm子弹|5|
|MK12|射手步枪|5.56mm子弹|6|
|Mini14|射手步枪|5.56mm子弹|7|
|S686|霰弹枪|12号霰弹|8|
|DBS|霰弹枪|12号霰弹|9|

弹药
|弹药名称| 类型 | 占用空间 | 编号 |
| - | - | - | - |
|FragGrenade|投掷物| 5  |   10|
|SmokeGrenade| 投掷物 |    4|    11|
|MolotovCocktail |投掷物  | 3 |    12|
|Flashbang |投掷物        | 2    | 13|
|7.62mm |子弹 |0.2|                14|
|5.56mm| 子弹| 0.1                |15|
|3in（12号霰弹）| 子弹| 0.5|                     16|

请注意，上表中子弹的「占用空间」表示一发子弹所占用的空间。

另外，敌人在地图上的编号为 17。

inputFormat:
第一行有四个整数，依次表示地图行数 $n$，列数 $m$，背包容量 $k$，和 sltheen 会下达的指令条数 $t$。
接下来的 $n\times m$ 行中，第 $i$ 行代表第 $\lfloor\frac{i - 1}{n}\rfloor+1$ 行，第 $(i - 1)\%n+1$ 列的地图情况，其中 $i \% n$ 表示 $i$ 除以 $n$ 的余数：
- 此处若是物资，则本行有两个空格隔开的整数，为物资编号 $x$ 和物资数量 $y$，物资编号见「题目描述」中表格的最后一列（如果该物资是枪，则保证 $y = 1$）；
- 若此处是敌人，则本行有三个空格隔开的整数，第一个整数为 $17$，代表敌人，接下来两个整数依次表示敌人的 $a, b$ 两个参数。

接下来 $t$ 行，每行一个整数 $op$，表示 sltheen 为喷火下达的指令的移动方向：1 代表向上，2 代表向下，3 代表向左，4 代表向右。（第一行第一列是地图的左上角，最后一行第一列是地图的左下角）

outputFormat:
如果喷火死亡，则输出两个数 $u, v$，代表喷火在第 $u$ 行第 $v$ 列死亡。

若喷火未死亡，先输出两行，第一行为主武器编号，第二行为副武器编号，之后输出若干行，每行为两个整数整数，中间用空格隔开，第一个整数为物资名称，第二个整数为其数量，按照最后捡到时间从早到晚排序。

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

对于全部的测试点，保证：
- $1 \leq n, m \leq 100$，且 $1 \leq  n \times m \leq 100$。
- $1 \leq k \leq 500$，$1 \leq t,a,b  \leq 200$。
- $1 \leq x \leq 16$，$1 \leq y \leq 5000$。
- $1 \leq op \leq 4$。
- 数据保证每个格子内只有一种物资（或一个敌人），且背包能够装下任意一格的物资。