yl-9/probench huggingface dataset:
# 小苯晨跑

## 题目描述

> 小苯生活在计算机网络世界中，网络空间中到处都是数据，小苯每次晨跑，风都会带着这些数据乱飞。 

  


现在正在晨跑的小苯面前有四个数据，他想知道这些数据是否乱飞了，请你帮他确定吧。 

（如果所有数据都相等，则认为数据没有乱飞，反之则乱飞了。）  


## 输入描述:
    
    
    本题含有多组测试数据。  
    第一行一个正整数 $T\ (1 \leq T \leq 1000)$，表示测试数据的组数。  
    接下来对于每组测试数据，输入包含一行四个正整数 $a_1, a_2, a_3, a_4\ (1 \leq a_1, a_2, a_3, a_4 \leq 1000)$，表示小苯面前的四个数据。

## 输出描述:
    
    
    对于每组测试数据，输出一行一个字符串。  
    如果当前的数据乱飞了，则输出"YES"，否则输出一个 "NO"。  
    （都不包含双引号。）

示例1 

## 输入
    
    
    2
    2 2 2 2
    1 2 3 3

## 输出
    
    
    NO
    YES

## 说明
    
    
    第一组测试数据中，所有数据都相同，则数据没有乱飞。  
    第二组测试数据中，并不满足所有数据都相同，则我们认为数据乱飞了。

## 备注:
    
    
    嗯...等会去网工大买几个包子。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小苯过马路

## 题目描述

小苯生活在遥远的 B 星球，这天他正在等红绿灯，已知 B 星球的交规是：红灯有 $x$ 秒，绿灯有 $y$ 秒，红灯和绿灯是交替亮灯的。 

（红灯上的时间从 $x$ 减少到 $1$ 后，再过一秒灯就会变成绿色，同时灯显示的时间也会变成 $y$；绿灯也同理。） 

  


已知目前红绿灯颜色为 $c$，灯显示的时间为 $k$，小苯过马路需要花费的时间为 $t$。 

**遵守交规** 的小苯想知道，从此刻开始到他走到马路对面，最少经过多少秒，请你帮他算一算吧。**（小苯一旦开始过马路就不会停下脚步。）**

## 输入描述:
    
    
    输入包含一行，四个数字 $x, y, k, t\ (1 \leq x, y, k, t \leq 1000, t \leq y)$ 和一个字符 $c$ 。  
    
    
    分别表示该路口红灯和绿灯的时间 $x, y$，和目前灯上显示的数字 $k$，以及小苯通过马路需要花费的时间 $t$ 以及目前灯的颜色 $c$（'G' 表示绿灯，'R' 表示红灯）。
    
    （保证输入的时间是合法的，即如果 $c=$'G'，则 $k \leq y$，否则 $k \leq x$。）  
    

## 输出描述:
    
    
    输出一行一个整数，表示小苯走到马路对面最少经过的秒数。

示例1 

## 输入
    
    
    30 30 10 10 G

## 输出
    
    
    10

## 说明
    
    
    目前红绿灯是绿色，还剩 10 秒，刚好够小苯走过马路。

示例2 

## 输入
    
    
    30 40 5 10 G

## 输出
    
    
    45

## 说明
    
    
    目前是绿色，但只剩 5 秒，因此小苯需要等下一个绿灯，才能走过去，总共花费 45 秒。

## 备注:
    
    
    红灯停，绿灯行。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小苯的字符串染色

## 题目描述

小苯有一个长度为 $n$ 的字符串 $s$，其中有一些字符是黑色的，其余则为白色，他希望你可以给 $s$ 涂色，使得涂完后的 $s$ 是纯白色的。  
具体的涂色操作：  


$\bullet$ 选择一个长度为奇数的区间 $[l, r]\ (1 \leq l \leq r \leq n)$ 同时 $r-l+1$ 是奇数，接着将区间内的字符按照：白，跳过，白，跳过，白...的方式涂色（跳过的地方不涂色）。 

即：$s_l$ 和 $s_r$ 涂成白色，中间每间隔一个涂白一个的方式。 

  


小苯限制你最多进行 $n$ 次涂色操作，请你构造一个合法涂色方案，使得涂色完后的字符串是**全白色** 的吧，注意你**不必** 最小化操作次数。 

（注意，已经涂好颜色的地方依然可以被后续的涂色覆盖。） 

## 输入描述:
    
    
    本题含有多组测试数据。  
    第一行一个正整数 $T\ (1 \leq T \leq 100)$，表示测试数据的组数。  
    接下来对于每组测试数据，输出包含两行：  
    第一行一个正整数 $n\ (1 \leq n \leq 5000)$，表示字符串 $s$ 的长度。  
    
    
    第二行一个长度为 $n$ 的 $01$ 串 $s$。（保证 $s$ 仅有字符 '0' 和 '1' 构成，其中 '0' 代表白色，'1' 代表黑色。）
    
    （保证所有测试数据中，$n$ 的总和不超过 $5000$。）

## 输出描述:
    
    
    对于每组测试数据，第一行输出一个整数 $m\ (0 \leq m \leq n)$，表示进行操作的次数。  
    
    
    接下来 $m$ 行，每行两个正整数 $l, r\ (1 \leq l \leq r \leq n), ((r-l+1)\%2=1)$，表示对 $s_l, s_{l+1}, \cdots ,s_r$ 这一段区间执行涂色操作。
    
    （有多解输出任意即可，可以证明一定有解。）

