亲爱的同学，欢迎参加北京理工大学程序设计新生赛。也许你已经听说过，新生赛是一个卧虎藏龙的地方，有多学了一年来欺负学弟的大二同学，也有高中苦学3+n年的信息学竞赛的大一猛新，完全不给萌新留活路。为了缓解这一现象，好心的出题人lzd特意来向你传授三条宝贵的人生经验：

1、写程序要注意时间复杂度的问题：

你可以在题册上每道题的题目下面看到这一道题的时间限制，你的程序需要在规定时间通过该题。制约程序运行时间的主要要素是循环的次数，一种常用的粗略估算程序运行时间的方法是，忽略循环内具体的语句，只看循环的次数，一般认为$$$1$$$秒内程序可以执行循环的次数为$$$10^7$$$次（含$$$10^7$$$）。对于嵌套的循环，认为嵌套循环的循环总次数为各个嵌套部分的循环次数之积。例如，一个两层嵌套循环，外层循环次数为$$$10^5$$$，内层循环次数也为$$$10^5$$$，则认为总循环次数为$$$10^{10}$$$，且可以看出这一程序显然不能在新生赛通过（该程序会执行1000秒）。

2、注意整数溢出的问题：

以C/C++语言为例，常用的int数据类型能表示的范围只有约$$$2×10^9$$$，可能在一些题目会出现溢出，而long long类型能表示的范围则有约$$$9×10^{18}$$$。

声明一个long long变量的语法：

long long a;

输入一个long long变量的语法：

scanf("%lld",&a);

输入一个long long变量的语法：

printf("%lld",a);

3、被题目忽悠住了的问题：

你可能会觉得，这场比赛的题目看上去都太可怕了，要么看上去题面很晦涩、要么看上去根本无从下手，和乐学上清纯可爱的C语言题目大相径庭。但出题组认为，本场比赛有许多可以让萌新也能通过的题目，希望萌新们不要被题面给忽悠住了，也许你其实会做那道题呢。比如，这题题面就很长很吓人，但其实是个简单题。

下面是本题真正的题面：

一位萌新前来参赛，他做了一道时间限制为$$$m$$$秒的题目，写了一个具有$$$n$$$重循环的程序，请你帮他判断他的程序能否在规定时间能通过该题。为了便于系统判题，你需要回答$$$T$$$个问题。

Master Yi, Mao mao and zyw are good friends. Today they received some candies feed from Mao mao's girlfriend. There are a total of $$$n$$$ packs of candies, and each pack contains $$$2$$$ or $$$3$$$ candies. Now zyw wants to test you, is there a division scheme so that all of them get the same amount of candies. Note that the entire package of candy cannot be taken apart for distribution.

给定整数$$$n,x$$$，你需要构造一个长度为$$$n$$$的序列，序列中每个元素都是不超过$$$x$$$的正整数，且对于任意的区间$$$[l,r](1\le l\le r\le n)$$$满足：$$$a_l\oplus a_{l+1}\oplus ... a_{r-1}\oplus a_r \neq 0$$$。

其中$$$\oplus$$$为二进制按位异或。

  随着信息化时代的发展，外卖业务成为了一片新蓝海。其中，饱了没是一支刚刚起步的新秀，为了开拓市场业务，饱了没发放了非常多的红包...

  Sleep很喜欢点外卖，再他了解到饱了没之后，只恨没有早点发现这个平台，白白损失很多大米。自此，他非常热衷于收集饱了没的各类满减红包。现在他已经选好了一些订单，并且希望在结算的时候花掉一部分满减红包，使自己尽可能少的花钱。显然，每个红包只能在至多一个订单结算中使用(当然也可以不被使用)，每个订单结算的时候只能使用至多一个红包(当然也可以不使用)。在这种情况下，Sleep想知道他最少需要花费多少钱。

  满减红包是在满足满减金额要求的时候获得满减红包面额的优惠。比如$$$50$$$元的待支付订单，可以使用满$$$50$$$减$$$20$$$的红包，然后该订单仅需支付$$$30$$$元，但是该订单不能使用满$$$60$$$减$$$30$$$的红包。

