yl-9/probench huggingface dataset:
# 小苯的排列构造

## 题目描述

小苯有一个正整数 $n$，他希望构造一个长度为 $n$ 的排列 $p$，使得：  
  
$\bullet$ 对于任意正整数 $i$ ，令 $a_i=p_i+p_{p_i}$，他想要 $a$ 数组满足单调不增。即 $a_{i-1} \geq a_{i}\ ( 1 < i \leq n)$。  
  
请你帮他构造一个合法的解吧。

## 输入描述:
    
    
    输入包含 $T+1$ 行。  
    第一行一个正整数 $T\ (1 \leq T \leq 1000)$，表示测试数据组数。  
    接下来 $T$ 行，每行一个正整数 $n \ (1 \leq n \leq 200000)$，表示小苯想构造的排列 $p$ 的长度。  
    数据保证同一个数据中的所有$n$ 的总和不超过 $300000$。

## 输出描述:
    
    
    对于每组测试数据，如果有解，则输出包含一行 $n$ 个正整数，表示构造的排列 $p$。
    
    否则无解输出一行一个 $-1$ 即可。

示例1 

## 输入
    
    
    2
    10
    1

## 输出
    
    
    9 8 10 3 5 1 2 7 6 4
    1


## 时空限制

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

## 题目描述

小苯有一个正整数 $n$，他想让 $n$ 尽可能小，为此他可以做如下的操作任意次：  
$\bullet$ 将 $n$ 的第一个数位放在最后一位。（例如 $n=123$，则操作完后 $n=231$）。  
  
小苯想知道他最小可以将 $n$ 变为多少，请你帮他算一算吧。

## 输入描述:
    
    
    每个测试文件内都包含多组测试数据。  
    第一行一个正整数 $T\ (1 \leq T \leq 100000)$，表示测试数据的组数。  
    
    
    接下来对于每组测试数据，输入包含一行一个正整数$n\ (1 \leq n \leq 10^{10})$。
    
    （特别的，保证 $n$ 的数位中不含 $0$。）

## 输出描述:
    
    
    输出包含 $T$ 行，每行一个整数 $n$，表示小苯进行完操作后 $n$ 的最小值。

示例1 

## 输入
    
    
    4
    24567464
    56876563
    567786432
    1234

## 输出
    
    
    24567464
    35687656
    256778643
    1234


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 小苯的蓄水池（easy）

## 题目描述

小苯有一个大的蓄水场，其中有恰好 $n$ 个蓄水池排成一排，编号分别为 $1$ 到 $n$，其中第 $i$ 个蓄水池中的水量为 $a_i$。  
  
起初每两个相邻蓄水池之间都有一个隔板，而现在小苯希望在蓄水场维护一些操作和查询，具体的：  
$\bullet\ 1\ \ l\ \ r$ 表示将第 $l$ 个水池和第 $r$ 个水池之间所有的挡板拿走。（保证：$1 \leq l < r \leq n$）  
$\bullet\ 2\ \ i$ 表示查询第 $i$ 个水池目前的水量。  


（如果挡板被拿走，则原本挡板两侧水会混合在一起，最终对应的水量会变为平均值，具体可以看样例解释。） 

  


请你帮他回答每次查询吧。 

## 输入描述:
    
    
    输入包含 $m + 2$ 行。  
    第一行输入两个正整数 $1 \leq n, m \leq 2000$，分别表示蓄水场中水池的个数，以及操作的次数。  
    第二行 $n$ 个整数 $a_i\ (1 \leq a_i \leq 10^9)$，表示每个水池初始时的水量。  
    接下来 $m$ 行，每行第一个整数 $\ op  (1 \leq op \leq 2)$ 表示操作。  
    
    
    $\bullet$ 如果 $op = 1$，则表示取掉挡板操作，再输入两个正整数 $l, r\ (1 \leq l < r \leq n)$。
    
    $\bullet$ 如果 $op = 2$，则表示查询操作，再输入一个正整数 $i\ (1 \leq i \leq n)$。
    
    （注意：已经拿走的挡板在以后的操作中都是“被拿走”的状态。）
    
    （数据保证至少有一次查询操作。）

## 输出描述:
    
    
    输出包含若干行，每行一个实数，表示对每个 $op=2$ 的询问做出的回答。
    
    （与正确答案的绝对误差不超过 $10^{-4}$ 则视为正确。）

示例1 

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

## 输出
    
    
    2.3333333333
    2.3333333333
    3.0000000000
    3.0000000000

## 说明
    
    
    打开 1 到 3 号之间所有的挡板，则 1 2 3 号水池中的水会混合，水量为他们的平均值：7/3=2.333...。
    
    再打开 1 到 4 号之间所有的挡板，则 1 2 3 4 号水池中的水都会混合，水量为他们的平均值：12/4 = 3。


## 时空限制

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

## 题目描述

小苯有一个大的蓄水场，其中有恰好 $n$ 个蓄水池排成一排，编号分别为 $1$ 到 $n$，其中第 $i$ 个蓄水池中的水量为 $a_i$。  
  