示例1 

## 输入
    
    
    1
    6
    101101

## 输出
    
    
    2
    1 3
    4 6

## 说明
    
    
    $s$ 的颜色是：黑白黑黑白黑。  
    可以进行两次操作：  
    先涂 $[1,3]$ 区间，操作后 $s$ 变为：白白白黑白黑。  
    再涂 $[4,6]$ 区间，操作后 $s$ 变为全白。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 小苯的能量项链

## 题目描述

小苯有一个含有 $n$ 颗珠子的“能量项链”，珠子排成一排，其中第 $i$ 颗珠子的能量为 $a_i$。  
  
但是这个项链并不稳定，如果项链的珠子个数不少于 $3$ 个，则它即将发生“崩坏”，即：除了第一颗珠子和最后一颗珠子以外的其余所有珠子都将销毁，最终只留下**第一颗** 和**最后一颗** 珠子。  
  
小苯现在希望项链在“崩坏”后保留尽可能多的能量，为此他可以在崩坏前执行以下的操作：  
$\bullet$ 去掉项链的第一颗珠子（也就意味着项链原本的第二颗珠子将会变成第一颗）。  
$\bullet$ 去掉项链的最后一颗珠子（也就意味着项链原本的倒数第二颗珠子将会变成最后一颗）。  
  
两种操作各自均需要花费 $1$ 秒时间，而现在距离项链发生“崩坏”仅剩 $k$ 秒，小苯想知道，他最多可以保留住多少能量，请你帮他算一算吧。

## 输入描述:
    
    
    每个测试文件内都包含多组测试数据。  
    
    
    第一行一个正整数 $T\ (1 \leq T \leq 1000)$，表示测试数据的组数。
    
    接下来对于每组测试数据，输入包含两行。
    
    第一行两个整数 $n, k\ (1 \leq n \leq 5 \times 10^5, 0 \leq k \leq 10^9)$，表示项链的珠子个数和距离项链“崩坏”的时间。  
    第二行 $n$ 个正整数 $a_i\ (1 \leq a_i \leq 10^9)$，表示每颗珠子的能量。
    
    （保证所有测试数据中 $n$ 的总和不超过 $5 \times 10^5$。）

## 输出描述:
    
    
    对于每组测试数据，输出一行一个整数表示小苯能保留的最大能量。

示例1 

## 输入
    
    
    2
    5 2
    2 3 4 5 2
    1 1
    114514

## 输出
    
    
    8
    114514

## 说明
    
    
    对于第一组测试数据，距离发生“崩坏”还有 $k=2$ 秒，最优的方案是删除目前的第一个和最后一个数字，那么项链的能量会变成：$\{3,4,5\}$，最终 $3$ 和 $5$ 会保留下来，因此最大值为 $8$。  
    对于第二组测试数据，由于项链珠子个数小于3，因此不会发生崩坏，最终保留的能量就是 $114514$。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小苯的最短路

## 题目描述

小苯有一个 $n$ 个点的**无向完全图** ，编号从 $1$ 到 $n$，其中 $i$ 号点和 $j$ 号点之间的边权为 $i \oplus j$。 

  


他想知道从 $1$ 号点出发到达所有点的最短路，请你帮他算一算吧。（其中 $\oplus$ 表示按位异或运算。） 

（但为了避免输出数据量过大，你只需要输出到达所有点的最短路的异或和即可。） 

## 输入描述:
    
    
    本题含有多组测试数据。  
    第一行一个正整数 $T\ (1 \leq T \leq 10^5)$，表示测试数据的组数。  
    接下来 $T$ 行，每行一个正整数 $n\ (1 \leq n \leq 2 \times 10^9)$ 表示完全图的点数。

## 输出描述:
    
    
    对于每组测试数据，输出包含一行一个正整数 $S$，表示到所有点的最短路的异或和，即：令 $d_i$ 表示从 $1$ 到 $i$ 号点的最短路，则 $S=d_1 \oplus d_2 \oplus d_3 \oplus \cdots \oplus d_n$。。

示例1 

## 输入
    
    
    3
    1
    2
    4

## 输出
    
    
    0
    3
    4

## 说明
    
    
    对于第二组测试数据，从 $1$ 号点出发到 $2$ 号点只能走 $1\rightarrow2$ 这条边，因此 $d_2=3$，而又因为 $d_1=0$，因此输出的 $S=d_1 \oplus d_2 = 0 \oplus 3 = 3$。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小苯的优雅好序列

## 题目描述

小苯认为满足以下任一条件的序列 $a$ 是优雅的。  
$\bullet\ |a|=1$。  


$\bullet$ 对于所有 $i\ (1 \leq i \leq |a|)$，都存在 $j\ (1 \leq j \leq |a|, j \ne i)$，使得 $a_j | a_i$ 或 $a_i | a_j$。 

  


小苯认为一个长度为 $n$ 的数组 $a$ 是好数组，当且仅当 $a$ 所有的连续子数组都优雅。即对于所有 $l, r\ (1 \leq l \leq r \leq n)$，$a_l, a_{l+1},\cdots,a_r$ 都是一个优雅的序列。  
  
现在小苯有一个数组 $a$ 和正整数 $k$，他想知道有多少个不超过 $k$ 的正整数 $x\ (1 \leq x \leq k)$，都有：$a_1+x, a_2+x,\cdots,a_n+x$ 是一个好数组，请你帮他算一算吧。

