Asrit 有 $$$n$$$ 包馍片，它们排成一排。馍片共有 $$$5$$$ 种不同的味道：香葱味、孜然味、烧烤味、麻辣味、牛肉味。为了方便，我们将味道分别记为 $$$1 \sim 5$$$，其中第 $$$i$$$ 包馍片的味道为 $$$a_i$$$。

每当 Asrit 吃一包馍片时，他会获得 $$$1$$$ 点开心度。但是，总是吃同一种味道的馍片会很乏味。具体来说，如果 Asrit 先吃了一包味道为 $$$x$$$ 的馍片，紧接着吃的下一包馍片味道为 $$$y$$$，则他会额外获得 $$$(y - x + 5) \bmod 5$$$ 点开心度。

为了吃得更美味，Asrit 决定调整吃馍片的顺序。他会按照初始顺序依次处理每一包馍片，对于当前处理的馍片，选择是否将其扔到序列的最后。注意，一包馍片不能被扔两次，不然它会碎掉。

处理完所有馍片后，Asrit 会按照新的顺序依次吃掉它们。请问 Asrit 可以获得的最大开心度是多少？

给定一棵 $$$n$$$ 个节点的无根树 $$$T$$$，节点编号为 $$$1$$$ 到 $$$n$$$，每条边有一个整数边权（可能为负）。

定义树上两点 $$$a,b$$$ 的距离 $$$\operatorname{dis}(a,b)$$$ 为它们之间的唯一简单路径上的边权之和。

现有 $$$q$$$ 次查询，每次查询给定两个节点 $$$x$$$ 和 $$$y$$$，请你计算并输出： $$$$$$ \max_{u \in T}\bigl(\operatorname{dis}(x,u)+\operatorname{dis}(y,u)\bigr) $$$$$$

我们可以定义 $$$AB$$$ 表示两个字符串 $$$A$$$，$$$B$$$ 相连接，例如 $$$A = \texttt{aab}$$$，$$$B = \texttt{ab}$$$，则 $$$AB = \texttt{aabab}$$$。

并递归地定义 $$$A^1=A$$$，$$$A^n = A^{n - 1} A$$$（$$$n \ge 2$$$ 且为正整数）。例如 $$$A = \texttt{abb}$$$，则 $$$A^3=\texttt{abbabbabb}$$$。

现给定一个长度为 $$$n$$$ 的字符串 $$$S$$$，给定常数 $$$k$$$，求 $$$S = A^iB_1B_2\dots B_kC^j$$$ 的方案数，其中 $$$A,B_1,B_2,\dots,B_k,C$$$ 为任意非空字符串，$$$i,j$$$ 为任意正整数。

两种方案不同当且仅当 $$$A$$$、$$$B_1$$$、$$$B_2$$$、$$$\dots$$$、$$$B_k$$$、$$$C$$$、$$$i$$$、$$$j$$$ 中有至少一个字符串或数字不同。

答案要对 $$$998244353$$$ 取模。

宁宁现在在建设大楼！

在宁宁的规划中，大楼有 $$$n$$$ 层，从下到上依次为第 $$$1, 2, \cdots, n$$$ 层，她还要建设 $$$m$$$ 个电梯，每个电梯一定会停在第 $$$1$$$ 层和第 $$$n$$$ 层，她可以选择让这些电梯停在中间某些层（也可以不停）。她希望建设的这 $$$m$$$ 个电梯满足：对于任意不同的两层 $$$x, y$$$，存在一个电梯使 $$$x, y$$$ 可以直达（中间不经过任何可以停的层）。为了降低建造成本，她希望电梯数 $$$m$$$ 尽量小。

宁宁她不太聪明，于是她转过来求助你，希望你能告诉她 $$$m$$$ 的最小值并给出构造。

你不需要最小化停的总层数。但还是为了节约资源，你需要使得停的总层数不超过 $$$2 \times 10^6$$$。

这是一道交互题。

给定正整数 $$$n$$$，评测机会生成一个未知的长度为 $$$n$$$ 的 $$$\texttt{01}$$$ 序列 $$$a_1,a_2,\dots,a_n$$$，你最多可以问评测机 $$$17$$$ 个问题，来求解这个 $$$\texttt{01}$$$ 序列中 $$$\texttt{1}$$$ 的个数，即 $$$\sum\limits_{i=1}^n a_i$$$。数据保证至少有一个 $$$\texttt{1}$$$。

对于每一次询问，你可以选择若干个位置 $$$i_1,i_2,\dots,i_k$$$，设 $$$I=\{i_1,i_2,\dots,i_k\}$$$，评测机会返回 $$$(\sum\limits_{j\in I} a_j) \cdot (\sum\limits_{j\notin I} a_j)$$$ 的结果。

对于询问，请按以下格式输出一行（不包括引号）：

"$$$?\ k\ i_1\ i_2\ \dots\ i_k$$$" $$$(1\le k\le n,1\le i_1 \lt i_2 \lt \dots \lt i_k\le n)$$$。

