小J 有一个平面直角坐标系，在这个平面里有一条线段，小J 想要在这个平面里找到一个与这条线段长度相同且相互垂直的线段，请你帮助他找到一条这样的线段。

对一同一平面内的两条线段来说，称它们是相互垂直的当且仅当将两条线段都延长为直线后，两条直线相互垂直。

对于一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个正整数 $$$m$$$，称数组 $$$a$$$ 是好的当存在一个正整数 $$$b$$$，使得所有小于等于 $$$m$$$ 的正整数中，有且仅有在数组 $$$a$$$ 中出现的那些是 $$$b$$$ 的因子。

例如，当 $$$a=[1,2,3],m=5$$$ 的时候就是一个好的数组，因为可以选取 $$$b=6$$$。但是当 $$$a=[2,3],m=5$$$ 的时候就不是一个好的数组，因为当 $$$b=6$$$ 的时候，数组 $$$a$$$ 中缺少了 $$$b$$$ 的一个因子 $$$1$$$。当 $$$a=[1,2,3,4],m=6$$$ 时不能选取 $$$b=4$$$，因为数组 $$$a$$$ 中的数字 $$$3$$$ 不是 $$$b$$$ 的一个因子。

给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个正整数 $$$m$$$，请判断 $$$a$$$ 的每一个前缀是否是一个好的数组。

$$$n$$$ 座山从高到低排成了一条直线，这就是进入低谷的路；不过，现在并不是进入低谷的时候，你可以改变山的高度！！！

在每次操作中：

• 你可以选择任意一座下标为 $$$i$$$ 的山，使得它的高度变成当且高度的 $$$k$$$ 倍。形式化地来说，你可以选择任意一座高度为 $$$a_i$$$ 的山 $$$i$$$，使得 $$$a_i=a_i\times k$$$。

在任何时间，任何地点都有可能陷入低谷。所以请问，在给定 $$$k$$$ 的情况下，对于山的某个区间 $$$l$$$ 到 $$$r$$$ 来说，使得这个区间内的所有山的高度单调不减的操作次数最少是多少。

形式化地来说，给你一个长度为 $$$n$$$ 的单调不增序列 $$$a$$$，在每次操作中，你可以选择一个位置 $$$i(1\le i\le n)$$$，使得 $$$a_i=a_i\times k$$$。那么在给定 $$$k$$$ 的情况下，使得序列 $$$a$$$ 的某个子段 $$$[a_l,\dots,a_r]$$$ 单调不减的操作次数最小值是多少。

提瓦特大陆是一棵树，树上的每个节点从 $$$1$$$ 开始编号，在大陆上的每一个节点中，都有着无尽的知识和宝藏。现在，预言家说，在不久后，在节点 $$$1$$$ 会爆发出一场病毒危机，病毒会沿着树的边不断传播给相邻的节点。假设每一个点都有一个价值 $$$v$$$ 且可以花费 $$$w$$$ 使得该节点无法被感染（包括节点 $$$1$$$）。那么请问，假如可供节点无法被感染的花费总和最大为 $$$c$$$，使用最优的策略，被感染的节点总价值最小是多少？

时之旅人注定是孤独的。

Doctor who 是一位时间旅行者，他经常在宇宙中进行旅行。宇宙中有许多星球，星球是他旅行的目的地。宇宙可以被看作是一张有向图，对于编号为 $$$u,v$$$ 的两颗星球来说，它们之间有一条从 $$$u$$$ 到 $$$v$$$ 的有向边（保证 $$$u \lt v$$$），且经过该边需要经过 $$$w$$$ 的时间（边的长度为 $$$w$$$）。同时，宇宙是在不断变化的，对于一条长度为 $$$w$$$ 的边，这条边仅在时间轴中的 $$$t$$$ 至 $$$t+w$$$ 时间内存在，所以 Doctor who 必须恰好在 $$$t$$$ 时刻从这条边的起点出发。

Doctor who 拥有一个能够穿梭时间的时光机器，该机器只能在某个星球上时使用，且每次进行时间穿梭都需要消耗一定的能量，即存在两个时间点 $$$t_1,t_2$$$ 那么该机器从时间 $$$t_1$$$ 穿梭到时间 $$$t_2$$$ 所需要的能量是 $$$|t_1-t_2|+c$$$（$$$c$$$是一个常数，对于每颗星球来说是不同的），并且使用时光机器后 Doctor who 的位置也不会变。

那么请问，假如 Doctor who 在任意一个时刻可以进行以下三件事之一：

1. 呆在某个星球上不动。 2. 在某条连接两个星球的边上移动。 3. 进行时空穿梭。

且他在 $$$0$$$ 时刻从星球 $$$1$$$ 出发，那么他到达每个星球的时刻加上时光机消耗的能量的总和的最小值分别是多少。

Ambition 出去买饮料了！擅长光速机惨的 nkxjlym 显然不会错过这次机会，他决定进行他的机惨计划，用字符 a 填满 Ambition 电脑里的记事本！

nkxjlym 打开了 Ambition 电脑里的记事本，输入了一个字符 a。接下来，他有两种操作：

