yl-9/probench huggingface dataset:
# 颜色与方格

## 题目描述

小灰灰有 $n\times n$ 只五颜六色的袜子，放在了一个 $n$ 行 $n$ 列方格盒里。  
  
其中第 $i$ 行第 $j$ 列的袜子颜色为 $c_{i,j}$。  
  
小灰灰眼力有限，只会在一个 $K\times K$ 的范围中查找一双颜色相同的袜子去上课。  
  
小蓝很好奇小灰灰如此邋遢是否能找到合适的袜子，于是她向小灰灰提出了 $m$ 个问题。  
  
第 $i$ 个问题中，小蓝会给出两个整数 $x_i,y_i$，小灰灰需要回答，在以第 $x_i$ 行第 $y_i$ 列格子为左上角，占据 $K$ 行 $K$ 列的子矩阵中，有多少种颜色可以选出至少一双袜子。

## 输入描述:
    
    
    第一行包含三个空格分隔的整数 $n, m$ 和 $K$。  
      
    接下来输入 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 列的数表示 $c_{i, j}$。  
      
    接下来 $m$ 行，第 $i$ 行包含两个空格分隔的整数，分别代表 $x_i$ 和 $y_i$。  
      
    保证：  
    $1 \le K \le n \le 700, 1 \le m \le (n - K + 1)^2$  
    $1 \le x_i, y_i \le n - K + 1$  
    $1 \le c_{i, j} \le 10^6$

## 输出描述:
    
    
    输出共 $m$ 行，第 $i$ 行代表第 $i$ 次询问的答案。

示例1 

## 输入
    
    
    5 4 3
    1 1 2 3 4
    9 8 3 2 1
    3 2 4 1 2
    4 9 8 5 4
    7 7 6 6 4
    1 1
    3 3
    3 2
    2 2

## 输出
    
    
    3
    2
    1
    2


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 颜色与幸运数字

## 题目描述

有一天小灰灰和小蓝在河边散步，河边从上游到下游分布着 $n$ 颗小石子，其中第 $i$ 颗小石子的颜色为 $c_i$。  
  
小蓝和小灰灰分享了她的幸运数字 $k$，但是小灰灰总是粗心大意的忘记这个数字。  
  
所以她打算用 $m$ 个问题来考验小灰灰，她的第 $i$ 个问题是河边的第 $l_i$ 到第 $r_i$ 颗石子中，有哪些颜色的石子出现了恰好 $k$ 次，由于这样的石子可能太多了，所以小灰灰将会回答这些颜色种类数字的和作为答案。  
  
现在请你编写一个程序来计算出小灰灰每次回答的答案是多少。

## 输入描述:
    
    
    第一行输入三个空格分隔的整数 $n, m$ 和 $k$。  
      
    接下来一行 $n$ 个空格分隔的整数，第 $i$ 个数代表 $c_i$。  
      
    接下来 $m$ 行，第 i 行输入两个整数代表 $l_i$ 和 $r_i$。  
      
    保证：  
    $1\le n, m, c_i \le 10^6, 1 \le k \le n$  
    $1 \le l_i \le r_i \le n$

## 输出描述:
    
    
    输出共 $m$ 行，第 $i$ 行代表第 $i$ 个询问的答案。

示例1 

## 输入
    
    
    9 4 2
    2 2 1 4 1 4 2 5 1
    1 9
    2 8
    3 7
    5 9

## 输出
    
    
    4
    7
    5
    1


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 文本编辑器2

## 题目描述

今天又是无聊的一天，小灰灰打算在文本编辑器中写一些数字，具体来说小灰灰会连续进行 $q$ 次操作，每次操作为以下四种情况之一：  
  
\- 添加一个数字字符 $x$ 到当前光标位置，并将光标移动到这个数字后方  
\- 删去光标前方的一个数字（此操作保证光标前方存在至少一个数字）  
\- 将光标移动到前一个数字后方（此操作保证光标前方存在至少一个数字）  
\- 将光标移动到后一个数字后方（此操作保证光标后方存在至少一个数字）  
  
小蓝觉得小灰灰闲的令人发指，所以她打算来刁难小灰灰，她将会提出 $m$ 个问题，第 $i$ 个问题小灰灰需要告诉她从当前文本中第 $pos_i$ 个数字字符开始连续的 $len_i$ 个数字字符组成的大数是多少，由于这个数可能特别长，所以你只需要输出其模 998244353 之后的结果即可。  
  
注意小蓝也非常无聊，所以她会看着小灰灰操作，并时不时的提问，这意味着操作和询问是交替进行的。

## 输入描述:
    
    
    第一行输入两个空格分隔的整数，分别代表 $q$ 和 $m$。  
      
    接下来 $q + m$ 行，第 $i$ 行的输入为以下五种情况之一：  
    
    
    - 输入 `Q pos len` 代表一次询问
    
    - 输入 `I x` 代表执行一次操作一  
    - 输入 `D` 代表执行一次操作二  
    - 输入 `F` 代表执行一次操作三  
    - 输入 `B` 代表执行一次操作四  
      
    保证：  
    $1\le q \le 10^6$   
    $1\le m \le 2\times 10^5$   
    
    
    $0 \le x \le 9$

## 输出描述:
    
    
    对于每次询问操作，输出一行一个整数代表答案。

示例1 

## 输入
    
    
    7 3
    I 5
    F
    I 9
    Q 1 2
    I 0
    Q 2 1
    B
    I 0
    D
    Q 1 3

## 输出
    
    
    95
    0
    905