起初每两个相邻蓄水池之间都有一个隔板，而现在小苯希望在蓄水场维护一些操作和查询，具体的：  
$\bullet\ 1\ \ l\ \ r$ 表示将第 $l$ 个水池和第 $r$ 个水池之间所有的挡板拿走。（保证：$1 \leq l < r \leq n$）  
$\bullet\ 2\ \ i$ 表示查询第 $i$ 个水池目前的水量。  


（如果挡板被拿走，则原本挡板两侧水会混合在一起，最终对应的水量会变为平均值，具体可以看样例解释。）

  


请你帮他回答每次查询吧。 

（注意：因本题输入输出数据量较大，请选手选择快速的输入输出方式。）

## 输入描述:
    
    
    输入包含 $m + 2$ 行。  
    第一行输入两个正整数 $1 \leq n, m \leq 2 \times 10^5$，分别表示蓄水场中水池的个数，以及操作的次数。  
    第二行 $n$ 个整数 $a_i\ (1 \leq a_i \leq 10^9)$，表示每个水池初始时的水量。  
    接下来 $m$ 行，每行第一个整数 $\ op  (1 \leq op \leq 2)$ 表示操作。  
    
    
    $\bullet$ 如果 $op = 1$，则表示取掉挡板操作，再输入两个正整数 $l, r\ (1 \leq l < r \leq n)$。
    
    $\bullet$ 如果 $op = 2$，则表示查询操作，再输入一个正整数 $i\ (1 \leq i \leq n)$。
    
    （注意：已经拿走的挡板在以后的操作中都是“被拿走”的状态。）
    
    （数据保证至少有一次查询操作。）

## 输出描述:
    
    
    输出包含若干行，每行一个实数，表示对每个 $op=2$ 的询问做出的回答。
    
    （与正确答案的绝对误差不超过 $10^{-4}$ 则视为正确。）

示例1 

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

## 输出
    
    
    2.3333333333
    2.3333333333
    3.0000000000
    3.0000000000

## 说明
    
    
    打开 1 到 3 号之间所有的挡板，则 1 2 3 号水池中的水会混合，水量为他们的平均值：7/3=2.333...。
    
    再打开 1 到 4 号之间所有的挡板，则 1 2 3 4 号水池中的水都会混合，水量为他们的平均值：12/4 = 3。


## 时空限制

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

## 题目描述

小苯有一个长度为 $n$ 的字符串 $s$，对于每个位置 $i\ (1 \leq i \leq n)$，他定义 $Move(i)$ 为：把第 $i$ 个字符提到最前面，其余字符按原顺序依次排列接在后面的结果。  
  
例如对于 $s = "abcd", Move(2) = "bacd", Move(4) = "dabc"$。  
  
现在小苯想知道，对于 $i$ 从 $1$ 到 $n$，字典序第 $k$ 小的 $Move(i)$ 串是什么，请你帮他求一求吧。

## 输入描述:
    
    
    每个测试文件内都包含多组测试数据。  
    
    
    第一行一个正整数 $T\ (1 \leq T \leq 100)$，表示测试数据的组数。
    
    接下来对于每组测试数据，输入包含两行。
    
    第一行两个正整数 $n,k\ (1 \leq k \leq n \leq 10^6)$，表示数组 $a$的长度。  
    第二行一个长度为$n$ 的字符串 $s$。（保证 $s$ 只由小写字母构成。）
    
    （保证同一文件的测试数据中，$n$ 的总和不超过 $10^6$。）

## 输出描述:
    
    
    输出包含 $T$ 行，每行一个长度为 $n$ 的字符串，表示当前测试用例的第 $k$ 小字典序 $Move$ 串。

示例1 

## 输入
    
    
    4
    5 2
    cbaca
    8 4
    jsigosfg
    8 5
    nowcoder
    3 1
    aaa

## 输出
    
    
    acbca
    ijsgosfg
    onowcder
    aaa


## 时空限制

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

## 题目描述

小苯定义数字 $x$ 的“数位MEX”为：$x$ 的数位中没有出现的最小非负整数。例如 $1320$ 的“数位MEX”为 $4$，$112$ 的“数位MEX”为 $0$。 

  


小苯有一个正整数 $x$，他需要执行以下操作**恰好一次** ：  
  
$\bullet$ 选择一个不超过 $k$ 的非负整数 $y\ (0 \leq y \leq k)$，执行 $x:=x+y$。（其中 $:=$ 表示赋值。）  
  
小苯想问问你，$x$ 的“数位MEX”最大能达到多少，以及有多少个不同的 $y$ 能使得结果达到这个最大的“数位MEX”。 

## 输入描述:
    
    
    每个测试文件内都包含多组测试数据。  
    第一行一个正整数 $T\ (1 \leq T \leq 300)$，表示测试数据的组数。  
    接下来对于每组测试数据，输入包含一行两个整数$x, k\ (1 \leq x, k\leq 10^9)$。

## 输出描述:
    
    
    输出包含 $T$ 行，对于每组测试数据，输出一行两个整数，分别表示能达到的最大“数位MEX”，以及有多少个不同的 $y$ 取值可以使得结果达到最大“数位MEX”。

