上海理工大学是一所文脉绵延百余年的上海市属重点高校，办学源头可追溯至 $$$1906$$$ 年的沪江大学与 $$$1907$$$ 年的德文医工学堂，$$$1996 $$$ 年由两校合并定名，现为以工为主、多学科协调发展的大学。整个学校的发展脉络可以参见下图：
上海理工大学校史 从 $$$1906$$$ 年建校到现在 $$$2026$$$ 年 ， 上海理工大学已经走过 $$$120$$$ 个年头 。 值此学校 $$$120$$$ 周年校庆之际 ， 我们 USST-ACM 集训队也迎来了 "第六届上海理工大学程序设计全国挑战赛" 。 非常欢迎参加本次校赛的各位选手 ， 也希望大家都能享受比赛 、 AK 比赛 ！
USST-ACM 集训队教练老周最近在网上购买了很多数字气球 ， 每个气球表示的数字在 $$$0$$$ 到 $$$9$$$ 之间 。 老周想在校庆的时候在计算中心楼下悬挂尽可能多的 "120" 气球 ， 烘托一下校庆的气氛 ， 现在你能帮助他找到这些气球最多能组成多少个 "120" 吗 ？
注意 ： 每个气球最多被使用一次 。
第一行包含一个正整数 $$$n$$$ （ $$$3 \le n \le 2 \cdot 10^5$$$ ） ， 表示购买的气球个数 。
第二行包含 $$$n$$$ 个整数 $$$a_1, a_2, \dots, a_n$$$ （ $$$0 \le a_i \le 9$$$ ） ， 分别表示每个气球代表的数字 。
输出一个整数表示答案。
30 1 2
1
善良的鳄鱼 善良的鳄鱼与邪恶的小老鼠发现了一个长度为 $$$n$$$ 的十进制块数组。为了证明谁才是动物之王，它们决定玩一个比大小的小游戏。最初它们各有一个数字 $$$0$$$ ，然后双方将分别进行 $$$q_1$$$ 和 $$$q_2$$$ 次操作。
每次操作会从这个数组中截取一段连续的块，将这一段按固定 $$$10^9$$$ 进制拼接成一个整数，再与当前拥有的数字进行加、减或乘。最后比较两个数的大小，谁大谁就赢。
显然这种简单的小游戏还是太无聊了。因此鳄鱼提议，为了提升游戏的难度，同时为了避免出现打假赛的情况，每只动物最后计算出的数都必须在 $$$[0,10^{20000}]$$$ 内。这里的区间是闭区间，也就是说 $$$0$$$ 和 $$$10^{20000}$$$ 本身都是合法的。如果有动物最后的答案不在这个范围内，就要遭到严厉的惩罚。
现在鳄鱼和小老鼠已经完成了各自的操作。善良的鳄鱼迫切地想知道自己能不能成为动物之王，于是它便请教你来帮它计算游戏的结果。
具体来说，给定一个长度为 $$$n$$$ 的数组 $$$A$$$（下标从 $$$1$$$ 开始）。每个 $$$A_i$$$ 满足 $$$0 \le A_i \lt 10^9$$$ 。对于区间 $$$[l,r]$$$ ，定义
$$$$$$ value(l,r)=A_l\cdot(10^9)^{r-l}+A_{l+1}\cdot(10^9)^{r-l-1}+\cdots+A_r. $$$$$$
也就是说，每个块都视为固定 $$$9$$$ 位十进制块来拼接。允许块本身有前导零。例如数组片段 $$$[1,23]$$$ 表示整数 $$$1000000023$$$ ，而不是 $$$123$$$ 。
特别地，$$$10^{20000}$$$ 有 $$$20001$$$ 位十进制数字，是合法上界而不是非法值。由于一个块表示 $$$9$$$ 位十进制数字，且 $$$10^{20000}=100\cdot(10^9)^{2222}$$$ ，当一段长度为 $$$2223$$$ 、形如 $$$[100,0,0,\ldots,0]$$$ 的块被拼接时，它表示的正是 $$$10^{20000}$$$ 。
游戏开始时，鳄鱼拥有的数值 $$$x=0$$$ ，小老鼠拥有的数值 $$$y=0$$$ 。
鳄鱼将按顺序执行 $$$q_1$$$ 次操作，每次操作的对象是它当前的数值 $$$x$$$ 。
小老鼠将按顺序执行 $$$q_2$$$ 次操作，每次操作的对象是它当前的数值 $$$y$$$ 。
如果某动物的操作次数为 $$$0$$$ ，则其数值保持初始值 $$$0$$$ 。
每次操作包含三个参数：$$$op,l,r$$$ ，含义如下：
- 首先取数组 $$$A$$$ 中从第 $$$l$$$ 个块到第 $$$r$$$ 个块（包含两端）的连续片段，将其按上述方式视为整数 $$$a=value(l,r)$$$ 。
- 设当前动物的数值为 $$$z$$$（即鳄鱼操作时为 $$$x$$$ ，小老鼠操作时为 $$$y$$$），根据 $$$op$$$ 的值更新 $$$z$$$ ：
- 若 $$$op=0$$$ ，则 $$$z=z+a$$$ ；
- 若 $$$op=1$$$ ，则 $$$z=z-a$$$ ；
- 若 $$$op=2$$$ ，则 $$$z=z\cdot a$$$ 。
所有操作执行完毕后，分别检查两只动物的数值是否处于合法区间 $$$[0,10^{20000}]$$$ ：
- 若 $$$x \lt 0$$$ 或 $$$x \gt 10^{20000}$$$ ，则鳄鱼违规；否则鳄鱼合法。
- 若 $$$y \lt 0$$$ 或 $$$y \gt 10^{20000}$$$ ，则小老鼠违规；否则小老鼠合法。
请注意，操作过程中 $$$x$$$ 和 $$$y$$$ 可以暂时小于 $$$0$$$ 或者大于 $$$10^{20000}$$$ 。你只需要判定所有操作结束后的 $$$x$$$ 和 $$$y$$$ 是否在 $$$[0,10^{20000}]$$$ 内。
换言之，只看最终结果是否满足 $$$0 \le x,y \le 10^{20000}$$$ 。最终结果恰好等于 $$$10^{20000}$$$ 时不违规；最终结果大于 $$$10^{20000}$$$ ，例如 $$$10^{20000}+1$$$ ，才违规。
第一行包含一个整数 $$$T$$$（$$$1 \le T \le 10$$$），表示测试数据的组数。
对于每组测试数据：
第一行包含一个整数 $$$n$$$ （$$$1 \le n \le 2 \cdot 10^4$$$），表示数组长度。
第二行包含 $$$n$$$ 个整数 $$$A_1,A_2,\ldots,A_n$$$（$$$0 \le A_i \lt 10^9$$$），表示十进制块数组。
第三行包含两个整数 $$$q_1,q_2$$$（$$$0 \le q_1 \le 2 \cdot 10^4，0 \le q_2 \le 2 \cdot 10^4$$$） ，分别表示鳄鱼和小老鼠的操作次数。
接下来 $$$q_1$$$ 行，每行包含三个整数 $$$op_i,l_i,r_i$$$（$$$0 \le op_i \le 2$$$ ，$$$1 \le l_i \le r_i \le n$$$），表示鳄鱼的第 $$$i$$$ 次操作。
接下来 $$$q_2$$$ 行，每行包含三个整数 $$$op_i,l_i,r_i$$$（$$$0 \le op_i \le 2$$$ ，$$$1 \le l_i \le r_i \le n$$$），表示小老鼠的第 $$$i$$$ 次操作。
数据保证对于每个测试文件，所有测试数据满足：
$$$$$$ \sum n \le 2 \cdot 10^4,\quad \sum q_1 \le 2 \cdot 10^4,\quad \sum q_2 \le 2 \cdot 10^4. $$$$$$
对于每组测试数据，按以下规则输出结果。注意输出时不要带引号。
- 若双方均违规，输出 'both cheat'。
- 若仅鳄鱼违规（小老鼠合法），输出 'crocodile cheats'。
- 若仅小老鼠违规（鳄鱼合法），输出 'little mouse cheats'。
- 若双方均合法：
- 若 $$$x \gt y$$$ ，输出 'crocodile win'；
- 若 $$$x \lt y$$$ ，输出 'little mouse win'；
- 若 $$$x=y$$$ ，输出 'draw'。
320 1231 10 2 20 1 21101 01 1 131 234567890 02 10 1 22 2 30 2 3
drawcrocodile cheatscrocodile win
样例解释：
- 第一组：鳄鱼取第 $$$2$$$ 个块，得到 $$$123$$$ 。小老鼠取区间 $$$[1,2]$$$ ，因为块宽固定为 $$$9$$$ 位，得到 $$$0\cdot10^9+123=123$$$ 。双方合法且相等，输出 'draw'。
- 第二组：鳄鱼执行 $$$0-10=-10$$$ ，最终违规；小老鼠没有操作，保持 $$$0$$$ ，合法。因此输出 'crocodile cheats'。
- 第三组：鳄鱼先取区间 $$$[1,2]$$$ ，得到 $$$1\cdot10^9+234567890=1234567890$$$ ，再乘以区间 $$$[2,3]$$$ 的值 $$$234567890\cdot10^9$$$ ；小老鼠只取区间 $$$[2,3]$$$ 。双方最终均合法，鳄鱼数值更大，输出 'crocodile win'。
在做出了正确的选择后，托姆渐渐感觉自己的意识离开了虚无之海。然而，当托姆以为自己即将醒来时，他发现他并没有回到现实，而是坠入了更深的一层梦境。这一次，他来到了一个由 hsq 精心设计的迷宫。
这个迷宫中共有 $$$n$$$ 个房间，编号为 $$$1, 2, \ldots, n$$$。每个房间中都有一条无法改变的单向通道：如果托姆当前位于房间 $$$i$$$，那么在 hsq 对他进行一次操控后，他必然会沿着通道进入房间 $$$p_i$$$。
除了所在的房间，托姆还拥有一种梦境状态。梦境状态共有 $$$c$$$ 种，编号为 $$$0, 1, \ldots, c-1$$$。
在每一次操控时，若托姆当前位于房间 $$$i$$$，且当前的梦境状态为 $$$a$$$，hsq 可以将其梦境状态切换为任意状态 $$$b$$$（$$$b$$$ 可以与 $$$a$$$ 相同），并为此付出 $$$w_i(a, b)$$$ 的代价。这个代价可能为负数，表示这次操控反而让 hsq 获得了某种收益。在状态切换完成之后，托姆会立刻沿着房间 $$$i$$$ 的通道进入房间 $$$p_i$$$。
现在有 $$$q$$$ 次询问。每次询问给出四个整数 $$$x, k, s, t$$$，表示托姆初始位于房间 $$$x$$$，初始梦境状态为 $$$s$$$。hsq 需要恰好操控托姆 $$$k$$$ 次，并希望在 $$$k$$$ 次操控结束后，托姆的梦境状态恰好为 $$$t$$$。
请你求出，对于每次询问，hsq 达成目标所需要付出的最小总代价。
第一行包含三个整数 $$$n,c,q$$$ ($$$1 \le n,q \le 10^5$$$，$$$2 \le c \le 5$$$)，分别表示迷宫中的房间数量，梦境状态数量和询问次数。
第二行包含 $$$n$$$ 个整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$)。其中 $$$p_i$$$ 表示如果托姆当前位于房间 $$$i$$$，那么 hsq 操控他一次之后，托姆会进入房间 $$$p_i$$$。
接下来输入 $$$n$$$ 个代价矩阵。
对于每个房间 $$$i$$$ ($$$1 \le i \le n$$$)，输入 $$$c$$$ 行，每行包含 $$$c$$$ 个整数。
第 $$$a+1$$$ 行第 $$$b+1$$$ 个整数表示 $$$w_i(a, b)$$$ ($$$0 \le a,b \lt c$$$，$$$-10^9 \le w_i(a, b) \le 10^9$$$)，即当托姆位于房间 $$$i$$$，且当前梦境状态为 $$$a$$$ 时，hsq 将他的梦境状态切换为 $$$b$$$ 所需付出的代价。
接下来 $$$q$$$ 行，每行包含四个整数 $$$x,k,s,t$$$ ($$$1 \le x \le n$$$，$$$1 \le k \le 10^9$$$，$$$0 \le s,t \lt c$$$)，表示一次询问。
对于每次询问，输出一行一个整数，表示 hsq 恰好操控托姆 $$$k$$$ 次，并使他的最终梦境状态为 $$$t$$$ 时，需要付出的最小总代价。
3 2 3 2 3 2 0 3 -2 1 4 -1 -4 0 1 5 3 -3 1 1 0 1 1 2 0 0 2 3 1 0
3 -1 -7
在样例中，共有 $$$3$$$ 个房间和 $$$2$$$ 种梦境状态。
房间中的通道为：
$$$1 \to 2$$$，$$$2 \to 3$$$，$$$3 \to 2$$$。
对于第一次询问，$$$x=1,k=1,s=0,t=1$$$。
托姆初始位于房间 $$$1$$$，梦境状态为 $$$0$$$。hsq 只需要操控他一次，并让他的梦境状态变为 $$$1$$$。
此时代价为 $$$w_1(0, 1)=3$$$，所以答案为 $$$3$$$。
对于第二次询问，$$$x=1,k=2,s=0,t=0$$$。
托姆经过的房间依次为：
$$$1 \to 2 \to 3$$$。
一种最优方案为：
第一次操控，在房间 $$$1$$$，将梦境状态从 $$$0$$$ 切换为 $$$1$$$，代价为 $$$w_1(0, 1)=3$$$；
第二次操控，在房间 $$$2$$$，将梦境状态从 $$$1$$$ 切换为 $$$0$$$，代价为 $$$w_2(1, 0)=-4$$$。
总代价为 $$$3+(-4)=-1$$$，所以答案为 $$$-1$$$。
hsq 最近在研究二进制位运算 。 他发现了两个神秘的序列 $$$A$$$ 和 $$$B$$$ , 分别包含 $$$N$$$ 和 $$$M$$$ 个 互不相同 的非负整数 。 序列中的所有元素均严格小于 $$$2^K$$$ 。
你需要分别从序列 $$$A$$$ 和序列 $$$B$$$ 中选择一些元素 , 分别构成新的序列 $$$A'$$$ 和 $$$B'$$$ , 使得满足以下所有条件 :
- $$$A'$$$ 是 $$$A$$$ 的子序列 , $$$B'$$$ 是 $$$B$$$ 的子序列 。
- $$$A'$$$ 和 $$$B'$$$ 的长度相等 , 设其长度为 $$$L$$$ 。
- 对于任意 $$$1 \le j \le L$$$ , 选择的元素对 ( $$$A'_j$$$ , $$$B'_j$$$ ) 必须满足 : $$$A'_j \oplus B'_j = 2^K - 1$$$ 。
$$$\oplus$$$ 表示按位异或 （bitwise XOR） 运算 。
请你计算并输出 $$$L$$$ 的最大可能值 。
输入的第一行包含一个正整数 $$$T$$$ , 表示测试数据的组数 。
对于每组测试数据 : 第一行包含三个正整数 $$$N$$$ , $$$M$$$ , $$$K$$$ ( $$$1 \le N , M \le 10^5$$$ , $$$1 \le K \lt 31$$$ ) , 分别表示序列 $$$A$$$ 的长度 、 序列 $$$B$$$ 的长度以及二进制位数 。
第二行包含 $$$N$$$ 个非负整数 $$$A_1 , A_2 , \dots , A_N$$$ ( $$$0 \le A_i \lt 2^K$$$ ) , 表示序列 $$$A$$$ 的元素 。 保证序列 $$$A$$$ 中的元素互不相同 。
第三行包含 $$$M$$$ 个非负整数 $$$B_1 , B_2 , \dots , B_M$$$ ( $$$0 \le B_i \lt 2^K$$$ ) , 表示序列 $$$B$$$ 的元素 。 保证序列 $$$B$$$ 中的元素互不相同 。
数据保证
所有测试数据的 $$$N$$$ 之和不超过 $$$10^5$$$ 。
所有测试数据的 $$$M$$$ 之和不超过 $$$10^5$$$ 。
对于每组测试数据 , 输出一行一个整数 , 表示 $$$L$$$ 的最大可能值 。
23 3 31 4 25 6 34 4 41 2 4 814 13 11 7
24
对于第一组测试数据 , 我们可以选择的子序列为 $$$A' = [1 , 4]$$$ 和 $$$B' = [6 , 3]$$$ , 此时最大长度为 $$$2$$$ 。
对于第二组测试数据 , 我们可以选择的子序列为 $$$A' = [1 , 2 , 4 , 8]$$$ 和 $$$B' = [14 , 13 , 11 , 7]$$$ , 此时最大长度为 $$$4$$$ 。
历经千辛万苦，托姆终于逃离了迷宫。出现在托姆眼前的人，便是梦境世界的制造者——汤姆。只有与汤姆正面交锋并将其击败，托姆才能够彻底逃离梦境世界，并在现实世界中醒来。
场上初始有 $$$n$$$ 只怪物，第 $$$i$$$ 只怪物的初始血量为 $$$h_i$$$。
作为战斗的先手，托姆必须首先从这 $$$n$$$ 只怪物中选出一只，随后汤姆从剩下的 $$$n-1$$$ 只怪物中挑出一只，并将其他的怪物移出游戏。
挑选完毕后，托姆和汤姆轮流行动，其中托姆先手。每次行动时，当前玩家必须从场上血量严格大于 $$$0$$$ 的怪物中选择一只，对其发起一次攻击。
每次攻击造成的伤害为一个整数，该整数在闭区间 $$$[L, R]$$$ 内的所有整数中独立且等概率地随机产生 (即离散均匀分布) 。受到攻击的怪物，其血量将直接减去该次造成的伤害值。
当怪物的血量 $$$\le 0$$$ 时，该怪物被判定为死亡，并立即从场上移除，之后不可再被选中。成功击杀场上最后一只存活的怪物的玩家，将获得整场战斗的胜利。
假设双方都极其聪明，在每一次需要做出选择时，都会采取使自己最终获胜概率最大化的最优策略。托姆想知道，如果他在游戏开始时做出最优的怪物选择，最终能够获胜的最大概率是多少？
第一行包含三个正整数 $$$n$$$ , $$$L$$$ 和 $$$R$$$ $$$(2 \le n \le 2000$$$,$$$1 \le L \le R \le 2000)$$$ ，分别表示初始场上怪物的总数量，以及每次攻击伤害的下界和上界。
第二行包含 $$$n$$$ 个正整数 $$$h_1, h_2, \dots, h_n$$$ $$$(1 \le h_i \le 2000)$$$，表示每只怪物的初始血量 。
输出一个浮点数，表示托姆在双方均采取最优策略的前提下，能够获胜的最大概率。
你的答案将被认为是正确的，当且仅当你的答案与标准答案的绝对误差或相对误差不超过 $$$10^{-6}$$$ 。
3 1 2 1 2 3
0.50
托姆其中的一种最优策略是：
从 $$$3$$$ 只怪物中挑选出血量为 $$$1$$$ 的怪物 。
汤姆此时的最优策略是从剩下的 $$$2$$$ 只怪物中挑选出血量为 $$$2$$$ 的怪物 。
此时托姆能获得最大获胜概率为 $$$1/2$$$ 。
动物园正在举行一场疯狂的动物派对！派对上聚集了来自世界各地的动物，有喜欢美美隐身的鳄鱼 、 躲在地下打洞的老鼠 、 还有到处游走的蜥蜴等 。 它们排成了一排，依次编号为 $$$1$$$ 到 $$$n$$$ 。
为了在嘈杂的派对中保持联系，小动物们需要建立水平激光通讯链路 。 每只小动物 $$$i$$$ 都有一个所在的位置高度 $$$h_i$$$ （例如长颈鹿的高度是正数，而潜水的鳄鱼高度可能是负数） ， 以及一个通讯频段特征值 $$$a_i$$$ 。
当小动物 $$$l$$$ 和小动物 $$$r$$$ （ $$$1 \le l \lt r \le n$$$ ） 尝试进行通讯时，为了保证信号不被中间的动物挡住，通讯信号所在的有效高度 $$$H$$$ 取决于它们之间 （包含它们自己） 所有动物的最低高度，即： $$$$$$H = \min_{i=l}^r h_i$$$$$$
同时，派对专门的环境会对通讯产生干扰，干扰系数为一个常数 $$$K$$$ 。 链路的通讯强度不仅与有效高度有关，还受到两只动物频段异或值的影响。具体来说，它们之间的通讯强度定义为： $$$$$$S(l, r) = H \times ( ( a_l \oplus a_r ) - K )$$$$$$ 其中 $$$\oplus$$$ 表示按位异或运算 。
现在派对到达了高潮，请你作为动物园的网络管理员，计算出在所有可能的通讯对 $$$(l, r)$$$ 中，通讯强度的 最大值 是多少。
第一行包含一个整数 $$$T$$$ （ $$$1 \le T \le 10^4$$$ ） ， 表示测试数据的组数 。
对于每组测试数据： 第一行包含两个整数 $$$n$$$ 和 $$$K$$$ （ $$$2 \le n \le 2 \cdot 10^5$$$ ， $$$0 \le K \lt 2^{31}$$$ ） ， 分别表示小动物的数量和环境干扰系数 。
第二行包含 $$$n$$$ 个整数 $$$h_1, h_2, \dots, h_n$$$ （ $$$-10^8 \le h_i \le 10^8$$$ ） ， 表示每只小动物所在的高度 。
第三行包含 $$$n$$$ 个整数 $$$a_1, a_2, \dots, a_n$$$ （ $$$0 \le a_i \lt 2^{31}$$$ ） ， 表示每只小动物的通讯频段特征值 。
数据保证所有测试数据的 $$$\sum n \le 2 \cdot 10^5$$$ 。
对于每组测试数据，输出一行，包含一个整数，表示所有通讯对中通讯强度的最高值 。
25 1010 -10 10 -10 1012 5 2 8 143 82 -5 38 9 1
8035
对于第一组测试数据： $$$n = 5$$$ ， $$$K = 10$$$ 。
当 $$$l = 1$$$ , $$$r = 5$$$ 时，它们之间的最低高度 $$$H = \min(10, -10, 10, -10, 10) = -10$$$ 。
频段异或值为 $$$a_1 \oplus a_5 = 12 \oplus 14 = 2$$$ 。
通讯强度为 $$$S(1, 5) = -10 \times (2 - 10) = -10 \times (-8) = 80$$$ ，这是所有组合中的最高值 。
hsq 是一个社交达人 ， 他加入了许多群聊 。 为了更方便地了解和朋友们的共同兴趣 ， 他想要统计好友之间有多少个共同群聊 。
在这个社交网络中 ， 共有 $$$n$$$ 个人 ， 编号从 $$$1$$$ 到 $$$n$$$ 。 已知目前存在 $$$m$$$ 个群聊 ， 每个群聊的成员信息均已给出 。 现在共有 $$$q$$$ 次询问 ， 每次给出两个不同的人 $$$u$$$ 和 $$$v$$$ ， 请你计算他们两人同时出现在多少个群聊中 。
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) ， 表示测试数据的组数 。
对于每组测试数据 ：
第一行包含三个整数 $$$n$$$ ， $$$m$$$ 和 $$$q$$$ （ $$$2 \le n \le 2 \cdot 10^5$$$ ， $$$1 \le m, q \le 2 \cdot 10^5$$$ ， 且 $$$m \cdot q \le 2 \cdot 10^5$$$ ） ， 分别表示总人数 、 群聊总数和询问次数 。
接下来的 $$$m$$$ 行 ， 每行描述一个群聊的信息 。 首先是一个整数 $$$k$$$ ($$$3 \le k \le n$$$) ， 表示该群聊的人数 ； 接着是 $$$k$$$ 个整数 $$$id_1 , id_2 , \dots , id_k$$$ ($$$1 \le id_i \le n$$$) ， 表示群员的编号 。 数据保证每个群聊内的编号 $$$id$$$ 严格递增且不重复 。
接下来的 $$$q$$$ 行 ， 每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u , v \le n$$$ , $$$u \ne v$$$) ， 表示一次询问 。
数据保证
所有测试数据的 $$$n$$$ 之和不超过 $$$2 \times 10^5$$$ 。
所有测试数据的 $$$k$$$ 之和不超过 $$$5 \times 10^5$$$ 。
数据保证所有测试数据的 $$$m \cdot q$$$ 之和不超过 $$$2 \times 10^5$$$
对于每组测试数据的每次询问 ， 输出一行一个整数 ， 表示 $$$u$$$ 和 $$$v$$$ 共同拥有的群聊数量 。
15 2 23 1 2 33 1 2 41 21 4
21
对于样例中的第一次询问 ： 用户 $$$1$$$ 和用户 $$$2$$$ 同时出现在了第一个群聊 $$$\{1 , 2 , 3\}$$$ 和第二个群聊 $$$\{1 , 2 , 4\}$$$ 中 ， 因此共同群聊数为 $$$2$$$ 。
对于样例中的第二次询问 ： 用户 $$$1$$$ 和用户 $$$4$$$ 仅同时出现在了第二个群聊 $$$\{1 , 2 , 4\}$$$ 中 ， 因此共同群聊数为 $$$1$$$ 。
末日之战的场面犹如太空上的赤壁之战、火烧连营。人类联合舰队像一条绑成一串的蚂蚱，被水滴整整的一列洞穿。炸到第三列时，傲慢的人类战舰终于意识到要逃跑，可水滴以一种超出人类理解的锐角转弯迅速拦截，像一枚死神的绣花针。
水滴除了一列一列穿透每一艘战舰的核聚变燃料舱外 ，还能够通过在每一列战舰的 薄弱点 释放特殊电磁波来瘫痪一整列人类联合舰队。舰队共有 $$$n$$$ 艘 ，可以假设其所处位置都在一根数轴上 ，第 $$$i$$$ 艘战舰的位置为 $$$X_i$$$ 。 薄弱点 被定义为数轴上到这一列战舰的距离之和最小的点构成的区间的中点。
但是人类联合舰队的垂死挣扎会让薄弱点位置更改 ，请在每次人类舰队的行为发生后计算薄弱点的位置。舰队共有三种行为：
行为 $$$1$$$ ：一艘新战舰加入到这一列的 $$$K$$$ 位置。
行为 $$$2$$$ ：所有战舰向右移动 $$$K$$$ 个单位。
行为 $$$3$$$ ：所有战舰位移到关于 $$$x=K$$$ 对称的位置。
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ （ $$$1 \le n , m \le 2 \cdot 10^5$$$ ） ， 分别表示初始战舰个数与行为个数 。
第二行包含 $$$n$$$ 个整数 $$$X_1, X_2, \dots, X_n$$$ （ $$$-10^6 \le X_i \le 10^6$$$ ） ， 表示每艘战舰的初始位置 。
接下来 $$$m$$$ 行 ， 每行包含两个整数 $$$op$$$ 和 $$$K$$$ （ $$$1 \le op \le 3$$$ ， $$$-10^6 \le K \le 10^6$$$ ） ， 分别表示行为编号和行为内容：
若 $$$op = 1$$$ ， 表示一艘新战舰加入到 $$$K$$$ 位置 。
若 $$$op = 2$$$ ， 表示所有战舰向右移动 $$$K$$$ 个单位 。
若 $$$op = 3$$$ ， 表示所有战舰移动到关于 $$$x=K$$$ 对称的位置 。
所有行为都按照时间顺序给出 ， 且同一位置可能存在多艘战舰 。
共输出 $$$m+1$$$ 行。
第一行输出人类舰队所有行为发生前的薄弱点位置。
接下来的 $$$m$$$ 行 ，对于每次行为产生后 ，输出当前舰队的薄弱点位置。
选手输出的答案与标准答案的绝对误差或相对误差不超过 $$$10^{-4}$$$ 即被视为正确。
3 44 2 11 31 52 13 5
2.0000000000 2.5000000000 3.0000000000 4.0000000000 6.0000000000
初始时 ，战舰的位置为 $$$1, 2, 4$$$ 。数轴上到所有战舰距离之和最小的区间为 $$$[2, 2]$$$ ，该区间的中点为 $$$2.0$$$ 。
第一次行为后 ，新增一艘位于 $$$3$$$ 的战舰 ，所有战舰位置为 $$$1, 2, 3, 4$$$ 。数轴上到所有战舰距离之和最小的区间为 $$$[2, 3]$$$ ，该区间的中点为 $$$2.5$$$ 。
第二次行为后 ，新增一艘位于 $$$5$$$ 的战舰 ，所有战舰位置为 $$$1, 2, 3, 4, 5$$$ 。数轴上到所有战舰距离之和最小的区间为 $$$[3, 3]$$$ ，该区间的中点为 $$$3.0$$$ 。
第三次行为后 ，所有战舰向右移动 $$$1$$$ 个单位 ，所有战舰位置变为 $$$2, 3, 4, 5, 6$$$ 。数轴上到所有战舰距离之和最小的区间为 $$$[4, 4]$$$ ，该区间的中点为 $$$4.0$$$ 。
第四次行为后 ，所有战舰关于 $$$x=5$$$ 对称 ，所有战舰位置变为 $$$4, 5, 6, 7, 8$$$ 。数轴上到所有战舰距离之和最小的区间为 $$$[6, 6]$$$ ，该区间的中点为 $$$6.0$$$ 。
给定一个包含 $$$n$$$ 个点的二维点集 $$$P$$$ 。 我们定义点集 $$$P$$$ 的一个凹包为 ： 从 $$$P$$$ 中选出若干个点作为顶点 ， 按某种顺序连接而成的简单多边形 ， 满足其面积严格大于 $$$0$$$ ， 且凹 （即多边形内部至少存在一个内角严格大于 $$$180^\circ$$$ ） 。
现在共有 $$$q$$$ 次独立的询问 。 每次询问给定一条线段 $$$S$$$ ， 请你判断 ： 是否存在至少一个由 $$$P$$$ 的子集构成的合法凹包 ， 使得该凹包 （包含其内部与边界） 与线段 $$$S$$$ 有交集 ？
凹包 第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ( $$$3 \le n \le 2 \times 10^5$$$ , $$$1 \le q \le 2 \times 10^5$$$ ) ， 分别表示点集 $$$P$$$ 中的点的数量以及询问的次数 。
接下来的 $$$n$$$ 行 ， 每行包含两个整数 $$$x$$$ 和 $$$y$$$ ( $$$-10^9 \le x , y \le 10^9$$$ ) ， 表示点集 $$$P$$$ 中一个点的坐标 。 数据保证这 $$$n$$$ 个点互不相同 。
接下来的 $$$q$$$ 行 ， 每行包含四个整数 $$$x_1$$$ , $$$y_1$$$ , $$$x_2$$$ 和 $$$y_2$$$ ( $$$-10^9 \le x_1 , y_1 , x_2 , y_2 \le 10^9$$$ ) ， 表示一次询问中线段 $$$S$$$ 的两个端点分别为 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 。 数据保证每次询问的线段端点不重合 。
对于每次询问 ， 如果存在至少一个合法的凹包与线段 $$$S$$$ 相交 ， 请在一行中单独输出 Yes ； 否则 ， 输出 No 。
5 20 04 04 40 42 2-1 -1 -2 -21 1 5 5
No Yes
对于唯一的一组样例 ：
第一组询问 ， 给定线段从 $$$(-1, -1)$$$ 到 $$$(-2, -2)$$$ 。 该线段绝对无法与任何可能的凹包相交 ， 答案为 No 。
第二组询问 ， 给定线段从 $$$(1, 1)$$$ 到 $$$(5, 5)$$$ 。
我们可以构造多边形 $$$(0, 0)$$$ $$$(4, 0)$$$ $$$(4, 4)$$$ $$$(2, 2)$$$ $$$(0, 4)$$$ ， 这是一个合法的凹包 ， 与该线段相交 ， 因此答案为 Yes 。
这是一个 run-twice（通信）题。
灵梦有一个大小为 $$$n$$$ 的整数集合 $$$S$$$，为了防止魔理沙偷走其中的 $$$k$$$ 个数字，灵梦需要提前记录下 $$$k$$$ 个数字来防止她忘记被偷走的数字是什么。
也就是说，刚开始灵梦知道这 $$$n$$$ 个数字，并且知道魔理沙将会偷走其中的 $$$k$$$ 个数字，但是她不知道魔理沙具体会偷走哪些数字。灵梦会偷偷藏下 $$$k$$$ 个数字来应对魔理沙的偷窃行为。
当魔理沙把 $$$k$$$ 个数字偷走后，灵梦要从剩下的 $$$n-k$$$ 个数字以及她私藏的 $$$k$$$ 个数字中，还原出魔理沙偷走的 $$$k$$$ 个数字。
你的任务是设计一种策略，帮助灵梦来应对魔理沙。
第一次运行：
输入的第一行首先包含 first。这样做的目的是让你的程序认识到这是它的第一次运行，并且它应该充当刚开始的灵梦。
每个测试点包含多个测试用例。第一行包含一个整数 $$$t\ (1 \le t \le 1000)$$$，表示测试用例的数量。
每个测试点的第一行包含两个整数 $$$n,k\ (2 \le n \le 10^5, 1 \le k \le \min(n-1, 5000))$$$，表示灵梦初始拥有的数字个数和魔理沙将会偷走的数字个数。
接下来一行包含 $$$n$$$ 个两两不同的整数 $$$a_1,a_2,\cdots,a_n$$$ $$$(0 \le a_i \lt 2^{29})$$$，表示灵梦初始拥有的数字。
保证所有测试数据 $$$n$$$ 之和不超过 $$$10^5$$$，$$$k$$$ 之和不超过 $$$5000$$$。
第二次运行：
输入的第一行首先包含 second。这样做的目的是让你的程序认识到这是它的第二次运行，并且它应该充当数字被偷走的灵梦。
每个测试点包含多个测试用例。第一行包含一个整数 $$$t\ (1 \le t \le 1000)$$$，表示测试用例的数量。
每个测试点的第一行包含两个整数 $$$n,k\ (2 \le n \le 10^5, 1 \le k \le \min(n-1, 5000))$$$，表示灵梦初始拥有的数字个数和魔理沙已经偷走的数字个数。
接下来一行包含 $$$n-k$$$ 个两两不同的整数 $$$a_1,a_2,\cdots,a_{n-k}$$$ $$$(0 \le a_i \lt 2^{29})$$$，表示灵梦被偷走后剩下的数字。
接下来一行包含 $$$k$$$ 个整数 $$$b_1,b_2,\cdots,b_{k}$$$ $$$(0 \le b_i \lt 2^{30})$$$，表示灵梦私藏的数字。
保证所有测试数据 $$$n$$$ 之和不超过 $$$10^5$$$，$$$k$$$ 之和不超过 $$$5000$$$。
第一次运行：
对于每个测试用例，输出一行 $$$k$$$ 个整数 $$$b_1,b_2,\cdots,b_{k}$$$ $$$(0 \le b_i \lt 2^{30})$$$，表示灵梦私藏的数字。
第二次运行：
对于每个测试用例，输出一行 $$$k$$$ 个两两不同的整数 $$$c_1,c_2,\cdots,c_{k}$$$ $$$(0 \le c_i \lt 2^{29})$$$，表示魔理沙偷走的数字，输出数字的顺序可以是任意的。
注意：非 C++ 语言在程序输出之后需要刷新缓冲区，否则你会得到 IDLENESS_LIMIT_EXCEEDED。
first 2 4 1 1 2 3 4 6 3 11 45 14 19 198 10
4 114514 1919 810
second 2 4 1 2 3 4 4 6 3 11 19 10 114514 1919 810
1 45 198 14
hsq 现在有一个仅由字符 u, s, t 组成的字符串 ， 他正在仔细地数 ， 每次从中提取一个不相交的子序列 ， 最多能提取出多少个 usst ( 上海理工大学的英文缩写 ) 。
这个时候 zzj 来了 ， 他觉得 hsq 的这个问题太简单了 ， 于是在字符串上泼了一些墨水 。
hsq 回来可太难过了 ， 他拼尽全力 ， 发现原字符串中有些字符被墨水严重覆盖 ， 变成了一种模糊的类型 1 ：
类型 1 ， 它原本可能是 u 或者 t 。
其他没有被覆盖的字符依然清晰地显示为 u, s 或 t 。
现在你获得了这个被墨水污染的字符串 ， 请你帮助 hsq 判断出 ， 在最好的情况下 ( 即由你来决定每个 1 具体代表 u 还是 t ) ， 最多可能提取出多少个 互不相交 的 usst 子序列 。
第一行包含一个整数 $$$T$$$ （ $$$1 \le T \le 10^5$$$ ） ， 表示测试数据的组数 。
对于每组测试数据 ： 第一行包含一个整数 $$$n$$$ （ $$$1 \le n \le 2 \cdot 10^5$$$ ） ， 表示字符串 $$$S$$$ 的长度 。 第二行包含一个长度为 $$$n$$$ 的字符串 $$$S$$$ ， 字符串仅由字符 u, s, t 以及 1 组成 。
数据保证所有测试数据的 $$$\sum n \le 2 \cdot 10^5$$$ 。
对于每组测试数据 ， 输出一行一个整数 ， 表示在最优策略下 ， 最多能提取出的互不相交的 usst 子序列的数量 。
25u1sst8ususs1st
12
对于第一组测试数据，可以将 1 替换为 u，字符串变为 ussst，此时最多可以提取出 1 个 usst 子序列（例如选择下标为 1, 3, 4, 5 的字符）。
对于第二组测试数据，可以将 1 替换为 t，字符串变为 ususstst。此时我们可以提取出 2 个 互不相交 的 usst 子序列：
第一个子序列选择下标为 1, 2, 4, 6 的字符（对应字符分别为 u, s, s, t）；
第二个子序列选择下标为 3, 5, 7, 8 的字符（对应字符分别为 u, s, s, t）。
有一天 ， CirnoNine 给 hsq 出了一道找规律的问题 ： $$$$$$1 , 1 , 4 , 5 , 1 , (\quad)$$$$$$
hsq 觉得这道题实在是太难了 ， 他观察了很久也找不出这里面究竟有什么规律 。
聪明的你快来帮帮他 ， 给出一个合理的后续数字吧 ！
None
输出一个 $$$64$$$ 位有符号整数 （ 即在 $$$[-2^{63} , 2^{63} - 1]$$$ 范围内的整数 ） 。
注意 ： 你只需要保证输出的格式是一个合法的 $$$64$$$ 位有符号整数即可 ， 任何在这个范围内的整数都会被判定为正确 。
None
114514
在遥远的构造王国中 ， 坐落着 $$$m$$$ 座城邦 ， 居住着 $$$n$$$ 名居民 。
第 $$$j$$$ 座城邦由两位守门人驻守 ， 他们的编号分别为 $$$2j-1$$$ 和 $$$2j$$$ 。 第 $$$i$$$ 名居民的编号则为 $$$2m+i$$$ 。
起初 ， 王国中的任意两人均互为朋友 。 然而 ， 按照王国的法则 ， 若两人并非朋友 ， 他们便无法同时踏入同一座城邦 。
构造水晶为每位居民降下了指引 ： 第 $$$i$$$ 名居民必须前往并进入第 $$$c_i$$$ 座城邦 。
为了确保第 $$$i$$$ 名居民绝对无法进入其他任何城邦 $$$j$$$ （ 即满足 $$$j \neq c_i$$$ ） ， 你必须使该居民与第 $$$j$$$ 座城邦的至少一位守门人解除朋友关系 。 换言之 ， 对于所有满足 $$$j \neq c_i$$$ 的城邦 $$$j$$$ ， 你需要在 $$$(2m+i , 2j-1)$$$ 与 $$$(2m+i , 2j)$$$ 这两对朋友关系中 ， 至少断绝其中一条 。 与此同时 ， 王国希望在满足条件的前提下 ， 能够保留尽可能多的朋友关系 。
在被断绝的朋友关系中 ， 若被解除关系的一方为某座城邦的 ' 第一位守门人 ' （ 即编号为奇数的守门人 ） ， 那么此次关系的断绝将在该居民与该守门人身上各留下一道 ' 赤印 ' 。
此时 ， 构造水晶施加了额外的束缚 ： 其一 ， 第 $$$i$$$ 名居民的身上必须恰好背负 $$$p_i$$$ 道赤印 ； 其二 ， 第 $$$j$$$ 座城邦的第一位守门人身上必须恰好汇聚 $$$q_j$$$ 道赤印 。
你需要判断是否存在一种断绝朋友关系的方案 ， 能够同时满足以下所有条件 ： 首先 ， 确保每名居民只能进入水晶所指定的唯一城邦 ； 其次 ， 所有居民与城邦第一位守门人身上的赤印数量均严格符合上述限制 ； 最后 ， 在满足以上所有前提下 ， 使得最终保留下来的朋友关系总数达到最大 。
若存在这样的方案 ， 请给出任意一种合法的关系断绝列表 ； 若无论如何均无法达成 ， 则输出 $$$-1$$$ 。
输入的第一行包含两个正整数 $$$n$$$ 与 $$$m$$$ （ $$$1 \le n , m \le 1000$$$ ） ， 分别代表王国的居民数量与城邦数量 。
第二行包含 $$$n$$$ 个正整数 $$$c_1 , c_2 , \dots , c_n$$$ （ $$$1 \le c_i \le m$$$ ） ， 其中 $$$c_i$$$ 表示构造水晶为第 $$$i$$$ 名居民指定的城邦编号 。
第三行包含 $$$n$$$ 个非负整数 $$$p_1 , p_2 , \dots , p_n$$$ （ $$$0 \le p_i \le m-1$$$ ） ， 其中 $$$p_i$$$ 表示第 $$$i$$$ 名居民身上必须恰好拥有的赤印数量 。
第四行包含 $$$m$$$ 个非负整数 $$$q_1 , q_2 , \dots , q_m$$$ （ $$$0 \le q_j \le n$$$ ） ， 其中 $$$q_j$$$ 表示第 $$$j$$$ 座城邦的第一位守门人身上必须恰好拥有的赤印数量 。
若不存在任何满足所有条件的合法方案 ， 请仅输出一行一个整数 $$$-1$$$ 。
若存在合法方案 ， 请在第一行输出一个非负整数 $$$D$$$ （ $$$0 \le D \le 10^6$$$ ） ， 表示为了达成目标而需要断绝的朋友关系总数 。
随后输出 $$$D$$$ 行 ， 每行包含两个正整数 $$$u$$$ 与 $$$v$$$ （ $$$1 \le u , v \le 2m+n$$$ 且 $$$u \neq v$$$ ） ， 表示你选择断绝编号为 $$$u$$$ 和 $$$v$$$ 两人之间的朋友关系 。
你输出的每一对朋友关系必须互不相同 （ 即同一条关系不可被重复断绝 ） 。 断绝这些关系后 ， 必须严格满足题目描述中的所有限制条件 ， 并且在合法前提下使剩余的朋友关系数量达到最大 。 若存在多种符合条件的最优方案 ， 输出其中任意一种即可 。 此外 ， 任何未被输出的编号对之间将依然保持原始的朋友关系 。
3 3 1 2 3 1 1 0 1 1 0
6 7 3 7 6 8 1 8 6 9 2 9 4
可怜的 hsq 被通知周末连续两天上计组实验课 ， 但是他根本不会计组 。 计组实验的代码都是 克劳德先生 帮他完成的 。
等检查的时候 ， 老师问他 ： 这个七段数码管的显示原理是什么 ？ 译码器是怎么工作的 ？ 你现在显示的是 $$$1$$$ ， 我想显示 $$$2$$$ ， 你该怎么改输入 ？
hsq 当场就是一个投降 。 回到寝室后 ， 他痛定思痛 ， 开始研究数码管的显示效果 。
他发现 ， 实验板上的模块可以抽象成一个 $$$4n$$$ 位的移位寄存器 ， 寄存器中的信号每 $$$4$$$ 位被划分为一组 ， 作为一个二进制数 （ 规定高位在前 ， 例如 $$$0001$$$ 对应 $$$1$$$ ， $$$1000$$$ 对应 $$$8$$$ ， 转化后的十进制数字范围为 $$$0 \sim 15$$$ ） 输入到译码器中 ， 从而在 $$$n$$$ 个数码管上显示出 $$$n$$$ 个数字组成的数组 。
现在他有一串长度为 $$$4n$$$ 的环形二进制数据流 $$$S$$$ ， 但是他不知道应该从环上的哪个位置作为起始点 （ 即切口 ） 来拉直并读取这 $$$4n$$$ 位信号 。
他希望数据流解析完毕后 ， 能够在其解码出的 $$$n$$$ 个数字组成的数组中 ， 出现连续的子数组 $$$1, 2, 0$$$ （ 恰好他的寝室门牌号就是 $$$120$$$ ） 。
给定数据流 $$$S$$$ ， 请你帮他计算一下 ， 在所有的 $$$4n$$$ 个可能的起始点中 ， 有多少个起点解析出的数组包含至少一个连续的子数组 $$$1, 2, 0$$$ ？
第一行包含一个正整数 $$$t$$$ ( $$$1 \le t \le 10^4$$$ ) ， 表示测试数据的组数 。
对于每组测试数据 ：
第一行包含一个正整数 $$$n$$$ ( $$$3 \le n \le 10^5$$$ ) ， 表示解码后的整数数组长度 。
第二行包含一个长度为 $$$4n$$$ 的 $$$01$$$ 字符串 $$$S$$$ ， 表示环形数据流 （ 输入以线性串的形式给出 ， 实际首尾相连构成环 ） 。
数据保证 ， 在所有的测试数据中 ， $$$n$$$ 的总和不超过 $$$10^5$$$ 。
对于每组测试数据 ， 输出一行一个整数 ， 表示满足条件的起始点数量 。
2300010010000040001001000001111
12
在第一组测试数据中 ， 当起始点为 $$$0$$$ 时 ， 拉直后的字符串为 $$$000100100000$$$ ， 按 $$$4$$$ 位一组解码得到数组 $$$[ 1, 2, 0 ]$$$ ， 包含连续子数组 $$$1, 2, 0$$$ ， 因此是一个合法的起点 。
当起始点为 $$$1$$$ 时 ， 拉直后的字符串为 $$$001001000000$$$ ， 解码得到数组 $$$[ 2, 4, 0 ]$$$ ， 不包含连续子数组 $$$1, 2, 0$$$ ， 因此不是合法的起点 。
遍历所有 $$$12$$$ 个可能的起点 ， 最终只有 $$$1$$$ 个起点符合条件 。
在第二组测试数据中 ， 起始点为 $$$0$$$ 和 $$$12$$$ 时 ， 均能解码出连续的 $$$1, 2, 0$$$ ， 因此共有 $$$2$$$ 个合法的起始点 。