## 说明
    
    
    整数序列和光标的变化如下：
    
    5|  
    |5  
    9|5  
    Q 1 2  
    90|5  
    Q 2 1  
    905|  
    9050|  
    905|  
    Q 1 3


## 时空限制

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

## 题目描述

作为一个写程序的，小灰灰时常需要管理他的电脑资源。  
  
具体来说，小灰灰面前有 $n$ 种资源，其中第 $i$ 种资源有 $a_i$ 份。  
  
作为一个写文章的，小蓝并不在意这些资源，她只会不断地提出新的请求。  
  
具体来说，小蓝共有 $m$ 个请求，其中第 $i$ 个请求是申请使用第 $l_i$ 和第 $r_i$ 之间的所有电脑资源，每种资源都需要 $c_i$ 份。  
  
由于小蓝不会规划她的申请，所以她的申请可能并不合理，这样就会导致有时候电脑资源不足，从而无法响应小蓝的请求。  
  
比如：  
  
\- 总共有 $5$ 种资源，它们的数量分别是 $5, 3, 9, 6, 3$  
\- 小蓝提出的第 $1$ 个请求是申请第 $2$ 到第 $5$ 种电脑资源各 $2$ 份  
\- 电脑响应了这个请求，此时它剩余的资源是 $5, 1, 7, 4, 1$  
\- 小蓝提出的第 $2$ 个请求是申请第 $1$ 到第 $5$ 种电脑资源各 $5$ 份  
\- 此时电脑就会拒绝响应这个请求并且直接卡死，因为剩余资源不足以完成小蓝的申请  
  
小灰灰发现了这个悲剧，他能够很快的计算出小蓝在第几次申请时会被卡死。然而，小蓝为了避免卡死，她打算买一个新的电脑配件，帮助她**增加** 自己的电脑资源……  
  
小蓝有 $q$ 种想买的电脑配件，第 $i$ 种配件可以使得第 $ql_i$ 和第 $qr_i$ 之间的所有电脑资源增加 $x_i$ 份。  
  
为了帮助小蓝挑选到最合适的电脑配件，小灰灰计划对每一种电脑配件都计算出，如果选择这个电脑配件，小蓝在进行第几次申请时会发生卡死现象。

## 输入描述:
    
    
    第一行输入三个空格分隔的整数，分别代表 $n, m$ 和 $q$。  
      
    接下来一行 $n$ 各空格分隔的整数，分别代表 $a_1$ 到 $a_n$。  
      
    接下来 $m$ 行，第 $i$ 行输入三个空格分隔的整数，分别代表 $l_i, r_i$ 和 $c_i$。  
      
    接下来 $q$ 行，第 $i$ 行输入三个空格分隔的整数，分别代表 $ql_i, qr_i$ 和 $x_i$。  
      
    保证：  
    $1\le n \le 10^6$  
    $1 \le m, q \le 2\times10^5$  
    $0\le a_i,c_i,x_i \le 10^9$  
    $1 \le l_i\le r_i \le n$   
    $1\le ql_i\le qr_i\le n$

## 输出描述:
    
    
    输出共 $m$ 行，第 $i$ 行一个整数代表如果选用第 $i$ 种电脑配件，小蓝遇见卡死现象是因为第几次申请。  
      
    特别的，如果小蓝可以完成所有的申请操作，请输出 $-1$。

示例1 

## 输入
    
    
    5 3 3
    5 3 9 6 3
    2 5 2
    1 5 5
    1 2 1
    1 5 100
    1 5 0
    2 5 4

## 输出
    
    
    -1
    2
    3

## 备注:
    
    
    本题时限较为宽裕，不存在卡常的情况，请确定你的算法不会被卡常。


## 时空限制

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

## 题目描述

魔法商店里面有 $n$ 种打包小鱼干出售，第 $i$ 种打包共有 $a_i$ 条小鱼干，售价为 $2^{i-1}$ 个猫猫币。  
  
由于魔法商店的老板很吝啬，所以每天魔法商店只会开启一次，且每次每种打包小鱼干只能被购买一次。  
  
由于魔法商店的老板很慷慨，所以他保证如果有 $i < j$ 成立，那么一定有 $a_i \le a_j$ 成立（更贵的包里面的鱼干不会更少）。  
  
小蓝养了一只小猫，这只猫在剩下的 $q$ 天中，第 $i$ 天需要吃 $b_i$ 条小鱼干。  
  
小灰灰打算包下接下来每天中小猫的鱼干，所以他想知道每一天他最少需要花费多少钱才能凑够不少于 $b_i$ 的鱼干。  
  
注意，由于计算出来的花费可能非常大，所以你只需要输出最小花费模 998244353 的结果即可。

## 输入描述:
    
    
    第一行两个空格分隔的整数，分别代表 $n$ 和 $q$。  
      
    接下来一行 $n$ 个空格分隔的整数，第 $i$ 个整数代表 $a_i$。  
      
    接下来一行 $q$ 个空格分隔的整数，第 $i$ 个整数代表 $b_i$。  
      
    保证：  
    $1\le n, q \le 10^5$  
    $1\le a_i, b_i \le 10^{18}$  
    对于每个 $b_i$ 至少存在一种方式使得能够购买足够的小鱼干。

## 输出描述:
    
    
    输出共 $q$ 行，第 $i$ 行一个整数代表第 $i$ 天的最少花费余 998244353 的结果。

示例1 

## 输入
    
    
    8 4
    1 1 2 4 5 6 9 9
    10 14 8 5

## 输出
    
    
    25
    47
    15
    9


## 时空限制

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

## 题目描述

