1C
Algosia和Bajtek喜欢参加算法竞赛。在远程轮次中，共有18个任务需要解决，每个任务可以获得0到10分。参赛者按照获得的总分进行排名。如果总分相同，得到10分的任务数量更多的参赛者排名更高。如果还相同，得到9分的任务数量更多的参赛者排名更高，依此类推。如果还无法区分，那么宣布他们之间是平局。
Algosia和Bajtek记得他们在最后一次比赛中每个任务的成绩，但他们忘记了…谁赢了。你能帮助他们编写一个程序，读取他们的成绩并告诉他们哪个人排名更高吗？
输入
输入的第一行包含18个整数[0, 10]——Algosia在连续任务上的成绩。
同样，在输入的第二行中包含18个整数[0, 10]——Bajtek在连续任务上的成绩。
输出
输出的唯一一行应该包含一个单词——“Algosia”或“Bajtek”，表示获胜者的名字。如果是平局，应该使用“remis”。
例子
对于输入数据：
10 10 7 10 10 10 10 10 10 10 10 10 0 10 4 10 10 10
10 10 10 10 10 10 10 10 10 10 10 10 4 3 4 10 10 10
正确的结果是：
Algosia
示例解释：尽管Algosia和Bajtek都恰好获得了161分，但根据算法竞赛的规则，Algosia获得了更好的结果。
1B
根据PWN词典，“领导者”在其他方面也是“政党、工会或其他社会组织的领导人”。而在算法中，我们称一个序列中出现次数严格大于序列长度一半的元素为该序列的领导者。例如，序列[7, 2, 5, 7, 7]的领导者是数字7，而序列[2, 3, 2, 3]根本没有领导者。
在这个任务中，我们将关注“领导者”这一词的第二个含义。给定一个数字序列，你的任务是将它分割成尽可能少的序列（不一定是连续的），每个序列都有一个领导者，并输出这个最小的数目。可以证明，这样的分割总是可能的。
输入
输入的第一行包含一个整数n（1 ≤ n ≤ 500,000），表示序列的长度。
输入的第二行包含n个整数a1, a2, ..., an（1 ≤ ai ≤ n）。
输出
输出仅一行，应包含一个整数，表示可以将输入序列分割成的拥有领导者的结果序列的最小可能数量。
示例
对于输入数据：
5
1 2 3 1 2
正确的结果是：
2
示例解释：输入序列可以被分割成例如[1, 3, 1]和[2, 2]的序列。通过这种方式，两个结果序列都会有领导者（分别是数字1和2）。
1A
Bajtocka村庄正在进行现代化改造。最新的政府项目旨在向那些尚未拥有计算机的村庄和小城镇的居民提供计算机。Bajtazar负责监督计划中的一个村庄——Bajtoszyc的现代化改造，在这个村庄里，目前没有任何居民拥有计算机。
Bajtoszyc有n名居民，为了方便，Bajtazar用从1到n的整数对他们进行了编号。一开始，没有任何居民拥有计算机。Bajtazar的任务是处理三种类型的事件：
• + ai bi - 一台计算机被送到了Bajtoszyc的一位居民那里。但是Bajtazar不知道计算机是送给编号为ai还是bi的居民。可能发生ai = bi的情况——那么计算机肯定被送给了编号为ai的居民。可以肯定的是，计算机被送给了目前没有计算机的居民。
• - ci - 编号为ci的居民的计算机坏了。可以肯定的是，这位居民之前拥有计算机（但现在不会有了，因此未来可能会收到新的）。
• ? di - Bajtazar需要判断（根据他迄今为止获得的所有信息），编号为di的居民：肯定拥有计算机，肯定没有计算机，还是不确定是否拥有计算机。
编写一个程序，帮助Bajtazar回答他被问到的问题！
输入
输入的第一行包含两个整数n和q（1 ≤ n ≤ 300,000；1 ≤ q ≤ 1,000,000），分别表示Bajtoszyc的居民数量和Bajtazar需要处理的事件数量。
接下来的q行描述了任务描述中所述的各个事件。在所有事件中，都有1 ≤ ai, bi, ci, di ≤ n。
保证至少会有一次询问Bajtazar他的知识状态的事件，即输入至少包含一个‘?’类型的事件。也保证至少存在一种计算机交付过程，在该过程中，计算机总是被送给当前没有计算机的人，并且计算机总是会坏掉在当前拥有计算机的人那里。
输出
输出应该是一个长度等于‘?’类型事件数量的字符序列。如果在第i次查询时，该居民肯定拥有计算机，那么该序列中的第i个字符应该是‘1’。如果该居民肯定没有计算机，那么第i个字符应该是‘0’。如果该居民可能拥有计算机，但也可能不拥有，则第i个字符应该是‘?’。
示例
对于输入数据：
5 11
? 1
+ 1 2
+ 2 3
? 2
+ 3 1
- 2
? 1
? 2
? 3
+ 2 2
? 2
正确的结果是：
0?1011
示例解释：一开始没有人拥有计算机，所以对第一个问题的回答是否定的，输出的第一个字符是‘0’。然后送出了两台计算机，并且我们询问第二位居民是否拥有计算机。可能其中一台送给了他，但也可能是第一位和第三位居民分别收到了计算机。因此，我们不能确定第二位居民是否拥有计算机，答案是‘?’。注意，在下
2C
任务：ZNA
邮票 [C]
2024算法竞赛，第二轮。限制：1024 MB，2秒。2024年3月12日
Bajtazar曾经收集了一套相当大的邮票集。但他现在不像年轻时那么感兴趣了，因此他决定将自己的收藏赠送给年轻的集邮爱好者。不过，他希望这样做尽可能公平，于是需要你的帮助。
Bajtazar的收藏包含n枚邮票，其中第i枚来自于城市ai。为了简化，我们用整数来表示城市。Bajtazar打算在报纸上发布公告，宣布他计划赠送自己的收藏。如果有k位爱好者响应，他将给每位爱好者一些邮票的子集，并且要满足一个条件：每位爱好者必须获得相同的邮票多重集。这意味着，对于任意两位爱好者和任意一个城市，他们必须获得该城市相同数量的邮票。这可能意味着Bajtazar最终可能不会赠送任何邮票。
Bajtazar不知道到底会有多少人响应。因此，对于从1到n的每一个数k，你需要确定，如果有k位爱好者响应，Bajtazar最多可以赠送多少枚邮票。
输入
输入的第一行包含一个整数n（1 ≤ n ≤ 300,000），表示Bajtazar的邮票集中的邮票数量。
输入的第二行包含n个整数a1, a2, ···, an（1 ≤ ai ≤ 10^9）——表示Bajtazar的邮票分别来自哪些城市的编号。
输出
输出只有一行，包含n个由单个空格分隔的数字；第k个数字应等于如果有k位爱好者响应时，Bajtazar最多可以赠送的邮票数量。
示例
对于输入数据：
9
1 1 777 42 777 1 42 1 777
正确的结果是：
9 8 6 4 0 0 0 0 0
示例解释：如果只有一个爱好者响应，Bajtazar可以赠送他所有邮票。
如果有两位爱好者响应，Bajtazar可以给他们每人赠送两枚来自城市1的邮票，每人一枚来自城市42的邮票，以及每人一枚来自城市777的邮票，总共8枚邮票。
如果有四位爱好者响应，Bajtazar可以给他们每人赠送一枚来自城市1的邮票。
如果爱好者超过四人，Bajtazar将无法赠送任何邮票。
2B
任务：ALC
炼金术师Bajtazar [B]
2024算法竞赛，第二轮。限制：1024 MB，2秒。2024年3月12日
Bajtazar是一名著名的炼金术师，暂时搁置了制造哲人石的尝试，转而致力于物质的转化。具体来说，Bajtazar希望将一种分子转化为另一种分子。
Bajtazar拥有的分子由n个bajtonium原子组成，这些原子编号从1到n。某些原子对之间可能存在化学键，但每对原子之间最多只能存在一个化学键。Bajtazar的分子是一个连通体——从任一原子出发，都能通过一个或多个化学键到达其他任何原子。
Bajtazar有一份他想要获得的n原子分子的化学键描述——对于每对原子，他知道他是否希望它们最终通过化学键连接。目标分子也满足相同条件——它是一个连通体，且任意两个原子之间最多只有一个化学键。不幸的是，Bajtazar的分子可能与目标分子不同。为了解决这一问题，他可以利用他的炼金术能力。他随时可以执行以下两种操作之一：
- Bajtazar可以选择两个未通过化学键连接的不同原子a和b，并在它们之间创建一个化学键。由于bajtonium的极高不稳定性，他只能在存在一个与a和b都当前连接的不同原子c的情况下才能这么做。
- Bajtazar可以选择两个通过化学键连接的不同原子a和b，并移除它们之间的化学键。由于类似的原因，他只能在存在一个与a和b都当前连接的不同原子c的情况下才能这么做。
Bajtazar不希望在转化过程上花费太多时间。编写一个程序，帮助他将他的分子转化为目标分子，并且在不超过200,000步内完成。
输入
输入的第一行包含一个整数n（2 ≤ n ≤ 30,000），表示Bajtazar拥有的分子中的原子数量，以及目标分子中的原子数量。
输入的第二行包含一个整数ms（n−1 ≤ ms ≤ 50,000），表示Bajtazar拥有的分子中的化学键数量。
接下来的ms行每行包含两个整数。第i行中的数ai和bi（1 ≤ ai, bi ≤ n; ai ≠ bi）表示通过化学键连接的原子编号。保证Bajtazar的分子是一个连通体，且任意两个原子最多只能通过一个化学键连接。
输入的下一行包含一个整数md（n−1 ≤ md ≤ 50,000），表示目标分子中的化学键数量。
接下来的md行包含对这些化学键的描述，格式与Bajtazar拥有的分子的化学键描述格式相同。
- 在Bajtocja，bajtonium是最常见的化学元素之一，用于生产食品和隐形眼镜等。
输出
输出的第一行应包含你想要执行的移动次数r，0 ≤ r ≤ 200,000。
接下来的r行应描述接下来的每个移动。如果你想在第i次移动中创建原子xi和yi之间的化学键，那么第i行应以符号‘+’开始，后跟一个空格，然后是xi和yi的数字，数字之间也由一个空格分隔。如果你想移除连接原子xi和
yi的化学键，则该行应以符号‘-’开始，然后以相同的格式包含xi和yi的数字。
你编写的移动序列必须符合任务描述中给出的条件——在选择原子xi和yi时，必须存在另一个与它们都连接的不同原子。执行移动序列后，最终分子必须与目标分子完全相同：对于每对原子i和j（1 ≤ i < j ≤ n），当且仅当在目标分子中原子编号为i和j的原子通过化学键连接时，它们也应在最终分子中通过化学键连接。
请注意，你不需要最小化移动次数——只需确保不超过200,000次。
可以证明，总是可以通过不超过200,000次移动完成转化。
示例
对于输入数据：
4
3
1 2
3 4
3 2
4
1 4
1 2
2 3
3 4
正确的结果是：
3
+ 1 3
+ 1 4
- 3 1
示例解释：注意到Bajtazar一开始不能直接在第一个原子和第四个原子之间创建化学键，因为当时不存在一个同时与它们两个连接的原子。通过在第一个原子和第三个原子之间创建一个临时的化学键，使得第三个原子成为了这样一个原子。
2A
任务：GRU
排列组 [A]
2024算法竞赛，第二轮。限制：1024 MB，15秒。2024年3月12日
在这个任务中，我们将处理n元素的排列。每一个这样的排列都是一个由1到n（包括）的n个不同自然数构成的序列。排列a1, a2, ..., an和排列b1, b2, ..., bn的组合是排列ab1, ab2, ..., abn。在排列p1, p2, ..., pn中，任何一对索引(i, j)（i < j且pi > pj）都称为一个逆序。
Bajtek是n元素排列的大粉丝。他如此喜爱它们，以至于他甚至有k个最喜爱的排列。他决定开始在纸上写下所有可能通过组合他的最喜爱的排列（以任何顺序和可能多次使用其中的一些）得到的排列，同时仔细确保不重复写下任何排列。
不出所料，他很快就用完了纸。然后Bajtek想知道：如果他写下了所有可达到的排列，它们平均会有多少逆序？
帮助他并编写一个程序来计算这个值。更准确地说，你的任务是给出这个值模1 000 000 007的结果（关于输出更多信息见输出部分）。
输入
输入的第一行包含两个整数n和k（1 ≤ n, k ≤ 3000），分别表示排列的长度和Bajtek的最爱排列的数量。
接下来的k行包含了这些排列。其中第i行包含n个不同的整数ai,1, ai,2, ..., ai,n（1 ≤ ai,j ≤ n），等于Bajtek的第i个最爱排列。
输出
输出只有一行，应该包含所有Bajtek可能写下的排列中平均逆序数的一个整数，给出模1 000 000 007的结果。
形式上，假设结果等于p/q，其中q ≠ 0且p和q的最大公约数为1。然后应该输出一个数p · q^(-1)（模1 000 000 007），其中q^(-1)是集合1, 2, ..., 1 000 000 006中唯一一个满足q · q^(-1) ≡ 1（模1 000 000 007）的数。
可以证明，对于所有满足任务条件的测试用例，结果是一个分母在约简形式下不被1 000 000 007整除的有理数。
示例
对于输入数据：
3 1
2 3 1
正确的结果是：
333333337
而对于输入数据：
5 2
2 1 3 4 5
2 3 4 5 1
正确的结果是：
5
示例解释：在第一个示例测试中，Bajtek将写下排列{1, 2, 3}，有0个逆序，{2, 3, 1}，有两个逆序，以及{3, 1, 2}，也有两个逆序。因此，逆序的平均数量是4/3。由于3^(-1) ≡ 333333336（模1 000 000 007），我们有333333336 · 4 ≡ 1333333344 ≡ 333333337（模1 000 000 007）。
在第二个示例测试中，Bajtek将写下所有5个元素的排列。容易证明，它们平均有正好5个逆序。
3C
任务：OBR
画作 [C]
2024算法竞赛，第三轮。限制：1024 MB，2秒。2024年3月13日
Bajtazar刚搬进新公寓。在已经用来自各种朗诵比赛和Bajtocja定时呼啦比赛的奖杯装饰了书架后，他注意到一面墙完全空着。他不喜欢这样，所以想要用画作填满它。
Bajtazar的墙是一个h×w米的矩形。附近的艺术经纪人，是Bajtazar的好朋友，提供n种类型的画作，每种类型的画作都有无限数量。同一类型的所有画作尺寸完全相同——第i种类型的画作总是边长为di米的正方形。有趣的是，对于任意两个不同的di值，一个总是另一个的倍数。
对Bajtazar来说，画作的价格不是问题（毕竟在定时呼啦比赛中的奖金相当丰厚），但他希望确保墙上没有任何空白处。为此，他决定购买一定数量的画作并挂在墙上以完全覆盖它。当然，画作不能相互覆盖，但可以相互接触边缘。Bajtazar不想多次往返艺术经纪人那里——因此他希望尽可能少地购买画作。帮助他编写一个程序，计算他需要购买的画作数量，或者判断覆盖整面墙是否不可能。
输入
输入的第一行包含两个整数h和w（1 ≤ h, w ≤ 10^9）——Bajtazar的墙的尺寸。
输入的第二行包含一个整数n（1 ≤ n ≤ 30）——画作类型的数量。
输入的第三行包含n个不同的整数d1, d2, ..., dn（1 ≤ di ≤ 10^9；di < di+1；di+1是di的倍数）——各类型画作的尺寸。
输出
如果覆盖墙面是可能的，输出的一行应包含一个整数，表示覆盖墙面所需的最少画作数量。否则，这一行应该是-1。
示例
对于输入数据：
6 10
3
1 3 6
正确的结果是：
9
而对于输入数据：
3 3
1
2
正确的结果是：
-1
示例解释：在第一个示例测试中，Bajtazar可以用九幅画（六幅1×1尺寸，两幅3×3尺寸和一幅6×6尺寸）覆盖墙面，例如以以下方式：
在第二个示例测试中，不可能精确覆盖墙面。
3B
任务：ZEL
软糖 [B]
2024年算法对抗赛，第三轮。限制：1024 MB，3秒。2024年3月13日
Bajtek非常喜欢软糖。在新开的商店里（这家店只卖软糖），可以购买多达n种类型的软糖——第i种类型的软糖由软糖的颜色、重量（以bajtogram为单位）及价格（以bajtogrosz为单位）来描述。软糖是单独出售的。软糖的颜色用从1到k的数字表示。商店里有每种类型的软糖无限供应。
除了软糖，Bajtek还非常喜欢颜色美学。他只会在每种颜色的软糖都买相同数量的情况下，才会购买一些软糖的多重集合。
除了软糖和颜色美学，Bajtek还非常喜欢数字。对于区间[0, m − 1]内的每一个整数r，他都想知道，为了购买一个软糖的多重集合，在这个集合中所有软糖的总重量除以m的余数为r时，他至少需要花费多少bajtogrosz。请帮助他，编写一个程序来计算这些所需的值！
输入
在标准输入的第一行中有三个整数n, k和m（1 ≤ n, k, m ≤ 7000），分别表示软糖的销售种类数、软糖的颜色数以及上述的m值。
在接下来的n行中，每行包含三个整数。第i行的数字分别是ki, mi和ci（1 ≤ ki ≤ k; 1 ≤ mi ≤ m; 1 ≤ ci ≤ 10^9）——分别代表第i种软糖的颜色、重量（以bajtogram为单位）和价格（以bajtogrosz为单位）。
输出
输出应该包含m行。在其中的第i行，应该有一个整数——Bajtek可以购买的、使得软糖总重量除以m的余数为i−1的软糖多重集合的最小总价格。如果这样的多重集合不存在，那么在这一行应该输出数字−1。
例子
对于输入：
3 2 6
1 2 1
2 2 2
1 1 5
正确的结果是：
0
10
6
7
3
13
而对于输入：
2 3 3
1 1 1
3 1 1
正确的结果是：
0
-1
-1
示例解释：在第一个示例测试中：
·为了使软糖总重量能被m = 6整除，Bajtek可以不购买任何软糖——这样他根本不需要花费钱。
·为了使软糖总重量除以6的余数为1，Bajtek应该购买一个第一种类型的软糖，两个第二种类型的软糖，以及一个第三种类型的软糖。这样他将支付10 bajtogrosz，并获得两种颜色的软糖，总重量等于7 bajtogram。
·为了使软糖总重量除以6的余数为5，Bajtek应该购买两个第一种类型的软糖，三个第二种类型的软糖，以及一个第三种类型的软糖。
在第二个示例测试中，没有提供第二种颜色的软糖——唯一满足Bajtek要求的解决方案是不购买任何软糖。
3A
任务：SPL
序列交织 [A]
2024年算法对抗赛，第三轮。限制：1024 MB，9秒。2024年3月13日
在数列C中，我们将每一个非空且连续的子序列称为区间。特别地，这意味着每个长度为k的序列有k(k+1)/2个区间，因为每个区间都是由它的起始和结束位置确定的。
给定一个整数序列，我们将其最长严格单调区间的长度称为序列的稳定性。具体而言，序列[c1, c2, ... , ck]的稳定性是最大的整数s，使得存在索引i（1 ≤ i ≤ k - s + 1），满足ci < ci+1 < ... < ci+s-1或ci > ci+1 > ... > ci+s-1。例如序列[8, 6, 1, 3, 5, 7, 4, 2]的稳定性为4，因为它包含一个严格单调区间[1, 3, 5, 7]，而不存在更长的。
两个序列A和B的交织是指一个长度为|A| + |B|的序列，该序列包含一个子序列（不一定连续）等于A，且所有不在该子序列中的元素构成序列B。例如，序列[1, 2, 3]和[4, 5]的交织序列包括[1, 4, 2, 5, 3]、[4, 5, 1, 2, 3]和[4, 1, 5, 2, 3]，但不包括[1, 2, 3, 4, 3]和[1, 2, 3, 5, 4]。
最终，对于整数序列A和B，我们用f(A, B)表示它们的交织可能具有的最小稳定性。
给定两个整数序列A和B，长度分别为n和m，你的任务是对每一个整数x从1到n + m，计算满足条件的(A′, B′)对的数量，使得A′是A的一个区间，B′是B的一个区间，并且满足f(A′, B′) = x。由于得到的数值可能非常大，只需给出它们除以10^9 + 7的余数即可。
可以假设序列A和B中的所有元素都是互不相同的。
输入
输入的第一行包含两个整数n和m（1 ≤ n, m ≤ 300,000），分别代表序列A和B的长度。
输入的第二行包含n个整数A1, A2, ..., An（1 ≤ Ai ≤ n + m）——序列A。
输入的第三行包含m个整数B1, B2, ..., Bm（1 ≤ Bi ≤ n + m）——序列B。
保证序列A和B中的所有元素都是唯一的。换句话说，序列A和B的连接构成了从1到n + m的数的一个排列。
输出
输出仅一行，包含n + m个由单个空格分隔的数字；其中第i个数字等于满足条件的(A′, B′)对的数量，使得A′是A的区间，B′是B的区间，并且f(A′, B′) = i，结果对10^9 + 7取模。
示例
对于输入：
5 3
1 2 5 7 4
8 3 6
正确结果为：
0 84 6 0 0 0 0 0
示例解释：对于整个序列作为区间的情况，f([1, 2, 5, 7, 4], [8, 3, 6]) = 2，其交织序列稳定性等于2的一个
4C
任务：LAM
谜题 3 [C]
2024年算法对战，第四轮。限制：1024 MB，2秒。2024年3月14日
Bajtek喜欢玩手机游戏。然而，他经常感到烦恼的是那些出现的广告中，玩家表现得非常糟糕，这是为了激发观看者的挫败感和游玩欲望。其中一则广告（你们可能也见过）给Bajtek留下了深刻的印象。
因为灵感可以来自一切，Bajtek决定基于上述游戏创造一个任务。他将选择一个目标彩色棋盘，尺寸为n×m，游戏开始时的棋盘为n×m，没有任何颜色。每次移动，他可以选择一行或一列，并用他选择的颜色涂满（注意，这比上面图片中的游戏给予的更多自由，那里的行和列有指定的颜色）。为了正式化任务，他用英文字母的大写表示所有颜色。你能帮他写一个程序，对于他指定的每个棋盘，给出一个正确创建目标颜色布局的移动序列吗？你可以假设你将获得的输入数据中，这个目标可以在最多n + m步内实现。
输入
标准输入的第一行包含两个整数n和m（1 ≤ n, m ≤ 2000），分别代表棋盘的高度和宽度。
接下来的n行每行有m个字符，每个字符都是英文字母的大写；第i行的第j个字符表示位于第i行和第j列的棋盘格子的目标颜色。
保证给定的颜色布局可以通过题目描述中说的最多n+m步骤序列来实现。
输出
输出的第一行应该包含一个整数r（1 ≤ r ≤ n+m），表示你想要进行的移动次数。接下来的r行中，每行应该描述一个移动。
一个移动的描述应该以字符‘R’或‘K’开头，表示你想要涂色的是行还是列（其中‘R’表示行，‘K’表示列）。之后，跟着一个空格，应该是你想要涂色的行或列的编号。行从上到下用1到n的数字编号，列则从左到右用1到m的数字编号。然后，再跟着一个空格，应该是一个大写的英文字母，表示你想要将选定的行或列涂成的颜色。
注意，你不需要最小化移动次数——只要确保最多不超过n + m。
示例
对于输入数据：
5 5
AAPAA
APPAA
AAPAA
AAPAA
APPPA
一个正确的结果可能是：
10
R 1 Z
K 4 A
K 2 P
R 5 P
R 4 A
R 3 A
R 1 A
K 5 A
K 3 P
K 1 A
而对于输入数据：
2 3
AAA
PPP
一个正确的结果可能是：
2
R 2 P
R 1 A
示例解释：如果在第一个示例测试中，我们假设字母‘P’代表绿色，字母‘A’代表黄色，而字母‘Z’代表蓝色，那么选定的移动序列将以以下方式涂色棋盘：
4B
任务：DES
空降3 [B]
2024年算法战斗，第四轮。限制：1024 MB，4秒。2024年3月14日
巴杰托邦（再次）计划攻击比托邦。精英特种部队巴杰特隆拥有n名士兵，他们在今天早晨的集合中排成一列。负责执行空降的将军巴杰萨尔，从左到右用1到n的数字编号他们的位置。
每个士兵要么准备好执行空降，要么因为法律修正案需要额外训练。巴杰萨尔将军希望所有准备好空降的士兵能形成队列的一个连续区间。更正式地，他希望不存在这样的士兵位置三元组1 ≤ i < j < k ≤ n，使得第i位和第k位士兵准备好空降，而第j位士兵没有准备好。
由于这个条件可能不会默认满足，巴杰萨尔将下达m个命令。在第i个命令中，他将命令位于位置ai和bi的士兵相互通讯以交换他们的位置。只有当ai位士兵准备好空降，而bi位士兵没有准备好时，士兵们才会交换位置。
巴杰萨尔已经选择了一系列命令并打算下达它们。但他不知道有多少士兵准备好空降或他们处于哪些位置。因此，对于从1到n的每一个整数k，他想要解决以下问题：考虑所有n中恰好有k名士兵准备好空降的初始配置。在执行所有命令后，有多少配置满足巴杰萨尔的条件（即，准备好空降的士兵形成队列的一个连续区间）？帮助他计算他所寻求的值！
注意：由于算法战斗中有许多初学者程序员参加，我们决定不用大数字来折磨你们。因此，对于每个k，只需提供可能性数量除以2的余数。
输入
输入的第一行包含两个整数n和m（2 ≤ n ≤ 35；1 ≤ m ≤ 1000），分别表示队列中的士兵数量和命令数量。
接下来的m行包含命令的描述；其中的第i行包含两个整数ai和bi（1 ≤ ai, bi ≤ n; ai ≠ bi），如任务描述中所述。
输出
输出的第一行和唯一一行应该包含n个用单个空格分隔的整数；其中的第k个应该等于初始配置中恰好有k名士兵准备好空降，并且在执行所有命令后，所有准备好的士兵形成一个连续区间的配置的数量除以2的余数。
示例
对于输入：
4 4
4 1
1 2
3 4
1 4
正确的结果是：
0 0 1 1
示例解释：如果最初只有一个士兵准备好空降，那么他肯定会形成（一个元素的）连续区间。但不存在两个士兵准备好空降并且最终站在彼此旁边的情况。
考虑所有除第二个士兵外都准备好空降的情况。第一个命令不会影响士兵的位置。在第二个命令后，因为第一个士兵准备好
4A
任务：KOL
彩色森林 [A]
2024年算法战斗，第四轮。限制：1024 MB，8秒。2024年3月14日
为了庆祝π日，Bajtazar收到了一个森林作为礼物（一个无向无环图）包含n个顶点。
在这个森林中，顶点被编号为从1到n，边被赋予正整数长度。
此外，每个顶点都有一个用整数描述的颜色。最初，所有顶点的颜色都是0。
因为是你送给Bajtazar这份礼物，现在你的任务是回答Bajtazar关于这个森林的查询。每个查询都是以下几种类型之一：
- 1 ai bi di - Bajtazar在顶点ai和bi之间添加一条长度为di的无向边。保证添加这条边后图仍然不会有环。
- 2 ai bi - Bajtazar移除连接顶点ai和bi的边。
- 3 vi zi ki - Bajtazar将从顶点vi可达且距离不超过zi的所有顶点重新涂色为颜色ki。这里的距离是指两个顶点之间简单路径上的边长度之和。
- 4 ui - Bajtazar询问顶点ui的当前颜色。
输入
输入的第一行包含三个整数n, m和q (2 ≤ n ≤ 200,000; 0 ≤ m ≤ n − 1; 1 ≤ q ≤ 200,000)，分别表示森林中的顶点数量、最初存在的边数量以及查询的数量。
接下来的m行中包含森林中边的描述。其中的第i行包含三个整数ai, bi和di (1 ≤ ai, bi ≤ n; 1 ≤ di ≤ 10^9)，表示顶点ai和bi之间连接着一条长度为di的边。
接下来的q行中包含查询的描述，格式如任务描述中所示。所有查询中都满足1 ≤ ai, bi, vi, ui ≤ n, 1 ≤ di ≤ 10^9, 0 ≤ zi ≤ 10^15以及1 ≤ ki ≤ 10^9。
保证给出的m条边描述了一个合法的森林，且每次修改后图仍然是一个合法的森林，并且永远不会有删除当前不存在的边的查询。
还保证至少会有一个第四类型的查询。
输出
输出应该包含和输入中第四类型查询数量一样多的行。每行包含一个整数——Bajtazar询问的顶点的颜色。
示例
对于输入：
4 2 9
1 2 2
3 2 5
4 2
3 2 2 5
4 1
3 2 4 3
4 1
4 3
2 2 1
1 1 4 1
4 4
正确的输出是：
0
5
3
0
0
子任务
- 在一些测试组中，没有第一种和第二种类型的查询，并且满足m = n − 1。
- 在一些测试组中，所有第三种类型的查询中zi = 10^15。
对于每种上述情况，至少存在一个满足条件的组。这些组对于两个条件可以是相交的也可以是不相交的。
5C1
任务：BUC
非常喜爱的序列 [C]
算法竞赛 2024，第五轮。限制：1024 MB，6 s。2024年3月15日
3SUM 是一个著名的算法问题，给定一个整数序列 c1, c2, ... , cm，需要找到三个索引 i < j < k，使得 ci + cj + ck = 0。
对于任意整数序列，在 O(m^2) 之外没有已知的更好的解决方案。
幸运的是，Bajtek 不知道这一点，并决定为他的非常喜爱的序列解决这个问题。
Bajtek 的喜爱的序列由 n 个整数 a1, a2, ... , an 组成。通过考虑 Bajtek 喜爱的序列的所有 n(n+1)/2 个连续区间，计算它们的元素之和，并将所有这些和（包括重复）放在一个序列中（按区间起始索引的升序排列，如果起始索引相同，则按结束索引的升序排列），得到 Bajtek 的非常喜爱的序列。
为了增加难度，Bajtek 不仅仅是寻找满足 i < j < k 的三个索引的组合。他想知道正好有多少个这样的索引三元组，它们对应的元素之和为零。
帮助他编写一个程序来计算这样的三元组数量吧！
输入
在标准输入的第一行中有一个整数 n (1 ≤ n ≤ 500)，表示 Bajtek 喜爱的序列的长度。
下一行包含 n 个整数 ai (|ai| ≤ 20,000)，代表 Bajtek 喜爱的序列的连续元素。
输出
在标准输出的第一行和唯一一行中应该有一个整数 —— 对应于 Bajtek 非常喜爱的序列中的和为零的三个索引的组合的数量。
示例
对于输入：
3
7 -4 -2
正确的输出是：
1
对于输入：
10
0 0 0 0 0 0 0 0 0 0
正确的输出是：
26235
示例解释：在第一个示例测试中，非常喜爱的序列是 [7, 3, 1, -4, -6, -2]，唯一的不同元素三元组其和为 0 是 3 + 1 + (-4)，因此答案是 1。
在第二个示例测试中，Bajtek 的非常喜爱的序列由五十五个零组成。对于任意三个索引 i < j < k，它们对应的元素之和等于 0，这样的三元组有 26,235 个。
5C2
任务：ZAR
灯泡 [C]
算法竞赛 2024，第五轮。限制：1024 MB，3 s。2024年3月15日
Bajtazar 拥有编号为 1 到 n 的 n 个灯泡以及 m 个开关。每个灯泡最初可能是开着的或者关着的。每个开关影响一对灯泡。使用它会改变它们的状态，但仅当它们处于相同状态时——都是开着的或都是关着的。如果它们处于不同状态，按下开关不会有任何效果。
Bajtazar 想知道，通过任意次数、任意顺序使用开关（可能多次使用某些开关），他能达到多少种不同的灯泡开关状态配置。如果在两种配置中有任意一个灯泡在一种配置中是开着的而在另一种配置中是关着的，则认为这两种配置是不同的。由于结果可能很大，只需给出其除以 10^9 + 7 的余数。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n ≤ 200,000; 0 ≤ m ≤ 400,000)，分别表示灯泡的数量和开关的数量。
输入的第二行包含 n 个数字 ci (ci ∈ {0, 1})，用单个空格分隔。如果 ci = 1，则表示第 i 个灯泡最初是开着的。否则（ci = 0），第 i 个灯泡最初是关着的。
接下来的 m 行描述开关；其中第 i 行包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n; ai ≠ bi) - 表示第 i 个开关影响的灯泡编号。
你可以假设开关影响不同的无序灯泡对。更正式地说，对于任意一对不同的索引 i, j 在 1 到 m 之间，有 (ai, bi) ≠ (aj, bj) 且 (ai, bi) ≠ (bj, ai)。
输出
输出的第一行和唯一一行应该包含除以 10^9 + 7 后的可达到的灯泡开关状态配置的数量的余数。
示例
对于输入：
5 4
1 0 1 1 0
1 3
5 3
4 2
1 5
正确的输出是：
4
示例解释：可达到的最终灯泡状态为 10110, 00010, 00111 和 10011。
5B1
任务：DZI
除数 [B]
算法竞赛 2024，第五轮。限制：1024 MB，15 s。2024年3月15日
评委选定了一个整数 x 从区间 [1, n]。你的任务是猜出这个数字。为了不让你完全摸黑，你可以提出询问。在每次询问中，你可以提供一个整数 y 从区间 [0, c]，然后我们会告诉你 x + y 的正除数的数量。
为了使任务更具挑战性，在单次程序运行中，你将需要解决 t 个测试案例。你可以在这些测试案例中总共提出的询问数量受到 q 的限制。
交流
这是一个交互式任务。你需要写一个程序来与评委库通信，使用提供的库。要使用库，你需要在你的程序中包括：
- C++：#include "dzilib.h"
- Python：from dzilib import GetT, GetN, GetQ, GetC, Ask, Answer
库提供以下函数：
- GetT() - 返回测试案例的数量 t。
- GetN() - 返回隐藏值 x 的限制 n。
- GetQ() - 返回你在所有测试案例中可以提出的询问总数的限制 q。
- GetC() - 返回你可以提供的 y 值的限制 c。
- Ask(y) - 返回隐藏数字 x 增加 y 后的正除数数量。必须满足 0 ≤ y ≤ c。
- Answer(z) - 通知库你认为隐藏的值 x 为 z。没有返回值（在 C++ 中，函数类型为 void）。
在 Python 中，库函数的所有参数和返回值都是整数类型。在 C++ 中，函数接收和返回的类型与提供的示例库中的相同，有关更多信息请参阅实验部分。
在程序运行的任何时刻（除了程序结束时），都会有一个测试案例处于活动状态。程序开始运行时，第一个测试案例立即激活。当一个测试案例处于活动状态时，你可以使用 Ask 函数提出询问。当你确定知道隐藏的 x 值时，你可以通过 Answer 函数提供它，然后库将进行验证。如果提供的值不正确，库将终止程序运行，并返回“错误答案”的判决。如果参数值正确，则函数结束；如果解决的测试案例不是最后一个，则立即激活下一个。在回答了最后一个测试案例后，你应该结束程序的运行。如果你不这样做，并尝试使用 Ask 或 Answer 函数，你将收到“错误答案”的判决。
你可以在程序运行的任何时刻使用 GetT, GetN, GetQ, 以及 GetC 函数，它们返回的值不会改变。这些函数不计入询问限制，但会消耗处理器时间。
q 值仅限制 Ask 函数的调用次数。当你超过允许的总询问次数时，库将终止程序运行，并返回“错误答案”的判决。
不应从标准输入读取任何数据，也不应向标准输出打印任何内容。故意尝试影响评审库内部运行的尝试是禁止的。
库
所有测试中的隐藏值 x 及其顺序都是预先设定的。这意味着，与你的程序通信的库不会是恶意的，也不会根据你的程序的操作调整其行为。
任务说明中给出的限制仅适用于你的程序使用的时间和内存。库的运行时间和使用的内存可能取决于测试和你的程序的确切行为。因此，SIO2 中的时间和内存限制比任务说明中给出的稍大。
测试案例示例
在示例测试中，t = 2, n = 10^6, q = 10^4, c = 10^15，隐藏的值依次是 1000 和 1，与库的示例通信可能如下：
| 调用函数 |
结果 |
描述 |
| GetT() |
2 |
t = 2。 |
| GetN() |
1,000,000 |
n = 10^6。 |
| GetQ() |
10,000 |
q = 10^4。 |
| GetC() |
1,000,000,000,000,000 |
c = 10^15。 |
| Ask(1) |
8 |
x + 1 有 8 个正除数：1, 7, 11, 13, 77, 91, 143, 1001。 |
| Ask(24) |
11 |
x + 24 有 11 个正除数：1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024。 |
| Answer(1000) |
- |
提供正确答案，激活下一个测试案例。 |
| GetT() |
2 |
允许的查询 - 返回值不变。 |
| Answer(1) |
- |
提供正确答案，结束最后一个测试案例。提供答案后应结束程序运行。 |
提出了 2 个 Ask 查询，符合 10,000 查询的限制。记住，计算的是所有测试案例中的总查询数量。
5B2
任务：KRA
水龙头 [B]
算法竞赛 2024，第五轮。限制：1024 MB，4 秒。2024年3月15日
Radek及其朋友们的公司老板Radek尝试淹没竞争对手Mati及其合伙人公司的所有文件架。为了完美地进行破坏，他请他的朋友，水管工Janusz，在每个文件架上方安装微小的水龙头。
为简化，Mati公司的文件架可以用平面上的线段表示。每个文件架是一对点 (li, hi) 和 (ri, hi) 之间的线段。由水管工安装的水龙头是点，坐标为 ((li+ri)/2, hi + 0.5)。此房间的地板由OX轴表示。
当打开第 i 个文件架上方的水龙头时，该文件架将被淹没。自然地，水开始从文件架的边缘垂直向下滴落，并可能淹没下一个文件架或滴落到带有自然排水系统的地板上。
打开一个水龙头后水流向下的可视化，在第二个示例测试中。
Radek将按照某个固定的顺序考虑水龙头。当他考虑第 i 个水龙头时，仅当第 i 个文件架尚未被淹没时才会打开它。
Radek尚未决定他将按哪种顺序考虑水龙头。他将从 n! 个顺序中随机选择一个，每个顺序的概率相同。现在Radek想知道，他平均需要打开多少个水龙头。
你的任务是回答Radek的问题，并给出模 10^9 + 7 的答案。形式上，设结果等于 p/q，其中 q ≠ 0 且 GCD(p, q) = 1。那么应该输出一个数字 p·q^(-1) (mod 10^9+7)，其中 q^(-1) 是集合 {1, 2, ..., 10^9 + 6} 中唯一一个使得 q · q^(-1) ≡ 1 (mod 10^9 + 7) 的数字。
可以证明，对于所有满足任务条件的测试，结果是一个分母在约简后不可被 10^9 + 7 整除的有理数。
输入
输入的第一行包含一个自然数 n (1 ≤ n ≤ 500,000)，表示Mati公司的文件架数量。
接下来的 n 行包含文件架的描述。第 i 行包含两个自然数 li, ri (1 ≤ li < ri ≤ 2·n)，如任务描述中所述。为简化，我们假设 hi = i。
可以假设所有的数字 li, ri 是两两不同的——数字 li, ri 构成了从 1 到 2·n 的一个排列。
输出
标准输出的唯一一行应该包含一个数字，即Radek需要打开的水龙头的平均数量，模 10^9 + 7。
示例
对于输入：
3
4 6
1 3
2 5
正确的输出是：
2
而对于输入：
5
2 9
3 4
1 8
6 10
5 7
正确的输出是：
233333338
示例解释：考虑Radek在第一个示例测试中分析水龙头的所有可能顺序：
- 对于顺序 1, 2, 3，他将打开所有 3 个水龙头。
- 对于顺序 1, 3, 2，他将打开第一个和第三个水龙头。打开第三个水龙头后，水也会淹没第
二个文件架，因此不需要再打开第二个水龙头。
- 对于顺序 2, 1, 3，他将打开所有 3 个水龙头。
- 对于顺序 2, 3, 1，他将打开第二个和第三个水龙头。打开第三个水龙头后，水也会淹没第一个文件架，因此不需要再打开第一个水龙头。
- 对于顺序 3, 1, 2 和 3, 2, 1，他只会打开第三个水龙头。打开后，所有文件架都将被淹没，因此不需要再打开其他水龙头。
因此，Radek平均需要打开 1/6·(3 + 2 + 3 + 2 + 1 + 1) = 2 个水龙头。
在第二个示例测试中，Radek平均需要打开 91/30 个水龙头。由于 30^(-1) ≡ 233333335 (mod 10^9 + 7)，因此我们有 91 · 233333335 ≡ 21233333485 ≡ 233333338 (mod 10^9 + 7)。
5A1
任务：AUT
高速公路 2 [A]
算法竞赛 2024，第五轮。限制：1024 MB，4 秒。2024年3月15日
经过多年无意义的战争后，Bajtocja和Bitocja终于签订了和平条约。作为两国首都之间最终和解的标志，一条高速公路被建造了。你被指定为负责从Bajtocja向Bitocja方向的高速公路管理者。
目前，高速公路上有 m 个收费站，按从 1 到 m 的顺序编号。第一个收费站位于高速公路的起点，最后一个位于终点。通过某个收费站的费用可能会在一天中的不同时间有所不同。一天被分为 n 个小时，编号为 1 到 n。当前通过 j 号收费站的费用在 i 小时为 ci,j bajtalars。其中一些费用可能为 0（通过收费站是免费的）或甚至为负数（司机在通过收费站时将获得 −ci,j bajtalars）。
整个高速公路足够短，以至于可以在一小时内通过。但当然，不需要这么急——在旅途中可以随意停留。然而，不能在高速公路上过夜；必须在同一天通过所有收费站。
显然，司机希望以尽可能低的成本通过高速公路。通过 f(i, j) 表示如果司机在第 i 小时通过第一个收费站，而在第 j 小时通过最后一个收费站，那么通过整个高速公路的最小可能成本。所有的 f(i, j) 值已经在和平条约中由两国政府确定，因此作为高速公路的管理者，你无法更改它们。但是，你可以自由修改通过各个收费站的收费标准，或者甚至完全关闭一些收费站，只要第一个和最后一个收费站保持开放，f(i, j) 的值不变，以及你设定的所有费用都是一定数量的 bajtalars 的整数倍。
为了最小化高速公路的维护成本，你希望关闭尽可能多的收费站。确定必须保持开放的收费站的最小数量，以便仍然满足条约的条件。
收费模式重组项目将分为两个阶段。在第一阶段——初步设计阶段——只需找到最优的收费站数量即可。但在第二阶段——项目实施阶段——你还需要提供保留收费站的整个示例收费标准。
输入
输入的第一行包含三个整数 n, m 和 q (2 ≤ n, m ≤ 30,000; n·m ≤ 300,000; q ∈ {0, 1})，分别表示一天中的小时数，高速公路上当前的收费站数量，以及描述项目阶段的位。q 值为 0 表示项目处于初步设计阶段，而 q 值为 1 表示项目已进入实施阶段。
接下来的 n 行包含当前收费信息；第 i 行包含 m 个整数 ci,1, ci,2, ..., ci,m (−10^6 ≤ ci,j ≤ 10^6)。ci,j 的值表示在第 i 小时通过第 j 个收费站的费用，以 bajtalars 表示。如果 ci,j 的值是负数，则通过第 j 个收费站的费用会给司机 −ci,j bajtalars。
输出
输出的第一行应包含一个整数 k (2 ≤ k ≤ m)，表示为了不更改任何 f(i, j) 的值而需要保留在高速
公路上的最小收费站数量。如果 q = 0，输出应只包含这一个数字的一行。
如果 q = 1，则接下来的 n 行应包含符合任务条件的示例最优收费标准。第 i 行应包含 k 个整数 di,1, di,2, ..., di,k (−10^12 ≤ di,j ≤ 10^12)。di,j 的值表示在第 i 小时通过保留的第 j 个收费站的新费用。
可以证明，对于任务的限制，总是可以确定绝对值不超过 10^12 的整数费用。
示例
对于输入：
3 6 1
-1 0 4 0 -3 0
-4 1 5 2 -5 2
-5 2 3 0 -2 2
一个可能的正确输出是：
3
0 0 0
0 1 0
0 0 0
而对于输入：
5 7 0
0 0 0 8 0 0 0
0 7 6 5 9 7 0
0 0 0 5 9 6 0
9 4 0 4 4 7 0
0 0 0 9 8 6 0
正确的输出是：
3
示例解释：在第一个示例测试中，通过高速公路的各个最小成本分别为：
- f(1, 1) = (−1) + 0 + 4 + 0 + (−3) + 0 = 0,
- f(1, 2) = (−1) + 0 + 4 + 0 + (−5) + 2 = 0,
- f(1, 3) = (−1) + 0 + 4 + 0 + (−5) + 2 = 0,
- f(2, 2) = (−4) + 1 + 5 + 2 + (−5) + 2 = 1,
- f(2, 3) = (−4) + 1 + 3 + 0 + (−2) + 2 = 0,
- f(3, 3) = (−5) + 2 + 3 + 0 + (−2) + 2 = 0。
无法通过使用两个收费站实现相同的通过成本。请注意，即使在提议的 di,j 费用下，第一个和最后一个收费站没有收取任何费用，它们也不能被关闭。
在第二个示例测试中，输出不包含新的收费标准提议，因为收费模式重组项目仍处于初步设计阶段。
5A2
任务：MON
硬币 [A]
算法竞赛 2024，第五轮。限制：1024 MB，25 s。2024年3月15日
Natalia和Cezary喜欢玩游戏，尤其是他们自己发明的游戏。他们决定在自己面前排列一系列的硬币堆，每堆有m枚硬币，每枚硬币要么是蓝色，要么是红色。Natalia在她的回合中可以选择任何一枚蓝色硬币，并将其连同堆中所有位于它上面的硬币一起从游戏中移除。类似地，在他的回合中，Cezary可以选择任何一枚红色硬币，并将其以及同一堆中所有位于它上面的硬币从游戏中移除。
玩家将轮流进行操作，谁不能执行合法的操作就输了——也就是说，当他的所有硬币都已经被之前移除出游戏时。
现在他们已经知道了规则，他们需要决定游戏的初始状态——一系列d堆，每堆确切地包含m枚硬币。Natalia和Cezary都不希望拥有不公平的优势，所以他们一致认为，硬币堆的序列应该是公平的。如果假设Natalia和Cezary都采取最优策略，那么不执行首个操作的玩家将会获胜的硬币堆序列被称为公平的。因此，如果Natalia执行首个操作，那么在最优策略下Cezary将会获胜，反之亦然：如果Cezary开始，那么Natalia将会获胜。
这对已经排列了前k堆硬币，每堆m枚。现在他们正在考虑如何完成这个硬币堆序列。他们已经得出结论，游戏中没有必要有超过n堆硬币。
帮助他们，对于区间[k, n]中的每个数字d，说出有多少不同的公平的硬币堆序列包含m枚硬币，以他们已经排列的硬币堆序列开始。如果存在i∈[1, d]和j∈[1, m]，使得在这两个序列中，第i堆的第j枚硬币在一个序列中是蓝色，在另一个序列中是红色，则认为两个硬币堆序列是不同的。
由于这些结果可能非常大，只需提供它们除以10^9 + 7的余数。
输入
标准输入的第一行包含三个整数n, m和k (1 ≤ n ≤ 32; 1 ≤ m ≤ 24; 0 ≤ k ≤ n)，分别表示堆数的限制，每堆中的硬币数以及已经创建的堆数。
接下来的k行包含已经排列的堆的描述；其中第i行包含一个长度确切为m的'N'和'C'的字符串，表示第i堆中从底部开始的硬币的颜色。如果这个字符串的第j个字符是'N'，那么第i堆中从底部开始的第j枚硬币是蓝色的。否则，这个字符是'C'，那么这枚硬币是红色的。
输出
输出的唯一一行应该包含n - k + 1个整数，其中第i个数字应该是将序列扩展i - 1堆以使最终的堆序列公平的方法数除以10^9 + 7的余数。
示例
对于输入：
3 3 1
CCN
正确的结果是：
0 1 3
对于输入：
2 1 0
正确的结果是：
1 0 2
对于输入：
4 2 4
CN
NC
CC
NN
正确的结果是：
1
示例解释：在第一个示例测试中，如果我们不添加任何堆，那么单元素序列将不会是公平的。我们可以添加堆NNC - 这样的两堆序列已经是公平的。我们可以通过三种方式添加两个堆：[CCN, NNN]、[NNN, CCN]、[NCN, NCN]。
