"良"，意为"善"也。"善"字形如开口的羊羔，若是人如羊羔一般温顺，便配得上"良"这名字。
然而，我并不觉得自己是羊。
崇祯元年（1628年），舌头是与良同行的另一头狼，两人分工明确，舌头引人，良出力，劫掠山路上的"羊"，靠"羊毛"度日。
并且，良有一个习惯，每宰一只"羊"都要留些"羊毛"带在身上。
这天，两人劫了一只"羊"，从他身上拿了五两银、二百余钱，一身破衣，一个荷包等。
良把荷包带在了身上，随后两人继续合计怎么分摊"羊毛"。
为了使分摊尽可能的公平，两人希望各自拿到的物品价值总和尽可能的平均。
形式化的：给定 $$$n+1$$$ 个物品，价值分别为 $$$x,a_1,a_2,\cdots,a_n$$$。
设 $$$U = {x,a_1,a_2,\cdots,a_n}$$$，将 $$$U$$$ 划分为两个集合 $$$A$$$ 和 $$$B$$$，满足：
请你最小化 $$$|\sum_{x\in A}x - \sum_{x\in B} x|$$$，输出这个值。
第一行输入两个正整数 $$$n$$$，$$$x$$$（$$$1\le n\le 10^2$$$, $$$1\le x\le 10^2$$$），分别表示物品数量、荷包价值。
接下来一行输入 $$$n$$$ 个正整数 $$$a_1,a_2,\cdots,a_n$$$（$$$1\le a_i \le 10^2$$$），表示每个物品的价值。
输出一个整数，表示答案。
3 24 2 3
1
麦田无边无际，阳光照在麦田上、麦穗连在一起，仿佛金色的湖。
她的家人牵着她的手，跑在这风浪中。她笑着跌倒在金色的海洋里，开心地笑着。
良有 $$$n$$$ 条不连贯的与满穗有关的信息，无法将其联系起来。
问过满穗过后，满穗给出了 $$$m$$$ 对信息之间的关系，每一对关系在良眼里都有一个可信度。
良希望用尽可能少的关系把这些信息联系起来，并且整件事情的可信度尽可能的大。
形式化的：给定 $$$n$$$ 个点，$$$m$$$ 条边，每条边有边权。
选择最少数量的边使整个图联通，并且使得边权和最大。
如果无法使得图联通，输出 -1。
第一行输入两个正整数 $$$n$$$，$$$m$$$（$$$1\le n \le 10^5$$$，$$$1\le m \le 10^6$$$），分别表示信息和信息关系的数量。
接下来 $$$m$$$ 行，每行输入三个正整数 $$$u_i$$$，$$$v_i$$$，$$$w_i$$$（$$$1\le u_i,v_i\le n$$$，$$$1\le w_i \le 10^9$$$），分别表示 $$$u_i$$$ 和 $$$v_i$$$ 信息之间可以连贯，可信度 $$$w_i$$$。
输出一个整数，表示答案。
4 51 2 23 1 32 1 43 4 12 4 6
13
过了这么多年，我本以为自己改变了、变强了、从羊变成了狼，不用再畏惧任何事。
然而，我还是无法摆脱那一年的噩梦。
白袍——乌甲素包巾！丈八蛇矛——手内握哎 。
影子戏里，是刘关张三人大战赤兔吕布的场景。
白幕可以抽象成一个 $$$n\times m$$$ 的网格，满穗希望在上面放若干个骑兵。
满穗希望它们互不攻击。
请你帮忙计算网格中最多能放多少个互不攻击的骑兵。
形式化的：给定一张 $$$n\times m$$$ 的网格。
计算这张网格内最多能放多少个互不攻击的骑兵。
对于位于 $$$(i, j)$$$ 的骑兵，可以攻击到的位置为 $$$(i-2, j+1)$$$，$$$(i-1, j+2)$$$，$$$(i+1, j+2)$$$，$$$(i+2, j+1)$$$，$$$(i+2, j-1)$$$，$$$(i+1, j-2)$$$，$$$(i-1, j-2)$$$，$$$(i-2, j-1)$$$，输入下图所示：
有多组测试数据。第一行输入一个正整数 $$$T$$$（$$$1\le T \le 10^5$$$），表示测试数据组数。
每组测试数据输入一行，其中有两个正整数 $$$n$$$，$$$m$$$（$$$1\le n, m\le 10^9$$$），表示网格大小。
每组测试数据输出一行，包含一个整数，表示答案。
22 45 4
410
那么，我该相信谁。
该怎么选？
良的善恶在挣扎。
良的原则可以抽象为有 $$$n$$$ 个部分，每一部分权重为 $$$a_i$$$。
良的善念与这个长度为 $$$n$$$ 的序列所有的上升子序列的和有关。
现在请你计算这个值。
形式化的：给定一个长度为 $$$n$$$ 的序列 $$$a_1, a_2, \cdots, a_n$$$，现在请你计算下列计算式的值。 $$$$$$ W = \sum_{S\subseteq N}\sum_{i=1}^{|S|}a_{S_i} $$$$$$ 其中 $$$N$$$ 为 $$$\{1,2,\cdots,n\}$$$，$$$S$$$ 为 $$$N$$$ 的子集，且满足 $$$\forall i \in [2, |S|]$$$ 都有 $$$a_{S_{i - 1}} \lt a_{S_i}$$$。
现在你需要计算 $$$W$$$ 的值，由于答案可能非常大，请输出对 $$$998244353$$$ 取模后的答案。
第一行输入一个正整数 $$$n$$$（$$$1\le n \le 5\times 10^5$$$），表示序列长度。
第二行输入 $$$n$$$ 个正整数 $$$a_1,a_2,\cdots,a_n$$$（$$$1\le a_i\le 10^9$$$），描述了序列。
输出一个整数，表示答案。
35 2 3
15
很久以前，在那一场大爆炸发生之前，在良爷小的时候……
你想成为什么样的人呢？
良深知这世道，不是"侠"能活的世道。
成为"侠"的梦想早已破灭，也就无法再挥剑向不公，仗剑走天涯。
但另一个难题摆在良的面前。
"我该送她去复仇吗？"
"还是劝她不要再去复仇？"
早已被唤醒的良知影响着良，良不希望自己亲手送满穗去复仇。
两种选择分别对应着两个序列 $$$A$$$ 和 $$$B$$$。
良可以操作若干次，每次将 $$$A$$$ 中的一个值加上或减去 $$$A$$$ 与 $$$B$$$ 中位置不同的一对差值。
为了尽可能的劝说满穗放弃复仇，良需要最小化两序列差的绝对值之和。
形式化的：给定两个长度为 $$$n$$$ 的序列 $$$A$$$ 和 $$$B$$$，设 $$$A$$$ 与 $$$B$$$ 的权值为 $$$W$$$。 $$$$$$ W = \sum_{i=1}^n |a_i-b_i| $$$$$$ 你可以执行以下操作任意次（可能是 $$$0$$$）：
- 选择两个下标 $$$i$$$, $$$j$$$，令 $$$a_i := a_i+|a_j - b_j|$$$ 或 $$$a_i:=a_i-|a_j-b_j|$$$，其中 $$$i \ne j$$$。
计算任意次操作后，$$$W$$$ 的最小值。
第一行输入一个正整数 $$$n$$$（$$$1\le n\le 10^5$$$），表示序列长度。
第二行输入 $$$n$$$ 个整数 $$$a_1,a_2,\cdots,a_n$$$（$$$|a_i|\le 10^9$$$），表示序列 $$$A$$$。
第三行输入 $$$n$$$ 个整数 $$$b_1,b_2,\cdots,b_n$$$（$$$|b_i|\le 10^9$$$），表示序列 $$$B$$$。
输出一个整数，表示答案。
32 6 42 4 1
1
很多事，对于一个人的一生来说，是头一回，也大概是最后一回。
这大概是我与小羊们在他人面前演的第一次戏，也是最后一次。
两人打的难舍难分。
良最初体力值和攻击力为 $$$a$$$，闯将的体力值和攻击力为 $$$b$$$。
战斗分为若干个回合，每个回合双方都同时进攻对方，使对方的生命值减去自身攻击力的值，且自身攻击力减少 $$$1$$$。
若有一方的体力值先降低至 $$$0$$$ 及以下，则另一方获胜。
如果双方在同一回合的体力值均降低至 $$$0$$$ 及以下，则为平局。
若良获胜输出 Liang，闯将获胜输出 Chuang，平局则输出 Pingju。
第一行输入两个正整数 $$$a$$$, $$$b$$$（$$$1\le a,b \le 10^9$$$），分别表示良和闯将的体力值及攻击力。
输出一行，表示获胜方或平局。
21 10
Liang
你还是你。
你不是狼，是"良"。
清晨，良来到集市，准备为马上要分别的小羊们买些好吃的好玩的，好好道个别。
集市有 $$$n$$$ 个商铺，自西向东依次排开，编号为 $$$1,2,3,\cdots,n$$$，其中 $$$1$$$ 号商铺在最西边， $$$n$$$ 号商铺在最东边。
良最开始在编号为 $$$1$$$ 的商铺位置，一直向东走，他每次移动会随机均匀的走到在当前位置东边的一家商铺并逛 $$$1$$$ 次该店铺（包括当前所在位置商铺）。
注：在最开始时良并不会逛 $$$1$$$ 号商铺。
由于并不需要买特别多东西，因此他最多会逛 $$$k$$$ 次商铺。
良想知道，逛完 $$$k$$$ 次商铺的时候他的所在位置的概率。
形式化的：有 $$$n$$$ 个节点，以此编号为 $$$1,2,3,\cdots,n$$$，初始时在 $$$1$$$ 节点。
你必须执行以下操作 $$$k$$$ 次：
- 设当前节点为 $$$x$$$，你会等概率的选择 $$$[x, n]$$$ 之间的一个节点，并移动到该节点上。
随后 $$$q$$$ 次询问，每次询问一个位置 $$$x$$$，你需要回答在 $$$k$$$ 次操作后当前位置恰好在 $$$x$$$ 节点上的概率。
第一行输入三个正整数 $$$n$$$，$$$k$$$，$$$q$$$（$$$1\le n,k\le 2\times10^6$$$，$$$1\le q\le 10^5$$$），分别表示商铺个数，逛商铺次数，询问次数。
接下来 $$$q$$$ 行，每行输入一个正整数 $$$x$$$（$$$1\le x\le n$$$），表示询问位置。
输出 $$$q$$$ 行，每行输出一个小数，表示第 $$$i$$$ 次查询的答案。
当你的答案与标准答案的绝对误差或相对误差不超过 $$$10^{-6}$$$ 时将被视为正确。具体而言，设你的答案为 $$$a$$$，裁判答案为 $$$b$$$，当且仅当满足 $$$\frac{|a-b|}{\max(1,|b|)} \leq 10^{-6}$$$ 时，你的答案才会被判为正确。
4 2 224
0.14583333 0.52083333
若是这样的话……
你觉得自己还该复仇吗？
良需要在宵禁之前找到满穗。
鼓楼附近有一些满穗可能藏匿的地点，良知道这些地点的路径，他希望尽快的找遍这些地点。
形式化的：给定一张具有 $$$n$$$ 个点，$$$m$$$ 条边的无向图，起点为 $$$s$$$。
通过一条边所花费的时间为 $$$w_i$$$。
请你计算从 $$$s$$$ 出发走过所有点花费的最小时间是多少。
第一行输入三个整数 $$$n$$$，$$$m$$$，$$$s$$$（$$$1\le n\le 20$$$，$$$n-1\le m \le \frac{n(n-1)}{2}$$$，$$$1\le s\le n$$$），分别表示地点数量，路径数量和良当前所在的起点。
接下来 $$$m$$$ 行，每行输入三个正整数 $$$u_i$$$，$$$v_i$$$，$$$w_i$$$（$$$1\le u_i,v_i\le n$$$，$$$1\le w_i\le 10^9$$$），表示一条连接 $$$u_i$$$ 和 $$$v_i$$$ 且边权为 $$$w_i$$$ 的边。
保证给定的图为连通图，且不存在重边和自环。
输出一个正整数，表示答案。
4 5 31 2 22 3 13 4 41 4 22 4 5
5
这种突如其来的"不见"，以及那永远没有答案的结果，便是她对我的报复。
最温柔却最残忍的报复。
即便如此，良依然希望找到满穗。
洛阳城附近有若干条河流，其中一些相互联通。
每个河流有各自的宽度，宽度大小与能否找到满穗有关。
1. 对于一个环流，其宽度由其组成的最大河流宽度决定。
2. 对于一个链流，其宽度由其组成的最小河流宽度决定。
良需要你帮他找到决定所有河流宽度的河流，并输出方案，那里很可能找到满穗。
形式化的：给定一张 $$$n$$$ 个点的无向图，每个点有一个权值 $$$a_i$$$。
你可以执行若干次操作，最终使得整张图缩成一个点，每次操作选择以下两种操作的其中一种：
1. 选择一个简单环$$$^{\text{∗}}$$$，将这些点删除，建立一个新点，新点的权值为被环包含的点中的最大权值，且新点与直接连接环的点之间有一条连边（不计算重边和自环）。
2. 选择一条链$$$^{\text{†}}$$$，将这些点删除，建立一个新点，新点的权值为被环包含的点中的最小权值，且新点与直接连接环的点之间有一条连边（不计算重边和自环）。
其中，第 $$$i$$$ 次操作建立的新节点编号为 $$$n + i$$$。
请你找到在图缩成一个点后，能保留的最大权值，并输出一种操作方案，且操作次数不超过 $$$n$$$ 次。
如果存在多种合法方案，输出任意一种。
本题为 $$$\text{M}$$$ 题的 $$$\text{std}$$$ 程序。
$$$^{\text{∗}}$$$一条至少包含三条边的闭合路径，其中除了起点和终点相同外，其余所有顶点均不重复，且所有边也不重复。
$$$^{\text{†}}$$$一条所有顶点都不重复的路径。
有多组测试数据。
第一行输入一个正整数 $$$T$$$（$$$1\le T \le 10^3$$$），表示测试数据组数，对于每组测试数据：
第一行输入两个正整数 $$$n$$$，$$$m$$$（$$$1\le n \le 10^5$$$，$$$n - 1 \le m \le \min\left(\frac{n(n-1)}2,10^6\right)$$$），分别表示点数量，边数量。
第二行输出 $$$n$$$ 个整数 $$$a_1, a_2,\cdots a_n$$$（$$$1\le a_i \le n$$$），表示点权。
保证点权之间互不相同。
接下来 $$$m$$$ 行，每行输入两个正整数 $$$u_i$$$，$$$v_i$$$（$$$1\le u_i,v_i\le n$$$，$$$u_i \ne v_i$$$），表示一条连接 $$$u_i$$$ 和 $$$v_i$$$ 的边。
保证给定的图为连通图，且不存在重边、自环。
保证所有数据 $$$n$$$ 之和不超过 $$$10^5$$$，$$$m$$$ 之和不超过 $$$10^6$$$。
对于每组测试数据：
第一行输出一个正整数，表示保留的最大权值。
第二行输出一个整数，表示操作次数 $$$k$$$。
接下来 $$$k$$$ 行，每行输出若干个数字。
第 $$$i$$$ 行第一个整数表示操作方式，第二个该次操作选择的节点数量 $$$l$$$。
接下来 $$$l$$$ 个数字，表示该次操作选择的节点序列 $$$p_1, p_2, \cdots,p_l$$$，其中任意 $$$i\ne j$$$ 均满足 $$$p_i \ne p_j$$$。
对于正整数 $$$i$$$（$$$1\le i \lt l$$$），在 $$$p_i$$$ 与 $$$p_{i+1}$$$ 均存在一条边。
若为操作 $$$1$$$，额外要求 $$$p_1$$$ 与 $$$p_l$$$ 之间存在一条边。
24 44 2 1 31 22 31 31 44 41 2 4 31 22 31 31 4
3 2 1 3 1 2 3 2 2 4 5 4 2 2 2 1 4 1 3 2 3 5
杀，我会去杀、用我这条命去换我们仇人的命！
杀！用我的命去证明这世道是错的—天，亦是错的！
湖边寻到满穗后，良有太多疑问。
良的问题和满穗的实情可以抽象成两个 $$$n\times m$$$ 的 $$$01$$$ 矩阵 $$$A$$$ 和 $$$B$$$。
矩阵每一个位置 $$$(i, j)$$$ 有一个权值，如果该点为 $$$1$$$，权值为 $$$0$$$，否则为与它相邻的 $$$1$$$ 的数量（两个格子相邻当且仅当它们共用一个点或一条边）。
良的每次提问可以表示为反转 $$$A$$$ 中的某一位。
为了清楚事实，良希望尽可能的少提问，使得 $$$A$$$ 和 $$$B$$$ 的权值和相等。
形式化的：给定两个 $$$n\times m$$$ 的 $$$01$$$ 矩阵 $$$A$$$ 和 $$$B$$$。
矩阵 $$$(i, j)$$$ 位置的值为 $$$1$$$ ，权值为 $$$0$$$，否则为与它相邻的 $$$1$$$ 的数量（两个格子相邻当且仅当它们共用一个点或一条边）。
你可以执行以下操作：
选择 $$$A$$$ 的一个位置 $$$(i, j)$$$，反转这一位的 $$$01$$$ 值。
构造一种操作序列，在操作后两矩阵的权值和相等，且操作序列长度不能超过 $$$\lfloor \frac{nm}2 \rfloor$$$。
第一行输入两个正整数 $$$n$$$，$$$m$$$（$$$1\le n\times m \le 10^6$$$），表示矩阵大小。
接下来 $$$n$$$ 行，第 $$$i$$$ 行输入一个长度为 $$$m$$$ 的 $$$01$$$ 字符串，表示 $$$A_i$$$。
接下来 $$$n$$$ 行，第 $$$j$$$ 行输入一个长度为 $$$m$$$ 的 $$$01$$$ 字符串，表示 $$$B_j$$$。
第一行输出一个整数 $$$k$$$（$$$0\le k \le \lfloor \frac{nm}2 \rfloor$$$），表示操作序列的长度。
接下来 $$$k$$$ 行，每行输出两个正整数 $$$i$$$ 和 $$$j$$$，表示对 $$$A$$$ 的操作位置。
2 3011000101111
1 2 3
迎接我们的，是连绵不断的晴天，一望无际的麦田。
以及一个人人吃饱饭，不再有饿殍的时代……
就像计划的那样，良和穗跑不掉了。
但哪怕如此，良也依然想尝试一番。
门前有 $$$n$$$ 个捕快，每个捕快有各自的战力值 $$$a_i$$$，良的体力值为 $$$k$$$。
由于捕快的数量太多，全部肃清是不可能的。
但捕快的防线存在缺陷，如果存在一对 $$$(i, j)$$$ 且 $$$i \ne j$$$，使得 $$$a_i \oplus a_j \le k$$$，其中 $$$\oplus$$$ 为异或运算，那么良穗可以趁机闯出捕快的包围。
请你帮良判断他们有可能冲出重围吗。
形式化的：给定一个长度为 $$$n$$$ 的序列 $$$a_1, a_2, \cdots,a_n$$$ 和一个正整数 $$$k$$$。
查询是否存在一对 $$$(i, j)$$$ 且 $$$i\ne j$$$，使得 $$$a_i\oplus a_j \le k$$$，其中 $$$\oplus$$$ 为异或运算。
请注意本题特殊的空间限制。
第一行输入两个正整数 $$$n$$$，$$$k$$$（$$$2\le n \le 10^6$$$, $$$1\le k \lt 2^{30}$$$），分别表示捕快数量和良的体力值。
第二行输入 $$$n$$$ 个正整数 $$$a_1,a_2,\cdots,a_n$$$（$$$1\le a_i \lt 2^{30}$$$），表示捕快各自的战力值。
输出 Yes 或 No，表示良穗能否杀出重围。
3 44 6 3
Yes
开城门，迎闯王，闯王来了不纳粮！
迎闯王、不纳粮！迎闯王、不纳粮！
攻破洛阳城后，李自成派人找了一口大锅，把豚妖和它养的几只梅花鹿一起扔进锅里。
为了让百姓和士兵狠狠出一口几年以来积压的恶气，李自成打算把锅放在百姓和将士们的正中央，以便所有人目睹当报应降临到这横征暴敛，压榨百姓的罪魁祸首身上时，其求饶和痛苦的神情。
形式化的：所有人的位置可以抽象成一个二维坐标系，给定 $$$n$$$ 个士兵及百姓的位置 $$$(x_i, y_i)$$$。
锅的坐标为 $$$(a,b)$$$，这个点将坐标系划分为四个部分：
现在李自成希望选择锅的坐标，使得四部分点的数量尽可能的平均，即最大化四部分点集大小的最小值的坐标。
第一行输入一个正整数 $$$n$$$（$$$1\le n\le 10^5$$$），表示士兵及百姓的数量。
接下来 $$$n$$$ 行，每行包含两个整数 $$$x$$$，$$$y$$$（$$$|x|,|y|\le 10^9$$$），表示士兵及百姓的坐标。
输出包含两个整数 $$$a$$$，$$$b$$$（$$$|a|,|b|\le 10^9$$$），表示锅的坐标。
如果有多个合法的点，输出任意一个。
41 11 -1-1 1-1 -1
0 0
我能和她一起，看着她活着。
仅仅如此，对我而言便是最好的事了。
自此烟雨落金城，一人撑伞两人行。
九年之约，良穗相遇。
良已践行与满穗立下的湖畔之约，满穗再次宽限良，允许他实现最后的愿望。
就此，两人乘着小船，踏上了扬州之旅。
包括洛阳和扬州在内的若干个城镇由多条河流相连，且每个城镇有各自的发展水平值，船夫需要提前规划路线。
在船夫的规划有两种方式：
现在给定船夫的操作方案，请你帮忙计算最后保留城镇的发展程度值，若操作不合法或操作后不为一个点，输出 -1。
形式化的：给定一张有 $$$n$$$ 个点的无向图，每个节点有一个权值 $$$a_i$$$。
给定一个操作序列，其中包含两种合法操作：
其中，第 $$$i$$$ 次操作建立的新节点编号为 $$$n + i$$$。
请你计算操作后，在图缩成一个点后所保留的权值，若操作不合法或图不仅剩一点，输出 -1。
本题为 $$$\text{I}$$$ 题的 $$$\text{checker}$$$ 程序。
$$$^{\text{∗}}$$$一条至少包含三条边的闭合路径，其中除了起点和终点相同外，其余所有顶点均不重复，且所有边也不重复。
$$$^{\text{†}}$$$一条所有顶点都不重复的路径。
有多组测试数据。
第一行输入一个正整数 $$$T$$$（$$$1\le T \le 10^3$$$），表示测试数据组数，对于每组测试数据：
第一行输入两个正整数 $$$n$$$，$$$m$$$（$$$1\le n \le 10^5$$$，$$$n-1\le m\le \min\left(\frac{n(n-1)}{2},10^6\right)$$$），分别表示图中点数量，边数量。
接下来一行输入 $$$n$$$ 个正整数 $$$a_1,a_2,\cdots,a_n$$$（$$$1\le a_i\le n$$$），表示第 $$$i$$$ 个点的点权。
保证点权之间互不相同。
接下来 $$$m$$$ 行，每行输入两个正整数 $$$u_i$$$，$$$v_i$$$（$$$1\le u_i,v_i\le n$$$，$$$u_i \ne v_i$$$），表示一条连接 $$$u_i$$$ 和 $$$v_i$$$ 的边。
保证给定的图为连通图，且不存在重边、自环。
接下来一行输入一个正整数 $$$q$$$（$$$1\le q\le n$$$），表示操作序列长度。
接下来 $$$q$$$ 行，第 $$$i$$$ 行输入若干个整数 $$$op$$$，$$$l$$$，$$$p_1,p_2,\cdots,p_l$$$（$$$1\le op\le2$$$，$$$1 \lt l\le n$$$，$$$1\le p_i\le 2\times n$$$），描述了操作方式和操作所选的点序列。
保证所有数据 $$$n$$$ 之和不超过 $$$10^5$$$，$$$m$$$ 之和不超过 $$$10^6$$$。
对于每组测试数据：输出一行，包含一个整数，表示答案。
24 41 2 4 31 22 31 31 421 3 1 2 32 2 5 44 44 2 1 31 22 31 31 411 3 2 1 4
3-1