给定一张 $n$ 个结点 $m$ 条边的简单无向图，结点从 $1$ 到 $n$ 编号，每个结点都有一个颜色。  
  
我们可以说这个图是由若干个【团】组成的，若点 $a$ 和点 $b$ 在同一个团里，当且仅当存在一条从 $a$ 到达 $b$ 的路径，且这条路径上所有的点（包括点 $b$）与点 $a$ 同色。  
  
小灰灰接下来会进行 $q$ 次操作，每次操作会给定两个整数 $x$ 和 $c$，代表将 $x$ 以及所有和 $x$ 处在同一个团里的点颜色都修改为 $c$。  
  
小蓝需要在小灰灰每次操作之后回答当前的图中有多少个团，你能帮帮小蓝吗？

## 输入描述:
    
    
    第一行给定三个空格分隔的整数，分别代表 $n,m,q$；  
      
    接下来一行 $n$ 个空格分隔的整数，第 $i$ 个数代表编号为 $i$ 的结点的颜色；  
      
    接下来 $m$ 行，每行两个空格分隔的整数 $u,v$，代表结点 $u$ 和结点 $v$ 之间存在一条连边；  
      
    接下来 $q$ 行，每行两个空格分隔的整数 $x,c$，代表小灰灰操作了结点 $x$ 所在的团，将颜色转变成了 $c$。  
      
    保证：  
    图中不存在重边和自环。  
    $1\le n \le 10^5$  
    $1\le m \le 1.6 \times 10^5$   
    $1\le q \le 10^5$  
    颜色取值以及操作输入和连边结点编号都是不超过 $n$ 的正整数；

## 输出描述:
    
    
    输出共 $q$ 行，第 $i$ 行一个数代表小灰灰操作 $i$ 次后图中所具有的团的数量。

示例1 

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

## 输出
    
    
    4
    4
    2
    1

## 备注:
    
    
    提示：
    
    请注意本题的空间和时间限制。
    
    不建议定义过多的 STL 容器，容易导致空间和时间超限。


## 时空限制

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld
# 峡国西高校 (easy version)

## 题目描述

**本题 hard version 的唯一区别是，本题只需要求解两个数的 $k$ 进制异或和**  


**题目背景**

悸动的心,无法平复。  
被黑夜笼罩的天台上。  
我捂着开始隐隐作痛的心口,倚在仓库的墙壁上。  
“—— 明白了吗,不普通的你最终会走向哪里。 ”  
耳旁清里同学的声音,已然变得遥远。  
现在,她只是像一位击碎恋爱喜剧的代言人般,抛出了这些话。  
“ 我不知道你心中的理想是什么,只是,如果 ——”  
喀哒,脚步声又远了一步。  
“ 若追求的是如同青春小说般大家笑容洋溢的理想的话,若是为此而做着不普通的事情的话 ...... 等着你的未来,将是 ‘Bad Ending’ 。 ”  
喀哒,又一步。  
“ 所以啊,你周围的 “ 普通人们 ” ,并没有追求那样的理想。”  
喀哒  
“ 他们不想实现不持续努力就得不到的理想,他们不想看见与自己无关的理想。”  
喀哒  
“ 其实没有办法,能让那些只能每天佯装不知 ‘ 啊原来现实就是这样的啊 ’ ,在相应的日常中过活 ‘ 普通人们 ‘ 欢笑的啊。 ”  
喀哒  
“ 无视这一点,并将大家卷入理想的人,大家必定会对其露出獠牙。”  
喀哒 ——  
清里同学停下了脚步。  
“ 而离你最近的彩乃啊 —— 是一个,普通人吧。和未酱一样。”  
—— 啊  
“ 无论你如何在她的表面贴上理想,她最终也不过是一介普通人。”  
恶寒遍布我的全身  
“ 努力着努力着着,但现实都一直都不会如理想般现实,最终陷入理想与现实之间的泥潭中 ——”  
眼睛一阵刺痛。  
“ 长坂同学,你也不想让自己的 ‘ 青梅竹马 ’ 品尝这份痛苦吧? ”  
“ 现在一切都还不至于走到最坏的地步,还能够勉勉强强地回头。所以,就在这儿放弃追寻你的理想吧 ——”  
于是 ——  
曾是我 “ 恋爱喜剧 ” 的 “ 女主角 ” ,  
“ 在我让彩乃背叛之前 ——”  
最后,留下了这一句话  
从我面前,远去了。  


**题目描述**

koh 酱的运作原理非常简单，对于两个人，他们各自有一个特征值 $A$，则他们组在一起的权重为 $k$ 进制下特征值的异或和（也就是 $k$ 进制下的不进位加法）。  
现在给你两个用十进制表示的正整数与进制 $k$，求他们组在一起的权重。  


**数据范围**

$2\leqslant k\leqslant 500,1\leqslant A,B\leqslant 10^{18}$。  


## 输入描述:
    
    
    一行，三个正整数，分别表示进制 $k$ 与两个人的特征值 $A,B$。

## 输出描述:
    
    
    一行，一个正整数，表示他们组在一起的权重，用十进制表示。  
    
    
      
    

示例1 

## 输入
    
    
    5 4 8

## 输出
    
    
    7

## 说明
    
    
      
    


## 时空限制

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 峡国西高校 (hard version)

## 题目描述

**本题 easy version 的唯一区别是，本题需要求解一个序列中任两个不同的数的** $k$**进制异或和的和。**  


**题目背景**