对于输出答案，请按以下格式输出一行（不包括引号）：

"$$$!\ s$$$"，其中 $$$s=\sum\limits_{i=1}^n a_i$$$。

输出答案本身不计入查询次数。

交互器是非自适应的，也就是说，答案在参与者提出任何查询之前就已经确定了，并且不会依赖于参与者所提出的查询。

在输出每个查询之后，不要忘记输出换行并刷新输出缓冲区。

你可以使用如下语句来清空缓冲区：

• 对于 C/C++：fflush(stdout)
• 对于 C++：std::cout <{}< std::flush
• 对于 Java：System.out.flush()
• 对于 Python：sys.stdout.flush()

A国要举办世界杯了！

为了迎接世界杯的到来，A国打算修建高铁连接所有举办城市。（A国目前还没有修建高铁）

A国有 $$$n$$$ 个城市，$$$m$$$ 条线路有条件修建高铁，每条线路有各自的修建难度系数。

为了更好地施工，A国打算进口一台高级设备。但由于经费紧张，只能进口一台。如果进口了一台价格为 $$$V$$$ 的设备，那么该设备可以修所有难度系数不超过 $$$V$$$ 的路线。

此外，每个城市有一个繁荣程度。为了展现国家实力，A国肯定要在最繁荣的几个城市举办比赛。但随着时间的推移，每个城市的繁荣程度也在不断发生变化。

作为A国元首，你想知道，在当前局面下，若选择最繁荣的 $$$k$$$ 个城市举办比赛，想用高铁连接这些城市，至少需要花费多少经费（购买设备）。

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$（仅由小写字母组成，下标从 $$$1$$$ 开始），进行 $$$q$$$ 次询问，每次询问给出两个整数 $$$l,r$$$，询问子串 $$$s[l,r]$$$ 中出现次数最多的子串出现了多少次。

注：字符串 $$$s$$$ 的子串定义为 $$$s$$$ 中连续且顺序一致的一段字符序列，即对于下标 $$$l, r$$$ $$$(1 \le l \le r \le |s|)$$$，子串 $$$s[l,r]$$$ 表示为 $$$s_l s_{l+1} \dots s_r$$$。

南昌拌粉是当地早餐的灵魂，而一碗正宗拌粉的关键在于配料的搭配。老字号"万方"拌粉有一份祖传秘方：一碗拌粉的总鲜度与总辣度的比值必须恰好等于 $$$A:B$$$，只有这样才能激发出最绝妙的口感。

现在店里有 $$$n$$$ 种配料可供选择，第 $$$i$$$ 种配料的鲜度为 $$$U_i$$$，辣度为 $$$D_i$$$，价格为 $$$C_i$$$。每种配料最多只能加一份。

你带了 $$$M$$$ 块钱，想要选择至少一种配料加入拌粉中。你需要满足以下条件：

• 所选配料的总价格不超过 $$$M$$$；
• 所选配料的总鲜度与总辣度的比值恰好为 $$$A:B$$$。

在所有满足条件的方案中，你希望拌粉的总鲜度尽可能大。求这个最大总鲜度。如果无论如何都无法配出绝妙比例，输出 $$$-1$$$。

五月二十四日，是小 X 的生日。为了庆祝他的生日，他的朋友们为他准备了一个生日聚会。这个聚会上有一样非常重要的道具——灯带。这个灯带上需要放 $$$n$$$ 个灯（不能有位置不放），每个灯可以是红、绿、蓝三种颜色之一。为了尽可能地降低成本，朋友们只分别准备了 $$$r, g, b$$$ 个红、绿、蓝色灯，且恰好一共准备了 $$$n$$$ 个灯。

但是，小 X 对灯带是有自己的喜好的。具体来说，他的喜好包含 $$$m$$$ 对数 $$$(l_1, r_1), \dots, (l_m, r_m)$$$，他希望对于每一个 $$$i$$$，第 $$$l_i \sim r_i$$$ 个灯当中包含最多两种不同的颜色。保证对任意 $$$1 \le i \le m$$$，都有 $$$1 \le l_i \le r_i \le n$$$，且对任意 $$$1 \le i \lt j \le m$$$，都有 $$$r_i \lt l_j$$$ 或者 $$$r_j \lt l_i$$$（即区间 $$$[l_i, r_i]$$$ 和 $$$[l_j, r_j]$$$ 不交）。

现在小 X 的朋友们需要构造一个方案满足小 X 的喜好。但准备的灯实在是太多了，朋友们很难很快想出一种方案，于是来求助于会编程的你。请你帮帮他们，构造一种满足小 X 的喜好的灯带方案，或者告诉他们方案不存在。

夏天到了，又到了蛇蛇出来觅食的季节。

蛇蛇生活的地方可以看成一个二维平面，它位于原点 $$$(0,0)$$$。平面上有 $$$n$$$ 个食物，第 $$$i$$$ 个食物位于整数坐标 $$$(x_i,y_i)$$$，保证没有食物位于原点。

蛇蛇的觅食方式很特殊：