示例1 

## 输入
    
    
    3
    1 8
    1 9
    103 10

## 输出
    
    
    0 9
    2 1
    2 8

## 说明
    
    
    对于第一组测试数据，所有个位数的“数位MEX”都为 0，因此有 9 个 y 可以使得结果取到最大“数位MEX”。  
    对于第二组测试数据，仅有数字10的“数位MEX”为 2，其余都是 0，因此只有 1 个 y 可以使结果取到最大“数位MEX”。  
    对于第三组测试数据，103,104,105,106,107,108,109,110 的“数位MEX”都是 2，一共有 8 个 y 可以使结果取到最大“数位MEX”。


## 时空限制

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

## 题目描述

小红准备去超市买水果。已知苹果$a$元一斤，桃子$b$元一斤。  
小红一共带了$n$元钱，她想知道自己最多可以买多少斤水果？  
我们认为，同一种水果买的斤数必须是整数。

## 输入描述:
    
    
    三个整数$n,a,b$，用空格隔开。  
    $1\leq n,a,b \leq 100$

## 输出描述:
    
    
    一个整数，代表小红买的水果重量之和的最大值。

示例1 

## 输入
    
    
    8 4 3

## 输出
    
    
    2

## 说明
    
    
    小红买1斤桃子和1斤苹果，共花费7元，总共买了2斤水果。  
    该方案不唯一，但可以证明2斤为小红购买水果重量的最大值。  
    


## 时空限制

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

Difficulty: 300
# 雨幕

## 题目描述

今年的雨水格外的多，喜欢下雨的小红自然也很开心。  
  
给定一个$n$行$m$列的地图，用字符表示降雨情况，'.'代表未降雨，'*'代表降雨。请你帮小红求出有多少个2*2的区域满足该区域内全部都在降雨？

## 输入描述:
    
    
    第一行输入两个正整数$n,m$，代表地图的行数和列数。  
    接下来的$n$行，每行输入一个仅包含'.'和'*'的字符串，用来表示地图的降雨情况。  
    $1\leq n,m \leq 1000$

## 输出描述:
    
    
    一个正整数，代表2*2的区域都在降雨的区域数量。

示例1 

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

## 输出
    
    
    1


## 时空限制

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

Difficulty: 400
# 闺蜜

## 题目描述

小红和小紫是好闺蜜，作为闺蜜当然要“友好”的一起玩游戏。  
  
她们拿到了一个长度为偶数的数组，两人轮流进行取数，谁最终总和最大谁就获胜。小红先手取数。  
  
但这个比赛显然对小紫是不公平的，因此小红允许小紫使用一次技能“隙间”，小紫在游戏的任何时期，可以将自己手中的一个元素和小红手中的一个元素进行交换（该技能最多释放1次）。请你判断两人都是用最优策略的情况下，谁将取得最终的胜利？

## 输入描述:
    
    
    第一行输入一个正整数$t$，代表询问次数。  
    对于每组询问，第一行输入一个正整数$n$，代表数组大小；第二行输入$n$个正整数$a_i(1 \leq a_i \leq 10^9)$，代表数组的元素。  
    保证所有的$n$的总和不超过1000，且每个$n$都是偶数。

## 输出描述:
    
    
    对于每组询问，输出一行字符串代表答案。  
    如果小红获胜，请输出"kou"，如果小紫获胜，请输出"yukari"；如果平局（两人总和相同），请输出"draw"。

示例1 

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

## 输出
    
    
    yukari
    draw
    yukari

## 说明
    
    
    第一组询问，如果小红先拿了1，则小紫拿2，不发动技能，小紫获胜；如果小红先拿了2，则小紫拿1，然后发动技能，依然是小紫获胜。  
    第二组询问，显然最终是平局。  
    


## 时空限制

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

Difficulty: 700
# 医生

## 题目描述

小红是一名医生。  
  
现在小红对于每个病人的症状用一个长度为$m$的01串表示，第$i$个字符代表第$i$个身体部位的症状，0代表健康，1代表不健康。  
一共有$k$种药，每种药也用一个长度为$m$的01串表示，第$i$个字符为'1'代表该药可以治愈第$i$个部位的症状。  
对于每个病人，请你帮小红求出治愈该病人需要开的最少的药数量。

## 输入描述:
    
    
    第一行输入两个正整数$n,m$，代表病人数量和症状种类数。  
    接下来的$n$行，每行输入一个长度为$m$的01串，代表每个病人的症状情况。  
    接下来一行输入一个正整数$k$，代表药物的数量。  
    接下来的$k$行，每行输入一个长度为$m$的01串，代表每个药物可以治愈的症状情况。  
    $1\leq m \leq 20$  
    $1\leq n \leq 10^4$  
    $1\leq k \leq 10$

## 输出描述:
    
    
    输出$n$行，每行输出治愈该病人所需的最小药物数量。特殊的，如果该病人无法被治愈，请输出-1。

示例1 

## 输入
    
    
    3 4
    1000
    0101
    1011
    2
    1001
    0011

## 输出
    
    
    1
    -1
    2