「这样一来，你还没有意识到吗？自己的错误在哪里？」  
「——什么！」  
即便如此，我——  
我也要先否定现实（你）。  
「你，你……为什么要设计如此精细的行动……」  
「我的目的一直都没有改变过。」  
我点击了一下手机屏幕，轻轻地揣入胸前的口袋中。一下子挺直腰杆，与清里同学正面相对。  
接着，深深地吸了一口气。  
终于，对着“女主角”宣扬出了自己真意。  
「我想要做什么，这个始终都是一致的！只有一件事。  
在这只有一次的高中生涯中，实现最好的“理想乡（爱情喜剧）”，达成“完美无缺的happy end”——仅此而已！」

**题目描述**

有 $n$ 个点，我们认为第 $i$ 个点的特征值为 $a_i$。  
我们认为两个点组在一起的权重为 $k$ 进制下特征值的异或和（也就是 $k$ 进制下的不进位加法），而这个序列的权重为任选两个不同的点，将他们组合的权重之和。  
现在你需要求出这个序列的权重，对 $10^9+7$ 取模。

  


**数据范围**

$1\leqslant n\leqslant 2\times10^6,2\leqslant k\leqslant 500,1\leqslant a_i\leqslant 10^{18}$。  


## 输入描述:
    
    
    第一行两个正整数 $n,k$，分别表示序列长度与进制。  
    第二行 $n$ 个正整数，第 $i$ 个正整数为 $a_i$ 表示第 $i$ 个数的特征值。

## 输出描述:
    
    
    一行，一个正整数，表示这个序列的权重，对 $10^9+7$ 取模。

示例1 

## 输入
    
    
    2 5
    4 8

## 输出
    
    
    7

示例2 

## 输入
    
    
    8 16
    32178 3216 31268 31280 3879 34278 3728 217

## 输出
    
    
    898884


## 时空限制

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# 县立樱姬中学

## 题目描述

**题目背景**

我伸出手却够不到。还差一点点，可就是够不着。已经，永远都够不着了。 

“为什么就是够不着啊……”  
伸出的手上戴着的手表指针已经转到四点五十八分了，十秒，二十秒，三十秒。然后。  
“回来吧。”  
一道声音盖过雨声传了过来。  
温柔，圆润的声音。帮我捡起护身符的人是。  
“秋月。”  
“阳菜子阿姨……”  
谢谢。  
最后仿佛听到她低声说了句。  
之后，时间迎来了四点五十九分。  


我死去，她重生。 

  


**题目描述**

现在有 $n$ 个数，第 $i$ 个数的权值为 $a_i$。  
我们认为能从节点 $i$ 跳跃到节点 $j$，当且仅当 $a_j<a_i$ 且 $j<i$ 同时 $i \not\equiv j \pmod k$，其中 $k$ 为给出的定值。  
对于每个点 $i$，你需要求出从点 $i$ 开始最多能够跳跃多少次。  
保证 $a_i$ 互不相同。 

  


**数据范围**

$1\leqslant n,k\leqslant 10^6,1\leqslant a_i\leqslant 10^{18}$。  
  
保证 $a_i$ 互不相同。  


## 输入描述:
    
    
    第一行，两个整数 $n,k$，分别表示数的数量与判断跳跃的参数  
      
    第二行，$n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个点的点权。

## 输出描述:
    
    
    一行，$n$ 个整数，第 $i$ 个整数表示从第 $i$ 个点开始最多能够跳跃多少次。  
    

示例1 

## 输入
    
    
    5 3
    3 2 1 4 5

## 输出
    
    
    0 0 0 1 2


## 时空限制

时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 音吹高中

## 题目描述

**题目背景**

「（做什么白日梦呢。不对吧，星之守千秋。今天来这……难道不是为了做个了断吗）」  
没错。我让心春先回去，特地独自来这……可不是为了委身于这种甜蜜的幻想。  
倒不如说，是为了一决胜负。  
在这最后……。……为了断念这份「偶然」及「命运」，勇敢的，独自一人……将存在与此的，那令人留恋的奇迹般的「某物」——。  
「……千秋？」  
「————」  
突然，被人从身后搭话，我，完全僵硬了。  
没想到，居然，为什么，偏偏，在这个时候。  
纷乱的情感油然而生……但是，我依旧安慰自己「不，只不过是由我的愿望所产生的幻听而已。绝对是这样。这是最合理的解释！」，为了证明它，我停止观星回过头。  
于是，我慢慢降低视线，只见那里。  
「晚上好，千秋。没想到我特地独自一人来观星都能遭遇你……有点搞笑呢」  
带着天真无邪的笑脸的思念之人——雨野景太。  
我紧紧摁住胸口，不禁再次抬头看向星空。  
「（……放过我吧……真是受够了……）」  
我真心向玩弄自己的神明如此请愿。  
**题目描述**  


