给定$$$n,m$$$，求 $$$$$$ \sum_{i=1}^n\sum_{j=1}^m\frac{\gcd(i,j)}{ij}\ mod\ 998244353 $$$$$$
第一行，一个数字 $$$t(1\le t \le 10^4)$$$，代表数据组数。
对于每组数据，两个整数 $$$n,m(1\le n,m \le10^6)$$$。
对于每组数据，输出一行正整数代表答案。
可以证明答案一定可以表示成 $$$\frac{q}{p}$$$，其中$$$q$$$为正整数，$$$p$$$为正整数，且存在一个正整数$$$p^{(-1)}$$$，使得 $$$p^{(-1)}×p≡1\ mod\ 998244353$$$，即$$$p$$$在模$$$998244353$$$下一定存在逆元，你只需输出 $$$q×p^{(-1)}$$$模$$$998244353$$$的值即可。
5 1 3 22 13 1000 1000 114 5144 1000000 1000000
831870296 840003385 865445419 863853786 434780206
对于$$$n=1,m=3$$$，结果为$$$1+\frac{1}{2}+\frac{1}{3}=\frac{11}{6}$$$，$$$11·6^{-1}\ mod \ 998244353 = 831870296$$$。
有一个无限长度的二进制字符串，字符串下标从$$$0$$$开始，初始时该字符串每一位均为$$$0$$$，即字符串为'"000...000..."'。
这里有三个对于字符串的操作:
+ x1 x2：将字符串$$$[x1,x2]$$$位的所有数置为$$$1$$$。
- x1 x2：将字符串$$$[x1,x2]$$$位的所有数置为$$$0$$$。
? k：查询字符串中第$$$k$$$个$$$0$$$的位置（$$$k$$$从$$$1$$$开始）。
第一行，一个正整数 $$$q(1\le q \le 3⋅10^5)$$$，表示操作的次数。
下面的$$$q$$$行，一行一个合法的操作。
对于所有操作，保证 $$$0 \le x_1 \le x_2 \le10^{18}$$$, $$$1\le k \le 10^{18}$$$。
对于每个查询，输出一个数字代表本次查询的答案。
5 + 0 1 + 3 5 ? 2 - 0 2 ? 1
6 0
20 ? 878494275932786174 ? 191206274092260882 + 90709979082345650 155142141185936482 + 517494333569600530 564853145673499945 + 292058956849763644 736907297231575987 + 250899541204107384 366738113984603143 ? 259122961181491897 + 149295125735363566 910059229663807234 - 109473047945647405 565286205925699217 - 883301298997052753 913230049662700033 + 295634031302217703 309192531649055162 ? 915522570298079114 + 566433447467846309 754658072386278321 ? 610866486668767338 + 641530186302671096 742430918223400068 - 663857704259305552 687937536746193119 ? 349435671598058575 ? 282988533888872405 ? 157927321439531627 ? 899654625275143831
878494275932786173 191206274092260881 809562879312551333 1265859232579571863 961203148950260087 381757240808197789 315310103099011619 176690390302833381 1225911455069749012
猫的叫声是：
在一个空字符串后面加上任意正整数个'M'或'm'；
在上面的字符串后加上任意正整数个'E'或'e'；
在上面的字符串后加上任意正整数个'O'或'o'；
在上面的字符串后加上任意正整数个'W'或'w'；
狗的叫声是：
在一个空字符串后面加上任意正整数个'W'或'w'；
在上面的字符串后加上任意正整数个'A'或'a'；
在上面的字符串后加上任意正整数个'O'或'o'；
在上面的字符串后加上任意正整数个'V'或'v'；
例如：
'MmmMeEoowW','MMeooOWWWWWw','mEoW'是猫叫，'eoOW','MmmOoeewWW'都不是猫叫。
'Waovvvv','WWWaooOoV','WwwwwwaOOv'是狗叫，'Wao','Woavvasadsa'都不是狗叫。
第一行，一个整数 $$$t(1\le t\le 10^5)$$$，代表数据组数。
对于每组数据:
第一行，一个正整数 $$$n(1\le n \le 10^5)$$$，代表字符串长度。
第二行，一行字符串 $$$s(1\le|s|\le10^5)$$$，代表动物的叫声。
$$$\sum|s|\le 2⋅10^5$$$，保证$$$s$$$只包含大小写英文字母。
如果是猫，输出一行'0_0'。 如果是狗，输出一行'*_*'。 否则，输出一行'???'。
4 11 MMmmeOOowWW 17 WwwWAaAAOoOOvVVVv 15 MmmWWaaOOOwwVVV 13 WwwaAAoOoooWW
0_0 *_* ??? ???
反回文串是指对于某个长度为$$$n$$$的字符串$$$s$$$，对于$$$\forall i\in [0,n)$$$，均满足$$$s[i]≠s[n-1-i]$$$。
例如，字符串'codeforces'，'love'是反回文串，但是'you'，'abbc'就不是反回文串。
给你一个 $$$n$$$ 个节点的有根树，树的根节点为$$$1$$$，树的每个节点上有一个小写字母。
有 $$$q$$$ 次询问，每次询问给出两个值$$$now,deep$$$，代表对于节点$$$now$$$，其子树中所有对于根来说深度为$$$deep$$$（根的深度为$$$1$$$）的节点上的字母组成的集合能否构成一个反回文串。
第一行，两个整数 $$$n,q(1\le n \le 2·10^5;1\le q \le 2·10^5)$$$，代表树的节点数与询问数。
接下来的$$$n-1$$$行，每行两个整数 $$$u,v(1\le u,v \le n)$$$，代表树上的一条边，保证最终给出的是一棵树。
接下来的一行，一个长度为$$$n$$$的字符串$$$s$$$，其中$$$s[i-1]$$$代表节点$$$i$$$上的字母。
接下来的$$$q$$$行，每行两个整数 $$$now,deep(1\le now,deep \le n)$$$ ，代表一次询问。
对于每个询问，如果可以构成反回文串，输出'Yes'。 如果这次询问中的 $$$deep \lt dep[now]$$$ 或者深度为$$$deep$$$的子节点不存在或无法构成反回文串，输出'No'。
本题的输出大小写不敏感，即'"YES"'、'"yEs"'等均会被视作肯定的答案。
5 3 1 2 1 3 2 4 2 5 aabcc 1 2 3 3 2 3
Yes No No
对于询问 $$$1\ 2$$$，当前可以构成反回文串'ab'。
对于询问 $$$3\ 3$$$，深度为$$$3$$$的子节点不存在。
对于询问 $$$2\ 3$$$，'cc'显然不是反回文串。
我们给出一些弱的字符串 $$$T_i$$$ ，而如果 $$$T_i$$$ 作为一个字符串 $$$T'$$$ 的子串出现，那么 $$$T'$$$ 也是弱的。对于一个字符串 $$$S$$$，我们希望在其中任意截取的子串都是弱的。我们限制所截取子串的长度至少为 $$$k$$$，如果要满足上述限制，则这个 $$$k$$$ 的最小值是多少？
换句话说，你要找到一个最小长度 $$$k$$$ ，使得从文本串 $$$S$$$ 中截取出任意长度大于等于 $$$k$$$ 的子串，都至少有一个模式串是它的子串。如果不能找到这样一个长度，则输出 $$$-1$$$。
第一行一个正整数 $$$n (1 \leq n \leq 2 \times 10^5)$$$，表示模式串个数。
接下来 $$$n$$$ 行，为分别为一个模式串 $$$T_i (1 \leq |T_i| \leq 5 \times 10^4, \Sigma |T_i| \leq 5 \times 10^5)$$$
最后一行为一个文本串 $$$S (1 \leq |S| \leq 4 \times 10^6)$$$
保证所有输入的字符串都是由小写字母组成。
输出最小的子串长度 $$$k$$$。如果不存在，则输出 $$$-1$$$。
3 ab bcd bc abcd
3
有一个长度为$$$n$$$的括号序列$$$seq$$$，序列下标从$$$1$$$开始，你需要从中选择一个子序列，该子序列需要满足： 1. 该序列是一个匹配的括号序列。 2. 该序列中没有出现多层括号嵌套的情况。 例如'(())'中就出现了一个两层括号嵌套的情况，是不满足条件的，但是'()()()'就是一个满足条件的括号序列。
假设选出的括号序列$$$s$$$长度为$$$len$$$，$$$index_i$$$表示序列中第$$$i$$$个括号在原序列中的下标，那么这个括号序列的优美度为： $$$$$$ \sum_{i=1}^{len} index_i·[s_i = ')'] - \sum_{i=1}^{len} index_i·[s_i = '('] $$$$$$
其中'"[]"'内的内容代表需要满足的条件，即你选择的子括号序列中所有右括号在原序列中的下标和减去所有左括号在原序列中的下标和。
现在有$$$q$$$次修改操作: 'pos c'，即 $$$seq_{pos} := c$$$ 。
你需要在每次修改操作后输出一个整数，代表在这次修改后你能取出的优美度最大的合法子序列的优美度。
请注意，每次修改操作会实际地修改括号序列。
第一行，两个整数 $$$n,q(1\le n \le 2·10^5;1\le q \le 2·10^5)$$$代表初始时括号序列的长度和修改操作的次数。
第二行，一个长度为$$$n$$$括号序列，不保证该括号序列是匹配的括号序列。
接下来连续的$$$q$$$行，每行两个整数 $$$pos,c(1\le pos\le n;c是左括号或右括号)$$$，代表一次操作。
共$$$q$$$行，在每次操作后能输出可以取出的合法的优美度最大的子序列的优美度，如果取不出任何的合法的子序列，输出'0'。
5 2 ()))) 1 ) 2 (
0 3
第一次修改后，括号序列变为')))))'，选不出任何合法子序列。 第二次修改后，括号序列变为')()))'，选择下标$$$2$$$和$$$5$$$的括号作为当前子序列。
有一个长度为$$$n$$$的二进制字符串，我们将$$$k$$$个连续的字符分为一组，即第$$$1$$$个字符到第$$$k$$$个分为一组，第$$$k+1$$$个字符到第$$$2k$$$个字符为一组...保证$$$n$$$为$$$k$$$的倍数。你需要翻转（'0'变成'1','1'变成'0'）其中的一些字符，使得任意一组内的字符全部相等，在翻转次数最少的前提下，我们希望最终字符串被分成的'01'段的数量也最少。不仅如此，你还需要求出在满足前两个前提下，翻转的方案数有多少。
不同的翻转方案指的是翻转后的两个字符串在任何一个位置不同。
'01'段是指字符串以子段内全部字符相同为前提下最少划分的段数，例如'00100111'被划分成$$$4$$$个'01'段，'00000000'被划分成$$$1$$$个'01'段。
举个例子： 当$$$n=4,k=1$$$时，对于二进制字符串'0010'，最少需要翻转$$$0$$$次，最少分成的分成的'01'段的数量为$$$3$$$段，翻转方案数为$$$1$$$种。 当$$$n=8,k=4$$$时，对于二进制字符串'00110101'，最少需要翻转$$$4$$$次，最少分成的分成的'01'段的数量为$$$1$$$段，翻转方案为$$$2$$$种，即把字符串翻转为'00000000'或'11111111'，虽然把字符串翻转成'00001111'满足任意一组内的字符全部相等满足且翻转$$$4$$$次，但是此时字符串分成的分成的'01'段的数量为$$$2$$$段，**不满足**被分成的'01'段的数量也最少的条件，所以这不是一种合法的方案。
第一行，一个整数 $$$t(1\le t \le 5·10^5)$$$，代表数据组数。
对于每组数据：
第一行，两个个整数 $$$n,k(1\le n \le 5·10^5;1\le k \le n)$$$，代表二进制字符串的长度与每组字符的字符数，满足$$$n$$$是$$$k$$$的倍数。
第二行是一个长度为$$$n$$$的二进制字符串。
保证 $$$\sum n \le 5·10^5$$$。
对于每个二进制字符串，输出一行三个整数$$$a,b,c$$$，分别代表最少翻转次数、在保持最少翻转次数的前提下分成的'01'段的最少数量、在满足前两个前提下，翻转的方案数有多少。因为$$$a,b,c$$$可能较大，所以你输出答案时需要把三个数对于'998244353'取模。
3 4 1 0010 8 4 00110101 16 2 0100011000011011
0 3 1 4 1 2 5 2 3
对于样例的第$$$1$$$、$$$2$$$组数据的解释见题目描述。
我们假设一下，你和你的 npy 在$$$2023$$$年的$$$5$$$月$$$20$$$号在玩游戏（），游戏的内容就是石头剪刀布，游戏规则如下：
石头赢剪刀。
剪刀赢布。
布赢石头。
如果两人出的相同，则平局。
现在，假如知道你们玩的游戏的总局数$$$n$$$，你的 npy 分别出石头、剪刀、布的次数$$$a_1,b_1,c_1$$$和你分别出石头、剪刀、布的次数$$$a_2,b_2,c_2$$$，假如你可以准确预判你的 npy 会出什么，请问在$$$n$$$局游戏中你最少可以赢多少局，最多可以赢多少局。
第一行，一个整数 $$$t(1\le t\le 10^5)$$$，代表数据组数。
对于每组数据：
第一行$$$3$$$个整数 $$$a_1,b_1,c_1(0\le a_1,b_1,c_1 \le 10^6)$$$，代表你的 npy 分别出石头、剪刀、布的次数。 第二行$$$3$$$个整数 $$$a_2,b_2,c_2(0\le a_2,b_2,c_2 \le 10^6)$$$，代表你分别出石头、剪刀、布的次数。
保证 $$$a_1+b_1+c_1=a_2+b_2+c_2$$$。
对于每组数据，输出一行两个整数，分别代表你最少可以赢的局数和你最多可以赢的局数
4 100 100 100 100 100 100 520 0 0 0 0 520 11 45 14 45 14 11 182 103 34 10 53 256
0 300 520 520 20 70 119 226
对于第$$$2$$$组数据，你的 npy 出了$$$520$$$次石头，你出了$$$520$$$次布，所以你只能全部赢下。
YiYi 有一个长度为$$$n$$$的数组$$$a$$$，数组中的数字全是正整数，她希望你使用移动操作帮她把数组排个序，使其单调不减。
在每次移动操作中，你可以： - 选择数组中某一个位置的数字$$$a_i$$$，将这个数字移动到数组的其他任意位置，且这次操作的代价就是你移动的数字$$$a_i$$$的大小。
在你的每次移动过程中，除了你移动的数字，其他位置的数字的相对位置不会改变。
但是，她还给你提出了一个限制，那就是在你移动任何一个数字的前后，有$$$k$$$个数字的绝对位置（就是数字在数组中的下标）不能改变。
她想请你帮帮她，计算出把数组排序的最小代价是多少，如果数组在限制条件下没有方法变得单调不减，请输出'-1'。
第一行，一个整数 $$$t(1\le t \le 3·10^5)$$$，代表数据组数。
对于每组数据：
第一行，两个整数 $$$n,k(1\le n \le 3·10^5;0 \le k \le n)$$$代表数组中元素的数量和绝对位置不能改变的数字数量。
第二行，$$$n$$$个整数，代表数组 $$$a(1\le a_i \le 10^9)$$$。
第三行，$$$k$$$个整数，每个元素 $$$ban(1\le ban \le n)$$$代表绝对位置不能改变的数字位置。
保证 $$$\sum n \le 3·10^5$$$。
如果在限制条件下数组最终可以通过操作单调不减，输出排序的最小代价。
否则，输出'-1'。
3 5 1 2 1 3 5 4 3 4 0 1 7 3 2 6 2 1 1 4 5 1 4 2 6
5 5 -1
对于第$$$1$$$组数据，可以按照如下方式移动：
'2 1 3 5 4' -> '1 2 3 5 4' -> '1 2 3 4 5' ，即移动数字$$$1$$$和$$$4$$$，代价为 $$$1+4=5$$$，且此时数字$$$3$$$的绝对位置均无改变。 对于第$$$3$$$组数据，因为无法移动最后一个$$$4$$$，所以不论怎么移动数字，序列都不可能单调不减。
小Q有一个神奇的机器，可以随机生成某个长度的字符串（包括长度为$$$0$$$的空串）。字符串的不同位之间相互独立，同一字符在任一位上出现的概率都是相同的。
小Q发现了一个自己很喜欢的字符串$$$S$$$，他希望知道如果他让机器生成一个长度为$$$k$$$的字符串，$$$S$$$是该字符串的子序列的概率是多少。 一个字符串的子序列是指从该字符串中取部分字符（可以全取或全不取），取出来的字符按在原串中的顺序排列而成的字符序列。如空串、"aba"、"aac"、"ababc"都是"ababc"的子序列，而"cab"则不是。
第一行$$$26$$$个非负数，表示从'a'到'z'每个字符的权重，即输入$$$weight['a'..'z'](0 \le weight[i] \le 1000)$$$，字符$$$ch$$$在任一位上出现的概率为 $$$$$$ \frac{weight[ch]}{\sum_{i='a'}^{i='z'}weight[i]} $$$$$$
第二行一个字符串 $$$S(1\le |S| \le 100)$$$。
第三行一个正整数 $$$T(1\le T \le 100)$$$，表示数据组数。
接下来$$$T$$$行，每一个一个正整数 $$$k(0\le k \lt 2^{60})$$$，表示机器生成的字符串长度。
保证至少有一个$$$weight[i]$$$不为$$$0$$$。
$$$T$$$行，每行一个正整数，表示$$$S$$$是该字符串的子序列的概率，对$$$998244353$$$取模的结果。
可以证明答案一定可以表示成 $$$\frac{q}{p}$$$，其中$$$q$$$为非负整数，$$$p$$$为正整数，且存在一个正整数$$$p^{(-1)}$$$，使得 $$$p^{(-1)}×p≡1\ mod\ 998244353$$$，即$$$p$$$在模$$$998244353$$$下一定存在逆元，你只需输出$$$q×p^{(-1)}$$$模$$$998244353$$$的值即可。
30 40 30 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 abc 6 0 1 2 3 4 5
0 0 0 387318809 163712074 688748674
$$$a$$$在每一位上出现的概率为$$$0.3$$$，$$$b$$$为$$$0.4$$$，$$$c$$$为$$$0.3$$$，其余字符不可能出现。
$$$k=0$$$时，只能生成空串，$$$k=1,2$$$时，长度小于$$$3$$$，不可能包含子序列"abc"。
$$$k=3$$$时，长度为$$$3$$$的串只有abc，概率为$$$0.3·0.4·0.3=0.036$$$，模$$$998244353$$$为$$$387318809$$$。
$$$k=4$$$时，长度为$$$4$$$的串中abc*,ab*c,a*bc,*abc符合条件，计算得概率为$$$0.1080$$$，模$$$998244353$$$为$$$163712074$$$。
$$$k=5$$$时，概率为$$$0.20412$$$，模$$$998244353$$$为$$$688748674$$$。
我们可以把东南大学的校园抽象成一个$$$n$$$个点，$$$m$$$条边的有向图，每条边有长度$$$w$$$。
在校园中有$$$p$$$个点上有障碍物，你最多可以搬走$$$k$$$个障碍物，即你最多经过$$$k$$$个有障碍物的点。
那么，现在请问，在最多可以搬走$$$k$$$个障碍物的条件下，你从点$$$1$$$出发，到其他点的最短距离分别为多少。
第一行，$$$4$$$个整数 $$$n,m,p,k(1\le n \le 10^5;0\le m \le \min(10^5,n·(n-1));0\le p \le n-1;0\le k \le 5)$$$，分别代表图中的点数、边数、有障碍物的点数和你最多搬走的障碍物数量。
第二行，有$$$p$$$个整数，代表有障碍物的点的下标，保证这$$$p$$$个整数互不相同，且点$$$1$$$没有障碍物。
接下来连续的$$$m$$$行，每行$$$3$$$个整数 $$$u,v,w(1\le u,v \le n;1\le w \le 10^9)$$$，代表一条有向边的起点、终点和边的长度。
保证最终给定的图无重边、无自环。
在一行中输出用空格隔开的$$$n$$$个整数，代表从点$$$1$$$出发到达$$$n$$$个点的最短距离，如果不能到达某一个点，那就输出'-1'。
6 6 3 2 4 5 6 5 6 1 1 2 1 1 3 2 2 4 1 3 4 2 4 5 4
0 1 2 2 6 -1
80 分是一种老少咸宜的牌类游戏，四个玩家两副扑克是 80 分的标准玩法。四个玩家两两一队（自己的对家是自己的队友），一队中的两位玩家胜利条件一致。两队分为打家和闲家，在本题中，双方的胜利条件均为成为最后一轮的赢家。
每张扑克牌有两个属性，点数和花色。点数由小到大依次是 2、3、4、5、6、7、8、9（为简化题目，本题排除了大小王和 10 及以上的牌），花色为 S（♠），H（♥），C（♣），D（♦），表示如 4S（代表黑桃 4），6D（代表方块 6）。本题中有三种合法的牌型，分别为单张、对子和散牌。单张即任意一张牌，对子为花色且点数相同的两张牌，散牌则为不能构成对子的两张牌。
80 分出牌以轮为单位，即出牌从首家开始，沿逆时针（见图 1）轮流出牌，直至首家的上家打完牌后为止。合法的出牌方式要求首家出的牌型是单张或对子，且每个玩家在每轮的出牌张数必须与该轮首家一致，在满足这一前提的条件下，若手中含有与首家花色相同的牌，则必须打出该花色的牌，否则可任选牌打出。
一轮结束后，比较牌的大小，决定本轮的赢家。如果一个玩家在本轮打出牌的牌型和花色均与首家相同，称这位玩家满足条件。在所有满足条件的玩家中，比较扑克牌点数的大小，点数最大的称为赢家。若有两位玩家点数相同且均为最大，则本轮先出牌的为赢家。本轮的赢家为下一轮的首家，即下一轮第一个出牌的是本轮的赢家。若某轮玩家将手中的牌全部打出，则称该轮为最后一轮。
一天，小高，小杨，小黄，小吴四个人在小高家里打 80 分（小高和小黄是打家，小杨和小吴是闲家），局面十分激烈。现在大家手里都只剩两张牌了，本轮轮到小高率先出牌。聪明的小高早已有了自己的策略，只可惜愚笨的小黄出牌毫无章法。小高想考考你，她是否存在一种出牌方式，使得无论别人怎么出牌，打家都成为赢家？如果存在，输出 '"Gao"'（不含引号），否则输出 '"Yang"'（不含引号）。
毫无章法可以理解为不管小高出什么，小黄都会按照出牌规则随机出牌。
第一行，一个整数 $$$t(1\le t \le 10^4)$$$，代表数据组数。
对于每组数据：
输入共 $$$4$$$ 行，每行有两个长度为 $$$2$$$ 的字符串，代表两张牌。
第一行表示小高的牌，第二行表示小杨的牌，第三行表示小黄手里的牌，第四行表示小吴手里的牌。
对于每组数据，输出一行一个字符串 '"Gao"'（不含引号）或者 '"Yang"'（不含引号）。
2 2H 3H 9D 9D 5H 8C 7C 7C 2H 3H 8H 7D 5H 8C 2H 9D
Gao Yang