## 说明
    
    
    第一个病人开第一种药即可。  
    第二个病人显然是无法治愈的。  
    第三个病人需要同时开第一种和第二种药。  
    


## 时空限制

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

Difficulty: 1300
# 降温（easy）

## 题目描述

天气开始降温了。  
  
如果某一天的温度比前一天降低的值不小于$x$，小红就会认为这是一场“寒潮”。  
现在给定了每天的气温，但有一些日子的气温是未知的。小红想知道，发生寒潮的次数的最大值和最小值是多少？  
注：我们认为，每天气温的值域一定在[-50,50]。

## 输入描述:
    
    
    第一行输入两个正整数$n,x$，代表总天数、以及寒潮的判定标准。  
    第二行输入$n$个整数$a_i$，代表每天的气温。特殊的，如果$a_i$为-999，代表这一天的气温是未知的。  
      
    $1\leq n,x \leq 100$  
    $-50 \leq a_i \leq 50$或者$a_i=-999$

## 输出描述:
    
    
    两个整数，代表寒潮数量的最大值和最小值。

示例1 

## 输入
    
    
    3 10
    50 -999 -50

## 输出
    
    
    2 1

## 说明
    
    
    第二天的气温未知，若这一天的气温在[41,50]或者[-50,-41]，则共有1天寒潮；否则是两天寒潮。

示例2 

## 输入
    
    
    4 100
    -999 -999 -999 -999

## 输出
    
    
    2 0

## 说明
    
    
    当且仅当四天的气温为50,-50,50,-50时才会有2天寒潮。


## 时空限制

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

Difficulty: 1400
# 降温（hard）

## 题目描述

（本题和easy版题意相同，仅数据范围不同。判定未知的气温也有不同，请勿直接复制本题代码交到easy版！）  
  
天气开始降温了。  
  
如果某一天的温度比前一天降低的值不小于$x$，小红就会认为这是一场“寒潮”。  
现在给定了每天的气温，但有一些日子的气温是未知的。小红想知道，发生寒潮的次数的最大值和最小值是多少？  
注：我们认为，每天气温的值域一定在$[-5*10^8,5*10^8]$。

## 输入描述:
    
    
    第一行输入两个正整数$n,x$，代表总天数、以及寒潮的判定标准。  
    第二行输入$n$个整数$a_i$，代表每天的气温。特殊的，如果$a_i$为-999999999，代表这一天的气温是未知的。  
    $1\leq n,x \leq 10^5$  
    $-5*10^8 \leq a_i \leq 5*10^8$或者$a_i=-999999999$。

## 输出描述:
    
    
    两个整数，代表寒潮数量的最大值和最小值。  
    
    
      
    

示例1 

## 输入
    
    
    3 10
    50 -999999999 -50

## 输出
    
    
    2 1

## 说明
    
    
    第二天的气温未知，若这一天的气温在[41,50]或者[-50,-41]，则共有1天寒潮；否则是两天寒潮。

示例2 

## 输入
    
    
    4 100
    -999999999 -999999999 -999999999 -999999999

## 输出
    
    
    3 0

## 说明
    
    
      
    


## 时空限制

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

Difficulty: 1500
# 乌鸦

## 题目描述

小红有$n$个笼子，她准备往里面放置共$m$只乌鸦。小红希望相邻笼子的乌鸦数量正好相差1，请你给出一个放置方案。

## 输入描述:
    
    
    两个正整数$n,m$，用空格隔开。  
    $1\leq n \leq 10^5$  
    $1\leq m \leq 10^{18}$

## 输出描述:
    
    
    如果无解，请输出-1。  
    否则输出一行$n$个整数，代表每个笼子里的乌鸦数量。有多解时输出任意合法解即可。

示例1 

## 输入
    
    
    4 3

## 输出
    
    
    -1

示例2 

## 输入
    
    
    3 3

## 输出
    
    
    2 1 0

示例3 

## 输入
    
    
    3 4

## 输出
    
    
    1 2 1


## 时空限制

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

Difficulty: 1900
# 小红的对错判断

## 题目描述

小红在判题的时候，经常发现选手把"Yes"输出成"YES"或者"yes"，她希望写一个spj（special judge）来判断选手是否输出了"Yes"。你能帮帮她吗？

## 输入描述:
    
    
    一个长度不超过3的、仅由小写字母或者大写字母组成。

## 输出描述:
    
    
    若字符串可以通过大小写转换变成"Yes"，则输出"accept"。否则输出"wrong answer"。

示例1 

## 输入
    
    
    yEs

## 输出
    
    
    accept

示例2 

## 输入
    
    
    No

## 输出
    
    
    wrong answer


## 时空限制

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

Difficulty: 300
# 小红的幂表达

## 题目描述

小红拿到了一个正整数，请你帮小红将其表示为幂（$a^b$）的形式。

## 输入描述:
    
    
    一个正整数$x$  
    $2\leq x \leq 10^5$

## 输出描述:
    
    
    第一行输出$x$。  
    接下来每一行输出一个幂的表达式。  
    请按指数从小到大的顺序输出。

示例1 

## 输入
    
    
    16