STEPN是一款具有游戏-Fi和社交-Fi属性的Web3跑步软件。用户可以通过装备NFT运动鞋并运动来赚取GST通证。赚取通证时需要拥有能量。每1个能量可提供5分钟的运动收益时间，用户在获得NFT运动鞋后，能量即开始回复。要开始运动赚收益时，用户只需选择一个已所拥有的运动鞋，并按开始（Start）按键即可开始。

对于每一双NFT运动鞋都有四个属性Efficiency（效率），Luck（幸运），Comfort（舒适度）和Resilience（弹性），这些属性除了运动鞋本身的属性外，在升级时，也有额外的技能点供玩家提供。而FriedChicken只对赚取GST感兴趣，这只与效率和弹性有关，经过分析其他玩家的数据发现，每1个能量可以获得的GST的数量为Efficiency^0.49，需要消耗鞋子的耐久度为9.18 × (Resilience^- 0.33) - 1.69，而每消耗1点耐久度，需要花费X个GST进行修鞋。

为了简化这个问题，我们规定：

• 运动消耗的能量是按照分钟为单位计算的（即每分钟消耗0.2能量），不足1分钟的部分不计。
• 你的能量是无限的，你单次运动没有能量限制。
• 每次运动的耐久度会四舍五入的消耗，但每次运动至少消耗1耐久度。
• 效率和弹性值只会是整数。

现在FriedChicken买了一双NFT运动鞋，它的初始属性的效率为E，弹性为R，现在有k个技能点待分配，每消耗1点耐久度，需要花费X个GST进行修鞋。现在请你帮他计算一下，他需要将效率值点到多少，可以让自己的收益（每能量赚取的GST）最大化。

$$$n*m$$$的网格空间中有许多矩形的落石，这些石头只会向下落，并且在遇到其它石头后就会停止（不考虑平衡问题）。请你计算一下石头最终的状态。

海拉鲁大陆上的是一个和平安宁的世界，人们都幸福地生活着。但这天，沉睡百年的灾厄林克苏醒了。他盗取了众神的三角力量，流窜在大陆的各个角落。村庄的花瓶、自然馈赠的果实、安居乐业的猪猪无一幸免，他甚至连呀哈哈的屎都不放过！

作为勇者盖侬的你不想屈居在城堡之中守护塞尔达了，你要主动出击，夺回众神的三角力量！但是三角力量被林克隐藏在地脉中，你首先要知道林克夺取了多少三角力量。

海拉鲁大陆上一共有$$$n$$$个地脉节点，$$$m$$$条地脉。每条地脉连接了两个地脉节点。每当有三条不同的地脉首尾相接时，就说明林克在此隐藏一份三角力量。请你计算一下，灾厄林克究竟盗取了多少三角力量呢？

一般的，给定一个有$$$n$$$个节点，$$$m$$$条边的无向图，请你求出图中有多少三角形。图中的三角形定义为一个大小为三的边集，其中三条边各不相同，且依次首尾相连。

这天，懋懋的女票又给他们投喂糖果啦！但这次zyw不在，只有易大师和懋懋独享这些糖果，它们被懋懋等分成了数量为 n 的两堆糖果 A = [a₁, a₂, ..., a_n] 和 B = [b₁, b₂, ..., b_n]，其中 a_i 和 b_i 为第 i 包糖果的口味（你不知道？糖果口味可多了，有苹果、草莓、菠萝、覆盆子等等）。

现在懋懋想考考你，若易大师吃完前 x 包糖果且懋懋也吃完前 y 包糖果条件下，它们尝过的糖果口味是一样的嘛？等等！zyw表示没吃到糖果很委屈，他想为这题增加难度——如果我重复问 q 次呢？你开始挠头......