1. 花费 $$$v$$$ 秒，全选所有记事本里的文字，复制，并且将光标移动到文本的尾部。 2. 花费 $$$w$$$ 秒，按下粘贴键，将他最新一次复制的所有文本粘贴到记事本中已有文本的末尾。

nkxjlym 知道，要让 Ambition 的电脑死机，至少要在记事本中输入 $$$k$$$ 个字符。

不幸的是，Ambition 走前，为了防止 nkxjlym 机惨他，在电脑里写了一段程序，使得 nkxjlym 进行操作1的时间不是一个固定值，而是 $$$v=rnd()$$$，其中 rnd 是一段随机数程序，每一次调用都会返回一个新的值。

Ambition 马上就要回来了，nkxjlym 想要知道，假如以最优顺序按键，让 Ambition 的电脑死机的时间最短是多少。

以下是这段随机数程序的 C++ 版本和 py 版本。

int rnd()
{
	seed = (1ll * seed * 7 + 13) % mod;
	return seed;
}

def rnd():
    global seed
    seed = (seed * 7 + 13) % mod
    return seed

你获得了一串 $$$n$$$ 个宝石，从左到右排成了一行，其中每颗宝石有自己独特的价值，第 $$$i$$$ 颗宝石价值为 $$$v_i$$$。如果把这串宝石全部卖出去，可以获得所有宝石价值的总和这么多的钱财。

但是聪明的你发现，宝石内部的能量是不稳定的！对于宝石的某个区间 $$$[l,r](l \lt r)$$$，可以从左右两端向内部施加一次碰撞，来改变宝石的能量分布，使得 $$$[l,r]$$$ 内部的所有宝石的价值都变为 $$$v_l \oplus v_r$$$，其中 $$$\oplus$$$ 是二进制异或运算。注意，由于只有一个宝石时无法碰撞，所以要求选择的区间 $$$l \lt r$$$。

你可以任意决定碰撞操作的位置、顺序和次数，请问你能获得的最大价值是多少？

定义一个长度为 $$$n$$$ 的排列 $$$p$$$ 的得分 $$$score_p$$$ 为 $$$\sum_{i=1}^n[(\sum_{j=1}^i p_j)=k\times p_i]$$$，即在 $$$p$$$ 的所有下标中，前缀和是当前位置的值的 $$$k$$$ 倍的下标数量。

给定整数 $$$n$$$，你需要确定一个正整数 $$$k$$$，求出所有的长度为 $$$n$$$ 的排列中，得分的最大值是多少。

一个长度为 $$$n$$$ 的排列 $$$p$$$ 是指从 $$$1$$$ 到 $$$n$$$ 的每个整数恰巧在 $$$p$$$ 中出现一次，例如 $$$[3,1,2]$$$、$$$[1]$$$ 都是排列，但是 $$$[1,1,3]$$$、$$$[3,2,4]$$$ 都不是排列。

小J面前有一个 $$$n\times m$$$ 的棋盘，他手里面还有很多个形如"L"型的拼图，拼图如下图所示：

该拼图可以旋转或反转放入棋盘中

他想问你这个棋盘在拼图不互相重叠的情况下最多能摆多少块拼图。

给你一个以长度 $$$n$$$ 为循环周期的无限长度的正整数序列 $$$a_1,a_2\dots$$$ 和一个质数 $$$p$$$。不仅如此，还有对这个无限长度的序列的如下两种操作：

• $$$1$$$ $$$i$$$ $$$j$$$：对于所有的 $$$k\in N$$$，交换序列中所有的 $$$a_{k\times n+i}$$$ 和 $$$a_{k\times n +j}$$$。
• $$$2$$$ $$$x$$$：求出这个无限长度的循环序列的前 $$$x$$$ 个数拼接$$$^{\dagger}$$$在一起后对于 $$$p$$$ 取模的结果。

$$$^{\dagger}$$$对于两个正整数来说，将这两个数字$$$\it{拼接}$$$在一起意味着把这两个数字像字符串一样从左向右连接到一起，从而得到一个新的正整数。举个例子，将 $$$123$$$ 和 $$$45$$$ 拼接在一起的结果为 $$$12345$$$。

小w 很喜欢 $$$\gcd$$$ 和集合，于是他想出了这道题。但是 小w 还很喜欢看书，出完这道题他就跑去图书馆了。你能帮他解决这个问题吗？

称一个集合的 $$$\gcd$$$ 为集合内所有数的最大公因数。

形式化地，若集合 $$$A=\left \{ a_1,a_2,...,a_n \right \}$$$ ，则 $$$\gcd(A)=\gcd(a_1,a_2,...,a_n)$$$。

特别地，如果集合只有一个数，则它的 $$$\gcd$$$ 是就是这个数，即 $$$\gcd(\left \{ a \right \})={a}$$$。

给定一个大小为 $$$n$$$ 的不可重数集 $$$U$$$，你需要将其划分为 $$$k$$$ 个非空子集，使得每个子集的 $$$\gcd$$$ 的和最大。