## 输出
    
    
    16
    =16^1
    =4^2
    =2^4


## 时空限制

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

Difficulty: 700
# 小红的前缀询问

## 题目描述

小红拿到了一个数组，她有若干次询问，每次询问一个前缀内有多少对相同的数。你能帮帮她吗？ 

  


如果存在$i,j$，$1\leq i < j \leq n$，且$a_i=a_j$，那么 $(a_i, a_j)$ 就是一对相同的数对。只要下标不同，就是不同的数对。  


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

## 输出描述:
    
    
    输出$n$个整数，第$i$个整数代表前缀$[1,i]$内有多少对相同的数。

示例1 

## 输入
    
    
    6
    2 3 3 3 1 2

## 输出
    
    
    0 0 1 3 3 4

## 说明
    
    
    对于前缀 [2]，没有相同的数。  
    对于前缀 [2,3]，没有相同的数。  
    对于前缀 [2,3,3]，有1对相同的数。  
    对于前缀 [2,3,3,3]，有3对相同的数。  
    对于前缀 [2,3,3,3,1]，有3对相同的数。  
    对于前缀 [2,3,3,3,1,2]，有4对相同的数。  
    


## 时空限制

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

Difficulty: 800
# 小红和小紫的博弈游戏

## 题目描述

小红和小紫拿到了一个$2*2$的矩阵，她们准备在这个矩阵上玩一个博弈游戏。  
游戏的规则是：两人轮流操作，每次操作时选择两个相邻的正整数，使它们同时减1。谁先无法操作谁就输了。  
  
小红先手操作，她想知道，两人都使用最优策略的情况下，谁将获得最终胜利？

## 输入描述:
    
    
    第一行输入一个正整数$t$，代表询问次数。  
    接下来的$2*t$行，每两行分别输入两个整数$a_{ij}$，代表一次询问的初始矩阵。  
    $1\leq t \leq 10^4$  
    $0\leq a_{ij}\leq 10^9$

## 输出描述:
    
    
    如果小红获胜，则输出"kou"。否则输出"yukari"。

示例1 

## 输入
    
    
    2
    0 0
    0 1
    1 0
    1 0

## 输出
    
    
    yukari
    kou

## 说明
    
    
    第一组询问，小红无法操作，因此小紫获胜。  
    第二组询问，小红只需要将第一列的两个数同时减1即可获胜。  
    


## 时空限制

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

Difficulty: 1200
# 小红的字符串重排

## 题目描述

小红拿到了一个仅由小写字母组成的字符串，她希望你能重排这个字符串，使得每个对应位置的字符和重排前都不相同。你能帮帮她吗？

## 输入描述:
    
    
    一个仅由小写字母组成的字符串。长度不超过$10^5$。

## 输出描述:
    
    
    如果无解，请输出-1。  
    否则输出任意合法字符串。  
    

示例1 

## 输入
    
    
    aba

## 输出
    
    
    -1

示例2 

## 输入
    
    
    abbc

## 输出
    
    
    bcab

## 说明
    
    
    输出bacb也是可以的。


## 时空限制

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

Difficulty: 1700
# 小红的树上路径查询（easy）

## 题目描述

本题和$hard$难度的区别是，询问的次数仅有1次！  
  
小红拿到了一棵树，她有一次询问，给定一条简单路径$x,y$，她想知道树上所有节点到该路径的最短路之和是多少，你能帮帮她吗？  


定义节点到路径的最短路为：节点到路径上所有点的最短路中，值最小的那个。特殊的，如果节点在路径上，则最短路为0。 

简单路径：从树上的一个节点出发，沿着树的边走，不重复地经过树上的节点，到达另一个节点的路径。  


## 输入描述:
    
    
    第一行输入两个正整数$n,q$，代表节点数量和询问次数。  
    接下来的$n-1$行，每行输入两个正整数$u,v$，代表节点$u$和节点$v$有一条边连接。  
    接下来的$q$行，每行输入两个正整数$x,y$，代表一次询问。  
    $1\leq n \leq 10^5$  
    $q=1$  
    $1\leq u,v,x,y \leq n$

## 输出描述:
    
    
    输出$q$行，每行输出一个整数，代表询问的答案。

示例1 

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

## 输出
    
    
    1

## 说明
    
    
    仅有节点4到路径的距离为1，其余节点均在路径上，因此距离为0。


## 时空限制

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

Difficulty: 1500
# 小红的树上路径查询（hard）

## 题目描述

本题和$hard$难度的区别是，询问的次数有多次！  
  
小红拿到了一棵树，她有多次询问，每次询问输入一条简单路径$x,y$，她想知道树上所有节点到该路径的最短路之和是多少，你能帮帮她吗？  


定义节点到路径的最短路为：节点到路径上所有点的最短路中，值最小的那个。特殊的，如果节点在路径上，则最短路为0。 

简单路径：从树上的一个节点出发，沿着树的边走，不重复地经过树上的节点，到达另一个节点的路径。  