雨野拿到了 nobe 大师的新作品，这次是一个擂台游戏。  
初始总共有 $n$ 个人，每个人的体力值为 $a_i$，当第 $i$ 个人体力值降为 $0$ 的时候，第 $i$ 个人就会下场。  
假设第 $i$ 个人和第 $j$ 个人决斗，则两者体力值均减掉 $min(a_i,a_j)$。  
当最后只有一个人站在场上，那个人就获胜了。  
当然既然是 nobe 大师的作品怎么可能像小程序游戏一样唐？假设现在有 $m$ 个人，雨野可以选择一个长度为 $m$ 的排列 $p$，则每次在排列中选取前两位还没有下场的人进行决斗直到最后只剩一个人站在场上，如果没有人站在场上，那就没有人获胜。  
譬如序列 a 为 $[5,1,2,4,3]$，p 为 $[4,1,2,3,5]$，则第 $4$ 个人和第 $1$ 个人打，第 $4$ 个人体力变为 $4-\min(4,5)=0$，下场，第 $1$ 个人体力变为 $5-\min(4,5)=1$，留在场上；第 $1$ 个人接下来和第 $2$ 个人打，第 $1$ 个人体力变为 $1-\min(1,1)=0$，下场，第 $2$ 个人体力变为 $1-\min(1,1)=0$，同样下场；接下来第 $3$ 个人和第 $5$ 个人打，第 $3$ 个人变成 $2-\min(2,3)=0$，下场，第 $5$ 个人变成 $3-\min(2,3)=1$，此时只有第 $5$ 个人没有下场，所以第 $5$ 个人获胜。  
同时这个游戏还支持自定义角色，雨野自定义了 $q$ 个角色，他决定依次将这些角色加入游戏中，在加入第 $i$ 个角色之后他想立刻知道现在第 $i$ 个角色是否有可能获得胜利，如果可以，输出 mono 并构造方案，否则输出 nobe。  


**数据范围**

$1\leqslant n,q\leqslant 2\times 10^3,2\leqslant n+q \leqslant 2\times10^3,1\leqslant \sum a_i\leqslant 2\times 10^6$  


  


## 输入描述:
    
    
    第一行一个数 $n$ 表示总人数。  
    第二行 $n$ 个数，第 $i$ 个数为 $a_i$ 表示第 $i$ 个人最初的体力值。  
    第三行一个数 $q$ 表示自定义角色数。  
    第四行 $q$ 个数，第 $i$ 个数为雨野自定义的第 $i$ 个角色的体力值。

## 输出描述:
    
    
    对于第 $i$ 组询问，如果答案为 mono，则接下来一行输出一个长度为 $n+i$ 的排列 $p$，表示雨野安排的决斗顺序；否则输出一行结束。  
    

示例1 

## 输入
    
    
    2
    2 12
    1
    15

## 输出
    
    
    mono
    1 2 3

示例2 

## 输入
    
    
    2
    12 13
    1
    2

## 输出
    
    
    mono
    1 2 3

## 说明
    
    
      
    


## 时空限制

时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld
# 白树台学园 (easy version)

## 题目描述

**本题与 hard version 的区别在于每个颜色的随机区间是固定的，同时只有一组全局询问，相对的数据范围也有变化。**

**题目背景**

正因为如此，他才没有察觉。  
他没有察觉到，有个少女知晓一切——不，策划一切，并伸手打算为这场战斗画下真正的句点。  
宫里学长抬起眼,察觉到有只手从眼角余光逼近，但迟了数秒才反应过来——这是他致命的失误。正欲转身闪躲的学长，惊愕地目睹桐香出人意料、快狠准的伸手动作。  
桐香的指尖挖进宫里学长的太阳穴，勾起头带甩出去。白色的布条高高舞上日暮时分的紫红色天空，如垂死的鸟般挣扎片刻，最后终究失去力量，在尚未恢复流动的时间中随风飘落。  
有人高高举起手，抓住那条白色尸骸。  
——是会长。  
**题目描述**  


IT 社在运动会的夺棒中大获全败，伊藤在熬了三天三夜之后得出了一个伟大的模型！  
已知我方有 $n$ 个人，夺棒总共有 $m$ 个方面，其中各个人有各个擅长的方面，第 $i$ 个人擅长第 $a_i$ 个方面。  
**但是实际上只有一些位置我们已经确定好了人选，其** $a_i$**也是确定的，而有一些位置我们还没决定好会选谁，所以其** $a_i$**是在** $[1,m]$**中随机取的。**  
红方每次攻击都会先选择一个区间进行攻击。  
伊藤这个伟大的模型断定，如果有两个人拥有同一种才能，那么这方面的才能就只能发挥一次，**每次红方攻击的区间的牢固度，即为区间内不同才能的种数。**  
但是显然伊藤不知道红方的攻击策略，于是默认他们随机选择区间进行攻击。  
作为 IT 社底层社员，你的任务是：对于上面发下来的预编排位置，计算红方攻击的区间的牢固度的期望值，并对 $998244353$ 取模。  


**简要题意**

给一个长度为 $n$ 的序列，其中 $a_i$ 要么是一个在 $[1,m]$ 内的定值，要么是 $0$ 表示在 $[1,m]$ 内的随机值，现在随机一个区间，问你区间期望颜色数量是多少，对 $998244353$ 取模。 

**数据范围**

$1\leqslant n,m\leqslant 5\times 10^6$。  


## 输入描述:
    
    
    第一行，两个整数 $n$ 和 $m$，分别表示人数和方面数。  
    第二行，$n$ 个整数 $a_i$，表示每个人擅长哪方面，是 $0$ 则随机。

## 输出描述:
    
    
    第一行，一个整数，表示最后牢固度的期望值，对 $998244353$ 取模。

示例1 

## 输入
    
    
    5 3
    1 3 2 1 3

## 输出
    
    
    865145108

示例2 

## 输入
    
    
    8 4
    2 2 1 1 0 2 0 4

## 输出
    
    
    812806602


## 时空限制

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
# 白树台学园 (hard version)

## 题目描述

**本题与 easy version 的区别在于本题每个点的随机区间是给定的，并且有多组针对颜色区间的询问，相对的数据范围也有区别。**  


**题目背景**

在一阵诡异的紧张静谧中，她扬起冰雨般的笑容，视线从宫里学长移向路易学长。 