## 输入描述:
    
    
    每个测试文件内都包含多组测试数据。  
    
    
    第一行一个正整数 $T\ (1 \leq T \leq 500)$，表示测试数据的组数。
    
    接下来对于每组测试数据，输入包含两行。
    
    第一行两个正整数 $n,k\ (1 \leq n \leq 5 \times 10^4, 1 \leq k \leq 10^9)$，表示数组 $a$的长度。  
    第二行 $n$ 个整数 $a_i\ (1 \leq a_i \leq 10^9)$，表示数组 $a$。
    
    （保证所有测试数据中 $n$ 的总和不超过 $6\times 10^4$。）

## 输出描述:
    
    
    输出 $T$ 行，每行两个整数 $cnt, sum$，分别表示不同的 $x$ 数字个数，以及这些 $x$ 的和。

示例1 

## 输入
    
    
    3
    5 10
    7 79 1 7 1
    2 1000000000
    1 2
    1 100
    1000000000

## 输出
    
    
    3 8
    0 0
    100 5050

## 说明
    
    
    对于第一组测试数据，存在 $x=1, x=2, x=5$，这 $3$ 个合法的数字，他们的和是 $1+2+5=8$。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小苯的树上操作

## 题目描述

小苯有一个 $n$ 个点 $n-1$ 条边的无向无根树，但其点权中可能存在负数。 

现在如果树非空，则小苯可以对树进行一些“删点”操作任意次（两种都是任意次），具体的：  
  
$\bullet$ 小苯可以选择任意一个度数**至多** 为 $1$ 的节点，从树中直接删除该点和连接该点的边。  
$\bullet$ 小苯可以选择任意一个度数恰好为 $2$ 的节点，从树中删除该点，并将该点连接的两个邻点连接起来。  
  
小苯想知道，他最大可以将树的点权和变为多少，请你帮他算一算吧。  
（注意：空树的点权视为 $0$）。

## 输入描述:
    
    
    每个测试文件内都包含多组测试数据。  
    
    
    第一行一个正整数 $T\ (1 \leq T \leq 1000)$，表示测试数据的组数。
    
    接下来对于每组测试数据，输入包含若干行。
    
    第一行一个正整数 $n\ (2 \leq n \leq 2 \times 10^5)$，表示两人所在树的点数。
    
    第二行 $n$ 个整数 $a_i\ (-10^9 \leq a_i \leq 10^9)$，表示每个点的点权。  
    接下来 $n-1$ 行，每行两个正整数 $u,v\ (1 \leq u, v \leq n)$，表示 $u, v$ 两点间有一条边相连。（保证输入是一棵树。）  
    
    
    （保证所有测试数据中 $n$ 的总和不超过 $3 \times 10^5$。）

## 输出描述:
    
    
    输出包含 $T$ 行，对于每组测试数据，输出一行一个整数，表示小苯操作完后，树的最大点权和。

示例1 

## 输入
    
    
    2
    5
    2 -3 -2 -4 4
    1 2
    1 3
    2 4
    2 5
    7
    -1 -1 -1 -1 -1 -1 1
    1 2
    2 3
    3 4
    4 5
    5 6
    6 7

## 输出
    
    
    6
    1