Alice和Bob最近在研究象棋。象棋中的马可以走"日"字，即向一个方向移动两格后再向另一个与其垂直的方向移动一格，可以将这种移动方式为表示为(1,2)。为了让游戏更有趣，两人发明了一种加强棋子，其移动方式为(a,b)。

棋盘的大小为n*m，上面有k个点存在障碍物，棋子可以经过这些点，但不能停留在上面。初始时，棋子位于(x0,y0)，保证起点不会有障碍物。Alice先手，两人轮流移动棋子，起点和已经经过的点不能再次经过。最后不能移动棋子的人输。两人共进行t轮游戏，请输出各轮的结果。

Recently, lzd has been learning two-view correspondences and geometry using order-aware network, which is a neural network that infers the probabilities of correspondences being inliers and regresses the relative pose encoded by the essential matrix. The order-aware network contains three novel operations: differentiable pooling layer(a permutation-invariant methods to cluster nodes in a learnable manner and capture the local context), order-aware differentiable unpooling layer(to upsample the coarsened feature maps and build a hierarchical architecture), and order-aware filtering block(to capture the global context with spatial connections). Since the order-aware network achieved the state-of-the-art(SOTA) performance, lzd considers it a good methods and want to share a problem, which is relevant to one of the operation mentioned above, for you to solve.

Shortly, the problem can be refined as:

You are given a matrix $$$A$$$ with the shape of $$$n\times m$$$ and a matrix $$$B$$$ with the shape of $$$m\times m$$$. You can swap the arbitrary(任意) two rows of A and you can do this operation arbitrary times(possibly, 0 times).

Now, the question is that is it possible to make $$$B=A^T\times A$$$, where the $$$A^T$$$ stands for the transpose(转置) of matrix $$$A$$$ and the "$$$\times$$$" stands for the multiplication between two matrix.

当法伊、西格玛、戴安娜第三次次醒来时，发现他们再一次被关在了一个全新的密室中，有了之前几次的经验，他们显得并不吃惊。果然，密室里的小电视里，又出现了零的身影，他沙哑的嗓音也又一次从电视的扬声器中传出："别担心，这次只要玩一个数学游戏，猜中了，你们就可以安全的离开这里"。

"零这家伙，一定又在捣什么鬼，我才不信他会有这么好心。"西格玛喃喃自语道。

游戏的规则是：

使用如下的随机数生成器连续生成n个整数，请你帮忙计算所生成的所有数的最大公约数。

unsigned long long k1, k2, K;

void setSeed(unsigned long long a, unsigned long long b, unsigned long long c) {
  k1 = a;
  k2 = b;
  K = c;
}

unsigned long long xorShift128Plus() {
  unsigned long long k3 = k1, k4 = k2;
  k1 = k4;
  k3 ^= k3 << 23;
  k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
  return (k2 + k4) % K + 1;
}

现在，你知道了代码中的a，b和c，你想知道生成的随机数的前n个数的最大公约数。

你可以使用以下代码获得答案：

unsigned long long solve(unsigned long long a, unsigned long long b, unsigned long long c, unsigned long long n) {
  setSeed(a, b, c);
  unsigned long long res = xorShift128Plus();
  for (a = 1; a != n; ++a) {
    res = __gcd(res, xorShift128Plus());
  }
  return res;
}

众所周知，现在校园里时不时地需要排队做核酸。这天龙龙又要去做核酸了，他发现师生们都严格的按照一米的间隔排队，所以龙龙一眼就看出来所有的队伍都是一样长的。这让急性子的龙龙有些苦恼，他想要尽可能快的做完核酸回宿舍刷题。

可惜这个机构效率比较低，每个人做核酸需要1分钟，而且每个队伍每做一组10个人的核酸就需要花3分钟整理一下物资，才能开始下一组的检测。此时已经做完核酸的lzd过来告诉龙龙，现在所有的队伍都不在整理物资，而且他还告诉龙龙每个队伍在当前这组已经收集了几份核酸样本了。龙龙现在想知道他最少需要花多长的时间才能做上核酸，请你告诉他。