## 输入描述:
    
    
    第一行输入两个正整数$n,q$，代表节点数量和询问次数。  
    接下来的$n-1$行，每行输入两个正整数$u,v$，代表节点$u$和节点$v$有一条边连接。  
    接下来的$q$行，每行输入两个正整数$x,y$，代表一次询问。  
    $1\leq n,q \leq 10^5$  
    $1\leq u,v,x,y \leq n$

## 输出描述:
    
    
    输出$q$行，每行输出一个整数，代表询问的答案。

示例1 

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

## 输出
    
    
    1
    2


## 时空限制

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

Difficulty: 2000
# 小红的好数

## 题目描述

小红定义一个正整数是“好数”，当且仅当该数满足以下两个性质：  
1\. 数位恰好为2。  


2\. 个位数和十位数相同。 

请你判断一个给定的正整数是否是好数？  


## 输入描述:
    
    
    一个正整数$x$。  
    $1 \leq x \leq 10^9$

## 输出描述:
    
    
    若$x$是好数，请输出"Yes"。否则输出"No"。

示例1 

## 输入
    
    
    33

## 输出
    
    
    Yes

示例2 

## 输入
    
    
    144

## 输出
    
    
    No


## 时空限制

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

Tags: 字符串, 模拟
Difficulty: 300
# 小红的好数组

## 题目描述

小红定义一个数组是“好数组”，当且仅当该数组满足以下两个性质：  
1\. 该数组不是回文数组。  
2\. 修改恰好一个元素后，该数组变成回文数组。  
所谓回文数组，即将一个数组左右翻转后，和原数组相同，例如[12,3,12]是回文数组。  
  
现在小红拿到了一个数组，请你帮小红计算有多少个长度为$k$的连续子数组是好数组。

## 输入描述:
    
    
    第一行输入两个正整数$n,k$，代表数组大小、以及询问的连续子数组长度。  
    第二行输入$n$个正整数$a_i$，代表小红拿到的数组。  
    $1 \leq k \leq n \leq 1000$  
    $1 \leq a_i \leq 10^9$

## 输出描述:
    
    
    一个整数，代表长度为$k$的连续子数组是好数组的数量。

示例1 

## 输入
    
    
    5 3
    1 2 3 2 1

## 输出
    
    
    2

## 说明
    
    
    [1,2,3]和[3,2,1]是好数组。


## 时空限制

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

Tags: 暴力
Difficulty: 600
# 小红的矩阵行走

## 题目描述

小红因为太喜欢出“矩阵行走”的题，被小紫关进矩阵里了，她希望你来救救她！  
  
现在给定了一个矩阵，小红初始站在矩阵的左上角。已知小红每次可以向右或者向下走一步，当小红经过一个格子时，她将收集该格子的正整数。小红希望到达右下角时，收集到的所有正整数都相同。你能帮帮她吗？

## 输入描述:
    
    
    第一行输入一个正整数$t$，代表询问的次数。  
    对于每次询问，第一行输入两个正整数$n,m$，代表矩阵的行数和列数。  
    接下来的$n$行，每行输入$m$个正整数$a_{ij}$，代表矩阵每个格子的数字。  
    $1 \leq t \leq 100$  
    $1 \leq n,m \leq 100$  
    $1 \leq a_{ij} \leq 10^9$

## 输出描述:
    
    
    输出$t$行，每行输出一个字符串代表询问的答案。  
    如果小红可以到达右下角，则输出"Yes"。否则输出"No"。

示例1 

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

## 输出
    
    
    Yes
    No


## 时空限制

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

Tags: 搜索
Difficulty: 800
# 小红的行列式构造

## 题目描述

小红希望你构造一个3阶行列式，满足每个元素的绝对值不小于1，且行列式的值等于$x$。你能帮帮她吗？ 

## 输入描述:
    
    
    一个整数$x$  
    $-100\leq x \leq 100$

## 输出描述:
    
    
    输出三行，每行三个整数$a_{ij}$，用于表示构造的行列式。  
    请保证$-10^9 \leq a_{ij} \leq 10^9$，且$a_{ij}$不等于0。

示例1 

## 输入
    
    
    0

## 输出
    
    
    1 1 1
    1 1 1
    1 1 1


## 时空限制

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

Tags: 线性代数, 构造
Difficulty: 900
# 小红的 red 计数

## 题目描述

小红拿到了一个字符串。她有若干次询问，每次询问：若翻转第$l$个字符到第$r$个字符对应的区间，该字符串有多少"red"子序列。  
子序列指按原串顺序取若干字母（可以不连续）形成的新字符串。如"rreedd"存在8个"red"子序列。  
请注意，每次询问后并不会真正翻转区间！

## 输入描述:
    
    
    第一行输入两个正整数$n,q$，代表字符串长度和询问次数。  
    第二行输入一个长度为$n$的、仅由小写字母组成的字符串。  
    接下来的$q$行，每行输入两个正整数$l,r$，代表一次询问。  
      
    $1\leq n,q \leq 10^5$  
    $1\leq l \leq r \leq n$

## 输出描述:
    
    
    输出$q$行，每行输出一个整数，代表询问的答案。

示例1 

## 输入
    
    
    6 2
    rreedd
    1 2
    1 6

## 输出
    
    
    8
    0


## 时空限制

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

Tags: 组合数学, 数据结构, 线段树, STL, 枚举, 前缀和, 暴力
Difficulty: 1800
# 小红开灯

## 题目描述

平面直角坐标系上有$n$盏灯。  
小红每次操作可以选择一盏灯，改变和它同一行以及同一列所有的灯（包括它自己）的开关状态。  
用数学语言描述，若选择了坐标在$(x,y)$的灯，那么所有横坐标为$x$或者纵坐标为$y$的灯都将改变开关状态。  
  
小红想知道能否经过有限次操作，最终所有灯都变成开的状态？

## 输入描述:
    
    
    第一行输入一个正整数$n$，代表灯的数量。  
    第二行输入一个长度为$n$的01串，代表每个灯初始的开关状态。1代表开，0代表关。  
    接下来的$n$行，每一行输入两个整数$x,y$，代表每个灯所在的坐标。  
    $1\leq n \leq 100$  
    $-10^9 \leq x,y \leq 10^9$  
    保证任意两盏灯的坐标是不同的。

## 输出描述:
    
    
    如果无解，请输出-1。  
    否则输出一个任意合法的操作方案：  
    第一行输出一个整数$k$，代表操作次数。  
    第二行输出$k$个正整数$a_i$，代表每次操作选择的是第几盏灯。  
    请保证$0 \leq k \leq n$，可以证明，如果存在解，那么一定存在一组不超过$n$次操作的合法方案。  
    你不需要最小化操作次数。

示例1 

## 输入
    
    
    3
    011
    1 1
    0 1
    1 0

## 输出
    
    
    3
    1 2 3

## 说明
    
    
    对三盏灯分别各操作一次即可。

示例2 

## 输入
    
    
    3
    011
    0 0
    0 1
    0 -1

## 输出
    
    
    -1


## 时空限制

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

Tags: 线性代数, 线性基, 数论, 思维
Difficulty: 2000
# 小红的字符移动

## 题目描述

小红拿到了一个长度为5的、仅由小写字母组成的字符串，她希望你将第二个字符移动到字符串的最前面，其余字符顺序保持不变。你能帮帮她吗？

## 输入描述:
    
    
    一个长度为$5$的、仅由小写字母组成的字符串。

## 输出描述:
    
    
    移动后的字符串。

示例1 

## 输入
    
    
    abcde

## 输出
    
    
    bacde


## 时空限制

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

Tags: 模拟
Difficulty: 300
# 小红的数轴移动

## 题目描述

小红站在数轴的$x$点上，她准备按顺序进行$n$次操作，每次操作如下：  
1\. 若小红站在原点，则原地不动。  
2\. 否则按朝原点的方向，移动$a_i$距离。  
  
小红希望你求出她移动的总距离。你能帮帮她吗？

## 输入描述:
    
    
    第一行输入两个整数$n,x$，用空格隔开。分别代表小红的操作数量、小红的初始位置。  
    第二行输入$n$个正整数$a_i$，代表小红每次操作移动的距离（若移动）。  
    $1\leq n \leq 10^5$  
    $-10^9 \leq x \leq 10^9$  
    $1\leq a_i \leq 10^9$

## 输出描述:
    
    
    一个整数，代表小红移动的总距离。

示例1 

## 输入
    
    
    5 1
    5 4 3 2 1

## 输出
    
    
    9

## 说明
    
    
    小红初始站在坐标1处，她首先向左移动5距离，此时在坐标-4处；然后向右移动4距离，来到原点，接下来的三次操作均原地不动。


## 时空限制

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

Tags: 暴力
Difficulty: 400
# 小红的圆移动

## 题目描述

平面上有$n$个圆，小红可以进行任意次操作，每次操作可以选择一个圆，将它向任意方向移动若干距离。该操作的代价为该圆面积乘以移动的距离。  
小红希望最终包含原点的圆数量不超过$k$，请你帮小红算出她操作的最小总代价。

## 输入描述:
    
    
    第一行输入两个正整数$n,k$，用空格隔开。  
    接下来的$n$行，每行输入三个整数$x,y,r$，代表第$i$个圆的圆心是$(x,y)$，半径是$r$。  
    $1 \leq k \leq n \leq 10^5$  
    $-10^6 \leq x,y \leq 10^6$  
    $1 \leq r \leq 10^6$

## 输出描述:
    
    
    一个实数，代表操作的最小总代价。若你的输出和标准答案的相对误差不超过$10^{-6}$，则认为你的答案正确。

示例1 

## 输入
    
    
    2 1
    0 0 1
    0 0 2

## 输出
    
    
    3.14159265358979324

## 说明
    
    
    显然将小圆向任意方向移动距离1即可。


## 时空限制

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

Tags: 计算几何, 贪心
Difficulty: 800
# 小红的树上移动

## 题目描述

小红拿到了一棵树，初始所有节点均为白色。小红初始站在1号节点，并将1号节点染红。小红将不断进行移动直到停止：  
1\. 若当前节点的邻点中存在白色节点，则小红随机移动到某个相邻的白色节点，并将该节点染红。  
2\. 若当前节点的邻点中不存在白色节点，则停止移动。  
  