## 说明
    
    
    两个样例的树：
    
    ![](https://uploadfiles.nowcoder.com/images/20241125/0_1732548547247/D2AB30CABAB9460B3BFCBBFFC160D51E)  
    
    
    ![](https://uploadfiles.nowcoder.com/images/20241125/0_1732548527465/4D240358CAE635B8FE4CF8B85A1F5ABF)  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 构造C的歪

## 题目描述

$\hspace{15pt}$小歪有两个整数 $a$ 和 $b$ ，他想找到这样一个整数 $c$ ，使得这三个整数在经过排序后能成为一个等差数列。

## 输入描述:
    
    
    $\hspace{15pt}$在一行上输入两个整数 $a,b\left(1 \leqq a,b \leqq 10^6 \right)$ 代表已有的数字。

## 输出描述:
    
    
    $\hspace{15pt}$在一行上输出一个整数代表你所找到的第三个数字。  
      
    $\hspace{15pt}$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1 

## 输入
    
    
    3 2

## 输出
    
    
    1

## 说明
    
    
    $\hspace{15pt}$$\{1,2,3\}$ 是一个以 $1$ 为首项、$1$ 为公差的等差数列。当然，输出 $4$ 也是一个正确的答案。

示例2 

## 输入
    
    
    3 2

## 输出
    
    
    4


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld
# 不要三句号的歪

## 题目描述

$\hspace{15pt}$在书写超过 $3$ 个的连续的数字时，我们通常会将第一、二项和最后一项写出，中间的部分使用三个英文句号作为省略号 $\texttt{...}$ 替代，例如，$2,3,\texttt{...},7$ 其实就是使用省略号省略了 $4,5,6$ 这三个数字。  
$\hspace{15pt}$现在，对于给定的数列，你需要直接求解出省略了多少数字。

## 输入描述:
    
    
    $\hspace{15pt}$在一行上输入一个长度不超过 $20$ 的字符串。具体的规范为：  
    $\hspace{15pt}$字符串仅包含三个数字 $a,b,c \left( a + 1 =b;\ b + 1 <c \right)$ ，形如 $\texttt{a,b,...,c}$ 数字 $a$ 与 $b$ 间用且使用一个半角逗号（ $\texttt{,}$ ）间隔；省略号由三个半角句号（ $\texttt{.}$ ）构成；省略号前后各使用一个半角逗号间隔。

## 输出描述:
    
    
    $\hspace{15pt}$在一行上输出一个整数代表被省略的数字数量。

示例1 

## 输入
    
    
    2,3,...,7

## 输出
    
    
    3

示例2 

## 输入
    
    
    1,2,...,100000000

## 输出
    
    
    99999997


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# 仰望水面的歪

## 题目描述

$~~~~~~$小歪正在水底潜水，他所在的位置距离水面的直线距离为 $h$ 。小歪有一个神奇的激光装置，激光射向水面后会发生全反射现象。  
$~~~~~~$以小歪所在的位置为原点建立三维坐标轴，小歪的坐标即为 $(0,0,0)$ 。在水中，有一些坐标需要小歪使用激光击中，第 $i$ 个坐标使用 $(x_i,y_i,z_i)$ 表示。求解，对于每一个坐标，小歪需要以什么向量方向射出激光，使得经过一次水面全反射后恰好击中它。

## 输入描述:
    
    
    $~~~~~~$第一行输入两个整数 $n,h \left( 1 \leqq n \leqq 100;\ 1 \leqq h \leqq 10^9 \right)$ 代表需要击中的坐标位置数量、距离水面的距离。  
    $~~~~~~$随后 $n$ 行，每行输入三个整数 $x,y,z \left( 1 \leqq x,y \leqq 10^9; -10^9 \leqq z \leqq h\right)$ 代表需要击中的坐标。

## 输出描述:
    
    
    $~~~~~~$对于每一个坐标，在一行上输出三个整数 $i,j,k$ ，代表射出向量方向，你需要保证 $\gcd(i,j,k) = 1$ 。

示例1 

## 输入
    
    
    2 5
    3 3 2
    4 4 0

## 输出
    
    
    3 3 8
    2 2 5

## 说明
    
    
    向 $(2,2,5)$ 位置射出射线，经过全反射后会到达目标点 $2$ 。
    
    ![](https://uploadfiles.nowcoder.com/images/20240930/0_1727670723989/2B9ABEC605D24E53A99790B09E44CE6A)  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小心火烛的歪

## 题目描述

$\hspace{15pt}$小歪正在一个占地 $n \times m$ 大小的草地上研究他的燃放烟花计划。其中，一些位置已经堆放了杂物，为了便于观察，我们将给出一个 $n \times m$ 大小的字符矩阵描述草地。其中，堆放了杂物的位置使用数字 $1$ 标注；其余位置使用数字 $0$ 标注。  
$\hspace{15pt}$小歪已经做好了若干个烟花燃放计划，每一个计划均为一个 $n \times m$ 大小的字符矩阵，一一对应草地的每一个方格。在这个计划中，将会被燃放烟花的地块使用数字 $1$ 标注；没有烟花的地块使用数字 $0$ 标注。  
$\hspace{15pt}$他想选择一些计划同时实施，如果某个地块在任意一个计划中被标注为燃放，那么这个地块就会真的燃放上烟花。小歪想要知道，是否存在这样一种选择方法，使得全部有杂物位置均不会燃放烟花，而没有杂物的位置全部燃放上烟花；如果存在，请输出最少数量的计划。

## 输入描述:
    
    
    $\hspace{15pt}$第一行输入三个整数 $n,m,q \left( 1 \leqq n,m,q \leqq 7 \right)$ 代表草地的长、草地的宽、计划数量。  
    $\hspace{15pt}$此后 $n$ 行，每行输入 $m$ 个字符，代表草地初始状态。  
    $\hspace{15pt}$此后 $n \times q$ 行，每行输入 $m$ 个字符，用于描述计划。  
    $\hspace{15pt}$全部字符仅为数字 $\texttt{0}$ 或 $\texttt{1}$ 。

## 输出描述:
    
    
    $\hspace{15pt}$如果不存在满足要求的燃放方案，直接输出 $-1$ 。  
      
    $\hspace{15pt}$否则，请按如下格式输出：  
    $\hspace{15pt}$第一行上输出一个整数 $p \left( 0 \leqq p \leqq q \right)$ 代表使用到的计划数量。  
    $\hspace{15pt}$第二行输出 $p$ 个整数代表你所选择的计划编号。编号即输入顺序，从 $1$ 开始计数。  
      
    $\hspace{15pt}$如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

示例1 

## 输入
    
    
    2 2 1
    00
    01
    11
    10

## 输出
    
    
    1
    1

示例2 

## 输入
    
    
    7 7 5
    1110111
    1111111
    1100001
    0101000
    1100001
    1111111
    1110111
    0001000
    0000000
    0000000
    1000001
    0000000
    0000000
    0001000
    0000000
    0000000
    0011100
    0000000
    0011100
    0000000
    0000000
    0000000
    0000000
    0000010
    0000111
    0000010
    0000000
    0000000
    0000000
    0000000
    0010000
    0010000
    0010000
    0000000
    0000000
    0000000
    0000000
    0010000
    0010111
    0010000
    0000000
    0000000

## 输出
    
    
    4
    1 2 3 4

## 说明
    
    
    $\hspace{15pt}$草地初始状态如下图所示。在这个样例中，选择 $1,2,3,5$ 也是一个合法的答案。
    
    ![](https://uploadfiles.nowcoder.com/images/20241125/0_1732513792951/20402A8889C9AF147476C63CBBA7940D)  
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld
# 喜欢切数组的红

## 题目描述

$\hspace{15pt}$小红有一个长度为 $n$ 的数组 $\\{a_1,a_2,\dots,a_n\\}$ ，她打算将数组切两刀变成三个非空子数组，使得每一个子数组中至少存在一个正数，且每个子数组的和都相等。  
$\hspace{15pt}$ 看起来不是很难，所以小红想让你求解，一共有多少种不同的切分方案。

## 输入描述:
    
    
    $\hspace{15pt}$第一行输入两个整数 $n \left( 3 \leqq n \leqq 2 \times 10^5 \right)$ 代表数组中的元素数量。  
    $\hspace{15pt}$第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n \left( -10^9 \leqq a_i \leqq 10^9 \right)$ 代表数组元素。

## 输出描述:
    
    
    $\hspace{15pt}$在一行上输出一个整数，代表切分方案数。

示例1 

## 输入
    
    
    3
    3 3 3

## 输出
    
    
    1

示例2 

## 输入
    
    
    6
    1 1 4 5 1 4

## 输出
    
    
    0

示例3 

## 输入
    
    
    10
    0 3 4 2 3 2 1 -1 3 4

## 输出
    
    
    2


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# 研究red子序列的红

## 题目描述

$\hspace{15pt}$小红有两个长度为 $n$ 的字符串 $s,t$ ，仅包含小写字母，下标从 $1$ 开始。  
$\hspace{15pt}$她每次会进行一个操作，把 $s_i$ 和 $t_i$ 交换，你需要回答每一次交换后字符串 $s$ 中的 $\texttt{"red"}$ 子序列和 $t$ 中 $\texttt{"red"}$ 的 _子序列_ 之差。  
$\hspace{15pt}$每次询问不独立。  
  
$\hspace{15pt}$_子序列_ 是指在一个序列中，通过删除某些元素（可以是零个或多个元素），而不改变其余元素的相对顺序所得到的序列。  


## 输入描述:
    
    
    $\hspace{15pt}$第一行两个整数 $n,q \ (1\leqq n,q\leqq 2\times 10^5)$ 代表字符串长度和操作次数。  
    $\hspace{15pt}$第二行一个长度为 $n$ 的字符串 $s$ 。  
    $\hspace{15pt}$第三行一个长度为 $n$ 的字符串 $t$ 。  
    $\hspace{15pt}$此后 $q$ 行，每行一个整数 $x\ (1\leqq x\leqq n)$，表示每次交换的位置。

## 输出描述:
    
    
    $\hspace{15pt}$对于每一次询问，在一行上输出一个整数，表示交换后字符串 $s$ 中的 $\texttt{"red"}$ 子序列和 $t$ 中 $\texttt{"red"}$ 的子序列之差。

示例1 

## 输入
    
    
    5 2
    redar
    adade
    5
    4

## 输出
    
    
    1
    2


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# 三途川的摆渡人（二）

## 题目描述

小红这天来到了三途川，发现这里有一个摆渡人，名字叫小町。  
小町的职责是将一些灵魂运送到冥界。但小町非常喜欢偷懒，她经常在上班的时候摸鱼，导致很多灵魂不能成功送达，因此在彼岸开出了许多彼岸花。  
  
小红准备统计彼岸花的数量，她把排队等待摆渡的灵魂用一个01串来表示，'0'代表因小町摸鱼未能上船的灵魂，'1'代表成功到达冥界的灵魂。每个未上船的灵魂都将化为一朵彼岸花，请你帮小红计算彼岸花的数量。

## 输入描述:
    
    
    第一行输入一个正整数$n$，代表灵魂的数量。  
    第二行输入一个长度为$n$的01串，代表每个灵魂是否成功被小町送往冥界。  
    $1\leq n \leq 100$

## 输出描述:
    
    
    一个整数，代表彼岸花的数量。

示例1 

## 输入
    
    
    4
    0100

## 输出
    
    
    3

## 说明
    
    
    小町摸鱼只完成了1/4的工作，因此最终开出了3朵彼岸花。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 魔法之森的蘑菇（二）

## 题目描述

小红在魔法之森迷路了，森林中有一些致幻的毒蘑菇。森林用一个 $n$ 行 $m$ 列的矩阵表示。  
小红准备采集一个矩形区域里的资源，但小红非常讨厌蘑菇，因此她希望这个矩形内没有任何蘑菇。  
小红希望你帮她计算出一个面积最大的、且不包含蘑菇的矩形区域。

## 输入描述:
    
    
    第一行输入两个正整数$n,m$，代表矩阵的行数和列数。  
    接下来的$n$行，每行输入一个长度为$m$的字符串，用来表示森林地图。  
    保证所有的字符仅有'.'和'*'这两种，其中'.'代表道路，'*'代表蘑菇。  
    $1\leq n,m \leq 30$

## 输出描述:
    
    
    四个整数$x_1,y_1,x_2,y_2$，用空格隔开。代表矩形的左上角在第$x_1$行第$y_1$列，右下角在第$x_2$行第$y_2$列。保证至少有一个合法的答案。

示例1 

## 输入
    
    
    3 3
    .*.
    ...
    .*.

## 输出
    
    
    1 1 3 1

## 说明
    
    
    该答案不唯一，有3种选择矩形的方式都能采集到总面积为3的格子。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 迷途之家的大贤者（二）

## 题目描述

小红在穿越后不久，就被大贤者小紫发现了，于是小紫友好地请小红来迷途之家做客。  
  
她们准备玩一个游戏，两人分别拿到了一个长度为$n$的数组。她们可以进行若干次操作。  


对于每次操作，两人可以同时删除自己数组中任意一个元素。她们希望两人通过若干次删除操作，使得操作后的两个数组中所有元素均互不相同。例如$[1,2][3,4]$满足条件，而$[1,2][2,3]$不满足条件，因为两个数组中有两个值为$2$的元素。 

你能帮小红求出操作的最小次数吗？ 

## 输入描述:
    
    
    第一行输入一个正整数$n$，代表每个人数组的大小。  
    第二行输入$n$个正整数$a_i$，代表小红拿到的数组元素。  
    第三行输入$n$个正整数$b_i$，代表小紫拿到的数组元素。  
    $1\leq n \leq 10^5$  
    
    
    $1\leq a_i, b_i \leq 10^9$

## 输出描述:
    
    
    一个整数，代表操作的最小次数。  
    
    
      
    

示例1 

## 输入
    
    
    4
    1 2 1 3
    2 4 3 5

## 输出
    
    
    2

## 说明
    
    
    第一次操作，小红删除一个1，小紫删除一个2。  
    第二次操作，小红删除一个3，小紫删除一个4。  
    最终两人剩余的4个数分别为[1,2,3,5]，不包含相同的元素。  
    可以证明，操作方案不唯一，但最小操作次数为2。  
    

示例2 

## 输入
    
    
    3
    8 8 8
    8 8 8

## 输出
    
    
    3

## 说明
    
    
    必须进行3次操作删除掉所有元素。

示例3 

## 输入
    
    
    4
    2 1 1 2
    2 2 2 1

## 输出
    
    
    3


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 红魔馆的馆主（二）

## 题目描述

小红来到了红魔馆。众所周知，红魔馆的馆主是一只495岁的吸血鬼，所以她非常喜欢495这个数。  
  
现在小红拿到了一个数组，她认为该数组的“美丽度”为：选两个元素$a_i$和$a_j(i<j)$，乘积为495的倍数的方案数。  
小红可以进行最多1次操作：选择一个元素，使其加1。请你帮小红求出最多1次操作后，数组的最大美丽度。

## 输入描述:
    
    
    第一行输入一个正整数$n$，代表每个人数组的大小。  
    第二行输入$n$个正整数$a_i$，代表数组的元素。  
    $1\leq n,a_i \leq 400000$

## 输出描述:
    
    
    一个整数，代表最多一次操作后，数组的最大美丽度。

示例1 

## 输入
    
    
    4
    1 9 55 494

## 输出
    
    
    4

## 说明
    
    
    使第四个元素加1即可。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 博丽神社的巫女（二）

## 题目描述

小红来到了博丽神社，发现博丽神社门口有一个赛钱箱。  
  
这时神社里走出了一个巫女，对小红说：给你一个数组，你可以对任意元素进行任意次“该元素除以2向下取整”的操作，只要你能让这个数组所有元素之和等于100000，你就能拿走赛钱箱里所有的钱，否则你就必须往赛钱箱投十万元，你想和我玩这个游戏吗？  
  
小红很想赚取赛钱箱里的金币，请你帮帮小红。

## 输入描述:
    
    
    第一行输入一个正整数$n$，代表巫女给小红的数组大小。  
    第二行输入$n$个正整数$a_i$，代表数组的元素。  
    $1\leq n\leq 100$  
    $1\leq a_i \leq 10^5$  
    保证所有元素之和$S$的范围满足$100000 \leq S \leq 200000$

## 输出描述:
    
    
    如果小红必然输掉游戏，请输出-1。  
    否则输出$n$个非负整数$b_i(0\leq b_i \leq 10^5)$，分别代表对第$i$个元素执行$b_i$次操作。

示例1 

## 输入
    
    
    2
    50000 100000

## 输出
    
    
    0 1

## 说明
    
    
    对第二个元素操作1次即可。  
    方案不唯一，输出[12345,0]也是可以的。  
    

示例2 

## 输入
    
    
    2
    55555 66666

## 输出
    
    
    -1


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 雾之湖的冰精（三）

## 题目描述

雾之湖里有一只聪慧的冰精，她会进行9以内的加法运算，然而当计算的结果超过9了她的脑子就会陷入红温。  
  
小红拿到了一棵树，每个节点的权值为$a_i$。她想选择一条简单路径，使得该路径权值和不超过9，请你帮小红计算有多少种选择方案。  
  
我们认为，一个合法的路径应至少包含2个节点。u->v或者v->u我们视为同一条路径。

## 输入描述:
    
    
    第一行输入一个正整数$n$，代表树的节点数量。  
    第二行输入$n$个正整数$a_i$，代表每个节点的权值。  
    接下来$n-1$行，每行输入两个正整数$u$和$v$，代表树的一条边。  
    $1\leq n \leq 10^5$  
    $0\leq a_i \leq 9$  
    $1\leq u,v \leq n$

## 输出描述:
    
    
    输出一个整数，代表合法的路径数量。

示例1 

## 输入
    
    
    3
    3 4 5
    1 2
    2 3

## 输出
    
    
    2

## 说明
    
    
    存在两条合法的路径：1->2或2->3。请注意，1->3路径权值和为12，超过了9，因此会导致冰精陷入红温。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 排序危机

## 题目描述

$\,\,\,\,\,\,\,\,\,\,$小歪有一个同时包含了小写字母、大写字母和数字的字符串，他现在想要重新排列这些字符，使得小写字母都在左边，大写字母全在右边。注意，对于某两个小写字母，排序不会改变他们的相对位置。

## 输入描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$第一行输入一个整数 $n\left(1\le n \le 10^5\right)$ 代表字符串的长度。  
    $\,\,\,\,\,\,\,\,\,\,$第二行输入一个长度为 $n$ ，且由小写字母、大写字母和数字构成的字符串 $s$ 。

## 输出描述:
    
    
    $\,\,\,\,\,\,\,\,\,\,$在一行上输出一个长度为 $n$ 的字符串，代表排序后的字符串。

示例1 

## 输入
    
    
    5
    Aa123

## 输出
    
    
    a123A

## 说明
    
    
    $\,\,\,\,\,\,\,\,\,\,$注意，对于数字字符 '$\rm 1$' 、'$\rm 2$'  和 '$\rm3$' ，在输出时您不能改变他们彼此间的顺序，例如 "$\rm a321A$" 就是错误的。

示例2 

## 输入
    
    
    14
    D1dA1a4M5m14Ee

## 输出
    
    
    dame114514DAME


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小歪商店故事：卷

## 题目描述

$~~~~~~$小歪正在商店里出售牛可乐抱枕，$a$ 元 $b$ 个，物美价廉！  
$~~~~~~$客户说，隔壁的商店也在出售牛可乐抱枕，$c$ 元 $d$ 个，居然是抢生意的！  


$~~~~~~$小歪想要重新调整自己的价格，使得调整后自己出售的单个牛可乐价格**严格低于** 隔壁商店，且在此基础上价格尽可能的高。严谨地说，重新设定一个最大整数 $a'_{\rm max}$ ，使得 $\dfrac{a'_{\rm max}}{b} < \dfrac{c}{d}$ 。 

$~~~~~~$价格战每天都在打，每天都有变化，你只需要输出差价 $a - a'_{\rm max}$ 即可。

## 输入描述:
    
    
    $~~~~~~$第一行输入一个整数 $n\left(1\le n\le 10^4\right)$ 代表天数。  
    $~~~~~~$随后 $n$ 行，每行输入四个整数 $a,b,c,d \left(1\leqq a,b,c,d \leqq 10^9 \right)$ 代表小歪的价格与牛可乐个数、隔壁商店的价格与牛可乐个数。

## 输出描述:
    
    
    $~~~~~~$对于每一天，在一行上连续的输出一个整数，代表差价。

示例1 

## 输入
    
    
    3
    1 1 2 2
    2 1 40 1
    6 5 3 4

## 输出
    
    
    1 -37 3

## 说明
    
    
    $~~~~~~$第一天，小歪售卖的单个牛可乐的价格为 $1$ ，隔壁商户的价格也为 $1$ ，为了能以更低的价格出售，只能降价至 $a'_{\rm max}=0$ 元，这样，小歪的单价为 $0$ ，低于隔壁商户。  
      
    $~~~~~~$第二天，小歪售卖的单个牛可乐的价格为 $2$ ，隔壁商户的单价为 $40$ ，可以提价至 $a'_{\rm max}=39$ 元，这样，自己还是能以更低的单价出售，但是尽可能的多赚。  
      
    $~~~~~~$第三天，小歪售卖的单个牛可乐的价格为 $\frac{6}{5}$ ，隔壁的单价为 $\frac{3}{4}$ ，需要降价至 $a'_{\rm max}=3$ 元。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小苯的计算式

## 题目描述

小苯有一个长度为 $n$ 的字符串，其是一个两**非负整数** 加法运算的式子，形如：$A+B=C$。  
  
现在小苯只记得这个式子的结果 $C$，以及式子的长度 $n$。  
  


请你帮小苯数一数，总共有多少个不同的符合条件的这种式子呢。 

（注意：$A, B, C$ 都是不含前导零的。） 

## 输入描述:
    
    
    输入包含一行两个正整数 $n, C\ (5 \leq n \leq 20),\ (1 \leq C \leq 200000)$。分别表示计算式的长度，以及计算式的结果值。

## 输出描述:
    
    
    输出一行一个整数，表示不同的符合条件的计算式个数。

示例1 

## 输入
    
    
    5 2

## 输出
    
    
    3

## 说明
    
    
    长度为 5 的，运算结果为 2 的，只包含非负整数的不同运算式有：  
    0+2=2  
    1+1=2  
    2+0=2  
    这三个。

## 备注:
    
    
    小苯认为两个计算式 $s1, s2$ 不同：当且仅当 $s1, s2$ 长度不相同，或两者长度相同均为 $n$ 时，存在一个 $i\ (1 \leq i \leq n)$，使得 $s1_i \ne s2_i$。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# K

## 题目描述

$\hspace{15pt}$小歪正在出题，他想要构造一个长度为 $n$ 的数组 $\\{a_1,a_2,\dots,a_n\\} \left( 0 \leqq a_i \leqq n \right)$ ，使得选手找出最长的区间，满足区间中元素两两不同。为了便于描述，我们称这样的区间为“极大不同区间”。  
$\hspace{15pt}$这看起来太容易了，小龙提出了挑战，对于给定的 $k$ ，能否构造出这样的数组，使得“极大不同区间”的数量恰好为 $k$ ？

## 输入描述:
    
    
    $\hspace{15pt}$在一行上输入两个整数 $n,k \left( 1 \leqq n,k \leqq 2 \times 10^5 \right)$ 代表数组中的元素数量、小龙给出的构造限制。

## 输出描述:
    
    
    $\hspace{15pt}$如果存在这样的数组，在第一行上输出 $\rm YES$ ，随后在第二行上输出 $n$ 个整数，代表构造得到的符合要求的数组。  
    $\hspace{15pt}$否则，直接输出 $\rm NO$ 。

示例1 

## 输入
    
    
    6 3

## 输出
    
    
    YES
    1 1 4 5 1 4

## 说明
    
    
    在这个样例中，构造的数组恰好有 $3$ 个满足条件的区间：$[2,4]$ 、$[3,5]$ 和 $[4,6]$ 。

示例2 

## 输入
    
    
    6 20

## 输出
    
    
    NO


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
# 小苯的区间选数

## 题目描述

小苯有两个区间 $[l_1, r_1]$ 和 $[l_2, r_2]$，他想要在两个区间中各取一个数字求和（结果记为 $sum$），他希望最大化 $sum$ 的数位和。  


（数位和定义为数字的各个数位之和，例如 $123$ 的数位和为 $6$。） 

  


请你帮他算算数位和的最大值吧。 

## 输入描述:
    
    
    每个测试文件内都包含多组测试数据。  
    第一行一个正整数 $T\ (1 \leq T \leq 10000)$，表示测试数据的组数。  
    
    
    接下来对于每组测试数据，输入包含一行四个整数 $l_1, r_1, l_2, r_2\ (1 \leq l_1, l_2, r_1, r_2 \leq 10^{18}, l_1 \leq r_1, l_2 \leq r_2)$

## 输出描述:
    
    
    对于每组测试数据，输出一行一个整数表示最大的数位和。

示例1 

## 输入
    
    
    2
    11 12 13 20
    1 2 99 100

## 输出
    
    
    11
    3

## 说明
    
    
    对于第一组测试数据，第一个区间选择 11，第二个选择 18，求和为 29，数位和为 11 最大。  
    对于第二组测试数据，第一个区间选择 2，第二个选择 100，求和为 102，数位和为 3 最大。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小Z的树迁移

## 题目描述

小Z生活在树上，这一天他计划将他的住所向下迁移。  
现在给出一颗有 $n$ 个结点且以 $1$ 结点为根的树，树上的每一条边都有一个权值。有 $q$ 个询问，每一次询问给出两个数 $u$ 和 $d$，其中 $u$ 表示小Z目前居住的结点，$d$ 表示小Z计划向下移动的次数。小Z希望向下移动的路径上的边的权值和最大，请你输出能得到的最大权值。如果没有合法路径，输出 $-1$。

## 输入描述:
    
    
    第一行包含一个整数 $n(1 \leqq n \leqq 10^5)$，表示树的结点数。  
      
    接下来的 $n-1$ 行，每行包含三个整数 $a, b, w(1 \leqq a, b \leqq n; 1 \leqq w \leqq 10^9)$，表示结点 $a$ 和结点 $b$ 之间有一条权值为 $w$ 的边 。  
      
    接下来一行输入一个整数 $q(1 \leqq q \leqq 10^5)$，表示询问次数。  
      
    接下来的 $q$ 行，每行包含两个整数 $u, d(1 \leqq u \leqq n; 1\leqq d \leqq n)$，表示小Z目前居住的结点和计划向下移动的次数。

## 输出描述:
    
    
    对于每一个询问，输出小Z能够得到的最大权值和。如果没有合法路径，输出 $-1$。

示例1 

## 输入
    
    
    5
    1 2 3
    1 3 5
    2 4 2
    2 5 1
    3
    1 2
    2 1
    3 2

## 输出
    
    
    5
    2
    -1

## 说明
    
    
    第一个查询中，从结点 $1$ 向下移动 $2$ 次，路径为 $1 \to 2 \to 4$，权值和为 $3 + 2 = 5$。  
    第二个查询中，从结点 $2$ 向下移动 $1$ 次，路径为 $2 \to 4$，权值和为 $2$。  
    第三个查询中，从结点 $3$ 向下移动 $2$ 次没有合法路径，输出 $-1$。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小苯吃糖果

## 题目描述

小苯面前有三堆糖果（保证每堆糖果数量不同），他想要一次性吃掉其中的几堆，但有一个限制条件：如果小苯要吃掉数量最多的那堆糖果，则他不能吃其它的糖果。  
  
小苯想知道他最多可以吃多少颗糖果，请你帮他算一算吧。

## 输入描述:
    
    
    输入包含三个正整数 $x, y, z\ (1 \leq x, y, z\leq 10^6) ( x \neq y \neq z)$，表示每堆糖果分别有多少颗糖果。

## 输出描述:
    
    
    输出包含一行一个正整数，表示小苯最多吃掉的糖果数量。

示例1 

## 输入
    
    
    4 3 2

## 输出
    
    
    5

## 说明
    
    
    吃掉 2 和 3。

示例2 

## 输入
    
    
    3 2 1

## 输出
    
    
    3

## 说明
    
    
    可以选择吃掉：3，也可以选择吃掉：1，2。


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld