title: [ICPC2021 Nanjing R] Ancient Magic Circle in Teyvat

description:
Astrologist Mona Megistus discovers an ancient magic circle in Teyvat recently.

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

The magic circle looks like a complete graph with $n$ vertices, where $m$ edges are colored red and other edges are colored blue. Note that a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.

Mona realizes that if she chooses four different vertices such that the six edges between these four vertices are of the same color, she will get a *key* from the magic circle. If the color is red, she will get a *red key*, and if the color is blue, she will get a *blue key*.

Base on the information written in the ancient books Mona has read, the magic power of the ancient magic circle is the absolute difference between the number of *red keys* and the number of the number of *blue keys* she can get from the magic circle.

Mona needs your help badly, since calculating the magic power of the magic circle is really a tough job.

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

The first line of the input contains two integers $n$ and $m$ ($4 \le n \le 10^5$, $0 \le m \le \min(\frac{n(n-1)}{2}, 2 \times 10^5)$) indicating the number of vertices and the number of edges colored red of the ancient magic circle.

For the following $m$ lines, the $i$-th line contains two integers $u_i$ and $v_i$ ($u_i < v_i$) indicating a red edge connecting vertices $u_i$ and $v_i$. It is guaranteed that each edge appears at most once.

outputFormat: Output one line containing one integer indicating the magic power of the ancient magic circle.

translation:
给定一个 $n$ 个点的完全图，有 $m$ 条边是红色的，其余边是蓝色的，求出边均为蓝色的大小为 $4$ 的完全子图个数与边均为红色的大小为 $4$ 的完全子图个数的差。
$4\le n\le 10^5$，$0\le m\le \min(\frac{n(n-1)}{2},2\times 10^5)$。

hint: For the sample case, there is only one *red key* $(1,2,3,4)$ and there are four *blue keys* $(1,5,6,7)$, $(2,5,6,7)$, $(3,5,6,7)$ and $(4,5,6,7)$ in the ancient magic circle, thus the magic power of the magic circle is $|1-4|=3$.


title: [ICPC2021 Nanjing R] Secret of Tianqiu Valley

type: P

description:
In the north tower of Tianqiu Valley's ruins, there are some flame torch puzzles and Lumine the traveler is facing the last and the hardest one.

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

There are $n$ torches in a circle and some torches have been ignited initially. The $i$-th and the $(i \bmod n +1)$-th are adjacent for all $1 \le i \le n$.

To solve the puzzle, all the torches should be ignited. In each move, Lumine can ignite an extinguished torch, and the status of the adjacent torches will be reversed affected by the supernatural. That is, each of the adjacent torches will be ignited if it is currently extinguished, or be extinguished if it is currently ignited.

Time is money, Lumine wants to solve the puzzle in $2n$ moves or determine that the puzzle is unsolvable.

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

The first line of the input contains an integer $n$ ($3 \le n \le 10^5$) indicating the number of torches in the circle.

The second line contains a binary string $s_1s_2\cdots s_n$ of length $n$ ($s_i \in \{\text{`0'}, \text{`1'}\}$). If $s_i = \text{`0'}$ the $i$-th torch is extinguished initially; If $s_i = \text{`1'}$ the $i$-th torch is ignited initially. It is guaranteed that not all the torches have been ignited initially.

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

outputFormat:
If the puzzle is unsolvable, output `0`.

Otherwise, output an integer $k$ $(1 \le k \le 2n)$ in the first line indicating the number of moves Lumine needs to solve the puzzle. Then output a line containing $k$ integers $t_1, t_2, \cdots, t_k$ separated by a space, where $t_i$ indicating that Lumine will ignite the $t_i$-th torch in the $i$-th move. If there are multiple answers print any of them.

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

translation:
有 $n$ 个火炬排成一个环，编号为 $1,2,3,...,n$，输入一个长度为 $n$ 的二进制字符串 $s$，表示这 $n$ 个火炬是否已经被点燃（初始状态）。

你可以点燃一个**熄灭的**火炬 $s_i$，但两侧火炬的状态也会随之逆转（即 $s_{{i-1}}$、$s_{i}$、$s_{i+1}$（在取模条件下）同时取反）。请问，最多逆转 $2n$ 次，能否使所有火炬全部被点燃。如果能，输出对应的逆转次数，否则输出`0`。

- 小提示：$t$ 组数据。


title: [ICPC2021 Nanjing R] Windblume Festival

description:
The Windblume Festival in Mondstadt is coming! People are preparing windblumes for Barbatos and for those they love and adore. The Windblume Festival is also an opportunity to improve the relationships people have.

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

During the festival, a famous game will be played every year, invented by Jean, the Acting Grand Master of the Knights of Favonius. In the game, $n$ players numbered from $1$ to $n$ stand in a circle, each holding an integer with them. Each turn, one player will be removed. The game will end when there is only one player left.

For each turn, let $k$ be the number of players remaining and $a_i$ be the integer player $i$ holds. Two adjacent players, $x$ and $(x \bmod k + 1)$ are selected and player $(x \bmod k + 1)$ is removed from the game. Player $x$'s integer will then change from $a_x$ to $(a_x - a_{x \bmod k + 1})$. Player $y$ in this turn will become player $(y - 1)$ in the next turn for all $x < y \le k$, though the integer they hold will not change.

Jean wants to know the maximum possible integer held by the last remaining player in the game by selecting the players in each round optimally.

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

The first line contains one integer $n$ ($1 \le n \le 10^6$) indicating the initial number of players.

The next line contains $n$ integers $a_i$ ($-10^9 \le a_i \le 10^9$) where $a_i$ is the integer held by player $i$ at the beginning.

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

outputFormat: For each test case output one line containing one integer indicating the maximum possible integer.

translation:
给一个长度为 $n$ 环形整数序列 $a$, 每次操作可以任意选择一个下标 $x$，令 $ a_x = a_x - a_{(x\bmod n)+1}$，之后移除 $a_{(x\bmod n)+1}$。

最后会剩下一个元素，要求最大化这个元素。

数据范围 $1\le n\le10^6,-10^9\le a_i\le 10^9$。

hint:
For the first sample test case follow the strategy shown below, where the underlined integers are the integers held by the players selected in each turn.

$\{\underline{1}, -3, 2, \underline{-4}\}$ (select $x = 4$) $\to$ $\{-3, \underline{2, -5}\}$ (select $x = 2$) $\to$ $\{\underline{-3, 7}\}$ (select $x = 2$) $\to$ $\{10\}$.


title: [CCC 2015 S1] Zero That Out

description:
给定 $k$ 个整数 $a_{1 \dots k}$，维护一个序列，按顺序进行以下操作：

- 当 $a_{i} = 0$ 时，将序列中最后加入的数删除。
- 否则，将 $a_{i}$ 加入序列。

例如：当 $a = \{1,3,5,4,0,0,7,0,0,6\}$ 时，操作如下。

|$a_{i}$|序列|
|:--:|:--:|
|$1$|$\{1\}$|
|$3$|$\{1,3\}$|
|$5$|$\{1,3,5\}$|
|$4$|$\{1,3,5,4\}$|
|$0$|$\{1,3,5\}$|
|$0$|$\{1,3\}$|
|$7$|$\{1,3,7\}$|
|$0$|$\{1,3\}$|
|$0$|$\{1\}$|
|$6$|$\{1,6\}$|

你需要计算最终序列中所有数的和。

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

接下来 $k$ 行，每行一个整数 $a_{i}$。

outputFormat: 输出一行一个整数，表示最终序列中所有数的和。

hint:
**【数据范围】：**

$1 \leq k \leq 10^{5}$，$0 \leq a_{i} \leq 100$。

保证在 $a_{i} = 0$ 时序列不为空。


title: [CCC 2015 S2] Jerseys

description:
有编号为 $1 \sim n$ 的队服要分给 $m$ 个队员，队服从小到大分别有 S、M、L 三种大小，每个队员对于队服有一定的要求，具体的：第 $i$ 个队员希望得到的队服尺码**不小于** $a_{i}$，编号为 $b_{i}$。

求最多能满足多少人的要求。

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

接下来 $n$ 行，每行一个字符 $c_{i}$，表示编号为 $i$ 的队服大小，满足 $c_{i} \in \{\text{S,M,L}\}$。

接下来 $m$ 行，每行一个字符 $a_{j}$ 和一个整数 $b_{j}$，满足 $a_{j} \in \{\text{S,M,L}\}$，含义见题目描述。

outputFormat: 输出一行一个整数，表示最多能满足要求的人数。


title: [CCC 2015 S3] Gates

description:
机场有 $n$ 个登机口，你需要按顺序安排 $m$ 架飞机，第 $i$ 架飞机只能使用 $1 \sim g_{i}$ 号登机口，一个登机口永久只能被一架飞机使用。**当没有登机口可以供某架飞机使用时机场便会关闭，之后的飞机都不能登机。**

请确定一种方案，使得有登机口的飞机数量最多。

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

第二行一个整数 $m$。

接下来 $m$ 行，每行一个整数 $g_{i}$。

outputFormat: 一行一个整数，表示最多能安排的飞机数量。

hint:
**【数据范围】：**

对于 $40\%$ 的数据，$1 \leq n,m \leq 2 \times 10^{3}$。

对于 $100\%$ 的数据，$1 \leq n,m \leq 10^{5}$，$1 \leq g_{i} \leq n$。

本题中 Subtask 0 为原题数据，Subtask 1 为 Hack 数据，Hack 数据不计分。


title: [CCC 2015 S4] Convex Hull

description:
给定一个 $n$ 个点，$m$ 条边的无向图，每条边有两个边权 $t_{i}$ 和 $h_{i}$。

你需要找到一条从 $s$ 到 $t$ 的路径，满足路径上边的 $h_{i}$ 之和 $<k$ 且 $t_{i}$ 之和最小，只需要输出这个最小值即可，如果无法找到满足条件的路径，输出 $-1$。

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

接下来 $m$ 行，每行四个整数 $u_{i},v_{i},t_{i},h_{i}$ 表示一条从 $u_{i}$ 到 $v_{i}$ 的路径，边权为 $\{t_{i},h_{i}\}$。

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

outputFormat:
当存在满足条件的路径时，输出一行一个整数表示满足条件的最小 $t_{i}$ 之和。

否则输出一行 $-1$。


title: [CCC 2015 S5] Greedy For Pies

description:
给定一个长度为 $n$ 的序列 $a$ 和一个长度为 $m$ 的序列 $b$，你可以将 $b$ 序列中的元素任意插入到 $a$ 序列的任何位置（包括开头和末尾）。之后，你可以从新的序列中选一些元素，但你不能选择两个相邻的元素。

你需要使得你选出的数之和最大，输出这个最大值即可。

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

接下来 $n$ 行，每行一个整数 $a_{i}$。

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

接下来 $m$ 行，每行一个整数 $b_{i}$。

outputFormat: 输出一行一个整数，表示你能选出元素和的最大值。


title: 『PG2』模拟最大流

description: 给定 $n$ 个点，$m$ 条有向边，给定每条边的容量，保证每条边 $(u,v,w)$ 满足 $v-u\in[0,k]$，求从点 $1$ 到点 $n$ 的最大流。

inputFormat:
第一行包含三个正整数 $n$、$m$、$k$，用空格分隔。

接下来$m$行每行包含三个正整数 $u_i$、$v_i$、$w_i$，用空格分隔，表示第 $i$ 条有向边从 $u_i$ 出发，到达 $v_i$，容量为 $w_i$。

outputFormat: 一个整数，表示 $1$ 到 $n$ 的最大流。

hint:
对于 $20\%$ 的数据满足 $n\leq 10^2$，$m\leq 10^4$，$k\leq 2$。

对于 $40\%$ 的数据满足 $n\leq 10^4$，$m\leq 10^6$，$k\leq 2$。

对于 $60\%$ 的数据满足 $n\leq  8\times 10^4$，$m\leq 10^6$，$k\leq 2$。

对于 $80\%$ 的数据满足 $n\leq  8\times 10^4$，$m\leq 10^6$，$k\leq 4$。

对于 $100\%$ 的数据满足 $2\leq n\leq 8\times 10^4$，$1\leq m\leq 10^6$，$2\leq k\leq 7$，$1\leq w\leq100$。


title: [POI2021~2022R2] arm

background: 翻译自 [POI2021-2022R2 Day0 试机题](https://szkopul.edu.pl/problemset/problem/gxeCvLD1xW1t-Y33bbC0n3wZ/statement/)。

description:
初始时你有 $1$ 个物品，你需要将物品的数量按若干次以下步骤增加到 $> n$ 个。

- 选择 $1$：将物品数量存储进数据库中，耗费 $a$ 的时间。
- 选择 $2$：使物品数量增加等同于数据库中的数量，耗费 $b$ 的时间。

初始时数据库为空，问最小操作次数。

inputFormat: 输入一行，共三个整数 $n,a,b\ (1 \leq n \leq 10^{18},1 \leq a,b \leq 10^9)$。

outputFormat: 输出最小的操作次数。


title: [POI2021~2022R2] age

background: 翻译自 [POI2021~2022R2 Day1T1](https://szkopul.edu.pl/problemset/problem/weKRWGa1NgLNHT1WLDo5ohuH/statement/)。

description:
有一个 $n$ 个城市的国家，我们可以将其看为一棵 $n-1$ 条道路连接的树，有一天，你突发奇想，想要派出 $k$ 个人在不同城市上。人及其移动需要满足如下条件：

- 每天只能是一个人移动，移动到其相邻存在道路连接一个城市。

- 假如有两个人 $a,b$，城市 $i$ 被 $a$ 到达过了，则 $b$ 不能到达 $i$ 城市。

初始时你知道了人的位置，每个人初始所在地不相同，且该城市视为“已到达过”的城市，你需要安排一个合法的经过城市的方案。

请你求出最少要几天才能使所有的城市都被人到达过。

inputFormat:
第一行两个整数 $n,k\ (1 \leq n \leq 5 \times 10^5, 1 \leq k \leq n)$。

第二行 $k$ 个数，表示那些人的初始位置。

然后 $n-1$ 行，描述了每条道路 $(a_i,b_i)\ (1 \leq a_i,b_i \leq n)$。

outputFormat: 输出最少天数。


title: [POI2021~2022R2] lic

background: 翻译自 [POI2021~2022R2 Day1T2](https://szkopul.edu.pl/problemset/problem/kQ5ExYNkFhx3K2FvVuXAAbn4/statement/)。

description:
定义 $a$ 的「不友好数」$b$ 为 $\gcd(a,b)=1$ 的数。

现在你知道了数字 $n$，你需要求出它的「不友好数」升序排序第 $k$ 个开始后的 $c$ 个数。

outputFormat: 输出 $c$ 个数，表示第 $k \sim k+c-1$ 个 $n$ 的「不友好数」。


title: [POI2021~2022R2] bom

background:
翻译自 [POI2021~2022R2 Day2T1](https://szkopul.edu.pl/problemset/problem/MfTrGDTrlrVX21vwwhgsjaLv/statement/)。

时限：sub1 和 sub4 8s，sub2 2s, sub3 3s。

description:
你有一个 $n \times n$ 的图，仅包含 `.`、`X`、`P`、`K`、`#`，意义如下：

- `P` 起点。
- `K` 终点。
- `.` 可以通过的路。
- `X` 不可以通过的岩石墙。
- `#` 不可以通过的砖墙。

你还有一枚炸弹，你选择一个不是岩石墙的地方放置，爆炸时，会从原来的地方上下左右依次扩散爆炸直到某一方向碰到了岩石墙或超出了图的范围。
爆炸区域变为空地，但岩石墙不会。

然后你需要求出起点至终点的最短路径。

inputFormat:
第一行一个整数 $n\ (2 \leq n \leq 1000)$。

然后 $n \times n$ 大小的字符矩阵，描述了图。

outputFormat:
如果放置完炸弹并引爆后有解，则输出三行：

- 第一行：最短路径长度。
- 第二行：放置炸弹位置。
- 第三行：其中符合条件的最短路径（其中 `G` 表示向上，`D` 表示向下，`L` 表示向左，`P` 表示向右）。

若无解，输出 `NIE`。


title: [POI2021~2022R2] kon

background: 翻译自 [POI2021~2022R2 Day2T2](https://szkopul.edu.pl/problemset/problem/TEuljz3gsotYQRUKdlEZZr1G/statement/)。

description:
有一个舞会，一开始角色只有 $1$、$2$，他们两个都愿意和彼此跳舞。

然后存在 $q$ 个事件，分别对应下方的操作：

- `W x`：表示新加入一个人，他和编号 $x$ 的人愿意互相和对方跳舞。
- `Z x`：表示新加入一个人，初始时他和编号为 $x$ 的人愿意跳舞的对象都互相同意跳舞。
- `? x`：表示查询愿意与 $x$ 跳舞的有几个人。

新加入的人的编号是当前人数加一。

inputFormat:
第一行一个整数 $q\ (1 \leq q \leq 10^6)$。

然后 $q$ 行，每行一个字符和一个整数 $x$，含义如题目描述所述。

outputFormat: 对应每个 `?` 操作，输出一行答案。


title: 「FAOI-R2」梨花开 (C)

background:
> 忽如一夜春风来，千树万树梨花开。

雪，覆盖了大漠上的一颗颗树，仿佛朵朵梨花盛开。但是令 krjt 意想不到的是，这些树居然真的是梨树！

description:
给你一颗以 $1$ 为根的树，初始时每个点都是白色，每个点有两个权值 $a_i,b_i$，初始时所有点的两个权值都为 $0$，但 $a_1=k$。

我们通过如下操作定义一个序列 $\{v_t\}$ 的权值：
- 从小到大度过 $1,2,3,\dots,t$ 这 $t$ 个时刻。
- 在第 $x$ 个时刻，对于 $i\in[1,n]$，执行 $b_i\gets b_i+v_x$。
- 对于父子 $(u,v)$，设 $u$ 为父亲，可以选定整数 $h\in[0,a_u]$ 执行操作 $a_u\gets a_u-h$，$a_v\gets a_v+h$，之后该时刻内形如 $(v,w)$ 且 $v$ 为父亲的父子不能操作。
- 若一个点 $i$ 满足 $a_i+b_i<0$，将 $i$ 以及 $i$ 的子树中的点染成黑色。
- 执行最优操作以最大化第 $t$ 时刻后的白点个数，该序列权值即为最大白点个数。

定义一个序列 $\{v_t\}$ 合法仅当 $\forall i\in[1,t]$，$\lvert v_i\rvert\in[0,m]$。给定 $t$，求出所有合法序列 $\{v_t\}$ 的权值之和对 $998244353$ 取模的值。

### 原题面

krjt 的目光注视在一棵以 $1$ 号结点为根的，$n$ 个结点的梨树上。

这颗梨树的每个点在每一刻都可以做**任意次**以下操作：将自己的**基本**热量提供**任意正整数量**给某个儿子。

**但需要注意的是，在同一个时刻里，只有当一个结点的所有儿子结束操作后，该结点才能操作。**

雪纷纷地下着，梨树在 $t$ 个时刻的冬天里，第 $i$ 天**所有操作完成后**每个结点的都会加上 $v_i$ 点**附加**热量，若**加上后**该结点的**总**热量仍然 $<0$ 则会连同它的子树一起冻死（自动与其祖先断开，掉到地上）。每个 $v_i$ 都是 $[-m,m]$ 中的一个不确定的整数值。

梨树定义一个序列 $\{v_t\}$ 的价值为它作为每时刻增加的热量时，梨树最多保留的结点数。

梨树不愿在这个冬天死去，希望求出所有方案的价值和，以保留尽量多的结点迎接春天，绽放花朵。因为在冬天前，它的根结点储蓄了 $k$ 点**基本**热量（和 $0$ 点附加热量，其他结点储蓄了 $0$ 点热量），这是自知活不过冬天的伙伴给它的。

而它伙伴在最后一点意识隐隐消失时，仿佛能够看到：一夜春风轻抚，冰雪消融，树林里朵朵梨花开……

答案对 $998244353$ 取模。

inputFormat:
第一行四个非负整数 $n,m,t,k$，分别表示树的结点个数，$v_i$ 的取值范围，冬天的时长，根结点原本存储的热量。

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示 $u$ 号结点与 $v$ 号结点之间有一条边。


title: 「FAOI-R2」A trip to Macao (B)

background:
## 本题目背景仅供引出题意，无任何不良诱导。
## 出题人特别提醒：请勿在赌博非法地区模仿题目中的行为

这天，xhabc66 来到澳门旅游。一下飞机，他直奔赌场。

可是，今天的赌场格外热闹，不知发生了什么。

xhabc66 打开手机一看：啊，原来今天是 $12$ 月 $20$ 日！

因此，赌场在做活动！一年一度！机不可失！

xhabc66 径直走进了赌场。

description:
赌场贴出了如下规则（**你可以忽略没有加粗的内容**）：

1. 所有玩家在注册后方可进行游戏。
2. 活动期间，**新注册的玩家可从抽奖盒内拿走一枚筹码。抽奖盒内共 $m$ 种筹码，面值分别为 $a_1,a_2,\ldots,a_m$ 澳元（均为正整数）**，每种一个，保证公平。
3. 本赌场仅提供一种游戏：猜拳。游戏开始时，双方各下注相同数量（以 $1$ 澳元为单位）的筹码；若猜拳分出胜负，则胜者拿走所有下注。
4. 根据上一条可知，**玩家一次游戏中赢得的筹码（正整数）不得超过自身所携带的筹码**。
5. 公平游戏，严禁作弊，违者严惩。

xhabc66 注册后，**连赢数局（可以是 $0$ 局，但没有输过，也没有平局过）**，最终带着 $n$ 澳元走出了赌场。

出赌场后，xhabc66 突然好奇他是怎么赢到这么多钱的。然而，他不记得他每局下了多少注，不记得他一共玩了多少局，甚至不记得他开始时拿走的筹码是什么面值。

**他想知道：他有多少种不同的赢钱方法。**

**答案对 $10^9+7$ 取模。**

> 两种赢钱方法在满足以下任何一个条件时，xhabc66 都会认为它们不同：
>
> - 他某一局的下注金额不同；
> - 他玩的局数不同；
> - 他开始时拿走的筹码的面值不同。

### 形式化题意

求有多少个数列 $\{b_k\}$ 满足：

1. $\forall i \in [1,k],b_i \in \mathbb{N^*}$；
2. $\forall i \in [2,k],b_i \in [b_{i-1}+1,b_{i-1} \times 2]$；
3. $b_1 \in\{a_m\}$；
4. $b_k=n$。

数列的长度 $k$ 可以是任何**正整数**。

答案对 $10^9+7$ 取模。

inputFormat:
两行。

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

第二行，$m$ 个**从小到大排列**的正整数，$a_1 \sim a_m$。

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


title: 虚树

background:
首先，做这道题不需要用到任何虚树有关知识。

——尽管这是主题库里第一个名字含“虚树”的题（

description:
jq 姐姐有一棵以结点 $1$ 为根的树。定义一棵树的点集 $S$ 的非空子集 $s$ 是好的，当且仅当它满足 $\forall i,j \in s, \text{LCA}(i,j) \in s$。[什么是 $\text{LCA}$？](https://oi-wiki.org/graph/lca/)

为了让树的形态更加可爱，jq 姐姐打算修剪掉某个以节点 $i$ 为根的子树（也就是在原树里将节点 $i$ 及其子树内节点及其相连的边均删除）。

她有若干个修剪方案但从未实施，你需要求出每种方案实施后这棵树的好的非空子集数量。由于答案可能会很大，请输出其对 $998244353$ 取模的结果。

inputFormat:
第一行读入一个整数 $n$ ($n \leq 5 \times 10^5$)，表示树的节点数。

第 $2$ 到 $n$ 行，每行读入两个整数 $u_i,v_i$，表示一条从 $u_i$ 连向 $v_i$ 的边。

第 $n+1$ 行读入一个整数 $m$ ($m \leq 5 \times 10^5$)，表示修剪方案数。

接下来一行每行读入 $m$ 个整数 $q_i$，表示将以 $q_i$ 为根的子树修剪掉。

outputFormat: 共 $m$ 行，第 $i$ 行一个整数 $k$ 表示删除以 $q_i$ 为根的子树后原树的好的非空子集数量。

hint:
样例 1 解释：删去以 $2$ 为根的子树后，原树点集的 $3$ 个非空子集均满足性质，删去以 $5$ 为根的子树后，原树点集的 $15$ 个非空子集中有 $\{3,4\}$、$\{1,3,4\}$ 不满足性质。

对于前 $10\%$  的数据，$n,m \leq 20$。

对于前 $30\%$ 的数据，$n,m \leq 3000$。

对于 $100\%$ 的数据，$1 \leq n,m \leq 5 \times 10^5$，$q \in [1,n]$。


title: [集训队互测 2023] 超现实树

background: Alek 喜欢打信息竞赛，尤其喜欢超现实树。超现实树，顾名思义，就是树上的超现实数。

description:
Alek 认为，对于常数 $k$，一个字符串被称为「$k$-超现实数串」，如果其只包含字符 $\texttt{\{}, \texttt{|}, \texttt{\}}$，且：

- 空串为 $k$-超现实数串；
- 如果 $s, t$ 为 $k$-超现实数串，那么 $s + t$ 为 $k$-超现实数串；
- 如果 $k + 1$ 个字符串 $s_1, s_2, \cdots, s_{k + 1}$ 都是 $k$-超现实数串，那么 $\texttt{\{} + s_1 + \texttt{|} + s_2 + \texttt{|} + \cdots + \texttt{|} + s_{k + 1} + \texttt{\}}$ 为 $k$-超现实数串；
- $k$-超现实数串仅限于此。

给定一棵 $n$ 个点的无根树，节点编号为 $1 \sim n$。每个点 $i$ 上有一个字符 $a_i \in \{\texttt{\{}, \texttt{|}, \texttt{\}}\}$。

给定整数 $m$，Alek 希望你对 $k = 0, 1, \cdots, m$ 分别求出：有多少有序对 $(x, y)$，$1 \leq x, y \leq n$，使得树上从点 $x$ 到点 $y$ 的唯一简单路径上的字符依次拼接所得字符串是 $k$-超现实数串。

inputFormat:
第一行两个整数 $n, m$，分别表示树的节点数，和需要求答案的 $k$ 的上限。

第二行一个字符串 $a$，$a$ 的第 $i$ 个字符表示点 $i$ 上的字符。

接下来 $n - 1$ 行，每行两个整数 $x, y$，表示存在一条连接点 $x$ 和点 $y$ 的边。

outputFormat: 输出一行 $m + 1$ 个整数，分别表示 $k = 0, 1, \cdots, m$ 时的答案。

samples:
见附加文件 ex_surreal3.in。
见附加文件 ex_surreal3.ans。

hint:
对于所有数据，有 $2 \leq n \leq 10^5$，$0 \leq m \leq n - 2$，$a_i \in \{\texttt{\{}, \texttt{|}, \texttt{\}}\}$。

- **Subtask 1**（5 分）：$n \leq 4601$；
- **Subtask 2**（20 分）：对每条边 $(x, y)$ 有 $y = x + 1$；
- **Subtask 3**（5 分）：$a_i \neq \texttt{|}$, $m = 0$；
- **Subtask 4**（15 分，依赖 Subtask 3）：$m \leq 3$；
- **Subtask 5**（25 分，依赖 Subtask 1）：$n \leq 5 \times 10^4$；
- **Subtask 6**（30 分，依赖 Subtask 1, 2, 3, 4, 5）：无特殊限制。


title: [USACO05OPEN] Landscaping G

description:
农夫约翰正在做一次艰难的转型，从养山羊改成养奶牛，他的农场，由于是为养山羊而设计的所以有太多的山，为了养牛就必须将它整平。但是，将山整平是件很花钱的工作，所以他要移走尽可能少的土。

由于农场很细长，所以可以用一个 $n$ 和 $n$ 个整数（范围 $[1,10^6]$）组成的二维的数组来表示，如：

```
1 2 3 3 3 2 1 3 2 2 1 2
```

上述农场的侧面图是这样的：

```
    * * *     *
  * * * * *   * * *   *
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2
```

一个或是一些连续等高的地面，如果它左边或是右边的海拔都比它低的话，就被称为山顶，上面的例子就有三个山顶。 确定如果要使地图上仅有 $k$ 个山顶，至少要移走多少体积的土（每块地面减少一单位海拔需移走一单位的土）。注意，地面的海拔只能被降低不能被升高。 对于例子，如果要减少到只有 $1$ 个山顶，这需要移走 $2+1+1+1=5$ 个单位的土（`-` 表示移走的土）：

```
    * * *     -
  * * * * *   - - -   -
* * * * * * * * * * * *
1 2 3 3 3 2 1 3 2 2 1 2
```

inputFormat:
第 $1$ 行输入整数 $n$ 和 $k$。

之后 $n$ 行，每行输入一个整数，表示这块地的海拔。

outputFormat: 如果仅能有 $k$ 个山顶至少要移走多少土。


title: [USACO05OPEN] Around the world G

description:
这些年，农夫约翰在国际上交了一大批开农场的朋友。由于他有一段时间没有去见过英国的农夫泰德和荷兰的农夫波尔，所以他想去拜访他们。

他知道每个朋友的农场的经度（是一个从 $0$ 到 $359$ 的整数，我们把地球看成一个圆，经度在此圆上顺时针方向递增）。

农夫约翰打算乘飞机去拜访他的 $n$ 个朋友（用 $1$ 到 $n$ 来表示）。他知道在这些农场之间有 $m$ 条双向的航线。飞机是沿着地面上最短的路径飞行的（就是圆上的最短弧长）。两个农场之间的航线一定是最短的。

保证如果有两个农场在直径两端，那么它们之间一定不会被某条航线直接连接。

所以任何一次航行都可以被描述成顺时针或是逆时针的．比如说，经度 $30$ 到经度 $35$ 是顺时针的，经度 $350$ 到经度 $10$ 也是顺时针的，而经度 $350$ 到经度 $200$ 是逆时针的。

农夫约翰为了耍酷，决定要经过几个朋友的农场做到环球旅行，他想知道这是否可能，如果可能最少要乘几次飞机。

他想在他最好的朋友（即输入中的第一个）的农场上开始和结束这次旅行。为了保证这是一次环球航行，结束旅行，顺时针经过的路程不能等于逆时针经过的路程。

inputFormat:
第一行两个用空格隔开的整数 $n$ 和 $m$。

第二到 $n+1$ 行：第 $i+1$ 行有一个整数，表示第 $i$ 个农场的经度。第二行是他的最好的朋友的地址。

第 $n+2$ 过程 $n+m+1$ 行：第 $i+n+1$ 行有两个整数，表示这两个农场之间有航线。

outputFormat: 一个整数，表示农夫约翰至少要乘几次飞机才能完成环球旅行。每次农夫约翰从一个农场前往另一个农场算作乘一次飞机。如果不可能做到环球旅行则输出 `-1`。

hint: 对于 $100\%$ 的数据，$1 \leq n \leq 5 \times 10^3$，$1 \leq m \leq 2.5 \times 10^4$。


title: [USACO05OPEN] Expedition G

description:
一群奶牛抢了一辆卡车决定前往树林里探险，但是由于它们的驾驶技术太糟，油箱在路上给弄破了，所以它们每前进一个单位的路程就会漏掉一个单位的油。

为了修好油箱，奶牛们必须前往最近的城市（不会超过 $10^6$ 单位路程）。
在当前位置和城市之间有 $n$ 个加油站．奶牛可以在加油站加 $1$ 到 $100$ 单位的油。

对于人来说，树林是个危险的地方；对奶牛来说，更是这样。  所以，奶牛要尽可能的少停站加油，幸运的是，这辆卡车的油箱非常大，你可以认为它的容量是无穷大的。
卡车在离城 $l$ 个单位时还有 $p$ 个单位的油，你要算出奶牛们至少要停几站才能到城市，或者奶牛们根本到不了城市。

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

第二到 $n+1$ 行，每行有两个用空格隔开的整数，描述一个加油站。第一个数表示这个加油站离城市的距离，第二个数表示在这个加油站最多可以加多少油。

第 $n+1$ 行：两个用空格分开的整数 $l$ 和 $p$。

outputFormat: 一个表示卡车到城市最少要停的次数，如果无法到达输出 `-1`。


title: [USACO05OPEN] Lazy Cows G

description:
地母是这个世界上大地的主宰，在她眼中整个大地呈现两行 $n$ 列的一个状态。在这个大地上如珍珠般散落着各种宝藏，每个宝藏占据一个格子。不过这个消息让天公知道了，他想抢走这些宝藏。地母决定用「无极」牌帆布盖住这些宝藏。

「无极」牌帆布是矩形状的，而且地母现在手头比较紧，她决定用 $k$ 块帆布盖住所有的宝藏。现在希望你求出这 $k$ 块帆布的面积之和的最小值。

inputFormat: 第一行给出三个数，分别代表宝藏的个数 $m$，帆布的张数 $k$，以及整个大地所呈现的列数 $n$，下面 $m$ 行给出两个数，代表每个宝藏所在的位置。

outputFormat: 输出一行一个数，帆布面积之和的最小值。

hint: 对于 $100\%$ 的数据，$1 \leq n \leq 1.5 \times 10^7$，$1 \leq k \leq m \leq 10^3$。


title: [EC Final 2021] Check Pattern is Good

description:
Prof. Shou is given an $n\times m$ board. Some cells are colored black, some cells are colored white, and others are uncolored.

Prof. Shou likes **check patterns**, so he wants to color all uncolored cells and maximizes the number of check patterns on the board.

$4$ cells forming a $2\times 2$ square are said to have the check pattern if they are colored in one of the following ways:

```plain
BW
WB
```

```plain
WB
BW
```

Here `W` ("wakuda" in Chewa language) means the cell is colored black and `B` ("biancu" in Corsican language) means the cell is colored white.

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

The first line of each test case contains two integers $n$ and $m$ ($1\le n, m\le 100$) denoting the dimensions of the board.

Each of the next $n$ lines contains $m$ characters. The $j$-th character of the $i$-th line represents the status of the cell on the $i$-th row and $j$-th column of the board. The character is `W` if the cell is colored black, `B` if the cell is colored white, and `?` if the cell is uncolored.

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

outputFormat:
For each test case, output a line containing the maximum number of check patterns on the board.

In the next $n$ lines, output the colored board in the same format as the input. The output board should satisfy the following conditions.

- It consists of only `B` and `W`.
- If a cell is already colored in the input, its color cannot be changed in the output.
- The number of check patterns equals the answer you print.

If there are multiple solutions, output any of them.

translation:
#### 题目描述

教授 Shou 得到了一个 $(n \times m)$ 的棋盘。一些格子被涂成了黑色，一些被涂成了白色，还有一些没有上色。

教授 Shou 喜欢**棋盘图案**，所以他想给所有未上色的格子涂色，并最大化棋盘上的棋盘图案数量。

如果四个形成一个 $(2 \times 2)$ 方格的单元格以以下任一种方式上色，则说它们形成了一个棋盘图案：

`BW `

`WB`

或者

`WB `

`BW`

这里的 `W`（在奇瓦语中是“wakuda”，意为黑色）表示格子被涂成了黑色，而 `B`（在科西嘉语中是“biancu”，意为白色）表示格子被涂成了白色。

#### 输入格式

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

每个测试用例的第一行包含两个整数 $n$ 和 $ m$ $(1 \leq n, m \leq 100)$，表示棋盘的尺寸。

接下来的 $n$ 行每行包含 $m$ 个字符。第 $i$ 行的第 $j$ 个字符表示棋盘上第 $i$ 行和第 $j$ 列的格子的状态。如果格子被涂成了黑色，则字符为 `W`；如果格子被涂成了白色，则字符为 `B`；如果格子未上色，则字符为 `?`。

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

#### 输出格式

对于每个测试用例，输出一行，包含棋盘上的最大棋盘图案数量。

在接下来的 (n) 行中，以输入格式相同的方式输出上色后的棋盘。输出的棋盘应满足以下条件：

* 只包含 `B` 和 `W`。
* 如果输入中的格子已经上色，则在输出中不能改变其颜色。
* 棋盘图案的数量等于你打印的答案。

如果有多种解决方案，输出其中任何一种。


title: [EC Final 2021] Future Coder

description: Prof. Pang builds his famous coding team recently. To pursue a gold medal in ICPC, hundreds of pupils join his team. Unfortunately, one of Prof. Pang's students believes that for any integers $a$ and $b$, $a\times b\ge a+b$. To disprove this proposition, Prof. Pang writes $n$ numbers $a_1,a_2,\ldots, a_n$ on a paper and wants you to count how many pairs of numbers $(a_i, a_j)$ ($1\le i < j\le n$) satisfies $a_i\times a_j<a_i+a_j$.

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

For each test case, the first line contains a single integer $n$ ($1\le n\le 10^6$). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9\le a_i\le 10^9$).

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

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

translation:
### 题目描述

共 $T$ 组数据，每组给出一个数 $n$ 和 $n$ 个数 $a_1,a_2,...,a_n$，求有多少个二元组 $(a_i,a_j)$ 满足 $a_ia_j<a_i+a_j$。

### 输入格式

第一行为一个数 $T$。

接下来 $T$ 组数据，每组数据第一行为一个数 $n$，第二行为 $n$ 个数 $a_1,a_2,...,a_n$。

### 输出格式

$T$ 行，为满足 $a_ia_j<a_i+a_j$ 的二元组 $(a_i,a_j)$ 的组数。

Translated from [FurippuWRY](https://www.luogu.com.cn/user/993779)。


title: [EC Final 2021] Elden Ring

description:
Prof. Pang is getting addicted to the game called Elden Ring, in which the world is a connected graph including $n$ vertices indexed from $1$ to $n$ and $m$ undirected edges. Players start at vertex $1$ and travel across the world to slay the god on vertex $n$.

However, it's not that easy. For any vertex $i$ except vertex $1$, there is exactly one boss whose level is $l_i$, and the player starts the game with level $l_1$. For each day, the player can travel to any vertex $i$ from vertex $1$ and challenge the boss there. If the current level of the player is greater than the boss, the boss will be eliminated from the world (inactivated) and the level of the player will be increased by $A$. Notice that traveling through a vertex that has an active boss is forbidden. (In other words, Prof. Pang can travel from vertex $1$ to vertex $i$ if there is a path in the graph from vertex $1$ to vertex $i$ such that each vertex on this path, except for vertex $i$, has no active boss.) Meanwhile, at the beginning of each day, all the remaining bosses in the world will also be promoted by $B$ levels.

To finish a playthrough of the game, you need to slay the boss on vertex $n$ (Elden Beast). Given the information of the world, Prof. Pang is wondering how many days he needs at least to do so.

The Player can only challenge one boss each day.

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

For each test case, the first line includes four integers $n, m, A, B~(2\leq n\leq 2\times 10^5, 1 \le m, A, B\le 2\times 10^5)$. In next $m$ lines, each line contains two integers $a_i, b_i~(1 \le a_i, b_i \le n)$, denoting the endpoints of the $i$-th undirected edge. The last line contains $n$ integers $l_i~(1 \le l_i \le 2 \times 10^5)$, representing the initial levels of the player and bosses mentioned above.

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

outputFormat: For each test case, output a single line containing an integer, indicating the minimum number of days Prof. Pang needs to finish the game. If it is impossible to do so, please output $-1$.

translation:
有一个 $n$ 个节点 $m$ 条边的无向图，每个节点 $i$ 上有一个初始等级为 $l_i$ 的 boss。玩家开始时位于 1 号节点，初始等级为 $l_1$。（保证 1 号节点没有 boss）

每天开始后，玩家从 1 号节点开始，经过**没有 boss** 的节点到达一个有 boss 的节点 $i$，并击杀节点 $i$ 的 boss。玩家等级必须大于 boss 的等级才能将 boss 击杀，且每天只能击杀一个 boss。

每击杀一个 boss，玩家的等级会增加 $A$。每天开始时，所有**仍存在**的 boss 等级增加 $B$。输出至少需要多少天才能击杀节点 $n$ 的 boss 并通关，如果不能通关输出  -1 。


title: [EC Final 2021] Vision Test

description:
Prof. Pang has an extraordinary vision. He can see the pixels on a 4K monitor. To test Prof. Pang's vision, Prof. Shou will show Prof. Pang several pixels and let Prof. Pang guess a straight line that contains these pixels. Given $k$ pixels with coordinates $(i, y_i)$ ($0\le i<k$), Prof. Pang must find nonnegative integers $a, b$ and $c$ (which represent the line $y=\frac{ax+b}{c}$) such that $y_i=\lfloor \frac{ai+b}{c} \rfloor$ for all $0\le i<k$.

Prof. Shou will ask Prof. Pang multiple questions. They are given as follows: Prof. Shou has a fixed array $x_1,\ldots, x_n$. For each question, Prof. Shou chooses a range in the array, $x_l,\ldots, x_r$. Then he defines $y_i=x_{l+i}$ for $0\le i\le r - l$ and asks Prof. Pang to answer the question for the $r-l+1$ pixels $(0, y_0), \ldots, (r-l, y_{r-l})$.

Please help Prof. Pang answer all the questions. For each question, output the answer with the **minimum** $(c, a, b)$ **in lexical order**.

It is guaranteed that the answer exists when Prof. Pang chooses the whole array $x_1, x_2, \dots, x_n$. So the answer always exists when Prof. Pang chooses an interval of this array.

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

For each test case, the first line contains an integer $n$ ($1\leq n\leq 10^5$). The second line contains $n$ numbers $x_1, \ldots , x_{n}$ ($0\leq x_i\leq 10^9$).

The next line contains an integer $q$ ($1\le q\le 10^5$) denoting the number of questions.

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

It is guaranteed that the sum of $n$ over all test cases will not exceed $10^5$ and that the sum of $q$ over all test cases will not exceed $10^5$.

outputFormat: In the order of input, output one line with three integers $a, b, c$ denoting the answer for each question.

translation:
给定一个长度为 $n$ 的数组 $x$，接下来你有 $q$ 次询问。

第 $i$ 次询问给出一个区间 $l,r$，设 $k=r-l+1$，你提取出 $x$ 数组下标在 $l,r$ 之间的区间 $y_i=x_{i+l}(0\le i<k)$。

考虑 $k$ 个点 $(0,y_0),(1,y_1)\dots(k-1,y_{k-1})$。你需要找到一条直线的三个整数参数 $a,b,c$，满足 $\forall 0\le i<k,y_i=\lfloor \frac{ai+b}{c}\rfloor$。若有多条这样的直线，输出 $(c,a,b)$ 三元组字典序最小的一个。

保证对于整个数组，即 $l=1,r=n$ 的询问一定存在一组合法的解。

$n,q\le 10^5$，多组询问。


title: [EC Final 2021] Fenwick Tree

description:
Prof. Pang is giving a lecture on the Fenwick tree (also called binary indexed tree).

In a Fenwick tree, we have an array $c[1\ldots n]$ of length $n$ which is initially all-zero ($c[i]=0$ for any $1\le i\le n$). Each time, Prof. Pang can call the following procedure for some position $pos$ ($1\leq pos \leq n$) and value $val$:

```cpp
def update(pos, val):
    while (pos <= n):
        c[pos] += val
        pos += pos & (-pos)
```

Note that `pos & (-pos)` equals to the maximum power of $2$ that divides `pos` for any positive integer `pos`.

In the procedure, $val$ can be **any real** number. After calling it some (zero or more) times, Prof. Pang forgets the exact values in the array $c$. He only remembers whether $c[i]$ is zero or not for each $i$ from $1$ to $n$. Prof. Pang wants to know what is the minimum possible number of times he called the procedure assuming his memory is accurate.

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

For each test case, the first line contains an integer $n~(1 \le n \le 10 ^ 5)$. The next line contains a string of length $n$. The $i$-th character of the string is `1` if $c[i]$ is nonzero and `0` otherwise.

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

outputFormat: For each test case, output the minimum possible number of times Prof. Pang called the procedure. It can be proven that the answer always exists.

translation:
定义一次「操作」为选定任意一个 $pos$ 和 $val$ 后对 $c$ 序列进行以下操作（显然就是树状数组的单点加操作）：

```python
def update(pos, val):
    while (pos <= n):
        c[pos] += val
        pos += pos & (-pos)
```

给定序列长度 $n$ 和一个长度为 $n$ 的 $\texttt{01}$ 串 $s$，以及一个初始全为 $0$ 的序列 $c$。 求最少的操作数使得最终的 $c$ 序列满足 $\forall 1\le i\le n: s_i=\texttt0 \Leftrightarrow c_i=0,s_i=1\Leftrightarrow c_i\not=0$。

你只需要输出最少的操作数。

hint:
For the first example, Prof. Pang can call `update(1,1)`, `update(2,-1)`, `update(3,1)` in order.

For the third example, Prof. Pang can call `update(1,1)`, `update(3,1)`, `update(5,1)` in order.


title: [EC Final 2021] Prof. Pang and Ants

description:
Near Prof. Pang's big house, there is an ant group which has $m$ ants and lives underground in a cave with $n$ holes. They get out of the holes for food. So where is the food? It should be in Prof. Pang's big refrigerator. The ants want to steal the food from the big refrigerator.

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

Specifically, for an ant, it needs $1$ second to leave from the cave through any hole and $1$ second to enter the cave through any hole. Different holes have different locations. The distance between the $i$-th hole and the refrigerator is $a_i$. Thus, after leaving the cave through the $i$-th hole, an ant needs $a_i$ seconds to go to the refrigerator. After stealing some food from the refrigerator, an ant needs $a_i$ seconds to go back to the $i$-th hole. Stealing food costs no time for the ants since they are skillful enough.

Each ant will leave the cave to steal something from the refrigerator and return to (enter) the cave after stealing. Each ant must leave the cave exactly once and then return to the cave. One ant can arbitrarily choose one hole to leave and also arbitrarily choose one hole to enter, where the two holes need not be the same. For any hole, during any second, there can be at most one ant leaving or entering the cave through it. There cannot be one ant leaving the cave and another ant entering the cave using the same hole during the same second. Because of this capacity constraint, some ants may need to wait before they leave the hole and/or before they return to the hole after stealing.

So you, Prof. Pang's good friend, need to calculate the minimum time cost for ants to achieve the goal and play a trick on Prof. Pang so that the ants can steal the food without being caught by Prof. Pang. The time cost is defined as the total length of time during which at least one ant is not in the cave. When an ant is entering or leaving the cave through some hole, it is not in the cave.

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

For each test case, the first line contains two integers $n,m$ ($1\le n \le 10^5, 1\le m \le 10^{14}$) denoting the number of the holes and the number of the ants respectively. The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1\le a_i \le 10^9$) denoting the time needed to get to the refrigerator from the $i$-th hole.

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

outputFormat: For each test case, print one line containing one integer denoting the minimum time cost in seconds.

translation:
在庞教授的大房子边上，有一群包含 $m$ 只蚂蚁的蚁群，居住在有 $n$ 个洞口的洞穴里。 它们会外出寻找食物。食物在庞教授的大冰箱里，蚂蚁们试图从里面偷出食物来。

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

**传神.jpg**

特别的, 一只蚂蚁需要 $1$ 秒从任何洞口离开，并同样需要 $1$ 秒从任何洞口进入洞穴。不同的洞口有不同的位置，对一个洞口来说，它与冰箱的距离以 $a_i$ 表示，同样的，一只蚂蚁从冰箱偷出食物再到第i个洞口的时间也是 $a_i$ 秒。由于蚂蚁们技术高超，从冰箱拿出食物不会消耗它们任何时间。

每只蚂蚁都必须且只能从冰箱偷一次食物。蚂蚁可以任意选择一个洞口出发并进入任何一个洞口，前提是它们不是相同的。一个洞口在 $1$ 秒内只能有一只蚂蚁进出。因为这个原因，有些蚂蚁在偷完食物后需要等待一段时间才能进入洞口。

所以，你作为庞教授的好朋友， 需要计算出蚂蚁们偷出食物的最短时间。时间的定义为至少存在一只蚂蚁在洞穴外的时间总长，正在进出洞口的蚂蚁不被看作在洞穴里。

## 输入格式

第一行包括一个整数 $T~(1 \le T \le 10^5)$ ，表示测试数据的总数。

对每组测试数据：

第一行包括两个整数 $n,m$  ($1\le n \le 10^5, 1\le m \le 10^{14}$) ，分别代表洞口的总数与蚂蚁的总数。

第二行包括 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1\le a_i \le 10^9$)， 表示第$i$号洞口到冰箱的距离。

数据保证所有数据中 $n$ 的总和不超过 $5\times 10^5$.

## 输出格式

对每组数据，输出一行一个整数代表蚂蚁所用最短时间的秒数。

## 样例 #1

### 样例输入 #1

```
3
2 4
1 2
3 10
1 2 3
5 1
1 2 3 4 5
```

### 样例输出 #1

```
6
9
4
```

## 提示

在第三组测试数据中，蚂蚁需要 $2$ 秒通过第一个洞口进出洞穴，并需要 $2$ 秒前往冰箱并搬回食物。

hint: In the third test case, it takes the ant $2$ seconds to leave and enter the cave through the first hole. And it takes the ant $2$ seconds to move to the refrigerator and back to the hole.


title: [入门赛 #17] 方程求解

description:
小 A 有 $n$ 个关于 $x$ 的方程，第 $i$ 个方程形如 $a_ix_i+b_i=c_i$。方程的解 $x$ 均为正整数，例如下面几个方程都是符合要求的方程：

```
2x+4=10
-3x+13=10
4x-8=16
```

其中，第一组方程的解为 $x_1=3$，第二组方程的解为 $x_2=1$，第三组方程的解为 $x_3=6$。

小 A 想要知道，给定 $L,R$，在 $L\leq x\leq R$ 的范围内，有多少个正整数 $x$ 满足 $x$ 是其中至少一个方程的解。为了防止你欺骗他，他会询问你 $Q$ 次。

inputFormat:
第一行输入两个正整数 $n,Q$，分别表示小 A 有的方程数，以及小 A 想要向你询问的次数。

第二行开始，往下 $n$ 行，每行一个字符串，描述一个方程。

第 $(n+2)$ 行开始，往下 $Q$ 行，每行两个正整数 $L,R$，表示一次询问，即给定 $L,R$，询问在 $L\leq x\leq R$ 的范围内，有多少个正整数 $x$ 满足 $x$ 是其中至少一个方程的解。

outputFormat: 对于每次询问，输出一行一个整数，表示有多少个在 $L\leq x\leq R$ 的范围内的正整数 $x$，满足 $x$ 是其中至少一个方程的解。

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

对于第一组样例，即为题目中的举例。三组方程的解分别为 $x_1=3,x_2=1,x_3=6$。则：

- 对于 $1\leq x\leq 6$ 的范围，有 $3$ 个 $x$ 的取值（$x=1,3,6$）是其中至少一个方程的解；
- 对于 $1\leq x\leq 8$ 的范围，同上所述；
- 对于 $3\leq x\leq 6$ 的范围，有 $2$ 个 $x$ 的取值（$x=3,6$）是其中至少一个方程的解；
- 对于 $4\leq x\leq 5$ 的范围，不存在一个 $x$ 是其中至少一个方程的解；
- 因此分别输出 $3,3,2,0$。

对于第二组样例，五组方程的解分别为 $x_1=3,x_2=5,x_3=5,x_4=3,x_5=3$。则：

- 对于 $1\leq x\leq 3$ 的范围，只有 $x=3$ 满足是其中至少一个方程的解；
- 对于 $1\leq x\leq 5$ 的范围，有 $2$ 个 $x$ 的取值（$x=3,5$）是其中至少一个方程的解；
- 对于 $3\leq x\leq 5$ 的范围，有 $2$ 个 $x$ 的取值（$x=3,5$）是其中至少一个方程的解；
- 因此分别输出 $1,2,2$。

**【数据范围】**

数据保证，$1\leq n,Q\leq 2\times 10^5$，方程中 $a_i,b_i,c_i$ 满足 $1 \leq |a_i|,|b_i|,|c_i| \leq 10^9$，每一组方程的解 $x_i$ 必定为正整数。询问时的 $L,R$ 满足 $1\leq L\leq R\leq 2\times 10^9$。

本题输入数据较大，请注意代码输入输出的运行效率。


title: [语言月赛 202311] 食堂

type: B

description:
为了给师生提供良好的用餐体验，洛谷小学的食堂坚持现炒、现做每一道菜肴。

洛谷小学一共有 $a$ 名老师和 $b$ 名学生。食堂的营养师为每位师生的用餐进行配额：

- 一名学生，一次用餐需要 $R$ 克米饭，$V$ 克蔬菜，$M$ 克肉。
- 一名老师，一次用餐需要 $2R$ 克米饭，$3V$ 克蔬菜，$3M$ 克肉。

洛谷小学的食堂一天需要烹制两餐，分别为中午一餐、晚上一餐。其中，中午的一餐，学生和老师都需要，而晚上的一餐仅有老师需要。

现在请问，洛谷小学的食堂，一天要准备多少克米饭，多少克蔬菜，多少克肉呢？

inputFormat: 输入一行，五个正整数 $a,b,R,V,M$，分别表示老师的人数、学生的人数，以及一名学生一次用餐需要的米饭、蔬菜和肉的量。

outputFormat: 输出一行，三个正整数，分别表示洛谷小学的食堂一天要准备多少克米饭，多少克蔬菜，多少克肉。

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

对于样例 $1$，洛谷小学有 $5$ 个老师和 $10$ 个学生。每天每个学生吃 $1$ 餐，每个老师吃 $2$ 餐，因此：

- 一个学生一餐吃 $200$ 克米饭。因此需要准备：$1\times 10\times 200+2\times 5\times 400=6000$ 克米饭。
- 一个学生一餐吃 $100$ 克蔬菜。因此需要准备：$1\times 10\times 100+2\times 5\times 300=4000$ 克蔬菜。
- 一个学生一餐吃 $150$ 克肉，因此需要准备：$1\times 10\times 150+2\times 5\times 450=6000$ 克肉。

因此，输出 $6000,4000,6000$。

**【数据范围】**

对于所有数据，保证：$1\leq a,b,R,V,M \leq 10000$。


title: [语言月赛 202311] 数学选择题

description:
洛谷小学的数学考试由若干道选择题组成。选择题分为三档：简单题、中等题和困难题。每类题目都有评判标准：

- 简单题：回答正确得 $5$ 分，回答错误则不得分；
- 困难题：回答正确得 $20$ 分，回答错误倒扣 $20$ 分；

洛谷小学不鼓励学生为了做困难题而忽视基础，因此，如果简单题得到的总分，**不超过**给定的分值限制 $M$ 时，做困难题回答正确不得分，而回答错误一样倒扣 $20$ 分。同时，为了照顾学生情绪，如果学生所有题累计的得分小于 $0$，则按照 $0$ 分计算。

现在给定试卷中简单题的题数 $a$，困难题的题数 $b$，以及小 A 做对的简单题的题数 $c$，困难题的题数 $d$，以及给定的分值限制 $M$。问，小 A 最终能获得几分。

inputFormat: 输入一行，五个正整数 $a,b,c,d,M$，分别表示试卷中简单题的题数、困难题的题数、小 A 做对的简单题的题数、小 A 做对的困难题的题数以及给定的分值限制。

outputFormat: 输出一行一个整数，表示小 A 最终能获得几分。

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

- 对于样例 $1$，小 A 做对了 $7$ 道简单题获得了 $35$ 分，超过了给定的 $30$ 分限制，因此会正常计算困难题的得分。小 A 做对了 $4$ 个困难题获得 $80$ 分，但是错了一道要倒扣 $20$ 分，因此合计为 $35+80-20=95$ 分。
- 对于样例 $2$，小 A 做对了 $7$ 道简单题获得了 $35$ 分，并未超过给定的阈值 $40$，因此只计算做错困难题的倒扣分，合计为 $35-20=15$ 分。
- 对于样例 $3$，与样例 $2$ 一样，只计算做错困难题的倒扣分。小 A 只做对了 $1$ 个困难题，要倒扣 $80$ 分。此时小 A 累计的得分小于 $0$，则按照 $0$ 分作为最后的分值。

**【数据范围】**

对于所有数据，保证：$1 \leq a,b,c,d \leq 100$，$1 \leq c \leq a$，$1 \leq d \leq b$，$1 \leq M \leq 500$。


title: [语言月赛 202311] 风球

background:
与中国大陆不同，当台风即将来袭时，香港天文台将会根据情况发布 $1,3,8,9,10$ 五个等级的热带气旋警告信号。数字越大，代表台风影响越严重。当发布 $8$ 号烈风信号时，香港就会停课停工。下图为香港天文台的 $10$ 号飓风信号：

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

description:
香港天文台选定了 $8$ 个气象站。在台风影响期间，香港天文台会根据这些气象站的风速观测数据决定发布哪一个等级的预警。

- 因为已经受到台风影响，因此必然会发布 $1$ 号戒备信号；
- 若有 $4$ 个气象站的持续风力达到或超过 $41$ 千米/小时，则发布 $3$ 号强风信号；
- 若有 $4$ 个气象站的持续风力达到或超过 $63$ 千米/小时，则发布 $8$ 号烈风信号；
- 若有 $1$ 个气象站的持续风力达到或超过 $118$ 千米/小时，则发布 $10$ 号飓风信号；
- 多个条件同时满足，则发布其中最高等级的信号。

现在给定这些气象站的风力数据，请计算出香港天文台应当发布什么警告信号。

inputFormat: 输入共一行，用空格隔开的 $8$ 个正整数，表示这 $8$ 个气象站的风速观测数据。

outputFormat: 输出一行一个正整数，表示应当发布哪一个等级的警告信号。

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

第一组样例中，第一个气象观测站观测到了超过 $118$ 千米/小时的风速，因此应当发布 $10$ 号飓风信号。此为 2023 年超强台风苏拉影响香港的真实风速数据。

第二组样例中，只有 $3$ 个气象观测站的持续风力达到或超过 $41$ 千米/小时，因此只符合 $1$ 号戒备信号的标准。此为 2023 年强台风小犬影响香港的真实风速数据。

第三组样例中，恰好有 $4$ 个（第 $1,2,3,5$ 个）气象观测站的持续风力达到或超过 $63$ 千米/小时，因此符合 $8$ 号烈风信号的标准。此为 2008 年台风鹦鹉登陆香港的真实风速数据。

**【数据范围】**

对于所有风速观测数据 $x$，满足 $1 \leq x \leq 300$。


title: [语言月赛 202311] 画图练习

description:
为了培养学生的兴趣，洛谷小学的信息课上会教学生使用绘板软件，让学生在电脑上自由创作图画。

小 A 非常喜欢字符画。他打算在课上创作一幅自己的字符画。他的字符画一共有 $n$ 行，绘画规则如下：

- 第 $i$ 行的**非空格的**字符有 $i^2$ 个；
- 第 $i$ 行以**大写**的第 $i$ 个英语字母开头。每一列用其前一**非空格**列的字母的下一个填充。特别地，Z 的下一个字母是 A。
- 如果**当前列数**加上当前本应填充的字母的 ASCII 码**不为**质数，则跳过该列（用空格填充），直到列数加上本应填充的字母的 ASCII 码为质数为止。

请绘画出小 A 的字符画。

inputFormat: 输入一个正整数 $n$，表示这是一个 $n$ 行的字符画。

outputFormat: 输出 $n$ 行字符，表示这是小 A 创作的字符画。

samples:
 A
B  CD    E
   CD    E  F    G      H  IJ  K

samples:
 A
B  CD    E
   CD    E  F    G      H  IJ  K
  DE    F  G    H      I  JK  LM  N            O  P    QR        S
 EF    G  H    I      J  KL  MN  O            P  Q    RS        TU    V    W  X    Y    Z  A    B  C
FG    H  I    J      K  LM  NO  P            Q  R    ST        UV    W    X  Y    ZAB    C    D  E    F    GH        IJ  KL          M          N  O

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

对于样例 $1$：

- 第一行应当以第一个大写字母，即 A 开头。但是 A 的 ASCII 码是 $65$，加上列数 $1$，为 $66$，其并不是质数（$66=2\times 3\times 11$），因此第一列为空。而第二列，$65+2=67$，为质数，因此在第二列输出 A。此时已经输出了 $1^2$ 个字母，故换行。

- 第二行应当以第二个大写字母，即 B 开头。B 的 ASCII 码是 $66$，加上列数 $1$，为 $67$，为质数。因此第一列就输出 B。随后应当输出下一个英语字母 C。C 的 ASCII 码为 $67$，加上列数 $2$，为 $69=3\times 23$，不为质数，用空格跳过。而直到第四列，$67+4=71$ 为质数，因此在第四列输出 C。同理，在第五列输出 D，在第 $10$ 列输出 E。

对于样例 $2$：

- 该样例的第五第六行体现了 Z 的下一个字母是 A。

**【数据范围】**

对于所有数据，$1\leq n\leq 26$。


title: [语言月赛 202311] 式神考核

background: 作为隙间妖怪的式神的式神，橙自然需要接受蓝的考核。**源**于八云紫的严格要求被蓝带给了橙喵。橙喵在考核中不仅要接受精**神**的摧残，也要经历肉体的考验，以此得到**启**发，成为**动**物妖怪中首屈一指的存在。

description:
蓝给橙喵的考核题一共有 $n$ 道，总分为 $10^7$ 分，每道题的分值为 $\dfrac {10^7} n$。根据橙喵的完成情况，蓝可能会给出满分、给出一半的分数或不得分。另外，在所有获得满分的题目中，有一部分橙喵完成得特别好，因此蓝给她加上了每道题 $1$ 分的附加分。由于橙喵得到的分数可能是个小数，因此蓝决定将分数下取整得到最后的总分。

在橙喵完成了所有的考核之后，蓝给出了未得到满分的题目数量 $m$ 和加上附加分的总分 $s$。蓝希望橙喵告诉她，每种得分的题目分别有几道。

橙喵被难住了，因此找到了你，希望你写一个程序帮帮她。
可以证明的是，在这样的规则和数据范围下，**答案是唯一的。**

inputFormat: 一行三个整数 $n$，$s$，$m$。

outputFormat: 蓝希望你按照 `pA(+B) fC lD` 的格式给出可能的答案，其中 $A,B,C,D$ 均为整数，$A$ 为所有得满分的题目总数，$B$ 为获得附加分的题目数量，$C$ 为获得一半分的题目数量， $D$ 为不得分的题目数量。保证**有一个可行解。**


title: [语言月赛 202311] 表格处理

description:
小 A 有一张 $2\times n$ 行，$2\times m$ 列的表格。表格上每一行、每一列都有一个正整数。他将对表格先进行一次合并操作，再进行一次转置操作。

对于一个 $2\times n$ 行，$2\times m$ 列的表格 $A$，进行一次合并操作得到一个 $n$ 行 $m$ 列的表格 $A'$ 的流程为：

- 将奇数列的每个数加上其右侧相邻的数，之后删除所有的偶数列，给每一列重新编号为第 $1,2,3,\dots,m$ 列；
- 将奇数行的每个数加上其下侧相邻的数，之后删除所有的偶数行，给每一行重新编号为第 $1,2,3,\dots,n$ 行；

对于一个 $n$ 行 $m$ 列的表格 $A$，进行一次转置操作得到一个 $m$ 行 $n$ 列的表格 $A^T$ 的流程为：

- 对于所有的 $i,j$，令 $A^T_{i,j}=A_{j,i}$；

小 A 想要知道经过这样两次操作后表格会是什么样的。请输出该表格。

**本题的输入输出规模较大，特别是对使用 Java/Python 等非传统语言的选手，请使用相对快速的输入输出方式。**

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

第二行到第 $2\times n+1$ 行，每行输入 $2\times m$ 个正整数，表示表格上每一行每一列的值。

outputFormat: 输出一个 $m$ 行 $n$ 列的表格，表示经过两次操作后表格会是什么样的。同一行内的正整数之间用空格隔开。

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

对于样例一给出的表格，其是经过这些变换得到的：

$\begin{bmatrix}2 & 7 & 1 & 8 \\ 1 & 8 & 2 & 8 \\ 3 & 1 & 4 & 1 \\ 5 & 9 & 2 & 6 \end{bmatrix} \underrightarrow{删除列} \begin{bmatrix} 9 & 9 \\ 9 & 10 \\4 & 5 \\ 14 & 8 \\\end{bmatrix} \underrightarrow{删除行} \begin{bmatrix} 18 & 19 \\ 18 & 13\end{bmatrix} \underrightarrow{转置} \begin{bmatrix} 18 & 18 \\19 & 13\end{bmatrix}$

**【数据范围】**

对于所有数据，保证：$1 \leq n,m \leq 1000$，$1 \leq a_i \leq 10^6$。


title: [语言月赛 202311] 基因

description:
有一个长度为 $n$ 的字符串 $S$。其只包含有大写字母。

小 A 将 $S$ 进行翻转后，得到另一个字符串 $S'$。两个字符串 $S$ 与 $S'$ 对应配对。例如说，对于 $S=\tt{ATCGT}$，则有 $S'=\tt{TGCTA}$，$S$ 与 $S'$ 进行配对。

对于两个字符串 $S,S'$ 的第 $i$（$1 \leq i \leq n$）个字母，配对规则如下：

- 定义 $\tt A$ 与 $\tt T$，$\tt C$ 与 $\tt G$ 为可以配对的字母。
- 如果 $S_i$ 与 $S_i'$ 为可以配对的字母，那么该字符串的稳定性增加 $i$。
- 如果 $S_i$ 或者 $S_i'$ 中任意一方出现非 $\tt A,\tt T,\tt C,\tt G$ 的字母，则整个字符串的稳定性将直接为 $0$。

现在给定 $T$ 个字符串 $S$，对每一个字符串，询问若用其翻转再进行配对，其稳定性将如何。

inputFormat:
第一行输入一个正整数 $T$，表示给定多少个字符串。对于每一个字符串：

- 第一行输入一个正整数 $n$，表示字符串的长度；
- 第二行输入一个字符串 $S$，表示该字符串。

outputFormat: 对于每个字符串，输出一行一个整数，表示若用其翻转再进行配对，其稳定性将如何。

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

- 对于第一个字符串，$S=\tt{\red{A}TCG\blue{T}}$，$S'=\tt{\red{T}GCT\blue{A}}$。标红色的一组与蓝色的一组为可以配对的字母。它们分别是 $S$ 的第 $1$ 个字母和第 $5$ 个字母，因此稳定性是 $1+5=6$。
- 对于第二个字符串，$S=\tt{\red{A}\blue{C}\red{A}\blue{T}\red{G}\blue{T}}$，$S'=\tt{\red{T}\blue{G}\red{T}\blue{A}\red{C}\blue{A}}$，每个对应位置上的字母都可以配对，因此稳定性是 $1+2+3+\dots+6=21$
- 对于第三条字符串，出现了非 $\tt A,\tt T,\tt C,\tt G$ 的字母 $\tt U$，因此稳定性为 $0$。

**【数据范围】**

对于所有数据，保证：$1\leq T\leq 5$，$1\leq n\leq 10^5$，$S$ 中出现的所有字母保证为大写英语字母。


title: [语言月赛 202311] 方程求解

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

对于第一组样例，即为题目中的举例。三组方程的解分别为 $x_1=3,x_2=1,x_3=6$。则：

- 对于 $1\leq x\leq 6$ 的范围，有 $3$ 个 $x$ 的取值（$x=1,3,6$）是其中至少一个方程的解；
- 对于 $1\leq x\leq 8$ 的范围，同上所述；
- 对于 $3\leq x\leq 6$ 的范围，有 $2$ 个 $x$ 的取值（$x=3,6$）是其中至少一个方程的解；
- 对于 $4\leq x\leq 5$ 的范围，不存在一个 $x$ 是其中至少一个方程的解；
- 因此分别输出 $3,3,2,0$。

对于第二组样例，五组方程的解分别为 $x_1=3,x_2=5,x_3=5,x_4=3,x_5=3$。则：

- 对于 $1\leq x\leq 3$ 的范围，只有 $x=3$ 满足是其中至少一个方程的解；
- 对于 $1\leq x\leq 5$ 的范围，有 $2$ 个 $x$ 的取值（$x=3,5$）是其中至少一个方程的解；
- 对于 $3\leq x\leq 5$ 的范围，有 $2$ 个 $x$ 的取值（$x=3,5$）是其中至少一个方程的解；
- 因此分别输出 $1,2,2$。

**【数据范围】**

数据保证，$1\leq n,Q\leq 1000$，方程中 $a_i,b_i,c_i$ 满足 $1 \leq |a_i|,|b_i|,|c_i| \leq 2000$，每一组方程的解 $x_i$ 必定为正整数。询问时的 $L,R$ 满足 $1\leq L\leq R\leq 1000$。

本题前八个测试点每个测试点 8 分，后四个测试点每个测试点 9 分。


title: [EC Final 2021] DFS Order

description:
Prof. Pang has a rooted tree which is rooted at $1$ with $n$ nodes. These $n$ nodes are numbered from $1$ to $n$.

Now he wants to start the depth-first search at the root. He wonders for each node $v$, what is the minimum and the maximum position it can appear in the $\textbf{depth-first search order}$. The depth-first search order is the order of nodes visited during the depth-first search. A node appears in the $j$-th ($1\le j\le n$) position in this order means it is visited after $j-1$ other nodes. Because sons of a node can be iterated in arbitrary order, multiple possible depth-first orders exist. Prof. Pang wants to know for each node $v$, what are the minimum value and the maximum value of $j$ such that $v$ appears in the $j$-th position.

Following is a pseudo-code for the depth-first search on a rooted tree. After its execution, $\texttt{dfs\_order}$ is the depth-first search order.

```
let dfs_order be an empty list

def dfs(vertex x):
    append x to the end of dfs_order.
    for (each son y of x): // sons can be iterated in arbitrary order.
        dfs(y)

dfs(root)
```

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

For each test case, the first line contains an integer $n~(1 \le n \le 10 ^ 5)$. Each of the next $n-1$ lines contains two integers $x$ and $y$, indicating node $x$ is node $y$'s parent ($1\le x, y\le n$). These edges form a tree rooted at $1$.

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

outputFormat: For each test case, print $n$ lines. The $i$-th line contains two integers denoting the minimum and the maximum position node $i$ can appear in the depth-first search order.

translation: 给定一棵以 $1$ 为根节点的树，若按**任意顺序**进行深度优先搜索，则第 $i$ 个点最小是第几个被搜到的以及最大是第几个？


title: [EC Final 2021] Beautiful String

description:
Prof. Pang recently got a dictionary of the elvish language, including many strings representing their words. He thinks a partition of string $s$ is beautiful if both of the following conditions are satisfied:

- $s = s_1 + s_2 + s_3 + s_4 + s_5 + s_6$, where $s_i (1\leq i\leq 6)$ are nonempty substrings. $a + b$ means the concatenation of string $a$ and $b$ here.
- $s_1 = s_2 = s_5, s_3 = s_6$.

For example, you can partition the string ``114514`` into $6$ parts : ``114514`` = ``1`` + ``1`` + ``4`` + ``5`` + ``1`` + ``4``. The first, second, fifth parts are the same, and the third and sixth parts are the same. Thus, the partition of $s=$``114514`` into $s_1=$``1``, $s_2=$``1``, $s_3=$``4``, $s_4=$``5``, $s_5=$``1``, and $s_6=$``4`` is beautiful.

Accordingly, the beauty of a string $s$ is defined as the number of beautiful partitions of $s$.

Given a string $t$, please help Prof. Pang to figure out the sum of beauties of all substrings of $t$.

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

For each test case, there is one single line containing the string $t$, consisting of digits from `0' to `9'.

It is guaranteed that the length of each $t$ in each test case will not exceed $5000$ and the total length will not exceed $30000$.

outputFormat: For each test case, output a single line containing an integer, indicating the sum of beauties of all substrings of $t$.

translation:
当字符串 $s$ 的一个**划分**满足如下条件：

- $s = s_1 + s_2 + s_3 + s_4 + s_5 + s_6$，其中 $s_i (1\leq i\leq 6)$ 为非空子串，$a + b$ 表示将字符串 $b$ 接于 $a$ 后。

- $s_1 = s_2 = s_5, s_3 = s_6$。

则称该**划分**是**美丽的**。

字符串 $s$ 的**美丽值**定义为 $s$ 的不同的**美丽的划分**的个数。

给出字符串 $s$，求其**所有子串**的**美丽值之和**。


title: [EC Final 2021] String-dle Count

description:
While most people love to play Wordle these days, Prof. Pang has become addicted to String-dle.

String-dle is an interesting string-guessing game where the player tries to guess a string of $k$ capital letters through several rounds. In each round, the player submits a string of length $k$ as his guess, and the system grades the guess through the following pseudo-code:

```
def grading(answer, guess):
  let count be a hash map
  for i = 1 to k:
    if answer[i] not in count:
      count[answer[i]] = 1
    else:
      count[answer[i]] = count[answer[i]] + 1
  let grade be an array of length k
  for i = 1 to k:
    if answer[i] == guess[i]:
      grade[i] = 'O'
      count[guess[i]] = count[guess[i]] - 1
  for i = 1 to k:
    if answer[i] != guess[i]:
      if count[guess[i]] > 0:
        grade[i] = '-'
        count[guess[i]] = count[guess[i]] - 1
      else:
        grade[i] = 'x'
  return grade
```

The grade consisting of $\tt{O}$ (capital letter O), $\tt{-}$ (dash), and $\tt{x}$ (small letter x) is then returned to the player, and the player may base his next guess on the previous grades. The following is an example of one game Prof. Pang played:

```
G: CRANE
A: xx--x
G: UTTER
A: xxOxx
G: NASAL
A: OOxOO
G: NATAL
A: OOOOO
```

Strings after $\tt{G}$ are Prof. Pang's guesses and strings after $\tt{A}$ are the grades of the guesses.

Prof. Pang really enjoys the game. He believes that he has developed a perfect strategy for it. However, today he goes mad because he thinks the grading system is bugged! He wants to have someone write an analysis program to figure out the number of possible strings that can be the answer to the puzzle based on his list of guesses and grades.

Since the grading system might be bugged, it might not conform to the pseudo-code given above. So specifically, the task is to find how many strings that are consistent with the input. A string s is consistent with the input if for any guess g in the input and its corresponding grade d, grading(s, g)=d.

And of course, you will be doing the programming.

inputFormat:
The first line consists of two integers $n$ and $k$ $(1 \le n \le 10^4, 1 \le k \le 19)$, which are the number of guesses and the length of the string, respectively.

The following lines consist of the guesses and the grades, one per line, correspondingly.

outputFormat: An integer, denoting how many possible answers there are, modulo $10^9+7$.

hint:
For the second example:

If the answer is $\tt{ACDEF}$, the guess $\tt{BBBAA}$ will produce a grade of $\tt{xxx-x}$.


title: [EC Final 2021] Two Walls

description:
Prof. Pang has bought a humanoid cleaning robot to clean his yard. The robot is not very sophisticated. It can either move forward or change its direction at a time, all controlled by Prof. Pang's controller.

Prof. Pang's yard is a 2D plane. The robot needs to move from its current location $A$ to the destination $B$ to fulfill some ``cleaning`` needs of Prof. Pang. However, there are two straight walls $CD$ and $EF$ in Prof. Pang's yard. Since the robot is clumsy, it will fall over if it touches any of the walls (even at endpoints).

Now that Prof. Pang is lazy, he wants to minimize the number of times the robot changes its direction. Can you help him?

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

For each test case, the first line contains two integers $x_A, y_A$, the coordinates of point $A$. The second line contains two integers $x_B, y_B$, the coordinates of point $B$.
The third line contains four integers $x_C, y_C, x_D, y_D$, the coordinates of point $C$ and $D$ which are the endpoints of the first wall. The fourth line contains four integers $x_E, y_E, x_F, y_F$, the coordinates of point $E$ and $F$ which are the endpoints of the second wall.

It is guaranteed that neither the current location $A$ nor the destination $B$ of the robot are on any of the walls. A wall may degenerate to a point. It can be proved that the robot can always move from $A$ to $B$ without touching any of the walls. All values lie within $[-10^9, 10^9]$.

outputFormat: For each test case, print one number $d$ in one line, denoting the minimum number of turns.

translation:
平面直角坐标系上有两点 $A$ 与 $B$，以及两面墙 $CD,EF$，墙可以视作线段。

请问从 $A$ 到 $B$ 在不碰到墙（端点也不可碰到）的情况下最少要转几次弯（转弯的度数可以任意决定）？

hint:
The following are illustrations for the first sample and the third sample.

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

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


title: [EC Final 2021] Prof. Pang and Poker

description:
Prof. Pang is playing a card game with his two friends Alice and Bob. All cards are drawn from a standard 52-card deck. A standard 52-card deck comprises $13$ ranks in each of the four French suits: clubs ($\clubsuit$), diamonds ($\diamondsuit$), hearts ($\heartsuit$) and spades ($\spadesuit$). Each suit includes an Ace (A), a King (K), a Queen (Q), and a Jack (J), each depicted alongside a symbol of its suit; and numerals or pip cards from the Deuce (Two) to the Ten, with each card depicting that many symbols (pips) of its suit. $\textbf{No card can be drawn more than once.}$

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

Individual cards are ranked as follows (high-to-low): A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2. $\textbf{Suits do not affect ranks of the cards.}$ For example, Ace of diamonds and Ace of clubs have the same rank. No one of them is ranked strictly higher than the other.

Initially, Alice and Bob will hold one or more cards while Prof. Pang will hold exactly one card. $\textbf{Each player can see cards held by himself/herself and cards held by other players.}$ They will play the game in the following multi-round rule:

- The initiative player chooses one card and put it out to start one round.
- The next player can pass or put out a new card, then the player after the next can also pass or put out a new card, and so on. The only constraint is that the rank of the newly put card should be strictly higher than all previous cards in this round.
- The round ends when two players choose to pass consecutively. The one who put out the last card becomes the initiative player in the next round.
- If someone put out all the cards in his/her hand, the game ends immediately.

In this game, Alice is the initiative player in the first round. Bob, Prof. Pang,  and Alice are the next players of Alice, Bob,  and Prof. Pang respectively. Prof. Pang will be happy if and only if he is the one that first put out all the cards. (Prof. Pang wants to be happy, of course.) Alice wants to drink milk tea so she decides to make Prof. Pang happy and then asks him to buy milk tea for her. However, Bob doesn't want it to happen, so he decides to avoid Prof. Pang from being happy. If they play the game optimally for themselves, will Prof. Pang be happy in the end?

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

The first line contains two integers $n,m$ ($1\le n,m \le 50$) denoting the number of cards in Alice's hand and Bob's hand initially.

The second line contains $n$ strings $a_i$ ($1\le i \le n$) denoting the cards in Alice's hand.

The third line contains $m$ strings $b_i$ ($1\le i \le m$) denoting the cards in Bod's hand.

The fourth line contains one string $p$ denoting the card in Prof. Pang's hand.

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

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

outputFormat: For each test case, print one line. Print $\texttt{Pang}$ if Prof. Pang will be happy. Otherwise, print $\texttt{Shou}$.

translation:
舒克、贝塔、卢本伟在打抽象版斗地主。

+ 因为卢本伟不想再被飞机炸弹秒掉，所以所有人**只能出单牌**，牌的大小依次为（从小到大列举）：$2,3,4,5,6,7,8,9,\texttt{T},\texttt{J},\texttt{Q},\texttt{K},\texttt{A}$。
+ 因为舒克是色盲，所以牌的**花色无关紧要**（即：两牌数字相同时没有大小之分）。
+ 因为贝塔技不如人，所以所有人**明牌打**。
+ 其余和普通斗地主一样：
    + 主动方选一张牌，打出去开始新一轮比赛。
    + 下一个玩家可以出牌或跳过，出牌需满足牌值**严格大于**上一张牌。
    + 当两名玩家连续跳过后，另一名玩家开始一个新的回合，这另一名玩家成为了主动方。
    + 谁把牌打光谁就赢了。

现在，给你一个残局，舒克剩 $n$ 张牌，贝塔剩 $m$ 张牌，斗地主大师卢本伟只剩一张牌了。

现在是新一个回合，顺序是舒克、贝塔、卢本伟。舒克想让卢本伟赢，贝塔想让卢本伟输。

作为著名动画片的主角与斗地主慈善家，三人都绝顶聪明。问最后谁会赢，卢本伟赢输出 `Pang`，否则输出 `Shou`。注意**舒克赢不算卢本伟赢**。

translated by 卢本伟。

hint:
- For the first case, Prof. Pang can always put out his only card ``4S``.
- For the second case, Bob can put out ``4D`` and become the initiative player in the second round regardless of the card Alice put out in the first round, then Bob put out ``3H`` and the game ends.


title: [EC Final 2021] Vacation

description:
Prof. Pang has an annual leave of $c$ days and he wants to go on vacation.

Now there are $n$ days in a year. Prof. Pang can gain $a_i$ happiness if he rests on the $i$-th day. The values of happiness, $a_i$, may be negative.

Prof. Pang wants you to do $m$ operations:

- $1~x~y$, change the happiness of the $x$-th day to $y$.
- $2~l~r$, Prof. Pang wants to find a period of vacation in $[l, r]$. He wants to rest for several (possibly $0$) days in a row and gain as much happiness as possible. However, he only has $c$ days off, thus he can rest for no more than $c$ consecutive days in $[l,r]$.

That means he wants to find

$$\max\left(\max_{l \leq l' \leq r' \leq r\atop r'-l'+1\leq c}  ~~ \left(\sum_{i=l'} ^{r'} a_i\right), 0\right).$$

inputFormat:
The first line contains three integers $n, m, c (1\leq n\leq 2\times 10^5, 1\leq m \leq 5\times 10^5, 1\leq c\leq n)$ indicating the number of days in a year, the number of operations, and Prof. Pang's annual leave days.

The next line contains $n$ integers $a_1, a_2, \dots, a_n(-10^9 \leq a_i\leq 10^9)$ indicating the values of happiness of every day.

The next $m$ lines are the $m$ operations in the format described above.

It is guaranteed that $1\leq x\leq n, -10^9\leq y\leq 10^9, 1\leq l\leq r \leq n$.

outputFormat: For each operation of the second type, print the answer.

translation:
连续的 $n$ 天，每天的 $Happiness$ 为  $a_i$ 。包含 $m$ 次操作，和一个 $c$
。
- $1.$ 将 $a_x$ 的值改为 $y$ 。
- $2.$ 询问 $[l,r]$ 内，连续 $t$ 天内，最大的 $Happiness$ 值的和，其中 $t∈[0,c]$ 。


title: [EC Final 2021] Check Pattern is Bad

description:
Prof. Pang is given an $n\times m$ board. Some cells are colored black, some cells are colored white, and others are uncolored.

Prof. Pang doesn't like $\textbf{check patterns}$, so he wants to color all uncolored cells such that there is no check pattern on the board.

$4$ cells forming a $2\times 2$ square are said to have the check pattern if they are colored in one of the following ways:

```plain
BW
WB
```

```plain
WB
BW
```

Here `W` ("wakuda" in Chewa language) means the cell is colored black and `B` ("biancu" in Corsican language) means the cell is colored white.

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

The first line of each test case contains two integers $n$ and $m$ ($1\le n, m\le 100$) denoting the dimensions of the board.

Each of the next $n$ lines contains $m$ characters. The $j$-th character of the $i$-th line represents the status of the cell on the $i$-th row and $j$-th column of the board. The character is `W` if the cell is colored black, `B` if the cell is colored white, and `?` if the cell is uncolored.

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

outputFormat:
For each test case, output a line containing $\texttt{NO}$ if you cannot color all the uncolored cells such that there is no check pattern on the board.

Otherwise, output a line containing $\texttt{YES}$. In the next $n$ lines, output the colored board in the same format as the input. The output board should satisfy the following conditions.

- It does not have any check pattern.
- It consists of only $\texttt{B}$ and $\texttt{W}$.
- If a cell is already colored in the input, its color cannot be changed in the output.

If there are multiple solutions, output any of them.

translation:
$n \times m$ 的棋盘，知道一些位置是黑色的，一些位置是白色的，一些位置不知道是什么颜色。

请你构造一种方案让棋盘的每个位置被染成黑色或白色（已知的位置不能换颜色），使得棋盘上不存在子矩阵：

```
BW
WB
```

以及
```
WB
BW
```

多组询问。


title: [GESP202309 一级] 买文具

description: 开学了，小明来到文具店选购文具。签字笔 $2$ 元一支，他需要 $X$ 支；记事本 $5$ 元一本，他需要 $Y$ 本；直尺 $3$ 元一把，他需要 $Z$ 把。小明手里有 $Q$ 元钱。请你通过编程帮小明算算，他手里的钱是否够买他需要的文具。

inputFormat:
第一行包含一个正整数，是小明购买签字笔的数量。约定 $1 \le X \le 10$。

第二行包含一个正整数，是小明购买记事本的数量。约定 $1 \le Y \le 10$。

第三行包含一个正整数，是小明购买直尺的数量。约定 $1 \le Z \le 10$。

第四行包含一个正整数 $Q$，是小明手里的钱数（单位：元）。

outputFormat: 输出 $2$ 行。如果小明手里的钱够买他需要的文具，则第一行输出 `Yes`，第二行输出小明会剩下的钱数（单位：元）；否则，第一行输出 `No`，第二行输出小明缺少的钱数（单位：元）。


title: [GESP202309 一级] 小明的幸运数

description: 所有个位数为 $k$ 的正整数，以及所有 $k$ 的倍数，都被小明称为“ $k$ 幸运数”。小明想知道正整数 $L$ 和 $R$ 之间（包括 $L$ 和 $R$）所有 $k$ 幸运数的和，你能帮帮他吗？

inputFormat: 输入 $3$ 行。第一行包含一个正整数 $k$，第二行包含一个正整数 $L$，第三行包含一个正整数 $R$。约定 $2 \le k \le 9$，$1 \le L \le R \le 1000$。

outputFormat: 输出 $1$ 行，符合题意的幸运数之和。


title: [GESP202309 二级] 小杨的 X 字矩阵

description:
小杨想要构造一个 的 X 字矩阵（ 为奇数），这个矩阵的两条对角线都是半角加号 `+` ，其余都是半角减号 `-` 。例如，一个 $5 \times 5$ 的 X 字矩阵如下：

```plain
+---+
-+-+-
--+--
-+-+-
+---+
```

请你帮小杨根据给定的 打印出对应的“X 字矩阵”。

inputFormat: 一行一个整数 （ $5 \le N \le 49$，保证为奇数）。

outputFormat:
输出对应的“X 字矩阵”。

请严格按格式要求输出，不要擅自添加任何空格、标点、空行等任何符号。你应该恰好输出 $N$ 行，每行除了换行符外恰好包含 $N$ 个字符，这些字符要么是 `+`，要么是 `-`。

hint:
**特别提醒**

在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。


title: [GESP202309 二级] 数字黑洞

description:
给定一个三位数，要求各位不能相同。例如，$352$ 是符合要求的，$112$ 是不符合要求的。将这个三位数的三个数字重新排列，得到的最大的数，减去得到的最小的数，形成一个新的三位数。对这个新的三位数可以重复上述过程。神奇的是，最终一定会得到 $495$！

试试看，重新排列 $352$，得到的最大数为 $532$，最小数为 $235$，它们的差是 $297$；变换 $297$，得到 $972-279=693$；变换 $693$，$963-369=594$；变换 $594$，$954-459=495$。因此，经过 $4$ 次变换得到了 $495$。

现在，输入的三位数，你能通过编程得出，这个三位数经过多少次变换能够得到 $495$ 吗？

inputFormat: 输入一行，包含一个符合要求的三位数 $N$。

outputFormat: 输出一行，包含一个整数 $C$，表示经过 $C$ 次变换得到 $495$。


title: [GESP202309 三级] 小杨的储蓄

description: 小杨共有 $N$ 个储蓄罐，编号从 $0$ 到 $N-1$。从第 $1$ 天开始，小杨每天都会往存钱罐里存钱。具体来说，第 $i$ 天他会挑选一个存钱罐 $a_i$，并存入 $i$ 元钱。过了 $D$ 天后，他已经忘记每个储蓄罐里都存了多少钱了，你能帮帮他吗？

inputFormat:
输入 $2$ 行，第一行两个整数 $N,D$；第二行 $D$ 个整数，其中第 $i$ 个整数为 ${a_i}$（保证 $0 \le a_i \le N-1$）。

每行的各个整数之间用单个空格分隔。

保证 $1 \le N \le 1,000$；$1 \le D \le 1,000$。

outputFormat: 输出 $N$ 个用单个空格隔开的整数，其中第 $i$ 个整数表示编号为 $i-1$ 的存钱罐中有多少钱（$i=1, \cdots ,N$）。

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

小杨在第 $1$ 天、第 $2$ 天、第 $3$ 天分别向 $0$ 号、 $1$ 号、 $0$ 号存钱罐存了 $1$ 元钱、 $2$ 元钱、 $3$ 元钱，因此 $0$ 号存钱罐有 $1+3=4$ 元钱，而 $1$ 号存钱罐有 $2$ 元钱。


title: [GESP202309 三级] 进制判断

description:
$N$ 进制数指的是逢 $N$ 进一的计数制。例如，人们日常生活中大多使用十进制计数，而计算机底层则一般使用二进制。除此之外，八进制和十六进制在一些场合也是常用的计数制（十六进制中，一般使用字母 A 至 F 表示十至十五）。

现在有N个数，请你分别判断他们是否可能是二进制、八进制、十进制、十六进制。例如，`15A6F` 就只可能是十六进制，而 `1011` 则是四种进制皆有可能。

inputFormat:
输入的第一行为一个十进制表示的整数 $N$。接下来 $N$ 行，每行一个字符串，表示需要判断的数。保证所有字符串均由数字和大写字母组成，**可能以 $0$ 开头**。保证不会出现空行。

保证 $1 \le N \le 1000$，保证所有字符串长度不超过 $10$。

outputFormat:
输出 $N$ 行，每行 $4$ 个数，用空格隔开，分别表示给定的字符串是否可能表示一个二进制数、八进制数、十进制数、十六进制数。使用 $1$ 表示可能，使用 $0$ 表示不可能。

例如，对于只可能是十六进制数的 `15A6F`，就需要输出 `0 0 0 1`；而对于四者皆有可能的 `1011`，则需要输出 `1 1 1 1`。


title: [GESP202309 四级] 进制转换

description:
$N$ 进制数指的是逢 $N$ 进一的计数制。例如，人们日常生活中大多使用十进制计数，而计算机底层则一般使用二进制。除此之外，八进制和十六进制在一些场合也是常用的计数制（十六进制中，一般使用字母 A 至 F 表示十至十五；本题中，十一进制到十五进制也是类似的）。

在本题中，我们将给出 个不同进制的数。你需要分别把它们转换成十进制数。

inputFormat:
输入的第一行为一个十进制表示的整数 $N$。接下来 $N$ 行，每行一个整数 $K$，随后是一个空格，紧接着是一个 $K$ 进制数，表示需要转换的数。保证所有 $K$ 进制数均由数字和大写字母组成，且不以 $0$ 开头。保证 $K$ 进制数合法。

保证 $N \le 1000$；保证 $2 \le K \le 16$。

保证所有 $K$ 进制数的位数不超过 $9$。

outputFormat: 输出 $N$ 行，每一个十进制数，表示对应 $K$ 进制数的十进制数值。

hint:
对于任意一个 $L$ 位 $K$ 进制数，假设其最右边的数位为第 $0$ 位，最左边的数位为第 $L-1$ 位，我们只需要将其第 $i$ 位的数码乘以权值 $K^i$，再将每位的结果相加，即可得到原 $K$ 进制数对应的十进制数。下面是两个例子：

1. 八进制数 `1362` 对应的十进制数为：$1×8^3+3×8^2+6×8^1+2×8^0=754$；

2. 十六进制数 `3F0` 对应的十进制数为：$3×16^2+15×16^1+0×16^0=1008$。


title: [GESP202309 四级] 变长编码

description:
小明刚刚学习了三种整数编码方式：原码、反码、补码，并了解到计算机存储整数通常使用补码。但他总是觉得，生活中很少用到 $2^{31}-1$ 这么大的数，生活中常用的 $0\sim 100$ 这种数也同样需要用 $4$ 个字节的补码表示，太浪费了些。
热爱学习的小明通过搜索，发现了一种正整数的变长编码方式。这种编码方式的规则如下：

1. 对于给定的正整数，首先将其表达为二进制形式。例如，$(0)_{\{10\}}=(0)_{\{2\}}$，$(926)_{\{10\}}=(1110011110)_{\{2\}}$。

2. 将二进制数从低位到高位切分成每组 $7$ bit，不足 $7$bit 的在高位用 $0$ 填补。例如，$(0)_{\{2\}}$ 变为$0000000$ 的一组，$(1110011110)_{\{2\}}$ 变为 $0011110$ 和 $0000111$ 的两组。

3. 由代表低位的组开始，为其加入最高位。如果这组是最后一组，则在最高位填上 $0$，否则在最高位填上 $1$。于是，$0$ 的变长编码为 $00000000$ 一个字节， $926$ 的变长编码为 $10011110$ 和 $00000111$ 两个字节。

这种编码方式可以用更少的字节表达比较小的数，也可以用很多的字节表达非常大的数。例如，$987654321012345678$ 的二进制为 $(0001101 \ 1011010 \ 0110110 \ 1001011 \ 1110100 \ 0100110 \ 1001000 \ 0010110 \ 1001110)_{\{2\}}$，于是它的变长编码为（十六进制表示） `CE 96 C8 A6 F4 CB B6 DA 0D`，共 $9$ 个字节。

你能通过编写程序，找到一个正整数的变长编码吗？

inputFormat: 输入第一行，包含一个正整数 $N$。约定 $0\le N \le 10^{18}$。

outputFormat: 输出一行，输出 $N$ 对应的变长编码的每个字节，每个字节均以 $2$ 位十六进制表示（其中， `A-F` 使用大写字母表示），两个字节间以空格分隔。


title: [GESP202309 五级] 因数分解

description:
每个正整数都可以分解成素数的乘积，例如： $6=2\times 3$，$20=2^2\times5$。

现在，给定一个正整数，请按要求输出它的因数分解式。

inputFormat: 输入第一行，包含一个正整数 $N$。约定 $2 \le N \le 10^{12}$。

outputFormat: 输出一行，为的因数分解式。要求按质因数由小到大排列，乘号用星号 `*` 表示，且左右各空一格。当且仅当一个素数出现多次时，将它们合并为指数形式，用上箭头 `^` 表示，且左右不空格。


title: [GESP202309 五级] 巧夺大奖

description:
小明参加了一个巧夺大奖的游戏节目。主持人宣布了游戏规则：

1. 游戏分为 $n$ 个时间段，参加者每个时间段可以选择一个小游戏。

2. 游戏中共有 $n$ 个小游戏可供选择。

3. 每个小游戏有规定的时限和奖励。对于第 $i$ 个小游戏，参加者必须在第 $T_i$ 个时间段结束前完成才能得到奖励 $R_i$。

小明发现，这些小游戏都很简单，不管选择哪个小游戏，他都能在一个时间段内完成。关键问题在于，如何安排每个时间段分别选择哪个小游戏，才能使得总奖励最高？

inputFormat:
输入第一行，包含一个正整数 $n$。$n$ 既是游戏时间段的个数，也是小游戏的个数。约定 $1\le n\le500$。

输入第二行，包含 $n$ 个正整数。第 $i$ 个正整数为 $T_i$，即第 $i$ 个小游戏的完成期限。约定 $1\le T_i\le n$。

输入第三行，包含 $n$ 个正整数。第 $i$ 个正整数为 $R_i$，即第 $i$ 个小游戏的完成奖励。约定 $1\le R_i\le 1000$。

outputFormat: 输出一行，包含一个正整数 $C$，为最高可获得的奖励。

hint:
**样例解释 1**

$7$ 个时间段可分别安排完成第 4、2、3、1、6、7、5 个小游戏，其中第 4、2、3、1、7 个小游戏在期限内完成。因此，可以获得总计 $40+60+50+70+10=230$ 的奖励。


title: [GESP202309 六级] 小杨买饮料

description:
小杨来到了一家商店，打算购买一些饮料。这家商店总共出售 $N$ 种饮料，编号从 $0$ 至 $N-1$，其中编号为 $i$ 的饮料售价 $c_i$ 元，容量 $l_i$ 毫升。

小杨的需求有如下几点：

1. 小杨想要尽可能尝试不同种类的饮料，因此他希望每种饮料至多购买 $1$ 瓶；

2. 小杨很渴，所以他想要购买总容量不低于 $L$ 的饮料；

3. 小杨勤俭节约，所以在 $1$ 和 $2$ 的前提下，他希望使用尽可能少的费用。

方便起见，你只需要输出最少花费的费用即可。特别地，如果不能满足小杨的要求，则输出 `no solution`。

inputFormat:
第一行两个整数 $N,L$。

接下来 $N$行，依次描述第 $i=0,1,\cdots,N-1$ 种饮料：每行两个整数 $c_i,l_i$。

outputFormat: 输出一行一个整数，表示最少需要花费多少钱，才能满足小杨的要求。特别地，如果不能满足要求，则输出 `no solution`。

hint:
**样例 1 解释**

小杨可以购买 $1,2,4$ 号饮料，总计获得 $50+40+20=110$ 毫升饮料，花费 $2+4+3=9$ 元。

如果只考虑前两项需求，小杨也可以购买 $1,3,4$ 号饮料，它们的容量总和为 $50+30+20=100$ 毫升，恰好可以满足需求。但遗憾的是，这个方案需要花费 $2+5+3=10$ 元。

**样例 2 解释**

$1,2,3,4$ 号饮料总计 $140$ 毫升，如每种饮料至多购买 $1$ 瓶，则恰好无法满足需求，因此只能花费 $100$ 元购买 $0$ 号饮料。

**数据规模**

对于 $40\%$ 的测试点，保证 $N \le 20;1\le L \le 100; l_i \le 100$。

对于 $70\%$ 的测试点，保证 $l_i \le 100$。

对于 $100\%$ 的测试点，保证 $1\le N \le 500;1\le L \le 2000; 1\le c_i,l_i \le 10^6$。


title: [GESP202309 六级] 小杨的握手问题

description:
小杨的班级里共有 $N$ 名同学，学号从 $0$ 至 $N-1$。

某节课上，老师安排全班同学进行一次握手游戏，具体规则如下：老师安排了一个顺序，让全班 $N$ 名同学依次进入教室。每位同学进入教室时，需要和 **已经在教室内** 且 **学号小于自己** 的同学握手。

现在，小杨想知道，整个班级总共会进行多少次握手。

**提示：可以考虑使用归并排序进行降序排序，并在此过程中求解。**

inputFormat:
输入包含 $2$ 行。第一行一个整数 $N$ ，表示同学的个数；第二行 $N$ 个用单个空格隔开的整数，依次描述同学们进入教
室的顺序，每个整数在 $0$ $\sim$ $N-1$ 之间，表示该同学的学号。

保证每位同学会且只会进入教室一次。

outputFormat: 输出一行一个整数，表示全班握手的总次数。

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

$2$ 号同学进入教室，此时教室里没有其他同学。

$1$ 号同学进入教室，此时教室里有 $2$ 号同学。 $1$ 号同学的学号小于 $2$ 号同学，因此他们之间不需要握手。

$3$ 号同学进入教室，此时教室里有 $1,2$ 号同学。 $3$ 号同学的学号比他们都大，因此 $3$ 号同学需要分别和另外两位同学握手。

$0$ 号同学进入教室，此时教室里有 $1,2,3$ 号同学。   $0$ 号同学的学号比他们都小，因此 $0$ 号同学不需要与其他同学握手。

**样例解释2：**

全班所有同学之间都会进行握手，因为每位同学来到教室时，都会发现他的学号是当前教室里最大的，所以他需要
和教室里的每位其他同学进行握手。

对于$30\%$的测试点，保证 $N\le100$

对于所有测试点，保证 $2\le N\le3\times10^5$


title: 「Daily OI Round 3」Xor Graph

background: 在黎明来临之前，总要有人照亮黑暗。

description:
Xs_siqi 给了你 $2^n$ 个点，$x$ 到 $y$ 有**有向**边当且仅当 $x\operatorname{xor} y=2^k,k \in [0,n)$，且 $x>y$。其中，$\operatorname{xor}$ 表示按位异或，$k$ 为整数。令 $f_{x,y}$ 为 $x$ 点到 $y$ 点的不同路径数，求：

$$\sum_{i=1}^{2^n}\sum_{j=1}^{2^n}f_{i,j}(i\neq j)$$

答案对 $998244353$ 取模。

inputFormat:
第一行，一个整数 $t$。

接下来 $2 \sim t+1$ 行，一行一个整数表示 $n$。

outputFormat: 共 $t$ 行，每行一个整数表示题目要求的方案数。

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

对于样例的第一组，$3$ 向 $1,2$ 连边，这样 $3$ 到 $1$ 是一个方案，$3$ 到 $2$ 是一个方案，一共有 $2$ 个方案。

#### 【数据范围】

对于全部数据保证：$1 \le t \le 10^6$，$1 \le n \le 10^7$。


title: 括号

description:
圆给了你一个长度为 $n$ 的字符串 $S$，$S$ 仅由 ```(``` 和 ```)``` 构成。

她会对其做 $m$ 次操作，操作有两种类型：

1. ```1 l r```，她会翻转 $l$ 到 $r$ 的括号，即 ```(``` 变 ```)```，```)``` 变 ```(```。
1. ```2 l r```，她想知道区间 $\left[ l,r\right]$ 中最长合法括号子序列的长度除以 $2$ 的答案。

圆认为以下的括号序列是合法的：

1. 空序列是一个合法序列。

1. 如果 ```A``` 是一个合法序列，则 ```(A)```  也是一个合法序列。

1. 如果 ```A``` 和 ```B``` 都是合法序列，则 ```AB``` 也是一个合法序列。

圆认为，序列 $a$ 的子序列是满足 $1\le i_1<i_2<···<i_k \le n$ 的序列 $[a_{i_1},a_{i_2},...a_{i_k}]$。

由于操作太多了，她算不过来，请你帮帮她吧。

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

第二行一个长度为 $n$ 的字符串 $S$，保证仅由 ```(``` 和 ```)``` 构成 。

第三行一行一个整数 $m$。

接下来 $m$ 行，每行三个数 $op$，$l$，$r$，对应上面的两种操作。

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

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

- 第一次截取的字符串是 ```()```，答案为 $1$。
- 翻转后字符串变为 ```))(())```。
- 第二次截取的字符串是 ```)(```，答案为 $0$。
- 第三次截取的字符串是 ```())```，答案为 $1$。
- 第四次截取的字符串是 ```(())```，答案为 $2$。

**【数据范围】**

- 对于 $10\%$ 的数据，$1 \leq n,m \leq 500$；
- 对于 $20\%$ 的数据，$1 \leq n,m \leq 5000$；
- 对于 $40\%$ 的数据，$1 \leq n,m \leq 2\times 10^5$；
- 另有 $10\%$ 的数据，满足 $op=2$ 且数据随机生成；
- 另有 $15\%$ 的数据，满足 $op=2$ 但不保证数据随机生成；

对于所有数据，保证 $1\le n \le 5\times 10^5$，$1\le m \le 5 \times 10^5$，$1 \le l \le r \le n$，$op \in \{1,2\}$。数据有梯度。


title: 【MX-S2-T2】排

description:
有 $n$ 个整数 $a_1,a_2,\ldots,a_n$。$f_0=0,f_i= \left\{
\begin{aligned}
& f_{i-1}   &  \ f_{i-1}\times a_i>0, \\
& f_{i-1}+a_i &  \ f_{i-1}\times a_i\le 0.\\
\end{aligned}
\right.
$

重排 $a$ 使得得到的 $f_n$ 最大。

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

第二行 $n$ 个整数 $a_1,\dots,a_n$。

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

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

考虑重排为 $-6,-4,5,7,3$，最终的 $f_n$ 为 $6$，可以证明不存在更优的方案。

**【数据范围】**

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

- Subtask 0（6 pts）：$n\le10$。
- Subtask 1（14 pts）：$n\le 20$，$|a_i|\le10$。
- Subtask 2（8 pts）：$a$ 中全为正数或全为负数。
- Subtask 3（19 pts）：$a$ 中有且只有一个正数（注意 $a$ 中可以有 $0$）。
- Subtask 4（29 pts）：$n \le 200$，$|a_i|\le 200$。
- Subtask 5（24 pts）：无特殊限制。

对于所有测试数据，$1 \le n \le 2000$，$|a_i|\le 2000$。


title: 『STA - R4』踱步

description:
小 X 特别喜欢安静的环境，因为那可以让他心情愉悦。

现在给出 $N$ 分钟内每分钟屋内和屋外对小 X 的心情影响值，在这 $N$ 分钟内，小 X 可以从屋内踱步到屋外或是从屋外踱步到屋内**最多共** $K$ 次。（小 X 当且仅当每分钟初进行踱步，同一时刻至多踱步一次，并且踱步的时间忽略不计。第 $1$ 分钟初不可踱步，第 $N$ 分钟初可以踱步。但是在第 $1$ 分钟初可以自由选择初始状态）。

同时，过于频繁的改变会让小 X 心情烦躁，所以如果两次踱步的间隔**小于等于** $T$ 分钟，会对小 X 的心情额外造成 $P$ 点影响。（如果此次踱步是在第 $t_a$ 分钟初，上一次踱步是在第 $t_b$ 分钟初，那么这两次踱步的时间间隔为 $t_a - t_b$ 分钟）。

小 X 想知道自己的心情最好可以是多少，即第 $N$ 分钟末小 X 心情值的最大值。

若某一时刻小 X 的心情值为 $a$，之后小 X 的心情被影响了 $b$，那么在此之后小 X 的心情值将变为 $a + b$。

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

第一行两个正整数 $\text{id},\text{TEST}$。其中 $\text{id}$ 代表 Subtask 编号，$\text{TEST}$ 代表测试数据组数。特别的，样例的 $\text{id}$ 为 $0$。

对于每组测试数据：

第一行为四个整数 $N, K, T, P$。

接下来 $N$ 行每行两个整数。其中第 $i$ 行的两个整数 $a_i, b_i$ 分别代表第 $i$ 分钟屋内和屋外对小 X 心情的影响值。

outputFormat: 对于每组测试数据，输出一行一个整数，代表第 $N$ 分钟末小 X 心情值的最大值。

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

对于第 $1$ 组数据，最优方案为初始时选择在屋内，分别在第 $4, 5, 7$ 分钟初进行踱步。

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

其中第 $2$ 次踱步与第 $1$ 次踱步之间的间隔为 $5 - 4 = 1$ 分钟，对小 $\text{X}$ 的心情产生 $3$ 的贡献，第 $3$ 次踱步与第 $2$ 次踱步之间的间隔为 $7 - 5 = 2$ 分钟，对小 X 的心情产生 $3$ 的贡献。

因此小 X 的心情值为

$$\left(0+5+8-7+0-4-3+0\right) + 6 = 5$$

前半部分为灰色格子的权值和，后半部分为两次频繁踱步产生的额外贡献，可以证明此方案最优。

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

请注意答案可能超过 $32$ 位整型数字的范围。

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

请注意答案可能为负数。

**【数据范围】**

对于 $100\%$ 的数据：

- $1 \le \text{TEST} \le 10^5$；
- $2 \le N \le 2 \times 10^5$；
- $1 \le K \le \min\left\{200, N\right\}$；
- $1 \le T \le \min\left\{2 \times 10^4, N\right\}$；
- $\left\lvert a_i \right\rvert,\left\lvert b_i \right\rvert,\left\lvert P \right\rvert \le 10^9$。
- $\sum N \cdot K \le 5 \times 10^7$。
- 保证单个测试点输入数据规模不超过 10 MB。

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

|Subtask 编号|数据范围|分值|依赖子任务|
|:--------:|:--------:|:--------:|:--------:|
|1|$N \le 20, \text{TEST} \le 10$|$5$||
|2|$\sum N^2K \le 5 \times 10^7$|$20$|$1$|
|3|$K \le 5, N \le 5 \times 10^4, \text{TEST} \le 10$|$15$||
|4|$P=-10^9, 0 \le \left\lvert a_i \right\rvert,\left\lvert b_i \right\rvert \le 100$|$30$||
|5|无特殊限制|$30$|$1,2,3,4$|


title: [NOIP2023] 双序列拓展

description:
称某个序列 $B = \{b_1,b_2,\cdots,b_n\}$ 是另一个序列 $A = \{a_1,a_2,\cdots,a_m\}$ 的**拓展**当且仅当存在**正整数**序列 $L = \{l_1,l_2,\cdots,l_m\}$，将 $a_i$ 替换为 $l_i$ 个 $a_i$ 后得到序列 $B$。例如，

- $\{1,3,3,3,2,2,2\}$ 是 $\{1,3,3,2\}$ 的拓展，取 $L = \{1,1,2,3\}$ 或 $\{1,2,1,3\}$；
- 而 $\{1,3,3,2\}$ 不是 $\{1,3,3,3,2\}$ 的拓展，$\{1,2,3\}$ 不是 $\{1,3,2\}$ 的拓展。

小 R 给了你两个序列 $X$ 和 $Y$，他希望你找到 $X$ 的一个长度为 $l_0 = 10^{100}$ 的拓展 $F = \{f_i\}$ 以及 $Y$ 的一个长度为 $l_0$ 的拓展 $G = \{g_i\}$，使得任意 $1 \le i , j \le l_0$ 都有 $(f_i - g_i)(f_j - g_j) > 0$。由于序列太长，你只需要告诉小 R 是否存在这样的两个序列即可。

为了避免你扔硬币蒙混过关，小 R 还给了 $q$ 次额外询问，每次额外询问中小 R 会修改 $X$ 和 $Y$ 中若干元素的值。你需要对每次得到的新的 $X$ 和 $Y$ 都进行上述的判断。

**询问之间是独立的，每次询问中涉及的修改均在原始序列上完成。**

inputFormat:
输入的第一行包含四个整数 $c, n, m, q$，分别表示测试点编号、序列 $X$ 的长度、序列 $Y$ 的长度和额外询问的个数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。

输入的第二行包含 $n$ 个整数 $x_1,x_2,\cdots, x_n$，描述序列 $X$。

输入的第三行包含 $m$ 个整数 $y_1,y_2,\cdots, y_m$，描述序列 $Y$。

接下来依次描述 $q$ 组额外询问。对于每组额外询问：

- 输入的第一行包含两个整数 $k_x$ 和 $k_y$，分别表示对序列 $X$ 和 $Y$ 产生的修改个数。
- 接下来 $k_x$ 行每行包含两个整数 $p_x, v_x$，表示将 $x_{p_x}$ 修改为 $v_x$。
- 接下来 $k_y$ 行每行包含两个整数 $p_y, v_y$，表示将 $y_{p_y}$ 修改为 $v_y$。

outputFormat: 输出一行，其中包含一个长度为 $(q+1)$ 的 `01` 序列，序列的第一个元素表示初始询问的答案，之后 $q$ 个元素依次表示每组额外询问的答案。对于每个询问，如果存在满足题目条件的序列 $F$ 和 $G$，输出 `1`，否则输出 `0`。


title: [NOIP2023] 天天爱打卡

description:
小 T 同学非常热衷于跑步。为了让跑步更加有趣，他决定制作一款叫做《天天爱打卡》的软件，使得用户每天都可以进行跑步打卡。

开发完成后，小 T 同学计划进行试运行，他找了大 Y 同学来帮忙。试运行共 $n$ 天，编号为从 $1$ 到 $n$。

对大 Y 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 $d$。初始时，他的能量值是 $0$，并且试运行期间他的**能量值可以是负数**。

而且大 Y 不会**连续**跑步打卡**超过** $k$ 天；即不能存在 $1\le x\le n-k$，使得他在第 $x$ 到第 $x+k$ 天均进行了跑步打卡。

小 T 同学在软件中设计了 $m$ 个挑战，第 $i$（$1\le i \le m$）个挑战可以用三个正整数 $(x_i,y_i,v_i)$ 描述，表示如果在第 $x_i$ 天时，用户已经连续跑步打卡至少 $y_i$ 天（即第 $x_i-y_i+1$ 到第 $x_i$ 天均完成了跑步打卡），那么小 T 同学就会请用户吃饭，从而使用户的能量值提高 $v_i$。

现在大 Y 想知道，在软件试运行的 $n$ 天结束后，他的能量值**最高**可以达到多少？

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

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

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

- 输入的第一行包含四个正整数 $n,m,k,d$，分别表示试运行的天数、挑战的个数、大 Y 单次跑步打卡的连续天数限制以及大 Y 跑步打卡减少的能量值。
- 接下来 $m$ 行，每行包含三个正整数 $x_i,y_i,v_i$，表示一次挑战。

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


title: 「Cfz Round 3」Xor with Gcd

background:
她是午夜潜入海风漂流的沙砾

极光与她一齐许下明日愿景

飞身电波铺满天穹而海仍平静

“愿世界都繁花似锦”

description:
给定一个整数 $n$。

你需要求出 $\bigoplus\limits_{i=1}^{n} \gcd(i,n)$，即 $\gcd(1,n) \oplus \gcd(2,n) \oplus \cdots \oplus \gcd(n,n)$ 的值。其中 $\gcd(a,b)$ 表示 $a$ 和 $b$ 的**最大公约数**，$\bigoplus$ 表示**按位异或**，即 C++ 中的 `^`。

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

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

接下来依次输入每组测试数据。对于每组测试数据，输入一行一个整数 $n$。

outputFormat: 对于每组测试数据，输出一行一个整数，表示 $\bigoplus\limits_{i=1}^{n} \gcd(i,n)$ 的值。

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

对于第 $1$ 组数据，$\bigoplus\limits_{i=1}^{2} \gcd(i,2)=\gcd(1,2)\oplus\gcd(2,2)=1\oplus2=3$。

对于第 $2$ 组数据，$\bigoplus\limits_{i=1}^{3} \gcd(i,3)=\gcd(1,3)\oplus\gcd(2,3)\oplus\gcd(3,3)=1\oplus1\oplus3=3$。

#### 「数据范围」

对于所有数据，$1 \le T \le 100$，$1 \le n \le 10^{18}$。

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


title: [COCI 2023/2024 #1] Sudoku

description:
数独是一款逻辑推理类游戏，玩家的任务是用数字 $1\sim9$ 填满一个 $9\times9$ 的网格，使其满足以下条件：

- 数字 $1\sim 9$ 在每一行恰好出现一次。
- 数字 $1\sim 9$ 在每一列恰好出现一次。
- 把网格划分成 $9$ 个 $3\times3$ 的宫，数字 $1\sim 9$ 在每一宫恰好出现一次。

现在给你一个未完成的数独网格，请你判断当前是否存在错误。**一个网格是存在错误的，当且仅当存在一行或一列或一宫，其中至少一个数字出现了 $2$ 次及以上。**

如图展示了一个数独网格，它不存在错误。

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

inputFormat:
输入一个 $13\times 13$ 的字符矩阵，表示数独网格，其中：

- 字符 `-`、`|`、`+` 表示网格框架，表示将网格划分为 $9$ 个 $3\times 3$ 的宫。
- 字符 `.` 表示一个未填数字的单元格。
- 从 $1\sim9$ 的数字表示所在单元格已经填了这个数字。

具体请见样例。

outputFormat: 一行一个字符串，如果这个网格存在错误，输出 `GRESKA`，否则输出 `OK`。

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

这个网格没有错误，所有输出 `OK`。

### 【样例解释#2】

第 $9$ 列数字 $5$ 出现了 $2$ 次，且右下角的一个宫中数字 $5$ 出现了 $2$ 次。

### 【样例解释#3】

第 $2$ 列数字 $2$ 出现了 $2$ 次，且第 $7$ 列数字 $6$ 出现了 $2$ 次。

### 【数据范围】

对于 $100\%$ 的数据，字符矩阵中只包含数字 $1\sim9$、字符 `-`、`|`、`+`、`.`，且字符 `-`、`|`、`+` 出现的位置与样例一致。

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

| 子任务 | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: |
| $1$ | 如果存在错误，一定可以只检查行的限制找到 | $11$ |
| $2$ | 如果存在错误，一定可以只检查列的限制找到 | $12$ |
| $3$ | 如果存在错误，一定可以只检查宫的限制找到 | $13$ |
| $4$ | 无特殊性质 | $14$ |

### 【说明】

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

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


title: [COCI 2023/2024 #1] Labirint

background: Teo 和克罗地亚 EJOI 队伍在一个迷宫里面。

description:
这个迷宫是一个 $n\times m$ 的网格，用坐标 $(1,1)$ 表示左上角的单元格，用坐标 $(n,m)$ 表示右下角的单元格。每一对相邻（四连通，即与上、下、左、右相邻）的单元格之间都有一道门，门有四种颜色：蓝、红、绿、橙，分别用字符 `P`、`C`、`Z`、`N` 表示。只能通过门移动到其它单元格。

现在 Teo 给你 $q$ 组询问，每次询问给定 $a,b,c,d$，表示找到一条从 $(a,b)$ 到 $(c,d)$ 的路径，最小化经过的门的颜色数，请你回答最少的颜色数量。

inputFormat:
第一行两个整数 $n,m$ 表示网格的行数和列数。

接下来一个 $n$ 行 $m-1$ 列的字符矩阵，其中第 $i$ 行第 $j$ 列的字符表示 $(i,j)$ 和 $(i,j+1)$ 之间的门的颜色。

接下来一个 $n-1$ 行 $m$ 列的字符矩阵，其中第 $i$ 行第 $j$ 列的字符表示 $(i,j)$ 和 $(i+1,j)$ 之间的门的颜色。

接下来一行一个整数 $q$，表示询问数量。

接下来 $q$ 行，第 $i$ 行四个整数 $a_i,b_i,c_i,d_i$ 表示询问是 $(a_i,b_i)$ 到 $(c_i,d_i)$ 路径上门的颜色个数的最小值。

outputFormat: $q$ 行，每行一个整数表示这组询问的答案。

samples:
4 4
CCC
CPC
PPP
CNP
ZZZZ
PPPP
CPZC
4
3 1 2 3
1 1 4 4
2 2 3 3
1 4 4 1

hint:
### 【样例说明#3】

如图所示。

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

- 第一组询问，只需经过蓝色门；
- 第二组询问，只需经过蓝色门和绿色门；
- 第三组询问，只需经过蓝色门；
- 第四组询问，按图中的路径走，只需经过红色门、蓝色门、绿色门。

### 【数据范围】

对于 $100\%$ 的数据，$1\leq n,m,q\leq100$，$nm>1$，$1\leq a_i,c_i\leq n$，$1\leq b_i,d_i\leq m$，$(a_i,b_i)\ne(c_i,d_i)$，字符矩阵只有字符 `P`、`C`、`Z`、`N` 组成。

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

| 子任务 | 特殊性质 | 分值 |
| :----------: | :----------: | :----------: |
| $1$ | $n=1$ | $11$ |
| $2$ | 第一个字符矩阵中的字符只包含 `P`,第二个字符矩阵中的字符只包含 `C` | $13$ |
| $3$ | 所有字符矩阵中的字符只包含 `C` 和 `P` | $24$ |
| $4$ | 无特殊性质 | $22$ |

### 【说明】

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

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


title: 「Cfz Round 3」Sum of Permutation

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

给定一个 $1\sim n$ 的排列 $p$。

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

- 序列 $a$ 中的每个元素均为不大于 $n$ 的正整数；
- 不存在有序整数二元组 $(l,r)$，满足 $1 \le l \le r \le n$ 且 $\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i$；

或报告无解。

其中，$1\sim n$ 的排列指满足所有不大于 $n$ 的正整数恰好出现一次的序列。

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

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

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

- 第一行输入一个整数 $n$。
- 第二行输入 $n$ 个整数，表示给定的排列 $p$。

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

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

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

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

对于第 $1$ 组数据，$\{1,3,3\}$ 和 $\{1,1,3\}$ 均为满足条件的序列 $a$。

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

对于第 $3$ 组数据，除 $\{5,3,2,1,1 \}$ 外，$\{3,4,5,3,2 \}$、$\{1,4,5,3,4 \}$、$\{5,3,3,4,5\}$ 等均为满足条件的序列 $a$。

#### 「数据范围」

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

对于所有数据，$1 \le T \le 5000$，$2 \le n \le 10^6$，$\sum n \le 10^6$，保证 $p$ 是 $1\sim n$ 的排列。

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

**本题输入输出量较大，请使用较快的输入输出方式。**


title: [APC001] C - Not APC

background: 这题并没有什么有趣的题目背景，祝您愉快。

description:
小 A 有一个**仅由 `A`、`P`、`C` 构成**的字符串 $S$。

小 A 需要**尽可能地**不断在这个字符串中消除形如 `APC` 这样的**子序列**，直到无法消除。

最后，小 A 需要输出消除后的字符串。如果字符串可以被消除成空串，则输出 `Perfect`。

然而小 A 不会这个题，所以来找你帮忙。

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

接下来 $T$ 行每行一个字符串 $S$.

outputFormat:
**本题使用 Special Judge。**

请输出最短的答案字符串，并给出一种删除的方案。

对于每组数据，第一行输出一个最短的答案字符串。如果可能的最短答案字符串或生成最短答案字符串的方案有多种，请输出任意一个。

接下来一行输出一个整数 $q$，表示你的删除次数。

接下来 $q$ 行每行三个整数，分别表示你在一次操作中删除的字符 `A`、`P`、`C` **在原字符串中**的位置，**下标从 $1$ 开始**。

samples:
5
PAAAAPPPCA
CAPPCPCAPAPA
PPAAAACCAAAAAAAAC
CAPPCAAPA
APPAACPPAPPPAPAAAA

samples:
PAAAPPA
1
5 6 9
CPPCAPAPA
1
2 4 5
PPAAAACCAAAAAAAAC
0
CPAAPA
1
2 3 5
PAAPPAPPPAPAAAA
1
1 2 6

samples:
10
PPCPAPAAACPAPACPPCPC
APPAPPAPPCPAPPCCCPPA
APPCCPPAPPAACCPPPPPP
PACPPCAPCPPCPPPAAAAC
PPPCPPCCPACAAACCCCAC
ACAAPCPAPAAAAPPACPPC
ACACPPCCPPAACPAAAAAC
APPCPCCCAPCACPAACACC
AACPCAPACPPPCAAPCCPC
PPACPPPCCAPAAAPCPAPA

hint:
**样例解释 #1：**
对于第一组数据，字符串为 `PAAAAPPPCA`，下标为 $\{5,6,9\}$ 的字符串被删除，最终得到 `PAAAPPA`。

对于第二组数据，字符串为 `CAPPCPCAPAPA`，下标为 $\{2,4,5\}$ 的字符被消除，得到 `CPPCAPAPA`。

**样例解释 #2：**
唯一的一组数据中，字符串为 `APC`，显然能被全部消除，方案也显然。

$1\leq T\leq 10$，$1\leq \sum |S|\leq 3\times 10^6$。


title: 『SpOI - R1』架子鼓可以站 C

description:
现在有一棵 $n$ 个点的树，树根是节点 $1$。

可以对这棵树做任意次**站 C 操作**，每次**站 C 操作**为：选择树上的一个叶子结点 $x$，再选择根节点到 $x$ 路径上的一条边，删除它；然后添加一条连接 $x$ 和根节点的边。

你需要求出经过若干次**站 C 操作**后树的直径的最大值。

**注意：叶子结点的定义是不为根节点，且度数为 $1$ 的节点。**

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

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

接下来 $T$ 组数据，每组第一行一个整数 $n$，第二行一个长为 $n-1$ 的序列 $f_i$，第 $i$ 项为 $i+1$ 号节点在树上的父亲。

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


title: 『PG2』猪棋

background: 交互库绝顶聪明。

description:
猪棋的规则：

在一个 $1000\times 1000$ 的棋盘上，两人分别执黑棋白棋轮流执子，每次可以在当前没有子的不同位置将两颗子分别放下（有序），如果一颗子放下时出现有 $(x,y),(x+1,y),(x,y+1),(x+1,y+1)$ 的四个位置棋子颜色均相同则执此颜色者获胜。

你将扮演先手，在 $100$ 步内战胜交互库扮演的后手，保证有解。

对于每轮，你可以选择两个坐标 $(x_1,y_1)$ 与 $(x_2,y_2)$ 落子，你首先需要保证 $1\leq x_1,y_1,x_2,y_2\leq 1000$，你其次需要保证没人曾在 $(x_1,y_1)$ 落子，如果此时你获胜了判定结束且你获胜，否则你还需保证没人曾经在 $(x_2,y_2)$ 落子,如果此时你获胜了判定结束且你获胜，否则交互库将返回一组 $x_1,y_1,x_2,y_2$ 表示他在 $(x_1,y_1),(x_2,y_2)$ 落子，保证 $(x_1,y_1)\neq (x_2,y_2),1\leq x_1,y_1,x_2,y_2\leq 1000$，如果此时交互库获胜判定结束且你输了,否则判定棋盘上是否已经有 $400$ 颗子，如果是你获得平局，否则进入你的新一轮。

inputFormat: 你每轮结束后从**标准输入**中输入四个整数，代表评测机返回的结果。

outputFormat:
每轮开始时，你需要向**标准输出**输出四个 $[1,1000]$ 中的整数，**然后清空缓冲区**。

你可以使用如下语句来清空缓冲区：

- 对于 C/C++：`fflush(stdout)`；
- 对于 C++：`std::cout << std::flush`；
- 对于 Java：`System.out.flush()`；
- 对于 Python：`stdout.flush()`；
- 对于 Pascal：`flush(output)`；
- 对于其他语言，请自行查阅对应语言的帮助文档。

特别的，对于 C++ 语言，在输出换行时如果你使用 `std::endl` 而不是 `'\n'`，也可以自动刷新缓冲区。

hint:
共 $5$ 个测试点，在测试点中如果你获胜且每步都满足 $6\leq x,y\leq 994$ 你将获得 $100$ 分，否则获胜你将获得 $50$ 分，你输了将获得 $0$ 分，平局获得 $30$ 分，总分数取测试点最小值。

本题输入输出参考 $0$ 分程序：

```cpp
#include <bits/stdc++.h>

using namespace std;

int n;
int x,y,xx,yy;

signed main()
{
    int i,j,k;
    n=100;
    while(n--)
    {
        cout<<rand()%1000+1<<' '<<rand()%1000+1<<endl;
        cout<<rand()%1000+1<<' '<<rand()%1000+1<<endl;
        cin>>x>>y>>xx>>yy;
    }
    return 0;
}
```


title: [集训队互测 2023] 童话

background:
~~童话只美在真实却从不续写。~~

童话只美在温柔却从不续写。

description:
泠珞最近学习了前缀和算法，她写出了以下程序：

```cpp
read(n),read(a);
for(int i=0;i<=n;i++)read(f[i]);
for(int t=1;t<=n;t++){
    for(int i=1;i<=n;i++)f[i]=f[i]+a*f[i-1];
    ans[t]=f[t];
}
```

她发现这个程序在 $n$ 比较大的时候会运行超时，请你帮忙写一个程序帮她计算出 $\text{ans}_1,\text{ans}_2,\cdots,\text{ans}_n$，由于答案数值过大，你只需告诉她每个数除以 $998244353$ 的余数。

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

接下来一行 $n+1$ 个非负整数，表示 $f_0,f_1,\cdots,f_n$。


title: [ICPC2018 Qingdao R] Sequence and Sequence

description:
Consider the following two sequences $P$ and $Q$. We denote $P(i)$ as the $i$-th element in sequence $P$, and $Q(i)$ as the $i$-th element in sequence $Q$:

- Sequence $P$ is a $\textbf{sorted}$ sequence where for all $k \in \mathbb{Z^+}$, $k$ appears in sequence $P$ for $(k+1)$ times ($\mathbb{Z^+}$ is the set of all positive integers). That is to say, $P = \{1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, \dots \}$
- Sequence $Q$ can be derived from the following equations:
$$\begin{cases} Q(1) = 1 & \\ Q(i) = Q(i-1) + Q(P(i)) & \text{if } i > 1 \end{cases}$$
That is to say, $Q = \{1, 2, 4, 6, 8, 12, 16, 20, 24, 30, 36, 42, 48, 54, 62, \dots \}$

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

Given a positive integer $n$, please calculate the value of $Q(n)$.

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

The first and only line contains an integer $n$ ($1 \le n \le 10^{40}$).

outputFormat: For each test case output one line containing one integer, indicating the value of $Q(n)$.

translation:
### 题目描述

考虑下列两个序列 $P$ 和 $Q$。我们用 $P(i)$ 表示序列 $P$ 中的第  $i$ 个元素，用 $Q(i)$ 表示序列 $Q$ 中的第 $i$ 个元素：

- 序列 $P$ 是一个**已排序的**序列，其中，对于所有 $k \in \mathbb{Z^+}$，$k$ 在序列 $P$ 中出现 $(k+1)$ 次（$\mathbb{Z^+}$ 为正整数集）。也就是说，$P = \{1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, \dots \}$
- 序列 $Q$ 可以由以下方程导出：
$$\begin{cases} Q(1) = 1 & \\ Q(i) = Q(i-1) + Q(P(i)) & \text{if } i > 1 \end{cases}$$
也就是说，$Q = \{1, 2, 4, 6, 8, 12, 16, 20, 24, 30, 36, 42, 48, 54, 62, \dots \}$。

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

给定一个正整数 $n$，请计算 $Q(n)$ 的值。

### 输入格式

本题的测试点包含多组测试数据。

第一行输入包含一个整数 $T$ （$10^4$ 左右），表示测试数据的数量。对于每组测试数据：

- 第一行（也是唯一一行）包含一个整数 $n$ （$1 \le n \le 10^{40}$）。

### 输出格式

对于每组测试数据，输出一行，包含一个整数，表示 $Q(n)$ 的值。


title: 『PG2』消除萝卜 A

description:
有 $2\times n$ 的两行萝卜，萝卜分白萝卜和红萝卜，我们使用 $a_{i,j}=0/1$ 来表示第 $j$ 行第 $i$ 个萝卜是白萝卜还是红萝卜。

你每次可以花 $1$ 的代价，选定一个有萝卜的位置，并将这个萝卜所在的由同种颜色萝卜所构成的四连通极大连通块的萝卜全部拿走，然后一个在第二行的萝卜如果其对应的第一行的位置没有萝卜，就会掉落至第一行。

请问拿走所有萝卜的最小代价是多少。

inputFormat:
第一行包含一个正整数 $n$ 表示每行有多少个萝卜。

第二行有 $n$ 个 $0$ 或 $1$ 的整数,其中第 $i$ 个表示 $a_{i,2}$。

第三行有 $n$ 个 $0$ 或 $1$ 的整数,其中第 $i$ 个表示 $a_{i,1}$。

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


title: [LMXOI Round 1] Placer

background:
LMX 最近迷上了括号序列，她尤其钟爱合法括号序列。

LMX 为了检验 HQZ 的真诚，于是她出一道题准备考验下 HQZ。

description:
LMX 给出了一个长度为 $n$ 括号序列 $S$，以及一个长度为 $n$ 的序列 $a_i$。

定义 $w(l,r)=
\begin{cases}
a_r-a_l, & S_{l..r} \text{为合法括号序列}\\
\ 0 & \text{otherwise}
\end{cases}$

你可以将序列分成若干非空子段，定义整个序列的美丽度为每段的 $w(l , r)$ 之和。

求美丽度最大为多少。

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

第二行一个字符串，代表括号序列。

第三行代表序列 $a$。

outputFormat: 第一行一个整数，表示最大的美丽度。


title: 『PG2』消除萝卜 B

description:
有 $n\times 2$ 的两列萝卜，萝卜分白萝卜和红萝卜，我们使用 $a_{i,j}=0/1$ 来表示第 $i$ 行第 $j$ 个萝卜是白萝卜还是红萝卜。

你每次可以花 $1$ 的代价，选定一个有萝卜的位置，并将这个萝卜所在的由同种颜色萝卜所构成的四连通极大连通块的萝卜全部拿走，然后一个在第 $i$ 行的萝卜如果其对应的第 $i-1$ 行的位置没有萝卜，就会掉落至第 $i-1$ 行。

同时你也可以花初始为 $0$ 的代价，选定 $k=1/2$ 而将第 $k$ 列的所有萝卜上移（$a_{i,k}\to a_{i+1,k}$），并将一个红萝卜即 $1$ 放在第一行第 $k$ 个（$1\to a_{1,k}$），此后这个操作代价 $+1$。

请问拿走所有萝卜的最小代价是多少。

inputFormat:
第一行包含一个正整数 $n$ 表示有多少行萝卜。

接下来 $n$ 行，第 $i$ 行两个整数分别为 $a_{i,1},a_{i,2}$。

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


title: [ICPC2018 Qingdao R] Kawa Exam

description:
BaoBao is taking an online exam of the Kawa programming language, which consists of $n$ multiple choice questions. The exam is not easy, as for each question, BaoBao needs to select the one and only one correct answer from $10^5$ available choices! But don't worry, as an active committer of the famous \textit{open-kdk}, BaoBao obviously knows all the correct answers.

Although BaoBao is an expert in Kawa, the developers of the exam system are definitely not experts in software engineering. There are $m$ bugs in the exam system, and the $i$-th bug can be described as $(u_i, v_i)$, which means that BaoBao must select the same choice for question $u_i$ and $v_i$ (even if the choice he selects is incorrect!).

Time is limited, and the exam must go on. The developers only have time to fix one bug. Now the developers are wondering, for all $1 \le i \le m$, what's the maximum possible number of questions BaoBao can correctly answer if they fix the $i$-th bug. Please write a program to solve this problem so that the developers can select a proper bug to fix.

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

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^5$, $1 \le m \le 10^5$), indicating the number of questions and the number of bugs.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$), where $a_i$ indicates the correct answer for question $i$.

For the following $m$ lines, the $i$-th line has two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$), indicating the $i$-th bug.

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

outputFormat:
For each test case output one line containing $m$ integers $c_1, c_2, \dots, c_m$ separated by a space, where $c_i$ indicates the maximum possible number of questions BaoBao can correctly answer if the $i$-th bug is fixed.

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

translation:
BaoBao 正在参加 Kawa 编程语言的在线考试，该考试由 $n$ 个多项选择题组成。考试并不容易，对于每一道题，BaoBao 都需要从 $10^5$ 个可用选项中选择唯一一个正确答案！但别担心，作为著名的 $\text{open-kdk}$ 的积极参与者，BaoBao 显然知道所有正确的答案。

虽然 BaoBao 是 Kawa 方面的专家，但考试系统的开发人员绝对不是软件工程方面的专家。考试系统中有 $m$ 个错误，第 $i$ 个错误可以描述为 $(u_i,v_i)$，这意味着 BaoBao 必须为第 $u_i$ 和 $v_i$ 个问题选择相同的选项（即使他选择的选项不正确！）。

但是考试必须继续，这就意味着开发人员只有时间修复一个错误。现在，开发人员想知道，对于所有的 $1\le i\le m$，如果他们修复 $i$，BaoBao 可以正确回答的最大问题数量是多少。

## 输入格式

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

第一行包含两个整数 $n$ 和 $m$（$1\le n\le 10^5$，$1\le m\le 10^5$），表示问题数量和错误数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 10^5$），其中 $a_i$ 表示问题 $i$ 的正确答案。

对于以下 $m$ 行，第 $i$ 行有两个整数 $u_i$ 和 $v_i$（$1\le u_i,v_i\le n$），表示第 $i$ 个错误。

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

## 输出格式

对于每个测试用例的输出，一行包含由空格分隔的 $m$ 个整数 $c_1,c_2,\dots,c_m$，其中 $c_i$ 表示如果修复了第 $i$ 个错误，BaoBao 可以正确回答的最大问题数。

请不要在每行末尾输出多余的空格，否则您的答案可能会被认为是错误的！

## 提示

下表解释了第一个示例测试用例。

- “可能的选择”列表示 BaoBao 可以选择的每个问题的一组可能的选择，从而导致正确回答的问题的最大可能数量；

- “正确”列表示使用“可能的选择”列中提供的一组选择正确回答的问题的数量。

$$\begin{array}{|c|c|c|c|}
\hline
\textbf{Bug 编号} & \textbf{可能的选择} & \textbf{正确} \\
\hline
1 & (1, 2, 1, 2, 1, 1, 1) & 6 \\
\hline
2 & (2, 2, 1, 2, 1, 1, 1) & 5 \\
\hline
3 & (1, 1, 1, 2, 1, 1, 1) & 5 \\
\hline
4 & (1, 1, 1, 1, 1, 2, 1) & 5 \\
\hline
5 & (1, 1, 1, 1, 1, 1, 1) & 4 \\
\hline
\end{array}$$

对于第二个样本测试用例，无论哪个 bug 被修复，BaoBao 都必须为所有三个问题选择相同的选项。由于每个问题的正确答案不同，BaoBao 只能正确回答一个问题。

对于第三个示例测试用例，请注意，即使开发人员修复了第一个错误，第二个错误仍然有效，BaoBao 仍然必须为这两个问题选择相同的选项。如果第二个错误被修复，情况也是一样的。

hint:
The following table explains the first sample test case.

- The ``possible choices`` column indicates a possible set of choices to each question BaoBao can select, leading to a maximum possible number of correctly answered questions;
- The ``correct`` column indicates the number of correctly answered questions using the set of choices provided in the ``possible choices`` column.

$$\begin{array}{|c|c|c|c|}
\hline
\textbf{Bug No.} & \textbf{Possible Choices} & \textbf{Correct} \\
\hline
1 & (1, 2, 1, 2, 1, 1, 1) & 6 \\
\hline
2 & (2, 2, 1, 2, 1, 1, 1) & 5 \\
\hline
3 & (1, 1, 1, 2, 1, 1, 1) & 5 \\
\hline
4 & (1, 1, 1, 1, 1, 2, 1) & 5 \\
\hline
5 & (1, 1, 1, 1, 1, 1, 1) & 4 \\
\hline
\end{array}$$

For the second sample test case, no matter which bug is fixed, BaoBao has to select the same choice for all the three questions. As the correct answer for each question is different, BaoBao can only correctly answer 1 question.

For the third sample test case, note that even if the developers fix the first bug, the second bug is still taking effect and BaoBao still has to select the same choice for the two problems. It's the same if the second bug is fixed.


title: [ICPC2018 Qingdao R] Flippy Sequence

description:
DreamGrid has just found two binary sequences $s_1, s_2, \dots, s_n$ and $t_1, t_2, \dots, t_n$ ($s_i, t_i \in \{0, 1\}$ for all $1 \le i \le n$) from his virtual machine! He would like to perform the operation described below exactly twice, so that $s_i = t_i$ holds for all $1 \le i \le n$ after the two operations.

The operation is: Select two integers $l$ and $r$ ($1 \le l \le r \le n$), change $s_i$ to $(1 - s_i)$ for all $l \le i \le r$.

DreamGrid would like to know the number of ways to do so.

We use the following rules to determine whether two ways are different:

- Let $A = (a_1, a_2, a_3, a_4)$, where $1 \le a_1 \le a_2 \le n, 1 \le a_3 \le a_4 \le n$, be a valid operation pair denoting that DreamGrid selects integers $a_1$ and $a_2$ for the first operation and integers $a_3$ and $a_4$ for the second operation;
- Let $B = (b_1, b_2, b_3, b_4)$, where $1 \le b_1 \le b_2 \le n, 1 \le b_3 \le b_4 \le n$, be another valid operation pair denoting that DreamGrid selects integers $b_1$ and $b_2$ for the first operation and integers $b_3$ and $b_4$ for the second operation.
- $A$ and $B$ are considered different, if there exists an integer $k$ ($1 \le k \le 4$) such that $a_k \ne b_k$.

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

The first line contains an integer $n$ ($1 \le n \le 10^6$), indicating the length of two binary sequences.

The second line contains a string $s_1s_2\dots s_n$ ($s_i \in \{\text{`0'}, \text{`1'}\}$) of length $n$, indicating the first binary sequence.

The third line contains a string $t_1t_2\dots t_n$ ($t_i \in \{\text{`0'}, \text{`1'}\}$) of length $n$, indicating the second binary sequence.

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

outputFormat: For each test case, output an integer denoting the answer.

translation:
给定两个长度为 $n$ 的 **01** 字符串 $s,\,t$。你需要求出有多少个 $1 \le l_1 \le r_1 \le n,\, 1 \le l_2 \le r_2 \le n$，使得分别**取反** $s$ 串的区间 $[l_1,\,r_1]$ 和区间 $[l_2,\,r_2]$ 内的字符串后，$s$ 和 $t$ 相等。取反的定义是对于 01 字符串 $a$，若 $a_i = 0$ 则令 $a_i \leftarrow 1$，否则令 $a_i \leftarrow 0$。

$1\leq n\leq 10 ^ 6$，$\sum n\leq 10 ^ 7$。

hint:
For the second sample test case, there are two valid operation pairs: $(1, 1, 2, 2)$ and $(2, 2, 1, 1)$.

For the third sample test case, there are six valid operation pairs: $(2, 3, 5, 5)$, $(5, 5, 2, 3)$, $(2, 5, 4, 4)$, $(4, 4, 2, 5)$, $(2, 4, 4, 5)$ and $(4, 5, 2, 4)$.


title: [ICPC2018 Qingdao R] Magic Multiplication

description:
BaoBao is now learning a new binary operation between two positive integers, represented by $\otimes$, in his magic book. The book tells him that the result of such operation is calculated by concatenating all multiple results of each digit in the two integers.

Formally speaking, let the first integer be $A = a_1a_2 \dots a_n$, where $a_i$ indicates the $i$-th digit in $A$, and the second integer be $B = b_1b_2 \dots b_m$, where $b_i$ indicates the $i$-th digit in $B$. We have

$$A \otimes B = \sum\limits_{i=1}^n\sum\limits_{j=1}^m a_ib_j = a_1b_1 + a_1b_2 + \dots + a_1b_m + a_2b_1 + \dots + a_nb_m$$

Note that the result of $a_ib_j$ is considered to be a $\textbf{string}$ (without leading zeros if $a_ib_j > 0$, or contains exactly one `0` if $a_ib_j = 0$), NOT a normal integer. Also, the sum here means $\textbf{string concatenation}$, NOT the normal addition operation.

For example, $23 \otimes 45 = 8101215$. Because $8=2 \times 4$, $10=2 \times 5$, $12=3 \times 4$ and $15=3 \times 5$.

BaoBao is very smart and soon knows how to do the inverse operation of $\otimes$. Now he gives you the result of a $\otimes$ operation and the numbers of digits in the two original integers. Please help him to restore the two original integers $A$ and $B$.

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

The first line contains two positive integers $n$ and $m$ ($1 \le n, m \le 2 \times 10^5$), where $n$ indicates the length of $A$ and $m$ indicates the length of $B$. Here length of an integer means the length of the string when writing the number in decimal notation without leading zeros.

The second line contains only one positive integer $C$ without leading zeros, indicating the result of $A \otimes B$. The length of $C$ is no more than $2 \times 10^5$.

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

outputFormat:
For each test case output one line.

If there exist such $A$ and $B$ that $A \otimes B = C$, output one line containing two integers $A$ and $B$ separated by one space. Note that $A$ and $B$ should be positive integers without leading zeros, the length of $A$ should be exactly $n$, and the length of $B$ should be exactly $m$.

If there are multiple valid answers, output the answer with the smallest $A$; If there are still more than one answer, output one of them with the smallest $B$.

If such $A$ and $B$ do not exist, print ``Impossible`` (without quotes) on a single line.

translation:
BaoBao 现在正在他的魔法书中学习两个正整数之间的一种新的二进制运算，用 $\otimes$ 表示。这本书告诉他，这种运算的结果是通过将两个整数中每个数字的所有多个结果串联起来计算的。

形式上讲，让第一个整数为 $A=A_1a_2\dots A_n$，其中 $A_i$ 表示 $A$ 中的第 $i$ 位，第二个整数为 $B=B_1b_2\dots B_m$，其中 $B_i$ 表示 $B$ 中的第一位。我们有

$$A \otimes B = \sum\limits_{i=1}^n\sum\limits_{j=1}^m a_ib_j = a_1b_1 + a_1b_2 + \dots + a_1b_m + a_2b_1 + \dots + a_nb_m$$

请注意，$a_ib_j$ 的结果被认为是 $\textbf{string}$（如果 $a_ib_j>0$，则不带前导零，或者如果 $a_ib_j > 0$，则仅包含一个 $0$），而不是正常整数。此外，这里的 sum 表示 $\textbf{string concatenation}$，而不是正常的加法运算。

例如，$23\otimes 45=8101215$。因为 $8=2\times 4$，$10=2\times 5$，$12=3\times 4$ 和 $15=3\times 5$。

BaoBao 很聪明，很快就知道如何做 $\otimes$ 的逆运算。现在，他给出了 $\otimes$ 运算的结果以及两个原始整数中的位数。请帮助他恢复两个原始整数 $A$ 和 $B$。

## 输入格式

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

第一行包含两个正整数 $n$ 和 $m$（$1\le n,m\le 2\times 10^5$），其中 $n$ 表示 $A$ 的长度，$m$ 表示 $B$ 的长度。这里，整数的长度是指在不带前导零的十进制记数法中写入数字时字符串的长度。

第二行只包含一个不带前导零的正整数 $C$，表示 $A\otimes B$ 的结果。$C$ 的长度不超过 $2\times 10^5$。

保证所有测试用例的 $C$ 长度总和不会超过 $2\times 10^6$。

## 输出格式

对于每个测试用例输出一行。

如果存在这样的 $A$ 和 $B$，$A\otimes B=C$，则输出一行，其中包含由一个空格分隔的两个整数 $A$ 与 $B$。请注意，$A$ 和 $B$ 应该是不带前导零的正整数，$A$ 的长度应该正好是 $n$，$B$ 的长度应正好是 $m$。

如果存在多个有效答案，则输出具有最小 $A$ 的答案；如果仍然有一个以上的答案，请输出其中一个最小的 $B$。

如果不存在这样的 $A$ 和 $B$，请在单行上打印 ``Impossible``（不带引号）。


title: [ICPC2018 Qingdao R] Plants vs. Zombies

description:
BaoBao and DreamGrid are playing the game $\textit{Plants vs. Zombies}$. In the game, DreamGrid grows plants to defend his garden against BaoBao's zombies.

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

$\textit{Plants vs. Zombies(?)} \\
\textit{(Image from pixiv. ID: 21790160; Artist: socha)}$

There are $n$ plants in DreamGrid's garden arranged in a line. From west to east, the plants are numbered from 1 to $n$ and the $i$-th plant lies $i$ meters to the east of DreamGrid's house. The $i$-th plant has a defense value of $d_i$ and a growth speed of $a_i$. Initially, $d_i = 0$ for all $1 \le i \le n$.

DreamGrid uses a robot to water the plants. The robot is in his house initially. In one step of watering, DreamGrid will choose a direction (east or west) and the robot moves exactly 1 meter along the direction. After moving, if the $i$-th plant is at the robot's position, the robot will water the plant and $a_i$ will be added to $d_i$. Because the water in the robot is limited, at most $m$ steps can be done.

The defense value of the garden is defined as $\min\{d_i | 1 \le i \le n\}$. DreamGrid needs your help to maximize the garden's defense value and win the game.

- Each time the robot MUST move before watering a plant;
- It's OK for the robot to move more than $n$ meters to the east away from the house, or move back into the house, or even move to the west of the house.

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

The first line contains two integers $n$ and $m$ ($2 \le n \le 10^5$, $0 \le m \le 10^{12}$), indicating the number of plants and the maximum number of steps the robot can take.

The second line contains $n$ integers $a_1, a_2, ... , a_n$ ($1 \le a_i \le 10^5$), where $a_i$ indicates the growth speed of the $i$-th plant.

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

outputFormat: For each test case output one line containing one integer, indicating the maximum defense value of the garden DreamGrid can get.

translation:
给定 $n$ 个植物和 $m$ 的步数限制，每个植物在位置 $1\dots n$ 上。你初始时在位置 $0$，每次可以移动到相邻的位置上。

每次设你走完一步后到达的位置是 $i$，则会使得这个位置的植物的高度增加 $a_i$。设 $d_i$ 为走完 $m$ 步后位置 $i$ 的植物高度，求出一个最优的走法使得 $\min\limits_{1 \le i \le n} d_i$ 最大。

$2\leq n\leq 10 ^ 5$，$0\leq m\leq 10 ^ {12}$，$1\leq a_i\leq 10 ^ 5$，$\sum n\leq 10 ^ 6$。

hint:
In the explanation below, `E` indicates that the robot moves exactly 1 meter to the east from his current position, and `W` indicates that the robot moves exactly 1 meter to the west from his current position.

For the first test case, a candidate direction sequence is $\{E, E, W, E, E, W, E, E\}$, so that we have $d = \{6,6,12,6\}$ after the watering.

For the second test case, a candidate direction sequence is $\{E, E, E, E, W, E, W, E, W\}$, so that we have $d = \{10, 10, 4\}$ after the watering.