请你帮小红求出最终红点数量的期望。

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

## 输出描述:
    
    
    一个正数，代表最终的期望对$10^9+7$取模的答案。  
    可以证明，最终的期望一定是一个有理数。分数$x/y$对$p$取模的定义为：需要找到一个正整数$a∈[0,p-1]$满足$a*y\ mod\ p=x$

示例1 

## 输入
    
    
    2
    1 2

## 输出
    
    
    2

## 说明
    
    
    显然两个点都会被染红。

示例2 

## 输入
    
    
    4
    1 2
    1 3
    2 4

## 输出
    
    
    500000006

## 说明
    
    
    最终的答案是2.5（即5/2），由于500000006*2对1000000007取模的答案是5，因此输出500000006。


## 时空限制

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

Tags: 数学, 概率期望, 动态规划, 树形dp
Difficulty: 1200
# 小红的中位数查询（easy）

## 题目描述

**easy 版本中，所有的** $r - l + 1$**都相等，而 hard 版本中没有此限制。通过 easy 版本可以获得 250 分，通过 hard 版本可以获得 50 分。**  


  


小红拿到了一个数组，她有若干次询问，每次询问一个区间，她希望你输出该区间的中位数是多少。 

  
保证区间的元素数量为奇数。  
  
在本难度中，保证所有区间的长度都相等。  
  
区间中位数的定义：将区间所有元素从小到大排序后、最中间的那个数。例如[2,1,4]的中位数是2，[2,1,4,3,3]的中位数是3。

## 输入描述:
    
    
    第一行输入两个正整数$n,q$，代表数组大小、询问次数。  
    第二行输入$n$个正整数$a_i$，代表小红拿到的数组。  
    接下来的$q$行，每行输入两个正整数$l_i,r_i$，代表一次询问。  
    $1\leq n,q \leq 10^5$  
    $1\leq a_i \leq 10^9$  
    $1\leq l_i \leq r_i \leq n$  
    保证所有的$r_i-l_i+1$为奇数，且都相等。

## 输出描述:
    
    
    输出$q$行，每行输出一个正整数，代表询问的结果。

示例1 

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

## 输出
    
    
    2
    3


## 时空限制

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

Tags: 数据结构, 线段树, 分块, 主席树
Difficulty: 1300
# 小红的中位数查询（hard）

## 题目描述

**easy 版本中，所有的** $r - l + 1$**都相等，而 hard 版本中没有此限制。通过 easy 版本可以获得250 分，通过 hard 版本可以获得 50 分。**  


  


小红拿到了一个数组，她有若干次询问，每次询问一个区间，她希望你输出该区间的中位数是多少。 

  
保证区间的元素数量为奇数。  
  
区间中位数的定义：将区间所有元素从小到大排序后、最中间的那个数。例如[2,1,4]的中位数是2，[2,1,4,3,3]的中位数是3。

## 输入描述:
    
    
    第一行输入两个正整数$n,q$，代表数组大小、询问次数。  
    第二行输入$n$个正整数$a_i$，代表小红拿到的数组。  
    接下来的$q$行，每行输入两个正整数$l_i,r_i$，代表一次询问。  
    $1\leq n,q \leq 10^5$  
    $1\leq a_i \leq 10^9$  
    $1\leq l_i \leq r_i \leq n$  
    保证所有的$r_i-l_i+1$为奇数。

## 输出描述:
    
    
    输出$q$行，每行输出一个正整数，代表询问的结果。

示例1 

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

## 输出
    
    
    3
    3


## 时空限制

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

Tags: 数据结构, 线段树, 分块, 主席树
Difficulty: 1400
# 小红的数轴移动（二）

## 题目描述

小红站在数轴的$x$点上，她准备进行$n$次操作，每次操作如下：  
1\. 若小红站在原点，则原地不动。  
2\. 否则按朝原点的方向，移动$a_i$距离。  
  
小红可以自己选择操作的先后次序。她希望给出一个方案，使得最终移动的总距离最小，你能帮帮她吗？

## 输入描述:
    
    
    第一行输入两个整数$n,x$，用空格隔开。分别代表小红的操作数量、小红的初始位置。  
    第二行输入$n$个正整数$a_i$，代表小红每次操作移动的距离（若移动）。  
    $1\leq n \leq 100$  
    $-100 \leq x \leq 100$  
    $1\leq a_i \leq 100$

## 输出描述:
    
    
    第一行输出一个整数，代表小红移动的最小总距离。  
    第二行输入$n$个正整数$p_i$，代表第$i$次准备移动的距离为$a_{p_i}$。请保证输出的$p$数组为一个长度为$n$的排列。有多解时输出任意即可。保证有解。

示例1 

## 输入
    
    
    5 1
    5 4 3 2 1

## 输出
    
    
    1
    5 1 2 3 4

## 说明
    
    
    小红第一步进行操作5，想左移动1距离来到原点，后面四次操作均不移动。  
    因此输出的排列只需要保证第一个元素为5即可。  
    


## 时空限制

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

Difficulty: 2000