1. 先选择一个以原点为圆心的角度区间 $$$[\alpha,\beta]$$$；
2. 以原点为顶点，张开一个以该区间为圆心角的扇形，并且扇形会不断向外扩展，直到将该角度区间内（包含边界）的所有食物全部一口吞下。

扇形的面积大小就是蛇蛇本顿觅食消耗的能量。

蛇蛇现在很饿，它想知道，想要一口吃掉至少 $$$k$$$ 个食物，所需的最少能量是多少？

库若猫误入了狗群守护的街区，他需要你的帮助!

街区是一个 $$$n \times m$$$ $$$(1 \le n,m \le 2000)$$$ 的网格。每个格子可能是空地、障碍物或狗。每只狗朝向固定的方向（上、下、左或右），它的视线会沿其正前方延伸，直到被障碍物或另一只狗阻挡。

库若猫被困在起点 $$$S$$$，必须从街区出口 $$$E$$$ 逃脱，他的移动遵循以下规则：

• 每一步只能移动到相邻的四个空格（上、下、左、右）之一

• 不能跨越网格边界

• 不能进入任何狗的视线范围内

• 不能经过狗或障碍物所在的格子

你可以让一只狗睡着。睡着的狗会失去视线，但库若猫仍然不能经过它。请判断是否存在一种方案，使得库若猫能够顺利到达出口；如果存在，找出这只狗的坐标。

保证网格中至少存在一只狗，起点 $$$S$$$ 和出口 $$$E$$$ 是空地且不在任何狗的视线内

在 CCPC 省赛的颁奖晚宴上，场地中央摆放着一张巨大的圆形主桌。工作人员沿着圆桌边缘等距离地放置了 $$$N$$$ 把椅子。

晚宴开始前，有 $$$3$$$ 名参赛选手提前进入会场，并从这 $$$N$$$ 把椅子中任意选择了 $$$3$$$ 把不同的椅子坐下。坐定后，其中一人突然问道：

"我们三个人的位置在圆周上恰好构成了一个三角形。在所有可能的选座方案中，有多少种方案对应的三角形是直角三角形？"

现在，请你编写一个程序回答这个问题。

注意：一种选座方案只由最终被选中的 $$$3$$$ 把椅子决定，不区分三名选手分别坐在哪个位置。换句话说，这是一个组合问题，而不是排列问题。

白糖糕是一种流行于南昌民间的传统糕类小吃，起源于明清时期，被誉为"江西五大传统名点"。其特点香糯、柔软、洁白，造型上与一般白糖糕比独具一格，风味独特，深受大家喜爱。Orange_Ice 作为南昌人，从小就很喜欢吃白糖糕。这道菜也是亲朋好友聚会时，饭桌上必不可少的一道甜品。

在 Orange_Ice 的印象中，白糖糕外观是雪白的。然而每次和奶奶提起白糖糕时，作为老南昌人的她总会感慨："现在的白糖糕都是雪白雪白的，我们那时候吃的白糖糕都是带一些淡黄色的，那个才正宗！"

这一说法激起了 Orange_Ice 的兴致，他决定前往南昌老城区——万寿宫、大士院一带，寻找老一辈人吃的正宗白糖糕。

在老城区，Orange_Ice 发现了 $$$n$$$ 家售卖白糖糕的店铺。由于每家店的工艺略有不同，糕点的颜色是深浅不一的。而他无法确定奶奶所说的"淡黄色"究竟长什么样子。为了尽可能找到最正宗的白糖糕，他将第 $$$i$$$ 家白糖糕所带黄色的程度用一个非负整数 $$$a_i$$$ 表示，称为"色泽"，其中 $$$a_i \in [0, k]$$$，数值越小表示糕点越白，数值越大则表示越黄。

由于预算有限，他最多只能购买 $$$m$$$ 家店铺的白糖糕。为了保证无论奶奶心中的那个"标准色"$$$x$$$ 是多少，他都能拿出一块色泽最接近 $$$x$$$ 的糕点，他决定这样规划：他要挑选不超过 $$$m$$$ 家店铺购买，使得最坏情况下（即对于所有可能的 $$$x$$$），手中的糕点色泽最接近于 $$$x$$$ 的值，与 $$$x$$$ 的差距尽可能小。注意：$$$x \in [0, k]$$$，且为整数。

形式化地说，设选定的店铺集合为 $$$S$$$，定义对于任意目标色泽 $$$x$$$ 的偏差为 $$$f(x, S) = \min\limits_{s \in S} |x - s|$$$。目标是求出最小的最坏偏差 $$$ans$$$： $$$$$$ ans = \min_{\substack{S \subseteq \{a_1, \dots, a_n\} \\ |S| \le m}} \left( \max_{x \in [0, k]} \; f(x, S) \right) = \min_{\substack{S \subseteq \{a_1, \dots, a_n\} \\ |S| \le m}} \left( \max_{x \in [0, k]} \; \min_{s \in S} |x - s| \right) $$$$$$

请你帮 Orange_Ice 计算，这个"最坏情况下的最小偏差"是多少？