「你以为我是大将？真可惜呢。大将的头带，藏在一个绝对安全的家伙头上，也就是——这条。」  
会长解开宫里学长的白色头带，翻过来亮出绣好的「将」字。路易学长表情黯然，其他人根本不了解现在是什么状况。  
「你懂吧？宫里刚才变成红队的人，然后被白队的圣桥桐香抢走头带，而且他的头带上绣着『将』字。换句话说……」  
「红队的大将被淘汰了。」  


「——我们赢了。」 

**题目描述**

并非有题目背景。 

**简要题意**

现在给你一个长度为 $n$ 的序列，每个点有一个区间 $[L_i,R_i]$ 表示这个点的颜色在这个里面随机选取。 

同时有 $q$ 次操作，每次操作有两种形式，要么是在序列末尾加入一个在区间 $[lt,rt]$ 内随机的数，要么是给定一个颜色区间 $[lt,rt]$，表示你需要求出如果只承认颜色区间 $[lt,rt]$ 中的颜色有效，在全局随机一个下标区间的期望颜色数量，对 $998244353$ 取模。  
强制在线，具体来讲，你输入的是 $lt'$ 和 $rt'$，假设上一次询问的答案为 $lstans$（不存在则设为 $0$），则真正的 $lt=(lt'\ xor\ lstans)\ mod\ m+1,rt=(rt'\ xor\ lstans)\ mod\ m+1$，如果 $lt>rt$，则交换 $lt,rt$。  


**数据范围**

$1\leqslant n,m,q\leqslant 5\times10^5,1\leqslant lt,rt\leqslant m$。  


$lt',rt'$ 为 long long 范围内的非负整数。  


## 输入描述:
    
    
    第一行，三个整数 $n,m,q$，分别表示序列长度，值域范围，以及询问次数。  
    接下来 $n$ 行，每行两个整数 $L_i,R_i$，表示第 $i$ 个点的随机范围。  
    接下来 $q$ 行，每行三个整数 $opt,lt',rt'$，若 $opt=1$，则表示在序列末尾加一个数，若 $opt=2$，则表示询问期望颜色数量，具体可参照题目描述。。

## 输出描述:
    
    
    对于每个 $2$ 操作，输出一行一个整数，表示答案对 $998244353$ 取模后的结果。

示例1 

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

## 输出
    
    
    465847366
    2
    532396989

示例2 

## 输入
    
    
    10 10 20
    3 4
    2 2
    3 3
    1 2
    1 2
    1 6
    4 10
    4 5
    3 4
    3 3
    1 1432355238 1188125139
    2 1495854081 1287747189
    1 1031813651 659014611
    2 176453019 311972948
    1 595152290 1350063891
    2 1548786293 657174385
    2 537116146 2045708487
    2 1181196917 772022214
    1 2090978521 1234214707
    2 1643803091 1394578160
    2 684444582 1196029970
    2 1972191771 24965845
    1 483722735 474504488
    1 795695683 329012153
    1 2145759574 1576608400
    2 655450311 1424468515
    1 553675150 1610608220
    2 1325697365 293123810
    1 412428424 540843749
    2 1807006585 1759479551

## 输出
    
    
    156200756
    832586375
    930297398
    808063397
    769669383
    651904620
    825627810
    988385150
    975895544
    201499017
    85143196


## 时空限制

时间限制：C/C++/Rust/Pascal 8秒，其他语言16秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
# 岛屿题

## 题目描述

**题目背景**

时间紧任务重这是只有二十八字的题目背景我花五秒钟就写完了。  


**题目描述**

给你一张 $n$ 行 $m$ 列的地图，每个点可能是 '#','.' 和 'v' 三种状态，分别表示岛屿，空地与火山。  
现在有 $q$ 次询问，每次询问给你一个 $(x,y)$，询问从 $(x,y)$ 出发再回到 $(x,y)$，把所有岛屿围起来，路径权值最大是多少，  
我们定义一条路径合法，当且仅当他的每一步都不走出地图边界，不经过岛屿（特别地，火山是可以经过的），同时相邻两步的横坐标与纵坐标必然有一个相同另一个差 $1$，**注意这里并不要求这条路径不走回头路或是不走走过的路。**  
而我们定义一条路径的权值为路径中每一个点到火山的曼哈顿距离的最小值。 

多组数据。 

**注意可能有多个不联通的岛屿，你必须把他们全部围起来，具体地，假设把路径经过的点全部删除，没有任何一个岛屿点与没有被删除的边界八联通。**  


**数据范围**

$1\leqslant T\leqslant 10^4, 1\leqslant n,m\leqslant 1000,\sum nm\leqslant 10^6,1\leqslant q\leqslant 10^6,\sum q \leqslant 10^6,1\leqslant x\leqslant n,1\leqslant y\leqslant m$，数据保证至少存在一种从 $(x,y)$ 出发环所有岛屿一圈的方案，同时 $(x,y)$ 必然在空地。 

## 输入描述:
    
    
    第一行，一个整数 $T$，表示数据组数。  
    
    
    对于每组数据：
    
    第一行，三个正整数 $n,m,q$，分别表示地图的行列数与询问次数。
    
    接下来 $n$ 行，每行 $m$ 个字符，表示输入地图。  
    接下来 $q$ 行，每行两个正整数 $x,y$，表示询问的起点的位置。

## 输出描述:
    
    
    对于每组数据：
    
    $q$ 行，每行一个整数表示从 $(x,y)$ 出发再回到 $(x,y)$ 并围起所有岛屿的最大路径权值。

示例1 

## 输入
    
    
    1
    9 9 3
    .........
    .........
    ....###..
    ...v#....
    ..###....
    ...##...v
    ...##....
    .........
    v........
    1 1
    9 1
    5 7

