将要读二年级的小 Q 买了一款新型益智玩具——魔幻棋盘，它是一个 $N$ 行 $M$ 列的网格棋盘，每个格子中均有一个正整数。棋盘守护者在棋盘的第 $X$ 行第 $Y$ 列（行与列均从 $1$ 开始编号）并且始终不会移动。棋盘守护者会进行两种操作：

1. 询问：他会以自己所在位置为基础，向四周随机扩展出一块大小不定的矩形区域，向你询问这一区域内所有数的最大公约数是多少。

2. 修改：他会随意挑选棋盘上的一块矩形区域，将这一区域内的所有数同时加上一个给定的整数。

游戏说明书上附有这样一句话“聪明的小朋友，当你连续答对 $19930324$ 次询问后会得到一个惊喜噢！”。小 Q 十分想得到这个惊喜，于是每天都在玩这个玩具。但由于他粗心大意，经常算错数，难以达到这个目标。于是他来向你寻求帮助，希望你帮他写一个程序来回答棋盘守护者的询问，并保证 $100%$ 的正确率。

为了简化问题，你的程序只需要完成棋盘守护者的 $T$ 次操作，并且问题保证任何时刻棋盘上的数字均为不超过 $2^{62} - 1$ 的正整数。

给定正整数 $n,m,a,c,X[0],g$ ，求按照 $X[n+1] = (a X[n] + c) \bmod m$ 生成出的第 $n$ 项 $X[n] \bmod g$ 的值。

数据范围： $n,m,a,c,X[0] \leq 10^{18}$

题面请点击查看全文

给定一个 $n$ 个点，$m$ 条边的无向图，每条边有两种权值： $0$ 或者 $1$ 。

先询问能不能找出一个生成树，使得其中恰有 $k$ 条 $0$ 边，若存在，输出任意一个方案，否则输出 no solution 。

你的面前有 $n$ 个数排成一行，分别为 $a_1,a_2,…,a_n$ 。你打算在每相邻的两个 $a_i$c和 $a _ {i+1}$ 间都插入一个加号、减号或者乘号。那么一共有 $3^{n-1}$ 种可能的表达式。

你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了，所以你还打算支持一个修改操作，可以修改某个 $a_i$ 的值。

你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行，而不是在最初的表达式上进行。

假设目前被延误航班共有 $n$ 个，编号为 $1$ 至 $n$ 。机场只有一条起飞跑道，所有的航班需按某个顺序依次起飞（称这个顺序为起飞序列）。定义一个航班的起飞序号为该航班在起飞序列中的位置，即是第几个起飞的航班。

起飞序列还存在两类限制条件：

• 第一类（最晚起飞时间限制）：编号为 $i$ 的航班起飞序号不得超过 $k_i$ ;

• 第二类（相对起飞顺序限制）：存在一些相对起飞顺序限制 $(a, b)$ ，表示航班 $a$ 的起飞时间必须早于航班 $b$ ，即航班 $a$ 的起飞序号必须小于航班 $b$ 的起飞序号。

小 $\text{X}$ 思考的第一个问题是，若给定以上两类限制条件，是否可以计算出一个可行的起飞序列。第二个问题则是，在考虑两类限制条件的情况下，如何求出每个航班在所有可行的起飞序列中的最小起飞序号。

有 $n$ 件物品，每件物品有三个属性 $a[i], b[i], c[i]$ , $(a[i] < b[i])$ 。

再给出 $q$ 个询问，每个询问由非负整数 $m$ , $k$ , $s$ 组成，问是否能够选出某些物品使得：

• 对于每个选的物品 $i$ ，满足 $a[i] \leq m$ 且 $b[i]>m+s$ 。

• 所有选出物品的 $c[i]$ 的和正好是 $k$ 。

简单版题意：

给定一个 $R \times C$ 的矩形，在其中 $N$ 个位置有随机生成的资源点。现在请你求出在所有的子矩形中，至少包含一个资源点的矩形数量。

有一个长度为 $n$ 的字符串，每一位只会是 $\text{p}$ 或 $\text{j}$ 。求一个最长子串，使得不管是从左往右还是从右往左取，都保证每时每刻已取出的 $\text{p}$ 的个数不小于 $\text{j}$ 的个数。

给定两个数字串 $A$ 和 $B$ ，通过将 $A$ 和 $B$ 进行二路归并得到一个新的数字串 $T$ ，请找到字典序最小的 $T$ 。

给定一个 $n$ 个点，$m$ 条边的无向联通图，每条边的权值均为 $a$。

在原图所有满足 $u$ 节点和 $v$ 节点间最短路为 $2 \times a$ 的点对 $(u,v)$ 间建立一条无向边，边的权值均为 $b$。

给定一个起始节点$k$，求在上述操作后，$k$到所有节点的最短路径。

一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串. 一个串 $P$ 是串 $A$ 的前缀, 当且仅当存在串 $B$ , 使得 $A = PB$. 如果 $P \neq A$ 并且 $P$ 不是一个空串,那么我们说 $P$ 是 $A$ 的一个 $proper$ 前缀. 定义 $Q$ 是 $A$ 的周期, 当且仅当 $Q$ 是 $A$ 的一个 $proper$ 前缀并且 $A$ 是 $QQ$ 的前缀(不一定要是 $proper$ 前缀).

比如串 $abab$ 和 $ababab$ 都是串 $abababa$ 的周期. 串 $A$ 的最大周期就是它最长的一个周期或者是一个空串(当 $A$ 没有周期的时候), 比如说, $ababab$ 的最大周期是 $abab$ . 串 $abc$ 的最大周期是空串. 给出一个串,求出它所有前缀的最大周期长度之和.

可读版题意：

给定 $n$ 个仅包含大写字母的模板串，求所有的长度为 $M$ 且仅包含大写字母的不同字符串中，有多少个包含至少一个模板串。答案对 $10007$ 取模。

对于一个 $0/1$ 字符串，如果将这个字符串 $0$ 和 $1$ 取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如 $00001111$ 和 $010101$ 就是反对称的， $1001$ 就不是。

现在给出一个长度为 $n$ 的 $0/1$ 字符串，求它有多少个子串是反对称的。

可读版题意：

给定 $n$ 个字符串，第 $i$ 个字符串的长度为 $M_i$ ，求每个字符串在所有字符串中出现的次数。

数据范围：$n \leq 100,\ M = \sum M_i \leq 10^6$.