## 输出
    
    
    3
    0
    3

示例2 

## 输入
    
    
    1
    3 3 5
    ..v
    .#.
    ...
    1 2
    1 3
    2 3
    2 1
    3 2

## 输出
    
    
    0
    0
    0
    0
    0

示例3 

## 输入
    
    
    1
    14 13 5
    .............
    .............
    .............
    ...vvvvvvv...
    ...v.....v...
    ...v.###.v...
    ...v.#.#.v...
    ...v..v..v...
    ...v..v..v...
    ....v...v....
    .....vvv.....
    .............
    .............
    .............
    1 1
    7 7
    5 6
    4 10
    13 6

## 输出
    
    
    3
    0
    1
    0
    2

示例4 

## 输入
    
    
    1
    10 11 4
    ...........
    ..#######..
    ..#..#..#..
    ..#.....#..
    ..#..v..#..
    ..#.###.#..
    ..#.#.#.#..
    ..#...#.#..
    ..#####.#..
    ...........
    7 6
    3 7
    6 8
    1 1

## 输出
    
    
    1
    2
    3
    4

示例5 

## 输入
    
    
    1
    10 10 1
    ..........
    ..........
    ...#.#.#..
    ....#v#v..
    ...v.##v..
    v...vv...v
    ..#v...#..
    .....v.v..
    ...v..v...
    ..v.......
    2 3

## 输出
    
    
    1

示例6 

## 输入
    
    
    1
    10 10 1
    .v........
    .v........
    ......#...
    ..v....#..
    ....v.....
    ..........
    ..#.......
    .....v....
    ........v.
    ..........
    5 10

## 输出
    
    
    1


## 时空限制

时间限制：C/C++/Rust/Pascal 10秒，其他语言20秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld
# Wakey Wakey

## 题目描述

定义若干个数的绝对众数为，出现次数严格大于一半的数（若不存在则没有绝对众数）。 

定义一个序列是好的，当且仅当对于其中任意区间，都存在绝对众数。 

求长度为 $n$，值域为 $1\sim m$ 的好的序列方案数，对 $p$ 取模。保证 $p$ 为质数。 

## 输入描述:
    
    
    本题有多组数据。
    
    第一行，一个正整数 $T$，表示数据组数。
    
    接下来 $T$ 行，每行三个正整数 $n,m,p$。

## 输出描述:
    
    
    $T$ 行，每行一个非负整数，表示答案。

示例1 

## 输入
    
    
    2
    2 3 2
    10000 100000 2333

## 输出
    
    
    1
    2014

## 备注:

  * $1\le T\le 10$；
  * $1\le n,m\le 10^5$；
  * $1\le p\le 10^9$；
  * $p$ 为质数。




## 时空限制

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

Tags: 数论
Difficulty: 600
# Substring Not Subsequence

## 题目描述

给定长度为 $n$ 的字符串 $S$，请求出有多少个非空字符串 $T$ 满足： 

  


  * $T$ 作为子串在 $S$ 中出现至少一次； 
  * $S$ 中不存在不连续的子序列等于 $T$。  


  


## 输入描述:
    
    
    第一行，一个正整数 $n$。
    
    第二行，一个长为 $n$ 的字符串 $S$。

## 输出描述:
    
    
    一行，一个正整数，表示答案。

示例1 

## 输入
    
    
    5
    abcaa

## 输出
    
    
    9

## 说明
    
    
    共有 $9$ 个 $T$ 满足条件：$\texttt{a},\texttt{ab},\texttt{abc},\texttt{abcaa},\texttt{b},\texttt{bc},\texttt{bcaa},\texttt{c},\texttt{caa}$。
    
      
    
    
    串 $\texttt{abca}$ 不满足条件，因为取下标 $1,2,3,5$ 可以形成 $\texttt{abca}$，但是这些下标不连续。
    
      
    
    
    串 $\texttt{aba}$ 也不满足条件，因为 $\texttt{aba}$ 没有作为子串出现过。

## 备注:
    
          * $1\le n\le 2\times 10^5$；
      * $S$ 中只含小写英文字母。
    
    


## 时空限制

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

Tags: 字符串, 思维
Difficulty: 1400
# 序列

## 题目描述

有一个长度为 $4n$ 的 $01$ 串 $s_1s_2\dots s_{4n}$，你需要重复如下操作 $n$ 次： 

  * 设 $L$ 为当前 $s$ 的长度。选择一个 $1\le i\le L-3$，使得 $s_is_{i+1}s_{i+2}s_{i+3}=0011$，并将 $s_i,s_{i+1},s_{i+2},s_{i+3}$ 删去。假如这是第 $j$ 次操作，记 $x_j=i$。 



请求出有多少种不同的将整个字符串删空的方案，答案对 $10^9+7$ 取模。认为两种方案不同，当且仅当存在一个 $1\le j\le n$，使得两种方案的 $x_j$ 不相等。 

## 输入描述:
    
    
    本题有多组数据。
    
    第一行，一个正整数 $T$。
    
    接下来，对于每组数据：

  * 第一行，一个正整数 $n$；
  * 第二行，一个长为 $4n$ 的字符串 $s_1s_2\dots s_{4n}$。



## 输出描述:
    
    
    $T$ 行，每行一个非负整数，表示答案。

示例1 

## 输入
    
    
    4
    1
    1001
    2
    00110011
    5
    00000000011111101111
    5
    00011000111100110011

## 输出
    
    
    0
    2
    1
    40

## 备注:
    
    
    记 $N$ 为单个测试点中所有数据的 $n$ 之和。

  * $1\le n,N\le 10^5$；
  * $s_i\in \\{0,1\\}\ (1\le i\le 4n)$。




## 时空限制

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

Tags: 图论, 拓扑排序, 数据结构, 树
Difficulty: 2400
# 数据结构

## 题目描述

给定一个长为 $n$ 的正整数数列 $a_1,a_2,\dots,a_n$，有 $q$ 次操作，每次给定整数 $l,r,c$，你需要执行如下操作： 

  * 对于每个整数 $i\in [1,n]$，如果 $a_i\in [l,r]$ 且 $a_i\equiv c\pmod 2$，则令 $a_i\gets a_i-1$。 



每次操作后，你需要求出所有 $a_i$ 之和。 

## 输入描述:
    
    
      
    
    
    第一行，两个正整数 $n,q$。
    
    第二行，$n$ 个正整数 $a_1,a_2,\dots,a_n$。
    
    第 $3$ 至 $(q+2)$ 行，每行三个整数 $l,r,c$。
    
      
    

## 输出描述:
    
    
    为了减少输出量，设第 $i$ 次操作后的答案为 $s_i$，你只需要输出 $(1\times s_1)\oplus (2\times s_2)\oplus\dots\oplus (q\times s_q)$ 即可，其中 $\oplus$ 表示按位异或。

示例1 

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

## 输出
    
    
    18

## 说明
    
    
    $s=[11,11,8,6,3,0]$。

## 备注:

  * $1\le n,q\le 5\times 10^5$；
  * $1\le a_i\le 5\times 10^5\ (1\le i\le n)$；
  * $1\le l\le r\le 5\times 10^5$；
  * $c\in \\{0,1\\}$。




## 时空限制

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

Tags: 数据结构, 线段树, STL
Difficulty: 2700
# 配对

## 题目描述

给定偶数 $n$，有一棵 $n$ 个点的树，点的编号是 $1,2,\dots,n$。你需要将这 $n$ 个点配对，形成 $\frac{n}{2}$ 对点，每个点恰好在某一对点里出现一次。 

设 $d(u,v)$ 表示 $u$ 到 $v$ 的简单路径的边数，定义一种配对方案 $(u_1,v_1),(u_2,v_2),\dots,(u_{\frac{n}{2}},v_{\frac{n}{2}})$ 的权值是 $d(u_1,v_1)\times d(u_2,v_2)\times \dots \times d(u_{\frac{n}{2}},v_{\frac{n}{2}})$。 

求所有不同的配对方案的权值之和，对 $10^9+7$ 取模。 

认为两种配对方式是不同的，当且仅当存在一个点，在两种方案中与它配对的点不同。 

## 输入描述:
    
    
    第一行，一个正整数 $n$。
    
    第 $2$ 至 $n$ 行，每行两个正整数 $u,v$，描述树上的一条边。

## 输出描述:
    
    
    一行，一个非负整数，表示答案。

示例1 

## 输入
    
    
    4
    1 2
    1 3
    1 4

## 输出
    
    
    6

## 说明
    
    
    点 $1$ 与 $2,3,4$ 中的某个点配对，剩下的两个点配对，有三种配对方案，每种方案的权值都是 $2$，所以权值之和为 $6$。

示例2 

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

## 输出
    
    
    174

示例3 

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

## 输出
    
    
    140864

## 备注:

  * $1\le n\le 50$；
  * $2\mid n$。




## 时空限制

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

Tags: 背包问题, 动态规划, 树形dp
Difficulty: 2900
# Rookhopper's Tour

## 题目描述

给定正整数 $n,m$，设二元组集合 $S=\\{(x,y)\mid 1\le x\le n;1\le y\le m;x,y\in \mathbb{Z}\\}$。你需要选择 $S$ 的一个子集 $T$，使得： 

  * 对于任意 $(x_1,y_1),(x_2,y_2)\in T$，要么 $(x_1,y_1)=(x_2,y_2)$，要么 $x_1\neq x_2,y_1\neq y_2$； 
  * 对于任意 $(x,y)\in T$，存在 $(x',y')\in T$，满足 $|x-x'|=1$ 或 $|y-y'|=1$。 



有 $q$ 次询问，第 $i$ 次给定正整数 $k_i$，求有多少种选择 $T$ 的方案，使得 $T$ 满足上述条件，且 $|T|=k_i$。答案对 $10^9+7$ 取模。 

## 输入描述:
    
    
    第一行，三个正整数 $n,m,q$。
    
    第二行，$q$ 个正整数 $k_1,k_2,\dots,k_q$。

## 输出描述:
    
    
    一行，$q$ 个非负整数，表示答案。

示例1 

## 输入
    
    
    2 2 2
    1 2

## 输出
    
    
    0 2

## 说明
    
    
    有三种选择 $T$ 的方案：$\varnothing,\{(1,1),(2,2)\},\{(1,2),(2,1)\}$，其中 $|T|=1$ 的有 $0$ 种，$|T|=2$ 的有 $2$ 种。

示例2 

## 输入
    
    
    3 4 3
    1 2 3

## 输出
    
    
    0 30 24

示例3 

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

## 输出
    
    
    0 84994385 800381083 658879412 585470103

## 备注:

  * $1\le n,m\le 5\times 10^6$；
  * $1\le q\le 5$；
  * $1\le k_i\le \min(n,m)\ (1\le i\le q)$。




## 时空限制

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

Tags: 组合数学, 容斥原理与鸽巢原理, 数论
Difficulty: 3000